基于擴展卡爾曼濾波器的網(wǎng)絡(luò)隊列預(yù)測

余菁菁

摘 要：為解決網(wǎng)絡(luò)隊列動態(tài)預(yù)測問題，提出一個網(wǎng)絡(luò)系統(tǒng)在泊松分布流量和指數(shù)服務(wù)時間下的暫態(tài)隊列行為預(yù)測模型并進行仿真驗證。闡述基于擴展卡爾曼濾波（Kalman）的預(yù)測模型及其具體算法，結(jié)合網(wǎng)絡(luò)中的數(shù)據(jù)流量特性，構(gòu)建基于擴展卡爾曼濾波器的網(wǎng)絡(luò)暫態(tài)隊列預(yù)測模型，并根據(jù)仿真網(wǎng)絡(luò)中的實際數(shù)據(jù)對模型進行驗證。實驗結(jié)果表明，所建立的網(wǎng)絡(luò)暫態(tài)隊列實時預(yù)測模型預(yù)測效果比較理想，基本與實時隊列長度保持一致。因此，該模型可以較低的代價應(yīng)用于網(wǎng)絡(luò)中的動態(tài)路由算法及擁塞控制算法中。

關(guān)鍵詞：通信網(wǎng)絡(luò);擴展卡爾曼濾波器;泊松流量;OPNET仿真;預(yù)測模型

DOI：10. 11907/rjdk. 192161 開放科學(xué)（資源服務(wù)）標識碼（OSID）：

中圖分類號：TP393文獻標識碼：A 文章編號：1672-7800（2020）008-0212-04

Abstract： In order to solve the problem of network queue estimator dynamically， this paper presents the derivation of the transient queue behavior for a network with Poisson traffic and exponential service times and the result is then validated. The extended Kalman filter theory is presented and a network state estimator is designed using the transient queue behavior model combing with networks traffic trait. The behavior of the network state estimator is then investigated using traffic data from the simulated network. Simulation results show that the proposed scheme have a good prediction of queue size in network， and the prediction results are consistent with the real-time queue length， so it can be used in the algorithm of dynamic routing and congestion control algorithm with low cost.

Key Words： communication network; extended Kalman filter; poisson traffic; OPNET simulation; network state estimator

0 引言

現(xiàn)有絕大部分路由算法、流量控制算法和擁塞控制算法都是針對相對固定的網(wǎng)絡(luò)設(shè)計的，沒有考慮網(wǎng)絡(luò)的隨機變化特征，所以這些靜態(tài)算法對于動態(tài)變化的網(wǎng)絡(luò)（如Ad-hoc網(wǎng)絡(luò)、傳感器網(wǎng)絡(luò)和車載網(wǎng)絡(luò)等）效果不佳。如果對網(wǎng)絡(luò)的隨機特征可以精確建模，即利用過去的狀態(tài)估計現(xiàn)在狀態(tài)及預(yù)測未來狀態(tài)，則可利用該模型設(shè)計適合動態(tài)變化的路由算法、流量控制算法和擁塞控制算法等。

現(xiàn)有研究主要是對網(wǎng)絡(luò)流量進行預(yù)測，分為線性預(yù)測和非線性預(yù)測。線性預(yù)測具有代表性的是ARIMA[1-2]，其前提是網(wǎng)絡(luò)流量具有線性寬平穩(wěn)過程特征，但其預(yù)測精度較低，無法準確描述出網(wǎng)絡(luò)全部特征。文獻[3]提出基于卡爾曼濾波的流量預(yù)測，其引入狀態(tài)方程和測量方程，有效處理了系統(tǒng)噪聲和測量噪聲，從一定程度上提高了預(yù)測精度;非線性預(yù)測具有代表性的是小波分析[4]和神經(jīng)網(wǎng)絡(luò)[5]，但基于小波分析的模型預(yù)測實時性較差，基于神經(jīng)網(wǎng)絡(luò)的模型收斂速度慢，且容易陷入局部次優(yōu)。文獻[6]、[7]提出將卡爾曼濾波與小波分析相結(jié)合的預(yù)測模型，提高了預(yù)測精度?？梢钥闯?，以上研究都是對網(wǎng)絡(luò)流量整體建立一個預(yù)測模型，而沒有對路由器端口的某一特定隊列進行建模預(yù)測，因此這些預(yù)測模型不能直接運用到動態(tài)路由算法中，無法實現(xiàn)對路由器端口進行實時調(diào)整的目標。為了更加精確地預(yù)測網(wǎng)絡(luò)流量狀態(tài)，本文主要基于路由器端口隊列對網(wǎng)絡(luò)狀態(tài)進行研究。

一般認為通信網(wǎng)絡(luò)是一個排隊網(wǎng)絡(luò)，隊列是網(wǎng)絡(luò)中的一個重要組成部分，隊列大小從某種程度上可以表示此刻網(wǎng)絡(luò)的狀態(tài)，所以本文主要研究網(wǎng)絡(luò)隊列狀態(tài)建模與估計。通過對網(wǎng)絡(luò)隊列暫態(tài)行為進行建模，并將其測量值輸入擴展卡爾曼濾波器以預(yù)測網(wǎng)絡(luò)狀態(tài)。仿真結(jié)果表明，該方法預(yù)測效果比較理想，可應(yīng)用于網(wǎng)絡(luò)中的動態(tài)路由算法和擁塞控制算法中。

1 隊列模型與擴展卡爾曼濾波理論

1.1 隊列模型

設(shè)置source和queue中的參數(shù)與圖2中的一致，得到數(shù)據(jù)包暫態(tài)數(shù)量如圖4所示。由于每次仿真都產(chǎn)生不同的泊松流量，對隊列大小影響較大，所以單次仿真并不能反映真實結(jié)果。因此，運行20次仿真后得到隊列大小的平均值如圖5所示?？梢钥吹?，經(jīng)過多次平均后，實際隊列穩(wěn)定后的大小與理論值基本一致，為之后正確預(yù)測奠定了很好的基礎(chǔ)。

3.2 隊列預(yù)測結(jié)果

上文內(nèi)容給出了單個隊列的行為，下面研究組成網(wǎng)絡(luò)后隊列的行為。在給定包含噪聲的觀測值后，通過擴展卡爾曼濾波預(yù)測隊列大小。擴展卡爾曼濾波在Matlab上實現(xiàn)，本文采用芬蘭埃斯波赫爾辛基理工大學(xué)提供的EKF擴展卡爾曼濾波工具箱，網(wǎng)絡(luò)中的實際流量通過OPNET仿真得到。網(wǎng)絡(luò)拓撲采用簡單的直線型結(jié)構(gòu)，路由協(xié)議采用RIP，如圖6所示。通過定義Application和Profile模塊，從而定義兩個終端的通信類型，這里采用TCP服務(wù)。

運行仿真100s后，觀測Router1中的隊列大小，得到結(jié)果如圖7中藍線所示。本文設(shè)置采樣間隔為10s，即每10s采集一次實際路由器隊列長度，加上強度為12的高斯白噪聲之后，輸入到擴展卡爾曼濾波器中，得到的預(yù)測結(jié)果如圖7中紅線所示。橫坐標為采樣時刻，縱坐標為隊列大小，從圖中可以看出，預(yù)測結(jié)果走勢與網(wǎng)絡(luò)實際情況基本一致，完全能夠滿足實際需要，所以該方法可運用到網(wǎng)絡(luò)中的動態(tài)路由算法和擁塞控制算法中。

然而，預(yù)測結(jié)果與實際情況還有細微差別，下一步工作要從更加精確的隊列模型及其它預(yù)測方法入手，以更準確地預(yù)測網(wǎng)絡(luò)中的隊列大小。

4 結(jié)語

在動態(tài)路由和擁塞控制方法中，必須知道網(wǎng)絡(luò)實時狀態(tài)才能動態(tài)調(diào)整采取的策略。本文提出一種基于擴展卡爾曼濾波方法的網(wǎng)絡(luò)隊列預(yù)測方案，實驗結(jié)果表明，該方法能夠預(yù)測網(wǎng)絡(luò)隊列大小的大致走勢，可將該方案運用于動態(tài)路由、流量控制及擁塞控制等算法，對網(wǎng)絡(luò)路由與擁塞策略進行實時調(diào)整，從而避免因?qū)崟r測量網(wǎng)絡(luò)狀態(tài)帶來較大代價。在本方案中，隊列模型的準確性與噪聲的相關(guān)性都會影響預(yù)測結(jié)果，而且只預(yù)測了隊列大小。針對這些問題，下一步將采用其它隊列模型和預(yù)測方法以更準確地預(yù)測網(wǎng)絡(luò)狀態(tài)，并預(yù)測延遲等其它狀態(tài)量。

參考文獻：

[1] YU G，ZHANG C. Switching ARIMA model based forecasting for traffic flow [C]. International Conference on Acoustics， Speech， and Signal Processing，2004： 429-432.

[2] XU C， LI Z，WANG W. Short-term traffic flow prediction using a methodology based on autoregressive integrated moving average and genetic programming[J]. ?Transport， 2016， 31（3）：343-358.

[3] 伍錫銹. 基于小波分析的Kalman濾波組合模型在邊坡監(jiān)測中的應(yīng)用[J]. 工程勘察， 2019， 47（3）：71-75.

[4] 崔楊， 曲鈺， 王錚，等. 基于Daubechies6離散小波的風(fēng)電集群功率匯聚效應(yīng)的時頻特性分析[J]. 中國電機工程學(xué)報， 2019， 39（3）：38-48，320.

[5] 任師濤， 史志才， 吳飛，等. ?基于改進BP神經(jīng)網(wǎng)絡(luò)的路由器流量預(yù)測方法[J]. 傳感器與微系統(tǒng)， 2018（8）：49-50，54.

[6] LI Y， CHAO W， GONG J. A wavelet transform‐adaptive unscented Kalman filter approach for state of charge estimation of LiFePo4 battery[J]. ?International Journal of Energy Research， 2018， 42（2）：587-600.

[7] MOHAMMADI F， FARD A F， GHORBANI M A. Application of cross-wavelet-linear programming-Kalman filter and GIUH methods in rainfall-runoff modeling[J]. ?Environmental Earth Sciences， 2019.

[8] GROSS D，HARRIS C M.Fundamentals of queuing theory [M]. New York：Wiley-Interscience，1998.

[9] PERSONE V D N， BALSAMO S， ONVURAL R. Analysis of queueing networks with blocking[M]. Dordorecht： Dore Kluwer Academic Publishers， 2001.

[10] PERSONE V D N， CASALE G， SMIRNI E. Approximate analysis of blocking queueing networks with temporal dependence [C]. ?Hong Kong： IEEE/IFIP International Conference on Dependable Systems&networks， 2011.

[11] ZHENG Y， GAO W， OUYANG M， et al. State-of-charge inconsistency estimation of lithium-ion battery pack using mean-difference model and extended Kalman filter[J]. Journal of Power Sources， 2018，（383）：50-58.

[12] 劉廣哲，張科，呂梅柏，等. 基于擴展卡爾曼濾波算法的雙模制導(dǎo)仿真研究[J]. 航空兵器，2018（1）：27-32.

[13] WITKOVSKY V. Matlab algorithm mixed.m for solving Hendersons mixed model equations[M]. ?New York： Social Science Electronic Publishing，2002.

[14] PRASAD K，ASHLESH R M，PRASAD C，et al. An automated method using MATLAB to identify the adductor sesamoid for determining the onset of puberty and assessing the skeletal age in children[M]. Singapore： New York，2019.

[15] GUILLEMIN F， SLIM F. Sojourn time in an M/M/1 processor sharing queue with permanent customers[J]. Stochastic Models， 2018， 34（4）：1-23.

[16] XU X， WANG X， SONG X， et al. Fluid model modulated by an M/M/1 working vacation queue with negative customer[J]. ?Acta Mathematicae Applicatae Sinica， 2018， 34（2）：404-415.

[17] PAHLEVAN M，OBERMAISSER R. Evaluation of time-triggered traffic in time-sensitive networks using the OPNET simulation framework[C]. IEEE 2018 26th Euromicro International Conference on Parallel，Distributed and Network-based Processing，2018：283-287.

[18] CHONG C， ZUO Y Q， ZHANG F. Research on comprehensive performance simulation of communication IP network based on OPNET[C]. International Conference on Intelligent Transportation，2018：195-197.

[19] RASHID T A， BARZNJI A O. A virtualized computer network for Salahaddin university new campus of HTTP services using OPNET simulator[M]. ?Berlin： ?Springer， 2018.

（責(zé)任編輯：黃 ?。?/p>