基于不確定服務質量感知的云服務組合方法

王思臣,涂 輝,張以文

(1.計算智能與信號處理教育部重點實驗室(安徽大學), 合肥 230031;2.瓦斯治理國家工程研究中心(淮南礦業集團), 安徽 淮南 232001)(*通信作者電子郵箱zhangyiwen@ahu.edu.cn)

0 引言

隨著云計算的發展,越來越多的資源以服務的形式發布和使用,如何選擇高性能的服務來構建增值的應用已成為研究熱點。服務通常由功能屬性和非功能屬性構成,非功能屬性也稱為服務質量(Quality of Service, QoS),描述了服務在完成其功能的過程中表現出的執行特性,由響應時間、吞吐量、延遲、成功率、花費、信譽度等一系列屬性構成。然而,在許多情況下,單個服務是無法滿足用戶復雜需求的,需要根據用戶需求進行服務組合。由于功能屬性相似而非功能屬性不同的服務數量迅速增加,服務選擇變得越來越復雜,使得服務組合問題逐漸演變為NP(Non-derministic Polynomial)完全問題。為了高效地找到最優服務組合,許多方法被相繼提出。常用的方法有整數線性規劃(Integral Linear Programming, ILP)、混合線性規劃(Mixed Linear Programming, MLP)和人工智能(Artificial Intelligence, AI)算法[1-7]。然而,這些方法大多只考慮確定性QoS,而忽略現實中QoS的不確定性。文獻[8]考慮到不確定的服務質量,將具有不確定QoS的服務組合問題建模為一個區間數多目標優化問題(Interval Number Multi-Objective Optimization Problem, IMOP),并提出了一種基于分解的非確定性多目標進化算法。以上這些方法只考慮組合服務在執行階段的QoS性能,即組合服務的瞬時QoS性能,而忽略了云環境的不確定性。服務組合的成功在很大程度上取決于不同組件服務保持長期服務質量(QoS)滿足用戶需求的能力,與傳統的服務組合相比,云服務組合通常是從長期角度考慮的。文獻[9]定義了一種長期QoS感知云服務組合的方法,引入了三種元啟發式算法,即遺傳算法(Genetic Algorithm, GA)、模擬退火算法和禁忌搜索算法,以選擇具有最佳平均長期QoS的服務；然而,他們認為每個服務的時間序列的長度是固定的,通過隨機采樣對服務進行選擇。

基于以上分析,本文認為云服務組合是一個長期優化過程,在長期優化過程中,由于云環境的動態性,使得服務的QoS可能發生變化,需要在用戶長期使用過程中最大化滿足用戶需求。本文中,首先考慮現實世界中用戶對服務的訪問規律,即一段時間內單個服務的被訪問頻率,提出一種基于不確定QoS感知的服務組合時間序列模型,該模型使用不定長時間序列描述一段時間內QoS值的變化,能夠準確地描述用戶對服務的真實訪問記錄；其次,提出一種基于不確定QoS模型的改進遺傳算法,該算法通過采用錦標賽選擇策略改進選擇操作,使得種群保持了多樣性,提高了群體收斂速度。

1 相關工作

近年來,基于QoS感知的服務選擇和組合在面向服務的應用中得到了廣泛的關注。一般來說,QoS感知服務組合問題可以分為兩類:一是確定QoS感知的服務組合,二是不確定QoS感知的服務組合。對于確定QoS感知服務組合,最流行的方法有整數線性規劃(ILP)、混合線性規劃(MLP)和人工智能(AI)算法。然而,這些服務組合方法主要針對確定的QoS值,而忽略了現實中QoS的不確定性。文獻[10]考慮到服務質量的不確定性,提出了一種不確定QoS感知的服務選擇模型,并利用非參數檢驗和對服務質量的穩定性進行了比較,提出了一種基于簡單的目標函數值均值或方差比較的決策模型,并給出了實例分析和原型系統。

云服務組合通常是長期的。文獻[11]中考慮服務組合的長期性,從基于用戶的角度考慮云服務組合,使用離散貝葉斯網絡表示終端用戶的經濟模型,將云服務組合問題建模為一個影響圖問題,并提出了一種基于影響圖的云服務組合方法。文獻[12]中從長期的角度考慮了服務組合,提出了用時間序列來表示經濟模型,然后將云服務組合建模為多維時間序列數據庫中的相似搜索問題,并使用QoS屬性和QoS關系兩種結構來進一步提高相似性搜索方法的效率。文獻[13]中提出了一種基于長期經濟模型驅動的云服務選擇和組合方法,利用QoS歷史數據來預測服務提供商的長期QoS行為,利用QoS屬性之間的相關性來降低預測值和真實值之間的誤差,將預測的時間序列組表示為經濟模型,然后將云服務組合建模為相似搜索問題。文獻[14]中使用深度循環長期短期記憶(Long Short Term Memory, LSTM)來預測未來的QoS值變化,將預測的QoS值推薦給長期服務組合中的組件和替代品。文獻[15]考慮基于時間序列的感知QoS的云計算服務組合,將服務的QoS偏好隨時間不斷變化的過程納入云服務組合的研究范圍,將云服務組合建模成時間序列的相似度對比問題。

2 問題描述

2.1 相關概念

下面介紹云計算服務組合問題中的一些相關概念,并給出云服務、服務質量、服務組合模型以及組合服務(combined service)的形式化描述。

定義1 云服務。云服務是基于互聯網的相關服務的增加、使用和交互模式,通常涉及通過互聯網來提供動態易擴展且經常是虛擬化的資源?？捎靡粋€二元組表示,S={F,NF},其中F和NF分別代表服務的功能和非功能屬性。

非功能屬性用QoS表示,所以服務又可以表述為{F,Q},其中Q代表服務的QoS值。

定義2 服務質量。 服務質量指服務的非功能屬性,可用一個二元組{RT,TH}表示,其中RT和TH分別代表響應時間(response time)和吞吐量(throughput)。

1)響應時間RT。響應時間是從用戶提交服務請求到服務執行完成并返回結果的時間間隔，包括服務執行時間Texe,網絡傳輸時間Ttrans和其他時間花費Toth:

RT=Texe+Ttrans+Toth

2)吞吐量TH。吞吐量是指服務單位時間內可處理的請求數量。

QoS屬性可以分為兩類:正相關和負相關屬性。正相關屬性意味著屬性值越高,質量越好,例如:可靠性、可用性。負相關屬性意味著與正相關屬性相反。并且由于QoS中每個元素的取值有較大差異,數值不是一個數量級,因此在進行服務選擇和服務組合之前,需要對QoS各屬性值進行歸一化處理,通常每一個QoS屬性轉換成0～1的值。因為正相關屬性值很容易轉換成負相關屬性值,為了簡單,本文只考慮負相關屬性值。本文按以下公式進行歸一化處理。

1)效益型：

(1)

2)成本型：

(2)

定義3 組合服務(Combined Service, CS)。組合服務是將多個單一服務組合起來構建復雜、功能強大的服務。一個抽象的組合服務可用一個抽象的組合請求表示，CS={S1,S2,…,Sn},其中CS表示請求服務類。一個具體的組合服務可以定義為抽象組合服務的實例化。每個抽象服務類包含功能相同、QoS值不同的服務,通過服務選擇將CS中每個抽象服務類實例化,可以得到一個具體的組合服務。組合服務QoS計算方法如表1。本文采用順序結構模型討論QoS感知云服務組合問題。

2.2 QoS模型描述

本文考慮的QoS屬性為響應時間和吞吐量,分別用q1、q2表示。不同于傳統服務組合問題,組合服務的整體QoS性能需要從長期角度衡量。本文采用不定長時間序列描述服務的長期QoS值數據變化,時間序列是指將相同統計指標的數值按其發生的先后順序排列而成的數列。時間序列分析的主要目的是根據已有的歷史數據對未來進行預測。現實中,由于云環境的動態變化,服務提供商所提供服務質量可能會發生變化,在不同的時間段內,用戶對同一服務具有不同的QoS體驗。由于一段時間內每個服務被調用次數不同,為更真實地反映QoS的變化,將服務不確定QoS值表示為TSGm×2:

(3)

服務被調用m次后,其不確定QoS值可以形式化一個時間序列TSGm×2,Qi(i=1,2,…,m)代表某個具體服務在第i次被調用時QoS的瞬時記錄,qij(i=1,2,…,m;j=1,2)代表第j個QoS指標在第i次調用時的記錄值。

組合服務(CS)的QoS屬性用鏈表表示,記為List(CS)。服務組合中的每個節點表示對應抽象服務下所選擇的具體服務,即鏈表中每個節點代表一個具體的候選服務。

表1 組合服務QoS計算方法Tab.1 QoS computation formula of four basic composition patterns

2.3 目標函數

(4)

(5)

3 算法設計

3.1 基本遺傳算法

由于遺傳算法(GA)實現步驟簡單,并且具有良好的全局收斂能力、自適應能力和并行能力,目前已經被廣泛成功地應用于多個領域?；具z傳算法流程如圖1所示。

圖1 基本遺傳算法流程Fig. 1 Flow chart of basic genetic algorithm

采用遺傳算法求解服務組合問題的優點是規則簡單、編碼簡單,并且具有較強的全局尋優能力。其缺點是：穩定性差,遺傳算法屬于隨機性算法,需要進行多次運算,結果的可靠性差；易早熟收斂,即對新空間探索能力有限,易收斂到局部最優解。因此,在求解現實問題時,都需要對遺傳算法進行適當改進,提高算法效率。

3.2 算法改進策略

文獻[9]中將精英選擇策略應用到遺傳算法,以代替標準遺傳算法中的輪盤賭選擇策略,并指出精英選擇策略具有能夠防止最優個體的丟失、提高群體收斂速度等優點。但是,相對于輪盤賭選擇策略,精英選擇策略每次都需要從種群中選擇最好的部分個體,該操作將會使得種群多樣性丟失,極易導致早熟收斂,從而降低尋優精度。另外,采用精英選擇策略,每次選擇都需要對種群所有個體進行排序,時間開銷過大,造成運行時間很不理想。為此,本文提出一種改進遺傳算法T-GA(Tournament strategy GA),以提高遺傳算法的普適性和尋優性能。

T-GA中采用錦標賽選擇策略代替基本遺傳算法中輪盤賭選擇策略,每次進行選擇時,適應度較好的個體被選擇的概率較大。同時,由于它只是使用適應值的相對值作為選擇的標準,而與適應度的數值大小不成直接比例，從而能避免超級個體的影響,在一定程度上既使得種群保持了多樣性,防止早熟收斂,又提高了群體收斂速度。

錦標賽選擇策略每次從種群中選取出一定數量的個體,然后選擇其中最好的一個進入子代種群，重復該操作,直到新的種群規模達到原來的種群規模。具體的操作步驟如下:

1)確定每次選擇的個體數量R。

2)從種群中隨機選擇R個個體(每個個體入選的概率相同),根據每個個體的適應度值,選擇其中適應度值最好的個體進入子代種群。

3)重復步驟2)N次,得到的個體構成新一代種群。

3.3 算法描述

實驗中,組合服務是一個五元組,即每個CS記錄包含五個子服務過程。每個子服務作為染色體上的一個基因位,每個CS包含五個基因位。每個基因位置屬于不同的候選服務集。根據適應度函數計算適應度值,通過迭代,本文算法能夠找到最優組合方案。本文算法中種群采用實數編碼,具體算法描述如下。

算法1 T-GA。

Initializesmembers randomly as populationP

Evaluate each member inP

P′=NULL

while stop criterion not met do

Select (1-Pc)*smembers fromPby tournament and insert intoP′

Randomly selectpc*smembers fromPwith no duplicate

Crossover(Pc)

Insert the offspring intoP′

Randomly selectu*smembers fromP′

for each selected memberido

Mutation(u)

end for

P=P′

Evaluate each member inP

end while

returnbestmember

其中:s為初始種群數量,P為父代種群,P′為子代種群。在選擇操作中采用輪盤賭選擇策略從種群中選擇(1-Pc)*s個父代個體直接遺傳到子代,然后,將父代剩余個體進行交叉操作Crossover(Pc),采用單點交叉,其中交叉位置隨機產生,將交叉得到的個體保存到子代種群P′中。然后,從P′中隨機選擇u*s數量的個體進行變異操作Mutation(u),同樣,變異位置通過隨機產生。通過選擇、交叉和變異操作,本文算法不僅能夠使得種群保持了多樣性,防止早熟收斂,而且提高了種群收斂速度。

4 實驗分析

為驗證所提出時間序列模型的可行性,以及本文算法T-GA的性能,以公共數據集WSDream[3]為測試數據，將本文算法與基于精英選擇策略的遺傳算法(Genetic Algorithm based on Elite selection strategy, E-GA)[9]進行對比。

4.1 實驗數據與環境

為了使實驗更具代表性,實驗數據采用Zhang等的公用數據集WSDream[3],包含142個用戶在64個時間間隔對4 532個Web服務的響應時間和吞吐量的真實記錄值,現實世界中,大部分用戶都只調用過少數的Web服務,所以每個服務的真實調用記錄并不都包含64個時刻記錄。實驗環境為: 64位Windows 7 OS,Intel Core i7-4790 CPU @3.60 GHz,4 GB RAM,Visio Studio 2010。

由于數據集較為龐大,需要對數據進行處理,從中選取一部分數據作為實驗的真實數據。數據抽取操作步驟如下:

1)從數據源中抽取Service User ID為0的數據。

2)對數據進行降噪處理。

3)將數據集按Web Service ID提取出對應的QoS值時間序列,得到用戶0對1 610個Web Service ID的調用QoS值時間序列。

4)按順序選擇前1 500個Web Service ID作為實驗數據,將得到的數據集分為5組,每組300個Web Service ID對應的QoS值時間序列,每組中的服務提供相同的功能。

4.2 實驗結果與分析

下面評估所提出不定長時間序列(Uncertain-Long Time Series, ULST)模型的可行性和所改進的算法的有效性、效率和穩定性。實驗參數設置如表2所示。

表2 實驗參數設置Tab.2 Experimental parameter settings

圖2 ULST模型可行性Fig. 2 The feasibility of ULST model

4.2.1 ULST模型的可行性

為了驗證不定長時間序列模型的可行性,采用4.1節數據處理所得到的數據,從每個服務對應的時間序列中隨機選取一個QoS值作為該服務的瞬時訪問記錄,將得到的數據分為5組,每組300個Web Service ID對應的QoS值瞬時訪問記錄,每組中的服務提供相同的功能。

圖2中:Instant1和Instant2分別代表兩次隨機操作的結果,即瞬時QoS性能。從圖2可以看出,本文方法較瞬時訪問結果有所提高。

4.2.2 算法有效性分析

為了進行算法的有效性對比,在如下實驗參數設置下進行100次重復實驗,取其均值為最終衡量指標,實驗結果如表3所示。其中：種群規模為100,迭代次數為500,變異概率為0.15,交叉概率為0.8,QoS的維度為2,任務數量為5,每個任務的候選服務數以50為步長從50遞增到300。

從表3可以看出,隨著候選服務數量的增加,本文算法獲得的最優解優于E-GA[9],表明本文算法的尋優精度高。候選服務數在50和100時,由于候選服務數量少,兩種算法都能夠收斂到最優解;但隨著候選服務數量繼續增大,本文算法在收斂精度上具有明顯的優勢。

表3 不同候選服務數據集大小的適應度值對比Tab.3 Fitness value comparison with different candidate service dataset sizes

4.2.3 算法的時間效率分析

為進一步分析T-GA和E-GA的時間開銷,本文分別進行了兩組對比實驗:

1)具有不同的種群大小和相同的迭代次數(100)進行優化100次的平均運行時間(如圖3(a)所示);

圖3 算法在不同實際條件下的平均運行時間對比Fig. 3 Average running time comparison of algorithms under different actual conditions

2)具有相同的種群大小(100)和不同的迭代次數進行優化100次的平均運行時間(如圖3(b)所示)。

從圖3(a)可以看出,相同迭代次數情況下,隨著種群規模的增大,算法運行時間也在增加,且算法的運行時間與種群規模大小呈線性關系；同樣,如圖3(b),種群大小相同,隨著迭代次數的增加,算法運行時間與種群迭代次數呈線性增加。因此,在時間開銷方面,本文算法具有E-GA無法替代的優勢。

4.2.4 算法穩定性分析

為驗證T-GA尋優結果的穩定性,采用均方差(Root Mean Square Error, RMSE)驗證不同算法的穩定性。RMSE定義如下:

(6)

其中:xi表示第i次實驗結果；x表示n次實驗的平均結果。

圖4 不同算法的均方差對比Fig. 4 RMSE comparison of different algorithms

從圖4可以看出,隨著候選服務數的增加,算法的均方差值也在逐漸上升,即穩定性在降低,候選服務數越多,結果越不穩定。實驗結果可看出：E-GA尋優結果的波動性較大；而T-GA尋優結果的均方差低于E-GA算法,表明本文算法具有更好的穩定性。

4.2.5 變異概率u的影響

遺傳算法中,變異是模擬生物在自然環境中由于各種偶然因素引起的基因突變過程。變異概率u是遺傳算法中的重要參數,變異運算是種群產生新個體的輔助方法,決定了遺傳算法的局部搜索能力,同時保持種群多樣性,避免進化停滯,出現早熟收斂,其概率分布在0.1～1,變異體現了全局最優解的全局覆蓋。在遺傳算法中,為測試變異概率對算法的影響,設置候選服務規模為300,u的變化為0.1～0.9,步長為0.1。運行100次的平均適應度值的統計結果如圖5所示。

從圖5可以看出,在相同候選服務規模下,E-GA尋優結果隨u的不同而變化；T-GA在不同參數設置下,即使在相應參數變化足夠大時,尋優結果仍趨于不變，說明本文算法具有很好的穩定性。

以上實驗結果表明：本文提出的ULST模型能夠有效地解決不確定QoS感知的云服務組合問題；并且,結合所提出的改進遺傳算法T-GA的有效性、效率和穩定性來看,T-GA能夠有效地解決不確定性云服務組合優化問題。

圖5 變異概率對平均適應度值的影響Fig. 5 Influence of mutation probability on average fitness value

5 結語

本文研究基于不確定QoS感知的云服務組合問題,首先,提出了一種基于不確定性QoS感知的云服務組合時間序列模型,將服務的QoS值隨時間變化過程建模為不定長時間序列,該模型能夠準確地描述用戶對服務訪問的真實記錄;其次,采用一種改進的遺傳算法找尋最優解,該算法通過引入輪盤賭選擇策略改進基本遺傳算法選擇策略,使得算法能有效地避免早熟收斂,較好地提高算法的全局收斂能力和搜索效率。實驗結果表明了本文方法的可行性和有效性。在今后的工作中,將研究跨界服務不確定QoS問題,尋找一種解決復雜不確定性跨界服務系統的優化均衡方法。