Preemptive Mobile Computation Offloading With Hard Deadlines and Concurrent Local Execution

This paper considers Preemptive Mobile Computation Offloading when concurrent local execution (CLE) is used to guarantee task execution time constraints. By allowing simultaneous local and remote execution, CLE ensures that job deadlines are always satisfied in the face of unforeseen wireless channel conditions. In the preemptive offloading case, at the start of each time slot, a decision is made to either continue or temporarily interrupt the offload. This mechanism allows the system to adapt when channel conditions change. The paper considers the case for homogeneous Markovian wireless channels. Using Markovian decision process stopping theory, an online energy-optimal computation offloading algorithm is formulated for preemptive offloading, referred to as Optimal Preemptive Offloading (OPO). Since the computational complexity of OPO can be prohibitive, the paper introduces three computationally efficient techniques motivated by OPO: 1) water-filling; 2) water-filling with scheduling; and 3) generalized water-filling. For each method, two variations are considered. The first (Equ) uses the equilibrium channel state probabilities in offloading decision calculations, and the second (Exp) uses Markovian transition matrix exponentiation. This results in six algorithms with a wide variety of energy performance and computational complexity. Performance of the algorithms is compared that shows the tradeoffs between complexity and mobile energy saving performance.