DYNAMIC MINIMUM SPANNING TREE ROUTING FOR MULTI-AGENT SYSTEMS USING REAL-TIME GPS UPDATES

Abstract

Infrastructure-less mobile networks are increasingly important for applications such as disaster response, autonomous coordination, and remote field operations. However, maintaining efficient communication routes in such environments is challenging because node mobility continuously changes network topology. This study addresses the problem of maintaining stable and efficient routing among mobile nodes with limited computational capability. The objective of this research is to design and evaluate a real-time routing system for mobile networks using Minimum Spanning Tree (MST) optimization. The proposed system integrates GPS-enabled ESP32 nodes with a centralized server that computes network topology using Kruskal’s MST algorithm. A client–server architecture is implemented in which mobile nodes periodically send location updates to the server. The server constructs a weighted graph, computes the MST, and distributes routing instructions back to each node. Experiments were conducted under three mobility scenarios—static, linear motion, and random walk producing a total of 2,700 position updates. The results show that the system maintains server computation times below 10 ms and end-to-end latency between 187–223 ms. The Tree Stability Index reached 1.000 in static conditions, 0.947 during linear motion, and 0.683 in random mobility. These results demonstrate that the proposed approach provides efficient and responsive routing for mobile networks operating without communication infrastructure.