An approach for QoS-aware service composition based on genetic algorithms

ABSTRACT

Web services are rapidly changing the landscape of software engineering. One of the most interesting challenges introduced by web services is represented by Quality Of Service (QoS)--aware composition and late--binding. This allows to bind, at run--time, a service--oriented system with a set of services that, among those providing the required features, meet some non--functional constraints, and optimize criteria such as the overall cost or response time. In other words, QoS--aware composition can be modeled as an optimization problem.We propose to adopt Genetic Algorithms to this aim. Genetic Algorithms, while being slower than integer programming, represent a more scalable choice, and are more suitable to handle generic QoS attributes. The paper describes our approach and its applicability, advantages and weaknesses, discussing results of some numerical simulations.

References

1. R. Aggarwal, K. Verma, J. Miller, and W. Milnor. Constraint driven web service composition in METEOR-S. In Proc. IEEE International Conference on Services Computing (SCC'04), pages 23--30, Shanghai, China, Sept. 2004.
2. T. Andrews, F. Curbera, H. Dholakia, Y. Goland, J. Klein, F. Leymann, K. Liu, D. Roller, S. T. D. Smith, I. Trickovic, and S. Weerawarana. Business process execution language for web services. http://www-106.ibm.com/developerworks/webservices/library/ws-bpel/.
3. J. Cardoso. Quality of Service and Semantic Composition of Workflows. PhD thesis, Univ. of Georgia, 2002.
4. J. Cardoso, A. Sheth, J. Miller, J. Arnold, and K. Kochut. Quality of service for workflows and web service processes. Web Semantics: Science, Services and Agents on the World Wide Web, 1(3):281--308, April 2004.
5. F. Casati and M. Shan. Dynamic and adaptive composition of e-services. Information Systems, 26(3):143--162, May 2001.
6. C. A. Coello Coello. Theoretical and numerical constraint-handling tehniques used with evolutionary algorithms: A survey of the state of the art. Computer Methods in Applied Mechanics and Engineering, 191(11-12), January 2002.
7. B. Craenen, A. Eiben, and J. van Hemert. Comparing evolutionary algorithms on binary constraint satisfaction problems. IEEE Transactions on Evolutionary Computation, 7(5):281--308, October 2003.
8. H. Fang. Genetic Algorithms in Timetabling and Scheduling. PhD thesis, Univ. of Edimburg, 1994.
9. I. Grossmann. Review of nonlinear mixed-integer and disjunctive programming techniques. Optimization and Engineering, 3(3):227--252, September 2002.
10. T. Helm, S. Painter, and W. Oakes. A comparison of three optimization methods for scheduling maintenance of high cost, long-lived capital assets. In Proc. of the 2002 Winter Simulation Conference (WSC'02), pages 1880--1884, San Diego, California, Dec. 2002.
11. ISO. UNI EN ISO 8402 (Part of the ISO 9000 2002): Quality Vocabulary.
12. ITU. Recommendation E.800 Quality of service and dependability vocabulary.
13. E. R. U.Greiner. Quality-oriented handling of exceptions in web-service-based cooperative processes. In Proc. EAI-Workshop 2004 - Enterprise Application Integration, pages 11--18. GITO-Verlag, 2004.
14. J. Voas, A. Ghosh, G. McGraw, and K. Miller. Glueing together software components: How good is your glue? In Proceedings of the Pacific Northwest Software Quality Conference, pages 90--97, Oct 1996.
15. W3C Working Group. Web Service Choreography Interface. http://www.w3.org/TR/wsci/.
16. W3C Working Group. Web services architecture. http://www.w3.org/.
17. L. Zeng, B. Benatallah, A. H. H. Ngu, M. Dumas, J. Kalagnanam, and H. Chang. QoS-aware middleware for web services composition. IEEE Transactions on Software Engineering, 30(5), May 2004.

Index Terms

• Software and its engineering