一種基于卡爾曼濾波的隊列長度自適應(yīng)算法*

張孝鵬， 王　平， 邢建春， 楊啟亮，3

(1.解放軍理工大學 國防工程學院，江蘇 南京 210007；2.國防工程設(shè)備環(huán)境及智能化軍隊重點實驗室(解放軍理工大學)，江蘇 南京 210007；3.計算機軟件新技術(shù)國家重點實驗室(南京大學)，江蘇 南京 210093)

?

一種基于卡爾曼濾波的隊列長度自適應(yīng)算法*

張孝鵬1，2， 王平1，2， 邢建春1，2， 楊啟亮1，2，3

(1.解放軍理工大學 國防工程學院，江蘇 南京 210007；2.國防工程設(shè)備環(huán)境及智能化軍隊重點實驗室(解放軍理工大學)，江蘇 南京 210007；3.計算機軟件新技術(shù)國家重點實驗室(南京大學)，江蘇 南京 210093)

摘要:傳統(tǒng)主動隊列管理(AQM)算法在處理傳感器網(wǎng)絡(luò)突發(fā)流時具有響應(yīng)速度慢、抗網(wǎng)絡(luò)突變性能弱的缺點。針對此問題，提出了一種新的AQM算法，算法首先將隊列長度作為早期擁塞檢測參量,運用卡爾曼濾波理論預(yù)測隊列長度；其次根據(jù)隊列長度在緩沖區(qū)的占用比來劃分網(wǎng)絡(luò)狀態(tài)；最后根據(jù)不同占用比采取相應(yīng)的丟包策略，自適應(yīng)地調(diào)整丟包率，當出現(xiàn)網(wǎng)絡(luò)突變時，加大調(diào)整幅度，使隊列長度保持在理想?yún)^(qū)間。仿真實驗表明：新算法能夠較好地適應(yīng)網(wǎng)絡(luò)波動，提高網(wǎng)絡(luò)服務(wù)質(zhì)量(QoS)，算法綜合性能優(yōu)于主流AQM算法。

關(guān)鍵詞：主動隊列管理； 擁塞控制； 隊列長度預(yù)測； 卡爾曼濾波； 自適應(yīng)

0引言

在傳感器網(wǎng)絡(luò)中，由于傳感器節(jié)點資源嚴重受限、通信鏈路易受干擾等因素，使得擁塞問題十分嚴重，因此,擁塞控制成為傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量保障機制的關(guān)鍵技術(shù)之一[1]。主動隊列管理(active queue management,AQM)算法作為當前解決網(wǎng)絡(luò)擁塞問題的一個主要途徑，在降低丟包率、降低傳輸時延、抑制延時抖動等方面起到了重要作用。按照擁塞度量方法的不同，主要有基于隊列度隨機早期檢測(random early detection,RED)[2]、比例積分(proportion integration,PI)[3]；基于鏈路負載尺度的BLUE[4]、自適應(yīng)虛擬隊列(adaptive virtual queue,AVQ)[5]；基于混合尺度的隨機指數(shù)標記(random exponential marking,REM)[6]等算法。近年來，還有專家學者提出了一系列其他改進算法，例如：雙資源隊列(dual-resource queue)[7]、動態(tài)門限(dynamic threshold,DTH)[8]、擴散早期檢測(diffusion early marking,DEM)[9]等算法。但是大部分AQM算法在穩(wěn)定性、公平性、魯棒性等方面都有一定的局限。

本文主要針對現(xiàn)有AQM算法中自適應(yīng)調(diào)整能力較弱的問題進行研究，提出一種新的基于卡爾曼濾波的算法(Kalman filtering-based algorithm,KFA)，新算法運用卡爾曼濾波理論預(yù)測隊列長度，根據(jù)隊列長度在緩沖區(qū)的占用比來劃分網(wǎng)絡(luò)狀態(tài)，自適應(yīng)地調(diào)整丟包率使隊列長度保持在理想?yún)^(qū)間，很好地兼顧了隊列長度的長期穩(wěn)定性和對網(wǎng)絡(luò)突發(fā)流處理的及時性。

1基于卡爾曼濾波理論的隊列長度預(yù)測機制

理想狀況下，緩沖區(qū)隊列長度應(yīng)該保持在某一恒定范圍內(nèi)，但是由于受到網(wǎng)絡(luò)“噪聲”的影響，極易產(chǎn)生緩沖區(qū)隊列長度波動，影響網(wǎng)絡(luò)服務(wù)質(zhì)量(quality of service,QoS)。因此，已有部分專家學者對穩(wěn)定隊列長度實現(xiàn)擁塞控制進行了研究。

增強穩(wěn)定性的BLUE(stabilized blue,Sblue)算法[10]在計算隊長時，采用了類似帶權(quán)值低通濾波器(low-pass filter)的方法，“過濾”掉短期的隊列長度變化，盡量反映長期的擁塞變化。但是，指數(shù)加權(quán)滑動平均引入了大慣性環(huán)節(jié)，使得網(wǎng)絡(luò)需要經(jīng)過較長時間才能達到穩(wěn)定；并且，隊列長度周期性震蕩的網(wǎng)絡(luò)，其平均隊長卻是穩(wěn)定的。

帶加速因子的自適應(yīng)BLUE(self-tune accelerate blue,SAblue)[11]算法將瞬時隊長作為早期擁塞檢測參量和丟包概率步長調(diào)整的依據(jù)，這一算法避免了指數(shù)加權(quán)滑動平均引入的大慣性環(huán)節(jié)，但對網(wǎng)絡(luò)波動過于敏感，導致丟包概率調(diào)整過于頻繁。

1.1卡爾曼濾波隊長預(yù)測機制

AQM算法丟包或標記包決策所基于的網(wǎng)絡(luò)狀態(tài)信息越準確，則決策就越科學合理[12]。本文提出利用卡爾曼濾波理論計算隊列長度，卡爾曼濾波屬于一種軟件濾波方法，在網(wǎng)絡(luò)QoS領(lǐng)域取得了一定的研究成果[13～15]。卡爾曼濾波主要包括兩個過程：預(yù)估與校正[16]，基于這一思想，本文構(gòu)造離散時間隨機系統(tǒng)，通過隊列長度和隊列長度的一階微分來預(yù)測下一時刻的隊列長度。

若采樣時間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時刻緩沖區(qū)中的總數(shù)據(jù)包數(shù)。觀測方程也可以寫成yn=Nxn+en，其中N=[10]。

綜上，本文構(gòu)建了一個離散時間隨機系統(tǒng)，該系統(tǒng)通過狀態(tài)方程和觀測方程共同表示，分別描述狀態(tài)向量和觀測向量

(4)

根據(jù)卡爾曼濾波公式，可以得到以下方程：

時間更新方程

x-n+Mxn-1.

(5)

狀態(tài)更新方程

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)

估計誤差協(xié)方差

(10)

1.2Matlab仿真

在Matlab中對本文提出的卡爾曼濾波算法進行仿真。首先對恒定網(wǎng)絡(luò)狀況下的隊列長度預(yù)測進行仿真，設(shè)置理想隊列長度為300，取樣次數(shù)為200次，仿真時間為10 s，設(shè)置預(yù)測值初值為0。仿真結(jié)果表明，即使是在預(yù)測初值與實際值相差很大的情況下，隊列長度的預(yù)測值也能很快接近實際值，預(yù)測值與實際值非常接近，如圖1所示。

圖1　恒定網(wǎng)絡(luò)狀況下隊列長度預(yù)測Fig 1　Prediction of queue length under constant network state

針對實際網(wǎng)絡(luò)中存在大流量突發(fā)流的問題，在Matlab中進行仿真實驗，仿真環(huán)境同上，但在4s時，加入噪聲，引起隊列長度的較大震蕩，觀察在網(wǎng)絡(luò)波動情況下本文提出算法的預(yù)測效果。圖2的仿真結(jié)果表明:當存在噪聲影響時，隊列長度的預(yù)測值很快接近實際值，預(yù)測值與實際值相差不大，為下一步的丟包策略調(diào)整提供早期擁塞檢測信息。

圖2　網(wǎng)絡(luò)波動狀況下隊列長度預(yù)測Fig 2　Prediction of queue length under network fluctuation state

2基于網(wǎng)絡(luò)狀態(tài)區(qū)分的丟包策略

KFA的基本策略是將經(jīng)卡爾曼濾波算法預(yù)測所得的緩沖區(qū)隊列長度作為丟包概率調(diào)整的依據(jù)，根據(jù)網(wǎng)絡(luò)負載程度調(diào)整丟包率。網(wǎng)絡(luò)負載程度可以隊列長度在緩沖區(qū)中的占用比來反應(yīng)。KFA依據(jù)占用比θ將網(wǎng)絡(luò)負載狀態(tài)分為五個等級S1：θ∈[0，10 %)；S2：θ∈[10 %，30 %)；S3：θ∈[30 %，70 %)；S4：θ∈[70 %，90 %)；S5：θ∈[90 %，1]。

算法的目標是將網(wǎng)絡(luò)負載保持在理想狀態(tài)，當網(wǎng)絡(luò)處于輕載狀態(tài)S2和重載狀態(tài)S4時，小幅度地調(diào)整丟包概率Pm使隊列長度回到理想范圍內(nèi)。當網(wǎng)絡(luò)處于空閑狀態(tài)S1時，此時緩沖區(qū)資源沒有得到充分利用，應(yīng)大幅度減小丟包概率。當處于擁塞狀態(tài)S5時，網(wǎng)絡(luò)負擔過重，即將發(fā)生路由器溢出，應(yīng)大幅度增大丟包概率Pm。

算法偽代碼如表1所示，其中,ΔH,ΔL為當前隊列長度偏離率；β為調(diào)整因子，當網(wǎng)絡(luò)處于網(wǎng)絡(luò)輕載狀態(tài)S2和網(wǎng)絡(luò)重載狀態(tài)S4時，應(yīng)增大β的值；d1和d2分別決定了隊長大于或小于理想狀態(tài)時Pm增加的量。

3仿真實驗

為了驗證算法的性能，本文在NS2上進行仿真實驗。實驗的網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖3所示。

圖3　仿真拓撲結(jié)構(gòu)Fig 3　Topological structure of simulation

假定R1～R2之間為瓶頸鏈路，S1～Sn為發(fā)送端，D1～Dn為接收端。R1～R2之間帶寬為10Mbps，延遲時間為50ms，AQM算法在R1節(jié)點實現(xiàn)，分別為REM,PI,KFA，節(jié)點R1～

表1　算法偽代碼

R2之間的最大隊列長度為50個封包的隊列長度。其他鏈路的帶寬為100 Mbps，延遲時間為10 ms，且主動隊列管理方式均為DropTail。

3.1不同傳輸控制協(xié)議連接數(shù)下算法性能比較

在實際網(wǎng)絡(luò)環(huán)境中，連接到網(wǎng)絡(luò)中的用戶數(shù)處于不斷變化的過程中，AQM算法應(yīng)能適應(yīng)網(wǎng)絡(luò)的動態(tài)變化，對不同傳輸控制協(xié)議(transmission control protocol,TCP)連接數(shù)下的網(wǎng)絡(luò)均具有良好的適應(yīng)能力。本節(jié)對TCP連接數(shù)N=5i(i=1,2,…,10)情況下KFA,PI,REM算法的丟包率、平均延時、延時抖動進行仿真研究，如圖4、圖5、圖6所示。

圖4　不同TCP連接數(shù)下的丟包率對比Fig 4　Packet loss rate comparison of different TCP link number

圖5　不同TCP連接數(shù)下的平均延時對比Fig 5　Average delay comparison of different TCP link number

圖6　不同TCP連接數(shù)下的延時抖動對比Fig 6　Delay jitter comparison of different TCP link number

由仿真可知，隨著TCP連接數(shù)的增大，KFA,PI,REM算法的總體變化趨勢一致，性能較優(yōu)，丟包率、端到端延時、延時抖動均隨著連接數(shù)的增大而變大。但是在將三種算法進行橫向比較時，又體現(xiàn)出性能差異，本文提出的KFA由于針對不同的網(wǎng)絡(luò)狀態(tài)制定相應(yīng)的丟包策略，同時對緩沖區(qū)的隊列長度進行有效控制，使得在數(shù)據(jù)包傳遞過程中充分利用網(wǎng)絡(luò)資源，減少了網(wǎng)絡(luò)空閑和隊列溢出事件的發(fā)生，不同TCP連接數(shù)下網(wǎng)絡(luò)突變帶來的影響較小，算法性能與PI和REM相比具有一定優(yōu)勢。

3.2相同TCP連接數(shù)下算法性能比較

KFA根據(jù)不同的網(wǎng)絡(luò)狀態(tài)制定相應(yīng)的丟包策略，通過調(diào)整丟包率使網(wǎng)絡(luò)負載保持在理想狀態(tài)，維持隊列長度的穩(wěn)定，避免隊列溢出和路由器空閑現(xiàn)象的發(fā)生。本節(jié)將KFA與PI，REM相比較，設(shè)置TCP連接數(shù)N=50，仿真時間為50 s，其余參數(shù)同3.1節(jié),算法性能比較如圖7、圖8。

圖7　相同TCP連接數(shù)下KFA和PI實時隊列長度對比Fig 7　Comparison of real-time queue length betweenKFA and PI with same TCP linking number

圖8　相同TCP連接數(shù)下KFA和REM實時隊列長度對比Fig 8　Comparison of real-time queue length betweenKFA and REM with same TCP linking number

由仿真可知，PI和REM長期處于滿隊列狀態(tài)，且隊長波動較大，調(diào)整速率較慢。KFA很好地將實施隊列長度穩(wěn)定在理想?yún)^(qū)間，隊列長度占用比維持在30 %～70 %，實現(xiàn)了算法的初衷。在仿真開始階段，由于數(shù)據(jù)包需要將緩沖區(qū)填滿，因此，隊列長度達到滿隊列，這是不可避免的。在到達滿隊列后算法采取分區(qū)間隊列長度調(diào)整機制，對處于網(wǎng)絡(luò)擁塞狀態(tài)時的隊長采取加大丟包率的措施，因此,隊長很快回落到理想?yún)^(qū)間。在50s的仿真過程中，受到網(wǎng)絡(luò)波動的影響，隊列長度數(shù)次偏離理想?yún)^(qū)間，但是算法均能迅速調(diào)整，顯示出了良好的自適應(yīng)調(diào)整能力。

4結(jié)束語

針對傳統(tǒng)AQM算法處理傳感器網(wǎng)絡(luò)突發(fā)流時具有響應(yīng)速度慢、抗突變性能弱的缺點，本文提出了一種新的KFA。算法運用卡爾曼濾波理論預(yù)測隊列長度，提前感知網(wǎng)絡(luò)變化，為丟包策略的及時調(diào)整提供理論，解決了響應(yīng)速度慢的問題；針對不同的隊列長度占用比采取不同的丟包策略，在隊列長度偏離理想?yún)^(qū)間較大時增大丟包率調(diào)整幅度，將隊列長度穩(wěn)定在理想?yún)^(qū)間，解決了抗網(wǎng)絡(luò)突變性能差的問題。仿真表明：算法綜合性能優(yōu)于PI，REM等主流AQM算法。

參考文獻:

[1]孫利民,李波,周新運.無線傳感器網(wǎng)絡(luò)的擁塞控制技術(shù)[J].計算機研究與發(fā)展,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穩(wěn)定性的主動式隊列管理算法[J].通信學報,2005,26(3):68-74.

[11] 陳偉杰,王萬良,蔣一波,等.SABlue:一種帶加速因子的自適應(yīng)AQM算法[J].電子與信息學報,2011,33(2):479-483.

[12] 任豐原,林闖,黃小猛,等.主動隊列管理算法的分類器實現(xiàn)[J].電子學報,2004,32(11):1796-1800.

[13] 那振宇.衛(wèi)星互聯(lián)網(wǎng)服務(wù)質(zhì)量保障方法研究[D].哈爾濱:哈爾濱工業(yè)大學,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] 楊歆豪.基于控制理論的網(wǎng)絡(luò)擁塞控制中的若干算法研究[D].南京:南京理工大學,2010.

[16] 鄧自立.卡爾曼濾波與維納濾波[M].哈爾濱：哈爾濱工業(yè)大學出版社,2001.

張孝鵬(1991-)，男，江蘇鹽城人，碩士研究生，研究方向為軍事工程物聯(lián)網(wǎng)、傳感器網(wǎng)絡(luò)、網(wǎng)絡(luò)擁塞控制。

王平，通訊作者，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