基于LFSN和小波变换的业务流预测算法

陈国彬,张广泉

(1.重庆工商大学融智学院,重庆400033;2.苏州大学计算机科学与技术学院,江苏苏州215006;

3.中国科学院计算机科学国家重点实验室,北京100080)

基于LFSN和小波变换的业务流预测算法

陈国彬1,张广泉2,3

(1.重庆工商大学融智学院,重庆400033;2.苏州大学计算机科学与技术学院,江苏苏州215006;

3.中国科学院计算机科学国家重点实验室,北京100080)

针对实际业务流预测精度偏低的问题,结合线性分形稳定运动(LFSM)模型和小波变换提出一种新的业务流预测算法(SPWL)。定义线性分形稳定噪声(LFSN)分布特征,利用离散傅里叶变换产生满足LFSN过程的数列,并给出实际业务流数据拟合方法。通过小波变换降低实际业务流的突发特性,同时融合LFSM模型的预测结果提高实际业务流的预测精度。基于NS2和Matlab进行仿真实验,结果表明,与FARIMA算法相比,SPWL算法预测精度较高,其预测误差仅为12.83%。

业务流;预测精度;分布特征;线性分形稳定运动;小波

1 概述

随着Internet的迅速发展[1-3],实际业务流的性能状况日益受到关注,如何在发生拥塞前预测下一时刻实际业务流状态成为当前计算机网络研究的重点。目前对业务流预测方法较多,传统观念认为实际业务流是服从Possion分布或近似为 Markov过程,所以大多是基于线形模型来近似处理流量的发展趋势,其典型方法有AR,ARMA等模型,这些模型算法比较简单,短期预测有较高的精度,但不适用于长期预测。但是实际业务流往往具有分形特性,所以基于非线性预测方法被应用于长相关业务流刻画中,典型方法有小波变换、多重分形、Weibull、FARIMA、LFSN、混沌等模型。对此,国内外学者做了大量研究工作。文献[4]基于FARIMA模型提出了一种概率上限的预测算法,以达到减少实际流量时延的目的。文献[5]针对具有超线性收敛性的变尺度法改进ARMA预测模型,并基于自相关系数和偏自相关系数的拖尾方法对实际流量预测。文献[6]针对实际业务流的波动性与自相似特性提出了一种基于FARIMA-GARCH模型的预测算法,它利用分段双向CUSUM检测算法对流量序列的均值进行有效检测,并采用限定搜索法对分数差分阶数进行精确估计,以此预测下一时刻实际业务流状态。文献[7]利用最小二乘支持向量机和模糊LSSVM训练,建立了一种最优样本子集在线模糊预测算法,并深入研究实际流量的时变性和长周期性。文献[8]基于余弦函数来改进Logistic模型,并利用非线性时间序列分析方法和Logistic模型来描述实际流量状态的演化态势以及混沌特征量。文献[9]针对传统预测模型对训练数据依赖程度高的问题,结合小波技术和蚁群算法来建立Back Propagation网络权值预测方法,提高了预测精度。文献[10]基于量子自适应粒子群优化RBF神经网络算法建立了一种网络流量预测算法,它通过利用量子自适应粒子群优化算法来实现粒子位置的编码,并基于粒子飞行轨迹信息动态更新量子比特的状态,以避免陷入局部最优。

在上述工作基础上,本文提出了一种新的业务流状态预测算法,该算法通过融合LFSN模型[11-13]和小波变换[14-15]的预测结果来提高预测精度。

2 LFSN过程定义

如图1所示的网络环境中有m个无线节点,其中,节点O为汇聚处,节点an为数据源,业务流从节点an发送至节点O,再经由节点O进行转发。传统的刻画业务流性能方法有泊松模型、高斯分布等,其研究基础是认为流量呈现出短相关特性。而随着研究的深入,结果发现实际流量表现出自相似和长相关特征[16],令其分形参数为H(0＜H＜1),对此基于分形布朗运动(Fractal Brown Motion,FBM)模型提出了如下刻画模型:

其中,a为方差系数;m为平均到达速率;BH为标准分形布朗运动。

由于实际流量具有明显的尺度特性和分形特性,已有的混沌模型、FARIMA模型计算复杂,不能有效地进行实际应用,因此本文结合线性分形稳定运动(Linear Fractional Stable Motion,LFSM)重新对实际业务流特性进行刻画。在α-稳定条件下可以将FBM扩展为不同分形稳定运动形式,其中典型代表就是线性分形稳定运动,其定义为:

其中,α是特征指数(0＜α＜2);Ms是具有Lebesgue控制测度的α稳定测量;x+取值为max(0,x)。如果相关参数H＞1/α时,LFSM的增量过程表现为长相关。LFSM如果满足自相似平稳增量过程,则定义其为线性分形稳定噪声:

图1 网络环境

如果H＞1/α,LFSN则具有长相关,反之则LFSN具有短相关。将上述方程进行离散化处理可以得到:

其中,K表示积分截断点;m表示积分离散化中的网格参数;d=H-1/α,并且:

结合FBM模型,在满足稳定分布的条件下,式(4)满足偏态LFSN过程,这里定义时刻i内到达的业务流数量M(i)为:

对于参数σ,这里给出具体求解方法。

对上式取对数,得到:

令S=1时,可得:

结合式(9)、式(10),则有:

3 状态预测算法

为了方便实际应用和判断业务流特性,这里给出实际业务流拟合方法。首先将LFSN过程进行离散化:

结合离散傅里叶变换,对于具有离散形式Ni= Hi*Si的数列(*表示卷积),根据如下步骤产生满足LFSN过程的数列:

(1)针对序列Hi和Si,获取其和的离散傅立叶变换对象hi和si;

(2)计算hi和si的乘积,并令ni=hisi;

(3)根据离散傅立叶逆变换获得其序列{Ni}。

由此可以拟合实际业务流数据,并据此进行特性判断。如果实际业务流符合LFSN过程,那么就可以通过分布特性对业务流状态进行预测,以此进行拥塞控制。

假设时刻t节点O处的业务流Yt状态向量为St=[s1,s2,…,sn],结合LFSN模型对当前时刻状态进行分析,以获得下一时刻业务流状态St+1。同时,为了降低实际业务流的突发性,并提高预测精度,这里首先采用小波变换对业务流进行处理,然后利用LFSN模型对小波系数进行预测,将预测之后的小波系数进行合成,以获得下一时刻业务流状态。以下根据小波变换和LFSN模型建立实际业务流状态预测算法SPWL(State Prediction Algorithm Based on Wavelet Transform and LFSN):

Step 1 在开始时刻t=0,初始化网络拓扑结构及其相关参数;

Step 2 对于时刻t到达节点O处的实际业务流Yt,获取其状态向量St(这里假设其状态向量St= [s1,s2],其中,s1表示时延Dt;s2表示队长Lt),并根据LFSN模型判断是否服从其分布,如果满足则跳转到Step 3,否则跳转到Step 7;

Step 3 针对实际业务流的分形和突发特性,这里引入小波变换对业务流进行处理,根据式(13)所示的小波变换,利用Harr小波基对业务流Yt的状态(时延Dt和队长Lt)进行分解,获得小波系数dj(k)和尺度系数aj(k):

其中,j为小波分解层次;

Step 4 根据式(14)所示的ARMA模型对小波系数进行预测,并采用逆小波变换合成预测之后的时延Dt+1(1)和队长Lt+1(1);

其中,p和q为ARMA模型参数;τ为AR(p)过程参数;ρ为MA(q)过程参数;u代表时延Dt和队长Lt的小波系数序列;

Step 5 同时根据文献[17]的计算方法,求解t+1时刻业务流的时延Dt+1(2)和队长Lt+1(2):

其中,λ为节点O的负载大小;b为缓冲区大小;Ωk+n为实际流量的分布函数,这里的分布函数即为LFSN过程;

Step 6 将Step 4和Step 5预测后的结果进行融合(融合的目的是减少预测误差),以获得时刻t+1的最后预测结果:

其中,融合参数φ和φ表示这2种预测结果的权重分布,可以进行动态调整以获得最优结果,并且0≤φ≤1,0≤φ≤1,φ+φ=1;

Step 7 令t=t+1,跳转到Step 2,重复计算下一时刻实际流量向量,直至结束;

Step 8 算法结束。

4 数学仿真

针对上述建立的SPWL预测算法,这里结合NS2和Matlab进行仿真实验。首先在NS2中建立如图1所示的无线传感器网络拓扑结构,其中数据源节点共30个,其缓冲区容量为100 packet,汇聚节点O的缓冲区容量为1 000 packet,所有链路容量为15 Mb/s,延时10 ms,数据包大小为256 bit,融合参数φ=φ=0.5,小波变换分解层次为12。为了体现本文提出的SPWL算法有效性,这里将FARIMA模型、Weibull模型进行对比。实验中在各数据源产生H=0.9的长相关业务流,将这3种算法重复仿真20次后取其平均值,图2给出了业务流的时延状态和队长状态的预测结果比较。从图2可以看出, SPWL算法与实际业务流最为接近,其次是FARIMA,性能最差的是Weibull。这是由于为了描述实际业务流的分形特性,数据源产生了长相关特性的业务流,SPWL和FARIMA都具有刻画长相关特性的功能,因此预测效果比较理想,但是SPWL综合了LFSN和小波变换方法,其性能得到进一步提高。而Weibull仅仅针对重尾分布进行刻画,所以存在较大偏差。经过数据分析,SPWL、FARIMA和Weibull的预测误差分别为 12.83%,14.32%和18.71%。

图2 业务流时延状态和队长状态预测结果

这里对影响SPWL算法性能的关键因素进行深入研究。这里定义利用率ω为平均到达速率m与节点O的服务率ξ之比,图3和图4给出了不同相关参数H下时延、队长与节点O处利用率ω的变化情况。从图3可以看出,随着利用率的增加,时延呈现递减趋势。这一点容易理解,节点O的利用率提高,意味着处理业务流的转发效率提高,必然减少业务流排队时间,从而降低了时延。但是在小利用率下,参数H越大对应的时延越大,而在大利用率下,参数H越大对应的时延越小。这是因为利用率较小时,H越大意味着突发越强,而利用率越小对于处理突发情况的能力较低,所以造成时延更大。类似现象在图4中可以观察到,小利用率下参数H越大对应的队长越大,而小利用率下情况正好相反。其主要原因是受到有限缓冲区截断效应的影响,当缓冲区满状态时将直接丢弃后续到达数据包,从而使得业务流长相关特性受到影响。

图3 不同相关参数H下时延与利用率之间的关系

图4 不同相关参数H下队长与利用率之间的关系

同时,这里定义预测误差ε:

其中,sactual表示业务流实际状态;si表示算法预测状态(s1表示时延状态,s2表示队长状态)。图5和图6分别给出了不同偏差系数σ下时延、队长的预测误差与相关参数H之间的关系。从图5可以看出,随着相关参数H的增加,时延预测误差呈现递增趋势。在相关参数H较小时,偏差系数σ越小对应的预测误差越小,这与通常理解是一致的。但是在相关参数H较大时,偏差系数σ越大对应的预测误差却越小,造成这一现象的原因在于强相关性和有限缓冲区截断效应引起了业务流性能突变。并且在图6中也存在类似突变现象。

图5 不同偏差系数σ下时延预测误差与相关参数H之间的关系

图6 不同偏差系数σ下队长预测误差与相关参数H之间的关系

5 结束语

本文针对实际业务流预测精度不高的问题,利用LFSN模型和小波变换提出了一种新的状态预测算法SPWL。该算法首先给出了LFSN分布特征和数据拟合方法,同时结合小波变换建立了业务流预测方法,通过融合2种方法的预测结果来达到减少预测误差的目的。基于NS2和Matlab进行仿真实验,对比研究了FARIMA模型、Weibull模型之间的性能状态,结果显示该算法具有较好的适应性。最后通过深入分析影响SPWL算法的关键因素,发现偏差系数、相关参数等因素对业务流状态产生较大影响。在今后的研究中,将考虑结合多重分形模型和混沌理论,建立一套完整的实际业务流预测和评价模型。

[1] Lazarou G Y,Baca J,FrostV S,et al.Describing Network Traffic Using the Index of Variability[J]. IEEE/ACM Transactions on Networking,2009,17(5): 1672-1683.

[2] 王升辉,裘正定.结合多重分形的网络流量非线性预测[J].通信学报,2007,28(2):45-57.

[3] Seong S,Reddy A.Statistical Techniques for Detecting Traffic Anomalies Through Packet Header Data[J]. IEEE Transaction on Networking,2008,16(3): 562-575.

[4] 宋 杨,涂小敏,费敏锐 .基于 FARIMA模型的Internet时延预测[J].仪器仪表学报,2012,33(4): 757-763.

[5] 单 伟,何 群.基于非线性时间序列的预测模型检验与优化的研究[J].电子学报,2008,36(12): 2485-2489.

[6] 杨双懋,郭 伟,唐 伟.基于FARIMA-GARCH模型的网络业务预测算法[J].通信学报,2013,34(3): 23-31.

[7] 温祥西,孟相如,马志强,等.小时间尺度网络流量混沌性分析及趋势预测[J].电子学报,2012,40(8): 1609-1616.

[8] 李 超,赵 海,葛 新,等.基于混沌特征的网络延迟预测模型[J].电子学报,2009,37(12):2657-2661.

[9] 李丹丹,张润彤,王传臣,等.认知网络中基于蚁群算法的网络流量预测模型[J].电子学报,2011,39(10): 2245-2250.

[10] 郭 通,兰巨龙,李玉峰,等.基于量子自适应粒子群优化径向基函数神经网络的网络流量预测[J].电子与信息学报,2013,35(9):2220-2226.

[11] 喻 莉,白 云,朱光喜.基于LFSN自相似流量模型的随机突发边界分析[J].通信学报,2010,31(5): 16-21.

[12] Tan X H,Hu Y,Jin W D.Modeling and Performance Analysis of LFSN [C]//Proc.of International Conference on Network and Parallel Computing Workshops.Dalian,China:[s.n.],2007:549-554.

[13] Bai Y,Yu L,Zhu G.Fast Simulation of General LFSN Self-similar Network Traffic[C]//Proc.of the 3rd International Conference on Communications and Networking.Hangzhou,China:[s.n.],2008:437-441.

[14] 丛 锁,韩良秀,刘 岩,等.基于离散小波变换的网络流量多重分形模型[J].通信学报,2003,24(5): 43-48.

[15] 龙图景,孙政顺,李春文,等.一种新的网络业务流的多重分形小波模型[J].计算机学报,2004,27(8): 1074-1082.

[16] 张骏温,陈海文,陈常嘉.因特网业务量多重分形性本质成因的研究[J].软件学报,2002,13(3):470-474.

[17] 周满珍,权冀川,郭 艳,等.基于成批排队的自相似业务性能分析[J].系统仿真学报,2004,16(2): 306-309.

编辑 索书志

Service Flow Prediction Algorithm Based on LFSN and Wavelet Transform

CHEN Guo-bin1,ZHANG Guang-quan2,3
(1.Rongzhi College,Chongqing Technology and Business University,Chongqing 400033,China; 2.College of Computer Science and Technology,Soochow University,Suzhou 215006,China;
3.State Key Laboratory of Computer Science,Chinese Academy of Sciences,Beijing 100080,China)

Aiming at the problem of low prediction accuracy of actual service flow,a novel State Prediction algorithm based on Wavelet transform and LFSN(SPWL)is proposed by Linear Fractional Stable Noise(LFSN)and wavelet transform.In this algorithm,the characteristic of LFSN distribution is defined,and the fitting method of actual data which is satisfied LFSN progress is given with discrete Fourier transform.The prediction accuracy is improved by fusing the results of LFSN model.Simulation is conducted to study the key influence factor of algorithm with NS2 and Matlab,such as time delay,dropping rate,as well as utilization rate.Results show that,compared to FARIMA algorithm,SPWL algorithm has high accuracy prediction,the prediction error of SPWL is 12.83%.

service flow;prediction accuracy;distribution characteristic;Linear Fractional Stable Motion(LFSM); wavelet

1000-3428(2014)10-0214-05

A

TP393

10.3969/j.issn.1000-3428.2014.10.040

江苏省自然科学基金资助项目(BK2011152);中国科学院计算机科学国家重点实验室开放课题基金资助项目(CSYSKF0908);重庆市教委科学技术研究基金资助项目(KJ133103)。

陈国彬(1982-),男,讲师、硕士,主研方向:网络服务质量评价;张广泉,教授、博士。

2013-10-22

2013-12-22E-mail:chen_gb1982@163.com

中文引用格式:陈国彬,张广泉.基于LFSN和小波变换的业务流预测算法[J].计算机工程,2014,40(10):214-218.英文引用格式:Chen Guobin,Zhang Guangquan.Service Flow Prediction Algorithm Based on LFSN and Wavelet Transform[J].Computer Engineering,2014,40(10):214-218.