基于擴展卡爾曼濾波器的網絡隊列預測

余菁菁

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

關鍵詞：通信網絡;擴展卡爾曼濾波器;泊松流量;OPNET仿真;預測模型

DOI：10. 11907/rjdk. 192161 開放科學（資源服務）標識碼（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 引言

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

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

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

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

1.1 隊列模型

設置source和queue中的參數與圖2中的一致，得到數據包暫態數量如圖4所示。由于每次仿真都產生不同的泊松流量，對隊列大小影響較大，所以單次仿真并不能反映真實結果。因此，運行20次仿真后得到隊列大小的平均值如圖5所示。可以看到，經過多次平均后，實際隊列穩定后的大小與理論值基本一致，為之后正確預測奠定了很好的基礎。

3.2 隊列預測結果

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

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

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

4 結語

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

參考文獻：

[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濾波組合模型在邊坡監測中的應用[J]. 工程勘察， 2019， 47（3）：71-75.

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

[5] 任師濤， 史志才， 吳飛，等. ?基于改進BP神經網絡的路由器流量預測方法[J]. 傳感器與微系統， 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] 劉廣哲，張科，呂梅柏，等. 基于擴展卡爾曼濾波算法的雙模制導仿真研究[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.

（責任編輯：黃 健）