Optimal multi-part mobile computation offloading with hard deadline constraints

This paper considers mobile computation offloading when concurrent local execution (CLE) is used to enforce task execution time constraints. This mechanism can ensure that hard task deadlines are satisfied regardless of any randomness induced by the wireless channel, network or cloud servers. In this type of system, mobile device energy may be reduced by segmenting a task upload into multiple parts, rather than doing a conventional contiguous task upload. The paper uses this mechanism to adapt to changes in channel conditions during the offload. Unlike the contiguous task offload case however, the upload initiation times of each part must be determined dynamically. This is done while ensuring that hard task deadlines are always satisfied. In this paper, the multi-part computation offloading case is considered. In multi-part offloading, the task to be offloaded is partitioned into K upload parts before any offload initiation decisions are made. In this case, current channel state information is incorporated into the offload decisions, and the system must always satisfy a hard task execution time constraint using concurrent local execution. The paper considers the case for Markovian wireless channels. A provably energy-optimal online computation offloading algorithm (MuliOpt) is introduced for multi-part offloading. MultiOpt is shown to be optimal using Markovian decision process stopping theory. Since the computational complexity of MultiOpt can be significant, simpler and more computationally efficient heuristics, which also respect the hard task execution deadline, may be used. The paper introduces two such heuristics, the Immediate Offloading, and Multi Threshold algorithms. The mobile energy use of MultiOpt is compared to these heuristics, as well as to local execution without offloading and an offline energy bound. Simulation results show that MultiOpt performs significantly better when compared to the proposed heuristics, as well as when K increases.