Robust & Low-Complexity Task Scheduling Algorithms for a Mobile Edge Computing System

With the advent of Mobile Edge Computing (MEC), the arriving tasks in an Internet of Things (IoT) network can be executed locally or at an MEC server. A Constrained Markov Decision Process (CMDP) formulation can capture the trade-off between computation time and power consumption. However, the optimal policy obtained by solving the CMDP problem may be sensitive to the changes in the task arrival rate. Moreover, there may be constraint violations. To address these issues, in this paper, we provide a Robust Return Robust CMDP (R3CMDP) formulation that minimizes the worst-case total discounted power consumption subject to a constraint on the worst-case total discounted deadline violations. Based on robust Dynamic Programming (DP) methods, we propose a task allocation algorithm that provably provides the optimal R3C policy. We also establish that the proposed algorithm incorporates robustness into the MDP framework with almost no additional complexity. Furthermore, we propose a low-complexity robust heuristic that can be implemented online, unlike the former algorithm. The proposed algorithms are implemented in a Network Simulator-3 (ns-3) based IoT simulation package. Numerical and simulation results establish that the proposed algorithms are more robust compared to the state-of-the-art algorithms in the face of varying task arrival rates.