王思臣,涂 輝,張以文

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

0 引言

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

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

1 相關(guān)工作

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

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

2 問題描述

2.1 相關(guān)概念

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

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

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

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

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

RT=Texe+Ttrans+Toth

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

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

1)效益型：

(1)

2)成本型：

(2)

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

2.2 QoS模型描述

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

(3)

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

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

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

2.3 目標(biāo)函數(shù)

(4)

(5)

3 算法設(shè)計

3.1 基本遺傳算法

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

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

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

3.2 算法改進(jìn)策略

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

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

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

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

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

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

3.3 算法描述

實驗中,組合服務(wù)是一個五元組,即每個CS記錄包含五個子服務(wù)過程。每個子服務(wù)作為染色體上的一個基因位,每個CS包含五個基因位。每個基因位置屬于不同的候選服務(wù)集。根據(jù)適應(yīng)度函數(shù)計算適應(yīng)度值,通過迭代,本文算法能夠找到最優(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個父代個體直接遺傳到子代,然后,將父代剩余個體進(jìn)行交叉操作Crossover(Pc),采用單點交叉,其中交叉位置隨機產(chǎn)生,將交叉得到的個體保存到子代種群P′中。然后,從P′中隨機選擇u*s數(shù)量的個體進(jìn)行變異操作Mutation(u),同樣,變異位置通過隨機產(chǎn)生。通過選擇、交叉和變異操作,本文算法不僅能夠使得種群保持了多樣性,防止早熟收斂,而且提高了種群收斂速度。

4 實驗分析

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

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

為了使實驗更具代表性,實驗數(shù)據(jù)采用Zhang等的公用數(shù)據(jù)集WSDream[3],包含142個用戶在64個時間間隔對4 532個Web服務(wù)的響應(yīng)時間和吞吐量的真實記錄值,現(xiàn)實世界中,大部分用戶都只調(diào)用過少數(shù)的Web服務(wù),所以每個服務(wù)的真實調(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ù)進(jìn)行處理,從中選取一部分?jǐn)?shù)據(jù)作為實驗的真實數(shù)據(jù)。數(shù)據(jù)抽取操作步驟如下:

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

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

3)將數(shù)據(jù)集按Web Service ID提取出對應(yīng)的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對應(yīng)的QoS值時間序列,每組中的服務(wù)提供相同的功能。

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

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

表2 實驗參數(shù)設(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ù),從每個服務(wù)對應(yīng)的時間序列中隨機選取一個QoS值作為該服務(wù)的瞬時訪問記錄,將得到的數(shù)據(jù)分為5組,每組300個Web Service ID對應(yīng)的QoS值瞬時訪問記錄,每組中的服務(wù)提供相同的功能。

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

4.2.2 算法有效性分析

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

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

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

4.2.3 算法的時間效率分析

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

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

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

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

從圖3(a)可以看出,相同迭代次數(shù)情況下,隨著種群規(guī)模的增大,算法運行時間也在增加,且算法的運行時間與種群規(guī)模大小呈線性關(guān)系；同樣,如圖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可以看出,隨著候選服務(wù)數(shù)的增加,算法的均方差值也在逐漸上升,即穩(wěn)定性在降低,候選服務(wù)數(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)生新個體的輔助方法,決定了遺傳算法的局部搜索能力,同時保持種群多樣性,避免進(jìn)化停滯,出現(xiàn)早熟收斂,其概率分布在0.1～1,變異體現(xiàn)了全局最優(yōu)解的全局覆蓋。在遺傳算法中,為測試變異概率對算法的影響,設(shè)置候選服務(wù)規(guī)模為300,u的變化為0.1～0.9,步長為0.1。運行100次的平均適應(yīng)度值的統(tǒng)計結(jié)果如圖5所示。

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

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

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

5 結(jié)語

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