飞行自组网拓扑控制研究综述

刘亚群，谢钧，邢长友，倪保安

（1.陆军工程大学指挥控制工程学院，江苏 南京 210007；2.中国人民解放军92771 部队，山东 青岛 250100）

0 引言

无人机（UAV,unmanned aerial vehicle）具有快速部署、低成本、易控制、视距通信等特性，已经被广泛应用于多个领域[1-2]。例如，UAV 可以用于情报侦察、目标打击、信息分发、电子干扰等[3]，也可以用于实时监控[4]、交通管理[5]、空中基站[6]、网络中继[7]、数据采集[8]、货物运输[9]、灾后救援[10]等。

若干年来，单一的大型无人机一直被用于执行任务[11-13]。为了维持与地面基站或空中卫星之间的通信，该无人机需要配备昂贵且复杂的硬件[14]。此外，单无人机携带的资源有限，可能无法满足实际需求。随着无人机制造技术的发展以及制造成本的降低，规模化地生产低成本、高性能的小型或微型无人机已经成为可能。由于单一无人机能力有限，由若干小型或微型无人机组成的无人机集群开始被用于执行任务[15-17]。实践表明，相比于单无人机系统，多无人机系统具有若干优势[18-20]。例如，在容错性方面，当单无人机系统出现故障时，任务将无法继续执行，而在多无人机系统中，当个别无人机出现故障后，任务仍可由其他无人机继续执行。在任务性能方面，与单无人机系统相比，多无人机系统的覆盖面积更大，任务执行速度更快。

在多无人机系统中，无人机之间以及无人机与地面基站之间的通信架构可以分为2 种[14,21-22]：基于基础设施的多无人机系统和飞行自组网（FANET,flying ad-hoc network），如图1 所示。在基于基础设施的多无人机系统中，所有无人机都与地面基站等基础设施直接建立连接，无人机之间的通信均需要通过基础设施来实现。为了维持无人机与基础设施之间的连接，每个无人机都需要配备复杂的硬件并且维持较高的发送功率，无人机的移动范围受限。此外，由于无人机之间的通信都需要通过基础设施来实现，无人机之间的通信具有较高时延。在FANET 中，只有少量无人机与基础设施直接建立连接，无人机之间以及无人机与地面基站之间的通信可通过若干无人机中继实现，有效解决了基于基础设施的多无人机系统存在的问题。因此，FANET已成为多无人机系统的主要通信架构。

图1 多无人机系统通信架构

不同于其他自组网，FANET 具有节点密度低、移动性高、链路易中断等特点，这对维持FANET的连通性提出了挑战[18,22]。此外，FANET 还需要满足不同应用场景下的性能需求。例如，在执行灾后救援任务时，无人机需要将灾情信息实时传输给地面基础设施，因此FANET 需要具有较低的通信时延[23]；在执行数据收集任务时，为加快数据收集速度，FANET 需要具有较高的吞吐量[24]。

根据FANET 的特点及需求，FANET 拓扑控制通过构建和调整FANET 拓扑结构，维持FANET的连通性，并提高FANET 的性能[25]。具体地，FANET 拓扑控制算法通过调整无人机的组网方式、位置、功率等参数来生成并动态维护满足特定约束且具有较优性能的FANET 拓扑。FANET 拓扑控制算法具有以下特点：1) 在优化变量方面，FANET 拓扑控制优化的变量主要集中在无人机本身，例如，无人机之间的组网方式、无人机的位置和无人机的发送功率等；2) 在优化目标方面，FANET 需要优化的性能与其应用场景有关。由于FANET 的应用场景非常广泛，通信性能（如吞吐量、时延、干扰等）、任务性能（如覆盖率等）、能量消耗等均可能成为FANET 拓扑控制的优化目标；3) 在执行频率方面，FANET 中无人机具有高度的移动特性，FANET 拓扑控制需要高频率动态执行。

目前，研究人员已经开发出多种FANET 拓扑控制算法。然而，目前的FANET 综述还没有对FANET 拓扑控制算法进行全面且详细的分析。因此，本文对FANET 拓扑控制算法进行了全面的综述，梳理FANET 拓扑控制算法的研究思路，为FANET 拓扑控制算法的使用与开发提供依据。本文的主要贡献总结如下。

1) 介绍了FANET 的网络架构，给出了FANET拓扑控制的研究框架和需求。

2) 基于FANET 拓扑控制算法适用的网络架构，提出了一种FANET 拓扑控制算法的分类方法。根据每类FANET 拓扑控制算法的特有属性，对每类FANET拓扑控制算法进行了全面且详细的分析，并通过对比总结了不同算法的特点和优缺点，便于研究人员根据需求选择合适的FANET 拓扑控制算法以及开发新的FANET 拓扑控制算法。

3) 讨论了FANET 拓扑控制算法仍面临的挑战以及未来的研究方向。

1 相关工作

本节梳理了与FANET 和拓扑控制两大主题有关的综述，并讨论了本文与这些相关工作的不同之处，以凸显本文的创新性。

一些文献已经从多个角度对FANET 的相关研究进行了总结。文献[18]是第一篇有关FANET 的综述，它从应用场景、设计特点、通信协议、测试方法等角度对FANET 进行了综述。文献[26]总结了FANET 中的路由协议。文献[27]专门总结了FANET 中基于集群的路由协议。文献[19]总结了FANET 的特征，并围绕路由、服务切换、能量等关键问题对FANET 进行了综述。文献[21-22,28-30]主要从FANET 特征、应用场景、通信架构、路由协议、移动性模型和安全性等角度对FANET 进行了全面的综述。虽然这些文献已经对FANET 的相关研究进行了全面的综述，但是它们并没有关注FANET 中的拓扑控制问题。本文主要对FANET 拓扑控制的相关研究进行综述。

此外，一些文献对无线传感网（WSN,wireless sensor network）中的拓扑控制算法进行了综述。在WSN 中，拓扑控制主要通过调整节点的功率、状态等来维持网络连通性、增大网络覆盖范围、延长网络寿命等。文献[31]主要从功率调整、功率模式、聚类和混合4 个方面讨论了WSN 中以节能为目标的拓扑控制算法。文献[32]则通过覆盖性和连通性2 个性能指标对WSN 中的拓扑控制方法进行综述。文献[33]介绍了水下WSN 拓扑控制的特性、潜力以及挑战，并从功率控制、无线接口模式管理和移动辅助3 个角度对其拓扑控制算法进行综述。然而，FANET 与WSN 之间存在诸多不同，WSN 中的拓扑控制算法无法有效应用于FANET。例如，切换节点状态是WSN 中常用的拓扑控制技术，而无人机停留在空中需要持续消耗能量，因此状态切换技术不适用于FANET。

目前，有关FANET 拓扑控制的综述还相对较少。文献[34]主要总结了3 种基于虚拟力的FANET拓扑控制算法，但对目前已经出现的大量其他种类的FANET 拓扑控制算法没有系统分析。文献[25]基于FANET 拓扑控制算法的执行方式和数学模型对FANET 拓扑控制算法进行了分类，并对FANET拓扑控制算法进行了详细的分析。然而，在文献[25]提出的分类方法中，不同种类的算法之间区分不明显，每种算法的特有属性无法体现。此外，文献[25]仅分析了部分具有代表性的FANET拓扑控制算法，对现有FANET 拓扑控制算法的综述不够全面。本文提出了一种全新的FANET 拓扑控制算法的分类方法，并根据每一类算法的特有属性，对现有FANET 拓扑控制算法进行了全面的综述。

2 飞行自组网拓扑控制概述

2.1 飞行自组网架构

本文将FANET 的架构分为3 种：展平式FANET、基于连通支配集（CDS,connected dominating set）的FANET 和基于集群的FANET[35]，如图2 所示。其中，基于CDS 的FANET 和基于集群的FANET 都属于分层式FANET。

图2 FANET 分类

在展平式FANET 中，所有无人机都具有相同的角色，各无人机在通信过程中地位平等。在分层式FANET 中，各无人机具有不同的角色。具体地，无人机可以分为领导者和跟随者。其中，领导者充当跟随者的汇聚节点，负责将跟随者发送的数据包转发至目的地。相较于展平式FANET，分层式FANET 将大多数转发操作集中到少量的领导者，在路由设计、可扩展性、能量效率、时延等方面更具优势，因此被广泛应用于大规模无人机网络。在基于CDS 的FANET 中，领导者是构成CDS 的无人机节点，也被称为支配节点，跟随者是其余的无人机节点，也被称为被支配节点。被支配节点发送数据包时，会首先将数据包发送至其支配节点，然后由支配节点转发至目的地。支配节点之间形成一个虚拟主干网络，承载FANET 的主要流量。在基于集群的FANET 中，所有无人机被划分为若干集群，每个集群由一个集群首领和若干集群成员组成。集群首领作为领导者，负责管理其集群内部的通信。集群成员作为跟随者，在与其他集群内的无人机通信时会首先将数据包发送至其集群首领，然后由集群首领转发至目的地。集群首领之间形成一个虚拟主干网络，承载FANET 的主要流量。基于CDS 的FANET 和基于集群的FANET 的目的都是将大量的转发操作集中于少量的领导者。然而，这两者之间也存在若干不同：1) 在领导者选择方面，基于CDS的FANET 的领导者是组成CDS 的支配节点，而基于集群的FANET的领导者是每个集群的集群首领；2) 在跟随者管理方面，基于CDS 的FANET 中的支配节点负责管理其邻居节点中的被支配节点，而基于集群的FANET 中的集群首领负责管理其所在集群内的所有集群成员；3) 在领导者通信方面，基于CDS 的FANET 中的支配节点在给定无人机通信距离的情况下是连通的，而基于集群的FANET 一般不考虑集群首领的通信距离，默认集群首领之间可以互相通信。

2.2 飞行自组网拓扑控制的研究框架和需求

2.2.1研究框架

本文将FANET 拓扑控制研究框架分为三步：模型构建、算法设计及效果评估，如图3 所示。在模型构建阶段，需要根据FANET 的应用场景，确定FANET 的架构，设计拓扑控制算法需要满足的约束、优化的目标以及可调整的参数。在算法设计阶段，需要根据拓扑控制的实施阶段、约束、目标以及可调整的参数，选择合适的数学工具来设计相应的拓扑控制算法。根据拓扑控制算法的实施阶段，FANET 拓扑控制算法可分为拓扑构建算法和拓扑维护算法。其中，拓扑构建算法用于在没有无人机初始位置、发送功率和连接关系的情况下，从零开始构建FANET 拓扑；拓扑维护则用于在现有FANET 拓扑的基础上，通过调整相关变量，进一步优化FANET 拓扑。最后，在效果评估阶段，需要评估FANET 拓扑控制算法的性能，并进一步优化FANET 拓扑控制算法。

图3 FANET 拓扑控制研究框架

2.2.2需求

本文将FANET 拓扑控制的需求总结如下。

1) 连通性

在FANET 中，连通性指任意一对无人机之间以及任意一个无人机与基础设施之间至少存在一条通信路径。FANET 是一种为实现无人机之间以及无人机与基础设施之间通信而设计的网络架构，因此连通性是FANET 拓扑控制最基本的要求。

2) 网络性能

FANET 的网络性能是指无人机之间以及无人机与地面基站等基础设施之间通信的性能。FANET需要优化的网络性能与其应用的场景有关，因此，FANET 拓扑控制需要根据FANET 的应用场景设计合适的FANET 拓扑，以满足特定场景对FANET 的网络性能要求。通常，FANET 拓扑控制优化的网络性能有链路时延、链路吞吐量、无人机之间的干扰、负载均衡等。

3) 任务性能

FANET 的任务性能是指各无人机执行任务的性能。FANET 需要优化的任务性能同样与其应用的场景有关，以FANET 辅助地面用户通信为例，FANET 拓扑控制优化的任务性能有地面用户覆盖率、总吞吐量、最小吞吐量等。

4) 容错性

FANET 在任务执行期间可能会遇到无人机故障、障碍物、恶劣天气等不确定性情况。因此，FANET 拓扑控制需要设计具有容错性的FANET。一方面，在FANET 发生故障前，FANET 拓扑控制可以设计具有容错性的FANET 拓扑，使FANET 在个别无人机发生故障后仍能正常运行。例如，FANET 拓扑控制可以构建具有k（k≥ 2）连通性质的FANET 拓扑。另一方面，当FANET 发生故障后，FANET 拓扑控制添加无人机以及调整无人机的位置恢复FANET 的正常运行[36-37]。

5) 执行频率

FANET 中的无人机具有高移动性的特点，无人机之间的相对位置频繁变化。因此，FANET 拓扑控制需要高频率动态更新FANET 拓扑，以维持FANET的性能。为了满足FANET 拓扑控制动态执行的需求，FANET 拓扑控制需要在较短时间内完成。

6) 执行方式

FANET 拓扑控制算法的执行方式分为集中式执行和分布式执行2 种。其中，集中式执行的FANET拓扑控制算法需要由中央控制单元集中执行。相比之下，分布式执行的拓扑控制算法可以由各无人机自主执行，具有更小的通信开销，算法收敛速度更快，更适合于具有高移动性特点的FANET。

7) 能量消耗

无人机的能量消耗由通信能量消耗和飞行能量消耗两部分组成，其中飞行能量消耗远大于通信能量消耗，因此FANET 拓扑控制主要考虑无人机的飞行能量消耗。根据文献[38]，假设无人机的飞行速度恒定为V，飞行时间为T，固定翼无人机的飞行能量消耗可以表示为

其中，a1和a2是与无人机的重量、机翼面积和空气密度等因素有关的常量。旋翼无人机的飞行能量消耗可以表示为

其中，c1和c2是与无人机的重量、旋翼速度、旋翼盘面积、叶片角速度和空气密度等因素有关的常数，q是旋翼叶尖速度，do是机身阻力比，vo是平均旋翼速度，ρ是空气密度，s是旋翼密度，A是旋翼盘面积。由式(1)和式(2)可以看出，在无人机飞行速度恒定的情况下，无人机的飞行能量消耗主要与无人机的飞行时间有关，因此FANET 拓扑控制可以通过减少无人机的飞行距离来减少飞行时间，从而减少飞行能量消耗。

2.3 飞行自组网拓扑控制算法的分类

根据2.1 节可知，不同种类的FANET 架构具有不同的特点，其拓扑控制算法所解决的问题也有所不同。在展平式FANET 中，拓扑控制算法主要解决无人机数量、位置和发送功率的优化问题。在基于CDS 的FANET 中，拓扑控制算法主要在无人机位置确定的情况下解决CDS 的选择和维护问题。在基于集群的FANET 中，拓扑控制算法则主要解决集群划分与维护以及集群首领的选择与维护问题。由于不同架构FANET 中的拓扑控制算法解决的问题不同，其数学模型、原理和计算方法等也有所不同。因此，本文将FANET 拓扑控制算法分为3 类：展平式拓扑控制算法、基于CDS的拓扑控制算法和基于集群的拓扑控制算法，分别应用于展平式FANET、基于CDS 的FANET 和基于集群的FANET。此外，本文单独设置了一类基于虚拟力的拓扑控制算法。该算法假设每个无人机节点都会受到来自其邻居节点、障碍物、任务目标等的虚拟力，每个无人机仅需要根据其受到的虚拟力的合力自主调整位置，既可用于展平式FANET，又可用于基于集群的FANET；既可用于FANET 的初始拓扑构建，又可用于FANET 的动态拓扑维护。因此，基于虚拟力的拓扑控制算法实际上可以归入展平式拓扑控制算法和基于集群的拓扑控制算法。然而，基于虚拟力的拓扑控制算法使用了与其他算法完全不同的拓扑控制方法，其分布式的执行特点非常适合用于控制自组织、高动态的FANET。此外，基于虚拟力的拓扑控制算法的设计思路简单，其吸引力可以确保FANET 的连通性，排斥力可以确保FANET 的覆盖性，非常适合于在确保动态FANET 连通的前提下覆盖地面用户。近年来，大量文献使用基于虚拟力的拓扑控制算法来满足FANET 的连通和覆盖需求。基于以上特点，本文将基于虚拟力的拓扑控制算法设置为单独的类别，以便对此类算法感兴趣的读者对其有更清晰的认识。由此，FANET拓扑控制算法可以分为4 类，如表1 所示。后续章节将根据每一类拓扑控制算法所面临的特定挑战以及所使用的特定技术，对每一类拓扑控制算法进行更细粒度的分析。

表1 FANET 拓扑控制算法分类及对比

3 飞行自组网拓扑控制算法分析

3.1 展平式拓扑控制算法

展平式拓扑控制算法的常见应用场景有3 种，如图4 所示。在场景1 中，任务无人机的位置由其执行的任务确定，并且任务无人机需要与地面基站或其他任务无人机通信。拓扑构建算法通过求解中继无人机的部署位置，在每个任务无人机与地面基站之间以及任务无人机之间建立多跳路径，使每个任务无人机能够与地面基站或其他任务无人机通信。在场景2 中，所有无人机均可以执行侦察、通信覆盖等任务或充当其他无人机之间、无人机与地面基站之间通信的中继。在这一场景中，拓扑控制算法主要求解各无人机的部署位置。一方面，拓扑控制算法需要优化各无人机执行任务的性能；另一方面，拓扑控制算法需要在各无人机之间、无人机与地面基站之间构建多跳通信路径，优化FANET 的网络性能。在场景3 中，所有无人机的位置已知，此时拓扑控制算法主要通过求解无人机的发送功率来构建和维护FANET 拓扑。

图4 展平式拓扑控制算法应用场景

根据算法的执行阶段，展平式拓扑控制算法可以进一步分为2 类：展平式拓扑构建算法和展平式拓扑维护算法。

3.1.1展平式拓扑构建算法

展平式拓扑构建算法用于在没有无人机初始位置、发送功率和连接关系等信息的情况下，从零开始构建展平式FANET 拓扑。

为了减少场景1 中部署的中继无人机的数量，文献[39]介绍了3 种能够求解中继无人机位置的拓扑构建算法：多专用连接（MDC,multiple dedicated connection）算法、贪心算法和分布式自组织无人机（DSOD,distributed self-organized drone）算法。MDC算法在每个任务无人机与地面基站之间等距离地部署若干中继无人机，使每个任务无人机通过专门的中继无人机与地面基站通信。这一算法求得的中继无人机数量较多且需要集中式执行。贪心算法每次选择距离已有通信路径最近的未连通的任务无人机，并沿最短路径部署若干中继无人机，使该未连通的任务无人机能够与地面基站通信。这一算法求得的无人机数量较少，但是仍需要集中式执行。在DSOD 算法中，每个无人机自主决定是否需要额外的中继无人机，并且中继无人机根据其单跳邻居信息自主调整位置以保持连接。此外，中继无人机不断与附近无人机进行信息交换，以检测是否存在冗余的中继无人机。虽然DSOD 算法求得的无人机数量略高于贪心算法，但是DSOD 算法可以分布式执行。为了最小化场景1 中继无人机的数量，文献[40]利用求和形式的失真函数来表示连通性约束，并用一个概率成本函数来表示容量约束，最终用确定性退火算法来以集中式的方式求解该问题。实验结果表明，该算法求得的中继无人机数量接近最优。

此外，在场景1 中，一些文献还考虑最大化FANET 的网络性能。文献[41-42]在使用罚函数法将约束优化问题转换成无约束优化问题的基础上，提出了一种基于粒子群优化（PSO,particle swarm optimization）算法的集中式拓扑构建算法。实验结果表明，与随机方案相比，该算法能够显著提高FANET的网络性能。在场景1 的基础上，文献[43-44]均采用了软件定义网络（SDN,software defined network）架构，并且都提出了基于PSO 算法的集中式拓扑构建算法。在考虑通信距离和安全距离等指标的基础上，文献[43]考虑了任务无人机之间的路由数量、路由跳数、路由距离等指标，文献[44]考虑了连通节点对数量、可替换路由、故障点、桥接链路等指标，进一步优化了FANET 的通信性能。

在场景2 中，很多文献考虑在保证FAENET 连通性的情况下，最大化FANET 的任务性能。在FANET 为地面用户提供通信服务的场景中，为了最大化地面用户的总吞吐量，文献[45]将这一问题建模为连接最大吞吐量问题，并提出了一种具有性能保证的近似算法来求解地面用户的接入选择和各无人机的部署位置。文献[46]则将这一问题建模为混合合作竞争博弈模型，并提出了一种多智能体深度强化学习（MADRL,multi-agent deep reinforcement learning）算法来求解地面用户的接入策略和各无人机的轨迹。文献[47]研究了如何在地面用户概率密度已知的情况下最小化无人机与地面用户之间的平均距离，首先提出了一种用于视距通信场景的分布式部署算法来控制无人机移动，随后讨论了如何在非视距通信场景中使用该算法。文献[48]首先设计了一种改进的遗传算法以使用最少数量的无人机为地面用户提供覆盖，随后提出了一种无人机重新部署算法以最大程度增加覆盖用户的数量。文献[49]提出了一种MADRL 算法来控制无人机移动，从而同时最大化平均覆盖率，最大化覆盖公平性，最小化无人机能耗，并保持多无人机网络的连通性。

在场景3 中，文献[50]提出了一种基于关节点的离散PSO 算法（AP-DPSO,discrete PSO with articulation point），以构建鲁棒性高、干扰低以及无人机之间链路短的FANET 拓扑。为了减少通信开销并实现分布式控制，该算法首先通过寻找网络中的割点将网络划分为多个子网络。随后，子网络的局部拓扑控制问题被表述为受度数约束的最小生成树问题，对于该问题，每个无人机收集本地拓扑信息并使用离散PSO 算法求解自身发送功率。

展平式拓扑构建算法仅用于构建初始的FANET 拓扑，因此，此类算法的主要目标是构建可行有效的FANET 拓扑，而不需要过分关注算法的执行时间和执行方式。由于无人机的初始位置、发送功率和连接关系等信息未知，展平式拓扑构建问题通常被构建为非凸优化问题。因此，大多数展平式拓扑构建算法基于启发式算法、智能优化算法等设计。表2 展示了展平式拓扑控制算法的比较结果。

表2 展平式拓扑控制算法的比较结果

展平式拓扑构建算法大多在中央控制器中执行。在中央控制器中，展平式拓扑构建算法可以根据全局信息来计算展平式FANET 的拓扑，并且各无人机只需要根据中央控制器的计算结果来完成FANET 构建。因此，展平式拓扑构建算法设计相对简单，容易执行。综上所述，展平式拓扑构建算法主要适用于系统中存在中央控制器的情况下构建展平式FANET。当各无人机分配的资源固定时（如无人机的发送功率无法改变），可以设计展平式拓扑构建算法来求解各无人机的部署位置，进而构建初始的展平式FANET。当各无人机的位置固定时（如无人机的位置完全由其执行的任务决定），可以设计展平式拓扑构建算法来求解各无人机的发送功率，从而实现展平式FANET 的构建。

在优化目标方面，现有的文献大多单方面优化无人机的数量、FANET 的任务性能或FANET 的网络性能等。在实际的FANET 应用场景中，FANET 的若干性能需要同时优化。然而，不同的优化目标之间存在一定矛盾。例如，优化FANET 的任务性能会降低其网络性能，而优化FANET 的网络性能则会降低其任务性能[34,51]。如何均衡优化FANET 的各项性能有待进一步研究。一种简单的解决思路是根据实际需求给各优化目标设置不同的权值，并将各优化目标的加权和作为设计展平式拓扑构建算法的总目标。

此外，在优化变量方面，无人机的位置、功率和分配带宽等均可影响FANET 的性能。由于各优化变量之间相互耦合，一个变量的变化可能会影响另一个变量的优化，因此同时优化多个变量具有较高的复杂度。为此，可以采用交替优化的方法来交替优化各个变量，并在多次迭代之后求得最终结果。

3.1.2展平式拓扑维护算法

FANET 在执行任务的过程中，其无人机的位置会根据需要动态变化。为了维持FANET 的性能，FANET 的拓扑结构也需做出相应调整。展平式拓扑维护算法主要用于在现有FANET 拓扑的基础上，通过调整相关变量，更新FANET 拓扑，从而优化FANET 的性能。

一部分展平式拓扑维护算法通过调整无人机的位置来更新FANET 拓扑，如图5(a)所示。当任务无人机的位置发生变化时，文献[42]算法3、文献[51]算法2 和文献[43]算法2 根据每个中继无人机的单跳邻居信息，使用梯度法来分布式地调整每个中继无人机的位置，从而维持任务无人机与地面基站之间的通信性能。为了在任务无人机的位置发生变化时保证任务无人机之间的k连通性并且最小化中继无人机的移动距离，文献[52]首先使用steinerization 方法求出中继无人机的候选部署位置，随后使用完全二部图来表示中继无人机与中继无人机候选部署位置之间的关系，并根据中继无人机的当前位置与中继无人机的候选部署位置设置边的权重，最后使用Kuhn-Munkres 算法确定该加权二部图上的最大加权匹配，求得每个中继无人机的部署位置。该算法需要所有无人机的位置信息，因此需要集中式执行。为了增大FANET 的吞吐量，文献[24]算法3 在利用罚函数法将网络连通性、无人机安全距离、无人机单位时间内移动的最大距离等约束转化为优化目标的基础上，基于PSO 算法来集中式地求解无人机在下一时刻的位置。

图5 展平式拓扑维护算法

此外，基于功率的拓扑维护算法通过调整无人机的发送功率来改变无人机的通信范围，从而更新FANET 拓扑，如图5(b)所示。在不具有2-连通性质的初始FANET 拓扑上，局部拓扑功率控制（LTPC,localized topology power control）算法[53]将初始拓扑转化成块割树，并不断添加长度最短的边，最终生成具有2-连通性质的FANET 拓扑。在假设初始FANET 拓扑具有k（k≥ 3）连通性质，并且所有无人机发送功率相同的基础上，文献[24]算法1 采用了一种循环剪枝机制，不断删除当前拓扑中长度最长的边，直到生成的拓扑具有2-连通性质，从而求得能够使FANET 拓扑具有2-连通性质的无人机最小发送功率。考虑到FANET 的拓扑连通性、平均传输时延与链路损耗，文献[17]提出了一种基于联盟图博弈的自适应拓扑控制算法，通过轮转互操作在不具有2-连通性质的初始FANET 拓扑上添加边，最终实现拓扑连通性、平均传输时延与链路损耗3 种性能之间的权衡优化。

展平式拓扑维护算法主要用于当无人机位置发生变化时，通过在现有FANET 的基础上调整无人机的位置或发送功率，动态更新FANET 拓扑，从而优化FANET 的性能。具体地，基于位置的拓扑维护算法在保持无人机发送功率不变的情况下调整无人机的位置，基于功率的拓扑维护算法则在保持无人机位置不变的情况下调整无人机的发送功率。由于展平式拓扑维护算法需要高频率动态运行，算法的收敛速度、执行方式等都是影响展平式拓扑维护算法性能的重要因素。在算法收敛速度方面，启发式算法和以梯度法为代表的凸优化算法具有较快的算法收敛速度，可以满足展平式拓扑维护算法的需求。与之相比，博弈论算法以及智能优化算法等需要通过多次迭代才能求得最终解，具有较慢的算法收敛速度。在执行方式方面，集中式的展平式拓扑维护算法需要周期性执行，从而周期性地优化FANET 的性能。与之相比，分布式的展平式拓扑维护算法根据外部环境的变化实时调整无人机的位置、发送功率等，从而实时维护FANET 的性能。

展平式拓扑维护算法主要适用于在保证当前展平式FAENT 服务尽可能不中断的情况下，调整现有的展平式FANET 并提高其性能。当系统中存在中央控制器时（如FANET 采用SDN 架构），可以设计集中式的展平式拓扑维护算法或重新执行展平式拓扑构建算法，并根据全局信息调整展平式FANET 拓扑，获得更优的性能。当系统中不存在中央控制器时，需要设计分布式的展平式拓扑维护算法，使各无人机仅根据其局部信息来调整展平式FANET 拓扑。此外，当各无人机分配的资源固定时（如无人机的发送功率无法改变），可以设计展平式拓扑维护算法来调整各无人机的部署位置，进而维护展平式FANET。当各无人机的位置由其执行的任务等因素决定时，则可以设计展平式拓扑维护算法来调整各无人机的发送功率，从而维护展平式FANET。

现有的文献大多以集中式的方式实现展平式FANET 的拓扑维护，无法实时维护FANET 的性能。因此，如何以分布式的方式优化FANET 的性能有待进一步研究。为此，可以考虑各无人机在维持已有通信链路的基础上，分布式调整其位置或发送功率，从而优化展平式FANET 的性能。

此外，现有文献大多在外界环境变化之后进行展平式FANET 的拓扑维护，具有一定的滞后性。为解决这一问题，可以考虑预测外界环境的变化（例如，在FANET 为地面用户提供通信服务的场景中预测地面用户的位置变化情况），并根据预测的外界环境的变化情况来维护展平式FANET 拓扑[54]。

3.2 基于CDS 的拓扑控制算法

基于CDS 的拓扑控制算法主要在无人机位置已知的情况下构建和维护CDS 来实现对FANET 的拓扑控制，其应用场景如图6 所示。例如，当多无人机在执行野火监控、信息采集、野外救援等任务时，各无人机的位置由其执行的任务而决定。此时，基于CDS 的拓扑控制算法通过构建和维护CDS，将绝大多数转发操作集中于少量的支配节点，从而完成FANET 拓扑控制。

图6 基于CDS 的拓扑控制算法的应用场景

根据算法的执行阶段，基于CDS 的拓扑控制算法可以分为2 类：CDS 构建算法和CDS 维护算法。

3.2.1CDS 构建算法

CDS 构建算法主要用于在FANET 中构建初始的CDS。由于CDS 的构建问题是一个NP 完全问题，现有CDS 构建算法大多采用启发式或近似的方法来构建基于CDS 的FANET。

在启发式算法方面，文献[24]算法2 首先基于最小生成树算法生成CDS 候选集，然后基于页面排名算法来构建最小CDS。文献[55]算法1 基于最小生成树算法生成CDS 候选集，并将具有最大能量的CDS 作为初始的CDS。

在近似算法方面，文献[56]提出了3 种具有多项式时间复杂度的近似CDS 构建算法，其中，前2 种算法用于一般图，后一种算法用于有界度图。考虑到FANET 的拓扑变换频繁，文献[57]认为FANET中CDS 形成的虚拟主干网络需要具备一定的容错能力。为此，文献[57]提出了一种分布式k连通支配集（DKCDS,distributedkCDS）算法，该算法首先构建CDS，随后根据最大独立集理论构建k连通支配集。

实际上，由于CDS 构建算法难以优化FANET的任务性能和网络性能，CDS 构建算法在FANET的应用相对较少，而在WSN[58-59]、移动自组网（MANET,mobile ad-hoc network）[60]、车辆自组网（VANET,vehicle ad-hoc network）[61-62]等无线网络中已经得到了广泛的应用。这些算法可以较容易地移植到FANET 当中，感兴趣的读者可以查阅相关文献，以便更好地理解CDS 构建算法。

在FANET 中构建CDS 的主要目的是将大多数转发操作集中到少量支配节点，从而简化FANET的路由问题。支配节点的数量越少，转发操作越集中，FANET 的路由越简单。考虑到FANET 的不确定性，构建具有容错性的CDS 能够确保FANET 在其中个别无人机节点发生故障后仍能正常运行。此外，考虑到支配无人机节点承载的转发任务更多，其能量消耗更快。因此，使用能量最大的CDS 作为初始CDS 可以延长FANET 的生存时间。从算法设计、通信复杂度和时间复杂度等角度来看，启发式CDS 构建算法的设计相对容易，但其无法提供算法通信和时间复杂度的理论保证。与启发式算法相比，近似算法可以提供算法通信和时间复杂度的理论保证，但其设计难度较高。表3 展示了基于CDS的拓扑控制算法的比较结果。

表3 基于CDS 的拓扑控制算法的比较结果

根据CDS 构建算法的特点，CDS 构建算法主要适用于在执行大规模数据传输任务的FANET（如利用FANET 从地面物联网设备收集数据）中构建CDS，从而提高FANET 的传输效率。目前的CDS构建算法大多采用了集中式的构建方法，其中，启发式的CDS 构建算法设计简单，易于理解，因此适合对相关数学理论研究不太深入的初级研究者设计。近似CDS 构建算法设计复杂，但能提供性能的理论保证，适合对相关数学理论研究较为深入的高级研究者设计。

CDS 构建算法构建的CDS 将大多数转发操作集中到少量的支配节点，支配节点的能量消耗明显高于被支配节点。为此，在设计CDS 构建算法时需要考虑无人机的能量消耗问题，从而延长FANET的生存时间。一种可能的解决思路是将无人机的剩余能量作为评价无人机重要性的指标之一，并设计算法使重要性高的无人机成为支配节点的可能性更高。此外，现有的CDS 构建算法在构建CDS 时大多没有考虑端到端时延、丢包率等传统网络性能。为此，可以考虑将链路的网络性能作为链路的权重，并设计算法构建链路总权重较低的CDS。

此外，现有的CDS 构建算法大多在无人机位置、功率等固定的基础上构建CDS。可以考虑将调整无人机的位置、功率等与CDS 构建结合起来，在满足FANET 任务性能约束的情况下，进一步优化FANET 的网络性能。

3.2.2CDS 维护算法

由于FANET 的高度动态性，CDS 构建算法构建的CDS 无法保证永久有效。此时，如果使用CDS构建算法重构CDS，可能会产生较高的拓扑控制成本。在这一背景下，CDS 维护算法主要用于动态更新FANET 中的CDS，最小化CDS 更新的成本。

文献[55]算法2 在使用基于最小生成树的启发式CDS 构建算法生成CDS 候选集的基础上，使用马尔可夫模型预测即将断开的链路，并在CDS 候选集中找到一个与当前CDS 最相似的CDS 作为下一时刻的CDS。文献[63]考虑了一种特殊的CDS 维护场景。在该场景中，部分无人机会根据任务需要而改变自己的位置，其他无人机通过调整位置来实现CDS 维护。此外，一些无人机节点（如网关无人机）需要始终作为CDS 中的支配节点。为了解决该问题，文献[63]首先提出了一种启发式方法来确定需要移动的无人机节点，随后采用了一种级联方法来确定无人机节点的移动位置。

文献[64]提出了一种近似自适应最小d连通支配集（AMDC,adaptive minimaldCDS）算法，用于动态维护FANET 中的d跳CDS。该算法首先使用一种近似算法来维持最小d跳支配集，然后加入额外的节点来连接得到的d跳支配集以形成d跳CDS，最后使用顶树数据结构求得最小d跳CDS。

在优化目标方面，更新节点数量可以反映算法的通信开销，因此CDS 维护算法可通过最小化更新节点的数量来最小化通信开销。此外，当CDS维护算法通过调整无人机位置来维护CDS 时，CDS维护算法可以通过最小化无人机的移动距离，以尽快完成拓扑维护并减少无人机的能量消耗。在执行方式方面，分布式的执行方式更适合于CDS 维护算法，但分布式CDS 维护算法具有较高的通信开销。

CDS 维护算法主要适用于在保证当前基于CDS 的FAENT 服务尽可能不中断的情况下，维护FANET 中的CDS 并提高其性能。当系统中存在中央控制器时（如FANET 采用SDN 架构），可以设计集中式的CDS 维护算法或者重新执行CDS 构建算法，根据全局信息维护CDS，降低实现难度。当系统中不存在中央控制器时，需要设计分布式的CDS 维护算法，使各无人机仅根据其局部信息来维护CDS。

大多CDS 维护算法采用集中式的方法来实现CDS 维护，这不适用于无人机位置动态变化的FANET。少量CDS 维护算法虽然采用了分布式实现方式，但具有较高的通信开销。以上问题也导致CDS 维护算法目前在FANET 中应用较少。在未来，如何设计具有较低通信开销的分布式CDS 维护算法有待进一步研究，且具有一定难度。对于这一问题，可以考虑令各无人机分布式地调整各自的位置、功率等，从而维持已有的CDS 并优化FANET的性能。

此外，基于CDS 的FANET 中的支配节点具有较高的重要性。支配节点一旦损坏，整个FANET将无法继续运行。为此，需要考虑如何在支配节点损坏后快速形成新的CDS。一种可能的解决思路是给各支配节点选择备份节点，在支配节点故障后令备份节点代替故障的支配节点成为新的支配节点。

3.3 基于集群的拓扑控制算法

基于集群的拓扑控制算法主要在无人机位置已知的情况下通过集群划分和首领选择来实现对FANET 的拓扑控制，其应用场景如图7 所示。基于集群的拓扑控制算法与基于CDS 的拓扑控制算法的应用场景较类似，但其构建出的基于集群的FANET 与基于CDS 的FANET 具有不同的特点（详见2.1 节）。

图7 基于集群的拓扑控制算法的应用场景

根据算法的执行阶段，本文将基于集群的拓扑控制算法分为集群构建算法和集群维护算法。其中，集群构建算法负责进行集群划分和集群首领选择，从而形成初始的FANET 拓扑；集群维护算法则通过更新集群首领以及集群成员来维护FANET 拓扑。

3.3.1集群构建算法

文献[65]提出了一种集群控制方法来应对FANET 中无人机高移动性带来的挑战。在集群划分和首领选择方面，该方法首先根据FANET 执行的任务确定最佳集群数量，随后使用k均值算法将所有无人机划分为k个集群，并选择每个集群的中心无人机作为集群首领。

文献[66]使用集群控制方法来解决FANET 中无人机能量有限和高移动性问题。在集群划分方面，该方法首先通过暴力求解法求得最佳集群数量，随后使用k均值算法将FANET 中的无人机聚类为k个集群。在首领选择方面，每个集群中适应度最高的无人机被选为集群首领，以延长集群寿命并平衡网络流量。适应度计算式为

其中，EnergyResidual表示无人机的剩余能量，dist 表示无人机与集群内其他无人机的距离之和，Ddiff用于平衡集群之间的负载，w1、w2和w3表示各变量所占的权重。

文献[67]提出了一种集群控制方法来解决FANET 中的无人机高移动性和拓扑动态变化问题。在集群划分方面，该方法使用了一种改进的k均值算法来划分初始无人机集群。在首领选择方面，考虑到无人机高移动性和拓扑动态变化，使用以下适应度函数来选择集群首领

文献[68]提出了一种集群控制算法和一种路径规划算法来解决FANET 中无人机能量有限、移动性高的问题，下面重点分析其集群控制算法。该算法使用监督学习和单层感知器学习规则来训练集群首领选择系统，集群首领选择系统以无人机剩余能量、无人机之间的平均距离和无人机的度数3 项指标为依据选择集群首领。

文献[69]提出了一种集群控制方法来解决FANET 中的动态拓扑和无人机能量有限的问题。在集群首领选择和集群划分方面，各无人机根据自身的荧光素含量（与该无人机和邻居无人机之间的距离有关）以及剩余能量来计算自己的适应度。随后，各无人机向其邻居无人机发送自己的适应度并接受邻居无人机发送的适应度。如果该无人机在其邻居无人机中具有最高的适应度，则该无人机向其邻居无人机宣布自己为集群首领；否则，该无人机将邻居无人机中适应度最高的无人机作为集群首领，而自己成为集群成员。当集群形成后，各集群成员根据集群首领的位置变化情况来调整自己的位置。

文献[70]首先提出了一种基于混合灰狼优化算法的高能效、无范围的定位算法，然后提出了一种集中式的集群构建方法。在集群划分方面，该文献首先通过数学分析求得最优集群数量，使无人机向地面基站传输数据消耗的能量最少。随后使用混合灰狼优化算法来寻找每个集群的中心点，从而将各无人机划分到各个集群。在集群首领选择方面，该文献根据集群内无人机之间的距离、邻居数量和无人机的剩余能量来计算每个无人机的适应度，每个集群中适应度最高的无人机成为该集群的集群首领。在集群间的数据传输方面，该文献构建了一个基于最小生成树的虚拟主干网络，从而以最小跳数进行集群间的数据传输。由于该文献提出的是集中式的集群构建方法，这一方法需要首先获取各无人机的位置、剩余能量等信息，并根据收集的信息在某一中央控制器中求得集群首领选择和集群划分结果，随后中央控制器将计算结果发送给各无人机。

文献[71]提出了一种集中式的集群控制方法来解决FANET 中的路由和安全问题。在集群首领选择和集群划分方面，该方法根据无人机的剩余能量、声誉、运行时间、交易数量、移动性和连通性等指标，使用改进的人工蜂群算法选择集群首领。随后，剩余无人机加入其邻居的集群首领所在的集群，完成集群划分。此外，该方法使用区块链技术来保护路由数据。该文献提出的集群首领选择方法需要以集中式的方式运行，因此这一方法需要首先获取各无人机的位置、剩余能量、声誉和运行时间等信息，并根据收集的信息在某一中央控制器中求得集群首领选择结果，随后中央控制器将计算结果发送给各无人机。

为了使FANET 能够满足紧急通信的需求，文献[72]提出了一种基于PSO 算法的集群控制方法。在集群划分方面，该方法通过计算与相邻无人机的欧氏距离来获得最近的节点对，具有最近邻居距离的无人机被划分到同一个集群中，以节省数据传输过程中的能量消耗并延长链路生存时间。在集群首领选择方面，该方法根据无人机之间的平均距离、无人机与地面基站的平均距离以及无人机的剩余能量等指标，使用PSO 算法选择集群首领。该文献提出的集群首领选择方法和集群划分方法均需要以集中式的方式运行，因此这一方法需要首先获取各无人机的位置、速度、剩余能量等信息，并根据收集的信息在某一中央控制器中求得集群首领选择和集群划分结果，随后中央控制器将计算结果发送给各无人机。

文献[73]考虑了一种特殊的FANET 场景。在该场景中，无人机分为若干组，只有同一组的无人机之间需要互相通信。为此，作者提出了一种联盟博弈论框架，基于无人机的移动性信息，在集群大小和集群直径约束下，以分布式方式将无人机划分为若干联盟，从而最小化无人机之间的通信时延。

文献[74]提出了一种FANET 集群控制方法来解决无人机的高移动性问题。首先，每个无人机根据以下适应度函数来计算自己的适应值

其中，λi表示无人机的平均安全度，与该无人机和其邻居无人机之间的距离有关；ER,i表示无人机的剩余能量；σi表示移动感知因子，与该无人机的速度以及其邻居无人机的速度有关；w1、w2和w3表示各变量所占的权重。随后，在其单跳邻居中具有最小适应值的无人机成为集群首领，并且集群首领的邻居变成它的集群成员。

为了在时延约束下最大化无人机的覆盖性能，文献[75]提出了一种基于贪心思想的集群控制算法。首先，该算法通过添加或删除单个集群首领的方式来确定最终的集群首领，随后，其余无人机选择与其时延最小的集群首领并加入该集群。

在集群划分方面，无人机之间的距离、集群内无人机的数量和集群直径等指标是主要的划分依据。距离相近的无人机被划分到同一集群能够减少集群的空间大小，从而降低无人机之间的通信时延。各集群中包含相似数量的无人机以及具有相似的直径，可以平衡各集群产生的负载，提高数据的传输成功率。在集群首领选择方面，无人机的剩余能量、无人机之间的距离、无人机到地面基站的距离、无人机之间的相对速度、节点的度等指标是主要的参考依据。选择剩余能量多的无人机作为集群首领可以平衡各无人机的能量，延长FANET 的生存时间。无人机之间的距离主要影响无人机之间的通信时延，无人机到地面基站的距离主要影响集群首领到地面基站的通信时延，无人机之间的相对速度主要影响集群首领的生存时间，节点的度则主要影响集群之间的负载均衡。

基于集群的FANET 在可扩展性、可靠性、数据收集、能量效率和时延等方面更具优势，因此集群构建算法主要适用于在执行大规模数据传输任务的FANET（如利用FANET 从地面物联网设备收集数据）中划分集群并为各个集群选择集群首领，从而提高FANET 的数据传输效率。与CDS 构建算法不同，集群构建算法没有严格设定每个无人机的通信范围，因此集群构建算法更适用于无人机通信范围（由无人机的发送功率决定）可灵活调整的场景。

大多集群构建算法在进行集群首领选择和集群划分时仅考虑了同一集群中集群首领和集群成员之间的通信性能，而没有考虑不同集群中集群首领之间进行通信的性能。为此，需要将不同集群中集群首领之间的通信性能作为集群首领选择和集群划分的依据，从而优化FANET 的整体性能。此外，大多数集群构建算法大多在无人机位置、功率等固定的基础上进行集群首领选择和集群划分。可以考虑将调整无人机的位置、功率等与集群构建结合起来，在满足FANET 任务性能约束的情况下，进一步优化FANET 的网络性能。

3.3.2集群维护算法

文献[65]根据集群首领与邻居的平均相对速度、集群首领与邻居的相对位置以及地面基站与集群间无人机的平均距离3 项指标在每个集群中选择一个备用集群首领。当某个集群首领离开FANET 时，其备用集群首领成为新的集群首领。在文献[66]中，当FANET 中不在集群中的无人机占到20%以上时，重新执行集群划分和集群首领选择。在文献[67]中，如果集群首领离开集群，则在该集群中重新选择集群首领，集群首领根据无人机的剩余能量来管理集群成员。在文献[69]中，集群首领将剩余能量大于或等于阈值的集群成员继续作为其集群成员，而将剩余能量低于阈值的无人机作为死亡节点，不再作为其集群成员。

选择备用集群首领代替离开的集群首领以及重新选择集群首领是维护集群首领的常用方式，而能量指标是维护集群成员的主要依据。由于各无人机的位置频繁变化，集群维护算法需要高频率执行。因此，选择备用集群首领比重新选择集群首领更适合于基于集群的拓扑控制算法。

集群维护算法主要适用于在保证当前基于集群的FAENT 服务尽可能不中断的情况下，维护FANET 中的集群并提高其性能。当系统中存在中央控制器时（如FANET 采用SDN 架构），可以重新选择集群首领或重新进行集群划分；当系统中不存在中央控制器时，需要设计分布式的集群维护算法，使各无人机仅根据其局部信息来确定自己的角色以及加入或离开集群。

现有集群维护算法主要通过选择备用集群首领或者重选集群首领来完成集群维护，其思路局限于集群首领的选择方面。可以进一步考虑以动态更新集群数量、集群成员加入其他集群等方式来实现集群维护。此外，现有集群维护算法主要在集群首领离开后进行集群维护，因此可以考虑在集群首领能量不足、网络性能不佳等情况下主动进行集群维护。

3.4 基于虚拟力的拓扑控制算法

基于虚拟力的拓扑控制算法是一种分布式拓扑控制算法，该算法假设每个无人机节点都会受到来自其邻居节点、障碍物、任务目标等的虚拟力，该虚拟力的大小通常和无人机与邻居节点、障碍物、任务目标之间的距离有关。由此，每个无人机仅需要根据其受到的来自邻居无人机、障碍物、任务目标等的虚拟力的合力自主调整位置。

本文将基于虚拟力的拓扑控制算法中的虚拟力分为4 类：吸引力、排斥力、障碍避免力和任务力，如图8 所示。这4 种力分别用于实现以下4 个目标：1) 各无人机能够保证网络的连通性以进行信息交换；2) 无人机之间能够保证期望的距离，避免发生碰撞；3) 无人机能够绕过障碍物；4) 无人机集群能完成既定的任务。下面，本文将根据虚拟力的种类及其实现的目标对基于虚拟力的拓扑控制算法进行详细的分析。

图8 虚拟力种类

在无人机作为空中基站为地面用户提供服务的场景中，文献[77]提出了一种分布式运动控制算法，使每个无人机能够自主运动并按需覆盖地面用户。为了维持无人机网络的连通性，该算法中的吸引力控制无人机向热点区域中心运动。受万有引力定律启发，吸引力的计算式为

其中，di是无人机到热点以及2 个相邻热点之间连线的距离，是由热点重要性决定的吸引力因子。受胡克定律启发，使无人机之间能够保证期望距离的排斥力的计算式为

其中，Kr是排斥力因子，dij是无人机i和无人机j之间的距离，Ropt是无人机之间的期望距离。此外，根据万有引力定律，障碍避免力的计算式为

其中，dsafe是无人机到障碍物的安全距离，dobs是无人机和障碍物之间的实际距离。最后，根据万有引力定律，引导无人机接近地面用户的任务力的计算式为

其中，ka为任务力因子，due为无人机与地面用户之间的距离，Rs为无人机的感应范围。最终，无人机受到的虚拟力合力为

文献[78]提出了一种基于虚拟力的拓扑控制算法，可用于在基于集群的FANET 中控制集群成员跟随集群首领移动，且控制整个FANET 完成区域覆盖任务。维持网络连通性的吸引力和保持无人机距离的排斥力由同一计算式给出

其中，kT≥ 0，α∈[0,1]，dij是无人机i和无人机j之间的距离，αR是无人机之间的期望距离，eij是无人机i和无人机j的单位方向向量。为了减少无人机之间的重复覆盖区域，无人机受到的任务力的计算式为

其中，kC＞ 0，β∈[0,1]，dij是无人机i和无人机j之间的横向距离，D是无人机之间的最大横向感应范围，是无人机j到无人机i的垂直单位方向向量。最终，如果无人机i跟随无人机j，则无人机i受到的虚拟力合力为

在空中无人机为地面孤立用户提供多跳中继服务的场景中，文献[79]提出了一种基于虚拟弹簧模型的拓扑控制算法。链路的通信质量可以用链路预算表示为

其中，LBreq表示链路请求的预算，α表示传播衰减指数，k的值与链路类型有关。该虚拟力可同时用于保持网络连通性、维持无人机之间的距离以及满足FANET 对通信性能的需求。文献[80]也使用了类似的方法。

此外，一些文献使用势能来反映无人机受到的虚拟力。在分层式FANET 中，文献[81]提出了一种分层式无人机群控制算法，用于保持网络的连通性，并避免无人机之间发生碰撞。首先，为了使跟随者与其领导者之间的距离处于安全距离范围内，跟随者会受到来自其领导者的吸引力或排斥力，其对应的势能函数为

其中，r1表示最小安全距离，r2表示最大安全距离，diL表示跟随者与领导者之间的距离。此外，为了避免无人机之间发生碰撞，无人机会受到与其距离较近的无人机的排斥力，其对应的势能函数为

其中，Ti表示与无人机i的距离小于最小安全距离的无人机集合，dij表示无人机i和无人机j之间的距离。式(21)和式(22)中的势能函数实际上是遵循胡克定律的弹性力势能函数。无人机需要通过移动，尽量将自身受到的势能之和降低为零。

基于虚拟力的拓扑控制算法是一种分布式的FANET 拓扑控制算法。在通信开销方面，每个无人机仅需根据其邻居节点的相关信息来自主调整位置，通信开销小。此外，此类算法可以有效地满足FANET 在连通性、碰撞避免、障碍物避免和任务执行等方面的需求。此类算法的虚拟力及其对应势能的设计大多受现有物理模型启发，例如胡克定律、万有引力定律等。其中，基于胡克定律的虚拟力的大小随实际距离与设定距离之差线性变化，因此，该虚拟力主要用于将2 个无人机之间的距离或者一个无人机与目标位置之间的距离维持在设定值。此外，基于万有引力定律的虚拟力的大小随距离减小而迅速增大。因此，基于万有引力定律的虚拟力主要用于无人机飞往多个候选位置（或节点）中的一个位置（或节点），以及避免无人机碰撞。在设计基于虚拟力的拓扑控制算法时，本文需要FANET 的实际应用需求来设计合理的虚拟力。表4 展示了基于虚拟力的拓扑控制算法的比较结果。

表4 基于虚拟力的拓扑控制算法的比较结果

目前，基于虚拟力的拓扑控制算法主要适用于多个无人机以自组织的方式形成FANET 来为地面设备提供通信覆盖服务（例如，在灾难救援场景中，自组织的FANET 作为空中基站为灾区用户提供通信服务）。此外，基于虚拟力的拓扑控制算法还可用于保持无人机之间的分层结构或特定队形。

基于虚拟力的拓扑控制算法重点关注FANET的连通性和覆盖性能。在网络性能方面，基于虚拟力的拓扑控制算法可以保证FANET 的连通性，但不关注时延、丢包率等性能的优化。在任务性能方面，基于虚拟力的拓扑控制算法可以实现FANET对目标区域或目标用户的覆盖，但不关注用户吞吐量等通信质量的优化。针对基于虚拟力的拓扑控制算法存在的不足，一方面，可以考虑在设计虚拟力时引入端到端时延、用户吞吐量等指标，使端到端时延、用户吞吐量等指标影响无人机所受到的虚拟力大小。另一方面，可以考虑将基于虚拟力的拓扑控制算法与其他种类的拓扑控制算法相结合（例如，在利用基于虚拟力的拓扑控制算法满足FANET 的连通和覆盖需求后，各无人机进一步调整自己的位置，从而在维护网络连通性的前提下进一步优化FAENT 的端到端时延等网络性能以及用户吞吐量等任务性能），实现不同种类算法之间的优势互补。

4 挑战和未来研究方向

当前，FANET 拓扑控制仍处于发展阶段。本节讨论并总结了FANET 拓扑控制仍面临的挑战以及未来的研究方向。

1) 通信链路频繁中断

现有的FANET 拓扑控制算法大多假设无人机之间以及无人机与地面基站之间能够维持稳定的通信。而在真实的FANET 中，无人机密度较低且具有高度的动态性和不确定性，因此无人机之间以及无人机与地面基站之间的通信链路频繁中断。在无人机通信链路间歇性连接的场景中，设计一种有效的FANET 拓扑控制算法是一项艰巨且具有实际意义的任务。

2) 高频率动态执行

FANET 中的无人机具有高度的动态性和不确定性，相应地，FANET 拓扑控制算法需要高频率动态执行以实时更新FANET 拓扑，从而维持FANET的性能。FANET 拓扑控制算法的高频率动态执行对算法的收敛时间、通信开销、实现的性能等方面提出了严格的要求。然而，目前只有少量FANET 拓扑控制算法能够满足高频率动态执行的要求，有待于进一步研究开发。

3) 评估工具

FANET 拓扑控制的相关研究在仿真实验中使用了多种不同的仿真工具，例如，NS-2、OPNET、OMNET++、MATLAB 等。然而，这些仿真工具在3D 场景、通信信道和移动模型等方面的建模还不能很好地支持FANET 的特殊要求。为了有效地评估FANET 拓扑控制算法的性能，需要开发一种支持FANET 特性的仿真工具。

4) 安全问题

FANET 的拓扑结构是一种重要的网络资产，且严重影响FANET 的安全性。例如，当使用分层式FANET 执行侦察等任务时，根据FANET 的拓扑结构，敌方能够轻易地识别出其中的领导者无人机。此时，敌方仅需破坏乃至劫持少量的领导者无人机，就可对我方的FANET 造成严重损害。因此，在具有安全性需求的场景中，FANET 拓扑控制算法需要生成能够隐藏无人机相关信息的FANET 拓扑。

5) 任务性能和通信性能

FANET 的任务性能需求和通信性能需求之间通常是矛盾的[34,51]，而大多数FANET 拓扑控制算法没有考虑这一特性。为此，FANET 拓扑控制算法生成的FANET 必须同时满足FANET 的任务性能需求和通信性能需求，实现FANET 任务性能和通信性能之间的平衡。

6) 故障恢复

现有的FANET 拓扑控制算法主要通过生成具有容错性的FANET 拓扑来应对FANET 发生的故障，而不是在FANET 发生故障后快速恢复有效的FANET 拓扑。事实上，具有容错性的FANET 拓扑只能应对FANET中极少数无人机发生故障的情况，因此，在FANET 部分无人机发生故障后快速恢复有效的FANET 拓扑更符合实际的需求，相关的FANET 拓扑控制算法也需要进一步研究。

5 结束语

本文对现有的FANET 拓扑控制研究进行了综述。首先，分析了相关综述的不足，并指出了本文的贡献。随后，介绍了FANET 的网络架构以及FANET 拓扑控制的研究框架和需求和分类方法。之后，对每一类FANET 拓扑控制算法都进行了详细的分析。最后，总结了FANET 拓扑控制仍需解决的问题以及未来的研究方向。