无人机辅助边缘计算的能量效率最大化算法设计

吴启晖，吴伟,2

（1.南京航空航天大学电磁频谱空间认知动态系统工信部重点实验室，江苏 南京 211106；2.南京邮电大学通信与信息工程学院，江苏 南京 210003）

1 引言

随着信息通信技术的高速发展，人类社会开始进入万物互联的信息时代。智能移动设备的空前普及为许多新型智能应用提供了强大的平台，与此同时也带来了诸多新的挑战。智能化的应用（如人脸识别、交互游戏、自动驾驶等）往往计算任务密集且对时延敏感[1-2]，然而，大多数移动终端计算能力和电能储备有限，无法独立胜任当下需求。移动边缘计算（MEC,mobile edge computing）通过将云计算[3]和信息技术服务部署到网络边缘，提供辅助计算，可有效降低任务处理时延、避免网络拥塞、提高终端设备电池使用寿命[4]。

近年来，移动边缘计算被广泛研究用于提升蜂窝网络的能量效率、减少时延或最大化网络运营的系统效用[5]。文献[2]研究了非线性无线供能的MEC网络中计算能效最大化问题，在时延受限的情况下，分别对时分多址接入（TDMA,time division multiple access）和非正交多址接入（NOMA,nonorthogonal multiple access）方式下的部分卸载与二元卸载进行了分析比较。针对部署缓存的NOMA异构网络下的基站用户匹配及功率分配问题，以最大化缓存收益为目标，对功率资源和用户调度进行了合理设计，显著提升了系统吞吐量和时延等性能。在安全通信方面，针对有恶意窃听者的情况，文献[6]引入安全中断概率度量NOMA MEC 系统的安全性能，以最小化加权和能耗为优化准则，设计了最佳的资源分配方法。在此基础上，文献[7]进一步探究了在用户设备能量受限的情况下安全中断概率最小化问题，并给出了相应的最优安全卸载速率和功率分配方案。针对中继辅助的跨蜂窝移动边缘计算网络，文献[8]提出了一种混合中继转发协议以实现两终端设备之间的单向计算结果共享，利用非严格块坐标下降法有效地实现了执行时延与网络能耗之间的均衡。对原始数据压缩后再进行传输可有效提升网络吞吐量，基于此，文献[9]提出了一种MEC 辅助的计算与中继方案，以增强点对点通信系统吞吐量，通过对动态压缩率和发送功率进行联合优化设计，实现了能耗和时延的有效均衡，突破了传统点对点通信系统的性能瓶颈。

无人机（UAV,unmanned aerial vehicle）辅助的边缘计算与通信具备可灵活部署、机动性强、视距通信等诸多天然优势。利用无人机的灵活移动特性并给其配备具有一定运算处理能力的计算服务器，可实现对终端设备计算任务的高能效、低时延辅助处理[9-13]。与此同时，无人机辅助的边缘计算系统也面临着诸多现实挑战。无人机能量有限，如何高效地利用有限的通信和计算资源，设计最佳的飞行轨迹，最终以一种高能效的方式快速完成任务的辅助计算和共享，是研究者普遍关注的问题。此外，无人机飞行抖动及方向变化带来的信号波束实时动态调整、多无人机辅助时的无人机与地面用户动态关联等现实问题都给无人机辅助的边缘计算带来不少的挑战。文献[9]给无人机配备处理服务器以帮助多个用户终端设备计算卸载的任务，通过对无人机的飞行轨迹和任务卸载比特划分进行联合优化，实现了总的移动计算能耗最小化。进一步地，考虑到终端设备自身储能的局限性，文献[10]将无线供能模块引入无人机设备，在辅助地面终端任务计算的同时利用视距信道对其进行无线供能，相较于传统的地面基站无线供能更加高效灵活。通过利用交替优化算法，在部分卸载和二元卸载这2 种模式下最大化系统的计算速率。在无人机和可利用地面基站同时存在的情况下[12]，无人机在充当移动边缘计算辅助器的同时可作为空中中继，将部分计算任务二次卸载到地面基站，以减轻无人机的计算负担。为实现较高的系统能效，复杂的计算资源调度、带宽分配和无人机轨迹优化问题必须得到解决。文献[13]针对部分卸载模式下的多无人辅助边缘计算，综合考虑了用户关联、计算频率、信息传输功率、频谱资源块、多无人机轨迹等多因素的联合设计，以获得最佳的计算能效。

以上无人机辅助的边缘计算研究工作都关注于无人机协助地面终端计算并将结果反馈回地面终端的应用场景。不同于现有的研究工作以及文献[8]提出的依赖地面固定基站的边缘计算与结果共享系统，本文考虑了一种如图1 所示的无人机辅助边缘计算与结果共享系统，提出了一种两阶段交替优化算法以最大化系统能量效率。首先，利用Dinkelbach方法将建模的非线性分式规划问题转换为一类等价的参数问题。其次，通过对子问题的分析，给出了中央处理单元频率和数据比特量的闭式解。最后，所获得的解揭示了源节点选择卸载与共享自身数据和中继选择转发计算结果的必要条件，以及实现更高能量效率的方法。仿真结果表明，与传统算法相比，本文所提算法在能量效率方面可获得高达20 倍的性能提升。

2 系统模型及问题描述

如图1 所示，考虑一种无人机辅助的边缘计算与结果共享系统，该系统包含一个源节点S（位于地面）、一个目的节点D（位于地面）和一个无人机（位于空中），且均假设它们为单天线设备。假设S 和无人机都内置有独立的通信模块和计算处理单元。部署在室外环境下的S 捕获到图像、自然语言等信号数据并将该数据的处理结果共享给D。假设S 和D 的位置都是固定的，且因障碍物遮挡的原因，二者之间的直达无线链路无法进行有效的信息传输[14-15]。另外，小型化低功率的S 在功率和计算能力方面也十分有限。因此，部署空中无人机以辅助S 到D 之间的信息传输以及对S 所捕获数据的处理。进一步地，假设采用部分卸载的边缘计算模式且S 可同时进行数据的传输和本地计算。与此同时，假设无人机中继内配置一定大小的缓存来存储等待计算的卸载任务。因信息收发和任务计算分别在不同功能单元进行，故可同步进行[12]。

图1 无人机辅助的边缘计算与结果共享系统

采用三维笛卡尔坐标系，其中S 和D 的三维坐标分别为(0,0,0)和(xd，0，0)，且在有限时长T内，无人机的飞行高度固定为H。为便于探究，将有限时长T划分成N个等长的时隙，则每个时隙的时长，其中τ的值足够小以至于无人机在每个时隙内的坐标保持不变。因此，无人机在时长T内的飞行轨迹可表示为三维空间中N个离散坐标点的形式(x[n],y[n],H)，其中n∈Ν,Ν={1,…,N}。进一步地，假设无人机的起始和最终方位可被预先设定，将其分别表示为(x0,y0,H)和(xF,yF,H)。

为简便起见，假设无人机采用频分双工通信模式且各频段带宽相等，无人机与地面通信节点（S和D）之间的无线信道主要为视距信道。因此，在第n个时隙，S 和无人机以及无人机和D 之间的信道增益可分别表示为

其中，β0表示在基准距离d0=1情况下的信道功率增益，dsr和drd分别表示S 与无人机和无人机与D之间的距离。在快衰落信道模型下，系统涉及的无线信道在时长T内保持稳定状态。

假设S 所获取的原始数据逐位独立且可按任意比例进行拆分以便并行处理。据此，S 可采用如下2 种方法协作的方式完成数据处理结果的共享：1)S在本地完成部分原始数据的计算处理，然后在无人机中继的辅助下将计算结果发送给D；2)S 将余下的原始数据卸载到无人机，无人机进行辅助计算处理并将结果发送给D。进一步地，假设方法1)中S的计算时延和无人机的译码时延分别为一个时隙，方法2)中无人机的计算准备时延和计算处理时延也分别为一个时隙。

2.1 本地计算与结果共享

1) S 本地计算

捕获到原始数据之后，S 同步执行任务的本地计算和卸载。针对本地计算，令C表示执行单位比特计算任务所需的CPU 循环次数，ρ∈(0,1)表示数据压缩率。为高效利用有限的能量资源，S 采用动态电压和频率缩放技术以自适应地控制计算能量消耗。将S在第n时刻的CPU频率表示为fs[n]循环每秒。因此，在第n时刻S 计算的任务比特量和相应的能耗[6]分别为

其中，γs表示S 依赖于芯片结构的有效电容系数。

2) 无人机中继辅助S 到D 的计算结果共享

随着本地计算的进行，S 在无人机中继的辅助下将计算结果共享给D。令[n]表示第n时刻S发送出去的数据比特数，于是可以得到第n时刻S相应的信息传输能耗[16]为

通过分析易知，在第n时刻，S 只能发送或共享那些已被本地计算处理的数据，因此，有信息因果性约束为

2.2 任务卸载与结果共享

1) S 将计算任务卸载到无人机

2) 无人机辅助计算并将处理结果发送给D

接收到S 发来的任务数据，无人机首先对其进行计算处理，然后再将计算结果转发给D。假设无人机也采用动态电压和频率缩放技术以自适应地控制自身计算频率，且令fr[n]表示第n时刻的CPU频率。于是，第n时刻无人机计算的任务数据比特量和相应的能耗可分别表示为

其中，γr表示无人机依赖于芯片结构的有效电容系数。令表示第n时刻无人机转发到D 的数据比特量，则相应的传输能耗为

由分析可知，在每个时隙，无人机只能计算已接收到的来自S 的任务数据，且转发出去的数据量不得多于无人机经自身计算处理产生的数据量。因此，有信息因果性约束为

其中，式(16)右边的项为无人机在n− 2个时隙内计算出的数据结果比特量。显然，考虑到处理时延的存在，S 在最后2 个时隙不应该卸载任务给无人机，无人机在第一个和最后一个时隙不执行任务计算，且无人机在最开始的2 个时隙无计算结果转发到D。因此，有和。

类似地，基于以上分析，可将该方法下S 成功分享的数据比特量和相应的能量消耗分别表示为

此外，无人机的飞行能耗较大且会受其自身飞行轨迹的影响。为简便起见，可将无人机飞行能耗建模为关于飞行速度的二次函数，表示为

2.3 优化问题描述

考虑到源节点S 和无人机通常是功率受限的，如何提高它们的工作能效一直备受关注。因此，本文从整个系统的角度出发，通过对计算资源、通信资源和无人机轨迹进行联合优化，以实现系统能量效率最大化。本文的系统能效定义为总分享数据比特与系统总能耗的比值，即其中，式(22)表示在有限时长T内，S 分享的数据比特量不少于最低阈值Imin；式(23)～式(26)为2.1 节和2.2 节中给出的信息因果性约束；式(27)～式(32)保证了优化变量的非负性；式(33)～式(35)为无人机的移动性约束，包含无人机的初始和最终方位以及飞行速度，Vmax代表无人机的最大飞行速度。

问题P1 是一个复杂的非凸优化问题，现有的凸优化技术无法直接对其进行求解。基于此，本文首先考虑对问题P1 进行变换处理；然后，将其拆解为2 个子问题分别优化，即给定无人机轨迹下的计算资源和通信资源优化和给定计算资源和通信资源下的无人机轨迹优化；最后，基于各自获得的解，结合两阶段迭代算法对计算资源、通信资源和无人机轨迹进行交替优化。

3 能效最大化迭代算法

注意到优化问题P1 中的约束项关于各组优化变量是可分离的，并且数据比特量（包含、）与无人机轨迹这两组变量之间存在非线性耦合关系。因此，本文将优化变量分成两块，即(Ψ[n],Φ[n])和(u[n])，然后利用块坐标下降法来对两块变量分别进行优化。

在使用块坐标下降法之前，本文首先采用Dinkelbach[2]方法对式(21)中非凸的分式结构目标函数进行处理，以获得一种等价变换形式，使问题P1 更易于求解。具体如引理1 所示。

引理1根据Dinkelbach 方法，当且仅当式(36)成立时，可获得问题P1 的最优解。

其中，η*表示η的最大值。

证明证明过程请见文献[17]。

根据引理1，问题P1 可被等价转换为如式(37)所示的参数优化问题，表示为问题P2。

其中，η为一非负参数。为求解问题P2，首先需在给定η值的情况下求解问题P2，然后利用获得的ηCSE值对η进行更新，重复上述2 个步骤，直到式(36)满足等号条件。相应的算法细节将在3.2 节中提及。

3.1 通信与计算资源分配

将问题P1 改写成P2 之后，可采用块坐标下降法对其进行求解。基于变量分块优化的思想，可将问题P2 拆分成2 个独立的子问题。首先考虑第一个子问题：给定无人机轨迹下的计算与通信资源优化。该问题形式为

其中，f1(η)=I(1)+I(2)−η(E(1)+E(2))，源节点S的计算频率fs[n]和无人机中继的计算频率fr[n]为待优化的计算资源，源节点S 的卸载数据比特量和传输数据比特量以及无人机中继的转发数据比特量为待优化的通信资源。易知，问题P2.1 为标准的凸优化问题。然而，为洞悉最优解的数学结构，以给出更加直观的方案设计指导，本文考虑引入拉格朗日对偶法求解问题P2.1。令λ≥ 0表示与约束式(22)相应的对偶变量，问题P2.1 的部分拉格朗日表达式可写为

关于式(41)中的最优解，有如下结果。

定理1给定对偶变量取值的情况下，利用标准的拉格朗日方法和KKT（Karush-Kuhn-Tucker）条件，可获得式(41)中优化变量的最优闭式解析式为

3.2 无人机轨迹优化

已知通信与计算资源分配，无人机轨迹优化问题可表示为

最后，可将通信资源、计算资源和无人机轨迹联合优化的能效最大化两阶段交替优化方法归纳如下。1) 确定（给定）参数η的取值；2) 利用定理1 和定理2，计算给定无人机轨迹下的通信与计算资源分配；3) 基于问题P2.2 获得给定通信与计算资源分配下的无人机轨迹优化；4) 交替循环执行步骤 2)与步骤 3)直至迭代终止；5) 利用更新η的值，并返回步骤1)重新执行全部步骤，直至满足终止条件；6) 输出最优的优化变量值和相应的能量效率值ηCSE=η*。

4 仿真与分析

本节使用MATLAB 工具对所提算法进行仿真，并采用与现有方案对比的方式评价本文所提算法的性能。表1 给出了实验仿真中使用到的一些基本参数。

表1 实验仿真参数

图2 给出了不同分享数据比特阈值Imin下的无人机飞行轨迹，分别为Imin=0.5 ×104Mbit、Imin=1.0 ×104Mbit、Imin=1.5 ×104Mbit 和Imin=2.0×1 04Mbit这4 种不同的情况。由仿真结果可以发现，无人机倾向于靠近并在余下的时间里低速徘徊于源节点S和目的节点D 之间的中间点位置。这表明，无人机在源节点S和目的节点D的中间位置区间飞行可保证在完成协助计算和数据转发任务的同时尽可能地减少系统的总能耗，进而获得相对更高的能量效率。对比4 种不同情况的飞行轨迹可以进一步发现，随着所需分享数据比特数的增加，无人机越发倾向于徘徊在源节点S 和目的节点D 的中间更小位置区域，以尽可能地降低自身飞行能耗，将更多的能量用于辅助计算和数据转发。在相同基准信道功率增益β0的情况下，中间点位置可保证信道hsr[n]与信道hrd[n]之间的差异最小。无人机倾向于在源节点S 和目的节点D 的中间点位置徘徊，这一现象表明，两个信道之间的差异越小，越有利于数据的快速转发，待分享和处理的数据量越大，对二者信道之间的差异要求则越严格。

图2 不同分享数据比特阈值下的无人机飞行轨迹

图3 给出了3 种不同方案下系统能量效率随分享数据比特阈值变化的曲线。随着Imin的增加，系统能量效率呈递减趋势。由式(5)、式(7)和式(14)可知，数据的传输（转发）能耗与数据量呈指数关系，分享数据量的线性增长将导致传输（转发）能耗的指数级增长。因此能量效率随着Imin的增加而显著下降。在地面基站方案[8]中，本文将基站位置设定在（1 000,0,0）的方位。全卸载方案[11]指的是源节点S 对原始数据不做任何的计算处理，直接将数据全部卸载到无人机，无人机进行辅助计算并将结果转发给目的节点D。3 种方案对比显示，本文所提无人机辅助的部分卸载方案具有更好的能量效率性能，这凸显了无人机作为空中移动中继以及部分卸载方式的灵活性带来的好处。

图3 不同方案下系统能量效率随阈值 Imin的变化曲线

图4 给出了Imin=1.0 ×104Mbit 时本文所提算法的收敛情况。仿真图反映的是能量效率η的取值更新过程。任意选取3 种不同的初始化参数η0，本文所提算法均可在有限的迭代次数内实现快速收敛，具有较好的收敛性。

图4 本文所提算法收敛变化曲线

5 结束语

本文考虑了一种无人机辅助的边缘计算与结果共享系统，利用Dinkelbach 方法和两阶段交替优化，获得了系统能量效率最大化的最优无人机轨迹设计以及通信和计算资源分配。仿真结果显示了所提算法比现有方案具有更佳的能量效率性能和收敛性能。值得注意的是，本文所提优化框架和分析方法可适用于处理无线通信信号处理领域中出现的一类变量耦合分式规划相关问题。后续的研究中，可进一步考虑多个目的接收端的应用场景，同时引入非正交多址接入以提高资源利用效率，还可以考虑引入多个无人机进行辅助，以提供更高质量的通信与计算服务。此外，移动边缘计算场景下的任务数据卸载安全性也是非常值得关注的问题。