加权能耗最小化的无人机辅助移动边缘计算策略研究

曾耀平，夏玉婷，江伟伟，刘月强

（西安邮电大学通信与信息工程学院，陕西 西安 710121）

0 引言

随着物联网的发展和计算密集型移动应用的普及，现有移动设备在处理应用或提供能源等方面已经无法满足用户需求。同时，移动视频等大数据流量也呈指数级增长［1］，这使得移动网络计算资源受限的问题日益突出。大多数移动设备计算能力和功耗有限，物联网设备很难在最后期限内完成计算任务，移动边缘计算（MEC）被认为是一种有效的解决方案，其可以增强计算服务以应对上述挑战［2］。

目前，大部分研究致力于静态MEC 服务器的部署，但是，为了实现更广泛的区域覆盖和更多的设备服务，需要部署更多的静态MEC，这将大幅提高部署成本。针对该问题，无人机（UAV）辅助的无线通信被视为一种高效的解决方案，其能够在缺乏传统基础设施或基础设施有限的农村或偏远地区实现全方位的通信覆盖［3］。无人机具备按需操作、灵活部署、可控移动性强、链路质量高等优点，得到了广泛研究和关注。

文献［4］在基于云的无人机系统中，研究由无人机安装的MEC 服务器的稳定性与大数据采集率之间的关系。文献［5］将网络布局与5G 技术相结合，综合考虑波束宽度对频率、覆盖范围等因素的影响，以最小化网络功耗。文献［6］介绍一种空-地集成的MEC 架构，该架构由地面和无人机安装的MEC 服务器组成。文献［7］考虑无人机安装的MEC 服务器集群，并研究其中的计算卸载问题，以延长无人机使用寿命并减少整体计算时间。文献［8］研究无人机辅助MEC 系统中针对多用户的资源优化问题，完成了计算卸载、无人机轨迹和用户调度任务，然而，文献［8］方法的计算复杂度较高。文献［9］应用博弈论，以实现执行时间和能量消耗之间的权衡，并探究无人机网络中的计算卸载问题。现有关于计算卸载的研究大多集中在移动设备向MEC 服务器的卸载过程，打破了移动设备在计算能力、电池资源和存储可用性方面的限制。

然而，尽管无人机辅助计算通信在优化任务执行性能方面表现出色，但是相较于大型远程云服务器，MEC 平台的计算资源依然具有有限性。当大量计算任务被卸载到MEC 上时，可能会引发资源竞争现象。此外，移动边缘网络的流量分布具有异构性和动态性，单个MEC 难以持续地提供令人满意的计算服务。针对这些问题，本文研究D2D（Device-to-Device）通信，通过在MEC 之间实现任务卸载以提高MEC 性能。通过将重负载的MEC 上的任务卸载到轻负载的MEC 上，可实现异构网络中非均匀分布的流量的平衡。文献［10］基于当前蜂窝网络中的真实数据，建立一种描述多基站时间流量变化的正弦叠加模型。文献［11］研究具有有限回程能力的联合负载平衡和干扰管理策略。文献［12］提出一种睡眠控制服务器计算任务卸载在线优化策略，采用睡眠控制方案来降低MEC 网络的长期能耗。文献［13］设计一种新的在线小基站（SBS）对等卸载框架，以优化SBS 长期能源预算下的系统延迟。此外，非正交频分多址（NOMA）也能够通过功率分配和串行干扰消除（SIC）技术使SBS 共享同一资源（如频率等），从而大幅提升整个系统的吞吐量及能源效率［14］。因此，将D2D 与NOMA 技术相结合可以更好地部署未来系统，提高用户服务质量。文献［15］首次提出基于NOMA 的D2D 通信系统，使得单个D2D 发送端和几个接收端在同一频谱资源下实现通信。文献［16］提出当NOMA 传输同信道干扰时向MEC 服务器卸载更多信息的最优策略。文献［17］提出基于NOMA的无人机支持MEC 框架，该框架可以降低卸载能耗，克服设备的计算能量限制。

上述计算卸载方案通常忽略了MEC 间的协同作用，本文研究双层MEC 间的协同作用，其中，上层为多无人机辅助计算卸载，下层为SBS 间的协同作用，并设计MEC 间的卸载策略和资源分配方案，以优化全网络的系统能耗。随着基站的密集化和边缘计算平台的增加，对能源效率的需求进一步提升。本文考虑在系统每个区域内都设置无人机辅助SBS计算，利用李雅普诺夫（Lyapunov）优化框架将目标问题进行分解，提出一种在线资源分配调度优化算法。针对流量分布不均匀且会出现大部分流量突发的情况，本文在多服务器多SBS 的场景下，充分考虑随机的应用请求、不可预测的SBS 状态、计算资源分配以及共信道干扰约束等因素，以系统平均能耗为优化目标，基于排队论构建联合优化资源分配与飞行轨迹的自定义应用卸载模型。首先，构建本文模型时融合本地设备的M/M/1 计算模型和无人机的M/M/m 排队模型；其次，通过Lyapunov 随机优化理论，构建漂移惩罚函数，将随机优化问题转变为4 个独立的子问题；然后，设计一种启发式的用户匹配算法，获取用户最佳匹配方案；接着，提出改进的自适应下降交替方向乘子法（AD-ADMM），获取最优卸载决策；最后，利用块坐标下降法和连续凸逼近（SCA）算法，联合优化资源分配、卸载决策以及飞行轨迹调度问题。

1 系统模型

如图1 所示，本文考虑一种基于NOMA-D2D 的多无人机辅助边缘计算系统模型，该系统由K架搭载MEC 服务器的无人机和M个低功率SBS 构成。当网络流量分布不均时，重负载的SBS 可以选择将计算任务卸载到低负载的SBS 上进行处理。在附近无SBS 可供辅助卸载时，为确保整个系统的稳定性，请求SBS 选择将卸载的计算任务分配至UAV 上。为了便于表达，定义SBS、UAV 的集合分别为∀m∈M{1，2，…，M}、∀k∈K{1，2，…，K}。在该系 统中，每个SBS 和无人机均可以维护到达的任务队列，将到达的任务存储在任务缓冲区中，按照先进先出的顺序进行处理。

图1 系统模型Fig.1 System model

此外，无人机依靠有限的机载能量飞行，并在持续时间T内为SBS 提供边缘计算服务，将T均匀离散成N个时隙，各时隙间隔τ=T/N足够小，以确保各时隙内无人机和SBS 的位置基本恒定，记时隙集合为∀t∈N{1，2，…，N}。不失一般性，考虑一个三维笛卡尔坐标系，规定SBS 均位于水平地面上，无人机均以固定高度H飞行，SBSm在t时隙的水平位置为pm=(xm，ym)，无人机的位置为pk(t)=(xk(t)，yk(t))。假设无人机k在飞行周期结束后返回初始位置，鉴于实际工程应用中存在的局限性，无人机k在每个时隙内的飞行距离与飞行速度有关，且无人机之间需要维持最小安全飞行距离，以避免碰撞。因此，无人机应满足如下的移动性约束：

其 中：pk，I和pk，F分别表 示UAV 的初始 位置和 终止位置；Vmax表示无人机的最大飞行速度；Dmin表示防碰撞的最小安全距离。系统中使用的主要参数及含义如表1 所示。

表1 系统参数说明 Table 1 System parameters description

1.1 通信模型

考虑到在无人机飞行过程中视距链路（LoS）受环境中其他障碍物的影响，参考文献［18］，假设t时隙SBSm将计算任务卸载至UAVk上，则两者之间的仰角和LoS 概率分别为：

其中：a和b分别为取决于载波频率和环境类型的参数。因此，SBSm向UAVk传输的上行信道功率增益表示为：

其中：h0为参考距离d0=1 m 处的信道功率增益；P(LoS，ϑm，k(t))=P(LoS，ϑm，k(t))+μ(1-P(LoS，ϑm，k(t))) 表示考虑了使用μ＜1 的非视距信道的衰减效应的正则化LoS 概率［19］；ϑm，k(t)是t时刻SBSm和无人机k之间的角度。

根据NOMA 的原理，针对无人机之间的干扰问题，本文将整个频谱划分为K个带宽为B的正交无线子信道。假设不同的UAV 通过频分多址占用不同的子信道，将每个时隙共享同一子信道的SBSs 称为一个NOMA 组。将各NOMA 组中的SBSs 按其信道增益大小进行升序排列，无人机k将进行SIC 解调来自多个SBSs 的信号，而SIC 的排序方式则遵循信道增益的降序排列。根据NOMA 组中SBSs 的排序方法，上行SBS 可能会受到其他信道增益较低的SBSs 的干扰，从而导致组内干扰存在［20］。由香农公式可知，在t时刻，SBSm卸载的计算任务量应满足：

其 中：B=1 MHz 为信道带宽；为SBSm向UAV卸载的最大传输功率；N0=10-12W 为信道噪声功率；为同一NOMA 组内的用户间干扰。

在本文模型中，SBS 之间通过局域网进行数据传输，但局域网带宽有限，规定SBSm仅可向一个适宜的接收SBS 请求进行D2D 辅助卸载。然而，一个接收SBS 可以为多个请求SBS 提供协同传输。不失一般性，定义lmm'(t)∈{0，1}为D2D 卸载选择指示器，其中，m'∈M-m表示除SBSm外的属于SBS 集合M的其他SBS，lmm'(t)=1 时表示请求SBSm选择接收SBSm'辅助卸载，否则，lmm'(t)=0。因此，约束条件如下：

同时，定义αm，k(t)∈{0，1}为无人机卸载指示器，其中，αm，k(t)=1 表示SBSm卸载计算任务至UAVk上，否则，αm，k(t)=0。假设在任意时隙t，SBSm最多选择一个UAV 进行任务卸载，因此，约束条件应满足：

1.2 应用程序分区和协同传输调度模型

根据描述多基站时间流量变化的正弦叠加模型，在t时隙SBSm的计算任务用二元组Ω=＜Am(t)，ρ＞表示，其中，Am(t)表示SBSm到达的任务量，ρ为计算每比特任务所需的CPU 周期数［21］。定义fl，m(t)为SBSm的计算频率，fk，m(t)为UAVk分配给SBSm的计算资源，则本地执行和无人机执行的任务量分别表示为：

定义Qm(t)表示SBSm在时隙t的任务队列积压，和分别表示从Qm(t)传输给本地计算队列Lm(t)和卸载的任务量，则任务队列的更新过程满足：

由于应用状态的不可预测性，SBS 可能在不同时隙处于不同的运行状态（请求、接收和中立状态）。为了确保卸载任务不会发生卸载循环现象，从其他请求SBS 卸载的数据必须在接收SBS 的本地执行，可以得到本地计算队列Lm(t)的动力学公式为：

为了保证队列的稳定性，队列积压在时间平均意义上需满足：

1.3 能耗模型

系统中的总能耗［22］主要包括计算能耗、通信能耗和无人机的飞行能耗。

1.3.1 计算能耗

根据电路理论，执行任务的大部分能量消耗来自CPU，且CPU 周期频率与CPU 电压近似呈线性关系。任务执行的CPU 周期频率和CPU 能耗可以通过CPU 电压的变化来调整。因此，t时隙SBSm本地计算和UAVk处理来自SBSm计算任务的能耗分别为：

其中：κ是由硬件架构决定的CPU 有效切换电容［23］；fl，m(t)和fk，m(t)分别表示SBSm的计算频率以及UAVk分配给SBSm的计算频率。

1.3.2 通信能耗

根据文献［23］，从MEC 服务器到SBS 返回计算结果的过程中能耗足够小，其值在能量消耗模型中可以忽略不计。同时，值得注意的是，SBS 之间的数据传输主要依赖于光纤、同轴电缆等高效的局域网连接，其能耗在能量消耗模型中也可忽略［24］。因此，t时隙SBSm卸载任务至无人机k的能量消耗为：

1.3.3 无人机的机动性和飞行能耗模型

无人机k在第t时隙与第t-1 时隙之间的速度为：

其中：P0和PH分别代表悬停状态下的叶片轮廓功率和诱导功率；Utip为转子叶片的尖端速度；v0表示无人机悬停时转子的平均转子感应速度的一个常数；d0、ρ、s和A表示无人机空气动力学的相关参数。无人机k的飞行总能耗表示为：

因此，整个系统的总能耗可以通过时隙t的计算能耗、通信能耗和飞行能耗的总和来计算，如下：

其中：ωm∈{0，1}和ωc∈{0，1}分别为SBS 和UAV 的权重因子，满足ωm+ωc=1，这2 个值可根据实际系统进行调整，以满足优先能源需求，或实现SBS 和无人机之间的能耗平衡；η是飞行能量消耗的一个惩罚系数，旨在缓解幅度差异。式（27）假设所有的通信链路都是可靠的，不考虑计算任务重传的问题。

1.4 问题定式化

本文旨在解决一个基于NOMA-D2D 的多UAV辅助通信问题，在同时满足计算资源、缓存资源和任务缓冲区的限制条件下，通过联合优化卸载策略、发射功率、计算资源分配和轨迹调度，以最小化全网络的平均能耗。上述目标表述为如下的随机优化问题：

2 问题转换与算法

Lyapunov 优化是解决确定性时隙问题并求解低时间复杂度下平均最优解的有效算法，不需要使用先验数据的统计信息来预先指定控制参数，可以根据实时输入的数据在线计算出控制参数，从而实现对系统的在线控制和调整。本文采用Lyapunov 对任务到达队列进行分析和卸载，将式（28）转化为4 个易于优化的子问题，从而迭代地解决系统的资源分配和无人机轨迹优化问题。

2.1 队列分析与问题转换

假 设θ(t)=(Qm(t)，Lm(t)，Jm(t))|m∈M表示系 统中所有的任务队列积压，定义一个二次Lyapunov 函数为：

定义单槽Lyapunov 漂移为：

根据Lyapunov 优化理论，定义漂移加惩罚函数为：

其中：V≥0 是控制系统效用和队列稳定性之间权衡关系的系数；Es(t)是系统加权能耗。通过最小化D(θ(t))的上界来最小化漂移加惩罚函数：

通过优化式（32）右侧的上界，可以最小化漂移加惩罚函数，即将目标问题转化为：

从式（34）可以看出，解决优化问题需要考虑能量消耗和任务执行状态2 个方面，基于此，每个SBS可根据其状态（包括服务需求和数据队列积压等）采取独立的卸载方案。

2.2 在线资源协调分配分案

由于指示器的选择只和周围SBS 的位置信息以及空闲状态有关，因此lmm'(t)和其他优化变量无关。为了求解上述优化问题，针对不同的优化变量将问题分解为4 个最优子问题进行交替迭代求解。

2.2.1 SBS 卸载决策

本节提出一种最佳SBS 卸载决策方案，避免传统的遍历匹配等方法中计算复杂度呈几何倍数递增的问题。该方案采用一种基于匹配博弈的启发式算法，以降低计算复杂度，提高计算效率，并获得近似匹配结果。

本文将匹配的请求SBSm和接收SBSm'称为D2D匹配，这些SBSs 通过一个共同的控制渠道广播它们的需求和本地资源。对于需要卸载计算任务的请求SBS，首先根据收集到的信息检查是否存在潜在的接收SBS 可以提供帮助，若不存在潜在的接收SBS，则根据与UAV 之间的距离进行优先排序和选择，以获取最终的卸载决策。否则，针对所有潜在的接收SBS，根据卸载所需能耗生成偏好列表，以便在卸载决策时做出适宜的选择。因此，请求SBSm和接收SBSm'在D2D 匹配中的偏好可以分别表示为：

2.2.2 计算任务分配

在给定UAV 飞行轨迹的情况下，任务分配q=与UAV 的飞行轨迹pk(t)被解耦，此时任务分配问题可以表示为：

显然，式（37）是一个多变量耦合的线性约束凸优化问题，将原问题转化成增广拉格朗日形式，如下：

其中：β∈R+是用于调整AD-ADMM 收敛速度的惩罚参数。因此，AD-ADMM 会执行如下迭代直到收敛：

为了加 快收敛速度，定 义PΛ=max{λ，0}，v=执行以下迭代：

其中：γk是自适应步长的延长因子，一般γk∈(1，2)时收敛速度较快。是最优步长，表达式为：

此外，式（37）是具有强对偶性的凸优化问题，即其拉格朗日量具有鞍点，更新的变量随着迭代次数的增加都将收敛。定义算法收敛准则为：

其中：ε是一个值较小的正常数。

2.2.3 计算资源优化

固定无人机的飞行轨迹，对无人机上的计算资源进行分配，为MEC 服务器分配更大的计算能力来执行卸载任务，表述为：

对于式（45），元素之间没有耦合，因此，无人机的最佳处理频率由每个SBSm推导出，通过内点法求得的鞍点除此之外，MEC 服务器的最佳处理频率也可以由边界得到。综上，MEC 服务器的最优计算资源分配为：

2.2.4 无人机轨迹调度优化

预先确定无人机的频率分配和卸载决策，旋翼无人机的轨迹优化问题表示为：

为了处理目标函数中的非凸项Pk(||vk(t)||)，采用SCA 的方法，引入辅助变量vk，t≥||vk，t(t)||，将无人机的推进功率重写为：

由于式（50）的右侧第二项仍然非凸，因此进一步引入辅助变量：

由于式（52）是关于vk，t和yk，t的联合凸函数，记其右侧为，第j次迭代时的展开点为对 其进行一阶泰勒展开可得下界为：

由此，式（50）的右侧第二项转变为凸函数。接下来对非凸约束式（3）的左侧进行一阶泰勒展开，得其凸约束为：

因此，原始优化问题式（49）可以转化为：

此时，目标函数及约束条件均为凸函数，即式（58）为凸问题，可以很容易地通过CVX 等凸优化求解器进行求解。结合以上分析，求解各子问题的交替迭代优化算法描述如算法1 所示。

3 仿真结果分析

本节将通过一系列的仿真实验来分析所提算法的性能。在仿真实验中，在100 m×100 m 区域内随机分布50 个SBS，无人机为3 架。无人机从固定的初始位置出发，飞行一段时间后回到初始位置。无人机任务完成总时间T=2 s，平均包括N=50 个时隙。系统相关参数设置如表2 所示［26］。

表2 仿真参数设置 Table 2 Simulation parameter settings

为了体现本文所提算法的优越性，实验首先分析算法的参数对最终结果的影响，其次分析计算任务量对系统能耗的影响，将本文所提算法与以下算法进行比较：

1）本地计算算法（简称为Local 算法）：所有的SBS 均在本地执行计算任务。

2）随机算法（简称为Random 算法）：用户在无人机覆盖范围内时，随机地选择任务在本地计算还是卸载到无人机上处理。

3）ADMM 算法：未改进的计算任务分配算法，其他条件与本文所提算法相同。

图2 和图3 所示为不同权重因子下卸载能耗性能和Lyapunov 控制参数之间的关系。从中可以看出，系统平均能耗随着控制参数的增加而逐渐降低并趋于稳定，且任务队列随之增大。这是因为通过调节控制参数来实现系统效用和队列稳定性之间的权衡，从而表明本文所提算法在保证系统长期稳定的约束前提下，能够实现能耗最优的效果。同时图2和图3 也反映了权重因子对能耗和队列积压的影响，权重因子越大，无人机的能耗占比越大，系统向无人机卸载的任务量越小，导致任务缓冲区剩余的任务量越多。

图2 V 和ωc 权重因子对能耗的影响Fig.2 The effect of V and ωc on energy consumption

图3 V 和ωc 对任务队列积压的影响Fig.3 The effect of V and ωc on task queue backlogs

图4 和图5 分别描述了最大任务到达量以及无人机计算能力下系统总能耗的变化情况。图4 中能耗随着任务量的增加而显著增加并最终趋于稳定状态，这是因为在系统中通信资源和计算资源均有限，当系统中任务量达到饱和状态时，网络中就会出现任务拥塞现象。图5 反映了SBS 计算能力对系统总能耗的影响，从中可以看到，随着移动设备本地计算能力的提高，全部在本地计算的系统总成本降低得最快，这是因为当设备本身计算能力提高时，计算任务的效率也会提高，队列中任务等待的时间变短，因此，其总成本降低得较快。而其他算法随着用户计算能力的提高，系统总成本逐渐降低，但是降低幅度不大，因为当设备本身计算能力提高时，其他卸载算法卸载到无人机上执行的任务量可能会减少，降低了任务的传输成本，因此，他们的系统总成本会逐渐降低。综上，本文所提算法的系统总成本最低，体现了该算法的优越性。

图4 任务到达量对能耗的影响Fig.4 The effect of task arrivals on energy consumption

图5 用户计算能力对能耗的影响Fig.5 The effect of user computing power on energy consumption

图6 表示系统包含50 个SBS 时3 架UAV 的飞行轨迹，无人机从不同的初始位置开始并最终返回初始位置。从图6 可以观察到，优化轨迹后的无人机飞行靠近相应的用户集群，更倾向于为更接近它们的用户服务，这表明通过轨迹优化，UAV 能更好地为SBS 提供计算服务。然而，由于计算任务在队列中积压，优化后的轨迹不太平滑，包含较多的弯曲。在某些时刻，当大量计算任务被卸载到UAV 上时，导致无人机的位置发生跳跃。此外，可以观察到3 架无人机的轨迹倾向于尽量远离彼此，这是因为算法考虑了无人机的防碰撞约束。由于SBS 在不同时刻会产生随机计算任务，因此UAV1 和UAV2 的轨迹图像在某些时刻可能会重叠。最后，由于总的任务完成时间有限，因此无人机在飞行一段时间后会以高速和直线轨迹返回到最初位置。

图6 无人机的飞行轨迹Fig.6 Fly trajectory of unmanned aerial vehicles

4 结束语

本文通过联合优化资源分配、卸载决策以及轨迹调度，在保持队列稳定性的基础上，研究基于D2D的无人机辅助MEC 系统能耗最小化问题。该问题为非凸问题，为此，提出一种基于Lyapunov 的在线资源协调分配方案，将非凸问题分解为4 个易于管理的子问题。在每次迭代中，将卸载决策建模为给定无人机轨迹下的结构型凸优化问题，提出AD-ADMM算法进行求解。在给定资源分配的条件下，利用SCA 技术将旋翼无人机的轨迹优化问题转化为标准的凸优化问题进行求解。仿真结果表明，与基准测试方案相比，该算法在能耗方面具有一定的优越性。下一步将研究无人机的飞行高度协同通信功率、卸载决策以及轨迹规划问题，同时也将继续探讨其他类型无人机的轨迹优化技术。