楊雙懋，郭偉，唐偉

(1. 電子信息控制重點(diǎn)實(shí)驗(yàn)室，四川 成都 610036；2. 電子科技大學(xué) 通信抗干擾技術(shù)國家級重點(diǎn)實(shí)驗(yàn)室, 四川 成都 611731）

1 引言

網(wǎng)絡(luò)業(yè)務(wù)的流量特性是進(jìn)行網(wǎng)絡(luò)協(xié)議設(shè)計(jì)、性能評估、資源管理和設(shè)備研究所必須考慮的重要因素，目前已經(jīng)有大量文獻(xiàn)對此做出了研究。早期對網(wǎng)絡(luò)業(yè)務(wù)的流量特性的研究以泊松模型為主。然而，通過對真實(shí)網(wǎng)絡(luò)流量的深入分析發(fā)現(xiàn)數(shù)據(jù)交換網(wǎng)絡(luò)的流量特征不能通過泊松模型描述[1]。特別是文獻(xiàn)[2～4]通過對局域網(wǎng)和廣域網(wǎng)的流量特性進(jìn)行了實(shí)際測量與分析，發(fā)現(xiàn)了網(wǎng)絡(luò)流量具有自相似(self-similarity)和長相關(guān)性(long-range dependence)。因此，傳統(tǒng)的描述短相關(guān)性(short-range dependence)的泊松過程、Markov過程、AR(autoregressive)、MA(moving average)、ARMA(autoregressive moving average)和ARIMA(autoregressive integrated moving average)過程等已不適合于描述 LRD業(yè)務(wù)流。同時，長相關(guān)模型又缺乏刻畫業(yè)務(wù)短相關(guān)性的能力，因此必須采用能同時描述LRD和SRD的數(shù)學(xué)模型。當(dāng)前網(wǎng)絡(luò)流量的建模和預(yù)測主要集中于采用時間序列模型的算法[5]、小波模型[6～8]以及神經(jīng)網(wǎng)絡(luò)模型[9～16]等。

經(jīng)典的 ARMA模型的預(yù)測算法[17]具有較低復(fù)雜度，但是不適合于描述 LRD業(yè)務(wù)流；基于分?jǐn)?shù)自回歸求和滑動平均(FARIMA, fractional autoregressive integrated moving average)模型的預(yù)測算法[18]相對于文獻(xiàn)[17]提高了預(yù)測精度，但是對于網(wǎng)絡(luò)業(yè)務(wù)的劇烈波動性也不太適應(yīng)。文獻(xiàn)[6～8]把小波分析和時間序列模型結(jié)合起來，通過時間序列模型預(yù)測小波的細(xì)節(jié)分量或者預(yù)測重構(gòu)后單支分量，再進(jìn)行總體流量重構(gòu)，但沒有給出如何進(jìn)行長期預(yù)測和區(qū)間預(yù)測的方法。

基于神經(jīng)網(wǎng)絡(luò)的預(yù)測模型可以對非線性的序列進(jìn)行預(yù)測，能較好地描述網(wǎng)絡(luò)流量的不穩(wěn)定性，但訓(xùn)練復(fù)雜度和計(jì)算復(fù)雜度都較高。BP(back propagation)神經(jīng)網(wǎng)絡(luò)采用全局逼近，其訓(xùn)練時間偏長，因此其應(yīng)用受到限制；而徑向基(RBF, radial basis function)神經(jīng)網(wǎng)絡(luò)采用局部逼近訓(xùn)練算法，能夠以任意精度逼近任意連續(xù)函數(shù)。文獻(xiàn)[15]把RBF神經(jīng)網(wǎng)絡(luò)應(yīng)用到網(wǎng)絡(luò)業(yè)務(wù)預(yù)測算法中，文獻(xiàn)[16]用RBF神經(jīng)網(wǎng)絡(luò)對流量的小波細(xì)節(jié)分量進(jìn)行預(yù)測，再將流量進(jìn)行重構(gòu)，但是沒有考慮業(yè)務(wù)的長相關(guān)性，同時也沒有給出如何確定神經(jīng)網(wǎng)絡(luò)的嵌入維數(shù)和延遲時間。這2個參數(shù)將在很大程度上決定預(yù)測算法的精度[19]，然而目前還沒有普適的方法進(jìn)行確定[19,20]。

經(jīng)典的基于 FARIMA 模型的預(yù)測算法[18]分為序列零均值化、分?jǐn)?shù)差分階數(shù)估計(jì)、序列建模和預(yù)測3個關(guān)鍵步驟。其序列零均值化采用了整體去均值法，但是該法無法降低序列的波動性；而采用傳統(tǒng)的估計(jì)算法[5]得到的分?jǐn)?shù)差分階數(shù)依然不夠精確。同時，F(xiàn)ARIMA模型本身不能對序列的波動性進(jìn)行有效跟蹤。作者在前期研究中提出了一種基于 FARIMA改進(jìn)的預(yù)測算法[21]，而本文將作進(jìn)一步擴(kuò)充，提出一種基于廣義自回歸條件異方差(FARIMA-GARCH,generalized autoregressive conditional heteroscedasticity)模型的網(wǎng)絡(luò)業(yè)務(wù)預(yù)測算法。

本文所提算法流程如圖1所示。首先，提出一種分段雙向CUSUM檢測算法將序列零均值化，以此減小序列的波動性；然后針對分?jǐn)?shù)差分階數(shù)的精確估計(jì)提出了一種限定搜索法；接著對序列進(jìn)行FARIMA-GARCH建模；最后進(jìn)行流量預(yù)測和區(qū)間估計(jì)。

2 基于FARIMA-GARCH模型的預(yù)測算法

2.1 FARIMA-GARCH模型

時間序列中的 FARIMA(p,d,q)-GARCH(r,s)模型[22]是將FARIMA與GARCH相結(jié)合，能同時描述網(wǎng)絡(luò)業(yè)務(wù)的長相關(guān)性、短相關(guān)性和波動性的離散時間序列模型。令tX表示業(yè)務(wù)的時間序列，則該模型可以表示為

圖1 網(wǎng)絡(luò)業(yè)務(wù)建模預(yù)測流程

其中，B是時延算子，即 B Xt= Xt-1。分?jǐn)?shù)差分階數(shù) d ∈(-0 .5,0.5)， ?d為分?jǐn)?shù)差分算子。Φ(B)、Θ(B)、Ω(B)和A(B)為復(fù)變量多項(xiàng)式[18,22]。非負(fù)整數(shù)p和q是FARIMA模型的自回歸階數(shù)和滑動平均階數(shù)，{at}表示業(yè)務(wù)序列Xt的殘差序列，表示條件方差，非負(fù)整數(shù)r和s表示GARCH模型的階數(shù)，{vt}為零均值且方差為1的高斯白噪聲。

當(dāng) d = 0 時， Xt退化成ARMA(p, q)，只呈現(xiàn)出短相關(guān)性。所以，本文將在精確估計(jì)出分?jǐn)?shù)差分階數(shù)d后，通過分?jǐn)?shù)差分來消弱序列中的長相關(guān)性，以利用經(jīng)典的時間序列理論進(jìn)行參數(shù)估計(jì)。

2.2 分段雙向CUSUM均值檢測算法

式(2)中要求輸入的序列必須是零均值平穩(wěn)序列，實(shí)際的用戶業(yè)務(wù)序列往往不滿足零均值的要求。傳統(tǒng)的去均值的方法是整體去均值法[18]，但是該法不能減小序列的方差；而分段去均值法能夠得到更小的方差。因此，本文采用分段去均值法對序列進(jìn)行零均值化，且有定理1成立。

定理 1 分段去均值法獲得的方差不大于整體去均值法。

證明 設(shè)序列 { yt} ：y1, y2, … ,yv, yv+1,yv+2,… ,yL是具有均值變化點(diǎn)的時間序列，其均值為μ3，其中，時間點(diǎn)v為變點(diǎn)；設(shè)序列 y1, y2,… ,yv滿足均值為μ1，方差為，長度為v；后半部分序列yv+1,yv+2,… ,yL滿足均值為μ2，方差為，長度為L - v ，且有 μ1≠μ2。按照分段去均值法去均值后，得到時間序列{γt}；按照整體去均值法，得到{πt}，表示為

又由條件 μ1≠ μ2，可得D(πt)＞D(γt)。

由于網(wǎng)絡(luò)業(yè)務(wù)呈現(xiàn)出波動率聚類特性，即在較大幅度波動后面伴隨著較大幅度的波動，在較小波動幅度后面緊接著較小幅度的波動。為了更好地檢測序列均值的變化和在建模時平滑業(yè)務(wù)序列的波動性，本文提出一種分段雙向 CUSUM(cumulative sum)均值檢測算法。圖2是均值檢測算法的窗口移動示意，檢測窗口中包含L個業(yè)務(wù)序列樣本值。圖2(a)是窗口未檢測出序列均值的變化的示意，此時窗口右移一個樣本點(diǎn)，然后繼續(xù)檢測新窗口中的樣本。圖2(b)在窗口中檢測到時間點(diǎn)為 tC的均值變化點(diǎn)，此時窗口右移 C -1個樣本點(diǎn)再繼續(xù)檢測。

圖2 均值檢測數(shù)據(jù)窗口示意

給定檢測門限eh、序列的期望修正值δ、窗口起始值和長度L。記當(dāng)前窗口起始時刻為1t，向上變化決策函數(shù)為，向下變化決策函數(shù)為

其中，Y+運(yùn)算含義是：當(dāng) 0Y＞ 時，Y Y+= ；當(dāng) Y≤0時， 0Y+= 。Y-運(yùn)算含義是：當(dāng)Y≤0時，Y Y-= ，當(dāng) 0Y＞ 時， 0Y-= 。于是，分段雙向 CUSUM均值檢測算法步驟可由圖3的偽代碼表示。

圖3 分段雙向CUSUM算法偽代碼

由于CUSUM檢測算法假設(shè)序列的均值為負(fù)，而本算法的目標(biāo)檢測序列在實(shí)際物理系統(tǒng)中都是非負(fù)序列，因此需要修正值δ來改造時間序列，取為E(Xt)。而檢測門限值eh采用3倍標(biāo)準(zhǔn)差法，即eh = 3 × s td( Xt)。期望修正值δ、檢測門限值eh和窗口長度L可以根據(jù)當(dāng)前業(yè)務(wù)特征、精度和靈敏度要求在實(shí)際運(yùn)用中靈活調(diào)整。

2.3 限定搜索法

為了獲得流量的分?jǐn)?shù)差分階數(shù) d，可以通過估計(jì)序列的Hurst指數(shù)，再由關(guān)系式 0.5H d= + 得到。經(jīng)典的 Hurst指數(shù)估計(jì)方法[5,23～27]的時間復(fù)雜度不盡相同，但對實(shí)際的復(fù)雜網(wǎng)絡(luò)流量，這些方法的準(zhǔn)確度都不高。由于Hurst指數(shù)描述了序列整體平均的自相似特性，而這種整體的特性不一定適用于具有時變性的復(fù)雜網(wǎng)絡(luò)流量，因此對真實(shí)流量序列進(jìn)行估計(jì)時上述方法都存在誤差，采用不同方法對同一序列獲得的Hurst指數(shù)也有所不同[28]。因此，本文將計(jì)算復(fù)雜度比較低的 A-V小波法[26]和搜索法相結(jié)合，提出一種限定搜索法對d進(jìn)行精確估計(jì)。

如圖4所示，限定搜索法先使用A-V小波法估計(jì)出分?jǐn)?shù)差分階數(shù)d的粗估計(jì)?d，然后在?d的鄰域內(nèi)按照一定的規(guī)律遍歷，用?d對序列進(jìn)行分?jǐn)?shù)差分濾波，計(jì)算濾波后序列的自相關(guān)函數(shù)的平方和[29]。將平方和達(dá)到最小的?d作為分?jǐn)?shù)差分參數(shù)d。

圖4 限定搜索法

對流量序列 Xt進(jìn)行分?jǐn)?shù)差分濾波后獲得長度為N的序列 Wt，即設(shè) W 的K點(diǎn)協(xié)方差t函數(shù)估計(jì)量，歸一化自相關(guān)函數(shù)估計(jì)量k)和自相關(guān)函數(shù)序列的平方和M用如下公式計(jì)算

給定d的鄰域大小ed、M的精度ef，搜索步長step取為 /2ed 。用A-V小波分析法估計(jì)當(dāng)前序列的粗估計(jì)值，則當(dāng)前搜索點(diǎn)dc取為ed-。于是，限定搜索法的步驟可圖5的偽代碼所表示。

圖5 限定搜索法法偽代碼

其中，M(dc)表示對序列tX進(jìn)行分?jǐn)?shù)差分濾波后，再用式(4)～式(6)獲得濾波后序列的平方和M。

對于精度K，可以根據(jù)序列的自相關(guān)函數(shù)估計(jì)量是否顯著趨于0決定。精度需求ed和ef可以根據(jù)數(shù)據(jù)量和最終精度要求在實(shí)際運(yùn)用中靈活調(diào)整。

2.4 模型參數(shù)估計(jì)和檢驗(yàn)

如圖1所示，在前面的2個步驟之后，需要進(jìn)行模型的參數(shù)估計(jì)和檢驗(yàn)，主要包括模型定階、估計(jì)參數(shù)和擬合檢驗(yàn)3個步驟。本文采用了時間序列中的經(jīng)典方法[30,31]進(jìn)行處理。

2.5 業(yè)務(wù)序列預(yù)測算法

基于上述分析，提出如下算法實(shí)現(xiàn)圖1的流程。

1) 對給定業(yè)務(wù)流依2.2節(jié)中分段雙向CUSUM均值檢測算法進(jìn)行去均值，得到零均值序列tX。

2) 采用 2.3節(jié)中限定搜索法得到序列tX的分?jǐn)?shù)差分階數(shù)d。

3) 對tX進(jìn)行分?jǐn)?shù)差分濾波，得到ARMA序列tW。

4) 利用AIC(akaike information criterion)準(zhǔn)則[32,33]對序列tW定階。

5) 得到序列 Wt的參數(shù)組，利用式(1)迭代獲得殘差序列｛at｝ 。

6) 檢測｛at｝ 是否為白噪聲，如果是，則建模算法停止，轉(zhuǎn)入步驟9)；否則，則進(jìn)入一下步驟。

7) 利用AIC準(zhǔn)則對｛at｝ 進(jìn)行GARCH(r,s)定階。

8) 估計(jì)得到 GARCH(r,s)模型的參數(shù)組，利用式(3)迭代計(jì)算出異方差序列{}。

9) 進(jìn)行業(yè)務(wù)序列的預(yù)報(bào)。

為了減小預(yù)測誤差，需要對預(yù)測值進(jìn)行均值補(bǔ)償。設(shè)從時間點(diǎn)t后的 Wt的1步預(yù)測值( 1)為

表1 不同方法對自相似序列Hurst指數(shù)估計(jì)結(jié)果

利用2.2節(jié)中的方法，對時刻 t - L + 1→ t的長度為L的序列進(jìn)行均值檢測，如果沒有檢測到變點(diǎn)，則按照式(7)獲得序列 Xt的單步預(yù)測值(1)，若檢測到變點(diǎn)為 tC，則按照式(8)獲得序列 Xt的單步預(yù)測值(1)

3 預(yù)測算法的性能分析

3.1 算法的復(fù)雜度分析

假定業(yè)務(wù)序列 Xt的長度為N，預(yù)測過程的時間復(fù)雜度分析如下。在限定搜索法中需要 O ( N)次運(yùn)算獲得d的粗估計(jì)值，而精估計(jì)至少需要O ( -log(e f) K N)次運(yùn)算，相比較于K， - l og(e f)很小，因此認(rèn)為限定搜索法的運(yùn)算次數(shù)為 O ( K N )。

其他步驟的運(yùn)算時間和傳統(tǒng)的 FARIMA算法相當(dāng)，需要 O ( N2)次運(yùn)算來進(jìn)行模型定階和參數(shù)估計(jì)。由于K相較于N通常較小，因此整個預(yù)測算法并沒有顯著地增加運(yùn)算的耗時。

3.2 實(shí)驗(yàn)分析

為了在統(tǒng)一的評價(jià)體系下評估限定搜索法，采用Hosking[34,35]法生成若干不同Hurst指數(shù)的數(shù)據(jù)序列，用來檢測算法的性能。選擇方差法、R/S分析法、A-V小波法以及自適應(yīng)法[27]進(jìn)行比較。數(shù)據(jù)序列都采用4 096點(diǎn)，運(yùn)行20次取平均值。

表1給出了對自相似業(yè)務(wù)序列進(jìn)行Hurst指數(shù)估計(jì)的結(jié)果，同時還給出了相應(yīng)算法在仿真平臺上的耗時。當(dāng) Hurst指數(shù)較小時，5種方法估計(jì)結(jié)果的精度相差不大；當(dāng)Hurst指數(shù)較大時，方差法和R/S分析法的精度較差，誤差達(dá)到了10%，對后續(xù)建模算法的準(zhǔn)確度影響較大。R/S分析法耗時最高，是A-V小波法耗時的數(shù)百倍，這與R/S分析法具有所有算法中最高的時間復(fù)雜度 O ( N2)相應(yīng)。

雖然小波法和自適應(yīng)法耗時最短，估計(jì)誤差在3%～5%左右，但經(jīng)常出現(xiàn)無法有效而準(zhǔn)確地確定最優(yōu)尺度區(qū)間的現(xiàn)象。在面臨不同實(shí)際業(yè)務(wù)流時，2種算法都沒有給出最優(yōu)尺度區(qū)間的選擇方法。

限定搜索法建立在小波法和檢測序列自相關(guān)函數(shù)平方和的基礎(chǔ)上，估計(jì)誤差大致為 1‰，時間復(fù)雜度為 ( )O KN。該算法在增加少量計(jì)算開銷的代價(jià)下，提供了更優(yōu)的性能，能夠提高后續(xù)建模精度。

采用均方根誤差(RMSE, root mean-square err or)和相對均方根誤差(RRMSE, relative root meansquare error)來衡量預(yù)測的效果，定義如下。

使用GARCH模型對｛at｝ 建模的目的是提高區(qū)間預(yù)報(bào)的準(zhǔn)確性，因此需要定義一個統(tǒng)計(jì)量來描述區(qū)間預(yù)報(bào)的準(zhǔn)確度?？梢砸佬蛄杏^測值是否落入當(dāng)前觀測值預(yù)測區(qū)間獲得一個 1-0值的命中序列｛ht｝ 。設(shè)檢測的總次數(shù)是T，記某個序列觀測值Xt( k)的95%的置信區(qū)間是 Δt( k )，有

其中，置信區(qū)間針對不同模型具有不同的表達(dá)式。定義區(qū)間預(yù)測準(zhǔn)確度(IFA, interval forecasting accuracy)為

仿真實(shí)驗(yàn)中采用來自ACM SIGCOMM’04會議的真實(shí)網(wǎng)絡(luò)流[35]。用 sig04_ver01(如表 2所示)代表從SIGCOMM’04數(shù)據(jù)流中隨機(jī)選出的10 000個連續(xù)的分組到達(dá)時間戳。類似地，sig04_ver02和sig04_ver03分別代表了另外2組分組到達(dá)時間戳。

表2 仿真業(yè)務(wù)參數(shù)

為了考察大時間尺度和小時間尺度下預(yù)測算法的性能，將這3組數(shù)據(jù)按照10ms(小時間尺度)和100ms(大時間尺度)的尺度進(jìn)行聚合，聚合后的序列樣本值代表當(dāng)前時間尺度內(nèi)到達(dá)的分組個數(shù)，得到表2中的6條業(yè)務(wù)序列。然后將業(yè)務(wù)序列分為前后2部分，前部占總長的80%，用于模型辨識和參數(shù)估計(jì)，最后用建立好的模型對未來值進(jìn)行預(yù)測，將預(yù)測值和后部的真實(shí)值進(jìn)行比較和分析。

在RBF預(yù)測算法的仿真中，由于無法確定時間序列的最佳嵌入維數(shù)和延遲時間[19,20]，因此延遲時間取 1。嵌入維數(shù)采用多次訓(xùn)練的方法來確定，將預(yù)測效果最好的神經(jīng)網(wǎng)絡(luò)作為RBF算法預(yù)測網(wǎng)絡(luò)，同時限制最大神經(jīng)元個數(shù)是1 500。

表3～表5分別對比了在小時間尺度下幾種算法的預(yù)測性能。其中，RMSE越小說明預(yù)測值偏離真實(shí)值的幅度越小，預(yù)測精度越高。從結(jié)果看出，本文算法的RMSE在單步預(yù)測的條件下小于FARIMA預(yù)測算法，和RBF算法基本相當(dāng)，在預(yù)測步數(shù)明顯增加的情況下，本文算法明顯占優(yōu)。

RRMSE是歸一化的RMSE指標(biāo)，衡量了預(yù)測值與真實(shí)值之間歸一化的偏離程度。從結(jié)果看出，本文算法的RRMSE在單步預(yù)測條件下是最優(yōu)的。在預(yù)測步數(shù)增加時，本文算法和RBF算法的小幅增加，而FARIMA算法的RRMSE快速增加到不合理的狀態(tài)，例如表5中FARIMA算法的RRMSE快速增加到 7，此時預(yù)測值的誤差已經(jīng)大致相當(dāng)于真實(shí)值的7倍左右，預(yù)測性能已經(jīng)很不可靠。

表3 小時間尺度下預(yù)測業(yè)務(wù)流sig04_ver01的性能評價(jià)

表4 小時間尺度下預(yù)測業(yè)務(wù)流sig04_ver02的性能評價(jià)

表5 小時間尺度下預(yù)測業(yè)務(wù)流sig04_ver03的性能評價(jià)

IFA指標(biāo)衡量了預(yù)測算法的區(qū)間估計(jì)性能，由于RBF算法沒有實(shí)現(xiàn)區(qū)間估計(jì)的方式，因此只對比了 FARIMA算法。在仿真中采用置信度為95%的置信區(qū)間，因此平均來看，IFA不應(yīng)小于95%。但從結(jié)果來看，當(dāng)預(yù)測步數(shù)大于 1步的時候，F(xiàn)ARIMA算法的IFA下降到50%～60%左右，這說明一半以上的真實(shí)值落在了預(yù)測區(qū)間的外面，預(yù)測性能較差。而由于GARCH模型能比較精確和快速地跟蹤方差變化，根據(jù)歷史值來調(diào)整預(yù)測區(qū)間的大小，使得真實(shí)值落入預(yù)測區(qū)間的概率大大提高，IFA都在75%以上。在表4中，IFA基本穩(wěn)定在95%左右。

表6～表8分別對比了在大時間尺度下幾種預(yù)測算法的性能。由于大時間尺度下時間序列的突發(fā)性要相對小一些，3種算法的性能都相對小時間尺度下有所提高，說明預(yù)測大時間尺度網(wǎng)絡(luò)流量要比預(yù)測小時間尺度的網(wǎng)絡(luò)流量更加可靠和可實(shí)現(xiàn)。例如大時間尺度下的IFA，對比表3和表6，表4和表7、表5和表 8，同樣條件下IFA的性能優(yōu)于小時間尺度，這說明大時間尺度下的業(yè)務(wù)流由于方差更大，方差波動程度也更劇烈，GARCH模型能有效捕捉到這種波動性，因此根據(jù)GARCH估計(jì)出的區(qū)間能夠以更高的概率覆蓋真實(shí)值，達(dá)到較好的預(yù)測性能。

表6 大時間尺度下預(yù)測業(yè)務(wù)流sig04_ver01的性能評價(jià)

表7 大時間尺度下預(yù)測業(yè)務(wù)流sig04_ver02的性能評價(jià)

表8 大時間尺度下預(yù)測業(yè)務(wù)流sig04_ver03的性能評價(jià)

同時從仿真結(jié)果中看出，隨著預(yù)測步數(shù)的增加，RMSE和RRMSE都出現(xiàn)增加。本文算法增加的趨勢要平滑一些，而FARIMA算法增加幅度在有些業(yè)務(wù)流上則快速和明顯。而隨著步數(shù)的增加，IFA在有些業(yè)務(wù)流上也出現(xiàn)比較明顯的大幅下滑，說明該流量序列是一個隨機(jī)性和突發(fā)性都特別強(qiáng)的時間序列，不太可能進(jìn)行長期地精確預(yù)報(bào)，因此在做出短期預(yù)報(bào)后，需要及時根據(jù)后續(xù)真實(shí)值修正模型，再繼續(xù)預(yù)報(bào)。仿真結(jié)果表明，單步預(yù)測的性能是比較可靠和精確的。

圖6是業(yè)務(wù)流sig04_ver02在小時間尺度下的一段預(yù)測結(jié)果，采用單步預(yù)測。小時間尺度上網(wǎng)絡(luò)流量具有很強(qiáng)的突發(fā)性，單峰式的流量暴增點(diǎn)隨處可見。FARIMA模型采用同方差假定，不能有效跟蹤這種突發(fā)性的流量增加點(diǎn)。因此在這些流量突發(fā)處，F(xiàn)ARIMA模型預(yù)測值與真實(shí)值差距較大。而RBF算法同樣不能有效預(yù)測這些突發(fā)點(diǎn)，更多是跟蹤序列均值的變化。本文算法能先平滑序列波動，再使用GARCH跟蹤序列的波動性，使得這些突發(fā)點(diǎn)處的預(yù)測值比較接近真實(shí)值，預(yù)測效果較好。

圖6 小時間尺度流量預(yù)測仿真結(jié)果

圖7是業(yè)務(wù)流sig04_ver01在大時間尺度下的一段預(yù)測結(jié)果。由于時間尺度的加大，在一定程度上平滑了序列的突發(fā)性，因此流量暴增點(diǎn)的個數(shù)明顯減少，但是依然存在個別單峰式突發(fā)點(diǎn)。從仿真結(jié)果看出，在流量比較平穩(wěn)的階段，3種算法預(yù)測結(jié)果都能有效地逼近真實(shí)值。不過與圖6類似，在單峰式突發(fā)點(diǎn)，F(xiàn)ARIMA模型發(fā)現(xiàn)了流量突發(fā)，而不能較準(zhǔn)確地捕捉到突發(fā)點(diǎn)的流量，RBF算法只能預(yù)測到序列均值附近，而基于FARIMA-GARCH的預(yù)測算法明顯更能有效預(yù)測突發(fā)點(diǎn)的流量。

圖7 大時間尺度流量預(yù)測仿真結(jié)果

4 結(jié)束語

本文首先對流量預(yù)測中的2個關(guān)鍵步驟進(jìn)行改進(jìn)，即提出了分段雙向CUSUM檢測算法和限定搜索法，然后在此基礎(chǔ)上提出一種基于 FARIMAGARCH模型的網(wǎng)絡(luò)業(yè)務(wù)預(yù)測算法。

仿真實(shí)驗(yàn)驗(yàn)證了限定搜索法的性能，在 Hurst指數(shù)較大情況下，其精度高于方差法和R/S分析法。雖然比A-V小波法增加了少量的計(jì)算量，但是估計(jì)誤差也相應(yīng)減小，并且該算法的時間復(fù)雜度依然維持在 ( )O KN ，該復(fù)雜度與A-V小波法基本相當(dāng)。

接著采用真實(shí)網(wǎng)絡(luò)的業(yè)務(wù)流量對基于 FARIMAGARCH預(yù)測算法進(jìn)行了仿真驗(yàn)證。本文算法的RMSE和RRMSE與RBF算法基本相當(dāng)，而優(yōu)于傳統(tǒng)的FARIMA預(yù)測算法。同時對突發(fā)點(diǎn)的跟蹤和預(yù)測能力明顯優(yōu)于對比算法，其區(qū)間估計(jì)的性能也較傳統(tǒng)的FARIMA預(yù)測算法要好。本文算法在保持與FARIMA預(yù)測算法基本等價(jià)的運(yùn)算時間復(fù)雜度下，提供了更好的均值和區(qū)間估計(jì)性能，可以方便地應(yīng)用于網(wǎng)絡(luò)流量預(yù)測、接入控制、帶寬預(yù)留和分配以及負(fù)載均衡等場合。

[1] PAXSON V, FLOYD S. Wide-area traffic： the failure of poisson modeling[J]. IEEE/ACM Transactions on Networking, 1995, 3(3)：226-244.

[2] LELAND W E, WILLINGER W, TAQQU M S, et al. On the selfsimilar nature of ethernet traffic[J]. Computer Communication Review,1995, 25(1)：202-213.

[3] LELAND W E, WILLINGER W, TAQQU M S, et al. On the selfsimilar nature of ethernet traffic(extended version)[J]. IEEE/ ACM Transactions on Networking, 1994,2(1)：1-15.

[4] WILLINGER W. Self-similarity in wide-area network traffic[A].Lasers and Electro-Optics Society Annual Meeting[C]. San Francisco,USA,1997.462-463.

[5] HAMILTON J D. Time-Series Analysis[M]. New Jersey： Princeton University Press, 1994.

[6] 王西鋒, 高嶺, 張曉孿. 基于小波技術(shù)的網(wǎng)絡(luò)流量分析和預(yù)測[J].計(jì)算機(jī)應(yīng)用與軟件,2008,25(8)：70-72.WANG X F, GAO L, ZHANG X L. A network traffic analysis and forecast based on wavelet technology[J]. Computer Applications and Software, 2008, 25(8)：70-72.

[7] 白翔字,葉新銘,蔣海. 基于小波變換與自回歸模型的網(wǎng)絡(luò)流量預(yù)測[J].計(jì)算機(jī)科學(xué),2007,34(7)：47-49.BAI X Y, YE X M, JIANG H. Network traffic predicting based on wavelet transform and autoregressive model[J]. Computer Science,2007,34(7)：47-49.

[8] 陳曉天,劉靜嫻. 改進(jìn)的基于小波變換和FARIMA模型的網(wǎng)絡(luò)流量預(yù)測算法[J].通信學(xué)報(bào),2011,32(4)：153-157.CHEN X T, LIU J X. Network traffic prediction based on wavelet transformation and FARIIMA[J]. Journal on Communications, 2011,32(4)：153-157.

[9] TARRAF A, HABIB W, AHMED A. ATM multimedia traffic prediction using neural networks[A]. Global Data Networking Proceedings[C]. Cairo, Egypt, 1993.77-84.

[10] WANG F, XIA H B. Network traffic prediction based on grey neural network integrated model[A]. International Conference on Computer Science and Software Engineering[C]. Wuhan, China, 2008.915-918.

[11] JUN L, LI T, LI X. Network traffic prediction algorithm and its practical application in real network[A]. IFIP International Conference on Network and Parallel Computing Workshops[C]. Liaoning, China,2007.512-517.

[12] ARDHAN S, SATSRI S, CHUTCHAVONG V, et al. Improved model for traffic fluctuation prediction by neural network[A]. International Conference on Control, Automation and Systems[C]. Seoul, Korea,2007.122-125.

[13] ZHU L, QIN L, XUE K, et al. A novel BP neural network model for traffic prediction of next generation network[A]. Fifth International Conference on Natural Computation[C].Tianjin, China, 2009.32-38.

[14] LI X Y. Prediction of traffic flow base on neural network[A]. Intelligent Computation Technology and Automation[C].Changsha, China,2009.374-377.

[15] 王俊松,高志偉. 基于RBF神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)流量建模及預(yù)測[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(13)：6-11.WANG J S, GAO Z W. Network traffic modeling and prediction based on RBF neural network[J]. Computer Engineering and Applications,2008,44(13)：6-11.

[16] WEN Y, YANG D Y, ZHAO Y L. Traffic flow prediction based on wavelet transform and radial basis function network[A]. International Conference on Logistics Systems and Intelligent Management[C].Harbin, China, 2010.969-972.

[17] 鄒伯賢,劉強(qiáng). 基于 ARMA 模型的網(wǎng)絡(luò)流量預(yù)測[J].計(jì)算機(jī)研究與發(fā)展, 2002, 39(12)：1645-1652.ZOU B X, LIU Q. Arma-based traffic prediction and overload detection of network[J]. Journal of Computer Research and Development,2002, 39(12)：1645-1652.

[18] 舒炎泰,王雷,張連芳等. 基于FARIMA 模型的Internet網(wǎng)絡(luò)業(yè)務(wù)預(yù)報(bào)[J].計(jì)算機(jī)學(xué)報(bào),2001,24(1)：46-54.SHU Y T, WANG L, ZHANG L F, et al. Internet traffic modeling and prediction using FARIMA models[J]. Chinese Journal of Computers,2001, 24(1)：46-54.

[19] 馮慧芳. IEEE 802.11 無線局域網(wǎng)業(yè)務(wù)流特性研究及預(yù)報(bào)[D].天津：天津大學(xué),2006.FENG H F. Traffic Characterization and Prediction in IEEE 802.11 WLANs[D]. Tianjin： Tianjin University,2006.

[20] 呂金虎.混沌時間序列分析及其應(yīng)用[M]. 武漢：武漢大學(xué)出版社,2002.LV J H. Chaos Time Series Analysis and Application[M].Wuhan： Wuhan University Press, 2002

[21] 楊雙懋,郭偉,唐偉.認(rèn)知無線網(wǎng)絡(luò)中基于時間序列預(yù)測的沖突分解算法.通信學(xué)報(bào),2011,32(11)：51-58.YANG S M, GUO W ,TANG W. A collision resolution algorithm based on time-series forecasting for cognitive wireless networks[J].Journal on Communications, 2011,32(11)：51-58.

[22] WILFREDO P. Long-Memory Time Series ： Theory and Methods[M].Hoboken： John Wiley & Sons, 2007.

[23] ZHANG H F, SHU Y T, YANG O. Estimation of hurst parameter by variance time plots[A]. IEEE Pacific Rim Conference on Communications, Computers and Signal Processing[C]. Victoria, Canada, 1997.883-886.

[24] CLEGG R G. A practical guide to measuring the hurst parameter[J].International Journal of Simulation： Systems, Science and Technology,2006,7(2)：3-14.

[25] LAU W C, ERRAMILLI A, WANG J L, et al. Self-similar traffic parameter estimation： a semi-parametric periodogram-based algorithm[A]. IEEE Global Telecommunications Conference[C]. Singapore, 1995.2225-2231.

[26] ABRY P, VEITCH D. Wavelet analysis of long range dependent traffic[J]. IEEE Transactions on Information Theory, 1998, 44(1)：2-15.

[27] 洪飛,吳志美. 基于小波的 Hurst指數(shù)自適應(yīng)估計(jì)方法[J]. 軟件學(xué)報(bào),2005,16(9)：1685-1689.HONG F; WU Z M. Adaptive hurst index estimator based on wavelet[J]. Journal of Software, 2005, 16(9)：1685-1689.

[28] WILLIAM R, LES O, MARCO R, et al. Estimators for long range dependence： an empirical study[J]. Electronic Journal of Statistics,2009.1-16.

[29] 陳彥輝,謝維信. 隨機(jī)分形信號參數(shù)的分?jǐn)?shù)差分估計(jì)[J].電子與信息學(xué)報(bào),2001,23(1)：9-15.CHEN Y H, XIE W X. Fractional difference estimation for the parameters of random fractal signal[J]. Journal of Electronics and Information Technology, 2001, 23(1)：9-15.

[30] BROCKWELL P J,DAVIS R A. Time Series： Theory and Methods[M].New York： Springer,1987.

[31] GARCH 模型與應(yīng)用簡介[EB/OL]. http：//wenku.baidu.com/view/bd93f636a32d7375a41780b7.html, 2011.GARCH model application profile[EB/OL]. http：//wenku.baidu.com/view/bd93f636a32d7375a41780b7.html, 2011.

[32] AKAIKE H. A new look at the statistical model identification[J]. IEEE Transactions on Automatic Control, 1974,19(6)：716-723.

[33] SHIBATA R. Selection of the order of an autoregressive model by Akaike's information criterion[J]. Biometrika, 1976,63(1)：117-126.

[34] HOSKING J R M. Modeling persistence in hydrological time series using fractional differencing[J]. Water Resources Research, 1984,20(12)： 1898-1908.

[35] Sigcomm 2004 trace dataset[EB/OL]. http：//www.crawdad.org/meta.php?name=uw/sigcomm2004, 2011.