第3期 陈兴凯，等：基于0/-1特征值的网络可控性优化研究 ·591· 每一行最多仅有一个1元素，其他均为0元素，若 式(4)中的PBH判定矩阵[U-AB](以下简 第i行存在1元素则表示对i点有控制实施。 称PBH矩阵)可以写成以下模式： 针对式(2)的网络系统，常用的网络可控性判 -a12.-a1m b 定方法有2种：基本秩判据"和PBH秩判据。 -a21 b, 基本秩判据是根据式(3)进行可控性判据： rank[BABA2B.…A-B]=N (3) -an2 若网络系统满足式(3)，则网络系统是可控 不难看出，PBH矩阵在满秩的情况下，上式 的，否则不可控。 中的矩阵应该满足所有行向量线性不相关，而虚 PBH秩判据是根据式(4)进行可控性判据： 线右边的矩阵B可以消除虚线左边-A中行向 rank [AB]N.k=1,2,...,N (4) 量组的相关性，这就为求出矩阵B提供了实现方 式中：1k为邻接矩阵A所对应的所有特征值。若 法：首先计算出，-A,再将其进行初等列变换， 网络系统满足式(4)，则网络系统是可控的，否则 不改变行相关特性；根据行相关情况，通过设置 不可控。 最少的b,消除1-A的行相关性，使得PBH矩阵 从上述2种判定方法不难看出，网络可控性 中的所有行向量均不相关：最后将所有λ.对应的 的定性分析取决于邻接矩阵A和控制输入矩阵 b,设置情况进行整合，使得b,可以消除所有1对 B,即网络可控与否是由网络的拓扑结构和控制 应的PBH矩阵中行向量的相关性，即满足式 输人共同决定的。 (4)。此时，所对应的b,即组成最小控制输入对应 1.2定量分析 的矩阵B,最小控制输入的节点个数N:=rank(B)。 从网络可控性的定性分析不难看出，在某种 求出后，则可根据式(I)得到网络可控性 拓扑结构下，对网络所有节点实施控制（即M=W, 的度量指标n,完成定量分析。 则网络必定可以达到可控状态。然而，此时所实 20/-1特征值 施的控制不一定是最优的，因为对于任何一种网 络拓扑而言，最优的控制输人应该是使得网络达 从最小控制输入的求解可以看出，影响网络 到可控状态时，对网络中最少的节点实施控制。 可控性的直接因素是PBH矩阵中4I-A矩阵的 这种针对网络拓扑结构的最优控制即最小控制 行相关性。而行相关性不仅受到邻接矩阵A的 输入。最小控制输入的节点个数直接反映了在某 影响，还受到特征值的影响。虽然对于大部分 种拓扑结构下网络达到可控性的难易程度，即可 特征值而言，它们与行相关之间的联系并没有明 用于可控性的定量分析。因此，对网络可控性进 显的规律性，但0和-1这两个特征值却比较特 行定量分析的关键是求解出最小控制输入的节点 殊，它们不仅与行相关之间存在着一定联系，更 个数。 是极大地影响着网络可控性。 根据式(3)或式(4)的可控性判据，可以为最 2.1行相关类型 小控制输入的求解提供基本思路：针对邻接矩阵 对于-A矩阵的行相关性可以分为3类：零 A,求出满足式(3)或式(4)的最简矩阵B。最直 向量相关、重复相关和非重复相关。 接的方法是代入法，即针对网络中的所有节点， 1)零向量相关即存在全0行的行向量。以 将可能的控制输入由少至多进行遍历组合，生成 A,表示A的第x行，则零向量相关表现为 Ai1=Ai2=…=Am=0 所有可能情况下的输入矩阵B,由简至繁逐一代 例如A2=A=0,如下所示： 入式(3)或式(4)进行验证，一旦出现判定为可 [100001 控，则可将此时的矩阵B确定最小控制输入。然 00000 而，对于n个节点的网络而言，求出所有矩阵 00000 01000 B的计算复杂程度为CW+C%++CN=2W-1,显 00100 然，代入法在n较大的情况下是不适用的。如果 2)重复相关即存在完全相同的相关行向量。 不通过代入法求最小控制输入，式(3)由于涉及 以A表示A的第x行，则重复相关表现为 矩阵相乘，求出矩阵B是十分困难的。因此，较 Ai1=A2=…=Aim 为可行的代数方法是基于式(4)的PBH秩判据。 例如A=A=A3,如下所示：每一行最多仅有一个 1 元素，其他均为 0 元素，若 第 i 行存在 1 元素则表示对 i 点有控制实施。 针对式 (2) 的网络系统，常用的网络可控性判 定方法有 2 种：基本秩判据[1]和 PBH 秩判据[2]。 基本秩判据是根据式 (3) 进行可控性判据： rank[B AB A2B··· A N−1B] = N (3) 若网络系统满足式 (3)，则网络系统是可控 的，否则不可控。 PBH 秩判据是根据式 (4) 进行可控性判据： rank[λk I− AB] = N, k = 1,2,··· ,N (4) 式中：λk 为邻接矩阵 A 所对应的所有特征值。若 网络系统满足式 (4)，则网络系统是可控的，否则 不可控。 从上述 2 种判定方法不难看出，网络可控性 的定性分析取决于邻接矩阵 A 和控制输入矩阵 B，即网络可控与否是由网络的拓扑结构和控制 输入共同决定的。 1.2 定量分析 从网络可控性的定性分析不难看出，在某种 拓扑结构下，对网络所有节点实施控制 (即 M=N)， 则网络必定可以达到可控状态。然而，此时所实 施的控制不一定是最优的，因为对于任何一种网 络拓扑而言，最优的控制输入应该是使得网络达 到可控状态时，对网络中最少的节点实施控制。 这种针对网络拓扑结构的最优控制即最小控制 输入。最小控制输入的节点个数直接反映了在某 种拓扑结构下网络达到可控性的难易程度，即可 用于可控性的定量分析。因此，对网络可控性进 行定量分析的关键是求解出最小控制输入的节点 个数。 C 1 N C 2 N ··· C N N 2 N −1 根据式 (3) 或式 (4) 的可控性判据，可以为最 小控制输入的求解提供基本思路：针对邻接矩阵 A，求出满足式 (3) 或式 (4) 的最简矩阵 B。最直 接的方法是代入法，即针对网络中的所有节点， 将可能的控制输入由少至多进行遍历组合，生成 所有可能情况下的输入矩阵 B，由简至繁逐一代 入式 (3) 或式 (4) 进行验证，一旦出现判定为可 控，则可将此时的矩阵 B 确定最小控制输入。然 而，对于 n 个节点的网络而言，求出所有矩阵 B 的计算复杂程度为 + + + = ，显 然，代入法在 n 较大的情况下是不适用的。如果 不通过代入法求最小控制输入，式 (3) 由于涉及 矩阵相乘，求出矩阵 B 是十分困难的。因此，较 为可行的代数方法是基于式 (4) 的 PBH 秩判据。 式 (4) 中的 PBH 判定矩阵[λkI−A B](以下简 称 PBH 矩阵) 可以写成以下模式：   λk −a12 ··· −a1n −a21 λk ··· −a2n . . . . . . −an1 −an2 ··· λk b1 b2 . . . bn   不难看出，PBH 矩阵在满秩的情况下，上式 中的矩阵应该满足所有行向量线性不相关，而虚 线右边的矩阵 B 可以消除虚线左边 λkI−A 中行向 量组的相关性，这就为求出矩阵 B 提供了实现方 法：首先计算出 λkI−A，再将其进行初等列变换， 不改变行相关特性；根据行相关情况，通过设置 最少的 bi 消除 λkI−A 的行相关性，使得 PBH 矩阵 中的所有行向量均不相关；最后将所有 λk 对应的 bi 设置情况进行整合，使得 bi 可以消除所有 λk 对 应的 PBH 矩阵中行向量的相关性，即满足式 (4)。此时，所对应的 bi 即组成最小控制输入对应 的矩阵 B，最小控制输入的节点个数 Nd=rank(B)。 求出 Nd 后，则可根据式 (1) 得到网络可控性 的度量指标 nd，完成定量分析。 2 0/−1 特征值 从最小控制输入的求解可以看出，影响网络 可控性的直接因素是 PBH 矩阵中 λk I−A 矩阵的 行相关性。而行相关性不仅受到邻接矩阵 A 的 影响，还受到特征值 λk 的影响。虽然对于大部分 特征值而言，它们与行相关之间的联系并没有明 显的规律性，但 0 和−1 这两个特征值却比较特 殊，它们不仅与行相关之间存在着一定联系，更 是极大地影响着网络可控性。 2.1 行相关类型 对于 λkI-A 矩阵的行相关性可以分为 3 类：零 向量相关、重复相关和非重复相关。 1) 零向量相关即存在全 0 行的行向量。以 Ax 表示 A 的第 x 行，则零向量相关表现为 Ai1 = Ai2 = ··· = Aim = 0 例如 A2=A3=0，如下所示：   1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0   2) 重复相关即存在完全相同的相关行向量。 以 Ax 表示 A 的第 x 行，则重复相关表现为 Ai1 = Ai2 = ··· = Aim 例如 A1=A2=A3，如下所示： 第 3 期 陈兴凯，等：基于 0/-1 特征值的网络可控性优化研究 ·591·