POST: Parallel Offloading of Splittable Tasks in Heterogeneous Fog Networks

摘要

Fog computing has been promoted to support delay-sensitive applications in future Internet of Things (IoT). For a general heterogeneous fog network consisting of many dispersive fog nodes (FNs), it may well happen that some of them have delay-sensitive tasks to process, i.e., task nodes (TNs), and some have spare resources to help the TNs to process tasks, i.e., helper nodes (HNs). It remains a fundamental challenge to effectively map multiple tasks or TNs into multiple HNs to minimize every task's service delay in a distributed manner, i.e., the multitask multihelper (MTMH) problem. The problem becomes more challenging as tasks are splittable, i.e., tasks can be divided into multiple subtasks and offloaded to multiple HNs to further reduce the service delay via the scheme similar to distributed computing, because it introduces the more complicated task division problem which results in a much larger and more complex solution space. To tackle this challenge, in this article, a generalized Nash equilibrium problem (GNEP), called parallel offloading of splittable tasks (POST), is formulated and studied thoroughly. The structural properties of the problem are characterized and thus the existence of generalized Nash equilibrium (GNE) is proven via the fixed-point theorem. Furthermore, the corresponding distributed task offloading algorithm is developed via the Gauss-Seidel-type method. The simulation results show that the proposed POST algorithm can offer much better performance in terms of the system average delay, individual delay, delay reduction ratio (DRR), and number of beneficial TNs, compared with the existing solution to the counterpart problem for nonsplittable tasks.