تامین پویای سرویس در محیط مه مبتنی بر اتوماتای یادگیر و الگوریتم ژنتیک چندهدفه

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

نویسنده

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

چکیده

امروزه تعداد برنامه‌های کاربردی که نیاز به زمان پاسخ‌دهی کمی دارند، روز به روز در حال افزایش است و بکارگیری محیط مه اخیرا مورد توجه زیادی قرار گرفته است. با توجه به پویایی استفاده از منابع در اکثر برنامه‌های اینترنت اشیا، نمی‌توان مکان ثابتی برای قرارگیری و اجرای سرویس‌ها در محیط مه در نظر گرفت و بنابراین باید سرویس‌ها در محیط مه به صورت پویا قرار داده شوند. مساله قرار دادن سرویس‌های مورد نیاز اینترنت اشیا در دستگاه‌های مه با محدودیت منابع، به عنوان یک مساله NP-hard شناخته می‌شود. در این مقاله، روشی پویا مبتنی بر الگوریتم ژنتیک چندهدفه با رتبه‌بندی نامغلوب جهت حل این مساله ارائه می‌گردد. در روش پیشنهادی، از اتوماتای یادگیر، جهت بهبود رفتار ژنتیکی و تنظیم پویای نرخ جهش و تقاطع استفاده می‌شود. روش پیشنهادی با استفاده از نرم‌افزار iFogsim شبیه‌سازی شده و نتایج شبیه‌سازی نشان می‌دهد روش پیشنهادی با در نظر گرفتن همزمان سه معیار تاخیر سرویس، هزینه و انرژی مصرفی، کارایی بهتری را نسبت به الگوریتم‌های مورد مقایسه دارد. از نظر هزینه، در مقایسه با دو روش CSA و LRFC به‌ترتیب 11 و 21 درصد کاهش داشته است. همچنین روش پیشنهادی از نظر میانگین تاخیر سرویس‌دهی نسبت به دو روش CSA و HAFA به‌ترتیب 7 و 15 درصد کاهش داشته است. از نظر انرژی مصرفی نیز روش پیشنهادی نسبت به روش‌های دیگر بهبود حداقل 8 درصدی را نشان می‌دهد.

کلیدواژه‌ها


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

Dynamic Service Provisioning in Fog Environment based on Learning Automata and Multi-objective Genetic Algorithm

نویسنده [English]

  • Seyed Mahdi Jameii
Department of Computer Engineering, Shahr-e-Qods Branch, Islamic Azad University, Tehran, Iran.
چکیده [English]

Nowadays, the number of applications that require a short response time is increasing, and utilizing fog environment has recently received a lot of attention. Due to the dynamics of the resource usage pattern in most Internet of Things applications, a fixed location cannot be considered for the placement and execution of services in the fog environment, and therefore the services must be dynamically placed in the fog environment. The problem of placing required Internet of Things services in cloud devices with limited resources is known as an NP-hard problem. In this article, a dynamic method based on multi-objective genetic algorithm with non-dominated ranking is presented to solve this problem. In the proposed method, learning automata are used to improve genetic behavior and dynamically adjust mutation and crossover rates. The proposed method is simulated using iFogsim and the simulation results show that the proposed method has a better efficiency than the compared algorithms by simultaneously considering the three criteria of service delay, cost and energy consumption. In terms of cost, compared to the two CSA and LRFC methods, it has decreased by 11% and 21%, respectively. Also, in terms of the average service delay, compared to the CSA and HAFA methods, the proposed method has decreased by 7% and 15 %, respectively. In terms of energy consumption, the proposed method shows an improvement of at least 8% compared to other methods.

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

  • IoT
  • Fog Computing
  • Cloud Computing
  • Dynamic Service Provisioning
  • Genetic Algorithm
  • Learning Automata
[1] J. Li, X. Shen, L. Chen, D.P. Van, J. Ou, L. Wosinska, and J. Chen, “Service Migration in Fog Computing Enabled Cellular Networks to Support Real-Time Vehicular Communications,” IEEE Access, vol. 7,  pp. 13704-13714, 2019, doi: 10.1109/ACCESS.2019.2893571.
[2] M. Shirkhani, K. Khamforoosh, and M. Izadbin, “Providing an improved greedy approach for increasing the number of Served users in cloud-edge networks,” Soft Comput. J., vol. 10, no. 1, pp. 32-47, 2021, doi: 10.22052/scj.2022.243195.1005 [In Persian].
[3] M. Nickray and E. hosseini, “A Mobile and Fog-based Computing Method to Execute Smart Device Applications in a Secure Environment,” Soft Comput. J., vol. 8, no. 1, pp. 43-57, 2019, doi: 10.22052/8.1.43 [In Persian].
[4] A. Yousefpour, A. Patil, G. Ishigaki, I. Kim, X. Wang, H.C. Cankaya, Q. Zhang, W. Xie, and J.P. Jue, “FOGPLAN: A Lightweight QoS-Aware Dynamic Fog Service Provisioning Framework,” IEEE Internet Things J., vol. 6, no. 3, pp. 5080-5096, 2019, doi: 10.1109/JIOT.2019.2896311.
[5] S. Gholamshahi and S.M.H. Hasheminejad, “A method for identifying software components based on Non-dominated Sorting Genetic Algorithm,” Soft Comput. J., vol. 7, no. 2, pp. 47-64, 2019, dor: 20.1001.1.23223707.1397.7.2.4.5 [In Persian].
[6] C. Liu, J. Wang, L. Zhou, and A. Rezaeipanah, “Solving the Multi-Objective Problem of IoT Service Placement in Fog Computing Using Cuckoo Search Algorithm,” Neural Process. Lett., vol. 54, no. 3, pp. 1823-1854, 2022, doi: 10.1007/s11063-021-10708-2.
[7] M. Ghobaei-Arani and A. Shahidinejad, “A cost-efficient IoT service placement approach using whale optimization algorithm in fog computing environment,” Expert Syst. Appl., vol. 200, p. 117012, 2022, doi: 10.1016/j.eswa.2022.117012.
[8] B. Wu, X. Lv, W.D. Shamsi, and E.G. Dizicheh, “Optimal deploying IoT services on the fog computing: A metaheuristic-based multi-objective approach,” J. King Saud Univ. Comput. Inf. Sci., vol. 34, no. 10 Part B, pp. 10010-10027, 2022, doi: 10.1016/j.jksuci.2022.10.002.
[9] B.V. Natesha and R.M.R. Guddeti, “Meta-heuristic Based Hybrid Service Placement Strategies for Two-Level Fog Computing Architecture,” J. Netw. Syst. Manag., vol. 30, no. 3, p. 47, 2022, doi: 10.1007/s10922-022-09660-w.
[10] M. Azimzadeh, A. Rezaee, S.J. Jassbi, and M. Esnaashari, “Placement of IoT services in fog environment based on complex network features: a genetic-based approach,” Clust. Comput., vol. 25, no. 5, pp. 3423-3445, 2022, doi: 10.1007/s10586-022-03571-w.
[11] N. Sarrafzade, R. Entezari-Maleki, and L. Sousa, “A genetic-based approach for service placement in fog computing,” J. Supercomput., vol. 78, no. 8, pp. 10854-10875, 2022, doi: 10.1007/s11227-021-04254-w.
[12] F. Santos, R. Immich, and E.R.M. Madeira, “Multimedia services placement algorithm for cloud-fog hierarchical environments,” Comput. Commun., vol. 191, pp. 78-91, 2022, doi: 10.1016/j.comcom.2022.04.009.
[13] S. Shaik and S. Baskiyar, “Distributed service placement in hierarchical fog environments,” Sustain. Comput. Informatics Syst., vol. 34, p. 100744, 2022, doi: 10.1016/j.suscom.2022.100744.
[14] M. Tekiyehband, M. Ghobaei-Arani, and A. Shahidinejad, “An efficient dynamic service provisioning mechanism in fog computing environment: A learning automata approach,” Expert Syst. Appl., vol. 198, p. 116863, 2022, doi: 10.1016/j.eswa.2022.116863.
[15] S. Pallewatta, V. Kostakos, and R. Buyya, “QoS-aware placement of microservices-based IoT applications in Fog computing environments,” Future Gener. Comput. Syst., vol. 131, pp. 121-136, 2022, doi: 10.1016/j.future.2022.01.012.
[16] D. Zhao, Q. Zou, and M.B. Zadeh, “A QoS-Aware IoT Service Placement Mechanism in Fog Computing Based on Open-Source Development Model,” J. Grid Comput., vol. 20, no. 2, p. 12, 2022, doi: 10.1007/s10723-022-09604-3.
[17] H.O. Hassan, S. Azizi, and M. Shojafar, “Priority, network and energy-aware placement of IoT-based application services in fog-cloud environments,” IET Commun., vol. 14, no. 13, pp. 2117-2129, 2020, doi: 10.1049/iet-com.2020.0007.
[18] W. Ram?rez, X. Masip-Bruin, E. Mar?n-Tordera, V.B.C. Souza, A. Jukan, G.-J. Ren, and O.G. de Dios, “Evaluating the benefits of combined and continuous Fog-to-Cloud architectures,” Comput. Commun., vol. 113, pp. 43-52, 2017, doi: 10.1016/j.comcom.2017.09.011.
[19] F. Murtaza, A. Akhunzada, S. ul Islam, J. Boudjadar, and R. Buyya, “QoS-aware service provisioning in fog computing,” J. Netw. Comput. Appl., vol. 165, p. 102674, 2020, doi: 10.1016/j.jnca.2020.102674.
[20] M. Zare, Y.E. Sola, and H. Hasanpour, “Towards distributed and autonomous IoT service placement in fog computing using asynchronous advantage actor-critic algorithm,” J. King Saud Univ. Comput. Inf. Sci., vol. 35, no. 1, pp. 368-381, 2023, doi: 10.1016/j.jksuci.2022.12.006.
[21] N.B. Salah and N.B.B. Saoud, “Adaptive data placement in the Fog infrastructure of IoT applications with dynamic changes,” Simul. Model. Pract. Theory, vol. 119, p. 102557, 2022, doi: 10.1016/j.simpat.2022.102557.
[22] A. Alammari, S.A. Moiz, and A. Negi, “Enhanced layered fog architecture for IoT sensing and actuation as a service,” Sci. Rep., vol. 11, p. 21693, 2021, doi: 10.1038/s41598-021-00926-y.
[23] B.V. Natesha and R.M.R. Guddeti, “Adopting elitism-based Genetic Algorithm for minimizing multi-objective problems of IoT service placement in fog computing environment,” J. Netw. Comput. Appl., vol. 178, p. 102972, 2021, doi: 10.1016/j.jnca.2020.102972.
[24] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182-197, 2002, doi: 10.1109/4235.996017.
[25] T.-P. Hong, H.-S. Wang, W.-Y. Lin, and W.-Y. Lee, “Evolution of Appropriate Crossover and Mutation Operators in a Genetic Process,” Appl. Intell., vol. 16, no. 1, pp. 7-17, 2002, doi: 10.1023/A:1012815625611.
[26] J. Zhang, H.S.-H. Chung, and W.-L. Lo, “Clustering-Based Adaptive Crossover and Mutation Probabilities for Genetic Algorithms,” IEEE Trans. Evol. Comput., vol. 11, no. 3, pp. 326-335, 2007, doi: 10.1109/TEVC.2006.880727.
[27] K.S. Narendra and M.A.L. Thathachar, Learning automata - an introduction, Prentice Hall 1989, ISBN 978-0-13-527011-0, pp. 1-476.
[28] R. Buyya and S.N. Srirama, “Modeling and Simulation of Fog and Edge Computing Environments Using iFogSim Toolkit,” in Fog and Edge Computing: Principles and Paradigms, Wiley, 2019, pp.433-465, doi: 10.1002/9781119525080.ch17.
[29] MAVI (Sep. 2022), Wide mawi working group traffic archive, [Online]. Available: http://mawi.wide.ad.jp.