Web服务组合中的去冗余方法研究

◆崔晓柳 范国栋 李静

Web服务组合中的去冗余方法研究

◆崔晓柳 范国栋 李静通讯作者

（山东理工大学 山东 255049）

Web服务组合结合了网络上不同功能的服务，以完成更复杂的功能，满足用户的需求。然而，传统方法得到的解决方案往往包含不必要的冗余服务，效果重复的服务会导致额外的响应时间和成本。为了去除冗余服务，本文提出了一种Web服务组合的去冗余方法（CRR，composition redundancy removal）。该方法对规划图算法进行改进，在规划图算法中加入去冗余过程。首先对服务存储库进行搜索，找出满足用户需求的候选服务；然后，以用户请求的目标输出为起点进行逆向搜索，同时删除冗余服务，得到无冗余的Web服务组合结果。使用数据集进行实验分析与验证，结果表明，与改进前的规划图方法比较，CRR过程去除了大量冗余服务，可以获得服务质量QoS（Quality of Service）更优的解。

Web服务组合；QoS；规划图；去冗余

近年来，Web 服务作为可以满足用户需求的互联网资源，使用得越来越广泛。然而，单一的Web服务可实现的功能有限，有时网络上的单个服务不能满足用户提出的复杂需求。Web服务组合根据需要选择多个功能不同的Web服务并进行组合，可以实现用户更加复杂的需求。例如，网络上已存在将中文翻译为英语的服务1与将英语翻译为德语的服务2，如果我们想将中文翻译成德语，但没有单个服务可实现此功能，可以将1的输出结果作为2的输入，完成从中文翻译为德语的过程。

随着Web服务的日益成熟，网络上提供的功能相同的服务日益增多。如何从海量服务中搜索合适的服务并得到满足特定输入与输出的组合是当前急需解决的问题。服务组合方案应在满足功能性需求，即保证目标输出的前提下，选择Web服务质量QoS更优的服务。

Web服务组合问题作为计算机应用的一个研究热点，吸引了众多学者对其展开研究，并提出了一些算法。例如skyline算法[1，2]，规划图算法[3，4]。skyline算法可以使用更少的存储空间和更快的速度解决大的组合问题，规划图算法是Web服务自动组合的方法。

然而，在使用Web Service Challenge（WSC）的文献[6，7，8]中，几乎所有的算法都不能避免组合中出现冗余服务。为了解决这个问题并作为研究[5，9]的继续，本文提出了一种结合去冗余过程的Web服务组合方法CRR。该方法分为两个阶段：向前扩展阶段、向后搜索阶段。向前扩展阶段对服务存储库进行搜索，找出满足用户需求的候选服务；向后搜索阶段以用户请求的目标输出为起点进行逆向搜索，同时删除冗余服务，得到无冗余的Web服务组合方法。

1 背景知识

1.1 QoS标准

Web服务组合可以实现单一服务无法满足的复杂功能。在能够实现功能性需求的前提下，优先考虑非功能属性QoS，可以选择QoS更优的Web服务组合。

服务质量QoS是一个综合指标，用来体现服务能力，如响应时间、吞吐量、花费、可信度等。QoS属性可以分为两类：积极的属性和消极的属性。对于积极的属性，QoS值越高，代表服务的质量越好（如吞吐量和可信度）。而消极的属性，QoS值越低，代表服务质量越好（如响应时间与花费）。

Web服务可以按照顺序的方式连接，也可以按照流的方式连接。顺序连接的Web服务形式如（1;2;…;），按流连接的Web服务形式表示为（1||2||…||）。常用的Web服务质量的属性与其计算方式如下：

响应时间（）：收到查询消息与回复响应消息的时间间隔（单位：毫秒）。

吞吐量（）：单位时间内经由通信通道成功传递信息的数量。（单位：请求/分钟）

花费（）：用户为使用Web服务资源所付出的代价（单位：元）。

关于QoS更多分类可以参考文献[10]。

1.2 规划图方法

规划图是一种有向分层图，表示为文字和操作符交替的序列：（0;1;1;2;2;3;3; …;A;P; …;A;P）。在规划图中，层包含服务的参数，层包含可被唤醒的服务。初始参数层0表示规划问题的初始状态，A层的每个节点都有P层的输入弧与P层的输出弧，即P层的参数可以满足A层的输入，A层的输出被加到P层。层中的多个操作意味着它们可能被并行执行。

规划图方法包含两个阶段：向前扩展和向后搜索。

向前扩展阶段从初始状态构建规划图。首先，根据用户输入，构建初始参数层0层；然后执行循环：遍历Web服务存储库，对于存储库中的每一个服务，如果规划图中没有，且参数层P含当前服务所有输入参数，则服务可被唤醒。将加入A层，将的输出参数加入P层。重复循环的过程，当服务存储库遍历结束，且规划图的服务层A中不再添加任何服务，整个过程结束。如果规划图的参数层P存在要找的目标，就可以找到解决方案。

向后搜索阶段，是从最后一层到第一层的反向搜索循环，根据要找的目标，向前搜索路径，检索解决方案。执行循环：当P层存在用户要找的目标，在A层中寻找一组输出参数满足目标的服务，这一组服务的输入参数又是前一层P的目标。直到达到初始参数层，循环结束，得到一组从初始状态到目标状态的服务组合路径（w，w，…，w）。

2 去冗余过程

大部分Web服务有多个输入参数和输出参数。规划图方法得到的服务组合结果中，并不是每一个服务都必须用到。

冗余服务是在规划图的前向阶段被加进候选组合的大量后续用不到或产生与已有服务相同效果的Web服务。

冗余的Web服务会增加不必要的副作用。如果在组合中包含了冗余的Web服务，将导致组合的QoS变得更差，如响应时间变长、吞吐量减少，并且系统的总体执行时间和花费将会增大。

从用户的角度考虑冗余的Web服务组合，如果有两个付款的服务同时包含在Web服务组合中，就有可能为同一个订单付款两次。因此，我们需要找到无冗余的解决方案来避免这些问题。

图1为一个Web服务组合的实例。在这个组合中，3服务只有一个输出，而3的前一层，服务1已经输出参数。移除服务3后，服务组合依旧能够得到结果。所以，3是冗余服务。去除冗余服务后的结果如图2所示。

图1 服务组合

图2 冗余的服务组合

重复的输出造成了冗余。而在传统规划图的过程中，无法判别冗余服务的产生。将冗余服务移除，往往可以保持组合移除后的功能目标与QoS值不变，甚至QoS数值更优，得到性能更好的组合结果。

本文提出的去冗余方法为：在向后搜索的同时删除冗余服务。向后搜索过程中的每一层搜索结束后，向前遍历一遍，将遍历过程中的所有非冗余服务的输出参数放进集合。若集合包含前面层某服务的全部输出，则这个服务是冗余服务。该方法可将规划图前面层对组合结果无用的Web服务删除。具体过程见3.2的算法。

3 组合过程、算法与实例

3.1 组合过程

本文所提方法的流程如图3所示。

图3 总体流程图

用户发送请求到服务存储库，通过改进的规划图方法，得到服务组合结果。

实验所用的服务存储库由WSC数据集解析得到。该数据集包含WSDL文件、OWL文件、WSLA文件。WSDL文件用于描述 Web服务的名称、输入、输出、如何进行访问等，OWL文件用来描述服务本体论的结构关系，WSLA文件描述服务的QoS属性值。

改进规划图方法分为两个阶段：第一阶段在服务存储库中寻找满足用户需求的候选Web服务组合，向前扩展构成规划图；第二阶段以用户请求为起点，向后搜索的同时删除冗余服务。向后搜索阶段结束后，得到满足目标输出的无冗余服务组合结果。

3.2 算法

整个过程的算法分为向前扩展阶段和向后搜索阶段。

向前扩展阶段以服务存储集、初始输入、目标参数作为输入、输出规划图向前扩展的结果。该算法以初始输入为起点参数集，对服务存储库进行层次划分，过滤输入参数无法唤醒的服务。如果存储库中服务的所有输入参数被当前参数集包含，表示该服务能被唤醒，将该服务加入规划图，并添加服务的输出到参数集。服务存储库遍历结束，规划图当前层添加完毕。再次对服务存储库进行层次划分，将当前参数集能够唤醒的服务加入规划图下一层。直到不再加进新服务，获得前向规划图。如果前向规划图中有目标请求，继续执行向后搜索阶段。

向后搜索阶段以用户请求的输出参数为起点进行逆向搜索，同时删除冗余服务，得到无冗余服务的Web服务组合方法。该算法以前向规划图、初始输入、目标参数作为输入，输出为当前层得到的路径结果。以用户请求，即最后一层的输出目标为起点反向遍历，如果规划图下一层的服务输出与目标参数相同，将这个服务加入集合，使用RemoveRedundant（）方法删除路径结果中的冗余服务，并将加入路径结果。此时起点目标参数更新为未能满足的目标和新加入服务的输入。规划图的每一层均循环上述过程，当目标中所有目标都可由用户请求满足时，循环结束，最后一层的为无冗余的Web服务组合路径结果。

算法 RemoveRedundant（）

输入：cover，initial，solution

输出：redundant

2. for each srv in cover do

4. end for

5. for each level in solution do

6. for each srv in level do

7. if outset contains all srvout

9. delete redundant

10. else

12. end for

13. end for

在向后搜索阶段，规划图路径每新加入一层，都执行一遍去冗余算法。该算法以向后阶段准备加入下一层的服务集合、初始输入、向后搜索阶段中已得到的路径作为输入，最终效果为删除冗余服务。结果集合中存储初始输入参数中每个服务的输出参数和每层已判定为非冗余服务的输出参数。

将初始输入与集合的输出参数加入集合，将中每一个的服务的输出与集比较，若中存在此服务全部的输出，则该服务为冗余服务，将其删除；若没有存在此服务全部的输出，则该服务为非冗余服务，将它的输出也加入集合。

3.3 实例

在本节中，我们通过一个具体的例子来解释所提出的算法。在本例中，服务的信息表如表1所示，其中包括输入、输出的概念、响应时间、吞吐量。假设用户给定输入，与目标输出，求一组Web服务组合。

表1 Web服务信息表

3.3.1 Graphplan方法向前扩展

在向前扩展阶段，规划图方法以层的参数作为输入，从服务集合中选择满足功能性需求的服务，加入层，并将层的输出加入层，直到不再加入新的服务。如图4所示。

图4 规划图

3.3.2向后搜索并去冗余阶段

此阶段以用户请求为起点向后扩展，过程如下。

最后一层3中的目标结果可由服务4输出，于是规划图路径为{4}，结果集合记录为初始输入与4的输出{，}。

4需要的输入为和，在2层，由2输出，由3输出，规划图路径下一层将加入{2，3}，结果集合记录为初始输入与2、3的输出{，，}，此时路径中4的输出不存在于结果集合，因此当前没有冗余服务，结果集合为{，，}。此时规划图路径为{（2||3）;4}。

2与3需要的输入为，在1层，由1输出，规划图将加入{1}，此时结果集合为{，，}，遍历规划图路径中的服务：

2的输出不包含于结果集合，因此2不是冗余服务，将其输出加入结果集合，结果集合更新为{，，，}；3的输出包含于结果集合，因此3是冗余服务，将其删除；4的输出不存在于结果集合，不是冗余服务，将其输出加入结果集合，结果集合为{，，}。此时1的输入可由初始输入满足，向后搜索过程结束。

最终得到的服务组合路径为（1;2;4）。响应时间R和吞吐量T分别为：

R=R（1）+R（2）+R（4）=700

T=min（T（1），T（2），T（4））=1000

如果没有进行去冗余阶段，服务组合为{1;（2||3）;4}，得到的QoS结果为：

R=R（1）+R（3）+R（4）=800

T=min（T（1），min（T（2），T（3）），T（4））=1000

显然无冗余的组合方法QoS更优。

4 实验

4.1 数据源

我们使用了五个数据集[11]进行实验，每个数据集都有OWL文件、WSDL文件、WLSA文件，分别描述服务、本体、QoS。WLSA文件提供了每个服务响应时间和吞吐量的值。数据集均有500-15000个服务，5000-100000个参数概念。

4.2 实验环境

实验环境为：（1）CPU：Intel（R） Core（TM） i3-4170 CPU @ 3.70GHz 3.70GHz；（2）RAM：8.00GB；（3）操作系统：Windows 7旗舰版 Service Pack1。算法用Java实现。

4.3 实验结果

为了说明算法的有效性，将CRR方法的结果与改进前的规划图方法进行比较。如表2所示。

从实验结果可以看出，去冗余方法有显著效果，去除了大量冗余服务。与未改进的规划图方法相比，CRR组合结果的服务数量明显减少，且删除冗余服务后，组合的响应时间更短，从而有更好的QoS。

综上，无冗余的Web服务组合方法不仅可以完成的功能属性，实现目标输出，还可以优化组合的非功能属性。实验表明，此方法可以有效地删除冗余服务，特别是对于海量数据而言，可以大大减少组合结果的服务数量、优化QoS结果。

表2 实验结果

5 结语

本文提出了一种Web服务组合去冗余方法CRR，该方法可有效删除组合结果中的冗余服务。对服务存储库进行搜索，找出满足用户需求的候选服务；之后，以用户请求的输出参数为起点进行逆向搜索，同时删除冗余服务，得到无冗余的Web服务组合方法。使用数据集进行实验分析与验证，结果表明，与规划图方法比较，去冗余方法可以有效删除大量冗余服务，得QoS更好的组合结果。

去冗余方法可以结合其他服务组合方法，优化其他方法获得的解。用其他方法，如skyline算法筛选Web服务存储库后，在最后一步进行去冗余操作，剔除对组合结果无用的服务，得到更好的解决方案。

[1]J.Li，Y.Yan，D.Lemire.Scaling up web service composition with the skyline operator[C]//IEEE InternationalConference on Web Services，USA，ICWS，2016：147-154.

[2]杨莉，张文生，许国艳.基于Skyline服务的Top-k选择方法[J].计算机应用与软件，2016，33（11）：253-257.

[3]戴雪梅，姜浩.基于带权图规划算法的语义Web服务组合[J].计算机技术与发展，2010，20（03）：67-70+75.

[4]邹子靖.基于图规划的启发式Web服务组合算法研究[D].哈尔滨工程大学，2016.

[5]范国栋，祝铭，等.基于FAHP与规划图融合的Web服务组合方法[J].计算机科学，2020，47（01）：270-275.

[6]G.Fan，M.Zhu，X.Cui.（2019）.Optimizing Web Service Composition with Graphplan and Fuzzy Control.Journal of Ubiquitous Systems and Pervasive Networks. 11. 15-21.10.5383/JUSPN.11.02.003.

[7]T.Yu，K.J.Lin. Service selection algorithms for Web services with end-to-end QoS constraints. Seventh IEEE International Conference on E-Commerce Technology （CEC'05），San Diego，California，2004 pp.129-136.

[8]L.Zeng，B.Benatallah，A.H.H.Ngu，et al. QoS-Aware Middleware for Web Services Composition[J]. IEEE Transactions on Software Engineering，2004，30（5）：311-327.

[9]M.Zhu，X.Cui，G.Fan.（2019）.Modeling and Verification of Response Time of QoS-aware Web Service Composition by Timed CSP.Journal of Ubiquitous Systems and Pervasive Networks.11.01-09.10.5383/JUSPN.11.01.001.

[10]S.Ran.A Model for Web Service Discovery with QoS[J].AcmSigecom Exchanges，2003.

[11]WS-Challenge.Testsetgenerator2009[OL].https://code.google.com/p/wsc-pku-tcs/downloads/list.