多智能体系统控制技术是人工智能时代的研究热点之一^[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 = \{ {v_1},{v_2}, \cdots ,{v_n}\} $ ， ${v_i}$ 表示第i个无人机个体，边 ${v_i},{v_j} \in E$ 当且仅当第i个无人机与第j个无人机间可通信，G称为通信网络拓扑结构图。若无人机个体间的通信关系是单向的，则G为有向图；若无人机个体间是双向通信的，则G为无向网络。

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

$ {x_i}^\prime = \left\{ \begin{split} &\displaystyle\sum\limits_{{v_i},{v_j} \in E(G)} {({x_j} - {x_i})} ,\quad{x_i}{\text{为跟随顶点}}\\ &\displaystyle\sum\limits_{{v_i},{v_j} \in E(G)} {({x_j} - {x_i})} + {u_i},\quad{x_i}{\text{为领航顶点}} \end{split} \right. $

(1)

式中： ${x_i}$ 为第 $i$ 个无人机的状态信息； ${u_i}$ 为外界输入控制信息。如图1，由Kalman秩条件^[5]知，取 ${v_1}$ 或 ${v_3}$ 作为领航顶点，则系统可控；若取 ${v_2}$ 作为领航顶点，则系统不可控。

1.2 预备理论

设 ${{x}} = {[{x_1}\; \; {x_2}\; \; \cdots \; \; {x_n}]^{\rm{T}}}$ ，则式(1)为 ${{x'}} = - {{Lx}}$ ，其中 ${{L }}= {{D}} - {{A}}$ 为通信网络拓扑结构图 $G$ 的Laplace矩阵， ${{D}}$ 为度对角矩阵， ${{A}}$ 为邻接矩阵。不防设 $ F=\{{v}_{1},{v}_{2},\cdots ,{v}_{m}\} $ 为跟随集， $F$ 的补集 $\bar F = \{ {v_{m + 1}}, $ $ {v_{m + 2}}, \cdots ,{v_n}\}$ 为领航集。记 ${{{L}}_{S \to T}}$ 为 ${{L}}$ 中由顶点集 $S$ 对应行与顶点集 $T$ 对应列所组成的子矩阵。

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

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

性质2　设 $ \overline{F} $ 为领航集， ${{y}}$ 为Laplace矩阵 ${{L}}$ 的任意特征向量，则无向网络线性时不变系统式(1)可控当且仅当 ${{{y}}_{\bar F}} \ne {{0}}$ ，即 ${{y}}$ 中领航顶点对应的分量不全为0，其中 ${{{y}}_{\bar F}}$ 表示 ${{y}}$ 中对应于领航集 $\overline{ F}$ 分量构成的向量^{[12, 17]}。

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

2 关键集和完美关键集

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

2.1 关键集

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

定义2　完美关键集。设S为关键集，若存在 ${{L}}$ 的一个特征向量 ${{y}}$ 使得 ${{{y}}_v} \ne {{0}}(\forall v \in S)$ ，则称S为完美关键集(perfect critical set, PCS)。若 $|S| = k$ ，则称S为k完美关键集(k perfect critical set)。

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

若通信网络拓扑结构图为非连通图，则考虑它的连通分支，故不失一般性，本节讨论的通信网络拓扑结构图均为连通图。连通图的Laplace矩阵的零特征值是单重特征值，且其特征向量为 ${\bf{1}}_n^{\rm{T}}$ , ( ${{1}}_n^{}$ 表示分量均为1的n维列向量)，该特征向量不能导出关键集，因此，若无特别声明，本节中出现的特征值 $\lambda $ 都不为0。

由k关键集的定义可知，k为正整数且 $k < n$ ，定理1表明 $k \geqslant 2$ 。

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

证明　设 ${{y}}$ 为图G的Laplace矩阵 ${{L}}$ 的一个特征向量，设其相应的特征值为 $\lambda $ ，则有 ${{Ly}} = \lambda {{y}}$ 。于是有 ${{1}}_n^{\rm{T}}{{Ly}} = \lambda {{1}}_n^{\rm{T}}{{y}}$ 。由 ${{L}} = {{D}} - {{A}}$ 知 ${{1}}_n^{\rm{T}}{{L}} = {{{0}}_{1 \times n}}$ ，从而：

$ {{1}}_n^{\rm{T}}{{y}} = \sum\limits_{i = 1}^n {{y_i}} = 0 $

(2)

若S为1关键集，不防设 $S = \{ {v_1}\} $ ，则由 ${{{y}}_{\bar s}} = {{0}}$ 及式(2)可知 ${{{y}}_S} = {{0}}$ ，于是 ${{y}} = {{0}}$ 与 ${{y}}$ 为特征向量矛盾。

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

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

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

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

定理2　设顶点集 $S \subset V$ 且 $|S| \geqslant 2$ ，若 $\forall v \in \bar S$ ，v要么与S中所有顶点都相邻，要么与S中所有顶点都不相邻，则S为关键集。

证明　设 $\bar S$ 中有m个顶点与S中所有顶点都相邻。首先断言：矩阵 ${{{L}}_{S \to S}}$ 有特征值 $\lambda (\lambda \ne m)$ 。事实上，由于 $\bar S$ 中有m个顶点与S中所有顶点都相邻且其余顶点都不与S中顶点相邻，所以 ${{{L}}_{S \to S}} - m{{{I}}_{|S|}}$ 为顶点导出子图 $G[S]$ 的Laplace矩阵(其中 ${{{I}}_{|S|}}$ 为 $|S|$ 阶单位矩阵)，故 ${{{L}}_{S \to S}} - m{{{I}}_{|S|}}$ 有特征值0。

情况1　若矩阵 ${{{L}}_{S \to S}} - m{{{I}}_{|S|}}$ 只有零特征值。

此时必有 ${{{L}}_{S \to S}} - m{{{I}}_{|S|}} = {{{0}}_{|S| \times |S|}}$ 。注意到 $\forall v \in \bar S$ ，若v与S中顶点都相邻，则其在矩阵 ${{{L}}_{\bar S \to S}}$ 中对应的行向量 ${{{L}}_{v \to S}}$ 分量全为1；若v与S中顶点都不相邻，则其对应的行向量 ${{{L}}_{v \to S}}$ 分量全为0。因此，构造n阶列向量 ${{y}} = \left[ {1 - |S|\;1\; \cdots \;1\;0\; \cdots \;0} \right] $ ，则易见 ${{y}}$ 为Laplace矩阵 ${{L}}$ 的特征向量。

情况2　若矩阵 ${{{L}}_{S \to S}} - m{{{I}}_{|S|}}$ 有非零特征值。

此时取 ${{{L}}_{S \to S}} - m{{{I}}_{|S|}}$ 的特征值 $\lambda ' \ne 0$ ，令 $\lambda = \lambda ' + m$ ，则 $\lambda $ 为 ${{{L}}_{S \to S}}$ 的特征值且 $\lambda \ne m$ 。

设 ${{{y}}_S}$ 为矩阵 ${{{L}}_{S \to S}}$ 相应于特征值 $\lambda (\lambda \ne m)$ 的特征向量，构造n阶列向量 ${{y}} = [{{{y}}_S}\; \; \; {{0}}]$ ，则有

${{Ly}} = \left[ {\begin{array}{*{20}{c}} {{{{L}}_{S \to S}}}&{{{{L}}_{S \to \bar S}}} \\ {{{{L}}_{\bar S \to S}}}&{{{{L}}_{\bar S \to \bar S}}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{{{y}}_S}} \\ {{0}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {\lambda {{{y}}_S}} \\ {{{{L}}_{\bar S \to S}}{{{y}}_S}} \end{array}} \right]$

(3)

由 ${{{L}}_{S \to S}}{{{y}}_S} = \lambda {{{y}}_S}$ 知

$ {{1}}_{|S|}^{\rm{T}}{{{L}}_{S \to S}}{{{y}}_S} = m{{1}}_{|S|}^{\rm{T}}{{{y}}_S} = \lambda {{1}}_{|S|}^{\rm{T}}{{{y}}_S} $

再由 $\lambda \ne m$ 知 ${{1}}_{|S|}^{\rm{T}}{{{y}}_S} = {{0}}$ ，从而 ${{{L}}_{\bar S \to S}}{{{y}}_S} = {{0}}$ 。于是由式(3)知 ${{Ly}} = \lambda {{y}}$ ，即向量 ${{y}}$ 为 ${{L}}$ 的一个特征向量。

由定理2可知图1中的顶点集 $\{ {v_1},{v_3}\} $ 是关键集，所以 ${v_2}$ 不能作为领航顶点。

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

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

引理1　设S为k完美关键顶点集，则 $\forall v \in \bar S$ ，有 $|[\{ v\} ,S]| \ne 1$ 且 $|[\{ v\} ,S]| \ne k - 1$ 。

证明　设 $S = \{ {v_1},{v_2}, \cdots ,{v_k}\} $ 为k完美关键集，存在 ${{y}} = {[{y_1}\; \; {y_2}\; \; \cdots \; \; {y_k}\; \; 0\; \; \; \cdots \; \; 0]^{\rm{T}}}$ 为Laplace矩阵 ${{L}}$ 的特征向量。由S为k完美关键集知 ${y_i} \ne 0(i = 1, $ $ 2, \cdots ,k)$ 。

$\forall v \in \bar S$ ，若 $|[\{ v\} ,S]| = 1$ ，不妨设 $v{v_1} \in E$ ，则 ${{{L}}_{\{ v\} \to V}}{{y}} = $ $ {y_1} = 0,$ 矛盾。

$\forall v \in \bar S$ ，若 $|[\{ v\} ,S]| = k - 1$ ，不防设v与 ${v_1},{v_2}, \cdots , $ $ {v_{k - 1}}$ 都相邻，则

${{{L}}_{\{ v\} \to V}}{{y}} = \sum\limits_{i = 1}^{k - 1} {{y_i}} $

再由式(2)知 ${y_k} = 0,$ 矛盾。

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

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

定理3　设 $S \subset V$ 且 $|S| = 2$ ，则S为2关键集当且仅当对 $\forall v\in \bar{S}$ ，v要么与S中所有顶点都相邻，要么与S中所有顶点都不相邻。

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

设S为2关键集，由引理1知 $|[\{ v\} ,S]| \ne 1(\forall v \in \bar S)$ ，因此，v $|[\{ v\} ,S]| = 2$ 或 $|[\{ v\} ,S]| = 0$ ，即要么v与S中所有顶点都相邻，要么v与S中所有顶点都不相邻。

定理4　设 $ S\subset V $ 且 $|S| = 3$ ，则S为3关键集当且仅当 $\forall v \in \bar S$ ，v要么与S中所有顶点都相邻，要么与S中所有顶点都不相邻。

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

设S为3关键集，由引理1知 $|[\{ v\} ,S]| \ne 1$ 且 $|[\{ v\} ,S]| \ne 2(\forall v \in \bar S)$ ，因此，要么 $|[\{ v\} ,S]| = 3$ ，要么 $|[\{ v\} ,S]| = 0$ ，即要么v与S中所有顶点都相邻，要么v与S中所有顶点都不相邻。

由定理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.3 独立关键集的图特征

对于顶点集S，按照定理2，删除 $\bar S$ 中与S顶点都相邻或都不相邻的顶点，同时也删除顶点导出子图 $G\left[\bar{S}\right]$ 中所有边，称这样得到的图为关于顶点集S的简化图，记作 $ {G}_{S} $ 。当S是独立集时， ${G_S}$ 是二部图。记 $ {\bar{S}}_{{G}_{S}} $ 为S在简化图 $ {G}_{S} $ 中的补集。

若 $ S=\{{v}_{1},{v}_{2},\cdots ,{v}_{k}\} $ 为独立集且为k完美关键集，则Laplace矩阵 ${{L}}$ 有一个特征向量：

${{y}} = {[{y_1}\; \; \; {y_2}\; \; \cdots \; \; {y_k}\; \; 0\; \; \; \cdots \; \; \; \; 0]^{\rm{T}}}$

${y_i} \ne 0,\quad i = 1,2, \cdots ,k$

由S为独立集知 $\forall {v_i} \in S$ 有：

${L_{\{ {v_i}\} \to V}}{{y}} = {d_G}({v_i}){y_i} = \lambda {y_i},\quad i = 1,2, \cdots ,k$

即 ${d_G}({v_1}) = {d_G}({v_2}) = \cdots = {d_G}({v_k}) = \lambda $ 。亦即当S为独立集时，完美关键集S中顶点度均相等。基于此，定理5给出了独立集成为关键集的一个充分条件。

定理5　设S为独立集， ${G_S}$ 为关于顶点集S的简化图。若S中所有顶点在图G中的度相等，且 ${\bar S_{{G_S}}}$ 中所有顶点在 ${G_S}$ 中的度均为偶数，则S为关键集。

证明　不防设 $S = \{ {v_1},{v_2}, \cdots ,{v_k}\} $ 且S中所有顶点在图G中的度均为d。若简化图 $ {G}_{S} $ 为空图，则由定理2知结论成立，下设 ${G_S}$ 非空图。

$\forall v \in {\bar S_{{G_S}}}$ ，由v在图 ${G_S}$ 中的度为偶数知行向量 ${{{L}}_{v \to S}}$ 的所有分量求和为零(模2)，于是子矩阵 $ {\mathit{L}}_{{\overline{S}}_{{G}_{S}}\to S} $ 的列向量组线性相关，所以齐次线性方程组 ${{{L}}_{{{\bar S}_{{G_s}}} \to S}}{{x}} = {{0}}$ 有非零解 ${{x}} = {[{x_1}\; \; {x_2}\; \; \cdots \; \; \; {x_k}]^{\rm{T}}}$ 。

我们断言 $\displaystyle\sum\limits_{i = 1}^k {{x_i}} = 0$ ，事实上，由S中所有顶点在图G中的度均为d及简化图 ${G_S}$ 的构造过程可知顶点 ${v_i}(i = 1,2, \cdots ,k)$ 在简化图 ${G_S}$ 中的度也相等，设为 $d' \ne 0$ (因 ${G_S}$ 非空图)，于是

${{1}}_{1 \times |{{\bar S}_{{G_s}}}|}^{\rm{T}}{{{L}}_{{{\bar S}_{{G_S}}} \to S}}{{x}} = [d'\; \; d'\; \; \cdots \; \; \; d']{{x}} = d'\sum\limits_{i = 1}^k {{x_i}} = 0$

即有 $\displaystyle\sum\limits_{i = 1}^k {{x_i}} = 0$ 。

取 ${{y}} = {[{x_1}\; \; {x_2}\; \; \cdots \; \; {x_k}\; \; 0\; \; \; \cdots \; \; \; 0]^{\rm{T}}}$ ， $\lambda = d$ ，则有

${{{L}}_{S \to V}}{{y}} = [{{{L}}_{S \to S}}\; \; \; {{{L}}_{S \to \bar S}}]\left[ {\begin{array}{*{20}{c}} {{x}} \\ {{0}} \end{array}} \right] = {{{L}}_{S \to S}}{{x}} = $

${[d{x_1}\; \; \; d{x_2}\; \; \cdots \; \; \; d{x_k}]^{\rm{T}}} = \lambda {{x}}$

对 $\forall v \in \bar S$ ，若v与S中顶点都相邻，则由 $\displaystyle\sum\limits_{i = 1}^k {{x_i}} = 0$ 知 ${{{L}}_{\{ v\} \to V}}{{y}} = {{0}}$ ；若v与S中顶点都不相邻，则有 ${{L}}_{\left\{v\right\}\to V}{y}=0$ ；若 $\forall v \in {\bar S_{{G_s}}}$ ，则有

${{{L}}_{\{ v\} \to V}}{{y}} = [{{{L}}_{\{ v\} \to S}}\; \; \; \; {{{L}}_{\{ v\} \to \bar S}}]\left[ {\begin{array}{*{20}{c}} {{x}} \\ {{0}} \end{array}} \right] = {{{L}}_{\{ v\} \to S}}{{x}} = 0$

综上可知 ${{Ly}} = \lambda {{y}}$ ，即向量 $ {{y}} $ 为Laplace矩阵的特征向量，由于 ${{{y}}_{\bar S}} = {{0}}$ ，故由定义1知S为关键集。

例如，图3中的独立集S，考虑其简化图 ${G_S}$ ，在 $ {\bar{S}}_{{G}_{S}} $ 中的所有顶点的度都为偶数 $ 2 $ ，由定理5知S为4关键集。

3 最小领航集

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

3.1 算法理论基础

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

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

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

设 ${S_1},{S_2}, \cdots ,{S_m}$ 是无人机集群通信网络拓扑结构图的所有关键集，构造二部图 $H = (U,V;E)$ ，顶点集 $U = \{ {u_1},{u_2}, \cdots ,{u_m}\} $ ，其中 ${u_i}$ 与 ${S_i}$ 对应； $V = V(G) = \{ {v_1},{v_2}, \cdots ,{v_n}\} $ 为无人机集群通信网络拓扑结构图G的顶点集， ${v_i}{u_j} \in E(H)$ 当且仅当 ${v_i} \in {S_j}$ 。若 $ {v}_{i}{u}_{j}\in E\left(H\right) $ 则称顶点 ${v_i}$ 覆盖关键集 ${S_j}$ 。由定理6可知求最小领航集等价于求覆盖所有关键集的最小顶点集 $T(T \subseteq V)$ 。

3.2 最小领航集算法

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

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

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

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

例如，图4中G来自文献[15]，由定理3知它有2关键集 ${S_1} = \{ {v_1},{v_6}\} $ 、 ${S_2} = \{ {v_2},{v_3}\} $ 、 ${S}_{3}=\{{v}_{4},{v}_{5}\}$ 、 $ {S}_{4}=\{{v}_{7},{v}_{8}\} $ ；由定理4知该图没有3关键集；由于2个悬挂点 ${v_4}$ 、 ${v_5}$ 都与 ${v_9}$ 相邻，故由引理1知 ${v_9}$ 不属于任何完美关键集；同理，考虑 ${v_1}$ 和 ${v_6}$ 这2个顶点可知 ${v_{10}}$ 也不属于任何关键集。从而，容易知道图4中不存在5完美关键集；对于4完美关键集只能是上述4个 ${S_i}(i = 1,2,3,4)$ 中每个集合各取一个构成的集合，容易验证它们都不是关键集。即上述4个 ${S_i}(i = 1,2,3,4)$ 是该网络的全部最小完美关键集。

于是可构造二部图 $H = (U,V;E)$ 如图5所示。从该二部图中可以看出每个顶点 ${v_i}$ 只能覆盖一个 ${u_j}$ ，于是从每个 ${u_j}$ 的相邻顶点任取一个组成的集合就是图G的最小领航集，比如可取 $T = $ $ \{ v{_1},{v_2},{v_4},{v_7}\}$ 为最小领航集。

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

3.3 CSA算法复杂性分析

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

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

3.4 数值实验及分析

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

其中，图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,\cdots,8\} $ 。

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

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

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

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

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

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

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

从图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 $ 关键集的图特征。

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

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

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

4 结束语

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

如何刻画 $k(k \geqslant 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 \geqslant 4)$ 关键集的情况异常复杂。但是，这又是一个十分有意义的问题。比如，从数值实验可以看出，仅依据本文给出的定理2~5求出有限特殊的关键集，CSA算法就能在大多数情况下以90%以上的概率搜索到领航集。

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