大规模UAV编队信息交互拓扑的分级分布式生成

董文奇，何锋

北京航空航天大学 电子信息工程学院，北京 100083

无人机(Unmanned Aerial Vehicle，UAV)编队飞行是当前UAV领域研究的热点，随着UAV技术的不断发展，其已逐步被应用在目标侦察、目标跟踪、目标打击、通信中继、喷洒农药、空中加油等众多军用和民用领域[1]。集群UAV突破了单个无人机技术和性能上的限制，利用自组网技术组织多种性能不同、功能各异的UAV协同合作，极大地提高了执行任务的能力和效率[2]。伴随着UAV集群执行的任务越来越复杂多样，编队规模逐渐增大，编队内部UAV不易同步，编队队形难以保持，同时由于UAV自身存在计算/存储能力受限、机载能源有限等特点[3]，UAV编队飞行面临着新的挑战。因此对于大规模UAV集群，如何在保持队形的同时，尽量减少总通信代价以及提高编队续航能力进行UAV编队飞行是一个亟需解决的问题。

UAV编队飞行时，只需要使用部分通信链路即可保持队形，这部分通信链路即为队形保持下的信息交互拓扑，是通信网络拓扑的一个子集[4]。按照编队结构，多智能体信息交互拓扑的研究可大致分为领航-跟随者编队、一致性编队、刚性编队以及持久编队4类。针对领航-跟随者编队信息交互拓扑的研究，文献[5]证明了领航-跟随者控制方法下，UAV编队的信息交互拓扑是通信网络拓扑的一棵有向生成树；在此基础上，文献[4]提出了一种集中式基于最小树形图(Minimum Cost Arborescence，MCA)的领航-跟随者编队信息交互拓扑优化算法。一致性编队的主要核心思想是智能体利用与之通信的邻居智能体的状态信息更新自身的状态，并最终使所有智能体状态达到一致，比如文献[6]在动态变化的信息交互拓扑和权重因子条件下，提出了一种新的一致性控制协议，并将一阶系统推广到n阶可控系统。刚性编队则通过生成最优刚性图实现信息交互拓扑的构建[7-8]。持久编队信息交互拓扑的实现通过对最优刚性图进行有向化操作实现，文献[4，9]对这种思想进行了进一步扩展，分别讨论了通过MCA和5种有向化操作生成最优持久图的方法。

对于领航-跟随者编队信息交互拓扑的研究，目前主要集中在小规模UAV编队，文献[4]中的大规模UAV编队的规模也只有16，且仅以通信链路长度衡量通信代价，并将总通信代价最小作为单一的优化目标。分级分簇结构在扩大组网规模方面有着天然优势，在无线传感器网络方面应用广泛[10-12]，并已逐步应用在UAV领域，但目前仍未发现有相关文献将其应用在UAV编队信息交互拓扑的研究上。

因此，本文在文献[4]的基础上，将分级分簇结构引入信息交互拓扑的研究中，同时以提高编队续航能力、减少编队总通信代价作为组合优化目标，提出了一种分级分布式信息交互拓扑生成算法，并通过OMNeT++进行算法仿真验证。

本文结构如下：第1节介绍UAV编队信息交互拓扑模型；第2节介绍UAV编队信息交互拓扑的生成算法；第3节通过实验仿真，从求解时间、总通信代价和UAV剩余能量3方面对本文算法进行评估；第4节对本文工作进行总结，并对下一步工作进行展望。

1 信息交互拓扑模型

在UAV编队飞行中，常用的编队控制方法主要有领航-跟随者(Leader-Follower)方法、一致性方法、刚性图方法和持久图方法等，其中刚性图方法和持久图方法均属于图论法[13-14]。领航-跟随者方法是目前多UAV编队控制中最常用的方法之一，该方法是将编队中的某架无人机指定为领航者，而其他无人机作为跟随者，其具有较强的扩展性，且节约能量、简单易行，如图1所示。

文献[5]已经证明，领航-跟随者编队控制方法对应UAV编队的信息交互拓扑为通信网络拓扑的1棵有向生成树，信息交互拓扑和通信网络拓扑均可用赋权有向图表示。

1.1 图论基础

队形保持下UAV编队的通信网络拓扑可用赋权有向图G=(V,A,W)表示[15]，其中V={vi},i∈{1,2,…,n}，是有向图的点集合，vi代表UAVi；A={aij},i,j∈{1,2,…,n},i≠j，是有向图的弧集合，aij代表UAVi和UAVj之间的通信链接；W={wij},i,j∈{1,2,…,n},i≠j，是有向图所有弧的权值集合，wij代表通信链接aij的权值。信息交互拓扑是通信网络拓扑的一个子集，即T=(V,A*,W*)⊆G。

1) 生成树[16]：给定一个无向图G，如果图G的一个生成子图T是一棵树，则称T是G的一棵生成树。

2) 最小生成树：给定一个带权无向图G，存在一棵生成树T，其所有弧的权值和W(T)最小，则称T是G的最小生成树。

有向图的最小生成树称为最小树形图，队形保持下的信息交互拓扑和通信网络拓扑均可用赋权有向图表示，因此本文基于最小树形图设计队形保持下的信息交互拓扑模型及生成算法。

1.2 通信链路

编队飞行时，UAV之间采用无线链路发送位置信息以保持队形。设计UAV编队的信息交互拓扑生成算法时，需要对通信链路的代价进行合理的衡量，现有的信息交互拓扑模型在衡量通信链路代价时只单一考虑链路长度，本文在其基础上同时考虑了位置误差的传递迭代，为简化计算并对其进行了归一化：

1) 通信链路的长度[17]：一般情况下，UAV之间的通信距离越短，UAV所消耗的能量就越少，对应通信链路的代价越小。

UAVi和UAVj之间的距离用dij表示，代表链路的距离代价，则

(1)

式中：(xi,yi)为UAVi的位置坐标；(xj,yj)为UAVj的位置坐标。

对其进行归一化处理：

(2)

式中：dsafe为UAV之间的安全距离[18]，小于安全距离UAV之间将有发生碰撞的危险；drange为UAV之间的最大通信距离。

将通信链路长度作为衡量指标进行信息交互拓扑的优化，得到的信息交互拓扑可以尽量降低UAV编队保持队形时的能量消耗。

2) 位置误差的传递迭代[19]：在领航-跟随者编队中，存在位置误差的传递迭代，越靠后的UAV与领航者之间存在的位置误差越大，因此对应通信链路的代价就越大。

领航-跟随者编队中，领航者的下级在接收到位置信息时，会以此作为其跟随目标，由于端到端延迟的存在导致下级节点实际位置与此时的理论位置存在一定误差；它继续将自身位置信息向下传，经过迭代就形成了位置误差的传递。由于位置误差的传递迭代，越远离领航者的通信链路的代价越大。因此本文根据远离领航者的程度，首先赋予无人机一个误差系数，用f表示，越远离领航者的UAV的误差系数越大，图2中各无人机的误差系数如表1所示。

表1 无人机误差系数fi

划分编队中UAV误差系数时以某一UAV为中心，该UAV的误差系数为0，半径为r圆形范围内的UAV误差系数为1，r～2r圆环范围内的UAV误差系数为2，以此类推。本文分级分簇结构中，二级领航者以一级领航者为中心，簇内节点以二级领航者为中心。

有向通信链路的误差代价用起点无人机的误差系数表征，如图2所示，可以看出通信链路的误差代价与链路长度无关，与远离领航者的程度有关。

图2 无人机误差系数划分示意图

综上所述，通信链路aij的误差代价fij取决于发送UAV，即

fij=fi

(3)

对其进行归一化处理：

(4)

式中：fmax为能够保持队形的最大误差系数。

将位置误差的传递迭代作为衡量指标进行信息交互拓扑的优化，得到的信息交互拓扑可以保证UAV编队队形尽量接近预期队形。

综合以上两方面，通信链路aij的权值wij表示为

wij=αdDij+αcFij

(5)

式中：αd、αc分别为距离权重系数和误差权重系数，并且

αd+αc=1

(6)

结合非交叉型分级分簇结构，本文将整个UAV编队的信息交互拓扑生成问题分解为若干小编队的信息交互拓扑生成问题，在各个簇首上分布式执行。队形保持下分级分布式领航-跟随者编队的信息交互拓扑网络模型如图3所示，簇内与簇间均采用领航-跟随者编队，一级领航者沿规划路线飞行，二级领航者跟随一级领航者飞行，簇内成员跟随二级领航者飞行，形成了分级分布式领航-跟随者编队。

图3 队形保持下分级分布式领航-跟随者编队信息交互拓扑网络模型

2 信息交互拓扑生成算法

现有的信息交互拓扑生成算法局限于小规模UAV编队，且优化目标单一。本文在其基础上，结合分级分簇结构，同时以提高编队续航能力和减少编队总通信代价为组合优化目标，提出了一种基于MCA的分级分布式领航-跟随者编队信息交互拓扑生成算法。由于本文的信息交互拓扑模型采用了分级分簇结构，因此需分别构建簇间信息交互拓扑与簇内信息交互拓扑。

分级分簇结构中簇群、簇首集合分别采用符号C、H表示，其中簇群i可表示为

(7)

簇首集合H可表示为

H={h1,h2,…,hi,…,hNc}

(8)

式中：hi表示簇群i的簇首，编队一级领航者用L表示，且L∈H。

2.1 编队续航能力

为提高UAV编队整体续航能力，本文采取了根据UAV剩余能量周期性更新簇首的方法，以均衡网络能量。

UAV剩余能量根据式(9)计算：

Ea=Eb-ER-ET-EM

(9)

式中：Eb为上一周期UAV的剩余能量；Ea为本周期UAV的剩余能量：ER为本周期UAV接收消息消耗的能量；ET为本周期UAV发送消息消耗的能量；EM为本周期UAV移动消耗的能量。

假设UAV单次接收消息消耗能量为Er，单次发送消息消耗能量为Et，UAV移动单位距离消耗能量为Em，簇首更新周期为t，时间t内发送消息次数为MT，时间t内接收消息次数为MR，时间t内移动的距离为s，则

(10)

2.2 总体通信代价

非交叉型分级分簇结构下，为保证总体通信代价最小，须分别计算簇内通信网络拓扑和簇间通信网络拓扑的最小树形图构建信息交互拓扑。

证明：UAV编队的通信网络拓扑为G={Gi∪GH},i∈{1,2,…,Nc}，若T的总体通信代价不是最小的，则存在T′，使得W(T′)

根据以上两个优化目标提出的分级分布式领航-跟随者编队信息交互拓扑的生成算法流程如图4所示。算法主要包括位置信息发送、信息交互拓扑计算、拓扑信息发送以及簇首重新选举4个步骤。

图4 基于最小树形图的分级分布式领航-跟随者编队信息交互拓扑生成算法

本算法在分簇完成的基础上进行，输入簇的个数以及各个簇的成员数并初始化队形。

步骤1位置信息发送，下级节点向上级节点发送位置信息。

步骤2信息交互拓扑计算，判断hi是否为一级领航者，一级领航者需同时构建簇间通信网络拓扑和簇内通信网络拓扑，二级领航者即普通簇首只需构建簇内通信网络拓扑，计算通信网络拓扑的最小树形图。

步骤3拓扑信息发送，一级领航者将簇间拓扑信息发送给二级领航者，簇首(包括一级领航者和二级领航者)将簇内拓扑信息发送给簇内成员，构建UAV编队信息交互拓扑。

步骤4簇首重新选举，时间间隔t后根据式(9) 和式(10)计算UAV的剩余能量并更新簇首，若簇首集合H改变需重新计算信息交互拓扑，若未改变则信息交互拓扑不变。

上述算法将降低总通信代价和提高编队续航能力作为组合优化目标，分步完成。首先，将通信链路长度、位置误差的传递迭代作为衡量链路通信代价的指标，并通过计算簇内、簇间通信网络拓扑的最小树形图实现减少编队总通信代价的目标。分级分簇网络结构中，簇首除了维持拓扑外，还需要收集下级节点的信息并计算拓扑，因此与普通节点相比，航行相同距离簇首消耗的能量更多；在上述算法中，通过根据UAV剩余能量周期性更新簇首的方法均衡网络中无人机的能量，实现提高编队续航能力的目标。另外，由于本文算法考虑到位置误差的传递迭代，采用分级分簇结构分别构建簇内、簇间信息交互拓扑，通过分布式计算达到大规模编队下队形保持的目的。

3 算法效能评估

3.1 算法评价

UAV编队飞行时，信息交互拓扑生成算法需能够快速响应，以保证编队内UAV在到达预定位置后迅速构建拓扑，防止发生碰撞甚至损毁，因此信息交互拓扑生成算法的求解时间是一个重要的评价标准。另外，针对本文算法的两个优化目标，分别以编队内UAV剩余能量和信息交互拓扑的总通信代价作为评价标准。

3.2 实验仿真

利用OMNeT++平台搭建大规模UAV编队飞行场景，假设每架UAV的通信范围为1 500 m[20]，UAV之间的安全距离为200 m[21]，并且在飞行过程中均不会发生任何故障。

编队规模为40时，采用本文算法生成的分级分布式领航-跟随者编队的信息交互拓扑如图5所示，其中红色节点为一级领航者，蓝色节点为二级领航者，其间连线构成簇间信息交互拓扑；绿色节点为簇内节点，其与各自簇首之间的连线构成簇内信息交互拓扑。保持相同编队队形，传统领航-跟随者编队的信息交互拓扑如图6所示，红色节点为领航者，绿色节点为普通节点。

图5 分级分布式领航-跟随者编队信息交互拓扑(αc=0.2)

图6 传统领航-跟随者编队信息交互拓扑(αc=0.2)

1) 求解时间

算法的时间开销主要取决于位置信息发送与拓扑信息发送两个步骤。消息的端到端延迟包括传输延迟、传播延迟以及排队延迟，传播延迟正比于两节点之间的距离；在位置信息发送步骤中，下级节点同时向上级节点发送位置信息，消息长度固定即传输延迟相同；消息在接收节点处存在排队延迟，如图7所示。而在拓扑信息发送步骤中，拓扑消息的长度正比于下级节点的数量，即传输延迟正比于下级节点的数量；消息在发送节点处存在排队延迟，如图8所示。两个步骤的时间开销均随着下级节点数量的增多而增大。

图7 位置信息发送步骤上级节点接收队列

图8 拓扑信息发送步骤上级节点发送队列

分级分布式领航-跟随者结构采用分级分簇结构，簇首构建簇内信息交互拓扑，其下级节点数量即该簇群的成员节点数量；一级领航者构建簇间信息交互拓扑，其下级节点数量即二级领航者的数量，所以分级分布式领航-跟随者结构信息交互拓扑的求解时间与各个簇群的规模以及簇群的数量正相关；而在传统领航-跟随者编队中，信息交互拓扑的求解时间与整个编队的规模正相关。因此小规模编队时两种编队结构信息交互拓扑的求解时间相差较小，而随着编队规模的增大，分级分布式领航-跟随者编队结构的优势会逐渐显著。

通过实验对比不同编队规模下分级分布式领航-跟随者、传统领航-跟随者两种编队结构信息交互拓扑的求解时间，如图9所示。其中相关参数如表2所示。

表2 求解时间对比实验的相关参数

从图9中可以看出，20～80架无人机几种规模下分级分布式领航-跟随者编队信息交互拓扑的求解时间均小于传统领航-跟随者编队，求解效率分别约提高74%、85%、170%和250%，而当编队规模为100时，传统领航-跟随者编队由于位置误差的传递迭代已不能保持原有队形。

图9 两种编队结构信息交互拓扑求解时间对比

针对分级分布式领航-跟随者编队，一般来说，簇群规模大于簇群数量，此时信息交互拓扑的求解时间取决于簇群规模，簇群规模越大其求解时间越大；而当簇群规模小于簇群数量时，信息交互拓扑的求解时间取决于簇群数量，簇群越多其求解时间越大。因此分级分布式领航-跟随者编队结构下，为使信息交互拓扑求解时间最小，在给定编队规模的前提下应尽量使簇群数量与簇内UAV数量相当。

2) 总通信代价

分级分布式领航-跟随者编队采用分级分簇结构，需分别构建簇内、簇间通信网络拓扑，如图10(a) 所示。与传统结构相比，簇群的存在使得在构建通信网络拓扑时舍弃了一部分通信链路(图10(b)中绿色通信链路)。

本文算法在链路通信代价的衡量上同时考虑了链路长度以及位置误差的传递，并引入了距离权重系数αd以及误差权重系数αc。当αd=1.0时，即只用链路长度衡量链路通信代价时，分级分簇结构由于舍弃了一部分通信链路，信息交互拓扑总通信代价很可能高于传统结构；而当链路的通信代价同时考虑链路长度和位置误差的传递迭代时，分级分簇结构中位置误差仅仅在簇内或者簇首间传递，而传统结构在整个编队中传递(图10 中数字为链路误差代价)。此时伴随着αc的增大，分级分布式领航-跟随者编队在总通信代价上会明显优于传统领航-跟随者编队。

图10 两种编队结构通信网络拓扑示意图

通过实验对比不同距离权重系数下分级分布式领航-跟随者、传统领航-跟随者两种编队结构信息交互拓扑的总通信代价，如图11所示。其中相关参数如表3所示。

表3 总通信代价对比实验相关参数

从图11中可以看出，在αd=1.0时，此时通信链路权重的衡量只考虑了长度，本文分级分布式领航-跟随者编队的总通信代价高于传统领航-跟随者编队，这是由于分级分簇结构舍弃了通信网络拓扑中的一部分通信链路；而在αd=0.8,0.6,0.4 时，通信链路权重考虑了位置误差的传递迭代，此时分级分布式领航-跟随者编队的总通信代价低于传统领航-跟随者编队，对于传统领航-跟随者编队，由于位置误差的传递迭代，当编队规模足够大时编队队形将难以保持。UAV编队飞行时，αd参数的选取需要在通信代价和队形保持之间进行权衡。

图11 两种编队结构信息交互拓扑总通信代价对比

3) UAV剩余能量

本文算法的分级分布式领航-跟随者编队采取了分级分簇结构，与传统领航-跟随者编队相比在以下两个方面均衡了网络能耗：① 信息交互拓扑的计算在各个簇首上分布式执行，相当于各个簇首共同分担领航者的工作，避免出现领航者能耗过快的情况；② 可通过周期性选取簇首，进一步均衡网络能耗，以提高编队续航能力。

现用编队中UAV剩余能量的标准差来衡量网络能耗的均衡程度，通过实验进行仿真验证，相关参数如表4所示。

表4 剩余能量对比实验相关参数

图12是仿真时间10 s和20 s时两种编队结构UAV剩余能量的分布折线图，从图中可以看出本文分级分布式领航-跟随者结构中UAV剩余能量的分布更为均匀，标准差分别为1 006.463 293和3 109.960 689，而传统领航-跟随者结构UAV剩余能量的标准差分别为1 363.489和4 472.05。

图12 两种编队结构中UAV剩余能量分布折线图

4 结 论

本文提出的基于最小树形图的分级分布式领航-跟随者编队信息交互拓扑生成算法，其网络模型引入了分级分簇结构，更适应于大规模UAV编队。算法的仿真结果表明：

1) 在编队规模为20～80时，分级分布式领航-跟随者编队的求解时间均低于传统领航-跟随者编队的求解时间，且随着编队规模增大，本文算法优势将更加显著。

2) 在通信链路代价只考虑链路长度的情况下，本文算法由于采用了分级分簇结构，总通信代价高于传统领航-跟随者编队；在通信链路代价同时考虑位置误差的传递迭代时，本文算法的总通信代价明显低于传统领航-跟随者编队。

3) 本文算法通过周期性更新簇首，相同时间后编队中UAV剩余能量标准差更小，反映了网络能耗更加均衡，可有效提高编队整体续航能力。

进一步考虑UAV损毁以及通信链路中断等突发情况下本文方法的适应性，在本文算法中UAV编队的信息交互拓扑需进行周期性更新，当发生UAV损毁或者通信链路中断时，信息交互拓扑会及时进行再生成，但还是需要进一步考虑反应速度以及再生成代价等方面的影响。反应速度方面，突发情况下编队的信息交互拓扑应及时进行再生成，同时再生成时间应尽量小，否则可能发生更严重的碰撞事故；再生成代价方面，不同的突发情况对信息交互拓扑产生的影响不同，比如簇内通信链路中断仅影响簇内信息交互拓扑，簇间通信链路中断仅影响簇间信息交互拓扑，此时往往不需要进行整个信息交互拓扑的再生成。本文方法由于采用了分级分簇结构，可根据突发情况的类型，仅针对某个簇内的信息交互拓扑或者簇间信息交互拓扑进行再生成，再生成效率更高，代价更小。综上所述，本文算法经过反应速度等方面的完善可以适应突发情况下的信息交互拓扑优化生成，突发情况下算法的适应性将是后续进一步研究的方向。