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

Study of Algorithms for Dynamic Service Composition and Optimal Service Composed

作　　者：韩永国[1] 孙世新[1] 

机构地区：[1]电子科技大学计算机科学与工程学院

出　　处：《计算机科学》2005年第12期104-105,239,共3页Computer Science

基　　金：国家高技术研究发展863计划项目(2003AA116060);四川省教育厅项目(2003A124)

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

关 键 词：服务组合 WEB服务 最优组合服务算法 有向无环图 费用转移 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论] F830.59[自动化与计算机技术—计算机科学与技术]