The optimization design of the UAV formation information interaction topology is an important foundation to ensure safety and task execution efficiency of UAV formations. The generation algorithm of the UAV formation information interaction topology is currently limited to small-scale formation with a single optimization goal. To solve this problem, a hierarchical clustering structure is adopted to raise the information interaction topology level to meet the large-scale scene. A hierarchical distributed leader-follower formation information interaction topology generation algorithm based on the minimum cost arborescence is also proposed to improve the formation endurance and reduce the total communication cost of the formation. The simulation results are verified by OMNeT++. The experimental results show that the total communication cost of the hierarchical distributed leader-follower formation is significantly lower than that of the traditional leader-follower formation when considering the transfer iteration of position errors; the energy consumption of the network is more balanced and the endurance of the formation is improved through periodically updating the cluster head; at the formation scale of 80 UAVs, the hierarchical distributed leader-follower formation generation algorithm can be solved in 0.3 s, about 2.5 times that of traditional leader-follower formation algorithm; at the formation scale of 100 UAVs, the hierarchical distributed leader-follower formation generation algorithm can be solved within 0.4 s, while the traditional leader follower formation cannot maintain the original formation due to the transfer iteration of position errors.
DONG Wenqi
,
HE Feng
. Hierarchical and distributed generation of information interaction topology for large scale UAV formation[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021
, 42(6)
: 324380
-324380
.
DOI: 10.7527/S1000-6893.2020.24380
[1] LUO F, JIANG C X, DU J, et al. A distributed gateway selection algorithm for UAV networks[J]. IEEE Transactions on Emerging Topics in Computing, 2015, 3(1):22-33.
[2] 崔朝阳, 孙甲琦, 徐松艳, 等. 适用于集群无人机的自组网安全分簇算法[J]. 山东大学学报:理学版, 2018, 53(7):51-59. CUI Z Y,SUN J Q,XU S Y,et al. A secure clustering algorithm of Ad Hoc network for colony UAVs[J]. Journal of Shandong University:Natural Science, 2018, 53(7):51-59(in Chinese).
[3] 王祥科, 刘志宏, 丛一睿, 等. 小型固定翼无人机集群综述和未来发展[J]. 航空学报, 2020, 41(4):023732. WANG X K, LIU Z H, CONG Y R, et al. Miniature fixed-wing UAV swarms:Review and outlook[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(4):023732(in Chinese).
[4] 王国强. 面向队形保持的无人机编队信息交互拓扑优化问题的研究[D]. 合肥:合肥工业大学, 2016:19-20. WANG G Q. Research on information exchange topology optimization problem of UAV formation during formation keeping[D]. Hefei:Hefei University of Technology, 2016:19-20(in Chinese).
[5] REN W. Consensus strategies for cooperative control of vehicle formations[J]. IET Control Theory & Applications, 2007, 1(2):505-512.
[6] SU S Z, LIN Z L. Distributed consensus control of multi-agent systems with higher order agent dynamics and dynamically changing directed interaction topologies[J]. IEEE Transactions on Automatic Control, 2016, 61(2):515-519.
[7] GASPARRI A, WILLIAMS R K, PRIOLO A, et al. Decentralized and parallel constructions for optimally rigid graphs in R2[J]. IEEE Transactions on Mobile Computing, 2015, 14(11):2216-2228.
[8] PRIOLO A, WILLIAMS R K, GASPARRI A, et al. Decentralized algorithms for optimally rigid network constructions[C]//IEEE International Conference on Robotics and Automation. Piscataway:IEEE Press, 2014.
[9] 王金然, 罗小元, 杨帆, 等. 三维最优持久编队拓扑生成策略[J]. 自动化学报, 2015,41(6):1123-1130. WANG J R, LUO X Y, YANG F, et al. Generation strategy of optimal persistent formation topology in 3D space[J]. Acta Automatica Sinica, 2015,41(6):1123-1130(in Chinese).
[10] XIE W X, ZHANG Q Y, SUN Z M, et al. A clustering routing protocol for WSN based on type-2 fuzzy logic and ant colony optimization[J]. Wireless Personal Communications, 2015, 84(2):1165-1196.
[11] MEHRA P S, DOJA M N, ALAM B. Fuzzy based enhanced cluster head selection (FBECS) for WSN[J]. Journal of King Saud University Science, 2018, 32(1):390-401.
[12] ALAGIRISAMY M, CHOW C O. An energy based cluster head selection unequal clustering algorithm with dual sink (ECH-DUAL) for continuous monitoring applications in wireless sensor networks[J]. Cluster Computing, 2018, 21(1):91-103.
[13] ZHANG Y M, MEHRJERDI H. A survey on multiple unmanned vehicles formation control and coordination:Normal and fault situations[C]//International Conference on Unmanned Aircraft Systems. Piscataway:IEEE Press, 2013:1087-1096.
[14] 宗群, 王丹丹, 邵士凯,等. 多无人机协同编队飞行控制研究现状及发展[J]. 哈尔滨工业大学学报, 2017, 49(3):1-14. ZONG Q, WANG D D, SHAO S K, et al. Research status and development of multi UAV coordinated formation flight control[J]. Journal of Harbin Institute of Technology, 2017, 49(3):1-14(in Chinese).
[15] BAI J, WEN G G, RAHMANI A, et al. Formation tracking of fractional-order multi-agent systems based on error predictor[C]//Control & Decision Conference. Piscataway:IEEE Press, 2018.
[16] 卜月华, 王维凡, 吕新忠. 图论及其应用[M]. 2版. 南京:东南大学出版社, 2015:68. BU Y H, WANG W F, LV X Z. On graph theory and its application[M]. 2nd ed. Nanjing:Southeast University Press, 2015:68(in Chinese).
[17] YANG H, JIANG B, ZHANG Y M. Fault-tolerant shortest connection topology design for formation control[J]. International Journal of Control, Automation and Systems, 2014, 12(1):29-36.
[18] ABEYWICKRAMA H V, JAYAWICKRAMA B A, HE Y, et al. Algorithm for energy efficient inter-UAV collision avoidance[C]//International Symposium on Communications & Information Technologies. Piscataway:IEEE Press, 2017:1-5.
[19] POLLINI L, GIULIETTI F, INNOCENTI M. Robustness to communication failures within formation flight[C]//American Control Conference. Piscataway:IEEE Press, 2002.
[20] 严磊. 无人机自组织网络动态分簇与机会路由研究[D]. 南京:南京航空航天大学, 2018:38. YAN L. Dynamic clustering and opportunity routing research in UAV ad-hoc network[D]. Nanjing:Nanjing University of Aeronautics and Astronautics, 2018:38(in Chinese).
[21] LING L H, NIU Y F, ZHU H Y. Lyapunov method-based collision avoidance for UAVs[C]//Chinese Control & Decision Conference. Piscataway:IEEE Press, 2015:4716-4720.
CJA