曾 濤，李曉麗

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

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

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

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

1 可控性基礎(chǔ)理論

1.1 匹配概念和增廣路徑

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

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

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

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

1.2 仙人掌結(jié)構(gòu)

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

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

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

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

圖1 仙人掌結(jié)構(gòu)圖Fig.1 Cactus structure diagram

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

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

1.3 結(jié)構(gòu)能控性指數(shù)K

引理2(Kalman秩判據(jù)[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

由此給出結(jié)構(gòu)能控性指數(shù)的概念。

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

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

(5)

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

(6)

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

2 主要結(jié)論

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

K=max{Ki,…,KS}

(9)

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

然后能推出

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

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

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

max{K1,…,KM}=K

3 算法設(shè)計

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:重復(fù)步驟5、6,直到不存在入度為0的節(jié)點為止。

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

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

3.2 案例分析

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

4 仿真結(jié)果分析

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

表1 隨機網(wǎng)絡(luò)仿真結(jié)果Table 1 Simulation results for random networks

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

表2 真實網(wǎng)絡(luò)仿真結(jié)果Table 2 Simulation results for real networks

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

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

5 結(jié) 語

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