基于扩展卡尔曼滤波器的网络队列预测

余菁菁

摘 要：为解决网络队列动态预测问题，提出一个网络系统在泊松分布流量和指数服务时间下的暂态队列行为预测模型并进行仿真验证。阐述基于扩展卡尔曼滤波（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.

（責任编辑：黄 健）