基于负载自适应的Ad Hoc网视频传输队列调度算法

李 悦，陈卫卫，单 胜，丁良辉

(1.海军装备研究院，北京 100616；2.中国电子系统工程公司，北京 100141；3.国家电网公司信息通信分公司，北京 100761；4.上海交通大学 电子工程系，上海 200240)



基于负载自适应的Ad Hoc网视频传输队列调度算法

李 悦1，陈卫卫2，单 胜3，丁良辉4

(1.海军装备研究院，北京 100616；2.中国电子系统工程公司，北京 100141；3.国家电网公司信息通信分公司，北京 100761；4.上海交通大学 电子工程系，上海 200240)

移动终端多媒体业务的发展目前已经成为终端发展的必然趋势。如何在移动终端构成Ad hoc网络时有效地进行视频传输是无线网络研究的热点之一。提出了一种基于负载状况的跨层优化方案，其基本思想是结合应用层视频编码的特点和接入层的网络负载和资源的情况联合进行优化。在特定的资源下通过概率接入的方法对重要性更高的数据包进行更优先的接入。仿真结果显示，在网络处于高负载、多跳传输等场景下，提出的方案视频传输质量PSNR值提升3 dB以上。相对于传统调度算法，系统时延也可以大幅度降低。

负载自适应；无线自组网；视频传输

1 背景介绍

Ad Hoc网络可以在任何时刻、任何地点，不需要硬件基础网络设施的支持，快速构建起一个移动通信网络。它的建立不依赖于现有的网络通信设施，具有一定的独立性；Ad Hoc网络没有严格的控制中心；所有节点的地位平等，节点可以随时加入和离开网络；任何节点的故障不会影响整个网络的运行，具有很强的抗毁性。Ad Hoc 网络的这些特点使得它能满足许多应用领域的特殊需求，如军事通信网络、应急救灾等。

移动终端多媒体业务的发展目前已经成为终端发展的必然趋势，目前无线视频会议、无线视频监控以及无线视频对话等多媒体应用已经越来越多地出现在人们的生活和工作中，同时这些应用的需求也在飞速增长[1]。但是视频数据在无线网络中传输与有线传输有很大的不同[2-3]。首先，由于节点的移动以及无线信道的变化效应，无线链路传输不够稳定，对于网络的抖动有较大影响。其次，由于无线信道具有较高的误码率，对于通信质量有一定影响。再次，无线信道在一定的传输环境下信道共享，容易造成网络拥塞，使得网络延时较大。

而视频数据传输的特点决定了其对于网络通信质量的要求较高，视频数据在传输时具有如下特征。首先是数据流海量性，视频文件的数据量一般较大，因此视频数据传输需要的带宽较大；其次是流量不规则性，当今视频压缩技术采用预测编码方式，对于不同视频数据源的压缩率有一定改变，使得视频数据量随着压缩率改变；最后是传输需要实时性，视频数据往往对于时延有一定的要求，这对网络传输的时延和抖动都有较高的要求。由于上述特点，视频数据对无线网络传输性能的要求往往较高，这些性能主要包括在数据丢包率、网络吞吐量、传输延时和抖动等。虽然视频数据对于突发的传输错误能够承受，但其对带宽的要求仍然比较高。因此，无线网络传输的一系列问题加上视频数据的较高要求，使得无线网络很难为多媒体通信提供比较可靠的服务质量(Quality of Service，QoS)。

在无线网络中，各节点共享无线带宽，共同接入无线信道。因此如何有效分配信道则对网络的整个吞吐量和传输性能有着重要影响。因此在无线网络中，媒体接入控制协议(MAC)起着至关重要的作用。于无线自组网来说，由于没有中心节点，因此不能采用点协调功能的方式实现媒体接入调度。因此在无线自组网中，一般采用基于竞争的接入方式，因此分布式控制(Distributed Coordination Function, DCF)在无线自组网协议设计中得到广泛应用[4]。为了提升网络吞吐量，提高业务的传输质量，IEEE802.11协议组在IEEE802.11e标准中提出了增强分布式控制EDCA(Enhanced Distributed Channel Access)，利用不同优先级和接入参数的定义和调整提升传输效率[5]。EDCA协议对业务进行了区分，提供了8种用户优先级UP(User Priority)和4种接入类别(Access Category，AC)。4个接入类别分别对应4种类别的业务类型数据，其优先级别从高到低排列分别是：语音业务(AC_VO)、视频业务(AC_VI)、尽力而为业务(AC_BE)和背景业务(AC_BK)。对于不同优先级的业务给予不同的接入机会，使得网络资源要求更高的业务更有机会接入信道，从而在一定信道资源的情况下能够拥有更高的服务质量。IEEE802.11e的调度模型如图1所示。

随着视频编码技术的飞速发展，分层编码技术，又称为可伸缩性编码技术，在诸如MPEG-4以及H.264、H.264/SVC编码标准中广泛应用[6-7]。这种编码技术通过帧内帧间预测技术的方法去除大量的冗余信息以得到较高的压缩率。原始视频可以被编码成一个基本层和一个或者几个增强层。只需对基本层的解码即可恢复一个质量可以接受的视频。通过对更多增强层的数据进行解码便对视频的质量进一步提高。因此这样的编码方式对于无线视频传输而言，大大提高了无线视频传输的质量[8]。

结合视频编码中的分层编码技术与IEEE802.11的ED

图1 典型的自组网跨层资源调度框图

CA技术，研究人员提出了很多跨层优化传输方法[9-14]。文献[13]中提出了静态映射算法，利用编码的分层特点，将不同重要性的数据帧映射到不同的队列中去，将视频编解码过程和物理层传输过程联合优化；文献[14]中，作者提出了基于MPEG-4的一种动态映射算法。其目的是利用分层编码结构中不同类型数据的情况，并根据队列实时被占用的情况，动态地分配不同数据帧到不同的队列中去。

但是，上述研究都没有考虑到网络负载的动态变化情况，不能根据网络负载自适应地调整调度算法，充分利用网络资源，提高视频质量。针对此问题，本文提出了一种基于负载自适应的动态调度算法，结合应用层视频编码的特点和接入层网络负载和资源的情况联合进行优化。在特定的资源下通过概率接入的方法对重要性高的数据包进行优先接入。

2 相关研究进展

2.1 分层视频编解码技术

目前，关于可伸缩性的要求大致有3种：时间可伸缩性、空间可伸缩性以及信噪比可伸缩性。对于空间可伸缩性的实现，是将输入的原始视频序列进行下采样，得到低分辨率的序列，然后再对此序列变换后的系数进行量化编码，即可得到基本层码流。将基本层重构信息与原始视频信息的误差进行编码即可得到增强层码流。对于时间可伸缩性的实现，是将视频序列帧分为两组，对一个组的序列进行编码得到基本层，对于另一个序列进行编码得到增强层。基本层的码率相对较低，而增强层的码率相对较高。对于信噪比可伸缩性则是在变换系数量化过程中实现的，基本层采用量化步长相对较大，得到的码率也相对较低。而增强层则是对基本层残差数据采用更小的步长进行量化，从而得到更加精细的系数量化结果。本文的研究中，采用H.264/SVC的编码方法，并仅采用了时间可伸缩性，但是所提出的方法对于其他的编码方式仍然可行。数据帧通过时间可伸缩性区分的视频包数据类型包括T0，T1，T2。其关系如图2所示。

图2 H.264/SVC数据流结构

2.2 动态映射算法

在基于EDCA的视频传输系统中，视频数据是接入到第2个接入类别AC_VI中，其接入优先级仅次于对于传输性能要求更高的音频服务数据AC_VO队列，而高于最大努力型的业务数据AC_BE、背景业务数据AC_BK。与DCF相比，EDCA从一定程度上提高了视频数据的传输质量。但是这种机制将所有类型的视频数据统一处理，在网络资源紧缺的情况下将会面临数据量过大，从而导致网络拥塞丢包和不必要的时延。同时由于很多基本层帧丢失，造成接收到的增强层数据包即使正确接收也无法正确解码，使得视频的传输质量严重下降。

静态映射算法[13]，利用编码的分层特点，将不同重要性的数据帧映射到不同的队列中去。将重要性高的基本层数据帧映射到AC[2]，将重要性低的视频数据帧映射到低优先级的队列。静态映射方法在网络负载较重的时候对于视频的传输质量有一定的提升作用，但其固定的映射方式显然不够灵活，不能对网络负载的变化做出适时的反应。另外在网络负载较轻时，其表现并不如传统的EDCA机制，尤其是延时相对较长。

无线自组网受到无线传播环境的影响，信道状况一般有较大的波动，每个节点的出站速率会随之变化。同时由于网络中没有中心协调节点，无法做到实时的资源协调和分配，从而造成每个节点的负载和队列情况也是动态变化的。针对自组织网络的特征，动态映射算法[14]在一定程度上解决了静态映射方法存在的问题。动态映射算法利用分层编码输出数据的重要性信息，并结合队列实时被占用的情况，动态地将数据帧分配到不同的队列中去。一个典型的动态映射算法如下所述：

Step1：在包头添加了服务类型信息(Type of Service，TOS)用来记录视频数据帧的类型，应用层将这个信息传递到网络层和媒体接入层。

Step2：所有类型的视频数据包都按照EDCA的方式默认映射到AC[2]中。

Step3：媒体接入层对网络负载情况进行检测，当AC[2]被占用长度增大的情况下，视频数据包将以一定的概率被降至低优先级级的队列中去。对于视频编码来说，降队列概率与数据包重要性直接相关。

Step4：为了防止队列长度进一步增大，降队列概率在队列长度的特定范围内随着队列长度的增加而线性地增加，即

(1)

(2)

算法框图如图3所示，动态映射算法通过引入利用分层编码结构中的不同类型数据的情况，并根据队列实时被占用的情况，动态地将不同数据帧分配到不同的队列中去，可以较好地解决自组织网络中的视频传输问题。

图3 动态映射算法程序流程图

3 基于负载自适应的队列调度算法

动态映射算法虽然从某种程度上提高了接收视频的传输质量，但是仍然有许多缺点。首先仅仅采用AC[2]的队列占用长度显然对于网络负载情况和外部环境情况不能很好地体现。其次，采用降队列概率的方法虽然能够从一定程度上缓解负载过重的情况，但当网络持续负载较重的情况下，这种方式只能暂时缓解问题，当负载过重的情况下，AC[2]或者其他队列仍然会产生溢出，从而将重要性较高的数据包丢掉，对视频传输质量造成较大的影响。再次，降队列概率的最终值即分配概率为固定值，网络负载很重的情况下并不能得到最优的结果，而且当网络环境变化的情况下也不能及时地调节，从而对于性能会产生不良的影响。

3.1 算法描述

针对上述问题，提出了基于负载自适应的动态映射算法(Load Adaptive Dynamic Mapping，LADM)，算法框图如图4所示。

图4 负载自适应动态映射算法程序流程图

算法基本描述如下：

步骤2:所有类型的视频数据包都按照EDCA的方式默认映射到AC[2]中。

步骤3：媒体接入层对网络负载情况进行检测，当AC[2]被占用长度增大的情况下，视频数据包将以一定的概率被降至低优先级级的队列中去。对于视频编码来说，B帧应该具有最大的降队列概率，而I帧则应该有最小的降队列概率。

步骤4：降队列概率在队列长度的特定范围内随着队列长度的增加而线性地增加，降队列概率与分配概率的关系和动态映射算法相同，但分配概率随负载情况而变化。

3.2 网络负载状况判断算法

网络是否过载的判断通过利用所估计得到的网络资源信息与网络负载信息进行比较得出结果。即如果满足

(3)

判断此时的网络资源足够传输所用类型业务的数据，网络处于非过载状态。否则网络处于过载状态。

3.3 分配概率的计算

对于分配概率，即当队列长度超过较大门限时的降队列概率的最终值，需要采用针对负载和资源估计的值进行相应的调节。在本算法中，采用了根据负载和网络资源估计，针对相关的数据包率进行线性调节的方法，其计算方法为

(4)

3.4 丢弃概率的计算

当网络处于过载状态时，需要将一部分业务的数据包主动丢弃，为重要性更高的数据包让出信道资源，保证更加重要的数据包的传输。对于数据包的丢弃，仍然采用概率丢弃的方法。丢弃概率的值应该与网络资源和负载情况相关，在本算法中仍然采用了基于数据包率的线性关系来计算。计算方法为

(5)

4 仿真分析

文章对于无线自组网中的基于跨层优化的视频传输方案进行了仿真分析，网络仿真工具为NS2，视频编解码工具为可伸缩视频评估框架(ScalableVideoEvaluationFramework,SVEF)。SVEF是一款开源软件，专门用于评价H.264/SVC视频流的传输质量。在整个仿真过程中，首先要对原始视频进行编码，然后数据封装，之后将数据输入到NS2仿真过程之中进行仿真，将仿真结果记录下来并存储视频数据接收端所接收到的数据，然后对其进行解码后，将接收到的视频与原视频进行比较评估接收视频质量，从而得出视频数据传输质量的评估结果。仿真流程如图5所示。

图5 仿真流程图

4.1 网络负载对系统性能的影响

首先对在特定带宽不同网络负载情况下进行仿真，物理层传输的数据率设置为1Mbit/s。

在仿真过程中采用了3个节点，n0，n1和n2。n0发送H.264/SVC的视频业务，并且利用业务源流量产生器CBR作为背景业务数据和音频数据。其中n0向n1发送视频业务，视频码率为0.2Mbit/s，原始视频采用的是YUVCIF(352×288)格式的Foreman。n0向n2发送背景业务数据。

对于视频传输而言，丢包并不能完全说明传输质量。因为不同数据包的丢失对于视频质量影响不一样。计算接收视频的PSNR是对视频传输质量综合的体现，在上面的情况下对于不同网络负载的情况下，对不同算法下接收视频的PSNR进行了计算，算法包括EDCA、静态映射、动态映射、LADM，其PSNR结果如图6所示，传输时延的结果如图7所示。

根据图6可以看出，负载较轻的情况下，由于静态映射算法将数据包放入低优先级队列中造成丢包率相对更大。而动态映射算法通过队列长度对网络负载情况进行检测，因此存在一定的自适应性，并不是完全将重要性低的数据包放入低优先级队列进行调度。而自适应动态映射算法，采用了队列

图7 不同负载下延时仿真结果

发送速率和不同类型的数据包进队列速率作为网络情况的进一步衡量，在负载较轻时其表现与动态映射算法和EDCA基本差不多，但在负载情况较重时其表现优于其他算法，当负载到达物理层传输的极限时(5个视频流同时发射)，提出的算法PSNR改善3dB以上，有效地提升视频质量。

根据图7可以看出，静态算法的延时最大。动态算法和自适应算法的延时均比EDCA大，但比静态算法要小。自适应算法在网络负载较轻时，延时稍大于动态算法，但在网络负载较重时，延时小于动态算法。

4.2 节点竞争对系统性能的影响

为了评估自组织网络间节点通信产生的碰撞对系统的影响，设计以下的场景：网络中有3个节点，n0，n1和n2。n0和n1同时向n2发送数据，其中n0发送视频流和64kbit/s音频数据，n1同时也发送196kbit/s背景数据。视频传输质量如图8所示。

从图8的结果可以看出，当存在节点竞争时系统视频传输质量有较大变化。当网络负载较轻的时候，性能下降最多的是静态映射算法，其次是EDCA算法，然后是动态映射算法，自适应动态映射算法受到的影响最小。静态映射算法将数据包固定映射到低优先级的队列中之后，当出现节点竞争的时候，低优先级的队列传输性能变差，导致视频传输性能变差。然而自适应动态映射算法通过对网络的负载情况进行了更加详细的检测，因此可以改善这一情况。

图8 节点竞争下的仿真结果

4.3 多跳视频传输场景下的系统性能

对于自组网来说，多跳传输是自组网的一种重要的传输方式。因此对于多跳传输，同样通过设置一系列节点进行仿真。在NS2中设置了如图9的拓扑结构。其中，节点node(i-1)向节点node(i)发送视频数据，视频流速率为0.2Mbit/s。同时，节点间存在背景业务数据流速率为192kbit/s。

图9 多跳场景拓扑图

研究不同跳数情况下的视频传输质量PSNR和延时情况。其结果如图10和图11所示。

图10 多跳环境下的视频传输质量

图11 多跳环境下的延时

从仿真结果可以看出，随着跳数增加，视频传输质量有一定的下降。对于此仿真场景中，当跳数增加时视频质量有所下降，时延明显上升。从结果上看，静态映射算法的传输时延最长，多于其余几个算法，其次是动态映射算法的时延，然后是EDCA和自适应动态映射算法。从传输质量上看，在跳数增加的情况下，自适应动态映射算法的传输质量相对不如静态映射算法和动态映射算法，原因应该是对于每个节点都需要从传输过程中进行实时的参数监测，参数监测随着节点增加而准确度降低，因此调度过程一定程度上出现不准确的计算结果。

5 结论

本文主要提出了一种负载自适应的动态调度算法，其基本思想是结合应用层视频编码的特点和接入层网络负载和资源的情况联合进行优化。在特定的资源下通过概率接入的方法对重要性更高的数据包进行更优先的接入。仿真结果显示，在视频传输质量方面，自适应算法在负载较轻的时候并没有大幅度提升。但当网络负载较重的情况下，自适应动态映射算法的优势相对明显，PSNR提升3dB以上。在延时方面，自适应动态映射算法的延时在网络负载较重时稍好于动态映射算法，但都比EDCA本身延时大，但自适应算法在视频传输质量上有较明显的提升。

[1]CiscoSystems.Ciscovisualnetworkingindex:forecastandmethodology[R].[S.l.]：Cisco，2008.

[2]HALVORSENM,PLAGEMANNT,SIEKKINENM.Videostreamingovermanets:realityorfiction[C]//Proc.the4thInternationalMobileMultimediaCommunicationsConference.Oulu,Finland：[s.n.], 2008：153-162.

[3]TSENGYC,NISY,CHENYS,etal.Thebroadcaststormprobleminamobileadhocnetwork[J].Wirelessnetworks, 2002, 8(2/3)：153-167.

[4]BOUKERCHEA,TURGUTB,AYDINN,etal.Routingprotocolsinadhocnetworks:asurvey[J].ComputerNetworks, 2011, 55(13):3032-3080.

[5]RANIWALAA,CHIUEHT.ArchitectureandalgorithmsforanIEEE802.11-basedmulti-channelwirelessmeshnetwork[C]//Proc.the24thAnnualJointConferenceoftheIEEEComputerandCommunicationsSocieties.Miami,FLUSA：IEEEPress，2005：2223-2234.

[6]STOCKHAMMERT,HANNUKSELAMM,WIEGANDT.H.264/AVCinwirelessenvironments[J].IEEETrans.CircuitsandSystemsforVideoTechnology, 2003, 13(7):657-673.

[7]SOHNH,YOOH,LEEYB.MPEG-21-Basedscalablebitstreamadaptationusingmediumgrainscalability[C]//Proc.IEEERegion10Conference.[S.l.]：IEEEPress, 2008: 1-5.

[8]骆政屹，余松煜，宋利，等.H.264可分级扩展技术的介绍和分析[J].中国图象图形学报, 2006(11) :1578-1583.

[9]雷蕾, 林闯.无线数据网络中机会调度理论模型的研究[J].电子学报, 2007, 35(8):1548-1557.

[10]周超, 张行功, 郭宗明.面向 MIMO 多跳无线网络的多用户视频传输优化方法[J].软件学报, 2013, 24(2):279-294.

[11]MANTZOURATOSS, GARDIKIS G, KOUMARAS H, et al.Survey of cross-layer proposals for video streaming over Mobile Ad hoc Networks(MANETs)[C]//Proc.2012 International Conference on Telecommunications and Multimedia(TEMU).[S.l.]：IEEE Press，2012:101-106.

[12]LINC H, SHIEH C K, KE,C H，et al.An adaptive cross-layer mapping algorithm for MPEG-4 video transmission over IEEE 802.11e WLAN[J].Telecommunication Systems, 2009, 42(3/4): 223-234.

[13]NEJATIN, YOUSEFIZADEH H, JAFARKHANI H.Wireless video transmission: a distortion-optimal approach[C]//Proc.Data Compression Conference.[S.l.]：IEEE Press ,2008: 202-211.

[14]KSENTINI A, NAIMI M, GUEROUI A.Toward an improvement of H.264 video transmission over IEEE 802.11e through a cross-layer architecture[J].IEEE Communications Magazine, 2006, 44(1):107-114.

李 悦(1977— )，女，工程师，主研卫星通信、自组织网络；

陈卫卫(1976— )，高级工程师，主研无线自组织网络、无线通信；

单 胜(1971— )，工程师，主研无线自组织网络、视频通信；

丁良辉(1981— )，助理研究员，主研无线通信、无线网络。

责任编辑：薛 京

Load Adaptive Queue Scheduling for Video Transfer in Wireless Ad Hoc Networks

LI Yue1，CHEN Weiwei2，SHAN Sheng3, DING Lianghui4

(1.NavalArmamentResearchInstitute,Beijing100616,China; 2.ChinaElectronicSystemEngineeringCompany，Beijing100141,China;3.InformationandCommunicationBranch,NationalGrid,Beijing100761,China; 4.DepartmentofElectronicEngineering,ShanghaiJiaoTongUniversity,Shanghai200240,China)

Development of multimedia on mobile terminals has been the trend, and how to transfer video in wireless ad hoc networks has been a hot research topic in recent years.In this paper, the cross-layer optimization scheme for video transfer based on network load is proposed.The proposed scheme considers both video coding on application layer and network load status on MAC layer to optimize the video quality.Packets with higher priority are transmitted with high access probability when the network resource is limited.Simulation results show that the performance of the video, i.e.,PSNR, can be improved up to 3 dB in heavy-load and multi-hop scenario.Compared with traditional scheduling algorithm, system delay can also be reduced significantly.

load adaptive; wireless ad hoc networks; video transfer

国家自然科学基金项目(61301117；61102051；61221001；61420106008)；国家高技术研究发展“863”计划项目(2012AA011701；2012AA121601)；上海交通大学“科技创新专项资金”(AF0300021)；上海市数字媒体处理与传输重点实验室项目(12DZ2272600)

TN915

A

10.16280/j.videoe.2015.07.017

2014-10-20

【本文献信息】李悦，陈卫卫，单胜，等.基于负载自适应的Ad Hoc网视频传输队列调度算法[J].电视技术,2015，39(7).