Optimal Mobile Computation Offloading with Hard Deadline Constraints

This paper considers mobile computation offloading where task completion times are subject to hard deadline constraints. Hard deadlines are difficult to meet in conventional computation offloading due to the stochastic nature of the wireless channels involved. Rather than using binary offload decisions, we permit concurrent remote and local job execution when it is needed to ensure task completion deadlines. The paper addresses this problem for homogeneous Markovian wireless channel models. An online energy-optimal computation offloading algorithm, OnOpt, is proposed. Its energy optimality is shown by constructing a time-dilated absorbing Markov process and applying dynamic programming. Closed form results are derived for general Markovian processes, and the Gilbert-Elliott channel model is used to show how the particular structure of the Markov chain can be exploited in computing optimal offload initiation times more efficiently. It is shown that job completion time probabilities can be computed recursively, which leads to a significant reduction in the computational complexity of OnOpt. The performance of the proposed algorithm is compared to three others, namely, Immediate Offloading, Channel Threshold, and Local Execution. Performance results show that the proposed algorithm can significantly improve mobile device energy consumption compared to the other approaches while guaranteeing hard task execution deadlines.