无人机辅助边缘计算网络的任务卸载与资源分配联合优化

周晓天; 杨潇辉; 张海霞; 邓伊琴

doi:10.11999/JEIT240411

无人机辅助边缘计算网络的任务卸载与资源分配联合优化

doi: 10.11999/JEIT240411

1.
山东大学控制科学与工程学院济南 250061
2.
山东省智能通信与感算融合重点实验室济南 250061

基金项目: 国家自然科学基金联合基金项目(U22A2003)，山东省自然科学基金重大基础研究项目(ZR2022ZD02)

详细信息

作者简介:
周晓天：男，教授，研究方向为无线通信与网络、边缘计算与智能通信等

杨潇辉：男，硕士生，研究方向为无人机、边缘计算等

张海霞：女，教授，研究方向为无线通信与网络、无线资源管理、智能通信技术等

邓伊琴：女，博士后，研究方向为边缘计算、车联网、无线资源优化等

通讯作者:
张海霞　haixia.zhang@sdu.edu.cn

中图分类号: TN929.5; TP18
计量
- 文章访问数: 258
- HTML全文浏览量: 42
- PDF下载量: 39
- 被引次数: 0
出版历程
- 收稿日期: 2024-05-25
- 修回日期: 2024-11-07
- 网络出版日期: 2024-11-13

Joint Optimization of Task Offloading and Resource Allocation for Unmanned Aerial Vehicle-assisted Edge Computing Network

1.
School of Control Science and Engineering, Shandong University, Jinan 250061, China
2.
Shandong Key Laboratory of Intelligent Communications and Sensing-Computation Integration, Shandong University, Jinan 250061, China

Funds: The Joint Funds of the National Natural Science Foundation of China (U22A2003), The Major Fundamental Research Project of Shandong Provincial Natural Science Foundation (ZR2022ZD02)

摘要

摘要: 利用无人机(UAV)作为空中中继节点，构建空地一体化的边缘计算网络，可以有效克服地面环境局限，拓展网络覆盖范围，为用户提供便利计算服务。该文面向无人机中继辅助的多用户、多服务器边缘计算网络场景，以最大化任务完成量为目标，研究了无人机部署位置、用户-服务器关联策略、无人机带宽分配的联合优化问题。由于该问题包含连续与离散变量，故该文综合运用差分进化、粒子群优化等工具，提出了一种基于块坐标下降(BCD)的次优算法进行求解。所提算法将原问题解耦为3个子问题独立求解，并通过迭代逼近原始问题最优解。仿真实验表明，所提算法可在满足用户任务时延需求的前提下，最大化系统总任务完成量，优于其他对比算法。
- 无人机通信 /
- 多接入边缘计算 /
- 任务卸载 /
- 资源分配
Abstract: It can effectively overcome the limitations of the ground environment, expand the network coverage and provide users with convenient computing services, through constructing the air-ground integrated edge computing network with Unmanned Aerial Vehicle (UAV) as the relay. In this paper, with the objective of maximizing the task completion amount, the joint optimization problem of UAV deployment, user-server association and bandwidth allocation is investigated in the context of the UAV assisted multi-user and multi-server edge computing network. The formulated joint optimization problem contains both continuous and discrete variables, which makes itself hard to solve. To this end, a Block Coordinated Descent (BCD) based iterative algorithm is proposed in this paper, involving the optimization tools such as differential evolution and particle swarm optimization. The original problem is decomposed into three sub-problems with the proposed algorithm, which can be solved independently. The optimal solution of the original problem can be approached through the iteration among these three subproblems. Simulation results show that the proposed algorithm can greatly increase the amount of completed tasks, which outperforms other benchmark algorithms.
- Unmanned Aerial Vehicle (UAV) communication /
- Multi-access edge computing /
- Task offloading /
- Resource allocation

HTML全文

图 1 系统模型

下载: 全尺寸图片幻灯片

图 2 算法整体流程图

下载: 全尺寸图片幻灯片

图 3 算法收敛性能分析与UAV部署位置示意图

下载: 全尺寸图片幻灯片

图 4 不同方案及带宽资源对任务完成量的影响

下载: 全尺寸图片幻灯片

1 联合UAV位置、带宽分配、用户-边缘服务器关联算法

(1) 初始化$ {{\boldsymbol{\varOmega}} ^0} $, $ {{\boldsymbol{B}}^0} $, $ {{\boldsymbol{A}}^0} $，置$ k $=0;
(2) While 目标函数的增长值低于阈值$ \varepsilon $：
(3) 　　给定{$ {{\boldsymbol{B}}^k},{{\boldsymbol{A}}^k} $}，输入算法2，输出结果$ {{\boldsymbol{\varOmega}} ^{k + 1}} $;
(4) 　　给定{$ {{\boldsymbol{\varOmega}} ^{k + 1}},{{\boldsymbol{A}}^k} $}，输入算法3，输出结果$ {{\boldsymbol{B}}^{k + 1}} $;
(5) 　　给定{$ {{\boldsymbol{\varOmega}} ^{k + 1}},{{\boldsymbol{B}}^{k + 1}} $}，输入算法4，输出结果$ {{\boldsymbol{A}}^{k + 1}} $;
(6) 　　更新$ k = k + 1 $;
(7) End While
(8) 得到最终$ {\boldsymbol{\varOmega}} $, $ {\boldsymbol{A}} $, $ {\boldsymbol{B}} $

下载: 导出CSV

2 基于PSO的UAV 3维位置优化算法

输入：用户位置$ ({\boldsymbol{w}}_m^{\text{T}},0) $、边缘服务器位置$ ({\boldsymbol{w}}_s^{\text{T}},0) $、任务参数　$ ({l_i},{c_i},{\tau _i}) $；其他基本参数$ {A_1},{A_2},{\beta _0},N,\gamma ,{c_1},{c_2},{r_1},{r_2},{k_{{\text{max}}}} $;
输出：无人机3维位置$ {\boldsymbol{\varOmega}} $
(1) 初始化迭代次数$ k $=1;
(2) For 每个粒子$ i $:
(3) 　For 每个维度$ d $:
(4) 　　在允许范围内随机初始化粒子位置$ {{\boldsymbol{X}}_{id}} $;
(5) 　　在允许范围内随机初始化粒子位置$ {{\boldsymbol{V}}_{id}} $;
(6) 　End For
(7) End For
(9) While $ k \le {k_{{\text{max}}}} $:
(10) 　 For 每个粒子$ i $:
(11) 　　计算每个粒子能够完成的系统任务量;
(12) 　　 If $ f({\boldsymbol{X}}_{id}^k) < f({\bf{pbest}}_{id}^{k - 1}) $
(13) 　　　选择当前粒子位置作为该粒子的最优位置$ {\bf{pbest}}_{id}^k $;
(14) 　　 End If
(15) End For
(16) For 每个粒子$ i $:
(17) 　 For 每个维度$ d $:
(18) 　　根据式(6)计算粒子新速度;
(19) 　　根据$ {\boldsymbol{X}}_{id}^{k + 1} = {\boldsymbol{X}}_{id}^k + {\mkern 1mu} {\mkern 1mu} {\boldsymbol{V}}_{id}^{k + 1} $更新粒子新位置;
(20) 　 End For
(21) End For
(22) $ k = k + 1 $;
(23) End While

下载: 导出CSV

3 基于DE的带宽分配优化算法

输入：用户位置$ ({\boldsymbol{w}}_m^{\text{T}},0) $、边缘服务器位置$ ({\boldsymbol{w}}_s^{\text{T}},0) $、任务参数　$ ({l_i},{c_i},{\tau _i}) $；其他基本参数$ {A_1},{A_2},{\beta _0},N,{\text{CR}},{k_{{\text{max}}}} $;
输出：带宽分配比例$ {\boldsymbol{B}} $
(1) 初始化迭代次数$ k $=1;
(2) For 每个个体$ i $：
(3) 　For 每个维度$ d $：
(4) 　　在允许范围内随机初始化个体位置$ {{\boldsymbol{x}}_{n,1}} $;
(5) 　　计算每个个体能完成的系统任务量;
(6) 　End For
(7) End For
(8) While $ k \le {k_{{\text{max}}}} $：
(9) 　For 每个个体$ i $：
(10) 　从当前$ {{\boldsymbol{x}}_{n,k}} $中选择3个不同个体 $ {{\boldsymbol{x}}_{r1,k}} $, $ {{\boldsymbol{x}}_{r2,k}} $, $ {{\boldsymbol{x}}_{r3,k}} $;
(11) 　计算得到变异个体;
(12) End For
(13) For 每个个体$ i $：
(14) 　生成当前个体的交叉概率$ {\text{CR}} $;
(15) 　根据式(8)计算得到试验个体;
(16) End For
(17) For 每个个体$ i $：
(18) 　根据式(9)择优选出最优个体;
(19) End For
(20) $ k = k + 1 $;
(21) End While

下载: 导出CSV

4 基于交换的用户-边缘服务器关联矩阵优化算法

输入：用户位置$ ({\boldsymbol{w}}_m^{\text{T}},0) $、边缘服务器位置$ ({\boldsymbol{w}}_s^{\text{T}},0) $、任务参数　$ ({l_i},{c_i},{\tau _i}) $；其他基本参数$ \mathcal{H},\mathcal{F},{A_1},{A_2},{\beta _0} $；
输出：用户-边缘服务器关联矩阵$ {\boldsymbol{A}} $
(1) 初始化迭代次数$ k $=1；
(2) 根据式(10)计算得到当前系统完成任务量$ \varPhi $；
(3) 根据用户集合计算得到用户组合个数$ {{C}}_M^2 $；
(4) While $ k \le {{C}}_M^2 $：
(5) 　计算此连接方式下系统完成任务量$ {\varPhi ^ * } $；
(6) 　If $ {\varPhi ^ * } > \varPhi $：
(7) 　　交换此用户组合的连接方式，更新$ {{{a}}_{{{m}},{{s}}}} $；
(8) 　End If
(9) 　$ k = k + 1 $；
(10) End While

下载: 导出CSV

表 1 仿真参数设置

参数名	参数值	参数名	参数值
边缘服务器计算能力f_s	[1, 9] GHz	无人机传输功率$ {P_{\mathrm{u}}} $	2 W
边缘服务器最大用户服务数$ {\eta _s} $	3	噪声功率谱密度$ {N_0} $	–169 dBm/Hz
任务的数据量$ {l_i} $	[100, 900] kB	路径损耗系数$ \alpha $	2.5
用户-UAV上行链路带宽W	6 MHz	平均信道功率增益$ {\beta _0} $	–60 dB
UAV-服务器下行链路带宽W	6 MHz	Rician因子最小值$ {K_{{\text{min}}}} $	0 dB
用户设备传输功率$ {P_m} $	15 dBm	Rician因子最大值$ {K_{{\text{max}}}} $	30 dB

下载: 导出CSV

表 2 PSO, DE子算法参数设置

算法	参数名	参数值	算法	参数名	参数值
PSO	种群规模大小	40	DE	种群规模大小	60
	粒子维度	3		粒子维度	14
	最大迭代次数	300		最大迭代次数	300
	个体学习因子	2		缩放因子	0.5
	群体学习因子	2		交叉因子	0.4

下载: 导出CSV

表 3 仿真对比算法

算法类型	算法序号	算法简介
随机分配	对比算法1	随机给定UAV位置、用户-服务器关联矩阵、带宽分配比例。
随机分配	对比算法2	随机给定UAV位置、用户-服务器关联矩阵，平均分配带宽比例。
1维资源独立优化	对比算法3	单独优化用户-服务器关联矩阵；随机给定UAV位置、带宽分配比例。
	对比算法4	单独优化UAV位置；随机给定带宽分配比例、用户-服务器关联矩阵。
	对比算法5	单独优化带宽分配比例；随机给定UAV位置、用户-服务器关联矩阵。
2维资源联合优化	对比算法6	联合优化用户-服务器关联矩阵、UAV位置；随机给定带宽分配比例。
	对比算法7	联合优化UAV位置、带宽分配比例，随机给定用户-服务器关联矩阵。
	对比算法8	联合优化用户-服务器关联矩阵、带宽分配比例，随机给定UAV位置。

下载: 导出CSV

参考文献(17)

[1]	DJIGAL H, XU Jia, LIU Linfeng, et al. Machine and deep learning for resource allocation in multi-access edge computing: A survey[J]. IEEE Communications Surveys & Tutorials, 2022, 24(4): 2449–2494. doi: 10.1109/COMST.2022.3199544.
[2]	周晓天, 孙上, 张海霞, 等. 多接入边缘计算赋能的AI质检系统任务实时调度策略[J]. 电子与信息学报, 2024, 46(2): 662–670. doi: 10.11999/JEIT230129. ZHOU Xiaotian, SUN Shang, ZHANG Haixia, et al. Real-time task scheduling for multi-access edge computing-enabled AI quality inspection systems[J]. Journal of Electronics & Information Technology, 2024, 46(2): 662–670. doi: 10.11999/JEIT230129.
[3]	陈新颖, 盛敏, 李博, 等. 面向6G的无人机通信综述[J]. 电子与信息学报, 2022, 44(3): 781–789. doi: 10.11999/JEIT210789. CHEN Xinying, SHENG Min, LI Bo, et al. Survey on unmanned aerial vehicle communications for 6G[J]. Journal of Electronics & Information Technology, 2022, 44(3): 781–789. doi: 10.11999/JEIT210789.
[4]	YAN Xuezhen, FANG Xuming, DENG Cailian, et al. Joint optimization of resource allocation and trajectory control for mobile group users in fixed-wing UAV-enabled wireless network[J]. IEEE Transactions on Wireless Communications, 2024, 23(2): 1608–1621. doi: 10.1109/TWC.2023.3290748.
[5]	LI Mushu, CHENG Nan, GAO Jie, et al. Energy-efficient UAV-assisted mobile edge computing: Resource allocation and trajectory optimization[J]. IEEE Transactions on Vehicular Technology, 2020, 69(3): 3424–3438. doi: 10.1109/TVT.2020.2968343.
[6]	LUO Weiran, SHEN Yanyan, YANG Bo, et al. Joint 3-D trajectory and resource optimization in multi-UAV-enabled IoT networks with wireless power transfer[J]. IEEE Internet of Things Journal, 2021, 8(10): 7833–7848. doi: 10.1109/JIOT.2020.3041303.
[7]	NASIR A A. Latency optimization of UAV-enabled MEC system for virtual reality applications under Rician fading channels[J]. IEEE Wireless Communications Letters, 2021, 10(8): 1633–1637. doi: 10.1109/LWC.2021.3075762.
[8]	LIU Boyang, WAN Yiyao, ZHOU Fuhui, et al. Resource allocation and trajectory design for MISO UAV-assisted MEC networks[J]. IEEE Transactions on Vehicular Technology, 2022, 71(5): 4933–4948. doi: 10.1109/TVT.2022.3140833.
[9]	CHENG Kaijun, FANG Xuming, WANG Xianbin, et al. Energy efficient edge computing and data compression collaboration scheme for UAV-assisted network[J]. IEEE Transactions on Vehicular Technology, 2023, 72(12): 16395–16408. doi: 10.1109/TVT.2023.3289962.
[10]	WANG Yong, RU Zhiyang, WANG Kezhi, et al. Joint deployment and task scheduling optimization for large-scale mobile users in multi-UAV-enabled mobile edge computing[J]. IEEE Transactions on Cybernetics, 2020, 50(9): 3984–3997. doi: 10.1109/TCYB.2019.2935466.
[11]	MEI Haibo, YANG Kun, LIU Qiang, et al. Joint trajectory-resource optimization in UAV-enabled edge-cloud system with virtualized mobile clone[J]. IEEE Internet of Things Journal, 2020, 7(7): 5906–5921. doi: 10.1109/JIOT.2019.2952677.
[12]	LIU Tianyu, ZHANG Guangchi, CUI Miao, et al. Task completion time minimization for UAV-enabled data collection in Rician fading channels[J]. IEEE Internet of Things Journal, 2023, 10(2): 1134–1148. doi: 10.1109/JIOT.2022.3204658.
[13]	YOU Changsheng and ZHANG Rui. 3D trajectory optimization in Rician fading for UAV-enabled data harvesting[J]. IEEE Transactions on Wireless Communications, 2019, 18(6): 3192–3207. doi: 10.1109/TWC.2019.2911939.
[14]	MONDAL A, MISHRA D, PRASAD G, et al. Joint optimization framework for minimization of device energy consumption in transmission rate constrained UAV-assisted IoT network[J]. IEEE Internet of Things Journal, 2022, 9(12): 9591–9607. doi: 10.1109/JIOT.2021.3128883.
[15]	LI Jianyu, DU Kejing, ZHAN Zhiui, et al. Distributed differential evolution with adaptive resource allocation[J]. IEEE Transactions on Cybernetics, 2023, 53(5): 2791–2804. doi: 10.1109/TCYB.2022.3153964.
[16]	MILNER S, DAVIS C, ZHANG Haijun, et al. Nature-inspired self-organization, control, and optimization in heterogeneous wireless networks[J]. IEEE Transactions on Mobile Computing, 2012, 11(7): 1207–1222. doi: 10.1109/TMC.2011.141.
[17]	LIU Jialei, ZHOU Ao, LIU Chunhong, et al. Reliability-enhanced task offloading in mobile edge computing environments[J]. IEEE Internet of Things Journal, 2022, 9(13): 10382–10396. doi: 10.1109/JIOT.2021.3115807.