Joint Optimization of Task Offloading and Resource Allocation for Unmanned Aerial Vehicle-assisted Edge Computing Network
-
摘要: 利用无人机(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.
-
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}} $ 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 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 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 表 1 仿真参数设置
参数名 参数值 参数名 参数值 边缘服务器计算能力fs [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 表 2 PSO, DE子算法参数设置
算法 参数名 参数值 算法 参数名 参数值 PSO 种群规模大小 40 DE 种群规模大小 60 粒子维度 3 粒子维度 14 最大迭代次数 300 最大迭代次数 300 个体学习因子 2 缩放因子 0.5 群体学习因子 2 交叉因子 0.4 表 3 仿真对比算法
算法类型 算法序号 算法简介 随机分配 对比算法1 随机给定UAV位置、用户-服务器关联矩阵、带宽分配比例。 对比算法2 随机给定UAV位置、用户-服务器关联矩阵,平均分配带宽比例。 1维资源
独立优化对比算法3 单独优化用户-服务器关联矩阵;随机给定UAV位置、带宽分配比例。 对比算法4 单独优化UAV位置;随机给定带宽分配比例、用户-服务器关联矩阵。 对比算法5 单独优化带宽分配比例;随机给定UAV位置、用户-服务器关联矩阵。 2维资源
联合优化对比算法6 联合优化用户-服务器关联矩阵、UAV位置;随机给定带宽分配比例。 对比算法7 联合优化UAV位置、带宽分配比例,随机给定用户-服务器关联矩阵。 对比算法8 联合优化用户-服务器关联矩阵、带宽分配比例,随机给定UAV位置。 -
[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.