文章快速检索  
  高级检索
复杂网络在路形拓扑结构下可控的充要条件
晁永翠, 纪志坚, 王耀威, 董洁
青岛大学 自动化工程学院, 山东 青岛 266071
基金项目: 国家自然科学基金资助项目(61374062);山东省杰出青年科学基金资助项目(JQ201419).    
摘要: 分析了在路形拓扑结构下复杂网络的可控性问题。把系统的邻接矩阵进行适当分解,找到邻接矩阵的各子矩阵之间在特征值和特征向量上的关系,进而基于PBH(Popov-Belevitch-Hautus)判据,得到了复杂网络在路形拓扑结构下系统可控的充要条件。特别地,当控制节点为任意的某一个或多个节点时,给出了路图可控的判别方法。此外,文中提出了不可控特征值的概念,并给出了相应特征值的具体表达形式。文中2个主要定理通过算例进行验证,算例结果与定理结论一致。
关键词: 复杂网络     可控性     图论     拓扑     线性定常系统     特征值     特征向量     控制系统    
Necessary and sufficient conditions for the controllability of complex networks with path topology
CHAO Yongcui, JI Zhijian , WANG Yaowei, DONG Jie    
School of Automation Engineering, Qingdao University, Qingdao 266071, China
Abstract: The controllability of complex networks is analyzed in the paper for path topology. With adjacency matrix of the system being decomposed into submatrices, the relationship between eigenvalues and eigenvectors is revealed for the partitioned submatrices. Furthermore, necessary and sufficient conditions are derived by taking advantage of the PBH(Popov-Belevitch-Hautus) criteria. In particular, a method is proposed to determine path controllability when the controlled nodes are any single or multiple nodes, as well as the concept of uncontrollable eigenvalues is presented. The expressions for uncontrollable eigenvalues are provided as well. Two theorems in this paper is verified by examples and the results of examples are in agreement with the conclusion of the theorems.
Key words: complex networks     controllability     graph theory     topology     linear time-invariant systems     eigenvalue     eigenvectors     control system    

控制科学的发展表明,可控性概念是对系统进行分析与综合的基础,是系统的重要结构性质。20世纪60年代,卡尔曼(R.E.Kalman)[1]首先提出状态可控性的概念。其后的研究表明,可控性的概念是判别被控系统是否可控的重要途径。近年来,网络系统的可控性研究成为当前的一个热点研究领域,该问题的研究受到了国内外科研工作者的广泛关注[2, 3, 4, 5, 6]

本文致力于研究复杂网络系统的能控性,该研究可促进包括系统的镇定控制[7, 8]、编队控制[9, 10]、入侵检测[11, 12]和分布式估计[13, 14, 15, 16]等诸多问题的理解。和传统控制不同,网络系统是建立在个体间信息的传递之上的。自然地,信息关系图的拓扑结构在系统行为的动态演化中起到了关键性作用,不同拓扑结构下的系统性能可能截然不同。因此,许多科研工作者尝试探讨与能控性相关的图论刻画。例如,系统能控的图论特征,这些特征使得直接从图的拓扑结构出发判断系统的能控性成为可能;再如,能控性中领航者的选取问题,如何确定领航者的位置和数量使得系统能控,这也是网络系统能控性中的典型问题。

复杂网络的研究已渗透到数理学科、生命学科和工程学科等众多不同的领域,对复杂网络可控性的研究具有挑战性[17, 18]。即便是最简单的路形拓扑结构,和其可控性相关的研究也不简单[19]。文献[19]研究的是基于Laplacian矩阵的路图的能控性,与该问题相关的研究成果在文献[4, 6, 20]中也报道过。此外,还有基于邻接矩阵的网络系统可控性问题[17, 18],本文即是研究基于邻接矩阵的路图拓扑的可控性。

本文研究的是控制节点的选取,这不同于文献[17, 18]中驱动节点个数的选取问题。在基于邻接矩阵的可控性问题研究,文献[17]中表述,网络中节点的度的大小影响驱动节点个数的选取,在选取驱动节点时,选取度数小的驱动节点更有利于系统可控性的实现。但针对更复杂的拓扑结构,控制节点的选取比驱动节点的选取更为复杂,相应的结果也更少。文献[18]提出了对于特定的链接与加权网络,使系统可控的最少数目控制节点的判别方法。然而,以上两篇文章都没有给出针对网络拓扑图中,通过控制某一个或几个节点,来具体判断系统是否可控的方法。该问题涉及到控制节点的选取,这通常是更为复杂的研究方面,也是本文着力解决的内容。

本文将针对路形拓扑结构,对每个节点展开分析,通过建立充要条件,来判断相应系统的可控性。更具体地,通过对路图的邻接矩阵及其子矩阵进行分析,发现其特征值之间的相互关系,从而得到路图可控性的充分必要条件,该结果的一个显著特征是建立了所提出的代数条件与拓扑图中每个节点的联系。

1 预备知识

文中为自然数集,er为第r个元素为1,其他元素均为0的列向量,r,例如e1=[1 0 … 0]T。记G(b1,b2,…,bd)为d个自然数b1,b2,…,bd的最大公约数,dG(b1,b2,…,bd)>1表示b1,b2,…,bd有除了1之外的其他公约数。Rn表示n维实向量空间,Rm×n表示实m×n矩阵的集合。对于一个有n个节点的无向图G,所有的节点被标记为1,2,…,n。顶点集和边集分别记为V={1,2,…,n}与ε={(i,j)}∈V×Vij邻接。图G是由顶点集V和边集ε构成的二元组,记为G=(V,ε)。与顶点v相关联的边的总数称为顶点v的度。一个有n个节点的图G,若其顶点可以标号成(或重新标号成)1,2,…,n,使得它的边集是ε={(1,2),(2,3),…,(n-1,n)},则称图G为路图[21]。由此可知,除了第一个节点1与最后一个节点n的度为1之外,其他所有节点的度都为2。节点1与节点n称为外节点,其他的节点称为内节点。设图G的邻接矩阵A=(aij)n×n,则aij定义为

在已有文献中,通常把由外部输入控制的节点称为控制节点,由Ic={i1,i2,…,im}⊂{1,2,…,n}表示被控的节点集。考虑如下一个有n个节点的线性系统:

式中:x=[x1 x2xn]T表示系统的状态,ARn×n是系统的邻接矩阵,BRn×m是控制矩阵,uRm×n是输入矩阵。由于讨论的是无向图,所以A是对称矩阵。对任一给定的初始状态,如果存在一个控制输入u,使式(1)能在有限时间间隔内,从初始状态转移到任意指定的终端状态,则称该系统是可控的。目前,有许多判别线性系统可控的方法,例如Gram矩阵判据、PBH判据[22]、秩判据等。本文从PBH判据出发,分析系统的可控性,进而得到系统可控的充要条件。

引理1 系统(1)可控的充要条件是不存在非零的向量v满足以下等式:

若存在向量v使得上面的等式成立,则称相应的λ是系统不可控的特征值。

证明 根据PBH判据并结合A的对称性即知结论成立。

2 主要结论

本节将首先对邻接矩阵进行分解,基于此给出子矩阵特征值的表达形式,然后,通过所提出的矩阵特征值之间的关系,得出相应的引理与定理。

2.1 邻接矩阵的分解

B矩阵的具体表达与一系列的控制节点相对应,如果Ic={i1,i2,…,im},则B=[ei1 ei2eim]。由引理1可知,路图不可控意味着存在非零向量v满足Av=λv,且BTv=0。矩阵定义如下:

式中ν是矩阵的维数。

因为B=[ei1 ei2eim],由BTv=0可得向量v的第ic个向量元素为零,即(v)ic=0,icIc。因此,在Av=λv中,A可分解为

向量v可分解为

Av=λv可得

式中:vσ是向量v的第σ个分块向量,σ

引理2 矩阵A与矩阵Mν的特征向量的第一个元素与最后一个元素都不为0。

证明λA的一个特征值,对应的特征向量为ξ=[ξ1 ξ2ξn]T,由=λξ可得

ξ1=0时,ξ2=ξ3=…=ξn=0,即ξ为零向量,这与ξ是特征向量矛盾。同理可证ξn≠0。矩阵Mν的情况同样证明。

引理3 对于矩阵Mν,有

1)矩阵Mν的特征值的形式为

2)矩阵Mν的特征值必是矩阵Mαν+α-1的特征值,其中α

证明 1)可由文献[18]附加材料中关于路图的例子得到。2)可由矩阵Mν特征值的表达形式得到。

2.2 路图的可控性

将引理1与引理2结合可知,路图的每一个外节点为控制节点时,路图是可控的[23]。然而,当控制节点为路图的内节点时,其能控性如何,是更值得探讨的问题,这也是本节欲解决的问题。首先给出以下两个引理,其中,第一个引理是关于单个控制节点的情况。

引理4 对控制节点为r∈{2,3,…,n-1}的长度为n的路图,当且仅当矩阵Mr-1Mn-r没有相同的特征值时,路图是可控的。此外,矩阵Mr-1与Mn-r相同的特征值为矩阵A在控制节点为r时,系统不可控的特征值。

证明 为了简便,证其逆否命题。由PBH判据,当且仅当

erTv=0时,路图是不可控的。由erTv=0得

式中:v1Rr-1v2Rn-r。代入式(2)得

所以,系统不能控当且仅当不存在A的一个特征向量v使得式(3)成立。

充分性 若λ0Mr-1Mn-r的共同特征值,且对应的特征向量分别为v10v20。令

式中:ρR,(v10)r-1+(ρv20)1=0,则可验证v满足式(3),其中λ=λ0。所以系统不能控。

必要性 假设系统不能控,则由式(3)且v1≠0,v2≠0得,λ为矩阵Mr-1Mn-r的共同特征值。

此外,假设λ1Mr-1Mn-r共同的特征值,则存在一个如上的非零向量v=[v10T 0 ρv20T]T满足Av=λverTv=0。因此λ1是系统不可控的特征值。

引理4回答了控制节点为一个时,路图可控的充要条件,以下这个引理则给出了受控节点为多个时,路图可控的充要条件。

引理5 控制节点Ic={i1,i2,…,im}⊂{1,2,…,n}长度为n的路图,当且仅当矩阵Mi1-1Mi2i1-1,…,Mn-im没有相同的特征值时,路图是可控的。此外,矩阵共同的特征值为邻接矩阵A在控制节点为Ic时,系统不可控的特征值。

引理5的证明与引理4类似,此处不再赘述。

为了更清晰地表达以上关于可控性的条件,下面利用特征值的特殊形式与最大公约数理论,进一步给出路图可控的充分必要条件。

定理1 对于一个长度为n的路图,有以下陈述:

1)当控制节点为r∈{2,3,…,n-1}时,路图可控的充分必要条件为

G(r,n-r+1)=1

2)当控制节点集Ic={i1,i2,…,im}⊂{1,2,…,n}时,路图可控的充分必要条件为

G(i1,i2i1,…,imim-1,nim+1)=1

证明

充分性 证其逆否命题,由引理4可知,当矩阵Mr-1Mn-r有相同的特征值时,路图不完全可控。结合引理3可得

式中:q1∈{1,2,…,(r-1)},q2∈{1,2,…,(n-r)}。由于q1q2取自这2个特定集合,式(4)等式两边余弦内的数值都小于π,得

化简为

又由于q1q2的取值限制,使得式(5)成立的条件是整数rn-r+1不互质,即

G(r,n-r+1)>1

必要性 证其逆否命题,当G(r,n-r+1)>1时,则存在正整数ct1t2,使得ct1=rct2=n-r+1,其中t1<rt2<n-r+1。又有q1∈{1,2,…,r-1},q2∈{1,2,…,n-r},则当q1=t1q2=t2时,等式成立,即为式(5)的形式,则式(4)成立。即矩阵Mr-1Mn-r有相同的特征值。所以路图是不可控的。

对陈述2),证其逆否命题。引理5与引理3结合,取子矩阵的特征值。接下来的证明与陈述1)中的相似。最后即可得到陈述2)中的结论。

由定理1中陈述1)同样也可得到当控制节点为外节点时路图是可控的这一结论。具体如下:控制节点r=1或n时,根据陈述1)可得G(1,n)=1或G(n,1)=1,因为1与任何数都互质,可得当控制节点为外节点时路图是可控的。当控制节点r=2或n-2时,由陈述1)可知,需判断2与n-1是否互质。当n-1奇数,即n为偶数时,2与n-1互质,路图可控;反之,路图不可控。可表述为以下推论。

推论1 对于一个长度为n的路图,当控制节点r为外节点的邻接点时,若n为偶数时,则路图是可控的;若n为奇数时,则路图不可控。

由定理1中陈述1)还可推出一些简便的判别路图可控性的方法。例如,当控制节点r=n/2(r= (n+2)/2)且n为偶数时,路图是可控的。这是因为当r=n/2,nr+1=n/2+1(r=(n+2)/2,n-r+1=n/2),整数rn-r+1为相邻的2个数。我们知道,相邻的2个数肯定是互质的,所以路图是可控的。当n为奇数且r为偶数时,路图不可控。因为当n为奇数r为偶数时,n-r+1为偶数,即G(r,n-r+1)>1,路图不可控。

定理2 对于一个长度为n的路图,若n可分解为n=mp+m+p,其中m,p,则当控制节点集为Icpm={κ(p+1)}κ∈1,…,m时,路图是不可控的,其中κ∈{1,2,…,m}。此外,假设κ的取值从小到大依次为b1,b2,…,bs(s≤m),则系统有以下不可控的特征值

式中:β=min{b1,bkbk-1,m-bs+1},k∈{2,3,…,s}。

证明n=mp+m+p时,控制节点集为Icpm=κ(p+1)κ∈{1,2,…,m},即为定理1陈述2)中所有不可控的控制节点的集合。当整数p的取值不同时,即可得到不同的不可控的控制节点集。当β=min{b1,bkbk-1,m-bs+1},k∈{2,3,…,s},邻接矩阵A被分解为2种形式的子矩阵,即Mβ(p+1)-1M(β+μ)(p+1)-1(μ。子矩阵的共同特征值即为最小的子矩阵Mβ(p+1)-1特征值的部分或全部。即为式(6)表达的形式。若存在一个正整数y使μ=yβ,则不可控的特征值为最小的子矩阵Mβ(p+1)-1的全部特征值,即

为了更清晰地理解定理2,以下给出一个较为直观的解释。当pm固定时,对控制节点集Icpm中的节点给与相同的标记。把全部的节点用m个控制节点分为m+1份,每份的节点数为p个(除控制节点外)。但事实上,在选取控制节点时未必选择集合Icpm内的所有的节点为控制节点,所以有定理2中所述,不可控的特征值为邻接矩阵A中被分解的最小的子矩阵Mβ(p+1)-1的特征值的部分或全部。

2.3 实例分析

以下给出2个例子。n=11与n=14的路图,分别如图 1中与图 2所示。

图 1 n=11的路图 Fig. 1 The path graph with n=11

图 1中,横线标记的节点是控制节点为Icp1m1的集合,其中p1=1,m1=5。竖线标记的节点是控制节点为Icp2m2的集合,其中p2=2,m2=3。当控制节点为Icp1m1时,系统有相同的不可控的特征值λ=0,而1与-1为系统在控制节点集为Icp2m2时2个不可控的特征值。

图 2 n=14的路图 Fig. 2 The path graph with n=14

图 2中,斜线标记的节点是控制节点为Icpm的集合,其中p=2,m=4。当控制节点为节点3和节点9时,A可被分解为M2M5两种形式的子矩阵,矩阵M2M5的共同特征值即为矩阵M2的全部特征值。若控制节点为节点6时,A可被分解为M5M8两种形式的子矩阵,矩阵M5M8的共同特征值即为矩阵M5的部分特征值。

3 结束语

本文给出了判断复杂网络系统中路图可控性的方法,把PBH判据与对称的邻接矩阵相结合,得到了路图可控的充要条件,并应用数学中的简单理论,对于路图可控性的充要条件进行了更为数字化的表示。在此基础上,提出了系统不可控的特征值的表达形式。同理,可推出环图可控性的充要条件。本文通过对路图的每个节点进行分析,进而判断可控性,使得直接从图的结构形式判断能控性成为可能。本文对于路图可控性的研究方法和结果,为以后研究更为复杂的图拓扑结构的可控性提供了一个方向和基础。

参考文献
[1] KAMLAN R E.Mathematical description of linear dynamical systems[J].Journal of the Society for Industrial and Applied Mathematics Series A:Control,1963,1(2):152-192.
[2] NOTARSTEFANO G,PARLANGELI G.Controllability and observability of grid graphs via reduction and symmetries[J].IEEE Transactions on Automatic Control,2013,58(7):1719-1731.
[3] JI Zhijian,LIN Hai,YU Haisheng.Protocols design and uncontrollable topologies construction for multi-agent networks[J].IEEE Transactions on Automatic Control,2014,60(3):781-786.
[4] JI Zhijian,LIN Hai,YU Haisheng.Leaders in multi-agent controllability under consensus algorithm and tree topology[J].Systems&Control Letters,2012,61(9):918-925.
[5] JI Zhijian,WANG Zidong,LIN Hai,et al.Interconnection topologies for multi-agent coordination under leader-follower framework[J].Automatica,2009,45(12):2857-2863.
[6] RAHMANI A,JI Meng,MESBAHI M,et al.Controllability of multi-agent systems from a graph-theoretic perspective[J].SIAM Journal on Control and Optimization,2009,48(1):162-186.
[7] GUAN Yongqiang,JI Zhijian,ZHANG Lin,et al.Decentralized stabilizability of multi-agent systems under fixed and switching topologies[J].Systems&Control Letters,2013,62(5):438-446.
[8] KIM H,SHIM H,BACK J,et al.Stabilizability of a group of single integrators and its application to decentralized formation problem[C]//Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference.Orlando,USA,2011:4829-4834.
[9] SABATTINI L,SECCHI C,FANTNZZI C.Controllability and observability preservation for networked systems with time varying topologies[C]//Proceedings of the 19th World Congress on the International Federation of Automatic Control.Cape Town,South Africa,2014:1837-1842.
[10] MESBAHI M,EGERSTEDT M.Graph Theoretic Methods in Multiagent Networks[M].Princeton:Princeton University Press,2010:117-151.
[11] SUNDARAM S,HADJICOSTIS C N.Distributed function calculation via linear iterative strategies in the presence of malicious agents[J].IEEE Transactions on Automatic Control,2011,56(7):1495-1508.
[12] PASQUALETTI F,BICCHI A,BULLO F.Consensus computation in unreliable networks:A system theoretic approach[J].IEEE Transactions on Automatic Control,2012,57(1):90-104.
[13] LI Zhongkui,REN Wei,LIU Xiangdong,et al.Distributed containment control of multi-agent systems with general linear dynamics in the presence of multiple leaders[J].International Journal of Robust and Nonlinear Control,2013,23(5):534-547.
[14] FARINA M,FERRARI-TRECATE G,SCATTOLINI R.A moving horizon scheme for distributed state estimation[C]//Proceedings of the 48th IEEE Conference on Decision and Control.Shanghai,China,2009:1818-1823.
[15] JI Zhijian,WANG Zidong,LIN Hai,et al.Controllability of multi-agent system with time-delay in state and switching topology[J].International Journal of Control,2010,83(2):371-386.
[16] LIU Bo,CHU Tianguang,WANG Long,et al.Controllability of leader-follower dynamic network with switching topology[J].IEEE Transactions on Automatic Control,2008,53(4):1009-1013.
[17] LIU Yangyu,SLOTINE J J,BARABÁSI A L.Controllability of complex networks[J].Nature,2011,473(7346):167-173.
[18] YUAN Zhengzhong,ZHAO Chen,DI Zengru,et al.Exact controllability of complex networks[J].Nature Communications,2013,4:Aricle number 2447.
[19] PARLANGELI G,NOTARSTEFANO G.On the reachability and observability of path and cycle graphs[J].IEEE Transactions on Automatic Control,2012,57(3):743-748.
[20] PARLANGELI G,NOTARSTEFANO G.On the observability of path and cycle graphs[C]//Proceedings of the 49th IEEE Conference on Decision and Control.Atlanta,USA,2010:1492-1497.
[21] CHARTRAND G,ZHANG Ping.图论导引[M].范益政,等译.北京:人民邮电出版社,2007:1-17.
[22] TANNER H G.On the controllability of nearest neighbor interconnections[C]//Proceedings of the 43rd IEEE Conference on Decision and Control.Nassau,Bahamas,2004:2467-2472.
[23] PARLANGELI G,NOTARSTEFANO G.Graph reduction based observability conditions for network systems running average consensus algorithms[C]//Proceedings of the 18th Mediterranean Conference on Control and Automation.Marrakesh,Morocco,2010:689-694.
DOI: 10.3969/j.issn.1673-4785.201411031
中国人工智能学会和哈尔滨工程大学联合主办。
0

文章信息

晁永翠, 纪志坚, 王耀威, 董洁
CHAO Yongcui, JI Zhijian, WANG Yaowei, DONG Jie
复杂网络在路形拓扑结构下可控的充要条件
Necessary and sufficient conditions for the controllability of complex networks with path topology
智能系统学报, 2015, 10(04): 577-582.
CAAI Transactions on Intelligent Systems, 2015, 10(04): 577-582.
DOI: 10.3969/j.issn.1673-4785.201411031

文章历史

收稿日期: 2014-11-25
网络出版日期: 2015-07-16

相关文章

工作空间