基于徑向基神經(jīng)網(wǎng)絡(luò)的Web Service QoS屬性值組合預測方法

劉宗磊，莊 媛，張鵬程

(河海大學計算機與信息學院，江蘇 南京 211100)

0 引言

隨著面向服務(wù)計算技術(shù)的日趨成熟，網(wǎng)絡(luò)上出現(xiàn)了大量功能相同或相近而服務(wù)質(zhì)量有很大差別的Web Service，其中QoS 成為評價和選擇Web Service的重要依據(jù)［1］。而Web Service 是通過Internet 網(wǎng)絡(luò)提供服務(wù)，QoS 會隨著網(wǎng)絡(luò)環(huán)境、服務(wù)器負載等因素的變化而變化［2-4］。通過分析歷史QoS 觀察值(通常通過監(jiān)控服務(wù)執(zhí)行收集［5］)，可以在Web Service 發(fā)生失效前做出反應，選擇出正確的候選服務(wù)或者對現(xiàn)有服務(wù)做出調(diào)整，從而防止這些失效發(fā)生或者減少它們帶來的影響。

當前Web Service QoS 預測方法主要分為3 類:

1)基于相似度的QoS 預測方法。Shao［6］等在2007 年最早提出使用協(xié)同過濾法對用戶未使用過的QoS 進行預測。該方法只考慮用戶之間的相似度，而沒有考慮Web 服務(wù)之間的相似度，使得預測效果不太理想;Zheng［7］等提出了一種基于混合協(xié)同過濾方法的QoS 預測方法。該方法設(shè)計了2 種信心權(quán)重，其中一種信心權(quán)重表示對基于用戶之間相似度得到的QoS 預測值的信任程度，另一種信心權(quán)重表示對基于服務(wù)之間相似度得到的QoS 預測值的信任程度。

2)基于人工智能的QoS 預測方法。Liu［8］等提出了一種基于BP (Back-Propagation)神經(jīng)網(wǎng)絡(luò)的QoS預測方法。但BP 神經(jīng)網(wǎng)絡(luò)存在收斂速度慢、識別精度不確定和過學習等問題。Zhang［9］等提出了一種基于RBF 神經(jīng)網(wǎng)絡(luò)的QoS 短期預測方法。該方法具有結(jié)構(gòu)自適應性、網(wǎng)絡(luò)設(shè)計簡單、訓練時間短等優(yōu)點，但該方法的訓練神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)缺乏在線更新機制。

3)基于時間序列的QoS預測方法［10-12］。Amin［13］等提出一種基于線性非線性時間序列的自動預測QoS 屬性值方法，該方法自動將數(shù)據(jù)區(qū)分為線性和非線性2 種類型，提高了精確度，但在確定部分模型參數(shù)時，該方法默認了相同值，不能很好地建立高精度預測模型。

針對以上問題，本文提出一種以RBF 神經(jīng)網(wǎng)絡(luò)方法作為基礎(chǔ)的Web Service QoS 組合預測方法。首先進行數(shù)據(jù)處理，由于Web Service QoS 具有高動態(tài)性和非線性的特征，根據(jù)其具體數(shù)據(jù)特征，建立差分自回歸移動平均模型(Autoregressive Integrated Moving Average，ARIMA)［14］或自激勵門限自回歸移動平均模型(Self-Exciting Threshold Autoregressive Moving Average，SETARMA)［15］進行建模預測;同時，利用灰色模型無需考慮變化規(guī)律、分布規(guī)律的優(yōu)點，采用灰色等維新息模型［16］進行建模預測。最后建立RBF神經(jīng)網(wǎng)絡(luò)模型，將時間序列模型和灰色預測模型得到的結(jié)果作為輸入源傳遞給RBF 神經(jīng)網(wǎng)絡(luò)模型，訓練模型，并進行QoS 相關(guān)屬性值的預測。

1 一種基于RBF 神經(jīng)網(wǎng)絡(luò)的組合預測方法

圖1 組合模型構(gòu)建

本文提出的Web Service QoS 組合預測方法，如圖1 所示。該方法由3 部分組成:

1)時間序列模型。用時間序列預測模型從統(tǒng)計學角度進行數(shù)據(jù)分析，針對時間序列的線性和非線性特征，分別采用ARIMA 模型與SETARMA 模型進行預測。

2)灰色預測模型。通過灰色等維新息模型模擬出整個QoS 屬性值發(fā)展趨勢。對即使有數(shù)據(jù)缺失的情況，亦可建立高效的灰色預測模型進行預測。

3)RBF 神經(jīng)網(wǎng)絡(luò)模型。將模型1)和模型2)的預測結(jié)果輸入，形成組合預測模型。通過綜合利用各種方法提供的有用信息，有利于提高輸入質(zhì)量，以期組合預測模型在效率、質(zhì)量上優(yōu)于單一模型，產(chǎn)生更好的預測結(jié)果。

Web Service QoS 指標主要有響應時間(Response time)、可用性(Availability)、可靠性(Reliability)、代價(Cost)、帶寬(Band Width)等，本文以服務(wù)的響應時間為例進行預測。

1.1 時間序列模型

對響應時間x(rt)進行時間序列建模。

1.1.1 數(shù)據(jù)預處理

1)白噪聲檢驗，使用游程檢驗法進行，原假設(shè)H0表示時間序列為純隨機序列，當p-value ＜0.05 時則拒絕原假設(shè)，即序列不是純隨機序列，繼續(xù)下一步驟，若p-value ＞0.05 則接受原假設(shè)，即為純隨機序列，無預測意義;

2)正太分布檢驗，當非正太分布時用Box-Cox［13］進行近似轉(zhuǎn)換;

3)穩(wěn)定性檢測，使用ADF 檢驗法。對于非平穩(wěn)序列，可以逐次作差分直至轉(zhuǎn)換為平穩(wěn)序列。

1.1.2 建立模型

1)ARIMA 模型。

Step1 通過序列的自相關(guān)系數(shù)(Autocorrelationfunction，ACF)和偏自相關(guān)系數(shù)(Partial Autocorrelation Function，PACF)，確定參數(shù)q(移動平均模型階數(shù))和p(自回歸模型階數(shù))，其規(guī)律如表1 所示。

表1 AR/MA 模型識別方法

Step2 根據(jù)AIC 信息準則(Akaike Information Criterion，AIC)選擇AIC 信息值最小的模型，公式如下:

其中k 是參數(shù)的數(shù)量，L 是似然函數(shù)。

Step3 對模型進行顯著性檢驗，即為殘差序列的純隨機性檢驗，使用Ljung-Box(LB)統(tǒng)計量(也稱Q-統(tǒng)計量)進行檢驗，公式如下:

其中，rj是j 階自相關(guān)系數(shù)，T 是觀測值的個數(shù)。如不滿足則返回Step2 重新選擇。

2)SETARMA 模型。

通常選取門限空間個數(shù)l=2，此時門限值r 使用黃金分割搜索算法求得，即每次均以相同的比率0.618不斷縮小極值點所在的區(qū)間。將x(rt)按升序排列，初始區(qū)間為［x(π*(n-1))，x((1-π)*(n-1))］，其中π取值0.15，n 為樣本數(shù)。對于門限變量和延遲參數(shù)，選取不同的延遲參數(shù)(取小于等于ARIMA 模型中p的所有非負整數(shù))，在各個門限區(qū)間分別建立ARIMA模型，采用改進的AIC 準則選取最小值確定，公式如下:

1.1.3 選擇模型

對所求ARIMA 模型和SETARIMA 模型進行預測，選擇相對誤差均值(MSPE)和均方根誤差(RMSE)較小的模型，并將預測結(jié)果yts(rt)傳給RBF模型。

1.2 灰色預測模型

所述灰色預測模型中，即使某些數(shù)據(jù)信息缺失，依然可以采用GM(1，1)模型構(gòu)建可信的預測過程。使用GM(1，1)等維新息模型，即每補充一個新信息的同時，去掉一個最老的信息。同樣，以響應時間x(rt)作為原始數(shù)據(jù)。為減小波動性影響，以及與時間序列模型統(tǒng)一單位，同樣對x(rt)做對數(shù)變換得xlog2(rt)，以ygrey(rt)為預測輸出。通過計算，可以得到t+1 時刻的響應時間，此結(jié)果將傳遞給RBF 神經(jīng)網(wǎng)絡(luò)模型作為輸入。

1.3 RBF 神經(jīng)網(wǎng)絡(luò)模型

當時間序列模型和灰色預測模型建立好后，將得到的2 組數(shù)據(jù)(yts(rt)，ygrey(rt))作為輸入源傳遞給RBF 神經(jīng)網(wǎng)絡(luò)模型，同時以相同時刻的觀測值作為輸出值訓練神經(jīng)網(wǎng)絡(luò)。利用訓練好的RBF 網(wǎng)絡(luò)進行QoS 預測，并可利用最新的樣本集修正RBF 網(wǎng)絡(luò)繼續(xù)進行QoS 預測。

2 實 驗

2.1 實驗設(shè)置

本實驗使用數(shù)據(jù)為近2 個月時間筆者收集的4個Web 服務(wù)(分別為Domestic FlightSchedule，TV List，Captcha Code，RMB Instant Quotation)的響應時間，分別使用文獻［13］提出的基于時間序列模型的QoS 預測法，文獻［9］提出的基于RBF 模型的預測法和本文提出的組合預測方法進行預測和分析。在建立模型之前，對所有數(shù)據(jù)做對數(shù)變換。

4 個服務(wù)為每日的8:00 到17:00，間隔15 分鐘一次的記錄值，各采集2 000 個數(shù)據(jù)，如圖2 所示，其中1 900 個作為訓練樣本，其余100 個作為測試樣本。時間序列模型中，以1 000 為滑動窗口;灰色預測模型中，由于數(shù)據(jù)波動性較大，使用灰色等維新息模型，調(diào)整不同大小的滑動窗口。將時間序列模型和灰色預測模型預測的900 個數(shù)據(jù)作為RBF 神經(jīng)網(wǎng)絡(luò)的訓練樣本。

圖2 自測4 個服務(wù)的響應時間

2.2 實驗結(jié)果與分析

2.2.1 實驗結(jié)果

模型通過實驗建立了Domestic FlightSchedule，TV List，Captcha Code，RMB Instant Quotation 4 個服務(wù)的基于RBF 神經(jīng)網(wǎng)絡(luò)的組合預測模型(RBFC)時間序列和RBF 模型，預測的結(jié)果見圖3。

圖3 4 組Web Service 的組合預測模型與時間序列模型預測結(jié)果

從圖中可以看出，組合模型預測結(jié)果比RBF 模型預測結(jié)果有顯著提高，在一定程度上比時間序列模型更加精確。由于灰色預測模型只適用于單調(diào)性樣本數(shù)據(jù)，小窗口灰色等維新息模型的建立則可以彌補這一缺點，同時能夠更加準確地刻畫整體規(guī)律。

2.2.2 模型評估

根據(jù)預測結(jié)果對模型進行評估:

為了更直觀地比較組合預測模型和時間序列模型的預測結(jié)果，對3 個指標(MSPE，RMSE 和Proerror＜p)進行列表分析，計算結(jié)果如表2 所示。

1)相對誤差均值(MSPE):

其中N 為預測結(jié)果的個數(shù)，yi為第i 個實際觀測值，為第i 個預測值(以下N，yi，意義相同)。MSPE反映預測值偏離實際值的程度。

2)均方根誤差(RMSE):

RMSE 不僅反映相對誤差的大小，還反映預測結(jié)果的穩(wěn)定性。

3)相對誤差概率分布:

表2 自測4 個Web 服務(wù)預測結(jié)果指標比較

表2 中，提高值1 為組合模型較時間序列模型的精度提高，提高值2 為組合模型較RBF 模型的精度提高。從表中可以看出，組合模型與RBF 模型相比，在指標MAPE，RMSE 和下的預測結(jié)果均有顯著提高;與時間序列模型相比，預測值的相對誤差在0.01 以下均有所提高，但RMB Instant Quotation 數(shù)據(jù)集的組合預測模型的MSPE 和RMSE 值比時間序列結(jié)果略大，這可能是由于該數(shù)據(jù)集特征不適于灰色預測模型所致。

為了直觀描述相對誤差及相對誤差分布情況，采用箱線圖進行比較，如圖4 所示。

圖4 中，縱坐標表示相對誤差絕對值，分別為4組自測數(shù)據(jù)使用時間序列模型與組合模型預測結(jié)果的誤差分布。從圖中可以看出，基于RBF 神經(jīng)網(wǎng)絡(luò)的組合模型誤差分布的異常值均少于時間序列模型，且分布區(qū)間更加集中，這表明基于RBF 神經(jīng)網(wǎng)絡(luò)的組合模型預測結(jié)果更加穩(wěn)定與精確。

圖4 自測4 組數(shù)據(jù)誤差分布箱線圖

3 結(jié)束語

本文在前人研究成果的基礎(chǔ)上，結(jié)合時間序列模型與徑向基神經(jīng)網(wǎng)絡(luò)模型的優(yōu)點，并加入灰色等維新息模型，建立了基于徑向基神經(jīng)網(wǎng)絡(luò)模型的組合預測模型。與已有方法相比，在時間序列模型的建模過程中，并沒有統(tǒng)一線性、非線性模型的參數(shù)p 和q 的值，并對SETARMA 模型的各個區(qū)間分別求解p 和q 的值，增加了模型的準確性?；疑A測模型與徑向基神經(jīng)網(wǎng)絡(luò)模型均無需考慮規(guī)律變化，且徑向基神經(jīng)網(wǎng)絡(luò)模型可快速建模。通過實驗數(shù)據(jù)表明，組合預測模型在預測精度上有一定的提高。

本文僅根據(jù)線性和非線性2 種特征建立時間序列預測模型，但在對實際QoS 數(shù)據(jù)的分析過程中發(fā)現(xiàn)，其還存在波動性、周期性等特征，因此現(xiàn)有的方法在精度上仍可提高。未來將進一步研究時間序列模型中多特征識別，以及徑向基神經(jīng)網(wǎng)絡(luò)模型的優(yōu)化算法，同時，考慮加入?yún)f(xié)同過濾的方法，引入環(huán)境因素等的影響。

［1］馬友，王尚廣，孫其博，等.一種綜合考慮主客觀權(quán)重的Web 服務(wù)QoS 度量算法［J］.軟件學報，2014，25(11):2473-2485.

［2］華哲邦，李萌，趙俊峰，等.基于時間序列分析的Web Service QoS 預測方法［J］.計算機科學與探索，2013，7(3):218-226.

［3］Tselentis G，Domingue J，Galis A，et al.Towards the Fu-ture Internet:A European Research Perspective［M］.IOS press，2009.

［4］álvarez F，Cleary F，Daras P，et al.Future Internet Assembly 2012:From Promises to Reality［M］.Springer，2012.

［5］Papazoglou M，Pohl K，Parkin M，et al.Service Research Challenges and Solutions for the Future Internet:S-cubetowards Engineering，Managing and Adapting Servicebased Systems［M］.Springer，2010.

［6］Shao Lingshuang，Zhang Jing，Wei Yong，et al.Personalized QoS prediction for web services via collaborative filtering［C］// IEEE International Conference on Web Services.2007:439-446.

［7］Zheng Zibin，Ma Hao，Lyu M R，et al.WSRec:A collaborative filtering based Web service recommender system［C］// Proceedings of the 2009 IEEE International Conference on Web Services.2009:437-444.

［8］劉克非，王紅，許作萍.一種基于服務(wù)質(zhì)量預測的Web服務(wù)選擇方法［J］.計算機技術(shù)與發(fā)展，2007，17(8):103-105.

［9］張金宏，宋杰.基于RBF 神經(jīng)網(wǎng)絡(luò)的Web 服務(wù)QoS 短期預測［J］.遼寧工程技術(shù)大學學報(自然科學版)，2010，29(5):918-921.

［10］Li Mu，Huai Jinpeng，Guo Huipeng.An adaptive Web services selection method based on the QoS prediction mechanism［C］// IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technologies.2009:395-402.

［11］Godse M，Bellur U，Sonar R.Automating QoS based service selection［C］// IEEE International Conference on Web Services (ICWS).2010:534-541.

［12］Cavallo B，Di Penta M，Canfora G.An empirical comparison of methods to support QoS-aware service selection［C］// Proceedings of the 2nd ACM International Workshop on Principles of Engineering Service-Oriented Systems.2010:64-70.

［13］Amin A，Grunske L，Colman A.An automated approach to forecasting QoS attributes based on linear and non-linear time series modeling［C］// Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering (ASE).2012:130-139.

［14］Box G E P，Jenkins G M，Reinsel G C.Time Series Analysis:Forecasting and Control［M］.John Wiley ＆ Sons，2013.

［15］Tong H，Lim K S.Threshold autoregression，limit cycles and cyclical data［J］.Journal of the Royal Statistical Society，Series B (Methodological)，1980，42(3):245-292.

［16］石培基，胡科.等維灰數(shù)遞補模型在人口預測中的應用［J］.統(tǒng)計與決策，2008(6):12-14.

［17］王燕.應用時間序列分析［M］.北京:中國人民大學出版社，2012.