基于小波包分析的網(wǎng)絡(luò)流量組合預(yù)測(cè)模型

李慧敏

(福建交通職業(yè)技術(shù)學(xué)院信息技術(shù)與工程系，福建 福州 350007)

隨著計(jì)算機(jī)網(wǎng)絡(luò)的迅速發(fā)展，網(wǎng)絡(luò)規(guī)模日益龐大和復(fù)雜，發(fā)生各種故障的可能性也越大，為了給用戶提供優(yōu)質(zhì)的服務(wù)，網(wǎng)絡(luò)的維護(hù)與管理顯得尤為重要.傳統(tǒng)的響應(yīng)式網(wǎng)絡(luò)管理方法是在告警之后，解決潛在的問題，這時(shí)候網(wǎng)絡(luò)服務(wù)很可能已經(jīng)受到影響.這就使得網(wǎng)絡(luò)流量預(yù)測(cè)技術(shù)備受關(guān)注，因?yàn)樗沟锰崆鞍l(fā)出預(yù)警成為可能.人們最初主要借鑒PSTN的流量模型，用Poisson模型來描述數(shù)據(jù)網(wǎng)絡(luò)的流量模型.隨著網(wǎng)絡(luò)的發(fā)展，Paxson V與Floyd S指出這種傳統(tǒng)的Poisson模型已經(jīng)不適于Internet的流量描述與預(yù)測(cè)［1］.大量研究表明，實(shí)際的網(wǎng)絡(luò)流量具有自相似性，是指統(tǒng)計(jì)意義下的自相似性，即它的統(tǒng)計(jì)特性獨(dú)立于時(shí)間范圍.在這方面國(guó)內(nèi)很多學(xué)者進(jìn)行了大量的研究工作.例如，叢鎖等給出了基于小波技術(shù)的網(wǎng)絡(luò)流量特性刻畫［2］，并提出一種基于小波變換的網(wǎng)絡(luò)流量多重分形模型［3］，用于分析網(wǎng)絡(luò)流量的自相似特征;很多學(xué)者也把人工神經(jīng)網(wǎng)絡(luò)應(yīng)用到流量預(yù)測(cè)中［4－5］并取得了一定預(yù)測(cè)效果.

如何提高預(yù)測(cè)的準(zhǔn)確度一直是網(wǎng)絡(luò)流量預(yù)測(cè)的主要難題.本文就此問題展開研究.在本文的研究中，采用了從實(shí)際網(wǎng)絡(luò)上收集的實(shí)時(shí)網(wǎng)絡(luò)業(yè)務(wù)數(shù)據(jù)，實(shí)驗(yàn)結(jié)果表明該模型與比傳統(tǒng)單一的預(yù)測(cè)模型相比有較高的預(yù)測(cè)精度.

1 小波包多尺度分析

小波變換理論［6］是上世紀(jì)80年代后期發(fā)展起來的應(yīng)用數(shù)學(xué)分支，近年來被廣泛地應(yīng)用于信號(hào)處理、圖像處理、模式識(shí)別等科學(xué)領(lǐng)域.它具有多分辨率(Multi－Resolution)即多尺度的特點(diǎn)，可以由粗及精地逐步觀察信號(hào).小波變換能有效處理非平穩(wěn)時(shí)間序列，通過小波分解將時(shí)間序列一層一層分解到不同的頻率通道上，得到的結(jié)果在頻率成分上比原始信號(hào)單一，并且對(duì)時(shí)間序列做了平滑.小波包(waveletpacket)的概念是由M.V.Wiekerhauser，R.R.Coifman 等人在小波變換的基礎(chǔ)上進(jìn)一步提出來的，小波包借助于小波分解濾波器在各個(gè)尺度上對(duì)每個(gè)子帶均進(jìn)行再次降半劃分，從而得到比二進(jìn)離散小波變換更精細(xì)的信號(hào)分解.

小波包的基本思想是對(duì)多分辨分析中的小波子空間也進(jìn)行分解.令

式中g(shù)(k)=(-1)kh(1-k)，即兩系數(shù)也具有正交關(guān)系，其等價(jià)表示為

對(duì)離散信號(hào)S，采用(2)式和(3)式構(gòu)造的小波包序列進(jìn)行3層分解，分解結(jié)構(gòu)如圖1所示.

圖1 小波包的三層分解結(jié)構(gòu)樹

1.1 小波包的分解與重構(gòu)

信號(hào)f(t)的正交小波分解可以表示為

式中

正交小波的重建公式為

設(shè)

小波包系數(shù)的重構(gòu)可表示為

式中g(shù)0(l-2k)，g1(l-2k)分別為小波包重構(gòu)的低通和高通濾波器組.

根據(jù)(10)式，信號(hào)可以通過小波包分解系數(shù)重構(gòu)出各個(gè)子頻帶內(nèi)的時(shí)域信號(hào).重構(gòu)后的時(shí)域信號(hào)可以表示為

其中 x(t)表示原始信號(hào);x0(t)，x1(t)，…，x2j-1(t)表示經(jīng)過小波包分解系數(shù)重構(gòu)后在各個(gè)子頻帶內(nèi)的時(shí)域信號(hào).可見，小波包分解系數(shù)重構(gòu)后的各個(gè)子頻帶時(shí)域信號(hào)的疊加和就是原始信號(hào)，分解的頻帶個(gè)數(shù)由分解尺度決定.

2 網(wǎng)絡(luò)流量預(yù)測(cè)模型

網(wǎng)絡(luò)流量［7］具有較高的復(fù)雜性、非線性、不平穩(wěn)性，可以通過小波包變換對(duì)其進(jìn)行多尺度分解和單支重構(gòu)獲得多個(gè)近似信號(hào)和細(xì)節(jié)信號(hào).通過分解和重構(gòu)可以使信號(hào)的平穩(wěn)性得到改善.近似信號(hào)和細(xì)節(jié)信號(hào)變換特點(diǎn)各不相同:近似信號(hào)保持了與原始流量完全相同的變化趨勢(shì)而且數(shù)值很接近，體現(xiàn)了它對(duì)原始序列長(zhǎng)期的、根本性影響，較好地體現(xiàn)了流量的周期性，可以采用LMMSE估計(jì)方法來預(yù)測(cè)下一時(shí)刻網(wǎng)絡(luò)流量的近似信號(hào);細(xì)節(jié)信號(hào)比較平穩(wěn)，由于小波可以近似地去除流量過程的長(zhǎng)相關(guān)，所以細(xì)節(jié)信號(hào)體現(xiàn)了短時(shí)間依賴關(guān)系，可以通過對(duì)細(xì)節(jié)信號(hào)先建立AR模型，然后再通過AR模型實(shí)現(xiàn)對(duì)下一時(shí)刻的細(xì)節(jié)信號(hào)的預(yù)測(cè).最后，把各個(gè)預(yù)測(cè)的信號(hào)通過組合就可以生成流量的預(yù)測(cè)結(jié)果.

2.1 對(duì)近似信號(hào)的預(yù)測(cè)

2.1.1 LMMSE 估計(jì)

文獻(xiàn)［8］中給出了一種基于線性最小平均平方誤差估計(jì)(LMMSE)的網(wǎng)絡(luò)流量預(yù)測(cè)方法.令預(yù)測(cè)值^f(n+1)為已測(cè)量的前n個(gè)流量值的加權(quán)和:

式中，R(n)是時(shí)間序列的協(xié)方差函數(shù)，一般可以通過經(jīng)驗(yàn)公式獲得，n是一個(gè)可變的參數(shù)，表示序列采樣數(shù).

2.1.2 對(duì)近似信號(hào)的預(yù)測(cè)

由于近似信號(hào)有較強(qiáng)的周期性，屬于非平穩(wěn)信號(hào)，對(duì)逼近信號(hào)進(jìn)行LMMSE估計(jì)必須滿足是零均值平穩(wěn)隨機(jī)過程的假設(shè)，可將待預(yù)測(cè)的原始信號(hào)序列進(jìn)行零均值化處理.設(shè)x(t)表示原始序列，λ表示序列x(t)的均值，y(t)表示零均值化后的序列，則

通過上式處理后，y(t)可以看作近似平穩(wěn)序列，用LMMSE對(duì)序列y(t)進(jìn)行預(yù)測(cè)的結(jié)果加上λ就可以得到原始序列的預(yù)測(cè)結(jié)果.

2.2 對(duì)細(xì)節(jié)信號(hào)的預(yù)測(cè)

通過對(duì)原始序列進(jìn)行小波包多尺度分解和重構(gòu)可以得到一系列細(xì)節(jié)信號(hào)，這些信號(hào)比較平穩(wěn)，而且表現(xiàn)為短時(shí)間依賴關(guān)系，可以采用經(jīng)典的自回歸(AR)模型進(jìn)行預(yù)測(cè).

對(duì)模型參數(shù)的估計(jì)通常有矩估計(jì)、最小二乘估計(jì)、極大似然估計(jì)等.本文采用矩估計(jì)方法.

用AR模型進(jìn)行預(yù)測(cè)分析時(shí)，通常要經(jīng)過模型定階、參數(shù)估計(jì)、適應(yīng)性檢驗(yàn)、利用模型遞推法預(yù)測(cè)等幾個(gè)主要步驟.

對(duì)各序列分別進(jìn)行分析和預(yù)測(cè)后，通過(11)式組合預(yù)測(cè)的各個(gè)近似信號(hào)和細(xì)節(jié)信號(hào)就可以生成原始流量的預(yù)測(cè)值.

3 網(wǎng)絡(luò)流量預(yù)測(cè)實(shí)驗(yàn)

3.1 實(shí)驗(yàn)流程

基于小波包分析的網(wǎng)絡(luò)流量組合預(yù)測(cè)模型的實(shí)現(xiàn)過程描述如圖2所示.其中，LMMSE估計(jì)需要先采用AIC準(zhǔn)則來確定模型的階數(shù)，再利用(12)～(14)式計(jì)算就可得到預(yù)測(cè)值.而使用AR模型對(duì)一個(gè)單獨(dú)序列進(jìn)行預(yù)測(cè)的實(shí)現(xiàn)過程主要包括模型定階、參數(shù)估計(jì)、適應(yīng)性檢驗(yàn)、利用模型遞推法預(yù)測(cè)這4個(gè)階段.

圖2 基于小波包分析的網(wǎng)絡(luò)流量組合預(yù)測(cè)模型的實(shí)現(xiàn)過程

3.2 實(shí)驗(yàn)結(jié)果及分析

本文采用Cricket(基于SNMP協(xié)議的監(jiān)控網(wǎng)絡(luò)流量和主機(jī)資源的開放源代碼的管理工具)對(duì)中國(guó)教育科研網(wǎng)福建主節(jié)點(diǎn)上一臺(tái)高端路由器(Cisco 7609)某端口流出流量進(jìn)行監(jiān)測(cè)，監(jiān)測(cè)時(shí)間為3天，采樣時(shí)間間隔為5分鐘，所得流量數(shù)據(jù)曲線如圖3所示.從圖3中可以看出它具有很強(qiáng)的不規(guī)則性，而同時(shí)又表現(xiàn)出一定的周期性因素.

圖3 實(shí)際流量曲線圖

對(duì)實(shí)際流量數(shù)據(jù)序列進(jìn)行零均值化.采用雙正交小波bior6.8，用小波包分解算法對(duì)序列Y進(jìn)行3層分解，并對(duì)近似部分和細(xì)節(jié)部分分別進(jìn)行重構(gòu)，得到的結(jié)果數(shù)據(jù)圖形如圖4所示.

圖4 D0～D7

其中，D0～D7分別是第3層各部分分別重構(gòu)到原級(jí)別的序列.比較可以看出，近似部分的重構(gòu)結(jié)果明顯比原序列平滑.對(duì)于這些分解重構(gòu)后的各個(gè)序列，可以再次用其它的方法進(jìn)行平穩(wěn)化，從而能得到更高的預(yù)測(cè)準(zhǔn)確度.但是，為了體現(xiàn)出本文基于小波包變換的預(yù)測(cè)效果，我們不再對(duì)它們做其它平穩(wěn)化處理，而是直接通過建立組合模型進(jìn)行預(yù)測(cè).

對(duì)D0進(jìn)行LMMSE估計(jì)預(yù)測(cè)，對(duì)D1～D7采用AR模型進(jìn)行預(yù)測(cè)，所得預(yù)測(cè)結(jié)果如圖5所示.由圖5可以看出，這種預(yù)測(cè)方法對(duì)急劇變化的點(diǎn)掌握得不好(這些點(diǎn)的誤差較大，在定量誤差分析時(shí)會(huì)對(duì)誤差參數(shù)產(chǎn)生較大影響)，并且可以看出雖然預(yù)測(cè)結(jié)果的趨勢(shì)跟實(shí)際流量一致，但隨著流量值的增大，誤差也相應(yīng)變大.

圖5 預(yù)測(cè)圖和預(yù)測(cè)誤差

在分解層數(shù)2和3下，使用本文介紹的方法，對(duì)原始流量數(shù)據(jù)進(jìn)行預(yù)測(cè)，預(yù)測(cè)結(jié)果的誤差數(shù)據(jù)如表1所示.其中，MAE(Mean Absolute Error)為平均絕對(duì)誤差，MRE(Mean Relative Error)為平均相對(duì)誤差.表1中數(shù)據(jù)表明，隨著分解層數(shù)的增加，預(yù)測(cè)誤差變小，即預(yù)測(cè)準(zhǔn)確度提高，因?yàn)榉纸鈱訑?shù)越多，分解后的各部分在頻率成分上越單一.這也在一定程度上反映了小波包變換在本文預(yù)測(cè)方法中所起的作用.

表1 變換層數(shù)為2和3時(shí)的預(yù)測(cè)誤差

表2 不同方案的預(yù)測(cè)誤差對(duì)比表

為了查看本文方法的預(yù)測(cè)效果，我們分別使用本文介紹的方法和文獻(xiàn)［8］介紹的方法對(duì)圖3所示原始流量數(shù)據(jù)進(jìn)行預(yù)測(cè)，預(yù)測(cè)結(jié)果的誤差數(shù)據(jù)如表2所示.

由表2中數(shù)據(jù)可以看出，本文方法的預(yù)測(cè)誤差比另一種方案的預(yù)測(cè)誤差有了大幅減小，這表明小波包分解和重構(gòu)在預(yù)測(cè)過程中的作用是非常明顯的.這個(gè)結(jié)果說明了，基于小波包分析的網(wǎng)絡(luò)流量組合預(yù)測(cè)模型，對(duì)網(wǎng)絡(luò)流量預(yù)測(cè)是可行、有效的，并且比常用的預(yù)測(cè)方法具有更高的預(yù)測(cè)準(zhǔn)確度.

4 結(jié)語(yǔ)

本文提出一種基于小波包分析的網(wǎng)絡(luò)流量組合預(yù)測(cè)模型，實(shí)驗(yàn)結(jié)果表明，該方法比傳統(tǒng)的預(yù)測(cè)方法具有更高的預(yù)測(cè)精度，這表明小波包變換在網(wǎng)絡(luò)流量預(yù)測(cè)中的作用是顯著的.在對(duì)預(yù)測(cè)結(jié)果的分析中發(fā)現(xiàn)，本文的方法對(duì)急劇變化的點(diǎn)掌握得不好，并且可以看出雖然預(yù)測(cè)結(jié)果的趨勢(shì)跟實(shí)際流量一致，但隨著流量值的增大，誤差也相應(yīng)變大.所以下一步的主要研究工作就是針對(duì)這一塊做改進(jìn).

［1］Paxson V，F(xiàn)loyd S.Wide－area traffic:the failure of poissonmodeling［J］.IEEE/ACM Transactions on Networking，1995，3:226 －244.

［2］韓良秀，叢鎖.基于小波技術(shù)的網(wǎng)絡(luò)流量特性刻畫［J］.小型微型計(jì)算機(jī)系統(tǒng)，2001，2(9):1110 －1113.

［3］叢鎖，韓良秀.基于離散小波變換的網(wǎng)絡(luò)流量多重分形模型［J］.通信學(xué)報(bào)，2003，24(5):3 －8.

［4］程光，龔儉.CERNET流量行為季節(jié)預(yù)測(cè)模型［J］.小型微型計(jì)算機(jī)系統(tǒng)，2002，23(11):1321 －1324.

［5］馮海亮，陳滌，林青家，等.一種基于神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)流量組合預(yù)測(cè)模型［J］.計(jì)算機(jī)應(yīng)用2006，26(9):2206 －2208，2228.

［6］楊建國(guó).小波分析及其工程應(yīng)用［M］.北京:機(jī)械工業(yè)出版社，2005:17－63.

［7］李小航，劉淵，劉元珍.基于小波多尺度分析的網(wǎng)絡(luò)流量組合預(yù)測(cè)方法研究［J］.微電子學(xué)與計(jì)算機(jī)，2008，25(1):130 －133.

［8］Gao Yuan，He Guanghui，Hou JC.On exploiting traffic predictability in active queue management［M］.In Proc.of the INFOCOM 2002.New York:IEEE Communications Society，2002:1630 －1639.