移动边缘计算中的无人机群协同任务卸载策略研究

2022-07-02姚维，黄俊

重庆邮电大学学报(自然科学版) 2022年3期

姚维，黄俊

(重庆邮电大学计算机科学与技术学院，重庆 400065)

0 引言

随着移动终端设备的快速增长，智慧农业、自动驾驶、人脸识别、虚拟现实(virtual reality, VR)和增强现实(augmented reality, AR)[1]等新应用不断涌现。这些应用通常具有时延敏感、计算量大等特点。然而，设备的计算能力十分有限，在本地计算密集型任务会导致过大的延时和能耗[2]。作为5G中的关键技术之一，移动边缘计算(mobile edge computing, MEC)技术能够有效缓解资源有限的用户设备与计算密集型应用之间的矛盾。

移动边缘计算是指允许计算在网络边缘执行的技术，“边缘”指沿着数据源和云数据中心之间的路径上的任意计算和网络资源[3]。移动边缘计算可在靠近用户的网络边缘提供计算、存储、通信、无线感知等服务，并将部分任务从终端设备迁移到边缘云中以缩减应用程序的运行时间和终端设备的能耗。然而，移动边缘计算也面临诸多技术挑战。一方面，移动边缘计算技术容易受到传播延迟和路径损耗的影响；另一方面，当基础设施损毁时，特别是在应急场景下，移动边缘计算技术不能有效的发挥作用。

无人机协同下的移动边缘计算能较好地应对上述挑战，弥补其在应急场景中的不足。通过无人机协同，任务在更接近用户的位置完成，从而大大降低延时；同时，无人机具有的无线通信能力使得某些特殊情况如自然灾害场景也能保持正常通信。

近年来，利用无人机辅助进行任务卸载受到了广泛关注。文献[4]研究了多用户移动边缘计算系统中高能效资源分配方案。首先，建立从移动端到基站的计算卸载模型；其次，联合优化任务顺序、上传和下载持续时间，以及上传、下载、执行开始时间，最小化加权和总能耗；最后，将该优化问题转化为三阶段流水作业调度问题，利用Johnson算法和凸优化技术，提出了获得最优解的方法。但该模型仅考虑了移动终端-基站两层架构，并不适用于应急场景。在文献[5-7]中，作者利用单个无人机协助移动终端进行任务卸载。然而，在实际场景下，单无人机的计算能力有限，无法满足多用户密集型任务下的需求。作为单无人机的延伸，文献[8-9]设计了多无人机下自适应任务卸载方案，但未考虑无人机飞行过程中的耗能。在文献[10-11]中，作者分别利用贪婪算法和连续凸逼近算法(successive convex approximation, SCA)以减少无人机完成卸载任务所需的总时间。然而，这两种算法复杂度相对较高。

总结上述相关工作发现：①在应急场景下，通常采用多无人机或无人机群协同任务卸载；②应用多无人机协同任务卸载能满足多用户密集型任务的需求，从而有效降低延时；③现有无人机群任务卸载算法的复杂度较高，难以适应节点的快速变化。

为此，本文对移动边缘计算中无人机群协同任务卸载问题展开研究。利用联盟形成博弈理论进行建模。在对系统通信过程和计算过程的延时与能耗分析的基础上，设计联盟效用函数和回报函数，并基于享乐博弈模型提出联盟分割形成算法。理论分析证明，该算法最终收敛于某个稳定的联盟分割。仿真结果表明，相比其他典型策略，本文提出的策略具有更低延时和能耗。

1 系统模型

图1是无人机群协同任务卸载的系统模型示意图，由K部移动终端、J架无人机和1台基站组成。为了降低移动终端(mobile terminal，MT)的计算延时和能耗，任务可部分卸载到具有计算和通信能力的无人机群处理，或间接转发到远端基站上。假设移动终端在被测区域随机分布，无人机通过拍照或视频等方式监测任务、获取数据[12]，以满足实际应用场景。

图1 无人机群协同任务卸载的系统模型示意图Fig.1 System model of UAVs collaborative task offloading

本文的研究目标是实现整个系统延时和能耗加权最小。为了实现该目标，首先需要计算整个系统的延时和能耗。具体来说，整个过程包括任务卸载和计算结果的回传，如图1中箭头所示。其中，任务卸载包括链路的通信过程和计算过程。

1.1 通信过程建模

任务的执行过程包括任务的卸载和计算结果的回传。与文献[13-14]类似，本文不考虑回传过程所需的延迟和能耗开销，因为密集型计算任务产生的数据结果非常小，与输入数据量相比，回传所消耗的能量和延时可忽略不计。接下来将介绍通信过程的延时和能耗。

文献[15]提出MT与UAV间及UAV与AP间的通信方式均为视距通信(line of sight, LOS)。沿用该假设，无线网络中移动终端k与无人机j间，无人机j与基站间的信道增益可分别表示为

(1)

(2)

(1)—(2)式中：‖*‖为欧氏范数；dk和dAP分别表示移动终端k与无人机j间和无人机j与基站间的距离。移动终端k与无人机j间的传输速率可以表示为

(3)

(4)

(4)式中，Dk,j表示移动终端k卸载到无人机j的数据量。移动终端k到无人机j的任务卸载过程消耗的能量为

(5)

无人机j与AP之间链路延时和能耗的表述方式同上述无人机j与移动终端k相似。无人机j与地面基站间的传输速率可以表示为

(6)

(7)

(8)

1.2 计算过程建模

从系统角度出发，任务的计算过程主要发生在移动终端、无人机群和基站等设备上。本文未考虑在基站上计算任务时产生的延时与能耗，因为基站集成了高性能的处理服务器和充足的存储资源，所以对于整个系统来说，相比本地计算和无人机上计算，基站上计算任务产生的延时和能耗要小得多。具体的计算过程如下。

1)本地计算。顾名思义，本地计算表示任务在移动终端上处理。在本地计算过程中任务的延时表示为

(9)

(9)式中：Rk是移动终端k上任务的CPU周期；fk为节点k的CPU频率。移动终端通过动态电压频率调整技术(dynamic voltage and frequency scaling, DVFS)，以降低频率的方式控制能量的消耗[16]。因此，移动终端k的能耗为

(10)

(10)式中，Kk是移动终端k的有效电容系数。本地计算的数据量表示为

(11)

2)无人机上计算。假设无人机同样利用DVFS技术提升能量效率。则无人机j计算任务消耗的延时和能耗分别为

(12)

(13)

(12)—(13)式中：Rj表示无人机j上任务的CPU周期；fj是无人机j的CPU频率；Kj是无人机j的有效电容系数。在无人机j上完成的计算位数为

Lj=Tjfj/Ck

(14)

3)无人机飞行能耗模型。与文献[17]类似，无人机在飞行过程中的能耗为Efly，表示为

Efly=λ‖vu‖2

(15)

(15)式中：λ=0.5；vu表示无人机的飞行速度。基于上述模型和分析，可设计联盟分割形成算法以解决任务卸载问题。

2 基于博弈论的任务卸载策略

为了定义联盟S的总延时，我们做出了下面的假设：1)无人机必须等终端传输数据完成后才开始处理，以确保计算结果的可靠性；2)无人机任务的计算和卸载过程同步进行。那么，联盟S的总延时可表示为

(16)

联盟S的总耗能为

(17)

本文用联盟S总代价加权和的倒数作为效用函数。因此，对于任一联盟S⊂N，它的效用函数v(S)可表示为

v(S)=

(18)

需要指出的是，上式中，a和b分别表示延时和能耗的权重。当联盟S中仅包含移动终端或无人机时，规定联盟S的效用值为0。当联盟中只有移动终端时，无法与基站通信，导致效用为0；当联盟中只有无人机时，没有任务需要计算，所以效用也为0。

移动终端的任务能被任意划分，意味着联盟值也能在联盟成员中任意分配，这恰好满足可转移效用(transferable utility, TU)的定义。最终，给定一组参与者N和效用函数，将可转移效用的联盟博弈定义为(N,v)。为了得到每位参与者的回报，采用等分的分配规则，即

(19)

(19)式中，xi(S)表示参与者i从联盟S效用中获得的回报。

2.1 任务卸载博弈

本文利用联盟形成博弈中的享乐博弈[18-19]研究无人机群任务卸载问题。下面将引入参与者的偏好关系和偏好函数的定义：

定义1每个博弈参与者i能够对所有它可能属于的联盟集合{Sρ⊆N:i∈Sρ}建立完备的、自反的、可传递的偏好关系，用符号i表示。

对于参与者i∈N，给定两个联盟S1⊆N和S2⊆N，使得i∈S1和i∈S2，S1iS2表示和联盟S2相比，参与者i更偏好成为联盟S1的成员，或对联盟S1、S2具有相同的偏好。对任意参与者i，建立如下的偏好关系。

S1iS2⟺fi(S1)≥fi(S2)

(20)

(20)式中：S1、S2⊆N是任意2个包含参与者i的联盟，即i∈S1且i∈S2；fi是对任意用户i∈N所定义的偏好函数。偏好函数定义为

fi(S)=

(21)

(21)式中：xi(S)为联盟S中参与者i的收益；hi(S)表示参与者i访问联盟S的次数；qi表示i访问某个联盟S的最大次数；设置hi(S)的目的是避免参与者在联盟间频繁地换位，提高博弈的效率。xj(S)≥xj(S{i})表示联盟S中的任意成员j不会因i的加入而使自身回报减少。

2.2 基于博弈论的联盟分割形成算法设计

定义2换位准则给定一个对N的联盟分割H={S1,S2,…,Sr}，任何一个参与者i∈N当且仅当Sg∪{i}≻iSρ时，决定离开它当前所在联盟SH(i)=Sρ并加入另一个联盟Sg∈H∪{∅}，ρ∈{1,2,…,r}。于是，{Sρ,Sg}→ {Sρ{i},Sg∪{i}}，从而H→H′，其中H′表示每次独立的换位操作后产生的新联盟分割。

从换位准则可以看出，任一参与者i(移动终端或无人机)只要满足条件Sg∪{i}≻iSρ，就离开当前所在联盟，并加入新的联盟。根据(20)—(21)式，当参与者i加入新联盟时，它的回报会严格递增，且新联盟中其他成员的回报不会因为参与者i的加入而减少。此外，规定发生换位时hi(Sρ)的值增加1。

基于前面的联盟形成博弈的分析，本文提出了基于博弈论的联盟分割形成算法。算法的整个过程主要分为3个阶段：任务发现阶段，联盟形成阶段，任务处理阶段。整个算法的过程如下。

步骤2对每一个博弈参与者i∈N，给定当前的联盟分割Hcurrent；

步骤3参与者i∈N根据(21)所定义的偏好函数，调查可能的换位操作；

步骤4如果步骤3为真，参与者i∈N离开当前联盟Sρ，更新hi(Sρ)，并加入满足偏好的新联盟Sg；

步骤5重复上述步骤，直到收敛于一个稳定的联盟分割Hfinal；

步骤6∀UEi∈Sρ,Sρ∈Hfinal将部分任务卸载到同一联盟(Sρ)的无人机群上。一部分任务在无人机上计算，另一部分被转发到基站上处理。

联盟分割形成算法的收敛性证明如下。

联盟分割形成算法执行前，最初的联盟分割表示为Hinitial。经过联盟形成阶段后，最终收敛于某个联盟分割Hfinal。

首先，移动终端和无人机的数量一定，所以能形成的联盟分割数量也是有限的，经过不断换位，最终能收敛于某个稳定的联盟分割Hfinal，使得系统总效用最小。其次，参与者无法在联盟间频繁地换位。从(20)—(21)式可以看出，当参与者i换位时，离开联盟S的最大次数为qi。当参与者访问联盟S的次数超过qi时，fi(S)的值为负无穷，这意味着i一定会加入新的联盟。综上，经过联盟形成阶段后，移动终端和无人机形成的联盟最终将收敛于Hfinal。

3 仿真分析

为验证基于联盟分割形成算法下的协同卸载策略的优越性，将协同卸载策略和其他策略进行对比仿真。其他策略包括：①本地计算；②卸载到无人机；③卸载到基站。主要的仿真参数[20-22]在表1中给出。

表1 主要仿真参数Tab.1 Main parameters of simulation

图2描述了在6 km×6 km的被测区域内，6架UAV和20部MT组成的网络场景实例。其中，MT随机分布在被测区域，且其位置在一定时间内保持不变，UAV协同移动终端执行和转发任务，假设基站的坐标为(-3，-3)，在图中用绿色三角形表示。

图2 6架UAV和20台MT组成的网络场景实例Fig.2 Network scenario example composed of 6 UAVs and 20 MTs

图3给出了在20台移动终端下，随着无人机数量增加，提出的协同任务卸载策略和其他策略的总效用变化情况。从图3可知，4种不同模式下系统总效用按大小排序为：协同卸载策略>本地计算>在UAV计算>在基站上计算，且在本地计算策略下总效用保持不变。出现上述现象的原因是：本地计算策略下，系统的总效用值不受无人机数量的影响，总效用处于恒定的状态，约为0.952。卸载到无人机和基站上的效用值较小，其原因是将任务全部卸载会在通信链路上产生较大通信延时和能耗。协同卸载策略是4种任务处理方式中最优的一种，且当UAV=6时效用最高，约为1.78；当UAV数量小于6时，无人机负荷较大，大量任务会被转发到基站，导致效用较小；当UAV数量大于6时，无人机的飞行能耗占比较大，也导致效用较小。

图3 无人机数量对不同策略下总效用的影响Fig.3 Influence of UAV number on utility under different strategies

图4显示了在20台移动终端、6架无人机场景下，无人机的飞行高度h和总效用仿真结果。从图4可以看出，除本地计算外，其他策略的总效用随着无人机飞行高度增加都不断递减。与单无人机相比，多无人机协同卸载策略具有绝对的效用优势。出现上述现象的原因是：本地计算的效用不变，因为本地计算的过程未涉及无人机协同处理，与无人机的飞行高度无关。在其他策略下，随着无人机的飞行高度增加，传输速率Ck,j和Cj,AP都减少，使得卸载过程中的延时和能耗都增加，导致总效用降低。