基于改進(jìn)GM（1，1）模型-馬爾科夫殘差修正的網(wǎng)絡(luò)性能預(yù)測*

孫明瑋齊玉東王曉虹

（1.海軍航空大學(xué) 煙臺(tái) 264001）（2.中國人民解放軍第107醫(yī)院 煙臺(tái) 264001）

1 引言

網(wǎng)絡(luò)性能參數(shù)的準(zhǔn)確預(yù)測在計(jì)算機(jī)網(wǎng)絡(luò)的設(shè)計(jì)和管理、擁塞控制和動(dòng)態(tài)帶寬分配等領(lǐng)域具有十分重要的作用。要完成這項(xiàng)工作，建立精確的預(yù)測模型尤為重要。這對(duì)于網(wǎng)絡(luò)性能的準(zhǔn)確分析與預(yù)測、擁塞管理、提高網(wǎng)絡(luò)服務(wù)質(zhì)量等方面具有十分重要的價(jià)值。

目前關(guān)于網(wǎng)絡(luò)性能預(yù)測的研究已經(jīng)取得一定成果。邵雪梅［1］等通過分析校園網(wǎng)網(wǎng)絡(luò)流量的現(xiàn)狀及特點(diǎn)，利用RBF神經(jīng)網(wǎng)絡(luò)對(duì)網(wǎng)絡(luò)流量進(jìn)行預(yù)測，雖然預(yù)測精度較高，適合描述流量的不穩(wěn)定性，但是訓(xùn)練神經(jīng)網(wǎng)絡(luò)需要大量的歷史數(shù)據(jù)支撐，并且計(jì)算量較大，實(shí)時(shí)建模有一定的難度；劉宗磊［2］等將時(shí)間序列模型與灰色預(yù)測模型的結(jié)果作為輸入，建立基于RBF神經(jīng)網(wǎng)絡(luò)模型的組合預(yù)測模型，但是該模型對(duì)于處理具有波動(dòng)性、周期性等特征的數(shù)據(jù)精度有待提高；李捷［3］等通過構(gòu)建卡爾曼濾波和小波分析混合的流量預(yù)測算法，對(duì)網(wǎng)絡(luò)流量的線性部分和非線性部分進(jìn)行預(yù)測，該方法雖然具有實(shí)時(shí)性，但是缺乏對(duì)網(wǎng)絡(luò)流量的長期預(yù)測；唐萬梅［4］結(jié)合灰色預(yù)測模型與支持向量機(jī)二者的優(yōu)點(diǎn)，構(gòu)造出灰色支持向量機(jī)預(yù)測預(yù)測模型，但是該模型適用于處理具有規(guī)律的原始數(shù)據(jù)序列，對(duì)于網(wǎng)絡(luò)性能數(shù)據(jù)而言，其變化并無規(guī)律可言。

針對(duì)以上研究的不足，本文擬建立一個(gè)基于馬爾科夫殘差修正的改進(jìn)GM（1，1）模型的網(wǎng)絡(luò)性能預(yù)測方法。該方法首先采用移動(dòng)窗口最小二乘多項(xiàng)式平滑算法對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行平滑處理，然后將處理后的數(shù)據(jù)應(yīng)用于灰色GM（1，1）預(yù)測模型中，并采用馬爾科夫殘差修正模型對(duì)預(yù)測結(jié)果進(jìn)行修改以提高預(yù)測精度。

2 改進(jìn)的灰色殘差修正預(yù)測模型

2.1 灰色GM（1，1）預(yù)測模型

灰色預(yù)測模型（Gray ForecastModel）［5］是通過少量的、不完全的信息建立數(shù)學(xué)模型并做出預(yù)測的一種方法。當(dāng)應(yīng)用運(yùn)籌學(xué)的思想解決實(shí)際問題、指定發(fā)展戰(zhàn)略和政策、進(jìn)行重大問題的決策時(shí)，該模型根據(jù)客觀事物過去和現(xiàn)在的發(fā)展規(guī)律，借助于科學(xué)的方法對(duì)其未來的發(fā)展趨勢和狀況進(jìn)行描述和分析，并形成科學(xué)的假設(shè)和判斷?；疑A(yù)測模型所需要的建模信息量少，運(yùn)算方便，建模精度較高，在各種預(yù)測領(lǐng)域中都有廣泛的應(yīng)用，是處理小樣本預(yù)測問題的有效工具。

灰色GM（1，1）預(yù)測模型的實(shí)質(zhì)是對(duì)原始數(shù)據(jù)作一次累加處理，使生成的數(shù)據(jù)具有一定的規(guī)律，再通過建立一階線性微分方程，求得擬合曲線方程，用來對(duì)系統(tǒng)進(jìn)行預(yù)測［6］。

設(shè)原始非零數(shù)據(jù)序列為X(0)={x(0)(1)，x(0)(2)，…，x(0)(n)}，X(0)的一階累加序列（1-AGO序列）為

稱Z(1)為X(1)的緊鄰均值生成序列（也稱為背景構(gòu)造值），記為

其中：

將式（3）得到的向量a^帶入到一階線性微分方程中求得擬合曲線方程為

對(duì)x^(1)(t+1)作一次累減生成，即得灰色GM（1，1）預(yù)測模型為

2.2 灰色GM（1，1）預(yù)測模型改進(jìn)

雖然傳統(tǒng)灰色GM（1，1）預(yù)測模型中經(jīng)過一次累加生成后的數(shù)據(jù)序列呈現(xiàn)嚴(yán)格的指數(shù)增長趨勢，可以有效保證數(shù)據(jù)的擬合度，但是若原始數(shù)據(jù)序列出現(xiàn)較大的波動(dòng)時(shí)，一次累加生成后數(shù)據(jù)序列的增長趨勢將呈現(xiàn)不平滑現(xiàn)象，此時(shí)預(yù)測誤差較大。為了減小誤差，需要對(duì)傳統(tǒng)灰色GM（1，1）預(yù)測模型的原始數(shù)據(jù)序列做平滑處理。

本文采用移動(dòng)窗口最小二乘多項(xiàng)式平滑算法（Savitzky-Golay Smoothing）進(jìn)行數(shù)據(jù)平滑處理。Savitzky-Golay Smoothing算法［7～9］最初于1964年由Savitzky和Golay二人提出，主要用于對(duì)數(shù)據(jù)流的平滑降噪處理，如今在圖像處理領(lǐng)域中得到較為廣泛使用，該算法是一種基于最小二乘法的局部擬合方法，從數(shù)據(jù)流的起點(diǎn)開始，在事先確定的平滑窗口內(nèi)對(duì)數(shù)據(jù)流進(jìn)行平滑處理，通過向后滑動(dòng)平滑窗口直到數(shù)據(jù)流的終點(diǎn)為止，其最大的特點(diǎn)就是在平滑數(shù)據(jù)的同時(shí)保證數(shù)據(jù)流的形狀、寬度、變化趨勢不變。

假設(shè)原始數(shù)據(jù)序列為X，確定平滑窗口大小為m（通常情況下選擇奇數(shù)，本文選擇m=7），多項(xiàng)式最高階次數(shù)為n（這里選擇n=3）。移動(dòng)窗口最小二乘多項(xiàng)式平滑算法就是利用中心數(shù)據(jù)點(diǎn)與前三個(gè)數(shù)據(jù)點(diǎn)和后三個(gè)數(shù)據(jù)點(diǎn)進(jìn)行最小二乘擬合，每一個(gè)數(shù)據(jù)點(diǎn)可以表示為不同的多項(xiàng)式結(jié)果，從而利用7個(gè)數(shù)據(jù)點(diǎn)組成含有n+1個(gè)未知數(shù)，m個(gè)方程的方程組：

結(jié)合線性代數(shù)中的矩陣?yán)碚撝R(shí)，該方程組可表示成如下矩陣形式：

根據(jù)最小二乘法得到b的解析解b*：

進(jìn)而得到方程組中各未知數(shù)的最小二乘解為

將上述計(jì)算結(jié)果帶入式（6）中可以求出平滑后的數(shù)據(jù)點(diǎn)：

從結(jié)果表達(dá)式中可以發(fā)現(xiàn)，得到的結(jié)果其實(shí)是該平滑窗口內(nèi)部各點(diǎn)的線性組合，即新的數(shù)據(jù)序列由平滑窗口內(nèi)各點(diǎn)進(jìn)行加權(quán)計(jì)算而得。采用移動(dòng)窗口最小二乘多項(xiàng)式平滑算法進(jìn)行數(shù)據(jù)平滑處理，既增加了當(dāng)前數(shù)據(jù)的權(quán)重，又避免造成數(shù)據(jù)的劇烈波動(dòng)。

2.3 殘差修正模型

若使用原始數(shù)據(jù)序列建立的預(yù)測模型檢驗(yàn)不能滿足要求時(shí)，需要對(duì)建立的模型進(jìn)行殘差修正。假設(shè)通過改進(jìn)灰色GM（1，1）模型計(jì)算后的殘差序列為

由于該殘差序列中元素的符號(hào)有正有負(fù)，因此對(duì)殘差序列進(jìn)行修正之前需要對(duì)其進(jìn)行正化處理，即：

對(duì)正化殘差序列建立改進(jìn)灰色GM（1，1）預(yù)測模型，并利用最小二乘法得到ε(0)(t+1)′的殘差預(yù)測值為

進(jìn)而得到：

其中，殘差系數(shù)σ(t)是由殘差的正負(fù)值決定。但是，當(dāng)t＞n時(shí)，σ(t)的取值不確定。此時(shí)，引入馬爾科夫過程。

馬爾科夫預(yù)測模型在數(shù)據(jù)預(yù)測方面呈現(xiàn)出精度高、泛化能力強(qiáng)、適用范圍廣等特點(diǎn)，克服了傳統(tǒng)模型需要大量歷史數(shù)據(jù)的缺點(diǎn)，只需要從數(shù)據(jù)序列中找出內(nèi)在規(guī)律，通過建立相關(guān)模型進(jìn)行預(yù)測［10～11］。馬爾科夫預(yù)測模型描述的是一個(gè)隨機(jī)時(shí)間序列的動(dòng)態(tài)變化過程，它認(rèn)為在事物的發(fā)展過程中，從一種狀態(tài)轉(zhuǎn)變到另一種狀態(tài)是具有轉(zhuǎn)移概率的，而這種轉(zhuǎn)移概率可根據(jù)歷史數(shù)據(jù)推算出來，適用于處理隨機(jī)波動(dòng)性較大的數(shù)據(jù)序列［12］。若第t時(shí)刻模型的殘差值為正數(shù)，記狀態(tài)值為1；若為負(fù)數(shù)，記狀態(tài)值為0。將殘差值從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率記為一步轉(zhuǎn)移概率P，且一步轉(zhuǎn)移概率P可用下式來估計(jì)：

其中：Mi表示殘差值為狀態(tài)i的次數(shù)；Mij表示殘差值從狀態(tài)i轉(zhuǎn)變到狀態(tài)j的次數(shù)，定義向量

1表示狀態(tài)值為1（+）的概率，s(0)

2表示狀態(tài)值為0（-）的概率，經(jīng)過n′步轉(zhuǎn)移之后的狀態(tài)概率為其中Rn′表示由Pij的值構(gòu)成的n′步轉(zhuǎn)移矩陣。因此，根據(jù)向量s(n′)中元素的大小關(guān)系確定第n+n′時(shí)刻的殘差符號(hào)為

綜上所述，利用馬爾科夫殘差模型修正改進(jìn)灰色GM（1，1）模型公式為

3 模型合理性檢驗(yàn)

灰色GM（1，1）模型的精度檢驗(yàn)通常采用后驗(yàn)差檢驗(yàn)C和小概率頻率檢驗(yàn)P。其中：

這里Dε表示殘差序列的標(biāo)準(zhǔn)差，D0表示原始數(shù)據(jù)序列的標(biāo)準(zhǔn)差，εˉ表示殘差序列的均值。表1表示的是不同檢驗(yàn)值結(jié)果對(duì)應(yīng)的精度等級(jí)，通過計(jì)算改進(jìn)前與改進(jìn)后的后驗(yàn)差值和小概率頻率值鑒定模型的精度等級(jí)，從而驗(yàn)證改進(jìn)后模型的合理性。

表1 模型精度檢驗(yàn)值

4 改進(jìn)灰色GM（1，1）預(yù)測模型在網(wǎng)絡(luò)性能預(yù)測中應(yīng)用

為驗(yàn)證本文提出的基于馬爾科夫殘差修正的改進(jìn)灰色GM（1，1）模型的正確性和可靠性，本文選擇QWS數(shù)據(jù)集，并通過有效性和吞吐量擴(kuò)展出互操作性和擴(kuò)展性兩條屬性［13］，表2為截取的部分實(shí)驗(yàn)數(shù)據(jù)。

從表2數(shù)據(jù)可知，由于個(gè)別屬性的數(shù)據(jù)序列（如響應(yīng)時(shí)間、吞吐量、延遲）值域范圍較大，因而存在較大的波動(dòng)，為了提高模型擬合精度，需要在做一次累加生成之前，對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理。

表2 實(shí)驗(yàn)數(shù)據(jù)

4.1 數(shù)據(jù)預(yù)處理

以響應(yīng)時(shí)間數(shù)據(jù)為例，記歷史數(shù)據(jù)序列為

首先對(duì)原始數(shù)據(jù)序列作一次累加生成，消除原始數(shù)據(jù)上下振蕩的趨勢，記一次累加生成數(shù)據(jù)序列為

隨后對(duì)一次累加生成數(shù)據(jù)序列作對(duì)數(shù)變換：

最終以對(duì)數(shù)變換序列作為原始數(shù)據(jù)序列。

4.2 建立灰色GM（1，1）模型

利用式（1）～（5）對(duì)原始數(shù)據(jù)序列進(jìn)行預(yù)測，得到采用傳統(tǒng)灰色GM（1，1）模型方法預(yù)測計(jì)算公式為

接下來對(duì)傳統(tǒng)灰色GM（1，1）模型進(jìn)行改進(jìn)：

1）首先利用移動(dòng)窗口最小二乘多項(xiàng)式平滑算法對(duì)一次累加生成得數(shù)據(jù)序列進(jìn)行數(shù)據(jù)平滑處理，本文選用平滑窗口為7，最高階次數(shù)為3的移動(dòng)窗口最小二乘多項(xiàng)式平滑算法得到平滑序列為

2）將平滑后的數(shù)據(jù)放入預(yù)測公式中，計(jì)算預(yù)測值與真實(shí)值的殘差序列，并利用殘差修正模型得到殘差預(yù)測公式：

3）計(jì)算馬爾科夫殘差修正模型

通過對(duì)比殘差值與殘差預(yù)測值確定狀態(tài)轉(zhuǎn)移過程為011100。由此得到轉(zhuǎn)移矩陣為

將t=7作為初始狀態(tài)，根據(jù)式（17）～（18）確定后續(xù)時(shí)刻得殘差符號(hào)，進(jìn)而得到經(jīng)馬爾科夫殘差修正模型修正后的預(yù)測值。本文將t=1～7的數(shù)據(jù)作為模型的擬合數(shù)據(jù)，將t=8～11的數(shù)據(jù)作為模型的預(yù)測檢驗(yàn)數(shù)據(jù)。表3為傳統(tǒng)灰色GM（1，1）模型與改進(jìn)后的灰色GM（1，1）模型預(yù)測值對(duì)比表。從表3可以看到，傳統(tǒng)灰色GM（1，1）模型得到的預(yù)測結(jié)果不理想，預(yù)測值與真實(shí)值間的相對(duì)誤差較大，整個(gè)模型的后驗(yàn)差為0.7223<0.80，小概率誤差為0.7143>0.70，精度等級(jí)為三級(jí)，很難取得良好的預(yù)測效果。而采用改進(jìn)的灰色GM（1，1）模型通過數(shù)據(jù)平滑處理，將實(shí)驗(yàn)數(shù)據(jù)轉(zhuǎn)化為適合灰色預(yù)測模型的形式，同時(shí)采用馬爾科夫殘差修正模型修正預(yù)測結(jié)果，最終得到的平均相對(duì)誤差為2.832%，后驗(yàn)差為0.0513<0.35，小概率誤差為1>0.95，精度等級(jí)為一級(jí)，有效地減小了預(yù)測值與實(shí)際值間的誤差，提高了擬合精度。

表3 響應(yīng)時(shí)間預(yù)測值對(duì)比表

利用本文提出的預(yù)測方法對(duì)其他指標(biāo)的數(shù)據(jù)進(jìn)行預(yù)測，預(yù)測結(jié)果見表4所示，從表4中可以看到預(yù)測結(jié)果可以較為精確反映現(xiàn)實(shí)情況下各指標(biāo)的變化規(guī)律。

表4 各指標(biāo)預(yù)測值

5 結(jié)語

針對(duì)傳統(tǒng)灰色GM（1，1）預(yù)測模型擬合精度不高的問題，本文從修正原始數(shù)據(jù)的方向出發(fā)，提出一種基于馬爾科夫殘差修正的改進(jìn)灰色GM（1，1）預(yù)測模型。通過數(shù)據(jù)驗(yàn)證，改進(jìn)后的預(yù)測模型對(duì)于波動(dòng)情況較大的數(shù)據(jù)分析具有良好的實(shí)用價(jià)值，模型的預(yù)測精度明顯優(yōu)于傳統(tǒng)灰色GM（1，1）預(yù)測模型，從而有效地提高了預(yù)測結(jié)果的準(zhǔn)確性，為準(zhǔn)確預(yù)測網(wǎng)絡(luò)性能提供一種科學(xué)有效的方法。