基于改进蚁群算法的服务组合研究

摘要：在服务计算过程中，服务组合问题是其中关键的技术之一。在原子候选服务数目巨大的情况下，经典的算法一般都是寻找问题的最优解，存在运算量大，运行时间长的缺点，蚁群算法并不是寻找服务组合问题的最优解，而是得到用户能够认同的可行解。为了能够更有效的为用户提供各种服务，在静态的服务组合建立过程中，以服务发现的候选原子服务集合中的服务质量为权重，将服务组合问题分解成一个有向无环图，在组合代价为最小的原则下，采用改进的蚁群算法为搜索方法，迭代一定的次数或者达到用户设定的服务质量为算法的终止条件，找到能够组合为用户需要的原子候选服务集合，进而快速、准确的得到用户期望的服务。

关键词：服务计算；服务组合；蚁群算法；服务质量；组合代价

Service Composition Based on Improved Ant Colony Algorithm

Niu Yong Jie 1, Zhang Cheng 2

(1. Computing Center, Yan’an University;

2. Network Center, Yan’an University; Yan’an, 716000)

Abstract: In service computing, service composition problem is one of the key technologies. Large number of candidate services in the atomic case, the classical algorithms are generally looking for the optimal solution, there is large amount of computation, the shortcomings of a long running time, ant colony optimization services portfolio problem is not finding the optimal solution, but the user can identify a feasible solution. In order to more effectively provide various services for users, a static portfolio of services in the building process, to serve a collection of atomic services discovered in the candidate quality of service for weight, the service composition problem into a directed acyclic graph, in combination of the principle of minimum costs, an improved ant colony algorithm for the search method, the number of iterations or a certain quality of service to the user to set the termination conditions for the algorithm to find that combination of candidates for service users need a collection of atoms, then fast and accurate service to the user expectations.

Keywords: service computing; service component; ant colony optimization; quality of services; component costs

1研究背景及现状

目前，万维网信息的来源主要是静态数据的提供者，这些提供者逐渐形成了很多个信息的“孤岛”。在很多应用领域，要求很多的Web服务联合起来以提供更加完整、全面的信息，服务计算就应运而生。面向服务的计算（SOC，Service-orientedcomputing）技术又称服务计算（Service Computing），已成为软件领域最热门的话题之一，是标识分布式系统和软件集成等方向技术进步的一个新的里程碑。作为一种新型的计算模式，SOC把服务作为基本的组件，用来支持快速、低成本和简单的分布式，甚至异构环境的应用组合[1]；在服务计算中，服务描述、服务发现、服务组合是其中关键的几个问题。

关于服务组合的方法有很多[2-5]，有基于领域本体、基于语义、基于范例、基于服务关系、采用概率及接口连接关系的各种方法。Lassila等人提出一种基于工作流的Web服务发现和组合方法，但只能处理一般的顺序组合问题；付燕宁等提出基于服务链的Web服务组合方法，采用从目标服务出发搜索到源服务的反向链接方法[6]。但这些方法在进行服务组合时，往往只考虑服务组合的精度问题，而忽略了服务组合的代价问题，当进行服务组合的服务数量规模较小时，大部分的方法都能达到良好的效果，但是当服务的数量较大时，这些方法往往存在组合时间太长甚至在客户能够容忍的时间内不能得到组合服务。鉴于上述的问题，本文提出了基于蚁群算法的服务组合方法。

2服务组合

由于服务计算是以服务为最基本的单元，当没有单个服务满足某特定服务请求时，可能找到一组Web服务，它们的组合能够满足该请求。面向服务的方法要构建的是松耦合、可复用的软件系统，其中一个关键问题是如何将单一功能模块组合为功能更为复杂的模块（组合电子服务），从而满足用户需求。

服务组合可以通过把小粒度服务组合成大粒度的、具有业务含义的组合服务，可使客户仅仅关心组合服务的接口和功能而不必知道组合服务的内部组成和结构，有效降低了客户使用系统的复杂性[7]。同时，电子服务的组合能够增加互联网上可用服务的数量。此外，服务组合技术的发展为未来的软件开发模式奠定了可靠基础。服务组合可分为两个阶段：服务组合建立阶段和运行阶段，如图1所示。组合建立阶段依据应用领域和自动化程度，其组合方法分为动态和静态组合两类[8]。静态组合意味着请求者应在组合计划实施前创建一个抽象的过程模型，即流程建模。抽象的过程模型包括任务的集合以及任务间的数据依赖关系，每个任务包含一个查询的子句，用来查找完成任务的真正的Web服务。

图1服务组合实施过程

（1）静态组合指请求者在组合计划实施前创建了一个抽象的过程模型，即流程建模。抽象的过程模型包括任务的集合以及任务间的数据依赖关系，每个任务包含一个查询的子句，用来查找完成任务的Web服务。在静态组合中，被组合的过程具有固定的特性，被组合的服务在设计时由设计者选择。

（2）动态组合指组合过程具有动态的特性，通过一定的算法或按照一定的规则选择所需的原子服务进行组合操作。

在静态服务组合中，经典的方法是将服务发现中寻找到的原子服务作为候选服务集合，按照服务组合需要的流程将这些候选服务分为不同的层，一个组合服务就是从源头经过第一层、第二层，…，到达目的地的过程。然后将每个候选的原子服务提供服务时的服务质量作为权重，寻找源头到目的地之间服务代价最小的路径，于是就把问题转换为求解有向无环图中的最短路径问题，如图2所示，其中Si,j中的i表示服务组合中的层数，j表示该层拥有的候选原子服务个数。解决最短路径的经典算法有Dijkstra算法、Bellman-Ford算法还有很对其他的变形形式，这些方法都是寻找问题的最优解，当候选服务的集合规模比较小时，这些方法有较好的效果，但是当候选服务集合的问题规模比较大时，存在运算量大，运行时间长的问题，通常不能满足用户的要求。在实际情况中，对于一些问题的求解往往不需要求解问题的最优解，而只需要求解问题的可行解或者用户的满意解。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文