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

陳國彬,張廣泉

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

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

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

陳國彬1,張廣泉2,3

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

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

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

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

1 概述

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

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

2 LFSN過程定義

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

其中,a為方差系數(shù);m為平均到達(dá)速率;BH為標(biāo)準(zhǔn)分形布朗運動。

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

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

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

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

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

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

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

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

令S=1時,可得:

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

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

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

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

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

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

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

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

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

Step 1 在開始時刻t=0,初始化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其相關(guān)參數(shù);

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

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

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

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

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

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

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

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

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

Step 7 令t=t+1,跳轉(zhuǎn)到Step 2,重復(fù)計算下一時刻實際流量向量,直至結(jié)束;

Step 8 算法結(jié)束。

4 數(shù)學(xué)仿真

針對上述建立的SPWL預(yù)測算法,這里結(jié)合NS2和Matlab進行仿真實驗。首先在NS2中建立如圖1所示的無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),其中數(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ù)源產(chǎn)生H=0.9的長相關(guān)業(yè)務(wù)流,將這3種算法重復(fù)仿真20次后取其平均值,圖2給出了業(yè)務(wù)流的時延狀態(tài)和隊長狀態(tài)的預(yù)測結(jié)果比較。從圖2可以看出, SPWL算法與實際業(yè)務(wù)流最為接近,其次是FARIMA,性能最差的是Weibull。這是由于為了描述實際業(yè)務(wù)流的分形特性,數(shù)據(jù)源產(chǎn)生了長相關(guān)特性的業(yè)務(wù)流,SPWL和FARIMA都具有刻畫長相關(guān)特性的功能,因此預(yù)測效果比較理想,但是SPWL綜合了LFSN和小波變換方法,其性能得到進一步提高。而Weibull僅僅針對重尾分布進行刻畫,所以存在較大偏差。經(jīng)過數(shù)據(jù)分析,SPWL、FARIMA和Weibull的預(yù)測誤差分別為 12.83%,14.32%和18.71%。

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

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

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

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

同時,這里定義預(yù)測誤差ε:

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

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

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

5 結(jié)束語

本文針對實際業(yè)務(wù)流預(yù)測精度不高的問題,利用LFSN模型和小波變換提出了一種新的狀態(tài)預(yù)測算法SPWL。該算法首先給出了LFSN分布特征和數(shù)據(jù)擬合方法,同時結(jié)合小波變換建立了業(yè)務(wù)流預(yù)測方法,通過融合2種方法的預(yù)測結(jié)果來達(dá)到減少預(yù)測誤差的目的?；贜S2和Matlab進行仿真實驗,對比研究了FARIMA模型、Weibull模型之間的性能狀態(tài),結(jié)果顯示該算法具有較好的適應(yīng)性。最后通過深入分析影響SPWL算法的關(guān)鍵因素,發(fā)現(xiàn)偏差系數(shù)、相關(guān)參數(shù)等因素對業(yè)務(wù)流狀態(tài)產(chǎn)生較大影響。在今后的研究中,將考慮結(jié)合多重分形模型和混沌理論,建立一套完整的實際業(yè)務(wù)流預(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] 王升輝,裘正定.結(jié)合多重分形的網(wǎng)絡(luò)流量非線性預(yù)測[J].通信學(xué)報,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時延預(yù)測[J].儀器儀表學(xué)報,2012,33(4): 757-763.

[5] 單 偉,何 群.基于非線性時間序列的預(yù)測模型檢驗與優(yōu)化的研究[J].電子學(xué)報,2008,36(12): 2485-2489.

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

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

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

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

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

[11] 喻 莉,白 云,朱光喜.基于LFSN自相似流量模型的隨機突發(fā)邊界分析[J].通信學(xué)報,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)絡(luò)流量多重分形模型[J].通信學(xué)報,2003,24(5): 43-48.

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

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

[17] 周滿珍,權(quán)冀川,郭 艷,等.基于成批排隊的自相似業(yè)務(wù)性能分析[J].系統(tǒng)仿真學(xué)報,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

江蘇省自然科學(xué)基金資助項目(BK2011152);中國科學(xué)院計算機科學(xué)國家重點實驗室開放課題基金資助項目(CSYSKF0908);重慶市教委科學(xué)技術(shù)研究基金資助項目(KJ133103)。

陳國彬(1982-),男,講師、碩士,主研方向:網(wǎng)絡(luò)服務(wù)質(zhì)量評價;張廣泉,教授、博士。

2013-10-22

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

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