源自：《系统工程与电子技术》    

作者：余雪勇  朱烨  邱礼翔  朱洪波

摘 要

针对复杂地形中地面基础设施无法有效提供可靠通信和密集算力的问题,首先提出一种基于无人机(unmanned aerial vehicle, UAV)托管计算资源的卸载方案。考虑用户终端的计算需求,计算任务的时延约束,以及UAV的能量约束,构建了一种以最小化用户终端计算和卸载能耗为目标的UAV辅助边缘计算模型。其次,通过将原非凸的问题分解为两个凸优化子问题,采用了基于块坐标下降的两步迭代优化算法,联合优化了用户终端本地任务的数据量、卸载任务的数据量以及UAV的轨迹,实现约定时间内用户终端能耗的最小化。仿真结果表明,所提策略适用于优劣不同的信道条件,能够在保证用户终端完成任务的同时,使得用户终端能耗方面优于其他基准方案。

关键词

移动边缘计算; 无人机通信; 资源分配; 轨迹优化

0 引 言

随着物联网(internet of things, IoT)技术的发展,萌生了许多移动端的应用服务,例如增强现实(augmented reality, AR)、音视频业务、人脸识别、轻量级的深度学习应用等[1]。这些应用服务往往时延敏感且需要用户终端具备较强的计算能力[2]。而对于移动用户的终端设备,其有限的能量和计算能力无法很好的满足用户的应用需求[3-5]。

移动边缘计算(mobile edge computing, MEC)通过将服务器部署在靠近用户的边缘侧,使资源受限的用户终端可以将计算密集型任务卸载到边缘服务器去执行,大大减缓用户终端的计算压力[6]。但是,复杂的环境会带来高昂的基础设施部署成本,尤其对于偏远地区以及抢险救灾类的环境。

近来,无人机以其在移动性和成本上的优势被应用到无线通信网络中。但是续航受限的无人机上执行计算密集型任务可能会导致响应时间变慢和大量的能耗,并且还可能对电池寿命造成损害,最终可能影响任务的成功,特别是对于一些实时应用的任务,如森林火灾探测或探索无人区任务[7-8]。此外,地面用户与无人机之间的信道条件会直接影响用户终端与无人机的通信能耗,这就需要根据用户终端的位置合理规划无人机的飞行轨迹。

基于此,近年来许多学者对无人机辅助边缘计算问题进行了研究。文献[9]提出了无人机作为移动cloudlet辅助地面终端执行计算密集型任务,通过联合优化比特分配方案和无人机飞行轨迹,研究了不同的接入条件下终端能耗最小化问题。文献[10]通过引入二进制变量以确定用户是否进行卸载(本地计算或卸载计算),充分考虑了服务质量(quality of service, QoS),差异化了不同用户的任务复杂度,以QoS指标和无人机续航为约束,最大化用户终端计算卸载的数据量。文献[11]研究了一种具有异构云下多用户MEC系统中的任务卸载。用户的任务通过无线信道卸载到边缘云后,可以通过因特网进一步转发到远程云。基于动态编程提出了一种联合优化用户的带宽资源和计算资源分配的节能算法,在满足不同任务的延时标准下最小化用户设备的总能耗。文献[12]划分了无人机通信和计算任务的运动状态,通信时沿轨迹飞行而计算任务时保持悬停。以时延、无人机能耗以及用户终端的任务数据量为约束,联合优化比特分配方案和无人机轨迹,最小化用户终端的能耗。

在上述研究中,存在以下几点问题。

• (1) 无论是全卸载策略,还是二进制卸载策略,用户终端的任务在同一时刻只能在本地或边缘侧执行,由于终端用户的本地计算资源不足,任务只在本地进行计算并不合理。同时由于完全卸载产生的延迟问题、带宽浪费问题以及无人机自身电力有限,数据只在无人机边缘侧进行处理存在较大局限。

• (2) 忽略了任务过程中用户终端本地计算的时延。这可能会导致用户计算卸载和本地计算不同步完成的后果。

• (3) 缺乏对用户终端与无人机之间信道条件优劣的讨论。在信道信噪比较差的情况下,不能保证提出的模型与方案仍具备有效性和可靠性。

为了解决上述问题,本文研究了一种以最小化用户终端计算和卸载能耗为目标无人机辅助的边缘计算系统,对地面终端计算资源进行合理分配,从而实现终端能耗的最小化,对用户持续在线有着一定的意义。因此本文为了实现这一优化策略,主要作出的贡献如下。

• (1) 在MEC系统中建立了无人机的轨迹设计和终端用户任务卸载策略模型。为了解决完全本地计算或全卸载的弊端,对于用户终端任务可分割的场景,针对计算卸载策略,本文采用部分卸载策略,即用户终端在计算卸载的同时,保留一部分任务在本地进行计算。同时考虑了系统中的时延需求,解决了用户计算卸载和本地计算不同步问题。

• (2) 将逐次凸优化技术和块坐标下降算法进行结合,提出了一种基于块坐标下降的两步迭代算法。同时对算法的复杂度进行分析,并通过仿真结果进一步进行验证。

• (3) 对不同的信道条件下的用户终端能耗进行讨论。分析了不同的信道条件下本文的所提出的卸载策略对终端用户能耗的优化效果。

1 系统模型

无人机辅助多用户边缘计算系统如图1所示,由安装MEC服务器的无人机和地面k(k=1,2,…,K)个用户终端组成。其中,每个用户终端都具备一定的计算能力,满足本地执行简单任务的需求。相对地,无人机搭载MEC服务器具备更强的计算能力,能够快速完成计算密集型任务,为用户终端提供边缘计算服务。在飞行过程中同步执行卸载任务。

图1 无人机辅助多用户边缘计算系统

假设所有用户终端的任务均在时长T内完成。利用三维欧几里德坐标表示的方法,可以分别表示出用户终端和无人机的具体位置。用户终端分布在平面上,第k个用户终端的位置可表示为如下形式:

zk=(xk,yk,0),k∈{1,2,…,K}

(1)

式中:xk和yk分别表示第k个用户终端在平面上的横坐标和纵坐标。

假设无人机中存储了所有用户终端的位置信息,并以固定高度H在空中飞行,其瞬时位置可以表示为如下形式:

q(t)=(x(t),y(t),H),0≤t≤T

(2)

无人机从起点出发沿飞行轨迹向终点飞去,为沿途的用户终端提供边缘计算服务,由此无人机起始和结束的位置需要满足如下约束:

(3)

将时长T等分为N个时长为Δ的时间帧:

(4)

由于每帧的时长Δ都足够小,每一帧中无人机的位置可以近似看作不变。藉此,连续的无人机轨迹可以离散为N帧的无人机位置的集合。于是,式(2)和式(3)可以进一步表示为如下形式:

q[n]=(x[n],y[n],H),n∈{1,2,…,N}

(5)

(6)

已知第n帧的无人机位置,可以表示出第n帧无人机的速度v[n],并规定飞行速度的上限值vmax:

(7)

假设通信中多普勒频移可以被接收端补偿,信道质量取决于无人机和用户的之间的链路,由于无人机链路都为视距链路,即信道增益服从自由空间损耗模型。则在第n帧的用户终端k与无人机之间的平均信道增益hk[n]可以表示为如下形式:

(8)

式中:dk[n]指第n帧的用户终端k与无人机之间的欧氏距离;ρ0指在参考距离为1 m时,传输功率为1 W时的接收功率。

1.1  计算卸载模型

为了避免用户终端在卸载过程中相互干扰,采用时分多址(time division multiple access, TDMA)协议,将每帧的时长Δ等分成K份,并预分配给各个用户终端进行上行的计算卸载和下行的下载计算结果,以保证各用户的卸载时隙独立。由于MEC服务器计算得到的结果数据量很小,一般可以忽略用户终端下载结果所花费的通信时延,用Δ/K表示第n帧用户终端k计算卸载的时长。

设第n帧用户终端k计算卸载的任务数据量为

根据标准信息理论定义[13],第n帧用户终端k计算卸载所产生的通信能耗可以表示为如下形式:

(9)

式中:N0是具有零均值的加性高斯白噪声的功率谱密度,单位为dBm/Hz。

1.2   本地计算模型

类似于文献[14],计算能耗与频率的三次方成正比。设第n帧用户终端k本地计算的任务数据量为

则第n帧用户终端k本地计算的能耗可以表示为如下形式:

(10)

式中:Ck指的是任务每比特数据需要CPU运行的周期频率数,用于表示用户终端k任务的复杂度;γk表示用户终端k本地处理器的有效开关电容;fk表示用户终端k本地CPU的主频(即CPU的时钟频率),用于描述本地计算能力。

由上述条件,可以表示出在TDMA方式下用户终端k在N个时隙内完成本地计算所需要的时间。由于所有任务必须在时长T内完成,用户终端k本地计算也需要在时长T内结束,应满足如下约束:

(11)

1.3   无人机能耗模型

由于无人机的计算能耗与频率的三次方成正比[14],设无人机搭载的边缘服务器CPU的有效开关电容为γ c,主频为fc,则第n帧无人机处理用户终端k卸载的任务产生的能耗

为

(12)

无人机在边缘计算的同时保持飞行状态,考虑文献[12]中的飞行能耗模型,假设无人机每一帧的飞行能量仅依赖于速度,故在第n帧飞行产生的推进能耗Ef[n]为

(13)

式中:κ=0.5MuavΔ,Muav表示无人机的质量(包括其载重)。

1.4  目标问题

假设用户终端的任务可以被分割,计算任务可以分配到用户本地和无人机MEC服务器上执行。本文采用部分卸载策略,联合优化用户终端本地计算的任务量、计算卸载的任务量以及无人机的轨迹以最小化用户终端的能耗。

基于上述的模型,用户终端的能耗问题可以描述为问题P1:

s.t.

(14)

在问题P1中,C1规定了无人机的能量上限,E0表示无人机的总能量;C2保证了所有用户终端的任务都能在时长T内被完成,Lk表示各个用户终端的任务数据量;C3保证了用户终端k本地计算能够在时长T内结束;C4保证了在任意一帧内用户终端k的任务量都是非负的;C5规定了无人机飞行轨迹的起点和终点;C6限制了无人机飞行的速度。

2 优化过程

由于问题P1的目标函数存在两个优化变量的耦合且约束条件C1非凸,问题P1具有非凸性。对于非凸问题,因为其复杂程度过高,往往难以利用传统凸优化技术直接求解。文献[15]提出了一种块坐标下降法。其在解决优化问题时,一次只更新一个或几个变量块,相对于一次更新所有的变量块的复杂度要低的多。基于这种思想,本文采用了一种基于块坐标下降的两步迭代优化算法对问题P1进行求解。

首先,需要将目标问题P1分解成两个凸的子问题。其次,依次通过凸优化算法对子问题进行求解。最后,基于块坐标下降法进行全局优化,求解用户终端能耗的最小值。

由于用户终端计算卸载所产生的通信能耗

既与无人机的轨迹q[n]相关,也与计算卸载的任务量相关,这导致了目标函数的非凸性。为了进一步根据优化变量将目标问题分解成子问题,首先需要对表达式等价改写为f1(x1)f2(x2)形式:

(15)

式中：

从式(10)可知,用户终端本地计算的能耗

仅与本地计算的任务量相关。因此,类似式可以等价改写为以为变量的函数形式:

(16)

依此,问题P1与如下形式等价:

s.t.C1,C2,C3,C4,C5,C6

(17)

问题P1实质上由两个子问题组成,分别是用户终端任务量的分配问题和无人机的轨迹优化问题。

2.1   用户终端任务量的分配问题

固定无人机的初始轨迹q[n],则问题P1转变成一个以用户终端本地计算的任务量和计算卸载的任务量为优化变量,最小化用户终端能耗的问题。由于目标函数中初始轨迹q[n]在该子问题中为一常数,可以将问题P1最小值问题等价改写成求解如下的问题:

s.t.C1,C2,C3,C4

(18)

由于f0和f1都是凸函数,问题P1.1的目标函数可以看作是两个凸函数之和,依然具有凸性质。对于问题P1.1,可以利用CVX[16]工具,通过标准凸优化技术进行求解,得到第n帧用户终端k最优的本地计算的任务量

和最优的计算卸载的任务量

2.2  无人机的轨迹优化问题

以问题P1.1中解得的第n帧用户终端k最优的本地计算的任务量

和最优的计算卸载的任务量为基础,问题P1可以转变为以无人机的轨迹为优化变量,最小化用户终端能耗的问题。类似于问题P1.1方法,求解问题P1的可以进一步等价改写成问题P1.2:

(19)

问题P1.2的目标函数是关于q[n]的凸函数,且限制条件也是凸的,因此问题P1.2是一个凸问题。对于问题P1.2,同样可以利用CVX工具,通过标准凸优化算法进行求解,得到第n帧无人机最优的位置qopt[n]。

2.3   全局优化和复杂度分析

基于子问题P1.1和P1.2得到的最优解,利用块坐标下降法进行全局优化。具体过程如算法1所示。

在以上分析的基础上,算法1中介绍了详细的迭代算法过程,其中括号内变量为迭代变量i,时隙数n置为下标。在其他变量不变的情况下,通过依次优化无人机的位置、终端用户的本地计算数据量和卸载到无人机上的数据量,可以求解式(18)和式(19)。给出的算法步骤3的收敛性问题在文献[17]中进行了分析,在本文中不作介绍。在步骤4中,在i+1次迭代中将全局迭代变量替换为

和目标函数中第i+1次迭代用户总体能耗值小于第i次迭代中的用户整体能耗值。因此,随着迭代次数的增加,目标函数值逐渐减小。这一结果符合函数的收敛性。因此,所提出的迭代算法能够满足收敛性。算法1的复杂度主要来自两个方面：第一,用户终端计算任务的分配;第二,解决P1和P2问题的CVX法。令L1、L2分别表示算法1外层循环的迭代数和内层循环的迭代数,l1表示块坐标法的容错精度,由文献[18-20]可知,若用户终端数量为K,时隙数为N, 则KN+K2N表示用户计算资源分配迭代所产生的复杂度。由于CVX工具所采用的求解器SDPT3使用了原对偶内点法来进行问题的求解,所以这里内层的迭代复杂度由原对偶内点法的算法复杂度所决定,则CVX的算法产生的复杂度可以表示为L2N3.5。因此,算法1的总计算复杂度为其中,O(·)表示“大O表示法”[18]。

3 性能分析

在这一部分中,通过大量的数值实验验证了本文所采用的基于两步迭代的块坐标下降法的有效性。利用Matlab R2019a进行仿真实验,实验设备为Dell OptiPlex 7070 MFF,CPU为Intel Core i5-9500T,内存为16.0 GB。所采用的算法收敛阈值ε设置为10-1。

3.1   环境设置

本文的仿真环境在开阔无障碍的环境中设置了3个用户终端,分布在10 m×10 m平面中[11,14],其坐标分别为z1=(0,10,0) m,z2=(10,5,0) m,z3=(10,0,0) m。而无人机的起始位置为q[0]=(0,0,5) m,终点位置为q[N]=(5,0,5) m,始终在同一水平高度飞行,其初始速度为v0=(q[N]-q[0])/T,且无人机的飞控中预置各个用户的位置信息。假设任务时间范围T

[0.5,5]s,时隙数N=50,信噪比SNR为ρ0/(N0B)=-5 dB。各个用户的任务量分别为L1=8 Mbits、L2=12 Mbits、L3=4 Mbits,任务复杂度分别为C1=1 000、C2=1 500、C3=2 000。

除了上述预设参数外,其他的相关参数如表1所示。

表1 仿真参数

本文参考文献[9,21-22]中的仿真场景,将所提的节能卸载策略与其他基准方案进行了性能比较。基准方案主要包括以下3种。

(1) 不进行优化。由于在时长T内用户终端只靠本地计算完成不了任务,此方案中用户终端默认采用全卸载的策略,且在每个时间帧内,用户终端计算卸载的任务数据量都相同。另外,无人机的初始轨迹为起点到终点的一条直线,保持匀速飞行。

(2) 只对任务量的分配进行优化。保持无人机的匀速飞行的轨迹不变,优化每个时隙用户终端本地计算的任务量和计算卸载的任务量。

(3) 只对无人机的轨迹优化。保持计算卸载任务量的分配方案不变,优化无人机的飞行轨迹。

3.2   结果分析

 3.2.1   算法的迭代分析

图2为T=0.5 s时,用户终端能耗的优化过程,动态的展示了迭代优化过程中用户终端能耗的变化情况。由算法1可知,基于块坐标下降的两步迭代优化算法的终止条件为前后两次迭代的用户终端能耗差值小于阈值ε。如图2所示,横坐标表示迭代次数,纵坐标表示用户终端的能耗。可以发现,在第1次迭代的过程中,用户终端能耗急剧降低。在第2～4次迭代的过程中,用户终端能耗缓慢下降,并趋于平稳。在第4次迭代之后,用户终端能耗的数值不再发生改变,进入收敛状态。从整个收敛过程中可以发现,基于块坐标下降的两步迭代优化算法特点在于能够实现用户终端能耗的快速下降,并在几次迭代内就达到数值收敛,证明所提算法的收敛速度极快,具备实用意义。

图2 用户终端能耗的优化过程

 3.2.2   无人机的轨迹分析

图3为无人机的飞行轨迹图。无人机的初始轨迹为一条起点到终点间隔均匀的直线,对应了初始设定中无人机以匀速沿直线飞行。

图3 无人机的飞行轨迹

而优化后的飞行轨迹则是一条向用户终端2倾斜的外凸曲线,表明进行优化后无人机倾向于靠近用户终端2,提供计算卸载服务。从各用户终端计算任务的初始设定不难发现,任务量L2>L1>L3,复杂度C3>C2>C1,用户终端2的任务相较其他两者难度处理更大,卸载需求更明显,因此无人机倾向于在若干个时隙内靠近用户终端2,进行小范围的盘旋飞行。

 3.2.3   用户终端的计算卸载分析

图4为T=0.5 s时,优化后用户终端在不同时隙计算卸载数据量和本地计算数据量的变化曲线。由于在本实验中,用户终端设置的特点为低功耗和性能受限,因此本地计算的能耗开销很低。如图4(a)所示,用户终端倾向于利用本地算力,以较低的计算能耗处理一部分计算任务,因此,用户终端本地计算的数据量是一条直线,在每个时隙都根据自身性能处理尽可能多的本地处理任务。

图4 用户终端的计算卸载过程

图4(b)展示了用户终端如何分配剩余的任务数据量进行计算卸载。结合图3可以发现,在无人机靠近某个用户终端时,其计算卸载的数据量会处于一个高点。特别的,用户终端2在第33个时隙到第40个时隙之间持续以较大的数据量进行计算卸载,这正好对应了图3中无人机的优化轨迹靠近用户终端2,且在其附近悬停了这段时间。

 3.2.4   用户终端的能耗分析

图5给出了信噪比SNR=-5 dB的信道条件较差环境下,用户终端在不同优化方案下的整体能耗表现。如图5所示,随着任务时间T的增加,用户终端的能耗呈下降的趋势。这是因为在TDMA的方案下,T越大,用户终端上行的卸载时隙的时长就越长,相邻时隙间无人机的位置变化就越小,这意味着通信距离的改变也就越小,这节省了用户终端计算卸载的通信能耗。

图5 用户终端的能耗(SNR=-5 dB)

其次,可以发现用户终端的能耗下降的速度逐渐变缓,近乎收敛于某一个值。这是因为当任务时间T足够长的情况下,本地和无人机的处理器有足够的时间进行性能的释放。而在信道恶劣的环境中,通信的能耗开销高于本地计算的能耗开销,这使得用户终端会任务时间T内优先选择本地计算,对于在时长T内完成不了的任务,再选择计算卸载。因此用户终端的能耗会随着时长T的增大逐渐收敛至统一。

此外,对比各方案的优化效果可以发现,优化任务量的分配对用户终端的能耗有显著的节能效果,且随着时长T的增大,优化效果进一步提升。特别的,当T=5 s时,优化任务量分配(73.16 J)的方案相较于不优化(184.09 J)的方案,能耗降低了60.26%。原因与用户终端的能耗下降速度变缓相似。受到信道条件的影响,计算卸载带来的通信能耗剧增,超过了本地计算的能耗开销,任务量的分配在此时的作用尤为明显。随着时长T的增加,会进一步将任务量分配到本地,以节省能源。

而信道条件较好的情况下,如图6所示,在信噪比SNR=20 dB时,优化无人机的飞行轨迹则会有显著的效果。特别的,当T=5 s时,优化无人机飞行轨迹的方案实现了能耗降低53.21%。这是因为无人机与用户终端之间的距离会直接影响到用户终端计算卸载的通信能耗。而信道条件良好的情况下,计算卸载的通信能耗得到了极大的改善,此时保证距离合适的视距信道就显得格外重要。

图6 用户终端的能耗(SNR=20 dB)

最后,无论信道条件的优劣,本文提出的基于联合优化的节能卸载策略都取得了良好的性能表现。相较于其他3种基准方案,进一步降低了用户终端的能耗,且随着时长T的增大,优化效果越发明显。

如图5所示,在信噪比SNR=-5 dB,T=5 s时,联合优化(21.80 J)较不优化(184.09 J)、优化任务量分配(73.16 J)和优化无人机轨迹(86.14 J)这3种基准方案,用户终端的能耗分别降低了88.16%、70.20%和74.69%,相较于文献[9]中同场景下优化方案移动终端总能耗降低了20.1%。

如图6所示,在信噪比SNR=20 dB,T=5 s时,联合优化(0.1330 J)较不优化(0.5822 J)、优化任务量分配(0.4394 J)和优化无人机轨迹(0.2724 J)这3种基准方案,用户终端的能耗分别降低了77.16%、69.73%和51.17%,相较于文献[9]中同场景下优化方案移动终端能耗降低了10.3%。

 3.2.5    任务执行过程的分析

图7为联合优化方案下用户终端在不同时隙累计执行的任务数据量示意图,展示了用户终端在不同时隙累计执行的任务数据量。3个用户终端的任务数据量分别为8 Mbits,12 Mbits,4 Mbits。从图中可以明显看出,在时隙n=20时,用户累计执行的任务数据量变化率明显变快,这是由于随着优化算法的迭代,逐渐趋于收敛,这时无人机会更快的更新位置实现用户数据的高效卸载。

图7 用户终端累计执行的任务数据量

在当时隙n=50时,所有用户终端均完成了所有计算任务。因此,联合优化的方案不会对用户终端在时长T内完成任务产生影响,同时也可证明所采用的算法具有较快的收敛性。

综上,联合优化用户终端本地计算的任务量、计算卸载的任务量以及无人机的轨迹的节能卸载策略能够有效的、可靠的降低用户终端的能耗。

4 结束语

本文构建了一种无人机辅助边缘计算系统,利用无人机搭载边缘服务器以增强地面移动用户终端设备的计算能力。针对用户终端能耗受限的问题,提出了基于块坐标下降的两步迭代优化算法,联合优化用户终端本地计算的任务量、计算卸载的任务量以及无人机的轨迹,实现了用户终端能耗最小化的目标。实验结果表明,无论信道条件优劣,基于块坐标下降的两步迭代优化算法都能在保证用户终端完成任务的同时,有效的降低用户终端的能耗,达到节能的效果。下一步将考虑计算密集型任务下移动用户对于低时延的要求,改进计算卸载的策略,以达到用户终端能耗与系统时延之间的均衡。

声明:公众号转载的文章及图片出于非商业性的教育和科研目的供大家参考和探讨，并不意味着支持其观点或证实其内容的真实性。版权归原作者所有，如转载稿涉及版权等问题，请立即联系我们删除。