Premium
Time division inter‐satellite link topology generation problem: Modeling and solution
Author(s) -
Chu Xiaogeng,
Chen Yuning
Publication year - 2017
Publication title -
international journal of satellite communications and networking
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.388
H-Index - 39
eISSN - 1542-0981
pISSN - 1542-0973
DOI - 10.1002/sat.1212
Subject(s) - computer science , satellite , network topology , topology (electrical circuits) , division (mathematics) , link (geometry) , dilution of precision , algorithm , range (aeronautics) , distributed computing , global positioning system , computer network , mathematics , telecommunications , materials science , arithmetic , gnss applications , combinatorics , engineering , composite material , aerospace engineering
Summary 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 1 second. 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.