張鵬程, 王麗艷, 吉順慧, 李雯睿

1(河海大學(xué) 計算機與信息學(xué)院,江蘇 南京 211100)

2(南京曉莊學(xué)院 信息工程學(xué)院,江蘇 南京 211171)

隨著Web服務(wù)技術(shù)的快速發(fā)展和應(yīng)用,網(wǎng)絡(luò)上出現(xiàn)很多功能相似的Web服務(wù),在選擇滿足用戶需求的Web服務(wù)過程中,非功能性需求往往被人們忽視[1].近幾年來,作為非功能性因素的QoS逐步被人們重視[2].Web服務(wù)由Internet網(wǎng)絡(luò)提供,因為網(wǎng)絡(luò)環(huán)境等因素的變化而受到影響,因此,真實網(wǎng)絡(luò)的QoS具有非線性、動態(tài)多變的特點,選擇服務(wù)前提供有效的服務(wù)QoS信息顯得格外重要[3,4].

目前,越來越多的研究人員開始致力于Web服務(wù)QoS預(yù)測技術(shù),在服務(wù)功能滿足用戶需求的情況下,為用戶選擇服務(wù)或避免服務(wù)故障提供了技術(shù)支持.現(xiàn)有的預(yù)測模型根據(jù)預(yù)測技術(shù)可以分為基于結(jié)構(gòu)方程(structural equation)的QoS預(yù)測方法[5,6]、基于相似度的QoS預(yù)測方法[7,8]、基于人工智能的QoS預(yù)測方法[9,10]和基于時間序列的QoS預(yù)測方法[11]等.

(1) 基于結(jié)構(gòu)方程的QoS預(yù)測方法根據(jù)QoS的過去值分析當(dāng)前值變化趨勢,該方法可以分析屬性的內(nèi)部關(guān)系,但不能預(yù)測具體值[5].Le等人[6]根據(jù)單個屬性歷史信息的趨勢,提出了一種 QoS定量預(yù)測法,但只能預(yù)測屬性的變化情況,預(yù)測值不準(zhǔn)確;

(2) 基于相似度的QoS預(yù)測方法是利用使用過該Web服務(wù)的用戶的QoS,根據(jù)相似度預(yù)測其他未使用者或該用戶使用的其他服務(wù)的QoS[12].最早由Shao等人[7,8]提出,使用協(xié)同過濾法(collaborative filtering approach),根據(jù)用戶相似度預(yù)測未使用過的服務(wù)QoS.該類方法具有預(yù)測模型簡單、速度快的特點,但是只能用于單一功能且任務(wù)確定的Web服務(wù);

(3) 基于人工智能的 QoS預(yù)測方法具有很強的自適應(yīng)能力和實時預(yù)測能力[9,10],能夠預(yù)測復(fù)雜的非線性的QoS屬性值.Liu等人[13]提出一種基于BP(back-propagation)神經(jīng)網(wǎng)絡(luò)的Web服務(wù)QoS預(yù)測方法,在訓(xùn)練速度、預(yù)測精度方面并不完善,大多數(shù)模型都存在訓(xùn)練速度慢、時效性差等缺點,并沒有很好地發(fā)揮智能方法的優(yōu)點.Fan等人[10]提出了一種基于遺傳編程(genetic programming,簡稱 GP)的 QoS屬性預(yù)測方法,動態(tài)預(yù)測QoS屬性值,預(yù)測精度較好,但是預(yù)測步長短;

(4) 基于時間序列的QoS預(yù)測方法主要利用QoS屬性的時間維序列構(gòu)建模型,隨時間變化預(yù)測未來QoS的屬性值.該類方法最早用于經(jīng)濟、金融等領(lǐng)域[14],主要基于ARIMA(autoregressive integrated moving average)等模型[15],因為時間序列方法具有精確度相對較高、時效性強的優(yōu)點,后來逐漸擴展到其他領(lǐng)域,但仍然存在預(yù)測周期短、隨周期變長誤差逐漸變大的缺點.Ye等人[16]提出了一種基于多元時間序列的QoS長期預(yù)測方法,構(gòu)建了屬性關(guān)系式,基于ARIMA和Holt-Winters建立長期預(yù)測模型,該方法只適用于靜態(tài)預(yù)測,動態(tài)性較差.

根據(jù)上述分析,當(dāng)前Web服務(wù)QoS預(yù)測方法存在問題歸納如下.QoS屬性間的相互影響考慮不充分.QoS屬性主要包括響應(yīng)時間、吞吐量、可靠性、可用性、價格等[17].它們之間存在錯綜復(fù)雜的關(guān)系.例如：當(dāng)響應(yīng)時間變大時吞吐量變小,可擴展性對可靠性也產(chǎn)生影響,屬性間的關(guān)系無法用準(zhǔn)確的公式模型表示[6],自行構(gòu)建的關(guān)系式往往隨著數(shù)據(jù)樣本的改變而發(fā)生變動,大部分只針對目標(biāo)屬性的歷史數(shù)據(jù)預(yù)測未來值,存在 QoS屬性信息不足的缺點,影響預(yù)測周期和準(zhǔn)確性;預(yù)測步長較小,多步預(yù)測效果不好.Web服務(wù)QoS的整體發(fā)展趨勢隨服務(wù)提供商的策略變化具有動態(tài)多變的特性,直接利用目標(biāo)屬性的歷史數(shù)據(jù)做多步直接預(yù)測不能保證預(yù)測的精確度.對于企業(yè)或用戶長期使用的 Web服務(wù),需要多步長預(yù)測未來 Web服務(wù)質(zhì)量,因此,多步預(yù)測具有重要的研究意義;動態(tài)性差.Web服務(wù) QoS屬性值具有動態(tài)多變的特點,目前,大多數(shù)模型根據(jù)歷史數(shù)據(jù)建立固定模型,沒有考慮隨數(shù)據(jù)的更新、動態(tài)改變模型參量,在實際預(yù)測中缺乏實用性.

為解決上述問題,本文提出一種新穎的基于多元時間序列的 Web服務(wù) QoS預(yù)測方法,簡稱 MulA-LMRBF(multiple step forecasting with advertisement-levenberg marquardt radial basis function).一方面,對于用戶長期使用的 Web服務(wù),從長遠(yuǎn)角度預(yù)測服務(wù)質(zhì)量;另一方面,單元時間序列包含的非線性系統(tǒng)信息較少,適合短期單步預(yù)測穩(wěn)定且功能簡單的服務(wù).多元時間序列中包含較多的QoS信息,相空間(phase space)重構(gòu)后比單元時間序列包含更多的系統(tǒng)動態(tài)信息,因此采用多元時間序列實現(xiàn)QoS動態(tài)多步預(yù)測.總體來說,本文貢獻主要包括如下4個方面.

(1) 針對問題1),考慮QoS屬性間存在復(fù)雜的聯(lián)系,采用相空間重構(gòu)方法,將時間序列上每個QoS屬性歷史數(shù)據(jù)映射到一個動力系統(tǒng)中,近似恢復(fù)序列原來的多維非線性系統(tǒng).重構(gòu)后的時間序列包含更多QoS屬性動態(tài)信息,屬性之間的關(guān)聯(lián)可以通過非線性系統(tǒng)描述,使預(yù)測更具動態(tài)性和準(zhǔn)確性;

(2) 針對問題2),因為短期 QoS廣告數(shù)據(jù)(advertisement data)是根據(jù)服務(wù)未來的趨勢發(fā)布,代表當(dāng)前 QoS屬性值的走向.將模擬生成的短期服務(wù)提供商的QoS廣告數(shù)據(jù)加入到預(yù)測數(shù)據(jù)集中,輔助實現(xiàn)多步預(yù)測,提高預(yù)測精度;

(3) 針對問題3),利用LM算法改進的RBF神經(jīng)網(wǎng)絡(luò)模型(LMRBF)[18,19]實現(xiàn)動態(tài)預(yù)測,該模型以黑盒模式描述輸入變量與預(yù)測變量之間的復(fù)雜關(guān)系,利用LM最優(yōu)化算法訓(xùn)練權(quán)值,提高運算效率,但是迭代訓(xùn)練權(quán)值的運算不夠優(yōu)化.本文進一步優(yōu)化LMRBF方法,減小了時間開銷和空間開銷,相對準(zhǔn)確地預(yù)測屬性值.針對QoS動態(tài)多變的特點,每采集一新樣本動態(tài)更新神經(jīng)網(wǎng)絡(luò)的參數(shù)值,實現(xiàn)動態(tài)預(yù)測;

(4) 在提出方法的基礎(chǔ)上,利用開源數(shù)據(jù)集和自測數(shù)據(jù)實現(xiàn)相關(guān)實驗.實驗驗證了相空間重構(gòu)和廣告數(shù)據(jù)對預(yù)測的影響以及 MulA-LMRBF方法在多步動態(tài)預(yù)測中的有效性,與其他方法比較,在預(yù)測準(zhǔn)確度方面有明顯提高.

本文第1節(jié)介紹方法運用的背景知識和相關(guān)的理論基礎(chǔ).第2節(jié)介紹本文提出的預(yù)測方法MulA-LMRBF.第3節(jié)給出實驗設(shè)計和結(jié)果分析.第4節(jié)對本文工作加以總結(jié)和展望.

1 預(yù)備知識

1.1 相空間重構(gòu)

非線性時間序列可以看做由確定的非線性系統(tǒng)產(chǎn)生的,相空間是描述系統(tǒng)運動和演變最有力的工具之一,可以表示動力系統(tǒng)中所有可能的狀態(tài),其中每個狀態(tài)具有對應(yīng)的相位空間點,從而刻畫了一個點隨時間變化的情況.目前,很多研究人員選擇相空間重構(gòu)(phase-space reconstruction)處理非線性時間序列,近似恢復(fù)序列構(gòu)成的動力系統(tǒng).相空間重構(gòu)最早是由Takens[20]提出,相空間重構(gòu)定理認(rèn)為：系統(tǒng)中任意變量的發(fā)展都是由與之相互作用的其他變量決定的,相關(guān)變量的信息隱含在其他變量的發(fā)展過程中,當(dāng)選擇的嵌入維恰當(dāng)時就可以重構(gòu)序列的原系統(tǒng)[18,21].

樣本個數(shù)為N,屬性個數(shù)為M的多元時間序列表示為X={X1,X2,…,Xi,…,XN},其中,i∈{1,2,…,N}.多元時間序列X的每個數(shù)據(jù)樣本代表每個時間點的值,表示為Xi=[xi,1,xi,2,…,xi,j,…,xi,M],其中,j∈{1,2,…,M},j表示第j個屬性,Xi表示第i個時間點的樣本數(shù)據(jù),xi,j表示第i個時間點第j個屬性的值.

其中,mj表示第j個屬性的嵌入維數(shù),τj表示第j個屬性的延遲時間.

1.1.1 平均位移法

平均位移法[22]是同時考慮嵌入維數(shù)和延遲時間的相空間重構(gòu)方法,思想是：通過引入平均位移(AD),給每個屬性一個假設(shè)嵌入維數(shù)m,求延遲時間τ.平均位移的求解公式為

即：隨機給某一屬性賦值嵌入維數(shù)m,求對應(yīng)的〈Sm(τj)〉.原始的平均位移法原則是：當(dāng)〈Sm(τj)〉的增長斜率第 1次降為初始值的 40%時,對應(yīng)的點為所求的延遲時間.本文采用前人改進的平均位移法[23],即：隨著τj值增加,〈Sm(τj)〉的第 1個峰值點對應(yīng)的τj就是所求的延遲時間.

1.2 LM算法

列文伯格-馬夸爾特法(Levenberg-Marquardt,簡稱 LM)[24]是一種使用廣泛的最優(yōu)化方法,是牛頓法(Newton's method)和梯度下降法(gradient descent)的折中,通過迭代調(diào)整未知變量,求解二階函數(shù)f(W)的最優(yōu)值,具有收斂速度快的優(yōu)點.

令W為L個變量組成的向量,W=[w1,w2,…,wi,…,wL].求解最優(yōu)值的過程中,作用于向量W的最優(yōu)調(diào)整量ΔW的計算公式為ΔW=(H+λI)-1g,其中,H為多元函數(shù)f(W)二階偏導(dǎo)構(gòu)成的Hessian矩陣,可以表示為

I為與H同維的單位矩陣,λ為正則系數(shù),g為函數(shù)的梯度向量.為了化簡由Hessian矩陣計算帶來的復(fù)雜性,采用近似二階偏導(dǎo),忽略二階以上的導(dǎo)數(shù)項代替二階偏導(dǎo)[25].假設(shè)二階函數(shù)f(W)的優(yōu)化由如下代價函數(shù)產(chǎn)生：

dt表示真實值,g(Xt,W)是dt的逼近函數(shù),那么f(W)的近似二階偏導(dǎo)數(shù)項可以表示為

其中,i∈{1,2,…,L},j∈{1,2,…,L},N是訓(xùn)練樣本個數(shù).在迭代訓(xùn)練的過程中,除了每次計算權(quán)值調(diào)整量ΔW以外,也為正則系數(shù)λ分配足夠大的值,保證H+λI正定,盡快收斂到最優(yōu)解[25].

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

RBF神經(jīng)網(wǎng)絡(luò)由Moody和Darken根據(jù)人體大腦皮層的感知區(qū)域特點提出的一種前饋型神經(jīng)網(wǎng)絡(luò),網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示,通常包括輸入層、隱含層和輸出層[26].其中,第1層輸入層由感知神經(jīng)元組成,將輸入向量X引入神經(jīng)網(wǎng)絡(luò),其中,X=[X1,X2,…,Xi,…,Xn],n表示輸入層神經(jīng)元個數(shù);第2層隱含層把輸入向量從低維映射到高維,實現(xiàn)高維曲線擬合,通常隱含層激勵函數(shù)選擇徑向基函數(shù)φ(X);最后一層是輸出層,將隱含層的輸出進行線性加權(quán)組合作為最終輸出值,記為Y.

當(dāng)輸入樣本為n時,輸入層節(jié)點數(shù)為n(n?N*),隱層節(jié)點個數(shù)為L,采用單輸出,即輸出層節(jié)點個數(shù)為1.

2 一種基于多元時間序列的Web Service QoS預(yù)測方法

本文從多元時間序列的角度分析QoS數(shù)據(jù),提出一種動態(tài)Web服務(wù)QoS預(yù)測方法MulA-LMRBF,著重于多屬性的數(shù)據(jù)分析和神經(jīng)網(wǎng)絡(luò)模型的改進,流程描述如圖2所示.

用戶或企業(yè)需要長期使用的Web服務(wù)可能由于動態(tài)的Internet網(wǎng)絡(luò)變化產(chǎn)生短期或周期性的QoS變化,甚至發(fā)生服務(wù)故障,需要從長遠(yuǎn)角度預(yù)測服務(wù)的 QoS,為用戶選擇 Web服務(wù)提供真實可靠的服務(wù)質(zhì)量數(shù)據(jù).MulA-LMRBF方法充分利用QoS屬性的歷史數(shù)據(jù)信息并動態(tài)預(yù)測未來屬性的具體值,主要概括為3個步驟.

· QoS data collection and processing：確定QoS屬性個數(shù),選擇QoS屬性完備的樣本作為實驗數(shù)據(jù).收集的數(shù)據(jù)包括歷史數(shù)據(jù)和短期廣告數(shù)據(jù),分別對兩部分?jǐn)?shù)據(jù)進行預(yù)處理,歷史數(shù)據(jù)處理包括數(shù)據(jù)噪聲處理、尺度變換和相空間重構(gòu),廣告數(shù)據(jù)僅尺度變換,從而形成綜合的QoS數(shù)據(jù)序列;

· Model training：設(shè)定隱層節(jié)點個數(shù)等初始化參數(shù),通過最優(yōu)化訓(xùn)練樣本的誤差函數(shù)f(W),采用改進方法訓(xùn)練神經(jīng)網(wǎng)絡(luò)隱含層和輸出層間的權(quán)值W,進一步優(yōu)化W的更新計算過程,達到高效訓(xùn)練的效果;

· QoS dynamic forecasting：當(dāng)訓(xùn)練樣本滿足誤差函數(shù)f(W)的閾值要求時訓(xùn)練結(jié)束,獲取下一條新樣本,對其預(yù)處理并保存預(yù)測結(jié)果.為實現(xiàn)動態(tài)預(yù)測,計算其εk和βk,調(diào)整一次權(quán)值W.

2.1 數(shù)據(jù)收集和預(yù)處理

數(shù)據(jù)主要來自公開數(shù)據(jù)集和自測數(shù)據(jù)[16,27],分別對歷史數(shù)據(jù)和廣告數(shù)據(jù)兩部分進行預(yù)處理,具體由以下步驟組成.

(1) 歷史數(shù)據(jù)(QoS history data)噪聲處理

QoS歷史數(shù)據(jù)含有大量噪聲,噪聲會隨時間演化和后續(xù)計算造成精度損失,并且相空間重構(gòu)時間序列模型對數(shù)據(jù)噪聲很敏感,含噪聲數(shù)據(jù)會嚴(yán)重影響預(yù)測準(zhǔn)確度,因此采用非線性小波變換閾值去噪法(nolinear wavelet transform threshold denoising approach)[28-30]處理QoS歷史數(shù)據(jù).

(2) 數(shù)據(jù)尺度變換(scale transformation)

神經(jīng)網(wǎng)絡(luò)輸入變量在[0,1]或[-1,1]時,網(wǎng)絡(luò)運算效果較好[9],因此對數(shù)據(jù)進行尺度變換處理,將 QoS屬性歷史數(shù)據(jù)和QoS廣告數(shù)據(jù)都控制在[0,1]之間.尺度變換公式為

其中,i∈{1,2,…,N},j∈{1,2,…,M},x·,j是 QoS 第j個屬性的所有值,(x·,j)max是x·,j的最大值,(x·,j)min是x·,j的最小值.

(3) 歷史數(shù)據(jù)相空間重構(gòu)模型(phase-space reconstruction)

QoS歷史數(shù)據(jù)相空間重構(gòu),首先采用平均位移法確定重構(gòu)的嵌入維數(shù)m和延遲時間τ,m從[1,30]取值,用公式(1)計算每個QoS屬性的m對應(yīng)的〈Sm(τj)〉,取〈Sm(τj)〉到達第1個峰值對應(yīng)的τ.然后均衡多個屬性的m對應(yīng)的τ值,選擇所有屬性的m對應(yīng)τ達到平穩(wěn)狀態(tài)區(qū)間之內(nèi)的值作為相空間重構(gòu)的嵌入維數(shù)和延遲時間.

其中,i∈{1,2,…,N},相空間重構(gòu)時選擇的數(shù)據(jù)樣本個數(shù)為N,屬性個數(shù)為M,分別為每個屬性計算合適的m和τ.例如,假設(shè)某一Web服務(wù)的響應(yīng)時間(response time,簡稱RT)的嵌入維數(shù)為2,延遲時間為1,可靠性(reliability,簡稱R)的嵌入維數(shù)為2,延遲時間為2,在t時刻去噪和尺度變換后的數(shù)據(jù)Qt為Qt=[RTt,Rt],Qt相空間重構(gòu)后為[RTt,RTt-1,RTt-2,Rt,Rt-2,Rt-4].重構(gòu)后的Qt′充分利用歷史數(shù)據(jù)樣本,近似恢復(fù)RT和R屬性共同的原數(shù)據(jù)關(guān)系系統(tǒng),比原數(shù)據(jù)Qt包含更多QoS屬性的動態(tài)信息,因此我們將相空間重構(gòu)后的歷史數(shù)據(jù)用于QoS的動態(tài)多步預(yù)測.

Qt′=

(4) QoS綜合數(shù)據(jù)序列(QoS integrated data serirs)

2.2 LM算法改進的RBF神經(jīng)網(wǎng)絡(luò)預(yù)測模型

LM算法改進的RBF神經(jīng)網(wǎng)絡(luò)主要利用LM算法的最優(yōu)化思想,訓(xùn)練網(wǎng)絡(luò)隱含層與輸出層權(quán)值W.QoS綜合數(shù)據(jù)序列的數(shù)據(jù)作為輸入,隱含層節(jié)點個數(shù)固定不變,輸出層節(jié)點個數(shù)為 1,因此隱含層與輸出層權(quán)值最優(yōu)時,網(wǎng)絡(luò)的實際輸出值與真實值最接近.我們利用 LMRBF網(wǎng)絡(luò)的優(yōu)點并進一步改進,實現(xiàn)高效訓(xùn)練和動態(tài)預(yù)測的目標(biāo),提高預(yù)測精度.

RBF神經(jīng)網(wǎng)絡(luò)模型[31]的輸入為Xi,輸出為Yi,隱含層激勵函數(shù)選擇高斯函數(shù),其公式為

其中,i∈{1,2,…,N},N表示樣本個數(shù),k∈{1,2,…,L},L表示隱含層節(jié)點數(shù),φ(r)為隱含層激勵函數(shù);Ck為RBF神經(jīng)網(wǎng)絡(luò)隱含層中心,σk為第k個隱層節(jié)點的擴展常數(shù),其求解公式為

dk是第k個隱層節(jié)點與其他隱層節(jié)點的最小距離,k和t∈{1,2,…,L},t∈{1,2,…,L},λ是重疊系數(shù),σk是第k個隱層節(jié)點的擴展常數(shù).RBF神經(jīng)網(wǎng)絡(luò)輸出層公式為

其中,i∈{1,2,…,N},W是隱含層與輸出層的權(quán)值向量,W=[w1,w2,...,wL]T,Yi為輸出層函數(shù),wk為第k個隱層節(jié)點與輸出節(jié)點之間的權(quán)值.

(1) 模型訓(xùn)練階段(model training)

模型訓(xùn)練的目的是滿足誤差函數(shù)f(W)盡可能小,直到預(yù)測精度滿足閾值條件.當(dāng)不滿足閾值條件時,迭代更新W的值,使得f(W)達到閾值δ的要求.即f(W)＞δ時,更新權(quán)值W.誤差函數(shù)f(W)的計算公式為

其中,Ti表示樣本真實值,Yi表示RBF神經(jīng)網(wǎng)絡(luò)的實際輸出值,si表示第i個樣本的預(yù)測誤差,則N個訓(xùn)練樣本的預(yù)測值與真實值的誤差矩陣S=[s1,s2,…,si,…,sN].

利用LM算法訓(xùn)練RBF權(quán)值W的過程,見算法1,訓(xùn)練樣本訓(xùn)練時,W迭代更新的公式為

即：通過每次迭代調(diào)整神經(jīng)網(wǎng)絡(luò)權(quán)值,使網(wǎng)絡(luò)輸出值最大程度接近數(shù)據(jù)真實值.公式(13)中,權(quán)值W的調(diào)整量ΔW利用近似二階導(dǎo)數(shù)JTJ代替原來復(fù)雜的Hessian矩陣計算,f(W)的Jacobian矩陣J為

正則化系數(shù)μ的取值在LM算法優(yōu)化未知參量的過程中起決定性的作用,第n次迭代訓(xùn)練,如果f(W)值大于第n-1 次迭代f(W)的值,參數(shù)值μ=μ×a(μ＞0,a＞1);否則μ=μ/a,并更新權(quán)值W.

雖然采用 LM 算法改進 RBF神經(jīng)網(wǎng)絡(luò)訓(xùn)練權(quán)值可以快速地收斂到最優(yōu)解,分析迭代更新公式(12)～公式(14)可知：計算權(quán)值調(diào)整量ΔW需要耗費復(fù)雜的開銷,矩陣J需要存儲所有訓(xùn)練樣本的神經(jīng)網(wǎng)絡(luò)輸出函數(shù),進而才能計算JTJ和JTS,因此,優(yōu)化網(wǎng)絡(luò)訓(xùn)練的主要工作集中到Jacobian矩陣的存儲以及與它相關(guān)的矩陣計算.Wang等人采用LM算法改進ELM神經(jīng)網(wǎng)絡(luò)[18],通過公式改進,進一步優(yōu)化了預(yù)測模型.本文啟發(fā)性地從Jacobian矩陣和相關(guān)矩陣計算等方面優(yōu)化MulA-LMRBF動態(tài)預(yù)測模型：

矩陣J是由全部訓(xùn)練樣本輸出函數(shù)相關(guān)的偏導(dǎo)項構(gòu)成的,因此需要所有訓(xùn)練樣本經(jīng)過一次模型計算才可以進行權(quán)值調(diào)整.我們將預(yù)處理后的N個訓(xùn)練樣本分為db(data block,db≥1)長度的若干段,當(dāng)樣本量達到db時,計算一次誤差函數(shù)f(W)的值并判斷f(W)的閾值條件：滿足條件,則代表本段樣本訓(xùn)練結(jié)束;否則繼續(xù)迭代,直到f(W)≤δ.訓(xùn)練階段重復(fù)執(zhí)行上述步驟,每次判斷新db個樣本的f(W)是否滿足閾值條件,直到全部訓(xùn)練樣本訓(xùn)練結(jié)束.

權(quán)值調(diào)整量過程中,計算JTJ的時間復(fù)雜度為O(n3),JTS的時間復(fù)雜度為O(n2),空間復(fù)雜度為O(n2).進一步簡化計算,Jacobian矩陣中的偏導(dǎo)項?(si)/?wj進一步化簡為

因此,矩陣J可以化簡為Γ的形式：

可以看出,Γ是由神經(jīng)網(wǎng)絡(luò)隱含層的輸出函數(shù)構(gòu)成,每行代表一條樣本經(jīng)過網(wǎng)絡(luò)模型的隱含層輸出.

采用化簡矩陣Γ計算權(quán)值調(diào)整量ΔW,根據(jù)Γ矩陣的特點,依次化簡JTJ和JTS的計算.

a) 首先優(yōu)化計算JTJ,可以用如下公式表示：

b) 然后類比上述優(yōu)化JTS的計算：

其中,εk是第k個樣本對應(yīng)的隱含層輸出向量,sk表示第k個樣本的預(yù)測誤差.

算法1. LM算法改進的RBF神經(jīng)網(wǎng)絡(luò).

初始化：f(W)=0,εk=0,βk=0;db,L,μ,向量W,S隨機賦值;

輸出：更新后的權(quán)值W.

1.f(W1)=f(W); //f(W1) isf(W) in the last iteration

2. Calculateεkandβk;

3.Whencount=dbdo

4. Calculatef(W),W;

5.whilef(W)＞δdo

6.f(W2)=f(W); //f(W2) isf(W) in the this iteration

7. CalculateΔW;

8.iff(W2)＞f(W1)

9.μ=a*μ; //μis the regularization coefficient

10.else

11.μ=μ/a;

12. UpdateW,W=W+ΔW;

13. Calculatef(W);

14.end while

(2) 動態(tài)預(yù)測(QoS dynamic forecasting)

本文采用LM算法改進RBF神經(jīng)網(wǎng)絡(luò)訓(xùn)練權(quán)值W,在時間復(fù)雜度、權(quán)值調(diào)整量計算等方面有明顯改進.模型動態(tài)預(yù)測階段,延續(xù)訓(xùn)練階段采用改進算法訓(xùn)練權(quán)值的思想,輸入新數(shù)據(jù)動態(tài)更新權(quán)值W.每次權(quán)值調(diào)整過程中,正則化系數(shù)μ不斷調(diào)整的作用在于：當(dāng)μ趨近于0時,方法近似于訓(xùn)練速度快的高斯牛頓法,權(quán)值調(diào)整量ΔW調(diào)整地緩慢;當(dāng)μ取值很大時,方法近似于梯度下降法,ΔW調(diào)整幅度大,每迭代成功一步,μ值減小并逐步回歸到高斯牛頓法.

為了使模型動態(tài)長期地預(yù)測 QoS屬性值,訓(xùn)練樣本達到數(shù)量要求,訓(xùn)練結(jié)束后,當(dāng)采集到一條在線數(shù)據(jù)時,首先進行Step 1的步驟處理,形成QoS綜合數(shù)據(jù)序列;經(jīng)過Step 3調(diào)整模型輸出值作為預(yù)測結(jié)果;為實現(xiàn)模型參數(shù)更新,將新數(shù)據(jù)組成樣本對,轉(zhuǎn)向Step 2,計算該樣本的εk和βk,計算最新的db個樣本的誤差函數(shù)f(W),判斷閾值條件,當(dāng)不滿足時,根據(jù)誤差函數(shù)f(W)的增減情況調(diào)整參數(shù)μ以及權(quán)值W.隨著在線數(shù)據(jù)的實時采集,模型參數(shù)不斷更新,適應(yīng)動態(tài)、非線性的QoS預(yù)測要求,從而提高了預(yù)測的準(zhǔn)確性.

3 實 驗

3.1 實驗設(shè)置

本文實驗數(shù)據(jù)主要有5個部分：第1部分(Sourceforge)(https：//sourceforge.net/projects/qosmonitoring/files/)、第 2 部分(http：//www.datatang.com/data/15932)和第 3 部分?jǐn)?shù)據(jù)(http：//www.datatang.com/data/15938)來源于開源數(shù)據(jù)集,第 4部分是筆者采用公開方法(https：//www.ibm.com/developerworks/library/ws-quality/)收集的數(shù)據(jù),第五部分是短期QoS廣告數(shù)據(jù).上述數(shù)據(jù)集,除第3部分采用響應(yīng)時間(response time,簡稱RT)、吞吐量(throughput,簡稱 T)、可靠性(reliability,簡稱 R)和可用性(availability,簡稱 A)這 4個屬性,其他數(shù)據(jù)集主要包含響應(yīng)時間和吞吐量這兩個 QoS屬性,利用多屬性數(shù)據(jù)預(yù)測未來響應(yīng)時間.實驗環(huán)境為 Intel(R) Core(TM) i5-4200U CPU@1.60GHz,4.00GB RAM,Windows 7,matlab 7.11.

其中第1部分?jǐn)?shù)據(jù)的采集時間是每天8：00～17：00,連續(xù)每15分鐘記錄一次Web服務(wù)的響應(yīng)時間和吞吐量,共4個Web服務(wù),取每個Web的連續(xù)2 000條數(shù)據(jù)實驗.以其中一個服務(wù)RMB Instant Quotation為例分析實驗過程和結(jié)果,如圖3(a)所示,為RMB數(shù)據(jù)的曲線圖.第2部分主要來自142臺分布式計算機的4 532個真實Web服務(wù)的QoS數(shù)據(jù),選擇部分Web服務(wù)的數(shù)據(jù)實驗.第3部分是來自150臺分布式計算機,100個Web服務(wù)的監(jiān)控采集結(jié)果,除響應(yīng)時間和數(shù)據(jù)量等信息外,還包括服務(wù)的HTTP信息,反映服務(wù)當(dāng)前可用情況,本實驗根據(jù)HTTP信息、訪問服務(wù)失敗次數(shù)和服務(wù)失效時間,模擬QoS可靠性和可用性.第4部分為作者采集的數(shù)據(jù),選擇多個的Web服務(wù)ID,每個服務(wù)采集時間間隔為10分鐘,每個ID記錄了2 000多個樣本,選擇MobileCode為例進行實驗,原數(shù)據(jù)如圖3(b)所示.由于本文選擇的Web服務(wù)QoS屬性數(shù)據(jù)大部分都是早期采集的,未提供廣告數(shù)據(jù),所以第五部分?jǐn)?shù)據(jù)主要通過模擬生成QoS的響應(yīng)時間廣告數(shù)據(jù),根據(jù)QoS屬性呈現(xiàn)非線性、動態(tài)的特點以及Web服務(wù)呈現(xiàn)的間斷性優(yōu)化的趨勢,在原數(shù)據(jù)的曲線圖上,以一天為周期添加若干趨勢線,與真實數(shù)據(jù)的擬合度控制在50%～70%.

實驗通過均方根誤差(the root mean square error,簡稱RMSE)分析實驗,更直觀地比較不同方法的預(yù)測結(jié)果：

其中,Yi為第i個預(yù)測值,Ti為第i個真實值,N為樣本數(shù)量.RMSE表示預(yù)測相對誤差的大小,反映預(yù)測的穩(wěn)定性.

3.2 實驗過程

希望通過實驗證明使用相空間方法構(gòu)建屬性關(guān)系、采用廣告數(shù)據(jù)提高了多步預(yù)測的準(zhǔn)確度,驗證 QoS多元時間序列適合多步、中長期動態(tài)預(yù)測,通過對比實驗闡明該預(yù)測模型的準(zhǔn)確性.

從數(shù)據(jù)集中選擇若干Web數(shù)據(jù)實驗后,本文分別介紹基于單元時間序列LMRBF預(yù)測方法(S-LMRBF)、基于多元時間序列相空間重構(gòu)的LMRBF預(yù)測方法(Mul-LMRBF)、基于多元時間序列相空間重構(gòu)和帶廣告數(shù)據(jù)的LMRBF預(yù)測方法(MulA-LMRBF)這3組實驗,通過對比觀察相空間重構(gòu)和廣告數(shù)據(jù)對多元多步預(yù)測的影響,驗證多元時間序列在多步、中長期動態(tài)預(yù)測時,比單元時間序列預(yù)測精度高.與傳統(tǒng)靜態(tài)RBF神經(jīng)網(wǎng)絡(luò)預(yù)測方法[26,31]和ARMA預(yù)測方法[32]比較,證明本方法在精確度、動態(tài)多步預(yù)測方面的優(yōu)勢.簡單步驟描述如下.

(1) 將QoS歷史數(shù)據(jù)的多元時間序列進行處理,減少噪聲并變換數(shù)據(jù)尺度,數(shù)據(jù)處理后擾動性減小.如圖4所示,為RMB和MobileCode處理后的結(jié)果;

(2) 對預(yù)處理數(shù)據(jù)進行相空間重構(gòu),利用平均位移法同時考慮m和τ,計算m在[1,40]范圍內(nèi)的每個m對應(yīng)的τ,如圖5(a)和圖5(b)所示：隨著m的增加,重構(gòu)相空間滿足的τ整體呈減小趨勢.如圖5(a),RMB數(shù)據(jù)的m為[1,3]時,τ的波動較大,重構(gòu)的相空間處于不穩(wěn)定狀態(tài);當(dāng)m＞10時,一方面相空間重構(gòu)耗費樣本量過多,約耗費40%～50%的樣本,另一方面,不同屬性的m-τ圖的值不穩(wěn)定,因此RMB數(shù)據(jù)從[4,8]范圍內(nèi)選擇嵌入維數(shù).

(3) 選擇步長η(η≥1),則樣本表示為{Xi,Ti+η},i∈{1,2,…,N},建立預(yù)測模型進行模型訓(xùn)練,當(dāng)達到訓(xùn)練樣本數(shù)量時,動態(tài)預(yù)測未來屬性值.當(dāng)數(shù)據(jù)采集及時的情況下,本方法支持Web服務(wù)QoS動態(tài)在線預(yù)測,若數(shù)據(jù)采集頻度很低或出現(xiàn)大比例缺失數(shù)據(jù),動態(tài)預(yù)測無法正常進行.另外,本方法現(xiàn)在僅限于一定閾值范圍內(nèi)的多步預(yù)測,當(dāng)η超過范圍時,不能達到預(yù)測精度要求;同時,當(dāng)η很短時,數(shù)據(jù)進行相空間重構(gòu)的優(yōu)勢不明顯.因此,實驗總結(jié)平均最佳多元時間序列預(yù)測步長的適用范圍為[2,8].

3.3 實驗結(jié)果分析

3.3.1 相空間重構(gòu)和廣告數(shù)據(jù)對預(yù)測影響

為證明相空間重構(gòu)對動態(tài)多步預(yù)測的影響以及廣告數(shù)據(jù)對預(yù)測精度的影響,通過若干組實驗分析驗證.以RBM數(shù)據(jù)為例,取1 000組訓(xùn)練樣本,300個測試樣本,m在[3,8]范圍取值,分別做單步和多步預(yù)測實驗.如圖6所示,截取不同相空間重構(gòu)下單步預(yù)測結(jié)果和RMSE的對比,實驗的RMSE采用歸一化數(shù)據(jù)計算.

圖6(a)為單步預(yù)測結(jié)果,可以看出S-LMRBF預(yù)測結(jié)果擬合度較高,說明QoS單元時間序列的信息可以實現(xiàn)單步預(yù)測.圖6(b)為單步預(yù)測的RMSE,m在[3,17]范圍內(nèi)的取值分別代表不同m對應(yīng)的相空間重構(gòu)情況.從圖中可以看出：單步預(yù)測時,Mul-LMRBF的誤差值略大于S-LMRBF,MulA-LMRBF比Mul-LMRBF的預(yù)測誤差值小,大于S-LMRBF預(yù)測誤差.說明當(dāng)預(yù)測步長較短時,相空間重構(gòu)和廣告數(shù)據(jù)對預(yù)測準(zhǔn)確性影響不大.

如圖7所示為不同相空間重構(gòu)條件下,多步預(yù)測的對比實驗結(jié)果.m=4,6,8分別進行步長為 3和 5的預(yù)測,從 6個對比結(jié)果中看出：步長增加,預(yù)測誤差都會增加,但多元 MulA-LMRBF和 Mul-LMRBF預(yù)測結(jié)果比單元S-LMRBF預(yù)測結(jié)果的擬合好.取不同相空間重構(gòu)參數(shù)值,預(yù)測結(jié)果也不同,當(dāng)重構(gòu)維數(shù)m取值在m-τ曲線穩(wěn)定的范圍內(nèi)時,預(yù)測結(jié)果具有較高擬合度.因此,相空間重構(gòu)參數(shù)要綜合考慮m和τ兩個參數(shù),取參數(shù)值共同穩(wěn)定的范圍.MulA-LMRBF的擬合結(jié)果優(yōu)于Mul-LMRBF,廣告數(shù)據(jù)進一步提高了預(yù)測精度,因此,采用服務(wù)提供商提供的相對真實可靠的廣告數(shù)據(jù)進行QoS多步預(yù)測會進一步提高預(yù)測精度.

3.3.2 多元對預(yù)測步長的影響

通過相空間重構(gòu)和廣告數(shù)據(jù)的實驗,充分證明恰當(dāng)?shù)南嗫臻g和廣告數(shù)據(jù)能提高多步預(yù)測精度.以相空間重構(gòu)m在[3,10]范圍內(nèi)的值為例,通過實驗調(diào)整步長,觀察隨步長增加單元(S-LMRBF)、無廣告多元(Mul-LMRBF)、帶廣告多元(MulA-LMRBF)這3種預(yù)測的均方根誤差RMSE變化情況.從數(shù)據(jù)集中選擇若干個完整的Web服務(wù)QoS數(shù)據(jù)分別進行對比實驗,實驗證明：多步預(yù)測時,MulA-LMRBF的RMSE值最小,Mul-LMRBF和MulALMRBF多步預(yù)測的RMSE普遍優(yōu)于S-LMRBF單元預(yù)測結(jié)果.

圖8是RMB數(shù)據(jù)300個測試樣本的多步預(yù)測RMSE示例.當(dāng)Step＜3時,S-LMRBF的RMSE值明顯低于Mul-LMRBF和 MulA-LMRBF的值,說明小步長范圍內(nèi),單元時間序列可實現(xiàn)較高精度預(yù)測.Step≥3,所有預(yù)測的MulA-LMRBF明顯優(yōu)于其他預(yù)測的RMSE,其中,m=4時,Mul-LMRBF優(yōu)于S-LMRBF;m=6時,Step在[3,9]及大于10范圍內(nèi)Mul-LMRBF小于S-LMRBF的RMSE.因此,加入廣告的MulA-LMRBF一直比未加入廣告數(shù)據(jù)Mul-LMRBF預(yù)測結(jié)果的RMSE小.

如圖9所示是自己采集的MobileCode數(shù)據(jù)預(yù)測RMSE對比圖,選擇m-τ曲線平穩(wěn)范圍內(nèi)的相空間重構(gòu)參數(shù).以m=5為例,RMSE隨步長變大呈增長趨勢,當(dāng)步長大于1時,Mul-LMRBF和MulA-LMRBF的預(yù)測RMSE總體上優(yōu)于S-LMRBF,多元Mul-LMRBF在[2,5]步長范圍內(nèi)小于單元S-LMRBF的RMSE值.

從第2組數(shù)據(jù)堂數(shù)據(jù)中選擇258組QoS數(shù)據(jù)完整的Web服務(wù)進行實驗,統(tǒng)計m在[3,10]范圍內(nèi)不同步長取值的RMSE值.如圖10為m=4時,258組實驗的平均RMSE.

如圖 10所示,當(dāng)Step在[3,7]范圍時,帶廣告的多元 MulA-LMRBF預(yù)測誤差明顯優(yōu)于 Mul-LMRBF和S-LMRBF,與S-LMRBF相比,MulA-LMRBF的RMSE平均減小19%,多元Mul-LMRBF比S-LMRBF平均降低了16%.說明多元時間序列更適合多步長預(yù)測,可靠的廣告數(shù)據(jù)會提高預(yù)測的準(zhǔn)確度.根據(jù)實驗統(tǒng)計,模型的平均最佳多步預(yù)測步長范圍是[2,8].

3.3.3 對比實驗

對比傳統(tǒng) RBF神經(jīng)網(wǎng)絡(luò)模型、ARMA模型和本文提出的 MulA-LMRBF預(yù)測模型,步長分別取 1,3和 5,分析預(yù)測值和實際值的擬合情況以及預(yù)測的均方根誤差RMSE.

以RMB數(shù)據(jù)集為例,首先用S-LMRBF單步預(yù)測結(jié)果對比傳統(tǒng)RBF神經(jīng)網(wǎng)絡(luò)、ARMA單元單步預(yù)測結(jié)果,如圖11(a);然后,用m=6對應(yīng)的Mul-LMRBF多步預(yù)測結(jié)果對比傳統(tǒng)方法預(yù)測結(jié)果,如圖11(b),多步預(yù)測的RBF和ARMA都采用響應(yīng)時間和吞吐量兩屬性的歷史數(shù)據(jù).S-LMRBF和MulA-LMRBF分別對應(yīng)不同步長預(yù)測值.

表1為RMB數(shù)據(jù)預(yù)測結(jié)果的RMSE,綜合分析都優(yōu)于RBF和ARMA的預(yù)測結(jié)果.表2為MobileCode數(shù)據(jù)300個樣本點的對比實驗RMSE統(tǒng)計值,步長分別取1,3,5,多元取m=6進行相空間重構(gòu).從表中可以看出：相比其他方法,MulA-LMRBF和S-LMRBF的RMSE值都比較小,具有更好的預(yù)測精度.

Table 1 Comparison of RMSE for RMB data forecasting results表1 RMB數(shù)據(jù)預(yù)測結(jié)果RMSE指標(biāo)比較

Table 2 Comparison of RMSE for MobileCode data forecasting results表2 MobileCode數(shù)據(jù)預(yù)測結(jié)果RMSE指標(biāo)比較

為進一步驗證方法的通用性,將方法應(yīng)用在數(shù)據(jù)集2收集到的258個完整的包含響應(yīng)時間(response time,簡稱RT)和吞吐量(throughput,簡稱T)的Web服務(wù)數(shù)據(jù),表3為預(yù)測結(jié)果的平均RMSE.通過對比實驗,進一步證明了 MulA-LMRBF和 S-LMRBF的 RMSE值最小,特別是在多步長預(yù)測時,MulA-LMRBF要明顯優(yōu)于S-LMRBF.因此進一步證明了本文提出的MulA-LMRBF預(yù)測精度優(yōu)于傳統(tǒng)的RBF和ARMA方法,并且在動態(tài)和多步預(yù)測時,具有更好的預(yù)測效果.

Table 3 Comparison of RMSE for 258 Web services data average forecasting results表3 第2組Web預(yù)測平均RMSE指標(biāo)比較

表4為第3部分?jǐn)?shù)據(jù)集中ClientIP=128.83.122.179的平均RMSE結(jié)果,第3部分?jǐn)?shù)據(jù)集采用4個QoS屬性,比較平均RMSE可以看出當(dāng)Step=3和5時,MulA-LMRBF的預(yù)測結(jié)果明顯優(yōu)于單元時間序列S-LMRBF.整體比較,本文改進算法MulA-LMRBF的預(yù)測RMSE比傳統(tǒng)方法大約降低了50%,比S-LMRBF降低了20%左右.

Table 4 Comparison of RMSE for the third data set average forecasting results表4 數(shù)據(jù)堂數(shù)據(jù)集的平均RMSE指標(biāo)比較

4 結(jié)論與未來工作

現(xiàn)有的Web服務(wù)QoS預(yù)測方法存在預(yù)測周期短、動態(tài)能力差、屬性之間相互影響考慮不足等問題,針對上述問題,本文提出了一種基于多元時間序列的QoS預(yù)測方法 MulA-LMRBF.首先,該方法考慮多個QoS屬性之間的關(guān)系,采用相空間重構(gòu)描述并恢復(fù)各個屬性值在時間變化中存在的非線性、動態(tài)系統(tǒng),刻畫屬性間存在的關(guān)聯(lián);然后,利用服務(wù)廣告數(shù)據(jù)近似表示屬性值的未來趨勢,將歷史數(shù)據(jù)和廣告數(shù)據(jù)共同組成預(yù)測的綜合數(shù)據(jù)序列,實現(xiàn)多步長周期預(yù)測;為了改善原RBF神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練計算過程并實現(xiàn)動態(tài)預(yù)測,最后采用LM算法優(yōu)化RBF神經(jīng)網(wǎng)絡(luò)模型,隨著在線樣本采集,模型參數(shù)更新.

在未來的工作中,將重點考慮以下幾個問題.一是現(xiàn)有的計算相空間重構(gòu)嵌入維數(shù)和延遲時間的方法并不完善,目前運用的平均位移法可以提高預(yù)測的準(zhǔn)確性,但參數(shù)未證實最優(yōu),相空間重構(gòu)一直存在很大的研究挑戰(zhàn),參數(shù)值的選擇一直是研究熱點,后期進一步研究綜合考慮嵌入維數(shù)和延遲時間的方法;二是本方法只選擇網(wǎng)絡(luò)權(quán)值為動態(tài)參數(shù),動態(tài)性還不夠完備,隱層節(jié)點個數(shù)等方面未考慮.本文從時間序列數(shù)據(jù)分析和預(yù)測方面研究QoS預(yù)測,現(xiàn)實網(wǎng)絡(luò)中,需要Web服務(wù)數(shù)據(jù)實時收集、數(shù)據(jù)分析和處理、動態(tài)預(yù)測模型等更完備的系統(tǒng)支持,今后可更全面地研究;三是目前只考慮響應(yīng)時間和吞吐量兩個QoS屬性預(yù)測響應(yīng)時間,后期會進一步改進模型,可同時預(yù)測多個QoS屬性值.