[en] Fog computing is one of the major components of future 6G networks. It can provide fast computing of different application-related tasks and improve system reliability due to better decision-making. Parallel offloading, in which a task is split into several sub-tasks and transmitted to different fog nodes for parallel computation, is a promising concept in task offloading. Parallel offloading suffers from challenges such as sub-task splitting and mapping of sub-tasks to the fog nodes. In this paper, we propose a novel many-to-one matching-based algorithm for the allocation of sub-tasks to fog nodes. We develop preference profiles for IoT nodes and fog nodes to reduce the task computation delay. We also propose a technique to address the externalities problem in the matching algorithm that is caused by the dynamic preference profiles. Furthermore, a detailed evaluation of the proposed technique is presented to show the benefits of each feature of the algorithm. Simulation results show that the proposed matching-based offloading technique outperforms other available techniques from the literature and improves task latency by 52% at high task loads.
Disciplines :
Ingénierie électrique & électronique
Auteur, co-auteur :
Malik, Usman Mahmood
Javed, Muhammad Awais
Frnda, Jaroslav
Rozhon, Jan
KHAN, Wali Ullah ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > SigCom
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Efficient Matching-Based Parallel Task Offloading in IoT Networks
Titre traduit :
[en] Efficient Matching-Based Parallel Task Offloading in IoT Networks
Date de publication/diffusion :
13 septembre 2022
Titre du périodique :
Sensors
ISSN :
1424-8220
eISSN :
1424-3210
Maison d'édition :
Multidisciplinary Digital Publishing Institute (MDPI), Basel, Suisse
Giordani M. Polese M. Mezzavilla M. Rangan S. Zorzi M. Toward 6G Networks: Use Cases and Technologies IEEE Commun. Mag. 2020 58 55 61 10.1109/MCOM.001.1900411
Khan W.U. Javed M.A. Nguyen T.N. Khan S. Elhalawany B.M. Energy-Efficient Resource Allocation for 6G Backscatter-Enabled NOMA IoV Networks IEEE Trans. Intell. Transp. Syst. 2021 23 9775 9785 10.1109/TITS.2021.3110942
Malik U.M. Javed M.A. Zeadally S. Islam S.u. Energy efficient fog computing for 6G enabled massive IoT: Recent trends and future opportunities IEEE Internet Things J. 2021 9 14572 14594 10.1109/JIOT.2021.3068056
Ahmed M. Raza S. Mirza M.A. Aziz A. Khan M.A. Khan W.U. Li J. Han Z. A survey on vehicular task offloading: Classification, issues, and challenges J. King Saud Univ. Comput. Inf. Sci. 2022 34 4135 4162 10.1016/j.jksuci.2022.05.016
Ahmed M. Khan W.U. Ihsan A. Li X. Li J. Tsiftsis T.A. Backscatter Sensors Communication for 6G Low-Powered NOMA-Enabled IoT Networks Under Imperfect SIC IEEE Syst. J. 2022 1 11 10.1109/JSYST.2022.3194705
Javed M.A. Nguyen T.N. Mirza J. Ahmed J. Ali B. Reliable Communications for Cybertwin driven 6G IoVs using Intelligent Reflecting Surfaces IEEE Trans. Ind. Inform. 2022 10.1109/TII.2022.3151773
Liu J. Ahmed M. Mirza M.A. Khan W.U. Xu D. Li J. Aziz A. Han Z. RL/DRL Meets Vehicular Task Offloading Using Edge and Vehicular Cloudlet: A Survey IEEE Internet Things J. 2022 9 8315 8338 10.1109/JIOT.2022.3155667
Javed M.A. Zeadally S. Hamida E.B. Data analytics for Cooperative Intelligent Transport Systems Veh. Commun. 2019 15 63 72 10.1016/j.vehcom.2018.10.004
Javed M.A. Zeadally S. AI-Empowered Content Caching in Vehicular Edge Computing: Opportunities and Challenges IEEE Netw. 2021 35 109 115 10.1109/MNET.011.2000561
Xie J. Jia Y. Chen Z. Nan Z. Liang L. Efficient task completion for parallel offloading in vehicular fog computing China Commun. 2019 16 42 55 10.23919/JCC.2019.11.004
Farooq U. Shabir M.W. Javed M.A. Imran M. Intelligent energy prediction techniques for fog computing networks Appl. Soft Comput. 2021 111 107682 10.1016/j.asoc.2021.107682
Tran-Dang H. Kim D.S. FRATO: Fog Resource Based Adaptive Task Offloading for Delay-Minimizing IoT Service Provisioning IEEE Trans. Parallel Distrib. Syst. 2021 32 2491 2508 10.1109/TPDS.2021.3067654
Chiti F. Fantacci R. Picano B. A Matching Theory Framework for Tasks Offloading in Fog Computing for IoT Systems IEEE Internet Things J. 2018 5 5089 5096 10.1109/JIOT.2018.2871251
Liu Z. Wang K. Li K. Zhou M.T. Yang Y. Parallel Scheduling of Multiple Tasks in Heterogeneous Fog Networks Proceedings of the 2019 25th Asia-Pacific Conference on Communications (APCC), Ho Chi Minh Vietnam 6–8 November 2019 413 418 10.1109/APCC47188.2019.9026469
Alimudin A. Ishida Y. Matching-Updating Mechanism: A Solution for the Stable Marriage Problem with Dynamic Preferences Entropy 2022 24 263 10.3390/e24020263
Knuth D.E. Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms American Mathematical Society Providence, RI, USA 1997
Ma J. On Randomized Matching Mechanisms Econ. Theory 1996 8 377 381 10.1007/BF01211824
Roth A.E. Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions Working Paper 13225 National Bureau of Economic Research Cambridge, MA, USA 2007 10.3386/w13225
Liang Z. Liu Y. Lok T.M. Huang K. Multiuser Computation Offloading and Downloading for Edge Computing With Virtualization IEEE Trans. Wirel. Commun. 2019 18 4298 4311 10.1109/TWC.2019.2922613
Zhang G. Shen F. Liu Z. Yang Y. Wang K. Zhou M. FEMTO: Fair and Energy-Minimized Task Offloading for Fog-Enabled IoT Networks IEEE Internet Things J. 2019 6 4388 4400 10.1109/JIOT.2018.2887229
Sahni Y. Cao J. Yang L. Ji Y. Multi-Hop Multi-Task Partial Computation Offloading in Collaborative Edge Computing IEEE Trans. Parallel Distrib. Syst. 2021 32 1133 1145 10.1109/TPDS.2020.3042224
Li H. Li X. Wang W. Joint optimization of computation cost and delay for task offloading in vehicular fog networks Trans. Emerg. Telecommun. Technol. 2020 31 e3818 10.1002/ett.3818
Zhang H. Yang Y. Huang X. Fang C. Zhang P. Ultra-Low Latency Multi-Task Offloading in Mobile Edge Computing IEEE Access 2021 9 32569 32581 10.1109/ACCESS.2021.3061105
Ning Z. Dong P. Kong X. Xia F. A Cooperative Partial Computation Offloading Scheme for Mobile Edge Computing Enabled Internet of Things IEEE Internet Things J. 2019 6 4804 4814 10.1109/JIOT.2018.2868616
Thai M.T. Lin Y.D. Lai Y.C. Chien H.T. Workload and Capacity Optimization for Cloud-Edge Computing Systems with Vertical and Horizontal Offloading IEEE Trans. Netw. Serv. Manag. 2020 17 227 238 10.1109/TNSM.2019.2937342
Deb P.K. Misra S. Mukherjee A. Latency-Aware Horizontal Computation Offloading for Parallel Processing in Fog-Enabled IoT IEEE Syst. J. 2021 16 2537 2544 10.1109/JSYST.2021.3085566
Liu Z. Yang Y. Wang K. Shao Z. Zhang J. POST: Parallel Offloading of Splittable Tasks in Heterogeneous Fog Networks IEEE Internet Things J. 2020 7 3170 3183 10.1109/JIOT.2020.2965566
Zu Y. Shen F. Yan F. Shen L. Qin F. Yang R. SMETO: Stable Matching for Energy-Minimized Task Offloading in Cloud-Fog Networks Proceedings of the 2019 IEEE 90th Vehicular Technology Conference (VTC2019-Fall) Honolulu, HI, USA 22–25 September 2019 1 5 10.1109/VTCFall.2019.8891292
Tran-Dang H. Kim D.S. Impact of Task Splitting on the Delay Performance of Task Offloading in the IoT-enabled Fog Systems Proceedings of the 2021 International Conference on Information and Communication Technology Convergence (ICTC) Jeju Island, Korea 19–21 October 2021 661 663 10.1109/ICTC52510.2021.9620809
Bozorgchenani A. Tarchi D. Corazza G. An Energy and Delay-Efficient Partial Offloading Technique for Fog Computing Architectures Proceedings of the GLOBECOM 2017—2017 IEEE Global Communications Conference Singapore 4–8 December 2017 1 6 10.1109/GLOCOM.2017.8254703
Roth A. Vande Vate J. Random Paths to Stability in Two-Sided Matching Econometrica 1990 58 1475 1480 10.2307/2938326
Basir R. Qaisar S. Ali M. Naeem M. Cloudlet Selection in Cache-Enabled Fog Networks for Latency Sensitive IoT Applications IEEE Access 2021 9 93224 93236 10.1109/ACCESS.2021.3092819
Lyu X. Tian H. Sengul C. Zhang P. Multiuser Joint Task Offloading and Resource Optimization in Proximate Clouds IEEE Trans. Veh. Technol. 2017 66 3435 3447 10.1109/TVT.2016.2593486
Bertsimas D. Tsitsiklis J.N. Introduction to Linear Optimization Athena Scientific Belmont, MA, USA 1997 Volume 6
Baïou M. Balinski M. Many-to-many matching: Stable polyandrous polygamy (or polygamous polyandry) Discret. Appl. Math. 2000 101 1 12 10.1016/S0166-218X(99)00203-6
Wu H. Zhang J. Cai Z. Ni Q. Zhou T. Yu J. Chen H. Liu F. Resolving Multi-task Competition for Constrained Resources in Dispersed Computing: A Bilateral Matching Game IEEE Internet Things J. 2021 8 16972 16983 10.1109/JIOT.2021.3075673
Swain C. Sahoo M.N. Satpathy A. Muhammad K. Bakshi S. Rodrigues J.J.P.C. de Albuquerque V.H.C. METO: Matching-Theory-Based Efficient Task Offloading in IoT-Fog Interconnection Networks IEEE Internet Things J. 2021 8 12705 12715 10.1109/JIOT.2020.3025631
