Joint computation offloading and parallel scheduling to maximize delay-guarantee in cooperative MEC systems

Abstract

The growing development of the Internet of Things (IoT) is accelerating the emergence and growth of new IoT services and applications, which will result in massive amounts of data being generated, transmitted and processed in wireless communication networks. Mobile Edge Computing (MEC) is a desired paradigm to timely process the data from IoT for value maximization. In MEC, a number of computing-capable devices are deployed at the network edge near data sources to support edge computing, such that the long network transmission delay in cloud computing paradigm could be avoided. Since an edge device might not always have sufficient resources to process the massive amount of data, computation offloading is significantly important considering the cooperation among edge devices. However, the dynamic traffic characteristics and heterogeneous computing capabilities of edge devices challenge the offloading. In addition, different scheduling schemes might provide different computation delays to the offloaded tasks. Thus, offloading in mobile nodes and scheduling in the MEC server are coupled to determine service delay. This paper seeks to guarantee low delay for computation intensive applications by jointly optimizing the offloading and scheduling in such an MEC system. We propose a Delay-Greedy Computation Offloading (DGCO) algorithm to make offloading decisions for new tasks in distributed computing-enabled mobile devices. A Reinforcement Learning-based Parallel Scheduling (RLPS) algorithm is further designed to schedule offloaded tasks in the multi-core MEC server. With an offloading delay broadcast mechanism, the DGCO and RLPS cooperate to achieve the goal of delay-guarantee-ratio maximization. Finally, the simulation results show that our proposal can bound the end-to-end delay of various tasks. Even under slightly heavy task load, the delay-guarantee-ratio given by DGCO-RLPS can still approximate 95%, while that given by benchmarked algorithms is reduced to intolerable value. The simulation results are demonstrated the effectiveness of DGCO-RLPS for delay guarantee in MEC.

Keywords

Edge computing / Computation offloading / Parallel scheduling / Mobile-edge cooperation / Delay guarantee

References

[1] D. Gupta, S. Rani, S.H. Ahmed, S. Verma, M.F. Ijaz, J. Shafi, Edge caching based on collaborative filtering for heterogeneous ICN-IoT applications, Sensors 21 (16) (2021) 5491.

[2] J. Guo, X. Ding, W. Wu, A blockchain-enabled ecosystem for distributed electricity trading in smart city, IEEE Internet Things J. 8 (3) (2021) 2040-2050.

[3] G. Zhu, D. Liu, Y. Du, C. You, J. Zhang, K. Huang, Toward an intelligent edge: wireless communication meets machine learning, IEEE Commun. Mag. 58 (1) (2020) 19-25.

[4] G. Premsankar, M. Di Francesco, T. Taleb, Edge computing for the internet of things: a case study, IEEE Internet Things J. 5 (2) (2018) 1275-1284.

[5] S. Rani, D. Koundal, Kavita, M.F. Ijaz, M. Elhoseny, M.I. Alghamdi, An optimized framework for WSN routing in the context of industry 4.0, Sensors 21 (19) (2021) 6474.

[6] J. Guo, X. Ding, W. Wu, Reliable traffic monitoring mechanisms based on blockchain in vehicular networks, IEEE Trans. Reliab. 71 (3) (2021) 1219-1229.

[7] A.V. Dastjerdi, R. Buyya, Fog computing: helping the internet of things realize its potential, Computer 49 (8) (2016) 112-116.

[8] A. Yousefpour, C. Fung, T. Nguyen, K. Kadiyala, F. Jalali, A. Niakanlahiji, J. Kong, J.P. Jue, All one needs to know about fog computing and related edge computing paradigms: a complete survey, J. Syst. Architect. 98 (2019) 289-330.

[9] W. Shi, J. Cao, Q. Zhang, Y. Li, L. Xu, Edge computing: vision and challenges, IEEE Internet Things J. 3 (5) (2016) 637-646.

[10] Y.C. Hu, M. Patel, D. Sabella, N. Sprecher, V. Young, Mobile Edge Computing a Key Technology towards 5G, ETSI, White Paper, 2015, pp. 1-16.

[11] S. Wang, T. Tuor, T. Salonidis, K.K. Leung, C. Makaya, T. He, K. Chan, Adaptive federated learning in resource constrained edge computing systems, IEEE J. Sel. Area. Commun. 37 (6) (2019) 1205-1221.

[12] R. Deng, R. Lu, C. Lai, T.H. Luan, H. Liang, Optimal workload allocation in fog-cloud computing toward balanced delay and power consumption, IEEE Internet Things J. 3 (6) (2016) 1171-1181.

[13] Y. Miao, G. Wu, M. Li, A. Ghoneim, M. Al-Rakhami, M.S. Hossain, Intelligent task prediction and computation offloading based on mobile-edge cloud computing, Future Generat. Comput. Syst. 102 (2020) 925-931.

[14] Q. Yang, Y. Liu, T. Chen, Y. Tong, Federated machine learning: concept and applications, ACM Trans. Intell. Syst. Technol. 10 (2) (2019) 1-19, 12.

[15] S.M.A. Oteafy, H.S. Hassanein, Leveraging tactile internet cognizance and operation via IoT and edge technologies, Proc. IEEE 107 (2) (2019) 364-375.

[16] A. Alnoman, S.K. Sharma, W. Ejaz, A. Anpalagan, Emerging edge computing technologies for distributed IoT systems, IEEE Network 33 (6) (2019) 140-147.

[17] X. Ding, J. Guo, D. Li, W. Wu, An incentive mechanism for building a secure blockchain-based internet of things, IEEE Trans. Netw. Sci. Eng. 8 (1) (2021) 477-487.

[18] S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: from Theory to Algorithms, Cambridge university press, 2014.

[19] I. Goodfellow, Y. Bengio, A. Courville,Deep Learning, MIT Press, 2016. http://www.deeplearningbook.org.

[20] H. B. McMahan, E. Moore, D. Ramage, B. A. y Arcas, Federated Learning of Deep Networks Using Model Averaging, CoRR abs/1602.05629. arXiv:1602.05629.

[21] M. Guo, Q. Guan, W. Chen, F. Ji, Z. Peng, Delay-optimal scheduling of VMs in a queueing cloud computing system with heterogeneous workloads, IEEE Tran. Serv. Comput. 15 (1) (2022) 110-123.

[22] T. Zhao, S. Zhou, X. Guo, Z. Niu, Tasks scheduling and resource allocation in heterogeneous cloud for delay-bounded mobile edge computing, in: IEEE International Conference on Communications (ICC), IEEE, 2017, pp. 1-7.

[23] S.E. Mahmoodi, R.N. Uma, K.P. Subbalakshmi, Optimal joint scheduling and cloud offloading for mobile applications, IEEE Tran. Cloud Comput. 7 (2) (2019) 301-313.

[24] Z. Ning, X. Wang, J.J.P.C. Rodrigues, F. Xia, Joint computation offloading, power allocation, and channel assignment for 5G-enabled traffic management systems, IEEE Trans. Ind. Inf. 15 (5) (2019) 3058-3067.

[25] Y. Yu, J. Zhang, K.B. Letaief, Joint subcarrier and CPU time allocation for mobile edge computing, in: IEEE Global Communications Conference (GLOBECOM), IEEE, 2016, pp. 1-6.

[26] T.X. Tran, D. Pompili, Joint task offloading and resource allocation for multi-server mobile-edge computing networks, IEEE Trans. Veh. Technol. 68 (1) (2019) 856-868.

[27] J. Zhang, L. Zhou, Q. Tang, E.C.-H. Ngai, X. Hu, H. Zhao, J. Wei, Stochastic computation offloading and trajectory scheduling for UAV-assisted mobile edge computing, IEEE Internet Things J. 6 (2) (2019) 3688-3699.

[28] W. Shi, S. Dustdar, The promise of edge computing, Computer 49 (5) (2016) 78-81.

[29] M. Satyanarayanan, The emergence of edge computing, Computer 50 (1) (2017) 30-39.

[30] M. Mukherjee, S. Kumar, C.X. Mavromoustakis, G. Mastorakis, R. Matam, V. Kumar, Q. Zhang, Latency-driven parallel task data offloading in fog computing networks for industrial applications, IEEE Trans. Ind. Inf. 16 (9) (2020) 6050-6058.

[31] D. Van Le, C. Tham, A deep reinforcement learning based offloading scheme in ad-hoc mobile clouds, in: Proceedings of the 2018 IEEE Conference on Computer Communications Workshops, INFOCOM WKSHPS), 2018, pp. 760-765.

[32] Q. Qi, J. Wang, Z. Ma, H. Sun, Y. Cao, L. Zhang, J. Liao, Knowledge-driven service offloading decision for vehicular edge computing: a deep reinforcement learning approach, IEEE Trans. Veh. Technol. 68 (5) (2019) 4192-4203.

[33] Z. Tong, X. Deng, F. Ye, S. Basodi, X. Xiao, Y. Pan, Adaptive computation offloading and resource allocation strategy in a mobile edge computing environment, Inf. Sci. 537 (2020) 116-131.

[34] J. Liu, Q. Zhang, Offloading schemes in mobile edge computing for ultra-reliable low latency communications, IEEE Access 6 (2018) 12825-12837.

[35] L. Yang, B. Liu, J. Cao, Y. Sahni, Z. Wang, Joint computation partitioning and resource allocation for latency sensitive applications in mobile edge clouds, in: Proceedings of the 10th IEEE International Conference on Cloud Computing (CLOUD), IEEE, 2017, pp. 246-253.

[36] M. Guo, L. Li, Q. Guan, Energy-efficient and delay-guaranteed workload allocation in IoT-edge-cloud computing systems, IEEE Access 7 (2019) 78685-78697.

[37] A. Khairy, H.H. Ammar, R. Bahgat, Smartphone energizer: extending smartphone's battery life with smart offloading,in:Proceedings of the 9th International Wireless Communications and Mobile Computing Conference (IWCMC), IEEE, 2013, pp. 329-336.

[38] M. Hu, L. Zhuang, D. Wu, Y. Zhou, X. Chen, L. Xiao, Learning driven computation offloading for asymmetrically informed edge computing, IEEE Trans. Parall. Distr. 30 (8) (2019) 1802-1815.

[39] J. Liu, Y. Mao, J. Zhang, K.B. Letaief, Delay-optimal computation task scheduling for mobile-edge computing systems, in: Proceedings of 2016 IEEE International Symposium on Information Theory (ISIT), IEEE, 2016, pp. 1451-1455.

[40] S. C. G, V. Chamola, C.-K. Tham, G. S, N. Ansari, An optimal delay aware task assignment scheme for wireless SDN networked edge cloudlets, Future Generat. Comput. Syst. 102 (2020) 862-875.

[41] R. Uhlig, G. Neiger, D. Rodgers, A.L. Santoni, F.C.M. Martins, A.V. Anderson, S. M. Bennett, A. Kagi, F.H. Leung, L. Smith, Intel virtualization technology, Computer 38 (5) (2005) 48-56.

[42] P. Porambage, J. Okwuibe, M. Liyanage, M. Ylianttila, T. Taleb, Survey on multi-access edge computing for internet of things realization, IEEE Commun. Surv. Tut. 20 (4) (2018) 2961-2991.

[43] W. Yu, W. Rhee, S. Boyd, J.M. Cioffi, Iterative water-filling for Gaussian vector multiple-access channels, IEEE Trans. Inf. Theor. 50 (1) (2004) 145-152.

[44] C. Xing, Y. Jing, S. Wang, S. Ma, H.V. Poor, New viewpoint and algorithms for water-filling solutions in wireless communications, IEEE Trans. Signal Process. 68 (2020) 1618-1634.

[45] R.S. Sutton, A.G. Barto, Reinforcement Learning:an Introduction, MIT Press, Cambridge, MA, USA, 1998.

[46] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, K. Simonyan, D. Hassabis, A general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science 362 (6419) (2018) 1140-1144.

[47] D. Silver, A. Huang, C.J. Maddison, et al., Mastering the game of go with deep neural networks and tree search, Nature 529 (2016) 484-489.

[48] H.A. Alameddine, S. Sharafeddine, S. Sebbah, S. Ayoubi, C. Assi, Dynamic task offloading and scheduling for low-latency IoT services in multi-access edge computing, IEEE J. Sel. Area. Commun. 37 (3) (2019) 668-682.

[49] M. Mukherjee, M. Guo, J. Lloret, Q. Zhang, Leveraging intelligent computation offloading with fog/edge computing for tactile internet: advantages and limitations, IEEE Network 34 (5) (2020) 322-329.

[50] H. Tataria, M. Shafi, A.F. Molisch, M. Dohler, H. Sjöland, F. Tufvesson, 6G wireless systems: vision, requirements, challenges, insights, and opportunities, Proc. IEEE 109 (7) (2021) 1166-1199.

[51] Z. Xiao, X. Dai, H. Jiang, D. Wang, H. Chen, L. Yang, F. Zeng, Vehicular task offloading via heat-aware MEC cooperation using game-theoretic method, IEEE Internet Things J. 7 (3) (2020) 2038-2052.

[52] M.J. Neely, Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan and Claypool Publishers, 2010.

[53] J. Kurose, K. Ross, Computer Networking: A Top-Down Approach 7th, Pearson Education, Boston, MA, 2016.