一种基于任务碎片化重组的多无人机能耗公平性算法*

赵佳宜，赵文栋，刘存涛，刘泽原

（陆军工程大学，江苏 南京 210000）

0 引言

近年来，无人机因具有低成本、高机动、高隐身等一系列特点，在军事领域得到了广泛应用。在高危环境执行任务时，它能够体现出更大的优势[1]。与传统的数据传输不同，无人机可以从一个源节点装载数据，携数据在到达目的节点后将数据交付给目的节点[2]。由于有更好的信道条件且部署灵活，无人机在数据摆渡（Data Ferry）中取得了广泛应用。

如图1 所示，在数据摆渡中，无人机采用装载-携带-交付的模式[3]传送数据。无人机充当渡轮（Ferry）实现节点间的数据摆渡能确保数据的可靠交付，具有较好的应用前景。

图1 无人机数据摆渡的全过程

当前对于无人机辅助的数据传输进行了以下几个方面的研究。文献[4-7]研究了灾难情况下无人机辅助的数据调度。文献[4]用无人机组网解决灾害监测等应用中频谱稀缺的问题，改善了预先分配的频谱不足以维持高的数据传输速率这一现象。文献[5]研究了无人机为逃离受灾害事件影响地区的用户提供无线覆盖，最大限度地提高了受灾地区的总吞吐量。文献[6]研究并建立了无人机辅助灾害应急网络的统一框架，考虑地面基站全被摧毁时利用无人机作为空中基站与地面用户进行通信，研究了无人机基站的收发器设计和地面多跳设备到设备（Device-to-Device，D2D）通信的建立，以扩大无人机基站的覆盖范围。文献[7]设计了智能预测机制来预测应急区域设备的服务需求（即数据传输和电池充电情况），并据此建立了动态路径规划方案，以提高系统的能量效率。文献[8-11]采用无人机改善热点地区的通信状况。文献[8]研究了大量用户聚集在有限的区域引起地面基站难以响应多个用户需求的问题，通过建立空中基站来缓解地面基站的压力。文献[9]为了改善地面网络的过载特性，分析并比较了非正交多址（Non Othogonal Multiple Access，NOMA）方式和中继方式两种传输方案下的吞吐量。文献[10]提出了一种半分布系统，用于在紧急情况下自动部署无人机，以卸载热点区域变化的数据流量。文献[11]部署无人机作为空中基站构建机载网络，在临时事件发生时按需为地面用户提供服务，同时保持了无人机之间的连通性。此外，文献[12-14]研究了基站距离较远时，采用无人机充当移动中继提高通信质量的情况。文献[12]研究了静态基站（Base Station，BS）难以保证用户服务质量（Quality of Service，QoS）时无人机帮助BS 卸载用户数据流量，以改善边缘用户的信道条件。文献[13]研究的是当长期演进技术升级版（Long Term Evolution-Advanced，LTE-A）系统中源和目标用户设备之间的分离距离相对较长或链路质量较差时，选用中继辅助的方式改善设备到设备通信质量不佳的现象。文献[14]研究了空中部署多跳无人机网络，用于远程基站和物联网数据之间的传输，在不违反所有传感数据感测读数（Sensed Readings，SR）的时延约束条件下，减少多无人机的整体能耗。

无人机数据摆渡通信在源和目的地没有直接通信链路的情况下得到了广泛应用。但是，由于无人机自身能源有限，因此无人机辅助数据传输的能源消耗至关重要。无人机辅助数据传输网络的精确性能建模和优化需要精确的能耗模型、空中路径损失和信道衰落模型等。

本文研究了系统中的能耗公平性和轨迹优化的问题。如图2 所示，当多个无人机同时执行多个不同的数据摆渡任务时，受限于单无人机自身的任务执行能力，采用“一对一”的任务分配方式很可能导致部分任务无法得到有效完成，即无法在无人机自身能量范围内将源节点的数据传递至目的节点，从而直接影响任务的完成质量。此外，当单个任务中需要将多个源节点的数据转发至同一目的节点且源节点之间距离较远，或者多个任务之间存在重叠时，直接执行“一对一”的任务分配方式也会导致过高的无人机能耗，造成能耗效率低的问题。在这种情况下，基于任务碎片化重组的“多对多”协同任务分配方式通常具有更好的适用性，如图3 所示。

图2 “一对一”任务分配方式

图3 “多对多”任务分配方式

目前，已有许多文献围绕多无人机协同任务分配中的能耗问题展开了研究。文献[15-19]研究了无人机任务分配中的能耗最小化问题。文献[15]通过联合优化单无人机的轨迹、任务数据和功率分配，最小化所有用户设备的总能量消耗。文献[16]通过优化卸载策略、无人机悬停位置和计算速率，将系统中所有无人机和无人机的加权总能耗最小化。文献[17-19]研究的是无人机辅助移动边缘计算系统。文献[17]通过优化无人机的三维轨迹和地面基站之间的任务缓存策略，提出了一种块坐标下降算法，通过连续凸优化过程迭代求解，达到减少能耗的目的。文献[18]研究了无人机位置、时隙分配和计算任务分区的联合优化问题，确保在一个时间段内所有用户的任务计算成功的前提下系统能耗最小。文献[19]采用块坐标下降和逐次凸优化技术，对无人机轨迹、无人机与地面基站之间的关联关系以及发射功率进行了联合优化，降低了总能耗。但是，能耗最小并不能保证系统中的能耗公平性。如果无人机由于过度飞行而不能继续工作，它将严重影响性能，甚至导致多无人机系统故障。文献[20-21]研究了多无人机任务分配时的公平性问题。文献[20]通过最小化单架无人机的最大能耗来减小多架无人机之间的能耗差，达到确保无人机能耗公平的目的。文献[21]研究的是多无人机辅助边缘计算系统，通过使无人机中最大能耗的加权和最小化，实现了用户设备和无人机能源消耗的公平性。然而，上述研究很少从任务需求的角度考虑公平性，仅从能耗或系统收益的角度出发对任务进行分配，仍可能导致部分任务完成效果不佳。

本文考虑了基于多无人机摆渡的数据转发场景，研究了多无人机协同任务分配问题，采用任务拆分与重组的思想，提出了一种能耗公平的“多对多”协同任务分配方法，主要贡献如下。

（1）提出了一种基于任务碎片化重组的“多对多”任务分配方法，根据任务之间的距离对多个任务进行碎片化分解，而后计算每个碎片之间的距离，对不同的任务碎片进行重组，执行多无人机协同任务分配。

（2）将多无人机协同任务分配建模为最小最大路径覆盖问题，并以多无人机能耗公平性为目标对其进行优化。同时，提出了一种基于聚类的改进遗传算法对该优化问题进行求解，有效改善了无人机之间的能耗公平性。

（3）仿真结果表明，与“一对一”的任务分配算法相比，基于任务拆分与重组的“多对多”协同任务分配方法，将系统最大能耗降低32.0%～37.3%，且将标准差最多降低了90.2%。

本文的结构如下：第1 部分介绍了该场景下的系统模型；第2 部分介绍提出的FBTA 算法的详细过程；第3 部分是对所提算法的模拟和性能评估；最后，第4 部分介绍了结论和今后的工作。

1 系统模型

如图3 所示，本文考虑了一个基于多无人机的数据摆渡场景，包括一个信息中心、N个目标点和M架可用摆渡无人机。其中，目标点集合记为N={1,2,…,N}，无人机集合记为M={1,2,…,M}。信息中心接收到多个用户的数据获取需求后，为无人机分配数据摆渡任务；无人机根据分配到的数据摆渡任务，飞往任务目标点处，采用悬停的方式采集任务目标点的信息，而后将其携带回信息中心；信息中心接收到无人机获取的信息后，根据用户的需求向用户分发信息。此处，初始数据摆渡任务是根据用户的不同信息获取需求来区分的。记K={task1,task2,…,taskK,}表示K个任务的集合，其中taskk=表示第k个任务，poik是完成任务k需要访问的目标点集合。

如图2 所示，采用“一对一”的任务分配方式时，由于不同用户的信息获取需求不同，可能导致不同无人机访问目标点的数量存在较大差异（如UAV1和UAV3）。这一方面影响了无人机之间的能耗公平性，另一方面可能造成无人机资源的浪费。同时，由于单个无人机飞行能力有限，当其需要访问的目标点数量过多时，任务耗能通常会比较大，可能导致无法有效完成对应的数据摆渡任务。

1.1 能耗约束

在考虑能耗约束的情况下，无人机任务分配与路径规划之间具有高度耦合性，因为无人机的能耗很大程度上取决于其在任务执行过程中的飞行路径。为此，通常会同步考虑任务分配与路径规划。在确定任务分配策略后，无人机的飞行路径可以建模为完全无向图G(V,D)。其中：V为节点集合，表示无人机需要访问的所有目标点的集合；D为节点之间边的集合，当两个节点之间有边时，表示这两个节点由同一架无人机进行访问，即属于同一架无人机的任务目标点集合。此外，由于无人机在整个数据摆渡任务中的能耗主要包括采集目标点信息时的悬停能耗和飞行能耗两部分[22-23]，因此使用无人机的悬停能耗和飞行能耗分别作为节点和边的权重。对于节点vq∈V，点权重记为p(vq)；对于边m(vq,vq+1)∈D，边权重记为w(vq,vq+1)。下面对无人机的飞行能耗和悬停能耗进行详细描述。

1.1.1 飞行能耗

无人机i(i∈M)的飞行能耗Efi主要取决于i的飞行路径长度。记无人机i的飞行速度为γi，则Efi可以表述为：

式中：φ为单位距离的能量消耗率。

假设li为i的飞行路径，由其执行任务过程中所访问的目标点表示，记为。Si是路径li的长度，表示为：

1.1.2 悬停能耗

无人机i(i∈M)在目标点j(j∈N)的悬停能耗主要与其在目标点的悬停时间有关。假设每个目标点的数据量Dtj恒定，i收集数据时的信息传输速率为Bi，则i在j的悬停能耗可以表示为：

式中，β表示单位时间内的悬停能耗。

i的总能耗Eui可以表示为：

记i的最大可用能量为，则能耗约束可以表示为：

1.2 目标函数

为保证能耗的公平性，本模型的目标函数可以表述为最小最大路径覆盖问题，即耗能最大的无人机能耗最小。基于上述分析，本文优化问题的数学模型可以表示为：

2 算法描述

本文提出了一个启发式算法来解决以上问题，即基于公平性的任务分配算法（Fairly Based Task Allocation，FBTA）。该算法的主要思想如图4 所示，首先，将不同的任务拆解成多个任务碎片；其次，采用聚类算法将不同的碎片重组，形成新的分簇；再次，将这些新的分簇加上信息中心的位置，利用遗传算法计算得到每个分簇的最小总能耗minEui；最后，比较得出最大的minEui完成求解。

图4 FBTA 算法流程

2.1 聚类算法

聚类的目的是把目标点分类。本算法是根据距离来判断各个目标点之间的相似性，将相似的目标点归为一组形成新的分簇。聚类算法将任务碎片化重组算法的具体过程如下。

输入：无人机数目m，目标点坐标

输出：碎片化重组后的任务集合

1.随机选取m个初始质心；

2.分别计算所有目标点到这m个质心的距离；

3.如果目标点离质心si最近，那么这个目标点属于si点群；如果到多个质心的距离相等，则选择质心离原点最近的那个组；

4.按距离对所有目标点分完组后，计算每个组的均值作为新的质心；

5.重复步骤2、步骤3 和步骤4，直到新的质心和原质心相等，算法结束。

2.2 遗传算法

求解每个分簇的最小总能耗可以规约成传统的TSP 问题。该问题已被证明是NP-hard 问题[24]，通常可以通过数学规划算法、凸优化算法和启发式算法等进行求解。本文拟采用启发式算法求解。遗传算法是借鉴生物进化过程而提出的一种启发式搜索算法，通过选择、交叉和变异等操作产生下一代的解，并逐步淘汰适应度函数值低的解，增加适应度函数值高的解，从而通过进化演变逐步逼近问题的最优解。该算法具有简单通用、鲁棒性强以及适于并行处理等优势。遗传算法计算每个分簇的最小总能耗的算法过程具体如下。

输入：一个簇内的目标点坐标，起始点坐标

输出：每架无人机的最佳路径li，每架无人机的最小总能耗minEui；

1.初始化种群，种群规模popsize=80，迭代次数gen=5 000；

2.随机生成每代个体的路径基因型和中断点基因型，即产生路径点集合li；

3.计算w(vq,vq+1)、p(vq)和E矩阵；

4.根据上述的路径li和能耗矩阵E计算Eui；

5.如果Eui

6.将本次迭代的个体随机分成s组，从每一组中的最佳个体里修改路径基因型和中断点基因型；

7.子代再一次产生最小的能耗值Eui，若Eui小于历史最小minEui，则按照步骤5 替换最小能耗值minEui，并保存此时的路径作为子代，否则继续迭代下一个个体；

8.直到5 000 次迭代结束。

3 仿真分析

3.1 仿真参数设置

仿真过程中，目标点分布于大小为3 000 m×3 000 m的二维平面。图5 显示了目标点的分布情况和任务需求，目标点服从均匀分布。记信息中心的坐标为（0,0），可用无人机数量为4，目标点的默认数量为100，其他主要仿真参数如表1 所示。

图5 目标点分布及任务需求

表1 参数设置

3.2 仿真结果

3.2.1 任务碎片化重组结果分析

如图6 所示，任务在碎片化后被重新分为4 组。因为聚类算法对质心的初始位置选取比较敏感，因此本文选取了实验多次后的平均值。

图6 碎片化重组

3.2.2 算法能源效率分析

如图7 所示，采用“一对一”的任务分配方式时，由于任务1 和任务4 的信息需求量差异较大，导致无人机1 和无人机4 消耗的能量差异也较大。而经过“多对多”的任务碎片化重组后，无人机的能耗效率和公平性均得到明显改善。

图7 分能耗对比

3.3 算法适应性

3.3.1 目标区域大小对算法性能的影响

图8、图9 和图10 的仿真结果比较了目标区域大小对算法性能的影响。仿真中将侦察区域设置为正方形，图中的横坐标代表侦察区域的边长。随着侦察区域的增大，无人机的飞行距离变大，从而增加了无人机的飞行能耗。如图8 和图9 所示，与“一对一”的不协同任务分配方式相比，基于“多对多”的协同任务分配方式将系统最大能耗降低32.0%～37.3%，将系统的平均能耗降低了16.1%～24.3%。与“一对一”任务分配方式相比，“多对多”任务分配方式的标准差降低了82.5%～90.2%。与之相反，“一对一”任务分配方式的标准差很大，主要由于其在路径规划的过程中忽略了单架无人机的能耗。

图8 平均能耗对比

图9 最大能耗对比

图10 标准差对比

3.3.2 目标点数据量对算法性能的影响

图11、图12 和图13 的仿真结果比较了目标点数据量对算法性能的影响。图12 展示了最大能耗随侦察数据量变化的趋势，表明最大能耗随着数据量的增加而增加。与“一对一”的算法相比，FBTA 算法的平均能耗降低了18.9%～27.2%。随着侦察数据量的增加，悬停能耗在总能耗中的比例随之增加，因此本文提出的算法优势更加明显。图12 和图13 表明，算法FBTA 的最大能耗和标准差也取得了良好的效果，远小于不协同的最大能耗和标准差。

图11 平均能耗对比

图12 最大能耗对比

图13 标准差对比

4 结语

文章研究了多无人机执行数据摆渡任务时的多任务协同分配问题，提出了一种基于任务碎片化重组的“多对多”任务分配方法，将其建模为最小最大路径覆盖问题，通过聚类算法对任务进行预处理后用遗传算法对其进行求解。与传统的“一对一”任务分配方法相比，“多对多”的协同任务分配方法能够有效降低多无人机系统的最大能耗和标准差。在下一步研究中，拟考虑任务对时间紧迫性的要求，研究此时合理的碎片分解方式。同时，考虑完成任务所需的最小无人机数量，进一步提高任务完成质量。