任務粒化的質量約束感知服務組合

張以文 崔光明 嚴遠亭 趙 姝 張燕平

1(計算智能與信號處理教育部重點實驗室(安徽大學) 合肥 230031) 2 (安徽大學計算機科學與技術學院 合肥 230601) (zhangyiwen@ahu.edu.cn)

服務計算作為一種新的計算范式，憑借其以服務為基本構建塊，支持異構環境下分布式應用的快速、低成本、便捷組合的特點得到快速發展，其核心思想是通過重用已有的網絡服務而不是重新開發構造新的企業應用，使得分布在企業內部或跨越企業邊界的不同商業應用系統能得到快捷的實現、靈活的無縫集成和相互協作[1].但隨著越來越多的網絡資源以服務的形式發布與使用，具有相同功能的服務數量迅速增加，加之用戶需求的多樣化、動態化和復雜化等特點，導致服務組合方案呈現出指數增長趨勢，服務組合問題也逐漸演變為NP完全問題.

隨著服務質量(quality of service, QoS)的提出，不同服務之間的衡量更加科學化與規范化，越來越多的有關QoS感知的服務組合方法被應用到服務組合問題求解過程中[2].傳統的服務計算多認為不同服務的QoS具有相互獨立性，且服務之間不存在相互影響.但在實際應用背景下，服務之間往往存在質量約束，例如在圖1所示的網上購物案例中，購物時往往會涉及到商家與部分物流方的協同合作關系，即商家包郵，導致在服務組合優化過程中，同一候選服務在不同的服務組合實例中具有不同的QoS值.

Fig. 1 Case of online shopping圖1 網上購物案例

除此之外，在圖1所示的購物案例中，不同的任務由不同的主體去操作，例如物流服務由不同的物流方進行操作，但物流方如何內部操作，包括取貨、運輸等用戶無需關心，但整體的配送速度會影響用戶的購物體驗.因此，圖1所示的購物案例中，不同的任務之間既存在相互協同合作關系，即服務間的QoS約束問題也存在相互獨立性，即各提供商的內部操作互不影響.現有的服務組合研究較少同時關注這2種現象，尤其在big service[3-4]環境下，這一現象更加普遍.為解決這一問題，本文提出一種任務粒化的質量約束模型，通過將圖1所示的任務按照質量約束進行粒化處理，分解為多個任務粒，然后通過每個任務粒的局部最優選擇逐步逼近全局最優，同時，通過子模態理論，論證了任務粒化模型求解過程的完備性.本文的主要貢獻如下：

1) 提出基于商空間任務粒化的質量約束感知服務組合優化方法，構建了基于任務粒化的分層遞階服務組合模型，可有效解決大規模服務組合優化問題.

2) 總結了現有的QoS屬性聚合方式，從理論上驗證每種聚合方法都具有子模態性質，以及多屬性服務組合問題的效用函數仍具有子模態性質.

3) 提出一種任務粒化的質量約束感知的服務組合算法Tg-QcA，并通過大量的仿真實驗驗證了算法的可行性、高效性和穩定性.

1 分層遞階服務組合模型

為更直觀地描述質量約束感知的服務組合優化問題，基于商空間理論[5-6]，結合服務組合優化問題的常用模型[7-8]，首先給出分層遞階服務組合模型如圖2所示.

Fig. 2 Hierarchical model of service composition圖2 分層遞階服務組合模型

由圖2可知，質量約束的服務組合問題可以分為4層，分別為基本粒層(候選服務層)、功能粒層(任務層)、業務粒層(用戶需求)以及任務粒層(質量約束).其中，前3層均為服務組合問題的描述層，主要用于服務組合優化問題的模型描述，任務粒層則為質量約束感知的服務組合優化問題的求解層，用以形式化表示質量感知的任務粒化方法及求解方法.

1.1 服務組合問題粒化描述

服務組合問題粒化描述是指為形象直觀地描述服務組合問題而構建的分層遞階鏈模型，對應于圖2中基本粒層、功能粒層以及業務粒層，其詳細定義如下：

定義1. 基本粒.是服務組合問題的最小粒，表示每個原子服務，可以描述為一個五元組:s=(id,I,desc,O,Q).其中：

1)id表示每個服務的唯一標識；

2)I表示輸入參數，其定義為I={Is1,Is2,…,Isn};

3)desc表示功能描述；

4)O表述輸出參數，定義為O={Os1,Os2,…,Osn};

5)Q表示每個服務的服務質量QoS，定義Q={cost(Cost),availability(Ava),…}.

基本粒表示每個任務的候選服務，在圖1所示的網上購物案例中，每個候選服務均為基本粒.基本粒作為服務組合問題的基本元素，即服務提供者提供的服務都屬于基本粒.基本粒的數量不斷增加，其組織、存儲、最優化選擇日益困難.所以，為簡化求解用戶需求所包含功能問題的搜索空間，將基本粒按照其功能聚合成功能粒，其定義如下.

定義2. 功能粒.指具有相同功能屬性的基本粒聚類后的粒度表示，對應于服務組合問題的某個特定任務，功能粒包含基本粒.可采用四元組T=(I,desc,S,O) 進行描述.其中：

1)I表示輸入參數，其定義為I={Is1,Is2,…,Isn}；

2)desc表示功能粒描述；

3)S表示基本粒的集合；

4)O表述輸出參數，定義為O={Os1,Os2,…,Osn}.

功能粒包含基本粒，其功能屬性、接口一致，且在服務質量上有所差別.在圖1所示的案例中，將服務組合論域按照功能聚合之后，產生的功能粒個數為3，分別對應每個任務.

在基本粒層中，每個候選服務都是一個基本元素，獲得滿足用戶業務需求的組合服務較難，通過將粒度適度粗化，可以減少問題求解的時間和空間開銷.功能粒層是建立在任務之上，所以，在獲得用戶任務需求時，只需將功能粒商空間中部分任務按照某些邏輯結構有限次組合從而完成特定業務需求，即業務粒.

定義3. 業務粒.表示在某特定業務流程基礎上，滿足用戶需求功能粒的聚類集合，可以使用三元組B=(desc,T,U)表示.其中：

1)desc表示業務粒描述；

2)T表示實現某特定業務流程的功能粒集合；

3)U表示該業務粒的評價函數.

業務粒是解決服務組合問題的橋梁，以及與其應用領域知識的交互接口，在求解服務組合優化問題中是不可或缺的階段.服務組合是建立在業務需求之上，對于不同用戶需求獲得不同的業務流最優解是服務組合的目標.

在服務組合問題的逐層建模過程中，從基本粒到業務粒是問題的逐漸粗化過程，通過篩選用戶需求任務減少問題搜索空間.例如，對于圖1所示的服務組合案例，其對應的分層遞階商空間鏈模型論域描述如下.基本粒商空間論域可表示為{Taobao,…,JD,SF,…,DHL,WeChat,…,UnionPay}，元素個數為候選服務數.將候選服務按照所屬功能進行聚合，可得功能粒商空間的論域為{t1,t2,t3}，其中t1={Taobao,…,JD},t2={SF,…,DHL},t3={WeChat,…,UnionPay}.將功能粒按照用戶業務需求進行2次篩選，可得業務粒商空間.服務組合的分層遞階模型每一層都有實際意義，都可解決本層次的問題.基本粒層是原服務組合問題，可以獲得較多、較細的關于候選服務的信息，例如，基本粒層可以獲得每個候選服務按照輸入輸出構成的拓撲關系，而功能粒層則只有任務級別的拓撲關系；功能粒層相比于基本粒層更易于獲得用戶任務需求；業務粒層可以獲得用戶需求的最優候選服務序列.

1.2 質量約束與任務粒化

在圖2所示的模型中，利用分層遞階模型逐步獲得業務粒層服務組合問題模型，可以大幅度降低服務組合求解的問題搜索域.但在具體的實際應用中，基本粒服務之間往往存在質量約束關系，例如，購物與物流服務之間會存在包郵現象.為解決這一問題，本部分在圖2中業務粒層的基礎上構建任務粒層，其中任務粒的劃分是由基本粒服務之間的質量約束決定.基于此，先給出質量約束定義如下：

定義4. 質量約束.指基本粒服務之間具有的QoS約束關系，可以用三元組qc=(id,S,p)表示.其中：

1)id表示每個質量約束的唯一標識；

2)S表示具有該質量約束的基本粒服務集合；

3)p表示該質量約束的QoS約束值.

質量約束是用于描述服務與服務之間的QoS約束關系，例如圖1所示的服務組合案例，可以抽象為如下服務模型：SC={t1={s1,1,s1,2,s1,3,s1,4},t2={s2,1,s2,2,s2,3},t3={s3,1,s3,2,s3,3}}.質量約束可以抽象為表1(以價格為例)所示：

Table 1 Quality Constraint表1 質量約束

表1所示的質量約束是指基本粒服務s1,1與s2,1之間存在質量約束關系，QoS約束值為服務價格減少$14.

定義5. 隸屬度.指任務與任務之間的耦合度，通過候選服務之間的質量約束數量決定，表示為：M=h(ti,tj).其中，h(ti,tj)表示任務ti和tj之間具有質量約束的數量.通過隸屬度，可以判斷每2個任務間的耦合程度，隸屬度值越大表明該任務之間耦合關系越強，不利于劃分至不同的任務粒.

定義6. 任務粒.指業務粒根據隸屬度函數值將原組合服務問題分解為多個簡單子服務組合問題，可以用三元組Tg=(id,sc′,F)表示.其中：

1)id表示每個粒度劃分的唯一標識；

2)sc′表示原問題業務粒sc的子集，即sc中功能粒的子集；

3)F表示每個粒度劃分的評估函數.

任務粒是對服務組合問題按照粒化需求進行問題分解的形式化表示.例如，圖1所示的網上購物案例，原問題粒表示為{(t1,t2,t3)}，按照任務執行主體，可以將3個任務分為3類，分別為電商平臺方、支付方以及物流方，即任務粒表示為{(t1),(t2),(t3)}.在服務組合問題求解過程中，首先獲得每個子問題的最優解，然后將這些局部最優解進行組合成原問題可行解.若假設每個任務的候選服務數為n，則原問題求解規模為n3，而基于任務粒的求解規模則為n+n+n.尤其在big service環境下，n3?(n+n+n)，原問題的求解復雜度從指數級降為任務線性級，問題的求解規模大幅度降低.

2 粒化可行性分析

在數學上，子模態是集合函數的一種性質，其定義如下：

給定集合U={u1,u2,…,ui,…,un}，其包含n個元素，給定任意函數g:2U→，即g(x)的定義域是集合U的任意子集.若集合U滿足以下3個等價條件之一，則該集合具有子模態性質[9].

1) 對于任意一個X,Y?U,且X?Y,以及對任意x∈U，滿足

g(X∪{x})-g(X)≥g(Y∪{x})-g(Y)；

(1)

2) 對于任意一個X,Y?U，且滿足

g(X)+g(Y)≥g(X∪Y)+g(X∩Y)；

(2)

3) 對于任意一個X?U及x1,x2∈UX，且滿足

g(X∪{x1})+g(X∪{x1})≥
g(X∪{x1,x2})+g(X).

(3)

集合U具有子模態性質時，就是當添加一個新的元素進入集合U時，函數值g的增益隨著集合規模的增大而減小，即函數g滿足邊際效用遞減.從優化問題角度看，服務組合問題屬于多目標優化問題且為NP完全問題，若判斷效用函數滿足子模態性質，則基于簡單的尋優策略，如貪心算法，就可以在多項式時間內獲得高精度的解.基于此，接下來從服務組合效用函數的計算方式入手，其子模態性質分析如下.

2.1 QoS聚合方式

QoS感知的服務組合問題，不同的QoS屬性擁有不同的組合計算方式，但常用的可以歸納為表2所示的5類情況[10-13]:

Table 2 Calculation Method of QoS Combination表2 QoS組合計算方式

在表2所示的QoS組合計算方式中，同一屬性在不同的組合邏輯模型中存在不同的計算方式.例如，響應時間(response time)在順序模型中，一般計算各個任務響應時間之和，但在并行模型中通常取各任務響應時間的最大值.

2.2 QoS聚合子模態分析

根據表2所列的5種QoS聚合方式，假設服務組合問題的基本粒集合為U，對于任意一個U的子集X，即X?U，且x1,x2∈UX，可得每種QoS聚合方式的子模態性質分析如下.

情況1. 和.Sum(X∪{x1})+Sum(X∪{x2})≥Sum(X∪{x1,x2})+Sum(X)，其中Sum(X)表示集合X中各元素的和.

由于x1,x2∈UX，即x1,x2?X，可得Sum(X∪{x1})=Sum(X)+Sum({x1})，所以，Sum(X∪{x1})+Sum(X∪{x2})=2Sum(X)+Sum({x1})+Sum({x2})，Sum(X∪{x1,x2})+Sum(X)≤2Sum(X)+Sum({x1})+Sum({x2})(當x1≠x2時取等號).因此，和式成立.

情況2. 積.Pro(X∪{x1})+Pro(X∪{x2})≥Pro(X∪{x1,x2})+Pro(X)，其中Pro(X)表示集合U中各元素的積.

在候選服務的QoS中， QoS信息均可進行標準化處理，使其恒大于等于1，則Pro類型可以轉換為Sum類型，情況1已證，即也成立.

情況3. 均值.Avg(X∪{x1})=Sum(X∪{x1})(|X|+1)，其中，|X|表示集合X中元素的個數，Sum(X∪{x1})表示集合{X∪{x1}}中各元素的和，Avg(X∪{x1})表示集合{X∪{x1}}中各元素的均值，對于同一服務組合優化問題而言，任務數唯一，則Avg轉換為Sum問題，情況1已證.

情況4. 最大值.max(X∪{x1})+max(X∪{x2})≥max(X∪{x1,x2})+max(X)，其中max(X)表示集合X中各元素最大值，則令y1=max(X∪{x1})+max(X∪{x2})，y2=max(X∪{x1,x2})+max(X)，y1與y2間詳細比較如下：

1) 當max(X)≥max({x1}∪{x2})，則max(X∪{x1})=max(X∪{x2})=max(X∪{x1,x2})=max(X)，即y1=2max(X)=y2.

2) 當max({x1})>max(X)>max({x2})，則max(X∪{x1})=max(X)，max(X∪{x2})=max(X∪{x1,x2})，即y1=max(X∪{x1})+max(X∪{x2})=max(X∪{x1,x2})+max(X)=y2.

3) 當max({x1})>max({x2})>max(X)，則max(X∪{x1})=max(X∪{x1,x2})，max(X∪{x2})>max(X)，即y1>y2.

4) 當max({x2})>max({x1})>max(X)，則與3)類似，可得y1>y2.

5) 當max(X)=max({x1})=max({x2})，則y1=y2.

綜上分析可知，y1≥y2.

情況5. 最小值.min(X∪{x1})+min(X∪{x2})≥min(X∪{x1,x2})+min(X)，其中min(X)表示集合X中各元素最小值，由于min與max類型可相互轉換，則根據情況4易知，顯然成立.

通過上述分析可知，表2所列的組合服務QoS聚合方式均可進行粒化計算，對應于服務組合問題，即原問題可以分解為多個子問題，表明在任務粒化處理過程中QoS聚合方式均滿足子模態性質.

在服務組合優化問題中，每個基本粒服務對應的QoS屬性往往存在多個，即組合服務的效用函數是若干個聚合計算的線性加權，記為多目標效用函數.例如，QoS包含Cost和Availability，其中Cost采用Sum聚合方式，Availability采用Pro的聚合方式，在效用函數的計算時，則是2種方式的線性加權.為驗證多目標效用函數仍滿足子模態性質，引入如下引理1.

引理1. 設g1({x}),g2({x}),…,gk({x})都具有子模態性質，c1,c2,…,ck是非負實數，則函數

(4)

仍具有子模態性質.

證明. 因為g1({x}),g2({x}),…,gk({x})均具有子模態性質，對于任意一個U的子集X，即X?U，且x1,x2∈UX，可得：

g1(X∪{x1})+g1(X∪{x2})≥
g1(X∪{x1,x2})+g1(X),
g2(X∪{x1})+g2(X∪{x2})≥
g2(X∪{x1,x2})+g2(X),
?
gk(X∪{x1})+gk(X∪{x2})≥
gk(X∪{x1,x2})+gk(X).

由上式左右分別加權相加可得：

證畢.

通過上述分析可知，在服務組合優化問題中，常用的QoS聚合方式均滿足子模態性質，多目標效用函數計算仍滿足子模態性質.所以可得，任務粒化的質量約束感知服務組合問題，可以采用貪心算法，并且可以在多項式時間內獲得高精度的解.

3 算法設計

本節主要介紹基于任務粒化的質量約束感知服務組合優化算法，記為Tg-QcA.首先，通過隸屬度進行任務粒的劃分；其次，基于滿足子模態QoS計算方式，并根據每個任務粒的局部尋優獲得top-k解；最后，將每個局部最優組合進行組合獲取全局最優解.由于，每個基本粒服務的QoS存在單屬性和多屬性之分，且多屬性包含單屬性情況，因此，本節將任務粒的劃分和多屬性任務粒化分別進行闡述.

3.1 任務粒化算法

本文所提的粒化思想是基于任務間的隸屬度動態劃分，即對于不同的數據集以及不同的質量約束關系集，所得的任務粒化結果不同.其大致過程可以分為以下3步：首先，統計每個任務的隸屬度值，即每個任務對其他任務而言，存在質量約束的數量；其次，根據隸屬度閾值，對任務粒進行劃分；最后，輸出最終的任務粒.其詳細描述如算法1所示：

算法1. 任務粒化算法.

輸入：任務數n、隸屬度矩陣M、隸屬度閾值γ；

輸出：任務粒集合TS.

① 初始化TS=?,任務粒T=?；

② for eacht1≤n∧t1?TSdo

③T=?;

④T.add(t1)；

⑤ for eacht2≤n∧t2?TS∧t2≠t1do

⑥ if ?t3∈T∧M(t3,t2)≥γthen

⑦T.add(t2)；

⑧ end if

⑨ end for

⑩TS.add(T)；

其中，M(t3,t2)表示隸屬度矩陣M中的t3行的t2列的隸屬度值.由算法1可知，任務粒劃分的對象是每個任務，即確定每個任務的歸屬任務粒.以圖1和表1為例，可以構造任務之間的隸屬度矩陣如下所示：

(5)

其中，矩陣M的行列均表示任務t1至t3，且第i行第j列對應的數值表示任務ti和tj的隸屬度值.若設置隸屬度閾值為3，則式(5)所示的隸屬度矩陣可將任務t1至t3分為2個任務粒(t1,t2)與(t3)，若將隸屬度閾值設為2，則只可分為一個任務粒(t1,t2,t3)，這是由于任務t1與t2的隸屬度大于等于2，雖然任務t1和t3的隸屬度不大于2，但任務t2與t3的隸屬度大于等于2，因此任務t1,t2,t3均屬于同一任務粒.

3.2 多屬性驗證算法

多屬性是指每個候選服務的QoS不唯一，其計算方式是表2所列的計算方式的線性組合.由于多屬性服務組合問題，在每一維度上均最優的候選服務不一定存在，本部分則利用候選服務的效用函數(式(4))作為衡量指標，然后取每個任務粒的top-k個最優解.最后將各個任務粒的top-k個最優解進行枚舉，取其最優解作為原問題的解，其詳細過程如算法2所示:

算法2. 多屬性任務粒化驗證算法.

輸入：每個任務粒；

輸出：服務組合最優解.

① 初始化bestfit=0；

② Get thekvalue of the top-k；

③ Generate an arraybest[n,k] to keep the best services；

④ for eachsi∈sdo

⑤ for eachsi,j∈sido

⑥ Keep the top-kbest servicessi,j；

⑦ end for

⑧ Addsi,jintobest[i,k]；

⑨ end for

⑩ for eachsi,j∈best[n,k] do

其中，best[n,k]表示保存每個任務粒中top-k最優解，Enume(best[n,k])表示獲得best[n,k]中的枚舉最優解.在任務粒的枚舉過程中，對每一種服務組合方式均須進行質量約束計算，并取約束之后的結果作為最優化選擇依據.

4 實驗分析

為驗證基于任務粒化的質量約束感知的服務組合優化模型的可行性，以及本文算法Tg-QcA的高效性和穩定性，本部分以公共數據集QWS為測試數據[14-15].通過與考慮質量約束的粒子群算法(Qc-PSO[16])、采用剪枝優化的質量感知服務選擇算法(CASP[7])以及沒考慮質量約束的粒子群算法(PSO)進行對比，驗證本文所提求解方案的可行性、高效性以及穩定性.

4.1 實驗環境

本實驗環境是Microsoft Visual Studio 2010，編程語言為C#，實驗機器配置為16 GB內存、core i7 3.6 GHz處理器、Windows 7操作系統.任務數為5，每個任務的候選服務數從100遞變到500，每次實驗進行100次重復實驗，取其均值作為最終衡量指標，對比算法PSO中參數設置如表3所示：

Table 3 Experimental Parameter Settings表3 PSO算法實驗參數表

對于混合多屬性計算方式而言，TgA-k表示每個任務粒度中取top-k個最優解.

4.2 實驗結果與分析

針對本文所提任務粒化算法，本節首先驗證不同規模的質量約束數據集對服務組合問題尋優結果的影響；其次，驗證不同的QoS維數對任務粒化服務組合尋優結果的影響；最后，驗證不同候選服務數量對服務組合尋優結果的影響證.其中，采用均方差RMSE驗證不同算法的穩定性，定義如下：

(6)

其中，xi表示第i次實驗結果，x表示n次實驗的平均結果.

4.2.1 質量約束的影響

為驗證質量約束對服務組合優化問題的影響，本節通過在如下實驗參數設置下進行100次重復實驗，取其均值，結果如圖3所示.其中，每個任務的候選服務數量為450，QoS的維度為2，任務數量為5，質量約束比例以5%為步長從5%遞增到30%.

從圖3(a)可以看出，存在質量約束的情況下，服務組合問題的優化結果顯著提高，并且，隨著質量約束比例的增加，服務組合問題優化精度越來越高，表明質量約束的影響越來越大.CASP是基于剪枝的服務選擇算法，屬于一種枚舉的優化算法，因此，在圖3(a)中CASP與Tg-QcA尋優結果一致，表明本文算法具有優秀的全局尋優能力.尤其，從圖3(b)可以看出，本文算法相比于CASP而言，尋優時間顯著較低，綜合表明本文算法尋優能力強的同時具有很高的尋優效率.雖然從圖3(b)可以看出，存在質量約束的服務組合尋優時間相比于沒質量約束的要長，但是相比于其精度提升而言，在任務粒化方法中，其時間開銷可以忽略，對比Tg-QcA和Qc-PSO 2條時間曲線可以看出，在解決質量約束的服務組合優化問題時，任務粒化的時間優勢非常明顯.從圖3(c)可以看出，Tg-QcA算法是基于任務粒化的服務組合優化方法，其均方差近乎于0，顯著低于其他2種算法，表明本算法具有很好的穩定性，并且結合圖3(a)的尋優結果可知，本文算法在質量約束逐漸增加的情形下，具有優秀的尋優精度、尋優效率和尋優穩定性.

Fig. 4 Impact of QoS dimension圖4 QoS維數的影響

4.2.2 QoS維數的影響

為驗證QoS維數對質量約束感知服務組合優化問題的影響，本節通過在表3實驗參數設置下進行100次重復實驗，取其均值，實驗結果如圖4所示.其中，每個任務的候選服務數量為450，任務數量為5，質量約束比例為20%，QoS維數從1變化到9，其遞增步長為1.

從圖4(a)可以看出，隨著QoS維數的增加，服務組合優化問題的尋優結果逐步提高，實驗結果表明在QoS維度變化過程中，質量約束仍起到至關重要的作用，尤其隨著QoS維度的增加，質量約束的效果更明顯，即曲線間的差距越大.與質量約束影響結果類似，本文算法取得了與CASP一致的尋優精度，并且其時間開銷顯著低于CASP.由圖4(b)可以看出，隨著QoS維度的增加，尋優時間幾乎不增加，這是由于QoS維度只用于每個服務組合實例的效用值計算，其影響甚微，乃至于在大刻度的坐標軸下變化近乎為0，但從曲線的間距可以看出，采用任務粒化的質量感知服務組合優化算法的時間開銷遠小于Qc-PSO.由圖4(c)可以看出，Tg-QcA的均方差近乎于0，顯著低于其他2種算法，表明本算法具有很好的穩定性.綜上可知，本文算法在QoS維度逐漸增加的情形下，同樣具有很好的尋優精度、尋優效率和尋優穩定性.

4.2.3 候選服務數量的影響

為驗證候選服務數對質量約束感知服務組合優化問題的影響，本節通過在如下實驗參數設置下進行100次重復實驗，取其均值，實驗結果如圖5所示.其中，QoS的維度為2，任務數量為5，質量約束比例為20%，候選服務數量以50為步長，從50遞增到450.

Fig. 5 Impact of candidate service number圖5 候選服務數的影響

由圖5(a)可以看出，隨著候選服務數量的增加，Tg-QcA獲得的效用值最大，表明該算法的尋優精度最高，而且遠大于其他2種算法.Qc-PSO在任務數量較小的情況下，尋優效果不高于PSO，這是由于候選服務較少，對應的質量約束較少，而PSO又是一種隨機的啟發式群體智能算法，以至于結果具有隨機性.雖然隨著候選服務數量的增加，Qc-PSO的尋優效果逐步上升，但仍遠小于Tg-QcA.同樣，本文算法的尋優精度與CASP一致的同時，本文算法的時間效率遠高于CASP.從圖5(b)可以看出，隨著候選服務數的增加，Tg-QcA的時間開銷增大，但遠小于Qc-PSO，表明本文算法具有很好的時間性能.圖5(c)的實驗結果同樣反映了Tg-QcA的均方差接近于0，顯著低于其他2種算法，同樣表明本文算法具有很好的穩定性.

5 相關工作

本文旨在利用任務粒化思想解決質量約束感知的服務組合優化問題，通過對候選服務間的質量約束判斷任務間的隸屬度值，然后進行任務粒的劃分，進一步降低問題的求解規模，并逐步獲得原問題的最優解.從粒化角度，現有質量約束感知的服務組合優化方法主要可以分為2類：基于非粒化思想質量約束求解算法和基于粒化思想質量約束求解算法.

1) 基于非粒化思想質量約束求解算法

隨著QoS衡量方式的出現，考慮QoS之間關聯的研究成果也隨之出現.文獻[17]中利用了整數規劃表達式求解服務組合優化問題，而且構建適用于多QoS約束的整數規劃模型.文獻[18]在文獻[17]的基礎上給出有狀態的Web服務組合優化約束表達式.文獻[19]給出了服務質量依賴于其他可選服務，即提出支持服務關聯的QoS模型，而且利用整數規劃與啟發式求解問題最優解，但其關系模型構建較為復雜，尤其當候選服務數量較大時，其關系描述較為臃腫，不利于推廣.文獻[20]提出業務約束模型，并且利用改進遺傳算法解決QoS約束服務組合優化問題，但該文只限于2個而且是抽象的任務之間進行組合優化，實用性極大受限.文獻[7]提出一種QoS關聯的服務組合優化問題研究，在文章中通過以Response time為例構建系統的場景分析和同一個服務提供商的QoS約束模型，但沒能系統考慮QoS在整個組合服務中的關聯關系.

2) 基于粒化思想質量約束求解算法

近年來，考慮粒度的服務組合問題也有相關研究，但只是將粒度概念引入服務組合問題，而且解決的是服務組合中的特定問題.例如，文獻[21]利用多粒度方法分析一個提供商提供多個服務問題，并且采用圖的思路解決最優化問題.文獻[22]提出多粒度服務組合模型，利用粒度思想進行服務發現，并采用改進遺傳算法解決服務組合問題.文獻[23]提出一種多粒度上下文模型，獲得更多的上下文信息，用以解決更復雜的服務組合問題.在這類研究中，只是將服務組合部分過程進行粒度化處理，沒有系統考慮粒度下的服務組合問題.在質量約束感知的服務組合優化方面，文獻[16]引入粒度思想，但屬于將質量約束進行聚合操作，而不是對問題進行分解.

6 總 結

通過對質量約束感知的服務組合優化問題的分析，發現服務組合優化問題可以進行粒化處理，以便將復雜的服務組合過程分解為多個簡單的服務組合子問題.基于此，本文利用商空間理論將服務間的質量約束進行任務間的粒度劃分，即根據任務間的隸屬度值決定每個任務的歸屬.從理論方面分析了每個候選服務的QoS聚合方式均具有子模態性質，從而保證了任務粒化的精度和問題的完備性.進一步地，通過對任務粒化分析，提出基于任務粒化的質量約束感知服務組合優化算法Tg-QcA，并通過大量的仿真實驗，在質量約束數量、QoS維數以及候選服務數量3個方面驗證了本文算法的性能.本文模型對大數據驅動的大服務生態系統環境下大規模、高頻實時、跨領域協同的服務組合問題求解具有重要的理論和實踐參考價值.

[1]Wu Quanwang, Zhu Qingsheng. Transactional and QoS-aware dynamic service composition based on ant colony optimization[J]. Future Generation Computer Systems, 2013, 29(5): 1112-1119

[2]Ma You, Wang Shangguang, Hung P C K, et al. A highly accurate prediction algorithm for unknown Web service QoS values[J]. IEEE Trans on Services Computing, 2016, 9(4): 511-523

[3]Zheng Zibin, Zhu Jieming, Lyu M R. Service-generated big data and big data-as-a-service: An overview[C]Proc of IEEE Int conf on Big Data. Piscataway, NJ: IEEE, 2013: 403-410

[4]Xu Xiaofei, Sheng Quan, Zhang Liangjie, et al. From big data to big service[J]. Computer, 2015, 48(7): 80-83

[5]Zhang Ling, Zhang Bo. The quotient space theory of problem solving[J]. Fundamenta Informaticae, 2004, 59(23): 287-298

[6]Zhang Yanping, Zhang Ling, Xu Chenchu. The property of different granule and granular methods based on quotient space[M]Information Granularity, Big Data, and Computational Intelligence. Berlin: Springer, 2015: 171-190

[7]Deng Shuiguang, Wu Hongyue, Hu Daning, et al. Service selection for composition with QoS correlations[J]. IEEE Trans on Services Computing, 2016, 9(2): 291-303

[8]Deng Shuiguang, Huang Longtao, Hu Daning, et al. Mobility-enabled service selection for composite services[J]. IEEE Trans on Services Computing, 2016, 9(3): 394-407

[9]Kempe D, Kleinberg J, Tardos é. Maximizing the spread of influence through a social network[C]Proc of the 9th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2003: 137-146

[10]Zhang Yiwen, Cui Guangming, Zhao Shu, et al. IFOA4WSC: A quick and effective algorithm for QoS-aware service composition[J]. International Journal of Web and Grid Services, 2016, 12(1): 81-108

[11]Al-Helal H, Gamble R. Introducing replaceability into Web service composition[J]. IEEE Trans on Services Computing, 2014, 7(2): 198-209

[12]Zhang Yiwen, Cui Guangming, Wang Yan, et al. An optimization algorithm for service composition based on an improved FOA[J]. Tsinghua Science & Technology, 2015, 20(1): 90-99

[13]Jatoth C, Gangadharan G R, Buyya R. Computational intelligence based QoS-aware Web service composition: A systematic literature review[J]. IEEE Trans on Services Computing, 2017, 10(3): 475-492

[14]Al-Masri E, Mahmoud Q H. Discovering the best Web service[C]Proc of the 16th Int Conf on World Wide Web. New York: ACM, 2007: 1257-1258

[15]Al-Masri E, Mahmoud Q H. Qos-based discovery and ranking of Web services[C]Proc of the 16th Int Conf on Computer Communications and Networks. Piscataway, NJ: IEEE, 2007: 529-534

[16]Zhang Yiwen, Cui Guangming, Deng Shuiguang, et al. Alliance-aware service composition based on quotient space[C]Proc of Int Conf on Web Services. Piscataway, NJ: IEEE, 2016: 340-347

[17]Zeng L, Benatallah B, Ngu A H H, et al. Qos-aware middleware for Web services composition[J]. IEEE Trans on Software Engineering, 2004, 30(5): 311-327

[18]Ardagna D, Pernici B. Adaptive services composition in flexible processes[J]. IEEE Trans on Software Engineering, 2007, 33(6): 369-384

[19]Ren Lifang, Wang Wenjian, Xu Hang. Uncertainty-aware adaptive service composition in cloud computing[J]. Journal of Computer Research and Development, 2016, 53(12): 2867-2881 (in Chinese)(任麗芳, 王文劍, 許行. 不確定感知的自適應云計算服務組合[J]. 計算機研究與發展, 2016, 53(12): 2867-2881)

[20]Wu Quanwang, Zhu Qingsheng, Zhou Mingqiang. A correlation-driven optimal service selection approach for virtual enterprise establishment[J]. Journal of Intelligent Manufacturing, 2014, 25(6): 1441-1453

[21]Barakat L, Miles S, Poernomo I, et al. Efficient multi-granularity service composition[C]Proc of IEEE Int Conf on Web Services. Piscataway, NJ: IEEE, 2011: 227-234

[22]Wu Quanwang, Zhu Qingsheng, Jian Xing. Qos-aware multi-granularity service composition based on generalized component services[C]Proc of Int Conf on Service-Oriented Computing. Berlin: Springer, 2013: 446-455

[23]Niu Wenjia, Li Gang, Zhao Zhijun, et al. Multi-granularity context model for dynamic Web service composition[J]. Journal of Network and Computer Applications, 2011, 34(1): 312-326

ZhangYiwen, born in 1976. Received his PhD degree from Hefei University of Technology in 2013. Associate professor. Member of CCF. His main research interests include service computing, big data and cloud computing.

CuiGuangming, born in 1991. Master in Anhui University. His main research interests include service computing, evolutionary computing etc.

YanYuanting, born in 1986. Received his PhD degree in Anhui University. Lecturer. His main research interests include machine learning granular computing and bioinformatics.

ZhaoShu, born in 1979. Received her PhD degree from Anhui University. Professor. Her main research interests include machine learning, quotient space theory and social network.

ZhangYanping, born in 1962. PhD and professor in Anhui University. Her main research interests include computational intelligence, quotient space theory, granular computing and machine learning.