Delay-Sensitive Multi-Period Computation Offloading with Reliability Guarantees in Fog Networks

Computation offloading over fog computing has the potential to improve reliability and reduce latency in future networks. This paper considers a scenario where roadside units (RSUs) are installed for offloading tasks to the computation nodes including nearby fog nodes and a cloud center. To guarantee the reliable communication, we formulate the first subproblem of power allocation, and leverage the conditional value-at-risk approach to analyze the successful transmission probability in the worse-case channel condition. To complete computation tasks with low latency, we formulate the second subproblem of task allocation into a multi-period generalized assignment problem (MPGAP), which aims at minimizing the total delay by offloading tasks to the `right' fog nodes at `right' period. Then, we propose a modified branch-and-bound algorithm to derive the optimal solution and a heuristic greedy algorithm to obtain approximate performance. In addition, the master problem is proposed as a non-convex optimization problem, which considers both the reliability-guaranteed and delay-sensitive requirements. We design the Lagreedy algorithm by combining the subgradient algorithm and the heuristic algorithm. Comprehensive evaluations demonstrate that the Lagreedy is able to obtain the shortest delay with a high power consumption, while the branch-and-bound algorithm can achieve both shorter delay and lower power consumption with reliability guarantees.