基于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.