Automatic Web services composition algorithm based on optimal matching

Abstract

A novel layered method was proposed to solve the problem of Web services composition. In this method, services composition problem was formally transformed into the optimal matching problem of every layer, then optimal matching problem was modeled based on the hypergraph theory, and solved by computing the minimal transversals of the hypergraph. Meanwhile, two optimization algorithms were designed to discard some useless states at the intermediary steps of the composition algorithm. The effectiveness of the composition method was tested by a set of experiments, in addition, an example regarding the travel services composition was also given. The experimental results show that this method not only can automatically generate composition tree whose leaf nodes correspond to services composition solutions, but also has better performance on execution time and solution quality by adopting two proposed optimization algorithms.

Keywords

Web services / services composition / optimal matching / hypergraph theory