面向集群一致性的抗毀性網(wǎng)絡分析與設計

陳 浩 王祥科 楊 健

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由此可得出如下定理.

定理2 所對應的k 頂點版本如下.

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

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

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

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

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

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

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

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

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

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

3.1 2 邊/頂點連通有根圖

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

由命題2 可以看出,在k 邊連通有根圖中,對根頂點和非根頂點的入度有不同的要求.若,則有向圖的每個頂點都是根頂點,相應地,有向圖為強連通圖.對于強連通圖,有如下結論.

命題3 強連通圖都是2 邊連通有根圖.

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

另一方面,并非所有的強連通圖都是2 頂點連通有根圖.命題4 給出了一個比強連通更嚴苛的條件,以保證有根圖是2 頂點連通有根圖.

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

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

3.2 3 邊/頂點連通有根圖

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

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

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

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

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

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

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

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

4 仿真分析

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

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

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

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

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

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

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

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

5 結論

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

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