یک طرح برون‌سپاری وظایف آگاه از جابه‌جایی اشیاء مبتنی بر الگوریتم بهینه‌سازی کلونی مورچه در پردازش مه نرم‌افزار-محور

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

نویسندگان

1 استادیار، دانشکده مهندسی کامپیوتر، دانشگاه یزد، یزد، ایران

2 دانشجوی دکترا، دانشکده مهندسی کامپیوتر، دانشگاه یزد، یزد، ایران

چکیده

محاسبات مه رویکرد نوینی است که با هدف کاهش زمان پاسخ کاربرد‌های حساس به تأخیر و بهبود ارائه خدمات به کاربران، امکان برون‌سپاری وظایف (داده‌ها) اینترنت اشیاء را به تجهیزات شبکه فراهم می‌کند. این مقاله یک طرح برون‌سپاری وظیفه به محیط مه با بهره‌مندی از مزایای شبکه‌های نرم‌افزار-‌محور ارائه می‌دهد. در این پژوهش یک مدل ریاضی بهینه‌سازی برنامه‌ریزی خطی عدد صحیح مختلط (MILP) با هدف کمینه‌سازی تأخیر و هزینه ناشی از جابه‌جایی اشیاء و با در نظر گرفتن پردازش محلی، مشارکت گره‌های مه، توزیع برنامه‌های کاربردی و محدودیت منابع گره‌های مه ارائه شده است. با توجه به اینکه مدل ریاضی ارائه شده در این مسئله ان‌پی‌-سخت است، یک الگوریتم فرا‌-ابتکاری مبتنی بر بهینه‌سازی کلونی مورچه و با در نظر گرفتن محدودیت‌های مدل ریاضی ارائه شده است. مقادیر حاصل از ارزیابی روش پیشنهادی با مقدار بهینه حاصل از مدل ریاضی، روش‌ تصادفی و یک الگوریتم ابتکاری ارائه شده در کارهای مرتبط مقایسه شده است. نتایج حاصل نشان می‌دهد تأخیر و هزینه کل برون‌سپاری در روش پیشنهادی به ترتیب 22% و 28.75% از مقادیر بهینه بیشتر است و روش پیشنهادی قادر به کاهش تأخیر به میزان 20% و کاهش هزینه مهاجرت نتایج به میزان 40% نسبت به روش ابتکاری مقایسه شده است.

کلیدواژه‌ها


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

A Mobility Aware Task Offloading Scheme Based On Ant Colony Optimization Algorithm In Software-Defined Fog Computing

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

  • S.A. Mostafavi 1
  • E. Barkhordari 2
1 Department of Computer Engineering, Faculty of Engineering, Yazd University, Yazd, Iran
2 Department of Computer Engineering, Faculty of Engineering, Yazd University, Yazd, Iran
چکیده [English]

Fog computing is a new paradigm which enables offloading IOT data (tasks) to the network devices. The aim of this approach is reducing the response time for delay-sensitive applications and improving the quality of service for users. This paper presents a task offloading scheme with taking advantages of the Software-Defind Networks. In this research a mixed integer linear programming (MILP) optimization model is presented with the aim of minimizing delay and mobility cost of things, which considers local computing, fog nodes participation, applications distribution and resource limitations. Whereas the presented mathematical model is Np-hard, a meta-heuristic algorithm based on the ant colony optimization is proposed by considering constraints of the mathematical model. The results obtained from evaluation of the proposed method is compared with the optimal value obtained from the mathematical model, random method and a heuristic algorithm presented in related works. The results of evaluation show that the delay and the total offloading cost in the proposed method are 22% and 28.75% higher than the optimal values, respectively. Also, the proposed method is capable to reduce the delay by 20% and reduce the migration cost of computing results by 40% compared to the heuristic method in state-of-the-art.

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

  • Internet of Things
  • fog computing
  • task offloading
  • mobility of things
  • ant colony optimization
  • software-defined networking
[1] بهشید شایسته، وصال حکمی، سید اکبر مصطفوی، احمد اکبری، «ارائه روشی نوین برای محاسبه اعتماد در کاربردهای اینترنت اشیاء»، مجله مهندسی برق دانشگاه تبریز، جلد 50، شماره 2، صفحات 755-743، 1399
[2] S. O. Ogundoyin and I. A. Kamil, "Optimization techniques and applications in fog computing: An exhaustive survey," Swarm Evol Comput, vol. 66, p. 100937, Oct. 2021, doi: 10.1016/J.SWEVO.2021.100937.
[3] V. K. M. D. O. S. H. Pedram, "Energy and task completion time trade-off for task offloading in fog-enabled IoT networks," Pervasive Mob Comput, vol. 74, 2021.
[4] شهرام جمالی، سمیرا حورعلی، «موازنه گر نامتمرکز بار در محیط ابر با بهره گیری از سیاست تصمیم گیری چندشاخصه»، مجله مهندسی برق دانشگاه تبریز، جلد 46، شماره 3، صفحات 106-96، 1395.
[5] Y. Chen, F. Zhao, Y. Lu, and X. Chen, "Dynamic Task Offloading for Mobile Edge Computing with Hybrid Energy Supply," Tsinghua Sci Technol, vol. 28, no. 3, pp. 421–432, 2023, doi: 10.26599/TST.2021.9010050.
[6] A. M. Alwakeel, "An Overview of Fog Computing and Edge Computing Security and Privacy Issues," Sensors, vol. 21, no. 24, Dec. 2021.
[7] M. H. A. A. W. A. H. A. a. M. A. B. Alouffi, "A Systematic Literature Review on Cloud Computing Security: Threats and Mitigation Strategies," IEEE Access, pp. 1–1, 2021.
[8] A. Kishor and C. Chakarbarty, "Task Offloading in Fog Computing for Using Smart Ant Colony Optimization," Wirel Pers Commun, 2021, doi: 10.1007/s11277-021-08714-7.
[9] T. Gao, Q. Tang, J. Li, Y. Zhang, Y. Li, and J. Zhang, "A Particle Swarm Optimization With Lévy Flight for Service Caching and Task Offloading in Edge-Cloud Computing," IEEE Access, vol. 10, pp. 76636–76647, 2022, doi: 10.1109/ACCESS.2022.3192846.
[10] M. Keshavarznejad, M. H. Rezvani, and S. Adabi, "Delay-aware optimization of energy consumption for task offloading in fog environments using metaheuristic algorithms," Cluster Comput, vol. 24, no. 3, pp. 1825–1853, 2021, doi: 10.1007/s10586-020-03230-y.
[11] I. Sarkar, M. Adhikari, N. Kumar, and S. Kumar, "Dynamic Task Placement for Deadline-Aware IoT Applications in Federated Fog Networks," IEEE Internet Things J, vol. 9, no. 2, pp. 1469–1478, 2022, doi: 10.1109/JIOT.2021.3088227.
[12] Z. Wu, B. Li, Z. Fei, Z. Zheng, B. Li, and Z. Han, "Energy-Efficient Robust Computation Offloading for Fog-IoT Systems," IEEE Trans Veh Technol, vol. 69, no. 4, pp. 4417–4425, 2020, doi: 10.1109/TVT.2020.2975056.
[13] L.-A. Phan, D.-T. Nguyen, M. Lee, D.-H. Park, and T. Kim, "Dynamic fog-to-fog offloading in SDN-based fog computing systems," Future Generation Computer Systems, vol. 117, pp. 486–497, 2021, doi: https://doi.org/10.1016/j.future.2020.12.021.
[14] C. Kai, H. Zhou, Y. Yi, and W. Huang,"Collaborative Cloud-Edge-End Task Offloading in Mobile-Edge Computing Networks With Limited Communication Capability," IEEE Trans Cogn Commun Netw, vol. 7, no. 2, pp. 624–634, 2021, doi: 10.1109/TCCN.2020.3018159.
[15] M. Al-khafajiy, T. Baker, H. Al-Libawy, Z. Maamar, M. Aloqaily, and Y. Jararweh, "Improving fog computing performance via Fog-2-Fog collaboration," Future Generation Computer Systems, vol. 100, pp. 266–280, 2019, doi: https://doi.org/10.1016/j.future.2019.05.015.
[16] Z. L. X. W. and Y. L. D. Wang, "Mobility-Aware Task Offloading and Migration Schemes in Fog Computing Networks," IEEE Access, vol. 7, pp. 43356–43368, 2019.
[17] U. Saleem, Y. Liu, S. Jangsher, Y. Li, and T. Jiang, "Mobility-Aware Joint Task Scheduling and Resource Allocation for Cooperative Mobile Edge Computing," IEEE Trans Wirel Commun, vol. 20, no. 1, pp. 360–374, 2021, doi: 10.1109/TWC.2020.3024538.
[18] Y. Jiang and D. H. K. Tsang, "Delay-Aware Task Offloading in Shared Fog Networks," IEEE Internet Things J, vol. 5, no. 6, pp. 4945–4956, 2018, doi: 10.1109/JIOT.2018.2880250.
[19] M. Chen and Y. Hao, "Task Offloading for Mobile Edge Computing in Software Defined Ultra-Dense Network," IEEE Journal on Selected Areas in Communications, vol. 36, no. 3, pp. 587–597, 2018, doi: 10.1109/JSAC.2018.2815360.
[20] I. E. A. C. and A. K. O. Salman, "IoT survey: An SDN and fog computing perspective," Comput. Netw, vol. 143, pp. 221–246, 2018.
[21] S. Misra and S. Bera, "Soft-VAN: Mobility-Aware Task Offloading in Software-Defined Vehicular Network," IEEE Trans Veh Technol, vol. 69, no. 2, pp. 2071–2078, 2020, doi: 10.1109/TVT.2019.2958740.
[22] C. Yang, Y. Liu, X. Chen, W. Zhong, and S. Xie, "Efficient Mobility-Aware Task Offloading for Vehicular Edge Computing Networks," IEEE Access, vol. 7, pp. 26652–26664, 2019, doi: 10.1109/ACCESS.2019.2900530.
[23] A. Bozorgchenani, D. Tarchi, and G. E. Corazza, "Mobile Edge Computing Partial Offloading Techniques for Mobile Urban Scenarios," in 2018 IEEE Global Communications Conference (GLOBECOM), 2018, pp. 1–6. doi: 10.1109/GLOCOM.2018.8647240.
[24] G. Zhang, F. Shen, Z. Liu, Y. Yang, K. Wang, and M.-T. Zhou, "FEMTO: Fair and Energy-Minimized Task Offloading for Fog-Enabled IoT Networks," IEEE Internet Things J, vol. 6, no. 3, pp. 4388–4400, 2019, doi: 10.1109/JIOT.2018.2887229.
[25] Q. C. and J. Z. X. H. X. Yang, "Task Offloading Optimization for UAV-assisted Fog-enabled Internet of Things Networks," IEEE Internet Things J, 2021.
[26] S. Misra and N. Saha, "Detour: Dynamic Task Offloading in Software-Defined Fog for IoT Applications," IEEE Journal on Selected Areas in Communications, vol. 37, no. 5, pp. 1159–1166, 2019, doi: 10.1109/JSAC.2019.2906793.
[27] Sheldon M Ross, Introduction to Probability Models, 11th ed. Boston: USA: Academic Press, 2010.
[28] Liu, J. Zhang, X. Zhang, and W. Wang, "Mobility-Aware Coded Probabilistic Caching Scheme for MEC-Enabled Small Cell Networks," IEEE Access, vol. 5, pp. 17824–17833, 2017, doi: 10.1109/ACCESS.2017.2742555.
[29] A. Asensio et al., "Designing an efficient clustering strategy for combined Fog-to-Cloud scenarios," Future Generation Computer Systems, vol. 109, pp. 392–406, 2020, doi: https://doi.org/10.1016/j.future.2020.03.056.
[30] H. O. Hassan, S. Azizi, and M. Shojafar, "Priority, network and energy-aware placement of IoT-based application services in fog-cloud environments," IET Communications, vol. 14, no. 13, pp. 2117–2129, 2020, doi: https://doi.org/10.1049/iet-com.2020.0007.
[31] I. Lera, C. Guerrero, and C. Juiz, "Availability-Aware Service Placement Policy in Fog Computing Based on Graph Partitions," IEEE Internet Things J, vol. 6, no. 2, pp. 3641–3651, 2019, doi: 10.1109/JIOT.2018.2889511.
[32] A. Younis, B. Qiu, and D. Pompili, "Latency-aware Hybrid Edge Cloud Framework for Mobile Augmented Reality Applications," in 2020 17th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), 2020, pp. 1–9. doi: 10.1109/SECON48991.2020.9158429.
[33] Z. Ning, P. Dong, X. Kong, and F. Xia, "A Cooperative Partial Computation Offloading Scheme for Mobile Edge Computing Enabled Internet of Things," IEEE Internet Things J, vol. 6, no. 3, pp. 4804–4814, 2019, doi: 10.1109/JIOT.2018.2868616.
[34] H. Ma, P. Huang, Z. Zhou, X. Zhang, and X. Chen, "GreenEdge: Joint Green Energy Scheduling and Dynamic Task Offloading in Multi-Tier Edge Computing Systems," IEEE Trans Veh Technol, vol. 71, no. 4, pp. 4322–4335, 2022, doi: 10.1109/TVT.2022.3147027.
[35] M. K. Hussein and M. H. Mousa, "Efficient Task Offloading for IoT-Based Applications in Fog Computing Using Ant Colony Optimization," IEEE Access, vol. 8, pp. 37191–37201, 2020, doi: 10.1109/ACCESS.2020.2975741.
[36] F. Dahan, "An Effective Multi-Agent Ant Colony Optimization Algorithm for QoS-Aware Cloud Service Composition,” IEEE Access, vol. 9, pp. 17196–17207, 2021, doi: 10.1109/ACCESS.2021.3052907.
[37] A. Mseddi, W. Jaafar, H. Elbiaze, and W. Ajib, "Joint Container Placement and Task Provisioning in Dynamic Fog Computing," IEEE Internet Things J, vol. 6, no. 6, pp. 10028–10040, 2019, doi: 10.1109/JIOT.2019.2935056.