Robust Offloading Scheduling for Mobile Edge Computing

In this paper, we study the problem of Robust offloading schEduling for mobIle edge computiNg (REIN), i.e., in the presence of uncertain offloading failures, how to determine an offloading schedule to minimize the overall latency of all computation-intensive tasks. We mathematically formulate the problem in the form of min-max robust optimization, based on the twice equivalent transformations of the scheduling problem that originally does not consider robustness. REIN is challenging to solve because the min-max robust objective is computationally intractable with existing approaches, and the monotonicity of the objective function is uncertain, even if we transform the objective into the popular max-min form by introducing an appropriate constant upper bound. To solve the above challenges, we first construct a constant upper bound and a monotone modular function to approximate the transformed max-min objective function, and then propose a computationally feasible solution with provable performance bound. Moreover, given the fact of the weak computation ability of users in practical, we construct a tighter constant upper bound and a monotone submodular approximation function, and propose a feasible solution with possibly improved performance bound. Extensive results show that, given a maximum number of offloading failures, our proposed algorithms outperform three benchmark algorithms, and approach the optimum at small time costs.