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

doi:10.19678/j.issn.1000-3428.0068236

摘要/Abstract

摘要：

为缩短未知环境下移动边缘计算(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%。

关键词: 移动边缘计算, 无人机部署, 蛇优化算法, 差分进化算法, 混合整数非线性问题

Abstract:

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%.

Key words: Mobile Edge Computing (MEC), UAV deployment, snake optimizer algorithm, differential evolution algorithm, mixed integer nonlinear problem

万昊楠, 吴飞, 尹玲. 基于自适应无人机数量的节时部署优化算法[J]. 计算机工程, 2024, 50(10): 302-312.

WAN Haonan, WU Fei, YIN Ling. Time-Saving Deployment Optimization Algorithm Based on the Number of Adaptive Drones[J]. Computer Engineering, 2024, 50(10): 302-312.

https://www.ecice06.com/CN/Y2024/V50/I10/302

图/表 12

图1 无人机MEC系统

Fig.1 UAV MEC system

图2 自变异示意图

Fig.2 Schematic diagram of self-mutation

图3 染色体长度增长的交叉操作示意图

Fig.3 Schematic diagram of crossover operation for chromosome length growth

图4 染色体长度不变的交叉操作示意图

Fig.4 Schematic diagram of crossover operation when chromosome length remains constant

图5 染色体长度缩短的交叉操作示意图

Fig.5 Schematic diagram of crossover operation for chromosome length shortening

图6 4种场景下的UE分布

Fig.6 UE distribution in four scenarios

图7 迭代次数对收敛性的影响

Fig.7 The influence of iteration times on convergence

图8 4种场景下的UAV覆盖情况

Fig.8 UAV coverage in four different scenarios

图9 不同场景下覆盖率与UE数量间的关系

Fig.9 The relationship between coverage and the number of UEs in different scenarios

参考文献 25

1	YANG L, YAO H P, ZHANG X, et al. Multi-UAV deployment for MEC enhanced IoT networks[C]//Proceedings of IEEE/CIC International Conference on Communications in China. Washington D. C., USA: IEEE Press, 2020: 436-441.
2	董超, 沈赟, 屈毓锛. 基于无人机的边缘智能计算研究综述. 智能科学与技术学报, 2020, 2(3): 227- 239.
	DONG C, SHEN Y, QU Y B. A survey of UAV-based edge intelligent computing. Chinese Journal of Intelligent Science and Technology, 2020, 2(3): 227- 239.
3	ZHANG X, ZHONG Y J, LIU P P, et al. Resource allocation for a UAV-enabled mobile-edge computing system: computation efficiency maximization. IEEE Access, 2019, 7, 113345- 113354. doi: 10.1109/ACCESS.2019.2935217
4	ZHANG J, ZHOU L, TANG Q, et al. Stochastic computation offloading and trajectory scheduling for UAV-assisted mobile edge computing. IEEE Internet of Things Journal, 2019, 6(2): 3688- 3699. doi: 10.1109/JIOT.2018.2890133
5	蔡星娟, 郭彦亨, 赵天浩, 等. 基于进化多任务的边缘计算服务部署和任务卸载. 计算机工程, 2023, 49(7): 1- 9. URL
	CAI X J, GUO Y H, ZHAO T H, et al. Edge computing service deployment and task offloading based on evolutionary multitasking. Computer Engineering, 2023, 49(7): 1- 9. URL
6	ZHONG X K, HUO Y M, DONG X D, et al. QoS-compliant 3-D deployment optimization strategy for UAV base stations. IEEE Systems Journal, 2021, 15(2): 1795- 1803. doi: 10.1109/JSYST.2020.3015428
7	WANG L, HUANG P Q, WANG K Z, et al. RL-based user association and resource allocation for multi-UAV enabled MEC[C]//Proceedings of the 15th International Wireless Communications & Mobile Computing Conference. Washington D. C., USA: IEEE Press, 2019: 741-746.
8	刘漳辉, 郑鸿强, 张建山, 等. 多无人机使能移动边缘计算系统中的计算卸载与部署优化. 计算机科学, 2022, 49(S1): 619- 627.
	LIU Z H, ZHENG H Q, ZHANG J S, et al. Computation offloading and deployment optimization in multi-UAV-enabled mobile edge computing systems. Computer Science, 2022, 49(S1): 619- 627.
9	ZHANG X C, ZHANG J, XIONG J, et al. Energy-efficient multi-UAV-enabled multiaccess edge computing incorporating NOMA. IEEE Internet of Things Journal, 2020, 7(6): 5613- 5627. doi: 10.1109/JIOT.2020.2980035
10	AL-HOURANI A, KANDEEPAN S, LARDNER S. Optimal LAP altitude for maximum coverage. IEEE Wireless Communications Letters, 2014, 3(6): 569- 572. doi: 10.1109/LWC.2014.2342736
11	XU J, ZENG Y, ZHANG R. UAV-enabled wireless power transfer: trajectory design and energy optimization. IEEE Transactions on Wireless Communications, 2018, 17(8): 5092- 5106. doi: 10.1109/TWC.2018.2838134
12	KNJAZEW D, GOLDBERG D E. OMEGA—Ordering Messy GA: solving permutation problems with the fast messy genetic algorithm and random keys[EB/OL]. [2023-07-05]. http://gpbib.cs.ucl.ac.uk/gecco2000/GA059.pdf.
13	STRON R, PRICE K. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces[EB/OL]. [2023-07-05]. https://cse.engineering.nyu.edu/~mleung/CS4744/f04/ch06/Storn95-012.pdf.
14	HASHIM F A, HUSSIEN A G. Snake optimizer: a novel meta-heuristic optimization algorithm. Knowledge-Based Systems, 2022, 242, 108320. doi: 10.1016/j.knosys.2022.108320
15	YANG X S, DEB S. Cuckoo search via Lévy flights[C]//Proceedings of the World Congress on Nature & Biologically Inspired Computing. Washington D. C., USA: IEEE Press, 2009: 210-214.
16	XU Q Z, WANG L, WANG N, et al. A review of opposition-based learning from 2005 to 2012. Engineering Applications of Artificial Intelligence, 2014, 29, 1- 12. doi: 10.1016/j.engappai.2013.12.004
17	WANG Y, RU Z Y, WANG K, et al. Joint deployment and task scheduling optimization for large-scale mobile users in multi-UAV-enabled mobile edge computing. IEEE Transactions on Cybernetics, 2020, 50(9): 3984- 3997. doi: 10.1109/TCYB.2019.2935466
18	WANG B L, HUANG K, LI T K. Permutation flowshop scheduling with time lag constraints and makespan criterion. Computers & Industrial Engineering, 2018, 120, 1- 14.
19	GASS S I, HARRIS C M. Quadratic assignment problem[EB/OL]. [2023-07-05]. https://link.springer.com/referenceworkentry/10.1007/978-0-387-74759-0_534.
20	徐昌彪, 郭瑞博, 鲜永菊. 异构网络下带内回程基站部署方案. 计算机工程, 2020, 46(1): 150-156, 163. URL
	XU C B, GUO R B, XIAN Y J. Deployment scheme of in-band backhaul base station in heterogeneous network. Computer Engineering, 2020, 46(1): 150-156, 163. URL
21	麦伟杰, 刘伟莉, 钟竞辉. 基于种群状态信息的自适应差分进化算法. 通信学报, 2023, 44(6): 34- 46.
	MAI W J, LIU W L, ZHONG J H. Self-adaptive differential evolution algorithm based on population state information. Journal on Communications, 2023, 44(6): 34- 46.
22	KADDI M, KHALILI Z, BOUCHRA M. A differential evolution based clustering and routing protocol for WSN[C]//Proceedings of the 2nd International Conference on Mathematics and Information Technology. Washington D. C., USA: IEEE Press, 2020: 190-195.
23	王彬, 任露, 王晓帆, 等. 基于协方差分析的合作协同进化差分进化算法. 通信学报, 2023, 44(1): 189- 199.
	WANG B, REN L, WANG X F, et al. Cooperative coevolution algorithm with covariance analysis for differential evolution. Journal on Communications, 2023, 44(1): 189- 199.
24	WANG L, HUANG P Q, WANG K Z, et al. RL-based user association and resource allocation for multi-UAV enabled MEC[C]//Proceedings of the 15th International Wireless Communications & Mobile Computing Conference. Washington D. C., USA: IEEE Press, 2019: 741-746.
25	GHANAVI R, KALANTARI E, SABBAGHIAN M, et al. Efficient 3D aerial base station placement considering users mobility by reinforcement learning[C]//Proceedings of IEEE Wireless Communications and Networking Conference. Washington D. C., USA: IEEE Press, 2018: 1-6.

[1]	石琼, 段辉, 师智斌. 基于深度强化学习的可信任务卸载方案[J]. 计算机工程, 2024, 50(8): 142-152.
[2]	陈姣, 沈艳. 面向缓存机制的移动边缘计算任务卸载研究[J]. 计算机工程, 2024, 50(7): 194-203.
[3]	曾耀平, 夏玉婷, 江伟伟, 刘月强. 加权能耗最小化的无人机辅助移动边缘计算策略研究[J]. 计算机工程, 2024, 50(2): 288-297.
[4]	杨建军, 唐东明, 李驹光, 肖宇峰. 基于改进人工蜂鸟算法的MEC任务卸载策略[J]. 计算机工程, 2024, 50(10): 291-301.
[5]	彭世明, 林士飏, 贾硕, 杨苗会. 基于负载预测的多目标优化任务卸载策略[J]. 计算机工程, 2024, 50(1): 206-215.
[6]	杜逸潇, 王红军, 李修和. 基于频谱地图的辐射源指纹定位方法研究[J]. 计算机工程, 2023, 49(9): 183-190, 198.
[7]	班玉琦, 段利国, 温昊宇, 李爱萍, 赵菊敏. 面向移动感知的计算卸载及资源分配策略研究[J]. 计算机工程, 2023, 49(8): 163-173.
[8]	蔡星娟, 郭彦亨, 赵天浩, 张文生. 基于进化多任务的边缘计算服务部署和任务卸载[J]. 计算机工程, 2023, 49(7): 1-9.
[9]	梅晶, 戴龙宝, 童钊, 邓昕, 王嘉珂. 资源约束下基于Lyapunov优化的自适应卸载算法[J]. 计算机工程, 2023, 49(7): 34-46.
[10]	李强, 仪晋辉, 杜婷婷, 王胜春. 移动边缘计算中基于A3C的依赖任务卸载与资源分配[J]. 计算机工程, 2023, 49(6): 42-52.
[11]	生龙, 袁丽娜, 武南南, 姬少培. 基于GSA与DE优化混合核ELM的网络异常检测模型[J]. 计算机工程, 2022, 48(6): 146-153.
[12]	张伟成, 卫红权, 刘树新, 王庚润. 面向5G MEC基于行为的用户异常检测方案[J]. 计算机工程, 2022, 48(5): 27-34.
[13]	谢娜, 谭文安, 曹彦, 赵璐. 移动边缘计算中安全信息流建模与分析[J]. 计算机工程, 2022, 48(5): 35-42,52.
[14]	于成龙, 付国霞, 孙超利, 张国晨. 全局与局部模型交替辅助的差分进化算法[J]. 计算机工程, 2022, 48(3): 115-123.
[15]	姚政, 吴怀宇, 陈洋. 基于两阶段优化的并发流任务计算卸载策略[J]. 计算机工程, 2022, 48(12): 62-71.

选择文件类型/文献管理软件名称

选择包含的内容