روشی برای ساده‌سازی الگوها در ترکیب وب‌سرویس‌ها و انتخاب بهینه ترکیب با ساختار احتمالی

ظهیری, نرجس; بابامیر, سید مرتضی

doi:10.22052/scj.2021.243188.1003

روشی برای ساده‌سازی الگوها در ترکیب وب‌سرویس‌ها و انتخاب بهینه ترکیب با ساختار احتمالی

نوع مقاله : مقاله پژوهشی

نویسندگان

دانشکده برق و کامپیوتر، گروه مهندسی کامپیوتر، دانشگاه کاشان، کاشان، ایران

10.22052/scj.2021.243188.1003

چکیده

یکی از چالش‌برانگیزترین موضوعات مرتبط با وب‌سرویس‌ها مساله ترکیب آن‌هاست که به صورت یک گراف برای نمایش تعامل بین سرویس‌ها ارائه می‌شود. هر گره از این گراف، یک وب‌سرویس انتزاعی با وظیفه مشخص اما ویژگی‌های کیفی نامشخص است. برای هر سرویس انتزاعی، مجموعه‌ای از سرویس‌های کاندید با وظیفه یکسان اما ویژگی‌های کیفی متفاوت وجود دارد. جایگزینی یک وب‌سرویس کاندید برای هر سرویس انتزاعی به نحوی که یک ترکیب بهینه حاصل شود، یک مساله NP-hard است، لذا برای حل آن از الگوریتم‌های هیوریستیک استفاده می‌شود. تاکنون روش‌های متعددی برای ترکیب بهینه وب‌سرویس ها ارائه شده اما بیشتر این روش‌ها ساختار احتمالی را پشتیبانی نمی‌کنند. تنها یک روش ساختار احتمالی را پشتیبانی می‌کند که برای گراف های بزرگ مقیاس‌پذیر نیست، مبتنی بر قیود است و به تحلیل هر مسیر گراف به صورت جداگانه پرداخته است. این مقاله، رویکردی مقیاس‌پذیر و چندهدفه برای تحلیل گراف به صورت یکپارچه ارائه می‌دهد که علاوه بر پوشش دو الگوی جدید حلقه‌های تودرتو و حلقه‌های موازی، با ارائه روشی جهت ساده‌سازی ترکیب وب‌سرویس‌ها موجب بهبود کارایی نیز می‌شود. در این روش برای انتخاب بهینه وب‌سرویس‌ها و حفظ مقیاس‌پذیری، از الگوریتم‌های تکاملی NSGAII و SPEAII استفاده می‌شود. در روش پیشنهادی ابتدا در گراف‌هایی با الگوی شرطی، هر مسیر بر حسب احتمال آن، چند بار تکرار می‌شود و سپس از الگوریتم NSGAII به منظور تعیین بهترین مسیر در گراف و یافتن راه‌حل‌های بهتر استفاده می‌شود. روش پیشنهادی در مقایسه با بهترین روش مقایسه شده، 30 درصد در پارامتر قابلیت اطمینان و 121 میلی ثانیه در زمان پاسخ بهبود داشته است.

کلیدواژه‌ها

20.1001.1.23223707.1399.9.2.4.9

عنوان مقاله [English]

A method to simplify patterns in web services compositions and select optimal probabilistic composition

نویسندگان [English]

Narges Zahiri
Seyed Morteza Babamir

Faculty of Electrical and Computer Engineering, Department of Computer Engineering, University of Kashan, Kashan, Iran

چکیده [English]

One of the most challenging issues in web services is their composition, which is presented as a graph to show the interaction between services. Each node in such a graph is called an abstract web service with a specific function and undetermined quality attributes. For each abstract service, there is a set of candidate services with the same function but different quality attributes. Selecting a candidate web service for each abstract service leading to an optimal combination is an NP-hard problem; hence, heuristic algorithms should be used to resolve it. Several methods have been proposed to select optimal web service composition, but most of them don't support the probability structure. Among others, one method supports a probability structure that is not scalable for large graphs, is constraint based, and analyzes each path of the graph separately. This paper presents an integrated scalable multi-objective approach for analyzing graph where not only two new patterns of nested loops and parallel loops are dealt with but also performance is improved by representing a method for simplifying web-service compositions. In this method, to select optimal web services and to respect scalability, evolutionary algorithms NSGAII and SPEAII are used. In the proposed method, first in conditional graphs, each path is traversed according to its probability and then NSGAII is used to determine the best path in the graph and find better solutions. The proposed method was compared with the best known method; results showed the proposed method enjoys 30% improvement in reliability and 121 milliseconds in response time.

کلیدواژه‌ها [English]

Web services selection
Web service composition
Quality-aware web services
Probability complex structures
Graph simplification
Evolutionary algorithms
NSGAII algorithm
SPEAII algorithm

مراجع

[1] رسولزاردگان ع.، بصیری م.، «اندازه‌گیری کمی کیفیت در مهندسی نرم افزار سرویس‌گرا: روش‌ها، کاربردها و چالش‌ها»، مجله محاسبات نرم، جلد 3، شماره1، ص 2-19، 1393.
[2] دهقانی م.، عمادی س.، «ارائه یک مدلی جدید برای بلوغ حاکمیت بر معماری سرویس‌گرا»، مجله محاسبات نرم، جلد 4، شماره 2، ص 54-67، 1394.
[3] Chen, F., Dou, R., Li, M., & Wu, H., A flexible QoS-aware Web service composition method by multi-objective optimization in cloud manufacturing, Computers & Industrial Engineering, 99, 423-431, 2016.
[4] Strunk, A., QoS-aware service composition: A survey, In 2010 Eighth IEEE European Conference on Web Services (pp. 67-74), IEEE, 2010.
[5] Zheng, H., Zhao, W., Yang, J., & Bouguettaya, A., QoS analysis for web service compositions with complex structures, IEEE Transactions on Services Computing, 6(3), 373-386, 2012.
[6] Zheng, H., Zhao, W., Yang, J., & Bouguettaya, A., Qos analysis for web service composition, In 2009 IEEE International Conference on Services Computing (pp. 235-242), IEEE, 2009.
[7] Brahmi, Z., & Gammoudi, M. M., QoS-aware automatic web service composition based on cooperative agents, In 2013 Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (pp. 27-32), IEEE, 2013.
[8] Canfora, G., Di Penta, M., Esposito, R., & Villani, M. L., A lightweight approach for QoS-aware service composition. In Proc. 2nd International Conference on Service Oriented Computing (ICSOC’04)-short papers, 2004.
[9] Alrifai, M., Risse, T., Dolog, P., & Nejdl, W., A scalable approach for qos-based web service selection. In International conference on service-oriented computing (pp. 190-199). Springer, Berlin, Heidelberg, 2008.
[10] Liu, H., Zhong, F., Ouyang, B., & Wu, J., An approach for QoS-aware web service composition based on improved genetic algorithm. In 2010 International conference on web information systems and mining (Vol. 1, pp. 123-128). IEEE, 2010.
[11] Gohain, S., & Paul, A., Web service composition using PSO—ACO. In 2016 International conference on recent trends in information technology (ICRTIT) (pp. 1-5). IEEE, 2016.
[12] Liu, S., Liu, Y., Jing, N., Tang, G., & Tang, Y., A dynamic web service selection strategy with QoS global optimization based on multi-objective genetic algorithm. In International Conference on Grid and Cooperative Computing (pp. 84-89). Springer, Berlin, Heidelberg, 2005.
[13] Yao, Y., & Chen, H., A rule-based web service composition approach. In 2010 Sixth International Conference on Autonomic and Autonomous Systems (pp. 150-155). IEEE, 2010.
[14] Li, L., Yang, P., Ou, L., Zhang, Z., & Cheng, P., Genetic algorithm-based multi-objective optimisation for QoS-aware web services composition. In International Conference on Knowledge Science, Engineering and Management (pp. 549-554). Springer, Berlin, Heidelberg, 2010.
[15] Huo, Y., Qiu, P., Zhai, J., Fan, D., & Peng, H., Multi-objective service composition model based on cost-effective optimization. Applied Intelligence, 48(3), 651-669, 2018.
[16] Yilmaz, A. E., & Karagoz, P., Improved genetic algorithm based approach for QoS aware web service composition. In 2014 IEEE international conference on web services (pp. 463-470). IEEE, 2014.
[17] Ardagna, D., & Pernici, B., Global and local QoS guarantee in web service selection. In International Conference on Business Process Management (pp. 32-46). Springer, Berlin, Heidelberg, 2005.
[18] Tang, M., & Ai, L., A hybrid genetic algorithm for the optimal constrained web service selection problem in web service composition. In IEEE Congress on Evolutionary Computation (pp. 1-8). IEEE, 2010.
[19] Canfora, G., Di Penta, M., Esposito, R., & Villani, M. L., An approach for QoS-aware service composition based on genetic algorithms. In Proceedings of the 7th annual conference on Genetic and evolutionary computation (pp. 1069-1075), 2005.
[20] Mukherjee, D., Jalote, P., & Nanda, M. G., Determining QoS of WS-BPEL compositions. In International Conference on Service-Oriented Computing (pp. 378-393). Springer, Berlin, Heidelberg, 2008.
[21] Yao, Y., & Chen, H., Qos-aware service composition using nsga-ii1. In Proceedings of the 2nd international conference on interaction sciences: information technology, culture and human (pp. 358-363), 2009.
[22] Dumas, M., Garcia-Banuelos, L., Polyvyanyy, A., Yang, Y., & Zhang, L., Aggregate quality of service computation for composite services. In International Conference on Service-Oriented Computing (pp. 213-227). Springer, Berlin, Heidelberg, 2010.
[23] Li, J. Z., Luo, W. L., Jin-tao, Z., & Jie-wu, X., Application of SPEA2 algorithm in web services selection. In 2010 IEEE Youth Conference on Information, Computing and Telecommunications (pp. 387-390). IEEE, 2010.
[24] Sharifara, P., Yari, A., & Kashani, M. M. R., An evolutionary algorithmic based web service composition with quality of service. In 7'th International Symposium on Telecommunications (IST'2014) (pp. 61-65). IEEE, 2014.
[25] Liu, L., & Zhang, M., Multi-objective optimization model with AHP decision-making for Cloud service composition. KSII Transactions on Internet and Information Systems (TIIS), 9(9), 3293-3311, 2015.
[26] Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T., A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197, 2002.
[27] Radziukyniene, I., & Zilinskas, A., Evolutionary methods for multi-objective portfolio optimization. In Proceedings of the World Congress on Engineering (Vol. 2, pp. 1155-1159), 2008.
[28] Zitzler, E., Laumanns, M., & Thiele, L., SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-report, 103, 2001.
[29] Sadouki, S. C., & Tari, A., Multi-objective and discrete Elephants Herding Optimization algorithm for QoS aware web service composition. RAIRO-Operations Research, 53(2), 445-459, 2019.
[30] Seghir, F., FDMOABC: fuzzy discrete multi-objective artificial bee colony approach for solving the non-deterministic QoS-driven web service composition problem. Expert Systems with Applications, 167, 114413, 2021.
[31] Xie, N., Tan, W., Zheng, X., Zhao, L., Huang, L., & Sun, Y., An efficient two-phase approach for reliable collaboration-aware service composition in cloud manufacturing. Journal of Industrial Information Integration, 23, 100211, 2021.
[32] Thangaraj, P., & Balasubramanie, P., Meta heuristic QoS based service composition for service computing. Journal of Ambient Intelligence and Humanized Computing, 12(5), 5619-5625, 2021.
[33] https://qwsdata.github.io/