陳 浩 王祥科 楊 健

1.國防科技大學(xué)智能科學(xué)學(xué)院 湖南長沙 410073 2.華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院 廣東廣州 510640

一致性理論是集群系統(tǒng)分析的最基礎(chǔ)的理論之一,在集群分布式估計(jì)[1]、分布式優(yōu)化[2-3]、協(xié)同控制[4-6]、協(xié)同決策[7-8]等方面有著重要的應(yīng)用.一致性問題主要是研究如何使網(wǎng)絡(luò)中的智能體在某些狀態(tài)或輸出達(dá)成一致[9-10].在集群一致性問題中,網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)扮演著重要的角色.若網(wǎng)絡(luò)拓?fù)錇闊o向圖,為實(shí)現(xiàn)一致性,通常要求網(wǎng)絡(luò)為連通圖[11-12]；若網(wǎng)絡(luò)拓?fù)錇橛邢驁D,為實(shí)現(xiàn)一致性,通常要求網(wǎng)絡(luò)為有根圖[13],即網(wǎng)絡(luò)中存在某一頂點(diǎn),使得該頂點(diǎn)到網(wǎng)絡(luò)中其他任一頂點(diǎn)都存在有向通路,滿足這樣性質(zhì)的頂點(diǎn)即為有根圖的根.強(qiáng)連通有向圖是一類特殊的有根圖,此類圖中的每一個(gè)頂點(diǎn)都是根.

在集群執(zhí)行任務(wù)過程中,不可避免會(huì)有通信鏈路失效或智能體損毀等意外事件發(fā)生.其中,通信鏈路失效,相當(dāng)于在網(wǎng)絡(luò)中去掉對(duì)應(yīng)的邊,智能體損毀,相當(dāng)于在網(wǎng)絡(luò)中去掉對(duì)應(yīng)的頂點(diǎn).當(dāng)此兩類意外事件發(fā)生時(shí),可能會(huì)導(dǎo)致達(dá)成一致性的拓?fù)錀l件不再滿足,即無向圖不再連通,或有向網(wǎng)絡(luò)不再是有根圖.由于網(wǎng)絡(luò)拓?fù)渲貥?gòu)的分布式?jīng)Q策過程往往較為復(fù)雜,實(shí)際在網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)時(shí),可考慮增加額外的邊,通過冗余設(shè)計(jì),使集群具有“抗毀性”,即當(dāng)去掉網(wǎng)絡(luò)中一定數(shù)量的邊或頂點(diǎn)后,無向圖依然連通,或有向圖依然為有根圖.

近年來,在復(fù)雜網(wǎng)絡(luò)領(lǐng)域,網(wǎng)絡(luò)的抗毀性成為一大研究熱點(diǎn)[14],主要借助于圖論、統(tǒng)計(jì)物理等工具,使用連通度、堅(jiān)韌度等測度分析抗毀性.在集群協(xié)同控制方面,于長斌等基于剛性圖的概念,提出了k 邊剛性和k 頂點(diǎn)剛性的定義,其含義是網(wǎng)絡(luò)中去掉k 條邊或k 個(gè)頂點(diǎn)后,結(jié)果仍然是一個(gè)剛性圖[15]；Jafari 等提出了p 連接能控性和q 智能體能控性的概念,為集群系統(tǒng)在通信鏈路失效和智能體損毀的情況下的結(jié)構(gòu)能控性提供了度量方法[16].但現(xiàn)有網(wǎng)絡(luò)抗毀性研究并未從集群一致性的角度分析,如何衡量集群網(wǎng)絡(luò)在一致性意義下的抗毀性,仍然是一個(gè)待解決的問題.

基于此,本文分別針對(duì)無向網(wǎng)絡(luò)和有向網(wǎng)絡(luò),從實(shí)現(xiàn)集群一致性的拓?fù)錀l件出發(fā),提出了抗毀性的概念；對(duì)于無向網(wǎng)絡(luò),建立了一致性意義下的抗毀性網(wǎng)絡(luò)與連通度概念的聯(lián)系；對(duì)于有向網(wǎng)絡(luò),論文將圖論中連通度這一概念進(jìn)一步拓展,提出了邊/頂點(diǎn)連通有根圖的概念以刻畫有向網(wǎng)絡(luò)的抗毀性；論文提出了針對(duì)一般的有向/無向抗毀性網(wǎng)絡(luò)的設(shè)計(jì)方法,并在此基礎(chǔ)上,進(jìn)一步研究了幾類特殊的有向抗毀性網(wǎng)絡(luò)的性質(zhì)和相應(yīng)的生成算法.

1 無向抗毀性網(wǎng)絡(luò)

1.1 無向抗毀性網(wǎng)絡(luò)的概念

對(duì)于無向網(wǎng)絡(luò)連接的集群系統(tǒng),為實(shí)現(xiàn)一致性,通常要求網(wǎng)絡(luò)為連通圖.但面向復(fù)雜環(huán)境下集群的運(yùn)用需求,網(wǎng)絡(luò)的拓?fù)湓O(shè)計(jì)需要具備一定的冗余度,即滿足一定的抗毀性,以保證在局部通信鏈路失效或部分智能體損毀等意外事件發(fā)生后無向網(wǎng)絡(luò)仍連通.在此給出集群無向抗毀性網(wǎng)絡(luò)的定義如下.

在此以圖1中的例子闡述無向抗毀性網(wǎng)絡(luò)的定義.圖1左圖所示的網(wǎng)絡(luò)結(jié)構(gòu),當(dāng)去掉該圖中任意一條邊,或任意一個(gè)頂點(diǎn)及該頂點(diǎn)所連接的邊之后,無向網(wǎng)絡(luò)依然是連通的,因此,該網(wǎng)絡(luò)結(jié)構(gòu)具有1 邊無向抗毀性和1 頂點(diǎn)無向抗毀性；而對(duì)于圖1右圖所示的網(wǎng)絡(luò)結(jié)構(gòu),若去掉頂點(diǎn)1 和頂點(diǎn)2 之間的邊或頂點(diǎn)2 和頂點(diǎn)3 之間的邊,都會(huì)造成新得到的網(wǎng)絡(luò)不再連通；同樣,當(dāng)頂點(diǎn)2 或頂點(diǎn)3 去掉之后,網(wǎng)絡(luò)也不再連通.因此,圖1右圖所示的網(wǎng)絡(luò)不具有抗毀性.

圖1 闡釋無向抗毀性網(wǎng)絡(luò)概念的例子Fig.1 Examples to illustrate the concept of undirected survivable networks

對(duì)于無向網(wǎng)絡(luò),抗毀性的概念與連通度[17]的概念相對(duì)應(yīng),若網(wǎng)絡(luò)具有k 邊/頂點(diǎn)無向抗毀性,當(dāng)且僅當(dāng)具有k+1 邊/頂點(diǎn)連通度.現(xiàn)給出一個(gè)關(guān)于邊/頂點(diǎn)連通度的重要定理.

定理1 （Menger 定理[17）]對(duì)于無向圖,其邊/頂點(diǎn)連通度等于中任意兩個(gè)頂點(diǎn)之間邊/頂點(diǎn)不相關(guān)的路徑數(shù)目的最小值.

在定理1 中,兩條路徑是邊不相關(guān)的,指這兩條路徑?jīng)]有公共的邊；兩條路徑是頂點(diǎn)不相關(guān)的,指這兩條路徑除起始點(diǎn)和終止點(diǎn)之外,沒有公共的頂點(diǎn).由Menger 定理知,若網(wǎng)絡(luò)具有k 邊/頂點(diǎn)無向抗毀性,則中任意兩個(gè)頂點(diǎn)之間至少有k+1 條邊/頂點(diǎn)不相關(guān)的路徑.顯然,兩個(gè)頂點(diǎn)之間的頂點(diǎn)不相關(guān)的路徑也是邊不相關(guān)的,因此,由Menger 定理可以得出如下推論.

1.2 無向抗毀性網(wǎng)絡(luò)的生成算法

現(xiàn)假設(shè)集群網(wǎng)絡(luò)中所有智能體采用點(diǎn)對(duì)點(diǎn)通信的方式,且兩兩之間的通信代價(jià)已知,如何構(gòu)造k 邊/頂點(diǎn)無向抗毀性網(wǎng)絡(luò),使網(wǎng)絡(luò)中總的通信代價(jià)最小？

遺憾的是,當(dāng)k≥2 時(shí),該問題是NP 難.通常,采用貪婪等策略,給出次優(yōu)解.例如,L.Yang 針對(duì)模式識(shí)別領(lǐng)域高維流形映射到低維空間的數(shù)據(jù)嵌入問題,發(fā)表了一系列k 邊和k 頂點(diǎn)連通無向圖的生成算法,包括用于生成k 邊連通無向圖的k-MST 算法（重復(fù)提取k 個(gè)最小生成樹）[18]、Min-k-ST 算法（尋找總長最小的k 個(gè)邊不相關(guān)的生成樹）[19]、k-EC 算法（按邊長非減的順序添加連接兩個(gè)尚不存在k 條邊不相關(guān)路徑的頂點(diǎn)的邊）[20],以及用于生成k 頂點(diǎn)連通無向圖的k-VC 算法（按邊長非減的順序添加連接兩個(gè)尚不存在k 條頂點(diǎn)不相關(guān)路徑的頂點(diǎn)的邊）[21].其中,使用k-MST 算法和Min-k-ST 算法生成的k 邊連通無向圖邊數(shù)均為,而使用k-EC 算法生成的k邊連通無向圖以及k-VC 算法生成的k 頂點(diǎn)連通無向圖的邊數(shù)小于,大于.在此,簡要介紹k-EC 算法和k-VC 算法,根據(jù)上一節(jié)的分析,算法生成的k 邊/頂點(diǎn)連通無向圖具有k-1 邊/頂點(diǎn)無向抗毀性.

k-EC 算法如算法1 所示.該方法將各條邊的代價(jià)從小到大排序（算法第1 行）,并采用貪婪策略逐一向圖中添加各無向邊；第4 行至第9 行實(shí)質(zhì)上利用了k 邊連通性的傳遞性：即若頂點(diǎn)和之間有k 條邊不相關(guān)的無向通路,頂點(diǎn)和之間有k 條邊不相關(guān)的無向通路,則與之間也存在k 條邊不相關(guān)的無向通路.算法初始時(shí)共設(shè)置個(gè)組,在運(yùn)行過程中確保每組中的任意兩個(gè)頂點(diǎn)之間都有k 條邊不相關(guān)的無向通路,算法利用k 邊連通性的傳遞性合并各組,直到所有的組最終并入同一組中.兩個(gè)頂點(diǎn)之間邊不相關(guān)的無向通路數(shù)目檢測可以采用網(wǎng)絡(luò)最大流算法[17].

算法1 k-EC 算法輸入：一個(gè)無向完全圖都有其相應(yīng)的代價(jià),記作,圖中每一條邊.輸出：一個(gè)k 邊連通無向圖.分到一個(gè)單獨(dú)的組中.1:將初始化：,將每一個(gè)頂點(diǎn)中各條邊按照代價(jià)升序排序2:while do 3: 按序取下一條邊4: if v1 和v2 位于不同的組中then 5: if 在圖中v1 與v2 邊不相關(guān)的無向通路小于k then 6:7: else 8: 將v1 與v2 所在的組合并9:10: end if 11: end if 12:end while

k-VC 算法如算法2 所示.值得注意的是,k 頂點(diǎn)連通性并不具備傳遞性.但k 頂點(diǎn)連通性的一個(gè)性質(zhì)是,若至少有k 個(gè)頂點(diǎn)與和之間的頂點(diǎn)不相關(guān)的無向通路數(shù)均不小于k,則頂點(diǎn)和之間也存在k條頂點(diǎn)不相關(guān)的無向通路.k-VC 算法利用這一性質(zhì)為每一個(gè)頂點(diǎn)建立一個(gè)集合,當(dāng)兩個(gè)集合中有k 個(gè)相同元素時(shí),無需再進(jìn)行頂點(diǎn)不相關(guān)無向通路數(shù)目的檢測.頂點(diǎn)不相關(guān)的無向通路數(shù)目檢測,同樣可以采用網(wǎng)絡(luò)最大流算法.

2 一般的有向抗毀性網(wǎng)絡(luò)

2.1 有向抗毀性網(wǎng)絡(luò)的概念

對(duì)于有向網(wǎng)絡(luò)連接的集群系統(tǒng),為實(shí)現(xiàn)一致性,通常要求網(wǎng)絡(luò)為有根圖.在此基礎(chǔ)上,為保證集群系統(tǒng)在局部通信中斷和部分平臺(tái)損毀等意外事件下仍能正常工作,需要研究具有抗毀性的有根圖網(wǎng)絡(luò),使得在去掉有向圖中的若干邊或頂點(diǎn)之后,依然是有根圖.仿照定義1,可給出對(duì)有向抗毀性網(wǎng)絡(luò)的定義如下.

算法2 k-VC 算法輸入：一個(gè)無向完全圖,圖中每一條邊都有其相應(yīng)的代價(jià),記作.輸出：一個(gè)k 頂點(diǎn)連通無向圖.初始化：,為每個(gè)頂點(diǎn)分配一個(gè)集合.中各條邊按照代價(jià)升序排序2:for 每一條邊1:將do 3: if,并且頂點(diǎn)v1 和v2 在中頂點(diǎn)不相關(guān)的無向通路數(shù)小于k then 4: if v1 和v2 位于不同的組中then 5:6: else 7:8:9: end if 10:end for

本文提出的k 邊/頂點(diǎn)連通有根圖的定義為圖論中的全新概念,目前尚未有關(guān)于此類有向圖性質(zhì)的研究.為此,本節(jié)簡要介紹此類有根圖的性質(zhì).與無向網(wǎng)絡(luò)類似,本文在討論k 頂點(diǎn)連通有根圖時(shí)假定網(wǎng)絡(luò)中頂點(diǎn)的數(shù)目至少為k+1,以保證在去掉網(wǎng)絡(luò)中的k-1個(gè)頂點(diǎn)后,網(wǎng)絡(luò)中至少仍有2 個(gè)頂點(diǎn),從而能夠繼續(xù)分析網(wǎng)絡(luò)中剩余個(gè)體的一致性.

對(duì)于無向網(wǎng)絡(luò)而言,k 頂點(diǎn)連通是一個(gè)比k 邊連通更嚴(yán)格的條件,即若網(wǎng)絡(luò)具有k 頂點(diǎn)無向抗毀性,則其必然具備k 邊無向抗毀性,反之則不然.對(duì)于有向網(wǎng)絡(luò)而言,類比無向網(wǎng)絡(luò),顯然并非所有的k 邊連通有根圖都是k 頂點(diǎn)連通有根圖；但同時(shí),也并非所有的k 頂點(diǎn)連通有根圖都是k 邊連通有根圖.

現(xiàn)討論k 邊/頂點(diǎn)連通有根圖中,k 與各頂點(diǎn)入度及出度的關(guān)系.記為頂點(diǎn)v 的入度,為頂點(diǎn)v 的出度,,

采用同樣的思路可證明式（2）與式（3）成立.證畢.

現(xiàn)討論無向抗毀性與有向抗毀性的關(guān)系.當(dāng)一無向圖的每一條邊替換為方向相反的兩條有向邊后,可以得到一有向圖.而把一k 邊連通無向圖的各邊都替換為方向相反的兩條邊后,得到的有向圖是2k 邊連通有根圖.為證明這一點(diǎn),首先給出如下引理.

由此可得出如下定理.

定理2 所對(duì)應(yīng)的k 頂點(diǎn)版本如下.

定理3 可以很容易證明.現(xiàn)以圖2的例子對(duì)定理2 和定理3 加以說明.圖2左側(cè)的無向圖為2 頂點(diǎn)連通無向圖,當(dāng)其所有的邊替換為方向相反的有向邊后,得到的圖只是2 頂點(diǎn)連通有根圖,若去掉該圖的任意兩個(gè)不相鄰的頂點(diǎn)及與之連接的邊后,將只剩兩個(gè)孤立的頂點(diǎn).根據(jù)命題1,圖2左側(cè)的無向圖也是2邊連通無向圖,當(dāng)其各邊替換為有向邊時(shí),可以驗(yàn)證,去掉任意3 條邊后仍為有根圖,即圖2右側(cè)的圖為4邊連通有根圖.

圖2 2 頂點(diǎn)連通無向圖及替換后的有向圖Fig.2 2-vertex-connected undirected graph and the corresponding digraph after replacing its edges

2.2 有向抗毀性網(wǎng)絡(luò)的生成算法

定理2 和定理3 建立了集群一致性意義下有向抗毀性網(wǎng)絡(luò)與無向抗毀性網(wǎng)絡(luò)之間的關(guān)系,根據(jù)這兩個(gè)定理的分析,可以利用無向抗毀性網(wǎng)絡(luò)的生成算法得到有向抗毀性網(wǎng)絡(luò).

對(duì)于k 邊連通有根圖,本文提出了k-ECRU 算法（k-Edge connected rooted digraphs from undirected graphs）,如算法3 所示.該算法首先使用k-EC 算法生成無向圖,若k 是偶數(shù),則生成k/2 邊連通無向圖；若k 是奇數(shù),則生成（k+1）/2 邊連通無向圖；然后將該無向圖的每一條邊替換為方向相反的兩條有向邊；注意當(dāng)k 為奇數(shù)時(shí),上述步驟得到的實(shí)質(zhì)上是k+1邊連通有根圖,因而此時(shí)再去掉一條代價(jià)最大的邊.采用上述算法即可得到k 邊連通有根圖,該圖具有k+1 邊有向抗毀性.

與k 邊連通有根圖的生成算法類似,對(duì)于k 頂點(diǎn)連通有根圖,本文提出了k-VCRU 算法（k-Vertex connected rooted digraphs from undirected graphs）,如算法4 所示.該算法利用k-VC 算法生成k 頂點(diǎn)連通無向圖,再將該圖的每一條無向邊替換為方向相反的兩條有向邊,即得到k 頂點(diǎn)連通有根圖,該圖具有k+1頂點(diǎn)有向抗毀性.另外,由于k-VC 算法生成的無向圖也是k 邊連通無向圖,因此,根據(jù)定理3,k-VCRU算法生成的有向圖也是2k 邊連通有根圖,具有2k-1邊有向抗毀性.

算法3 k-ECRU 算法輸入：包含n 個(gè)頂點(diǎn)的有向完全圖,圖中每一條邊都有其相應(yīng)的代價(jià),記作.輸出：一個(gè)k 邊連通有根圖.初始化：.1: 將轉(zhuǎn)化為無向完全圖,對(duì)中的每一條邊,設(shè)置其代價(jià)為2:if k 是偶數(shù)then 3: 使用k-EC 算法生成k/2 邊連通無向圖4: 將每一條無向邊替換為兩條有向邊和,得到5:else 6: 使用k-EC 算法生成（k+1）/2 邊連通無向圖7: 將每一條無向邊替換為兩條有向邊和,得到8: 去掉一條中代價(jià)最大的邊,得到.9:end if

算法4 k-VCRU 算法輸入：包含n 個(gè)頂點(diǎn)的有向完全圖,圖中每一條邊都有其相應(yīng)的代價(jià),記作.輸出：一個(gè)k 邊連通有根圖.初始化：.1: 將轉(zhuǎn)化為無向完全圖,對(duì)中的每一條邊,設(shè)置其代價(jià)為2:使用k-VC 算法生成k 頂點(diǎn)連通無向圖3: 將每一條無向邊替換為兩條有向邊和,得到

3 幾類特殊的有向抗毀性網(wǎng)絡(luò)

第2 章針對(duì)集群一致性意義下有向網(wǎng)絡(luò)的抗毀性,提出了k 邊/頂點(diǎn)連通有根圖的概念,并設(shè)計(jì)了用于生成一般的k 邊連通有根圖的k-ECRU 算法和生成一般的k 頂點(diǎn)連通有根圖的k-VCRU 算法.本章在此基礎(chǔ)上,討論k=2 和k=3 這兩種特殊的情形.

3.1 2 邊/頂點(diǎn)連通有根圖

對(duì)于k 邊/頂點(diǎn)連通有根圖,當(dāng)k=1 時(shí),則退化為一般的有根圖.現(xiàn)討論k=2 的情形.

由命題2 可以看出,在k 邊連通有根圖中,對(duì)根頂點(diǎn)和非根頂點(diǎn)的入度有不同的要求.若,則有向圖的每個(gè)頂點(diǎn)都是根頂點(diǎn),相應(yīng)地,有向圖為強(qiáng)連通圖.對(duì)于強(qiáng)連通圖,有如下結(jié)論.

命題3 強(qiáng)連通圖都是2 邊連通有根圖.

反之并不成立,即2 邊連通有根圖并不一定是強(qiáng)連通圖.

另一方面,并非所有的強(qiáng)連通圖都是2 頂點(diǎn)連通有根圖.命題4 給出了一個(gè)比強(qiáng)連通更嚴(yán)苛的條件,以保證有根圖是2 頂點(diǎn)連通有根圖.

現(xiàn)在分析邊數(shù)最少的2 邊/頂點(diǎn)連通有根圖的形式.有如下定理成立.

根據(jù)定理4,邊數(shù)最少且通信代價(jià)最小的2 邊/頂點(diǎn)連通有根圖問題,等價(jià)于求解最小Hamilton 回路的旅行商問題.

3.2 3 邊/頂點(diǎn)連通有根圖

定理4 分析了k=2 時(shí),k 邊/頂點(diǎn)連通有根圖所包含的最少邊數(shù).現(xiàn)分析k=3 的情形.首先考慮3 邊連通有根圖.顯然,只包含2 個(gè)頂點(diǎn)的簡單有向圖至多只有2 條邊,故在討論3 邊連通有根圖時(shí),限定

1）若頂點(diǎn)v*的入度為0,則圖中其他頂點(diǎn)均為非根頂點(diǎn),根據(jù)命題2（a）,這些頂點(diǎn)的入度均不小于3.因此,該情形下.此外,為確保簡單有向圖為3 邊連通有根圖,需保證.

2）若頂點(diǎn)v*的入度為1,由于其他頂點(diǎn)的入度至少為2.因此,.

算法5 3 邊連通有根圖構(gòu)造算法輸入：頂點(diǎn)集.輸出：一個(gè)3 邊連通有根圖.1:生成一個(gè)Hamilton 回路,得到圖2: 向圖中添加所有與中的邊方向相反的邊,得到圖3:去掉中任意一條邊,新的邊集記為,得到

現(xiàn)討論3 頂點(diǎn)連通有根圖所包含的最少邊數(shù).

1）有3 個(gè)頂點(diǎn)的入度恰好為1,并且這3 個(gè)頂點(diǎn)構(gòu)成一條有向回路.在圖中,不能再有由其他頂點(diǎn)指向這3 個(gè)頂點(diǎn)的邊,否則這3 個(gè)頂點(diǎn)的入度會(huì)大于1,不滿足該條件.因而只有這3 個(gè)頂點(diǎn)為有根圖的根頂點(diǎn).此外,除這3 個(gè)頂點(diǎn)外,其余頂點(diǎn)的入度至少為3.為證明這一點(diǎn),記這3 個(gè)根頂點(diǎn)分別為,和,則必存在一頂點(diǎn)以及由某個(gè)根頂點(diǎn)指向頂點(diǎn)的邊.不失一般性,記這條邊為（,）,若頂點(diǎn)的入度僅為2,記指向頂點(diǎn)的另外一條邊為.當(dāng)去掉頂點(diǎn)和及與之相連的邊后,得到的有向圖中,仍然有原有向圖的根頂點(diǎn)和,但并無有向邊指頂點(diǎn),因此,不是有根圖,這與是3 頂點(diǎn)連通有根圖矛盾.因此,頂點(diǎn)的入度至少為3；同樣地,存在頂點(diǎn)v5以及由頂點(diǎn)-中的某個(gè)頂點(diǎn)指向頂點(diǎn)v5的邊,采用同樣的方法可以證明頂點(diǎn)v5的入度至少為3；以此類推,可以證明除3 個(gè)根頂點(diǎn)外,其余頂點(diǎn)的入度至少為3.因此,該情形下,.

2）恰好有2 個(gè)頂點(diǎn)的入度小于2,現(xiàn)證明當(dāng)其余頂點(diǎn)的入度均為2 時(shí),這兩個(gè)頂點(diǎn)的入度均為1.若不然,不妨設(shè)頂點(diǎn)的入度為0,頂點(diǎn)的入度為1.根據(jù)上述分析,；并且除頂點(diǎn)和之外,其余頂點(diǎn)的入度均為2.為保證去掉頂點(diǎn)或或二者同時(shí)去掉后,得到的有向圖仍然是有根圖,則必須有一個(gè)頂點(diǎn)是有向圖的根頂點(diǎn),并且.由于是圖'的根頂點(diǎn),因而存在頂點(diǎn)滿足.由于,則要么,要么.若,則圖去掉頂點(diǎn)和后,得到的有向圖將不再是有根圖,與是3 頂點(diǎn)連通有根圖矛盾.同理,同樣會(huì)與是3 頂點(diǎn)連通有根圖的前提矛盾.因此,該情形下.

算法6 3 頂點(diǎn)連通有根圖構(gòu)造算法輸入：n 個(gè)頂點(diǎn)組成的集合.輸出：一個(gè)3 頂點(diǎn)連通有根圖.1:生成一個(gè)Hamilton 回路,得到圖2:沿Hamilton 回路,將各頂點(diǎn)依次標(biāo)記為,新的邊集記為3:向中逐次添加邊,得到

4 仿真分析

通過一個(gè)典型算例,進(jìn)一步闡釋本文提出的面向集群一致性的網(wǎng)絡(luò)抗毀性概念,以及抗毀性網(wǎng)絡(luò)的設(shè)計(jì)算法.

如圖3（a）所示,100 個(gè)智能體隨機(jī)分布在1 000×1 000 的區(qū)域內(nèi),用智能體兩兩之間的距離表示通信代價(jià),現(xiàn)針對(duì)這些智能體設(shè)計(jì)有向抗毀性網(wǎng)絡(luò).

分別采用k-ECRU 算法和k-VCRU 算法設(shè)計(jì)2邊連通有根圖和2 頂點(diǎn)連通有根圖.對(duì)于2 邊連通有根圖,k-ECRU 算法首先使用k-EC 算法生成一個(gè)1邊連通無向圖,此時(shí),相當(dāng)于使用Kruskal 算法生成一個(gè)最小生成樹,如圖3（b）所示.將這個(gè)無向圖的每一條邊替換為方向相反的兩條有向邊,即得到k-ECRU 算法生成的2 邊連通有根圖,該圖具有1 邊有向抗毀性,但不具備1 頂點(diǎn)有向抗毀性.對(duì)于2 頂點(diǎn)連通有根圖,k-VCRU 算法首先使用k-VC 算法生成一個(gè)2 頂點(diǎn)連通無向圖,如圖3（c）所示.該無向圖具有1 頂點(diǎn)無向抗毀性,將其每一條邊替換為方向相反的兩條有向邊后,即得到k-VCRU 算法生成的2 頂點(diǎn)連通有根圖,該圖既有1 頂點(diǎn)有向抗毀性,也具有3 邊有向抗毀性.圖3（d）為使用蟻群算法得到的最優(yōu)Hamilton 回路,將回路指定方向后對(duì)應(yīng)的有向圖也是最優(yōu)的2 邊/頂點(diǎn)連通有根圖.

圖3 場景設(shè)置及相應(yīng)算法生成的無向圖Fig.3 Simulation settings and the undirected graphs obtained with the corresponding algorithms

表1比較了幾種算法得到的2 邊/頂點(diǎn)連通有根圖.從中可以看出,3.1 節(jié)提出的采用Hamilton回路生成2 邊/頂點(diǎn)連通有根圖的算法,不僅能得到具有1邊和1 頂點(diǎn)有向抗毀性的網(wǎng)絡(luò),也使得網(wǎng)絡(luò)中邊的數(shù)目和總的通信代價(jià)顯著降低.

表1 幾種算法得到的2 邊/頂點(diǎn)連通有根圖比較Table 1 Comparison of the 2-edge-connected and 2-vertexconnected rooted digraphs obtained with different algorithms

進(jìn)一步考慮3 邊/頂點(diǎn)連通有根圖.分別執(zhí)行算法3～算法6,其中,執(zhí)行算法5 時(shí)用到的Hamilton 回路即采用圖3（d）中的Hamilton 回路,算法第3 行去掉的邊選擇代價(jià)最大的邊.執(zhí)行算法6 時(shí)同樣選擇圖3（d）中的Hamilton 回路,第2 行標(biāo)記頂點(diǎn)時(shí)選擇能夠使得總代價(jià)最小的方式.幾種算法最終得到的3 邊/頂點(diǎn)連通有根圖的情況如表2所示.從表中可以看出,除k-VCRU 算法外,其余算法均無法同時(shí)保證2邊抗毀和2 頂點(diǎn)抗毀,但采用k-VCRU 算法生成的有向圖邊數(shù)和總代價(jià)都明顯高于其余三者；而3.2 節(jié)專門針對(duì)3 邊/頂點(diǎn)連通有根圖設(shè)計(jì)的算法5 和算法6 能夠在確保2 邊抗毀或2 頂點(diǎn)抗毀的前提下,顯著降低邊數(shù)和總代價(jià).

表2 幾種算法得到的3 邊/頂點(diǎn)連通有根圖比較Table 2 Comparison of the 3-edge-connected and 3-vertexconnected rooted digraphs obtained with different algorithms

5 結(jié)論

隨著集群系統(tǒng)的不斷發(fā)展及其在作戰(zhàn)領(lǐng)域應(yīng)用的不斷成熟,如何提升集群系統(tǒng)在復(fù)雜條件下的容錯(cuò)性,更好地發(fā)揮集群的優(yōu)勢,成為集群指揮控制領(lǐng)域的一個(gè)重要課題.本文面向一致性這一集群協(xié)同的基礎(chǔ)問題,提出了面向集群一致性的抗毀性網(wǎng)絡(luò)概念,并從圖論的角度,分析了此類網(wǎng)絡(luò)的性質(zhì),并設(shè)計(jì)了抗毀性網(wǎng)絡(luò)的生成算法,提升了集群網(wǎng)絡(luò)的容錯(cuò)性.

本文提出的面向集群一致性的抗毀性網(wǎng)絡(luò)是圖論中的全新概念,本研究還處于起步階段.特別是針對(duì)具有有向抗毀性的k 邊/頂點(diǎn)連通有根圖,分析推導(dǎo)此類網(wǎng)絡(luò)圖結(jié)構(gòu)的更多性質(zhì),并對(duì)k 為一般正整數(shù)時(shí),設(shè)計(jì)更為優(yōu)化的網(wǎng)絡(luò)生成算法將是下一步研究的重點(diǎn).此外,在集群leader-follower 協(xié)同跟蹤等問題中,如何與leader 選擇方法結(jié)合,確保在部分智能體損毀時(shí)具備leader-follower 一致性,同樣是一個(gè)值得研究的問題.