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

References

[1] PrakashJ., RajaV.. Evaluating Web service composition methods with the help of a business application [J]. International Journal of Engineering Science and Technology, 2010, 2(7): 2931-2935

[2] MaamarZ., ShengZ., BenatallahB.. Towards a conversation-driven composition of Web services [J]. Web Intelligence and Agent Systems, 2004, 2(2): 145-150

[3] MilanovicN., MalekM.. Current solutions for Web service composition [J]. IEEE Internet Computing, 2004, 8(6): 51-59

[4] ArdagnaD., PerniciB.. Adaptive service composition in flexible processes [J]. IEEE Transaction on Software Engineering, 2007, 33(6): 369-384

[5] MedjahedB., BouguettayaA.. A multilevel composability model for semantic Web services [J]. IEEE Transaction on Knowledge and Data Engineering, 2005, 17(7): 954-968

[6] LinsF., JuniorJ., RosaN.. Adaptive web service composition [J]. ACM Sigsoft Software Engineering Notes, 2007, 32(4): 6-14

[7] YuQ., LiuX.-m., BouguettayaA., MedjahedB.. Deploying and managing Web services: Issues, solutions, and directions [J]. The International Journal on Very Large Data Bases, 2008, 17(3): 537-572

[8] BerardiD., CalvaneseD., GiuseppeG. D.. Automatic composition of e-Services [C]. Proceedings of the First International Conference on Service-Oriented Computing, 2003, Trento, Springer: 43-58

[9] TaejongY., BuhwanJ., HyunboC.. A Petri Nets based functional validation for services composition [J]. Expert Systems with Applications: An International Journal, 2010, 37(5): 3768-3776

[10] DingZ.-j., WangJ.-l., JiangC.-jun.. An approach for synthesis Petri Nets for modeling and verifying composite Web service [J]. Journal Information Science and Engineering, 2008, 24(5): 1309-1328

[11] ThakkarS., KnoblockC. A., AmbiteJ. L., ShahabiC.. Dynamically composing Web services from on-line sources [C]. Proceedings of the AAAI-02 Workshop on Intelligent Service Integration, 2002, Edmonton, Alberta, Canada, AAAI Press: 18-25

[12] OhS. C., OnB. W., LarsonE. J., LeeD.. BF*: Web services discovery and composition as graph search problem [C]. Proceedings of the 2005 IEEE International Conference on e-Technology, e-Commerce and e-Service, 2005, Hong Kong, China, IEEE Computer Society: 784-786

[13] LiM., WandD.-z., DuX.-y., WangShan.. Dynamic composition of Web services based on domain ontology [J]. Chinese Journal of Computers, 2005, 28(4): 644-650

[14] HouL.-s., JinZ., WuB.-dan.. Modeling and verifying Web services driven by requirements: An ontology based approach [J]. Science in China (Series E), 2006, 36(10): 1189-1219

[15] BenatallahB., HacidM., LegerA.. On automating Web services discovery [J]. The International Journal on Very Large Data Bases, 2005, 14(1): 84-96

[16] PaolucciM., KawmuraT., PayneT., SycaraK.. Semantic matching of Web service capabilities [C]. Proceedings of the International Semantic Web Conference, 2002, Sardinia, Italia, Springer Verlag: 333-347

[17] EiterT., GottlobG.. Identifying the minimal transversals of a hypergraph and related problems [J]. SIAM Journal on Computing, 1995, 24(6): 1278-1304

[18] BergeC.Hypergraphs: Combinatorics of finite sets [M], 1989, Amsterdam, North-Holland Elsevier Publication: 1-268