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.

Department of Electrical and Computer Engineering COMSATS University Islamabad Islamabad 45550 Pakistan

Department of Electrical Engineering National University of Science and Technology Islamabad 44000 Pakistan

Department of Quantitative Methods and Economic Informatics Faculty of Operation and Economics of Transport and Communications University of Zilina 01026 Zilina Slovakia

Department of Telecommunications Faculty of Electrical Engineering and Computer Science VSB Technical University of Ostrava 70800 Ostrava Czech Republic

Interdisciplinary Centre for Security Reliability and Trust University of Luxembourg 1855 Luxembourg Luxembourg

Zobrazit více v PubMed

Giordani M., Polese M., Mezzavilla M., Rangan S., Zorzi M. Toward 6G Networks: Use Cases and Technologies. IEEE Commun. Mag. 2020;58:55–61. doi: 10.1109/MCOM.001.1900411. DOI

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. doi: 10.1109/TITS.2021.3110942. DOI

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. doi: 10.1109/JIOT.2021.3068056. DOI

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. doi: 10.1016/j.jksuci.2022.05.016. DOI

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. doi: 10.1109/JSYST.2022.3194705. DOI

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 doi: 10.1109/TII.2022.3151773. DOI

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. doi: 10.1109/JIOT.2022.3155667. DOI

Javed M.A., Zeadally S., Hamida E.B. Data analytics for Cooperative Intelligent Transport Systems. Veh. Commun. 2019;15:63–72. doi: 10.1016/j.vehcom.2018.10.004. DOI

Javed M.A., Zeadally S. AI-Empowered Content Caching in Vehicular Edge Computing: Opportunities and Challenges. IEEE Netw. 2021;35:109–115. doi: 10.1109/MNET.011.2000561. DOI

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. doi: 10.23919/JCC.2019.11.004. DOI

Farooq U., Shabir M.W., Javed M.A., Imran M. Intelligent energy prediction techniques for fog computing networks. Appl. Soft Comput. 2021;111:107682. doi: 10.1016/j.asoc.2021.107682. DOI

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. doi: 10.1109/TPDS.2021.3067654. DOI

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. doi: 10.1109/JIOT.2018.2871251. DOI

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; pp. 413–418. DOI

Alimudin A., Ishida Y. Matching-Updating Mechanism: A Solution for the Stable Marriage Problem with Dynamic Preferences. Entropy. 2022;24:263. doi: 10.3390/e24020263. PubMed DOI PMC

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. doi: 10.1007/BF01211824. DOI

Roth A.E. Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions. National Bureau of Economic Research; Cambridge, MA, USA: 2007. Working Paper 13225. DOI

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. doi: 10.1109/TWC.2019.2922613. DOI

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. doi: 10.1109/JIOT.2018.2887229. DOI

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. doi: 10.1109/TPDS.2020.3042224. DOI

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. doi: 10.1002/ett.3818. DOI

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. doi: 10.1109/ACCESS.2021.3061105. DOI

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. doi: 10.1109/JIOT.2018.2868616. DOI

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. doi: 10.1109/TNSM.2019.2937342. DOI

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. doi: 10.1109/JSYST.2021.3085566. DOI

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. doi: 10.1109/JIOT.2020.2965566. DOI

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; pp. 1–5. DOI

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; pp. 661–663. DOI

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; pp. 1–6. DOI

Roth A., Vande Vate J. Random Paths to Stability in Two-Sided Matching. Econometrica. 1990;58:1475–1480. doi: 10.2307/2938326. DOI

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. doi: 10.1109/ACCESS.2021.3092819. DOI

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. doi: 10.1109/TVT.2016.2593486. DOI

Bertsimas D., Tsitsiklis J.N. Introduction to Linear Optimization. Volume 6 Athena Scientific; Belmont, MA, USA: 1997.

Baïou M., Balinski M. Many-to-many matching: Stable polyandrous polygamy (or polygamous polyandry) Discret. Appl. Math. 2000;101:1–12. doi: 10.1016/S0166-218X(99)00203-6. DOI

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. doi: 10.1109/JIOT.2021.3075673. DOI

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. doi: 10.1109/JIOT.2020.3025631. DOI