面向复杂任务的多无人机协同计算资源分配与优化

郭鸿志，王宇涛，王佳黛，刘家佳

(西北工业大学 网络空间安全学院，陕西 西安 710072)

0 引言

在无人机空中计算中，计算卸载与资源分配[1](Computation Offloading and Resource Allocation,CORA)问题的目标是无人机在其性能(尺寸、计算能力、电量等)允许的范围内，针对地面用户的任务计算需求，确定各个无人机的任务执行序列，以确保任务的低时延或无人机的低能耗要求。随着5G的发展和商用，时延敏感且计算密集型的复杂任务大量出现[2]。这些复杂任务包含多个存在数据依赖关系的子任务，需要遵从严格的子任务执行时序约束。例如，视频导航任务涉及图形、人脸检测、摄像机预览和视频处理，可以划分为14个依赖的任务[3]。面向原子任务(不可切分)的CORA，通常采用全卸载模式将整个任务卸载到一个无人机上[4-6]。而对于包含多个子任务的复杂任务的CORA，若采用全卸载模式将其全部卸载到一个无人机上计算将会存在两个问题：第一，一个无人机的性能难以同时满足所有子任务的计算资源需求，导致任务计算时延延长；第二，该无人机任务执行序列中后续任务的等待时延将被延长。因此，研究面向复杂任务的CORA方法来降低任务处理时延，保证用户服务质量，具有理论和实际意义。

与全卸载模式相比，将复杂任务划分为多个子任务，并采用部分卸载模式将子任务卸载到不同的无人机上计算，无人机将以较小的粒度灵活分配子任务需要的资源，从而进一步降低任务处理时延。同时考虑到子任务之间的数据依赖关系，部分卸载模式下需要无人机之间的高效协同。现有面向复杂任务的CORA研究工作存在一定局限性，其中，Ning等人[7]应用增强现实框架将复杂的应用模块简化为线性序列模块，并设计了一个迭代启发式边缘计算资源分配算法给出部分卸载策略。该工作只适用于线性模型，未考虑其他几种典型的任务关联模型。Zhu等人[8]考虑部分卸载任务的相互依赖性，采用马尔可夫决策过程求解得到卸载策略。该工作中，地面用户的所有任务只能通过一个固定的地面接入点上传到无人机，易产生堵塞，延长任务响应时间；无人机之间只能通过固定顺序通信，处理任务不灵活。

基于此，本文构建了面向复杂任务的多无人机空中协同计算模型。在该模型中，复杂任务被表示为3种典型的子任务流模型，并采用部分卸载模式计算。为了降低复杂任务的处理时延，本文针对多无人机协同部分计算策略优化问题采用一种双层博弈近似计算卸载算法求解。

1 系统模型

多无人机协同计算模型如图1所示，无人机被划分为管理无人机和计算无人机。其中，管理无人机负责收集计算无人机的可用资源和数据存储信息等；计算无人机处理地面用户的计算任务。在该模型中，任务采用部分卸载模式卸载到无人机计算，且每个计算无人机都维护一个任务执行队列。计算无人机的信息表示为U={V,F,P,L,N}，其中，V={1，2，…,|V|}代表计算无人机的集合，|V|代表计算无人机的数量，F={f1,f2,…,f|V|}代表无人机的计算能力，P={p1,p2,…,p|V|}代表无人机的发射功率，L={(x1,y1),(x2,y2),…,(x|V|,y|V|)}代表无人机的二维坐标，N={N1,N2,…,N|V|}代表在计算无人机v的覆盖范围内的用户集合。无人机悬停在高度为h的空中，Gk={pk,(xk,yk)}表示用户k的发射功率和水平坐标。

图1 系统模型Fig.1 System model

1.1 通信模型

1.1.1 空地通信

本文采用文献[9-10]中的概率路径损耗模型建模空地通信。该模型考虑了实际环境中不同发生概率的视距(Line-of-Sight,LoS)和非视距(Non-LoS,NLoS)通信，并定义用户k与无人机v之间LoS/NLoS通信的概率为：

(1)

(2)

(3)

(4)

因此，用户k与无人机v之间的空地通信速率可表示为：

(5)

式中，BG代表空地通信带宽，N0代表噪声功率，INk,v代表干扰功率信号。

1.1.2 空中通信

考虑到无人机悬停高度较高，空中通信主要由LoS链路主导，因此采用文献[11]中的自由空间路径损失模型，并将无人机v和v′之间的通信路径损耗表示为：

(6)

因此，无人机v和v′之间的数据速率表示为：

(7)

式中，BA代表空中通信带宽。

1.2 计算模型

(8)

2 任务处理过程

复杂任务的处理过程包括任务上传、任务划分及任务空中通信和计算、任务计算结果返回3个步骤。由于计算结果的数据量远小于输入数据，因此忽略结果返回的时间和能量成本[13]。

2.1 任务模型

如图2所示，典型的子任务流模型包括线性模型、树型模型和网状模型3种，每条有向边代表子任务之间的数据依赖关系。

(a) 树形模型

2.2 任务处理时延

用户i通过空地通信链路将任务上传到无人机v的传输时延表示为：

(9)

子任务si,j的所有前驱子任务执行完毕后，将前驱子任务的输出数据发送到计算si,j的无人机上，si,j才可以开始执行。由于子任务的中间输出数据量小，本文忽略发送输出数据的时间。

无人机v将子任务si,j传输到无人机v′的时延表示为：

(10)

计算子任务si,j的平均服务时延表示为：

(11)

考虑到子任务在无人机之间的传输与其前驱子任务的执行是同时执行的，定义子任务的空中通信和计算时延为：

t(si,j)=tcomp(si,j,v)+

(12)

在树型和网状模型中，一些子任务是并行执行的。因此，子任务流的处理时延取决于任务上传时延与该子任务流中最大的空中通信和计算时延之和，表示为：

T(Si)=tG2A(Si,i,v)+max{t(si,j)}。

(13)

2.3 无人机能耗

计算无人机在处理任务过程中的能耗包括悬停能耗、通信能耗和计算能耗[14]。

(14)

式中，ph为最小悬停功率，η为功率效率，ε为无人机的有效开关电容。管理无人机的能耗主要只悬停能耗[15]，可表示为：

(15)

3 多无人机协同部分计算卸载策略优化问题

(16)

约束C1和C2代表任务卸载约束，即每个子任务只能卸载到一个计算无人机上执行；约束C3和C4代表无人机能耗约束，即计算无人机和管理无人机的能耗都不能超过无人机的能量预算e0；约束C5代表任务执行时序约束，即具有数据依赖关系的子任务必须遵守执行顺序；约束C6代表任务响应时间约束，即任务需要在指定的最大时间限度Ti内完成。

4 双层博弈近似计算卸载策略设计

该问题是一个非凸的最小最大化问题，是NP难的[16]。枚举法可用于求解该问题，但是枚举法的计算复杂度为O((mn)|V|)，运行时间长，导致其在实际应用中受到限制。因此，本文提出一种双层博弈近似计算卸载算法。

博弈论被广泛应用于解决具有不同目标的多个博弈参与者之间的决策问题[17]。多无人机协同部分计算卸载优化问题存在双层博弈关系，因此本文提出了双层博弈近似计算卸载算法。在内层博弈中，子任务流中的所有子任务作为博弈参与者，经过有限次博弈找到该子任务流的近似最优计算卸载策略；在外层博弈中，所有子任务流作为博弈参与者，经过有限次博弈找到所有博弈者的近似最优计算卸载策略，最终得到最小的任务处理总时延。具体实现步骤如算法1所示。

算法1 双层博弈近似计算卸载算法输入:初始卸载策略X0;输出:近似最优的任务卸载策略X和最小任务处理总时延Tmin;初始化:需要更新策略的子任务集合Ui,j(t)和子任务流集合Ui(t);1: 从时刻t开始循环:2: 对于集合S中的每一个子任务流Si:3: 对于Si中的每一个子任务Si,j:4: 更改子任务的卸载策略,在满足任务响应时间和无人机能耗约束的前提下,计算使子任务在时刻t+1处理时延最小的最优卸载策略;5: 将子任务放入Ui,j(t)并存储其策略;6: ifUi,j(t)不为空then7: if子任务Si,j得到更新机会then8: 更新Si,j的策略以及X;9: endif10: endif11: 计算使子任务流在时刻t+1处理时延最小的最优卸载策略;12: 将子任务流放入Ui(t)并存储卸载策略;13: ifUi(t)不为空then14: if子任务流Si得到更新机会then15: 更新Si的策略以及X0;16: endif17: endif18:循环结束

该算法在内层博弈中遍历m个子任务，在外层博弈中遍历n个子任务流，经过C次迭代，达到纳什均衡状态，得到了一个近似最优的卸载策略及其最小的任务处理时延。因此，该算法的计算复杂度为O(C×m×n)。

5 仿真实验与结果分析

本节对本文提出的双层博弈近似卸载算法求解面向复杂任务的多无人机协同计算资源分配与优化问题，并进行了仿真。实验设计、实验结果及实验分析如下所示。

5.1 实验设计

考虑在多无人机空中计算场景中，地面用户随机分布在1 000×1 000的区域中，每个用户产生一个具有内在数据依赖的复杂任务。表1给出了仿真实验的场景设置和参数取值。

表1 场景参数取值Tab.1 Scene parameter values

基于表1设定的参数取值进行两组对比实验，一是对比验证双层博弈近似计算卸载算法的有效性和高效率；二是通过对比不同的方案得到的任务总处理时延以及单个任务的处理时延，验证双层博弈近似计算卸载算法在降低时延方面的性能。

5.2 实验结果及分析

为了评价双层博弈近似计算卸载算法的有效性和高效率，图3将该算法得到的任务处理总延迟和运行时间分别与穷举搜索法(得到最优解)进行比较。从图3(a)中可知，双层博弈近似计算卸载算法得到的任务处理时延略高于穷举法，说明双层博弈近似计算卸载算法可以找到问题的近似最优解，证明该算法是有效的。图3(b)的运行时间对比结果验证了双层博弈近似计算卸载算法的计算复杂度更低。因此，穷举搜索法虽然可以得到最优解，但是在处理较大规模的问题时运行时间过长。双层博弈近似计算卸载算法可以快速处理中等规模甚至大规模的实际问题。

(a) 任务处理时延对比

为了验证双层博弈近似计算卸载算法在降低任务处理延迟方面的性能，设计实验将其与两种已有方案进行对比。具体设计如表2中实验方案设计所示，方案一[18]未考虑多无人机协同和部分卸载模式，方案二[19]只考虑了多无人机协同，但未考虑部分卸载模式，而双层博弈近似计算卸载算法同时考虑了多无人机协同和部分卸载模式。

表2 实验方案设计Tab.2 Experiment scheme design

由图4可知，双层博弈近似计算卸载算法得到的线性模型、树型模型和网状模型任务的处理时延都低于其他两种方案。图5中双层博弈近似计算卸载算法得到的每个子任务流的时延相较于方案一更趋于稳定，相较于方案二时延更低。因此，双层博弈近似计算卸载算法在降低任务处理时延方面具有更好的性能，能够有效降低任务处理时延，合理利用无人机资源，实现无人机负载均衡。

(a) 线性模型

图5 双层博弈近似计算卸载算法与已有方案计算线性任务得到的每个子任务流时延对比Fig.5 Comparison of each subtask-flow’s processing delay with linear model between two-layer game-theoretic approximation computation offloading algorithm and existing schemes

6 结论

本文针对具有内在关联特性的复杂任务，研究了面向复杂任务的多无人机协同部分计算卸载策略优化问题。其中，无人机进行角色划分，通过各角色及角色之间的协同为地面用户提供计算服务。在任务执行时序、任务响应时间、任务卸载和无人机能耗约束下，通过优化子任务的部分卸载策略最小化任务处理时延。为求解该非凸优化问题，本文提出了一个双层博弈近似计算卸载算法求解得到任务的近似最优计算卸载策略。仿真结果验证了该算法的有效性和低计算复杂度，且相较于已有的解决方案，该算法在降低任务处理时延方面具有更好的性能。