复杂无向网络连通性的一种高效判定算法
An Efficient Algorithm for Determining the Connectivity of Complex Undirected Networks
查看参考文献21篇
|
文摘
|
通信网络的拓扑结构连通性是多智能体系统一致性控制或编队控制等的理论前提.以往,各种多智能体系统一致性控制或编队控制方面的文献仅侧重于控制协议、智能体动力学模型和控制律设计,而缺乏对多智能体通信网络拓扑结构的连通性研究.网络连通性高效判定算法不仅是大规模多智能体系统一致性控制或编队控制的保证,而且在图论、现代移动通信、计算机与交通等各种网络中有着重要和广泛的应用.针对复杂无向网络的连通性问题,本文给出了一种新的高效判定算法、以及该算法的时间复杂度和空间复杂度的上界.该算法具有非常低的时间复杂度和空间复杂度,且便于计算机实现,因而具有重要的理论意义和广泛的实用价值. |
|
其他语种文摘
|
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. |
|
来源
|
自动化学报
,2020,46(10):2129-2136 【核心库】
|
|
DOI
|
10.16383/j.aas.c190246
|
|
关键词
|
复杂无向网络
;
图论
;
连通性
;
多智能体系统
;
高效算法
|
|
地址
|
1.
北京航空航天大学前沿科学技术创新研究院, 北航–首医大数据精准医疗高精尖创新中心, 北京, 100191
2.
北京量子信息科学研究院, 北京, 100193
3.
北京航空航天大学仪器科学与光电工程学院, 北京, 100191
4.
广东工业大学自动化学院, 智能决策与协同控制广东省重点实验室, 广州, 510006
5.
中国科学院自动化研究所, 复杂系统管理与控制国家重点实验室, 北京, 100190
|
|
语种
|
中文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
0254-4156 |
|
学科
|
数学;自动化技术、计算机技术 |
|
基金
|
国家自然科学基金
;
北京量子信息科学研究院
|
|
文献收藏号
|
CSCD:6833304
|
参考文献 共
21
共2页
|
|
1.
陈世明. 组合连通拓扑下基于事件触发的多智能体快速一致性算法.
自动化学报,2018,44(12):2269-2277
|
被引
8
次
|
|
|
|
|
2.
杨东岳. 有向图中基于扰动观测器的线性多智能体系统一致性.
自动化学报,2018,44(6):1037-1044
|
被引
4
次
|
|
|
|
|
3.
严卫生. 受损多智能体系统的信息一致性.
自动化学报,2012,38(11):1880-1884
|
被引
7
次
|
|
|
|
|
4.
罗小元. 多智能体系统的最优持久编队生成策略.
自动化学报,2014,40(7):1311-1319
|
被引
17
次
|
|
|
|
|
5.
闵海波. 多个体协调控制问题综述.
自动化学报,2012,38(10):1557-1570
|
被引
27
次
|
|
|
|
|
6.
曹然. 有向图中网络系统无需相对速度信息的群一致性.
自动化学报,2018,44(1):44-51
|
被引
6
次
|
|
|
|
|
7.
Huang C. Necessary and Sufficient Conditions for Consensus in Third Order Multi-Agent Systems.
IEEE/CAA Journal of Automatica Sinica,2018,5(6):1044-1053
|
被引
7
次
|
|
|
|
|
8.
罗小元. 多智能体最优持久编队动态生成与控制.
自动化学报,2013,39(9):1431-1438
|
被引
10
次
|
|
|
|
|
9.
Wang Q. The Formation Control of Multi-agent Systems on a Circle.
IEEE/CAA Journal of Automatica Sinica,2018,5(1):148-154
|
被引
4
次
|
|
|
|
|
10.
Maithripala D H A. Rigid formation keeping and formation reconfiguration of multi-agent systems.
IFAC Proceedings Volumes,2008,41(2):5155-5160
|
被引
1
次
|
|
|
|
|
11.
游科友. 网络控制系统的最新研究综述.
自动化学报,2013,39(2):101-118
|
被引
65
次
|
|
|
|
|
12.
Huo Zhihong. Fault-Tolerant Control Research for Networked Control System under Communication Constraints.
Acta Automatica Sinica,2006,32(5):659-666
|
被引
5
次
|
|
|
|
|
13.
Chung F. Graph theory in the information age.
Notices of the American Mathematical Society,2009,57(6):726-732
|
被引
1
次
|
|
|
|
|
14.
Zhang S H. Network topology identification algorithm based on adjacency matrix.
Proceedings of the 2017 IEEE Innovative Smart Grid Technologies,2017:1-5
|
被引
1
次
|
|
|
|
|
15.
Ghosh R K. Parallel algorithms for connectivity problems in graph theory.
International Journal of Computer Mathematics,1986,18(3/4):193-218
|
被引
1
次
|
|
|
|
|
16.
Wagenpfeil J. A distributed minimum restrictive connectivity maintenance algorithm.
IFAC Proceedings Volumes,2009,42(16):365-370
|
被引
2
次
|
|
|
|
|
17.
Pisano A. Retaining connectivity in mobile communication mesh networks.
IFAC-PapersOnLine,2017,50(1):800-807
|
被引
1
次
|
|
|
|
|
18.
Nagamochi H. Graph algorithms for network connectivity problems.
Journal of the Operations Research Society of Japan,2004,47(4):199-223
|
被引
1
次
|
|
|
|
|
19.
Mcnunn G S. A proposed implementation of Tarjan0s algorithm for scheduling the solution sequence of systems of federated models.
Procedia Computer Science,2013,20:223-228
|
被引
1
次
|
|
|
|
|
20.
Hwang F. Control algorithms for rearrangeable clos networks.
IEEE Transactions on Communications,1983,31(8):952-954
|
被引
1
次
|
|
|
|
|
了解气象卫星更多信息，请访问