Towards efficiency of QoS-driven semantic web service composition for large-scale service-oriented systems

• Published in: Service oriented computing and applications 2012-03, Vol.6 (1), p.1-13
• Main Authors: Xu, Bin, Luo, Sen, Yan, Yixin, Sun, Kewu
• Format: Article
• Language: English
• Subjects: Computer Appl. in Administrative Data Processing; Computer Science; Computer Systems Organization and Communication Networks; e-Commerce/e-business; IT in Business; Management of Computing and Information Systems; Original Research Paper; Software Engineering/Programming and Operating Systems
• ISSN: 1863-2386; 1863-2394
• DOI: 10.1007/s11761-011-0085-8

Quality-of-Service (QoS) performance guarantee for service-oriented systems (SOS) has become a critical problem. With the increasing number of offered services comes the challenge of efficiently building large-scale SOS to meet the required QoS criteria. Optimization of QoS-driven semantic Web service composition is known to be NP-hard. We address the efficiency issue by developing a polynomial time algorithm (QDA) for shortest sequence composition. We use dynamic programming to find service candidates for each execution. When all the services are searched, we use a depth-first trace back to derive the execution plan. We have tested our approach under Web-scale demands 20,000 services and 150,000 semantic concepts. In comparison with existing approaches, our experimental results show that QDA can be used to solve large-scale service composition problem effectively and efficiently with QoS guarantee.