基于子網融合的多智能體系統自組網連通性恢復方法

摘 要：在受損的多智能體自組網中，在維持現有連通結構的前提下快速恢復全連通極具挑戰性。為此，提出一種基于子網融合的多智能體系統自組網連通性恢復方法。首先，該方法設計基于網絡故障探測的子網劃分算法來確定系統中的故障節點以及子網割裂情況。其次，該方法在子網內部署領航-追隨者的主從移動模型，從而維持子網內部的穩定性。最后，該方法設計基于強化學習的子網融合算法，根據建立強化學習模型來進行領航者選舉，依據智能體移動距離和智能體能量消耗設計獎勵函數，引導子網完成周期性領航者選舉的動作，領航者帶領追隨者移動實現子網之間的融合，從而實現全網連通性恢復。實驗結果表明，相比于現有方法，該方法在實現連通恢復時所需的時間平均減少了11.3%，系統所產生的能量消耗平均降低了10.58%，證明該方法在效率和能耗方面更具優勢。

關鍵詞：多智能體系統； 連通性恢復； 領航-追隨者； 強化學習

中圖分類號：TP393.03 文獻標志碼：A

文章編號：1001-3695（2024）10-036-3135-06

doi：10.19734/j.issn.1001-3695.2024.03.0040

Self-organized network connectivity recovery method for multi-agentsystem based on subnet fusion

He Xingyua，b， Yu Pingpinga， Yang Guisonga

（a.School of Optical-Electrical & Computer Engineering， b.College of Communication & Art Design， University of Shanghai for Science & Technology， Shanghai 200093， China）

Abstract：It is challenging to quickly restore full connectivity in a damaged multi-agent self-organizing network while maintaining the residual connectivity structure. Therefore， this paper proposed a connectivity restoring method based on subnet fusion for self-organized networks in multi-agent systems. Firstly， the method designed a subnet partition algorithm based on network fault detection， to identify faulty nodes and subnet fragmentation in the system. Secondly， the method deployed a leader-follower mobility model within each subnet to maintain the residual network connectivity. Finally， the method designed a reinforcement learning-based subnet fusion algorithm for leader election， where elected leaders periodically according to a reward function related to mobility distance and energy consumption， being responsible for guiding their followers to move for fusion between subnets. The experimental results show that this method reduces average restoration time by 11.3% and decreases energy consumption by 10.58%， demonstrating its advantages in efficiency and energy usage.

Key words：multi-agent system; connectivity restoration; leader-follower; reinforcement learning

0 引言

多智能體系統因具備較高的自適應性，在眾多實際場景中得到應用，如交通管理［1］、災害救援［2］、物流配送［3］。多智能體群智協同是其系統效率和智能化水平提升的關鍵，且是建立在多智能體系統網絡的穩定連通性基礎之上，連通的重要性體現在信息傳遞與共享［4］、協作［5］以及系統的穩定可靠性上［6］。但在實際應用中，由于智能體自身的能耗有限或者來自外部環境的破壞，多智能體系統中會出現部分節點故障或死亡的情況，從而導致系統網絡的連通性被破壞，割裂成多個無法連通的子網。針對上述情況，現有研究主要從兩個方面對多智能體系統的網絡連通性進行恢復：部署額外的中繼節點以及重新部署健康節點兩種方法。

部署額外的中繼節點方法是通過向損壞網絡系統中的關鍵位置派遣新的中繼節點。文獻［7］通過基于虛擬力量的接力動作和利用分區領導者之間的博弈論來部署額外的中繼節點。文獻［8］通過使用無人機群向孤立的地面網絡補充空中無線鏈路來修復網絡，從空中執行網絡探測，并找出部署后可顯著恢復本地和全局路由性能的關鍵點，文獻［9］提出了一種新的多無人機網絡壽命增強恢復方法，該方法不僅提供了一種路由解決方案，而且還提供了一種故障安全方法。

重新部署健康節點是重新對現有健康節點進行路徑規劃、排序等方式實現網絡連通性恢復。文獻［10］采用分區檢測方法，快速使傳感器意識到網絡中的分區，傳感器利用存儲在每個傳感器處的到匯聚節點的先前路由信息并利用傳感器移動性來聯合分區恢復數據通信。文獻［11］通過模糊邏輯在健康節點中選擇最佳恢復團隊達到恢復連通的目的，文獻［12］通過開發健康節點中的最佳p循環恢復模型來實現網絡恢復。文獻［13］研究了無人機群網絡在不可預測外部破壞下快速重建通信連通性所需要的自愈問題。針對一次性外部破壞和一般化外部破壞，提出了可在線查找無人機群網絡恢復拓撲的圖卷積神經網絡和基于GCN的軌跡規劃算法，使無人機群在自愈過程中重建連通性。

上述第一類方法不需要調整已有的連通結構，相對簡單，但需要相對長的額外節點部署時間，不能對網絡進行實時修復，在實時性要求高的任務場景無法適用。相反地，第二類方法則可以在網絡故障后立即作出網絡連通性恢復響應，但其復雜性更大，具體來說，主要面臨兩大挑戰：a）在調整健康節點位置的同時維持其原有的連通性；b）要兼顧網絡連通性恢復的開銷和速度。

本文主要對第二類方法展開研究。針對該類方法的第一個挑戰，本文將在健康節點組成的子網內引入領航-追隨者［14］模式來保持子網已有的連通性。領航-追隨者模式是編隊控制中的一種常用方法，其將團隊中的一個智能體指定為領航者統一調度其余作為追隨者的智能體的行動，以維持團隊的內部穩定，例如文獻［15］提出了一種領航-追隨者無人機編隊控制規律，將控制和通信約束以平衡的方式結合在一起，實現無人機編隊，又例如文獻［16］通過優化網絡中領航者和跟隨者之間協調控制的代價函數來獲得智能體的控制輸入，保證領航者和跟隨者之間的共識。

針對第二類方法的第二個挑戰，本文將利用強化學習［17］方法來優化多智能體系統網絡連通性恢復過程中的效率和開銷。強化學習是智能體以“試錯”的方式進行學習，通過與環境進行交互獲得的獎賞從而指導行為，該方法已被應用于多智能體系統的協同以完成通信來執行任務，例如文獻［18］采用Actor-Critic強化學習方法解決智能體之間沒有通信的情況下達到共識的目的。又例如文獻［19］提出了災害應急場景下基于多智能體深度強化學習的任務卸載策略，避免動作空間大量無用的搜索。

目前，并沒有相關研究將領航-跟隨者模式以及強化學習方法共同引入網絡連通性恢復過程中。基于上述構思，本文提出了一種基于子網融合的多智能體系統自組網連通性恢復方法。該方法首先設計基于網絡故障探測的子網劃分算法來確定系統中的故障節點以及子網劃分情況，進而在子網內部部署領航-追隨者的移動模型。最后，該方法設計基于強化學習的子網融合算法，根據建立強化學習模型來進行領航者選舉，依據智能體移動距離和智能體能量消耗設計獎勵函數，引導子網完成周期性領航者選舉的動作，領航者帶領追隨者移動實現子網之間的融合，從而實現全網連通性恢復。本文的主要貢獻如下：

a）為了在調整健康節點位置的同時維持其原有的連通性，首先，本文設計基于網絡故障探測的子網劃分方法來確定系統中的故障以及子網割裂情況；然后，在子網中采用領航-追隨者移動控制模型。每個智能體從引發子網割裂的故障消息中找出故障節點的鄰居節點，將它們中位于其他子網的節點其放入候選子目標列表。在實現網絡連通恢復的過程中，領航者會收集到子網追隨者反饋的環境信息（其他子網的智能體，即陌生智能體的位置信息），并將其放入候選子目標列表。領航者選擇候選子目標列表中距離自身最近的智能體作為移動子目標，同時，領航者負責收集追隨者信息和廣播子網狀態信息，追隨者向領航者反饋自身所探測的環境狀態，并且根據鄰居的移動方向均值來更新更新自身的移動方向，從而兼顧了連通性恢復的運行控制和子網內部連通性的維持。

b）為了兼顧網絡連通性恢復的開銷和速度，本文設計了用于領航者選舉的強化學習模型，依據領航者的能量消耗設置個體獎勵以及子網中智能體與子目標的距離平均值設置全局獎勵，使得子網周期性完成一次領航者選舉的動作，選舉結果由當前領航者廣播給追隨者，新的領航者將帶領追隨者朝著新的子目標移動。此外，本文設計了基于子網融合的連通性恢復算法，即在子網移動的過程中，通過周期性更新子網狀態和候選子目標列表，領航者即時廣播狀態信息和子目標信息來促進子網進行融合，從而實現網絡連通性恢復。

1 系統模型

本文構建了一個多智能體系統，包括I個智能體，表示為A={A1，A2，…，Ai，…，AI}，其中第i個智能體表示為Ai（1<i<I），智能體Ai是具有感知、計算、存儲、通信能力的無人車、無人機或機器人，其初始能量為Ei。智能體對應的位置集合為L={L1，L2，…，Li，…，LI}，Li表示智能體Ai的位置。每個智能體有固定的探測半徑R1和通信半徑R2（R1>R2）。

每個智能體周期性與鄰居智能體交換鄰居列表（時間周期為Δt）。智能體Ai的鄰居列表定義為Aneighbori={A1i，A2i，…，Aδi}，其中Ai的第n個鄰居智能體用Ani表示。每個智能體可以通過收集其他智能體的鄰居列表來計算和更新全網的連通性矩陣C，如式（1）所示。

C=CA1，A1…CA1，Ai2…CA1，AICAi1，A1…CAi1，Ai2…CAi1，AICAI，A1…CAI，Ai2…CAI，AI（1）

在矩陣C中，智能體Ai1和Ai2之間的連通性度量用CAi1，Ai2表示，通過式（2）計算獲得。

CAi1，Ai2=∑I-1w=1cwij（2）

cwij為任意兩個智能體Ai和Aj之間的w跳連通性度量，由式（3）迭代計算獲得。

cwij=∑Iy=1cw-1iyc1yj（3）

當w=1時，cwij為任意智能體Ai和Aj之間的直接連通度量，可通過分析鄰居關系直接獲得，若cwij=1，則智能體Ai和Aj之間存在w跳連通，否則不連通。

2 基于網絡故障探測的子網劃分

為了判斷故障智能體是否導致網絡割裂，本文設計基于網絡故障探測的子網劃分算法，如算法1所示。在算法1中，智能體Ai向鄰居智能體發送鄰居列表交互請求后，如果在時間間隔Δt內未收到鄰居智能體Aj的請求確認，則認為智能體Aj發生故障。在探測到智能體Aj發生故障后，智能體Ai會更新鄰居列表，并通過式（2）（3）更新全網的連通性矩陣C，根據該矩陣C判斷網絡是否發生割裂，以及根據該矩陣C從智能體Aj的鄰居表中與自身仍然連通的智能體，將自身和這些智能體放入網絡故障處理候選者列表Aci。

當智能體Ai根據矩陣C發現智能體Aj的故障沒有引發網絡割裂，如果自身的中介度為Aci中最小的（智能體Ai的中心度為其到所在子網其他節點的最小跳數和），則需要自身作為故障處理者負責將子網號不變的故障消息Mimsg沿著最短路徑廣播給其所在子網的其他智能體，否則不做任何處理。

當智能體Ai發現智能體Aj的故障引發了網絡割裂，如果自身比Aci其他故障處理候選者距離Aj更近，則需要作為故障處理者生成包含自身位置和故障探測時間的新子網號，并將包含該新子網號的故障信息Mimsg沿著最短路徑廣播給所在子網的其他智能體，否則不做任何處理。

為了對因節點故障導致網絡割裂而形成的各個子網進行唯一標識，本文將處理網絡割裂的智能體位置和其探測到網絡割裂的時間定義為新產生的子網號。如圖1所示，故障消息Mimsg由以下幾部分組成：消息發送者Ai，消息接收者Aρ（Aρ為Ai所在子網的其他智能體），子網號NtAi（t表示子網劃分時間，Ai表示子網割裂的故障處理者），故障智能體Aj的ID、位置Lj以及鄰居列表Anj。

算法1 基于故障探測的子網劃分算法

輸入：連通矩陣C，故障智能體Aj。

輸出：子網號NtAi。

a）智能體Ai根據故障智能體Aj更新鄰居列表，同時通過式（2）（3）更新連通矩陣C；

b）獲取Aj的鄰居表中與Ai存在鏈路的智能體集合Aci；

c）if網絡未發生割裂then

d） if智能體Ai為Aci中中心度最小的節點 then：

e） 廣播子網號未變化的故障消息Mimsg；

f） end if ;

g）else 網絡發生割裂then

h）智能體Ai為Aci中距離故障智能體Aj最近的智能體， 將自身位置和探測到故障智能體Aj的時間定義為新子網號NtAi，廣播包含新子網號NtAi的故障消息Mimsg；

i）end if;

本文將以圖2的場景為例對上述算法1進行詳細說明。在圖2中，智能體A1～A10之間周期性交互鄰居信息，某時刻，A2、A5、A6和A10無法在規定時間間隔內接收到A1的鄰居消息確認，即檢測到智能體A1故障。A2、A5、A6和A10分別通過式（2）（3）來計算更新全網連通矩陣，判斷網絡已經發生割裂。由于智能體A2和A5相連通且A2比A5離故障節點A1更近，則A2會生成新的子網號NtA2，并把包含NtA2的故障消息MA2msg發送給A3、A4以及A5。A6和A10與A1的其他鄰居節點都不相連通，則各自生成子網號NtA6和NtA10，并將子網號NtA6和NtA10分別發送給A7、A8和A9。

3 基于強化學習的子網融合

3.1 子網中領航者和追隨者定義

1）功能角色 在廣播故障消息結束后，每個子網會啟動領航-追隨者模式來實現網絡連通性恢復。每個子網中會周期性選舉出一個智能體擔任領航者，其余智能體則為追隨者，領航者引導追隨者移動尋找與其他子網的融合機會，在移動過程中，領航者通過強化學習模型得出下一次的領航者選舉決策，將決策結果在子網內廣播。本文設置領航者選舉時間間隔為Δt，即時間間隔Δt內更新一次子網狀態。在子網NtAi中第k次選舉后的領航者標記為leadertAi（k），追隨者定義為follower（g）tAi（k），即子網NtAi第k次選舉后的第g個追隨者智能體。

2）子目標 每個智能體從引發子網割裂的故障消息中找出故障節點的鄰居節點，將它們中位于其他子網的節點其放入候選子目標列表。在實現網絡連通恢復的過程中，領航者會收集到子網追隨者反饋的環境信息（其他子網的智能體，即陌生智能體的位置信息），將其放入候選子目標列表，并將更新后的候選子目標列表廣播給其他追隨者。子網中的領航者將從候選子目標列表中選擇距離自己最近的候選子目標作為實際子目標，并帶領追隨者朝著實際子目標的位置移動。將子網NtAi中第k次選舉后的實際子目標定義為TARtAi（k）。

3）移動模型 在移動過程中，領航者會根據當前子目標的位置進行移動，追隨者則結合領航者共享的子網狀態和鄰居智能體的運動方向來更新自身的運動方向。本文以子網為例說明領航者和追隨者之間的移動模型。在子網NtAi的移動過程中，其領航者智能體NtAi會通過移動子目標的位置獲得移動方向θleadertAi（k），其計算如下：

θleadertAi（k）=atan2（dy，dx）TARtAi（k）（4）

（dy，dx）TARtAi（k）表示當前子網的移動子目標所在的位置，系統中所有智能體速度都為vei。追隨者follower（g）tAi（k+1）的移動方向更新計算如下：

θfollower（g）（k+1）=〈θfollower（g）（k）〉Γ（5）

其中：〈θfollower（g）（k）〉Γ表示子網NtAi中追隨者follower（g）tAi（k+1）的所有鄰居智能體上一輪移動方向的平均值，可由下式計算：

〈θfollower（g）（k）〉Γ=arctan∑j∈Γi（k）sin〈θfollower（j）（k）〉∑j∈Γi（k）cos〈θfollower（j）（k）〉（6）

3.2 基于強化學習的子網領航者選舉

為了提升網絡連通性恢復效率，本文提出用于子網領航者選舉的強化學習模型（圖3），該模型在子網內部的每個智能體上部署，當前輪被選為領航者的智能體通過觀察環境中位于其他子網的陌生智能體作為候選移動子目標，然后在與移動開銷相關的獎勵函數引導下作出下一輪的領航者選擇決策，并且領航者帶領追隨者向著移動子目標移動，直至與其他子網發生融合。強化學習模型的具體定義如下：

a）狀態。子網NtAi中智能體的狀態信息包含子網號、當前子目標、子網中的所有智能體的位置和能量信息，以及候選子目標集合，例如第k輪領航者選舉中的狀態信息定義如下：

s（k）=［NtAi（k），PtAi（k），EtAi（k），TARtAi（k），tartAi（k）］（7）

其中：NtAi（k）表示在第k次領航者選舉時的子網號；PtAi（k）表示子網NtAi所有智能體在第k次領航者選舉時的位置信息集合；EtAi（k）表示子網NtAi中所有智能體在第k次領航者選舉時的剩余能量集合；TARtAi（k）表示第k次領航者選舉時的子目標；tartAi（k）表示第k次領航者選舉時的候選子目標集合。

b）動作。從子網智能體集合中選擇下一輪的領航者，定義為

a（k）=AuNtAi，AuNtAi∈AUNtAi（8）

其中：AUNtAi表示子網NtAi中智能體的集合；AuNtAi表示集合中第u個智能體。領航者的動作是自主選擇，追隨者的動作是由領航者廣播告知。

c）獎勵。本文通過設置獎勵函數引導子網選舉合適的領航者，獎勵函數定義為r（k），表示第k輪選舉所獲得的獎勵，計算如下：

r（k）=λr1（k）+μr2（k）（9）

其中：λ和μ分別代表獎勵值r1（k）和獎勵值r2（k）在總獎勵值的占比權重，兩者和為1。r1（k）為第k輪選舉的領航者能量相關的獎勵，通過第k輪領航者的剩余能量與子網中所有智能體的平均能量差值計算得出，具體如式（10）所示。在第k輪結束時，子網中智能體平均剩余能量定義為Eκt，Ai，領航者智能體Ai的當前剩余能量為Eki。

r1（k）=Eki-Eκt，AiEi（10）

r2（k）是與第k輪選舉后移動子目標位置相關的獎勵，根據第k輪選舉后所有智能體距離移動子目標的總距離與第k-1輪子網中所有智能體距離移動子目標的總距離的差值計算得出，具體如式（11）所示。其中dktar是第k輪選舉后所有智能體距離移動子目標的總距離，dk-1tar是第k-1輪子網中所有智能體距離移動子目標的總距離。

r2（k）=-（dktar-dk-1tar）R2（11）

其中：獎勵r1（k）的設計考慮到了領航者智能體因信息的收集與廣播將消耗比其他智能體更多的能耗；獎勵r2（k）的設計是為了降低連通性恢復的開銷。

3.3 子網融合

為了促進子網融合來實現整個多智能體系統的網絡全連通，本文提出基于強化學習的子網融合算法，如算法2所示。在算法2中，在基于故障探測的子網劃分過程結束之后，各子網探測到故障智能體并啟動領航-追隨者模式進行移動，在子網移動過程中，間隔時間Δt內更新當前子網的狀態和子網連通矩陣，若子網內有智能體探測到陌生智能體，則將探測到的信息反饋給當前領航者，并將探測到的智能體信息存入候選子目標列表中，領航者根據追隨者所反饋的信息更新子網狀態信息，并進行下一輪領航者選舉決策以及將決策結果廣播給子網中其他智能體。當選的領航者在帶領追隨者移動的過程中不斷更新全網連通性矩陣C，通過分析該矩陣探測新故障以及子網融合事件的發生。若探測到子網中出現新故障，則直接重啟該算法；如果探測到發生子網融合，則更新子網號（新的子網號由融合時間以及融合處能量最高的節點決定），并更新移動候選子目標列表（將移動子目候選列表中融合進新子網的智能體刪除，在新子網內交互移動子目候選列表信息，然后再重啟該算法）。

算法2 基于強化學習的子網融合算法

輸入：子網割裂的故障消息以及新子網號。

輸出：全網連通矩陣C。

a）初始化子網狀態；

b）for間隔時間Δt do

c） 更新子網狀態信息；

d） 基于強化學習的領航者選舉；

e） 若被選舉為領航者則帶領子網中追隨者朝著子目標移動，否則作為追隨者；

f）將子網中智能體探測到的陌生智能體存入候選子目標列表；

g）if子網內部發生新的割裂故障then

h） 返回步驟a）；

i）else if子網發生融合then

j） 更新全網連通性矩陣C；

k）更新子網號和候選子目標列表；

l）在新的子網中交換候選子目標列表；

m）連通矩陣C顯示全網未全連通，間隔時間Δt結束返回至步驟c）；

n） end if;

o）end for;

4 強化學習模型的求解

本文采用多智能體深度確定性策略梯度算法（multi-agent deep deterministic policy gradient，MADDPG）［20］對本文強化學習模型求解。MADDPG算法使用Actor-Critic基本框架，采用深度神經網絡作為策略網絡和動作價值函數的近似，使用隨機梯度法訓練策略網絡和價值網絡模型中的參數。在訓練本文定義的模型時需要將動作連續化，輸入的是子網中所有智能體的位置信息、所有智能體的剩余能量、候選子目標列表以及當前子目標，輸出的是選舉出的領導者智能體及子目標位置。

算法3 基于MADDPG的強化學習模型求解算法

a）for episode=1 to M do：

b） 初始化一個用于動作探索的隨機過程Φ；

c） 獲得初始觀察狀態s（k）；

d） for t=1 to T do：

e） ai=μθi（oi）+Φt;

f）執行動作a=（a1，…，aΦ），得到獎勵r（k）和下一個狀態s（k+1）；

g）數據［s（k），a（k），r（k），s（k+1）］存入經驗池D；

h）s（k）←s（k+1）

i）for agent i=1 to I do：

j） 從D中隨機抽取一個數目值為S的樣本集合［s（k）j，a（k）j，r（k）j，s（k+1）j］；

k） yi=rji+γQμ′i［s（k+1）j，a（k+1）1，…，a（k+1）1|a（k+1）w=μ（k+1）w（σjw）

l）最小化損失函數L來更新Critic網絡；

m）L（θi）=1S∑j（yj-Qμi（sj，aj1，…，ajI））2;

n）采用策略梯度更新Actor策略網絡;

o）θiJ≈1S∑jθiμi（oji）aiQμi（sj，aj1，…，ai，…，ajI）|ai=μi（oji）;

p）若智能體Ai為本輪子網中的領航者， 更新智能體Ai的目標網絡;

r）θ（k+1）i←τθ（k）i+（1-τ）θ（k+1）i；

s） end for;

t）end for;

5 實驗及分析

為了評估本文算法的性能優劣，在Python實驗環境中，本文首先對獎勵值收斂性進行了對比和驗證，之后再通過與現有的方法在時間和能耗兩個方面進行對比分析。實驗的主要參數設置如表1所示。

5.1 本文算法性能分析

本文算法考慮到智能體之間的相互作用和協作，智能體共享一個全局的Actor網絡和Critic網絡來學習，在選擇動作時兼顧其他智能體的動作和狀態，使用一個集中的動作-價值函數來評估聯合動作的價值。此外，本文算法的經驗池允許智能體共享和重復使用經驗，智能體可以從其他智能體的經驗中學習，并且可以通過經驗回放緩沖區中的樣本來減少訓練過程中的樣本相關性，這種經驗共享有助于提高智能體學習效率。為了評估本文算法的特性，在實驗過程中以深度確定性策略梯度（DDPG）算法、貪婪算法（Greedy）以及隨機算法（Random）作為獎勵收斂對比，三種方法分別部署在單個智能體上，通過觀察本文算法與三種算法的獎勵值以及獎勵收斂情況來評估本文算法在訓練智能體學習方面的性能。DDPG中的Actor-Critic網絡是單個智能體的，它使用一個單獨的動作-價值函數來評估當前智能體的動作價值，并根據評估出的價值更新策略。貪婪算法通過每次選擇當前最優的解決方案來逐步構建問題的解決過程，它不會進行回溯或全局優化，只關注當前步驟的最優選擇。隨機算法則通過在每一步使用隨機選擇的方法作出決策，通過概率分析，對算法的平均性能進行評估。

從圖4可以得出，通過設置2 000輪訓練迭代過程，本文算法和DDPG的算法性能對于本文研究都展現出較好的效果，但相比于本文算法，DDPG獎勵收斂的值略小于本文算法，并且趨于收斂的迭代次數也要略多于本文算法，而貪婪算法和隨機算法則達不到收斂效果。

5.2 對比算法及實驗指標

為了體現實驗結果的客觀性和準確性，本文以文獻［11，12］中的兩種方法作為對比，對比算法具體如下：

a）分布式節點重定位算法（CoRFL）。CoRFL算法通過模糊邏輯在分區的健康節點中選擇節點來組成恢復團隊實現與部署中心（CoD）的通信，從而實現全網連通性恢復。

b）p循環恢復算法（p-cycle）。p-cycle網絡恢復模型考慮到網絡資源利用率和保護網絡免受故障影響，通過提供環形恢復速度為網絡提供足夠的保護。

為了驗證本文算法對本文場景應用的有效性，從系統總消耗對本文算法和兩種對比算法進行評估。其中系統平均總消耗可以細分為平均時延和平均能量消耗兩項指標，系統平均時延是由在完成連通性恢復過程系統需求的總時間除以子網分區數量得出；系統平均能量消耗是由在完成連通性恢復過程中系統產生的總消耗除以子網分區數量得出。

5.3 對比實驗結果與分析

本文算法與對比算法的系統平均時延消耗如圖5所示。由圖5可知，隨著系統中子網數量的不斷增加，本文算法與兩種對比算法的時延消耗都逐漸增大，p-cycle算法在子網數量規模增大的過程中，系統消耗時長增幅也逐漸增大。CoRFL算法的消耗時長在小規模系統應用中表現效果尚佳，但對于大規模系統所耗費時間逐漸增多。在子網數量從5增加到25時，本文算法的時延消耗增加值大約為500，并且其耗費時長的漲幅也隨著子網數量增加表現出縮小的趨勢，因此本文算法在實現連通性恢復時所耗費的時間方面均優于兩種對比算法，并且隨著系統規模的增大，本文算法與兩種對比算法所耗費時間的差值也有所增大。

本文算法與兩種對比算法的系統平均能量消耗如圖6所示。由圖可知，在實現連通恢復過程中四種方法的系統平均能量消耗值都隨著系統中智能體數量的增加變化幅度較大，p-cycle在實現網絡連通恢復過程中的智能體能量消耗值明顯高于其他三種方法。在子網數量規模較小時，本文算法以及CoRFL所產生的系統消耗相差不大，但隨著子網數量的增多，CoRFL和本文算法消耗的能量增幅較小，并且本文算法在大規模子網系統中所產生的能量消耗小于CoRFL，因此在能量消耗方面，本文算法優于兩種對比算法。

為了展現本文算法相較于兩種對比算法在實現連通恢復過程中的效率優勢，圖7展示了本文算法連通性恢復過程結束時與其他兩種算法的網絡拓撲結構對比（圖中節點則代表智能體）。由圖7可以得出，本文算法相比于兩種對比算法，更早完成網絡全連通恢復，在相同的恢復時間內，本文算法已實現全部連通，不存在割裂子網，而兩種對比算法均存在不同程度的割裂情況，未達到全連通恢復的效果。在恢復的過程中，CoRFL算法更多考慮對節點進行路徑規劃和編隊，其所實現的連通性恢復更趨向于形成一條通信鏈路。p-cycle算法在實現連通恢復的過程中更多考慮避障，節點間會保持最大的安全距離。

此外，由于本文設置的獎勵函數由領航者的剩余能量和與子目標距離兩部分組成，通過設置獎勵函數不同部分的參數來得到最終智能體在時延和能量兩部分的消耗值，如圖8所示。λ是針對能量消耗所設置的獎勵參數，按［0，1］進行取值，可以觀察到，隨著λ參數的增大，系統完成連通性恢復所消耗的能量和時間都出現了先減小后增大的趨勢。在過度追求能耗獎勵的時候，子網會更貪心地選擇剩余能量較多的智能體作為領航者，忽視了對移動子目標的探索，從而增加了系統恢復所消耗的時間，造成系統產生的總能量增加。同樣，在過度追求恢復時間時，在進行領航者切換時忽略了智能體本身所剩余的能量，會導致網絡恢復過程中產生較多的故障智能體，這也為系統的連通性恢復帶來了阻礙，從而增加了系統恢復所需的時間。因此，本文所設計的兩個部分獎勵：能耗獎勵和距離獎勵函數，是息息相關的，兩者呈現出同樣的變化趨勢，只有在兩者權重相同的時候，才能使系統實現網絡連通性恢復所產生的能量消耗和時間消耗達到最優的效果。

6 結束語

為了實現多智能體網絡中的連通性恢復，本文通過在分區中選擇健康節點的方式，提出了一種領航-追隨者模式的網絡連通性恢復方法。首先，通過智能體周期性信息交互確定網絡中的故障區域以及子網劃分情況；然后，結合子網在融合過程中會產生的網絡開銷等提出了基于強化學習的領航-追隨者恢復機制，各子網之間呈現分布式，子網內部采用領航-追隨者模式，通過強化學習不斷去探索更優的恢復策略，選舉出每一輪的最佳領航者。最后，提出子網融合來實現全網連通恢復，在子網連通矩陣發生改變時判斷是否達成全網連通，從而實現全網連通的結果。實驗結果表明，本文方法不僅能有效恢復網絡連通，更適用于較大的網絡系統的連通性恢復。在未來的工作中，將考慮任務環境下的多智能體網絡連通性恢復，節點移動不僅要考慮到實現連通，更要兼顧環境中的任務完成情況。同時，將考慮網絡擁塞、網絡異常流量等因素對網絡連通恢復的影響。

參考文獻：

［1］Xu Jianyou， Zhang Zhichao， Zhang Shuo， et al. An improved traffic signal control method based on multi-agent reinforcement learning［C］//Proc of the 40th Chinese Control Conference. Piscataway， NJ： IEEE Press， 2021： 6612-6616.

［2］Majima T， Takadama K， Watanabe D， et al. Application of multi agent system and transition matrix analysis to logistics system for equal distribution under disaster situation［C］//Proc of the 58th Annual Conference of the Society of Instrument and Control Engineers of Japan. Piscataway， NJ： IEEE Press， 2019： 108-114.

［3］Zhang Jiawei， Chang Cheng， Zeng Xianlin， et al. Multi-agent DRL-based lane change with right-of-way collaboration awareness［J］. IEEE Trans on Intelligent Transportation Systems， 2022， 24（1）： 854-869.

［4］Wang Jie， Li Shaoyuan， Zou Yuanyuan. Connectivity-maintaining consensus of multi-agent systems with communication management based on predictive control strategy［J］. IEEE/CAA Journal of Automatica Sinica， 2023， 10（3）： 700-710.

［5］ElHamamsy A， Aghili F， Aghdam A. Connectivity preservation and collision avoidance in multi-agent systems using model predictive control［J］. IEEE Trans on Network Science and Engineering， 2023， 10（3）： 1779-1791.

［6］Zhou Ruimin， Ji Wenqian， Xu Qingzheng， et al. Collision avoidance and connectivity preservation for time-varying formation of second-order multi-agent systems with a dynamic leader［J］. IEEE Access， 2022， 10： 31714-31722.

［7］Akkaya K， Senturk I F， Vemulapalli S. Handling large-scale node failures in mobile sensor/robot networks［J］. Journal of Network and Computer Applications， 2013， 36（1）： 195-210.

［8］Park S Y， Shin C S， Jeong D， et al. DroneNetX： network reconstruction through connectivity probing and relay deployment by multiple UAVs in Ad hoc networks［J］. IEEE Trans on Vehicular Techno-logy， 2018， 67（11）： 11192-11207.

［9］Bashir N， Boudjit S， Saidi M Y. A distributed anticipatory life-enhancing recovery approach for unmanned aerial vehicular networks［C］//Proc of the 18th IEEE Annual Consumer Communications & Networking Conference. Piscataway， NJ： IEEE Press， 2021： 1-7.

［10］Senturk I F， Akkaya K， Yilmaz S. Relay placement for restoring connectivity in partitioned wireless sensor networks under limited information［J］. Ad hoc Networks， 2014， 13： 487-503.

［11］Baroudi U， Aldarwbi M， Younis M. Energy-aware connectivity restoration mechanism for cyber-physical systems of networked sensors and robots［J］. IEEE Systems Journal， 2020， 14（3）： 3093-3104.

［12］Awoyemi B S， Alfa A S， Maharaj B T. Network restoration in wireless sensor networks for next-generation applications［J］. IEEE Sensors Journal， 2019， 19（18）： 8352-8363.

［13］Mou Zhiyu， Gao Feifei， Liu Jun， et al. Resilient UAV swarm communications with graph convolutional neural network［J］. IEEE Journal on Selected Areas in Communications， 2021， 40（1）： 393-411.

［14］Sader M， Wang Fuyong， Liu Zhongxin， et al. Distributed fuzzy fault-tolerant consensus of leader-follower multi-agent systems with mismatched uncertainties［J］. Journal of Systems Engineering and Electronics， 2021， 32（5）： 1031-1040.

［15］Mukherjee S， Namuduri K. Formation control of UAVs for connectivity maintenance and collision avoidance［C］//Proc of IEEE National Aerospace and Electronics Conference. Piscataway， NJ： IEEE Press， 2019： 126-130.

［16］Cao Lei， Liu Guoping， Zhang Dawei. A leader-follower formation strategy for networked multi-agent systems based on the PI predictive control method［C］//Proc of the 40th Chinese Control Conference. Piscataway， NJ： IEEE Press，2021： 4763-4768.

［17］Liu Chunming， Xu Xin， Hu Dewen. Multiobjective reinforcement learning： a comprehensive overview［J］. IEEE Trans on Systems， Man， and Cybernetics： Systems， 2014， 45（3）： 385-398.

［18］Kandath H， Senthilnath J， Sundaram S. Mutli-agent consensus under communication failure using actor-critic reinforcement learning［C］//Proc of IEEE Symposium Series on Computational Intelligence. Piscataway， NJ： IEEE Press， 2018： 1461-1465.

［19］米德昌， 王霄， 李夢麗， 等. 災害應急場景下基于多智能體深度強化學習的任務卸載策略［J］. 計算機應用研究， 2023， 40（12）： 3766-3771，3777. （Mi Dechang， Wang Xiao， Li Mengli， et al. Task offloading strategy based on multi-agent deep reinforcement learning in disaster emergency scenarios［J］. Application Research of Computers， 2023， 40（12）： 3766-3771，3777.）

［20］Zhao Maomao， Zhang Shaojie， Jiang Bin. Multi-agent cooperative attacker-defender-target task decision based on PF-MADDPG［C］//Proc of the 6th International Symposium on Autonomous Systems. Piscataway， NJ： IEEE Press， 2023： 1-6.