زمان‌بندی مبتنی بر اولویت وظایف با استفاده از سیستم فازی در محاسبات لبه سیار
محورهای موضوعی : مهندسی برق و کامپیوترانتصار حسینی 1 , محسن نیک رای 2 * , شمس اله قنبری 3
1 - دانشگاه قم
2 - دانشگاه قم
3 - دانشگاه آزاد واحد آشتیان
کلید واژه: محاسبات لبه سیار, زمان‌بندی, حریصانه, فازی, انرژی مصرفی, زمان انتظار,
چکیده مقاله :
محاسبات لبه سیار، تکنولوژی نوینی برای بهبود مشکل تأخیر، ظرفیت و منابع موجود در محیط محاسبات ابری سیار است. هدف اصلی در محاسبات لبه سیار، زمان‌بندی پویا و بارگذاری بهینه با کمترین هزینه در استفاده از منابع است. ما در این مقاله، از یک مدل سیستم سه‌سطحی دستگاه‌های سیار، لبه و ابر استاندارد، استفاده و دو الگوریتم بارگذاری و زمان‌بندی را پیشنهاد می‌کنیم. یک الگوریتم تصمیم‌گیری برای بارگذاری وظایف مبتنی بر الگوریتم کوله‌پشتی حریصانه در سمت دستگاه سیار است که وظایف با انرژی مصرفی بالا را برای بارگذاری انتخاب می‌کند و باعث صرفه‌جویی در انرژی مصرفی دستگاه می‌شود. همچنین در سمت MEC، یک الگوریتم زمان‌بندی پویا را با اولویت‌بندی وظایف مبتنی بر فازی جهت اولویت‌بندی و زمان‌بندی وظایف بر اساس دو معیار ارائه می‌کنیم. نتایج عددی نشان می‌دهند که کار ارائه‌شده در مقایسه با سایر روش‌ها باعث کاهش زمان انتظار وظایف برای اجرا، تأخیر و بار سیستم می‌شود و تعادل سیستم با کمترین تعداد منابع تأمین می‌گردد و سیستم ارائه‌شده، مصرف باتری را در دستگاه هوشمند تا حدود 90% کاهش می‌دهد. نتایج نشان می‌دهند که بیش از 92% وظایف با موفقیت در محیط لبه اجرا می‌شوند.
Mobile edge computing (MEC) are new issues to improve latency, capacity and available resources in Mobile cloud computing (MCC). Mobile resources, including battery and CPU, have limited capacity. So enabling computation-intensive and latency-critical applications are important issue in MEC. In this paper, we use a standard three-level system model of mobile devices, edge and cloud, and propose two offloading and scheduling algorithms. A decision-making algorithm for offloading tasks is based on the greedy Knapsack offloading algorithm (GKOA) on the mobile device side, which selects tasks with high power consumption for offloading and it saves energy consumption of the device. On the MEC side, we also present a dynamic scheduling algorithm with fuzzy-based priority task scheduling (FPTS) for prioritizing and scheduling tasks based on two criteria. Numerical results show that our proposed work compared to other methods and reduces the waiting time, latency and system overhead. Also, provides the balance of the system with the least number of resources. And the proposed system reduces battery consumption in the smart device by up to 90%. The results show that more than 92% of tasks are executed successfully in the edge environment.
[1] J. Huang, C. C. Xing, and C. Wang, "Simultaneous wireless information and power transfer: technologies, applications, and research challenges," IEEE Communications Magazine, vol. 55, no. 11, pp. 26-32, Nov. 2017.
[2] K. Zhang, et al., "Energy-efficient offloading for mobile edge computing in 5g heterogeneous networks," IEEE Access, vol. 4, pp. 5896-5907, 2016.
[3] Y. Sun, J. Li, X. Fu, H. Wang, and H. Li, "Application research based on improved genetic algorithm in cloud task scheduling," Journal of Intelligent & Fuzzy Systems, vol. 38, no. 1, pp. 239-246, Jan. 2020.
[4] G. Li, J. Wang, J. Wu, and J. Song, "Data processing delay optimization in mobile edge computing," Wireless Communications and Mobile Computing, vol. 2018, Article ID: 6897523, 9 pp., 2018.
[5] W. Zhimin, Z. Qinglin, X. Fangxin, D. Hongning, and Z. Yujun, "Detection performance of packet arrival under downclocking for mobile edge computing," Wireless Communications and Mobile Computing, vol. 2018, Article ID: 9641712, 2018.
[6] W. Yu, et al., "A survey on the edge computing for the Internet of things," IEEE Access, vol. 6, pp. 6900-6919, 2018.
[7] Y. Guo, et al., "Distributed machine learning for multiuser mobile edge computing systems," IEEE J. of Selected Topics in Signal Processing, vol. 16, no. 3, pp. 460-473, Apr. 2022.
[8] Z. Jiao, et al., "Energy-latency trade-off for energy-aware offloading in mobile edge computing networks," IEEE Internet of Things J., vol. 5, no. 4, pp. 2633-2645, Aug. 2018.
[9] A. Selvaraj and S. Sundararajan, "Evidence-based trust evaluation system for cloud services using fuzzy logic," International J. of Fuzzy Systems, vol. 19, no. 2, pp. 329-37, Apr. 2017.
[10] M. Fonseca, U. H. Bezerra, J. D. Brito, J. C. Leite, and M. H. Nascimento, "Pre-dispatch of load in thermoelectric power plants considering maintenance management using fuzzy logic," IEEE Access, vol. 6, pp. 41379-41390, 2018.
[11] K. Wang, K. Yang, and C. Magurawalage, "Joint energy minimization and resource allocation in C-RAN with mobile cloud," IEEE Trans. Cloud Comput, vol. 6, no. 3, pp. 331-346, Jul./ Sept. 2017.
[12] Y. Mao, J. Zhang, and K. B. Letaief, "Dynamic computation offloading for mobileedge computing with energy harvesting devices," IEEE J. Sel. Areas Commun, vol. 34, no. 12, pp. 3590-3605, Dec. 2016.
[13] H. Kchaou, Z. Kechaou, and A. M. Alimi, "Towards an offloading framework based on big data analytics in mobile cloud computing environments," Procedia Comput. Sci., vol. 53, pp. 292-297, 2015.
[14] S. Misra and S. Sarkar, "Theoretical modeling of fog computing: a green computing paradigm to support IoT applications," IET Networks, vol. 5, no. 2, pp. 23-29, Mar. 2016.
[15] L. Yang, J. Cao, H. Cheng, and Y. Ji, "Multi-user computation partitioning for latencysensitive mobile cloud applications," IEEE Trans.Computers, vol. 64, no. 8, pp. 2253-2266, Aug. 2015.
[16] G. Shuaishuai, W. Dalei, Z. Haixia, and Y. Dongfeng, "Resource modeling and scheduling for mobile edge computing: a service provider's perspective," IEEE Access, vol. 6, pp. 35611-35623, 2018.
[17] Z. Wenchen, et al., "Markov approximation for task offloading and computation scaling in mobile edge computing," Mobile Information Systems, vol. 2019, Article ID: 8172698, 2019.
[18] T. Chia Wei, T. Fan Hsun, Y. Yao Tsung, L. Chien Chang, and C. LiDer, "Task scheduling for edge computing with agile VNFs on-demand service model toward 5G and beyond," Wireless Communications and Mobile Computing, vol. 2018, Article ID: 7802797, 2018.
[19] Y. Yibo, M. Yongkui, X. Wei, G. Xuemai, and Z. Honglin, "Joint optimization of energy consumption and packet scheduling for mobile edge computing in cyber-physical networks," IEEE Access, vol. 6, pp. 15576-15586, 2018.
[20] W. Yuan, et al., "NOMA-Assisted multi-access mobile edge computing: a joint optimization of computation offloading and time allocation," IEEE Trans. on Vehicular Technology, vol. 67, no. 12, pp. 12244-12258, Dec. 2018.
[21] A. Aghababaeipour and S. Ghanbari, " A new adaptive energy-aware job scheduling in cloud computing," in Proc. Int. Conf. on Soft Computing and Data Mining, pp. 308-317, Senai, Malaysia, 5-7 Feb. 2018.
[22] S. Ghanbari and M. Othman, "Time cheating in divisible load scheduling: sensitivity analysis, results and open problems," Procedia Computer Science, pp. 935-943, vol. 1, no. 125, Jan. 2018.
[23] Y. Changyan, C. Jun, and S. Zhou, "A multi-user mobile computation offloading and transmission scheduling mechanism for delay sensitive application," IEEE Trans. on Mobile Computing, vol. 19, no. 2, pp. 99-110, Jan. 2018.
[24] D. Yueyue, X. Du, M. Sabita, and Y. Zhang, "Joint computation offloading and user association in multi-task mobile edge computing," IEEE Trans. on Vehicular Technology, vol. 67, no. 12, pp. 12313-12325, Dec. 2018.
[25] X. Chen, J. Lei, L. Wenzhong, and F. Xiaoming, "Efficient multi-user computation offloading for mobile-edge cloud computing," IEEE/ACM Trans. on Networking, vol. 24, no. 5, pp. 2795-2808, Oct. 2016.
[26] C. Ying, Z. Ning, Z. Yongchao, and C. Xin, "Dynamic computation offloading in edge computing for the Internet of Things," IEEE Internet of Things J., vol. 6, no. 3, pp. 239-251, Jun. 2019.
[27] N. Zhaolong, D. Peiran, K. Xiangjie, and X. Feng, "A cooperative partial computation offloading scheme for mobile edge computing enabled Internet of Things," IEEE Internet of Things J., vol. 6, no. 3, pp. 4804-4814, Jun. 2019.
[28] Y. Zhang, D. Niyato, and P. Wang, "Offloading in mobile cloudlet systems with intermittent connectivity," IEEE Trans. Mobile Computing, vol. 14, no. 12, pp. 2516-2529, Dec. 2015.
[29] L. Tianze, W. Muqing, Z. Min, and L. Wenxing, "An overhead optimizing task scheduling strategy for ad hoc based mobile edge computing," IEEE Access, vol. 5, pp. 5609-5622, 2017.
[30] R. Morabito and N. Beijar, "Enabling data processing at the network edge through lightweight visualization technologies," in Proc. of the IEEE Int. Conf. on Sensing, Communication, and Networking, SECON Workshops, 6 pp., London, UK, Jun. 2016.
[31] H. Wang, J. Gong, Y. Zhuang, H. Shen, and J. Lach, "Health edge: task scheduling for edge computing with health emergency and human behavior consideration in smart homes," in Proc. of the IEEE Int. Conf. on Big Data, pp. 1213-1222, Shenzhen, China, 7-9 Aug. 2017.
[32] P. Samal and P. Mishra, "Analysis of variants in round robin algorithms for load balancing in cloud computing," International J. of Computer Science and Information Technologies, vol. 4, no. 3, pp. 416-419, 2013.
[33] C. You, Y. Mao, J. Zhang, and K. Huang, "Energy-efficient offloading for mobile edge computing," In Wiley 5G Ref: The Essential 5G Reference Online, 2016.
[34] J. Maozhu, W. Hua, S. Lijun, L. Yuxue, and Z. Yucheng, "Man-machine dialog system optimization based on cloud computing," Personal and Ubiquitous Computing, vol. 22, no. 5-6, pp. 937-942, Oct. 2018.
[35] J. Wang, J. Peng, Y. Wei, D. Liu, and F. Jielin, "Adaptive application offloading decision and transmission scheduling for mobile cloud computing," in Proc. IEEE Int. Conf. on Communications, ICC’26, 7 pp., Kuala Lumpur, Malaysia, 22-27 May 2016.
[36] F. Scott, K. Carlenri, Y. Di, B. George, and K. Mellow, "An analysis of vehicular wireless channel communication via queueing theory model," in Proc. IEEE Int. Conf. on Communications, pp. 1736-1741, Sydney, Australia, 10-14 Jun. 2014.
[37] L. Tong, Y. Li, and W. Gao, "A hierarchical edge cloud architecture for mobile computing," in Proc. 35th Annual IEEE Int. Conf. on Computer Communications, IEEE INFOCOM’16, 9 pp., San Francisco, CA, USA, 10-14 Apr. 2016.
[38] X. Chen, L. Pu, L. Gao, W. Wu, and D. Wu., "Exploiting massive D2D collaboration for energy-efficient mobile edge computing," IEEE Wireless Communications, vol. 24, no. 4, pp. 64-71, Aug. 2017.
[39] A. Salehan, H. Deldari, and S. Abrishami, "An online context-aware mechanism for computation offloading in ubiquitous and mobile cloud environments," The J. of Supercomputing, vol. 75, no. 7, pp. 1-41, Ju.. 2019.
[40] M. Al-Zinati, R. Alrashdan, B. Al-Duwairi, and M. Aloqaily, "A reorganizing biosurveillance framework based on fog and mobile edge computing," Multimedia Tools and Applications, vol. 80, no. 11, pp. 16805-16825, 2021.
[41] S. Deng, et al., "Burst load evacuation based on dispatching and scheduling in distributed edge networks," IEEE Trans. on Parallel and Distributed Systems, vol. 32, no. 8, pp. 1918-1932, Aug. 2021.
[42] F. Jazayeri, A. Shahidinejad, and M. Ghobaei-Arani, "Autonomous computation offloading and auto-scaling the in the mobile fog computing: a deep reinforcement learning-based approach," J. of Ambient Intelligence and Humanized Computing, vol. 12, pp. 8265-8284, 2021.
[43] J. C. Guevara and N. L. da Fonseca, "Task scheduling in cloud-fog computing systems," Peer-to-Peer Networking and Applications, vol. 14, no. 2, pp. 962-977, 2021.
[44] T. D. Lee, B. M. Lee, and W. Noh, "Hierarchical cloud computing architecture for contextaware IoT services," IEEE Trans. Consume Electron, vol. 64, no. 2, pp. 222-230, May2018.
[45] Y. Shi, S. Chen, and X. Xu, "MAGA: a mobility-aware computation offloading decision for distributed mobile cloud computing," IEEE Internet of Things, vol. 5, no. 1, pp. 164-174, Feb. 2018.
[46] M. Goudarzi, M. Zamani, and A. Toroghi Haghighat, "A genetic-based decision algorithm for multisite computation offloading in mobile cloud computing," Int J. Commun Syst, vol. 30, no. 10, Article ID: e3241, Jul. 2017.
[47] A. Raneetha, H. Moshe, O. Binyamin, and Z. Ilze, "Strategic bidding in a discrete accumulating priority queue," Operations Research Letters, vol. 47, no. 3, pp. 162-167, May 2019.
[48] J. Yuan and Y. Li, "Solving binary multi-objective knapsack problems with novel greedy strategy," Memetic Comp., vol. 13, pp. 447-458, 2021.
[49] V. Kumar and K. Dinesh, "Transitive blocks and their applications in fuzzy interconnection networks," Fuzzy Sets and Systems, vol. 352, pp. 142-160, Dec. 2018.
[50] Y. Mao, J. Zhang, S. H. Song, and K. B. Letaief, "Power-delay tradeoff in multi-user mobile-edge computing systems," in Proc. IEEE Global Communication. Conf., GLOBECOM’16, 6 pp., Washington, DC, USA, 4-8 Dec. 2016.
[51] R. Gopi, S. T. Suganthi, R. Rajadevi, et al., "An enhanced green cloud based queue management (GCQM) system to optimize energy consumption in mobile edge computing," Wireless Pers Commun, vol. 117, pp. 3397-3419, 2021.
[52] P. Zou, O. Ozel, and S. Subramaniam, "Optimizing information freshness through computation-transmission tradeoff and queue management in edge computing," IEEE/ACM Trans. on Networking, vol. 29, no. 2, pp. 949-963, Apr. 2021.