无人机群辅助边缘计算系统的任务卸载和资源分配联合优化

刘世豪, 黄仰超, 胡 航,*, 司江勃, 韩蕙竹, 安 琪

(1. 空军工程大学信息与导航学院, 陕西 西安 710077;2. 西安电子科技大学综合业务网理论及关键技术国家重点实验室, 陕西 西安 710071)

0 引 言

随着移动设备的日益增多,各种新型的移动应用不断涌现,如导航、图像和视频处理、增强虚拟现实、人脸识别、实时在线游戏和无人驾驶,这些应用大多具有计算密集性和时延敏感性等特点,对传统网络性能提出了巨大的挑战[1-2]。为了解决该问题,移动边缘计算(mobile edge computing,MEC)通过部署设备在用户附近提供高效的服务来缓解用户设备的计算压力[3-4]。但是该方案在部署边缘计算服务器(edge computing server,ECS)时受地理环境制约。由于无人机的灵活性和机动性,通过无人机平台搭载ECS为用户提供计算服务,是降低时延和能耗的一种很有前景的方案[5-11]。

单个无人机由于能耗和负载的约束,计算性能难以适应日益增长的需求,制约了无人机的应用场景[12-13],因此关于无人机群的研究越来越多。目前关于无人机群辅助边缘计算的研究包括:文献[14]在研究无人机部署时,通过引入差分进化机制,最小化平均时延来平衡无人机的负载。文献[15]研究了多无人机中继系统的应用,其中地面终端至少被一个无人机服务,目标是最大限度地减少提供无线覆盖的无人机数量。文献[16]研究了无人机的部署优化问题,在确定区域内用最少的无人机取得最大的覆盖范围,使无人机覆盖时间最大化。文献[17]在用户需求约束下,通过进化算法联合优化了多架无人机的部署和任务调度,以最小化系统的能耗。文献[18]通过联合优化无人机的轨迹和资源分配,以最小化系统能耗,而且在轨迹优化时增加了无人机之间的防撞策略。文献[19]针对用户关联性,提出基于压缩感知优化算法以最小化系统的功耗。文献[20]考虑将多个无人机进行角色划分和用户分组,以便最大限度地利用通信和计算资源。文献[21]通过联合优化多架无人机的轨迹和计算资源,最小化无人机与用户能耗加权和以确保用户卸载公平性。然而,文献[21]并没有考虑时延的影响,文献[22]仅考虑了在单无人机情况下,通过联合优化计算资源和任务调度,最小化无人机能耗和时延加权和,以增强无人机服务的性能,但在多无人机条件下并没有得到充足的研究。文献[23]研究了多个无人机辅助用户卸载和轨迹联合优化以最小化用户最大时延。文献[24]讨论了无人机群作为用户需要边缘计算服务条件下,优化了各个无人机的3D位置以最小化服务时延。

以上的无人机群系统研究大多关注无人机的机动性,并没有充分利用无人机与无人机之间的通信优势。文献[14]虽然利用了无人机的机动性动态选择其服务的用户来均衡无人机的负载,但是当无人机的机动性受到制约时(例如,无人机管控政策制约无人机的飞行范围),无人机服务的区域相对固定,区域内用户只能选择区域相关的无人机进行卸载[12-13,25]。由于单个无人机计算性能有限,用户数据存在随机性,当无人机的机动性受限时,导致无人机负载不均衡、计算资源利用不足等问题。而无人机群可以通过无人机之间传输数据来完成各种任务[26-28],因此可以从全新的角度来解决无人机负载均衡问题。

对于无人机群空中协作场景的研究尚未成熟,文献[28]讨论了了无人机群在边缘计算的潜力和挑战,文献[29]中通过将无人机分类,以满足不同时延受限的服务。文献[30]在无人机群辅助边缘计算条件下,通过控制无人机计算器件的开关,决定计算数据是否卸载到其他无人机计算数据。但是以上文献只考虑数据的二元卸载方案,并没有考虑协作卸载方案以及计算资源优化问题。

本文讨论了一种新的MEC网络结构,充分利用了无人机通信资源和无人机之间视距链路的优势。在该系统中,无人机之间可以卸载数据为用户提供服务。为取得系统时延和能耗的加权和最小,联合优化了多架无人机的部署、任务调度和资源分配。本文工作的主要贡献如下:

(1) 针对无人机群辅助边缘计算系统存在的负载均衡问题,构建一种新的网络结构,在该网络中无人机充当ECS和中继,无人机通过数据的相互卸载缓解负载均衡问题。同时考虑系统的能耗和时延,构建能耗和时延加权和最小的优化问题。

(2) 为解决上述非凸问题,提出了双层优化方法——启发最优评价算法(heuristic optimal evaluation algorithm, HOEA)。上层使用粒子群优化 (particle swarm optimization, PSO) 算法优化无人机的位置,下层在给定的位置下优化无人机的数据卸载和资源分配。在实际操作中,将下层问题分解成两个子问题并使用块坐标下降(block coordinate descent, BCD)算法进行求解。

(3) 与其他方案相比,所提策略在无人机计算资源不均衡或者数据不均衡的情况下能取得更低的系统成本,尤其是负载不均衡程度加剧时,效果更为明显。说明可以通过无人机群边缘计算提高无人机的计算资源利用率,减少系统成本。

1 系统模型与问题描述

无人机群辅助边缘计算模型如图1所示。

图1 系统模型Fig.1 system mode

图1中每个阴影部分代表一个区域,并且每个区域都配备有一个无人机,称为本地无人机,每架无人机可以为本区域内的用户提供计算服务,受无人机管控政策约束,本地无人机只能在对应区域的上空飞行,禁止跨区域飞行,无人机在空中可以进行通信,并且配备多根天线。系统不考虑用户间的通信干扰。具体而言,部署R个无人机对应R个区域,每个区域地面用户有L个,其中区域的划分r∈R={1,2,…,R},R表示区域集合。无人机使用对应的区域进行编号,区域的范围集合为O={O1,O2,…,OR},Or表示无人机r能机动的范围,各区域的用户集合为Lr={1,2,…,L},Lr表示区域r内的用户集合。假设每个无人机都装备有MEC服务器,并且具有通信中继功能。

矩阵A表示无人机之间的连接方案,矩阵元素ars表示无人机r到无人机s之间的连接状态,ars=1表示无人机r卸载数据到无人机s,ars=0表示无人机r未卸载数据到无人机s,并且asr和ars含义并不相同。

(1)

1.1 通信模型

(2)

式中:α0表示发送功率为1 W、距离为1 m处的信道增益;||·||为欧式范数。那么,地面区域r中第i个用户到本地无人机的传输速率为

(3)

同理,无人机r与无人机s之间的通信速率为

(4)

1.2 时延模型

假设地面用户k的任务记为{ck,ik},ik为用户k计算数据大小(bit),ck表示用户k计算任务执行1位数据时所需ECS的中央处理器(central processing unit, CPU)周期数(cycles/bit)。用户在向本地无人机进行卸载时,采用全卸载方案,无人机向无人机卸载数据时,采取协作式卸载方案。

时延主要有3个方面,地面用户到无人机的传输时延,无人机本地计算需要的时间,以及无人机卸载到其他无人机传输数据的时延和数据计算的时延,其中无人机计算数据和卸载数据可以同时进行。在本文中忽略结果回传所需的时延和能耗。区域r内i用户卸载数据到本地无人机的时延为

(5)

本地无人机计算时延为

(6)

第s个无人机卸载i用户数据到第r个无人机的传输时延为

(7)

为简化问题,无人机向目标区域分配的计算资源被目标区域内用户平均占用。第r个无人机计算s区域i用户卸载数据的时延为

(8)

(9)

1.3 功率模型

无人机r与其他无人机通信所消耗的能量为

(10)

无人机的计算功耗包含两部分,计算本地数据能耗以及计算其他无人机卸载的数据能耗。本文中使用文献[31]中的能量计算模型,无人机r的计算能耗为

(11)

式中:K为CPU架构的有效开关电容。

系统中用户传输数据的总能量为

(12)

无人机计算能耗和通信能耗的总和为

(13)

1.4 问题描述

假设地面用户位置和计算任务量已知,无人机的部署、资源分配、数据卸载比例和连接方案分别为Q,f,β,A。为提升无人机群边缘计算系统在负载不均衡场景下的效果,通过联合优化用户卸载比例、无人机的部署和计算资源分配最小化系统成本。优化问题表示为

(14)

2 优化问题求解

原优化问题为非凸问题,一般的优化算法不容易解决。启发式算法由于和梯度无关,有利于解决该问题。由于无人机的位置和任务分配是紧密耦合的,因此单独使用启发式算法不太合适。受文献[17]启发,本文采用分层优化算法,上层使用PSO算法优化无人机的位置,而下层以最优资源分配方式对该位置进行评价。对于无人机之间的连接方案,考虑实际情况的限制,可以很明显地减少备选连接方案。

2.1 连接方式

如果对上层的连接方式直接进行遍历,若有R个无人机,则有2R×(R-1)种连接方式,当无人机数量很多时,该方式不合理。但是通过观察发现一些无人机连接情况是不可能出现的,通过消除这些不可能出现的连接能很大程度缩小可行域。在实际场景中,当无人机提供向其他无人机卸载数据时,便不再向其他无人机提供计算服务。在本文中无人机的连接方式使用矩阵A中元素ars表示,当无人机ars=1,表示无人机r向无人机s卸载数据,则此时所有的无人机都不会向无人机r卸载数据,则无人机之间卸载约束为

(15)

(16)

(17)

计算资源占用大的向计算资源占用小的卸载,反之则不会,即在Gr>Gs,r,s∈R条件下,无人机r到无人机s可以选择卸载和不卸载数据两种状态,但是无人机s却不能卸载数据到无人机r,可表示为

(18)

通过上述分析可以很大程度上缩减寻找最优连接方式的范围,如算法1所示。

算法 1 连接方式筛选算法1 初始化矩阵(R-1)×(R-1),每个元素值只有{0,1}可以选择;2 计算辅助变量Gi,i∈R;3 通过式(15)～式(18)选择符合条件的矩阵,总计为Nmax;4 输出符合条件的矩阵A和总数Nmax。

2.2 HOEA

多无人机的位置优化是一个非凸的问题,并且各个无人机之间位置选择是相互耦合的,这对优化有非常大的影响,导致一般的优化方法很难解决,因此考虑使用启发式算法求解。本文采用标准PSO算法[33],但是传统的PSO算法很难解决无人机位置与任务调度紧密相关的问题,为此以PSO算法为基础,将PSO和凸优化方法结合,解决无人机位置和任务调度的紧密相关的问题。将原问题分解成两层问题,上层算法使用PSO算法寻找多个无人机的部署,下层算法在给定无人机部署情况下,以最优任务调度评估多无人机的部署,用以粒子的更新。

给定无人机部署Q和连接方式A条件下,下层的问题可以表述为

(19)

(20)

式中:C9和C10保证了将服务延迟线性化后和原问题等价,但是线性化之后,问题依然非凸,则在本文中采用BCD算法将其分成两个子问题。

子问题1:计算资源分配优化

(21)

式中:变量χ={f};C2,C7,C8表示每个无人机计算资源受限并且分配的资源非负。由于目标函数为凸的,约束为凸,则该问题为凸优化问题,使用CVX工具箱进行求解。

子问题2:数据分配优化

(22)

式中:变量χ={β};约束C1,C5和C6表示全部数据被计算以及数据分配非负。该目标函数对变量β是仿射的,并且约束为凸,所以该问题为凸优化问题,使用CVX工具箱进行求解。

BCD资源分配算法展示如算法2所示。

算法 2 BCD资源分配算法输入 无人机连接方式AN,位置Q和任务分配β0,ξ=10-3; Repeat (1) 输入AN,Q,β(k),计算P3得出f(k); (2) 输入AN,Q,f(k),计算P3得出β(k),并计算对应的值U(k); (3) 更新k=k+1; (4) 如果|U(k+1)-U(k)|≤ξ跳出循环,输出{β,f},并且输出此时的系统成本值U=U(k+1); 输出 {β,f,U}。

(23)

(24)

对粒子的边界进行处理,使用算法2计算效用函数,更新每个粒子的全局最优值和局部最优值,直至达到最大迭代次数Smax。

本文提出了无人机部署、卸载方案和计算资源联合优化解决方案,在给定无人机连接情况下,通过PSO算法进行无人机位置部署,使用BCD算法进行任务卸载和计算资源分配。HOEA算法的伪代码展示如算法3,图2展示了该算法的流程图。类似文献[34]分析,整个算法的复杂度主要受PSO算法和BCD算法影响。PSO算法的复杂度取决于粒子维度大小Np和最大迭代次数Smax,在最坏的情况下复杂度为O(NpSmax)。计算资源分配和任务调度优化算法使用BCD算法,该算法最大复杂度约为O((N+M)Gmax),其中Gmax为迭代的最大次数,N和M分别为计算资源优化的变量数和任务分配的变量数,则整个算法的复杂度为O(NmaxNp(N+M)GmaxSmax)。

3 仿真结果分析

本节中仿真环境为配置英特尔i7-12700H,2.3 GHz和32 G RAM的计算机,以验证系统的可行性和所提策略的有效性。该场景下区域数量R=4,无人机数量R=4,每个区域内的地面用户数量L=5,水平位置分布在边长为4 000 m的正方形区域,该区域被平均分成4个区域。区域分布和编号如图3所示,用户随机分布在区域内。表1为仿真参数。

表1 仿真参数

3.1 位置优化的优势

图3展示了无人机的移动方向和无人机连接情况。无人机1会把本地的数据向其他的3个无人机进行卸载,使用矩阵A表述为[0111;0000;0000;0000]。图4展示了所提算法与PSO算法在矩阵A=[0111;0000;0000;0000]条件下的性能对比,所提算法和PSO有类似的收敛速度。但是所提算法相比PSO能取得更小的系统成本,因此所提算法优于PSO算法。

图3 无人机位置变化和连接图Fig.3 Unmanned aerial vehicle position change and connection map

图4 算法收敛性Fig.4 Algorithm convergence

表2展示了有无位置优化下的系统成本。无人机位置部署优化受到地面用户和卸载无人机的影响,具体来说用户将数据卸载到本地无人机时,无人机的部署会影响用户传输能耗和传输时延,当无人机向其他无人机卸载数据时,无人机之间的距离同样会影响无人机传输能耗和传输时延。当无人机随机部署时,对用户和无人机能耗和传输时延造成影响,因此无人机部署是有必要的,表2仿真数据证明了无人机部署优化的必要性。

表2 有无位置优化对比

3.2 所提策略优势

为探究所提策略的优势,将与以下两个方案进行对比。方案1:多个无人机共同服务用户,用户只能将数据卸载到本地无人机,无人机之间不相互卸载数据,且本地无人机都在最优的位置提供计算服务,且使用HOEA。方案2:无人机之间可以相互卸载数据,但是每个无人机最多只能向一个无人机卸载数据,并且在最优的位置卸载数据,且使用HOEA。

3.2.1 数据变化的影响

图5 系统成本随区域1数据量的变化Fig.5 System cost variation with region 1 data volume

图6 各区域卸载比例随区域1数据量的变化Fig.6 Variation of offloading ratio of each region with the amount of data in region 1

图7展示了在所提策略下无人机随区域数据变化的轨迹。无人机部署随着区域数据的变化而变化,尤其随着数据不平衡程度的加深,无人机位置变化剧烈,无人机会相互靠近以此来减少数据传输所带来的时延和能耗。

图7 无人机位置随着计算性能的变化Fig.7 Variation of unmanned aerial vehicle position with computational performance

3.2.2 计算性能变化的影响

图8比较了3种策略在不同计算性能下系统成本的大小,所有策略下系统成本都随着无人机1计算频率的增大而减小。随着无人机1计算性能的增加,所提策略相比其他策略就越有优势。

图8 3种策略系统成本随无人机1计算资源的变化Fig.8 Variation of system cost with unmanned aerial vehicle 1 computing resources for three strategies

从图9(b)～图9(d)中可以看到,随着无人机1计算性能的增大,其他无人机卸载到无人机1上的比例也越大。图9(a)说明,当无人机 1计算性能强于其他无人机时,区域1内的用户数据全部被本地无人机所计算。当无人机之间计算性能相同时,无人机全部采用本地计算的方式,此时所提方案、方案1和方案2三者相同。当无人机之间计算性能差异增大时,计算性能强的无人机所在的区域会选择全部本地计算,计算性能弱的无人机会向其他无人机卸载数据。从图10中可以看到,无人机计算性能的变化对整个无人机的位置并没有明显的影响。

图9 各区域卸载比例随无人机1计算性能的变化Fig.9 Variation of unloading ratio of each region with the computational performance of unmanned aerial vehicle 1

图10 无人机位置随着计算性能的变化Fig.10 Variation of unmanned aerial vehicle position with computational performance

4 结束语

本文构建了无人机群辅助边缘计算的网络模型,通过设计无人机和无人机之间、无人机和用户之间的信息交互以实现在数据或计算能力不均衡的情况下,缓解无人机计算负担,实现整个系统的成本最小化。所提HOEA以PSO为基础,联合优化了多无人机卸载、部署和资源分配方案,并通过仿真验证了所提算法的有效性。此外,文中提出的优化方法可以适用于无人机辅助通信场景下,无人机位置部署和资源分配问题变量耦合的相关问题。在后续的研究中,考虑引入动态多无人机场景,设计无人机的轨迹和任务分配策略,以取得更好的系统性能。此外,无人机群辅助边缘计算场景下数据卸载的安全性也需要格外重视。