2.765

2022影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

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

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

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

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

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

doi: 10.16383/j.aas.c190246
基金项目: 

国家自然科学基金 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

An Efficient Algorithm for Determining the Connectivity of Complex Undirected Networks

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

  • [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
  • 加载中
图(3)
计量
  • 文章访问数:  1360
  • HTML全文浏览量:  204
  • PDF下载量:  187
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-03-25
  • 录用日期:  2019-06-06
  • 刊出日期:  2020-10-29

目录

    /

    返回文章
    返回