基于邻接矩阵的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服务是一种典型的分布式计算模型，在服务组合流程中简单服务间最基本的执行顺序只有两种：顺序和并发，选择结构是加条件的顺序执行。因此，服务组合建模可归结为对服务顺序和并发关系的建模。邻接矩阵是表示有向图中顶点间相邻关系的矩阵，通过矩阵可建立图中众多顶点之间的复杂关系网络。在此将服务组合间的顺序关系和并发关系用邻接矩阵表示。

定义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