基于自适应无人机数量的节时部署优化算法

Time-Saving Deployment Optimization Algorithm Based on the Number of Adaptive Drones

为缩短未知环境下移动边缘计算(MEC)系统服务用户所需的平均时延,提高MEC系统服务质量(QoS),设计了一种基于多无人机(UAV)的MEC系统,并针对UAV数量大量增加、因用户平均时延减少呈现边际效应递减所带来的资源浪费问题,设计一种可变UAV数量的节时部署算法。MEC系统首先将UAV部署问题分解为一个双层嵌套问题,外层为最大覆盖问题(MCLP),内层为基于广义指派问题(GAP)的任务卸载问题,并将人为设置的惩罚项加入待优化目标中,在优化过程中使MEC系统UAV数量和用户所需平均时延之间达到平衡。部署算法设计了一种混合算法来针对嵌套问题进行求解,外层使用基于差分进化-蛇优化算法(DE-SO)的联合优化算法来解决UAV的部署覆盖问题,内层使用贪心算法来解决任务卸载问题。仿真实验结果表明,在多种UE分布环境下,相较于CS-G、SAO-G等算法,该算法在适应度、覆盖率等性能上取得了最优表现,相比寻优精度最高的对比算法,DE-SO-G在寻优精度上平均提升5.67%。

To reduce the average delay required by Mobile Edge Computing(MEC)service users in unknown environments and to improve the Quality of Service(QoS)of MEC systems,this study designs both an MEC system based on multiple Unmanned Aerial Vehicles(UAVs)and a time-saving deployment algorithm with a variable number of UAVs.The MEC system first decomposes the UAV deployment problem into a two-layered nesting problem.The outer layer is a deployment coverage problem based on the Maximum Covering Location Problem(MCLP),and the inner layer is a task offloading problem based on the General Assignment Problem(GAP).Artificially set penalty terms are added to the target to be optimized to achieve a balance between the number of UAVs in the MEC system and the average latency required by users during the optimization process.As the deployment algorithm,the study designs a hybrid algorithm to solve the nesting problem.The outer layer uses a joint optimization algorithm based on Differential Evolution-Snake Optimization(DE-SO)to solve the UAV deployment coverage problem,whereas the inner layer uses a greedy algorithm to solve the task offloading problem.Several simulation experiments show that,compared with CS-G,SAO-G,and other algorithms,the proposed algorithm achieves the best performance in terms of fitness,coverage,and other performance under a variety of User Equipment(UE)distribution environments.In addition,compared with the comparison algorithm with the highest optimization accuracy,DE-SO-G improves the optimization accuracy by an average of 5.67%.