可伸缩视频流的单跳无线网络使用Contention-Based访问MAC协议

文摘

有限的带宽和丢包率高构成严重挑战视频在无线网络应用程序。即使包丢失不存在,带宽波动,由于任意数量的活跃在IEEE 802.11网络流动,可能会极大地降低视频质量。本文旨在提高质量的视频流应用在无线家庭网络通过联合优化视频layer-allocation技术,允许控制算法,和介质访问控制(MAC)协议。使用一个Aloha-like MAC协议,我们提出一个新颖的允许控制框架,这可以看作是一个优化问题,最大化的平均质量承认视频,给定一个特定的最低为每个流视频质量。我们提出一些硬度结果对各种条件下的优化问题和提出一些启发式算法寻找一个好的解决方案。特别是,我们表明,一个简单的贪婪layer-allocation算法可以执行相当不错,虽然它通常不是最优的。因此,我们提出一个更昂贵的启发式算法,保证在一个常数因子近似最优解。仿真结果表明,我们建议的框架可以提高视频质量26%,相比现有的方法。

1。介绍

近年来的爆炸性增长的多媒体无线应用,如视频会议(1]。这个巨大的增长的原因之一是广泛部署的IEEE 802.11无线局域网(无线局域网)在私人住宅和企业网络。尽管这些看似成功的,但许多基本问题在无线网络传输多媒体数据保持相对没有解决。的一个挑战是如何有效地保证指定的视频流量无线网络的带宽。流行的WLAN,特别是分布式协调功能(DCF)在典型的IEEE 802.11 (2)运营contention-based信道访问机制的情况下,不提供一个机制来保证多个并发流的最小带宽。因此,视频应用程序可能会经历重大质量退化由于任意免费入场,大量的流动。然而,点协调功能(PCF)在典型的IEEE 802.11和HCF控制信道访问(HCCA)在IEEE 802.11 e [3)能够提供一个调查访问机制来保证最小带宽。然而,利用色散和HCCA机制,调度器和美联社的排队机制需要控制和调节HCCA的轮询频率和PCF为流动提供所请求的吞吐量。也就是说,本文认为contention-based允许控制方法,类似于Banchs等的工作。4],IEEE 802.11的参数e contention-based模式设置适当,使流动实现他们请求的吞吐量或减少延迟。

允许控制可以防止一个新的流加入网络为了维持一个合理的现有流动的质量。决定接受或拒绝一个新的流请求进入有线链接可以说是容易,相比,无线连接。一个简单的为有线连接接纳控制算法可以跟踪使用的总带宽。然后等于可用带宽使用的链路容量和带宽之间的区别。新流承认如果请求的带宽小于链接的可用带宽的阈值,否则将被拒绝。从理论上讲,同样的算法可以应用到无线连接如果时分多址(TDMA)计划是用来为每个流分配带宽。使用TDMA方案,每个流分配给一组独家时段传输数据,从而消除多用户干扰无线连接。结果,允许控制算法可以精确确定其可用带宽和决定接受或拒绝一个新的流。

然而,这样的协议可能需要一个集中的调度算法,在分布式环境中可能并不可行。因此,现有的介质访问控制(MAC)协议,例如IEEE 802.11,采用随机存取的方法,允许流动争夺渠道有效地共享。IEEE 802.11协议,允许流动实现高吞吐量,同时最小化他们的碰撞。因此,描述浪费带宽的碰撞是特定于一个MAC协议。

例如IEEE 802.11 MAC协议的问题是多用户干扰,也就是说,新流之间的碰撞和现有的流动,减少所有流的吞吐量。这些碰撞数量的增加而非线性的数量竞争流动,承认更难控制算法确定了所有流的吞吐量以做出正确的决定(5]。特别是,对于一个简单的单跳无线网络,来决定是否承认一个新的流程,允许控制算法必须确保至少是可用的带宽Kbps,的总带宽请求包括新流程,然后呢是发生碰撞的开销。而给出的算法,确定吗使用一个典型的MAC协议时是重要的。计算在多次反射无线网络更加困难。

即使一个算法可以确定精确碰撞带宽,它并不总是有利于采用传统录取控制框架,决定承认一个新的流是完全基于带宽和延迟需求的流动。相反,随着视频编码技术的发展,我们认为流入学的标准应该是视觉质量的视频流。即最低录取控制算法的输入是视觉视频流的质量,不是他们的带宽和延迟的要求。前方法假定每个视频编码在特定比特率,因此任何较小的利率提供的网络是不可接受的,因为视频回放经常被打断。另一方面,可伸缩视频编码技术,编码的视频是一个分层的层次结构。因此,可以在不同的传送一个视频比特率(或数字视频层),尽管在不同的视觉品质。这种方法的优点是,大量的流动可以被允许进入网络,只要每个流的视频质量并不低于指定的最低门槛。然后目标是最大化的平均质量承认视频,给定一个特定的最低为每个流视频质量,以及当前的可用带宽。

也就是说,我们的论文旨在提高视频流的质量通过联合应用在无线家庭网络优化的视频layer-allocation技术,允许控制算法,和MAC协议。虽然可以扩展我们的框架来多次反射无线临时环境,为了清楚起见,我们的讨论仅限于单跳无线网络,例如,所有的无线网络主机(设备)在一个家庭或一座小型建筑,每台主机上可以听到所有其他主机的传输。使用一个Aloha-like MAC协议(6),我们提出一个新颖的允许控制框架,这可以看作是一个优化问题,最大化的平均质量承认视频,给定一个特定的最低为每个流视频质量。特别是,使用可伸缩视频流,我们的框架允许更多的流动进入网络,只要每个流的视频质量并不低于指定的最低门槛。然后我们现在一些硬度结果对各种条件下的优化问题,提出两种启发式算法获得一个好的解决方案。我们表明,一个简单的贪婪layer-allocation算法可以执行合理的,尽管它通常不是最优的。因此,我们提出一个更昂贵的启发式算法,保证在一个常数因子近似最优解。

论文的大纲如下。我们首先讨论一些相关录取工作控制无线网络和可伸缩视频编码部分2。节3,我们将描述一个MAC协议结合使用允许控制算法。然后我们制定允许控制框架作为一个优化问题4。节5,我们提供一些硬度结果的优化问题,获得良好的解决方案和相应的启发式算法。仿真结果将给出部分6。然后我们总结我们的贡献,总结我们的论文部分的几句话7。

在互联网上提供QoS流动非常困难,如果不是不可能的,由于其原始设计与大型网络规模。当前设计的地方没有限制数量的流动进入网络,或试图调节单个流的带宽。因此,带宽的多媒体应用在互联网上经常无法保证。为此,许多可伸缩编码技术提出了视频在互联网上传播。可伸缩视频编码技术是用来压缩视频比特流在一个分层的层次结构组成的基本层和增强层(7]。基地层最有助于视频的视觉质量,同时增强层提供连续质量改进。因此,使用一个可伸缩的视频比特流,发送方能够适应当前可用的网络带宽的视频比特率通过发送基础层和适当数量的增强层(8- - - - - -14]。接收者就可以查看视频在一个特定的视觉质量,取决于网络条件。

我们注意到可伸缩视频编码技术可以减轻带宽不足的问题,但最根本的问题是缺乏带宽适应所有的流动。因此,必须使用允许控制。虽然很难实现允许控制大型异构网络,例如,互联网,它可以实现某种形式的控制或调节在小型网络中,例如,WLAN。因此,有很多研究为媒体提供某种形式的QoS交通在无线局域网15- - - - - -21]。最近,引入新的介质访问控制协议的IEEE 802.11 e称为混合协调功能(HCF);夏尔van der et al。22)提出了一个HCF通道访问控制——基于(HCCA)录取控制视频流的应用程序可以同时承认更多的电台。

许多其他现有的无线局域网允许控制算法也被提出。高et al。23)提供了一个允许控制通过使用物理率方案在IEEE 802.11 e。他们使用的长期平均物理利率计算的预订渠道一段时间称为传输机会(TXOP)为每个站然后TXOP的分发给每个人。他们的框架提供了一定程度的承认控制。肖和李24)使用测量提供流保护(隔离)在IEEE 802.11 e网络。他们的算法很简单,但有效。该算法要求接入点(AP)必要的信息以其他无线电台播出。特别是,美联社公布预算的其余的传输时间为每个交通类(有4交通类在IEEE 802.11 e)通过信标帧。类是耗尽的时间预算时,这个类的新流将不会被承认。肖和李的工作设置一个固定限制传输时间为整个会话,导致低带宽利用率,当每个交通类不接近极限。最近,白等。25肖]提高带宽的利用率和李的工作通过动态改变每个类的传输时间根据当前交通状况。还有其他录取控制方案的实现在不同层网络堆栈。例如,巴里et al。26]提出监控通道使用虚拟MAC帧和估计当地的服务水平通过测量虚拟帧。沙et al。27)提出了一个应用程序层允许控制基于MAC层测量使用数据包。Valaee和李28)提出了一种基于服务曲线的录取程序使用探测数据包。乒乓球和摩尔人(29日)和摩尔人(29日]提出允许控制流在IEEE 802.11的QoS策略调整竞争窗口的大小和传播的机会。所有这些允许控制方案不采取的质量流量,尤其是视频质量在我们的框架中,直接考虑。另一方面,我们提倡直接跨层优化的视频质量,同时允许控制算法,和MAC协议,。最接近我们的工作是Banchs et al。4]。因为我们将使用这个方案性能比较,我们讨论推迟到部分6。

3所示。MAC协议

正如前面所讨论的那样,从碰撞浪费带宽的无线网络是不同的,当使用不同的MAC协议。在本节中,我们描述一个Aloha-like MAC协议(6)用于拟议的允许控制框架,旨在最大化承认视频的平均质量,给定一个特定的最低为每个流视频质量。为了对比新的MAC协议的优点,我们首先简要描述现有的IEEE 802.11 e协议contention-based访问模式。

3.1。Contention-Based访问机制

contention-based通道访问计划在现有的IEEE 802.11协议被称为增强型分布式信道访问(EDCA),它定义了一组用于WLAN应用QoS增强通过修改MAC层。主机访问通道,第一感官通道。如果信道空闲时间超过仲裁帧间空间(aif)时间,它开始发送数据。否则,它设置一个倒扣计时器时段之间的随机数在哪里是最小竞争窗口大小。倒扣计时器是由每个空闲时间递减槽后,如果时间和中断传输检测时递减。递减简历时aif的通道又感觉到闲置时间。主机可以开始传输通道一旦它倒扣定时器达到零。如果发生碰撞,也就是说,不承认收到包后很短的时间内,倒扣计时器是随机选择的在哪里重传的次数。实际上,竞争窗口大小为每个传输,以减少一倍的交通负载很高的网络。每次一个主机成功获得渠道,它可以保留一段时间的通道(TXOP)。不同于IEEE 802.11 b, IEEE 802.11 e可以调整传输参数(例如,,、TXOP aif)提供QoS支持特定的应用程序。EDCA能够运行在临时或基础设施模式。

现有的IEEE 802.11协议的优点是带宽效率。基于当前交通状况,每个主机调整利率来实现高吞吐量,同时减少碰撞的数量。另一方面,一个流的速度无法控制精确,除非我们使用PCF或HCCA。通常,这视频应用程序是有问题的。特别是,没有使用PCF或HCCA,波动实现吞吐量可能会发生在现有的IEEE 802.11协议由于他们最大的努力行为。然而,PCF和HCCA需要有这样一个完美的调度程序,以保证实现的所有流的吞吐量。因此,我们主张不同的MAC协议,使用时,会产生一个稳定的流的吞吐量。此外,最好以最少的硬件实现新的MAC协议修改现有的IEEE 802.11设备。事实上,这是可能的。

3.2。提出了MAC协议

在新的MAC协议,竞争窗口的大小不是每个不成功传输的尝试后翻了一倍。相反,根据速度要求由一个主机,它被分配给一个固定的值。所有其他操作是完全相同的IEEE 802.11协议。我们认为适当的允许控制时,消除了一倍在IEEE 802.11协议有助于提高带宽效率因为每个主机的速度不是减少不必要的。我们注意到现有的与EDCA不能精确控制速度由于最好的努力行为。此外,传输参数(例如,,EDCA TXOP aif)不是设计来实现精确率(平均)。这将导致不必要的增加传输速率比较请求率或意想不到的碰撞。然而,我们提出了基于协议能够解决这样的问题争用IEEE 802.11 e。

基于上述讨论,承认控制算法的关键是确定是否存在一组每台主机的年代,满足他们的要求利率没有翻倍年代。为了回答这个问题,我们现在继续新的MAC协议的分析。

我们假设使用预定的包,也就是说,请求发送/清除发送(RTS / CTS)包。RTS / CTS包是用来减少碰撞交通以及消除隐藏终端问题[30.]。主要的思想是把小数据包储备实际数据传输的通道。通过这样做,只有发生碰撞与小的包,因此减少浪费带宽。因为我们假设所有主机可以听到彼此的传输,我们没有隐藏终端问题。我们使用RTS / CTS只是减少碰撞的带宽。

我们的分析是基于time-slotted reservation-based协议类似于Aloha协议,在预订的时间是一个几何分布的随机变量和参数。我们协议和Aloha协议之间的显著差异是我们的网络中的所有主机能够听到对方传输。因此,主人不会试图传播如果确定信道的忙,也就是说,一些主机发送。因此,宿主将试图发送一个RTS数据包的概率只有确定信道的空闲。

与一些概率假设主机传送数据包。翻译传播概率回到IEEE 802.11协议中使用的竞争窗口的大小,连续波可以设置。我们注意,这只是一个近似以来连续波在IEEE 802.11协议不是重置在每一个时间段。为了简化分析,我们进一步假设每台主机上最多只能启动一个流在任何时候。一个简单的概括来支持多个流每个主机是考虑所有流从一个主机作为一个单一的大流量的传输概率。当一个主机成功获得渠道,它选择一个数据包从一个流发送。数据包从一个特定的选择流的概率等于流的吞吐量的比例的总吞吐量流在同一个主机上。这种方法会导致正确的平均吞吐量要求所有的流动。

为一个网络流,我们的目标是确定是否存在一组和每个流,这样所有的流动实现他们指定的吞吐量,考虑到碰撞。由于利率的比例取决于成功的时段,我们首先描述相撞的百分比,成功,和空闲插槽,对每个流的年代。为此,我们表示如下:(我) :空闲插槽的百分比,(2) :成功的百分比RTS流槽(3) :槽相撞的百分比,(iv) :流的吞吐量信道容量的一小部分。请注意,。假设新流传输概率,然后槽,在碰撞发生,新的交通将没有影响。为槽,与概率,它可能会导致冲突。对于一个槽,与概率,它将成为一个槽。否则它保持不变。使用上述的论点,我们可以计算,,在新的流程开始。特别是,新的闲置,相撞,成功的概率可以使用当前的计算,作为在这里,我们表示。同样,我们可以计算成功的概率作为任何现有的流,成功的概率为新流(), 使用上面的公式,我们可以计算出的年代,的年代,的年代流,考虑到传播概率。特别是,以下算法可以用来计算碰撞概率,它将用于以后接纳控制算法。

算法1使我们能够计算出基于给定的传输成功概率精确概率”。另一方面,一个通常要确定传输概率的,考虑到请求的利率从每个流的。自率相应的成功的概率成正比吗现在,我们展示如何计算的基础上的。然后,我们展示如何相关的年代的年代,完成我们的目标。

$C = 计算_C (p_{1}, p_{2}, \dots, p_{N}, N)$
$我 = 1$
$C = 0$
$年代 = 0$
为 $我 = 1$ 来 $N$ 做
$年代 = 年代 \times (1 - p_{我}) + 我 \times p_{我}$
$我 = 我 - 我 \times p_{我}$
$C = 1 - 我 - 年代$
结束了
返回 $C$

算法1

计算

C

,考虑到传播概率

p_{我}

的年代。

原则上,(1)- (3让我们写下一组方程,未知变量在已知的变量的年代,解出的。不幸的是,这些方程不是线性的,因此很难解决。我们提出一个算法来找到的给基于以下的观察。当一个流停止,将增加。如果流重新开始使用相同的传输概率和之前一样,其成功的可能性仍然存在像以前一样。因此,以下方程: 这是真的,因为的概率是空闲插槽不流。因此,在流开始,其成功的概率这也应该等于精确在停止之前,成功的概率。因此,我们有这样的方程对应流。我们也有约束在哪里和是所有的碰撞和成功概率流。我们注意到,是相同的每一个方程,因为它的概率是空闲插槽当所有流动是活跃的。现在,我们可以解出未知,为,一个用于。解决这个组方程很简单因为每个方程是线性的(除了5)。方程(5)是非线性的因为和多项式的的结果(1)- (3)。然而,(5)将作为一个约束。自系统,可以尝试不同的值从大到小,也就是说,1 - 0。为每个值,我们计算的根据(4)。所有的然后输入算法1来计算。然后,我们测试是否约等于1。如果是这样,我们有一个容许集的解决方案。如果没有,我们增加通过一个小值和重复的过程。如果该算法不能找到的整个范围不存在,那么解决方案。这表明无效的年代。

通常情况下,的,不是的年代,。因此,使用上面的过程中,我们首先计算的方面通过最少的改动。从IEEE 802.11 e标准,我们的框架使用IEEE 802.11 e帧格式和计时图如图1。信道是空闲一段时间后等于一个分布式帧间空间(dif)时间槽,而不是倒计时在开始一个新的传输之前,主机发送RTS的概率保留共享信道。这意味着我们组一样的一个典型的IEEE 802.11标准(2]。因为所有主机可以倾听对方传输,碰撞会发生只有当有多个主机启动RTS在相同的时间段。否则,主机成功保留通道,那么主机可以开始传输TXOP时段没有进一步的碰撞。主机检测不成功传输的RTS如果没有CTS dif时间段内到达。注意,主机需要等待很短的时间内(sif)称为短帧间空间之前发送ACK如图1。公平地说在所有的交通流相同的类(3),也就是说,视频流,每个人都使用相同的TXOP那里。

假设后时段,大,我们观察到有吗成功的RTS和传输为每个流槽的数据传输。然后根据定义,我们有在哪里可以被认为是主机吗的请求带宽的信道容量的一小部分,和是流动的数量。如果通道容量BW,传输速率可以这样计算。例如,如果通道容量(BW) 54 Mbps,和主机请求率(27岁)Mbps。

使用(6),考虑到指定的利率的,一个人可以计算相应的的,然后使用在以下算法来确定传输概率的,如果有这样的的年代。

我们注意到对于每个失败的RTS传播,我们浪费通道等于时间槽。另一方面,每一个成功的RTS传输只使用RTS时段。此外,算法2明确认为相撞的百分比,成功,空闲插槽对RTS传输,以保留通道。这将导致总在哪里接近(或等于)1。我们现在描述我们提出允许控制框架。

$(p_{1}, p_{2}, \dots, p_{N}, 成功] = 计算_p (R_{1}^{'}, R_{2}^{'}, \dots, R_{N}^{'}, N)$
$ϵ = 0.01$
$我^{'} = 1$
${我^{'}$ 空闲插槽的百分比吗 $}$
$search_step = 0.01$
$成功 = 0$
为 $我 = 1$ 来 $N$ 做
${年代}_{我} = \frac{R_{我}^{'}}{TXOP \times (1 - \sum_{我 = 1}^{N} R_{我}^{'})}$
结束了
而 $我^{'} < 1$ 做
为 $我 = 1$ 来 $N$ 做
$p_{我} = \frac{{年代}_{我}}{我^{'} + {年代}_{我}}$
结束了
${$ 运行算法1计算碰撞概率 $C}$
$C = 计算_C (p_{1}, p_{2}, \dots, p_{N}, N)$
$总 = 我^{'} + C (即时战略游戏 + dif) + \sum_{我 = 1}^{N} {年代}_{我} (即时战略游戏)$
${$ 检查边界条件更小 $ϵ$ 导致更高的精度 $}$
如果 $(腹肌 (总 - 1) < ϵ)$ 然后
$成功 = 1$
$返回 (p_{1}, p_{2}, \dots, p_{N}, 成功]$
如果
$我^{'} = 我^{'} - search_step$
$e n d w h 我 l e {$ 找不到 $p$ , $成功 = 0}$
$返回 (0,0, \dots 0, 成功]$

算法2

计算

p_{我}

考虑到的

R_{我}^{'}

的年代。

4所示。允许控制框架

4.1。体系结构

由于典型的小型单跳网络,我们承认控制算法在AP或民选主机运行。我们假设所有主机是协作。即每个主机遵循入学协议操作如下。

为简单起见,在本文中,我们假定没有cross-traffic以外的任何类型的视频。一般来说,以适应其他nontime敏感交通在拟议的框架中,一个或许可以设置最小交通吞吐量要求。每台主机可以发送视频和接收从互联网,或者他们可以彼此发送视频。当主机要注入新的视频流网络,它首先请求加入网络通过发送消息给美联社。对于视频应用程序,该消息可能包含率失真的视频,它指定不同的变形量和相应的层数。消息还包含一个视频的最大允许变形。注意,对于实时视频应用程序,率失真通常提前不知道,但可以估计。也就是说,本文的重点将在流媒体应用程序。在收到请求时,美联社(或一些当选主机)将允许控制算法产生一组传输概率对每个流的年代最大化的平均视觉质量流,给出每个视频的最大变形的水平和整体带宽约束。如果存在这样的传输概率,美联社将广播传输概率所有主机的年代。

在接受美联社的指示,每台主机开始传输数据包的概率(或大约设置其竞争窗口观察到信道空闲的时候)。每个传输概率对应于一个特定的速度(或层数)。如果没有可行的传输概率,美联社将通知新的流无法加入网络。

4.2。问题公式化

我们现在能够制定率失真优化问题的多个分层视频流在带宽和失真约束。我们注意到,单位时间内平均吞吐量和传输速率对于一个流可以通过设置它的传输概率。对每个人来说都有足够的带宽时,将大的值,这样所有的层视频流将被发送。当没有足够的带宽,例如,由于太多的流动,从某些视频层下降导致平均失真最小的所有视频。对于一个简单的场景,我们假设没有数据包在传输过程中丢失。传输速率为流视频传输层的数量成正比吗。

摘要研究优化问题是选择最优数量的视频层传输的主机(或流),同时最大化整个视频质量。此外,包含术语的带宽开销由于信道争用访问(碰撞和预约带宽用于RTS / CTS包)让我们优化问题不同于其他优化问题。特别是,通过给指定的问题是:对于每一个主机,一个函数使用时,给出了减少失真在主机层,速度函数出所需的传输带宽从主机层,一个开销函数让消耗的带宽开销(例如,由于信道争用)对于一个给定的层分配给主机,下界的减少失真用,最后一个在总带宽BW绑定。考虑到这些数量,优化问题如下:

我们必须找到最优层分配给每个主机,最大化的减少总失真受带宽和局部最小值减少失真约束。特别是,存在一个解决方案,如果我们能计算出一组传输概率对应的最优分配层的每一个人。一个必要条件是,每个流要求最大限度地减少总失真至少。然而,选择层的方式取决于我们使用的图层选区的策略(如贪婪算法、详尽的搜索)。注意,传播延迟和处理延迟可以忽略由于操作在单跳网络中。然而,延迟变异或抖动可能会影响协议的性能。吞吐量抖动的详细分析讨论部分6.3。接下来,我们将研究的计算属性图层选区问题,表明在一般是计算困难的问题,在某些合理的条件下,一个简单的贪婪layer-allocation算法可以保证执行接近最优。

5。层优化的计算复杂度

在本节中,我们研究上述层分配问题的计算复杂性,显示硬度结果和条件最优近似解可以保证在多项式时间内。我们的优化问题是不同于其他大多数带宽开销的优化问题的包容在带宽约束。因此,现有的算法和复杂性的证据并不直接适用于我们的问题。下面,我们首先考虑解决问题最佳的复杂性,然后我们考虑有效的近似算法。

5.1。计算最优解

在这里,我们分析问题的计算复杂性类在前一节中给出的形式。我们首先声明三个假设优化问题和考虑这些假设的复杂性在不同子集。

假设1。统一的加息每级:

假设2。收益递减:

假设3。不变的开销:

下面,我们也会参考这意味着添加剂的性质开销个人可以被分解为一笔开销函数。也就是说,

直观地,第一个假设状态量的增加率函数是常数在所有层的流。第二个假设,在一个特定的流,更高的层次可能永远不会减少失真比低层次。因此,它永远不会是这样,一个流必须包括许多下层低失真减少为了得到大变形减少在更高的层。第三个假设,给出特定层跨层分配,增加任何层由一个生产函数相同的增加开销。这意味着开销函数是公正的递增的特殊流和当前层数分配给流。

我们的第一个结果是,考虑到以上三个假设(8)- (10),我们可以使用一个有效的解决优化问题的贪婪layer-allocation算法。该算法所得如下。(1)对于每一个流,我们初始化层数到最小的这样。如果由于某种这是不可能的,然后返回“无解”。(2)如果不能增加任何流的层数在不违反带宽约束然后终止,返回当前层数。换句话说,它是不可能找到一个可行的传输概率每个主机使用的算法2节3。(3)增加层数的流1,流流,当增加产生最大的减少失真在不违反带宽约束。

命题1。贪婪layer-allocation算法是最优的任何问题,假设1,2,3持有。

证明。我们首先介绍一些符号。我们将使用一个分配向量指定层分配每一个主机在哪里是主机的总数。我们将表示,减少失真造成分配向量。一层增量序列是一个序列的指数,表示层的顺序递增终于到达一个最终分配向量在层的总增量。
注意,不变的开销和统一的加息,层中的每个增量计数结果完全相同的带宽的增加。这意味着所有最优层分配会满足对于一些价值。也就是说,所有最优层分配将是一个确切的结果增加层数。因此,寻找最优层分配相当于找到一个长度一层一层增量序列结果最好的分配从零配置。
现在,考虑任何层分配,让的指数选择的主机将从贪婪算法,让产生的失真减少贪婪的一步。现在考虑任何层增量序列从导致分配向量。我们说序列是一个最优一步一步的完成如果该值的是最大可能从什么时候和递增层。
我们的索赔,总有一个最优的关键一步一步来完成包括一个增量。认为这并非如此,上述序列最优的完成,这意味着它不包含一个增量。我们表明,这导致矛盾。首先,让等于减少失真添加后产生的th层增量和注意等于这个序列的总和。收益递减的假设,我们有对所有。这是真的,因为贪婪算法选择指数最大的减少失真在所有层,从而进一步减少造成任何层不得大于递增,否则将违反收益递减。从这一点上考虑新图层增量序列,让应用这个序列开始的结果相等。它可以很容易地验证,这是一个合法的序列,而相应的减少失真序列=。自只是这个序列的和我们知道吗这意味着。因此,我们展示了一个最优一步一步完成,其中包括一个增量,提供一个矛盾。
使用上面的事实,它是直接显示通过感应的贪婪的步骤贪心算法总是保持最优一步一步的完成空集,完成了证明。

我们现在考虑在命题2- - - - - -4这个问题的复杂性,当每个上面的假设之一是取消。

命题2。的一类决策问题的假设2和3持有但假设1不会是np完全即使限制开销常数零函数。

证明。我们的问题显然是NP,可以列举可能的层分配和检查他们在多项式时间内。每个证书layer-allocation polynomial-size暗示中的决策问题是NP。显示np困难,我们从0 - 1背包问题减少。更正式,0 - 1背包的实例是一个4-tuple所示在哪里和,并给出的价值和成本项,是价值目标,是限制成本。我们将形成以下版本的问题在哪里,,对所有输入。也就是说,我们只有一个层分配。减少失真,功能层是相等的和分别为0 - 1背包问题。请注意,这个问题并不满足恒定速率增加可以为每个不同。然而,它满足的假设2和3非常。这是直截了当的表明layer-allocation问题给出的答案(13)将“是”当且仅当相应的答案是“是的”0 - 1背包问题。

命题3。的一类问题的假设1和3持有但假设2不会是np完全即使限制开销常数零函数。

证明。问题是NP和上面同样的理由。为了这个问题,我们将只考虑0 - 1背包问题的整数值,,,。我们可以不失一般性,因为我们总是可以将所有的数字乘以10的适当的力量。给指定的0 - 1背包问题的一个实例(12),我们减少构造以下层分配问题: 在哪里为,,,。这里的直觉是,我们有许多层在每一个流,但只有最后一层实际上降低了失真。这种行为违反了假设2。每一层增加了一个单位的带宽满足的假设1开销是零,这满足的假设3。还请注意,流动的层数是。为了减少失真,我们必须支付的带宽,这与0 - 1背包问题。
鉴于这种减少,这表明有一个“是”的答案所构造的层分配问题如果有一个“是”的答案的0 - 1背包实例。

最后,我们表明,假设3在某种意义上也是必要的。特别是,当它把问题变成了计算困难即使限制类添加剂开销的问题。

命题4。的一类问题的假设1和2持有但假设3不会是np完全即使限制添加剂开销。

证明。这里我们只考虑整数背包问题。给定的整数0 - 1背包问题的一个实例,我们构造以下实例层的分配问题: 在哪里,,在哪里为和。我们这里有报酬递减的属性,因为对于每一层我们添加单个单位减少失真。我们有非常恒定带宽属性。但是我们没有自当我们移动一层不变的开销从0到1的增加。只有函数占用带宽,因为所有的开销率等于零。鉴于这种减少,很容易验证有一个“是”的答案到0 - 1背包实例是否存在一个“是”的答案所构造的层分配问题。

这些复杂性的结果表明,如果我们一起删除任何三种假设,因此成为赋权的问题是不可能解决一个高效的算法,尤其是贪婪算法。结果还表明,这是真的,即使我们严格限制开销函数的形式。即使开销添加剂,所表现出的问题是困难的命题4。

在实践中,常常可能满足的假设1和2。不幸的是,我们可以表明,开销函数产生在我们的协议不是不变的根据的假设3,因此一个有效的最优解仍是不可能的。

命题5。拟议的MAC协议的开销不是不变的。

证明。我们将表明,提出的MAC协议的开销不不变的矛盾。假设带宽开销、带宽参与预订,是不变的,那么在哪里和表示的开销增加造成的个基点(一层)流和流,分别。自,我们有在哪里和表示空闲时段增加造成的个基点到流和流,分别。特别是,添加个基点到流增加的结果通过。我们可以代表而言,作为也就是说, 扩大双方的产品(19),所有产品条款,除了一个或将被取消,导致自,(20.)是正确的如果。自成正比,这意味着为了实现,当前发送的任何两个视频必须相等。这是不正确的,因此提出了MAC协议的带宽开销不是不变的。

5.2。计算近似解

上面的三个假设,假设2收益递减,是最有可能在应用程序设置感到满意,因为大多数编码方案表现出收益递减的行为。假设1,统一的利率增加,也会经常感到满意,虽然它会排除非均匀速率编码方案。假设3不变的开销,正如我们所看到的是违反了我们的协议,我们不知道其他协议,满足的假设。在这种情况下,有趣的是考虑如何从理论上说只有假设2是满意的。我们知道从命题2和3一般来说问题是np难解决最佳只有假设2,然而,这并不排除的存在有效的近似算法。

事实上,使用略微修改了贪婪layer-allocation算法,我们可以得到一个解决方案保证内部的一个因素从最优解决方案。我们现在描述第一近似算法。

5.2.1。Double-Greedy算法

该算法是基于最近的结果(31日]。我们考虑一个修改版本的原始贪婪算法,在每一步,而不是添加视频层大多数增加减少失真,我们添加层,达到减少失真的最大比例的增加带宽,提供添加没有违反总带宽约束BW。为每个迭代,我们添加层以减少失真的最大比率增加带宽,这样总使用带宽小于BW。重复迭代,直到没有视频可以被添加到网络层在不违反带宽约束。因此,它可以表明,甚至这个修改算法可以产生任意贫穷的结果相比,最优的解决方案。然而,如果一个返回找到的最好的解决方案最初的贪婪算法或改进贪婪算法,可以保证一个近似的因素之一。我们将调用这个算法<我>double-greedy算法。

这表明通过增加计算时间两倍在原来的贪婪算法(即。,wemust now run both greedy and modified greedy), it is possible to achieve a nontrivial approximation bound. (Technically, it is not necessary to run the full greedy algorithm in order to achieve the approximation bound. Rather, one needs to only run the original greedy algorithm for one iteration (i.e., selecting the best single element of the set) and then to return the maximum of the best single element and the result of the modified greedy algorithm. The results of<我>double-greedy保证至少一样好,往往更好,但计算时间的增加)。

5.2.2。Triple-Greedy算法

事实证明,通过增加进一步计算,但剩下的多项式时间,可以提高近似绑定为约束优化问题,比赛结果为无约束问题,作为证明(31日,32]。新算法简单地列举了所有三元组的连续层,用每个流,不违反带宽约束BW。对于每一个三,该算法运行修改后的贪婪算法初始化设置然后返回一组在所有三元组的实现的最高比率减少变形的增加带宽。该算法增加了运行时的一个因素超过原来的贪婪算法,但收益率更近似的结果。我们有下面的结果。

定理1。的和算法实现一个常数因子近似范围和,分别。

证明。由于空间的限制,读者被称为细节证明以上结果的完整技术报告(33]。

6。仿真结果

在本节中,我们提供了一个综合评价的提出了在单跳网络中视频优化框架。特别是,模拟提供视频流的视觉质量,以均方误差(MSE),当进气控制采用结合不同的层分配算法和提出的MAC协议。感兴趣的层分配算法是最优的,相等的速率,贪心,贪心算法的两倍。我们故意省略结果以来triple-greedy算法在我们的模拟,他们观察到double-greedy算法是相同的。这也许表明,典型的视频的比特率和失真水平层,double-greedy算法足以获得一个很好的解决方案。

我们注意到最优算法使用了一个详尽的搜索方案。也就是说,它检查视频层的所有可能的组合和选择的结果在最低的失真,即最小MSE满足带宽和失真约束。因此,最优算法是非常昂贵的数字视频层和主机是巨大的。最优算法,然而,产生最小MSE和因此用来评估的其他算法。平等率算法将等量的带宽分配给每一个视频(主机),一层一层地以循环方式,直到限制总带宽不再是满足使用。贪婪、双贪婪算法之前章节中描述5。1和5。2,分别。

在我们所有的模拟中,我们使用两套标准的视频资料,每组由三层视频,如表所示1和2(7,34- - - - - -37]。根据场景,模拟可能使用一个或两组视频资料。

层 Akiyo 海岸警卫队工头

比特率(Kbps) 失真(MSE) 减少失真(MSE) 比特率(Kbps) 失真(MSE) 减少失真(MSE) 比特率(Kbps) 失真(MSE) 减少失真(MSE)

1 64年 - - - - - - - - - - - - 32 123.90 - - - - - - 64年 - - - - - - - - - - - -

2 128年 83.77 - - - - - - 112年 103.06 20.84 128年 71.30 - - - - - -

3 192年 63.54 20.23 160年 87.72 15.34 192年 56.63 14.67

4 256年 50.48 13.06 208年 78.18 9.54 256年 46.03 10.60

5 320年 38.29 12.19 256年 71.30 6.88 320年 39.18 6.85

6 384年 32.59 5.70 304年 65.03 6.27 384年 33.35 5.83

7 448年 27.74 4.85 352年 57.95 7.08 448年 29.05 4.30

8 512年 23.61 4.13 400年 51.65 6.30 512年 25.89 3.16

表1

标准视频个人资料我。

层领班1 (FGS-temporal可伸缩性模式) 海岸警卫队(投篮) 领班2 (FGS-AFP模式)

比特率(Kbps) 失真(MSE) 减少失真(MSE) 比特率(Kbps) 失真(MSE) 减少失真(MSE) 比特率(Kbps) 失真(MSE) 减少失真(MSE)

1 140年 57.03 - - - - - - 110年 60.68 - - - - - - 384年 42.96 - - - - - -

2 240年 33.05 23.98 160年 51.65 9.03 512年 31.12 11.84

3 340年 21.89 11.16 240年 43.96 7.69 640年 26.43 4.69

4 440年 16.30 5.59 300年 38.29 5.67 768年 22.55 3.88

5 540年 11.46 4.84 360年 31.12 7.17 896年 19.19 3.36

6 640年 8.67 2.79 420年 26.48 4.63 1024年 17.91 1.28

7 740年 7.24 1.43 490年 24.16 2.33 1152年 15.96 1.95

8 840年 5.87 1.37 590年 20.56 3.60 1280年 14.22 1.74

9 940年 4.59 1.28 730年 17.50 3.06 1408年 13.27 0.95

10 850年 14.89 2.61

11 900年 11.56 3.33

表2

标准视频第二个人资料。

6.1。协议的评估

我们第一次比较的性能提出了对标准IEEE 802.11 MAC协议不允许控制(2)和IEEE 802.11 e与录取控制。特别是,IEEE 802.11 e与进气控制,我们用Banchs提出的机制等。4]。这种机制有点类似我们的,在某种意义上,每一个流通过设置竞争窗口实现其吞吐量一个适当的大小。对于我们的提议MAC,我们可以近似。最根本的差别,然而,在制定导致两种不同的算法,因此不同的行为。在IEEE 802.11 e与进气控制,Banchs等人制定了允许控制过程的总吞吐量最大化所有的流动受到限制为每个流的相对吞吐量。特别是,该算法试图争用窗口的设置值为每个流的方式最大化,同时确保在哪里,,流的数量,吞吐率的流,分别和一组给定的需求。注意,我们随机选择作为一个参考。作为一个直接结果,每个流获得的吞吐量可能高于指定的,特别是当指定的总吞吐量比网络容量小得多。另一方面,我们的算法产生精确指定为每个流率。很快将会解释,能够精确地控制速度将使一个有效的跨层优化。

我们的模拟器是一个完全时间驱动,项目基于模拟器用MATLAB编写的。它的目的是模仿尽可能接近真实的操作使用所有关键参数在IEEE 802.11协议。指定的参数的模拟,对跳频扩频(FHSS) PHY层1 Mbps的通道容量表所示3。我们注意到,IEEE 802.11 e包含2字节的QoS场除了IEEE 802.11。我们还假设处理和传播延迟是零。

参数价值

数据包的有效载荷 1500个字节

MAC头( ${MAC}_{hdr}$ ) 36字节

PHY头( ${体育}_{hdr}$ ) 16字节

即时战略游戏 $20. 字节 + {体育}_{hdr}$

CTS $14个字节 + {体育}_{hdr}$

消 $14个字节 + {体育}_{hdr}$

信道容量(BW) 1 Mbps

槽时间 50微秒

sif 28微秒

dif 128微秒

即时战略游戏时间 $(即时战略游戏 / BW \times 8 \times 10^{6}) + dif$ 微秒

表3

FHSS系统参数对IEEE 802.11 e用于获得计算结果。

我们第一次显示仿真结果组成的单跳无线网络3主机。每个主机发送一个视频到其他主机在一个有限的信道容量(BW) 1 Mbps。这些流假定为在同一交通类。的最小流吞吐量要求1 ()和2 ()被设置为200 Kbps, 300 Kbps,分别。流的最小吞吐量3 (从115 Kbps)增加线性370 Kbps的步长15 Kbps。IEEE 802.11 e与进气控制,的设置根据标准IEEE 802.11的接纳控制算法而不允许控制,和分别设置为15 - 1023。

数据2(一个)- - - - - -2 (c)显示观察吞吐量IEEE 802.11不允许控制,IEEE 802.11 e与进气控制,我们提议允许控制的函数3流的吞吐量。看,标准IEEE 802.11执行当总请求的吞吐量比网络容量小。然而,不允许控制流3不能实现其请求的吞吐量超过320 Kbps。另一方面,IEEE 802.11 e与录取控制执行得很好,每个流的吞吐量持续高于其指定的最低要求。与IEEE 802.11 e,我们提议允许控制产生一个精确的要求为每个流吞吐量。因此,碰撞率(浪费带宽)远小于标准和IEEE 802.11 e如图2 (d)有用,即使总吞吐量大约在这两个方案都是一样的。这是一个使用该MAC协议的优势。毫不奇怪,我们的算法的总带宽使用情况远小于其他协议如图2 (e)为一组特定的利率。

(一)

(b)

(c)

(d)

(e)

图2

为拟议中的协议性能比较和IEEE 802.11和IEEE 802.11协议。(一)吞吐量流1,(b)吞吐量流2,(c)吞吐量流3,(d)整体碰撞(e)整体带宽使用情况。

我们现在展示的性能提出contention-based MAC协议时大量的主机争夺共享介质。具体来说,我们模拟一个场景组成的30主机,54 Mbps带宽容量设置。每个主机注入一个流。流的吞吐量1 (从120 Kbps)增加线性460 Kbps的步长20 Kbps。流的吞吐量2 (从80 Kbps)增加线性590 Kbps的步长30 Kbps。剩余的流(),其吞吐量需求设置为200 Kbps。指定的参数直接序列传播spectrum-orthogonal频分多路复用(DSSS-OFDM) PHY层长序言PPDU格式如表所示4。在这个模拟,和控制数据包(RTS / CTS / ACK)仅发送1 Mbps,而全速率发送数据部分的54 Mbps。

参数价值

数据包的有效载荷 1500个字节

编码率 3/4

MAC头( ${MAC}_{hdr}$ ) 36字节

PHY头( ${体育}_{hdr}$ ) 32个字节

即时战略游戏 $20. 字节 + {体育}_{hdr}$

CTS $14个字节 + {体育}_{hdr}$

消 $14个字节 + {体育}_{hdr}$

信道容量(BW) 54 Mbps

槽时间 20微秒

sif 10微秒

dif 50微秒

即时战略游戏时间 352微秒

表4

DSSS-OFDM系统参数对IEEE 802.11 e用于获得计算结果。

数据3(一个)- - - - - -3 (d)显示观察吞吐量IEEE 802.11 e因使用我们提出的允许控制流量的函数1的吞吐量。见过,他们都实现所需的吞吐量。然而,请注意,因为部分和控制数据包发送速度慢得多(1 Mbps),这将导致低的整体数据部分,如图3 (e)。同时,我们提出的碰撞率协议是约1%的总带宽使用时信道容量的90%。图3 (f)代表每个主机的传输概率相应请求的吞吐量。见,我们提出了MAC协议执行相当不错甚至在网络竞争与大量的主机。

(一)

(b)

(c)

(d)

(e)

(f)

图3

提出的协议验证30流过54 Mbps带宽。流1和2 (a)吞吐量,(b)吞吐量为3 - 10流动,(c)吞吐量流11日至20日,(d)吞吐量为21 - 30流动,(e)整体带宽使用情况,(f)传输概率。

我们现在显示仿真结果应用跨层优化传输3视频时流。首先,提供一些关于之间的交互的直觉提出MAC协议和部分中描述的层分配算法5。2。具体来说,我们目前的仿真结果对各种物理量,例如,吞吐量、传输概率,当使用一个简单的贪婪的层分配。仿真参数如表所示3。因为所有视频流在同一个交通类,他们使用相同的TXOP那里。我们使用标准的视频概要集我模拟。图4(一)显示不同的视频流的平均吞吐量增加与规范化的带宽使用情况。从左到右,图中的每个点代表一个额外的层被添加到一个视频根据贪婪算法。最右边的点表示为每个视频最后的层数。添加一层每个图此时将违反任何视频带宽约束。换句话说,通过添加一个新图层,算法2节3将无法找到一组传输概率,满足所有的视频的请求率。我们注意到,在这一点上,总带宽使用率为95%,表明一个相对高带宽利用率。

(一)

(b)

(c)

(d)

(e)

(f)

图4

$年代$ $我$ $C$ $年代$ 使用贪婪算法性能结果。吞吐量(a)、(b)传输概率;(c)的百分比槽,(d)的百分比,,槽,在MSE (e)变形,(f)率失真特性。

图4 (b)显示了每个主机的传输概率的函数归一化的带宽使用情况。正如预期的那样,随着层数的增加对每个视频,他们传播概率也相应增加,以确保数据传输的机会更高。有趣的是,传播概率几乎成倍增加,以弥补整体吞吐量大约线性增加。图4 (c)显示了成功的比例相应增加槽(超过的nondata名额)不同的视频流,直接导致传输概率的增加。

然而,随着传输概率的增加,碰撞插槽的比例也大幅增加,如图4 (d)。当然,空闲插槽的比例相应减少。同意我们的直觉关于拟议的MAC协议。我们注意到,通过使用这种MAC协议,一个是能够控制的速度流恰恰通过调整其传输概率。反过来,这些利率控制的视觉质量的视频流。图4 (e)显示了视觉质量的三个视频流的MSE的函数归一化带宽使用。在这种情况下,贪婪算法,最小化总均方误差给出了所有的流的带宽限制,收益率的MSE 38, 71年,并为Akiyo 46,海岸警卫队,分别和工头序列。图4 (f)展示了各种包类型的实际带宽百分比。见过,只有最小的带宽开销(2%)发生在使用RTS 36字节和1500字节数据包的有效载荷。

6.2。层分配算法性能

我们现在展示不同的层分配算法的性能。为简单起见,我们假设没有包丢失。此外,通过使用标准的视频资料h / SVC在桌子上1,我们要求失真水平(MSE) Akiyo,海岸警卫队,和领班不能大于63,103人,分别为56。选择模拟,这些均方误差值相当随意,但在实践中用户可以指定他或她的视觉质量要求。数据5(一个)和5 (b)显示扭曲导致视频资料表的使用不同的算法1和2,分别。对于表2工头,最大变形要求1,海岸警卫队,51岁,和领班2 21日和31日。正如预期的那样,最优算法(穷举搜索)总是产生最低的失真,尽管它有最高的计算成本。

(一)

(b)

图5

1 2 失真表现不同的算法(a)视频资料表,(b)视频资料表。

图5(一个)表明,贪婪的表演和双贪婪的视频资料表都是相同的1。在0.8 Mbps,贪婪和双贪婪算法无法找到最优的解决方案。然而,贪婪的表现,双贪婪的,和最优算法都是相同的通道容量的1 Mbps和1.2 Mbps。这表明,贪婪和双贪心算法在实践中也许就足够了。正如所料,等于速率算法执行最差,因为它甚至不尽量减少整体变形。

另一方面,数字5 (b)表明,贪婪算法未能找到两个实例的最优解(Mbps和2.4 Mbps)。相比之下,通常双贪婪算法找到最优的解决方案。然而,这是没有保证的double-greedy算法不收敛到最优解Mbps。我们注意到部分中描述5。2算法的计算成本double-greedy贪婪算法的两倍,因为它必须运行贪婪的和改进的贪心算法和选择最好的一个。修改后的贪婪算法基本的贪婪算法,在每一步,而不是添加层大部分减少失真,我们添加层,达到最大的比率减少畸变层的比特率,提供添加层没有违反带宽约束。修改后的贪婪算法可能会也可能不会产生一个更好的解决方案比贪婪算法。贪婪和修改算法可以产生任意糟糕的解决方案,而double-greedy算法,它返回最佳解决方案(低失真)的贪婪和修改贪婪算法,保证它的解决方案是一个常数近似系数最优解决方案。

表5和6显示详细信息与不同的算法的相关视频资料I和II,分别。可以看到,最优算法总是最低的失真。在所有情况下,带宽开销相对较小,表明框架的能力来有效地利用带宽。注意,还有一些其他的带宽开销(例如,,sif dif,应答),8 - 10%的总带宽。

失真规范化的带宽使用情况(%) 传播艾滋病的可能性

(MSE) 总开销 $年代$ 开销 $C$ 吞吐量其他人 Akiyo 海岸警卫队工头

最优解 129.12 98.47 2.11 0.07 87.86 8.43 0.0215 0.0269 0.0215

贪婪的 129.12 98.47 2.11 0.07 87.86 8.43 0.0215 0.0269 0.0215

修改后的贪婪 129.12 98.47 2.11 0.07 87.86 8.43 0.0215 0.0269 0.0215

双贪婪的 129.12 98.47 2.11 0.07 87.86 8.43 0.0215 0.0269 0.0215

相等的速度 135.42 93.56 2.00 0.02 83.52 8.02 0.0046 0.0051 0.0046

表5

详细信息与视频资料我不同的算法(Mb / s)。

失真规范化的带宽使用情况(%) 传播艾滋病的可能性

(MSE) 总开销 $年代$ 开销 $C$ 吞吐量其他人领班1 海岸警卫队领班2

最优解 51.78 95.86 2.01 0.06 83.74 10.05 0.0140 0.0129 0.0165

贪婪的 52.02 97.14 2.04 0.08 84.84 10.18 0.0203 0.0155 0.0280

修改后的贪婪 51.78 95.86 2.01 0.06 83.74 10.05 0.0140 0.0129 0.0165

双贪婪的 51.78 95.86 2.01 0.06 83.74 10.05 0.0140 0.0129 0.0165

相等的速度 52.60 96.47 2.02 0.07 84.26 10.12 0.0165 0.0186 0.0165

表6

详细信息与不同的算法对视频资料二世(Mb / s)。

6.3。吞吐量抖动评价

提出优化框架保证每个流将实现其要求时吞吐量平均在很长一段时间。然而,流的吞吐量可能会有很短的一段时间内由于信道争用的概率性质的访问。这些流量波动可能防止光滑许多音频和视频播放流媒体的应用程序。为了缓解这个问题,许多流媒体应用程序采用prebuffering技术中,接收器将接收到的数据放入一个缓冲时间在短时间内开始播放。更长的缓冲结果平滑播放会话。另一方面,使用一个更大的缓冲结果在较大的初始延迟和所需要的内存。交互式应用程序,如视频会议可能不会容忍如此大的延迟,和低功耗无线主机可能没有足够的内存缓冲。因此,重要的是要使用协议的吞吐量抖动造成的特点。

图6(一)显示实际吞吐量所请求的吞吐量的比例不同的流视频资料我,平均每300 kb。信道容量是设置为1 Mbps。图6 (b)显示了不同流的吞吐量比视频资料二世,平均每600 kb,与频道设置为2 Mbps的能力。看到,周围的吞吐率波动1,表明所有的流动达到所需的吞吐量。这些波动的大小也小(例如,0 - 20%)表明一个可以使用一个小流缓冲顺利回放。

(一)

(b)

图6

1 2 每个流抖动的吞吐量(a)视频资料表,(b)视频资料表。

在这个模拟中,我们反复传输三个视频视频资料我20分钟。我们想量化多久流缓冲区应该为了防止丢失数据包由于迟到。为了防止流量波动,我们也请求一个略大的带宽比记录视频比特率。这个带宽安全裕度提供了健壮性与可能的吞吐量消耗在一个会话。图7(一)图7 (d)显示的数据包数量的函数流缓冲区长度不同带宽安全利润率。

(一)

(b)

(c)

(d)

图7

百分比的数据包流缓冲区长度的函数(以秒为单位);带宽安全裕度(a) 0%, (b) 1%的带宽安全裕度,带宽安全裕度(c) 2%,安全裕度(d) 3%的带宽。Akiyo的比特率、海岸警卫队和工头是192年,160年和256 Kbps。

看,没有晚包没有带宽安全裕度,用户接收Akiyo平均需要等待,48秒顺利回放一个20分钟的视频。用户收到海岸警卫队和领班需要等待88 40秒,分别。然而,所需的等待时间减少了带宽的增加安全系数。例如,使用3%的带宽安全裕度,Akiyo的等待时间,海岸警卫队,和工头用户减少到24日,32岁和12秒。

我们也流的吞吐量抖动量化分数归一化标准差的吞吐量是在一个时间段的数量。具体地说, 在哪里是一小部分的数据槽流测量范围内时间槽,表示其长期平均分数的吞吐量。显然,一个更大的会导致一个更小的归一化吞吐量标准差自从我们平均吞吐量在更长一段时间。这是简单的证明在哪里表示流动和的数量的表示成功的时间槽流的数量。(这个结果可以得到注意到成功的传输插槽的数量在一段时间内二项分布参数和。)

量化的归一化吞吐量标准差,我们模拟三个流,,被设置为0.1,0.27和0.4,分别。图8显示了三种不同的归一化吞吐量标准差流缓冲区大小的函数()。正如所料,如增加时,归一化吞吐量标准差降低。然而,越来越多的意味着增加播放延迟。

图8

$T$ 归一化吞吐量标准差作为缓冲区大小的函数()。

6.4。整体性能

现在我们比较的性能提出框架对现有的IEEE 802.11不允许控制和IEEE 802.11 e与录取控制提出Banchs et al。4]。模拟现实的设置,包损失引入模拟。为简单起见,我们假设所有接收器的丢包率是相同的。我们还假设数据包将被反复传播,直到获得成功。因此,有用的吞吐量和丢包率的增加减少。接纳控制模块被认为能够测量丢包率,从而可以确定整体有效吞吐量。使用全面有效吞吐量和视频配置文件作为输入,它可以使用不同的优化策略来分配带宽的接收器的平均失真降到最低。

图9(一个)显示各种策略的平均失真当流媒体视频概要。正如预期的那样,最优策略,也就是说,穷举搜索,总是提供最小的平均失真。double-greedy算法也同样执行。贪婪算法执行稍差,其次是平等率算法,IEEE 802.11协议不允许控制,和IEEE 802.11 e与录取控制。糟糕的主要原因表现在使用IEEE 802.11和IEEE 802.11 e是缺乏层分配优化。IEEE 802.11,由于随机contention-based访问,每个流都有一个平等的机会访问共享信道,所有三个流获得大约相同的吞吐量。然而,这不是最优分配最小化整体变形。凭直觉,IEEE 802.11应该执行以及平等的分配率。另一方面,使用等率分配方案提出允许控制导致较小的碰撞带宽相比的IEEE 802.11。因此,平等的平均失真率方案通常是低于IEEE 802.11。

(一)

(b)

图9

扭曲导致使用各种协议:(一)使用视频配置文件我和信道容量设置为1 Mbps, (b)使用视频配置文件二世与信道容量设置为2 Mbps。

然而,承认控制机制并不能提高视频质量。看到这,让我们考虑IEEE 802.11 e允许控制的性能。使用这种方案,一个是能够保证每个流的最小的吞吐率。然而,如果在提供这些最小流的吞吐量,仍有许多可用带宽,然后像设计的那样,IEEE 802.11 e协议将允许每个流来增加吞吐量比例直到到达无线容量。最后每个流的吞吐量得到接纳控制算法要求视频的质量。换句话说,在这种情况下使用的层分配是按比例分配率根据初始条件。例如,如果最低利率(或相当于最大扭曲)三个流指定最初200 Kbps, 400 Kbps, 400 Kbps,信道容量的2 Mbps, IEEE 802.11 e协议大致分配400 Kbps, 800 Kbps, 800 Kbps这些流(为了说明,我们假设没有碰撞带宽)。显然,这种分配不是最佳的,因为它没有考虑为每个视频失真概要文件。说,没有理由IEEE 802.11 e允许控制应该执行比IEEE 802.11或其他方案有足够的带宽。事实上,图9 (b)表明,IEEE 802.11 e的结果在一个更大的平均失真一直在使用视频资料。我们建议的框架,集成了接纳控制层分配优化使我们能够达到最低的失真。总的来说,我们提出的框架提高了视频质量26%的一个典型的基于IEEE 802.11网络。

7所示。结论

我们提出了一个框架来提高质量的视频流应用在无线家庭网络通过联合优化视频layer-allocation技术,允许控制算法,和MAC协议。使用一个Aloha-like MAC协议,我们允许控制框架,它可以被看作是一个优化问题,最大化的平均质量承认视频,给定一个特定的最低为每个流视频质量。我们提供了一些硬度结果在不同条件下优化问题,并提出了两种启发式算法获得一个好的解决方案。特别是,我们表明,一个简单的贪婪layer-allocation算法可以执行合理的,尽管它通常不是最优的。因此,我们提出了一个更昂贵的启发式算法,保证在一个常数因子近似最优解。基于我们的场景中,仿真结果表明,我们建议的框架可以提高视频质量26%,相比现有的方法。

引用

e . Setton x朱,b·吉伦特“Congestion-optimized调度无线ad hoc网络的视频,”<我>诉讼IEEE国际研讨会的电路和系统(ISCAS ' 05)4卷,第3534 - 3531页,神户,日本,2005年5月。视图:出版商的网站|谷歌学术搜索

IEEE Std 802.11,“无线局域网介质访问控制(MAC)和身体之后(体育)规范,”1999年。视图:谷歌学术搜索

IEEE Std 802.11 e,“无线局域网介质访问控制(MAC)和身体之后(体育)规范,”2005年。视图:谷歌学术搜索

a . Banchs x Perez-Costa d·乔,”提供吞吐量担保在IEEE 802.11无线局域网,”<我>十八国际话务国会(ITC诉讼' 03),柏林,德国,2003年9月。视图:谷歌学术搜索

m . Ergen和p . Varaiya吞吐量分析和IEEE 802.11允许控制,”<我>移动网络和应用程序,10卷,不。5,705 - 716年,2005页。视图:出版商的网站|谷歌学术搜索

t .阮、k .阮和h .临海”协作的分布式承认控制(CDAC)无线网络,”<我>学报》第27届国际会议上分布式计算系统研讨会(ICDCSW ' 07)p。75年,多伦多,加拿大,2007年6月。视图:出版商的网站|谷歌学术搜索

w·李”,概述细粒度可伸缩性的mpeg - 4视频标准,“<我>IEEE电路和系统视频技术,11卷,不。3、301 - 317年,2001页。视图:出版商的网站|谷歌学术搜索

p . p . Tang和T.-Y。c·泰”,网络流量使用令牌桶模型描述,”<我>《第十八届联席会议IEEE计算机和通信的社会(信息通信的99),1卷,页51 - 62,纽约,纽约,美国,1999年3月。视图:出版商的网站|谷歌学术搜索

l . p . Kondi f .人士,a . k . Katsaggelos“视频信噪比可伸缩性”<我>《IEEE国际会议上图像处理(ICIP ' 98),3卷,第938 - 934页,芝加哥,生病,美国,1998年10月。视图:出版商的网站|谷歌学术搜索

j . Chakareski和p . Frossard率失真优化分布式分组调度多个视频流的通信资源共享,“<我>IEEE多媒体,8卷,不。2、207 - 218年,2006页。视图:出版商的网站|谷歌学术搜索

温格,“时间使用P-pictures低延迟应用程序可伸缩性,”<我>IEEE学报》2日研讨会多媒体信号处理(MMSP 98),页559 - 564,雷东多海滩,加利福尼亚州,美国,1998年12月。视图:出版商的网站|谷歌学术搜索

w·周,d . Sarkar Ramakrishnan,“空间可伸缩的mpeg - 4视频流量模型,”<我>《IEEE全球电信会议(GLOBECOM ' 05),1卷,第260 - 256页,2005年11 - 12月刊圣路易斯,密苏里州,美国。视图:出版商的网站|谷歌学术搜索

问:张、w·朱和Y.-Q。张“Channel-adaptive资源配置为可伸缩的3 g无线网络视频传输,”<我>IEEE电路和系统视频技术,14卷,不。8,1049 - 1063年,2004页。视图:出版商的网站|谷歌学术搜索

d .歌曲和c·w·陈,“Qos保证SVC-based视频传输MIMO无线系统和信道状态信息,”<我>《图像处理国际会议(ICIP 06年),页3057 - 3060年,亚特兰大,乔治亚州,美国,2006年10月。视图:出版商的网站|谷歌学术搜索

a·林格伦a Almquist, o . Schelen”的服务质量评估方案IEEE 802.11无线局域网”<我>第26届IEEE会议程序本地计算机网络(LCN的01)坦帕,页348 - 351年,佛罗里达州,美国,2001年11月。视图:出版商的网站|谷歌学术搜索

h·朱m . Li i Chlamtac, b .普拉巴卡兰”在IEEE 802.11网络服务质量的调查,“<我>IEEE无线通信,11卷,不。4、6日至14日,2004页。视图:出版商的网站|谷歌学术搜索

c . Castelluccia操弄,问:倪,t . Turletti”加强IEEE 802.11性能与连续波下降缓慢,“IEEE 802.11 e工作组文件,2002年11月。视图:谷歌学术搜索

l . Romdhani问:倪,t . Turletti“适应性EDCF:增强服务差异化IEEE 802.11无线自组网,”<我>《IEEE无线通信和网络(WCNC ' 03),卷2,页1373 - 1378,新奥尔良,洛杉矶,美国,2003年3月。视图:出版商的网站|谷歌学术搜索

人力诉Kanodia c, a b . Sadeghi和e .骑士的“命令数据包调度无线ad hoc网络:机制和性能分析,”<我>学报》第三届ACM国际研讨会上移动Ad Hoc网络与计算(MobiHoc ' 02)瑞士洛桑,58 - 70页,2002年6月。视图:出版商的网站|谷歌学术搜索

e . Setton t . Yoo x朱,a·戈德史密斯和b·吉伦特“跨层设计的特设网络实时视频流,”<我>IEEE无线通信,12卷,不。4,59 - 65年,2005页。视图:出版商的网站|谷歌学术搜索

m·李和b .普拉巴卡兰”,MAC层允许控制和优先级处理QoS保证在非合作功率无线局域网,“<我>移动网络和应用程序,10卷,不。6,947 - 959年,2005页。视图:出版商的网站|谷歌学术搜索

m . van der夏尔y Andreopoulos, z,“优化可伸缩视频流在IEEE 802.11 / e HCCA无线网络延迟的约束下,“<我>IEEE移动计算,5卷,不。6,755 - 768年,2006页。视图:出版商的网站|谷歌学术搜索

d高,j . Cai和k . n .颜,“允许控制在IEEE 802.11无线局域网,“<我>IEEE网络,19卷,不。4,6-13,2005页。视图:出版商的网站|谷歌学术搜索

y小h·李,“评价分布式承认控制的IEEE 802.11 e EDCA,”<我>IEEE通讯杂志,42卷,不。9日,S20-S24, 2004页。视图:出版商的网站|谷歌学术搜索

答:白,b . Selvig t Skeie, p . Engelstad”基于类动态承认时间限制802.11 e EDCA的接纳控制算法,”<我>学报第六届国际研讨会在无线网络应用和服务(ASWN 06年)柏林,德国,2006年5月。视图:谷歌学术搜索

m·巴里·a·t·坎贝尔和a·维尔“分布式控制算法在无线分组网络服务差异化”<我>学报的第20届联席会议IEEE计算机和通信的社会(INFOCOM ' 01),1卷,页582 - 590,安克雷奇,阿拉斯加,美国,2001年4月。视图:出版商的网站|谷歌学术搜索

美国沙、陈k和k . Nahrstedt”动态带宽管理无线网络单跳的特别,”<我>学报第一IEEE国际会议上普适计算和通信(PerCom ' 03)沃斯堡,页195 - 203年,德克萨斯州,美国,2003年3月。视图:谷歌学术搜索

Valaee和b·李”特设网络,分布式呼叫允许控制”<我>职业训练局第56 IEEE车辆技术研讨会论文集(02),卷2,页1244 - 1248,温哥华,加拿大,2002年9月。视图:出版商的网站|谷歌学术搜索

d . Pong t·摩尔人,“争用IEEE 802.11呼叫允许控制访问机制,”<我>《IEEE全球电信会议(GLOBECOM ' 03),1卷,第178 - 174页,2003年12月旧金山,加州,美国。视图:出版商的网站|谷歌学术搜索

c . l . Fullmer和j。j Garcia-Luna-Aceves”,在无线网络解决隐藏终端问题,”<我>ACM SIGCOMM计算机通信评审,27卷,不。4,39-49,1997页。视图:出版商的网站|谷歌学术搜索

A·克劳斯和c Guestrin”,注意预算最大化的子模块功能,“计算机科学学院的卡内基梅隆大学,匹兹堡,宾夕法尼亚州,美国,2005年。视图:谷歌学术搜索

m . Sviridenko”,注意在一组子模块功能最大化背包约束,“<我>行动研究快报,32卷,不。1,41-43,2004页。视图:出版商的网站|谷歌学术搜索|MathSciNet

m . Lertsutthiwong t阮,蕨类植物,“无线单跳网络视频流,”俄勒冈州立大学的科瓦利斯,俄勒冈州,美国,2008年2月。视图:谷歌学术搜索

吴x太阳,f、s . Li w·高,和Y.-Q。张,“Macroblock-based进步细粒度可伸缩视频编码(PFGS)灵活temporal-SNR scalablilities,”<我>《图像处理国际会议(ICIP ' 01),卷2,页1025 - 1028,塞萨洛尼基,希腊,2001年10月。视图:出版商的网站|谷歌学术搜索

f . Wu s, r .偏航,x的太阳,Y.-Q。张,“高效、通用可伸缩视频编码,”<我>《IEEE国际会议上图像处理(ICIP ' 02),卷2,页37-40,罗切斯特,纽约,美国,2002年9月。视图:出版商的网站|谷歌学术搜索

h·m·达·m·范德沙尔和y陈,“mpeg - 4细粒度的可伸缩视频编码的IP多媒体流的方法,”<我>IEEE多媒体,3卷,不。1,53 - 68年,2001页。视图:出版商的网站|谷歌学术搜索

S.-R。陈,C.-P。常,C.-W。林”,mpeg - 4的投篮使用自适应土层预测编码的性能提升,”<我>《IEEE国际会议音响、演讲和信号处理(ICASSP ' 04),3卷,第268 - 265页,蒙特利尔,加拿大,2004年5月。视图:出版商的网站|谷歌学术搜索

版权

版权©2008 Monchai Lertsutthiwong等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。