# Navigation Resource Allocation Algorithm for LEO Constellations Based on Dynamic Programming
###### Abstract  
Navigation resource allocation for low-earth-orbit (LEO) constellations refers to the optimal allocation of navigational assets when the number and allocation of satellites in the LEO constellation have been determined. LEO constellations can not only transmit navigation enhancement signals but also enable space-based monitoring (SBM) for real-time assessment of GNSS signal quality. However, proximity in the frequencies of LEO navigation signals and SBM can lead to significant interference, necessitating isolated transmission and reception. This separation requires that SBM and navigation signal transmission be carried out by different satellites within the constellation, thus demanding a strategic allocation of satellite resources. Given the vast number of satellites and their rapid movement, the visibility among LEO, medium-earth-orbit (MEO), and geostationary orbit (GEO) satellites is highly dynamic, presenting substantial challenges in resource allocation due to the computational intensity involved. Therefore, this paper proposes an optimal allocation algorithm for LEO constellation navigation resources based on dynamic programming. In this algorithm, a network model for the allocation of navigation resources in LEO constellations is initially established. Under the constraints of visibility time windows and onboard transmission and reception isolation, the objective is set to minimize the number of LEO satellites used while achieving effective navigation signal transmission and SBM. The constraints of resource allocation and the mathematical expression of the optimization objective are derived. A dynamic programming approach is then employed to determine the optimal resource allocation scheme. Analytical results demonstrate that compared to Greedy and Divide-and-Conquer algorithms, this algorithm achieves the highest resource utilization rate and the lowest computational complexity, making it highly valuable for future resource allocation in LEO constellations. LEO navigation enhancement; space-based monitoring; dynamic programming; resource allocation 20241622231  
15 May 202417 June 202417 June 202418 June 202418 June 202  
allocation of navigation resources in LEO constellations. This involves strategically distributing satellite functions to maximize the efficiency of navigation enhancement functions while minimizing resource expenditure. LEO navigation enhancement functions mainly include navigation signal transmission and space-based monitoring (SBM) [4; 5; 6]. Navigation signal transmission refers to LEO satellite transmission navigation enhancement signals to ground users to achieve information enhancement or signal enhancement of GNSS signals; SBM refers to configuring high-precision GNSS monitoring receivers on LEO satellites to receive downlink signals of GNSSs and analyze the quality of these signals. Suppose the frequency band of SBM is consistent with or close to that of LEO navigation signals; the transmission power of LEO navigation signals is much higher than the receiving power of GNSS signals, which will cause strong interference to SBM. To solve this problem, transceiver isolation is usually used; that is, SBM or navigation signal enhancement functions are implemented on different LEO satellites. Therefore, satellite resources used for SBM need to be rationally allocated to maximize the need for SBM and navigation signal enhancement. Since the GNSS system is a pure navigation system and does not have communication and SBM functions, it does not have the above problems. Therefore, the current research on the optimal allocation of satellite navigation resources mainly focuses on the allocation and scheduling of inter-satellite links. To improve the communication capabilities of inter-satellite links in navigation constellations, [PERSON] [7] and [PERSON] [8] took reducing call blocking probability and inter-satellite communication delay as optimization goals, respectively, and used the simulated annealing algorithm to solve the problems of discontinuous connections.