陳國彬,張廣泉

(1.重慶工商大學融智學院,重慶400033;2.蘇州大學計算機科學與技術學院,江蘇蘇州215006;

3.中國科學院計算機科學國家重點實驗室,北京100080)

基于LFSN和小波變換的業(yè)務流預測算法

陳國彬1,張廣泉2,3

(1.重慶工商大學融智學院,重慶400033;2.蘇州大學計算機科學與技術學院,江蘇蘇州215006;

3.中國科學院計算機科學國家重點實驗室,北京100080)

針對實際業(yè)務流預測精度偏低的問題,結合線性分形穩(wěn)定運動(LFSM)模型和小波變換提出一種新的業(yè)務流預測算法(SPWL)。定義線性分形穩(wěn)定噪聲(LFSN)分布特征,利用離散傅里葉變換產生滿足LFSN過程的數(shù)列,并給出實際業(yè)務流數(shù)據(jù)擬合方法。通過小波變換降低實際業(yè)務流的突發(fā)特性,同時融合LFSM模型的預測結果提高實際業(yè)務流的預測精度?；贜S2和Matlab進行仿真實驗,結果表明,與FARIMA算法相比,SPWL算法預測精度較高,其預測誤差僅為12.83%。

業(yè)務流;預測精度;分布特征;線性分形穩(wěn)定運動;小波

1 概述

隨著Internet的迅速發(fā)展[1-3],實際業(yè)務流的性能狀況日益受到關注,如何在發(fā)生擁塞前預測下一時刻實際業(yè)務流狀態(tài)成為當前計算機網(wǎng)絡研究的重點。目前對業(yè)務流預測方法較多,傳統(tǒng)觀念認為實際業(yè)務流是服從Possion分布或近似為 Markov過程,所以大多是基于線形模型來近似處理流量的發(fā)展趨勢,其典型方法有AR,ARMA等模型,這些模型算法比較簡單,短期預測有較高的精度,但不適用于長期預測。但是實際業(yè)務流往往具有分形特性,所以基于非線性預測方法被應用于長相關業(yè)務流刻畫中,典型方法有小波變換、多重分形、Weibull、FARIMA、LFSN、混沌等模型。對此,國內外學者做了大量研究工作。文獻[4]基于FARIMA模型提出了一種概率上限的預測算法,以達到減少實際流量時延的目的。文獻[5]針對具有超線性收斂性的變尺度法改進ARMA預測模型,并基于自相關系數(shù)和偏自相關系數(shù)的拖尾方法對實際流量預測。文獻[6]針對實際業(yè)務流的波動性與自相似特性提出了一種基于FARIMA-GARCH模型的預測算法,它利用分段雙向CUSUM檢測算法對流量序列的均值進行有效檢測,并采用限定搜索法對分數(shù)差分階數(shù)進行精確估計,以此預測下一時刻實際業(yè)務流狀態(tài)。文獻[7]利用最小二乘支持向量機和模糊LSSVM訓練,建立了一種最優(yōu)樣本子集在線模糊預測算法,并深入研究實際流量的時變性和長周期性。文獻[8]基于余弦函數(shù)來改進Logistic模型,并利用非線性時間序列分析方法和Logistic模型來描述實際流量狀態(tài)的演化態(tài)勢以及混沌特征量。文獻[9]針對傳統(tǒng)預測模型對訓練數(shù)據(jù)依賴程度高的問題,結合小波技術和蟻群算法來建立Back Propagation網(wǎng)絡權值預測方法,提高了預測精度。文獻[10]基于量子自適應粒子群優(yōu)化RBF神經(jīng)網(wǎng)絡算法建立了一種網(wǎng)絡流量預測算法,它通過利用量子自適應粒子群優(yōu)化算法來實現(xiàn)粒子位置的編碼,并基于粒子飛行軌跡信息動態(tài)更新量子比特的狀態(tài),以避免陷入局部最優(yōu)。

在上述工作基礎上,本文提出了一種新的業(yè)務流狀態(tài)預測算法,該算法通過融合LFSN模型[11-13]和小波變換[14-15]的預測結果來提高預測精度。

2 LFSN過程定義

如圖1所示的網(wǎng)絡環(huán)境中有m個無線節(jié)點,其中,節(jié)點O為匯聚處,節(jié)點an為數(shù)據(jù)源,業(yè)務流從節(jié)點an發(fā)送至節(jié)點O,再經(jīng)由節(jié)點O進行轉發(fā)。傳統(tǒng)的刻畫業(yè)務流性能方法有泊松模型、高斯分布等,其研究基礎是認為流量呈現(xiàn)出短相關特性。而隨著研究的深入,結果發(fā)現(xiàn)實際流量表現(xiàn)出自相似和長相關特征[16],令其分形參數(shù)為H(0＜H＜1),對此基于分形布朗運動(Fractal Brown Motion,FBM)模型提出了如下刻畫模型:

其中,a為方差系數(shù);m為平均到達速率;BH為標準分形布朗運動。

由于實際流量具有明顯的尺度特性和分形特性,已有的混沌模型、FARIMA模型計算復雜,不能有效地進行實際應用,因此本文結合線性分形穩(wěn)定運動(Linear Fractional Stable Motion,LFSM)重新對實際業(yè)務流特性進行刻畫。在α-穩(wěn)定條件下可以將FBM擴展為不同分形穩(wěn)定運動形式,其中典型代表就是線性分形穩(wěn)定運動,其定義為:

其中,α是特征指數(shù)(0＜α＜2);Ms是具有Lebesgue控制測度的α穩(wěn)定測量;x+取值為max(0,x)。如果相關參數(shù)H＞1/α時,LFSM的增量過程表現(xiàn)為長相關。LFSM如果滿足自相似平穩(wěn)增量過程,則定義其為線性分形穩(wěn)定噪聲:

圖1 網(wǎng)絡環(huán)境

如果H＞1/α,LFSN則具有長相關,反之則LFSN具有短相關。將上述方程進行離散化處理可以得到:

其中,K表示積分截斷點;m表示積分離散化中的網(wǎng)格參數(shù);d=H-1/α,并且:

結合FBM模型,在滿足穩(wěn)定分布的條件下,式(4)滿足偏態(tài)LFSN過程,這里定義時刻i內到達的業(yè)務流數(shù)量M(i)為:

對于參數(shù)σ,這里給出具體求解方法。

對上式取對數(shù),得到:

令S=1時,可得:

結合式(9)、式(10),則有:

3 狀態(tài)預測算法

為了方便實際應用和判斷業(yè)務流特性,這里給出實際業(yè)務流擬合方法。首先將LFSN過程進行離散化:

結合離散傅里葉變換,對于具有離散形式Ni= Hi*Si的數(shù)列(*表示卷積),根據(jù)如下步驟產生滿足LFSN過程的數(shù)列:

(1)針對序列Hi和Si,獲取其和的離散傅立葉變換對象hi和si;

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

(3)根據(jù)離散傅立葉逆變換獲得其序列{Ni}。

由此可以擬合實際業(yè)務流數(shù)據(jù),并據(jù)此進行特性判斷。如果實際業(yè)務流符合LFSN過程,那么就可以通過分布特性對業(yè)務流狀態(tài)進行預測,以此進行擁塞控制。

假設時刻t節(jié)點O處的業(yè)務流Yt狀態(tài)向量為St=[s1,s2,…,sn],結合LFSN模型對當前時刻狀態(tài)進行分析,以獲得下一時刻業(yè)務流狀態(tài)St+1。同時,為了降低實際業(yè)務流的突發(fā)性,并提高預測精度,這里首先采用小波變換對業(yè)務流進行處理,然后利用LFSN模型對小波系數(shù)進行預測,將預測之后的小波系數(shù)進行合成,以獲得下一時刻業(yè)務流狀態(tài)。以下根據(jù)小波變換和LFSN模型建立實際業(yè)務流狀態(tài)預測算法SPWL(State Prediction Algorithm Based on Wavelet Transform and LFSN):

Step 1 在開始時刻t=0,初始化網(wǎng)絡拓撲結構及其相關參數(shù);

Step 2 對于時刻t到達節(jié)點O處的實際業(yè)務流Yt,獲取其狀態(tài)向量St(這里假設其狀態(tài)向量St= [s1,s2],其中,s1表示時延Dt;s2表示隊長Lt),并根據(jù)LFSN模型判斷是否服從其分布,如果滿足則跳轉到Step 3,否則跳轉到Step 7;

Step 3 針對實際業(yè)務流的分形和突發(fā)特性,這里引入小波變換對業(yè)務流進行處理,根據(jù)式(13)所示的小波變換,利用Harr小波基對業(yè)務流Yt的狀態(tài)(時延Dt和隊長Lt)進行分解,獲得小波系數(shù)dj(k)和尺度系數(shù)aj(k):

其中,j為小波分解層次;

Step 4 根據(jù)式(14)所示的ARMA模型對小波系數(shù)進行預測,并采用逆小波變換合成預測之后的時延Dt+1(1)和隊長Lt+1(1);

其中,p和q為ARMA模型參數(shù);τ為AR(p)過程參數(shù);ρ為MA(q)過程參數(shù);u代表時延Dt和隊長Lt的小波系數(shù)序列;

Step 5 同時根據(jù)文獻[17]的計算方法,求解t+1時刻業(yè)務流的時延Dt+1(2)和隊長Lt+1(2):

其中,λ為節(jié)點O的負載大小;b為緩沖區(qū)大小;Ωk+n為實際流量的分布函數(shù),這里的分布函數(shù)即為LFSN過程;

Step 6 將Step 4和Step 5預測后的結果進行融合(融合的目的是減少預測誤差),以獲得時刻t+1的最后預測結果:

其中,融合參數(shù)φ和φ表示這2種預測結果的權重分布,可以進行動態(tài)調整以獲得最優(yōu)結果,并且0≤φ≤1,0≤φ≤1,φ+φ=1;

Step 7 令t=t+1,跳轉到Step 2,重復計算下一時刻實際流量向量,直至結束;

Step 8 算法結束。

4 數(shù)學仿真

針對上述建立的SPWL預測算法,這里結合NS2和Matlab進行仿真實驗。首先在NS2中建立如圖1所示的無線傳感器網(wǎng)絡拓撲結構,其中數(shù)據(jù)源節(jié)點共30個,其緩沖區(qū)容量為100 packet,匯聚節(jié)點O的緩沖區(qū)容量為1 000 packet,所有鏈路容量為15 Mb/s,延時10 ms,數(shù)據(jù)包大小為256 bit,融合參數(shù)φ=φ=0.5,小波變換分解層次為12。為了體現(xiàn)本文提出的SPWL算法有效性,這里將FARIMA模型、Weibull模型進行對比。實驗中在各數(shù)據(jù)源產生H=0.9的長相關業(yè)務流,將這3種算法重復仿真20次后取其平均值,圖2給出了業(yè)務流的時延狀態(tài)和隊長狀態(tài)的預測結果比較。從圖2可以看出, SPWL算法與實際業(yè)務流最為接近,其次是FARIMA,性能最差的是Weibull。這是由于為了描述實際業(yè)務流的分形特性,數(shù)據(jù)源產生了長相關特性的業(yè)務流,SPWL和FARIMA都具有刻畫長相關特性的功能,因此預測效果比較理想,但是SPWL綜合了LFSN和小波變換方法,其性能得到進一步提高。而Weibull僅僅針對重尾分布進行刻畫,所以存在較大偏差。經(jīng)過數(shù)據(jù)分析,SPWL、FARIMA和Weibull的預測誤差分別為 12.83%,14.32%和18.71%。

圖2 業(yè)務流時延狀態(tài)和隊長狀態(tài)預測結果

這里對影響SPWL算法性能的關鍵因素進行深入研究。這里定義利用率ω為平均到達速率m與節(jié)點O的服務率ξ之比,圖3和圖4給出了不同相關參數(shù)H下時延、隊長與節(jié)點O處利用率ω的變化情況。從圖3可以看出,隨著利用率的增加,時延呈現(xiàn)遞減趨勢。這一點容易理解,節(jié)點O的利用率提高,意味著處理業(yè)務流的轉發(fā)效率提高,必然減少業(yè)務流排隊時間,從而降低了時延。但是在小利用率下,參數(shù)H越大對應的時延越大,而在大利用率下,參數(shù)H越大對應的時延越小。這是因為利用率較小時,H越大意味著突發(fā)越強,而利用率越小對于處理突發(fā)情況的能力較低,所以造成時延更大。類似現(xiàn)象在圖4中可以觀察到,小利用率下參數(shù)H越大對應的隊長越大,而小利用率下情況正好相反。其主要原因是受到有限緩沖區(qū)截斷效應的影響,當緩沖區(qū)滿狀態(tài)時將直接丟棄后續(xù)到達數(shù)據(jù)包,從而使得業(yè)務流長相關特性受到影響。

圖3 不同相關參數(shù)H下時延與利用率之間的關系

圖4 不同相關參數(shù)H下隊長與利用率之間的關系

同時,這里定義預測誤差ε:

其中,sactual表示業(yè)務流實際狀態(tài);si表示算法預測狀態(tài)(s1表示時延狀態(tài),s2表示隊長狀態(tài))。圖5和圖6分別給出了不同偏差系數(shù)σ下時延、隊長的預測誤差與相關參數(shù)H之間的關系。從圖5可以看出,隨著相關參數(shù)H的增加,時延預測誤差呈現(xiàn)遞增趨勢。在相關參數(shù)H較小時,偏差系數(shù)σ越小對應的預測誤差越小,這與通常理解是一致的。但是在相關參數(shù)H較大時,偏差系數(shù)σ越大對應的預測誤差卻越小,造成這一現(xiàn)象的原因在于強相關性和有限緩沖區(qū)截斷效應引起了業(yè)務流性能突變。并且在圖6中也存在類似突變現(xiàn)象。

圖5 不同偏差系數(shù)σ下時延預測誤差與相關參數(shù)H之間的關系

圖6 不同偏差系數(shù)σ下隊長預測誤差與相關參數(shù)H之間的關系

5 結束語

本文針對實際業(yè)務流預測精度不高的問題,利用LFSN模型和小波變換提出了一種新的狀態(tài)預測算法SPWL。該算法首先給出了LFSN分布特征和數(shù)據(jù)擬合方法,同時結合小波變換建立了業(yè)務流預測方法,通過融合2種方法的預測結果來達到減少預測誤差的目的?；贜S2和Matlab進行仿真實驗,對比研究了FARIMA模型、Weibull模型之間的性能狀態(tài),結果顯示該算法具有較好的適應性。最后通過深入分析影響SPWL算法的關鍵因素,發(fā)現(xiàn)偏差系數(shù)、相關參數(shù)等因素對業(yè)務流狀態(tài)產生較大影響。在今后的研究中,將考慮結合多重分形模型和混沌理論,建立一套完整的實際業(yè)務流預測和評價模型。

[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] 王升輝,裘正定.結合多重分形的網(wǎng)絡流量非線性預測[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] 單 偉,何 群.基于非線性時間序列的預測模型檢驗與優(yōu)化的研究[J].電子學報,2008,36(12): 2485-2489.

[6] 楊雙懋,郭 偉,唐 偉.基于FARIMA-GARCH模型的網(wǎng)絡業(yè)務預測算法[J].通信學報,2013,34(3): 23-31.

[7] 溫祥西,孟相如,馬志強,等.小時間尺度網(wǎng)絡流量混沌性分析及趨勢預測[J].電子學報,2012,40(8): 1609-1616.

[8] 李 超,趙 海,葛 新,等.基于混沌特征的網(wǎng)絡延遲預測模型[J].電子學報,2009,37(12):2657-2661.

[9] 李丹丹,張潤彤,王傳臣,等.認知網(wǎng)絡中基于蟻群算法的網(wǎng)絡流量預測模型[J].電子學報,2011,39(10): 2245-2250.

[10] 郭 通,蘭巨龍,李玉峰,等.基于量子自適應粒子群優(yōu)化徑向基函數(shù)神經(jīng)網(wǎng)絡的網(wǎng)絡流量預測[J].電子與信息學報,2013,35(9):2220-2226.

[11] 喻 莉,白 云,朱光喜.基于LFSN自相似流量模型的隨機突發(fā)邊界分析[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] 叢 鎖,韓良秀,劉 巖,等.基于離散小波變換的網(wǎng)絡流量多重分形模型[J].通信學報,2003,24(5): 43-48.

[15] 龍圖景,孫政順,李春文,等.一種新的網(wǎng)絡業(yè)務流的多重分形小波模型[J].計算機學報,2004,27(8): 1074-1082.

[16] 張駿溫,陳海文,陳常嘉.因特網(wǎng)業(yè)務量多重分形性本質成因的研究[J].軟件學報,2002,13(3):470-474.

[17] 周滿珍,權冀川,郭 艷,等.基于成批排隊的自相似業(yè)務性能分析[J].系統(tǒng)仿真學報,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-),男,講師、碩士,主研方向:網(wǎng)絡服務質量評價;張廣泉,教授、博士。

2013-10-22

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

中文引用格式:陳國彬,張廣泉.基于LFSN和小波變換的業(yè)務流預測算法[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.