加权能耗最小化的无人机辅助移动边缘计算资源分配策略

李 安 戴龙斌 余礼苏*② 王 振③

①(南昌大学信息工程学院 南昌 330031)

②(中国科学院计算技术研究所，计算机体系结构国家重点实验室 北京 100190)

③(北京邮电大学人工智能学院 北京 100876)

1 引言

随着物联网和5G技术的发展，各种新型应用不断涌现，比如目标识别、自动驾驶、图像处理和网络游戏等。这些应用往往会产生大量需要及时处理的实时数据，而通常大部分此类应用的前端物联网设备资源严重受限[1]，这对其计算能力和能耗提出了巨大的挑战。解决这一挑战的一种有效的方法是部署边缘服务器，通过将计算任务卸载到移动边缘计算(Mobile Edge Computing, MEC)服务器，使计算资源距离设备更近，并减少设备的能量消耗[2]。然而是否将计算任务卸载给边缘服务器在很大程度上取决于终端设备与边缘服务器之间的信道。对于基站基础设施有限或没有现有基站的场景(例如，某些偏远的山区或者沙漠地区)使用无人机(Unmanned Aerial Vehicle, UAV)搭载边缘服务器为物联网设备提供数据卸载，以降低终端设备计算能耗是一种很有前景的方案，因为无人机可以利用其灵活的机动性获得良好的空对地视距[3,4]。

现有研究在无人机作为空中移动基站为地面设备提供计算服务方面进行了大量的研究[5,6]，以满足不同的通信目的，比如通信延迟最小化[7]、比特数计算速率最大化[8]、通信能效最大化[9,10]及通信最小保密率最大化[11]等。然而这些研究并未考虑对系统能耗方面的优化，在以最小化能耗为目的的研究中，大致可分为3类：第1类以最小化地面设备能耗为目的；第2类以最小化无人机能耗为目的；第3类以最小化无人机和地面设备的总能耗为目的。

在以最小化地面设备能耗为目的的研究中，文献[12]通过对无人机轨迹、任务数据和计算资源的分配来最小化最大地面设备能耗。文献[13]通过联合优化资源分配和卸载策略将数据卸载到无人机上以最大限度地减少地面设备的能耗。然而这些研究主要关注的是地面设备的能耗最小化问题，并未考虑无人机能耗的优化。而无人机能耗直接关系到任务执行时间的长短。在以最小化无人机能耗为目的的研究中，文献[14]以计算卸载、资源分配和无人机轨迹作为联合优化设计方案，最小化无人机能耗和完成时间，同时还给出了无人机能耗和完成时间之间进行权衡的帕累托最优解。文献[15]研究了具有无线充电技术的无人机辅助MEC系统，其中无人机上装备了能量发射器，可以为地面设备提供能量补充。并通过联合优化MEC服务器的计算频率资源、设备卸载数据量、无人机的发射功率及轨迹，使无人机整体能耗最小化。文献[16]研究了固定翼和旋翼无人机向地面终端提供通信和服务的MEC系统，通过联合优化无人机的3维轨迹和任务缓存策略来最小化无人机整体能耗。然而这些研究主要关注无人机整体能量最小化问题，并没有考虑终端设备的能耗优化。在以最小化无人机和地面设备的总能耗为目的的研究中，文献[17]研究了基于非正交多址接入(Non-Orthogonal Multiple Access,NOMA)的无人机辅助MEC系统，研究了最小化多无人机和地面设备的加权能耗。然而文献[17]并未考虑卸载数据在无人机上的处理延时约束，而且其所采用的无人机推动力能耗模型缺乏通用性。文献[18]在以无人机作为中继的场景下，研究了无人机辅助地面设备将任务数据卸载到地面基站的MEC系统，通过优化数据比特分配、时隙分配、功率分配及无人机轨迹规划使无人机和通信的加权能耗最小化。虽然这些研究考虑了系统的加权能耗，但是其并没研究权重因子会给无人机能耗和地面设备能耗带来怎样的影响，这些文献主要关注如何去最小化加权能耗，而没有关注权重因子对系统能耗的影响趋势。

本文主要的研究贡献如下：

(1)本文结合旋翼无人机飞行能耗模型，提出在给定的任务完成时间内最小化无人机能耗和地面设备能耗的加权和问题。通过联合优化无人机轨迹、资源分配来最终解决本文所提出的问题，使系统的加权能耗最小化。此外，还对无人机能耗与地面设备能耗进行折中考虑，通过改变权重因子的大小，给出了无人机能耗和设备能耗之间的Pareto最优曲线。

(2)所提问题是非凸的，难以直接解决。针对该非凸问题，提出一个基于交替优化算法的两阶段迭代算法来解决该非凸问题。第1阶段在给定地面设备的卸载功率下，利用连续凸逼近方法将子非凸问题变为凸问题，以求解无人机轨迹规划、CPU频率资源分配及卸载时间分配；第2阶段求解地面设备的卸载功率分配。

2 系统模型

考虑如图1所示的无线通信场景，搭载MEC计算服务器的UAV为地面的K个不同设备提供计算服务，其中k∈K,K={1,2,...,K},K表示地面设备集合，并假设K个设备的位置是固定已知的。不失一般性，考虑一个3维欧几里得空间，并将任务完成时间T均匀离散化为N个时隙，第n个时隙的时间间隔可表示为τn=T/N， 其中n∈N,N={1,2,...,N}，且时隙τn足够小以保证无人机的位置在每个时隙内可以被认为是固定不变的[13]。因此，无人机在第n个时隙内的位置可以表示为qn=[xn,yn,H]，其中xn,yn表示无人机的水平位置，H表示无人机固定飞行高度。第k个地面设备的位置表示为uk=[xk,yk]。在每个时隙n内，K地面设备采用时分多址接入(Time Division Multiple Access, TDMA)无人机，以避免不同地面设备之间的干扰[14]。且在每个时隙内采用TDMA接入方式能给地面设备提供更多的卸载机会以减小设备间的接入竞争。考虑到实际应用中无人机在完成任务后需要前往附近的基站进行能量补充。可令无人机起始位置分别为qI和qF，并且无人机在飞行过程中的最大速度为Vmax。因此无人机移动性需要满足的约束可表示为

图1 系统模型

假设无人机与地面设备之间的通信信道为视距传输(Line Of Sight, LOS)链路[3]，而且由于无人机移动性而产生的多普勒效应可以由接收机端完全补偿。因此，对于每个时隙n，无人机和地面设备之间的信道功率增益可以表示为

其中，β0表示在基准距离等于1 m情况下的信道功率增益。那么在第n个时隙内第k个地面设备与无人机之间的信息速率表示为

其中，B表示信道带宽(H z)，γkn=Pknβ0/σ2,Pkn表示第k地面设备第n时 隙的卸载功率，σ2表示无人机处的噪声功率。本文主要参数及其含义如表1所示，在本文中| |·||表示欧氏范数，粗体小写字母表示向量。

脑型脂肪栓塞综合征可表现为头痛、烦躁不安、失眠、易怒、谵妄甚至昏迷、复视、去大脑强直、偏瘫，也可伴有呕吐、尿失禁及自主神经功能紊乱，常早期出现病理反射，脑脂肪栓塞呈弥漫性时较少出现定位体征［2,3,5］。累及中枢神经系统的FES病例常伴有瘀点性皮疹、发热、心动过速及低血压，但肺动脉高压的症状或体征反而较少。FES可能成为术后患者出现中枢神经系统症状（如意识障碍等）的原因之一。

表1 系统参数

3 能耗模型

在整个任务的完成过程中，系统能耗由任务卸载能耗、任务执行能耗和无人机飞行能耗组成。

假设第k个地面设备所需要处理的数据大小为Ik，而每个地面设备在给定的时间内不能单独完成任务，因为每个地面设备的计算能力和电池容量非常有限，所以地面设备不得不将部分数据卸载到具有强大计算能力的MEC服务器上处理。并假设所有地面设备都采用部分卸载模式[15]，这意味着地面设备将会把数据分成两部分，一部分在地面设备本地进行计算，另一部分将会卸载到无人机MEC服务器上进行计算。在每个时隙内，本地设备CPU的计算频率可能是不同的，并且假设地面设备都是单核的CPU，每个地面设备的CPU最大频率均为fmax， 因此第n个时隙内地面设备的CPU计算频率应满足约束fkn ≤fmax,n ∈N,k ∈K。同时无人机上MEC服务器是也单核的CPU，其最大频率为，那么在第n个时隙内无人机分配给第k个地面设备的计算频率为fu,kn，因此无人机上CPU频率需要满约束

(1) 任务卸载能耗：由于所有地面设备在每个时隙内采用TDMA方式接入无人机，所以在每个时隙内K个地面设备将依次接入无人机，其数据卸载过程如图2所示，其中wkn表示第k个地面设备第n个时隙的卸载时间，所以第n个 时隙内K个地面设备的卸载时间之和需要满足的约束[14,17]为

图2 数据比特卸载协议示例

所以在第n个时隙内K个地面设备的卸载能耗之和可以表示为

注意，在任务的卸载过程中，考虑到地面设备数据的发送延时，第n个时隙卸载的数据将会在无人机上第n+1个时隙内计算，所以，第1个时隙内无人机不执行数据的计算，而在最后第N个时隙内，地面设备将会停止向无人机发送数据。

(2) 任务执行的能量消耗：假设地面设备和无人机上MEC服务器的CPU都采用动态电压和频率缩放技术以自适应地控制自身计算频率[11]。那么所有地面设备在本地计算所消耗的能量和在无人机上计算消耗的能量[18]分别为

(3) 无人机飞行能耗：本文采用旋翼无人机搭载MEC服务器。通过将无人机飞行时间离散化，无人机推进能耗模型[19]可表示为

本文的工作主要集中在无人机辅助MEC系统的加权能耗优化。为此，忽略了数据从无人机边缘服务器下传的过程，因为在无人机上处理后的数据大小与原始任务数据大小相比通常是可以忽略不计的[12–18]，而且忽略下载过程能够简化系统模型而不明显影响系统的能耗。

4 优化问题描述

无人机能耗和地面设备总能耗分别表示为

考虑到地面设备能耗相比于无人机能耗非常小，所以需要对地面设备能耗增加权重因子，以此来平衡无人机能耗和地面设备能耗之间的关系。而且无人机作为基础设施的一部分，通常携带较大的电池，而且可以更频繁地充电[17]。相比之下，地面设备的任务卸载和执行耗费了自身相当多的电池能量。因此，在优化过程中需要权重因子来调整不同部分的优先级，以达到无人机能耗与地面设备能耗的折中考虑。所以总的优化目标可以表示为

其中，Etotal表示无人机能耗和地面设备能耗的加权和，ω表示权重因子，用来平衡无人机能耗与地面设备能耗。相应的优化问题建模为

其中，C1表示地面设备卸载时间约束，C2表示每个时隙内在本地和无人机上计算处理的总数据量Dkn。约束C3表示要求第k个地面设备所有时隙计算处理的数据量之和要大于等于给定的任务数据，C4, C5是无人机和地面设备的CPU计算频率资源约束，C6是因果约束，第n个时隙地面设备卸载到无人机上的数据大于等于第n+1个时隙无人机上处理的数据，这样做的目是保证无人机上处理的数据大小不超过无人机接收的数据大小，同时可以让无人机的处理延时在一个时隙以内。相比文献[14,17]在此约束上进行了求和，这将导致不能保证延时在一个时隙以内。C7～C9是无人机轨迹的约束，C10表示第1个时隙无人机上不执行计算，C11表示地面设备最后一个时隙不进行数据的卸载。C12, C13表示地面设备卸载功率约束，C14～C16为非负约束。

问题P1是非凸问题，现有的凸优化技术无法对其直接求解。针对这一问题，本文先将其分解为两个子问题，然后通过一个基于交替优化的两阶段迭代算法来求解原问题的次优解。第1阶段，在给定地面设备的卸载功率下，求解无人机轨迹规划、CPU频率资源分配及卸载时间分配；第2阶段，基于第1阶段获得的解求解地面设备卸载功率的分配。

5 优化问题求解

第1阶段，P1的子问题为CPU频率资源分配、卸载时间分配和无人机轨迹优化，其中卸载功率Pkn是固定的。第1阶段子问题表述为

因此，无人机飞行能耗可重写为

对式(17)利用泰勒展开，问题P2的约束C6可转换为

引入松弛变量后，问题P2中约束C6转化为式(18)，不难看出式(18)为凸约束。在固定Pkn下，非凸问题P2通过引入松弛变量un,ykn转化的近似凸问题为

其中，约束C17, C18要求松弛变量非负。

因为P3是一个凸优化问题，所以可以利用MATLAB中的CVX工具箱来求解[17]。

第2阶段求解卸载功率分配。基于第1阶段子问题获得的解，作为第2阶段子问题的初值。第2阶段优化问题表述为

其中， C1′为因果约束，相对于原问题P1中的约束C6。

注意到问题P4的目标函数和约束条件都是凸的，所以该问题可直接由CVX工具箱求解。当第2阶段问题P4求解后，将得到的卸载功率作为给定值返回到问题P3，以求解第1阶段问题。如此交替迭代优化直到收敛到给定的精度。具体的两阶段资源分配策略如表2算法1所示。

表2 算法1：基于交替优化算法的两阶段资源分配策略

6 仿真结果及分析

本节给出仿真结果，以评估所提出算法的有效性。考虑一个无人机辅助的MEC系统为随机分布在一个矩形区域内5个地面设备提供计算服务。具体参数设置如表3所示。

表3 仿真参数值

图3表示不同权重因子下无人机的飞行轨迹，可以明显看出权重因子对轨迹的影响。当权重因子由小变大时无人机的轨迹将会逐渐靠近地面设备，这是因为当权重因子增大时，加权下的地面设备能耗在总的系统加权能耗中占比增大，所以无人机将会靠近地面设备，以减少地面设备的能量消耗。

图3 不同权重因子下无人机的飞行轨迹

图4比较了本文提出的基于交替优化算法的两阶段资源分配策略与固定功率、固定轨迹、最小化无人机能耗3种基准方案比较的Pareto最优曲线。从图4可以看出，与固定轨迹优化相比，当所消耗的无人机能量相同时，基于交替优化算法的两阶段资源分配策略消耗的地面设备能量更少。同时与固定功率优化和最小化无人机能耗方案[14]相比，当无人机能耗小于4.1×104J时，两阶段资源分配策略和这两种方案所消耗的地面设备能量相近，而当无人机能耗大于4.1×104J时，两阶段资源分配策略所消耗的地面设备能量将大幅低于这两种方案。综上所述，在消耗相同的无人机能耗下，通过对地面设备和无人机能耗的加权优化可以很大程度地降低地面设备的能耗。同时也可以看出在相同的地面设备能量需求下，本文提出的两阶段资源分配策略所消耗的无人机能量最低。

图4 不同优化方案下无人机能耗与地面设备能耗的关系

图5比较了在权重因子相同时不同方案下地面设备能耗的大小关系，可以看出本文提出的两阶段资源分配策略在降低地面设备能耗方面要优于其他方案。同时可以看出所提算法能够较快地收敛。

图5 在ω = 200时不同优化方案下地面设备能耗的大小

图6表示每个时隙不同地面设备的卸载时间分配，图7表示每个时隙无人机分配给不同地面设备的计算频率分配。结合图6、图7可以看出每个地面设备的卸载时间和其对应在无人机上分配的计算频率几乎是同步的，这也验证了数据在无人机上的处理延时不超过一个时隙。而且从图中可以看出每个地面设备只在无人机靠近的时候才增大自身的卸载时间，而当无人机远离时，地面设备将会减少卸载时间。相应的无人机将会在靠近地面设备时，因为收到的数据量增加而提高无人机上分配给地面设备的计算频率。

图6 在ω = 200,T = 80 s时地面设备在不同时隙内的卸载时间

图7 在ω = 200,T = 80 s时无人机分配给地面设备的计算频率

7 结束语

本文研究了基于加权能耗最小化的无人机辅助移动边缘计算系统的最优资源分配问题。通过联合优化无人机轨迹以及资源分配最小化无人机能耗和地面设备能耗的加权和。并通过改变权重因子来得到无人机能耗与地面设备能耗的Pareto最优曲线。由于所求优化问题是非凸的，难以求解，因此本文通过基于交替优化的两阶段迭代算法来找到原问题的次优解。仿真结果表明所提出的基于交替优化的两阶段资源分配策略在降低系统能耗方面优于固定功率、固定轨迹和最小化无人机能耗的基准方案，而且可通过改变权重因子来极大地减少地面设备的能耗，这在一些地面设备能量不足的偏远地区对其地面设备能耗的节省是有意义的。下一步将在本文的基础上考虑被服务的区域存在大量需要进行数据卸载的物联网设备，此时单个无人机由于有限的计算资源，同时又难以靠近区域内的每个设备进行协助计算而导致不能完成任务的情况下，考虑多无人机协助区域内地面设备数据的计算。