基于图的三阶段Web服务组合方法

孙朋姣，郭学俊，张鹏程

（河海大学 计算机与信息学院，江苏 南京211100）

0 引 言

Web服务技术高速发展，通过服务组合来满足用户需求已经成为必然趋势。网络上存在着大量功能和模型结构相同而服务质量各异的服务［1］，如何从中选取合适的服务组合成一个高质量的大粒度服务，众多学者对此做了不同深度的研究。主要有基于图的算法［2－5］和遗传算法［6］两种。遗传算法虽能解决全局最优问题，但容易出现收敛性差和结果不稳定的情况［7］。基于图的Web服务组合方法，其模型简洁，能够很好地处理多路径选择，运行一次就能够找到最优组合，因而在实践中被经常采用［8］。

基于图的Web服务组合方法将整个候选服务空间中的服务及服务之间的相互关系抽象为一个有向图，构造出一个基于图的Web服务组合模型，然后利用图算法求取最优组合方案。应用于服务组合的图算法主要有动态规划算法、Dijkstra算法、Bellman－Ford算法、MCSP－K算法等。文献［2］将Web服务组合的每个服务任务看成一个阶段，将完成每个任务的候选服务看成有向图的结点，将服务之间的调用关系抽象为有向图的有向边，将调用每个服务的成本作为权值，然后利用动态规划算法求得起点到终点的最小总成本。由于每个阶段只考虑到固定的服务任务，该方法只适合单一路径的情况，而不适合用户的多路径选择需求。文献 ［3］构造的有向图的结点集合由情景中出现的输入和输出动作组成，边的集合由从每个输入动作到输出动作的服务组成，权值为各服务的总QoS值，组合算法采用Dijkstra算法，由于每个服务的输入和输出信息都是基于特定情景的，方法实用性较差。文献 ［4］使用的是Bellman－Ford算法，它和Dijkstra算法相似，但服务的权值可以为负，可以解决服务间有负关联的组合，但没有考虑到用户的约束条件。文献 ［5］中的MCSP－K算法能够考虑到用户的多QoS约束需求，算法采用的图模型支持多路径选择。这些组合算法的时间复杂度在候选服务规模较少时还可以接受，当候选服务规模持续增大，有向图的点集、边集也会呈指数增长，影响了组合效率。为了提高组合效率，本文提出一种新的基于图的Web服务组合方法Sky－MCSP－R，该方法将服务组合分为3个阶段进行，首先从候选服务空间中筛选出Skyline服务，接着用改进的MCSP－K算法求得可行解，最后用Relax算法求取最优解。实验结果表明此方法在保持较高优化率的基础上提高了组合效率，减少了无解现象。

1 基于图的Web服务组合模型

一个满足用户需求的大粒度Web服务可由组成这个服务的各个任务所对应小粒度Web服务组合而成。在互联网上能完成一个特定任务的候选Web服务有很多，即它们的功能属性相同。但功能属性相同的服务的非功能属性却不相同，也即服务质量 （QoS）不相同，常用的QoS属性有时延、费用、可靠性、信誉度、可用性、安全性等。

每个QoS属性值qj＊（1≤j≤l）都可以归一化［9］为一个在 ［0，1］区间内的值qj，且质量越高其值越大。假设有l个QoS指标，用户规定其权值为wi，则单个Web服务si（1≤i≤n） 的综合QoS值可以表示为

则包含n个任务的组合服务S的综合QoS值可以线性化表示为

C＝ ｛C1，C2，…，Cm｝，1≤m≤l表示用户的全局QoS约束集合，则

基于图的Web服务组合方法把各个候选的Web服务抽象成有向图的一个个结点，把服务之间的前驱后继关系抽象成有向图的有向边。图1就是这样一有向无环图（DAG），每个圆角矩形框代表一个候选服务类Si（i ≥ 1），这个服务类表示一个特定的服务任务，每个服务类所包含的候选服务用其中的椭圆形Vi（i≥1）表示，候选服务之间的有向边表明了服务之间的前驱后继关系。若Si和Si＋1之间存在一条有向边，则表明完成任务Si后可选的任务是Si＋1。起点Vs终点Vd是两个虚服务。

满足QoS约束条件的服务组合问题可以转化为一个求得从起始点Vs到终止点Vd的最优组合服务路径问题，这条路径经式 （2）计算有较高的QoS值，并且满足式 （3）所规定的约束条件。由于完成特定功能的组合服务有多组不同的服务任务可选，因此这个基于图的Web服务组合模型可以很方便处理多路径选择。为了提高组合效率，本文提出的服务组合方法Sky－MCSP－R将减少模型的结点规模，在服务组合之前除去不可能出现在最优组合路径中的结点，然后采用引入了过约束机制的MCSP－K算法进行服务组合，以产生尽可能多的可行解，最后运用Relax算法求得最优解。

图1 基于图的Web服务组合模型

2 Web服务组合方法Sky－MCSP－R

Sky－MCSP－R是一种基于图的三阶段 Web服务组合方法，第一阶段对候选服务空间进行Skyline，为每个服务类筛选出一部分高质量候选服务，缩小DAG的结点规模。第二阶段采用引入了过约束机制的MCSP－K算法进行服务组合，得到可行解。第三阶段对这些可行解运用Relax算法求得最优解。Sky－MCSP－R方法能够在保持较高的优化率的基础上提高求解速度，减少无解现象。这依赖于各个阶段算法的恰当选取和良好图模型的构造。选择图1这样支持多路径选择的组合模型，能保证候选服务空间经过筛选仍维持一定的结点规模，使组合算法有足够的服务可以挑选。

2.1 Skyline服务筛选

Skyline的概念最早来源于数据库［10］，近些年来有学者将其用于 Web服务组合。文献 ［11，12］将Skyline方法贯穿于服务组合的整个过程，灵活性较差。文献 ［13，14］仅将Skyline方法用于服务筛选，服务组合可以根据需求采用不同的方法，因而有较强的灵活性。本文亦采用Skyline方法进行服务筛选，被筛选出的服务称为Skyline服务，定义如下。

定义1 Skyline服务：对于服务类Si中某一候选服务P，若不存在另一个候选服务Q能控制服务P（QP），即不存在另一个候选服务Q的所有QoS指标都小于或等于服务P的，则称服务P为服务类S的Skyline服务。

可以证明，非Skyline服务不可能出现在服务组合的最优解中，而最优的服务组合中的服务一定是Skyline服务［11］。文献 ［13，14］并没有给出求取Skyline服务的具体算法，结合基于图的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并生成对应的图结点Vi（1～2行），如果Vi受它前面的某一候选服务Vj所控制，即Vi不是Si的Skyline服务，就将服务Vi对应的图结点Vi删除 （3～4行）。如果Vi控制Vj，即Vj不是Si的Skyline服务，就删除服务Vj对应的结点Vj（5～6行）。这样，剔除候选服务空间的非Skyline服务，就可以直接在优质候选服务的基础上构造基于图的Web服务组合模型，进而进行服务组合。

2.2 MCSPi算法

为了满足用户的多QoS约束条件，支持多路径选择，本文选取MCSP－K算法进行服务组合。经过阶段一的Skyline服务筛选，虽然服务组合的效率得以提高，但在某些情况下，会出现如文献 ［13］中提到的无解现象。这属于过约束问题，Web服务组合中的过约束是指当用户的约束条件过多以致严苛导致在候选服务空间中找不到一组能够满足用户需求的服务所产生的无解现象［15］。当候选服务空间经过Skyline进一步缩小后，在多QoS约束条件下就更易发生过约束。为了解决这一问题，本文借鉴文献 ［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.｝

为了求出一条较高质量组合路径，每个结点都保留从源点Vs到它自身的满足硬约束条件Chard的多条路径 （4～5行），为了减少每个结点保留的路径数，仅仅保留住代价最小也就是最有可能成为最优解的前K条路径 （6～7行），终点Vd中保留的路径即求得的可行解。

2.3 Relax算法

Relax算法可以从MCSPi组合算法求取的可行解中求取最优解。为了保证最优解的性能，现要考虑软约束条件Csoft。假设运行MCSPi算法后在终点Vd中得到n条路径，即阶段二求得的可行解，现在就逐一考察这n条路径，根据它们满足软约束条件个数的多少给予总质量相应的加分，即在式 （2）的基础上加上不同的常数C′

那么最优路径就是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方法的组合效率和优化率进行比较测试。25个Test Case（实验用例）被分为5个Test group（实验组），平均每个实验组有5个实验用例，如实验组2的实验用例为6至10。可以看出，同一实验组实验用例的No.Candidates（候选服务数）相同，但No.Service Class（服务类数）不同，如实验组4的每个实验用例的候选服务数都为40，但服务类数从10到50不等。不同实验组实验用例的候选服务数不同，但可以有相同的服务类数，如实验组3的实验用例13和实验组5的实验用例23的候选服务数不同，但服务类数都为30。这样用同一实验组的实验用例可以测试当候选服务数不变时组合方法效率同服务类数目之间的关系。不同实验组的实验用例可以测试当服务类数不变时组合方法效率同候选服务数目之间的关系。实验采取的数据集由随机函数产生，共选取5个QoS属性，取值范围都在 ［0，100］。实验环境为奔腾2.13GHz，内存2G，开发语言为Java。

表2 对比了Sky－MCSP－R方法和MCSP－K方法在25个测试用例上的优化率，即最终所选服务组合的质量与穷举法求出的最优解质量的比率，反映了组合方法所选服务组合方案的性能。

从表2中不难看出，本文提出的Sky－MCSP－R方法的优化率略低于 MCSP－K方法。Sky－MCSP－R方法能达到平均90%的优化率，同MCSP－K算法平均91%的优化率相比降低了1%。

表1 实验用例

表2 优化率 （%）

图2 和图3展示了Sky－MCSP－R方法和 MCSP－K方法在实验用例上的运行时间比。用户的约束条件为2个，没有软约束条件。可以看出，在所有的情况下，时间比都小于1，说明Sky－MCSP－R方法的运行时间小于 MCSP－K方法，Sky－MCSP－R方法具有较高的时间效率。因为事实上平均每个服务类可以筛选出80%的Skyline服务，淘汰掉20%的候选服务，搜索效率得以提高。图2展示了对同一实验组实验用例的测试情况，能看到当候选服务数不变时组合方法效率的提升随服务类数的增加而增加，当服务类数较少时，效率的提升还有限，随着服务类数的增多，效果就非常明显了，最理想时Sky－MCSP－R的运行时间还不到MCSP－K的30% （Test Case＝20）。图3展示了不同实验组实验用例的测试情况，能看到当服务类数不变时组合方法效率的提升随候选服务数的增加而增加，但这不是必然的，有时效率的提升也会随候选服务数的增加而减少（对比Test Case＝9和Test Case＝14），这是因为随着候选服务数的增加，计算Skyline服务的时间开销也在增加。所以，增加服务类的数目比增加候选服务的数目更能促进Sky－MCSP－R方法效率的提升。但不论哪种情况，Sky－MCSP－R方法较之MCSP－K方法在时间效率上的优越性都是很明显的，虽然Sky－MCSP－R方法的优化率不如 MCSP－K方法，但以降低1%的优化率换取大幅度提高的时间效率，这显然是值得的。

此外，当约束条件为2个时，两种方法都未发生无解现象。将约束条件增为5个，用MCSP－K方法求解时，25个实验用例中有5个无解。而用Sky－MCSP－R方法求解时，因为将5个约束条件转化为2个 “硬条件”和3个 “软条件”，并未出现过约束，无解现象降低。

4 结束语

基于QoS的Web服务组合优化问题是目前Web服务技术研究的一个热点问题［16］。本文提出一种基于图的三阶段服务组合方法Sky－MCSP－R。该方法可以从候选服务空间中筛选出80%的高质量Skyline服务，缩小图算法的结点规模。然后运行MCSPi算法进行服务组合，尽可能找到满足用户需求的服务组合，提高了出解率。最后运行Relax算法求得最优解。Sky－MCSP－R方法有效解决了满足用户多QoS约束条件的Web服务组合优化问题，在时间效率和优化率之间获取平衡。

［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）.［王勇，代桂平，候亚荣.信任感知的组合服务动态选择方法［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）.［李金忠，夏洁武，唐卫东，等.基于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服务发现与服务组合研究 ［D］.重庆：重庆师范大学，2011.］

［10］Papadias D，TAO Y F，Fu 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和局部选择的启发式服务组合方法 ［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感知的动态服务选择 ［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） ［何炎祥，吴钊.动态Web服务组合关键技术与性能分析 ［M］.北京：清华大学出版社，2011.］