基于鄰接矩陣的Web服務組合*

李景霞，吳國棟，錢俊彥

(1.安徽農業大學信息與計算機學院，安徽 合肥 230036；2.桂林電子科技大學計算機科學與工程學院,廣西 桂林 541004)

基于鄰接矩陣的Web服務組合*

李景霞1，吳國棟1，錢俊彥2

(1.安徽農業大學信息與計算機學院，安徽 合肥 230036；2.桂林電子科技大學計算機科學與工程學院,廣西 桂林 541004)

針對當前Web服務組合方法在動態性和算法時間復雜度方面存在的不足，提出一種基于鄰接矩陣的服務組合方法，使用鄰接矩陣表示服務間的順序及并發關系，在構建抽象服務基礎上由領域專家初步建立抽象服務的組合關系，利用Warshall算法計算傳遞閉包來判定服務請求是否可滿足，同時構建動態服務組合流程。方法操作簡單，Warshall算法時間復雜度為O(n3)，在服務組合中有較好的實用性。

Web服務；服務組合；鄰接矩陣；傳遞閉包；Warshall算法

1 引言

Web服務組合將網絡上分布的多個功能單一的Web服務按某種業務邏輯組合起來提供增值服務，是當前服務計算領域研究熱點之一[1]。Web服務組合研究主要有以下組合方法：基于工作流的Web服務組合[2,3]，提供了直觀、易于理解的服務流程組合方法，但流程是靜態的，不能動態規劃產生；基于人工智能的Web服務組合[4,5]，根據服務需求，在服務庫中匹配生成符合需求的服務組合，無需組合流程模板，動態規劃產生組合服務，但隨著服務庫的不斷擴大，動態規劃效率越來越低；基于形式化方法的Web服務組合[6～8]，利用形式化工具輔助組合服務的生成及流程正確性驗證，流程模板是靜態的；基于圖搜索的Web服務組合方法[9,10]，利用圖來對服務進行建模，服務組合問題轉換為圖搜索問題。隨著服務不斷增加，產生可用服務組合代價越來越高。

針對當前Web服務組合方法在動態性和算法時間復雜度方面存在的不足，本文提出一種基于鄰接矩陣的Web服務組合方法，在抽象服務基礎上由領域專家初步建立抽象服務間的組合關系，根據服務請求動態生成服務組合方案，克服了基于工作流的服務組合動態性差的缺點。另外，和基于人工智能及形式化方法的服務組合方法中算法復雜度呈指數級或不可判定性相比，本方法具有確定時間復雜度O(n3)。

2 Web服務組合流程

Web服務組合是一個復雜的過程[11～13]：首先將服務請求信息和原子Web服務描述進行匹配，選出一組相關的原子服務；隨后對這組原子服務進行服務組合，最終獲得一個組合服務。Web服務組合離不開服務匹配[14]，合理地安排服務匹配活動，能夠提高服務組合效率。服務的匹配分兩個階段進行：在服務組合之前進行功能匹配，將參數匹配后移，從而排除參數匹配而功能不相關服務的干擾，整體上縮減服務組合的時間。同時，借鑒基于工作流的服務組合中抽象服務[15,16]的概念，構建一種動態抽象服務組合流程，如圖1所示。但是，與基于工作流的服務組合方法不同的是，該流程中不存在固定的服務組合模板或流程，所有組合方案都是根據用戶請求進行功能匹配動態組合生成的。抽象服務的引入及領域專家對抽象服務間組合關系的預處理在支持動態服務流程生成的同時也明顯提高了服務組合的效率。

Figure 1 Web service composition process

在圖1所示流程中，如果服務請求可滿足，那么可構建一個服務組合方案。圖1所示組合流程中抽象服務的構建可通過聚類分析實現[17，18]，在抽象服務基礎上由領域專家初步建立抽象服務間的組合關系，下文討論的重點為服務組合方案的求解。

3 基于鄰接矩陣的Web服務組合方法

基于鄰接矩陣的Web服務組合的基本思路：將Web服務看成有向圖中的頂點集合，如果服務間可組合，則頂點間有有向邊相連。利用鄰接矩陣對服務組合建模，然后根據鄰接矩陣的傳遞閉包判斷服務請求是否可滿足，并確定服務組合方案。

3.1 基于鄰接矩陣Web服務組合建模

Web服務是一種典型的分布式計算模型，在服務組合流程中簡單服務間最基本的執行順序只有兩種：順序和并發，選擇結構是加條件的順序執行。因此，服務組合建?？蓺w結為對服務順序和并發關系的建模。鄰接矩陣是表示有向圖中頂點間相鄰關系的矩陣，通過矩陣可建立圖中眾多頂點之間的復雜關系網絡。在此將服務組合間的順序關系和并發關系用鄰接矩陣表示。

定義1順序關系：兩個及以上服務按照排列次序先后執行。順序關系可用序偶來表示，即〈si,sj〉表示服務sj由服務si觸發。

例如,在購買行為中，商品投遞服務由顧客支付服務觸發，兩個服務間存在順序關系。

定義2并發關系：兩個及以上服務在同一時刻執行或者不限制執行的先后順序。若用≮si,sj≯表示服務si和服務sj并發關系，則≮si,sj≯={〈si,sj〉,〈sj,si〉}，服務并發關系可用順序關系模擬。

例如，旅游組合服務方案中，景點天氣查詢服務和景點路線查詢服務可同時進行，也可先后進行，兩者是并發關系。

定義3相鄰關系：給定服務組合順序關系Rseq中一個序偶〈si,sj〉，若不存在服務sk，使得R中〈si,sk〉和〈sk,sj〉成立，那么稱〈si,sj〉是相鄰關系Radj，并稱si是sj的前驅，sj是si的后繼。

定義4可達關系：給定服務組合順序關系Rseq中一個序偶〈si,sj〉，若存在服務sk使得R中〈si,sk〉和〈sk,sj〉滿足，那么稱〈si,sj〉為可達關系Rrea，并稱sk為〈si,sj〉的中繼。

順序關系分類：在服務執行階段，存在相鄰關系的服務之間由前驅直接觸發后繼，而可達關系的服務之間不存在此性質。

定義5服務路徑：服務間的可達關系〈si,sj〉表明從初始服務si開始執行，經過一個或多個中間服務sk的過渡，目標服務sj最終間接觸發。初始服務、中間服務和目標服務構成了一條以服務為節點的路徑，簡稱服務路徑。

定義6服務組合方案求解： 給定n個抽象服務集合ws={s1,s2,…,sn}及這個抽象服務集合上的相鄰關系：Radj={〈si,sj〉|si,sj∈ws}，使用鄰接矩陣M表示服務間的相鄰關系Radj，記作：

相鄰關系具有傳遞性，通過求鄰接矩陣M的傳遞閉包得到服務間的可達關系Mt=M+M2+…+Mn：Rrec={〈si,sj〉|si,sj∈ws}，求解出服務路徑，即可得出服務組合方案。

利用鄰接矩陣對服務組合建模，其優點是容易利用順序關系模擬并發關系，直觀方便。對于ws中任意兩個服務si和sj：

(1)M[i][j]=1,M[j][i]=0，表示服務si、sj順序執行；

(2)M[i][j]=0,M[j][i]=1，表示服務sj、si順序執行；

(3)M[i][j]=1,M[j][i]=1，表示服務si、sj并發執行。

3.2 Web服務組合方案求解

Warshall算法適用于求解鄰接矩陣的傳遞閉包，但服務組合問題的目的是求解傳遞閉包中的服務路徑。因此，需要在Warshall算法基礎上添加一個用于保存服務路徑的數據結構。引入路徑矩陣Path，該矩陣保存任意兩個服務的中繼服務信息，間接保存了服務路徑，見定義7。

定義7路徑矩陣Path：給定n個抽象服務集合ws={s1,s2,…,sn}及抽象服務集合上的可達關系：C={〈si,sj〉|si,sj∈ws}，服務集合ws的路徑矩陣定義為：

對Warshall算法改進后，求解服務組合的Warshall-SC算法如下所示：

voidWarshall-SC( ){

inti,j,k=0;

for (i=0;i

for(j=0;j

C[i][j]=M[i][j];

//可達關系初始化為相鄰關系

intpath[][][]=0;

for(i=0;i

for(j=0;j

for(k=0;k

if(C[i][k]*C[k][j]==1){

Path[i][j][k]=1;

/*若服務i和j經過服務k可達，記錄中繼服務k*/

C[i][j]=1;

}

}

Warshall-SC算法的執行時間比Warshall算法略有增加，但數量級未變，仍為O(n3)。

3.3 服務請求可滿足性判定

基于鄰接矩陣的服務組合方法判定服務請求能否滿足的基本步驟：首先檢驗服務組合的輸出能否包含服務請求所期望的輸出；其次檢驗服務請求的輸入能否包含服務組合所需的輸入；最后通過可達關系判定從服務請求的輸入到服務請求的輸出是否可達。具體判定條件見定義8。

定義8服務請求可滿足性：給定服務請求Req={IR,OR}和抽象服務集合ws={s1,s2,…,sn}及其上的可達關系：C={〈si,sj〉|si,sj∈ws}，其中IR為服務請求的輸入，OR為服務請求需要的輸出。若存在抽象服務sm和sn，滿足下列條件：

(1)OR?Osn;

(2)Ism?IR;

(3)〈sm,sn〉∈C。

則服務請求Req是可滿足的，至少存在一條有限的服務路徑，該路徑上的所有服務順序觸發后，滿足服務請求。

假設服務sm和sn分別是抽象服務集合ws中滿足服務的初始服務請求輸入、輸出的服務，那么抽象服務集合ws的可達關系C包含了由服務sm到sn的服務路徑。根據Path矩陣保存的服務中繼信息，展開〈sm,sn〉得到服務路徑。服務路徑生成算法SPG如下：

voidSPG(intm,intn){

for(k=0;k

if (Path[m][n][k]==1){

Insert(&P,k,m,n);

/* 函數Insert將k插入數組P的m與n中間*/

if (〈sm,sk〉∈Reduce(C,R))

//函數Reduce去除可達關系中的相鄰關系

SPG(〈sm,sk〉);

else

return;

if(〈sk,sn〉∈Reduce(C,R))

SPG(〈sk,sn〉)；

else

return;

}

}

SPG算法經過有限步展開，返回數組P，得到一條由初始服務sm開始，經過集合{sk|〈sm,sk〉,〈sk,sn〉∈C}中若干個中間服務過渡，最終到達目標服務sn的服務路徑，即一個服務組合方案。

Web服務是一種典型的分布式計算模型，在必要的情況下，還需對服務組合方案作并發處理：如果服務組合方案中順序關系〈si,sj〉被進一步判定為并發關系，那么這兩個原子服務可同時執行，取原sj的后繼為兩者的共同后繼。根據定義6，當相鄰關系Radj的鄰接矩陣M中M[i][j]=1和M[j][i]=1同時成立，很容易判定服務si和sj為并發關系。

3.4 應用實例

下面以網絡訂票為例，說明基于鄰接矩陣的語義Web服務組合方法的應用。

在網絡訂票中一共有5個抽象服務：票務查詢服務(s1)、飛機票訂購服務(s2)、火車票訂購服務(s3)、銀行支付服務(s4)、投遞服務(s5)。

給定一個服務請求：Req={{出發地：合肥；目的地：北京；時間：7月1日；人數：1；付款方式：銀行賬號；郵寄地址：合肥市長江西路130號}，{單程飛機票}}。求解服務組合方案的過程如下：

(1)這些服務組成的抽象服務集合：ws={s1,s2,s3,s4,s5}。

(2)根據領域專家知識，利用鄰接矩陣對服務組合建模，得到服務組合集合ws的相鄰關系：r={〈s1,s2〉,〈s1,s3〉,〈s2,s4〉,〈s3,s4〉,〈s4,s5〉}。

(3)對相鄰關系R的鄰接矩陣M調用Warshall-SC算法，得到服務間的可達關系：C={〈s1,s2〉,〈s1,s3〉,〈s2,s4〉,〈s3,s4〉,〈s4,s5〉,〈s1,s4〉,〈s1,s5〉,〈s2,s5〉,〈s3,s5〉}。

(4)根據抽象服務s1、s2、s4的輸入和s5輸出，以及〈s1,s5〉∈C可以確定服務請求Req是可滿足的，且初始服務為s1、目標服務為s5、Path[1][5]=4、Path[1][4]=2。對〈s1,s5〉調用SPG算法，可得服務路徑：s1、s2、s4、s5。

至此，由服務請求Req得到的服務組合方案為：s1、s2、s4、s5。另外,若本例中Req是一個關于火車票訂購的服務請求，那么生成的服務組合方案為：s1、s3、s4、s5，表明根據服務請求的變化，基于鄰接矩陣的語義Web服務組合方法可動態生成服務組合方案。隨著抽象服務數的增多，服務組合算法Warshall-SC不會出現狀態空間爆炸問題，具有良好的實用性。

4 結束語

本文提出了一種基于鄰接矩陣的Web服務組合方法，利用鄰接矩陣對Web服務組合進行建模，通過確定服務間的可達關系給出服務組合方案。與以往的Web服務組合方法相比，通過對服務進行聚類預處理得出抽象服務，由領域專家初步構建抽象服務間的順序及并發關系，使用該方法可實現時間復雜度為O(n3)的動態Web服務組合。

[1] Cui Hua,Ying Shi,Yuan Wen-Jie,et al. Review of semantic web service composition[J]. Computer Science,2010,37(5):21-25.(in Chinese)

[2] Charif Y，Sabouret N．An overview of semantic Web services composition approaches[J]．Electronic Notes in TheoreticalComputer Science,2006,146:33-41.

[3] Wen Jia-jia. Research on Web services composition and related technology[D].Beijing:Beijing University of Posts and Telecommunications,2006.(in Chinese)

[4] Russell S，Norvig P．Artificial intelligence-A modem approach[M]．Englewood:Prentice Hall，2004.

[5] Nau D,Au Tsz-Chiu.SHOP2:An HTN planning system [J].Journal of Artificial Intelligence Research，2003,20:379-404.

[6] Qian Zhu-zhong,Lu Sang-lu,Xie Li. Automatic composition of Petri net based web services[J].Chinese Journal of Computers,2006,29(7):1057-1066.(in Chinese)

[7] Tang Xian-fei,Jiang Chang-jun,Ding Zhi-jun, et al. A Petri net based semantic web service automatic composition method[J]. Journal of Software,2007,18(12):2991-2998.(in Chinese)

[8] Ceri S,Daniel F,Lecue F,et al.Towards the composition of stateful and independent semantic web service[C]∥Proc of ACM Symposium on Applied Computing,2008:1．

[9] Lu Jing-yun,Zhang Wei-qun. Method of automatic semantic web services composition based on AND/OR graph[J]. Computer Scicence,2010,37(3):188-190.(in Chinese)

[10] Liang Qian-hui,Stanley Y W S.AND/OR graph and search algorithm for discovering composite web services[J]．International Journal of Web Services Research，2005,2(4)：48-68.

[11] Brogi A, Corfini S, Popescu R. Semantics-based composition-oriented discovery of web services[J]. ACM Transactions on Internet Technology,2008,8(4):1-39.

[12] Medjahed B,Bouguettaya A,Elmagarmid A.Composing web services on the semantic web[J]. The VLDB Journal,2003,12(4):333-351.

[13] Katia S,Massimo P, Anupriya A, et al. Automated discovery,interaction and composition of semantic web services[J]. Web Semantics:Science,Services and Agents on the World Wide Web,2003,1(1):27-46.

[14] Ye Lei,Zhang Bin.A method of web service discovery based on functional semantics[J]. Journal of Computer Research and Development,2007,44(8):1357-1364.(in Chinese)

[15] Wen Yan,Fang Jun,Han Yan-bo. An approach to improve the service availability on the basis of business service abstraction[J]. Chinese Journal of Computers,2010,33(11):2190-2201.(in Chinese)

[16] Ou Wei-jie,Zeng Cheng,Zeng Qing,et al. QoS-aware efficient abstract service selection[J].Journal of Chinese Computer Systems,2013,34(1):1-8.(in Chinese)

[17] Li Jing-xia,Wu Guo-dong. Web service management based on fuzzy clustering[J]. Journal of Shanghai University of Engineering Science,2014,28(2):145-148.(in Chinese)

[18] Wang Zhuo-hao,Zhao Zhuo-feng,Fang Jun,et al. A SaaS-friendly service community model and its application in the nationwide service network for sharing science and technology information[J].Chinese Journal of Computers,2010,33(11):2033-2043.(in Chinese)

附中文參考文獻：

[1] 崔華,應時,袁文杰,等.語義Web服務組合綜述[J].計算機科學,2010,37(5):21-25.

[3] 溫嘉佳．Web服務組合及其相關技術的研究[D]．北京：北京郵電大學，2006.

[6] 錢柱中,陸桑璐,謝立.基于Petri網的web服務自動組合研究[J].計算機學報,2006,29(7):1057-1066.

[7] 湯憲飛,蔣昌俊,丁志軍，等.基于Petri網的語義Web服務自動組合方法[J]．軟件學報,2007,18(12):2991-2998.

[9] 盧錦運,張為群.一種基于與或圖的語義Web服務自動組合方法研究[J].計算機科學,2010,37(3):188-190.

[14] 葉蕾,張斌.基于功能語義的Web服務發現方法[J].計算機研究與發展,2007,44(8):1357-1364.

[15] 溫彥,房俊,韓燕波.一種利用業務服務抽象提升服務可用性的方法[J].計算機學報,2010,33(11):2190-2201.

[16] 歐偉杰,曾承,曾青,等.Qos感知的高效抽象服務選擇[J].小型微型計算機系統,2013,34(1):1-8.

[17] 李景霞,吳國棟.基于模糊聚類的Web服務管理[J].上海工程技術大學學報,2014,28(2):145-148.

[18] 王卓昊,趙卓峰,房俊,等.一種SaaS模式下的服務社區模型及其在全國科技信息服務網中的應用[J].計算機學報,2010,33(11):2033-2043.

李景霞(1976-),女,安徽巢湖人，博士，講師，CCF會員(E200040303M)，研究方向為服務計算和本體應用。E-mail:jxiali@163.com

LI Jing-xia,born in 1976,PhD,lecturer,CCF member(E200040303M)，her research interests include service computing, and ontology application.

吳國棟(1972-),男,安徽安慶人，副教授，研究方向為智能決策和知識管理。E-mail:wugd@ahau.edu.cn

WU Guo-dong,born in 1972,associate professor,his research interests include intelligent decision, and knowledge management.

錢俊彥(1973-),男,浙江嵊州人，博士，教授，研究方向為軟件系統可靠性和安全性。E-mail:qjy2000@gliet.edu.cn

QIAN Jun-yan,born in 1973,PhD,professor,his research interests include software reliability, and software security.

Adjacency matrix-based web service composition

LI Jing-xia1，WU Guo-dong1，QIAN Jun-yan2

(1.School of Information and Computer,Anhui Agricultural University,Hefei 230036；2.School of Computer Scinece and Engineering,Guilin University of Electronic Science and Technology,Guilin 541004,China)

Aiming at the disadvantages in dynamics and algorithm time complexity in the existing web service composition methods, we propose an adjacency matrix-based web service composition approach. Sequential and parallel relationship among web services is represented by adjacency matrix. Abstract services are created by clustering, and the composition relationship among abstract services is established by domain experts. The Warshall algorithm is utilized to calculate the transitive closure of the adjacency matrix so that we can judge whether the the service request is met or not. Meanwhile the dynamic service composition flow is constructed. The proposed method applies well in service composition due to its simple operation and theO(n3) time complexity of the Warshall algorithm.

web service;service composition;adjacency matrix;transitive closure;Warshall algorithm

1007-130X(2015)09-1627-05

2014-06-12;

2015-01-16基金項目：安徽農業大學2014年學科骨干培育項目(編號2014XKPY-61);安徽省科技攻關計劃項目(1501031082);國家自然科學基金資助項目(31271615)

TP312

A

10.3969/j.issn.1007-130X.2015.09.004

通信地址：230036 安徽省合肥市長江西路130號安徽農業大學信息與計算機學院

Address:School of Information and Computer,Anhui Agricultural University,130 Changjiang Rd West,Hefei 230036,Anhui,P.R.China