Local Consistency Reinforcement for Enhancing Web Service Composition
Keywords:Arc-consistency, constraint problems, NP-complete, web service composition, ontology web language for web services
Composing Web services to fulfill a user query remains one of the most challenging research problems due to its importance to the world economy. Several composition techniques have been proposed, but these techniques are becoming more and more expensive due to the tremendous growth of data over the internet, the intensive use of services, and the continuous changes of available services. The workflow-based Web service composition problem is an NP-complete problem, due mainly to the property of the workflow structuring the composition and the diversity of underlying constraints. Reinforcing local consistency is one of the well-known pre-processing techniques to reduce the complexity of most NP-complete problems. These techniques are mainly dedicated to binary constraint satisfaction problems. Therefore, only few researchers devoted their efforts toward reinforcing some level of local consistency on Web service composition problems that can be semantically defined in the Ontology Web Language for Web Services (OWL-S) control structure based constraints. The main goal of this paper is to propose a novel approach for reinforcing a reasonable level of local consistency, node and arc-consistency on any Web service composition problems. It is expected to provide a more up-to-date and realistic representation of any Web service composition problems without any user interactions, but with the ability to cope with any types of user’s query, such as incomplete, ambiguous, and others. This is due to the existence of several novel rules for reinforcing node and arc-consistency on all types of control structure constraints. Experiments were performed on random problems of different levels of complexity to evaluate the performance of the proposed approach.
B. Medjahed and A. Bouguettaya, Describing and Organizing Semantic Web Services, pp. 73–99. New York, NY: Springer New York, 2011.
Y. Hammal, K. S. Mansour, A. Abdelli, and L. Mokdad, “Formal techniques for consistency checking of orchestrations of semantic web services,” Journal of Computational Science, vol. 44, pp. 1–17, 2020.
D. Martin, M. Burstein, J. Hobbs, O. Lassila, D. McDermott, S. McIlraith, S. Narayanan, M. Paolucci, B. Parsia, T. Payne, et al., “Owl-s: Semantic markup for web services,” W3C member submission, vol. 22, no. 4, 2004.
C.-H. Liu, S.-L. Chen, J. Y. Kuo, and T.-Y. Huang, “A flow graph-based test model for owl-s web services,” in 2011 International Conference on Machine Learning and Cybernetics, vol. 2, pp. 897–902, IEEE, 2011.
A. B. Hassine, S. Matsubara, and T. Ishida, “A constraint-based approach to horizontal web service composition,” in International semantic Web conference, pp. 130–143, Springer, 2006.
L. Thomas and A. Immanuel, “Web service composition: A survey on the various methods used for web service composition.,” International Journal of Advanced Research in Computer Science, vol. 8, no. 3, pp. 665 – 670, 2017.
P. Guluru and R. Niyogi, “New approaches for service composition based on graph models,” in 2014 Seventh International Conference on Contemporary Computing (IC3), pp. 507–512, IEEE, 2014.
F. Slaimi, S. Sellami, O. Boucelma, and A. B. Hassine, “A multigraph approach for web services recommendation,” in On the Move to Meaningful Internet Systems: OTM 2016 Conferences, (Cham), pp. 282–299, Springer International Publishing, 2016.
F. Dahan, H. Mathkour, and M. Arafah, “Two-step artificial bee colony algorithm enhancement for qos-aware web service selection problem,” IEEE Access, vol. 7, pp. 21787–21794, 2019.
F. Dahan, “An effective multi-agent ant colony optimization algorithm for qos-aware cloud service composition,” IEEE Access, vol. 9, pp. 17196–17207, 2021.
U. Arul and S. Prakash, “Toward automatic web service composition based on multilevel workflow orchestration and semantic web service discovery,” International Journal of Business Information Systems, vol. 34, no. 1, pp. 128–156, 2020.
A. Abid, M. Rouached, and N. Messai, “Semantic web service composition using semantic similarity measures and formal concept analysis,” Multimedia Tools and Applications, vol. 79, no. 9, pp. 6569–6597, 2020.
K. Ghedira, Constraint satisfaction problems: csp formalisms and techniques. John Wiley & Sons, 2013.
M. Mouhoub, “Dynamic arc consistency for csps,” International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 13, no. 2, pp. 45–58, 2009.
S. Kong, S. Li, and M. Sioutis, “Exploring directional path-consistency for solving constraint networks,” The Computer Journal, vol. 61, no. 9, pp. 1338–1350, 2018.
A. Idrissi and A. B. Hassine, “Circuit consistencies,” in PRICAI 2004: Trends in Artificial Intelligence (C. Zhang, H. W. Guesgen, and W.-K. Yeap, eds.), (Berlin, Heidelberg), pp. 124–133, Springer Berlin Heidelberg, 2004.
H. Fekih, S. Mtibaa, and S. Bouamama, “Local-consistency web services composition approach based on harmony search,” Procedia computer science, vol. 112, pp. 1102–1111, 2017.
A. Bramantoro, A. B. Hassine, S. Matsubara, and T. Ishida, “Multilevel analysis for agent-based service composition.,” J. Web Eng., vol. 14, no. 1&2, pp. 63–79, 2015.
V. Gabrel, M. Manouvrier, and C. Murat, “Web services composition: complexity and models,” Discrete Applied Mathematics, vol. 196, pp. 100–114, 2015.
M. Paolucci, T. Kawamura, T. R. Payne, and K. Sycara, “Semantic matching of web services capabilities,” in International semantic web conference, pp. 333–347, Springer, 2002.
P. Philipp, M. Maleshkova, A. Rettinger, and D. Katic, “A semantic framework for sequential decision making for journal of web engineering,” Journal of Web Engineering, vol. 16, no. 5&6, pp. 471–504, 2017.
M. Abdel-Salam, W. Bahgat, E. Mohamed Eldaydamony, and A. Atwan, “A novel framework for web service composition,” International Journal of Simulation: Systems, Science and Technology, vol. 20, p. 1, 07 2019.