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

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.