International Journal of Nonlinear Analysis and Applications

Automatic QoS-aware web services composition based on set-cover problem

Document Type : Research Paper

Authors

1 Department of Computer Engineering, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran.

2 Department of Computer Engineering, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran

Abstract

By definition, web-services composition works on developing merely optimum coordination among a number of available web-services to provide a new composed web-service intended to satisfy some users requirements for which a single web service is not (good) enough. In this article, the formulation of the automatic web-services composition is proposed as several set-cover problems and an approximation algorithm has been exploited to solve them. In proposed method, the web-service composition has been carried out within two main phases, the top-down expansion of the composition tree, and the production of composed service by bottom-up traversal of composition tree. In the first phase, the production of a composition tree (similar to the production of tree in problemsolving by searching) is proposed by starting from the output or post-conditions of the requested service towards its input or pre-conditions. Each node or state of the tree is a set of inputs and/or outputs or conditions, and services as tree edges illustrate the transition from one node to another. In the second phase, finding the path from the leaves of the produced composition tree to the root is considered equal to reaching the output of requested service, and this path specifies the involved services and the composition plan. The requested service input set determines the available leaves of the composition tree. To achieve each non-leaf node of the tree, a set-cover problem is produced and solved using a greedy approximation algorithm. If the production and solving of the set-cover problems continues hierarchically until it reaches the root node, the composition plan and cost of the required composition service will be specified. The main focus of this research is the joint sequential and parallel composition with the aim of producing near-optimal and QoS-aware composed services.

Keywords

[1] Web Service Choreography Interface (WSCI) 1.0., Available: https://www.w3.org/TR/wsci/. [Accessed: 13-Apr-2020].
[2] G. Baryannis and D. Plexousakis, “Automated Web Service Composition?: State of the Art and Research Challenges,” ICS-FORTH, Tech. Rep, no. October, 2010.
[3] L.A.F. Leite, G. Ansaldi Oliva, G.M. Nogueira, M.A. Gerosa, F. Kon, and D.S. Milojicic, A systematic literature review of service choreography adaptation, Serv. Oriented Comput. Appl.  7(3) (2013) 199–216.
[4] J. Rao and X. Su, A survey of automated web service composition methods, Proc. First Int. Conf. Semantic Web Services and Web Process Composition, Springer-Verlag, 2005, pp. 43–54.
[5] Y. Chen, J. Huang, and C. Lin, Partial Selection: An Efficient Approach for QoS-Aware Web Service Composition, IEEE International Conference on Web Services, 2014, pp. 1–8.
[6] Q. Wu and F. Ishikawa, Towards Service Skyline for Multi-granularity Service Composition, Proceedings of the 2014 International Workshop on Web Intelligence and Smart Sensing - IWWISS ’14, 2014, pp. 1–6.
[7] M. Suresh Kumar and P. Varalakshmi, A Novel Approach for Dynamic Web Service Composition through Network Analysis with Backtracking, Advances in Computing and Information Technology (2013) 357–365.
[8] S. R. Ponnekanti and A. Fox, SWORD?, A Developer Toolkit for Web Service Composition, Proc. Elev. Int. World Wide Web Conf. 45 (2009) 1–23.
[9] Y. Yao and H. Chen, A Rule-Based Web Service Composition Approach, Sixth International Conference on Autonomic and Autonomous Systems, 2010, pp. 150–155.
[10] L. Huang, X. Zhang, Y. Huang, G. Wang, and R. Wang, A Qos Optimization for Intelligent and Dynamic Web Service Composition Based on Improved PSO Algorithm, Second International Conference on Networking and Distributed Computing, 2011, pp. 214–217.
[11] M. Li, T. Deng, H. Sun, H. Guo, and X. Liu, GOS: A Global Optimal Selection Approach for QoS-Aware Web Services Composition, Fifth IEEE International Symposium on Service Oriented System Engineering, 2010, pp. 7–14.
[12] W. Li and H. Yan-Xiang, A Web Service Composition Algorithm Based on Global QoS Optimizing with MOCACO, Proceedings of the 2011, International Conference on Informatics, Cybernetics, and Computer Engineering (ICCE2011), 2011, pp. 79–86.
[13] H. Rezaie, N. Nemat Baksh, and F. Mardukhi, A Multi-Objective Particle Swarm Optimization for Web Service Composition, NDT 2010: Networked Digital Technologies, 2010, pp. 112–122.
[14] L. Li, P. Cheng, L. Ou, and Z. Zhang, Applying Multi-objective Evolutionary Algorithms to QoS-Aware Web Service Composition, ADMA 2010: Advanced Data Mining and Applications, 2010, pp. 270–281.
[15] J. He, L. Chen, X. Wang, and Y. Li, Web Service Composition Optimization Based on Improved Artificial Bee Colony Algorithm, J. Networks 8(9) (2013).
[16] F. Chen, M. Li, and H. Wu, GACRM: A dynamic multi-Attribute decision making approach to large-Scale Web service composition, Appl. Soft Comput.  61 (2017) 947–958.
[17] F. Chen, R. Dou, M. Li, and H. Wu, A flexible QoS-aware Web service composition method by multi-objective optimization in cloud manufacturing, Comput. Ind. Eng. 99 (2016) 423–431.
[18] H. Wang, B. Zou, G. Guo, D. Yang, and J. Zhang, Integrating Trust with User Preference for Effective Web Service Composition,” IEEE Trans. Serv. Comput. 10(4) (2017) 574–588.
[19] X. Liang, A. K. Qin, K. Tang, and K. C. Tan, QoS-aware Web Service Composition with Internal Complementarity, IEEE Trans. Serv. Comput., pp. 1–1, 2016.
[20] Y. Liu, J. Liao, Q. Qi, J. Wang, and J. Wang, Lightweight approach for multi-objective web service composition, IET Softw. 10(4) (2016) 116–124.
[21] S. Niu, G. Zou, Y. Gan, Y. Xiang, and B. Zhang, “Towards the optimality of QoS-aware web service composition with uncertainty,” Int. J. Web Grid Serv., vol. 15, no. 1, p. 1, 2019.
[22] S.-L. Fan, F. Ding, C.-H. Guo, and Y.-B. Yang, Supervised Web Service Composition Integrating Multi-objective QoS Optimization and Service Quantity Minimization, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10966 LNCS, Springer, Cham, 2018, pp. 215–230.
[23] S. Chibani Sadouki and A. Tari, “Multi-objective and discrete Elephants Herding Optimization algorithm for QoS aware web service composition, RAIRO - Oper. Res. 53(2) (2019)  445–459.
[24] A. Kedia, A. Pandel, A. Mohata, and S. Sowmya Kamath, An Intelligent Algorithm for Automatic Candidate Selection for Web Service Composition, Springer, Singapore, 2018, pp. 373–382.
[25] A. Sawczuk da Silva, H. Ma, Y. Mei, and M. Zhang, A Hybrid Memetic Approach for Fully Automated Multi-Objective Web Service Composition, IEEE International Conference on Web Services (ICWS), 2018, pp. 26–33.
[26] M. H. Shirvani, Web Service Composition in multi-cloud environment: A bi-objective genetic optimization algorithm, Innovations in Intelligent Systems and Applications (INISTA), 2018, pp. 1–6.
[27] X. Sun et al., A Fluctuation-Aware Approach for Predictive Web Service Composition,  IEEE International Conference on Services Computing (SCC), 2018, pp. 121–128.
[28] Y. Cheng and C. Ding, Optimization of web services composition using artificial bee colony algorithm, 10th International Congress on Image and Signal Processing, BioMedical Engineering and Informatics (CISP-BMEI), 2017.
[29] D. H. Elsayed, M. H. Gheith, E. S. Nasr, and A. E. D. M. El Ghazali, Integration of Parallel Genetic Algorithm and Q learning for QoS-aware Web Service Composition, 12th International Conference on Computer Engineering and Systems (ICCES), 2017, pp. 221–226.
[30] Y. Zhao, W. Tan, and T. Jin, QoS-aware Web Service Composition Considering the Constraints between Services, Proceedings of the 12th Chinese Conference on Computer Supported Cooperative Work and Social Computing= ChineseCSCW ’17, 2017, pp. 229–232.
[31] M. Alrifai, T. Risse, and W. Nejdl, A hybrid approach for efficient Web service composition with end-to-end QoS constraints, ACM Trans. Web 6(2) (2012)  1–31.
[32] V. Gabrel, M. Manouvrier, and C. Murat, Optimal and Automatic Transactional Web Service Composition with Dependency Graph and 0-1 Linear Programming, ICSOC 2014: ServiceOriented Computing, 2014, pp. 108–122.
[33] B. S, C. Rajendran, and S. RP, Penalty Based Mathematical Models for Web Service Composition in a Geo-Distributed Cloud Environment, IEEE International Conference on Web Services (ICWS), 2017, pp. 886–889.
[34] M. Ghobaei-Arani and A. Souri, “LP-WSC: a linear programming approach for web service composition in geographically distributed cloud environments,” J. Supercomput., vol. 75, no. 5, pp. 2603–2628, May 2019.
[35] M. Alrifai, D. Skoutas, and T. Risse, “Selecting skyline services for QoS-based web service
composition, Proceedings of the 19th international conference on World wide web - WWW ’10, 2010, pp. 11.
[36] C.-F. Lin, R.-K. Sheu, Y.-S. Chang, and S.-M. Yuan, A relaxable service selection algorithm for QoS-based web service composition, Inf. Softw. Technol. 53(12) (2011)  1370–1381.
[37] E. Kaldeli, A. Lazovik, and M. Aiello, Continual Planning with Sensing for Web Service Composition, Artif. Intell., 2010, pp. 1198–1203.
[38] D. Darling Jemima and G. R. Karpagam, Conceptual framework for semantic web service composition, International Conference on Recent Trends in Information Technology (ICRTIT), 2016, pp. 1–6.
[39] F. Wagner, B. Kloepper, F. Ishikawa, and S. Honiden, Towards robust service compositions in the context of functionally diverse services, Proceedings of the 21st international conference on World Wide Web - WWW ’12, 2012, pp. 969.
[40] L. Wu, Y. Zhang, and Z. Di, A service-cluster based approach to service substitution of web service composition,” in Proceedings of the 2012 IEEE 16th International Conference on Computer Supported Cooperative Work in Design (CSCWD), 2012, pp. 564–568.
[41] M. Rathore, M. Rathore, and U. Suman, A quality of service broker based process model for dynamic web service composition,” Proc. 3RD Int. Work. Model. Enterp. Inf. Syst. (EIS’ 07, pp. 1267–1274, 2011.
[42] N. H. Rostami, E. Kheirkhah, and M. Jalali, An Optimized Semantic Web Service Composition Method Based on Clustering and Ant Colony Algorithm, Feb. 2014.
[43] K. Huynh, T. Quan, and T. Bui, Smaller to Sharper: Efficient Web Service Composition and Verification Using On-the-fly Model Checking and Logic-Based Clustering, International Conference on Computational Science and Its Applications, 2016, pp. 453–468.
[44] J. Li, Y. Yan, and D. Lemire, Full Solution Indexing for Top-K Web Service Composition,” IEEE Trans. Serv. Comput. 11(3) (2018) 521–533.
[45] J. Li, Y. Yan, and D. Lemire, Full Solution Indexing for Top-K Web Service Composition,” IEEE Trans. Serv. Comput. 11(3) (2018) 521–533.
[46] V.A. Permadi and B. J. Santoso, Efficient skyline-based web service composition with QoS awareness and budget constraint, International Conference on Information and Communications Technology (ICOIACT), 2018, pp. 855-860.
[47] S. Chattopadhyay and A. Banerjee, QoS constrained Large Scale Web Service Composition using Abstraction Refinement, IEEE Trans. Serv. Comput. 2017 (2017) 1–1.
[48] Z.-Z. Liu, D.-H. Chu, Z.-P. Jia, J.-Q. Shen, and L. Wang, Two-stage approach for reliable dynamic Web service composition,” Knowledge-Based Syst. 97 (2016) 123–143.
[49] S. Bansal, A. Bansal, G. Gupta, and M. B. Blake, Generalized semantic Web service composition, Serv. Oriented Comput. Appl. 10(2) (2016) 111–133.
[50] A. Sawczuk da Silva, Y. Mei, H. Ma, and M. Zhang, Particle Swarm Optimisation with Sequence-Like Indirect Representation for Web Service Composition, EvoCOP 2016: Evolutionary Computation in Combinatorial Optimization, 2016, pp. 202–218.
[51] A. Sawczuk da Silva, Y. Mei, H. Ma, and M. Zhang, A memetic algorithm-based indirect approach to web service composition, IEEE Congress on Evolutionary Computation (CEC), 2016, pp. 3385–3392.
[52] A. Sawczuk da Silva, H. Ma, Y. Mei, and M. Zhang, A Hybrid Memetic Approach for Fully Automated Multi-Objective Web Service Composition, IEEE International Conference on Web Services (ICWS), 2018, pp. 26–33.
[53] Y. Yan, M. Chen, and Y. Yang, Anytime QoS optimization over the Plan Graph for web service composition, Proceedings of the 27th Annual ACM Symposium on Applied Computing - SAC ’12, 2012, pp. 1968.
[54] R. Eshuis, F. Lecue, and N. Mehandjiev, Flexible Construction of Executable Service Compositions from Reusable Semantic Knowledge, ACM Trans. Web 10(1) (2016) 1–27.
[55] I. Salomie, V. R. Chifu, and C. B. Pop, Hybridization of Cuckoo Search and Firefly Algorithms for Selecting the Optimal Solution in Semantic Web Service Composition, Cuckoo Search and Firefly Algorithm, Springer International Publishing, 2014, pp. 217–243.
[56] C. B. Pop, V. R. Chifu, I. Salomie, and M. Dinsoreanu, Immune-Inspired Method for Selecting the Optimal Solution in Web Service Composition, RED 2009: Resource Discovery, 2010, pp.1–17.
[57] Z. Zhang, W. Li, Z. Wu, and W. Tan, Towards an Automata-Based Semantic Web Services Composition Method in Context-Aware Environment, IEEE Ninth International Conference on Services Computing, 2012, pp. 320–327.
[58] Y. Xiao, X. Zhou, and X. Huang, Automated Semantic Web Service Composition Based on Enhanced HTN, Fifth IEEE International Symposium on Service-Oriented System Engineering, 2010, pp. 59–63.
[59] H. Tong, J. Cao, S. Zhang, and M. Li, A Distributed Algorithm for Web Service Composition Based on Service Agent Model, IEEE Trans. Parallel Distrib. Syst. 22(12) (2011)  2008–2021.
[60] X. Tang, C. Jiang, and M. Zhou, Automatic Web service composition based on Horn clauses and Petri nets,” Expert Syst. Appl. 38(10) (2011) 13024–13031.
[61] A. Bekkouche, S. M. Benslimane, M. Huchard, C. Tibermacine, F. Hadjila, and M. Merzoug, QoS-aware optimal and automated semantic web service composition with user’s constraints, Serv. Oriented Comput. Appl. 11(2) (2017) 183–201.
[62] F. Moo Mena, R. Hernandez Ucan, V. Uc Cetina, and F. Madera Ramirez, Web service composition using the bidirectional Dijkstra algorithm, IEEE Lat. Am. Trans. 14(5) (2016)  2522–2528.
[63] P. Rodriguez-Mier, C. Pedrinaci, M. Lama, and M. Mucientes, An Integrated Semantic Web Service Discovery and Composition Framework, IEEE Trans. Serv. Comput. 9(4) (2016) 537–550.
[64] F. Bey, S. Bouyakoub, and A. Belkhir, Time-Based Web Service Composition, Int. J. Semant. Web Inf. Syst. 14(2) (2018) 113–137.
[65] S.-L. Fan, Y.-B. Yang, and X.-X. Wang, Efficient Web Service Composition via KnapsackVariant Algorithm, Springer, Cham, 2018.
[66] L. T¸ ucar and P. Diac, Semantic Web Service Composition based on Graph Search, Procedia Comput. Sci. 126 (2018) 116–125.
[67] H. Elmaghraoui, L. Benhlima, and D. Chiadmi, Dynamic web service composition using AND/OR directed graph, 3rd International Conference of Cloud Computing Technologies and Applications (CloudTech), 2017, pp. 1–8.
[68] S.-L. Fan, Y.-B. Yang, and X.-X. Wang, Efficient Web Service Composition via KnapsackVariant Algorithm, Springer, Cham, 2018.
[69] A. Bekkouche, S. M. Benslimane, M. Huchard, C. Tibermacine, F. Hadjila, and M. Merzoug, QoS-aware optimal and automated semantic web service composition with user’s constraints, Serv. Oriented Comput. Appl. 11(2) (2017) 183–201.
[70] S. Niu, G. Zou, Y. Gan, Z. Zhou, and B. Zhang, UCLAO* and BHUC: Two Novel Planning Algorithms for Uncertain Web Service Composition, IEEE International Conference on Services Computing (SCC), 2016, pp. 531–538.
[71] Bo Zhang, A heuristic bidirectional search algorithm for automatic Web service composition, International Conference on Advanced Intelligence and Awareness Internet (AIAI 2010), 2010, pp. 407–411.
[72] S. Deng, B. Wu, J. Yin, and Z. Wu, Efficient planning for top-K Web service composition, Knowl. Inf. Syst.  36(3) (2013) 579–605.
[73] N. Ukey, R. Niyogi, A. Milani, and K. Singh, A Bidirectional Heuristic Search Technique for Web Service Composition, ICCSA 2010: Computational Science and Its Applications – ICCSA 2010, 2010, pp. 309–320.
[74] C.-S. Wu and I. Khoury, Tree-based Search Algorithm for Web Service Composition in SaaS, Ninth International Conference on Information Technology - New Generations, 2012, pp. 132–138.
[75] P. Rodriguez-Mier, M. Mucientes, and M. Lama, Automatic Web Service Composition with a Heuristic-Based Search Algorithm, IEEE International Conference on Web Services, 2011, pp. 81–88.
[76] F. D. O. Jr and J. De Oliveira, QoS-based Approach for Dynamic Web Service Composition., J. Univers. Comput. Sci. 17(5) (2011) 712–741.
[77] M. Ghobaei-Arani, A. A. Rahmanian, M. S. Aslanpour, and S. E. Dashti, CSA-WSC: cuckoo search algorithm for web service composition in cloud environments, Soft Comput. 22(24) (2018) 8353–8378.
[78] H. Fekih, S. Mtibaa, and S. Bouamama, An Efficient User-Centric Web Service Composition Based on Harmony Particle Swarm Optimization, Int. J. Web Serv. Res. 16(1) (2019) 1–21.
[79] H. Ye and T. Li, Web Service Composition with Uncertain QoS: An IQCP Model, Springer, Singapore, 2019, pp. 146-162.
[80] S. Deng, Y. Du, and L. Qi, A Web Service Composition Approach Based on Planning Graph and Propositional Logic, J. Organ. End User Comput. 31(3) (2019) 1–16.
[81] E. Shahsavari and S. Emadi, Semantic Constraint and QoS-Aware Large-Scale Web Service Composition, Shahrood Univ. Technol. 7(1) (2019) 181–191.
[82] J. Huang, Y. Zhou, Q. Duan, and C. Xing, Semantic Web Service Composition in Big Data Environment, GLOBECOM 2017 - 2017 IEEE Global Communications Conference, 2017, pp.1–7.
[83] J. Alves and J. Marchi, Web Service Composition: An Agent-Based Approach, Brazilian Conference on Intelligent Systems (BRACIS), 2017, pp. 121–126.
[84] Set cover problem, Available: https://en.wikipedia.org/wiki/Set cover problem. [Accessed: 16-Jul-2017].
[85] D.S. Johnson, Approximation algorithms for combinatorial problems, J. Comput. Syst. Sci. 9(3) (1974) 256–278.
[86] J.  Beasley and P.  Chu, A genetic algorithm for the set covering problem, Eur. J. Oper. Res. 94(2) (1996), 392–404.
[87] R. Jovanovic and M. Tuba, An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem, Appl. Soft Comput.  11(8) (2011) 5360–5366.
[88] S. C. Geyik, B. K. Szymanski, P. Zerfos, and D. Verma, “Dynamic Composition of Services in Sensor Networks,” in 2010 IEEE International Conference on Services Computing, 2010, no. Scc,pp. 242–249.
[89] V. Gabrel, M. Manouvrier, K. Moreau, and C. Murat, QoS-aware automatic syntactic service composition problem: Complexity and resolution, Futur. Gener. Comput. Syst., Apr. 2017.
[90] Journal Citation Reports - Web of Science Group, [Online]. Available: https://clarivate.com/webofsciencitation reports/. [Accessed: 22-Mar-2020].
[91] M. Khani and S. Araban, “QoS-WSC,” Mendeley Data, 2020.
 
International Journal of Nonlinear Analysis and Applications
Volume 12, Issue 1
May 2021
Pages 87-109
  • Receive Date: 04 February 2020
  • Revise Date: 14 October 2020
  • Accept Date: 22 October 2020