Efficient composition of semantic web services with end-to-end QoS optimization
Bin Xu, Sen Luo, Yixin Yan · Tsinghua Science & Technology · 2010
The efficiency of OoS-aware service composition is important since most service composition problems are known to be NP-hard. With the growing number of web services, service composition is like a decision problem on selecting services or/and execution plans to satisfy the users' end-to-end OoS requirements (e.g. response time, throughput). Composite services with the same functionality may have different execution plans, which may cause different end-to-end OoS. This paper presents a model combining semantic data-links and OoS, which leads to an efficient approach to automatic construction of a composite service with optimal end-to-end OoS. The approach is based on a greedy algorithm to select both services and execution plans for composite services. Empirical and theoretical analyses of the approach show that its time complexity is O(mn2) for a repository with n services and an ontology with m concepts. Moreover, the approach increases linearly in time when using an index to search services in the repository. Tests with a repository with 20 000 services and an ontology with 300 000 concepts show that the algorithm significantly outperforms current existing algorithms in terms of composition efficiency while achieving optimal end-to-end qoS.