基于狼群算法的web服务组合优化研究

何健文

摘要：近年来，随着以服务为导向的框架技术的产生和发展，web服务技术已经获得了信息技术社区和商业社会的广泛关注和研究。Web服务是一种跟传统面向对象开发模式所不一样的新型模块化开发模式，具有面向功能的更高抽象粒度。但是，随着web服务数量的逐渐增多，单一功能的Web服务面临着难以满足用户复杂多变的实时需求。在很多场景下必须把单一功能的Web服务整合成具有更复杂功能的复合Web服务。因此，人们提出很多优化算法来解决基于Qos属性的Web服务组合问题。该文针对以上Web服务组合问题，引入一种新型的基于群体智能的优化算法来解决Web服务组合问题。实验结果表明了改进后的狼群算法跟传统的优化算法相比在效率和性能有一定的提高。

关键词：面向功能框架；Web服务组合；QoS属性；狼群算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）01-0070-04

WCA-based Web Service Composition Optimization Research

HE Jian-wen

（School of Software Engineering，Tongji University， Shanghai 201804，China）

Abstract： Thanks to the emergence and widespread of Service-oriented Architecture（SOA），Web service technology has got its attention around the Internet Community. However， single simple web service face the challenge of being unable to satisfy users complex requirements in runtime environment as the amounts of web services become larger and larger. Therefore a lot of optimization solution has been proposed aimed to address the web service composition issue. Whereas most of them are of low efficiency and accuracy. The paper has introduced a new kind of colony intelligent algorithm to address the QoS-based web service composition， which is called Wolf Colony Algorithm. The experimental results show that the WCA outperform in comparison with traditional heuristic algorithm such as particle swarm algorithm.

Key words： SOA； web service composition； QoS property； WCA

Web服务作为一种新型的web应用模式，近年来得到了迅速的发展。如何动态地把现存的各种web服务整合起来以形成新的、满足不同用户需求的、增值的复杂服务已成为新的应用需求和研究热点。为了解决现有服务组合中服务选择技术的不足，已经提出了多种解决服务组合中服务动态选择QoS全局最优化问题的实現算法，例如粒子群算法和遗传算法等。但是这些群体智能优化算法不同程度地都存在着一些不足，如算法后期收敛速度较慢，易陷入局部最优或计算精度不高等问题。因此有必要针对该类问题引入新的优化算法。该文的主要研究工作集中在如何帮助用户获取满足用户特定约束条件的最优化组合服务。

服务组合技术今年获得了广泛的关注和应用，主要用来为企业或个人提供商业业务工作流过程模型。通过使用不同web服务提供商提供的现存的web服务，企业或者个人可以建立基于自身业务需求的商业业务过程。现金商业社区经常用分布式系统的方式来建立web服务。在这种框架中web服务用一种称为WSDL的语言描述，并且用BPEL语言来进行工作流整合。这种方法专注于复合web服务的执行过程，而并不需要太多地考虑驱动开发过程的需求。

在本课题中，我们提出了在动态环境下解决web服务组合问题的新的最优化算法。通过用QoS属性来衡量web服务，我们建立了web服务组合流程模型的数据模型，并且对最优化算法做出了一些改进。在完成了算法的设计和部署后，用对比实验验证算法的性能特点。

1 QoS驱动的web服务组合数据模型

1.1 web服务的QoS模型

实际上，Web服务组合过程可以看成是一种基于Web 服务的工作流模型。在这个工作流模型中，每一个结点都表示为一个抽象的Web服务接口，每一个接口都有相对应的输入和输出。在运行时，每一个抽象的Web服务接口根据服务的Qos值调用具体功能的Web服务。Web服务的Qos模型是指每一个Web服务的Qos值作为在多个相同功能的Web 服务中选择的标准。结果，一系列具体的Web 服务会根据其对应的Qos属性被选中形成一个复合的web 服务。

每一个web服务都有多种的QoS属性，也就是非功能属性。例如，最常见的有价格，响应时间，可靠性和名声等级。一般来说，QoS属性可以分为两种，一种是积极的QoS属性，一种是消极的QoS属性。像响应时间和执行时间等是消极的QoS属性而可用性和名声等级是积极的QoS属性。对于消极的QoS属性来说，值越高，说明质量指数越低，而积极的QoS属性正好相反。在本课题中，我们将用一个四维向量的形式来定义一个web服务的QoS属性，如：[q=[QoS1，QoS2，QoS3，QoS4]]。

一般来说，有四种计算QoS属性值的基本模型。这四种模型分别是串行，并行，条件和循环模型。在这四种模型里，我们假设每个web服务包含以下四种QoS属性：执行时间、执行成本、名声等级和可行性。

1.2 web服务组合的数学模型

根据前面的描述，我们可以总结出Web服务组合优化问题可以简化成一种多目标优化的数学模型。

显然，这是一种多目标优化问题。然后我们可以为多目标Web服务组合问题建立以下模型：

[MAX fr（x）=frj=1n1x1j，j=1n2x2j，...，j=1nix2i]r=1，...，m

St. （1） [xi，j=0 or 1，0≤i

1） [xi，j=0 or 1]限制了每个web服务有且仅有两个状态：选择或者是不选。

2） [i=1NLx1，j=1]可以保证在每个服务集里面只有一个服务会被选择。

为了更清楚地描述所要解决的问题，在这个课题中我们会把执行价格和成本设置为目标变量，也就是说，我们需要把价格和成本降到尽可能低。然后名称等级和可靠性被设置为两个约束变量。[Rcp0]和[Ru]各自表示最低的名称等级和最低的可靠性等级。因此，我们可以把多目标组合优化模型描述为：

MinF（P）=（T（P），C（P））

St. （1）[Rcp（P）≥Rcp0] （2）[R（P）≥R0]

多目标优化的最关键的一个特点是两个不同的QoS属性间的一个共同的矛盾性，在候选服务中需要更少执行时间的会需要支付更高的价格。因此，组合优化的最后目标是输出满足约束条件的最优化方案，而不是单个的Web服务。

2 web服务组合优化的狼群算法

2.1 狼群算法的设计及其实现

跟其他群体智能算法类似，狼群算法的灵感来源于自然界中狼群的捕食行为。我们知道，在狼群社区中，有严格的等级制度，明确的责任分工以及为了高效地捕杀猎物而采取的同步行动。尽管狼是野性的和富有攻击性的，但是在每一个狼群里，都有一个首领狼，在捕食行动中首领狼具有完全的控制权。正是由于狼群的这种组织原则，狼群才能够成功地捕获猎物并且在自然界中生存下去。但是，狼群中的首领狼并不是一成不变的，一些候选狼会定期地竞争狼群中首领狼的角色。这样可以保证狼群的灵活性和社群的多样性。在捕食猎物的过程当中，在发现目标的那一刻，首领狼会通过嚎叫来通知其他狼。在首领狼的控制下，狼群逐渐包围目标猎物。最终，一旦猎物抓到以后，狼群开发对猎物进行分配，按照狼群的规则，强壮的狼会在分配猎物的过程中比弱小的狼分到更多的部分。這样，按照适者生存的规则，强壮的狼在狼群中的数量会逐渐增多，狼群捕获到食物的概率也会增高。在本课题中，狼群算法根据自然界中狼群的该种捕食行为来实现最优结果的搜索。以下为狼群算法的实施步骤。

1） 数据初始化。在初始化步骤里，一些相关的参数被赋初值并且输入数据也会被导入进来。

2） 竞选领导狼。一定数量的候选狼根据特定的规则竞选成为领导狼。

3） 向领导狼靠近。一旦领导狼确定以后，狼群中的其他狼会逐渐向领导狼的位置靠近。

4） 包围猎物。一旦目标被发现以后，领导狼会通过发送信号来通知其他狼包围猎物。

5） 狼群更新。根据优胜劣汰的食物分配原则，在具体的算法实现中，一些弱小的狼会随机性地被一些新的狼代替。

6） 连续性结果的离散化处理。因为在实际应用过程中，web服务组合的最优化方案是离散。但是狼群算法的搜索空间却是连续的。因而根据以上规则搜寻得到的结果会根据特定的规则进行离散化处理。

7） 终止条件判断。当狼群的一次迭代结束以后，下一次迭代会根据终止条件来决定是否继续执行。

2.2 连续域结果的离散化处理

以上实现的狼群算法部分是用来解决连续域的最优化问题。也就是说，狼群位置的变化以及其他变量在连续范围内变化，所涉及的计算规则也是针对连续型变量。但是，在实际应用过程中，许多工程问题里需要离散化处理的。一般来说，有三种主要的离散化策略。

首先，受激发于解决0-1规划问题的二进制算法原理，我们可以通过把位置的改变看成一种概率性事件的方法来对算法结果离散化处理。也就是说，在离散化的狼群算法中，二维空间意味着一个超立方体空间，狼群中每个狼的位置可以表示为一个二进制变量。因此狼群在搜索空间中的移动可以通过这些二进制变量值的翻转来捕获。狼群位置的更新如下：

[xid=1 （if（rand（）

[sig（vid）]是一个特定的控制翻转的约束函数，可以保证狼群位置的每个元素限制为0或1。rand（）是一个介于0和1之间的随机数。

其次，连续域算法的离散化策略也可以通过对运算符的重新定义来实现。这种方法意味着对狼群算法的某新参数操作的重新定义。这种方法具有较高的复杂性。

最后，另外一个可选方案是直接利用连续域狼群算法的结果来转换为离散型结果。根据连续型结果变量和离散型变量的距离，选出和连续型变量最为接近的一个离散型变量作为离散处理后的结果。

由于上述描述的三种方法中，概率处理的方法在很多场景中并不适用，运算符重新定义的方法具有较高复杂性。因此本课题采用直接转换连续型变量的策略来对狼群算法进行离散化处理。具体的实现操作是把离散域中最接近的值赋值给人工狼的位置，剩下的算法操作和原来一样。连续域结果被赋值以后，系统计算解决方案的适应度并根据特定规则决定是否激发下一次迭代。尽管在这种方法的执行过程中，可能会有多个连续型结果变量指向同一个离散型结果变量而且离散化后的结果也有可能会溢出约束的范围。然后计算结果表明，在结果高维优化问题的时候，算法具有较高的稳定性而且不会陷于局部最优。

2.3 狼群算法的適应度计算函数

在本课题的算法实现中，我们用以下的方式计算适应性函数：

其中Agg是第d个QoS属性的计算值，Con是用户定义约束。w是第d个QoS属性的权重。

3 实验分析

根据前文的描述，我们介绍了一些传统优化算法的基本原理并且引入实现了改进后的狼群算法。为了更好地比较和测量狼群算法和其他优化算法的执行效率和性能，相关的对比实验是很有必要的同时也能让本课题的研究内容更加有说服力。在本次实验中我们使用响应时间和系统吞吐量来作为web服务的两个QoS属性，输入数据在本章前面部分已经介绍过。实验数据中QoS属性每个矩阵代表339个用户对于5825个web服务的实时环境使用历史记录。

为了更好地进行性能评估，算法操作中的许多参数已经被提前设定。在以下实验中，基于准确性和有效性的考虑，我们为每个关键参数设置了相关的值。

对于狼群算法来说，参数值设定如下：

WOLF_SIZE=625，maxdh=15，stepa=1.5，stepb=0.9，h=4，cta=0.2，ramax=0.9，ramin=0。

算法的实验环境为：

操作系统：Ubuntu Linux OS

处理器：Intel Core i5

运行时：Java Version 1.7.0 JDK

实验仿真结果如图1所示。

实验结果表明狼群算法具有较高的运算效率并且一定程度上优于粒子群算法。

4 结束语与展望

本文就围绕着Web服务组合中如何获得全局最优的web组合方案展开研究。我们的工作主要集中在建立基于QoS的web服务组合数据模型并且利用狼群算法来解决基于QoS的web服务组合问题。实验结果表明狼群算法具有较高的运算效率并且一定程度上优于粒子群算法。

本文针对Web服务组合优化问题进行研究，在充分掌握了当前的研究存在的问题的基础之上，提出了一些改进的方法，并通过实验验证了这些改进所取得的效果，但是本文在以下方面仍然存在着一些不足。在当前互联网快速发展的环境下，大数据、数据挖掘、机器学习等算法正在得到越来越多的关注。是否可以把数据挖掘，机器学习等算法运用到Web服务的QoS预测或者服务推荐当中，将是我们未来探索的一个方向。

参考文献：

[1] Xianglan H.A Survey on QoS-Aware Dynamic Web Service Selection[C]//Wireless Communications， Networking and Mobile Computing （WiCOM）， 2011 7th International Conference on. 2011. IEEE.

[2] Alrifai M，Risse T.Combining global optimization with local selection for efficient QoS-aware service composition[C].Proceedings of the 18th international conference on World wide web，ACM. 2009.

[3] Wan S.Developing a Selection Model for Interactive Web Services[C].Web Services， 2006. ICWS'06. International Conference on. 2006. IEEE.

[4] Maximilien E M， Singh M P.A framework and ontology for dynamic web services selection[J].Internet Computing， IEEE， 2004，8（5）： 84-93.

[5] Wada H.Multiobjective optimization of SLA-aware service composition[C].Services-Part I，2008.IEEE Congress on. 2008. IEEE.

[6] Yu T，Zhang Y，Lin K-J.Efficient algorithms for Web services selection with end-to-end QoS constraints[J]. ACM Transactions on the Web （TWEB）， 2007，1（1）： 6.

[7] Trelea I C.The particle swarm optimization algorithm： convergence analysis and parameter selection[J]. Information processing letters， 2003，85（6）： 317-325.

[8] Ludwig S A.Applying Particle Swarm Optimization to Quality-of-Service-Driven Web Service Composition[C]. Advanced Information Networking and Applications （AINA）， 2012 IEEE 26th International Conference on. 2012. IEEE.

[9] LIU C.The Wolf Colony Algorithm and Its Application[J]. Chinese Journal of Electronics， 2011，20（2）.