Topological design and routing for low-Earth orbit satellite networks

TLDR

In low‑Earth‑orbit satellite networks, selecting inter‑satellite links and routing traffic to maximize call capacity is a key design challenge. The study investigates a combined topological design and routing problem for LEO satellite networks with limited inter‑satellite links. The authors model the network as a finite state automaton, then solve a mixed‑integer optimization for each state using a two‑step heuristic with simulated annealing, precomputing link and routing tables that satellites load at each state transition. Simulations demonstrate that the proposed method is applicable to practical LEO satellite networks.

Abstract

We investigate a topological design and routing problem for low Earth orbit (LEO) satellite communication networks where each satellite can have a limited number of direct inter-satellite links (ISLs) to a subset of satellites within its line-of-sight. First, we model LEO satellite network as a FSA (finite state automaton) using satellite constellation information. Second, we solve a combined topological design and routing problem for each configuration corresponding to a state in the FSA. The topological design (or link assignment) problem deals with the selection of ISLs, and the routing problem handles the traffic distribution over the selected links to maximize the number of carried calls. This NP-complete mixed integer optimization problem is solved by a two-step heuristic algorithm that first solves the topological design problem, and then finds the optimal routing. The algorithm is iterated using the simulated annealing technique until the near-optimal solution is found. The link assignment table and the routing table that are pre-calculated off-line for each state are loaded into the satellites and a new set of these tables are retrieved at each state transition. The simulation result shows that the proposed method is applicable to practical LEO satellite networks.