An Optimal and Complete Algorithm for Automatic Web Service Composition
- 1 April 2012
- journal article
- Published by IGI Global in International Journal of Web Services Research
- Vol. 9 (2), 1-20
- https://doi.org/10.4018/jwsr.2012040101
Abstract
The ability of web services to build and integrate loosely-coupled systems has attracted a great deal of attention from researchers in the field of the automatic web service composition. The combination of different web services to build complex systems can be carried out using different control structures to coordinate the execution flow and, therefore, finding the optimal combination of web services represents a non-trivial search effort. Furthermore, the time restrictions together with the growing number of available services complicate further the composition problem. In this paper the authors present an optimal and complete algorithm which finds all valid compositions from the point of view of the semantic input-output message structure matching. Given a request, a service dependency graph which represents a suboptimal solution is dynamically generated. Then, the solution is improved using a backward heuristic search based on the A* algorithm which finds all the possible solutions with different number of services and runpath. Moreover, in order to improve the scalability of our approach, a set of dynamic optimization techniques have been included. The proposal has been validated using eight different repositories from the Web Service Challenge 2008, obtaining all optimal solutions with minimal overhead.Keywords
This publication has 27 references indexed in Scilit:
- Using Markov Decision Process Model with Logic Scoring of Preference Model to Optimize HTN Web Services CompositionInternational Journal of Web Services Research, 2011
- Composition of web services through genetic programmingEvolutionary Intelligence, 2010
- Web Services Compositions Modelling and Choreographies AnalysisInternational Journal of Web Services Research, 2010
- WSBenInternational Journal of Web Services Research, 2009
- Web Service Planner (WSPR)International Journal of Web Services Research, 2007
- Search Strategies for Automatic Web Service CompositionInternational Journal of Web Services Research, 2006
- AND/OR Graph and Search Algorithm for Discovering Composite Web ServicesInternational Journal of Web Services Research, 2005
- HTN planning for Web Service composition using SHOP2Journal of Web Semantics, 2004
- Planning and Monitoring Web Service CompositionLecture Notes in Computer Science, 2004
- IntroductionCommunications of the ACM, 2003