ترکیب خودکار سرویس‌ها مبتنی بر گراف رنگ‌آمیزی

نویسندگان

دانشگاه آزاد اسلامی واحد یزد - گروه مهندسی کامپیوتر

چکیده

سرویس‌های وب به‌عنوان مؤلفه‌های نرم‌افزاری مستقل توسط ارائه‌دهندگان سرویس بر روی اینترنت منتشر شده و توسط درخواست‌کنندگان سرویس برای رسیدن به اهداف مختلف فراخوانی می‌شوند. با این حال در بسیاری از موارد هیچ سرویسی به‌تنهایی در مخزن سرویس یافت نمی‌شود که بتواند رضایت درخواست‌کننده را برآورده سازد. ترکیب سرویس، مؤلفه‌های جدیدی را با استفاده از یک مدل تعاملی برای سرعت بخشیدن به برنامه‌ها ایجاد می‌کند. قبل از ترکیب سرویس‌ها با یکدیگر، مهم‌ترین مسئله برای پیدا کردن نمونه سرویس‌های کاندید مطلوب، مطابقت آن سرویس‌ها با نیازمندی‌های غیروظیفه‌مندی است؛ لذا چگونگی طراحی یک روش کارآمد جهت ترکیب زنجیره‌ای از سرویس‌های متصل‌به‌هم مهم است. به‌تازگی تحقیقات زیادی جهت کاهش زمان جستجو برای پیدا کردن یک ترکیب سرویس انجام شده است. با این حال بسیاری از این روش‌ها برای پیمایش و بررسی همه وب‌سرویس‌های موجود در یک مخزن وب به مدت‌زمان طولانی نیاز دارند که به‌صورت قابل توجهی وقت کاربر را اشغال می‌کند. این مقاله رویکردی برای ترکیب خودکار سرویس‌های آگاه از کیفیت سرویس و همچنین استفاده از سلایق کاربران در رسیدن به نتیجه ترکیب بهینه ارائه می‌دهد. بدین منظور از روش پیشنهادی گراف رنگ‌آمیزی اصلاح شده برای فیلتر نمودن سرویس‌ها قبل از ایجاد ترکیب در داده‌هایی با مقیاس بزرگ استفاده می‌شود که مجموعه سرویس‌های انتخابی را کاهش می‌دهد. همچنین استفاده از الگوریتم KPL در این پژوهش باعث گردیده است تا چندین راه‌حل مناسب به کاربر ارائه شود تا در مواقع لزوم از قابلیت جایگزینی این راه‌حل‌ها به‌جای بهترین ترکیب استفاده نماید. نتایج حاصل از تحلیل و ارزیابی روش پیشنهادی، بهبود مطلوبی را در زمان اجرا و مصرف حافظه نمایان می‌سازد.

کلیدواژه‌ها


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

Automatic Service Composition Based on Graph Coloring

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

  • S. Sheivandi
  • S. Emadi
Department of Computer Engineering, Yazd Branch, Islamic Azad, Yazd, Iran
چکیده [English]

Web services as independent software components are published on the Internet by service providers and services are then called by users’ request. However, in many cases, no service alone can be found in the service repository that could satisfy the applicant satisfaction. Service composition provides new components by using an interactive model to accelerate the programs. Prior to service composition, the most important issue in finding suitable candidate services samples is their compliance with non-functional requirements. Thus, designing an efficient way to combine a chain of connected services is important. Recently, numerous studies have been done to reduce the search time in finding a service composition. However, many of these methods to examine and investigate all Web services in a Web repository require a long time, which occupy the user's time significantly. This paper provides an approach for automatic quality-aware service composition as well as the users’ preferences in achieving the optimum composition results. For this purpose, modified graph coloring method to filter the data before compositions in large-scale data is used which decreases selected services set. The application of KPL algorithm in this study provided some proper solutions to the user so that these solutions can be used instead of the best composition if necessary. Therefore, the results derived from the analysis of the proposed method, indicates a good optimization in runtime and memory consumption.

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

  • Service composition
  • graph coloring
  • Top-K algorithm
  • quality-aware service
  • KPL algorithm
[1] W. Jiang, D. Lee, and S. Hu. “Large-scale longitudinal analysis of soap-based and restful web services,” IEEE 19th International Conference on Web Services (ICWS), pp. 218-225. IEEE, 2012.
[2] E. Sirin, B. Parsia, D. Wu, J. Hendler and D. Nau, “HTN planning for web service composition using SHOP2,” Web Semantics: Science, Services and Agents on the World Wide Web 1, no. 4: 377-396, 2004.
[3] A. Zhou, S. Huang and X. Wang, “Bits: A binary tree based web service composition system,” International Journal of Web Services Research (IJWSR) 4, no. 1: 40-58, 2007.
[4] S.V. Hashemian, and F. Mavaddat. “A graph-based framework for composition of stateless web services,” 4th European Conference on Web Services, pp. 75-86. IEEE, 2006.
[5] De Oliveira, S. B., Balloni, A. J., Nogueira, F., & Toda, F. A., "Information and service-oriented architecture & web services: enabling integration and organizational agility", Procedia Technology 5, pp. 141-151, 2012.‌
[6] El Ouahed, A. K., Erradi, M., & Azzoune, H., "A Discovery Service for Automatic Composition of Web Services Oriented-Agent", 22nd International Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE), pp. 33-35, 2013.‌
[7] Klein, A., Ishikawa, F. and Honiden, S . "SanGA: A self-adaptive network-aware approach to service composition." IEEE Transactions on Services Computing 7, no. 3: 452-464, 2014.
[8] Z. Brahmi, “QoS-aware Automatic Web Service Composition based on Cooperative Agents,” 22nd International Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE), pp. 27-32. IEEE, 2013.
[9] S. Deng, B. Wu, J. Yin and Z. Wu, “Efficient planning for top-K Web service composition,” Knowledge and information systems 36, no. 3: 579-605, 2013.
[10] S. Deng, L. Huang, W. Tan and Z. Wu, “Top-automatic service composition: A parallel method for large-scale service sets,” IEEE Transactions on Automation Science and Engineering 11, no. 3: 891-905, 2014.
[11] G. Zou, Y. Gan, Y. Chen and B. Zhang, “Dynamic composition of Web services using efficient planners in large-scale service repository,” Knowledge-Based Systems 62: 98-112, 2014.
[12] A.S. da Silva, H. Ma and M. Zhang, “A graph-based particle swarm optimization approach to qos-aware web service composition and selection,” In 2014 IEEE Congress on Evolutionary Computation (CEC), pp. 3127-3134. IEEE, 2014.
[13] A. S. da Silva, H. Ma and M. Zhang, "Genetic programming for QoS-aware web service composition and selection." Soft Computing-A Fusion of Foundations, Methodologies and Applications, no. 10: 3851-3867, 2016.
[14] J. Liao, Y. Liu, X. Zhu and J. Wang, “Accurate sub-swarms particle swarm optimization algorithm for service composition, ” Journal of Systems and Software 90: 191-203, 2014.
[15] Q. Yu, L. Chen and B. Li, “Ant colony optimization applied to web service compositions,” in cloud computing Computers & Electrical Engineering 41: 18-27, 2015.
[16] D. Wang, Y. Yang and Z. Mi, “A genetic-based approach to web service composition,” in geo-distributed cloud environment Computers & Electrical Engineering 43: 129-141, 2015.
[17] M. Li, D. Zhu, T. Deng, H. Sun, H. Guo and X. Liu, “GOS: a global optimal selection strategies for QoS-aware web services composition,” Service Oriented Computing and Applications 7, no. 3: 181-197, 2013.
[18] G. Zou, Q. Lu, Y. Chen, R. Huang, Y. Xu and Y. Xiang, “QoS-aware dynamic composition of Web services using numerical temporal planning,” IEEE Transactions on Services Computing 7, no. 1: 18-31, 2014.
[19] A. Immonen and D. Pakkala, “A survey of methods and approaches for reliable dynamic service compositions,” Service Oriented Computing and Applications 8, no. 2: 129-158, 2014.
[20] J. Wu, L. Chen and T. Liang, “Selecting dynamic skyline services for QoS-based service composition,” Applied Mathematics & Information Sciences 8, no. 5: 2579, 2014.
[21] C. H. Lee, S. Y. Hwang, I. L. Yen and T. K. Yu, “A service pattern model for service composition with flexible functionality,” Information Systems and e-Business Management 13, no. 2: 235-265, 2015.
[22] H. Jin, X. Yao and Y. Chen, “Correlation-aware QoS modeling and manufacturing cloud service composition,” Journal of Intelligent Manufacturing: 1-14, 2015.
[23] D. Nagamouttou, I. Egambaram, M. Krishnan and P. Narasingam, “A verification strategy for web services composition using enhanced stacked automata model,” Springer Plus 4, no. 1: 1, 2015.
[24] M. El Kholy and A. El Fatatry, “FRWSC: a framework for robust Web service composition,” Service Oriented Computing and Applications: 1-23, 2016.
[25] W. Jiang, S. Hu and Z. Liu, “Top K query for QoS-aware automatic service composition,” IEEE Transactions on Services Computing 7, no. 4: 681-695, 2014.
[26] Klo¨epper B, Ishikawa F, Honiden S, “Service Composition with Pareto-Optimality of Time-Dependent QoS Attributes", in Service-Oriented Computing, Lecture Notes in Computer Science. Berlin, Germany: Springer-Verlag, no. 6470: 635-640, 2010.
[27] S. Rafiee, and P. Moradi, “Improving Performance of Fuzzy C-means Clustering Algorithm using Automatic Local Feature Weighting,” Tabriz Journal of Electrical Eng., vol. 46, no.2, summer 2016.
[28] S. Abdollahzadeh, M. A. Balafar, and L. Mohammad Khanli, “Using Clustering and Markov Model in Predicting Web Users' Next Request,” Tabriz Journal of Electrical Eng., vol. 45, no. 3, autumn 2015.
[29] M. Rafiee, M. abbasi, and M. Nassiri, “An Efficient Method for Parallel Implementation of H-Trie Packet Classification Algorithm on GPU,” Tabriz Journal of Electrical Engineering, vol. 46, no. 3, autumn 2016.
[30] Yuan, Yuan, Xiuguo Zhang, Wenxi Sun, Zhiying Cao, and Hao Wang. "Optimal web service composition based on context-awareness and genetic algorithm." International Conference on Information Science and Cloud Computing Companion (ISCC-C), pp. 660-667. IEEE, 2013.