复杂无向网络连通性的一种高效判定算法

王卓; 秦博东; 徐雍; 鲁仁全; 魏庆来

doi:10.16383/j.aas.c190246

复杂无向网络连通性的一种高效判定算法

doi: 10.16383/j.aas.c190246

王卓^{1, 2,},
秦博东^3,,
徐雍^4,,
鲁仁全^4, ,,
魏庆来^5,

1.
北京航空航天大学前沿科学技术创新研究院北航-首医大数据精准医疗高精尖创新中心北京 100191
2.
北京量子信息科学研究院北京 100193
3.
北京航空航天大学仪器科学与光电工程学院北京 100191
4.
广东工业大学自动化学院智能决策与协同控制广东省重点实验室广州 510006
5.
中国科学院自动化研究所复杂系统管理与控制国家重点实验室北京 100190

基金项目:

国家自然科学基金 61673041

国家自然科学基金 61722312

国家自然科学基金 61876041

国家自然科学基金 61425009

国家自然科学基金 U1611262

北京量子信息科学研究院 Y18G34

详细信息

作者简介:
王卓  北京航空航天大学前沿科学技术创新研究院教授. 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

计量
- 文章访问数: 1490
- HTML全文浏览量: 265
- PDF下载量: 197
- 被引次数: 0
出版历程
- 收稿日期: 2019-03-25
- 录用日期: 2019-06-06
- 刊出日期: 2020-10-29

An Efficient Algorithm for Determining the Connectivity of Complex Undirected Networks

WANG Zhuo^{1, 2
,},
QIN Bo-Dong^3
,,
XU Yong^4
,,
LU Ren-Quan^{4
, ,},
WEI Qing-Lai^5
,

1.
The Research Institute of Frontier Science, and Beijing Advanced Innovation Center for Big Data-Based Precision Medicine, Beihang University, Beijing 100191
2.
Beijing Academy of Quantum Information Sciences, Beijing 100193
3.
The The School of Instrumentation and Optoelectronic Engineering, Beihang University, Beijing 100191
4.
The School of Automation, Guangdong University of Technology, and Guangdong Provincial Key Laboratory of Intelligent Decision and Cooperative Control, Guangzhou 510006
5.
The State Key Laboratory for Management and Control of Complex Systems, Institute of Automation, Chinese Academy of Sciences, Beijing 100190

Funds:

National Natural Science Foundation of China 61673041

National Natural Science Foundation of China 61722312

National Natural Science Foundation of China 61876041

National Natural Science Foundation of China 61425009

National Natural Science Foundation of China U1611262

eijing Academy of Quantum Information Sciences Research Program Y18G34

More Information

Author Bio:
WANG Zhuo  Professor at the Research Institute of Frontier Science, Beihang University, China. He received his Ph. D. degree in Electrical and Computer Engineering Department from University of Illinois at Chicago, USA in 2013. His research interest covers data-based system identiflcation, modeling, analysis, optimization and control, adaptive dynamic programming methods, nonlinear adaptive control, atomic-spin-efiect-based inertial measurement technology, and atomic ensemble control (manipulation) methods

QIN Bo-Dong  Master student at the School of Instrumentation and Optoelectronic Engineering, Beihang University. His main research interest is sensing data processing for high precision quantum measurement in struments

XU Yong  Associate professor at the School of Automation, Guangdong University of Technology. He received his Ph. D. degree from the College of Control Science and Engineering, Zhejiang University in 2014. His research interest covers networked control systems, state estimation, and positive systems

WEI Qing-Lai Professor at the State Key Laboratory for Management and Control of Complex Systems, Institute of Automation, Chinese Academy of Sciences. He received his Ph. D. degree in control theory and control engineering from Northeastern University in 2009. His research interest covers intelligent control, artiflcial intelligence, learning systems, adaptive dynamic programming, adaptive optimal control, data-based control, neural network-based control, optimization in industrial systems, and smart grid

Corresponding author: LU Ren-Quan Professor at the School of Automation, Guangdong University of Technology. He received his Ph. D. degree from the College of Control Science and Engineering, Zhejiang University in 2004. His research interest covers complex systems, networked control systems, and nonlinear systems. Corresponding author of this paper

摘要

摘要: 通信网络的拓扑结构连通性是多智能体系统一致性控制或编队控制等的理论前提.以往, 各种多智能体系统一致性控制或编队控制方面的文献仅侧重于控制协议、智能体动力学模型和控制律设计, 而缺乏对多智能体通信网络拓扑结构的连通性研究.网络连通性高效判定算法不仅是大规模多智能体系统一致性控制或编队控制的保证, 而且在图论、现代移动通信、计算机与交通等各种网络中有着重要和广泛的应用.针对复杂无向网络的连通性问题, 本文给出了一种新的高效判定算法、以及该算法的时间复杂度和空间复杂度的上界.该算法具有非常低的时间复杂度和空间复杂度, 且便于计算机实现, 因而具有重要的理论意义和广泛的实用价值.
- 复杂无向网络 /
- 图论 /
- 连通性 /
- 多智能体系统 /
- 高效算法
Abstract: The topological connectivity of communication network is the theoretical premise of consistency control or formation control of multi-agent systems. The past literature on consistency control or formation control of multi-agent systems focused only on control protocol, agent dynamics model and control law design, lacking the research on the topological connectivity of multi-agent communication network. The efficient determination algorithm of network connectivity is not only the guarantee of consistency control or formation control for the large-scale multi-agent systems, but also has important and extensive applications in graph theory and various networks such as modern mobile communication networks, computer networks and transportation networks. This paper presents a new efficient determination algorithm with the upper bounds of the time complexity and space complexity of the algorithm, for the connectivity problem of complex undirected networks. The algorithm has very low time complexity and space complexity, and can be realized easily with computer programs, which makes it have important theoretical significance and wide practicability.
- Complex undirected networks /
- graph theory /
- connectivity /
- multi-agent systems /
- efficient algorithm
Recommended by Associate Editor LIU Yan-Jun
注释:

1) 本文责任编委刘艳军

HTML全文

图 1 $G1$

Fig. 1 $G1$

下载: 全尺寸图片幻灯片

图 2 $G2$

Fig. 2 $G2$

下载: 全尺寸图片幻灯片

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

Fig. 3 Block diagram of the connectivity determination algorithm for complex undirected networks based on the neighbor matrix

下载: 全尺寸图片幻灯片

参考文献(21)

[1]	陈世明, 管俊杰, 高彦丽, 裴惠琴, 邱昀.组合连通拓扑下基于事件触发的多智能体快速一致性算法.自动化学报, 2018, 44(12): 2269-2277 doi: 10.16383/j.aas.2018.c160839 Chen Shi-Ming, Guan Jun-Jie, Gao Yan-Li, Pei Hui-Qin, Qiu Yun. Event-triggered fast consensus algorithm for multi-agent systems under jointly-connected topology. Acta Automatica Sinica, 2018, 44(12): 2269-2277 doi: 10.16383/j.aas.2018.c160839
[2]	杨东岳, 梅杰.有向图中基于扰动观测器的线性多智能体系统一致性.自动化学报, 2018, 44(6): 1037-1044 doi: 10.16383/j.aas.2017.c160747 Yang Dong-Yue, Mei Jie. Disturbance observer based consensus of linear multi-agent systems under a directed graph. Acta Automatica Sinica, 2018, 44(6): 1037-1044 doi: 10.16383/j.aas.2017.c160747
[3]	严卫生, 李俊兵, 王银涛.受损多智能体系统的信息一致性.自动化学报, 2012, 38(11): 1880-1884 doi: 10.3724/SP.J.1004.2012.01880 Yan Wei-Sheng, Li Jun-Bing, Wang Yin-Tao. Consensus for damaged multi-agent system. Acta Automatica Sinica, 2012, 38(11): 1880-1884 doi: 10.3724/SP.J.1004.2012.01880
[4]	罗小元, 杨帆, 李绍宝, 关新平.多智能体系统的最优持久编队生成策略.自动化学报, 2014, 40(7): 1311-1319 doi: 10.3724/SP.J.1004.2014.01311 Luo Xiao-Yuan, Yang Fan, Li Shao-Bao, Guan Xin-Ping. Generation of optimally persistent formation for multi-agent systems. Acta Automatica Sinica, 2014, 40(7): 1311-1319 doi: 10.3724/SP.J.1004.2014.01311
[5]	闵海波, 刘源, 王仕成, 孙富春.多个体协调控制问题综述.自动化学报, 2012, 38(10): 1557-1570 doi: 10.3724/SP.J.1004.2012.01557 Min Hai-Bo, Liu Yuan, Wang Shi-Cheng, Sun Fu-Chun. An overview on coordination control problem of multi-agent system. Acta Automatica Sinica, 2012, 38(10): 1557-1570 doi: 10.3724/SP.J.1004.2012.01557
[6]	曹然, 梅杰.有向图中网络Euler-Lagrange系统无需相对速度信息的群一致性.自动化学报, 2018, 44(1): 44-51 doi: 10.16383/j.aas.2018.c160637 Cao Ran, Mei Jie. Group consensus for networked Euler-Lagrangian systems under a directed graph without relative velocity information. Acta Automatica Sinica, 2018, 44(1): 44-51 doi: 10.16383/j.aas.2018.c160637
[7]	Huang C, Zhai G S, Xu G S. Necessary and sufficient conditions for consensus in third order multi-agent systems. IEEE/CAA Journal of Automatica Sinica, 2018, 5(6): 1044-1053 doi: 10.1109/JAS.2018.7511222
[8]	罗小元, 邵士凯, 关新平, 赵渊洁.多智能体最优持久编队动态生成与控制.自动化学报, 2013, 39(9): 1431-1438 doi: 10.3724/SP.J.1004.2013.01431 Luo Xiao-Yuan, Shao Shi-Kai, Guan Xin-Ping, Zhao Yuan-Jie. Dynamic generation and control of optimally persistent formation for multi-agent systems. Acta Automatica Sinica, 2013, 39(9): 1431-1438 doi: 10.3724/SP.J.1004.2013.01431
[9]	Wang Q, Wang Y Z, Zhang H X. The formation control of multi-agent systems on a circle. IEEE/CAA Journal of Automatica Sinica, 2018, 5(1): 148-154 doi: 10.1109/JAS.2016.7510022
[10]	Maithripala D H A, Jayasuriya S. Rigid formation keeping and formation reconfiguration of multi-agent systems. IFAC Proceedings Volumes, 2008, 41(2): 5155-5160 doi: 10.3182/20080706-5-KR-1001.00866
[11]	游科友, 谢立华.网络控制系统的最新研究综述.自动化学报, 2013, 39(2): 101-118 doi: 10.3724/SP.J.1004.2013.00101 You Ke-You, Xie Li-Hua. Survey of recent progress in networked control systems. Acta Automatica Sinica, 2013, 39(2): 101-118 doi: 10.3724/SP.J.1004.2013.00101
[12]	Huo Zhi-Hong, Fang Hua-Jing. Fault-tolerant control research for networked control system under communication constraints. Acta Automatica Sinica, 2006, 32(5): 659-666 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=zdhxb200605002
[13]	Chung F. Graph theory in the information age. Notices of the American Mathematical Society, 2009, 57(6): 726-732 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=fc9314476dedf26ba1ab76fb0fdc2c7f
[14]	Zhang S H, Yan Y H, Bao W, Guo S W, Jiang J D, Ma M R. Network topology identification algorithm based on adjacency matrix. In: Proceedings of the 2017 IEEE Innovative Smart Grid Technologies. Auckland: IEEE, 2017. 1-5
[15]	Ghosh R K. Parallel algorithms for connectivity problems in graph theory. International Journal of Computer Mathematics, 1986, 18(3-4): 193-218 doi: 10.1080/00207168608803490
[16]	Wagenpfeil J, Trachte A, Hatanaka T, Fujita M, Sawodny O. A distributed minimum restrictive connectivity maintenance algorithm. IFAC Proceedings Volumes, 2009, 42(16): 365-370 doi: 10.3182/20090909-4-JP-2010.00063
[17]	Pisano A, Franceschelli M, Pilloni A, Shtessel Y, Usai E. Retaining connectivity in mobile communication mesh networks. IFAC-PapersOnLine, 2017, 50(1): 800-807 doi: 10.1016/j.ifacol.2017.08.143
[18]	Nagamochi H. Graph algorithms for network connectivity problems. Journal of the Operations Research Society of Japan, 2004, 47(4): 199-223 http://www.ams.org/mathscinet-getitem?mr=2174063
[19]	McNunn G S, Bryden K M. A proposed implementation of Tarjan's algorithm for scheduling the solution sequence of systems of federated models. Procedia Computer Science, 2013, 20: 223-228 doi: 10.1016/j.procs.2013.09.265
[20]	Hwang F. Control algorithms for rearrangeable clos networks. IEEE Transactions on Communications, 1983, 31(8): 952-954 doi: 10.1109/TCOM.1983.1095923
[21]	Kenneth H R. Discrete Mathematics and Its applications. 7th Edition. 1221 Avenue of the Americas, NewYork, NY: McGraw-Hill, 2012. 603-606

施引文献

资源附件(0)

访问统计

图(3)

计量

文章访问数: 1490
HTML全文浏览量: 265
PDF下载量: 197
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

复杂无向网络连通性的一种高效判定算法

doi: 10.16383/j.aas.c190246

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

计量

An Efficient Algorithm for Determining the Connectivity of Complex Undirected Networks

计量

目录

留言板

复杂无向网络连通性的一种高效判定算法

doi: 10.16383/j.aas.c190246

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

计量

出版历程

An Efficient Algorithm for Determining the Connectivity of Complex Undirected Networks

计量

出版历程

目录

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