Joint Deployment and Task Scheduling Optimization for Large-Scale Mobile Users in Multi-UAV-Enabled Mobile Edge Computing
Joint Deployment and Task Scheduling Optimization for Large-Scale Mobile Users in Multi-UAV-Enabled Mobile Edge Computing
复制标题
多无人机移动边缘计算中大规模移动用户联合部署与任务调度优化
DOI：
10.1109/tcyb.2019.2935466
复制
发表时间：
2020-09-01
影响因子：
11.8
通讯作者：
Huang, Pei-Qiu
中科院分区：
文献类型：
--
作者：
Wang, Yong;Ru, Zhi-Yang;Huang, Pei-Qiu
建立了一种新的基于多无人机的移动边缘计算(MEC)系统，在该系统中部署了多个无人机作为飞行边缘云，以满足大规模移动用户的需求。在这个系统中，我们需要通过考虑无人机的数量和位置来优化无人机的部署。同时，要为所有移动用户提供良好的服务，就必须对任务调度进行优化。具体来说，对于每个移动用户，我们需要确定其任务是在本地执行还是在无人机上执行(即，卸载决策)，以及应该分配多少资源(即，资源分配)。以系统能耗最小为目标，提出了一种无人机部署和任务调度联合优化的两层优化方法。通过对该系统的分析，我们得到了如下性质：在所有任务都能完成的情况下，无人机的数量应该尽可能少。基于这一性质，在上层，我们提出了一种带淘汰算子的差分进化算法来优化无人机的部署，其中每个个体代表一个无人机的位置，整个种群代表整个无人机的部署。在进化过程中，我们首先确定无人机的最大数量。随后，消除算子逐渐减少无人机的数量，直到至少有一个任务在延迟约束下无法执行。这一过程实现了无人机数量的自适应调整。在下层，根据给定的无人机部署情况，将任务调度问题转化为0-1整数规划问题。针对该0-1整数规划问题规模大的特点，提出了一种高效的贪婪算法，以较少的时间获得近似最优解。在10个实例上验证了所提出的两层优化方法和所建立的支持多无人机的MEC系统的有效性。
This article establishes a new multiunmanned aerial vehicle (multi-UAV)-enabled mobile edge computing (MEC) system, where a number of unmanned aerial vehicles (UAVs) are deployed as flying edge clouds for large-scale mobile users. In this system, we need to optimize the deployment of UAVs, by considering their number and locations. At the same time, to provide good services for all mobile users, it is necessary to optimize task scheduling. Specifically, for each mobile user, we need to determine whether its task is executed locally or on a UAV (i.e., offloading decision), and how many resources should be allocated (i.e., resource allocation). This article presents a two-layer optimization method for jointly optimizing the deployment of UAVs and task scheduling, with the aim of minimizing system energy consumption. By analyzing this system, we obtain the following property: the number of UAVs should be as small as possible under the condition that all tasks can be completed. Based on this property, in the upper layer, we propose a differential evolution algorithm with an elimination operator to optimize the deployment of UAVs, in which each individual represents a UAV's location and the entire population represents an entire deployment of UAVs. During the evolution, we first determine the maximum number of UAVs. Subsequently, the elimination operator gradually reduces the number of UAVs until at least one task cannot be executed under delay constraints. This process achieves an adaptive adjustment of the number of UAVs. In the lower layer, based on the given deployment of UAVs, we transform the task scheduling into a 0-1 integer programming problem. Due to the large-scale characteristic of this 0-1 integer programming problem, we propose an efficient greedy algorithm to obtain the near-optimal solution with much less time. The effectiveness of the proposed two-layer optimization method and the established multi-UAV-enabled MEC system is demonstrated on ten instances with up to 1000 mobile users.