# Navigation Resource Allocation Algorithm for LEO Constellations Based on Dynamic Programming
###### Abstract
GNSS satellite network link allocation problem; [PERSON] [9] designed a topological inter-satellite link allocation algorithm for broadband LEO satellite systems, which prioritizes inter-satellite communication; [PERSON] [10] used the mean-variance theory optimizes the network link capacity under random business conditions; [PERSON] [11] and [PERSON] [12] proposed a random link allocation scheme for satellite optical networks based on laser links, randomly generated an arbitrarily connected network topology; [PERSON] [13] proposed an algorithm with a constant time interval for inter-satellite link topology transformation with the minimization of PDOP value as the optimization goal; [PERSON] [14], with link stability as a prerequisite, proposed an extensive weighted inter-satellite link allocation scheme that optimized both link latency and link switching performance. [PERSON] [15; 16], aiming to fully utilize the limited communication terminal resources on board the satellite, put forward a link allocation scheme based on the perfect matching model. This scheme transforms the link allocation into a perfect matching problem of a mixed complete bipartite graph. The inter-satellite link solution derived from this approach can be applied to all communication terminals on the satellite. Inter-satellite links for navigation satellites need to take into account the dual requirements of communication and measurement. [PERSON] [17; 18] applied the Greedy Algorithm to the link allocation of inter-satellite communication and inter-satellite observation can ensure that the number of inter-satellite observations is maximized while reducing the communication cost of the entire network as much as possible; [PERSON] [19] proposed a method based on the average of the entire network A link allocation algorithm weighted by the observation position accuracy factor and the entire network delay. The optimization goal of this algorithm is to minimize the link cost; [PERSON] [20] proposed an inter-satellite link allocation suitable for GNSS satellite networks, a cascade optimization design method that takes into account both communication and ranging capabilities; [PERSON] [21] proposed a group-based time slot scheduling method to obtain more ranging observation data and realize satellite and ranging Fast communication with a short delay between measurement and control stations. [PERSON] [22], [PERSON] [23], and [PERSON] [24] used genetic algorithms for inter-satellite communication and ranging link allocation in navigation constellations, which improved the operating efficiency of the algorithm to a certain extent but had shortcomings such as poor fault tolerance and slow convergence speed of the algorithm. In summary, existing research on satellite navigation resource allocation solves the problem of link resource allocation between navigation satellites in the same orbit. The goal is to utilize all resources to maximize inter-satellite communication or ranging needs, and the navigation resource allocation in LEO constellations is to use as few resources as possible to maximize navigation enhancement capabilities among all resources, and the mission goals are different; secondly, because the number of satellites in previous navigation constellations is small, usually only dozens, and each satellite only needs to consider the link allocation between itself and surrounding satellites visible in a short period, and the calculation amount is generally not large. Future LEO satellite systems are usually mega-constellations composed of hundreds to thousands of satellites, and LEO satellites move extremely fast, resulting in complex and changeable visibility between LEO satellites and mid- and high-orbit satellites. Moreover, in order to achieve global optimization, it is necessary to consider the visibility of the LEO constellation period and the least common multiple of the GNSS constellation period, which may last for several months.