Clustered Multi-Criteria Routing Algorithm for Mega Low Earth Orbit Satellite Constellations
Jian Jiao, Penglin Yang, Zhuang Du, Ye Wang, Qinyu Zhang
Abstract
Mega low Earth orbit (LEO) satellite constellations are regarded as an emerging paradigm shift in the next generation of network. However, the challenges posed by the mega LEO satellite constellations, such as dynamic network topologies, limited on-board resources, and the multimodal data services present significant obstacles for existing routing algorithms. To address these challenges, we propose a clustered multi-criteria routing (CMCR) algorithm for multimodal data services in mega LEO satellite constellations. First, we develop a clustering approach for mega LEO satellite constellation by taking into account the flying direction, line of sight (LoS) inter-satellite link (ISL) and latitude of satellites, which divides the CMCR into intra- and inter-cluster routing. Then, we construct a time-varying graph to represent the dynamic topology of mega constellations. Both intra- and inter-cluster routing start with the identification of satellites that can establish an ISL based on the time-varying graphs, and then compute the dominant paths for multimodal data services. We introduce the attribute consistency to reflect the relative preference of ISLs for each data service, and the CMCR compares the attributes consistency of ISLs to determine the dominant paths. Thus, our CMCR algorithm selects a routing path for the multimodal data services from the dominant paths with the most preferred attribute, and we define a routing algebraic for our CMCR to demonstrate that it can converge to the optimal path. Simulation results validate that the CMCR outperforms the existing routing algorithms according to preference of multimodal services.