基于任务需求匹配的网络连通质量控制方法

何杏宇　王怡　杨桂松　贾明权　周玥　徐心玥

摘 要：现有多智能体系统网络研究方法缺乏对局部网络质量与区域性任务需求之间的匹配分析，这将影响任务的完成效率和质量，为此提出一种基于任务需求匹配的网络连通质量控制方法。首先，利用智能体移动状态分析系统网络的间歇连通性；然后，结合任务需求以及系统的间歇网络连通性构建基于主从模式的多智能体子网集合，进而从三个方面评估子网集合的连通质量；最后，提出基于网络连通质量控制的多智能体移动优化模型，用最大的子网集合连通质量表示多智能体网络连通质量，在智能体移动距离和网络连通质量的约束下求解任务完成率最大化的多智能体移动策略，通过该策略形成多智能体网络以执行任务。实验结果表明，该方法可以有效控制网络连通质量，维持任务完成率并提高智能体移动效用。

关键词：多智能体系统；任务需求；网络连通性分析；网络连通质量

中图分类号：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-），男，上海人，本科生，主要研究方向为无人自主系统.