Delay-Sensitive Multi-Period Computation Offloading with Reliability Guarantees in Fog Networks
- 27 May 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 19 (9) , 2062-2075
Abstract
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.Keywords
This publication has 33 references indexed in Scilit:
- Ultra-low latency service provision in 5G Fog-Radio Access Networks2016
- A Distributionally Robust Linear Receiver Design for Multi-Access Space-Time Block Coded MIMO SystemsIEEE Transactions on Wireless Communications, 2016
- Optimal Workload Allocation in Fog-Cloud Computing Towards Balanced Delay and Power ConsumptionIEEE Internet of Things Journal, 2016
- Energy-efficient dynamic offloading and resource scheduling in mobile cloud computing2016
- Toward Vehicle-Assisted Cloud Computing for SmartphonesIEEE Transactions on Vehicular Technology, 2015
- D2D-based V2V communications with latency and reliability constraints2014
- Fog Computing: A Platform for Internet of Things and Analytics2014
- Distributionally robust joint chance constraints with second-order moment informationMathematical Programming, 2011
- On-demand broadcast for multiple-item requests in a multiple-channel environmentInformation Sciences, 2010
- A branch and bound algorithm for the generalized assignment problemMathematical Programming, 1975