Robust Offloading Scheduling for Mobile Edge Computing
Yuben Qu, Haipeng Dai, Fan Wu, Dongyu Lu, Chao Dong, Shaojie Tang, Guihai Chen
Abstract
In this paper, we study the problem of <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</u> obust offloading sch <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</u> duling for mob <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">I</u> le edge computi <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</u> g (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.