基于改進GM（1，1）模型-馬爾科夫殘差修正的網絡性能預測*

孫明瑋齊玉東王曉虹

（1.海軍航空大學 煙臺 264001）（2.中國人民解放軍第107醫院 煙臺 264001）

1 引言

網絡性能參數的準確預測在計算機網絡的設計和管理、擁塞控制和動態帶寬分配等領域具有十分重要的作用。要完成這項工作，建立精確的預測模型尤為重要。這對于網絡性能的準確分析與預測、擁塞管理、提高網絡服務質量等方面具有十分重要的價值。

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

針對以上研究的不足，本文擬建立一個基于馬爾科夫殘差修正的改進GM（1，1）模型的網絡性能預測方法。該方法首先采用移動窗口最小二乘多項式平滑算法對實驗數據進行平滑處理，然后將處理后的數據應用于灰色GM（1，1）預測模型中，并采用馬爾科夫殘差修正模型對預測結果進行修改以提高預測精度。

2 改進的灰色殘差修正預測模型

2.1 灰色GM（1，1）預測模型

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

灰色GM（1，1）預測模型的實質是對原始數據作一次累加處理，使生成的數據具有一定的規律，再通過建立一階線性微分方程，求得擬合曲線方程，用來對系統進行預測［6］。

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

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

其中：

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

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

2.2 灰色GM（1，1）預測模型改進

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

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

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

結合線性代數中的矩陣理論知識，該方程組可表示成如下矩陣形式：

根據最小二乘法得到b的解析解b*：

進而得到方程組中各未知數的最小二乘解為

將上述計算結果帶入式（6）中可以求出平滑后的數據點：

從結果表達式中可以發現，得到的結果其實是該平滑窗口內部各點的線性組合，即新的數據序列由平滑窗口內各點進行加權計算而得。采用移動窗口最小二乘多項式平滑算法進行數據平滑處理，既增加了當前數據的權重，又避免造成數據的劇烈波動。

2.3 殘差修正模型

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

由于該殘差序列中元素的符號有正有負，因此對殘差序列進行修正之前需要對其進行正化處理，即：

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

進而得到：

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

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

其中：Mi表示殘差值為狀態i的次數；Mij表示殘差值從狀態i轉變到狀態j的次數，定義向量

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

2表示狀態值為0（-）的概率，經過n′步轉移之后的狀態概率為其中Rn′表示由Pij的值構成的n′步轉移矩陣。因此，根據向量s(n′)中元素的大小關系確定第n+n′時刻的殘差符號為

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

3 模型合理性檢驗

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

這里Dε表示殘差序列的標準差，D0表示原始數據序列的標準差，εˉ表示殘差序列的均值。表1表示的是不同檢驗值結果對應的精度等級，通過計算改進前與改進后的后驗差值和小概率頻率值鑒定模型的精度等級，從而驗證改進后模型的合理性。

表1 模型精度檢驗值

4 改進灰色GM（1，1）預測模型在網絡性能預測中應用

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

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

表2 實驗數據

4.1 數據預處理

以響應時間數據為例，記歷史數據序列為

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

隨后對一次累加生成數據序列作對數變換：

最終以對數變換序列作為原始數據序列。

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

利用式（1）～（5）對原始數據序列進行預測，得到采用傳統灰色GM（1，1）模型方法預測計算公式為

接下來對傳統灰色GM（1，1）模型進行改進：

1）首先利用移動窗口最小二乘多項式平滑算法對一次累加生成得數據序列進行數據平滑處理，本文選用平滑窗口為7，最高階次數為3的移動窗口最小二乘多項式平滑算法得到平滑序列為

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

3）計算馬爾科夫殘差修正模型

通過對比殘差值與殘差預測值確定狀態轉移過程為011100。由此得到轉移矩陣為

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

表3 響應時間預測值對比表

利用本文提出的預測方法對其他指標的數據進行預測，預測結果見表4所示，從表4中可以看到預測結果可以較為精確反映現實情況下各指標的變化規律。

表4 各指標預測值

5 結語

針對傳統灰色GM（1，1）預測模型擬合精度不高的問題，本文從修正原始數據的方向出發，提出一種基于馬爾科夫殘差修正的改進灰色GM（1，1）預測模型。通過數據驗證，改進后的預測模型對于波動情況較大的數據分析具有良好的實用價值，模型的預測精度明顯優于傳統灰色GM（1，1）預測模型，從而有效地提高了預測結果的準確性，為準確預測網絡性能提供一種科學有效的方法。