Automatic QoS-aware web services composition based on set-cover problem

By definition, web-services composition works on developing merely optimum coordination among a number of available web-services to provide a new composed web-service intended to satisfy some users requirements for which a single web service is not (good) enough. In this article, the formulation of the automatic web-services composition is proposed as several set-cover problems and an approximation algorithm has been exploited to solve them. In proposed method, the web-service composition has been carried out within two main phases, the top-down expansion of the composition tree, and the production of composed service by bottom-up traversal of composition tree. In the first phase, the production of a composition tree (similar to the production of tree in problemsolving by searching) is proposed by starting from the output or post-conditions of the requested service towards its input or pre-conditions. Each node or state of the tree is a set of inputs and/or outputs or conditions, and services as tree edges illustrate the transition from one node to another. In the second phase, finding the path from the leaves of the produced composition tree to the root is considered equal to reaching the output of requested service, and this path specifies the involved services and the composition plan. The requested service input set determines the available leaves of the composition tree. To achieve each non-leaf node of the tree, a set-cover problem is produced and solved using a greedy approximation algorithm. If the production and solving of the set-cover problems continues hierarchically until it reaches the root node, the composition plan and cost of the required composition service will be specified. The main focus of this research is the joint sequential and parallel composition with the aim of producing near-optimal and QoS-aware composed services.

Keywords:

Web Services , Composed Services , Set-cover Problem , Approximation Algorithm