劉澤遠(yuǎn)， 楊孝宗， 舒燕君

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 哈爾濱 150001)

0 引 言

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

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

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

本文研究在論述上，首先探討了該方向的相關(guān)研究工作,并分析了現(xiàn)有工作的優(yōu)缺點(diǎn)；接下來(lái)給出了本文預(yù)測(cè)方法的理論基礎(chǔ)與具體設(shè)計(jì)；然后，將該方法與經(jīng)典的方法展開(kāi)比較實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析；最后總結(jié)全文，進(jìn)而展望未來(lái)的研究工作。

1 相關(guān)研究

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

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

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

2 理論基礎(chǔ)

ARIMA模型與卡爾曼濾波相結(jié)合的關(guān)鍵就是將ARIMA模型轉(zhuǎn)換成狀態(tài)空間模型，再使用卡爾曼濾波對(duì)狀態(tài)進(jìn)行預(yù)測(cè)與更新。一個(gè)ARIMA(p,d,q)模型經(jīng)d階差分就可得到ARMA(p,q)模型，數(shù)學(xué)公式可表述如下：

(1)

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

(2)

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

φ(B)Zt=θ(B)at

(3)

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

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

(4)

化簡(jiǎn)公式(4)，就會(huì)得到ψm的數(shù)學(xué)運(yùn)算公式可見(jiàn)如下：

(5)

由此，可以將Zt+m-i=ψ(B)at+m-i表達(dá)式展開(kā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，觀測(cè)值Zt=Zt|t-1+at，觀測(cè)方程即可表示為：

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

(10)

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

St+1=FSt+Gat

(11)

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

(12)

綜上就是模型ARMA(p,q)轉(zhuǎn)移到狀態(tài)空間模型的推導(dǎo)過(guò)程，在得到狀態(tài)空間模型后，就可轉(zhuǎn)入卡爾曼濾波的應(yīng)用設(shè)計(jì)的研究。

3 方法設(shè)計(jì)

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

圖1 預(yù)測(cè)方法概覽

3.1 ARIMA模型建立

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

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

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

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

3.2 卡爾曼濾波預(yù)測(cè)

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

St+1|t=FSt|t

(13)

Pt+1|t=FPt|tFT+GQGT

(14)

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

Zt+1|t=HSt+1|t

(15)

得到觀測(cè)值Zt+1，可以對(duì)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就是卡爾曼增益矩陣，通過(guò)最小化預(yù)測(cè)誤差的后驗(yàn)協(xié)方差矩陣計(jì)算得出，計(jì)算結(jié)果決定了狀態(tài)向量受到觀測(cè)值的影響程度。

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

4 實(shí)驗(yàn)

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

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

圖2 ARIMA預(yù)測(cè)值與實(shí)際值

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

圖3 卡爾曼濾波預(yù)測(cè)值與實(shí)際值

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

(18)

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

5 結(jié)束語(yǔ)

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

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

(1)時(shí)間序列的噪聲。噪聲會(huì)對(duì)序列本身信息的挖掘產(chǎn)生影響，而去噪方法的選擇也將涉及多方面的因素考證，因此為Web服務(wù)的QoS序列進(jìn)行合理去噪，將會(huì)是未來(lái)的研究熱點(diǎn)。

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