Fault-tolerant communication topology management based on minimum cost arborescence for leader–follower UAV formation under communication faults

A novel fault-tolerant communication topology management method for the leader–follower unmanned aerial vehicle (UAV) formation is proposed to minimize the formation communication cost while keeping the formation shape, even in the case of communication faults during the formation flight. This method is based on Edmonds’ algorithm for the minimum cost arborescence problem in graph theory. When a formation shape is given before the formation flight, this method can get the optimal initial communication topology with the minimum formation communication cost for keeping the formation shape. When some communication faults occur during the formation flight, which will cause the formation shape cannot be kept, this method can reconfigure the communication topology in time to guarantee the safety of all UAVs and recover the formation shape, and then it can reoptimize the communication topology by UAV position reconfiguration in the formation shape to minimize the formation communication cost for continuously keeping the formation shape. The effectiveness of this method is demonstrated through several simulation experiments.