基于改進貝葉斯算法的云服務(wù)可靠性預(yù)測方法研究

錢雙洋 陳 喆 劉原序

(解放軍信息工程大學 河南 鄭州 450001)

基于改進貝葉斯算法的云服務(wù)可靠性預(yù)測方法研究

錢雙洋 陳 喆 劉原序

(解放軍信息工程大學 河南 鄭州 450001)

目前服務(wù)消費者業(yè)務(wù)的不斷發(fā)展，業(yè)務(wù)邏輯的不斷復(fù)雜，對云服務(wù)組合的可靠性性能需求不斷增加。通過對服務(wù)組合可靠性進行預(yù)測，根據(jù)預(yù)測結(jié)果向服務(wù)消費者推薦滿足其可靠性需求的組合服務(wù)，以提高服務(wù)使用質(zhì)量?；趥鹘y(tǒng)的貝葉斯預(yù)測模型提出一種改進貝葉斯預(yù)測算法(IDLM)。通過采用指數(shù)加權(quán)回歸方法對算法中的狀態(tài)誤差方差項進行估算，有效解決了傳統(tǒng)貝葉斯模型中狀態(tài)誤差方差參數(shù)確定困難等問題，并且具有較高的預(yù)測效率和預(yù)測準確性。實驗結(jié)果表明，改進的貝葉斯預(yù)測算法(IDLM)較其他傳統(tǒng)的時間序列預(yù)測算法具有較高的準確性。

服務(wù)組合 可靠性 貝葉斯模型 預(yù)測

0 引 言

面向服務(wù)[1]計算是在面向?qū)ο?、面向?gòu)件及分布式計算等軟件工程技術(shù)的基礎(chǔ)上產(chǎn)生的一種新的計算范式。隨著云計算服務(wù)資源的不斷豐富，云計算環(huán)境中不可避免地涌現(xiàn)出大量功能相同但服務(wù)質(zhì)量QoS不同的服務(wù)資源。通過一定的組合邏輯和業(yè)務(wù)流程，將功能單一的原子服務(wù)組合成具有增值功能的組合服務(wù)，來滿足用戶QoS偏好，這一過程稱之為服務(wù)組合。通常服務(wù)提供者和服務(wù)請求者之間協(xié)商出服務(wù)等級協(xié)定(SLA)來規(guī)約服務(wù)組合過程中的一系列非功能性指標。服務(wù)提供者的目標是滿足SLA的前提下，以盡可能小的成本來提供用戶所需的服務(wù)。服務(wù)請求者希望花費最小的費用來獲得QoS指標最高的服務(wù)。

云服務(wù)的評價指標主要是根據(jù)Web服務(wù)的評價指標和云服務(wù)自身的特點，目前，云服務(wù)QoS指標主要包括性能、可用性、可靠性和安全性?？煽啃宰鳛樵u價軟件質(zhì)量指標的重要屬性之一，也是云服務(wù)QoS質(zhì)量指標中重要的屬性之一。在保障功能需求的前提下，現(xiàn)今用戶更加注重云服務(wù)于的QoS屬性。提高云服務(wù)的可靠性，對可靠性進行預(yù)測，在故障發(fā)生之前采取相應(yīng)的措施，能有效地保障服務(wù)消費者的權(quán)益，同時也能夠降低服務(wù)提供者的成本。

目前現(xiàn)有的可靠性預(yù)測方法都是通過預(yù)測技術(shù)對云服務(wù)的可靠性指標進行預(yù)測，從而根據(jù)預(yù)測結(jié)果進行服務(wù)推薦。云服務(wù)以及云服務(wù)組合的可靠性研究已經(jīng)受到廣大學者的廣泛關(guān)注，但是目前還沒有很好的解決方法，服務(wù)組合的可靠性預(yù)測也已成為面向服務(wù)計算和軟件可靠性領(lǐng)域亟需解決的問題。文獻[2]為了解決測量服務(wù)可靠性矩陣無法準確測量的問題，利用微積分幾何工具將可靠性秩約束矩陣演化為沒有約束的幾何優(yōu)化，為服務(wù)預(yù)測和推薦提供了參考。Ma等[3]使用概率分布函數(shù)和概率密度函數(shù)提出云服務(wù)可靠性預(yù)測的概率模型。文獻[4]采用貝葉斯算法來分析可靠性預(yù)測過程中可能出現(xiàn)的服務(wù)違規(guī)和可靠性缺失問題。文獻[5]提出了基于貝葉斯算法的網(wǎng)格計算服務(wù)組合可靠性預(yù)測模型。文獻[6]提出案例推理的方法來對Web服務(wù)組合的可靠性進行預(yù)測。梁員寧等[7]針對云服務(wù)的冗余特性和可靠性保障需求，設(shè)計了基于信任冗余的云服務(wù)可靠性增強總體框架。鐘旭航等[8]通過軟件容錯技術(shù)來提高組合服務(wù)的可靠性，其首先建立服務(wù)組合的可靠性預(yù)測模型，然后提出了一種建立基于冗余的Web服務(wù)組合的可靠性優(yōu)化模型的方法。鄭子彬等[9]將協(xié)同過濾技術(shù)、鄰居矩陣分解策略、服務(wù)調(diào)用者的歷史信息和鄰居用戶的信息結(jié)合起來，從而對服務(wù)可靠性進行預(yù)測，繼而提出基于可靠性感知的Web服務(wù)推薦系統(tǒng)。Geebelen 等[10]提出了一種基于在線支持向量機的組合Web 服務(wù) QoS 預(yù)測方法。該預(yù)測方法首先采用在線支持向量機預(yù)測組件服務(wù)的 QoS， 然后基于組件服務(wù)的 QoS 預(yù)測值預(yù)測組合 Web 服務(wù)的 QoS，并依據(jù)預(yù)測的組合 Web 服務(wù)的 QoS計算質(zhì)量協(xié)議的概率。

綜上所述，在進行服務(wù)可靠性預(yù)測過程中，現(xiàn)有的部分預(yù)測方案和預(yù)測方法的準確性不高。并且有的算法在預(yù)測過程中需要消耗大量的系統(tǒng)資源和歷史數(shù)據(jù)，導致算法復(fù)雜度高，預(yù)測開銷大，最終導致無法對云服務(wù)進行實時的預(yù)測，更不能對整個服務(wù)的使用流程進行實時預(yù)測。因此本文提出一種基于改進貝葉斯預(yù)測模型的可靠性預(yù)測算法，提出的算法不僅具有較高的預(yù)測準確度，并且在算法復(fù)雜度和消耗系統(tǒng)資源方面也有很好的表現(xiàn)。

1 云服務(wù)組合流程及其可靠性計算

通過服務(wù)組合將功能單一的原子服務(wù)組合成具有增值功能的組合服務(wù)來滿足用戶的QoS需求，云服務(wù)組合的基本順序結(jié)構(gòu)包括順序、迭代、并行和選擇。通過隨機Petri網(wǎng)對上述四種模型進行形式化描述，得到如圖1所示的服務(wù)組合模型圖。

圖1 服務(wù)組合隨機Petri流程圖

迭代結(jié)構(gòu)是當邏輯條件滿足規(guī)定條件的時候，就循環(huán)執(zhí)行循環(huán)體內(nèi)的原子服務(wù)，如圖1(b)所示，假設(shè)循環(huán)體內(nèi)的服務(wù)被執(zhí)行N次，那么迭代結(jié)構(gòu)的可靠性計算公式為：RL=R(si)N。其中R(si)是循環(huán)體內(nèi)的原子服務(wù)的可靠性值。

選擇結(jié)構(gòu)和并列結(jié)構(gòu)類似，也是具有多分支結(jié)構(gòu)，但是執(zhí)行下一個原子服務(wù)的條件是任意分支上的原子服務(wù)執(zhí)行完畢。因此選擇結(jié)構(gòu)是在眾多分支中選擇一個分支執(zhí)行，假設(shè)選擇結(jié)構(gòu)的分支數(shù)目為N，選擇分支Si的概率為pi，那么選擇結(jié)構(gòu)的可靠性計算公式為：

上述四種組合結(jié)構(gòu)是服務(wù)組合中基本的四種結(jié)構(gòu)，通常情況下實際中的組合不會這么簡單，通常是上述一種或者幾種基本組合結(jié)構(gòu)的再組合。下面通過一個實例來詳細介紹實際中一個云服務(wù)組合的可靠性。如圖2所示。

圖2 服務(wù)組合可靠性計算示例

圖2中的服務(wù)組合中包含了S1-S7七個原子服務(wù)。從總體上看整個服務(wù)組合分為三個部分，S1、并列結(jié)構(gòu)和S7組成了整個服務(wù)組合，其中并列結(jié)構(gòu)中包括兩個分支，分支一包含S2、選擇結(jié)構(gòu)，選擇結(jié)構(gòu)中包含兩個分支，分別為S6和S5，分支二包含S3、循環(huán)結(jié)構(gòu)，循環(huán)結(jié)構(gòu)中包含S4循環(huán)k次。綜上所述，假設(shè)單個原子服務(wù)Si的可靠性為R(si)，那么上述整個服務(wù)組合的可靠性為：

Rs=R(s1)×R(s2)×[p1×R(s4)+p2×R(s5)]×

R(s3)×Rk(s6)×R(s7)

服務(wù)提供者在向服務(wù)注冊中心發(fā)布原子服務(wù)的同時會提供原子服務(wù)的可靠性參數(shù)值，通過上述服務(wù)組合的可靠性計算公式可計算出組合服務(wù)的可靠性。相同的服務(wù)由于服務(wù)請求者的地理信息環(huán)境與網(wǎng)絡(luò)環(huán)境不同，其可靠性值也會不同。服務(wù)的可靠性的值的變化是相對有規(guī)律的，通過對云服務(wù)的可靠性值進行實時預(yù)測，分配一個未來時間段內(nèi)滿足服務(wù)請求者可靠性需求的云服務(wù)。同時對一些即將發(fā)生可靠性違規(guī)的云服務(wù)采取一定的措施，這對進一步提高云服務(wù)的服務(wù)質(zhì)量具有重要的意義。因此下一節(jié)將提出改進的貝葉斯算法(IDLM)來進行服務(wù)可靠性的預(yù)測。

2 改進貝葉斯算法的設(shè)計與實現(xiàn)

通過貝葉斯統(tǒng)計對預(yù)測歷史數(shù)據(jù)進行分析和演變，從而建立預(yù)測模型稱之為貝葉斯預(yù)測模型。貝葉斯預(yù)測模型充分利用先驗信息，結(jié)合歷史數(shù)據(jù)信息和預(yù)測模型，從而可以對即將到來的數(shù)據(jù)進行預(yù)測和判斷。貝葉斯預(yù)測模型按照其狀態(tài)方程和預(yù)測方程中參數(shù)的不同確定方法，可以將貝葉斯模型分為常均值模型、常均值折扣模型。上述兩種模型的基礎(chǔ)是正態(tài)動態(tài)線性模型，本節(jié)將詳細介紹正態(tài)動態(tài)線性模型、常均值模型、常均值折扣模型以及本文提出的改進貝葉斯算法(IDLM)。

2.1 正態(tài)動態(tài)線性模型

貝葉斯模型的基礎(chǔ)是正態(tài)動態(tài)線性模型DLM(Dynamic Linear Models)，其先驗概率隨著時間的變化而變化。DLM是由觀測方程和預(yù)測方程確定的預(yù)測系統(tǒng)，通過狀態(tài)回歸矩陣和狀態(tài)轉(zhuǎn)移矩陣來反映預(yù)測數(shù)值如何以系統(tǒng)狀態(tài)在系統(tǒng)內(nèi)部之間轉(zhuǎn)化。DLM可以表示為{F,G,V,W}t={Ft,Gt,Vt,Wt}，對于任意時刻t，一般存在：

(1)

將上述正態(tài)動態(tài)線性模型DLM{F,G,V,W}表示成方程，如下所示：

μt=Gtμt-1+ωtωt～N[0,Wt]

(2)

yt=Ftμt+vtvt～N[0,Vt]

(3)

其中:式(2)為狀態(tài)方程，式(3)為觀測方程，F(xiàn)t是n×r維動態(tài)回歸矩陣，Gt是n×n維狀態(tài)轉(zhuǎn)移矩陣，vt和ωt是r維和n維的觀測誤差項和狀態(tài)誤差項，觀測誤差項和狀態(tài)誤差項都服從正態(tài)分布，且相互獨立，其方差為Vt、Wt。

從式(2)-式(3)可以看出，如果知道t時刻云服務(wù)可靠性的值，并且能夠得到狀態(tài)轉(zhuǎn)移矩陣、動態(tài)回歸矩陣、觀測誤差項和狀態(tài)誤差項，可以通過式(2)-式(3)預(yù)測出下一時刻云服務(wù)可靠性的預(yù)測值。觀察式(2)-式(3)可得，正態(tài)線性模型就是觀測向量、狀態(tài)向量、觀測誤差向量和狀態(tài)誤差向量都服從正態(tài)分布的動態(tài)模型，只要知道{Ft,Gt,Vt,Wt}就可以確定正態(tài)動態(tài)線性模型DLM。

2.2 常均值模型

常均值模型是在上述正態(tài)動態(tài)線性模型的基礎(chǔ)上演變而來，通過將上述正態(tài)線性模型中的觀測向量和狀態(tài)向量Ft、Gt均設(shè)為1，則得到常均值模型DLM{1,1,Vt,Wt}。方程表示如下：

μt=μt-1+ωtωt～N[0,Wt]

(4)

yt=μt+vtvt～N[0,Vt]

(5)

式(4)為常均值模型狀態(tài)方程，式(5)為常均值觀測方程。

證明：由于狀態(tài)方程和vt、ωt、μt都服從于正態(tài)分布，并且相互獨立，由正態(tài)分布的可加性可得：

2.3 常均值折扣模型

μt=μt-1+ωtωt～N[0,Wt]

(6)

Wt=Ct-1(γ-1-1)

(7)

yt=μt+vtvt～N[0,Vt]

(8)

式(6)為常均值折扣模型的狀態(tài)方程，式(7)為常均值折扣模型的狀態(tài)誤差方差約束條件，式(8)為常均值折扣模型的觀測方程。

2.4 改進貝葉斯算法(IDLM)

雖然常均值折扣模型引入折扣因子γ來解決常均值模型中狀態(tài)誤差方差很難求解的問題，但是其處理方法過于簡單，對于預(yù)測的準確度還有待提高。本節(jié)針對常均值折扣模型預(yù)測精度不高的問題，提出了另外一種改進的貝葉斯預(yù)測算法(IDLM)。通過對歷史數(shù)據(jù)進行處理，按照時間序列對其進行排序，通過指數(shù)加權(quán)回歸方法對其處理，按照指數(shù)分布規(guī)律對歷史數(shù)據(jù)賦予不同的權(quán)重值。然后結(jié)合先驗分布對未來數(shù)據(jù)進行預(yù)測，進而提高預(yù)測算法的準確性和穩(wěn)定性。

通過狀態(tài)方程和觀測方程可知，如果對狀態(tài)誤差方差Wt進行指數(shù)加權(quán)回歸方法處理，可得：

Wt=(λ2-β)(1-β)Vt/β

(9)

式(9)中令λ=1，可得：

Wt=(1-β2)Vt/β

(10)

證明：對于方程

根據(jù)指數(shù)加權(quán)回歸的方法，狀態(tài)誤差方差Wt可表示成如下形式：

Wt=(λ2-β)(1-β)Vt/β

由觀測方程可得：

(1-λB)μt=ωt

(11)

由狀態(tài)方程可得：

(1-λB)yt=(1-λB)μt+(1-λB)vt

(12)

再根據(jù)式子Wt=(λ2-β)(1-β)Vt/β，令λt=λ，n=1，p=0，q=0，并且令：

xt=(1-λB)yt=(1-βB/λ)et=(ωt+vt)+λBvt

這里記c1=ωt+vt,c2=-λv，則xt的自協(xié)方差函數(shù)可描述為下式：

γx=E((c1+Bc2)(c1+B-1c2))

又因為γk=γ-k，其中k=0或者1，因此γk的自回歸系數(shù)為：

γ1=E(c1c2)=-λv

γ0=E(c12+c22) = (1 +λ2)v+ω

由公式xt=(1-λB)yt=(1-βB/λ)et=(ωt+vt)+λBvt可知：

γx=E{(1-βB/λ)(1-βB-1/λ)}et2

由公式γx=E{(1-βB/λ)(1-βB-1/λ)}et2可得到的自回歸系數(shù)為：

如果令t趨于無窮大，那么有：

再比較各自的回歸系數(shù)，可得到式(9)如下：

Wt=(λ2-β)(1-β)Vt/β

令λ=1可得式(10)：

酒。酒精能使胃黏膜分泌過量的胃酸，大量飲酒后，胃黏膜上皮細胞受損，誘發(fā)黏膜水腫、出血，甚至潰瘍、糜爛，再嚴重就會出現(xiàn)胃出血。

Wt=(1-β2)Vt/β

得證。

基于改進的貝葉斯算法的云服務(wù)可靠性預(yù)測算法如算法1所示。

算法1：

Input：Vrel.t.

Output：Prel.t+1.

Begin procedure

Initialize1： β=0.8,m0=Vrel.0,C0=72

1:yt←Vrel.t;

3:Qt←Rt+Vt;

4:At←Rt/Qt;

5:ft←mt-1;

6:et←yt-ft;

7:Ct←AtVt;

8:mt←mt-1-Atet;

9:Prel.t+1←mt;

Endproceduce

Output:Prel.t+1.

3 實驗仿真分析

3.1 實驗環(huán)境設(shè)計

本文采用實驗室搭建的基于openstack的云平臺實驗環(huán)境，分析和驗證提出的服務(wù)組合可靠性模型，并采用現(xiàn)代數(shù)學計算工具MATLAB來分析求解。實驗證明本文提出的基于改進貝葉斯模型的云服務(wù)可靠性預(yù)測算法在實際運行環(huán)境中具有較好的性能。

為了實驗對比，將本文提出的算法和常用的時間序列算法進行對比。實驗對象為改進的貝葉斯常均值(IDLM)、貝葉斯常均值折扣(BCMD)、一次移動平均法(MAM)、一次指數(shù)平滑法(SES)。

3.2 結(jié)果評價指標

為了對實驗結(jié)果進行分析和對比，設(shè)計如下四種評價指標：

平方和誤差(SSE):

平均絕對誤差(MAE):

均方誤差(MSE)：

平均絕對百分比誤差(MAPE)：

式中：Vrel.t表示的t時刻云服務(wù)可靠性的實時檢測值，Prel.t+1表示的是t+1時刻云服務(wù)可靠性的預(yù)測值。

3.3 實驗結(jié)果分析

在基于openstack的云平臺上創(chuàng)建40臺虛擬機表示云平臺可以向服務(wù)請求者提供的40個云服務(wù)。同時設(shè)置了1 000個應(yīng)用任務(wù)表示服務(wù)請求者的任務(wù)在上面運行。在虛擬機的執(zhí)行過程中檢測服務(wù)可靠性值和預(yù)測算法來預(yù)測下一時刻服務(wù)可靠性值，計算上述提到的四種評價指標，來表示預(yù)測算法的準確性和穩(wěn)定性。通過對本文提出的改進的貝葉斯算法(IDLM)與貝葉斯常均值折扣(BCMD)、一次移動平均法(MAM)、一次指數(shù)平滑法(SES)進行實驗對比分析。得到實驗數(shù)據(jù)如表1所示。

表1 實驗數(shù)據(jù)分析

表1中第一行為實驗的四種預(yù)測算法(IDLM、BCMD、MAM、SES)，第一列為四種評價指標(SSE、MAE、MSE、MAPE)。從表1中第二行可以得到IDLM預(yù)測算法的SSE值為0.005 625，在四種預(yù)測算法中為最小，表明了IDLM通過Vrel.t來預(yù)測Prel.t+1時預(yù)測的穩(wěn)定性最好，即預(yù)測的準確性最高。同理，比較其他三種評價指標均可以得到IDLM的預(yù)測準確性最高。

通過上述實驗可知，通過本文提出的改進的貝葉斯預(yù)測算法來進行云服務(wù)可靠性預(yù)測時，預(yù)測數(shù)據(jù)具有較低的方差值。即通過t時刻的云服務(wù)可靠性值Vrel.t能夠預(yù)測出最滿足用戶可靠性需求的組合服務(wù)，來推薦給服務(wù)請求者。

4 結(jié) 語

隨著云服務(wù)的發(fā)展和成熟，用戶已經(jīng)從滿足服務(wù)的功能需求逐漸轉(zhuǎn)變?yōu)閷Ψ?wù)的非功能性需求提出更高的要求。可靠性作為服務(wù)非功能屬性中的重要屬性之一，可靠性的高低直接影響著服務(wù)質(zhì)量的高低。對云服務(wù)可靠性進行預(yù)測進行研究來對服務(wù)可靠性保障具有重要的研究意義。本文在傳統(tǒng)的貝葉斯預(yù)測模型的基礎(chǔ)上對狀態(tài)誤差方差進行指數(shù)加權(quán)回歸處理，來提高預(yù)測算法性能。實驗表明，提出的算法較傳統(tǒng)的時間序列預(yù)測算法具有較高的準確性和穩(wěn)定性。

[1] Abbadi I M, Alawneh M. A framework for establishing trust in the Cloud[J]. Computers & Electrical Engineering, 2012, 38(5):1073-1087.

[2] Zhao Y, Li Z, Chu X. QoS Prediction for the Cloud Service Marketplace: A Grassmann Manifold Approach[C]// IEEE, International Conference on Cloud Computing. IEEE, 2015:221-228.

[3] Ma Y, Wang S, Yang F, et al. Predicting QoS Values via Multi-dimensional QoS Data for Web Service Recommendations[C]// IEEE International Conference on Web Services. IEEE, 2015:249-256.

[4] Tang B, Tang M. Bayesian Model-Based Prediction of Service Level Agreement Violations for Cloud Services[C]// Theoretical Aspects of Software Engineering Conference. IEEE, 2014:170-176.

[5] Kazem A A P, Pedram H, Abolhassani H. BNQM: A Bayesian Network based QoS Model for Grid service composition[J]. Expert Systems with Applications, 2015, 42(20):6828-6843.

[6] Frey S, Luthje C, Reich C, et al. Cloud QoS Scaling by Fuzzy Logic[C]// IEEE International Conference on Cloud Engineering. IEEE Computer Society, 2014:343-348.

[7] 梁員寧，陳建良，葉笠. 云服務(wù)可靠性優(yōu)化方法研究[J].計算機科學, 2013,40(8):129-133.

[8] 鐘旭航、齊治昌，徐錫山. 基于冗余的Web服務(wù)組合可靠性優(yōu)化方法研究[J].計算機工程, 2008,34(4):31-33.

[9] Zheng Z, Ma H, Lyu M R, et al. Collaborative Web Service QoS Prediction via Neighborhood Integrated Matrix Factorization[J]. IEEE Transactions on Services Computing, 2013, 6(3):289-299.

[10] Geebelen D， Geebelen K， Truyen E， et al． QoS prediction for Web service compositions using kernel-based quantile estimation with online adaptation of the constant offset[J]．Information Sciences， 2014，268: 397-424.

CLOUDSERVICERELIABILITYPREDICTIONMETHODBASEDONIMPROVEDBAYES

Qian Shuangyang Chen Zhe Liu Yuanxu

(PLAInformationEngineeringUniversity,Zhengzhou450001,Henan,China)

In view of the continuous development of the service consumer business and the complexity of the business logic, the demand for reliability of the cloud service composition is increasing. Through the prediction of the reliability of service composition, according to the prediction results, the service composition was recommended to service consumers to satisfy their reliability requirements to improve the service quality. We propose an improved Bayesian prediction algorithm based on the traditional Bayesian prediction model. By using the exponential weighted regression method to estimate the variance term of the state error in the algorithm, the problem of difficulty in determining the variance parameters of state error in the traditional Bayesian model is solved effectively. And it has high predictive efficiency and predictive accuracy. The experimental results show that the improved Bayesian prediction algorithm has higher accuracy than other traditional time series prediction algorithms.

Service composition Reliability Bayesian model Prediction

2017-02-19。國家高技術(shù)發(fā)展研究計劃項目(2008AA01Z404)；國防預(yù)研基金項目(9140A26010306JB5201)。錢雙洋，碩士生，主研領(lǐng)域：系統(tǒng)工程與信息安全。陳喆，副教授。劉原序,碩士生。

TP3

A

10.3969/j.issn.1000-386x.2017.11.006