小波變換與GARCH組合模型的網(wǎng)絡(luò)流量預(yù)測＊

劉 淵，黃世忠

（江南大學(xué)數(shù)字媒體學(xué)院，江蘇 無錫 214211）

1 引言

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

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

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

在一些網(wǎng)絡(luò)環(huán)境中，網(wǎng)絡(luò)流量數(shù)據(jù)存在波動聚類性和異方差性，而國內(nèi)將GARCH模型應(yīng)用于網(wǎng)絡(luò)流量預(yù)測的文獻(xiàn)極少，因此本文提出使用小波變換與GARCH的組合模型進(jìn)行網(wǎng)絡(luò)流量預(yù)測。

2 基本理論

2.1 小波變換

小波變換［5］是一個(gè)平方可積函數(shù)f（t）與一個(gè)在時(shí)頻域上均具有良好局部性質(zhì)的小波函數(shù)φ（t）的內(nèi)積：

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

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

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

在實(shí)際應(yīng)用中，需要對尺度因子a和位移因子b進(jìn)行離散化處理，可以?。?/p>

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

則離散小波函數(shù)表示為：

相應(yīng)的離散小波變換表示為：

二進(jìn)制離散小波變換Mallat算法簡潔實(shí)用，廣泛應(yīng)用于實(shí)際時(shí)間序列處理中。

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

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

分解后的信號可由Mallat重構(gòu)算法進(jìn)行重構(gòu)，該算法可表示為：

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

2.2 GARCH模型

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

其中，e（t）～I(xiàn)ID（0，1），也就是說，｛e（t）｝是一個(gè)均值為0、方差為1的獨(dú)立同分布隨機(jī)變量序列，并且e（t）與過去的值無關(guān)。e（t）與Zt－k（k≥1）相互獨(dú)立，α0＞1，αi≥0，β≥0均為常數(shù)，且滿足：

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

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)說明

本文采用實(shí)際流量數(shù)據(jù)LBL－tcp－3.tcp［7］進(jìn)行網(wǎng)絡(luò)流量預(yù)測實(shí)驗(yàn)。該數(shù)據(jù)集來源于伯克利實(shí)驗(yàn)室，是公允的權(quán)威流量數(shù)據(jù)。其內(nèi)容包括兩小時(shí)內(nèi)在一個(gè)隔離區(qū)（Demilitarized Zone）中通過某服務(wù)器所有的網(wǎng)絡(luò)流量數(shù)據(jù)，以微秒級記錄某個(gè)時(shí)刻的網(wǎng)絡(luò)數(shù)據(jù)流量大小。

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

為了達(dá)到對比目的，本文使用了傳統(tǒng)的小波分析與ARMA組合模型對相同的網(wǎng)絡(luò)流量數(shù)據(jù)建模和預(yù)測，并將其預(yù)測結(jié)果與小波分析與GARCH組合模型預(yù)測結(jié)果進(jìn)行比較。

Figure 1 Experimental network traffic data圖1 實(shí)驗(yàn)網(wǎng)絡(luò)流量數(shù)據(jù)

3.2 小波分解

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

3.3 建模與預(yù)測

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

Figure 2 3－level wavelet decomposition of the raw network traffic圖2 db3小波對原始網(wǎng)絡(luò)流量進(jìn)行三層分解

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

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

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

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

然后，使用極大似然估計(jì)，計(jì)算出該模型的各參數(shù)的估計(jì)值，其結(jié)果如表2所示。

Table 2 Parameters estimation of GARCH（1，1）表2 GARCH（1，1）模型的參數(shù)估計(jì)

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

3.4 預(yù)測結(jié)果及其對比

使用Mallat重構(gòu)算法，將子序列a3，d3，d2，d1的預(yù)測結(jié)果進(jìn)行重構(gòu)，最終便可得到原始流量序列的預(yù)測值。

為了對預(yù)測效果進(jìn)行客觀的量化評價(jià)，本節(jié)引入了式（12）和式（13）量化指標(biāo)。

均方根誤差（RMSE）：

相對均方根誤差（RRMSE）：

其中，Xk為序列的實(shí)際觀察值，為Xk的預(yù)測值，N為原始流量數(shù)據(jù)序列預(yù)測元素的個(gè)數(shù)。

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

為了進(jìn)行橫向比較，本節(jié)同時(shí)使用了小波分析與ARMA組合模型對該流量數(shù)據(jù)進(jìn)行了預(yù)測，其結(jié)果如圖3所示，預(yù)測效果量化指標(biāo)如表3所示。圖4截取了前30秒的預(yù)測結(jié)果。

Table 3 Comparison of forecasts precision表3 預(yù)測精度比較

Figure 3 Comparison of the forecasts圖3 預(yù)測結(jié)果對比圖

Figure 4 Details of comparison of the forecasts圖4 預(yù)測結(jié)果放大對比圖

4 結(jié)束語

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

［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，F(xiàn)eng 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－h(huán)ui.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）

附中文參考文獻(xiàn)：

［1］ 姜明，吳春明，張旻，等.網(wǎng)絡(luò)流量預(yù)測中的時(shí)間序列模型比較研究［J］.電子學(xué)報(bào)，2009，37（11）：2353－2357.

［2］ 洪飛，吳志美.基于小波的多尺度網(wǎng)絡(luò)流量預(yù)測模型［J］.計(jì)算機(jī)學(xué)報(bào)，2006，29（1）：166－170.

［3］ 董夢麗，楊庚，曹曉梅.網(wǎng)絡(luò)流量預(yù)測方法［J］.計(jì)算機(jī)工程，2011，37（16）：98－100.

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

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

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

［7］ 易丹輝.時(shí)間序列分析：方法與應(yīng)用［M］.北京：中國人民大學(xué)出版社，2011.

［8］ 潘紅宇.時(shí)間序列分析［M］.北京：對外經(jīng)濟(jì)貿(mào)易大學(xué)出版社，2006.

［9］ 魏進(jìn)武，鄔江興，陳庶樵.網(wǎng)絡(luò)流量的聯(lián)合多重分形模型及特性分析［J］.電子學(xué)報(bào)，2004，32（9）：1459－1463.