Mobile Computation Offloading with Hard Task Completion Times

This chapter introduces algorithms for 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. By sometimes allowing simultaneous local and remote execution, job deadlines are always satisfied in the face of any unexpected wireless channel conditions. Online optimal algorithms are introduced that reduce the remote and local execution overlap so that energy wastage is minimized. Two job uploading schemes are introduced, continuous and discrete. In the case of continuous offloading, the mobile device will upload the entire job in one piece without interruption, and an OnOpt algorithm is used for deciding the offloading initiation time. In the discrete computation offloading, the job is partitioned into a known number of parts, each part is uploaded separately, and a MultiOpt algorithm is used to decide the upload initiation time of each part during runtime. The problem is studied for homogeneous Markovian wireless channels, and energy optimality is proved for the OnOpt algorithm based on continuous uploading and MultiOpt based on multi-part uploading. The MultiOpt saves more energy of the mobile device at a price of higher complexity in decision-making.