一种基于卡尔曼滤波的队列长度自适应算法*

张孝鹏， 王　平， 邢建春， 杨启亮，3

(1.解放军理工大学 国防工程学院，江苏 南京 210007；2.国防工程设备环境及智能化军队重点实验室(解放军理工大学)，江苏 南京 210007；3.计算机软件新技术国家重点实验室(南京大学)，江苏 南京 210093)



一种基于卡尔曼滤波的队列长度自适应算法*

张孝鹏1，2， 王平1，2， 邢建春1，2， 杨启亮1，2，3

(1.解放军理工大学 国防工程学院，江苏 南京 210007；2.国防工程设备环境及智能化军队重点实验室(解放军理工大学)，江苏 南京 210007；3.计算机软件新技术国家重点实验室(南京大学)，江苏 南京 210093)

摘要:传统主动队列管理(AQM)算法在处理传感器网络突发流时具有响应速度慢、抗网络突变性能弱的缺点。针对此问题，提出了一种新的AQM算法，算法首先将队列长度作为早期拥塞检测参量,运用卡尔曼滤波理论预测队列长度；其次根据队列长度在缓冲区的占用比来划分网络状态；最后根据不同占用比采取相应的丢包策略，自适应地调整丢包率，当出现网络突变时，加大调整幅度，使队列长度保持在理想区间。仿真实验表明：新算法能够较好地适应网络波动，提高网络服务质量(QoS)，算法综合性能优于主流AQM算法。

关键词：主动队列管理； 拥塞控制； 队列长度预测； 卡尔曼滤波； 自适应

0引言

在传感器网络中，由于传感器节点资源严重受限、通信链路易受干扰等因素，使得拥塞问题十分严重，因此,拥塞控制成为传感器网络服务质量保障机制的关键技术之一[1]。主动队列管理(active queue management,AQM)算法作为当前解决网络拥塞问题的一个主要途径，在降低丢包率、降低传输时延、抑制延时抖动等方面起到了重要作用。按照拥塞度量方法的不同，主要有基于队列度随机早期检测(random early detection,RED)[2]、比例积分(proportion integration,PI)[3]；基于链路负载尺度的BLUE[4]、自适应虚拟队列(adaptive virtual queue,AVQ)[5]；基于混合尺度的随机指数标记(random exponential marking,REM)[6]等算法。近年来，还有专家学者提出了一系列其他改进算法，例如：双资源队列(dual-resource queue)[7]、动态门限(dynamic threshold,DTH)[8]、扩散早期检测(diffusion early marking,DEM)[9]等算法。但是大部分AQM算法在稳定性、公平性、鲁棒性等方面都有一定的局限。

本文主要针对现有AQM算法中自适应调整能力较弱的问题进行研究，提出一种新的基于卡尔曼滤波的算法(Kalman filtering-based algorithm,KFA)，新算法运用卡尔曼滤波理论预测队列长度，根据队列长度在缓冲区的占用比来划分网络状态，自适应地调整丢包率使队列长度保持在理想区间，很好地兼顾了队列长度的长期稳定性和对网络突发流处理的及时性。

1基于卡尔曼滤波理论的队列长度预测机制

理想状况下，缓冲区队列长度应该保持在某一恒定范围内，但是由于受到网络“噪声”的影响，极易产生缓冲区队列长度波动，影响网络服务质量(quality of service,QoS)。因此，已有部分专家学者对稳定队列长度实现拥塞控制进行了研究。

增强稳定性的BLUE(stabilized blue,Sblue)算法[10]在计算队长时，采用了类似带权值低通滤波器(low-pass filter)的方法，“过滤”掉短期的队列长度变化，尽量反映长期的拥塞变化。但是，指数加权滑动平均引入了大惯性环节，使得网络需要经过较长时间才能达到稳定；并且，队列长度周期性震荡的网络，其平均队长却是稳定的。

带加速因子的自适应BLUE(self-tune accelerate blue,SAblue)[11]算法将瞬时队长作为早期拥塞检测参量和丢包概率步长调整的依据，这一算法避免了指数加权滑动平均引入的大惯性环节，但对网络波动过于敏感，导致丢包概率调整过于频繁。

1.1卡尔曼滤波队长预测机制

AQM算法丢包或标记包决策所基于的网络状态信息越准确，则决策就越科学合理[12]。本文提出利用卡尔曼滤波理论计算队列长度，卡尔曼滤波属于一种软件滤波方法，在网络QoS领域取得了一定的研究成果[13～15]。卡尔曼滤波主要包括两个过程：预估与校正[16]，基于这一思想，本文构造离散时间随机系统，通过队列长度和队列长度的一阶微分来预测下一时刻的队列长度。

若采样时间T足够小，则(n+1)T时刻的队列长度qn+1可用一阶差分方程表示

(1)

(2)

(3)

观测方程为yn+1=qn+1+en+1，en+1为观测噪声，是符合N(0,Rn)分布的高斯噪声，yn+1为(n+1)T时刻缓冲区中的总数据包数。观测方程也可以写成yn=Nxn+en，其中N=[10]。

综上，本文构建了一个离散时间随机系统，该系统通过状态方程和观测方程共同表示，分别描述状态向量和观测向量

(4)

根据卡尔曼滤波公式，可以得到以下方程：

时间更新方程

x-n+Mxn-1.

(5)

状态更新方程

P-n=MPn-1MT+Vn-1.

(6)

卡尔曼增益矩阵

Kn=P-nS-n，

(7)

Sn=P-n+Rn.

(8)

校正更新方程

xn=x-n+Kn(yn-x-n).

(9)

估计误差协方差

(10)

1.2Matlab仿真

在Matlab中对本文提出的卡尔曼滤波算法进行仿真。首先对恒定网络状况下的队列长度预测进行仿真，设置理想队列长度为300，取样次数为200次，仿真时间为10 s，设置预测值初值为0。仿真结果表明，即使是在预测初值与实际值相差很大的情况下，队列长度的预测值也能很快接近实际值，预测值与实际值非常接近，如图1所示。

图1　恒定网络状况下队列长度预测Fig 1　Prediction of queue length under constant network state

针对实际网络中存在大流量突发流的问题，在Matlab中进行仿真实验，仿真环境同上，但在4s时，加入噪声，引起队列长度的较大震荡，观察在网络波动情况下本文提出算法的预测效果。图2的仿真结果表明:当存在噪声影响时，队列长度的预测值很快接近实际值，预测值与实际值相差不大，为下一步的丢包策略调整提供早期拥塞检测信息。

图2　网络波动状况下队列长度预测Fig 2　Prediction of queue length under network fluctuation state

2基于网络状态区分的丢包策略

KFA的基本策略是将经卡尔曼滤波算法预测所得的缓冲区队列长度作为丢包概率调整的依据，根据网络负载程度调整丢包率。网络负载程度可以队列长度在缓冲区中的占用比来反应。KFA依据占用比θ将网络负载状态分为五个等级S1：θ∈[0，10 %)；S2：θ∈[10 %，30 %)；S3：θ∈[30 %，70 %)；S4：θ∈[70 %，90 %)；S5：θ∈[90 %，1]。

算法的目标是将网络负载保持在理想状态，当网络处于轻载状态S2和重载状态S4时，小幅度地调整丢包概率Pm使队列长度回到理想范围内。当网络处于空闲状态S1时，此时缓冲区资源没有得到充分利用，应大幅度减小丢包概率。当处于拥塞状态S5时，网络负担过重，即将发生路由器溢出，应大幅度增大丢包概率Pm。

算法伪代码如表1所示，其中,ΔH,ΔL为当前队列长度偏离率；β为调整因子，当网络处于网络轻载状态S2和网络重载状态S4时，应增大β的值；d1和d2分别决定了队长大于或小于理想状态时Pm增加的量。

3仿真实验

为了验证算法的性能，本文在NS2上进行仿真实验。实验的网络拓扑结构如图3所示。

图3　仿真拓扑结构Fig 3　Topological structure of simulation

假定R1～R2之间为瓶颈链路，S1～Sn为发送端，D1～Dn为接收端。R1～R2之间带宽为10Mbps，延迟时间为50ms，AQM算法在R1节点实现，分别为REM,PI,KFA，节点R1～

表1　算法伪代码

R2之间的最大队列长度为50个封包的队列长度。其他链路的带宽为100 Mbps，延迟时间为10 ms，且主动队列管理方式均为DropTail。

3.1不同传输控制协议连接数下算法性能比较

在实际网络环境中，连接到网络中的用户数处于不断变化的过程中，AQM算法应能适应网络的动态变化，对不同传输控制协议(transmission control protocol,TCP)连接数下的网络均具有良好的适应能力。本节对TCP连接数N=5i(i=1,2,…,10)情况下KFA,PI,REM算法的丢包率、平均延时、延时抖动进行仿真研究，如图4、图5、图6所示。

图4　不同TCP连接数下的丢包率对比Fig 4　Packet loss rate comparison of different TCP link number

图5　不同TCP连接数下的平均延时对比Fig 5　Average delay comparison of different TCP link number

图6　不同TCP连接数下的延时抖动对比Fig 6　Delay jitter comparison of different TCP link number

由仿真可知，随着TCP连接数的增大，KFA,PI,REM算法的总体变化趋势一致，性能较优，丢包率、端到端延时、延时抖动均随着连接数的增大而变大。但是在将三种算法进行横向比较时，又体现出性能差异，本文提出的KFA由于针对不同的网络状态制定相应的丢包策略，同时对缓冲区的队列长度进行有效控制，使得在数据包传递过程中充分利用网络资源，减少了网络空闲和队列溢出事件的发生，不同TCP连接数下网络突变带来的影响较小，算法性能与PI和REM相比具有一定优势。

3.2相同TCP连接数下算法性能比较

KFA根据不同的网络状态制定相应的丢包策略，通过调整丢包率使网络负载保持在理想状态，维持队列长度的稳定，避免队列溢出和路由器空闲现象的发生。本节将KFA与PI，REM相比较，设置TCP连接数N=50，仿真时间为50 s，其余参数同3.1节,算法性能比较如图7、图8。

图7　相同TCP连接数下KFA和PI实时队列长度对比Fig 7　Comparison of real-time queue length betweenKFA and PI with same TCP linking number

图8　相同TCP连接数下KFA和REM实时队列长度对比Fig 8　Comparison of real-time queue length betweenKFA and REM with same TCP linking number

由仿真可知，PI和REM长期处于满队列状态，且队长波动较大，调整速率较慢。KFA很好地将实施队列长度稳定在理想区间，队列长度占用比维持在30 %～70 %，实现了算法的初衷。在仿真开始阶段，由于数据包需要将缓冲区填满，因此，队列长度达到满队列，这是不可避免的。在到达满队列后算法采取分区间队列长度调整机制，对处于网络拥塞状态时的队长采取加大丢包率的措施，因此,队长很快回落到理想区间。在50s的仿真过程中，受到网络波动的影响，队列长度数次偏离理想区间，但是算法均能迅速调整，显示出了良好的自适应调整能力。

4结束语

针对传统AQM算法处理传感器网络突发流时具有响应速度慢、抗突变性能弱的缺点，本文提出了一种新的KFA。算法运用卡尔曼滤波理论预测队列长度，提前感知网络变化，为丢包策略的及时调整提供理论，解决了响应速度慢的问题；针对不同的队列长度占用比采取不同的丢包策略，在队列长度偏离理想区间较大时增大丢包率调整幅度，将队列长度稳定在理想区间，解决了抗网络突变性能差的问题。仿真表明：算法综合性能优于PI，REM等主流AQM算法。

参考文献:

[1]孙利民,李波,周新运.无线传感器网络的拥塞控制技术[J].计算机研究与发展,2008(1):007.

[2]Floyd S,Jacobson V.Random early detection gateways for congestion avoidance[J].IEEE/ACM Transactions on Networking,1993,1(4):397-413.

[3]Hollot C V,Misra V,Towsley D,et al.On designing improved controllers for AQM routers supporting TCP flows[C]∥Procee-dings of Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies,INFOCOM 2001，IEEE,2001:1726-1734.

[4]Feng W,Kandlur D,Saha D,et al.BLUE:A new class of active queue management algorithms[J].Ann Arbor,1999,1001:48105.

[5]Kunniyur S S,Srikant R.An adaptive virtual queue(AVQ)algorithm for active queue management[J].IEEE/ACM Transactions on Networking,2004,12(2):286-299.

[6]Athuraliya S,Low S H,Li V H,et al.REM:Active queue management[J].Network,IEEE,2001,15(3):48-53.

[7]Shin M,Chong S,Rhee I.Dual-resource TCP/AQM for proces-sing-constrained networks[J].IEEE/ACM Transactions on Networking(TON),2008,16(2):435-449.

[8]Lim L B,Guan L,Grigg A,et al.Controlling mean queuing delay under multi-class bursty and correlated traffic[J].Journal of Computer and System Sciences,2011,77(5):898-916.

[9]Barrera I D,Arce G R,Bohacek S.Statistical approach for congestion control in gateway routers[J].Computer Networks,2011,55(3):572-582.

[10] 吴春明,姜明.SBlue:一种增强Blue稳定性的主动式队列管理算法[J].通信学报,2005,26(3):68-74.

[11] 陈伟杰,王万良,蒋一波,等.SABlue:一种带加速因子的自适应AQM算法[J].电子与信息学报,2011,33(2):479-483.

[12] 任丰原,林闯,黄小猛,等.主动队列管理算法的分类器实现[J].电子学报,2004,32(11):1796-1800.

[13] 那振宇.卫星互联网服务质量保障方法研究[D].哈尔滨:哈尔滨工业大学,2010.

[14] Cotter S F,Murthi M N.Target tracking-based network active queue management[C]∥IEEE International Conference on Acoustics,Speech and Signal Processing,ICASSP 2009,IEEE,2009:2757-2760.

[15] 杨歆豪.基于控制理论的网络拥塞控制中的若干算法研究[D].南京:南京理工大学,2010.

[16] 邓自立.卡尔曼滤波与维纳滤波[M].哈尔滨：哈尔滨工业大学出版社,2001.

张孝鹏(1991-)，男，江苏盐城人，硕士研究生，研究方向为军事工程物联网、传感器网络、网络拥塞控制。

王平，通讯作者，E—mail：wp893@sina.com。

An adaptive queue length algorithm based on Kalman filtering*

ZHANG Xiao-peng1,2, WANG Ping1,2, XING Jian-chun1,2, YANG Qi-liang1,2,3

(1.College of Defense Engineering,PLA University of Science and Technology,Nanjing 210007,China; 2.Key Laboratory of PLA for Device,Environment and Intelligent System of Defense Engineering, PLA University of Science and Technology,Nanjing 210007,China; 3.State Key Laboratory for Software Novel Technology,Nanjing University,Nanjing 210093,China)

Abstract:Traditional active queue management(AQM)algorithm has shortcomings of slow response and weak performance of dealing with sudden flow in sensor networks.To solve this problem, propose a new AQM algorithm,firstly the algorithm put queue length as an early congestion detection parameters,predict the queue length by Kalman filtering theory;secondly the algorithm divides network status according to occupancy ratio of queue length in buffer zone;finally,the algorithm takes corresponding packet loss strategy according to different occupancy ratio,adjust packet loss rate adaptively,when network mutation occurs,algorithm increase adjustment amplitude to make queue length remains at desired interval.Simulation results show that the new algorithm can adapt to network fluctuations better and improve network quality of service(QoS),comprehensive performance of the new algorithm is better than mainstream AQM algorithms.

Key words:active queue management(AQM); congestion control; queue length prediction; Kalman filtering; adaptive

作者简介:

中图分类号：TP 393

文献标识码：A

文章编号：1000—9787(2016)01—0131—04

*基金项目：国家自然科学基金资助项目(61321491)

收稿日期：2015—11—09

DOI:10.13873/J.1000—9787(2016)01—0131—04