A Shortest Delay Routing Protocol Based on Time-Varying Graph for UAV Formation

The traditional routing algorithms of unmanned aerial vehicle (UAV) formation cannot effectively utilize the advance predictability of topology changes, and the high cost of the routing algorithm will be caused by sending massive detection messages. A shortest delay routing protocol for UAV formation based on discrete time-aggregated graph (TAG) is proposed by introducing the time-varying graph model. Firstly, utilizing the prior knowledge of the UAV formation, the network link resources and topology are characterized by using the discrete TAG model. Secondly, the routing decision algorithm is designed based on TAG to solve the shortest delay path from the source to the destination of the network. Finally, simulation results demonstrate that the routing protocol can improve the packet delivery ratio, end-to-end delay and routing control overhead compared with the traditional ad-hoc on-demand distance vector routing protocol.