基于多尺度小波變化的自相似網(wǎng)絡(luò)流量預(yù)測

何凱霖，丁曉峰

（電子科技大學(xué) 成都學(xué)院 計算機系，四川 成都611731）

0 引 言

Leland W E等［1］在大量的業(yè)務(wù)流量監(jiān)測過程中發(fā)現(xiàn)了網(wǎng)絡(luò)流量具有自相似 （self－similarity）特性，指出實際流量序列的自相關(guān)函數(shù)隨時間尺度的增大呈漸近雙曲線衰減而非負指數(shù)衰減，流量表現(xiàn)出重尾分布的長相關(guān)性 （longrange dependence，LRD）特征，并且不論網(wǎng)絡(luò)的拓撲結(jié)構(gòu)、用戶數(shù)量、服務(wù)類型如何變化，這種自相似性是始終存在的。這宣告了具有短相關(guān)特征的流量模型已不能充分反映網(wǎng)絡(luò)流量的高可變性，不再適合于網(wǎng)絡(luò)流量的分析和建模［2，3］。

后續(xù)研究結(jié)果表明［4－6］，傳輸層協(xié)議本身就是導(dǎo)致網(wǎng)絡(luò)流量出現(xiàn)自相似性的決定因素之一，特別是占整個網(wǎng)絡(luò)流量的90%左右的TCP協(xié)議，其擁塞控制中的超時重傳和指數(shù)退避機制會使分組到達時間間隔呈重尾分布；反言之，網(wǎng)絡(luò)流量自相似性的存在又給網(wǎng)絡(luò)管理和網(wǎng)絡(luò)協(xié)議的運行增加了復(fù)雜性［7］，如大尺度上的突發(fā)性會造成網(wǎng)絡(luò)資源嚴(yán)重過利用率和欠利用率時間的增大，而且隨自相似程度的增加，丟失率、重傳率以及平均隊列長度和響應(yīng)時間均隨之增長［8］；路由器中包序列的排隊問題也受網(wǎng)絡(luò)流量在小尺度時間范圍內(nèi)波動的影響，而尺度的劃分通常正是以擁塞控制機制中的RTT為基準(zhǔn)［9，10］。所以，網(wǎng)絡(luò)流量尺度特性和不同尺度上的自相似特征必然影響到TCP的擁塞控制機制，這使傳統(tǒng)模型下所沿用的如下結(jié)論都不再適用：緩存線性增長導(dǎo)致報文丟失按指數(shù)規(guī)律減少以及傳輸帶寬利用率成比例增長等。這直接導(dǎo)致網(wǎng)絡(luò)擁塞不可避免，從而造成TCP難以有效地實施網(wǎng)絡(luò)控制和QoS保證。因此針對具有自相似特性的流量，網(wǎng)絡(luò)協(xié)議的優(yōu)化尚需更多的研究。

本文提出以DWT多尺度分析為依據(jù)建立網(wǎng)絡(luò)流模型并進行流量預(yù)測。把利用該模型計算得到的預(yù)測流量相似性程度值Hurst引入路由器的主動隊列管理算法 （AQM）中，采用AQM算法形成的嚴(yán)謹?shù)捻憫?yīng)方案對異常的估計流量進行處理，可以提高動態(tài)流量控制的有效性，實現(xiàn)了網(wǎng)絡(luò)協(xié)議的優(yōu)化。

1 流量數(shù)據(jù)基于DWT的多尺度分析

考慮到網(wǎng)絡(luò)流量具有較高的復(fù)雜性和不平穩(wěn)特性，本文首先利用DWT對原始流量數(shù)據(jù)進行多尺度分解，以獲得包含不同頻率特性的近似分量與細節(jié)分量。所謂近似分量是指與分解前的網(wǎng)絡(luò)流量基本性質(zhì)一致的分量，即基本不包含高頻的短相關(guān)特性而保留著未分解流量的長相關(guān)性等；所謂細節(jié)分量是指反映細節(jié)特性如動態(tài)流量的短期依賴關(guān)系即短相關(guān)性。因此通過小波變換不僅保持原流量的趨勢并減少突發(fā)，能有效達到消噪預(yù)處理的效果，且使網(wǎng)絡(luò)業(yè)務(wù)流量的復(fù)雜性得到分解。之后在特性相對單一的小波分量上建立刻畫網(wǎng)絡(luò)流量特性的序列模型，可實現(xiàn)以較快的收斂性、較高的平穩(wěn)性和較低的誤差來進行流量預(yù)測?；贒WT的多尺度分析方法在網(wǎng)絡(luò)流量預(yù)測和控制中極具有效性。并且通過分析論證可得網(wǎng)絡(luò)協(xié)議性能優(yōu)化空間與預(yù)測流量自相似程度密切相關(guān)。大的相似性在適當(dāng)條件下可以提供更優(yōu)越的性能。

1.1 自相似程度的判斷

為達到對網(wǎng)絡(luò)流量自相似性程度進行判斷的目的，本文選取研究者普遍認同的用以刻畫自相似性程度的Hurst參數(shù)H，當(dāng)H取值在1／2＜H＜1之間時，則認為隨機過程具有自相似性，其程度大小隨H值的增大而增加。這種現(xiàn)象映射到實際網(wǎng)絡(luò)中就叫做網(wǎng)絡(luò)流量突發(fā)，目前網(wǎng)絡(luò)實際流量的H估計值通常在0.7～0.9之間。以上用于求解Hurst值的方法需要較強的穩(wěn)定性，故采用R／S法 （resealed adjusted range statistic）。

1.2 基于DWT的多尺度分析過程

要將小波變換應(yīng)用于網(wǎng)絡(luò)流量分析中，需要采用離散小波變換 （DWT）以更好地處理離散數(shù)據(jù)信號［11，12］。這里將信號f（t）的連續(xù)小波變換 （CWT）定義為

圖1 j層小波分解過程

Aj＝ ｛aj，1，aj，2，…，aj，k｝為第j層的尺度系數(shù)，反映第j層的低頻近似分量，表達序列的大致趨勢；Dj＝ ｛dj，1，dj，2，…，dj，k｝為第j層的小波系數(shù)，反映第j層的高頻細節(jié)分量，表達序列在細節(jié)上的差異。直觀上，DWT把一維網(wǎng)絡(luò)流量信號分解為兩維信號。原始信號A0分解為A1和D1，低頻部分進一步分解，即：A1再分解為A2和D2，…，如此進行可得到任意尺度 （或分辨率）上的近似分量和細節(jié)分量，力求構(gòu)造一個頻率上高度逼近L2（R）空間的正交小波基。而Mallat中的單支重構(gòu)則是對小波分解的小波系數(shù)和尺度系數(shù)進行小波逆變換，形成與原始序列等長度的單支序列。

1.3 DWT的具體實施

本文以MATLAB為流量小波變換的輔助工具，作為母小波的函數(shù)必須具有很好的時、頻局部特性，以更好地刻畫信號的突變信息。因此這里選取Haar小波、Daubechies小波系 （DbN）、Coiflets小波系 （CoifN）和Symlets小波系 （SymN）等常見小波基進行測試，將原始流量與合成流量分別用相應(yīng)的小波進行分解，并統(tǒng)計各尺度上小波系數(shù)的標(biāo)準(zhǔn)差，最終選擇支集長度較小的、仿真流量性能與原始流量性能較為接近的Db4為實驗用小波基函數(shù)。對流量數(shù)據(jù)的DWT一維多尺度分解、消噪與重構(gòu)在MATLAB中的實現(xiàn)代碼如下：

2 流量序列預(yù)測模型

2.1 FARIMA

網(wǎng)絡(luò)流量的建模選用分形自回歸求和滑動平均模型，簡稱 FARIMA （fractional auto－regressive integrated moving average）。在建模過程中使用了3個參數(shù)p、d和q，其中d可以體現(xiàn)所要估測流量的長相關(guān)性，而p、q則反映所含部分流量的短相關(guān)性，所以該方法生成的預(yù)測序列能保持與真實序列一致的長相關(guān)和短相關(guān)特征，具有較高的靈活性。FARIMA是ARIMA （p，d，q）模型的自然擴展，后者可表示為φ（B）（1－B）dXt＝ Θ（B）at，其中B 是滯后算子，1－B為差分算子，｛at｝為白噪聲序列。FARIMA與ARIMA的唯一區(qū)別在于參數(shù)d允許使用非整數(shù)，此時d階差分算子其 中 參 數(shù)參數(shù)d可由式H＝d＋0.5求得，H 為序列的Hurst參數(shù)，即可利用Hurst參數(shù)計算間接對d進行近似估計。

2.2 模型整體功能結(jié)構(gòu)

這里將所設(shè)計的流量序列預(yù)測模型的整體功能進行算法描述，如圖2所示。

（1）為了對網(wǎng)絡(luò)自相似性進行估測，需要計算表征其程度大小的H值。這里求解采用的方法是R／S法，其應(yīng)用對象是代表待測流量的序列f（t），由關(guān)系式d＝H－0.5獲得對預(yù)測模型FARIMA （p，d，q）中差分參數(shù)d的有效估計。

（2）對于帶有明顯相似性和長相關(guān)特征的初始流量數(shù)據(jù)f（t），采用Db4DWT方法予以分解，規(guī)定其分解尺度為J，該過程結(jié)束后輸出量分別為近似以及細節(jié)分量。前者以AJ表示，后者以D1，D2，…，DJ表示。

圖2 基于DWT多尺度分析的協(xié)議優(yōu)化模型

（3）將分解后的近似分量使用FARIMA模型進行預(yù)測得到a’j；同理，對 （2）中D1，D2，…，DJ予以相同處理后記所得結(jié)果為a’1，a’2，…，a’j。

（4）利用Mallat算法對 （3）中所得兩類分量予以重構(gòu)，具體公式如下：a′j－1＝

（5）經(jīng) （4）得到新的流量序列f′（t），為了明確新的網(wǎng)絡(luò)自相似性程度亦即H’值，對f′（t）施以FARIMA模型預(yù)測初始流量。一般情況下參數(shù)p、q隨現(xiàn)實狀況而定，本文p賦值2，q賦值1。

（6）最后得到FARIMA （p，d，q）擬合流量，進一步以均方誤差來定量評估預(yù)測效果，M為數(shù)據(jù)總量。對比分析利用計算機仿真所得結(jié)果與真實流量狀況，總結(jié)本文估測結(jié)果在變化趨勢等方面對真實狀況的趨近程度。進一步分析當(dāng)前時刻過后網(wǎng)絡(luò)流量在各方面可能發(fā)生的變化，以輔助實施網(wǎng)絡(luò)協(xié)議的擁塞控制策略。

3 網(wǎng)絡(luò)協(xié)議優(yōu)化策略及仿真實驗

3.1 網(wǎng)絡(luò)擁塞和流量控制機制分析

網(wǎng)絡(luò)中經(jīng)常出現(xiàn)擁塞甚至系統(tǒng)崩潰等情況，用以解決這一問題的方案基本都是在網(wǎng)絡(luò)中建立擁塞控制機制，以最具代表性的TCP協(xié)議為例 （根據(jù)MCI的統(tǒng)計，網(wǎng)絡(luò)中總字節(jié)數(shù)的95%和總報文數(shù)的90%均使用TCP傳輸），TCP采用慢啟動、擁塞避免、快速重傳、快速恢復(fù)、選擇性應(yīng)答 （SACK）等算法確保網(wǎng)絡(luò)的傳輸性能。然而網(wǎng)絡(luò)中不存在專門的連接通道供端系統(tǒng)查明網(wǎng)絡(luò)狀況，因此端系統(tǒng)采取控制網(wǎng)絡(luò)傳送數(shù)據(jù)等行動的根據(jù)唯有來源于ACK、RTO超時等信息。這就造成反映不及時進而可能導(dǎo)致反饋延遲和網(wǎng)絡(luò)抖動等問題［11］。而作為網(wǎng)絡(luò)狀態(tài)最直接感受者的路由器，如果能在IP層參與擁塞控制，必然成為端系統(tǒng)的有力補充。路由器通過檢測當(dāng)前負載狀況，可以在網(wǎng)絡(luò)設(shè)備的緩沖溢出之前丟棄或標(biāo)記報文，以降低排隊延遲，并形成擁塞指示以輔助端系統(tǒng)進行流量控制［12］。

在流量估算和控制中，當(dāng)前網(wǎng)絡(luò)協(xié)議常選擇的是EWMA法。該方法可以滿足低通濾波的要求，相鄰兩個時刻的流量速率估算方式為。應(yīng)注意，EWMA算法對于只存在短相關(guān)性的傳統(tǒng)泊松過程是合理的，即作為短相關(guān)流量，其自相關(guān)函數(shù)呈指數(shù)衰減，距當(dāng)前分組到達時間越近的速率值對于當(dāng)前速率估算值的影響越大；當(dāng)時間間隔Ts足夠大時，R（t＋Ts）與R（t）的流量速率是不相關(guān)的。這與實際自相似網(wǎng)絡(luò)流量中大量存在的長相關(guān)特征并不相符，顯然并不適合在擁塞控制協(xié)議中用作網(wǎng)絡(luò)流量控制的關(guān)鍵手段。

此外，我們通過實驗統(tǒng)計了在不同自相似參數(shù)下分組丟失率隨緩沖區(qū)容量的變化情況，如圖3所示?？捎^察到在緩沖區(qū)容量相同時，長相關(guān)業(yè)務(wù)在H值越大時分組丟失率越高。這證實了自相似程度增加時，網(wǎng)絡(luò)流量突發(fā)性增強，重傳率、平均隊列長度和響應(yīng)時間均增大，網(wǎng)絡(luò)性能下降。

圖3 自相似性程度對不同緩沖區(qū)容量下的分組丟失率的影響

綜合上述分析，本文嘗試將基于DWT的流量預(yù)測模型的結(jié)果引入到路由器的主動隊列管理算法 （AQM）中，利用自相似流量的統(tǒng)計規(guī)律和預(yù)測特征，以擁塞預(yù)警而非“被動響應(yīng)”的方式，形成對網(wǎng)絡(luò)協(xié)議中的擁塞控制機制的有效優(yōu)化。

3.2 協(xié)議優(yōu)化策略

在改進AQM算法時，這里選擇基于優(yōu)化流控思想OFC得到的REM算法作為改進依據(jù)，利用FARIMA模型計算Hurst值H’來表征相似性程度大小，根據(jù)實際狀況適當(dāng)改變擁塞控制機制中的參數(shù)標(biāo)記概率，按以下步驟進行：

（1）利用下式求解REM算法中的參數(shù)Price：pl（t＋1）＝［pl（t）＋γ（al（bl（t）－b＊l）＋xl（t）－cl））］＋，可以看出該計算公式包含參數(shù)al以實現(xiàn)調(diào)節(jié)功能，此外路由器使用狀況以及帶寬占用情況也是需要考慮的因素。

（2）以標(biāo)記概率代表擁塞控制機制的擁塞指示，隊列1的計算公式為是常量。其中t代表一段時間。從而得到端到端報文標(biāo)記概率為引入H’的調(diào)節(jié)作用，將標(biāo)記概率計算公式調(diào)整為為權(quán)重參數(shù)，h0為閾值，通常取0.8～0.9之間。

3.3 算法復(fù)雜度分析

由于小波變換的計算效率很高，對含N個采樣數(shù)據(jù)的信號進行Mallat離散小波變換的時間復(fù)雜度僅為0（N），對分解后的流量分量采用FARIMA過程進行線性預(yù)測時，F(xiàn)ARIMA算法乘法操作次數(shù)為0（N2），因此對網(wǎng)絡(luò)流量進行預(yù)測的時間復(fù)雜度為0（N2）；空間復(fù)雜度上，如果選擇的小波長度為N，那么本算法中進行小波分解和重構(gòu)所需存儲空間大小是0（N），對分解后流量進行預(yù)測時，F(xiàn)ARIMA過程需要存儲p、d、q等中間變量，其中d的大小為N，p、q的大小為N2，因此總的空間復(fù)雜度為0（N2）。

3.4 實驗仿真與結(jié)構(gòu)分析

（1）實驗方案：本文采用MATLAB軟件和C＋＋語言編程實現(xiàn)該模型，以NS為仿真環(huán)境，以Pareto模型產(chǎn)生自相似輸入流量，實驗過程如圖4所示。網(wǎng)絡(luò)協(xié)議選取目前網(wǎng)絡(luò)中應(yīng)用最廣的TCP版本：TCP New Reno，在尺度為J＝3上運行Mallat算法對網(wǎng)絡(luò)流量進行多尺度db4小波分解和重構(gòu)。

圖4 仿真實驗運行過程

（2）流量分析結(jié)論及流量預(yù)測模型效果檢驗：首先我們統(tǒng)計了原始流量與合成流量的自相似特性表征值H，經(jīng)R／S估值，發(fā)現(xiàn)在原始流量的H為0.8319時，合成流量的H’值為0.8298，這表明DWT多尺度變換能近似表征出原始流量的LRD特性。此外，多個不同流量樣本數(shù)據(jù)展現(xiàn)出如下特點；①網(wǎng)絡(luò)流量在1秒級以上的尺度上，表現(xiàn)出明顯的LRD特性；②網(wǎng)絡(luò)流量在多種時間尺度上表現(xiàn)出非平穩(wěn)特性。

圖5是一段TCP流經(jīng)過流量預(yù)測模型處理、重構(gòu)疊加后的流量特征與實際流量的對比，測試顯示模型具有較高的預(yù)測精度。

（3）優(yōu)化后協(xié)議性能仿真結(jié)果

圖5 流量模型的預(yù)測值與實際流量對照

1）在有干擾背景流震蕩的情況下，模擬優(yōu)化后協(xié)議的運行情況。如圖6所示：Flow1為原始流量，F(xiàn)low2是運行模型擬合、經(jīng)協(xié)議優(yōu)化后的流量。結(jié)果表明這種新的擁塞控制機制可以預(yù)測并抑制自相關(guān)流量在大尺度上的固有突發(fā)，能夠在一定程度上有效保證網(wǎng)絡(luò)性能的穩(wěn)定性。

圖6 仿真結(jié)果1

2）圖7是協(xié)議間公平性實驗，TCP1和TCP2是運行優(yōu)化后協(xié)議的兩個共享同一瓶頸鏈路的同等條件流量，60s時刻啟動該鏈路上的一個UDP流。此實驗同時測試TCP流之間的公平性以及TCP流與無擁塞控制機制的UDP流之間的公平性。結(jié)果表明，經(jīng)優(yōu)化后，協(xié)議間公平性特征良好，具有較好的可擴展性。

圖7 仿真結(jié)果2

4 結(jié)束語

就網(wǎng)絡(luò)流量而言，是否可對其進行預(yù)測有賴于自身性質(zhì)。如果對自相似性網(wǎng)絡(luò)進行流量預(yù)測，了解其長相關(guān)性非常重要，況且網(wǎng)絡(luò)流量的尺度特性對于網(wǎng)絡(luò)效率的提高和網(wǎng)絡(luò)協(xié)議的設(shè)計均具有重大的影響，因此本文進行以DWT多尺度分析為基礎(chǔ)的網(wǎng)絡(luò)流量建模和預(yù)測，并在預(yù)測基礎(chǔ)上改變傳統(tǒng)的控制方式，于傳統(tǒng)網(wǎng)絡(luò)協(xié)議的基礎(chǔ)上改進算法進而實現(xiàn)對自相似網(wǎng)絡(luò)的流量預(yù)測，對提高資源利用率、進一步實施流量控制工程、網(wǎng)絡(luò)性能更優(yōu)都具有顯著的研究意義。

［1］Leland WE，Gao L，Zhang X L.A network traffic analysis and forecast based on wavelet technology ［J］.Computer Applications and Software，1992，25 （8）：70－72.

［2］WANG Junsong，GAO Zhiwei.Network traffic modeling and forecasting based on RBF neural network ［J］.Computer Engineering and Application，2011，44 （13）：6－11 （in Chinese）.［王俊松，高志偉.基于RBF神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)流量建模及預(yù)測［J］.計算機工程與應(yīng)用，2011，44 （13）：6－11.］

［3］Bai X Y，Ye X M，Jiang H.Network traffic predicting based on wavelet transform and autoregressive model ［J］.Computer Science，2013，34 （7）：47－49.

［4］Chen X T，Liu J X.Network traffic prediction based on wavelet transformation and FARIIMA ［J］.Journal on Communications，2011，32 （4）：153－157.

［5］YIN Bo，XIA Jingbo，F(xiàn)U Kai，et al.Based on IPSO chaos of support vector machine （SVM）network traffic prediction research ［J］.Computer Application Research，2012，29 （11）：4293－4295（in Chinese）. ［尹波，夏靖波，付凱，等.基于IPSO混沌支持向量機的網(wǎng)絡(luò)流量預(yù)測研究 ［J］.計算機應(yīng)用研究，2012，29 （11）4293－4295.］

［6］Yang X S，Deb S.Engineering optimization by cuckoo search［J］.International Journal of Mathematical Modeling and Numerical Optimization，2012，1 （4）：330－343.

［7］LI Dandan，ZHANG Runtong.Cognitive network in network traffic prediction model based on ant colony algorithm ［J］.Journal of Electronics，2011 （10）：100－103 （in Chinese）.［李丹丹，張閏彤.認知網(wǎng)絡(luò)中基于蟻群算法的網(wǎng)絡(luò)流量預(yù)測模型 ［J］.電子學(xué)報，2011 （10）：100－103.］

［8］BAI Xiangyu，YE Xinming，JIANG Hai.Based on wavelet transform and autoregressive model of network traffic prediction ［J］.Journal of Computer Science，2011，34 （7）：47－49 （in Chinese）.［白翔宇，葉新銘，蔣海.基于小波變換與自回歸模型的網(wǎng)絡(luò)流量預(yù)測 ［J］.計算機科學(xué)，2011，34 （7）：47－49.］

［9］Li Chunfu，Zheng Guangjun，Li Yanqi，et al.Study on control strategy of lockup process of torque converter ［J］.Automobile Technology，2013 （10）：15－17.

［10］MO Yuanbin，LIU Fuyong，ZHANG Yunan.With gauss mutation of artificial fireflies optimization algorithm ［J］.Computer Application Research，2013，30 （1）：121－124 （in Chinese）.［莫愿斌，劉付永，張宇楠.帶高斯變異的人工螢火蟲優(yōu)化算法 ［J］.計算機應(yīng)用研究，2013，30 （1）：121－124.］

［11］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.

［12］WANG Fan，HE Xingshi，WANG Yan.The cuckoo search algorithm based on gauss perturbation ［J］.Journal of Computers，2011，25 （4）：566－569 （in Chinese）.［王凡，賀興時，王燕.基于高斯擾動的布谷鳥搜索算法 ［J］.計算機學(xué)報，2011，25 （4）：566－569.］