Rolling weight-matching methods for the inter-satellite link assignment in global navigation satellite systems

Inter-satellite links (ISLs) have become an important technology for developing global navigation satellite systems (GNSSs). Due to satellite platform restrictions, the number of ISLs is limited, how to optimize ISL assignment is a crucial challenge. A mathematical optimization model is formulated that accommodates both ranging and communication requirements. We prove that the ISL assignment problem for ranging performance optimization is non-deterministic polynomial-time complete (NP-complete), and propose a rolling weight-matching method to solve the problem, where Edmonds’ blossom algorithm is used to find a maximum weight matching. Then, a weight enhancement strategy is designed to improve communication performance, classifying links into four types and adjusting the corresponding weights. A simulation experiment consisting of 10,080 epochs is run to evaluate the effectiveness of the proposed methods. The results demonstrate that the solution found is close to the optimal solution of the ranging performance, and the method with weight enhancement obtains better solutions than the other studied algorithms on both objectives.