基于ARIMA和卡爾曼濾波的在線Web服務QoS預測方法

劉澤遠， 楊孝宗， 舒燕君

(哈爾濱工業(yè)大學 計算機科學與技術學院， 哈爾濱 150001)

0 引 言

Web服務為面向服務的體系架構(Service-Oriented Architecture，SOA)提供了一個標準化的解決方案[1]，并在設計上成功解決了分布式計算基于標準、松耦合、協(xié)議無關的需求。隨著Web服務的指數(shù)級增長，研究發(fā)現(xiàn)很多服務的服務質量良莠不齊，僅僅通過功能上的要求無法做出有效選擇，因而需要通過服務質量(Quality of Service，QoS)的評估，來選擇滿足要求的Web服務。服務質量描述Web服務的非功能方面的特性，主要包括響應時間、吞吐量、故障間隔時間等指標。

在波動大、變化快的分布式Web服務環(huán)境中，Web服務的服務質量不會保持不變，而要保證Web服務滿足使用者的要求，就要尋找一種有效的方法來判斷Web服務在一定時間內能否滿足服務質量的約束。針對這一問題，研究指出可以對QoS歷史記錄數(shù)據(jù)進行分析，用來預測Web服務在未來時間的QoS值。立足于這一研究角度，很多有關基于時間序列分析的Web服務QoS預測方法的研究已陸續(xù)涌現(xiàn)[2]，同時也證明了這一思路的設計可行性。

本文在已有研究基礎上提出一種基于時間序列分析的Web服務QoS預測方法，結合了ARIMA(Auto-regressive Integrated Moving Average)與卡爾曼濾波(Kalman Filtering)技術，首先使用ARIMA模型對QoS歷史記錄值進行擬合，將ARIMA模型轉換成狀態(tài)空間模型，使用卡爾曼濾波器預測未來時間點的QoS值，在運行時每次測得的QoS值都可以對卡爾曼濾波器進行更新。該方法具有適應性高，計算復雜度低等特點，通過在公開的Web服務QoS記錄數(shù)據(jù)集[2]上實施的實驗可以驗證該方法的準確性。

本文研究在論述上，首先探討了該方向的相關研究工作,并分析了現(xiàn)有工作的優(yōu)缺點；接下來給出了本文預測方法的理論基礎與具體設計；然后，將該方法與經典的方法展開比較實驗，并對實驗結果進行分析；最后總結全文，進而展望未來的研究工作。

1 相關研究

在基于時間序列分析的Web服務的QoS預測中，目前已可見到一系列的研究工作和學術成果。Cavallo等人[2]比較了在時間序列模型中堪稱代表的ARIMA模型與當前值方法、歷史平均值方法以及線性回歸法AR的仿真測試，結果表明ARIMA算法對異常值的容忍度較高，并且對QoS的違規(guī)有良好的預測效果，在預測結果上能夠表現(xiàn)出相對較小的預測誤差。Amin等人[3]提出結合ARIMA與廣義自回歸條件異方差(GARCH)模型，GARCH模型可以改善ARIMA模型中方差恒定假設的不足，更加貼近真實的Web服務QoS數(shù)據(jù)特征。Ye等人[4]考慮QoS多個屬性維度之間的相關性，提出使用多元ARIMA模型、Holters-Winters指數(shù)平滑模型，并在此后的研究中，將提出的方法同VAR(向量自回歸)做了比較處理，其中包括了許多基于自回歸的方法，諸如AR、SETAR(自激勵門限回歸模型)、ARIMA以及ARMA-GARCH模型。

可以發(fā)現(xiàn)，將單一的統(tǒng)計學模型進行組合是研究Web服務QoS預測的熱門趨勢，單一的模型已難以滿足波動大并且沒有統(tǒng)一規(guī)律的Web服務QoS預測。而隨著近年來機器學習技術的迅猛發(fā)展，已經有一些研究者開始嘗試將機器學習的方法應用到Web服務QoS的預測中。Zadeh等人[5]和Senivongse等人[6]即應用ANN(人工神經網絡)解決Web服務QoS預測的問題，Yang等人[7]則提出使用遺傳編程的方法。Wang等人[8]提出使用長短期記憶循環(huán)神經網絡模型，預測Web服務系統(tǒng)的可靠性。綜合分析上述研究結果可知，機器學習的方法并未能在預測準確率上達到質的提升，而這些方法在執(zhí)行上的復雜卻已經成為將其付諸現(xiàn)實應用的制約因素。

在使用ARIMA模型預測Web服務的QoS時間序列的研究中經過分析發(fā)現(xiàn)，單純地使用ARIMA模型不能夠適應Web服務QoS數(shù)據(jù)的波動頻繁、包含噪聲等復雜特點，為了獲得更加準確的預測效果，本文使用卡爾曼濾波對ARIMA模型的結果進行修正?？柭鼮V波是一種最優(yōu)化自回歸數(shù)據(jù)處理算法(Optimal Recursive Data Processing Algorithm)[9]，其最突出的優(yōu)勢即在于能夠從一些包含噪聲的觀測量估計系統(tǒng)的狀態(tài)?？柭鼮V波利用前一時刻的估計值和當前時刻的觀測值，更新當前時刻的狀態(tài)向量，利用這一特點就可以很好地彌補單一ARIMA模型在QoS時間序列預測上的不足。下面首先詳述ARIMA與卡爾曼濾波相結合的理論基礎，然后闡述該方法的設計過程。

2 理論基礎

ARIMA模型與卡爾曼濾波相結合的關鍵就是將ARIMA模型轉換成狀態(tài)空間模型，再使用卡爾曼濾波對狀態(tài)進行預測與更新。一個ARIMA(p,d,q)模型經d階差分就可得到ARMA(p,q)模型，數(shù)學公式可表述如下：

(1)

其中，Zt為t時刻觀測值；at為t時刻預測值與觀測值的誤差；φi、θj為模型參數(shù)。設m=max{p,q}，令φi=0(i>p)，θj=0(j>q)，那么公式(1)也可以表示為：

(2)

設B為延遲算子，可將公式(2)變化為：

φ(B)Zt=θ(B)at

(3)

接下來，要將式(3)轉換為Zt=ψ(B)at的形式，令ψ(B)=θ(B)/φ(B)，其中ψ(B)=(ψ0+ψ1B+…+ψmBm+…)，ψ0=1。根據(jù)延遲算子B的每一項系數(shù)相等，可以得出：

-θm=-φmΨ0-φm-1Ψ1-…-φ1Ψm-1+Ψm

(4)

化簡公式(4)，就會得到ψm的數(shù)學運算公式可見如下：

(5)

由此，可以將Zt+m-i=ψ(B)at+m-i表達式展開為如下形式：

Zt+m-i=at+m-i+Ψ1at+m-1+Ψ2at+m-i-2+…

(6)

Zt+m-i|t=Ψm-iat+Ψm-i+1at-1+Ψm-i+2at-2+…

(7)

Zt+m-i|t-1=Ψm-i+1at-1+Ψm-i+2at-2+…

(8)

由公式(7)、(8)可得：

Zt+m-i|t=Zt+m-i|t-1+Ψm-iat

(9)

令狀態(tài)向量St=(Zt|t-1,Zt+1|t-1,...,Zt+m-1|t-1)T，觀測值Zt=Zt|t-1+at，觀測方程即可表示為：

Zt=[1,0,…,0]St+at

(10)

根據(jù)公式(5)、(9)可推得狀態(tài)轉移方程為：

St+1=FSt+Gat

(11)

其中，F(xiàn)、G的運算可使用如下數(shù)學公式：

(12)

綜上就是模型ARMA(p,q)轉移到狀態(tài)空間模型的推導過程，在得到狀態(tài)空間模型后，就可轉入卡爾曼濾波的應用設計的研究。

3 方法設計

如圖 1所示，本文提出的Web服務QoS預測方法主要分為2個模塊，分別是：ARIMA模型的確立和卡爾曼濾波器的更新?？偟貋碚f，根據(jù)QoS歷史數(shù)據(jù)進行ARIMA建模，根據(jù)第2節(jié)的方法將其轉換為狀態(tài)空間模型，在運行時獲得新的QoS觀測值后，對狀態(tài)向量進行更新，再將卡爾曼濾波的預測值作為最后的預測結果。對此內容，本節(jié)將給出闡釋分述如下。

圖1 預測方法概覽

3.1 ARIMA模型建立

(1)白噪聲檢測。如果一個時間序列是純隨機的，此時就沒有必要再利用ARIMA方法繼續(xù)接下來的操作，因其并不適用于該方法。若一個時間序列純由白噪聲構成，那么在理論上其各階自相關系數(shù)(Auto-Correlation Function，ACF)均為0，基于這一點即可判斷時間序列是否為純隨機。

(2)穩(wěn)定性檢測。最簡單的判斷時間序列穩(wěn)定性的方法就是通過肉眼觀察樣本的二維曲線圖得出結論；當然也有其它的方法。理論上可證明平穩(wěn)的時間序列通常會具有短期相關性，隨著延遲增加，序列的自相關系數(shù)很快會降低至0，根據(jù)這一點就能判斷時間序列的平穩(wěn)性。如果序列非平穩(wěn)，則引入逐次差分，直至得到平穩(wěn)序列，即將ARIMA模型轉化成ARMA模型。

(3)定階。得到平穩(wěn)的時間序列后，需進一步判斷序列是否滿足自回歸(AR)、滑動平均(MA)。識別方法是序列的自相關系數(shù)(ACF)和偏自相關系數(shù)(Partial Auto-Correlation Function，PACF)。若ACF曲線衰減的同時、PACF曲線截斷，則AR模型適用；若ACF曲線截斷的同時、PACF曲線衰減，MA模型適用。根據(jù)ACF的拖尾特征、PACF的截尾特征，可以確定對應的階數(shù)p、q。

(4)模型參數(shù)擬合與檢驗。模型的階數(shù)確定后，模型參數(shù)個數(shù)也確定了。需要擬合出其它參數(shù)，即φi(i=1,2,...,p)、θj(j=1,2,...,q)，文獻[10]給出使用極大似然估計法進行參數(shù)擬合的完整計算步驟。對于模型的檢驗環(huán)節(jié)，就需要檢驗模型是否具有統(tǒng)計意義，即檢驗是否對時間序列提取足夠充分的信息。理論上推導可知，如果模型信息提取充分，殘差序列即為白噪聲。

3.2 卡爾曼濾波預測

卡爾曼濾波分為時間更新方程和狀態(tài)更新方程。在Web服務的QoS預測中，結合ARMA(p,q)轉化的狀態(tài)空間方程，設St|t為時刻t基于先驗信息得到的狀態(tài)估計，卡爾曼濾波時間更新方程的公式表達詳見如下：

St+1|t=FSt|t

(13)

Pt+1|t=FPt|tFT+GQGT

(14)

其中，Pt|t是時刻t預測誤差的后驗協(xié)方差矩陣；Pt+1|t是時刻t+1預測誤差的先驗協(xié)方差矩陣；Q為過程噪聲的協(xié)方差矩陣。狀態(tài)轉移矩陣F將St|t轉換為St+1|t，將Pt|t轉換為Pt+1|t。t+1時刻QoS預測值根據(jù)狀態(tài)向量St+1|t可由如下公式計算得出：

Zt+1|t=HSt+1|t

(15)

得到觀測值Zt+1，可以對St+1|t+1、Pt+1|t+1做出更新，卡爾曼濾波的狀態(tài)更新方程如式(16)所示：

St+1|t+1=St+1|t+Pt+1|tHT[HPt+1|tHT+R]-1(Zt+1-Zt+1|t)

(16)

Pt+1|t+1=Pt+1|t-Pt+1|tHT[HPt+1|tHT+R]-1HPt+1|t

(17)

其中，Pt+1|tHT[HPt+1|tHT+R]-1就是卡爾曼增益矩陣，通過最小化預測誤差的后驗協(xié)方差矩陣計算得出，計算結果決定了狀態(tài)向量受到觀測值的影響程度。

在實際操作中，輸入初始狀態(tài)S0|0和P0|0，然后計算Z1|0和V1|0。當?shù)玫接^測值Z1后，使用更新方程計算S1|1和P1|1，將其作為下一次循環(huán)的初始狀態(tài)。值得一提的是，輸入任意的初始值S0|0和P0|0，初始值對后面預測值的影響會隨著t的增加而變得越來越小，因為狀態(tài)轉移矩陣F的特征值均小于1，也就是說，隨著t的增加，卡爾曼濾波器保證了初始值對后面結果的影響將逐步趨近于0。

4 實驗

本節(jié)將驗證研發(fā)提出的預測方法的實際效果。實驗數(shù)據(jù)采用Cavallo公開發(fā)布的數(shù)據(jù)集[2]，選取了XML Daily Fact的服務，該數(shù)據(jù)記錄了2006年7月～11月對該服務每隔1 h調用一次的QoS值記錄，包括響應時間、可用性等。本次測試實驗擬對實踐中最常用的響應時間屬性進行分析，選取了連續(xù)400個時刻的記錄作為實驗數(shù)據(jù)。為了削減異常值對模型的影響，對實驗數(shù)據(jù)中高于3 000 ms的值(這些值相比樣本個數(shù)非常少)設為正常數(shù)據(jù)的均值。

首先是使用單一的ARIMA模型的預測效果，繪制后即如圖 2所示。

圖2 ARIMA預測值與實際值

使用本文提出的預測方法，結合ARIMA模型與卡爾曼濾波的預測效果則如圖 3所示。

圖3 卡爾曼濾波預測值與實際值

從圖2、圖3中可以直觀地看出，本文的預測方法的預測結果更加接近真實值，對波動情形的反應更為及時，在下一時刻就能做出調整與修正。為了更加客觀地展現(xiàn)本文預測方法的準確率，對2種預測方法的預測結果與實際值的誤差進行統(tǒng)計。本文計算了預測結果與實際值的均方根誤差(Root Mean Squared Error，RMSE)，均方根誤差的數(shù)學定義可表示如下：

(18)

基于單一的ARIMA模型預測結果,均方根誤差為216.862 6;基于本文預測方法,預測結果的均方根誤差為200.673 3，預測效果整體提升了7.47%。

5 結束語

準確地預測Web服務的QoS，能夠為服務提供者有效地降低服務質量違規(guī)的風險，而且也能夠幫助服務使用者在使用時間內調取到服務質量穩(wěn)定的服務。故而，本文研發(fā)設計了一種基于時間序列分析的Web服務預測方法，并在公開的數(shù)據(jù)集上進行實驗，驗證了該方法的有效性。實驗結果表明，相比傳統(tǒng)的單一ARIMA模型預測方法，本文方法能夠自適應地實現(xiàn)對QoS波動的預測，進而及時發(fā)出QoS違規(guī)的預警。

Web服務的QoS相對其它領域的時間序列有其本身的特點，由于業(yè)務復雜程度不一、網絡環(huán)境波動大的影響，要更加準確地預測Web服務的QoS值就勢必還有很多的工作需要成為當下的關鍵研究課題。后續(xù)工作將主要著重于如下方面：

(1)時間序列的噪聲。噪聲會對序列本身信息的挖掘產生影響，而去噪方法的選擇也將涉及多方面的因素考證，因此為Web服務的QoS序列進行合理去噪，將會是未來的研究熱點。

(2)QoS各屬性的相關性。單變量的預測方法更加難以抵抗噪聲對預測結果的影響，如何挖掘多個屬性之間的相關性，提高預測準確率，則亟待后續(xù)的深入系統(tǒng)研究。