李景霞，吳國棟，錢俊彥

(1.安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院，安徽 合肥 230036；2.桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣西 桂林 541004)

基于鄰接矩陣的Web服務(wù)組合*

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

(1.安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院，安徽 合肥 230036；2.桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣西 桂林 541004)

針對(duì)當(dāng)前Web服務(wù)組合方法在動(dòng)態(tài)性和算法時(shí)間復(fù)雜度方面存在的不足，提出一種基于鄰接矩陣的服務(wù)組合方法，使用鄰接矩陣表示服務(wù)間的順序及并發(fā)關(guān)系，在構(gòu)建抽象服務(wù)基礎(chǔ)上由領(lǐng)域?qū)＜页醪浇⒊橄蠓?wù)的組合關(guān)系，利用Warshall算法計(jì)算傳遞閉包來判定服務(wù)請(qǐng)求是否可滿足，同時(shí)構(gòu)建動(dòng)態(tài)服務(wù)組合流程。方法操作簡單，Warshall算法時(shí)間復(fù)雜度為O(n3)，在服務(wù)組合中有較好的實(shí)用性。

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

1 引言

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

針對(duì)當(dāng)前Web服務(wù)組合方法在動(dòng)態(tài)性和算法時(shí)間復(fù)雜度方面存在的不足，本文提出一種基于鄰接矩陣的Web服務(wù)組合方法，在抽象服務(wù)基礎(chǔ)上由領(lǐng)域?qū)＜页醪浇⒊橄蠓?wù)間的組合關(guān)系，根據(jù)服務(wù)請(qǐng)求動(dòng)態(tài)生成服務(wù)組合方案，克服了基于工作流的服務(wù)組合動(dòng)態(tài)性差的缺點(diǎn)。另外，和基于人工智能及形式化方法的服務(wù)組合方法中算法復(fù)雜度呈指數(shù)級(jí)或不可判定性相比，本方法具有確定時(shí)間復(fù)雜度O(n3)。

2 Web服務(wù)組合流程

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

Figure 1 Web service composition process

在圖1所示流程中，如果服務(wù)請(qǐng)求可滿足，那么可構(gòu)建一個(gè)服務(wù)組合方案。圖1所示組合流程中抽象服務(wù)的構(gòu)建可通過聚類分析實(shí)現(xiàn)[17，18]，在抽象服務(wù)基礎(chǔ)上由領(lǐng)域?qū)＜页醪浇⒊橄蠓?wù)間的組合關(guān)系，下文討論的重點(diǎn)為服務(wù)組合方案的求解。

3 基于鄰接矩陣的Web服務(wù)組合方法

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

3.1 基于鄰接矩陣Web服務(wù)組合建模

Web服務(wù)是一種典型的分布式計(jì)算模型，在服務(wù)組合流程中簡單服務(wù)間最基本的執(zhí)行順序只有兩種：順序和并發(fā)，選擇結(jié)構(gòu)是加條件的順序執(zhí)行。因此，服務(wù)組合建模可歸結(jié)為對(duì)服務(wù)順序和并發(fā)關(guān)系的建模。鄰接矩陣是表示有向圖中頂點(diǎn)間相鄰關(guān)系的矩陣，通過矩陣可建立圖中眾多頂點(diǎn)之間的復(fù)雜關(guān)系網(wǎng)絡(luò)。在此將服務(wù)組合間的順序關(guān)系和并發(fā)關(guān)系用鄰接矩陣表示。

定義1順序關(guān)系：兩個(gè)及以上服務(wù)按照排列次序先后執(zhí)行。順序關(guān)系可用序偶來表示，即〈si,sj〉表示服務(wù)sj由服務(wù)si觸發(fā)。

例如,在購買行為中，商品投遞服務(wù)由顧客支付服務(wù)觸發(fā)，兩個(gè)服務(wù)間存在順序關(guān)系。

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

例如，旅游組合服務(wù)方案中，景點(diǎn)天氣查詢服務(wù)和景點(diǎn)路線查詢服務(wù)可同時(shí)進(jìn)行，也可先后進(jìn)行，兩者是并發(fā)關(guān)系。

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

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

順序關(guān)系分類：在服務(wù)執(zhí)行階段，存在相鄰關(guān)系的服務(wù)之間由前驅(qū)直接觸發(fā)后繼，而可達(dá)關(guān)系的服務(wù)之間不存在此性質(zhì)。

定義5服務(wù)路徑：服務(wù)間的可達(dá)關(guān)系〈si,sj〉表明從初始服務(wù)si開始執(zhí)行，經(jīng)過一個(gè)或多個(gè)中間服務(wù)sk的過渡，目標(biāo)服務(wù)sj最終間接觸發(fā)。初始服務(wù)、中間服務(wù)和目標(biāo)服務(wù)構(gòu)成了一條以服務(wù)為節(jié)點(diǎn)的路徑，簡稱服務(wù)路徑。

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

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

利用鄰接矩陣對(duì)服務(wù)組合建模，其優(yōu)點(diǎn)是容易利用順序關(guān)系模擬并發(fā)關(guān)系，直觀方便。對(duì)于ws中任意兩個(gè)服務(wù)si和sj：

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

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

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

3.2 Web服務(wù)組合方案求解

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

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

對(duì)Warshall算法改進(jìn)后，求解服務(wù)組合的Warshall-SC算法如下所示：

voidWarshall-SC( ){

inti,j,k=0;

for (i=0;i

for(j=0;j

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

//可達(dá)關(guān)系初始化為相鄰關(guān)系

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;

/*若服務(wù)i和j經(jīng)過服務(wù)k可達(dá)，記錄中繼服務(wù)k*/

C[i][j]=1;

}

}

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

3.3 服務(wù)請(qǐng)求可滿足性判定

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

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

(1)OR?Osn;

(2)Ism?IR;

(3)〈sm,sn〉∈C。

則服務(wù)請(qǐng)求Req是可滿足的，至少存在一條有限的服務(wù)路徑，該路徑上的所有服務(wù)順序觸發(fā)后，滿足服務(wù)請(qǐng)求。

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

voidSPG(intm,intn){

for(k=0;k

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

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

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

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

//函數(shù)Reduce去除可達(dá)關(guān)系中的相鄰關(guān)系

SPG(〈sm,sk〉);

else

return;

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

SPG(〈sk,sn〉)；

else

return;

}

}

SPG算法經(jīng)過有限步展開，返回?cái)?shù)組P，得到一條由初始服務(wù)sm開始，經(jīng)過集合{sk|〈sm,sk〉,〈sk,sn〉∈C}中若干個(gè)中間服務(wù)過渡，最終到達(dá)目標(biāo)服務(wù)sn的服務(wù)路徑，即一個(gè)服務(wù)組合方案。

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

3.4 應(yīng)用實(shí)例

下面以網(wǎng)絡(luò)訂票為例，說明基于鄰接矩陣的語義Web服務(wù)組合方法的應(yīng)用。

在網(wǎng)絡(luò)訂票中一共有5個(gè)抽象服務(wù)：票務(wù)查詢服務(wù)(s1)、飛機(jī)票訂購服務(wù)(s2)、火車票訂購服務(wù)(s3)、銀行支付服務(wù)(s4)、投遞服務(wù)(s5)。

給定一個(gè)服務(wù)請(qǐng)求：Req={{出發(fā)地：合肥；目的地：北京；時(shí)間：7月1日；人數(shù)：1；付款方式：銀行賬號(hào)；郵寄地址：合肥市長江西路130號(hào)}，{單程飛機(jī)票}}。求解服務(wù)組合方案的過程如下：

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

(2)根據(jù)領(lǐng)域?qū)＜抑R(shí)，利用鄰接矩陣對(duì)服務(wù)組合建模，得到服務(wù)組合集合ws的相鄰關(guān)系：r={〈s1,s2〉,〈s1,s3〉,〈s2,s4〉,〈s3,s4〉,〈s4,s5〉}。

(3)對(duì)相鄰關(guān)系R的鄰接矩陣M調(diào)用Warshall-SC算法，得到服務(wù)間的可達(dá)關(guān)系：C={〈s1,s2〉,〈s1,s3〉,〈s2,s4〉,〈s3,s4〉,〈s4,s5〉,〈s1,s4〉,〈s1,s5〉,〈s2,s5〉,〈s3,s5〉}。

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

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

4 結(jié)束語

本文提出了一種基于鄰接矩陣的Web服務(wù)組合方法，利用鄰接矩陣對(duì)Web服務(wù)組合進(jìn)行建模，通過確定服務(wù)間的可達(dá)關(guān)系給出服務(wù)組合方案。與以往的Web服務(wù)組合方法相比，通過對(duì)服務(wù)進(jìn)行聚類預(yù)處理得出抽象服務(wù)，由領(lǐng)域?qū)＜页醪綐?gòu)建抽象服務(wù)間的順序及并發(fā)關(guān)系，使用該方法可實(shí)現(xiàn)時(shí)間復(fù)雜度為O(n3)的動(dòng)態(tài)Web服務(wù)組合。

[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)

附中文參考文獻(xiàn)：

[1] 崔華,應(yīng)時(shí),袁文杰,等.語義Web服務(wù)組合綜述[J].計(jì)算機(jī)科學(xué),2010,37(5):21-25.

[3] 溫嘉佳．Web服務(wù)組合及其相關(guān)技術(shù)的研究[D]．北京：北京郵電大學(xué)，2006.

[6] 錢柱中,陸桑璐,謝立.基于Petri網(wǎng)的web服務(wù)自動(dòng)組合研究[J].計(jì)算機(jī)學(xué)報(bào),2006,29(7):1057-1066.

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

[9] 盧錦運(yùn),張為群.一種基于與或圖的語義Web服務(wù)自動(dòng)組合方法研究[J].計(jì)算機(jī)科學(xué),2010,37(3):188-190.

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

[15] 溫彥,房俊,韓燕波.一種利用業(yè)務(wù)服務(wù)抽象提升服務(wù)可用性的方法[J].計(jì)算機(jī)學(xué)報(bào),2010,33(11):2190-2201.

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

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

[18] 王卓昊,趙卓峰,房俊,等.一種SaaS模式下的服務(wù)社區(qū)模型及其在全國科技信息服務(wù)網(wǎng)中的應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào),2010,33(11):2033-2043.

李景霞(1976-),女,安徽巢湖人，博士，講師，CCF會(huì)員(E200040303M)，研究方向?yàn)榉?wù)計(jì)算和本體應(yīng)用。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-),男,安徽安慶人，副教授，研究方向?yàn)橹悄軟Q策和知識(shí)管理。E-mail:wugd@ahau.edu.cn

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

錢俊彥(1973-),男,浙江嵊州人，博士，教授，研究方向?yàn)檐浖到y(tǒng)可靠性和安全性。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基金項(xiàng)目：安徽農(nóng)業(yè)大學(xué)2014年學(xué)科骨干培育項(xiàng)目(編號(hào)2014XKPY-61);安徽省科技攻關(guān)計(jì)劃項(xiàng)目(1501031082);國家自然科學(xué)基金資助項(xiàng)目(31271615)

TP312

A

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

通信地址：230036 安徽省合肥市長江西路130號(hào)安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院

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