QoS约束下的语义web服务组合评估及优化

王向辉，冯志勇

(1. 天津大学计算机科学与技术学院，天津 300072；2. 山东建筑大学计算机学院，济南 250101)

QoS约束下的语义web服务组合评估及优化

王向辉1,2，冯志勇1

(1. 天津大学计算机科学与技术学院，天津 300072；2. 山东建筑大学计算机学院，济南 250101)

针对 QoS约束下的语义 web服务组合的多个组合方案，提出组合质量概念，并改进组合算法以便快速获得高质量组合方案．针对组合质量的不同指标，引入质量平衡系数，构造可调节的启发函数，并增加到两步组合算法的后向搜索中，从而使用户通过调节质量平衡系数，获得预期质量的组合方案．为了提高组合速度，在高效数据存储结构的基础上，采用逐步变窄的前向搜索策略．基于前述改进的算法实现一个组合规划器．实验表明该规划器能够快速给出满足QoS约束的组合方案，且通过质量平衡系数的设置，能够给出满足预期质量的组合方案．

web服务组合；组合质量；两步搜索；QoS；质量平衡系数

Web服务在跨语言、跨平台的数据交换和集成方面有着突出优势，成为实现SOA系统的首选[1]．随着 web技术的发展，互联网上出现了数量庞大的web服务，如何从中发现符合用户需求的服务(服务发现)是一项挑战性的工作，并受到服务计算领域研究者的广泛关注．在服务发现过程中，如果单个 web服务可能无法满足用户需求，就需要 web服务组合技术[2]，即从庞大的web服务集合中查找一组可组合的web服务，并形成满足用户需求的组合方案．语义web技术[3]的出现，解决了来自不同服务供应商、涉及不同领域的 web服务间的概念语义匹配问题，为实现web服务的自动组合奠定了基础．

QoS感知的 web服务组合问题，是近些年来的一个研究热点．它在组合过程中不仅考虑 web服务的功能属性，还要考虑与功能无关而与 web服务质量相关的 QoS属性，如响应时间、吞吐量、价格等，最终获得QoS最优的组合方案．关于这个问题，当前采取的解决方法有 3种：一是基于 web服务的功能属性找到若干组合方案，然后按照 QoS值进行排序[4-6]；二是利用任一时间算法首先找到一个组合方案，然后随着时间的推移将会遍历到所有组合方案，所以最终能得到 QoS值最优的方案[6-7]；三是改进两步搜索算法，直接找到QoS最优的组合方案[8-11]．

虽然前两种方法最终能够找到 QoS最优的方案，但它们的执行效率不高，而最后一种方法可以快速地获得QoS最优的组合方案．但针对一个QoS属性(如最短响应时间或最大吞吐量)，有的只是给出一个最优组合方案[8-10]，有的则能够给出全部的最优方案[11]．然而，对于语义 web服务组合来说，在获得某个 QoS属性值的多个最优解后，用户将面临新的选择，即如何从中选择一个最好的方案，这对组合方法的使用来说是迫切需要解决的问题．为此，本文提出一个组合方法，该方法能够快速找到满足 QoS约束的组合方案，且能够按照用户的偏好给出一个较好的组合方案．本文有3个创新点．

(1) 提出组合质量概念，将组合方案的语义质量、服务数和路径等都作为组合质量的组成元素，使用户可从这几个方面对 QoS相同的组合方案进行评价和比较．由于当前没有统一的组合语义评价模型，本文提出一个语义质量模型，它利用参数概念间的匹配关系和路径长度来确定组合方案的语义质量．

(2) 将 web服务按照输入参数概念聚类并存储，然后在组合算法中采用逐步变窄的前向搜索策略，使得前向搜索不再成为两步组合算法的瓶颈，从而保证了组合算法的高效性．

(3) 针对组合质量的不同指标，引入质量平衡系数，构造可调节的启发函数，并增加到两步组合算法的后向搜索中，从而使用户通过调节质量平衡系数，获得预期质量的组合方案．

1 问题定义

语义web服务组合问题包含问题域、语义本体、用户请求和组合方案4个要素．为了对本文讨论的组合问题有一个清楚的认识，这里先描述这4个要素．

一个问题域是所有可用的 web服务组成的集合．为了解决QoS约束下的组合问题，这里除了描述web服务的功能属性外，还需要描述QoS属性，如响应时间、吞吐量、价格等．

定义1 带QoS的web服务．web服务是一个四元组＜ws，Is，Os，QoSs＞，其中 ws为服务名，Is为输入参数集合，Os为输出参数集合，QoSs为服务提供的质量集合．这里QoSs中的每个质量使用三元组描述＜QoSn，QoSv，QoSr＞，即 QoSn名称，如＜Responsetime，300,ms，MAX＞表示QoS的最长响应时间为300,ms．

定义2 带QoS的问题域．带QoS的问题域是一个集合，其中的每个元素为带QoS的web服务．

在问题域中，web服务间是否能够组合，主要取决于一个服务的输入参数集与另一个服务的输出参数集概念间是否能够匹配．在同一本体内，概念间的匹配关系体现在本体中的语义匹配关系．而概念集间是否匹配表现为它们间满足的关系，具体定义如下.

定义 3 语义匹配关系．令 C为概念集合，x、y∈C，MR为语义匹配函数，若y＝MR(x)，则说明在函数MR的作用下，概念y可用概念x代替，即x在语义上匹配y，或y在语义上被 x匹配，表示为序偶＜x，y＞ MR∈ ．

在后面的描述中，通常将 MR看作语义匹配关系的集合．显然，语义匹配关系具有自反性和传递性.

定义 4 语义满足关系⊆MR．令 C为概念集合，MR为C中概念间的语义匹配关系集合，R和S是C的子集，则R⊆MRS＝(∀x)(x∈R→(∃y)y∈S∧＜x，y＞ MR∈ ．

定义 5 带 QoS的用户请求．该用户请求是一个三元组＜RIs，ROs，RQoS＞，其中RIs表示请求的输入参数集合，ROs表示期望的输出参数集合，RQoS表示对组合方案的 QoS期望．如＜Responsetime，3,000,ms，MAX＞表示用户期望的响应时间不超过3,000,ms．

定义 6 带 QoS的组合方案．该组合方案是一个四元组＜CIs，，COs，CQoS，CG＞，其中，CIs为其接受的输入参数集合，COs为其产生的输出参数集合，CQoS为其提供的QoS，CG为组合方案对应的带标记的有向无环图．这里，CG中的节点表示web服务，有向边表示服务参数概念间的语义匹配关系，其上的标记记录从始端节点的输出参数到终端的输入参数间的所有语义匹配关系．已知概念语义匹配关系集合MR，WS为CG中的web服务集合，则CG需满足下列条件：

(1) 对于任一入度为 0的 web服务 ws，满足ws.Is⊆MRCIs；

(2) 对于任一入度为k(k≠0)的web服务ws，假设mri表示指向ws的第i条有向边上的语义匹配关系集合，则满足∀in.(in ∈w s.Is→∃out.＜out，in＞∈∪1≤i≤kmri)，且

(4) 给定QoS计算函数fQoS，则符合上述3个条件的有向图CG，满足fQoS(CG)＝CQoS；

(5) 如果去掉CG中的任意一个节点，形成一个新的有向图 CG’，则 CG’不能同时满足上述的 4个条件．

这里使用带标记的有向无环图来表示组合方案，它能更加直观地展现组合方案中的控制流和数据流结构，方便向标准的工作流执行语言转换，如 WSBPEL[12]．同时，定义 6中的(1)～(3)条限定了组合方案需满足用户的功能请求；第(4)条要求组合方案满足用户的非功能请求，这两方面是保证组合方案正确性的必要条件；而第(5)条要求组合方案不存在冗余的web服务，这在组合方案执行时，可减少重复执行，提高执行效率．

需要注意的是，有向无环图表示的组合方案能够转换成带并行和顺序结构的工作流描述，见定理1．

定理 1 定义 6中描述的组合方案中的有向图CG能够转换成带并行和顺序结构的工作流W．

证 明 wsout0表示组合方案 CG中出度为 0的web服务集合，可以按照下面的步骤生成W：

(1) 对于 wsout0中入度为 0的任一 web服务ws，其对应的工作流Wws＝invoke(ws)；

(2) 对于 wsout0中入度大于 0的任一 web服务ws，进行下面的处理：①在 CG中查找使 ws得以满足的最小子图Gws；②wsout0’为Gws中指向ws的web服务集合，ws’为wsout0’中任一web服务，令wsout0＝wsout0’，则重复步骤(1)、(2)，可得到 ws’对应的工作流 Wws’；③生成一个并行结构 flow(Wws’)，即将wsout0’中的每个 web服务对应的工作流作为其中的一个分支；然后再生成一个顺序结构 sequence (flow(Wws’)，invoke(ws))，即执行flow结构，再执行invoke结构，这时Wws＝sequence(flow(Wws’)，invoke (ws))．

(3) 在W中创建并行结构flow(Wws)，即将每个Wws作为 flow的一个分支．这时，整个组合方案 CG的工作流转换完成．证毕．

定义 7 ,QoS约束下的语义 web服务组合问题．给定带QoS的问题域WS，带QoS约束的服务请求 R，概念语义匹配关系集合 MR，服务组合问题即为确定是否存在一个带 QoS的组合方案 CR，满足CR.CIs＝R.RIs，CR.COs＝R.ROs，且 CR.CQoS符合R.RQoS．

由于在解答一个 QoS约束下的组合问题时，会获得多个不同的组合方案，它们都满足给定的 QoS约束条件．因此，其他质量因素成了这些组合方案相互比较的依据，如参数间的语义匹配度、web服务的个数、服务路径的长度等．为了同 QoS质量相互区别，本文将这些质量因素称为组合方案的组合质量．这样，具有优良组合质量的组合方案可以称为一个好的组合方案，而对于QoS约束下的web服务组合来说，找到一个好的组合方案是一件有意义的事情，也是本文研究的重点．下面首先介绍带QoS的组合方案(定义6)的QoS质量和组合质量的计算方法，然后再介绍具体的组合方法．

2 质量模型及评估

为了简化处理，在本文的组合问题中，将响应时间作为组合问题的 QoS约束条件，同时在组合方案选取时考虑语义匹配度和服务个数这两个组合质量属性．这里将分别描述组合方案在每种质量指标下的计算模型．

2.1 ,QoS质量

在文献[13]中给出了带有并行和顺序结构的BPEL组合方案的QoS计算方法，而对于组合方案来说，基于有向图的表达形式更具有普遍性，因此，这里基于定义6描述的有向图给出一个等价的QoS计算模型MinRQM．

假定G为一个组合方案的有向图，这里将G中重复出现的web服务看作是不同的web服务．对于G中每个 web服务 ws，使用 frts(ws)获得其本身执行的最大响应时间，ind(ws)表示 ws节点的入度，wsin表示指向ws的web服务集合．则在G中ws得以执行的最短响应时间的计算函数如下：

即对于入度为0的web服务，根据定义6中的第(1)条，它们的输入参数均由用户请求直接提供，所以其在组合方案中的响应时间即为自身的响应时间．而对于入度非 0的 web服务，它们的执行时间是在所有提供其输入参数的 web服务执行完毕后，所以根据定义6中的第(2)条，wsin中的web服务均执行完毕后才可执行ws．同时，为了节约时间，对wsin中每个web服务的不同执行路径，采用并行方式执行，因此，这些执行路径最短响应时间的最大值才是 ws开始执行的时间，再加上ws本身的响应时间，即为ws在整个组合方案G中的最短响应时间．同时，考虑组合方案G的有向无环性，frt函数能够保证求得G中每个ws的最短响应时间．

使用wsout0表示组合方案G中出度为0的web服务集合，则根据每个web服务的最短响应时间，组合方案G的最短响应时间的计算函数如下：

即G中出度为0的web服务将在组合方案的最后执行，它们中最短响应时间中的最大值才能保证所有的ws都执行完毕，因此取最大值作为整个组合方案的最短响应时间．这里，函数公式(1)、(2)构成了最短响应时间计算模型MinRQM．根据定理1中的步骤，容易证明用 MinRQM模型计算的 G最短响应时间和与其对应的工作流 W的最短响应时间相同，其中W的计算方式与文献[13]中的描述方式相同．这里通过实例来说明转换过程和最短响应时间，见图1．

图1 组合方案及其工作流结构Fig.1 A solution and its workflow structure

图 1(a)表示用有向图形式描述的一个组合方案，其中每个椭圆里面分别标注了服务名和响应时间．根据 MinRQM模型，frt(ws5)＝max{frt(ws3)，frt(ws4)}＋100，而 frt(ws3)＝frt(ws1)＋50＝250， frt(ws4)＝max{frt(ws1)，frt(ws2)}＋100＝300，所以frt(ws5)＝max{250，300}＋100＝400；又 frt(ws6)＝frt(ws4)＋200＝500，且ws5和ws6都是出度为0的节点，因此，图 1(a)描述的组合方案的最短响应时间为max{frt(ws5)，frt(ws6)}＝500．

图 1(b)是对应图 1(a)的工作流描述，它使用Flow前缀描述了并行结构；使用 Seq描述了顺序结构，并且在该图中默认左边的分支先于右边的分支执行；使用Inv前缀表示对具体web服务的调用．在最短响应时间的计算方法[14]中，规定并行结构取分支的最大响应时间作为该结构的最短响应时间，顺序结构则取所有分支响应时间的总和作为顺序结构最短响应时间．根据这个规定，可以计算得到图中 Seq1的最短响应时间为 400，Seq2的最短响应时间为500，因此 Flow1的最短响应时间为 max{Seq1，Seq2}＝500．这与图1(a)使用MinRQM模型计算的结果相同．

2.2 组合质量

对一个组合方案来说，服务数和路径长度都有统一的计算方法，而对于体现其参数间语义匹配程度的语义质量来说，并没有统一的计算方法，这里提出一个简捷合理的组合方案语义质量模型WSCSQM．

在描述组合方案的语义质量之前，首选需要确定每对匹配的参数概念间的相似度．这里假定所有的概念使用本体描述，概念之间的关系由它们在本体层次上的匹配类型和距离确定．匹配类型采用 Exact、Plugin和Subsume 3种类型[15]，同时借鉴匹配质量计算方法[14]，取 Exact匹配类型的概念间相似度为 1，Plugin为3/4，Subsume为1/2．已知参数a1、a2，其类型分别为t1、t2，若a1匹配a2，则t1与t2的匹配关系为Exact、Plugin、Subsume中的一种，其计算函数如下：

定义6描述的组合方案的有向图中，虽然通过边上的标记描述了参与组合的web服务间的参数匹配信息，但未展示用户请求中的参数与web服务具体参数间的匹配信息．而这些信息在整个组合方案语义质量计算中不可缺少，因此，本文通过引入初始请求服务和目标请求服务来扩展前面的组合方案定义．

定义 8 初始请求服务．初始请求服务是一个web服务，它没有输入参数，只有输出参数，且输出参数为用户请求的初始参数集合．

定义9 目标请求服务．目标请求服务也是一个web服务，它只有输入参数，没有输出参数，且输入参数为用户请求的目标参数集合．

给定用户请求 R，其提供的输入参数为{1#，2#，3#，4#}，输出参数为{18#，19#}，引入初始和目标请求两个扩展服务，并在边上加入标记后，图 1(a)的组合方案转变成扩展的带标记组合方案，见图 2．在图2中，带#后缀的数字表示参数名．若边上只标注一个参数名，表明两端web服务通过同名参数匹配；若使用尖括号标记，则表示两端 web服务通过不同的参数名匹配，其中，第1个参数名为始端web服务的参数，第2个为终端的参数，如ws1和ws3间的＜7#，9#＞，表示ws1的参数7#与ws3的参数9#在语义上匹配；若使用花括号标记，则表示两端web服务间有不止1对参数能够匹配，如ws4与ws6间的{＜15#，15#＞，＜20#，21#＞}，表示ws4的参数15#匹配ws6的15#，ws4的20#匹配ws6的21#．

图2 扩展的带标记组合方案Fig.2 An extended solution with labels

直观地，组合方案中的每个执行路径的语义质量，是由路径上的每个 web服务的语义质量决定的．因此，这里给出每个web服务ws在执行路径上的语义质量，即执行到该web服务时，参数的语义匹配质量，其计算函数如下：

式中：wsin为有向图中指向 ws的 web服务集合；label(wsi，ws)为有向边(wsi，ws)上的标记集合．

式(4)表示 web服务在执行路径上的语义质量等于其所有输入参数的语义质量的平均值，而每个输入参数的语义质量则等于与之匹配的输出参数的匹配度，与产生这个输出参数的 web服务语义质量的乘积．若指定 ws为目标请求服务，则该公式计算的结果即为整个组合方案的语义质量．

从式(4)可以看出，fsd函数的计算是通过递归的方式完成的，并且其取值区间是(0，1]．在执行路径前面的参数匹配情况会通过路径上的 web服务传递下去，这是与实际情况相符的．例如，若某个非初始请求服务 ws执行路径上的所有参数的匹配度都为1，则这个路径上所有的web服务的语义质量也为1，最终根据式(4)，ws的语义质量也为 1．若执行路径上存在参数匹配度小于1的匹配，则整个组合方案的语义质量将小于 1．如果这种近似匹配经过的路径越长，则其匹配度越低，从而说明了匹配过程中的语义损耗．

式(3)、式(4)构成了组合方案的语义质量模型WSCSQM．下面通过计算图 2中组合方案的语义质量来说明WSCSQM模型的使用．这里，假设出现在边上不同参数名间的匹配对(即尖括号中参数名不同的标记)匹配度为0.75，同名参数的匹配度为1，则整个组合方案的语义质量为 fsd(目标请求)．根据式(4)若要计算fsd(目标请求)，则需从头计算每个执行路径上的web服务的语义质量，计算过程如下：

同样的算法，可以得到 fsd(ws5)＝0.615,234，fsd(ws6)＝0.669,922，最终 fsd(目标请求)＝0.481,933．

组合方案的服务数也是衡量组合方案质量的一个重要指标．这里将组合方案最终执行的 web服务的个数作为其服务数，并不是不同的 web服务个数．如图 1表示的组合方案，其服务数为 10，即图1(b)中展示的 Invoke个数，而不是图 1(a)中的服务个数6．因为在实际执行中，ws1、ws2和ws4将被重复执行．

3 组合方法

前面已给出了QoS约束下的语义web服务组合问题的定义和组合方案的质量模型及评估方法，本节给出一个高效的问题解决方案，它保证得到的组合方案能够满足给定的 QoS约束，且具有较高的组合质量．

3.1 系统框架

WS-Challenge2010[13]给出了一个 web服务组合框架，但该框架是针对竞赛的，不具有一般性．这里结合前面的定义，给出一个更加通用的系统框架．通过该框架不仅能够解决文献[13]中的问题，而且还能处理本文提出的新问题．由于 web服务组合问题本质上是AI规划问题[16]，所以这里将web服务组合系统称为 web服务组合规划器．由于该规划器主要解决 QoS约束下的组合问题，因此这里简称为QoSWSCPlaner，其系统框架如图3所示．

图3 QoSWSCPlaner系统框架Fig.3 Framework of QoSWSCPlaner

从图中可以看出 QoSWSCPlaner主要由问题预处理和组合引擎两部分组成，前者对问题相关描述进行解析，包括问题的检索空间即带QoS的问题域、用户的检索请求即带 QoS的用户请求，以及描述两者中参数概念间的语义关系的域本体，并对这些描述进行预处理生成便于组合引擎使用的数据结构．组合引擎是QoSWSCPlaner的核心，它改进了传统图规划算法，在高效的数据结构的基础上，采用逐步变窄的前向搜索和 QoS约束的后向启发搜索重新设计了两步搜索算法；同时，增加组合质量调节功能，使得用户可以根据自己的偏好控制启发函数，从而获得期望质量的组合方案．此外，QoSWSCPlaner还可以利用生成工作流程功能将有向图组合方案转换成标准的工作流执行文件．

3.2 问题预处理

作为QoSWSCPlaner输入的问题域、域本体和用户请求，通常使用各种现有的 XML文件存放，如使用WSDL或OWL-S等存放问题域中的每个web服务和用户请求，使用 OWL来存放域本体描述．这就需要在解决组合问题之前首先对这些文件进行解析，并使用合理的存储结构和存取方式进行组织和存储，以便供后续的组合引擎使用．

在这一阶段形成了两个重要的数据存储结构：一个用来存取 web服务的 wsSetByInput，另一个用来存取概念语义匹配关系的 matchRelations．前者使用哈希存储结构，其中出现在问题域中的所有输入参数以及能够匹配这些参数的所有概念作为其索引键，能够接受键值的 web服务集合作为其存储值，而每个元素记录 web服务及其被键值匹配的输入参数．后者采用两级哈希结构，记录所有概念间两两匹配关系，一级键为被匹配的参数，二级键为匹配的参数，值为(0，1]范围的数值，表示两级键之间的匹配情况，其值按照式(3)计算得到．在规划器运行时，所有的 web服务和语义数据都按照这两种存储结构直接加载到内存中，这样可减少对外存的访问，从而加快整个规划器的执行速度．

3.3 组合引擎

基于图规划的两步搜索算法经常被用于进行web服务组合[4,11,16]．其核心思想是首先在问题域中的所有 web服务中，查找用户请求输入参数能够满足的所有 web服务，形成一个展现 web服务执行关系的有向分层图，称为前向搜索过程；接着在前向搜索得到的有向分层图上，从后往前以深度优先的方式查找能够提供用户期望输出参数的 web服务执行路径，过滤掉那些与请求输出参数无关的服务；最终，这些执行路径形成了web服务的组合方案．在QoS约束下的服务组合中，QoS约束主要体现在第2步的后向搜索中，即需要查找那些提供用户期望输出参数且满足QoS约束条件的web服务执行路径，称这个过程为QoS约束的后向搜索．

前向搜索关键的操作是在每一层都需要遍历所有的 web服务以检查其输入参数是否被满足，这个过程耗时巨大，直接影响着组合的效率．因此，为减少前向搜索的时间，研究者采取了各种措施[9,11,17].本文采用逐步变窄的前向搜索策略，并本着将重复检查降到最低的原则，重新设计了一个快速的前向搜索算法．同时，为了方便QoS约束的后向搜索，算法在进行有向分层图构建的同时，记录并计算了每个web服务执行路径的最优 QoS值．QoSWSCPlaner组合引擎的执行过程如图4(算法1)所示．算法1 WebServiceComposition(matchRelations，wsSetByInput，QWr)

图4 算法1Fig.4 Algorithm 1

图中，outputInfos是 1个集合，记录了每个参数和web服务的详细信息，包括其最短响应时间、提供该参数的web服务集合等；QWr为带QoS的用户请求(定义 5)；compResult为带有并行和顺序结构的组合方案(行5～6)．

3.3.1 逐步变窄的前向搜索

算法1中的FastForeSearchToFixPoint函数实现了加速的前向搜索功能，其执行过程如图 5(算法 2)所示．该算法将用户请求的输入参数作为开始的当前状态 currentstates(行 1)；然后在 wsSetByInput中查找与 currentstates中输入参数相关的 web服务集合(行 8～17)，这样就在问题域中过滤掉大量不相关的web服务；接着在这些相关web服务中，查找其输入参数都能够被currentstates满足的web服务，并将这些 web服务的输出参数加入到 currentstates(行18～30)，这些web服务构成了有向分层图的第1个层次；最后基于新的currentstates进行第2个层次的查找，依次类推，直到到达不动点整个前向查询过程终止(行6)．

为了提高前向搜索的执行速度，在算法2中采取了3项加速措施：

(1) 在查找相关 web服务过程中，为每个 web服务增加是否访问标记isVisited(行12～15)，减少对已访问web服务的重复添加；

(2) 在筛选满足的 web服务过程，每个已满足web服务在下一层次的筛选中也是满足的，所以为其增加是否满足标记 isSatisfied(行 20～23)，减少重复判断；

(3) 判断每个 web服务的所有输入参数是否被当前状态满足，需要逐个判断其匹配性，是相当耗时的．但注意到，WSsetByInput中其实保存了每个输入参数与所对应的web服务的信息，因此，在查找相关web服务的过程中使用inputSetSatisfied顺便记录了当前状态能够提供的 web服务的那个输入参数(行 11)．这样，在满足性判断中，就不需对当前状态和服务的输入参数进行逐一语义匹配判断，只需查看输入参数集是否包含在inputSetSatisfied中(行24)．

此外，算法 2在建立有向分层图的过程中，维护和更新了outputInfos(行3、21、27)，这些信息是后面计算 QoS约束组合方案的基础．InitRespTime-

图5 算法2Fig.5 Algorithm 2

算法2 FastForeSearchToFixPoint(wsSetByInput，matchRelations，QWr)OfReqparam函数用来将用户请求的输入参数能够匹配的所有的参数的响应时间置 0，ComputeOptResp-Byws函数用来循环更新每个输出参数的最短响应时间和能够提供该参数的 web服务，以及 web服务在执行路径上的最短响应时间等信息．

3.3.2 QoS约束的后向启发搜索

算法1中的BackSearchWithQoS函数实现了后向搜索，其过程如图6(算法3)所示．

算法 3 DoBackSearchWithQoS(currentGoalStates，maxResponse，

图6 算法3Fig.6 Algorithm 3

该算法递归地查找实现每个当前子目标的 web服务执行路径，且要求每条执行路径的响应时间在QoS范围内，并将这些路径组成一个并行结构的工作流程．在算法递归调用过程中，按照式(3)、式(4)递归计算了组合方案的语义质量(行7、19～21、24)．

对于一个 QoS约束下的组合方案来说，满足QoS约束是其正确性的必要条件，但正确并不意味着质量高．一个高质量的组合方案应该具有响应时间短、语义质量高、服务数少、路径短的特点．但实际中，约束下的多准则优化问题是 NP-hard问题[18]，所以，目前没有办法找到满足这些特点的最优组合方案，只能通过近似算法找到其近似最优解．这里的后向搜索算法，在选择每个提供参数的web服务时，采用了综合响应时间、语义质量和服务数特点的局部启发策略(算法 3)，该策略保证每次都选择综合质量最高的web服务，其主要思路如下：

(1) 在前向搜索过程中，记录每个 web服务的最短响应时间，优先选择这个时间短的web服务；

(2) 每个候选 web服务都记录了与给定目标参数匹配的输出参数以及它们之间的语义匹配度，优先选择这个匹配度高的web服务；

(3) web服务的入度数越少，意味着执行该服务所需的web服务数可能越少，因此，优先选择入度数少的web服务；

(4) 所选 web服务的响应时间越长，有可能组合路径越长，根据前面的语义质量模型 WSCSQM，从而可能使整个方案的语义质量降低；同时，路径越长，也可能意味着组合方案的服务数越多．可以看出，这3个维度对组合方案的质量是相互影响的．因此，在实际选择中，需要综合考虑这 3个影响质量的因素，提供灵活、有效的web服务质量评估方法．

在GetWSwithOptimal函数中采用的启发函数表达式为

式中：md为给定目标参数与所提供参数的匹配度；ind为候选web服务的入度；rt为候选web服务的最短响应时间；mind为问题域中所有 web服务的最大入度；mrt为给定目标参数的最大响应时间约束；cr为组合质量的平衡系数，其范围为[0，1]；cl为组合质量和QoS平衡系数，其范围也为[0，1]．若cr为0，则表示只选择入度最小的服务；若cr为1，表示只选择语义匹配度最高的服务；若 cr为(0，1)范围内的值，则需要选择组合质量综合值最高的服务．cl为0表示选择最短响应时间最小的服务；cl为1表示只考虑组合质量因素；(0，1)范围内的cl值表示两方面因素都考虑．

4 实验结果与分析

WS-Challenge2010[13]提供了专门的 web服务组合测试集生成工具 TestsetGenerator和检验工具ChallengeChecker，使用 TestsetGenerator可以生成不同规模的虚拟测试集，每个测试集包括 web服务的描述文件、服务质量描述文件、本体描述文件和用户请求描述文件．为了方便结果的比较，本文使用竞赛第1名[9]的5个测试集，其基本特征描述见表1．

表1 测试集基本特征Tab.1 Basic features of test sets

本文 QoSWSCPlaner使用Java语言实现，本次实验的硬件环境为ThinkPad E300笔记本(2.4,GHz× 2，4,GRAM，Win7)．在实验中，QoS因素只考虑响应时间．下面分别对 QoSWSCPlaner前向搜索的高效性、后向搜索中质量调节的灵活性和有效性、以及整个规划器的执行效率和正确性进行相关的实验．需要说明的是，为了减少实验中的不稳定因素，所有执行时间相关的实验数据是在多次执行的基础上取其中多次出现的一个值．

4.1 前向搜索的结果与分析

在 QoSWSCPlaner中采用逐步变窄的前向搜索策略，即在前向搜索的每次迭代中，在查找当前状态满足的web服务之前，先对问题域中的 web服务进行一遍过滤，得到与当前状态相关的web服务集合，然后在该 web服务集上进行当前状态满足性的检查，得到有效的web服务集合．

从图7可以看出逐步变窄策略对web服务的过滤效果明显，尤其在后3个大规模测试集中，第1次分别过滤出30%、51%、31%的相关web服务．这样，在满足性检查时，仅检查这些相关的web服务即可，从而大大缩短了前向搜索的时间．同时，在满足性检查时，通过充分利用过滤相关服务时记录的已满足参数信息，进一步减少了搜索时间．文献[11]也提出了一种快速的组合算法，基于本文同样的测试集给出了前向搜索的时间，本文提出的前向搜索时间明显高于文献[11]，如图8所示．

图7 逐步变窄前向策略的过滤效果Fig.7 Effects of gradually narrowing forward search

图8 本文前向搜索时间与文献[11]的比较Fig.8 Comparison of forward search time between this paper and Ref.[11]

4.2 后向搜索的结果与分析

QoSWSCPlanner的后向搜索保证得到的是满足QoS约束的组合方案，同时它允许用户通过质量平衡系数调节组合方案的组合质量．在 Testset5上，假定QoS约束为最短响应时间4,070,ms，验证质量平衡系数 cl和 cr(见式(5))对组合方案的语义质量和服务数的影响．实验中对 cl的取值为 0、0.2、0.5、0.8和1.0，然后对每一个cl值对cr取值0、0.2、0.5、0.8和1.0．其对组合方案的调节效果如图9所示(横坐标第1行表示cr的不同取值)．

当 cl＝0时，根据式(5)，cr的调节作用失效，实验得到一个组合方案，其语义质量为 0.114,3，服务数为32个．其他情况下，cr的调节具有明显的作用．通过分析，得出3点结论．

(1) 候选 web服务的最短响应时间对组合质量的影响很大．

当cl＝0即只考虑最短响应时间时，得到组合方案的服务数为 32，是所有实验中的最小服务数．当cl＝1.0(见图9(d))即在选择web服务时完全不考虑最短响应时间，得到的服务数都比 cl小于 1的情况大，同样组合方案的语义质量也不高．在cl＝0.2时(见图9(a))，cr系数调节作用比较明显，语义质量和服务数均与平衡系数cr呈线性递增关系．即cr越大在构建组合方案的过程中考虑的语义因素越多，则整个方案的语义质量越高；同时cr越大，在选取web服务时考虑的服务数因素越少，则整个方案的服务数越多．

(2) 后向搜索的启发策略是局部的，因此找到的是近似最优解．从图 9(b)和图 9(c)可以看出，随着cr的增加，其考虑的服务数因素减少时，整个组合方案的服务数反而下降．

(3) 在选择 web服务时，如果考虑语义质量和服务数因素(cl≠0)，则组合方案的组合质量变化明显．这意味着用户可以根据自己的偏好，在多个不同质量组合方案中做出自己的选择，充分说明了QoSWSCPlanner中质量调节的有效性．

图9 质量平衡系数对组合质量的影响Fig.9 Effects of quality equilibrium coefficient on composition quality

4.3 执行效率及正确性的结果与分析

QSynth系统[10]是基于 WS-Challenge2009第 1名的算法[9]实现的组合系统，它将查找最短响应时间组合方案与查找最大吞吐量组合方案并行执行，在300,ms(不包含预处理时间)的时间内找到全部 5个测试集的最优组合方案．由于采用并行算法，可以认为其单独查找最短响应时间组合方案的时间与查找两个组合方案的时间相当．本文提出的QoSWSCPlaner在组合时间上体现出了与QSynth相当的执行速度，而且找到了每个测试集的最短响应时间，如表2所示．这里，在运行QoSWSCPlaner时，设置每个测试集的 QoS约束为其最短响应时间(见表1)，并取cl＝0．

表2 QSynth与本文的QoSWSCPlaner比较Tab.2 Comparison between QSynth and QoSWSCPlaner

QoSWSCPlaner得到的所有组合方案均使用ChallengeChecker工具进行了正确性测试，并得到了组合方案的路径长度和服务数信息(见表 2)．从实验数据中可以看出：QoSWSCPlanner能够在300,ms内找到最优解，且最优解的路径长度和服务数与QSynth相当；在 Testset4中找到的最优解的服务数为 40个，远少于 QSynth的 93个，进一步说明了QoSWSCPlanner后向搜索中减少web服务的措施是有效的．

5 相关工作

目前，考虑QoS属性的web服务组合方法主要有两大类：一类是排序法，即首先根据web服务的功能属性查找若干组合方案，然后按照QoS进行排序，并将QoS最优的方案提供给用户[4-5]；另一类是QoS感知的方法，即在组合过程中，既考虑服务的功能属性又考虑其QoS属性，直接得到一个组合方案．由于排序法在组合时并不考虑 QoS因素，所以其第一阶段的组合结果将有很多，而基于多个组合结果的排序也是一个耗时的过程．所以，从效率上来讲，排序法远低于 QoS感知的方法．因此，本文主要采用 QoS感知的方法进行组合，下面主要介绍 QoS感知组合的相关工作．

一些研究者[6-7]采用任一时间算法来进行QoS感知的组合，这种算法可以很快得到一个组合方案，并且时间越长，结果越好．Kil[6]基于近似搜素算法beam stack和启发策略，设计了任一时间QoS感知的WSC算法，并验证了其可以更快地找到质量较高的组合方案．Yan等[7]根据 QoS值扩展规划图，将其值标记成边的权重，然后在该图基础上运用迪杰斯特拉(Dijkstra)算法查找最优方案，由于迪杰斯克拉算法会遍历到图中的每个顶点，因此随着时间的推移，它总能找到无冗余的QoS最优方案[9]．文中将I/O参数的语义匹配关系进行了扁平化处理，不用每次在匹配时都运行 OWL推理机，这样节省了组合时间．任一时间算法虽然效率很高，但得到的组合方案并不一定是QoS最优的，而QoSWSCPlanner可以快速得到一个QoS最优的方案，实验表明它在大规模的web服务集中效率也很高．

也有一些研究通过QoS感知的方法得到了QoS最优的方案[8-10]．Xu等[8]采用前向广度优先搜索和后向深度优先搜索相结合的方法找到了 QoS最优的组合方案．在前向搜索中，记录了每个web服务和数据类型的最优 QoS值，并通过前向搜索的逐步迭代过程更新这些最优值；然后在后向搜索中按照目标输出参数类型，递归查找每个提供该类型的 QoS最优的web服务，最终形成一个QoS最优的组合方案．Jiang等[9-10]采用 3个阶段完成组合，首先采用前向过滤找到有效的 web服务，然后采用动态编程方法找到每个概念的最优 QoS值，并在查找的过程中记录提供最优值的 web服务，形成组合子图；最后，利用多线程技术在组合子图上并行查找满足最大吞吐量和最短响应时间的组合方案．在 WS-Challenge2009中，姜伟团队的方法在最快的时间内找了所有测试集的最优QoS方案，获得了第1名；而许斌团队则在第5个大规模测试集上的执行时间多于前者，取得了第 2名．这些方法对每个QoS值获得了一个最优方案，邓水光等[11]提出了 QoS最优的全解构造方法，也是采用3个阶段完成，首先进行前向搜索获得去掉无用服务的分层规划图，然后基于该图进行 QoS最优值的计算，最后以QoS最优值为约束条件，以用户请求的输出参数为起点后向搜索所有的 QoS最优解．该方法能够获得多个 QoS最优的组合方案，但其获得单个最优解的效率不如文献[9]中的方法．

Bartalos等[17]提出了高效的 QoS感知的组合方法，它在组合前的预处理阶段设计了高效的数据结构和算法，为后面的快速组合提供了基础．通过web服务间的兼容性检验将 web服务连接成一个有向无环图，图中记录了 web服务间的前驱-后继关系．然后将 web服务分成两种：一种是其输入参数可由其他服务提供；另一种是其有一个或多个输入参数不能由其他服务提供，后者称为用户相关服务．对于用户相关服务来说，如果用户请求的输入参数不能满足，则该服务为无效服务．基于前面的预处理，组合算法取得了很好的速度，但其组合算法并不能求得 QoS最优的方案．

本文提出的 QoSWSCPlanner能够快速地得到QoS最优的方案，它借鉴了文献[8]中的组合思路，但在预处理阶段使用输入参数聚类相关 web服务，并利用逐步变窄的思想修改了前向搜索算法，大大提高了前向搜索速度，同时也使其整体组合速度与文献[9]相当．此外，QoSWSCPlanner并不局限于仅得到一个 QoS最优的方案[8-9]，也不局限于求所有最优方案[11]，而是建立了语义质量模型，在后向搜索中通过灵活的质量启发函数来优化 QoS约束下的组合方案质量，为通过放宽 QoS约束条件的方式来获得优良的组合方案提供了可行的思路．

在 web服务组合中利用质量启发来改进组合方案质量的研究也有一些．Arpinar等[19]在组合过程的web服务选择中，对候选web服务的QoS值和语义相似度进行综合权衡，优先选择综合质量高的 web服务．Freddy用公共描述度与匹配度计算参数间的相似度，并提出语义链的质量的计算方法，同时将其与 QoS整合在一起建立组合方案质量模型[14]. Hatzi等[20]给出了通过参数语义距离计算组合方案语义距离的方法．本文将组合方案质量分成 QoS质量和组合质量两部分，并在 QoS约束下评估组合方案的组合质量．因此，要求组合方案首先满足 QoS约束，然后再计算其组合质量，包括语义质量和服务数．在语义质量计算时不仅考虑语义相似度，而且还考虑路径长度对语义质量的影响．本文工作与相关文献的比较如表3所示．

表3 本文工作与相关文献的比较Tab.3 Comparison among this paper and others

6 结 语

在解决QoS约束下的web服务组合问题时，可能会得到多个满足 QoS约束的组合方案．本文提出了包含语义质量和服务数的组合质量概念，用来对多个组合方案进行评估和比较．其中，基于带标记的有向图，设计了合理的语义质量模型，为多个组合方案的语义评估提供了依据．同时，改进了图规划的两步搜索算法，并基于该算法设计了一个组合规划器QoSWSCPlanner，它能够快速找到满足 QoS约束且具有高组合质量的方案．它在组合开始前使用以输入参数为键的哈希结构组织 web服务，在此基础上设计了逐步变窄的高效前向搜索算法，实验表明这样的改进大大缩短了前向搜索的时间．它也修改了后向搜索算法，在其中引入了组合质量启发函数．该函数通过质量平衡系数能够对候选 web服务的语义匹配度、入度数以及执行路径上的最短响应时间进行控制，从而达到对最终方案的组合质量特性进行干预的目的．最后的实验验证了这种调节是有效性的．

通过质量平衡系数的不同设置，QoSWSCPlanner能够得到多个 QoS相同但组合质量不同的组合方案，为用户按需选择组合方案提供了基础．此外，实验展示了QoSWSCPlanner在大规模测试集上也能够在毫秒级上快速给出组合方案，这为面向互联网构建大规模的面向服务系统提供了一个有效的方法．

当然，本文的方法还有一些需要优化的地方. 如后向启发函数还可以进一步优化，可以增加影响组合质量的其他因素，使得规划器对组合质量的调节更加灵敏和有效，从而为用户提供更有意义的参考．再有，本文的规划器在组合时默认环境是静态的，并没有考虑服务环境的动态性，如服务的增加、删除和QoS质量变化情况等，动态环境下的 QoS约束组合将更具有实际意义．最后，组合方案的正确性还需验证技术的支持[21]．

［1］ High Rob Jr，Kinder Stephen，Graham Steve. IBM's SOA Foundation-An Architectural Introduction and Overview[M]. IBM，2005.

［2］ Rao Jinghai，Su Xiaomeng. A survey of automated web service composition methods[C]// Semantic Web Services and Web Process Composition 2004. Washington：Springer-Verlag Berlin Heidelberg，2005：43-54.

［3］ Antoniou Grigoris，van Harmelen Frank. A Semantic Web Primer [M]. 2nd ed. Massachusetts，London：The MIT Press，2008.

［4］ Bansal S K，Bansal A，Gupta G. Semantics-based web service composition engine[G]// Blake M B，ed. Semantic Web Services. Washington：Springer-Verlag Berlin Heidelberg，2012：329-343.

［5］ Shiaa M M，Fladmark J O，Thiell B. An incremental graph-based approach to automatic service composition [C]// IEEE International Conference on Services Computing. Honolulu，USA，2008：397-404.

［6］ Kil Hyunyoung. Efficient Web Service Composition：From Signature-Level to Behavioral Description-Level[D]. Pennsylvania，USA：Department of Computer Science and Engineering，The Pennsylvania State University，2011.

［7］ Yan Yuhong，Chen Min，Yang Yubin. Anytime QoS optimization over the PlanGraph for web service composition[C]//Proceedings of the 27th Annual ACM Symposium on Applied Computing. New York，USA，2012：1968-1975.

［8］ Xu Bin，Luo Sen，Yan Yixin，et al. Towards efficiency of QoS-driven semantic web service composition for large-scale service-oriented systems[J]. Service Oriented Computing and Applications，2012，6(1)：1-13.

［9］ Huang Zhenqiu，Jiang Wei，Hu Songlin，et al. Effective pruning algorithm for QoS-aware service composition[C]// IEEE Conference on Commerce and Enterprise Computing. Vienna，Austria，2009：519-522.

［10］ Jiang Wei，Zhang Charles，Huang Zhenqiu，et al. QSynth：A tool for QoS-aware automatic service composition[C]// Proceedings of the IEEE International Conference on Web Services(ICWS). Miami，USA，2010：42-49.

［11］ 邓水光，黄龙涛，吴 斌，等. 一种QoS最优的语义Web服务自动组合方案[J]. 计算机学报，2013，36(5)：1015-1029. Deng Shuiguang，Huang Longtao，Wu Bin，et al. QoS optimal automatic composition of semantic Web services [J]. Chinese Journal of Computers，2013，36(5)：1015-1029(in Chinese).

［12］ OASIS. Web Services Business Process Execution Language Version 2.0[EB/OL]. https：//www.oasis-open. org/committees/download.php/21575/wsbpel-specification_ public_review_draft_2_diff.pdf，2006-11-20/2013-10-27.

［13］ CEC’2010. Web Services Challenge 2010[EB/OL]. http：//ws-challenge. georgetown. edu/wsc10/，2013-04-06.

［14］ Lécué F. Optimizing QoS-aware semantic web service composition[C]// Proceedings of the Eighth International Semantic Web Conference(ISWC). Washington：Springer-Verlag Berlin Heidelberg，2009：375-391.

［15］ Paolucci M，Kawamura T，Payne T R，et al. Semantic matching of web services capabilities[C]// ISWC 2002. Washington：Springer Berlin Heidelberg，2002：333-347.

［16］ Oh S-C，Lee D，Kumara S R. Effective web service composition in diverse and large-scale service networks [J]. IEEE Transactions on Services Computing，2008，1(1)：15-32.

［17］ Bartalos P，Bieliková M. Effective QoS aware service composition based on forward chaining with service space restriction[G]// Blake M B，ed. Semantic Web Services. Washington：Springer-Verlag Berlin Heidelberg，2012：313-328.

［18］ Papadimtriou C H，Steiglitz K. Combinatorial Optimization：Algorithms and Complexity [M]. London：Prentice-Hall，1982.

［19］ Arpinar I B， Zhang Ruoyan， Aleman-Meza Boanerges，et al. Ontology-driven Web services composition platform[J]. Information Systems and e-Business Management，2005，3(2)：175-199.

［20］ Hatzi O，Vrakas D，Bassiliades N，et al. The PORSCE II framework：Using AI planning for automated semantic Web service composition[J]. The Knowledge Engineering Review，2013，28(2)：137-156.

［21］ 胡 静，饶国政，冯志勇. 基于多元 Pi-演算的 Web服务组合描述与验证[J]. 天津大学学报：自然科学与工程技术版，2013，46(6)：520-525. Hu Jing，Rao Guozheng，Feng Zhiyong. Polyadic Picalculus based description and verification for Web service[J]. Journal of Tianjin University：Science and Technology，2013，46(6)：520-525(in Chinese).

（责任编辑：赵艳静）

Evaluating and Optimizing Semantic Web Service Composition Under QoS Constraints

Wang Xianghui1,2，Feng Zhiyong1
(1. School of Computer Science and Technology，Tianjin University，Tianjin 300072，China；2. School of Computer Science and Technology，Shandong Jianzhu University，Jinan 250101，China)

Regarding many solutions in semantic web service composition under a given QoS constraint，a composition quality concept was proposed，and an improved composition algorithm was designed to quickly generate a solution with high composition quality. Concerning different criteria of composition quality，quality equilibrium coefficient was introduced. And it was used to construct an adjustable heuristic function，which was applied to backward search of traditional two-step search algorithms. Thus，users can obtain a solution with desirable composition quality by adjusting the equilibrium coefficient. To improve efficiency，the composition algorithm adopted the gradual narrowing forward search strategy，which was based on an efficient data storage structure. On the basis of this improved algorithm，a composition planner was achieved. A series of experiments indicate that the planner can generate solutions satisfying given QoS constraint values. Meanwhile，by setting different values to the quality equilibrium coefficient，the planner can produce a desirable composition quality solution.

web service composition；composition quality；two-step search；QoS；quality equilibrium coefficient

TP301

A

0493-2137(2015)02-0126-13

10.11784/tdxbz201310075

2013-10-31；

2013-11-27.

国家自然科学基金资助项目(61173155，61070202).

王向辉（1979— ），女，博士研究生，讲师.

王向辉，wxh_225@163.com.

时间：2014-01-06. 网络出版地址：http：//www.cnki.net/kcms/detail/12.1127.N.20140106.1530.002.html.