Shortest Delay Routing Protocol for UAV Formation Based on Discrete Time Aggregation Graph

LI Bo; WANG Gaifang; YANG Hongjuan; RU Xuefei; ZHANG Jingchun; WANG Gang

doi:10.11999/JEIT230707

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2024 >

LI Bo, WANG Gaifang, YANG Hongjuan, RU Xuefei, ZHANG Jingchun, WANG Gang. Shortest Delay Routing Protocol for UAV Formation Based on Discrete Time Aggregation Graph[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT230707

Citation:

LI Bo, WANG Gaifang, YANG Hongjuan, RU Xuefei, ZHANG Jingchun, WANG Gang. Shortest Delay Routing Protocol for UAV Formation Based on Discrete Time Aggregation Graph[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT230707

Citation:

PDF( 1587 KB)

Shortest Delay Routing Protocol for UAV Formation Based on Discrete Time Aggregation Graph

doi: 10.11999/JEIT230707

1.
School of Information Science and Engineering, Harbin Institute of Technology at Weihai, Weihai 264209, China
2.
Communication Research Center, Harbin Institute of Technology, Harbin 150001, China

Funds: The National Natural Science Foundation of China (No.62171154, No.61971156), The Natural Science Foundation of Shandong Province (No.ZR2020MF007), The Research Fund Program of Guangdong Key Laboratory of Aerospace Communication and Networking Technology (No.2018B030322004)

Received Date: 2023-07-15
Rev Recd Date: 2024-01-17

Available Online: 2024-01-25

Abstract

Abstract

Aiming at the problems that the traditional UAV formation routing algorithm cannot effectively utilize the advance predictability of topology changes, and the high cost is caused by acquiring the link connection by sending detection packets, a UAV formation shortest delay routing protocol based on discrete time aggregation graph is proposed by introducing the time-varying graph model. Firstly, using the prior knowledge of the UAV formation network, such as the movement trajectory of nodes and the network topology changes, the network link resources and network topology are characterized by using the discrete time aggregation graph. Secondly, the routing decision algorithm is designed based on the graph model. The delay in the process of route discovery is used as the link weight to solve the shortest delay route from the source node to the destination node of the network. Finally, the simulation performance shows that the routing protocol improves the packet delivery rate, reduces the end-to-end delay and diminishes the network control overhead compared with the traditional Ad-hoc On-Demand Distance Vector routing protocol.
- UAV ad hoc network,
- UAV formation,
- Time-varying graph model,
- Shortest delay route

FullText(HTML)

References(17)

References

[1]	AZARI M M, GERACI G, GARCIA-RODRIGUEZ A, et al. UAV-to-UAV communications in cellular networks[J]. IEEE Transactions on Wireless Communications, 2020, 19(9): 6130–6144. doi: 10.1109/TWC.2020.3000303
[2]	陈新颖, 盛敏, 李博, 等. 面向6G的无人机通信综述[J]. 电子与信息学报, 2022, 44(3): 781–789. doi: 10.11999/JEIT210789 CHEN Xinying, SHENG Min, LI Bo, et al. Survey on unmanned aerial vehicle communications for 6G[J]. Journal of Electronics & Information Technology, 2022, 44(3): 781–789. doi: 10.11999/JEIT210789
[3]	YOU Wenjing, DONG Chao, CHENG Xiao, et al. Joint optimization of area coverage and mobile-edge computing with clustering for FANETs[J]. IEEE Internet of Things Journal, 2021, 8(2): 695–707. doi: 10.1109/JIOT.2020.3006891
[4]	SRILAKSHMI U, ALGHAMDI S A, VUYYURU V A, et al. A secure optimization routing algorithm for mobile ad hoc networks[J]. IEEE Access, 2022, 10: 14260–14269. doi: 10.1109/ACCESS.2022.3144679
[5]	SRIVASTAVA A, BAGGA N, and RAKHRA M. Analysis of cluster-based and position-based routing protocol in VANET[C]. Proceedings of the 2021 9th International Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions), Noida, India, 2021: 1–5.
[6]	KANG Hongyue, CHANG Xiaolin, MIŠIĆ J, et al. Improving dual-UAV aided ground-UAV bi-directional communication security: Joint UAV trajectory and transmit power optimization[J]. IEEE Transactions on Vehicular Technology, 2022, 71(10): 10570–10583. doi: 10.1109/TVT.2022.3184804
[7]	DARABKH K A, ALFAWARES M G, and ALTHUNIBAT S. MDRMA: Multi-data rate mobility-aware AODV-based protocol for flying ad-hoc networks[J]. Vehicular Communications, 2019, 18: 100163. doi: 10.1016/j.vehcom.2019.100163
[8]	LI Xianfeng and YAN Jiaojiao. LEPR: Link stability estimation-based preemptive routing protocol for flying ad hoc networks[C]. Proceedings of 2017 IEEE Symposium on Computers and Communications, Heraklion, Greece, 2017: 1079–1084.
[9]	GANKHUYAG G, SHRESTHA A P, and YOO S J. Robust and reliable predictive routing strategy for flying ad-hoc networks[J]. IEEE Access, 2017, 5: 643–654. doi: 10.1109/ACCESS.2017.2647817
[10]	LEE S W, ALI S, YOUSEFPOOR M S, et al. An energy-aware and predictive fuzzy logic-based routing scheme in flying ad hoc networks (FANETS)[J]. IEEE Access, 2021, 9: 129977–130005. doi: 10.1109/ACCESS.2021.3111444
[11]	TANG Zhu, YU Wanrong, ZHAO Baokang, et al. Time-efficient transient loops avoiding in snapshot routing algorithm[C]. Proceedings of 2014 International Conference on Smart Computing Workshops, Hong Kong, China, 2014: 57–64.
[12]	KÖHLER E, LANGKAU K, and SKUTELLA M. Time-expanded graphs for flow-dependent transit times[C]. Proceedings of the 10th Annual European Symposium on Algorithms, Rome, Italy, 2002: 599–611.
[13]	GEORGE B and SHEKHAR S. Time-aggregated graphs for modeling spatio-temporal networks[C]. Proceedings of International Conference on Conceptual Modeling, Tucson, AZ, USA, 2006: 85–99.
[14]	GEORGE B, KIM S, and SHEKHAR S. Spatio-temporal network databases and routing algorithms: A summary of results[C]. Proceedings of the 10th International Symposium on Spatial and Temporal Databases, Boston, MD, USA, 2007: 460–477.
[15]	LI Hongyan, ZHANG Tao, ZHANG Yangkun, et al. A maximum flow algorithm based on storage time aggregated graph for delay-tolerant networks[J]. Ad Hoc Networks, 2017, 59: 63–70. doi: 10.1016/j.adhoc.2017.01.006
[16]	ZHANG Tao, LI Hongyan, ZHANG Shun, et al. STAG-based QoS support routing strategy for multiple missions over the satellite networks[J]. IEEE Transactions on Communications, 2019, 67(10): 6912–6924. doi: 10.1109/TCOMM.2019.2929757
[17]	LEI Liu and LI Hongyan. A routing policy based on time-varying graph for predictable delay tolerant networks[C]. Proceedings of 2015 International Conference on Wireless Communications & Signal Processing, Nanjing, China, 2015: 1–6.