基于混沌理論與改進回聲狀態(tài)網絡的網絡流量多步預測

田中大，李樹江，王艷紅，王向東

?

基于混沌理論與改進回聲狀態(tài)網絡的網絡流量多步預測

田中大，李樹江，王艷紅，王向東

（沈陽工業(yè)大學信息科學與工程學院，遼寧沈陽 110870）

網絡流量預測是網絡管理及網絡擁塞控制的重要問題，針對該問題提出一種基于混沌理論與改進回聲狀態(tài)網絡的網絡流量預測方法。首先利用0-1混沌測試法與最大Lyapunov指數法對不同時間尺度下的網絡流量樣本數據進行分析，確定網絡流量在不同時間尺度下都具有混沌特性。將相空間重構技術引入網絡流量預測，通過C-C方法確定延遲時間，G-P算法確定嵌入維數。對網絡流量時間序列進行相空間重構之后，利用一種改進的回聲狀態(tài)網絡進行網絡流量的多步預測。提出一種改進的和聲搜索優(yōu)化算法對回聲狀態(tài)網絡的相關參數進行優(yōu)化以提高預測精度。利用網絡流量的公共數據集以及實際數據進行了仿真，結果表明，提出的預測方法具有更高的預測精度以及更小的預測誤差。

網絡流量；混沌；回聲狀態(tài)網絡；時間尺度；預測

1 引言

隨著網絡技術的發(fā)展，網絡規(guī)模越來越大和復雜化，網絡信息流量劇增，網絡擁塞越來越嚴重，網絡管理的難度日益增加，如何有效地管理和控制網絡，為用戶提高更加優(yōu)質服務顯得十分重要。網絡流量是衡量網絡運行負荷和狀態(tài)的重要參數，通過對網絡流量的監(jiān)測，可以及時了解網絡當前運行狀況，因此如何進行網絡流量的精確預測引起了學者廣泛的關注[1]。

網絡流量是一定采樣時間內通過網絡設備或傳輸介質的信息量(報文數、數據分組數或字節(jié)數)。一般的研究對象都為基于IP協(xié)議的網絡流量。網絡流量預測問題可定義為[2]：給定當前時刻的一組IP網絡流量數據，則未來某一時刻的流量可由給出，這里為預測步長。當時為單步預測，時為多步預測。相對于單步預測而言，多步預測有著更重要的理論與實際意義。

網絡流量是按時間采集的，因此是一種典型的時間序列數據，具有高度非線性、多時間尺度和不確定性等特點。近些年來，諸多學者對網絡流量預測進行研究，提出了許多的預測方法。其中，很多學者將網絡流量看作線性模型，采用自回歸滑動平均(ARMA, auto regressive moving average)模型[3, 4]、差分自回歸滑動平均(ARIMA, auto regressive integrated moving average)模型[5, 6]以及差分自回歸求和滑動平均模型[7,8](FARIMA, fractional auto regressive integrated moving average)等線性模型進行預測。但是隨著網絡復雜度的增加，網絡流量特性已經超出傳統(tǒng)意義上認為的泊松或者馬爾可夫分布模型，而這些傳統(tǒng)時間序列分析方法均屬于線性模型，適合于季節(jié)性、周期性等特征平穩(wěn)的時間序列預測。對于具有非平穩(wěn)、非線性特征的網絡流量時間序列，由于它們不能全面反映網絡流量序列的復雜變化特征，預測準確率比較低，使預測的精確性無法提高。而非線性預測模型主要包括支持向量機[9,10]（SVM, support vector machine）、最小二乘支持向量機[11,12]（LSSVM, least squares support vector machine）、人工神經網絡（RBF神經網絡[13]、ELM神經網絡[14]以及Elman神經網絡[15]等）、卡爾曼濾波模型[16](KFM, Kalman filtering mode)、灰色模型[17]等。雖然非線性模型的預測精度較線性模型有了一定程度的提高，但是也存在著各自的缺陷。SVM與LSSVM雖然需要樣本數少，但是其關鍵參數很難確定，預測精度受核參數影響很大；神經網絡雖然可以任意精度逼近非線性函數，但是其存在易陷于局部最優(yōu)值、網絡結構難以確定的缺點；卡爾曼濾波模型誤差難以量化，而網絡流量具有隨機性和突發(fā)性，使KFM模型運算量大，參數設置復雜，實際應用性較差；灰色模型只適合網絡流量數據變化不是劇烈的情況下。因此網絡流量的非線性預測模型也都存在著各自的局限性。很多學者也提出了一些混合預測模型[18~20]，即將2種以上的預測模型通過某些算法進行結合，達到提高預測精度的目的。

雖然學者們在網絡流量預測問題上進行了大量的研究，但是目前的研究大多未考慮網絡流量時間序列具有的混沌特性，而實際網絡是一個時變的、開放的復雜巨系統(tǒng)，因此網絡流量具有高度的非線性和不確定性。理論上更精確的預測方法是用符合網絡流量特性的非線性動力學理論進行建模并預測，以提高預測精度和可信度。對于確定性混沌系統(tǒng)，采用基于混沌的相關理論進行預測，就能獲得較高的預測精度。但是目前考慮到混沌特性的相關研究只針對單一時間尺度的網絡流量進行預測[21,22]。因而確定不同時間尺度下網絡流量序列是否具有混沌特性，是應用混沌理論進行網絡流量預測的前提?；谝陨峡紤]，首先對不同時間尺度的網絡流量時間序列進行混沌特性分析，通過0-1混沌測試法與最大Lyapunov指數法確定網絡流量時間序列具有混沌特性。針對網絡流量時間序列的混沌特性結合相空間重構技術展開預測，利用C-C方法確定序列延遲時間，通過G-P算法確定序列嵌入維數。

在預測模型的選擇上，利用Jaeger等[23]于2001年提出的一種新型的遞歸神經網絡—回聲狀態(tài)網絡(ESN, echo state network)。ESN核心部分是一個大規(guī)模儲備池，網絡的輸入權值和儲備池內部連接權值隨機生成，并在訓練中保持不變，只有輸出權值需要通過線性回歸方法求解，學習算法簡單快速，彌補了一般神經網絡收斂速度慢的缺點。為了克服不同的儲備池參數以及輸入數據噪聲對于ESN預測效果的影響，提出對ESN輸入端加入補償信號與比例系數，同時利用改進的和聲搜索算法完成ESN最佳預測參數的確定。

綜上所述，本文提出一種基于混沌理論與回聲狀態(tài)網絡的網絡流量多步預測方法，首先確定網絡流量時間序列具有混沌特性，對原始網絡流量進行相空間重構處理，然后通過改進的和聲搜索算法優(yōu)化預測模型的相關參數，利用優(yōu)化后的參數進行網絡流量的多步預測。通過仿真實驗表明提出的方法具有更高的預測精度與更小的預測誤差。

2 網絡流量數據來源及其分形特征

網絡流量數據分組包括公共數據集與實際數據2部分。網絡流量時間尺度的劃分基本上分為小時間尺度與大時間尺度。一般認為小時間尺度為采樣時間小于1 s。因此本文也認為采樣間隔在1 s以內的為小時間尺度，大于1 s間隔的為大時間尺度。

小時間尺度網絡流量數據集來自于http://ita.ee. lbl.gov/html/contrib/BC.html中的BC-pAug89數據集，其采集了3 142.82 s內的包括局域網、廣域網等網絡的單向流量，按照10 ms、100 ms、1 s的采樣間隔，將數據集分成T_10 ms、T_100 ms、T_1s這3個數據集，為了對比研究方便，數據集長度均取為1 000。大尺度網絡流量數據為ftp://ita.ee. lbl.gov/traces/BC-Oct89Ext4.TL.Z中的BC-Oct89Ext4數據集，共采集了307 h的共106組網絡流量數據。對其按照10 s、1 min、10 min、30 min、1 h的間隔采樣，生成T_10s、T_1min、T_10min、T_30min、T_1hour 5個數據集，這里前6個數據集的長度都取為1 000，后2個數據集長度取為300。8個數據集數據傳輸層均采用TCP協(xié)議，數據集的單位為byte。由此得到的8個數據集如圖1所示。

實際網絡流量數據來源于中國聯(lián)合網絡通信公司遼寧分公司3G網絡一核心路由器流入的網絡流量數據，數據采集尺度為10 min，傳輸層協(xié)議為TCP協(xié)議，共采集300組數據，單位為MB。圖2為300組實際網絡流量數據。

在給出網絡流量數據來源后，這里將對網絡流量數據進行分形特征的討論。分形理論由美國科學家Benoit于20世紀70年代中期創(chuàng)立，分形理論用于研究復雜系統(tǒng)的自相似性。重標度極差分析(R/S, rescaled range analysis)是以分形理論為基礎的時間序列研究方法，該方法特別適用于分析具有長相關特性的非線性時間序列，而且對所研究對象可不做任何假設，屬非參數分析法，具有較好的穩(wěn)健性[24]。1951年，英國學者Hurst在研究尼羅河水流量時，提出了R/S分析方法建立Hurst指數，作為判斷時間序列數據是否是隨機游走還是有偏隨機游走的指標。隨后分形學說創(chuàng)始人Mandelbort在理論上證實了該方法的正確性，并加以完善與補充[25]。其方法可描述為

圖1 不同時間尺度下的網絡流量序列

表1 不同時間尺度網絡流量的Hurst指數

從表1中可觀察到，不同時間尺度下的網絡流量時間序列具有分形特征，且Hurst 指數值均大于0.5，表明不同時間尺度下的網絡流量時間序列數據服從分形布朗運動，且時間序列具有長期的正相關特征，所測定的時間周期內表現(xiàn)的特征將得到延續(xù)，即趨勢具有可持續(xù)性，這也說明了網絡流量時間序列的可預測性。

3 網絡流量時間序列混沌特性與相空間重構

混沌現(xiàn)象是非線性動力系統(tǒng)中常見的現(xiàn)象。混沌系統(tǒng)是一個確定系統(tǒng)，它對系統(tǒng)初值具有較強的敏感性。對于混沌系統(tǒng)的預測而言，由于其存在初值敏感性，因此不能長期預測，但是同時由于其確定性，混沌系統(tǒng)具有短期預測能力。對于網絡流量時間序列的預測問題，首先需要確定其是否具有混沌特性，只有進行不同時間尺度下網絡流量時間序列的混沌特性判定，才能確定不同時間尺度下網絡流量時間序列的可預測性。

網絡流量時間序列的混沌特性判定可通過0-1混沌測試方法[26]與最大Lyapunov指數[27]2種方法。受限于篇幅，算法具體計算過程可參見相關文獻。

3.1 0-1混沌測試法

從圖3~圖5可看出，10 ms時間尺度網絡流量時間序列的與的相圖呈現(xiàn)布朗特性，而均方位移隨時間線性增長，同時計算可得到漸進增長率K為0.998 3，接近于1，因此10 ms時間尺度網絡流量序列具有混沌特性。同理，對其余8個不同時間尺度的網絡流量時間序列計算其漸進增長率，結果如表2所示，從中可看出不同時間尺度下的都趨近于1，0-1混沌測試法表明網絡流量時間序列在不同時間尺度下都具有混沌特性。

表2 不同時間尺度網絡流量的漸進增長率

3.2 相空間重構

相空間重構是混沌時間序列預測的基礎，相空間重構用原始系統(tǒng)中某個變量的延遲坐標來重構相空間，Takens從數學上為其奠定了可靠的基礎。他的基本觀點是：相空間重構法雖然是用一個變量在不同時刻的值構成相空間，但動力系統(tǒng)的一個變量的變化自然跟此變量與系統(tǒng)的其他變量的相互作用有關，即此變量隨時間的變化隱含著整個系統(tǒng)的動力學規(guī)律。因此，重構的相空間的軌跡也反映系統(tǒng)狀態(tài)的演化規(guī)律。

受限于篇幅，這里僅對10 ms時間尺度網絡流量時間序列進行詳細分析。利用C-C算法得到10 ms網絡流量時間序列的變化曲線如圖6所示。從圖中可看出的第一個局部最小值發(fā)生在，因此確定10 ms時間尺度網絡流量時間序列的時延為2。按照G-P算法得到圖7所示的隨著的增大，的變化曲線，圖8的與關聯(lián)維數的曲線。從圖7與圖8可知，隨著嵌入維數的增加，線性區(qū)域內出現(xiàn)了趨于飽和的現(xiàn)象，繼續(xù)增加嵌入維數幾乎不影響關聯(lián)積分的值。從圖8中可看出關聯(lián)維數的收斂值為4.5左右，依據原則，確定10 ms時間尺度網絡流量時間序列的嵌入維數為10。

對于一個混沌時間序列，如果延遲時間取值不合理，混沌吸引子的相軌線被壓縮或被折疊，空間點對的距離分布不均勻。而從圖9與圖10的相圖可看出在為2時，空間點對點間的距離趨于均勻分布，吸引子所包含信息量較大，二維與三維相圖表明其對吸引子有序結構的展開相對較為充分，因此確定延遲時間為2較為合理。

將10 ms時間尺度網絡流量時間序列按照得到的嵌入維數與延遲時間進行相空間重構，計算其遞歸圖（RP, recurrence plot），結果如圖11所示。

圖11表明，10 ms時間尺度網絡流量時間序列不同于隨機信號，其遞歸圖并非均勻分布于整個遞歸平面，而且存在與主對角線平行的直線段，因此10 ms尺度網絡流量序列為典型的混沌時間序列，在局部范圍內具有可預測性。同理，可計算其他時間尺度網絡流量時間序列對應的相空間參數，結果如表3所示。

表3 不同時間尺度網絡流量時間序列相空間參數

3.3 最大Lyapunov指數

Lyapunov指數描述了系統(tǒng)軌道演化過程的特性，度量了系統(tǒng)對于初始條件依賴的敏感性，通過其各指數符號組合能很好判斷出系統(tǒng)的最終演化是否會出現(xiàn)混沌現(xiàn)象，Lyapunov指數中，最大的指數非常重要，如果網絡流量系統(tǒng)是混沌的，則至少有一個正的Lyapunov指數。利用wolf方法計算了9個數據集的最大Lyapunov指數，結果如表4所示。從表4中可發(fā)現(xiàn)9個數據集的最大Lyapunov指數都大于0，因此同樣可表明網絡流量時間序列同樣具有混沌特性。

表4 不同時間尺度網絡流量的最大Lyapunov指數

通過0-1混沌測試法與最大Lyapunov指數方法可知網絡流量時間序列具有混沌特性，同時利用混沌理論中的相空間技術得到各個時間尺度網絡流量序列的重構參數后，將利用下節(jié)的回聲狀態(tài)網絡進行網絡流量的預測。

4 回聲狀態(tài)網絡

回聲狀態(tài)網絡將網絡隱層設計成一個具有很多神經元組成的稀疏網絡，通過調整網絡內部權值的特性達到記憶數據的功能。其內部的動態(tài)儲備池(DR, dynamic reservoir)包含了大量稀疏連接的神經元，蘊含系統(tǒng)的運行狀態(tài)，并具有短期記憶功能,而非線性系統(tǒng)的動態(tài)特性即由DR產生?；芈暊顟B(tài)網絡一經提出便成為學術界的研究熱點，并應用到各種不同領域，尤其是時間序列的預測問題[33~35]。圖12為ESN網絡結構[36]。

4.1 ESN學習算法

設系統(tǒng)具有個輸入單元，個內部處理單元，同時具有個輸出單元，輸入單元、內部狀態(tài)、輸出單元在時刻的值分別為

與傳統(tǒng)神經網絡相比，ESN的隱層是由較多神經元構成的循環(huán)網絡所形成的動態(tài)儲備池。為使DR內部具有動態(tài)記憶能力，權值通常保持連接度5%至10%，譜半徑小于1。

(4)

4.2 權值計算

也就是希望計算權值矩陣滿足系統(tǒng)均方誤差最小，即求解如下目標

(6)

可歸結為如下形式

4.3 基于相空間重構與ESN的網絡流量多步預測

本文使用迭代法實現(xiàn)基于相空間重構與ESN的網絡流量多步預測，即ESN輸出層為1，通過反復迭代完成多步預測，其實現(xiàn)步驟可表示為如下。

step1 采集網絡流量數據，假設目前采集得到的網絡流量時間序列為，利用C-C方法計算延遲時間，利用G-P算法計算嵌入維數，生成相空間重構參數。

step2 對ESN模型參數賦值。生成輸入輸出集合，對ESN進行訓練，生成對應權值矩陣。

5 改進的ESN及儲備池參數優(yōu)化

5.1 儲備池參數優(yōu)化

ESN的性能由儲備池的4個參數決定的，簡要介紹儲備池的4個參數[37]。

1) 儲備池內部連接權譜半徑。為連接權矩陣的絕對值最大的特征值，記為，是保證網絡穩(wěn)定的必要條件。合理的才能確保ESN具有的回聲狀態(tài)屬性，使網絡狀態(tài)與輸入在足夠長的時間后，對網絡的影響消失。

2) 儲備池規(guī)模。為儲備池中神經元的個數，儲備池的規(guī)模選擇與樣本個數有關，對網絡性能影響很大，儲備池越大ESN對給定動態(tài)系統(tǒng)的描述越準確，但是過大會帶來過擬合問題，導致模型對測試數據的泛化能力下降，目前一般的方法是逐漸增大，直到測試數據的性能指標變壞為止。

3) 儲備池輸入單元尺度。為儲備池的輸入信號連接到儲備池內部神經元之前需要相乘的一個尺度因子，即對輸入信號進行一定的縮放。Jaeger在其文獻[23]中給出了選擇原則，即需要處理的對象非線性越強，越大。其本質是通過，將輸入數據轉換到神經元激活函數所能適應的范圍。

4) 儲備池稀疏程度。表示儲備池中神經元之間的連接情況，儲備池中并不是所有神經元之間都存在連接的。表示儲備池中相互連接的神經元占總的神經元（）的百分比?？梢院饬績涑厮蛄康呢S富程度，向量的豐富程度影響網絡的非線性逼近能力，因此越大意味著網絡非線性逼近能力越強。

儲備池的參數對于ESN網絡流量預測模型的預測精度有著重要的影響，為了說明這些參數對預測精度的影響，以10 ms時間尺度網絡流量序列為例，利用前400組數據作為輸入，401到500組作為輸出進行了測試。圖13給出了嵌入維數，輸入單元尺度，儲備池稀疏程度，譜半徑變化范圍為[0.1,1)，變化步長為0.05，儲備池規(guī)模變化范圍為[10,150)，變化步長為1，100組網絡流量預測值與實際值之間均方根誤差（RMSE）的分布。

從圖13與圖14可以看出儲備池參數對于預測精度會造成不同的影響，因此如何根據網絡流量訓練集選擇合適的模型參數是一個重要的問題，直接影響最后ESN預測的精度。為了得到最優(yōu)的儲備池參數，提出一種改進的和聲搜索算法（IHS）進行儲備池參數的尋優(yōu)。

和聲搜索（HS, harmony search）算法是2001年源于樂曲創(chuàng)作過程的模仿而出現(xiàn)的群智能優(yōu)化算法[38]，算法利用所有個體的合作而產生新個體，具有不依賴初始條件，結構簡單、實現(xiàn)容易、收斂速度快等特點[39]，相關文獻[40, 41]表明和聲搜索算法的優(yōu)化性能要強于遺傳、模擬退火、粒子群等優(yōu)化算法。

如下為標準HS算法實現(xiàn)步驟。給定優(yōu)化問題

step1 HS算法首先初始化如下參數：和聲記憶庫大小（HMS, harmony memory size）、學習與記憶庫概率（HMCR, harmony memory consideration rate）、微調概率（PAR, pitch adjusting rate）、音調微調帶寬（BW, band width）、迭代次數（NI, number of iteration）。

step2 隨機創(chuàng)建和聲記憶庫如下

(9)

(10)

step5 重復步驟step3和step4，直到迭代次數達到。

雖然和聲搜索算法具有較好的全局尋優(yōu)能力，但是其算法存在隨機性大，穩(wěn)定性不高，同時搜索沒有方向性，因此在此作一定的改進。由基本和聲搜索算法描述可知，HMCR有助于算法找到全局改進解和局部改進解，而PAR和BW在和聲微調中是非常重要的2個參數，優(yōu)化前期階段保持較小的PAR值與較大的BW值有利于增強解向量的多樣性，從而能快速找到局部最優(yōu)解。而在優(yōu)化的后期，較小的BW與較大的PAR值有利于算法快速找到全局最優(yōu)解。標準的和聲搜索算法采用了固定的參數值，不能同時兼顧局部最優(yōu)解和全局最優(yōu)解的要求。同時算法的搜索速度與收斂精度也和算法參數是相關的，為提高算法搜索效率，克服標準和聲搜索算法的缺點，作如下的改進。

對于參數HMCR應由大到小動態(tài)調節(jié)，這樣可使HM算法先對和聲記憶庫內充分搜索，迭代搜索后期轉到和聲記憶庫外部搜索，可提高種群的多樣性，調節(jié)方法如下。

在HS算法的初期，PAR取值小有利于算法快速的搜索更好的區(qū)域，在HS算法的后期，較大的PAR則利于算法跳出局部最優(yōu)值，因此PAR應該是從小到大變化的，改進的PAR變化策略如下

(12)

對于BW，在算法初期較大的BW有利于HS算法在較大的范圍內搜索，而算法搜索后期，較小的BW則有利于小范圍內的精確搜索，因此BW應該由大變小的，改進的BW的變化策略如下。

(14)

為了驗證改進HS算法（IHS, improved harmony search）的性能，選用式（15）的Rosenbrock函數進行測試。

為了消除隨機性的影響，所有算法都運行20次，取平均值作為尋優(yōu)結果，圖15為某一次測試3種算法的適應度收斂曲線，為了顯示方便，橫坐標為每迭代50次記錄一次適應度值，縱坐標為適應度取10的對數值，從圖中可看出本文改進的HS算法較標準HS算法以及EHS算法收斂速度更快，同時具有更好的適應度值。表5給出了3種算法的最佳適應度值，平均適應度值，適應度均值的對比，最佳適應度值與平均適應度值反映了算法的收斂性，適應度均值反映了算法的頑健性，成功率反映了算法全局尋優(yōu)能力。從表中可看出本文方法的最佳適應度、適應度均值等指標都優(yōu)于其他2種算法。

表5 算法仿真結果

5.2 改進的ESN

雖然利用上節(jié)的IHS算法可以對ESN的儲備池參數進行優(yōu)化，但是ESN的性能與網絡輸入數據也是相關的，尤其輸入數據中的噪聲對于預測性能有著一定的影響。為了消除輸入數據中的噪聲信號，可在輸入端加入一個補償信號，則式（3）轉變?yōu)?/p>

(17)

相較于標準ESN，改進的ESN由于引入輸入的補償而增加了3個參數、與，為了統(tǒng)一處理，這里可以同樣采用上節(jié)的IHS算法進行優(yōu)化。

這里對改進的ESN進行算法穩(wěn)定性分析。文獻[43]指出只有網絡具有回聲狀態(tài)屬性時，對網絡的訓練才是有意義的，因此網絡的訓練算法應該保證網絡具有回聲狀態(tài)屬性。通過對隨機產生的內部連接權矩陣進行整體的運算保證儲備池的回聲狀態(tài)屬性，即保證網絡的穩(wěn)定性。實際應用中在穩(wěn)定性方面，它可以通過預先設定動態(tài)記憶庫矩陣的譜半徑來保證遞歸網絡的穩(wěn)定性,當矩陣的譜半徑小于1（）時，回聲狀態(tài)網絡是漸進穩(wěn)定的，由于本文并未改進標準ESN權值矩陣的產生過程，因此改進的ESN也是漸進穩(wěn)定的。

綜上，基于改進的ESN與儲備池參數優(yōu)化的預測過程可描述如下。

1) 建模過程

step1 采集網絡流量數據，生成建模數據集。

step2 根據網絡流量訓練樣本序列，通過C-C算法與G-P算法確定相空間重構參數。

step3 設置IHS算法參數，設定待優(yōu)化參數為儲備池參數、、、以及、與取值范圍。

step4 網絡流量樣本數據歸一化處理，利用相應樣本參數訓練ESN，將網絡流量預測值與網絡流量實際值的RMSE作為適應度函數，即

利用IHS算法結合適應度函數反復迭代進行參數的優(yōu)化，直到滿足結束條件，輸出最佳參數。

2) 在線預測過程

step2 按照式（6）、式（7）進行網絡訓練，計算輸出權矩陣，通過式（17）、式（18）預測未來時刻的網絡流量預測值。

6 仿真對比

為了說明本文方法的有效性，利用10 ms時間尺度網絡流量時間序列與實際采集的遼寧聯(lián)通網絡流量時間序列進行仿真研究。其中10 ms時間尺度網絡流量序列前400組數據作為訓練樣本，401到500組作為測試樣本。遼寧聯(lián)通網絡流量樣本數據前250組作為訓練樣本，后50組作為測試樣本。儲備池參數的變化范圍為，，，。由于網絡流量數據都進行了歸一化處理，因此改進ESN的3個參數取值范圍為，，。按照上文步驟利用IHS算法進行參數優(yōu)化，優(yōu)化結果如表6所示。

表6 參數優(yōu)化結果

預測精度是指預測模型對實際數據擬合的好壞程度，即預測模型所產生的預測值與實際值擬合程度的優(yōu)劣。除了通過預測曲線擬合程度之外，預測效果的評價指標還包括MAE（平均絕對誤差）、MAPE（平均絕對百分誤差）、RMSE（均方根誤差）、ME（絕對誤差）、MRE（平均相對誤差）等。MAE、MAPE以及RMSE對較大的預測誤差不存在正負抵消的問題，易于計算，對于預測系統(tǒng)的整體性能評價十分重要，而ME與MRE等評價指標由于將正誤差與負誤差正負抵消，會導致對預測效果的錯誤判斷，因此選擇MAE、MAPE與RMSE作為評價指標。RMSE定義如式（19），MAE與MAPE的定義分別如式（20）與式（21）。

(21)

6.1 T_10ms數據集仿真對比

作為對比，與文獻[3]中的ARMA模型（預測模型參數為=3,=1），文獻[4]中的ARIMA模型（預測模型參數為=4,=3,=1），文獻[12]中的組合核函數LSSVM模型（預測模型參數為=32，=0.92，=101.36，=6.21，=3.25），文獻[15]中的Elman神經網絡(預測模型參數為輸入層為300，中間層為50，輸出層為100，最大迭代次數為5 000)進行了仿真對比。圖16為本文預測方法與其他幾種方法的網絡流量預測值與實際值對比曲線，圖17為幾種方法的預測誤差分布對比。從圖16與圖17可知提出的預測方法具有更好的預測效果與預測精度，預測誤差更小，預測值與實際值擬合更好。

表7為本文方法與其他幾種方法的T_10ms數據集預測評價指標的對比。

表7 T_10ms數據集預測指標對比

從10 ms時間尺度的網絡流量預測仿真結果中可看出，本文的網絡流量預測方法在數據擬合程度以及預測誤差上都優(yōu)于當前主要的預測方法。對于其他時間尺度的7組網絡流量也進行了仿真驗證，預測效果與精度同樣優(yōu)于其他的方法，限于篇幅原因，這里不給出具體仿真結果。

對于時間序列預測問題，預測時間也是一個重要的指標。預測時間包括離線建模時間與在線預測時間。表8為本機（CPU為Intel i3-4030, 4 GB內存，Windows 7操作系統(tǒng)，仿真軟件Matlab R2010b）環(huán)境下的建模與100步在線預測所需時間。從表8中可看出，由于本文需要利用IHS算法對ESN的參數進行優(yōu)化建模，因此需要的時間要長于ARMA、ARIMA以及Elman神經網絡，與多核LSSVM比較接近。這些模型在線預測時間相差不大，各個模型的單步預測時間都小于采樣周期10 ms，說明這些預測方法都可以滿足T_10ms數據集，而對于更大時間尺度的100 ms甚至秒級之上的網絡流量而言，在線預測時間遠小于其時間尺度，因此在線預測時間可滿足實際的應用。

表8 不同模型離線建模與在線預測時間對比

6.2 聯(lián)通網絡流量數據集仿真對比

對比模型依然選擇上節(jié)的幾種預測方法，ARMA模型參數為=7,=6；ARIMA模型參數為=9，=8,=1；組合核函數LSSVM模型參數同文獻[12]；Elman神經網絡參數為輸入層為150，中間層為80，輸出層為50，最大迭代次數為5 000。圖18為本文預測方法與其他幾種方法的網絡流量預測值與實際值對比曲線，圖19為幾種方法的預測誤差分布對比，表9為幾種方法的聯(lián)通網絡流量數據集預測評價指標的對比。

從圖18、圖19以及表9可知提出的預測方法對于實際采集的網絡流量數據同樣具有更好的預測效果。

表9 聯(lián)通網絡流量數據集預測指標對比

基于以上仿真結果，預測效果提高的主要原因在于通過0-1混沌測試法與最大Lyapunov指數法確定網絡流量具有混沌特性，將相空間重構技術引入網絡流量預測，同時對ESN進行一定的改進，并結合IHS算法進行儲備池參數的聯(lián)合優(yōu)化，因此提高了網絡流量的預測精度。

7 結束語

針對網絡流量的預測問題而提出一種基于混沌理論與回聲狀態(tài)網絡的網絡流量多步預測方法。首先將網絡流量樣本按照不同時間尺度進行分類，通過0-1混沌測試法與最大Lyapunov指數法對不同時間尺度網絡流量進行分析，確定網絡流量具有混沌特性。在此基礎上，利用相空間重構技術，確定重構參數，然后通過改進的回聲狀態(tài)網絡對網絡流量進行多步預測。同時，利用改進的和聲搜索算法對回聲狀態(tài)網絡預測模型相關的參數進行優(yōu)化。通過仿真對比表明所提出的預測方法具有更高的預測精度以及更小的預測誤差。

[1] QU H, MA W T, ZHAO J H. Prediction method for network traffic based on maximum correntropy criterion[J]. China Communications, 2013(1):134-145.

[2] 王升輝, 裘正定. 結合多重分形的網絡流量非線性預測[J]. 通信學報，2007, 28(2):45-50.

WANG S H, QIU Z D. Network traffic nonlinear prediction combined with mutifractal[J]. Journal on Communications，2007, 28(2): 45-50.

[3] LANER M, SVOBODA P, RUPP M. Parsimonious fitting of long-range dependent network traffic using ARMA models[J]. IEEE Communications Letters，2013，17(12): 2368-2371.

[4] ZHOU D D, CHEN S L, DONG S. Network traffic prediction based on ARIMA model[J]. International Journal of Computer Science Issues, 2012,6(9):106-111.

[5] WANG J. A process level network traffic prediction algorithm based on ARIMA model in smart substation[C]// 2013 IEEE Int Conf on Signal Processing, Communications and Computing. Washington, DC. c2013: 1-5.

[6] 袁小坊，陳楠楠，王東，等. 城域網應用層流量預測模型[J]. 計算機研究與發(fā)展, 2009, 46(3): 434-442.

YUAN X F, CHEN N N, WANG D，et al. Traffic prediction models of traffics at application layer in metro area network[J]. Journal of Computer Research and Development, 2009, 46(3):434-442.

[7] REN X Y，YANG Y，ZHANG J F, et al. Parameter estimation and application of time-varying FARIMA model[J]. International Journal of Advancements in Computing Technology, 2011, 3(3):89-94.

[8] 陳曉天, 劉靜嫻. 改進的基于小波變換和FARIMA 模型的網絡流量預測算法[J]. 通信學報, 2011, 32(4): 153-157.

CHEN X T, LIU J X. Network traffic prediction based on wavelet transformation and FARIMA[J].Journal on Communications,2011, 2011, 32(4): 153-157.

[9] 孟慶芳, 陳月輝, 馮志全. 基于局域相關向量機回歸模型的小尺度網絡流量的非線性預測[J]. 物理學報，2013,62(15):150509.

MENG Q F, CHEN Y H, FENG Z Q, et al. Nonlinear prediction of small scale network traffic based on local relevance vector machine regression model[J]. Acta Phys Sin, 2013, 62(15):150509.

[10] LIU X W, LI H, CHEN L. An improved forecasting algorithm for wireless network traffic[J]. IEICE Electronics Express, 2011, 8(12):916-922.

[11] 唐舟進, 彭濤, 王文博.一種基于相關分析的局域最小二乘支持向量機小尺度網絡流量預測算法[J]. 物理學報，2014,63(13):130504.

TANG Z J, PENG T, WANG W B. A local least square support vector machine prediction algorithm of small scale network traffic based on correlation analysis[J]. Acta Phys Sin, 2014,63(13):130504.

[12] 田中大，高憲文，石彤. 用于混沌時間序列預測的組合核函數最小二乘支持向量機[J]. 物理學報，2014,63(16)：160508.

TIAN Z D, GAO X W, SHI T. Combination kernel function least squares support vector machine for chaotic time series prediction[J]. Acta Phys Sin, 2014, 63(16)：160508.

[13] Li X B. RBF neural network optimized by particle swarm optimization for forecasting urban traffic flow[C]// 3rd International Symposium on Intelligent Information Technology Application. c2009: 124-127.

[14] QIAN F. A extreme learning machines approach for accurate estimation of large-scale IP network traffic matrix[J]. Journal of Computational Information Systems, 2012, 8(2):755-762.

[15] WANG J S, WANG J K, ZHANG M Z. Prediction of internet traffic based on Elman neural network[C]// Chinese Control and Decision Conference. c2009: 1248-1252.

[16] 趙艷平，姜子運. 基于EKF的神經網絡在網絡流量預測中的應用[J]. 蘭州交通大學學報，2009, 28(6)：23-25.

ZHAO Y P, JIANG Z Y. Network traffic prediction based on EKF neural network[J]. Journal of Lanzhou Jiaotong University, 2009, 28(6)：23-25.

[17] CAO J H, LIU Y, DAI Y. Network traffic prediction based on error advanced DGM(1,1) model[C]// International Conference on Wireless Communication Networking and Mobile Computing. c2007:6353-6356.

[18] PENG Y, LEI M, LI J B, et al.A novel hybridization of echo state networks and multiplicative seasonal ARIMA model for mobile communication traffic series forecasting[J]. Neural Computing and Applications, 2012: 1-8.

[19] WANG P, ZHANG S Y, CHEN X J. VoIP traffic capacity estimation of hybrid network based on finite user timely refuse model[C]// 5th International Conference on Wireless Communications, Networking and Mobile Computing. c2009:1-4.

[20] CHANG B R, TSAI H F. Improving network traffic analysis by foreseeing data-packet-flow with hybrid fuzzy-based model prediction[J]. Expert Systems with Applications, 2009, 36(2): 6960-6965.

[21] 溫祥西，孟相如，馬志強，等.小時間尺度網絡流量混沌性分析及趨勢預測[J]. 電子學報,2012, 40(8): 1609-1616.

WEN X X, MENG X R, MA Z Q , et al. The chaotic analysis and trend prediction on small-time scale network traffic[J]. Acta Electronic Sinica, 2012, 40(8): 1609-1616.

[22] LIU X W, FANG X M，QIN Z H，et al. A short-term forecasting algorithm for network traffic based on chaos theory and SVM[J]. Journal of Network and Systems Management, 2011, 19(4): 427-447.

[23] JAEGER H, HAAS H. Harnessing nonlinearity: predicting chaotic systems and saving energy in wireless communication[J]. Science, 2004, 304(5667): 78-80.

[24] XUE Y, JIA L S, TENG W Z, et al. Long-range correlations in vehicular traffic flow studied in the framework of Kerner's three-phase theory based on rescaled range analysis[J]. Communications in Nonlinear Science and Numerical Simulation, 2015, 22(1-3): 285-296.

[25] MANDELBORT B B. How long is the coast of Britain statistical self-similarity and fractional dimension[J]. Science, 1967, 1556(3775):636-678.

[26] GOTTALD G A, MELBOURNE I. On the implementation of 0-1 test for chaos[J]. SIAM Journal on Applied Dynamical Systems, 2009, 8(1):129-145.

[27] WOLF A, SWIFT J B, SWINNEY H L, et al. Determining Lyapunov exponents from a time series[J]. Physica D, 1985, 16:285-317.

[28] 李新杰, 胡鐵松, 等. 0-1測試方法的徑流時間序列混沌特性應用[J]. 水科學進展，2012, 32(6): 875-882.

LI X J, HU T S, et al. Application of the 0-1 test algorithm for chaos to runoff time series[J]. Advances in Water Science, 2012, 32(6): 875-882.

[29] KHATIBI R，SIVAKUMAR B，GHORBANI M A，et al . Investigating chaos in river stage and discharge time series[J].Journal of Hydrology，2012（414-415）：108-117.

[30] KIM H S, EYKHOLT R, SALAS J D. Nonlinear dynamics delay times, and embedding windows [J]. Physica D, 1999, 127(1): 48-60.

[31] 張洪賓,孫小端,賀玉龍.短時交通流復雜動力學特性分析及預測[J]. 物理學報，2014,63(4):040505.

ZHANG H B, SUN X D, HE Y L. Analysis and prediction of complex dynamical characteristics of short-term traffc flow[J]. Acta Phys. Sin, 2014,63(4): 040505.

[32] GRASSBERGER P, PROCACCIA I. Measuring the strangeness of strange attractors[J]. Physics D, 1983, 9:189-208

[33] ONGENAE F, VAN L S, VERSTRAETEN D, et al. Time series classification for the prediction of dialysis in critically ill patients using echo state networks[J]. Engineering Applications of Artificial Intelligence, 2013,26(3):984- 996.

[34] SHENG C Y, ZHAO J, LIU Y，et al. Prediction for noisy nonlinear time series by echo state network based on dual estimation[J]. Neurocomputing,2012(82):186-195.

[35] LI D C，HAN M，WANG J. Chaotic time series prediction based on a novel robust echo state network[J]. IEEE Trans on Neural Networks and Learning Systems，2012,23（5）：787-797.

[36] OZTURK M C, XU D M, PRINCIPE J C. Analysis and design of echo state networks[J]. Neural Computation, 2007, 19(1): 111-138.

[37] 彭宇，王建民，彭喜元. 基于回聲狀態(tài)網絡的時間序列預測方法研究[J]. 電子學報, 2010, 38(z1):148-154.

PENG Y, WANG J M, PENG X Y. Researches on time series prediction with echo state networks[J]. Acta Electronic Sinica, 2010, 38(z1):148-154.

[38] GEEM Z W, KIM J H, LOGANATHAN G V. A new heuristic optimization algorithm: harmony search [J]．Simulations, 2001, 76(2): 60-68．

[39] 歐陽海濱，高立群，鄒德旋, 等. 和聲搜索算法探索能力研究及其修正[J]. 控制理論與應用，2014, 31(1)：57-65.

OUYANG H B, GAO L Q, ZOU D X, et al. Exploration ability study of harmony search algorithm and its modification[J]. Control Theory and Applications, 2014, 31(1)：57-65.

[40] MAHDAVI M, FESANGHARY M，DAMANGIR E. An improved harmony search algorithm for solving optimization problems[J]．Applied Mathematics and Computation, 2007, 188(2): 1567-1579．

[41] ALATAS B. Chaotic harmony search algorithms [J]. Applied Mathematics and Computation, 2010, 216(9): 2687-2699.

[42] DAS S, MUKHOPADHYAY A, ROY A, et al. Exploratory power of the harmony search algorithm: analysis and improvements for global numerical optimization [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2011, 41(1): 89-106.

[43] 彭宇，王建民，彭喜元.儲備池計算概述[J]. 電子學報, 2011, 39(10):2387-2396.

PENG Y, WANG J M, PENG X Y. Survey on reservoir computing[J]. Acta Electronic Sinica, 2011, 39(10): 2387- 2396.

Network traffic multi-step prediction based on chaos theory and improved echo state network

TIAN Zhong-da, LI Shu-jiang, WANG Yan-hong, WANG Xiang-dong

(College of Information Science and Engineering, Shenyang University of Technology, Shenyang 110870, China)

Network traffic prediction was an important problem of network management and network congestion control. In order to solve this problem, a network traffic prediction method based on chaos theory and improved echo state network was proposed. Firstly, network traffic sample with different time scale were analyzed by 0-1 test algorithm for chaos and maximum Lyapunov exponent, the calculation results show that the network traffic has chaotic characteristics in different time scale. The phase space reconstruction technique was introduced for the prediction of network traffic, the delay time was determined through the C-C method, the embedding dimension was determined through the G-P algorithm. Network traffic time series was processed with phase space reconstruction, the multi-step prediction of network traffic was achieved by an improved echo state network. In order to improve the prediction precision, the key dynamic reservoir and prediction parameters of echo state network were optimized by an improved harmony search algorithm. Through the simulation on public and actual network traffic data, the results verify the proposed prediction method has higher prediction accuracy and smaller prediction error.

network traffic, chaos, echo state network, time scale, prediction

TP393

A

10.11959/j.issn.1000-436x.2016053

2015-03-31；

2015-12-02

國家自然科學重點基金資助項目（No.61034005）；遼寧省博士啟動基金資助項目（No.20141070）

The National Natural Science Foundation of China (No.61034005), Liaoning Province Doctor Startup Fund (No.20141070)

田中大（1978-），男，遼寧沈陽人，博士，沈陽工業(yè)大學講師，主要研究方向為時間序列建模與預測、網絡控制系統(tǒng)時延補償、非線性系統(tǒng)預測控制等。

李樹江（1966-），男，遼寧沈陽人，博士，沈陽工業(yè)大學教授，主要研究方向為復雜工業(yè)過程建模與控制、智能控制技術的應用研究與開發(fā)等。

王艷紅（1967-），女，遼寧沈陽人，博士，沈陽工業(yè)大學教授，主要研究方向為生產調度與優(yōu)化、先進制造信息系統(tǒng)、分布式信息處理與智能控制。

王向東（1959-），男，遼寧沈陽人，博士，沈陽工業(yè)大學教授，主要研究方向為生產調度與優(yōu)化、復雜工業(yè)過程建模與控制、智能控制技術的應用研究與開發(fā)。