动态服务组合构造与最优组合服务算法研究

Study of Algorithms for Dynamic Service Composition and Optimal Service Composed

服务组合是将已有服务组合为一个新服务的过程,以增加服务的功能或/和性能。本文将组合方案表示为一个有向无环图,节点表示服务,边表示服务交互,以目标服务的输入为指标集,给出候选组合方案的构造算法。以服务费用为测度,并计入服务的计算、存储和通信费用。通过费用转移,提出了基于经典Dijkstra算法的最优组合服务算法。

Service composition is a process of taking existing services and combing them to form new services with high- er performance and/or more functions. Available composition plans are represented as a directed acyclic graph in which a node is a service, and an edge is interaction between services. Based on the graph theory and set theory, an algorithm is proposed for composing service plans by index set of inputs of objective service in this paper. An optimal algorithm is developed for selecting composed service of lowest cost. The algorithm counts the cost of computing and storing and the cost of service interaction/communication. By transferring node cost （computing and storing cost） to edge （interaction/communication cost）, the optimal algorithm gets the foundation of Dijkstra＇s shortest path algorithm, which has a time complexity of O（n^2）. The implementation of the algorithms by typical service composition languages in Web service and grid service is discussed.