引用本文

王卓, 秦博东, 徐雍, 鲁仁全, 魏庆来.复杂无向网络连通性的一种高效判定算法.自动化学报, 2020, 46(10): 2129-2136 doi: 10.16383/j.aas.c190246

Wang Zhuo, Qin Bo-Dong, Xu Yong, Lu Ren-Quan, Wei Qing-Lai. An e–cient algorithm for determining the connectivity of complex undirected networks. Acta Automatica Sinica, 2020, 46(10): 2129-2136 doi: 10.16383/j.aas.c190246

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190246

关键词

复杂无向网络，图论，连通性，多智能体系统，高效算法 

摘要

通信网络的拓扑结构连通性是多智能体系统一致性控制或编队控制等的理论前提.以往, 各种多智能体系统一致性控制或编队控制方面的文献仅侧重于控制协议、智能体动力学模型和控制律设计, 而缺乏对多智能体通信网络拓扑结构的连通性研究.网络连通性高效判定算法不仅是大规模多智能体系统一致性控制或编队控制的保证, 而且在图论、现代移动通信、计算机与交通等各种网络中有着重要和广泛的应用.针对复杂无向网络的连通性问题, 本文给出了一种新的高效判定算法、以及该算法的时间复杂度和空间复杂度的上界.该算法具有非常低的时间复杂度和空间复杂度, 且便于计算机实现, 因而具有重要的理论意义和广泛的实用价值.

文章导读

自多智能体系统理论提出以来, 其协调控制方面[1]的研究受到了国际学术界的广泛关注, 相关研究内容仅涉及多智能体系统一致性控制[2-3]或编队控制协议[4-5]、智能体动力学模型[6-7]和控制律设计[8-10], 而多智能体通信网络拓扑结构的连通性[11-12]研究未见有文献报道.通信网络拓扑结构的连通性是多智能体系统一致性控制与编队控制等的理论前提.网络连通性高效判定算法不仅是大规模多智能体系统一致性控制或编队控制的保证, 而且在图论[13-15]、现代移动通信[16-17]、计算机与交通[18]等各种网络中有着重要和广泛的应用.

在多智能体系统一致性控制或编队控制中, 如果两个智能体在规定的时间(通常为一个采样周期)内至少有一次数据交换, 则认为这两个智能体在通信方面是连通的.如此, 进行数据交换的多个智能体构成了一个移动通信网络.若所有智能体构成的这个移动通信网络在规定的时间内是连通的, 则称该网络的拓扑结构是连通的.这种多智能体通信网络常被建模为复杂无向网络(含自环和多重边), 而其拓扑结构的连通性检测和判定问题就可转化为复杂无向网络的连通性检测和判定问题.

迄今为止, 判定网络连通性的算法主要有两类:基于深度优先搜索技术的算法, 如Tarjan算法[19]和Gabow算法[20]等; 基于可达矩阵的算法和基于关系传递闭包的Warshall算法[21]等. Tarjan算法和Gabow算法是一类面向网络的直接搜索算法, 其优点是算法复杂度低(均为O$(n+m)$, 其中$n$为节点数, $m$为边数), 缺点是仅适合简单网络(无自环或多重边)且不易编程(需使用堆栈和标号技术). Warshall算法的优点是结构异常简洁且可采用效率更高的位运算方法, 缺点是算法复杂度高(O$(2n^3)$)且同样仅适用于简单网络.基于可达矩阵的连通性判定算法虽可用于复杂无向网络, 但由于其算法复杂度太高(O$(n^4)$)而很难适用于大规模移动通信网络或计算机互联网络的连通性判定.

针对具有$n$个节点的复杂无向网络, 本文给出了一种新的连通性判定算法, 该算法的时间复杂度和空间复杂度分别为O$(3n^2)$和O$(n^2+n)$.与基于可达矩阵的连通性判定算法和基于关系传递闭包的Warshall算法相比, 本文所给算法在时间复杂度上具有显著优势, 因而更适合大规模移动通信网络或计算机互联网络的连通性检测与判定.

图 1  $G1$

图 2  $G2$

图 3  基于邻居矩阵的复杂无向网络连通性判定算法框图

在引言部分, 论述了网络连通性判定算法、特别是高效连通性判定算法的理论与现实意义.

本文第1节给出了复杂无向网络邻居矩阵和邻居集的定义及相关概念, 它们是基于邻居矩阵的复杂无向网络连通性判定算法, 即本文所给算法的前提.

本文第2节给出了邻居集交与并的运算规则、相关概念及其集合解释.在此基础上, 给出了基于邻居矩阵的复杂无向网络连通性判定算法.该算法是本文的主要贡献, 显然它也适用于简单无向网络的连通性判定.

第3节分析给出了本文所给算法的时间复杂度O$((3n^2))$和空间复杂度O$((n^2 + n))$, 它较Warshall算法和基于可达矩阵的算法具有低得多的时间复杂度和空间复杂度.此外, 本节还给出了可使最大可能的计算量达到最小的最优分布式计算规则, 相关结果则是本文的另一有意义的贡献.

与现有算法相比, 本文所给算法的时间复杂度和空间复杂度均非常低、易于分布式计算, 更适合大规模动态复杂无向网络的连通性判定.需要说明的是, 本文所给算法不能直接用于复杂有向网络的连通性判定.我们今后的工作是将上述结果推广到复杂有向网络, 以期得到更一般和更高效的连通性判定算法.

作者简介

王卓

北京航空航天大学前沿科学技术创新研究院教授. 2013年获得美国伊利诺伊大学芝加哥分校电子与计算机工程系博士学位.主要研究方向为基于数据的系统辨识、建模、分析、优化与控制, 自适应动态规划方法, 非线性自适应控制, 基于原子自旋效应的惯性测量技术, 自旋原子系综控制(操控)方法. E-mail: zhuowang@buaa.edu.cn

秦博东

北京航空航天大学仪器科学与光电工程学院硕士研究生.主要研究方向为精密量子测量仪器传感数据处理. E-mail: qinbodong qbd@163.com

徐雍

广东工业大学自动化学院副教授. 2014年获得浙江大学控制科学与工程学院博士学位.主要研究方向为网络化控制系统, 状态估计, 正定系统. E-mail: xuyong809@163.com

魏庆来

中国科学院自动化研究所复杂系统管理与控制国家重点实验室研究员. 2009年获得东北大学控制理论与控制工程专业博士学位.主要研究方向为智能控制, 人工智能, 自学习系统, 自适应动态规划, 自适应最优控制, 数据驱动控制, 神经网络控制, 工业控制系统优化, 智能电网. E-mail: qinglai.wei@ia.ac.cn

鲁仁全

广东工业大学自动化学院教授. 2004年获得浙江大学控制科学与工程学院博士学位.主要研究方向为复杂系统, 网络控制系统, 非线性系统.本文通信作者. E-mail: rqlu@gdut.edu.cn