小波變換與GARCH組合模型的網絡流量預測＊

劉 淵，黃世忠

（江南大學數字媒體學院，江蘇 無錫 214211）

1 引言

隨著各種網絡服務如網上支付、視頻會議、IP電話等的廣泛應用，人們對網絡質量的要求越來越高。然而，當今網絡已經變得十分復雜，出現突發事件與擁塞的可能性也大為增加，因此改善網絡的運行環境顯得至關重要，這就需要人們更好地了解網絡流量的特征及其變化規律并用來預測未來的網絡流量。網絡流量預測在擁塞控制、網絡管理與診斷、路由器設計等領域都具有重要意義［1］。

近年來，許多學者應用小波變換和時間序列方法對網絡流量進行了大量的研究和分析。文獻［2］在國內最早提出了基于小波的多尺度網絡流量自回歸滑動平均ARMA（Auto Regressive Moving Average）預測模型。該模型融合了多尺度時間序列分析和回歸分析的優點，在網絡流量預測中得到了廣泛應用。但是，由于其基于線性建模并且假設網絡流量序列為同方差，因此在某些環境中，難以準確、全面地描述網絡流量的非線性變化規律，從而影響最終預測精度［3］。

Engel［4］首先提出了廣義自回歸條件異方差GARCH（Generalized Auto Regressive Conditional Heteroskedasticity）模型，用于對時間序列的方差進行建模。GARCH模型可以較好地描述序列的異方差性，因此在時間序列建模和預測中具有廣泛應用。

在一些網絡環境中，網絡流量數據存在波動聚類性和異方差性，而國內將GARCH模型應用于網絡流量預測的文獻極少，因此本文提出使用小波變換與GARCH的組合模型進行網絡流量預測。

2 基本理論

2.1 小波變換

小波變換［5］是一個平方可積函數f（t）與一個在時頻域上均具有良好局部性質的小波函數φ（t）的內積：

其中，〈＊，＊〉表示內積，a＞0為尺度因子，b為位移因子，＊表示復數共軛，φa，b（t）稱為小波。

改變a值，對函數φa，b（t）具有伸展（a＞1）或收縮（a＜1）的作用；改變b值，則會影響函數f（t）圍繞b點的分析結果。φ（t）稱為母小波函數，其必須滿足容許性條件：

其中，φ（t）是ψ（ω）的傅里葉變換。

在實際應用中，需要對尺度因子a和位移因子b進行離散化處理，可以取：

其中，m、n為整數，b0為大于1的常數，a和b的選取與小波φ（t）的具體形式有關。

則離散小波函數表示為：

相應的離散小波變換表示為：

二進制離散小波變換Mallat算法簡潔實用，廣泛應用于實際時間序列處理中。

Mallat小波分解是將原始信號分別通過高頻和低頻兩個濾波器進行頻帶劃分，該算法可表示為：

其中，H為低通濾波器，G為高通濾波器。Mallat算法將原始信號分解為低頻部分和高頻部分。低頻部分是近似分量，反映的是信號的輪廓特征與變化趨勢；高頻部分是細節分量，反映隨機擾動等動態因素所帶來的影響。

分解后的信號可由Mallat重構算法進行重構，該算法可表示為：

其中，和分別為H和G的對偶算子。

2.2 GARCH模型

GARCH模 型［6，7］是 自 回 歸 條 件 異 方 差 模 型ARCH（Auto Regressive Conditional Heteroskedasticity）模型的進一步推廣，其定義如下：對于給定的階數p≥0和q≥0，有：

其中，e（t）～IID（0，1），也就是說，｛e（t）｝是一個均值為0、方差為1的獨立同分布隨機變量序列，并且e（t）與過去的值無關。e（t）與Zt－k（k≥1）相互獨立，α0＞1，αi≥0，β≥0均為常數，且滿足：

式（10）定 義 的 隨 機 過 程z（t）稱 為GARCH（p，q）過程。其中，h（t）是z（t）的條件變量，對于｛Z（s），s＜t｝，e（t）為相應的殘差變量。GARCH模型的實質是使用殘差平方序列的q階滑動平均擬合當期異方差函數值以及利用異方差函數的p階自相關性。

3 仿真實驗

3.1 實驗說明

本文采用實際流量數據LBL－tcp－3.tcp［7］進行網絡流量預測實驗。該數據集來源于伯克利實驗室，是公允的權威流量數據。其內容包括兩小時內在一個隔離區（Demilitarized Zone）中通過某服務器所有的網絡流量數據，以微秒級記錄某個時刻的網絡數據流量大小。

通過計算，本文以1秒為時間尺度獲得了該網絡中前2 000秒的網絡數據流量（如圖1所示），并使用前1 900秒的網絡流量數據進行小波分解，將其分解成高頻信號和低頻信號，如果這些分量信號存在GARCH效應，則進行GARCH建模；如不存在GARCH效應，則進行ARMA建模。然后，分別使用這些模型預測后100秒的網絡流量，最終通過小波分析理論將預測的結果進行重構，并與真實流量數據進行比較并計算出精確度的量化指標。

為了達到對比目的，本文使用了傳統的小波分析與ARMA組合模型對相同的網絡流量數據建模和預測，并將其預測結果與小波分析與GARCH組合模型預測結果進行比較。

Figure 1 Experimental network traffic data圖1 實驗網絡流量數據

3.2 小波分解

本文運用了Daubechies（db3）小波，使用Mallat算法對實驗數據進行尺度為w的小波分解，得到一組近似分量aw和w組細節分量dj（j＝1，2，…，w）。w值的選取不宜過大，也不宜過小。w過大對流量數據的信息損失大，分解過程中必然存在計算上的誤差；w過小則不能很好地得到反映流量數據某些特性的高頻信號。通過反復實驗，當w＝3時誤差較小且能獲取豐富的高頻信號，結果如圖2所示。

3.3 建模與預測

對各子序列a3，d3，d2，d1建立起合適的模型。通過拉格朗日乘數檢驗方法［8］得出子序列d2和d1具有GARCH效應，因此對子序列d2和d1建立GARCH模型，對a3和d3則建立ARMA模型。

Figure 2 3－level wavelet decomposition of the raw network traffic圖2 db3小波對原始網絡流量進行三層分解

本文限于篇幅，僅介紹子序列d2的GARCH建模過程。

為了選擇合適的GARCH階數，本節計算了赤池信息量準則AIC（Akaike Information Criterion）［9］值。AIC準則要求AIC值越小越好，其計算結果如表1所示。

Table 1 AIC of subsequence d2of GARCH with different orders表1 子序列d2的GARCH模型階數的AIC值

綜上，GARCH（1，1）的AIC值最小，因此選擇GARCH（1，1）較為合適。

然后，使用極大似然估計，計算出該模型的各參數的估計值，其結果如表2所示。

Table 2 Parameters estimation of GARCH（1，1）表2 GARCH（1，1）模型的參數估計

接著就可以使用該GARCH（1，1）模型來預測子序列d2后100秒的數據。

3.4 預測結果及其對比

使用Mallat重構算法，將子序列a3，d3，d2，d1的預測結果進行重構，最終便可得到原始流量序列的預測值。

為了對預測效果進行客觀的量化評價，本節引入了式（12）和式（13）量化指標。

均方根誤差（RMSE）：

相對均方根誤差（RRMSE）：

其中，Xk為序列的實際觀察值，為Xk的預測值，N為原始流量數據序列預測元素的個數。

均方根誤差和相對均方根誤差的值越小，說明預測值與實際觀察值越接近，預測效果越好。

為了進行橫向比較，本節同時使用了小波分析與ARMA組合模型對該流量數據進行了預測，其結果如圖3所示，預測效果量化指標如表3所示。圖4截取了前30秒的預測結果。

Table 3 Comparison of forecasts precision表3 預測精度比較

Figure 3 Comparison of the forecasts圖3 預測結果對比圖

Figure 4 Details of comparison of the forecasts圖4 預測結果放大對比圖

4 結束語

本文對實際網絡流量數據使用小波分析與GARCH組合模型進行了預測，仿真實驗結果表明，小波分析與GARCH組合模型可以較好地描述網絡流量數據的異方差性。由于實驗數據具有“波動集群”現象，其方差是隨著時間而變化的，這與傳統的小波分析與ARMA組合模型的同方差假設不相符，因此小波分析與GARCH組合模型較之傳統的小波分析與ARMA組合模型大幅提高了預測精度。而且，小波變換與GARCH模型的計算復雜度均為線性，因此該算法時間復雜度為O（N），在實際應用當中一般可行，在網絡流量等非線性預測問題中應用前景廣泛。

［1］ Jiang Ming，Wu Chun－ming，Zhang Min，et al.Research on the comparison of time series models for network traffic prediction［J］.Acta Electronica Sinica，2009，37（11）：2353－2357.（in Chinese）

［2］ Hong Fei，Wu Zhi－mei.Multiscale network traffic prediction model based on wavelet［J］.Chinese Journal of Computers，2006，29（1）：166－170.（in Chinese）

［3］ Dong Meng－li，Yang Geng，Cao Xiao－mei.Methods of network traffic prediction［J］.Computer Engineering，2011，37（16）：98－100.（in Chinese）

［4］ Wu wei，Liu Xi－yu，Yang Yi，et al.Analysis method of time array and two models of ARMA and GARCH［J］.Computer Technology and Development，2010，20（1）：247－249.（in Chinese）

［5］ Zhang Shan－wen，Lei Ying－jie，Feng You－qian.Application of time series with MATLAB［M］.Xi’an：Xidian University Press，2007.（in Chinese）

［6］ Cryer J D，Chan Kung－Sik.Time series analysis with applications in R［M］.Pan Hong－yu，translation.Beijing：China Machine Press，2011.（in Chinese）

［7］ Yi Dan－hui.Analysis of time series：Methods and application［M］.Beijing：China Renmin University Press，2011.（in Chinese）

［8］ Pan Hong－yu.Analysis of time series［M］.Beijing：University of International Business and Economics Press，2006.（in Chinese）

［9］ Wei Jin－wu，Wu Jiang－xing，Chen Shu－qiao.Joint multifractal model and characteristics analysis of network traffic［J］.Acta Electronica Sinica，2004，32（9）：1459－1463.（in Chinese）

附中文參考文獻：

［1］ 姜明，吳春明，張旻，等.網絡流量預測中的時間序列模型比較研究［J］.電子學報，2009，37（11）：2353－2357.

［2］ 洪飛，吳志美.基于小波的多尺度網絡流量預測模型［J］.計算機學報，2006，29（1）：166－170.

［3］ 董夢麗，楊庚，曹曉梅.網絡流量預測方法［J］.計算機工程，2011，37（16）：98－100.

［4］ 武偉，劉希玉，楊怡，等.時間序列分析方法及ARMA，GARCH兩種常用模型［J］.計算機技術與發展，2010，20（1）：247－249.

［5］ 張善文，雷英杰，馮有前.MATLAB在時間序列中的應用［M］.西安：西安電子科技大學出版社，2007.

［6］ Cryer J D，Chan Kung－Sik.時間序列分析及應用：R語言［M］.潘紅宇，等譯.北京：機械工業出版社，2011.

［7］ 易丹輝.時間序列分析：方法與應用［M］.北京：中國人民大學出版社，2011.

［8］ 潘紅宇.時間序列分析［M］.北京：對外經濟貿易大學出版社，2006.

［9］ 魏進武，鄔江興，陳庶樵.網絡流量的聯合多重分形模型及特性分析［J］.電子學報，2004，32（9）：1459－1463.