第3期 戴丽：双向通信无人机集群领航顶点选取方法 ·485· ZFS与CM之间具有等价关系。基于NEP概念人 输入控制信号的个体称为领航顶点，其余顶点则 们给出了网络可控的必要条件，同时也证明了网 称为跟随顶点。本文考虑有n个无人机个体的线 络可控当且仅当它的每个连通分支可控。 性时不变系统，个体的动力学方程描述为 Ji等u6-1切则是通过Laplace矩阵的特征向量 (x:-x), x为跟随顶点 研究无向网络的可控性，其中文献[16)给出了无向 VI.VJEE(G) (1) 网络可控的充要条件，文献[I7]则给出DCD、TCD x为领航顶点 等破坏网络可控性的顶点集图特征。文献[18-19] （,eE(G 证明了高阶时不变系统的可控性等价于一阶（线 式中：：为第i个无人机的状态信息；山为外界输 性)时不变系统的可控性，通过Laplace矩阵的特 入控制信息。如图l,由Kalman秩条件知，取 征向量给出了无向网络可控的充要条件，同时指 或作为领航顶点，则系统可控：若取2作为领 出了使网络可控的2个方法：增加领航顶点和修 航顶点，则系统不可控。 改网络权值。 这些研究关注重点在于从理论上给出领航集 的代数特征或图论特征，所举算例规模较小。对于 仅具有单特征值的无向网络系统，可以从代数角 度给出领航集。理论研究表明，当网络中个体数 图1领航集的选取对系统可控性影响 量趋向无穷时，网络Laplace矩阵仅具有单特征值 Fig.1 Influence of leader's selection on the control- 的概率趋向1。但是，对于无人机集群系统，个体数 lability of the systems 量大多在几十至几百之间，这类系统的Laplace矩 1.2预备理论 阵具有多重特征值的可能性很大。现有的研究很 设x=[x…xJ,则式(I)为x=-Lx,其中 少涉及求解这种规模无向网络领航集的算法。 L=D-A为通信网络拓扑结构图G的Laplace 复杂网络的相关研究值得借鉴。Hamdan 矩阵，D为度对角矩阵，A为邻接矩阵。不防设 等如采用启发式算法求复杂网络的领航集，之所 F={,2,…,ym}为跟随集，F的补集F={ym+1 以采用启发式算法求领航集是因为这一问题是NP vm+2,…,vn}为领航集。记Ls-r为L中由顶点集S 难问题。在无向复杂网络的可控性研究中，多采 对应行与顶点集T对应列所组成的子矩阵。 用携带更多信息的可控性Gramian矩阵22)。 研究结果表明，无向网络可控性与Laplace矩 Katherine等P网研究了平均可控性以及可控性与鲁 阵L的特征值和特征向量有关。 棒性的关系，并给出使树图可控的领航集选取方 性质1618图设F为跟随集，则无向网络线性 法。2020年，基于顶点分类文献[25]提出大规模 时不变系统式(1)可控，当且仅当L与LF没有 动态系统的最小领航顶点选取问题的算法。 共同特征值。 本文针对具有几十个个体的无向领航跟随模 性质2设F为领航集，y为Laplace矩阵L 式无人机集群领航顶点选取问题，研究领航顶点 的任意特征向量，则无向网络线性时不变系统 的图特征，解决具有何种图特征的顶点必须成为领 式(1)可控当且仅当y≠0，即y中领航顶点对应 航顶点，以及如何求出最小领航集这2个问题；给 的分量不全为0，其中yF表示y中对应于领航集 出求领航集的算法并用数值仿真实验验证算法的 F分量构成的向量21刀。 有效性，分析无人机集群领航集的数值特征。 性质2给出领航集的代数特征。值得注意的 1 基本理论 是，性质2中的特征向量y是Laplace矩阵L的任 意一个特征向量，因此，当L有多重特征值时，并 1.1无人机集群通信网络的图论模型 不能仅通过考察它的所有线性无关的特征向量得 无人机个体间的通信关系可用图表示。设图 到领航集，而应进一步验证全部具有零分量的特 G=(VE),其中顶点集V={y,2,…,yn},y表示第 征向量。从数值计算角度而言，这种验证计算量 i个无人机个体，边，yeE当且仅当第i个无人 大，难以实现。本文将从领航顶，点的图特征出发， 机与第j个无人机间可通信，G称为通信网络拓 给出确保系统可控的领航集求解算法。 扑结构图。若无人机个体间的通信关系是单向 2关键集和完美关键集 的，则G为有向图；若无人机个体间是双向通信 的，则G为无向网络。 由性质2可知，对于非空顶点集T,若通信网 对于领航跟随模式的无人机集群，接收外界 络拓扑结构图G的Laplace矩阵L有一个特征向ZFS 与 CM 之间具有等价关系。基于 NEP 概念人 们给出了网络可控的必要条件，同时也证明了网 络可控当且仅当它的每个连通分支可控。 Ji 等 [16-17] 则是通过 Laplace 矩阵的特征向量 研究无向网络的可控性，其中文献 [16] 给出了无向 网络可控的充要条件，文献 [17] 则给出 DCD、TCD 等破坏网络可控性的顶点集图特征。文献 [18-19] 证明了高阶时不变系统的可控性等价于一阶 (线 性) 时不变系统的可控性，通过 Laplace 矩阵的特 征向量给出了无向网络可控的充要条件，同时指 出了使网络可控的 2 个方法：增加领航顶点和修 改网络权值。 这些研究关注重点在于从理论上给出领航集 的代数特征或图论特征，所举算例规模较小。对于 仅具有单特征值的无向网络系统，可以从代数角 度给出领航集。理论研究表明，当网络中个体数 量趋向无穷时，网络 Laplace 矩阵仅具有单特征值 的概率趋向 1。但是，对于无人机集群系统，个体数 量大多在几十至几百之间，这类系统的 Laplace 矩 阵具有多重特征值的可能性很大。现有的研究很 少涉及求解这种规模无向网络领航集的算法。 复杂网络的相关研究值得借鉴。Hamdan 等 [20-21] 采用启发式算法求复杂网络的领航集，之所 以采用启发式算法求领航集是因为这一问题是 NP 难问题。在无向复杂网络的可控性研究中，多采 用携带更多信息的可控性 Gramian 矩阵[ 2 2 - 2 3 ]。 Katherine 等 [24] 研究了平均可控性以及可控性与鲁 棒性的关系，并给出使树图可控的领航集选取方 法。2020 年，基于顶点分类文献 [25] 提出大规模 动态系统的最小领航顶点选取问题的算法。 本文针对具有几十个个体的无向领航跟随模 式无人机集群领航顶点选取问题，研究领航顶点 的图特征，解决具有何种图特征的顶点必须成为领 航顶点，以及如何求出最小领航集这 2 个问题；给 出求领航集的算法并用数值仿真实验验证算法的 有效性，分析无人机集群领航集的数值特征。 1 基本理论 1.1 无人机集群通信网络的图论模型 G = (V,E) V = {v1, v2,··· , vn} vi vi , vj ∈ E 无人机个体间的通信关系可用图表示。设图 ，其中顶点集 ， 表示第 i 个无人机个体，边 当且仅当第 i 个无人 机与第 j 个无人机间可通信，G 称为通信网络拓 扑结构图。若无人机个体间的通信关系是单向 的，则 G 为有向图；若无人机个体间是双向通信 的，则 G 为无向网络。 对于领航跟随模式的无人机集群，接收外界 输入控制信号的个体称为领航顶点，其余顶点则 称为跟随顶点。本文考虑有 n 个无人机个体的线 性时不变系统，个体的动力学方程描述为 xi ′ =    ∑ vi,vj∈E(G) (xj − xi), xi为跟随顶点 ∑ vi,vj∈E(G) (xj − xi)+ui , xi为领航顶点 (1) xi i ui v1 v3 v2 式中： 为第 个无人机的状态信息； 为外界输 入控制信息。如图 1，由 Kalman 秩条件[5] 知，取 或 作为领航顶点，则系统可控；若取 作为领 航顶点，则系统不可控。 v1 v2 v3 图 1 领航集的选取对系统可控性影响 Fig. 1 Influence of leader’s selection on the control￾lability of the systems 1.2 预备理论 x = [x1 x2 ··· xn] T x ′ = −Lx L = D− A G D A F = {v1, v2,··· , vm} F F¯ = {vm+1, vm+2,··· , vn} LS→T L S T 设 ，则式 (1) 为 ，其中 为通信网络拓扑结构图 的 Laplace 矩阵， 为度对角矩阵， 为邻接矩阵。不防设 为跟随集， 的补集 为领航集。记 为 中由顶点集 对应行与顶点集 对应列所组成的子矩阵。 L 研究结果表明，无向网络可控性与 Laplace 矩 阵 的特征值和特征向量有关。 L LF→F 性质 1 [16-18] 设 F 为跟随集，则无向网络线性 时不变系统式 (1) 可控，当且仅当 与 没有 共同特征值。 F y L yF¯ , 0 y yF¯ y F 性质 2 设 为领航集， 为 Laplace 矩阵 的任意特征向量，则无向网络线性时不变系统 式 (1) 可控当且仅当 ，即 中领航顶点对应 的分量不全为 0，其中 表示 中对应于领航集 分量构成的向量[12, 17]。 y L L 性质 2 给出领航集的代数特征。值得注意的 是，性质 2 中的特征向量 是 Laplace 矩阵 的任 意一个特征向量，因此，当 有多重特征值时，并 不能仅通过考察它的所有线性无关的特征向量得 到领航集，而应进一步验证全部具有零分量的特 征向量。从数值计算角度而言，这种验证计算量 大，难以实现。本文将从领航顶点的图特征出发， 给出确保系统可控的领航集求解算法。 2 关键集和完美关键集 T L 由性质 2 可知，对于非空顶点集 ，若通信网 络拓扑结构图 G 的 Laplace 矩阵 有一个特征向 第 3 期 戴丽：双向通信无人机集群领航顶点选取方法 ·485·