Time division inter-satellite link topology generation problem: Modeling and solution

In this paper, we study the time-division inter-satellite link topology generation (TDILTG) problem for the well-known Chinese BeiDou Global Navigation Satellite System. The TDILTG problem consists in generating a time-division topology of the inter-satellite link network for the navigation satellite system to spread systematic data to all satellites via a few source satellites with the purpose of minimizing the time required to spread the data. We propose a mathematical model to formulate the TDILTG problem and study its 2 lower bounds through a thorough analysis of the problem characteristics. We also present a deterministic constructive (DC) algorithm to solve this problem approximately but very quickly, with a time complexity of O(n(3)), where n is the number of satellites. Extensive experimental studies on a wide range of randomly generated instances show that the proposed DC algorithm is able to obtain the optimal solutions for most tested instances in less than 1second. Meanwhile, we also validate that the DC algorithm performs well when the problem scale is large. Furthermore, we provide insights of the effects of different instance parameters on the final results.