1 引言
随着Ad Hoc网络规模的扩大,业务流的发送端与接收端跨度也在增加,仅仅依靠端到端的拥塞控制难以满足各种应用需求. 因此研究者考虑在路由节点引入主动队列管理(active queue management,AQM)机制,通过动态检测并管理节点的数据堆栈长度,实现对网络拥塞的检测与控制.
近年来,研究者基于控制理论研究AQM[1]以改进拥塞控制的稳定性和健壮性. 文[2]研究了Ad Hoc网络TCP(transmission control protocol)流的AQM拥塞机制模型,但模型无法分析UDP(user datagram protocol)流量. 文[3]针对混合流提出一种时间加权平方误差积分的AQM,对UDP流量具有较好的抗干扰能力,但由于研究目标是TCP流服务质量(quality of service,QoS),仅把UDP流量作为AQM系统的干扰,没有探讨拥塞状态下的UDP传输性能. 文[4]研究了纯UDP流在队列机制下的超时丢包策略,根据视频分组重要度来优化丢包机制,提高了视频传输的质量,但实际网络环境中往往是混合流[5],具有超时机制的TCP流会干扰算法. 文[6]在纯UDP环境中进行了3种AQM的视频传输品质对比实验,结果显示预测比例积分算法的性能优于权重随机早期丢包及丢尾算法,但也没有考虑TCP业务对AQM的影响. 文[7]根据混合业务流特点,为不同类型业务流设置不同的优先级,改进的RED(random early detection)算法根据分组优先级进行丢弃,既保证了视频传输,也能保障TCP不受较大影响. 但文[8]显示有线网络中研究广泛的RED算法在Ad Hoc网络中具有不公平性,而且RED算法对配置的参数非常敏感,Ad Hoc网络中的队列性能并不理想. 文[9]设计了一种视频流的速率控制协议,其本质是建立视频分组传输的反馈控制机制,研究显示速率控制获得了较好的视频传输品质,但有研究者[10]提出真实网络环境中存在多种业务流,不同的传输协议会给速率反馈控制算法的性能带来较大不确定性,此外反馈控制依然存在稳定性与鲁棒性问题,还会使视频传输的延时增加. 文[11]建立了有基础设施无线网络MPEG(moving pictures experts group)视频传输的实验评估体系,改进了原有网络多媒体传输实验体系仅有简单错误模型的问题,添加了无线MAC(media access control)重传等机制,但没有涉及Ad Hoc网络的视频传输研究. 基于神经网络理论,文[12]设计了一种分组优先级分类器,可避免路由器丢弃重要的视频分组,但也没有考虑Ad Hoc网络混合流情况.
综上,在Ad Hoc网络应用场景中存在TCP与UDP混合流,仅仅针对单一流量的拥塞控制策略无法保证网络的服务质量. 一方面,传统AQM研究的基础是TCP反馈机制,对于混合流拥塞,队列控制器将UDP流作为系统扰动,无法保障基于UDP的视频传输性能; 另一方面,UDP视频传输拥塞研究又往往不考虑TCP业务流的干扰. 因此,Ad Hoc混合流网络AQM如何保障视频传输需进一步研究.
本文研究Ad Hoc网络源节点发送机制及路由节点排队机制,建立了混合业务流的AQM拥塞控制模型,提出一种保障视频传输品质的PI-V主动队列管理. 当传输画质下降,算法依据视频帧权重与分组长度,动态调整UDP视频流的丢弃概率,保障视频传输质量; 当传输画质上升,算法仍以经典PI(proportional integral,PI)队列算法丢弃UDP分组,避免UDP应用对TCP流的冲击. NS实验表明,PI-V算法优于PI与去尾算法,提高了视频传输质量0.82 dB~2.22 dB的峰值信噪比,算法也能兼顾TCP流量.
2 混合流AQM被控对象建模变量定义: t为时间(t≥0); C为链路容量(分组/秒); N为TCP连接数; p(t)为分组丢弃概率; q(t)为队列长度(分组); q0为理想队列长度; W(t)为TCP拥塞窗口值(分组); α为常系数(0<α<1); R(t)为TCP往返时间(round trip time),单位为s; 下标i代表第i个TCP流,则其往返时间Ri(t)=Di+q(t)/C,其中Di为固定的传播延时; Bi(t)为第i个TCP流的发送速率; 数学期望E(φ)简记作.
设计队列控制器,首先要建立被控对象的数学模型. 本文混合流队列包含TCP与UDP两类流量: TCP发送特性服从TCP拥塞窗口原理,UDP发送特性由视频文件的编码决定.
2.1 TCP发送特性丢包率p(t)可代表拥塞事件发生的概率. 设Y(t)为时间区间(t,t+R(t))内拥塞事件发生的次数,由文[13]可知,Y(t)近似服从二项分布(W(t),p(t)). 假设丢包率为10%,一个R(t)中,拥塞事件Y(t)是1个或0个的总概率达到95%. 在均值条件下,可设Y(t)为[0, 1]的随机数,故本文假设一个R(t)中拥塞事件至多发生一次(某次拥塞事件可能是单分组丢失,也可能是多分组的关联丢失[14]).
根据TCP拥塞窗口加法增大乘法减小(additive-increase and multiplicative-decrease,AIMD)原理,TCP拥塞窗口的数学表达如下:
拥塞避免: W(t+R(t))=W(t) 分组丢失(3 dup ack): W(t+R(t))=(1-α)W(t) 分组丢失(超时): W(t+R(t))=1 根据上述特性,TCP拥塞窗口值可写为
整理式(1)为
设时间[0,t]内拥塞造成的分组丢失数M(t)服从泊松分布,其丢失速率为λ(t),则有:
将式(3)代入式(2),则有:
根据TCP的AIMD原则,一般取α=0.5,对第i个TCP流:
取数学期望,考虑E(g(x)dM)≈E(g(x))dE(M),式(5)化为
根据E(g(x)dM)≈E(g(x))E(dM)与E(f(x))≈f(E(x)),由泊松过程性质E(M(t))=λt,代入式(6)得
根据泊松分布的定义:
λ=p(t-Ri(t))i(t-Ri(t))
整理得
第i个TCP流的发送速率Bi(t)=Wi(t)/Ri(t).
2.2 UDP发送特性
应用层的视频文件由帧号、 帧类型、 帧大小、 发送时间等信息组成. 视频通过UDP传输前,图像传输程序首先会读取视频文件,并把各视频帧封装到UDP分组中. 如果视频帧长度大于规定的UDP分组长度,还需要切割该视频帧. 可见,UDP发送特性与视频文件的编码相关,帧大小fr(t)(分组)与帧发送间隔int均以编码形式存储在视频st文件中. 据此,UDP流的发送速率B′(t)为
B′(t)=fr(t)/int 2.3 路由节点混合流队列特性考虑TCP流在稳态下,离散时刻源端的发送分组数{A(k),k=0,1,2,…},a(k)为离散间隔内发送数,则进入队列的分组即为a(k)=A(k)-A(k-1).
考虑UDP流在稳态下,离散时刻源端的发送分组数{A′(k),k=1,2,…},a′(k)为离散间隔内发送数,则进入队列的分组即为a′(k)=A′(k)-A′(k-1).
根据Lindley方程,并转化为连续时间上的函数:
TCP流发送a(t+Δt)=∑Ni=1Bi(t)Δt,UDP视频流发送a′(t+Δt)=B′(t)Δt,代入式(9)取数学期望,则路由节点混合流队列方程可写为
2.4 AQM被控系统建模
数学期望意义不变,省略其上标,联立式(8)和式(10),Ad Hoc网络TCP与UDP混合流AQM拥塞模型为
对式(11)用小信号线性化处理[15],进行拉普拉斯变换,最终将其转换为如图 1所示的控制框图.
对图 1进行整理,考虑e-sR0近似为1,可得如图 2所示的队列控制系统框图,混合流队列被控对象见图 2右侧虚线框,其中,P0(s)=C2/(2N)(s+2N/(CR20))(s+(C-fr/int)/CR0),p为分组丢弃概率,q为队列长度,q0为理想队列长度. 混合流队列控制器见图 2左侧虚线框,其结构在第3节中讨论.
3 混合流AQM的设计
3.1 TCP流丢弃算法
针对TCP流,选择PI控制,其基本原理是丢弃概率与队列误差及队列误差在时间上的积分成正比,丢弃概率表达式为
式(12)中,系统误差信号e(t)=q(t)-q0,kp为比例控制系数,ki为积分控制系数. 可见,对于TCP流,AQM控制器仍是依据队列长度信息进行分组丢弃.
3.2 UDP流丢弃算法
3.2.1 视频流画质分析
峰值信噪比(peak signal to noise ratio,PSNR)是图像处理领域的一种视频质量评价指标. PSNR值越大,表示目的图像与原始图像差距越小,画质越好.
根据峰值信噪比定义[16],计算PSNR需要比较原始图像和目的图像的亮度数值,一般用于视频传输结束后的评定,在传输过程中求取PSNR数值比较复杂. 因此,本文计算一个画质参数Q,以便AQM机制无需复杂的图像学计算即可获得画质的变化趋势,协助AQM做出合理的丢弃决策.
首先说明视频编码格式. 视频数据被编码为周期性的图像组(group of pictures,GOP)结构,根据不同的画面类型,GOP可分为内部编码I帧、 前向预测P帧及双向内插B帧. I帧是以自身画面数据作为编码,即不需要参考其它画面; P帧是以自身画面数据及之前被编码的I帧或P帧作为编码; B帧是以自身画面数据及其前后的I帧或P帧作为编码[17].
定义视频文件已传输的GOP单元数为NGOP. I、 P及B帧的已传帧总数为Nc-I、 Nc-P及Nc-B. I、 P及B帧的可解码帧数为Nd-I、 Nd-P及Nd-B. 一个GOP单元中必定有一个I帧,所以Nc-I等于NGOP. 某个视频帧可能分割为多个UDP分组,CI、 CP及CB分别为I、 P及B帧在传输层的分组数.
为获得画质参数Q,下面分别求取已传图像中可解码I、 P及B帧的数学期望[17].
(1) 可解码的I帧
只要属于某个I帧的所有分组都被正确接收,则此I帧可解码.
GOP中I帧可解码的概率为 (1-p(t))CI
因此,在已传输图像文件中可解码I帧数的数学期望为 d-I=(1-p(t))CI·NGOP
(2) 可解码的P帧
设一个GOP单元中有Np个P帧. 当属于这个P帧画
面的所有分组都被正确接收,且此画面所参考的先前的I帧或P帧都可解码,此P帧才可解码.
GOP中第1个P帧可解码的概率为
(1-p(t))CI(1-p(t))CP
第2个P帧可解码的概率为
(1-p(t))CI(1-p(t))CP(1-p(t))CP=(1-p(t))CI+2CP
第Np个帧可解码的概率为
(1-p(t))CI(1-p(t))NpCP=(1-p(t))CI+NpCP
因此,已传输图像中可解码的P帧数的数学期望为
d-P=(1-p(t))CI·∑Npj=1(1-p(t))jCPNGOP
(3) 可解码的B帧
在一个GOP单元中,连续的B帧具有相同的参考性,所以把这些连续的B帧当成一个帧集合. 当属于这个B帧画面的所有分组都被正确地接收,并且此画面所参考的先前及之后的I帧或P帧都可解码,此B帧才可解码.
GOP中第1个B帧可解码的概率为
(1-p(t))CI(1-p(t))CP(1-p(t))CB
第2个B帧可解码的概率为
(1-p(t))CI(1-p(t))2CP(1-p(t))CB
第NⅡ/NIP个B帧可解码的概率为
(1-p(t))2CI(1-p(t))(NⅡ/NIP-1)CP(1-p(t))CB
其中,NⅡ是从I帧到I帧的画面数,NIP是从I帧到P帧的画面数.因此,已传输图像中可解码的B帧数的数学期望为
d-B=(NIP-1)(1-p(t))CI+CB. (1-p(t))CI+NPCP+∑Npj=1(1-p(t))jCPNGOP
根据以上分析,视频画质Q可定义为
通过计算式(13),可以在传输过程中评估视频流画质的变化,为设计合理的UDP丢弃算法提供理论依据.
3.2.2 UDP丢弃设计
当发生拥塞时,如果只依据队列长度信息进行无差别的分组丢弃,对无应答及无重传机制的UDP视频流较为不利. 本文结合视频帧权重和UDP分组长度,提出一种保障视频质量的UDP丢弃算法.
首先考虑视频帧权重. 根据3.2.1节中对GOP编码机制的分析,I、P及B帧的重要性并不相同,因此分别丢弃I、 P及B帧对传输质量的影响差异较大. 文[18]中给出了一种衡量I、P及B帧重要性的权重表达式,如式(14)所示:
式(14)中wn为GOP单元中第n个帧的重要度,NP为GOP单元中P帧的数目,NB为GOP单元中B帧的数目,m为GOP单元中第m个P帧,有1≤m≤NP.
其次考虑UDP的长度信息. 本文定义视频帧切割的分组最大长度Lmax为1 024 Byte(到网络层需再加上UDP
头8字节与IP头20字节,分组头合计28 Byte). 但视频文件的I帧、 P帧及B帧的大小并不恒定,导致视频帧封装为UDP分组后大小不一. 以foreman.st文件编码为例,第3号B帧为1 442 Byte,需切割为2个UDP分组. 第31号B帧为241 Byte,只需要1个分组. 因此,对同一类视频帧分组而言,分组长度越大,所含信息量就越大,也相对更重要.
结合以上2个方面的分析,定义UDP分组丢弃概率为
注 网络层IP分组长度为LIP,取l=Lmax/(LIP-28); 当计算的p(t)值大于1时,取p(t)=1.
3.3 混合流AQM算法实现
上述UDP丢弃没有考虑队长信息,过度保护UDP业务可能会给TCP流带来公平性问题. 因此,本文以画质参数Q作为执行UDP流丢弃的条件: 如果画质Q(t)Q(t-R(t)),则仍执行式(12)的PI算法. PI-V算法伪码为
ptcp(t)=kpe(t)+1Ti∫t0e(t)dt if (分组是TCP流)//判断分组类型 p(t)=ptcp(t) else {//计算当前画质
if (Q(t)
p(t)=∫l0(1-wn)dl,∫l0(1-wn)dl≤pq(t)
pq(t),∫l0(1-wn)dl>pq(t);
//启动UDP丢弃算法
else p(t)=ptcp(t);
} |
Ad Hoc网络节点S1,…,SN,SN+1通过瓶颈节点G向目标节点D2发送数据,其中S1至SN发送TCP流到D2,其应用层运行FTP服务,而SN+1则发送UDP流到D2,其应用层运行视频服务,视频GOP结构为IBBPBBPBB(NⅡ=9,NIP=3,Np=2,NB=6),拓扑结构如图 3所示. Ad Hoc网络所有节点链路容量为11 Mb/s,瓶颈节点G接口队列长度为50包,其混合流队列特性见第2节推导结论,节点G队列管理采用去尾、 PI及PI-V算法,后两种算法的理想队列长度均设为30包,PI控制器参数kp=0.02,ki=0.01. 仿真总时间为100 s.
仿真1 单纯UDP视频流传输(无拥塞)
TCP负载数为0. 由于只有一个节点在传输视频流,而链路容量足够大,拥塞及队列丢弃现象没有发生,队列 曲线图略. 实验中,UDP分组仍有极少量的丢失(0.91%,具体数据见表 1),通过对NS输出trace文件分析,是由于节点执行路由算法,链路不稳定产生的丢失.
仿真2 混合业务流下的去尾算法
初始时刻0 s有7个FTP业务源启动(S1~S7均发送到D2),在72 s时有1个视频业务源启动(S8发送到D2),路由节点G的队列长度曲线如图 4所示,当引入FTP业务做背景流时,去尾算法受其影响较大,瓶颈节点多次出现满队列,队列长度也震荡剧烈.
仿真3 混合业务流下PI算法的影响
仿真3在瓶颈节点G上使用PI队列算法,其它设置与仿真2一致. 队列长度如图 5所示. 瓶颈节点不再到队列全满时才丢弃分组,而是把队长控制在理想队列长度附近,降低了严重拥塞发生的可能性,PI算法比去尾算法更好地控制了队列震荡.
仿真4 混合业务流对PI-V算法的影响
仿真4在瓶颈节点G上使用PI-V队列算法,其它设
置与仿真3一致,队列长度如图 6所示. 可见PI-V算法能有效控制混合流队列,但由于PI-V算法要保障视频质量,最重要的I帧几乎不会主动丢弃,这给队列管理增加了难度,因而其队列动态稳定性略差于PI算法.
根据以上实验,在节点D2上分别获得视频yuv文件,3种队列策略的视频图像对比见图 7、 8.
仿真1~4的相关实验数据对比见表 1,PI及PI-V算法具有更好的队列控制效果,平均队长、 延时与丢弃概率均明显优于去尾算法. PI及PI-V算法在平均队长(队列静态性能)、 延时指标上十分接近. 对UDP流而言,尽管PI-V算法在UDP丢弃概率方面略高于PI,但由于PI-V算法优先丢弃视频权重低及分组长度小的分组,所以其画质参数PSNR反而高于PI. 而对TCP平稳流而言,PI-V算法通过主动丢弃非关键的视频分组,在TCP丢弃方面还略低于PI,没有出现因保护视频流而干扰TCP业务的情况. 另外无拥塞与去尾两列数据显示,TCP作为干扰流,的确会对UDP流量的QoS产生很大影响.
无拥塞 | 去尾 | PI | PI-V | |
平均队长 /包 | - | 31.4 | 23.0 | 22.9 |
平均延时 /s | 0.025 | 0.306 | 0.228 | 0.230 |
最大延时 /s | 0.094 | 0.616 | 0.520 | 0.540 |
UDP丢失概率 /% | 0.91 | 10.60 | 6.22 | 6.52 |
TCP丢失概率 /% | - | 3.09 | 5.39 | 5.24 |
PSNR /dB | 34.30 | 30.39 | 31.79 | 32.61 |
仿真5 突发TCP流量对PI与PI-V算法的影响
初始时刻0 s有5个FTP业务源启动(S1~S5发送到D2),在72 s时有1个视频业务源启动(S11发送到D2),75 s时另有5个FTP业务源启动(S6~S10发送到D2),仿真5显示在面对突发TCP流量时,PI-V算法有一定程度的震荡,但仍能够把队列稳定在设定值附近,队列长度如图 9所示. 突发TCP流下的实验数据对比见表 2,相较TCP平稳流量实验,两种算法均提高了UDP丢弃率,但PI-V算法的UDP丢弃率明显小于PI算法,而其TCP丢失率并未显著增加,显示PI-V算法通过适当丢弃UDP分组,既能 尽量克服突发干扰流造成的视频流传输质量下降,又能较好地稳定混合流队列,维护了算法对TCP业务流的公平性.
参数名 | 参数值 |
电枢电阻Ra | 0.524 |
电枢电感La /mH | 0.390 |
转动惯量J /(g·cm2) | 10.5 |
转矩常数Km /(N·m/A) | 0.016 9 |
最大转速ωmax /(r/min) | 10 400 |
本文设计的PI-V混合流队列控制器能针对不同业务流进行丢弃,提高了主动丢弃算法处理混合流的自适应能力. 本文仅考虑了一条视频UDP流,在网络环境中,UDP流也可能不止一条,因此其它UDP流对视频应用的影响是下一步研究的方向.
[1] | 张永敏, 徐伟强, 黄炯, 等. Ad Hoc网络节能型功率控制与拥塞控制的跨层优化[J]. 软件学报, 2013, 24(4): 900-914. Zhang Y M, Xu W Q, Huang J, et al. Optimal cross-layer power control and congestion control providing energy saving for Ad Hoc networks[J]. Journal of Software, 2013, 24(4): 900-914. |
[2] | 陈亮, 张宏. 基于TCP的无线自组网AQM建模[J]. 控制理论与应用, 2011, 28(7): 956-962. Chen L, Zhang H. Modeling active queue management based on transmission control protocol in Ad Hoc network[J]. Control Theory & Applications, 2011, 28(7): 956-962. |
[3] | 汪浩, 李晓明, 严伟, 等. 具有最小时间加权平方误差积分的主动队列管理算法ISTE-PI[J]. 计算机学报, 2012, 35(5): 951-963. Wang H, Li X M, Yan W, et al. A novel AQM algorithm based on the PI controller with minimum ISTE[J]. Chinese Journal of Computers, 2012, 35(5): 951-963. . |
[4] | 裴畅姣, 卢汉成, 洪佩琳. 无线环境下具有实时约束的主动队列管理机制[J]. 电子与信息学报, 2013, 35(5): 1069-1075. Pei C J, Lu H C, Hong P L. Deadline-constrained active queue management mechanism in wireless networks[J]. Journal of Electronics & Information Technology, 2013, 35(5): 1069-1075. . |
[5] | 朱海婷, 丁伟, 缪丽华, 等. UDP流量对TCP往返延迟的影响[J]. 通信学报, 2013, 34(1): 19-29. Zhu H T, Ding W, Miao L H, et al. Effect of UDP traffic on TCP's round-trip delay[J]. Journal on Communications, 2013, 34(1): 19-29. . |
[6] | 蔡小玲, 范新丽. 不同队列管理机制对多媒体传输品质的影响[J]. 计算机应用, 2009, 29(12): 24-26. Cai X L, Fan X L. Effect on multimedia transmission for several queue management mechanisms[J]. Journal of Computer Applications, 2009, 29(12): 24-26. . |
[7] | 杨巧宁, 胡友山, 赵淑清, 等. 基于实时媒体服务质量的主动拥塞控制[C]//第19届中国IT网络信息技术电子仪器仪表创新学术会议. 2005: 179-186. Yang Q N, Hu Y S, Zhao S Q, et al. Active congestion control based on real-time media quality of service[C]//The 19th China Instruments Innovation Conference on IT Network Information Technology Electronic. 2005: 179-186. . |
[8] | Xu K X, Mario G, Qi L T, et al. TCP unfairness in Ad Hoc wireless networks and a neighborhood RED solution[J]. Wireless Networks, 2005, 11(4): 383-399. |
[9] | Huang Y S, Mao S W, Midkiff S. A control-theoretic approach to rate control for streaming videos[J]. IEEE Transactions on Multimedia, 2009, 11(6): 1072-1081. |
[10] | Hu W H, Xiao G X. Comments on “A control-theoretic approach to rate control for streaming videos”[DB/OL].. [2010-09]. |
[11] | Ke C H, Shieh C K, Hwang W S, et al. An evaluation framework for more realistic simulations of MPEG video transmission[J]. Journal of Information Science and Engineering, 2008, 24(2): 425-440. |
[12] | Santos C, Ribeiro E, Pedroso C. The application of neural networks to improve the quality of experience of video transmission over IP networks[J]. Engineering Applications of Artificial Intelligence, 2014, 27(1): 137-147. |
[13] | Geest V D. The binomial distribution with dependent Bernoulli trials[J]. Journal of Statistical Computation and Simulation, 2005, 75(2): 141-154. |
[14] | Gurtov A, Floyd S. Modeling wireless links for transport protocols[J]. ACM SIGCOMM Computer Communication Review, 2004, 34(2): 85-96. |
[15] | Hollot C, Misra V, Towsley D, et al. A control theoretic analysis of RED[C]//Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ, USA: IEEE, 2001: 1510-1519. |
[16] | 叶浩, 薛开平, 洪佩琳, 等. 无线Ad Hoc网络中一种网络无关的P2P流媒体优化传输方案[J]. 中国科学院研究生院学报, 2012, 29(4): 557-558. Ye H, Xue K P, Hong P L, et al. A network-independent transmission optimization mechanism for P2P streaming over wireless Ad Hoc networks[J].]. Journal of the Graduate School of the Chinese Academy of Sciences, 2012, 29(4): 557-558. |
[17] | 柯志亨, 程容祥, 邓德隽. NS2仿真实验[M]. 北京: 电子工业出版社, 2009: 268-270. Ke Z H, Chen R X, Deng D J. NS2 simulation experiment[M]. Beijing: Publishing House of Electronics Industry, 2009: 268-270. |
[18] | Lou C, Qiu L. QoS-aware scheduling and resource allocation for video streams in e-MBMS towards LTE-A system[C]//Vehicular Technology Conference. 2011: 1-5. |