基于任務需求匹配的網絡連通質量控制方法

何杏宇　王怡　楊桂松　賈明權　周玥　徐心玥

摘 要：現有多智能體系統網絡研究方法缺乏對局部網絡質量與區域性任務需求之間的匹配分析，這將影響任務的完成效率和質量，為此提出一種基于任務需求匹配的網絡連通質量控制方法。首先，利用智能體移動狀態分析系統網絡的間歇連通性；然后，結合任務需求以及系統的間歇網絡連通性構建基于主從模式的多智能體子網集合，進而從三個方面評估子網集合的連通質量；最后，提出基于網絡連通質量控制的多智能體移動優化模型，用最大的子網集合連通質量表示多智能體網絡連通質量，在智能體移動距離和網絡連通質量的約束下求解任務完成率最大化的多智能體移動策略，通過該策略形成多智能體網絡以執行任務。實驗結果表明，該方法可以有效控制網絡連通質量，維持任務完成率并提高智能體移動效用。

關鍵詞：多智能體系統；任務需求；網絡連通性分析；網絡連通質量

中圖分類號：TP393.03 文獻標志碼：A 文章編號：1001-3695（2023）10-037-3125-07

doi：10.19734/j.issn.1001-3695.2023.02.0042

Network connectivity quality control method based on matching task requirement

He Xingyu1a，1b，Wang Yi1a，Yang Guisong1a，Jia Mingquan2，Zhou Yue1b，Xu Xinyue1b

（1.a.School of Optical-Electrical & Computer Engineering，b.College of Communication & Art Design，University of Shanghai for Science & Technology，Shanghai 200093，China；2.Southwest China Institute of Electronic Technology，Chengdu 610036，China）

Abstract：The existing multi-agent network researches ignore the matching between qualities of local networks and the requirements of regional tasks，which influences task completion efficiency and quality.In view of this，this paper proposed a network connectivity quality control method based on matching task requirement.Firstly，this method analyzed the intermittent connectivity of multi-agent network by using states of agents.Secondly，it constructed a subnet set based on leader-follower model to execute tasks，according to the requirements of tasks and the intermittent connectivity of network，and it further evaluated the connectivity quality of the subnet set.Finally，this method designed a multi-agent mobility optimization model based on network connectivity quality，in which the maximum connectivity quality of subnet set represented to the network connectivity quality.Under the constraints of agents mobile distance and network connectivity quality，this model obtained multi-agent mobility strategy with optimal task completion rate.Experimental results verify that the proposed method can effectively control the network connectivity quality，maintain the task completion rate and improve the mobile utility of agents.

Key words：multi-agent system；task requirement；network connectivity analysis；network connectivity quality

0 引言

隨著通信控制、人工智能、工業制造等諸多領域的快速發展，多智能體系統已經成為一個新的研究熱點。因具有低人力成本、快速處理大量數據、高效智能自主決策等優點，被廣泛應用于軍事作戰［1］、環境監測［2］、智能交通［3］和智慧工廠［4］等場景。在上述場景中，多智能體形成連通的網絡以交互信息從而協同完成任務。為了保證任務完成效率和質量，如何調整多智能體網絡的連通性以匹配任務需求是多智能體系統中的一個關鍵問題。從網絡連通性的角度分析，現有的多智能體網絡可以分為持續連通網絡和間歇連通網絡。

持續連通的多智能體網絡在執行任務時具有可靠性和穩定性，現有研究的目標可分為維持網絡持續連通性和連通性約束下優化多智能體協同執行任務的過程。前者通過同步、跟蹤的方式保證網絡持續連通［5，6］；后者在全局連通性［7～9］或局部連通性［10］的約束下，改變多智能體的網絡連通性以協同執行任務。但是在實際執行協同任務的過程中存在智能體移動性和惡劣環境等因素的限制，使多智能體網絡很難保持持續連通，同時持續連通網絡的部署維護成本高且智能體的移動距離受限，將導致其無法高效執行任務。

為克服持續連通網絡中存在的問題，現有研究利用網絡的間歇連通性執行任務。間歇連通的多智能體能夠靈活地組網以完成任務，現有研究的目標可分為實現多智能體共識［11，12］和探索任務環境以協同執行任務［13～15］。前者為了解決間歇連通多智能體的信息滯后問題，在某種共識下智能體之間及時通信并共享信息以協同完成任務；后者放寬智能體移動范圍，無須時刻保持多智能體的網絡連通性就能協同完成任務。但是，間歇連通的多智能體之間通信不穩定，難以形成可靠的通信鏈路和穩定的多智能體網絡，這將影響任務完成效率。為了提高間歇連通網絡的穩定性，現有研究提出了周期性間歇連通網絡，該網絡通過控制網絡節點的移動軌跡來實現。文獻［16］提出了具有彈性共識的多智能體時變通信方法，多智能體沿著路徑移動，在組內或組間形成周期性的通信。文獻［17，18］對間歇連通智能體的移動進行約束，令智能體沿環形軌跡運動，使智能體之間的通信具有周期性。

然而，現有的周期性間歇連通網絡研究大多關注的是全局網絡連通性，較少關注局部網絡連通性以及局部網絡連通性與任務的匹配情況，這將影響多智能體的任務完成效率和質量。多智能體網絡與以數據傳輸為主要目的的網絡不同，后者通過關注全局網絡連通性充分利用整個網絡中存在的數據傳輸路徑以提高數據傳輸性能，而前者是面向任務需求實現組網，任務的執行情況與覆蓋該任務的局部子網密切相關。

鑒于現有研究中缺乏針對任務需求匹配的局部網絡性能分析方法，本文提出了基于任務需求匹配的網絡連通質量控制方法。根據任務所在位置和任務所需智能體數量來調整智能體的移動狀態，令其形成匹配任務需求的多智能體子網集合以協同執行任務。首先分析多智能體系統的間歇網絡連通性；然后，根據任務需求構建基于主從模式的多智能體子網集合來執行任務，進而從子網集合與任務需求的匹配度、子網集合的穩定性和子網集合中智能體的負載三個方面評估子網集合的連通質量；最后提出一種基于網絡連通質量的多智能體移動優化模型，用最大的子網集合連通質量表示多智能體網絡連通質量，在智能體移動距離和網絡連通質量的約束下最大化任務完成率。本文為了匹配多智能體局部網絡的質量和區域性任務的需求，根據任務所在位置和所需智能體數量構造基于主從模式的子網集合，由子網中智能體協同執行任務；為了保證任務完成效率和質量，提出了一種基于任務需求匹配的網絡連通質量控制方法。

1 系統模型

本文構建了一個多智能體系統模型，多智能體之間形成周期性間歇連通網絡以執行平臺發布的任務，其應用場景如圖1所示。其中，平臺根據任務需求和智能體的當前位置對智能體的移動狀態進行調整，以形成與任務需求匹配的周期性間歇連通子網集合。具體地，平臺從環境中收集任務信息和多智能體移動狀態，分析多智能體網絡的連通質量，在智能體移動距離和網絡連通質量的約束下求解任務完成率最大化的多智能體移動狀態；平臺將該移動策略傳遞給多智能體網絡，多智能體網絡在執行任務后向平臺反饋任務執行結果。

1.1 智能體

系統中存在一組智能體，N個智能體構成智能體集合為V={v1，v2，…，vi，…，vN}。其中，智能體的通信距離為Δ。這些智能體在時段Tk內沿環形軌跡移動，形成周期性間歇連通的多智能體網絡。相比于在網絡中被視做一個隨機移動的點，沿環形軌跡移動的智能體將獲取更多的連通機會和更廣的連通范圍。在時段Tk-1的初始時刻tk-1采樣智能體移動狀態Sk-1，為匹配任務需求，在時刻tk智能體的移動狀態調整為Sk。在時刻tk，多智能體移動狀態的集合為Sk={sk1，sk2，…，ski，…，skN}，其中，智能體vi的移動狀態ski由其所處環形軌跡的圓心位置oki和軌跡上的移動相位ωki組成，即ski={oki，ωki}。具體地，圓心位置oki∈L處于網格內部，移動相位ωki={0°，90°，180°，270°}有四種狀態。對于任意智能體，有相同的軌跡半徑r和軌跡上智能體移動速度sp，且智能體沿順時針方向移動。

1.2 任務

在時刻tk，系統中存在一系列任務，M個任務的集合為A（k）={ak1，ak2，…，akj，…，akM}。其中，任務akj所在位置為apkj，且需要ankj個智能體協同完成。在時段Tk，多智能體組成網絡執行任務集合A（k）中的任務。為了可靠地完成任務，多智能體網絡需要保證穩定通信，即智能體之間連通時長超過τ。當執行任務akj的多智能體子網中存在圓心位置與任務位置重合的領隊智能體、與平臺直接連通的智能體，且子網中智能體的數量滿足任務需求時任務被完成。

1.3 平臺

本文搭建了集中控制平臺，平臺調整智能體的移動狀態以協同執行任務。根據調整后多智能體的移動狀態分析多智能體的網絡連通性，從所有智能體中選擇部分智能體組成子網以協同執行任務，并將任務執行結果傳遞回平臺。在調整的過程中，關注智能體的移動距離、任務完成率和網絡連通質量以高質量、高效率地完成任務。具體來說，為滿足時段Tk內的任務需求，平臺在時刻tk調整智能體移動狀態為Sk，智能體在時段Tk內按調整后的軌跡移動。另外，本文定義平臺所在位置為PPF，同時假設智能體調整移動狀態的時間忽略不計。

舉個例子，假設網格的大小為6×6，平臺所在位置為（3，3），如圖2中藍色方形所示（參見電子版）。存在智能體集合V={v1，v2，v3，v4，v5}，如圖2中綠色圓形所示，其移動軌跡半徑為1個單位，軌跡上的移動速度為1周/Δt。平臺未發布任務時，智能體按照上一時段執行任務的軌跡移動，如圖2（a）所示。在時刻tk，平臺發布任務，為滿足任務需求，智能體移動狀態由圖2（a）調整為圖2（b），在時段Tk，智能體按照圖2（b）中的軌跡移動以協同完成任務。調整智能體的移動狀態時，考慮任務完成率和智能體的移動距離，關注執行任務的子網的網絡連通質量，形成滿足當前任務需求的多智能體網絡。具體地，在時刻tk，平臺發布任務ak1，任務所在位置為（5，4），需要兩個連通的智能體協同完成，如圖中紅色三角形所示。分析圖2（a）中智能體與任務的距離，選擇智能體v2作為領隊直接執行任務ak1。在時段Tk，為了滿足任務需求且減小智能體移動距離，智能體v2和v4組成子網在整個時段內保持連通且與平臺連通以執行任務，智能體v1、v3和v5保持原有移動軌跡，如圖2（b）所示。此時，每個智能體完成任務ak1的移動距離分別為{0，1，0，2，0}。

為調整多智能體的移動狀態以保證任務完成效率和質量，本文分析多智能體組成網絡協同執行任務的情況。主要變量符號及含義如表1所示。

2 多智能體系統的間歇網絡連通性分析

為分析多智能體網絡的連通性，平臺根據智能體的移動狀態計算時段內智能體之間的連通時長，篩選穩定的智能體連通邊構成穩定通信的周期性間歇連通的多智能體網絡，并獲得該網絡的連通矩陣。為執行任務，多智能體網絡中智能體移動狀態如圖3（a）所示，對應的網絡連通圖如圖3（b）所示。

a）根據智能體的移動狀態Sk計算時段Tk內智能體的位置。在時刻tk，智能體vi的環形軌跡圓心為oki、軌跡上移動相位為ωki、智能體軌跡半徑為r且在軌跡上的移動速度為sp。在時段Tk內的任意時刻t，智能體vi的實時位置pti計算如下：

利用智能體的實時位置和智能體的通信距離判斷智能體之間的連通性。通過式（1）（2）計算時刻t智能體vi1和vi2的實時位置pti1和pti2。當兩智能體之間的距離小于智能體的通信距離Δ，則認為智能體vi1和vi2在該時刻連通，由此得到兩智能體連通的時刻。

b）本文定義了多智能體網絡的連通圖。在時段Tk，多智能體網絡的連通圖為Gk=（V，Ek），其中，節點集合V包含了N個多智能體，即V={v1，v2，…，vi，…，vN}，邊集合Ek包含了任意兩節點之間的連通邊，即Ek={Ek1，2，Ek1，3，…，EkN-1，N}。其中，智能體vi1和vi2之間連通邊的集合為Eki1，i2={ei1，i2（ti1，i2，ti1，i2）}，ti1，i2表示兩智能體開始連通的時刻，ti1，i2表示兩智能體結束連通的時刻。若兩智能體在一個時段內多次連通，則集合中存在多條邊。

c）為了保證智能體之間通信的穩定性，從多智能體網絡連通圖中篩選滿足智能體信息傳輸時長的連通邊，獲得穩定通信的多智能體網絡的直接連通性。因此，本文定義了多智能體網絡的直接連通矩陣如式（3）所示。

其中：c（1）i1，i2（k）表示智能體vi1和vi2在該時段內是否具有穩定的直接連通性。如式（4）所示，如果在兩智能體連通邊的集合Eki1，i2中，最大連通時長的連通邊滿足智能體信息傳輸時長τ的要求，認為兩智能體之間具有穩定的直接連通性。

其中：cglobali1，i2（k）表示智能體vi1和vi2在該時段內是否具有連通性。通過多智能體網絡的直接連通矩陣C（1）（k）的自乘，計算h跳連通矩陣C（h）（k），累加多跳連通矩陣中兩智能體之間的連通性，判斷智能體之間的連通性，如式（6）所示。

另外，在多智能體網絡的連通矩陣中智能體不存在自連通性，即連通矩陣對角線的值為0。

3 基于任務需求匹配的子網連通性質量分析

3.1 基于主從模式的子網構建

利用上文中多智能體網絡的連通矩陣Cglobal（k），從智能體集合V中選擇部分智能體組成多智能體子網以協同執行任務。為了提高多智能體組網效率，本文基于主從模式構建子網，子網中包含了領隊智能體和追隨者智能體。

在時段Tk內存在任務akj，定義執行該任務的多智能體子網為（Gsub）kj=（Vkj，Ekj）。其中，子網中智能體的集合為VkjV，子網中智能體之間連通邊的集合為EkjEk。在子網的智能體集合中，包含了領隊智能體leaderkj和追隨者智能體集合followerkj。此外，為執行任務集合A（k），從智能體集合中選擇多組形成智能體子網集合（Gsub）k。

3.1.1 領隊智能體

在時刻tk，為穩定地執行任務akj，要求調整移動狀態后領隊智能體leaderkj的圓心okleaderkj與任務位置apkj重合。因此，根據調整前智能體的位置pk-1i選擇調整距離最小的智能體作為領隊智能體，根據上一時段采樣的智能體移動狀態Sk-1，計算在時刻tk-1智能體的實時位置pk-1i。

在時刻tk，為執行M個任務A（k），選擇領隊智能體集合Leaderk，如式（7）所示。為提高任務完成率并保證任務完成質量，智能體可在不同子網中執行任務，但不能同時作為領隊智能體執行多個任務，即領隊智能體集合中元素不重復。

3.1.2 追隨者智能體

為執行任務akj，在確定領隊智能體leaderkj，后選擇追隨者智能體集合followerkj與其組成子網（Gsub）kj執行任務。在選擇追隨者智能體時，考慮子網中智能體之間的連通性、智能體的數量和追隨者智能體的多種選擇方式。

a）判斷子網的智能體集合Vkj中所有智能體是否具有連通性，如式（8）所示。對于子網智能體集合中任意智能體vi，利用式（4）判斷集合中是否有其他智能體v與其直接連通。

b）為了減少資源浪費并最大限度滿足任務需求，多智能體子網（Gsub）kj中智能體的數量不超過任務需求ankj，即追隨者智能體的數量不超過ankj-1。

c）為匹配任務需求，存在多種追隨者智能體followerkj的選擇方式。如圖4所示，假設任務a12需要四個智能體協同完成，其中，智能體v2作為領隊智能體leader12存在兩種追隨者智能體集合可以滿足任務需求，即智能體v1、v3和v4作為追隨者智能體集合follower12，或智能體v3、v4和v5作為追隨者智能體集合follower12。選擇哪種追隨者集合組成子網以執行任務，需要匹配多任務需求，評估執行多任務的子網集合的連通質量，將在后文詳細闡述。

3.1.3 判斷子網是否成立

在匹配任務需求前需要判斷子網是否成立，具體地，除了子網中智能體之間具有連通性和子網中存在領隊智能體外，還要求子網中存在與平臺穩定連通的智能體，將完成的任務傳遞回平臺。

在時段Tk內，為獲取平臺與智能體的穩定連通性，利用式（1）（2）計算智能體vi的實時位置，當智能體位置pti和平臺位置pPF的距離小于智能體通信距離Δ時，智能體與平臺連通。據此可知，智能體與平臺在時刻tPF，i開始連通，在時刻tPF，i結束連通。為保證平臺與子網穩定的連通性，要求智能體與平臺的連通時長超過信息傳輸時長τ。因此，在平臺與智能體穩定的直接連通性（CPF，V）（1）（k）中，智能體vi與平臺穩定的直接連通性（cPF，V）（1）PF，i（k）如式（9）所示。

綜上所述，從三個方面判斷多智能體子網（Gsub）kj是否能執行任務akj，即子網中智能體具有連通性、存在領隊智能體leaderkj和與平臺穩定連通的智能體vi，如式（10）所示。

3.2 基于任務需求匹配的子網連通性質量評估

為分析局部網絡質量與區域性任務需求之間的匹配情況，本文定義子網集合的連通質量。子網集合的連通質量除了與任務需求的匹配度有關，子網的性能也對其有重要影響。具體地，網絡性能指標包括網絡連通時長［19］、負載均衡［20］和網絡穩定性［21］等。本文從子網集合與任務需求的匹配度、子網集合的穩定性、子網集合中智能體的負載三個方面評估子網集合的連通質量。

具體地，在當前智能體移動狀態Sk下，子網集合（Gsub）k的連通質量Q（Gsub）k受子網集合與任務需求的匹配度TND（Gsub）k、子網集合的穩定性NS（Gsub）k以及子網集合中智能體的負載NL（Gsub）k的影響，子網集合的連通質量越高，多智能體越能高質量、高效率完成任務。參數α、β和γ調節上述三種因素對子網集合連通質量的影響程度。

3.2.1 子網集合與任務需求的匹配度

子網集合與任務需求的匹配度TND（Gsub）k是指多智能體子網集合（Gsub）k滿足任務集合A（k）中任務需求的程度。其中，任務akj需要ankj個智能體協同完成，執行該任務的多智能體子網（Gsub）kj中智能體數量為|Vkj|，任務需求和子網的匹配度為TND（Gsub）k，如式（12）所示。同時，子網集合應可執行該任務，如式（13）所示。

當多智能體子網集合（Gsub）k執行任務集合A（k）中所有任務時，任務需求和子網集合的匹配度為TND（Gsub）k，如式（14）所示。

3.2.2 子網集合的穩定性

子網的穩定性NS（Gsub）k是指多智能體網絡中連通邊有一定的概率被破壞，在這種情況下子網集合執行任務的情況。多智能體網絡中子網執行任務時，如果某條連通邊因障礙物或網絡傳輸等原因被破壞，可能無法維持原有的任務完成效率。當智能體vi1和vi2之間的連通邊ei1，i2（ti1，i2，ti1，i2）被破壞，子網（Gei1，i2sub）kj是否能執行任務akj用T（Gei1，i2sub）kj表示，通過式（10）判定子網是否能執行任務。

多智能體網絡中任意連通邊有一定概率pd被破壞，在這種情況下，多智能體子網集合（Gsub）k執行任務時的網絡穩定性用NS（Gsub）k表示，如式（15）所示。其中，需要利用多智能體網絡的連通矩陣Cglobal（k），統計多智能體網絡中連通邊的數量Enk，如式（16）所示。

3.2.3 子網集合中智能體的負載

子網集合中智能體的負載NL（Gsub）k是指智能體所在子網的數量。如果一個智能體參與過多任務，該智能體需要傳輸大量數據，將難以維持任務完成質量，因此規定智能體的最大負載為Lmax。利用子網集合（Gsub）k計算智能體vi的負載L（Gsub）ki，進而統計符合負載要求的智能體的比例NL（Gsub）k，如式（17）所示。

4 基于網絡連通質量控制的多智能體移動策略

4.1 基于網絡連通質量控制的多智能體移動優化模型

本文對智能體的移動過程進行建模，在智能體移動距離和多智能體網絡連通質量的約束下最大化任務完成率。

本文用最優的子網集合連通質量表示多智能體網絡連通質量。具體地，在當前智能體移動狀態Sk下，有多種子網集合的選擇方式，通過評估每種智能體子網集合的連通質量求解連通質量最優的子網集合（Gsub）k。用該子網集合的連通質量Q（Gsub）k表示多智能體網絡連通質量Q（Gk）。

為執行任務A（k），智能體的移動狀態從Sk-1調整為Sk的移動距離集合為D（Sk）={d（Sk）1，d（Sk）2，…，d（Sk）N}。在智能體的移動狀態Sk下，從多智能體網絡Gk中選擇連通質量最優的多智能體子網集合（Gsub）k來完成任務，利用式（14）計算該子網集合和任務需求的匹配度TND（Gsub）k，即當前狀態下多智能體的任務完成率TCR（Sk）。

多智能體移動優化模型的優化目標是最大化任務完成率，得到最優的多智能體移動策略。在智能體移動距離和網絡連通質量的約束下求解任務完成率最優的多智能體移動狀態（Sk），優化目標如下：

其中：約束式（20）表示智能體的最大移動距離為dmax，約束式（21）表示多智能體網絡連通質量的閾值為Qthreshold，通過控制網絡連通質量以保證任務完成質量。

4.2 基于網絡連通質量控制的多智能體移動優化模型求解

為保證任務完成效率和質量，獲得網絡連通質量控制下任務完成率最優的多智能體移動狀態，本文設計了基于網絡連通質量控制的多智能體移動優化模型，采用能處理高復雜度組合問題的模擬退火算法求解。在求解過程中，為獲取多智能體網絡連通質量，采用遺傳算法求解。

a）多智能體移動狀態編碼。采用實數編碼的方式對多智能體移動狀態編碼，將調整前多智能體移動狀態Sk-1編碼為Y（Sk-1），調整后多智能體移動狀態編碼為Y，狀態由移動軌跡圓心和移動相位組成，編碼的長度為3N，編碼方式為Y={（ok1（x），ok1（y），ωk1），…，（okN（x），okN（y），ωkN）}。具體如算法2所示。

b）初始化解狀態。為了加快收斂并提高算法效率，優先選擇領隊智能體集合并固定領隊的圓心位置，在此基礎上形成多智能體的移動狀態。

c）計算多智能體網絡連通質量。為篩選符合約束條件的解狀態，需要求解當前多智能體移動狀態下連通質量最優的子網集合和對應連通質量，即網絡連通質量。詳細過程如算法1所示。

（a）子網集合編碼。采用0-1編碼的矩陣表示多智能體子網集合執行任務的情況，矩陣X的行和列分別對應N個智能體和M個任務，矩陣中元素Xi，j為0或1。在矩陣X的第j列中，元素值為1的智能體的集合是執行任務akj的多智能體子網。

（b）初始化種群。初始化種群是在搜索開始時生成一組染色體，種群規模為Popsize，其中染色體為X1～XPopsize。為執行任務akj，根據當前多智能體移動狀態Y分析網絡連通性，從領隊智能體leaderkj連通的智能體中，選擇追隨者智能體集合組成子網（Gsub）kj，進而得到執行任務A（k）的子網集合（Gsub）k，子網集合（Gsub）k編碼后即為一條染色體Xps。

（c）適應度函數。分析染色體Xps的連通質量，網絡連通質量越大，適應度越好。因此染色體Xps的適應度函數計算為

算法1 網絡連通質量求解算法

輸入：多智能體移動狀態集合Y。

輸出：當前狀態下，最優子網集合X，網絡連通質量F1（X）。

1 初始化種群，產生滿足約束條件的染色體X1～XPopsize；

2 初始化迭代次數，令iter=0；

3 根據式（23）計算種群中染色體的適應度；

4 更新當前最優個體X；

5 采用輪盤賭方法選擇適應度高的染色體；

6 對選擇的染色體進行交叉操作；

7 對選擇的染色體進行變異操作，即個體中的值有一定概率發生突變；

8 令iter=iter+1，達到閾值停止迭代，否則跳到步驟1；

9 輸出最優子網集合X和對應連通質量，即網絡連通質量F1（X）。

d）目標函數。在求解最優多智能體移動狀態的過程中，關注多智能體的任務完成率，計算最優子網集合的任務完成率。為評價新解和當前解的優劣，設計目標函數F2（Y），目標函數計算為

算法2 多智能體移動優化算法

輸入：任務集合A（k），調整前多智能體移動狀態集合Y（Sk-1）。

輸出：調整后最優多智能體移動狀態集合Y。

1 根據式（7）選擇領隊智能體集合Leaderk，確定其調整后軌跡圓心；

2 初始化迭代溫度temp=temp（0），根據算法1計算網絡連通質量，初始化滿足約束式（20）和（21）的解狀態Y；

3 初始化迭代次數，令iter_temp=0；

4 對當前解Y中部分元素進行突變或交換，產生滿足約束式（20）和（21）的新解Y′，解的變換范圍滿足多智能體移動狀態的約束；

5 根據式（24）中目標函數計算新解的增量ΔF2=F2（Y）-F2（Y′ ）；

6 若ΔF2<0，接受Y′ 作為新的當前解，否則以exp{-ΔF2/temp}的概率接受新的當前解；

7 令iter_temp=iter_temp+1，達到閾值停止迭代，否則跳到步驟1；

8 更新溫度，令溫度按照一定的比例逐漸減少，temp=temp·；

9 輸出最優解Y。

在算法1中，計算染色體適應度函數的時間復雜度為O（N2M），求解網絡連通質量的時間復雜度為O（N2M·Popsize）。其中，迭代次數iter為常數。在算法2中，選擇領隊智能體集合的時間復雜度為O（NM），計算目標函數的時間復雜度為O（N+M），求解最優多智能體移動狀態集合的時間復雜度為O（N2M·Popsize·iter_temp）。其中，溫度temp更新到閾值的迭代次數為iter_temp，內循環迭代次數iter_temp為常數。

5 實驗分析

本文通過上述基于網絡連通質量控制的多智能體移動策略實現基于任務需求匹配的網絡連通質量控制方法。為評價本文方法，在Python中對相關方法進行實驗仿真，相關參數如表2所示。

5.1 對比方法和實驗指標

本節將本文方法與現有的兩種方法進行對比并進行實驗仿真。其中，方法1是文獻［9］采用多智能體保持持續連通以執行任務的方法，方法2是文獻［15］利用多智能體的間歇連通以執行任務的方法。為了分析網絡連通質量控制對本文方法的影響，將對比不考慮網絡連通質量控制的多智能體周期性間歇連通執行任務的情況，即方法3。

為了設置本文方法中網絡連通質量的閾值，對比不同閾值下任務數量的變化對任務完成率的影響；為了驗證本文方法的有效性，從任務完成率、網絡連通質量和多智能體移動效用三項指標對本文方法和對比方法進行評價，分析任務數量對實驗指標的影響。具體地，任務完成率是指多智能體組成網絡完成任務的程度，通過最優子網集合中智能體的數量除以任務需求得出；網絡連通質量綜合分析多智能體組成網絡執行任務的情況，通過結合子網集合與任務需求的匹配度、子網集合的穩定性和子網集合中智能體的負載得出；智能體移動效用是指智能體移動一個單位距離得到的任務完成率，通過任務完成率除以平均每個智能體移動距離得出。

5.2 實驗結果分析

5.2.1 網絡連通質量閾值分析

通過控制網絡連通質量以提高任務完成質量，網絡連通質量閾值對任務完成率的影響如圖5所示。在實驗中，設置不同的網絡連通質量閾值（即Q= 0.1、0.2、0.3、0.4、0.5、0.6）分別分析任務完成率，最終設置網絡連通質量的閾值為0.6。

如圖5所示，隨著任務數量的增加，任務對智能體的需求增加，多智能體的任務完成率隨之降低。網絡連通質量的閾值越高，多智能體網絡與任務需求的匹配度越高，任務完成率越高。當Q=0.1時，難以對多智能體網絡產生有效約束，因此任務完成率較低；當Q=0.2、0.3、0.4、0.5時，多智能體通過移動達到連通質量的閾值較為容易，因此任務完成率相近，使多智能體網絡性能的控制提高不明顯；當Q=0.6時，任務完成率有所提高。過低的網絡連通質量使多智能體網絡的連通性無法滿足任務需求，任務完成率低；過高的網絡連通質量要求多智能體網絡結構穩定，即智能體相對聚集執行任務，同時要求多智能體網絡滿足任務需求，但環境中智能體數量固定，而智能體聚集導致分散的任務無法執行。因此，網絡連通質量的閾值在達到0.6后難以提高。

5.2.2 不同方法的任務完成率

本文方法與三種對比方法的任務完成率如圖6所示。隨著任務數量增加，任務所在范圍更廣、對智能體的需求更大，使各方法的任務完成率逐步下降。由圖6可知，本文方法的任務完成率略低于方法1的任務完成率，因為相比于本文方法，方法1的網絡連通性約束更強，智能體在較大的范圍內保持連通，更容易滿足任務需求；在方法2中，多智能體之間間歇連通，任務數量少時智能體靈活移動以獲得較高任務完成率，隨著任務數量增加，智能體無法組成滿足任務需求的多智能體網絡，使任務完成率下降明顯；本文方法和方法3均為周期性間歇連通網絡，任務完成率的降低趨勢相似。該網絡擴展多智能體連通范圍，因此相較于方法2，本文方法和方法3的任務完成率下降趨勢平緩，但方法3沒有控制網絡連通質量，難以高效匹配多智能體網絡和任務需求，導致無法提高任務完成率。

5.2.3 不同方法的網絡連通質量

本文算法與三種對比方法的網絡連通質量如圖7所示。在任務數量較少時，網絡連通質量均大于0.6，隨著任務數量的增加，多智能體網絡難以在滿足任務需求的同時維持較高的網絡性能，因此本文算法和三種對比方法的網絡連通質量不斷降低。由于本文方法設置網絡連通質量的閾值為0.6，當任務數量增加時，本文方法的網絡連通質量下降后趨于平穩，實驗效果優于對比方法。

在未控制網絡連通質量時，隨著任務數量的增加，網絡逐漸難以滿足任務需求，網絡的穩定性下降。方法1中多智能體保持持續連通，當任務數量達到25時，多智能體網絡的穩定性變化不明顯，智能體分布范圍相對變大，多智能體的負載更均衡，網絡連通質量維持在0.45左右；方法2中多智能體之間間歇連通，當任務數量達到20時，網絡穩定性不再明顯降低，相較于方法1，該方法的網絡穩定性和任務完成率更低，網絡連通質量維持在0.35左右；方法3中的多智能體周期性間歇連通，隨著任務數量增加，多智能體網絡可以維持一定的穩定性，但相較于持續連通網絡仍有一定劣勢，最終網絡連通質量逐漸穩定在0.4左右。

5.2.4 不同方法的智能體移動效用

本文算法與三種對比方法的智能體移動效用如圖8所示。由圖8可知，隨著任務數量的增加，本文方法的智能體移動效用實驗效果優于對比方法。

在任務數量小于15時，本文方法和方法1、3中的網絡具有一定的連通性，隨著任務數量的增加，智能體移動相同距離可以執行更多的任務，從而使智能體移動效用增加；在任務數量大于15時，任務數量的增加導致任務完成率下降，智能體移動效用隨之下降。相比于方法1，本文方法移動更少的距離就可以組成子網執行任務，因此本文方法的智能體移動效用略高；而在方法3中，初始任務完成率較低，導致初始移動效用較低；在方法2中，任務數量較少時智能體移動效用達到了0.9，隨著任務數量的增加，移動效用不斷下降。由于間歇連通的智能體移動靈活且沒有連通性約束，在任務數量少時，靈活組網即可滿足任務需求，所以相較于本文方法有較高移動效用，但隨著任務數量增加，多智能體為了滿足任務需求產生較大移動成本，且因無連通性約束，多智能體移動后組網的效率降低，所以智能體移動效用降低。

6 結束語

為了保證任務完成效率和質量，匹配多智能體局部網絡質量和區域性任務需求，本文提出了一種基于任務需求匹配的網絡連通質量控制方法。通過分析周期性間歇連通多智能體網絡的連通性，構建基于主從模式的多智能體子網集合，進而基于任務需求匹配評估子網集合的連通質量。用最大的子網集合連通質量表示多智能體網絡連通質量，提出了基于網絡連通質量控制的多智能體移動策略。實驗結果表明，本文方法有效保障了網絡連通質量，維持了任務完成率，提高了智能體移動效用。在未來的工作中，將考慮分布式的多智能體組網方式，在動態變化的任務環境中使多智能體自適應地組成子網以執行任務。除此之外，為了對多智能體網絡連通質量進行更為準確和全面的分析，還將考慮網絡異常流量［22］、網絡擁塞等其他因素對網絡連通質量的影響。

參考文獻：

［1］Basak A，Zaroukian E G，Corder K，et al.Utility of doctrine with multi-agent RL for military engagements［C］//Proc of Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications IV.2022：1211323.

［2］Babic＇ A，Loncˇar I，Arbanas B，et al.A novel paradigm for underwater monitoring using mobile sensor networks［J］.Sensors，2020，20（16）：4615.

［3］Wang Yanan，Xu Tong，Niu Xin，et al.STMARL：a spatio-temporal multi-agent reinforcement learning approach for cooperative traffic light control［J］.IEEE Trans on Mobile Computing，2022，21（6）：2228-2242.

［4］Dornhfer M，Sack S，Zenkert J，et al.Simulation of smart factory processes applying multi-agent-systems：a knowledge management perspective［J］.Journal of Manufacturing and Materials Processing，2020，4（3）：89.

［5］Peng Zhouhua，Wang Dan，Li Tieshan，et al.Output-feedback cooperative formation maneuvering of autonomous surface vehicles with connectivity preservation and collision avoidance［J］.IEEE Trans on Cybernetics，2020，50（6）：2527-2535.

［6］Gu Nan，Wang Dan，Peng Zhouhua，et al.Observer-based finite-time control for distributed path maneuvering of underactuated unmanned surface vehicles with collision avoidance and connectivity preservation［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2021，51（8）：5105-5115.

［7］Boldrer M，Bevilacqua P，Palopoli L，et al.Graph connectivity control of a mobile robot network with mixed dynamic multi-tasks［J］.IEEE Robotics and Automation Letters，2021，6（2）：1934-1941.

［8］Meng Shaofeng，Kan Zhen.Deep reinforcement learning-based effective coverage control with connectivity constraints［J］.IEEE Control Systems Letters，2022，6：283-288.

［9］Afonso R J M，Maximo M R O A，Galvo R K H.Task allocation and trajectory planning for multiple agents in the presence of obstacle and connectivity constraints with mixed-integer linear programming［J］.International Journal of Robust and Nonlinear Control，2020，30（14）：5464-5491.

［10］Parasuraman R，Kim J，Luo Shaocheng，et al.Multipoint rendezvous in multirobot systems［J］.IEEE Trans on Cybernetics，2020，50（1）：310-323.

［11］Wang Cong，Liu Chenglin，Liu Shuai.Robust fixed-time connectivity-preserving consensus for second-order multi-agent systems with external disturbances［J］.IET Control Theory & Applications，2020，14（17）：2674-2681.

［12］Shang Yilun.Resilient consensus for robust multiplex networks with asymmetric confidence intervals［J］.IEEE Trans on Network Science and Engineering，2021，8（1）：65-74.

［13］Chapnevis A，Güven I，Njilla L，et al.Collaborative trajectory optimization for outage-aware cellular-enabled UAVs［C］//Proc of the 93rd IEEE Vehicular Technology Conference.Piscataway，NJ：IEEE Press，2021：1-6.

［14］Liu Zhiyu，Wu Bo，Dai Jin，et al.Distributed communication-aware motion planning for networked mobile robots under formal specifications［J］.IEEE Trans on Control of Network Systems，2020，7（4）：1801-1811.

［15］Dong He，Wu Nan，Feng Guangsheng，et al.Research on computing task allocation method based on multi-UAVs collaboration［C］//Proc of IEEE International Conference on Smart Internet of Things.Pisca-taway，NJ：IEEE Press，2020：86-93.

［16］Yu Xi，Saldaa D，Shishika D，et al.Resilient consensus in robot swarms with periodic motion and intermittent communication［J］.IEEE Trans on Robotics，2021，38（1）：110-125.

［17］Wei Cong，Yu Xi，Tanner H G，et al.Synchronous rendezvous for networks of active drifters in gyre flows［C］//Proc of the 14th International Symposium on Distributed Autonomous Robotic Systems.Cham：Springer，2019：413-425.

［18］Yu Xi，Hsieh M A.Synthesis of a time-varying communication network by robot teams with information propagation guarantees［J］.IEEE Robotics and Automation Letters，2020，5（2）：1413-1420.

［19］Piltyay S，Bulashenko A，Demchenko I.Wireless sensor network connectivity in heterogeneous 5G mobile systems［C］//Proc of IEEE International Conference on Problems of Infocommunications：Science and Technology.Piscataway，NJ：IEEE Press，2020：625-630.

［20］Wang Shaoqing，Yu Jiguo，Atiquzzaman M，et al.CRPD：a novel clustering routing protocol for dynamic wireless sensor networks［J］.Personal and Ubiquitous Computing，2018，22（3）：545-559.

［21］劉英杰，劉士虎，徐偉華.基于有效路徑拓撲穩定性的鏈路預測方法［J］.計算機應用研究，2022，39（1）：90-95.（Liu Yingjie，Liu Shihu，Xu Weihua.Link prediction method based on topology stability of effective path［J］.Application Research of Computers，2022，39（1）：90-95.）

［22］Xia Yuanjun，Dong Shi，Peng Tao， et al.Wireless network abnormal traffic detection method based on deep transfer reinforcement learning［C］//Proc of the 17th International Conference on Mobility，Sensing and Networking.Piscataway，NJ：IEEE Press，2021：528-535.

收稿日期：2023-02-12；修回日期：2023-04-11基金項目：國家自然科學基金資助項目（61602305，61802257）；上海市自然科學基金資助項目（18ZR1426000，19ZR1477600）；南通市科技局社會民生計劃資助項目（MS12021060）；浦東新區科技發展基金產學研專項資助項目（PKX2021-D10）；敏捷智能計算四川省重點實驗室開放式基金資助項目

作者簡介：何杏宇（1984-），女，湖南岳陽人，副教授，碩導，博士，主要研究方向為物聯網和移動群智計算；王怡（1996-），女，湖北十堰人，碩士研究生，主要研究方向為無人自主系統和群智計算；楊桂松（1982-），男（通信作者），河南漯河人，副教授，碩導，博士，主要研究方向為物聯網與普適計算等（gsyang@ usst.edu.cn）；賈明權（1982-），男，四川合江人，高級工程師，博士，主要研究方向為先進智能計算；周玥（1999-），男，山東菏澤人，本科生，主要研究方向為無人自主系統；徐心玥（2001-），男，上海人，本科生，主要研究方向為無人自主系統.