Routing Algorithms for VLEO Constellations

Very Low Earth Orbit (VLEO) satellite constellations are gaining attention for enabling low-latency, high-throughput non-terrestrial networks and high-resolution Earth observation. Operating at 300–500 km, they offer reduced propagation delays and stronger signals but also face challenges such as increased atmospheric drag, limited satellite lifespans, high Doppler shifts, and fast-changing topologies that complicate routing. Efficient routing is critical in these dynamic environments. DisCoRoute, a recently proposed heuristic, has shown strong performance under such conditions. This work builds on it, with two primary objectives. The first was to assess its performance under time-varying conditions. Starting from an existing MATLAB implementation, the code was adapted to reflect the dynamic positions of satellites over time. The analysis showed that latency between a fixed source and destination varies over time due to orbital geometry or route changes. Additionally, the frequency of path changes was evaluated across different sampling intervals to identify the time step that ensures route stability. The second objective focused on adapting DisCoRoute to a revised satellite topology in which each node has three communication terminals: Two for intraplane links and one for interplane. This deviates from the original four-terminal setup, which included two interplane links. Several DisCoRoute variants were developed for this three-terminal configuration, and the most effective was selected and named DisCo3T. Its performance was benchmarked against a modified Dijkstra algorithm adapted to the same network structure. To further improve routing efficiency, a novel method was devised to compute the minimum number of Inter-Satellite Link (ISL) hops between any two nodes in the new topology. A new mathematical model, called Interleaved Scenario - MinHopCount(IS-MHC), was formulated and implemented in MATLAB, allowing direct comparison with Dijkstra-based results under evenly distributed planes and satellites. The method consistently matched the theoretical minimum hop counts obtained through benchmarking. In the final phase of the research, the optimized hop-count method was integrated into an enhanced version of the DisCo3T algorithm. While preserving the original structure, this new version leveraged the refined hop-count calculation to approximate optimal path selection. The resulting routing method outperformed traditional shortest-path algorithms such as Dijkstra in terms of computational efficiency, requiring only 3.56% of the execution time needed by Dijkstra-based approaches, while maintaining near-optimal latency performance with a gap of just 2.5%.