Communication graph for UAV swarm

The graphs for task assignments and the graphs for communication with the drones in the UAV swarm are different and serve different purposes. The mesh network for communication is designed to provide an efficient and reliable network for UAVs. The minimum spanning tree (MST) ensures that all drones are connected with minimal total distance, optimizing the overall efficiency of the network. The distances are Euclidean in a three dimensional co-ordinate system between pairs of drones in a graph of drone distances. The MST is a foundational structure optimizing the costs and improving the efficiency of communication. With a frequent iteration of updating positions of each drone, recalculating inter-drone distances between pairs, and constructing the MST, the UAV swarm can respond faster and better to meet critical operational requirements such as collision avoidance.

To construct the MST, we use Prim’s MST

This is a greedy algorithm that maintains a set A of edges which grows until it covers the graph. While most generic MST do that, in the case of Prim, the set A is a tree.

MST-Prim

// this grows a tree

A = null

for each vertex v in G, initialize the key and the parent

Initialize a min-priority queue Q with vertices

while the Queue is not empty

       extract the vertex with the minimum edge distance connecting it to the tree

       for each adjacencies v of this vertex u

              set the key to the weight(u,v) and parent

Reference: previous article: https://1drv.ms/w/c/d609fb70e39b65c8/EdbLDbqLUR5NtKTXdv1w67EBaI6PS9lHF255VJaaICDSxw?e=Ij6GOH