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

王思臣,涂 輝,張以文

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

0 引言

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

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

1 相關工作

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

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

2 問題描述

2.1 相關概念

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

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

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

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

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

RT=Texe+Ttrans+Toth

2)吞吐量TH。吞吐量是指服務單位時間內(nèi)可處理的請求數(shù)量。

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

1)效益型：

(1)

2)成本型：

(2)

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

2.2 QoS模型描述

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

(3)

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

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

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

2.3 目標函數(shù)

(4)

(5)

3 算法設計

3.1 基本遺傳算法

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

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

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

3.2 算法改進策略

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

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

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

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

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

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

3.3 算法描述

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

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

4 實驗分析

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

4.1 實驗數(shù)據(jù)與環(huán)境

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

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

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

2)對數(shù)據(jù)進行降噪處理。

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

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

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

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

表2 實驗參數(shù)設置Tab.2 Experimental parameter settings

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

4.2.1 ULST模型的可行性

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

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

4.2.2 算法有效性分析

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

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

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

4.2.3 算法的時間效率分析

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

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

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

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

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

4.2.4 算法穩(wěn)定性分析

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

(6)

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

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

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

4.2.5 變異概率u的影響

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

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

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

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

5 結(jié)語

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