Since the birth of web service composition, minimizing the number of web services of the resulting composition while satisfying the user request has been a significant perspective of research. With the increase of the number of services released across the Internet, seeking efficient algorithms for this research is an urgent need. In this paper we present an efficient mechanism to solve the problem of web service composition. For the given request, a service dependency graph is firstly generated with the relevant services picked from an external repository. Then, each search step on the graph is transformed into a dynamic knapsack problem by mapping services to items whose volume and cost is changeable, after which a knapsack-variant algorithm is applied to solve each problem after transformation. Once the last search step is completed, the minimal composition that satisfies the request can be obtained. Experiments on eight public datasets proposed for the Web Service Challenge 2008 shows that the proposed mechanism outperforms the state-of-the-art ones by generating solutions containing the same or smaller number of services with much higher efficiency.
A heuristic A* search algorithm is proposed in @cite_6 for the problem of automatic web service composition. For a given request, a digraph called service dependency graph is constructed firstly with a part of the original services chosen from an external repository. Meanwhile, some techniques are applied to reduce the useless nodes in the graph. Then the heuristic-based search algorithm named A* is executed over the optimized graph to seek the minimal composition which fulfills the user request. Though it can obtain compositions with minimal number of services on WSC-2008's datasets, it may show a poor performance in large-scale and real-time environments. On one hand, different kinds of optimizations on the service dependency graph may spend large quantities of time. On the other hand, quite a few iterations of A* search algorithm aren't applicable to real-time scenarios.
@cite_6
2130281899
Service Oriented Architectures and web service technology are becoming popular in recent years. As more web services can be used over the Internet, the need to find efficient algorithms for web services composition that can deal with large amounts of services becomes important. These algorithms must deal with different issues like performance, semantics or user restrictions. In this paper we present an A* algorithm which solves the problem of semantic input-output message structure matching for web service composition. Given are quest, a service dependency graph with a subset of the original services from an external repository is dynamically generated. Then, the A*search algorithm is used to find a minimal composition that satisfies the user request. Moreover, in order to improve the performance, a set of dynamic optimization techniques has been implemented over the search process. A full experimental validation with eight different public repositories has been done showing a good performance as in all tests as the algorithm finds a valid solution with minimal number of services and execution path.