双向通信无人机集群领航顶点选取方法

戴丽

（国防科技大学 文理学院，湖南 长沙 410073）

多智能体系统控制技术是人工智能时代的研究热点之一[1]，其成果可用于多个领域，如智能交通、机器人编队，甚至是军事用途，如无人机蜂(狼)群作战等。无人机集群作为一种特殊的多智能体系统，个体无需全局通信，仅通过对其周围一定范围内个体间的通信、合作和协调等就可以表达集群整体结构和功能。它在自组织能力、推理能力，以及对未知环境的适应性等方面有很多潜在应用。

无论是地面起飞式无人机集群，还是空投式无人机集群，其控制技术的难点都在于队形控制，核心在于解决可行性和有效性两个问题[2]：可行性是研究无人机集群能不能全局可控，使之形成所有预定队形；有效性则回答了最少需要输入多少信号，才能达到全局可控。最小领航集选取与这2个问题密切相关。

对于通信网络拓扑结构图为有向图的领航跟随网络系统，文献[3]通过引进匹配概念，使有向网络的可控性问题已得到较好解决。但是，对于无向领航跟随网络系统控制而言，正如Kumar等[4]于2019年所指出的那样：如何选取领航顶点、如何选取最少个数的领航顶点都是尚待解决的难题。

目前，无向网络控制技术已经引起人们的广泛关注。文献[5]是一篇较早关注无向网络可控性的文章，该文通过Kalman秩条件给出了无向网络可控的充要条件。研究无向网络领航集常用的图结构有：强制零点集(zero forcing set, ZFS)[4,6-8]、约束匹配(constraint matching, CM)[8-11]和非平凡等价划分(nontrivial equitable partition，NEP)[12-15]等。已有的研究成果表明无向网络可控当且仅当领航集是推广的ZFS，且Shima等[8,10]发现了网络中ZFS与CM之间具有等价关系。基于NEP概念人们给出了网络可控的必要条件，同时也证明了网络可控当且仅当它的每个连通分支可控。

Ji等[16-17]则是通过Laplace矩阵的特征向量研究无向网络的可控性，其中文献[16]给出了无向网络可控的充要条件，文献[17]则给出DCD、TCD等破坏网络可控性的顶点集图特征。文献[18-19]证明了高阶时不变系统的可控性等价于一阶(线性)时不变系统的可控性，通过Laplace矩阵的特征向量给出了无向网络可控的充要条件，同时指出了使网络可控的2个方法：增加领航顶点和修改网络权值。

这些研究关注重点在于从理论上给出领航集的代数特征或图论特征，所举算例规模较小。对于仅具有单特征值的无向网络系统，可以从代数角度给出领航集。理论研究表明，当网络中个体数量趋向无穷时，网络Laplace矩阵仅具有单特征值的概率趋向1。但是，对于无人机集群系统，个体数量大多在几十至几百之间，这类系统的Laplace矩阵具有多重特征值的可能性很大。现有的研究很少涉及求解这种规模无向网络领航集的算法。

复杂网络的相关研究值得借鉴。Hamdan等[20-21]采用启发式算法求复杂网络的领航集，之所以采用启发式算法求领航集是因为这一问题是NP难问题。在无向复杂网络的可控性研究中，多采用携带更多信息的可控性Gramian矩阵[22-23]。Katherine等[24]研究了平均可控性以及可控性与鲁棒性的关系，并给出使树图可控的领航集选取方法。2020年，基于顶点分类文献[25]提出大规模动态系统的最小领航顶点选取问题的算法。

本文针对具有几十个个体的无向领航跟随模式无人机集群领航顶点选取问题，研究领航顶点的图特征，解决具有何种图特征的顶点必须成为领航顶点，以及如何求出最小领航集这2个问题；给出求领航集的算法并用数值仿真实验验证算法的有效性，分析无人机集群领航集的数值特征。

1 基本理论

1.1 无人机集群通信网络的图论模型

无人机个体间的通信关系可用图表示。设图G=(V,E) ，其中顶点集V={v1,v2,···,vn}，vi表示第i个无人机个体，边vi,vj∈E当且仅当第i个无人机与第j个无人机间可通信，G称为通信网络拓扑结构图。若无人机个体间的通信关系是单向的，则G为有向图；若无人机个体间是双向通信的，则G为无向网络。

对于领航跟随模式的无人机集群，接收外界输入控制信号的个体称为领航顶点，其余顶点则称为跟随顶点。本文考虑有n个无人机个体的线性时不变系统，个体的动力学方程描述为

式中：xi为第i个无人机的状态信息；ui为外界输入控制信息。如图1，由Kalman秩条件[5]知，取v1或v3作为领航顶点，则系统可控；若取v2作为领航顶点，则系统不可控。

图1 领航集的选取对系统可控性影响Fig.1 Influence of leader’s selection on the controllability of the systems

1.2 预备理论

研究结果表明，无向网络可控性与Laplace矩阵L的特征值和特征向量有关。

性质1[16-18]设F为跟随集，则无向网络线性时不变系统式(1)可控，当且仅当L与LF→F没有共同特征值。

性质2给出领航集的代数特征。值得注意的是，性质2中的特征向量y是Laplace矩阵L的任意一个特征向量，因此，当L有多重特征值时，并不能仅通过考察它的所有线性无关的特征向量得到领航集，而应进一步验证全部具有零分量的特征向量。从数值计算角度而言，这种验证计算量大，难以实现。本文将从领航顶点的图特征出发，给出确保系统可控的领航集求解算法。

2 关键集和完美关键集

由性质2可知，对于非空顶点集T，若通信网络拓扑结构图G的Laplace矩阵L有一个特征向量y使得yT=0 ， 则该顶点集T不能作为领航集，也就是说，此时为使无人机集群可控，必须将T的补集中某些顶点加入到领航集。基于此，本文提出关键集的概念。

2.1 关键集

定义1 关键集。设非空顶点集S⊂V，L为通信网络拓扑结构图G的Laplace矩阵，若存在L的一个特征向量y使得yS¯=0，则称顶点集S为关键集(critical set, CS)。若 |S|=k，则称S为k关键集(kcritical set)。

定义2 完美关键集。设S为关键集，若存在L的一个特征向量y使得yv≠0(∀v∈S)，则称S为完美关键集(perfect critical set, PCS)。若 |S|=k，则称S为k完美关键集(kperfect critical set)。

定义3 最小完美关键集。设S为关键集，若它的任何真子集都不再是关键集，则称S为最小完美关键集(minimal perfect critical set, MPCS)。若 |S|=k，则称S为k最小完美关键集(kminimal perfect critical set)。

由k关键集的定义可知，k为正整数且k

定理1n阶连通无向网络不存在1关键集。

若S为1关键集，不防设S={v1}， 则由ys¯=0 及式(2)可知yS=0， 于是y=0 与y为特征向量矛盾。

由性质2及定理1知推论1、2成立。

推论1 设G为n阶连通无向网络，S⊂V且|S|=n−1，若取S为领航集，则系统可控。

推论2 设n阶无向网络G为非连通图，则G有1关键集的充要条件是G中有孤立顶点。

由定理1可知，对于n阶连通无向网络的k关键集，必有 2 ≤k≤n−1。

定理2 设顶点集S⊂V且 |S|≥2 ，若 ∀v∈S¯，v要么与S中所有顶点都相邻，要么与S中所有顶点都不相邻，则S为关键集。

情况1 若矩阵LS→S−mI|S|只有零特征值。

此 时 必 有LS→S−mI|S|=0|S|×|S|。 注 意 到 ∀v∈S¯ ，若v与S中顶点都相邻，则其在矩阵LS¯→S中对应的行向量Lv→S分量全为1；若v与S中顶点都不相邻，则其对应的行向量Lv→S分量全为0。 因此，构造n阶列向量y=[1−|S|1···10···0]，则易见y为Laplace矩阵L的特征向量。

情况2 若矩阵LS→S−mI|S|有非零特征值。

此 时 取LS→S−mI|S|的 特 征 值 λ′≠0，令λ=λ′+m，则λ 为LS→S的特征值且λ ≠m。

设yS为矩阵LS→S相应于特征值 λ (λ≠m) 的特征向量，构造n阶列向量y=[yS0]，则有

由LS→SyS=λyS知

由定理2可知图1中的顶点集 {v1,v3} 是关键集，所以v2不能作为领航顶点。

在一定条件下，运用定理2判断一个顶点子集S是否为关键集时，可以不考虑S¯ 中那些与S中顶点都相邻或者都不相邻的顶点。

设特征向量y是与k完美关键集S对应的特征向量，即yS¯=0 且y的非零分量恰有k个，于是有引理1。设 [ {v},S] 表示一个端点为v另一个端点属于S的边集。

引理1 设S为k完美关键顶点集，则∀v∈S¯ ，有 |[ {v},S]|≠1 且 |[ {v},S]|≠k−1。

证明 设S={v1,v2,···,vk} 为k完美关键集，存在y=[y1y2···yk0 ···0]T为Laplace矩阵L的特征向量。由S为k完美关键集知yi≠0(i=1,2,···,k)。

再由式(2)知yk=0, 矛盾。

2.2 2关键集和3关键集的图特性

由定理1知，2关键集是2完美关键集，也是2最小完美关键集。

证明 由定理2知充分性成立。只须证明必要性。

证明 由定理2知充分性成立。只须证明必要性。

由定理3可知，2关键集实际上就是文献[26]给出的twins顶点对，由此可见，2关键集是twins顶点对的推广。但与文献[17]中所提出的DCD顶点对不同，DCD顶点对考虑的是在跟随集中的2个顶点，而2关键集考虑的对象则是所有顶点。

另外，定理3和定理4表明顶点集S能否成为2关键集或3关键集与S中的顶点是否相邻无关。但是，当S中顶点数更多时，该结论不一定成立。如图2中4个深色顶点构成的顶点集S，当S中顶点的相邻关系如图(a)时，它是4关键集；但当S中顶点的相邻关系如图(b)时，它不再是4关键集。

图2 4关键集与G[S]的关系Fig.2 Relationship between four critical set an G[S]

2.3 独立关键集的图特征

若S={v1,v2,···,vk} 为独立集且为k完美关键集，则Laplace矩阵L有一个特征向量：

y=[y1y2···yk0 ··· 0]T

yi≠0,i=1,2,···,k

由S为独立集知 ∀vi∈S有：

即dG(v1)=dG(v2)=···=dG(vk)=λ。亦即当S为独立集时，完美关键集S中顶点度均相等。基于此，定理5给出了独立集成为关键集的一个充分条件。

证明 不防设S={v1,v2,···,vk} 且S中所有顶点在图G中的度均为d。若简化图GS为空图，则由定理2知结论成立，下设GS非空图。

取y=[x1x2···xk0 ···0]T， λ=d，则有

综上可知Ly=λy， 即向量y为Laplace矩阵的特征向量，由于yS¯=0，故由定义1知S为关键集。

图3 简化图及其关键集Fig.3 Simplification of graph G and its CS

3 最小领航集

基于关键集的概念，本节讨论如何求出无人机集群最小领航集的算法。

3.1 算法理论基础

由性质2及关键集的定义知定理6成立。

定理6 设F为跟随集，F为领航集，则双向通信无人机集群线性时不变系统(见式(1))可控当且仅当F中不包含关键集。

证明 由性质2知系统(见式(1))可控当且仅当yF¯≠0 ，其中y是任意一个特征向量。由定义1知，yF¯≠0 当且仅当F不是关键集且不包含任何关键集。

设S1,S2,···,Sm是无人机集群通信网络拓扑结构图的所有关键集，构造二部图H=(U,V;E)，顶点集U={u1,u2,···,um} ，其中ui与Si对应；V=V(G)={v1,v2,···,vn}为无人机集群通信网络拓扑结构图G的顶点集，viuj∈E(H) 当且仅当vi∈Sj。若viuj∈E(H) 则称顶点vi覆盖关键集Sj。由定理6可知求最小领航集等价于求覆盖所有关键集的最小顶点集T(T⊆V)。

3.2 最小领航集算法

基于定理6，本节给出求领航集的算法(critical set algorithm, CSA)：

1)求出无人机集群通信网络拓扑结构图G的所有k关键集Si(i=1,2,···,m)；

2)构造二部图H=(U,V;E)；

3)求最小顶点集T(T⊆V) 使T中的顶点覆盖所有关键集，则T即为最小领航集。

例如，图4中G来自文献[15]，由定理3知它有2关键集S1={v1,v6} 、S2={v2,v3} 、S3={v4,v5}、S4={v7,v8}；由定理4知该图没有3关键集；由于2个悬挂点v4、v5都与v9相邻，故由引理1知v9不属于任何完美关键集；同理，考虑v1和v6这2个顶点可知v10也不属于任何关键集。从而，容易知道图4中不存在5完美关键集；对于4完美关键集只能是上述4个Si(i=1,2,3,4) 中每个集合各取一个构成的集合，容易验证它们都不是关键集。即上述4个Si(i=1,2,3,4) 是该网络的全部最小完美关键集。

图4 图G及其关键集Fig.4 Graph G it’s critical set

于是可构造二部图H=(U,V;E) 如图5所示。从该二部图中可以看出每个顶点vi只能覆盖一个uj，于是从每个uj的相邻顶点任取一个组成的集合就是图G的最小领航集，比如可取T={v1,v2,v4,v7}为最小领航集。

图5 二部图Fig.5 Bipartite graph

本算例说明如何运用关键集求出无人机集群通信网络拓扑结构图的最小领航集。

3.3 CSA算法复杂性分析

一般地，CSA算法的1)和3)都不是多项式时间的算法。但是，基于本文给出的定理，求出相应特殊的关键集及领航集则是多项式时间算法，具体的算法流程如图6所示。

图6 CSA算法流程Fig.6 Flow chart of CSA

由定理3知，在CSA算法流程图中找出所有2关键集的算法复杂性为O(n3)。由定理4知，找所有3关键集的算法复杂性为O(n4)，因此，图6所示的CSA算法复杂性为O(n4)。

3.4 数值实验及分析

在实验中，设无人机集群的初始位置随机，经过一段时间后形成稳定的通信网络拓扑结构图，并在后续保持通信关系不变。在具体的数值实验中，程序将在 1 0×10 平面区域内随机生成n个顶点，代表n个无人机个体的初始位置，设无人机个体的通信半径为参数d。图7是实验中随机生成的3个通信网络拓扑结构图G。

图7 无人机集群的通信网络拓扑结构Fig.7 Topology of communication network for UAVs

其中，图7(a)是通信半径为5时随机生成的具有10个无人机个体的通信网络拓扑结构图，CSA算法求出的领航集为 { 1,2,3}；图7(b)是通信半径为7时随机生成的具有10个无人机个体的通信网络拓扑结构图，CSA算法求出的领航集为{1,2,3,4,5}；图7(c)是70个无人机个体通信半径为1.5时生成的通信网络拓扑结构图，CSA算法求出的领航集为 { 1,2,···,8}。

实验1 代数方法、图论方法及CSA算法的对比实验。

在代数方法中，首先对于单重特征值，先求它的1个特征向量，若该特征向量的非零分量对应的顶点集不是顶点集V，由定义1知，这些非零分量对应的顶点集是1个关键集，在该关键集中任取1个顶点放入领航顶点集；其次，对于多重特征值，设它的重数为m(m≥2)，由于这种特征值对应的特征向量可能具有不同的非零分量集合，因此，这种特征值可能对应多个不同的MPCS，程序对具有相同非零分量的特征向量进行识别并重新认定该特征值的重数m1(m1≤m)。在特征向量的非零分量中任取m1个对应顶点放入领航顶点集。

在图论方法中，程序基于本文给出的定理2～5，求出2关键集、3关键集和孤立关键集等一些特殊的关键集。然后，在每个关键集中任取一个顶点放入领航顶点集。

CSA算法则是将代数方法和图论方法相结合求关键集。对于单重特征值，程序用代数方法求它的关键集；对于多重特征值，则用图论方法求出2关键集、3关键集。实验结果如图8所示。

从图8中可以看出，通过引入图论理论求关键集，使得求解效率得到大幅度提高，特别是当通信半径d=1 时，单纯的代数方法或图论方法都难以搜索到领航集，但将两者相结合的CSA算法仍然使得求解效率在80%以上。实验表明，代数方法能找到一部分领航顶点，而图论方法则可以找出另一部分领航顶点，CSA正是借助关键集概念，将代数方法和图论方法统一用于构建最小领航顶点集。

图8 对比实验Fig.8 Comparison of experimental results

实验2 CSA算法的求解效率与无人机个体通信半径间关系。

在本实验中，针对不同的无人机个体数目，测试CSA算法在不同通信半径条件下的求解效率，实验结果如图9所示。

图9 CSA算法求解效率与通信半径的关系Fig.9 Relationship between the efficiency of CSA and communication radius of UAV

从图9中可以看出，尽管CSA算法在求解过程有一定程度的抖动，但当顶点个数小于30时，求解效率在95%上。一个有趣的现象是，当顶点个数大于30时，若其通信半径介于3～9，则CSA算法几乎100%可以找到领航集；若通信半径小于3或大于9，则CSA算法都出现了不同程度的抖动，特别是当通信半径介于0.5～3时，算法求解效率较差。出现这一现象的原因在于，此时图中单重特征值减少而多重特征值增加，这使得同一特征值对应的关键集增加，而基于本文给出的定理2～5，CSA算法只求出2关键集、3关键集和孤立关键集等一些特殊的关键集，从而使得算法难以找到领航集。例如，见图10，该无向网络的特征值中，除单重特征值外，还有1个3重特征值、1个4重特征值和1个5重特征值，CSA算法难以找到它的领航集。这说明，当顶点个数多且通信半径较小时，图中的关键集情况较复杂，需要进一步从理论上研究k关键集的图特征。

图10 复杂特征值情况的网络结构Fig.10 Description of networks with multiple eigenvalues

实验3 领航顶点个数与边数关系。

随着无人机个体和边数的变化，领航顶点的个数也会相应地变化，因此，本实验不考虑领航顶点个数的绝对值，而是考虑“领航顶点个数/无人机个体数量n”与“边数/总边数(即完全图中的边数n(n−1)/2)”间的关系。

实验结果如图11所示。从图11中可以看出，随着边数占比趋于1，领航顶点占比趋于(n−1)/n；随着边数占比趋于0，领航顶点占比趋于1；特别是，领航顶点占比达最小。从图11中可以看出，当无人机个体数量为10时，领航顶点占比达最小的情况出现在边数占比为0.6～0.7；当无人机个体的数量为30时，领航顶点占比达最小的情况出现在边数占比为 0.4～0.6；当无人机个体的数量为50(70)时，领航顶点占比达最小的情况出现在边数占比为 0 .1～0.3。也就是说，从整体上看，所有“领航顶点占比与边数占比”曲线都是下凸曲线，无人机个体数越多，曲线越向下凸且极小值点越向“左”偏。这一现象说明，若用较少个数的无人机个体控制整个无人机集群，则通信网络拓扑结构图中的边数应取值于适当范围，实验3从统计意义上给出了这个范围。

图11 领航顶点个数与边数的关系Fig.11 Relationship between the number of leaders and edges

4 结束语

本文以几十架无人机构成的无人机集群为应用背景，利用Laplace矩阵的特征向量提出关键集概念，指出领航集所必须具备的图特征，即领航集需覆盖所有关键集。给出了2关键集和3关键集的图特征，从图论角度给出独立集成为关键集的一个充分条件。数值实验表明，基于关键集，CSA算法在大多数情况下能以90%以上的概率搜索到领航集。

如何刻画k(k≥4) 关键集的图特征是需进一步研究的内容。这是十分难以解决的问题，比如由图2知4关键集与这4个顶点的相邻关系有关，全体4阶互不同构的简单图有11个，其中边数为0、1、2、3、4、5、6的图的个数分别为1、1、2、3、2、1、1。而全体5阶互不同构的简单图有34个。随着k的增加，k(k≥4) 关键集的情况异常复杂。但是，这又是一个十分有意义的问题。比如，从数值实验可以看出，仅依据本文给出的定理2～5求出有限特殊的关键集，CSA算法就能在大多数情况下以90%以上的概率搜索到领航集。

另外，从图论角度给出领航集的充要条件，最小领航顶点数的上、下界等也都是值得进一步研究的问题。