基于二分圖的網絡能控性指數研究*

顧　天，李曉麗，趙曙光，鄭鵬遠

(1.東華大學 信息科學與技術學院，上海 201620； 2.上海電力學院 自動化工程學院，上海 200090)

?

基于二分圖的網絡能控性指數研究*

顧天1，李曉麗1，趙曙光1，鄭鵬遠2

(1.東華大學 信息科學與技術學院，上海 201620； 2.上海電力學院 自動化工程學院，上海 200090)

網絡系統的規模不斷擴展，趨向于龐大復雜化。文章針對系統內部信息傳遞所帶來的控制滯后等問題，在網絡系統能控的研究基礎上引入能控性指數的概念，用以描述網絡系統能控的性能指標；基于二分圖提出算法獲得網絡系統能控性指數，并提供每個控制量相應的控制鏈，為后續劃分大規模網絡系統的節點群等研究工作提供科學依據。

網絡系統；二分圖；能控性指數

0　引言

隨著計算機技術的飛速發展，出現了越來越多規模龐大且結構復雜的網絡，其通常具有空間分布式特征，例如跨區域的電力網、縱橫交錯的交通網等。對網絡中若干節點施加控制以實現整個網絡能控，對網絡系統的可控性進行分析，可望在進入定量研究前先得到全局的指導信息[1]，有助于理解各控制量對網絡系統的影響。目前網絡系統的可控性是指在不限制控制步數的情況下，通過施加控制量使其可控，但隨著網絡規模的不斷擴大，網絡系統的各個組成部分彼此間傳遞信息或狀態會帶來控制作用滯后等問題[2]。通過基于能控性指數的算法研究可以將大網絡系統分散化進行控制，縮短了控制過程。

1　問題描述及判據

大規模網絡系統具有極其復雜的結構和不穩定性。針對高維性、非線性的大系統，研究其可控性問題十分復雜，可以將其轉化為在一定范圍內按不同工作點線性化所得的線性系統，進而分析轉化后的線性系統是否可控[1]。考慮由n個節點構成的線性時不變網絡系統:

(1)

定義1:系統(1)可控的充要條件：

rank[B,AB,A2B...An-1B]=n

(2)

網絡系統可控表明其可由任意初始狀態受控制器驅動到達任何所需的最終狀態[4]。其中矩陣An-1B本質上體現了從控制器出發在n-1步路徑內與網絡系統所有節點建立了聯系，根據定義1引入網絡能控性指數μ，對于n維連續時間線性時不變系統，能控性指數μ定義如下：

定義2:系統(1)k步可控的充要條件：

gr[B,AB,A2B...AkB]=n

(3)

滿足式(3)的k的最小值即為能控性指數μ。

圖1為由4個節點構成的網絡系統，對其進行分析。

圖1　網絡關系圖

其中常值矩陣A、B為：

分析發現gr[B,AB,A2B,A3B]=4，符合定義1與定義2，表明該網絡系統可控，也可稱之為3步可控。同時gr[B,AB]=4，符合定義2，而gr[B]<4,則滿足條件的k的最小值為1，即能控性指數為1，控制鏈如圖2所示。

圖2　控制量與節點關系

2　算法

將一個圖的頂點劃分為兩個不相交集U和V，使得連邊分別連接U、V中的頂點，若存在這樣的劃分則此圖就是一個二分圖，而邊數最多的匹配方法即為最大匹配[5]。通過最大匹配能解決很多實際問題，如棋盤走法、配對問題等。匈牙利數學家Edmonds對二分圖的最大匹配進行研究并得到一種普適性的匈牙利算法。

2.1匈牙利算法

以圖3為例介紹匈牙利算法的基本思想。

首先從1開始匹配：1-A，2-C，3-A，如圖3加粗路線，此時由于A已匹配給1，因此將1-A轉變為1-B，從而成功匹配3-A，如圖4所示。

圖3　連接關系

圖4　匈牙利算法步驟1

圖5　匈牙利算法步驟2

繼續匹配4，4-C，如圖4所示。此時由于C已經匹配給2，為了形成更多的匹配邊，因此將4-C轉變為4-D。最終最大匹配方案為1-B、2-C、3-A、4-D，如圖5所示。

2.2算法Aci

研究網絡系統可控性時，可以將網絡表示為二分圖，利用最大匹配理論匹配盡可能多的邊，得出為使網絡可控的一種控制器選取方案，而本文基于可控網絡分析匹配方案以獲取能控性指數。

假設網絡系統如圖6所示。

圖6　網絡節點間關聯情況

通過匈牙利算法可知對節點1、3、5、9施加控制可使該網絡可控，但分析控制方案時會出現圖7所示匹配方式：

圖7　匹配方案

由控制器u5控制的節點群5-6-7-2-8形成了一條控制鏈，但相比于1、3-4、9-10，該條控制鏈顯得較長，易影響控制作用。

在已知網絡可控的基礎上，從各控制量出發，根據節點間的可達關系逐步匹配節點形成或長或短的控制鏈。將一條控制鏈看作一個子系統，當整個系統劃分成若干子系統后，若其分別為k1,k2，…kn步可控，定義其中最大值為kmax，則整個大系統稱為kmax步可控。kmax需盡可能小，當其取值最小時即為能控性指數μ。

以控制器直接控制的節點i為起始點，同時進行匹配。由網絡可控可知每個節點都必存在于匹配邊中，因此若匹配完成后仍有節點未被匹配，則必須改變某節點的匹配方式，直至所有節點均被匹配。

能控性指數算法Aci描述如下：

(1)列出所有根節點i(1≤i≤n)；

(2)λ:根節點i的數目,設置k=0；

(3)重復步驟(4)～(6)；

(4)匹配i的可達節點j(i-j),j∈Ni,若j出現重復則改變前者匹配方式，j的數目為η,k=k+1,λ=λ+η；

(5)令j為新的根節點,匹配其可達節點；

(6)當η=0,λ≠n,節點σ未匹配(δ可達σ),退回δ所在步驟,改變其匹配方式為δ-σ,從該步驟開始繼續向下匹配；

(7)直至λ=n，n為網絡節點數目；

(8)所有節點已存在于匹配邊中,μ=k。

3　仿真與結論

利用二分圖描述圖6所示網絡，如圖8所示，箭頭表示始端節點可達末端節點，例如1指向2表示節點1可達節點2。

圖8　網絡(圖6)二分圖

分析圖6網絡，n=10，k=0，起始點為1、3、5、9，λ=4，第一步如圖9所示。

圖9　網絡系統

匹配節點為2、4、6、10，η=4。此時λ=8，k=1，第二步如圖10所示。

圖10　網絡系統

匹配節點為8、7。其中4-2，2在第一步就已匹配(舍去)，轉變為4-8，而此步驟已將8分配給了2，改變匹配方式2-10，而10在第一步就已匹配(舍去)，因此2向下不可再匹配，η=2。此時λ=10=n，所有節點已存在于匹配邊中，k=2，μ=2。

最終匹配方式如圖11所示，控制鏈為：1-2；3-4-8；5-6-7；9-10。同時可驗證gr[B,AB,A2B]=10，k的最小值為2，即能控性指數μ=2。

圖11　網絡系統

以圖12網絡系統為例，可控性指數μ=5，通過匹配邊將原本關聯復雜的網絡分散化，獲得各條結構簡單明了的控制鏈，使得控制作用更有效。

圖12　網絡系統的控制鏈

4　結束語

本文引入網絡系統能控性指數的概念并給出能控性

判據，在此基礎上提出算法Aci獲得能控性指數及相應的控制鏈，縮短了控制過程和時間。在實際網絡如電網中，大量節點具有固定的匹配方式，這樣就能為分析網絡的k步可控性節省大量時間，同時研究各個控制器所控制的節點群，可以明顯地從復雜的網絡中得到各條清晰的控制鏈，以各控制器為起始點，只需抓住這個起始點將其從網絡中抽出便可獲知該控制器依次控制的各個節點。對于研究某些實際網絡模型有很大的參考價值，并可反過來服務于研究控制器的選取。

[1] 席裕庚.動態大系統方法導論[M].北京：國防工業出版社,1988.

[2] 李健勇,羅永平,黃道穎,等.網絡控制系統時延分布分析與建模[J].鄭州輕工業學院學報(自然科學版),2014,29(4):50-53.

[3]LiuYangyu,SLOTINEJJ,BARABA′SIAL.Controllabilityofcomplexnetworks[J].Nature， 2011，473(12)：167-173.

[4] 鄭大鐘.線性系統理論[M].北京：清華大學出社,2011.

[5] 邵長城,張錫哲.復雜網絡可控性分析與驅動節點集拓撲性質研究[D].沈陽：東北大學,2012.

Research on index of controllability for network based on bipartite graph

GuTian1，LiXiaoli1，ZhaoShuguang1，ZhengPengyuan2

(1.CollegeofInformationScience&Technology,DonghuaUniversity,Shanghai201620,China;2.CollegeofAutomationEngineering,ShanghaiUniversityofElectricPower,Shanghai200090,China)

Thescaleofthenetworksystemisexpandingandtendstobehugeandcomplex.Aimingattheproblemaboutcontrollagcausedbytheinternalinformationtransmissionofsystem,onthebasisofresearchonthecontrollabilityofnetworksystem,theindexofcontrollabilityisintroducedtocharacterizetheperformanceindices.Thispaperproposesanalgorithmbasedonbipartitegraphandobtainstheindexandcorrespondingcontrolchainofeachcontroller,andthisworkprovidesscientificbasisforresearchonthedivisionofnodegroupinlarge-scalenetworksystem.

networksystem;bipartitegraph;theindexofcontrollability

國家自然科學基金(61203073,61271114,61573239);教育部博士點基金(20120075120008);上海市自然科學基金(16ZR1446700,15ZR1418600)

TP11ADOI： 10.19358/j.issn.1674- 7720.2016.15.006

2016-04-13)

顧天(1992-)，通信作者，男，碩士研究生，主要研究方向：網絡系統可控性。E-mail:gutianlol@126.com。

李曉麗(1980-)，女，博士，副教授，碩士生導師，主要研究方向：復雜網絡系統控制與優化。

趙曙光(1965-)，男，博士，教授，主要研究方向：智能儀器與系統、電子系統設計自動化。

引用格式：顧天，李曉麗，趙曙光，等. 基于二分圖的網絡能控性指數研究[J].微型機與應用，2016,35(15)：21-23.