An Evolutionary Computation Framework for Task Off-and-Downloading Scheduling in Mobile Edge Computing

When designing task scheduling algorithms in mobile edge computing (MEC), the mobile device (MD)’s mobility becomes an important concern, since the change in MD’s location would affect the data transmission rate, leading to fluctuations in task transmission duration and completion time. In this article, we study a mobility-aware task off-and-downloading scheduling problem in MEC, considering both the communication delay and energy consumption caused by the data offloading and the result downloading. We first formulate a mathematical optimization model of the studied problem and prove its NP-hardness. To explore high-quality task scheduling decisions, we propose a swarm intelligence (SI) algorithm-based evolutionary computation (START) framework. The main technical innovations of START include a solution representation of off-and-downloading sequence, an exponential probability model-based mapping operator, and a task dispatching heuristic. Specifically, the solution representation makes START applicable to a wide range of SI algorithms. The mapping operator establishes the link between individual space and solution space, in which the critical parameter is determined by a rigorous theoretical analysis. The task dispatching strategy is the only component of the START framework that is relevant to the particular problem, providing the extensibility of applying START to solving other problems. In experiments, we create a real-world MD trajectory data set MDT-NJUST, and integrate several representative SI algorithms to justify the performance of START in solving the scheduling problem. Experimental results also verify the conclusion drawn from the theoretical analysis on critical parameter determination.