Matching Theory based Efficient Task Offloading Strategies in IoT-Fog Networks

Abstract

Task offloading enables Internet of Things (IoT) devices with constrained resources to transfer tasks to remote Cloud/Fog Nodes (FNs), facilitating the execution of time-sensitive services. The delegation of tasks for real-time services, including industrial automation, online gaming, video streaming, virtual reality, augmented reality, and smart healthcare, to a distant cloud server results in undesirable delays. The factors contributing to these delays are intermittent communication channels, considerable physical distances between IoT devices and the Cloud, and the limited availability of spectrum resources. Thus, transferring tasks to nearby FNs proves more advantageous as it brings about numerous benefits, including improved latency, improved energy efficiency, higher scalability, and reduced costs. Nevertheless, the act of offloading tasks to FNs presents several notable research challenges: (i.) the allocation of limited FN resources, (ii.) adherence to maximum tolerable delay constraints for heterogeneous services, and (iii.) the necessity for computationally inexpensive and scalable strategies. Additionally, the task offloading problem has been established as NP-Hard problem. In this regard, the initial contribution introduces three protocols based on matching theory. These models utilize different variations of the Deferred Acceptance Algorithm (DAA) with maximum and minimum quotas at FN. The objectives of these protocols are to minimize the average offloading delay and outages caused by non-cluster assignments. Note that outages mean offloading delay of the task overshooting its prescribed tolerable delay. The initial protocol, called Artificial cap Deferred Acceptance based Fair Task Offloading A-DAFTO, incorporates an additional quota at FN, i.e., artificial quota, to provide a non-cluster allocation with a relatively balanced distribution. Imposition of artificial quotas at FNs can result in inefficient utilization of computationally efficient FNs, deleteriously impacting the objectives. To address this limitation, another matching-based protocol is devised, referred to as Multistage Deferred Acceptance Fair Task Offloading M-DAFTO. In this approach, the FN operates only with maximum and minimum quotas. Furthermore, enforcing the strict processing order of tasks in M-DAFTO is achieved by utilizing a Precedence List (PL) as input. It appears that M-DAFTO yields superior outcomes compared to A-DAFTO, but this configuration needs to be revised as it fails to fully exploit the potential of all the computationally efficient FNs inside the network with a restrictive environment. Hence, an alternative protocol, Extended Deferred Acceptance Fair Task Offloading E-DAFTO, is developed that does not impose strict task processing orders. This suggests that the tasks can propose the FNs in any processing order, demonstrating flexibility without compromising the objectives. All the protocols mentioned above have the following pitfalls: (i.) outcome of each protocol is partially stable, (ii.) the energy consumption at IoTs and FNs is discarded while taking offloading decision. The subsequent contribution introduces a framework Deferred Acceptance based Strongly Stable Task Offloading DASTO to rectify the limitations identified in the preceding contribution. The proposed approach in this study involves adopting a many-to-one matching-based offloading technique. This strategy considers the maximum quota of the FN and aims to provide a strongly stable matching that addresses the first issue. The second problem is addressed by considering energy usage in the context of the IoT and FN while making offloading decisions. Despite generating a strongly stable assignment, DASTO exhibits certain deficiencies. (i.) User cost should be considered in the decision-making process of offloading, potentially leading to a better Quality of Services (QoS) experienced by end users. (ii.) In a multiple Service Providers (SPs) scenario where they deploy the FNs, DASTO may not perform efficiently. To address the challenges associated with DASTO, the third contribution introduces a framework known as a Student Project Allocation based Strongly stable Task Offloading (SPASTO) model. This framework utilizes a Student Project Allocation Algorithm (SPAA). SPASTO provides a strongly stable matching plan and minimizes not only the average offloading delay, outages, and average offloading energy but also the total user cost.