, 金建宇3, 李琨21. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
2. 渤海大学 工学院, 辽宁 锦州 121013;
3. 东北大学 国防教育学院, 辽宁 沈阳 110819
收稿日期：2016-10-21
基金项目：国家自然科学基金资助项目(61773108，61403040)。
作者简介：韩莹(1982-)，女，辽宁锦州人，东北大学博士研究生;
井元伟(1956-)，男，辽宁沈阳人，东北大学教授，博士生导师。
摘要：网络流量数据序列具有混沌特性.相空间重构后, 采用一种改进黑洞算法优化回声状态网络的非线性模型对网络流量进行预测.改进黑洞算法是在现有工作的基础上提出一种新的新解生成机制, 可以提高算法的收敛速度和精度; 相比于遗传算法、和声搜索算法等其他优化算法, 所提出的改进黑洞算法不依赖自身相关参数的准确设定; 将其应用于回声状态网络4个重要参数的优化选取, 使得预测模型具有较好的预测稳定性.通过Mackey-Glass混沌时间序列和网络流量公共数据集的仿真实验，结果表明所提出的方法具有较好的预测性能.
关键词：网络流量混沌时间序列回声状态网络黑洞算法预测
Network Traffic Short-Term Prediction Based on Echo State Network Optimized by Improved Black Hole Algorithm
HAN Ying1,2, JING Yuan-wei1
, JIN Jian-yu3, LI Kun21. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. College of Engineering, Bohai University, Jinzhou 121013, China;
3. School of National Defense Education, Northeastern University, Shenyang 110819, China
Corresponding author: JING Yuan-wei, E-mail: jingyuanwei@ise.neu.edu.cn
Abstract: The network traffic data series has chaos characteristics. After phase space reconstruction, a nonlinear prediction model based on echo state network (ESN) optimized by improved black hole (BH) was used to predict network traffic. The improved BH algorithm is a new mechanism for new-solution generation based on current works, which can increase the algorithm's convergence speed and precision. Compared with other optimization algorithms, such as genetic algorithm (GA), harmony search (HS) algorithm, etc, the proposed improved BH algorithm is not affected by the accuracy of the setting for some parameters of itself. It is used to optimally select four key parameters of the ESN model, which has better prediction stability. Simulation experiments of Mackey-Glass chaos time series and public network traffic data set show that the proposed method has better prediction ability.
Key Words: network trafficchaos time seriesecho state network(ESN)black hole algorithmprediction
网络流量是评价网络负载和运行状态的一个较为重要的参数, 通过对其连续监测以实现准确预测, 是掌握网络运行状况以及实施有效管理和控制的重要手段.网络流量是基于时间的数据, 具有时间序列数据的特点, 有学者已经证明其具有混沌特性[1], 可以对其进行预测.对于时间序列数据的预测方法, 主要有线性方法和非线性方法.其中, 线性方法主要有:自回归(auto regression, AR)[2]、自回归滑动平均(auto regressive moving average, ARMA)[3]、自回归综合滑动平均(auto regressive integrated moving average, ARIMA)[4]等; 非线性方法主要有:支持向量机(support vector machine, SVM)[5]、最小二乘支持向量机(least square support vector machine, LSSVM)[6]、人工神经网络(artificial neural network, ANN)[7]、灰色模型(grey model, GM)[8]等.随着网络规模和复杂程度的不断提高, 非线性分析可以很好地处理复杂数据的非平稳、非线性等问题, 因此, 非线性方法在网络流量预测中发挥着越来越重要的作用.
回声状态网络(echo state network, ESN)是一种新型的递归神经网络, 具有算法简单、收敛速度快等特点[9].相对于SVM, LSSVM, ANN和GM等方法, ESN有其独特的优势, 虽然SVM和LSSVM方法需要的样本较少, 但是其预测精度受限于核函数及其参数的准确选取, 且易陷入局部极值; ANN方法虽然能够以任意精度逼近函数, 但是其模型结构复杂, 较难精确给定; GM方法较难处理网络流量数据存在剧烈变化的情况; ESN方法内部设置一个动态储备池(dynamic reservoir, DR), 由大量神经元构成, 蕴含非线性系统的动态特性, 具有短暂记忆的功能, ESN网络的输入层到储备池的连接权值以及储备池内部的连接权值在初始化时随机生成, 且在整个训练过程中保持不变, 只有输出权值是需要求解的部分, 使其与ANN相比收敛速度快, 且没有陷入局部极值的问题, 有学者已经将ESN方法应用于网络流量的预测中[1, 10].
ESN模型的预测精度主要由DR的4个参数决定, 分别为:权值谱半径(SR)、储备池大小(N)、输入尺度因子(IS)和储备池神经元连接程度(SD), 这几个参数的取值对ESN的预测精度有重要的影响[1], 因此, 在模型训练过程中实现对4个参数的优化选择是非常重要的.黑洞(black hole, BH)算法是2013年由Hatamlou提出的一种启发式优化算法[11], 原理简单, 易于实现.与遗传算法(genetic algorithm, GA)、粒子群(particle swarm optimization, PSO)、模拟退火(simulated annealing, SA)、蚁群(ant colony optimization, ACO)以及和声搜索(harmony search, HS)等算法相比, BH算法的最大优点是受优化算法自身参数设置的影响较小[6], 因为这些参数的设定一般依赖人工经验, 如果设置不合理, 会影响算法的计算精度.通过仿真实验已经证明, BH算法的计算精度优于GA, PSO等算法[6, 11], 因此, 该算法已受到很多学者的关注[6, 12-13].但是, BH算法也有它自身的不足, 就是算法的运行时间较长, 造成收敛速度较慢; 对此, 在对经典算法中新解的生成机制会影响收敛速度进行分析后, 提出一种改进的黑洞算法, 采用一种新的新解生成机制, 在提高算法收敛速度的同时, 还能够改善其收敛精度.
1 混沌时间序列原始数据集表示为{xi, i=1, 2, …, Z}, 相空间重构后, 得到如下混沌时间序列:Xt=[xt, xt+τ, …, xt+(m-1)τ], t=1, 2, …, Z-(m-1)τ.其中:m和τ分别为嵌入维数和延迟时间, m和τ的取值可以根据C-C法[14]进行计算.混沌时间序列的输出为Yt=xt+1+(m-1)τ, 将Xt和Yt分别作为预测模型的输入和输出进行建模.对于时间序列预测模型的步长, 本文采用单步预测方式, 即每预测出一个Yt后, 使其自动加入到新的输入Xt+1的最后一维.
2 回声状态网络(ESN)设定系统有M个输入, N个内部状态, K个输出.那么, 它们在时刻t的值分别表示为
 | (1) |
ESN的学习步骤如下:
 | (2) |
根据式(2), 各单元连接权值的计算决定了ESN的输出结果, 由于Win, W和Wback在初始化时随机生成, 且在整个训练过程中保持不变, 因此只有Wout是需要求解的部分, 可以通过DR内部状态单元和模型期望输出的线性回归最小平均误差得到Wout, 有
 | (3) |
在模型训练过程中, 希望得到的wiout能够使模型的均方误差最小, 即有如下的优化求解问题:
 | (4) |
 | (5) |
3 改进的黑洞算法3.1 黑洞(BH)算法下面简要介绍BH算法的基本原理[6]:
步骤1??进行初始化, 由星星表示空间中的候选解.
步骤2??将每个星星所代表的候选解代入适应度函数, 最优适应度函数值所对应的星星认定为黑洞.
步骤3??所有星星向黑洞移动, 位置变化如下:
 | (6) |
步骤4??重新计算每个星星的适应度函数值, 如果星星比黑洞具有更优的值, 互换它们的位置.
步骤5??如果星星移动到黑洞的半径之内, 会被其吸收, 黑洞的半径定义如下:
 | (7) |
某个星星被黑洞吸收而消失, 为了保证候选解数量的一致, 会在解空间内的随机位置上生成一个新的星星.
步骤6??如果算法满足终止条件, 输出最优解; 如果不满足, 返回到步骤3重新迭代.
3.2 BH算法的改进本文在文献[6]的基础上, 对BH算法中星星被黑洞吸收而消失后产生新解的机制进行进一步的研究, 以提高算法的优化性能.根据BH算法中步骤5, 迭代前期, 星星的移动方向较为固定, 算法的收敛速度较快; 而在后期, 当前最优解(黑洞)附近可能会存在更优解, 但搜索的吸收-生成机制降低了算法的局部寻优能力, 使得算法收敛变慢.因此, 应该将生成新解的范围限定在黑洞附近, 从而增加得到更优解的可能.对此, 本文对BH算法进行改进, 提出一种新解生成的新机制.
首先, 假设第i个星星被黑洞吸收而消失, 根据式(8)和(9)确定生成新解的范围.
 | (8) |
 | (9) |
然后, 在范围[pinew_inf,pinew_sup]内取任意的一个值作为第i个星星被黑洞吸收而消失后生成的新解的位置pinew.可以看到, 所提出的新解生成的机制通过将生成新解的位置限定在最优解(黑洞)周围, 既可以使算法避免陷入局部最优解, 又能使搜索过程以较高的效率在最优解附近寻找更优解.
于是, ESN的4个参数SR,N, IS和SD就可以采用本文所提出的改进BH算法进行优化选择.
4 基于改进BH算法优化ESN的时间序列预测基于改进BH算法优化ESN的时间序列预测模型的主要计算步骤如下.
步骤1??参数初始化, 设定待优化参数的取值范围[1], 其中:SR∈[0.1, 1),N∈[10, 150), IS∈[0.01, 1), SD∈[0.01, 1).
步骤2??将原始数据集中的数据归一化到区间[0, 1], 对其进行相空间重构, 确定模型的输入和输出, 由ESN方法进行训练和建模.
步骤3??调用改进的BH算法进行参数的优化选择, 设置候选解的种群数量并给定初值, 将其定位为星星.
步骤4??将每个星星所代表的参数值代入预测模型, 计算适应度函数值, 适应度函数定义如下:
 | (10) |
步骤5??所有星星向黑洞移动, 根据式(6)进行位置的更新.
步骤6??重新计算每个星星的fitness值, 如果某个星星的fitness值比黑洞的更小, 那么就互换两者的位置.
步骤7??根据式(7), 计算每个星星与黑洞的距离, 如果小于RBH, 该星星在空间内消失; 同时, 根据式(8)和式(9), 由第3.2节所提出的新解生成的新机制在解空间内生成一个新解.
步骤8??如果满足终止条件, 算法终止, 输出黑洞所对应的最优参数, 否则返回步骤5重新迭代.
步骤9??将所得到的最优参数代入ESN模型中进行预测, 并对预测结果进行反归一化处理.
5 仿真分析采用Mackey-Glass混沌时间序列进行仿真,
 | (11) |
设定混沌时间序列的参数m=5和τ=1, 分别采用黑洞算法优化ESN(BH-ESN)、改进的黑洞算法优化ESN(IBH-ESN)和本文方法进行预测, 进化代数为100.图 1为3种方法的实际值与预测值的对比曲线, 表 1为两种方法的均方根误差RMSE(root mean square error)和平均绝对误差MAE(mean absolute error)评价指标的对比结果.
图 1(Fig. 1)
 | 图 1 三种方法的实际值与预测值的对比Fig.1 Comparison of the three methods with true values and predictive values |
表 1(Table 1)
 表 1 三种方法的关键性能指标对比Table 1 Comparison of key performance indicators among the three methods
| 表 1 三种方法的关键性能指标对比 Table 1 Comparison of key performance indicators among the three methods |
6 实例验证采用网络流量公共数据集BC-pAug89进行实例验证.文献[1]通过对不同采样时间间隔下网络流量时间序列进行混沌特性分析和相空间重构, 已得到其相空间参数.本文采用T_100 ms数据集进行验证, 采样数据集长度取1 000, 前400组数据作为训练样本, 第401~500组数据作为测试样本, 数据集的样本序列分别如图 2所示.
图 2(Fig. 2)
 | 图 2 T_100 ms数据集网络流量序列Fig.2 Network traffic data sequence of T_100 ms data set |
将本文所提出的改进BH-ESN预测模型分别与HS-ESN, GA-LSSVM, HS-LSSVM和Elman神经网络预测模型进行比较.其中, ESN参数优化的取值范围为:SR∈[0.1, 1), N∈[10, 150), IS∈[0.01, 1)和SD∈[0.01, 1);GA-LSSVM中参数设置如下:编码串长取10, 交叉概率pc∈[0.4, 0.8], 变异概率pm∈[0.001, 0.005];HS-ESN和HS-LSSVM中的参数设置如下:和声数M∈[10, 40]，保留概率HMCR∈[0.5, 0.9], 记忆扰动概率PAR∈[0.05, 0.2], 带宽范围为[0.001, 1];Elman神经网络预测模型中设置输入层∈[100, 150], 中间层∈[40, 80], 输出层∈[30, 50].设定算法迭代次数为100次, 每个模型重复执行20次取平均(平均值±标准偏差), 每次执行过程中, 各算法的相关参数在取值范围内随机取值.由RMSE和MAE作为评价指标.T_100ms数据集在不同模型下的预测指标如表 2所示.本文所提方法预测精度不依赖参数设置, 预测结果较为稳定, 在网络流量短期预测上具有较好的效果.
表 2(Table 2)
表 2 T_100 ms数据集预测指标Table 2 Prediction index of the T_100 ms data set
| 表 2 T_100 ms数据集预测指标 Table 2 Prediction index of the T_100 ms data set |
7 结论本文提出一种基于混沌时间序列和回声状态网络模型的网络流量短期预测方法.首先对网络流量数据集进行相空间重构; 然后针对影响模型预测性能的四个重要参数:权值谱半径、储备池大小、输入尺度因子和储备池神经元连接程度, 采用改进的黑洞算法进行优化选取.所提出的改进黑洞算法受主观设定参数的影响较小, 使得预测模型不依赖于相关参数的准确设定.根据仿真实验结果, 所提出的方法相比于其他方法, 模型的预测结果较为稳定, 且具有更好的预测性能.
参考文献
| [1] | 田中大, 李树江, 王艳红, 等. 基于混沌理论与改进回声状态网络的网络流量多步预测[J].通信学报, 2016, 37(3): 55–70. ( Tian Zhong-da, Li Shu-jiang, Wang Yan-hong, et al. Network traffic multi-step prediction based on chaos theory and improved echo state network[J].Journal on Communications, 2016, 37(3): 55–70.DOI:10.11959/j.issn.1000-436x.2016053) |
| [2] | Chisci L, Mavino A, Perferi G, et al. Real-time epileptic seizure prediction using AR models and support vector machines[J].IEEE Transactions on Biomedical Engineering, 2010, 57(5): 1124–1132.DOI:10.1109/TBME.2009.2038990 |
| [3] | Laner M, Svoboda P, Rupp M. Parsimonious fitting of long-range dependent network traffic using ARMA models[J].IEEE Communications Letters, 2013, 17(12): 2368–2371.DOI:10.1109/LCOMM.2013.102613.131853 |
| [4] | Narendra B C, Eswara R B. A moving-average filter based hybrid ARIMA-ANN model for forecasting time series data[J].Applied Soft Computing, 2014, 23(1): 27–38. |
| [5] | 孟庆芳, 陈珊珊, 陈月辉, 等. 基于递归量化分析与支持向量机的癫痫脑电自动检测方法[J].物理学报, 2014, 63(5): 1–7. ( Meng Qing-fang, Chen Shan-shan, Chen Yue-hui, et al. Automatic detection of epileptic EEG based on recurrence quantification analysis and SVM[J].Acta Physica Sinica, 2014, 63(5): 1–7.) |
| [6] | 李琨, 韩莹, 黄海礁. 基于IBH-LSSVM的混沌时间序列预测及其在抽油井动液面短期预测中的应用[J].信息与控制, 2016, 45(2): 241–247. ( Li Kun, Han Ying, Huang Hai-jiao. Chaotic time series prediction based on IBH-LSSVM and its application to short-term prediction of dynamic fluid level of the oil wells[J].Information and Control, 2016, 45(2): 241–247.) |
| [7] | Du W, Leung S Y S, Kwong C K. Time series forecasting by neural networks:a knee point-based multi-objective evolutionary algorithm approach[J].Expert Systems with Applications, 2014, 41(7): 8049–8061. |
| [8] | Wang Z X, Pei L L. An optimized grey dynamic model for forecasting the output of high-tech industry in China[J].Mathematical Problems in Engineering, 2014, 2014(1): 1–7. |
| [9] | Jaeger H, Haas H. Harnessing nonlinearity:predicting chaotic systems and saving energy in wireless communication[J].Science, 2004, 304(5667): 78–80.DOI:10.1126/science.1091277 |
| [10] | 田中大, 李树江, 王艳红, 等. 基于KPCA优化ESN的网络流量预测方法[J].电机与控制学报, 2015, 19(12): 114–120. ( Tian Zhong-da, Li Shu-jiang, Wang Yan-hong, et al. Network traffic prediction method based on KPCA optimized ESN[J]. Electric Machines and Control, 2015, 19(12): 114–120.) |
| [11] | Hatamlou A. Black hole:a new heuristic optimization approach for data clustering[J].Information Science, 2013, 222(1): 75–184. |
| [12] | Li K, Gao X W, Zhou H B, et al. Fault diagnosis for down-hole conditions of sucker rod pumping systems based on the FBH-SC method[J].Petroleum Science, 2015, 12(1): 135–147.DOI:10.1007/s12182-014-0006-5 |
| [13] | 王通, 高宪文, 蒋子健. 基于黑洞算法的LSSVM的参数优化[J].东北大学学报(自然科学版), 2014, 35(2): 170–174. ( Wang Tong, Gao Xian-wen, Jiang Zi-jian. Parameters optimizing of LSSVM based on black hole algorithm[J].Journal of Northeastern University(Natural Science), 2014, 35(2): 170–174.) |
| [14] | Kim H S, Eykholt R, Salas J D. Nonlinear dynamics, delay times, and embedding windows[J].Physica D:Nonlinear Phenomena, 1999, 127(1): 48–60. |
