﻿ 双向通信无人机集群领航顶点选取方法
«上一篇
 文章快速检索 高级检索

 智能系统学报  2021, Vol. 16 Issue (3): 484-492  DOI: 10.11992/tis.202006010 0

### 引用本文

DAI Li. Leaders’ selection for UAV swarm with two-way communication[J]. CAAI Transactions on Intelligent Systems, 2021, 16(3): 484-492. DOI: 10.11992/tis.202006010.

### 文章历史

Leaders’ selection for UAV swarm with two-way communication
DAI Li
College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, China
Abstract: Leaders’ selection plays a vital role in the controllability of multiagent systems, such as the leader-follower framework of UAVs. Using the UAV swarm with dozens of individuals as the research object and aiming at the problem of leaders’ selection, this paper proposes a critical set based on the eigenvector of a Laplace matrix. Theoretically, the graphical characteristics of two, three, and isolated critical sets are proved. Based on this, an algorithm named CSA for finding the minimum critical set of undirected communication networks is presented. Finally, numerical simulation is used to obtain the numerical features of the minimum leaders of UAVs of various sizes and communication radii.
Key words: leader’s selection    leader-follower framework    undirected network    Laplacian matrix    controllability    critical vertex set    minimum leader set    algorithm

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

1 基本理论 1.1 无人机集群通信网络的图论模型

 ${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)

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$ 对应列所组成的子矩阵。

2 关键集和完美关键集

2.1 关键集

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

 ${{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}}$ 为特征向量矛盾。

${{{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}$

$\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.2 2关键集和3关键集的图特性

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

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

 Download: 图 2 4关键集与G[S]的关系 Fig. 2 Relationship between four critical set an G[S]
2.3 独立关键集的图特征

$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给出了独立集成为关键集的一个充分条件。

$\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}}}$

 ${{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$

${{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$ ，若vS中顶点都相邻，则由 $\displaystyle\sum\limits_{i = 1}^k {{x_i}} = 0$ ${{{L}}_{\{ v\} \to V}}{{y}} = {{0}}$ ；若vS中顶点都不相邻，则有 ${{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$

 Download: 图 3 简化图及其关键集 Fig. 3 Simplification of graph G and its CS
3 最小领航集

3.1 算法理论基础

${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 最小领航集算法

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

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

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

3.3 CSA算法复杂性分析

3.4 数值实验及分析

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

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

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

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