Composite Heuristics for Scheduling Tasks in Mobile Edge Computing by Considering Security
Abstract
The computing power of mobile devices is too limited to execute computation tasks fast. Mobile edge computing (MEC) allows mobile devices to offload tasks to near servers to reduce the completion time of the tasks (a.k.a makespan). The input data of some critical tasks should be encrypted before the offloading. Aiming at the security critical tasks in the MEC composed of multiple servers, this paper addresses to minimize the makespan by scheduling security-critical tasks. We provide the formulation of the problem which is generally an integer programming problem, and three effective composite heuristics CH1–CH3 are proposed to solve the problem. Task permutations are considered as solutions. We construct a greedy heuristic algorithm to calculate the value of the objective. These three composite heuristics consist of two phases: solution initialization and solution improvement. In the first phase, the solutions of all the proposed algorithms are generated by a task arrangement rule called Biggest data Task First (BTF), and then in the second phase, improved by three searching methods based on different neighborhoods including a insertion neighborhood, a swap neighborhood and a hybrid neighborhood, respectively. Experimental results show that CH1–CH3 outperform the well-known RoundRobin algorithm. Particularly, BTF is demonstrated to initialize highly qualified solutions, making contributions to the high effectiveness. Meanwhile, all the improvement methods are justified to be effective and the method based on the hybrid neighborhood achieves the best effectiveness.
This paper was recommended by Regional Editor Tongquan Wei.
