Optimal Multi-Decision Mobile Computation Offloading With Hard Task Deadlines

Multi-decision mobile computation offloading occurs when a task to be remotely executed is uploaded in separate parts. Since the upload is partitioned, separate decisions are needed to determine the best time to initiate each upload. The multi-decision problem is considered for the case where execution completion times are subject to hard deadline constraints and where task offloads occur over a Markovian wireless channel. An online energy-optimal computation offloading algorithm, Multiopt (Multi-decision online Optimum), is introduced, whose optimality is proven using Markovian stopping theory. The paper presents results using the Gilbert-Elliott channel model, where task completion time probabilities can be efficiently computed using Dynamic Programming. Although the proposed algorithm is proven to be energy optimal, its performance is also compared to four others, namely, Immediate Offloading, Channel Threshold, Local Execution, as well as optimal single-part offloading. Results show that the proposed algorithm can significantly improve mobile device energy consumption compared to the other approaches while guaranteeing hard task execution deadlines.