大規(guī)模有向網絡的K可控性研究

曾 濤，李曉麗

(東華大學 a.信息科學與技術學院, b.數字化紡織服裝技術教育部工程研究中心, 上海 201620)

各種大規(guī)模網絡系統(tǒng)無處不在,大到覆蓋全國的國家電力網絡和Internet網,小到人體內的神經網絡,甚至是生活中的人際關系網絡。這些網絡系統(tǒng)具有維度高、關聯(lián)復雜,以及不確定性等特征[1-2]。如何給網絡系統(tǒng)中某些節(jié)點施加控制作用使網絡達到預期的狀態(tài),這是廣大學者一直研究的方向。隨著科技發(fā)展,計算機的計算能力大大提高,其成為分析復雜網絡的強大工具,可進一步推進網絡可控性的研究。

由傳統(tǒng)的能控性理論可知,線性系統(tǒng)可控的充分必要條件是系統(tǒng)能控性判別矩陣滿秩。Mortazavian[13]首先提出“K-controllability”的概念,“K-controllability”是一個滿足能控性判別矩陣的秩條件的指標。為了描述這個指標,Li等[14]提出結構能控性指數K來描述這個指標,且給出“K-controllability”的一個充分條件,并對該條件充分性進行證明,但是并沒有證明“K-controllability”的必要性,也沒有對大規(guī)模網絡和真實網絡進行仿真。一個網絡是否可控決定于網絡中是否存在擴張,擴張是網絡中產生控制輸入需求點。Chung等[15]提出一個基于擴張的框架,該框架能夠清楚地了解哪些節(jié)點可能是網絡的輸入節(jié)點,同時該框架還可以分析網絡在擾動下的可控性。Chen等[16]從能量的角度指出,當驅動節(jié)點到目標節(jié)點的路徑距離最小時,控制能量是最佳的,這表明網絡的結構能控指數K越小,網絡的控制能量最佳。一個大規(guī)模網絡系統(tǒng)中,給系統(tǒng)的哪些節(jié)點添加輸入可以使系統(tǒng)可控,在控制輸入下系統(tǒng)可以分解什么樣的子系統(tǒng),以及可控時的控制長度,這些都是需要研究的問題。

本文的研究重點在于針對一個給定的大規(guī)模有向網絡系統(tǒng),從系統(tǒng)的控制性能出發(fā),提出一個K可控定理將大規(guī)模網絡分解為許多個擁有仙人掌結構的子系統(tǒng),對系統(tǒng)的結構能控性指數K進行分析討論,并對該定理進行充分必要性證明。為驗證該定理的可行性,設計了一個K可控算法,對大規(guī)模網絡和真實網絡進行仿真,驗證K可控算法的有效性。

1 可控性基礎理論

1.1 匹配概念和增廣路徑

定義1給定一個有向圖對應的二分圖G=(V,E)中,V是G的頂點集,E是G的邊集,M=(VM,EM)是G的一個子圖,M的邊集EM中的任意兩條邊都不包括相同的頂點,M是G一個匹配。

定義2在二分圖G=(V,E)中,包含邊數最多的匹配稱為該二分圖G的最大匹配[7]。

定義3在二分圖G=(V,E)中,以未匹配的節(jié)點為起點,另一個未匹配的節(jié)點為終點。依次按照未匹配邊、已匹配邊、未匹配邊形成的交替路徑稱為增廣路徑。

定義4起點和終點重合的一條有向路徑稱為環(huán)。

1.2 仙人掌結構

對于一個擁有N個狀態(tài)節(jié)點和M個控制輸入的時不變網絡系統(tǒng),如式(1)所示。

式中:x(t)=(x1(t),x2(t),…,xN(t))T表示在固定時間t下的狀態(tài)向量;A為N×N維系統(tǒng)矩陣,用來描述節(jié)點之間的關聯(lián)關系和連接強度;u(t)為固定時間t下的控制輸入;B為一個N×M維輸入矩陣,表示M個控制輸入和N個狀態(tài)節(jié)點之間的關系。

對應的有向圖稱為芽,如圖1(b)所示。

定義5一個單輸入仙人掌結構由一條“莖”和若干個“芽”按照一定的結構組成,記為G,如圖1(c)所示。

圖1 仙人掌結構圖Fig.1 Cactus structure diagram

(1)系統(tǒng)每個節(jié)點都輸入可達并且滿足,如式(2)所示。

(2)系統(tǒng)對應的拓撲有向圖可以由一個仙人掌結構張成。

1.3 結構能控性指數K

引理2(Kalman秩判據[17]):系統(tǒng)(1)完全可控的充要條件為能控性判別矩陣

C=[B,AB,…,AK-1B,AKB,…,AN-1B]

(3)

滿足:

rank(C)=N

事實上,對于已知(A,B),可能存在矩陣:

Q=[B,AB,…,AKB]

(4)

使得

rank(Q)=N

由此給出結構能控性指數的概念。

定義6若系統(tǒng)(A,B)滿足式(5)和(6)兩種情況時可控,則系統(tǒng)(A,B)可控,且系統(tǒng)的能控性指數為K。

rank([B,AB,…,AKB])=N

(5)

rank([B,AB,…,AK-1B])

(6)

式(7)和(8)中的K≤N,即結構能控性指數K不超過N。結構能控性指數K的物理意義表示從網絡系統(tǒng)的控制節(jié)點出發(fā)通過K次的信息傳遞可以影響到所有節(jié)點,即網絡達到可控狀態(tài),因此稱為K可控。

2 主要結論

引理4網絡系統(tǒng)(A,B)對應的拓撲有向圖G=G1∪G2∪…∪GS,G1,G2…,GS是不相鄰的子圖,每一個子網絡Gi對應的結構能控性指數為Ki,那么網絡G的結構能控性指數如式(9)所示。

K=max{Ki,…,KS}

(9)

證明:G由不相鄰的S個子圖G1,…,GS組成,則以下等式成立:

然后能推出

所以,Q=[B,AB,…,AKB]可以被描述為

因此,系統(tǒng)G的能控性指數對應于子網絡圖Gi([Ai]Ni×Ni,[Bi]Ni×1,),Gi的能控性指數為Ki,顯然有

所有的1≤i≤S都滿足式(10)和(11)。因此,以上過程證明K=max{K1,K2,…,KS}。結合引理3和引理4,可以提出K可控的充分必要條件。

max{K1,…,KM}=K

3 算法設計

3.1 K可控算法步驟

步驟1:置集合M為空。

步驟2:找出一條新的增廣路徑P,通過異或操作獲得更大匹配的集合M′,用M′代替原來的M。

步驟4:初始化控制鏈集合為S1={},存儲每一條控制鏈中所有節(jié)點的集合為S1_k={},控制環(huán)集合S2={},存儲每一個控制環(huán)中所有節(jié)點的集合為S2_k={},k=1。

步驟5:隨機查找未在S1中并且入度為0的點vi(1≤i≤N),令S1_k=S1_k∪{vi}。

步驟6:從vi出發(fā)尋找下一個可達節(jié)點vj,若存在vj則形成鏈路vi→vj,令S1_k=S1_k∪{vj}。繼續(xù)從vj出發(fā)尋找,直到找不到可達節(jié)點時停止。將找到的控制鏈vi→vj→…→vn存入集合S1_k中且k=k+1。

步驟7:重復步驟5、6,直到不存在入度為0的節(jié)點為止。

步驟8:隨機選取不在S1和S2中的剩余節(jié)點vs(1≤i≤N),令S2_k=S2_k∪{vs},重復步驟6尋找控制環(huán)vs→vk→…→vs,并將控制環(huán)存入集合S2-k中,令S2=S2∪{S2-k}。直到所有節(jié)點都遍歷完停止。

如果希望能控性指數K的數值不至于過大,也就是控制鏈過長的問題,可以通過對矩陣維度進行控制,將矩陣進行再分塊使得最大維度變小,最終使結構能控性指數變小,但會增加控制節(jié)點。

3.2 案例分析

通過步驟1可以把矩陣簡化成以下形式:

4 仿真結果分析

利用K可控算法對大規(guī)模隨機網絡進行仿真,表1為仿真結果。N為網絡節(jié)點的個數,L為網絡的邊的總數,〈d〉為隨機網絡的平均度。令nD=ND/N來表示網絡系統(tǒng)的控制輸入情況,其中ND為控制節(jié)點。nD,max為最大匹配算法下得到的值,nD,node為文本提供的算法下得到的值。Kmax是最大匹配算法[5]下的結構能控性指數K值(控制鏈路的最大長度),Knode為K可控算法下的結構能控性指數K值。

表1 隨機網絡仿真結果Table 1 Simulation results for random networks

由表1可以看出,K可控算法和最大匹配算法擁有相同的最少驅動節(jié)點,使得網絡K可控,顯然兩種算法的原理都是尋找增廣路徑,但是K可控算法在此基礎上加入了仙人掌結構。同時,K可控算法在相同網絡和相同驅動節(jié)點下,擁有更小的結構能控性指數K值,即控制鏈路相對更短,控制速度更快。針對不同規(guī)模的隨機網絡,當網絡的平均度〈d〉值相差不大時,nD的值變化不大。由此說明最小控制輸入與網絡的平均度相關。對不同的真實網絡進行仿真(見表2),所有的真實網絡數據集來源于文獻[4]。從表2可以看出,K可控算法擁有和最大匹配算法一樣的最少驅動節(jié)點,網絡可控時的結構能控性指數K值更小。同時可以看出網絡平均度〈d〉相差較大時nD的值差距也較大,驗證了網絡的平均度決定網絡的最小控制輸入。同時驗證K可控算法的可行性,為真實網絡驅動節(jié)點的選取和控制性能研究提供一定的參考價值。

表2 真實網絡仿真結果Table 2 Simulation results for real networks

利用限制結構能控性指數K值,觀察K值和最小控制輸入的關系(見圖2),P表示節(jié)點之間的連邊概率,N表示節(jié)點數量。其中:圖2(a)為P=0.005時對不同節(jié)點數量N的網絡仿真結果;圖2(b)為N=1 000時對不同連邊概率P的網絡仿真結果。由圖2的仿真結果可知,在同一網絡中,K值與最小控制輸nD呈負相關,并且K值越大,最小控制輸入變化越小。由此說明:在網絡系統(tǒng)中,長的控制鏈總是占少數,短的控制鏈占大多數,因此當K值較小時,斷開的控制鏈越多,增加的驅動節(jié)點就越多;K值越小,驅動節(jié)點的增加速度越快。由圖2(b)可知,在相同節(jié)點數量下,連邊概率越大,最小控制輸入越小。文獻[12]研究表明,當連邊的概率P<0.006時,最小控制輸入隨著P的增大而減少。同時連邊概率越大,結構能控性指數K值越大。基于以上規(guī)律,在真實網絡中應該根據實際情況選擇合適的K值和控制節(jié)點。

圖2 K值與最小控制輸入的關系Fig.2 Relationship between K value and minimum control input

5 結 語

本文為研究大規(guī)模有向網絡系統(tǒng)的控制性能,將結構能控性指數K作為其控制性能的指標,提出K可控定理將大規(guī)模網絡系統(tǒng)分解成獨立可控的“仙人掌”系統(tǒng),從而得到系統(tǒng)的結構能控性指數K和驅動節(jié)點集?；谠摱ɡ硖岢鯧可控算法,利用計算機對大規(guī)模隨機網絡和真實網絡進行仿真,結果驗證了K可控定理的有效性。此外,通過限制子矩陣的維度來控制能控性指數K的大小,同時明確不同K值與最小控制輸入之間的關系,為真實網絡驅動節(jié)點的選取提供參考。