基于圖的三階段Web服務組合方法

孫朋姣，郭學俊，張鵬程

（河海大學 計算機與信息學院，江蘇 南京211100）

0 引 言

Web服務技術高速發(fā)展，通過服務組合來滿足用戶需求已經(jīng)成為必然趨勢。網(wǎng)絡上存在著大量功能和模型結(jié)構(gòu)相同而服務質(zhì)量各異的服務［1］，如何從中選取合適的服務組合成一個高質(zhì)量的大粒度服務，眾多學者對此做了不同深度的研究。主要有基于圖的算法［2－5］和遺傳算法［6］兩種。遺傳算法雖能解決全局最優(yōu)問題，但容易出現(xiàn)收斂性差和結(jié)果不穩(wěn)定的情況［7］?；趫D的Web服務組合方法，其模型簡潔，能夠很好地處理多路徑選擇，運行一次就能夠找到最優(yōu)組合，因而在實踐中被經(jīng)常采用［8］。

基于圖的Web服務組合方法將整個候選服務空間中的服務及服務之間的相互關系抽象為一個有向圖，構(gòu)造出一個基于圖的Web服務組合模型，然后利用圖算法求取最優(yōu)組合方案。應用于服務組合的圖算法主要有動態(tài)規(guī)劃算法、Dijkstra算法、Bellman－Ford算法、MCSP－K算法等。文獻［2］將Web服務組合的每個服務任務看成一個階段，將完成每個任務的候選服務看成有向圖的結(jié)點，將服務之間的調(diào)用關系抽象為有向圖的有向邊，將調(diào)用每個服務的成本作為權值，然后利用動態(tài)規(guī)劃算法求得起點到終點的最小總成本。由于每個階段只考慮到固定的服務任務，該方法只適合單一路徑的情況，而不適合用戶的多路徑選擇需求。文獻 ［3］構(gòu)造的有向圖的結(jié)點集合由情景中出現(xiàn)的輸入和輸出動作組成，邊的集合由從每個輸入動作到輸出動作的服務組成，權值為各服務的總QoS值，組合算法采用Dijkstra算法，由于每個服務的輸入和輸出信息都是基于特定情景的，方法實用性較差。文獻 ［4］使用的是Bellman－Ford算法，它和Dijkstra算法相似，但服務的權值可以為負，可以解決服務間有負關聯(lián)的組合，但沒有考慮到用戶的約束條件。文獻 ［5］中的MCSP－K算法能夠考慮到用戶的多QoS約束需求，算法采用的圖模型支持多路徑選擇。這些組合算法的時間復雜度在候選服務規(guī)模較少時還可以接受，當候選服務規(guī)模持續(xù)增大，有向圖的點集、邊集也會呈指數(shù)增長，影響了組合效率。為了提高組合效率，本文提出一種新的基于圖的Web服務組合方法Sky－MCSP－R，該方法將服務組合分為3個階段進行，首先從候選服務空間中篩選出Skyline服務，接著用改進的MCSP－K算法求得可行解，最后用Relax算法求取最優(yōu)解。實驗結(jié)果表明此方法在保持較高優(yōu)化率的基礎上提高了組合效率，減少了無解現(xiàn)象。

1 基于圖的Web服務組合模型

一個滿足用戶需求的大粒度Web服務可由組成這個服務的各個任務所對應小粒度Web服務組合而成。在互聯(lián)網(wǎng)上能完成一個特定任務的候選Web服務有很多，即它們的功能屬性相同。但功能屬性相同的服務的非功能屬性卻不相同，也即服務質(zhì)量 （QoS）不相同，常用的QoS屬性有時延、費用、可靠性、信譽度、可用性、安全性等。

每個QoS屬性值qj＊（1≤j≤l）都可以歸一化［9］為一個在 ［0，1］區(qū)間內(nèi)的值qj，且質(zhì)量越高其值越大。假設有l(wèi)個QoS指標，用戶規(guī)定其權值為wi，則單個Web服務si（1≤i≤n） 的綜合QoS值可以表示為

則包含n個任務的組合服務S的綜合QoS值可以線性化表示為

C＝ ｛C1，C2，…，Cm｝，1≤m≤l表示用戶的全局QoS約束集合，則

基于圖的Web服務組合方法把各個候選的Web服務抽象成有向圖的一個個結(jié)點，把服務之間的前驅(qū)后繼關系抽象成有向圖的有向邊。圖1就是這樣一有向無環(huán)圖（DAG），每個圓角矩形框代表一個候選服務類Si（i ≥ 1），這個服務類表示一個特定的服務任務，每個服務類所包含的候選服務用其中的橢圓形Vi（i≥1）表示，候選服務之間的有向邊表明了服務之間的前驅(qū)后繼關系。若Si和Si＋1之間存在一條有向邊，則表明完成任務Si后可選的任務是Si＋1。起點Vs終點Vd是兩個虛服務。

滿足QoS約束條件的服務組合問題可以轉(zhuǎn)化為一個求得從起始點Vs到終止點Vd的最優(yōu)組合服務路徑問題，這條路徑經(jīng)式 （2）計算有較高的QoS值，并且滿足式 （3）所規(guī)定的約束條件。由于完成特定功能的組合服務有多組不同的服務任務可選，因此這個基于圖的Web服務組合模型可以很方便處理多路徑選擇。為了提高組合效率，本文提出的服務組合方法Sky－MCSP－R將減少模型的結(jié)點規(guī)模，在服務組合之前除去不可能出現(xiàn)在最優(yōu)組合路徑中的結(jié)點，然后采用引入了過約束機制的MCSP－K算法進行服務組合，以產(chǎn)生盡可能多的可行解，最后運用Relax算法求得最優(yōu)解。

圖1 基于圖的Web服務組合模型

2 Web服務組合方法Sky－MCSP－R

Sky－MCSP－R是一種基于圖的三階段 Web服務組合方法，第一階段對候選服務空間進行Skyline，為每個服務類篩選出一部分高質(zhì)量候選服務，縮小DAG的結(jié)點規(guī)模。第二階段采用引入了過約束機制的MCSP－K算法進行服務組合，得到可行解。第三階段對這些可行解運用Relax算法求得最優(yōu)解。Sky－MCSP－R方法能夠在保持較高的優(yōu)化率的基礎上提高求解速度，減少無解現(xiàn)象。這依賴于各個階段算法的恰當選取和良好圖模型的構(gòu)造。選擇圖1這樣支持多路徑選擇的組合模型，能保證候選服務空間經(jīng)過篩選仍維持一定的結(jié)點規(guī)模，使組合算法有足夠的服務可以挑選。

2.1 Skyline服務篩選

Skyline的概念最早來源于數(shù)據(jù)庫［10］，近些年來有學者將其用于 Web服務組合。文獻 ［11，12］將Skyline方法貫穿于服務組合的整個過程，靈活性較差。文獻 ［13，14］僅將Skyline方法用于服務篩選，服務組合可以根據(jù)需求采用不同的方法，因而有較強的靈活性。本文亦采用Skyline方法進行服務篩選，被篩選出的服務稱為Skyline服務，定義如下。

定義1 Skyline服務：對于服務類Si中某一候選服務P，若不存在另一個候選服務Q能控制服務P（QP），即不存在另一個候選服務Q的所有QoS指標都小于或等于服務P的，則稱服務P為服務類S的Skyline服務。

可以證明，非Skyline服務不可能出現(xiàn)在服務組合的最優(yōu)解中，而最優(yōu)的服務組合中的服務一定是Skyline服務［11］。文獻 ［13，14］并沒有給出求取Skyline服務的具體算法，結(jié)合基于圖的Web服務組合方法的個性，本文設計Skyline算法如下：

Skyline（Si，V）｛

1.for each candidate service Vi∈Si｛

2.generate the graph node Vi；

3.if VjVi（i≥j）

4.delete Vi；

5.elseif ViVj

6.delete Vj；｝

7.｝

算法依次掃描服務類Si中的候選服務Vi并生成對應的圖結(jié)點Vi（1～2行），如果Vi受它前面的某一候選服務Vj所控制，即Vi不是Si的Skyline服務，就將服務Vi對應的圖結(jié)點Vi刪除 （3～4行）。如果Vi控制Vj，即Vj不是Si的Skyline服務，就刪除服務Vj對應的結(jié)點Vj（5～6行）。這樣，剔除候選服務空間的非Skyline服務，就可以直接在優(yōu)質(zhì)候選服務的基礎上構(gòu)造基于圖的Web服務組合模型，進而進行服務組合。

2.2 MCSPi算法

為了滿足用戶的多QoS約束條件，支持多路徑選擇，本文選取MCSP－K算法進行服務組合。經(jīng)過階段一的Skyline服務篩選，雖然服務組合的效率得以提高，但在某些情況下，會出現(xiàn)如文獻 ［13］中提到的無解現(xiàn)象。這屬于過約束問題，Web服務組合中的過約束是指當用戶的約束條件過多以致嚴苛導致在候選服務空間中找不到一組能夠滿足用戶需求的服務所產(chǎn)生的無解現(xiàn)象［15］。當候選服務空間經(jīng)過Skyline進一步縮小后，在多QoS約束條件下就更易發(fā)生過約束。為了解決這一問題，本文借鑒文獻 ［15］的思想，引入一種過約束機制，將用戶的約束條件分為硬約束、軟約束。硬約束是選擇過程中必須要滿足的約束條件，是用戶給出的硬性QoS指標，必須滿足式 （3）。軟約束反應了用戶對服務組合一些指標的期望，屬于可選約束條件，不一定要滿足式 （3），但是不滿足時會影響組合路徑的得分。但不同文獻 ［15］的是，本文在運行組合算法MCSPK的過程中只考慮硬約束條件，以提高組合效率。這樣就得到MCSP－K的改進算法MCSPi，算法如下：

MCSPi（G＝ （V，E），Vs，Vd，Chard）｛

1.for each node Vi∈G，in topological order

2.for each node Vjlinked with Vi｛

3.Q（VS→Vj）＝Q（VS→Vi）＋Q（Vi→Vj）；

4.if Q（VS→Vj）satisfies Chard｛

5.add P（VS→Vj）to node Vj，and delete

paths which may not be the optimal；

6.if size（paths of Vj）＞K

7.keep the first Kpaths whose cost are

lower；｝

8.else

9.return；｝

10.｝

為了求出一條較高質(zhì)量組合路徑，每個結(jié)點都保留從源點Vs到它自身的滿足硬約束條件Chard的多條路徑 （4～5行），為了減少每個結(jié)點保留的路徑數(shù)，僅僅保留住代價最小也就是最有可能成為最優(yōu)解的前K條路徑 （6～7行），終點Vd中保留的路徑即求得的可行解。

2.3 Relax算法

Relax算法可以從MCSPi組合算法求取的可行解中求取最優(yōu)解。為了保證最優(yōu)解的性能，現(xiàn)要考慮軟約束條件Csoft。假設運行MCSPi算法后在終點Vd中得到n條路徑，即階段二求得的可行解，現(xiàn)在就逐一考察這n條路徑，根據(jù)它們滿足軟約束條件個數(shù)的多少給予總質(zhì)量相應的加分，即在式 （2）的基礎上加上不同的常數(shù)C′

那么最優(yōu)路徑就是Q（S）值最高的那條路徑，偽代碼如下：

Relax（Vd，Csoft）｛

1.for each path∈Vd｛

2.calculate the Q（S）value of the path using for

mular（4）；

3.return the highest Q（S）value path；｝

4.｝

3 實驗分析

為了驗證本文提出的Sky－MCSP－R方法的效率和有效性，采用如表1所示的實驗用例對Sky－MCSP－R方法和MCSP－K方法的組合效率和優(yōu)化率進行比較測試。25個Test Case（實驗用例）被分為5個Test group（實驗組），平均每個實驗組有5個實驗用例，如實驗組2的實驗用例為6至10。可以看出，同一實驗組實驗用例的No.Candidates（候選服務數(shù)）相同，但No.Service Class（服務類數(shù)）不同，如實驗組4的每個實驗用例的候選服務數(shù)都為40，但服務類數(shù)從10到50不等。不同實驗組實驗用例的候選服務數(shù)不同，但可以有相同的服務類數(shù)，如實驗組3的實驗用例13和實驗組5的實驗用例23的候選服務數(shù)不同，但服務類數(shù)都為30。這樣用同一實驗組的實驗用例可以測試當候選服務數(shù)不變時組合方法效率同服務類數(shù)目之間的關系。不同實驗組的實驗用例可以測試當服務類數(shù)不變時組合方法效率同候選服務數(shù)目之間的關系。實驗采取的數(shù)據(jù)集由隨機函數(shù)產(chǎn)生，共選取5個QoS屬性，取值范圍都在 ［0，100］。實驗環(huán)境為奔騰2.13GHz，內(nèi)存2G，開發(fā)語言為Java。

表2 對比了Sky－MCSP－R方法和MCSP－K方法在25個測試用例上的優(yōu)化率，即最終所選服務組合的質(zhì)量與窮舉法求出的最優(yōu)解質(zhì)量的比率，反映了組合方法所選服務組合方案的性能。

從表2中不難看出，本文提出的Sky－MCSP－R方法的優(yōu)化率略低于 MCSP－K方法。Sky－MCSP－R方法能達到平均90%的優(yōu)化率，同MCSP－K算法平均91%的優(yōu)化率相比降低了1%。

表1 實驗用例

表2 優(yōu)化率 （%）

圖2 和圖3展示了Sky－MCSP－R方法和 MCSP－K方法在實驗用例上的運行時間比。用戶的約束條件為2個，沒有軟約束條件?？梢钥闯觯谒械那闆r下，時間比都小于1，說明Sky－MCSP－R方法的運行時間小于 MCSP－K方法，Sky－MCSP－R方法具有較高的時間效率。因為事實上平均每個服務類可以篩選出80%的Skyline服務，淘汰掉20%的候選服務，搜索效率得以提高。圖2展示了對同一實驗組實驗用例的測試情況，能看到當候選服務數(shù)不變時組合方法效率的提升隨服務類數(shù)的增加而增加，當服務類數(shù)較少時，效率的提升還有限，隨著服務類數(shù)的增多，效果就非常明顯了，最理想時Sky－MCSP－R的運行時間還不到MCSP－K的30% （Test Case＝20）。圖3展示了不同實驗組實驗用例的測試情況，能看到當服務類數(shù)不變時組合方法效率的提升隨候選服務數(shù)的增加而增加，但這不是必然的，有時效率的提升也會隨候選服務數(shù)的增加而減少（對比Test Case＝9和Test Case＝14），這是因為隨著候選服務數(shù)的增加，計算Skyline服務的時間開銷也在增加。所以，增加服務類的數(shù)目比增加候選服務的數(shù)目更能促進Sky－MCSP－R方法效率的提升。但不論哪種情況，Sky－MCSP－R方法較之MCSP－K方法在時間效率上的優(yōu)越性都是很明顯的，雖然Sky－MCSP－R方法的優(yōu)化率不如 MCSP－K方法，但以降低1%的優(yōu)化率換取大幅度提高的時間效率，這顯然是值得的。

此外，當約束條件為2個時，兩種方法都未發(fā)生無解現(xiàn)象。將約束條件增為5個，用MCSP－K方法求解時，25個實驗用例中有5個無解。而用Sky－MCSP－R方法求解時，因為將5個約束條件轉(zhuǎn)化為2個 “硬條件”和3個 “軟條件”，并未出現(xiàn)過約束，無解現(xiàn)象降低。

4 結(jié)束語

基于QoS的Web服務組合優(yōu)化問題是目前Web服務技術研究的一個熱點問題［16］。本文提出一種基于圖的三階段服務組合方法Sky－MCSP－R。該方法可以從候選服務空間中篩選出80%的高質(zhì)量Skyline服務，縮小圖算法的結(jié)點規(guī)模。然后運行MCSPi算法進行服務組合，盡可能找到滿足用戶需求的服務組合，提高了出解率。最后運行Relax算法求得最優(yōu)解。Sky－MCSP－R方法有效解決了滿足用戶多QoS約束條件的Web服務組合優(yōu)化問題，在時間效率和優(yōu)化率之間獲取平衡。

［1］WANG Yong，DAI Guiping，HOU Yarong.Dynamic methods of trust－aware composite service selection ［J］.Chinese Journal of Computers，2009，32 （8）：1668－1675 （in Chinese）.［王勇，代桂平，候亞榮.信任感知的組合服務動態(tài)選擇方法［J］.計算機學報，2009，32 （8）：1668－1675.］

［2］ZHAO Weiwei，DONG Dong，WANG Kun，et al.A personalized composition of web services based on CBR and multiagents［J］.Computer Applications and Software，2012，29（1）：145－148 （in Chinese）.［趙偉偉，董東，王昆，等.一種基于CBR和多Agent的Web服務個性化組合 ［J］.計算機應用與軟件，2012，29 （1）：145－148.］

［3］CAO Lipei，LI Ailing，LIU Jing.Method of services selection in two phases based on QoS ［J］.Computing Engineering and Design，2009，30 （3）：747－751 （in Chinese）.［曹利培，李愛玲，劉靜.基于QoS的兩階段Web服務選擇方法 ［J］.計算機工程與設計，2009，30 （3）：747－751.］

［4］WANG Yifei，WU Suqin，WANG Rong.Research of Web services composition based on graph ［J］.Microcomputer ＆ its Applications，2010，29 （1）：41－43 （in Chinese）.［王一飛，吳素芹，王榕.基于圖的 Web服務組合的研究 ［J］.微型機與應用，2010，29 （1）：41－43.］

［5］YU T，LIN K J.Service selection algorithms for composing complex services with multiple QoS constraints［C］／／Amsterdam，Holland：Proc of 3rd Int’l Conf on Service Oriented Computing，2005：130－143.

［6］ZHANG Wencheng，SU Sen，CHEN Junliang.Genetic algorithm on Web services selection supporting QoS ［J］.Chinese Journal of Computers，2009，29 （7）：1029－1037 （in Chinese）.［張文成，蘇森，陳俊亮.基于遺傳算法的QoS感知的Web服務選擇 ［J］.計算機學報，2009，29 （7）：1029－1037.］

［7］LI Jinzhong，XIA Jiewu，TANG Weidong，et al.Survey on web services selection algorithms based on QoS ［J］.Application Reseach of Computers，2010，27 （10）：3622－3627 （in Chinese）.［李金忠，夏潔武，唐衛(wèi)東，等.基于QoS的Web服務選擇算法綜述 ［J］.計算機應用研究，2010，27 （10）：3622－3627.］

［8］Johny K，Jose T.Algorithms for efficient Web service selection with different constraints ［J］.Communication in Computer and Information Science，2011，203 （1）：293－300.

［9］HOU Qing.Reseach on web service discovery and service composition with QoS constrained driven ［D］.Chongqing：Chongqing Normal University，2011 （in Chinese）.［候青.支持QoS約束的Web服務發(fā)現(xiàn)與服務組合研究 ［D］.重慶：重慶師范大學，2011.］

［10］Papadias D，TAO Y F，F(xiàn)u G，et al.Progressive skyline computation in database systems ［J］.ACM Trans Data－base Syst，2005，30 （1）：41－82.

［11］YU Q，Bouguettaya A.Computing service skylines over sets of services ［C］／／Miami，USA：Proc of the IEEE Conference on Web Services，2010：481－488.

［12］YU Q，Bouguettaya A.Efficient service skyline computation for composite service selection ［J］.Knowledge and Data Engineering，2012，25 （4）：776－789.

［13］XIE Haijun，QI Lianyong，DOU Wanchun.Combining skyline and local selection for heuristic web service composition［J］.Journal of Southeast University，2011，41 （3）：449－452（in Chinese）.［謝海軍，齊連永，竇萬春.基于Skyline和局部選擇的啟發(fā)式服務組合方法 ［J］.東南大學學報，2011，41 （3）：449－452.］

［14］WU Jian，CHEN Liang，DENG Shuigang，et al.QoS skyline based dynamic service selection ［J］.Chinese Journal of Computers，2010，33 （11）：2136－2145 （in Chinese）.［吳健，陳亮，鄧水剛，等.基于Skyline的QoS感知的動態(tài)服務選擇 ［J］.計算機學報，2010，33 （11）：2136－2145.］

［15］Rosenberg F，Celikovic P，Michlmayr A，et al.An end－toend approach for QoS－aware service compositon ［C］／／Auckland，New Zealand：Proc of the Enterprise Distributed Object Computing Conference，2009：151－160.

［16］HE Yanxiang，WU Zhao.key technology and performance analysis of dynamic web service combination ［M］.Beijing：Tsinghua University Press，2011 （in Chinese） ［何炎祥，吳釗.動態(tài)Web服務組合關鍵技術與性能分析 ［M］.北京：清華大學出版社，2011.］