# Navigation Resource Allocation Algorithm for LEO Constellations Based on Dynamic Programming
## 3 Navigation Resource Allocation Algorithm Based on Dynamic Programming
### Algorithm Process
Based on the resource allocation schemes obtained from different algorithms in Table 3 and the set of visible links between the two constellations, the coverage performance of different constellation allocation schemes for the BDS satellites can be derived, as shown in Figure 17. The results indicate that all three constellation resource allocation schemes meet the requirement for triple coverage at all times. Additionally, the average minimum coverage multiplicities for all BDS satellites achieved by the constellation allocation schemes obtained from the three algorithms are 3, 3, and 22.7, respectively; the average coverage multiplicities are 6, 8, and 30.3, respectively; and the maximum coverage multiplicities are 7.7, 11.3, and 37.4, respectively. Figure 16: Coverage performance of different navigation resource allocation schemes for ground stations. (**a**) NRAA-DP. (**b**) GA. (**c**) DCA. Figure 15: Constellation distribution map of the resource allocation scheme by DCA. (**a**) Inclined orbit satellites. (**b**) Near-polar orbit. As shown in Table 4, the navigation resource allocation schemes obtained from all three algorithms can simultaneously achieve LEO satellites' navigation signal transmission and SBM functions, meeting the requirements for global single coverage and triple coverage of GNSS satellites. The NRNA-DP proposed in this paper yields the optimal solution, with the least number of satellites in the constellation allocation and the highest utilization of LEO satellite resources. The satellite numbers in the resource allocation schemes obtained from the GA and the DCA are 1.4 times and 1.7 times that of the NRNA-DP, respectively, leading to redundant navigation resources, occupying communication resources, and reducing the overall resource utilization of the LEO constellation. This inefficiency arises because the DCA isolates the multi-stage problem into several single-stage problems without considering the solutions of other stages while optimizing each stage. This results in locally optimal solutions for each single-stage problem rather than a globally optimal solution. Similarly, as a centralized algorithm, the GA is prone to getting trapped in local optima. In contrast, the NRNA-DP considers the solution of the previous stage in each single-stage problem, thus achieving an approximate global optimum. ### Computational Complexity

As shown in Figure 10, the visibility between LEO satellites and BDS satellites is highly complex and variable, with 556,021 visible links observed over 7 days. To ensure triple coverage at any given moment, it is necessary to calculate the least common multiple (LCM) of the orbital periods of the LEO constellation and the BDS constellation, which can span several months. During this period, the number of visible links between LEO satellites and BDS satellites can reach millions. Therefore, it is essential to evaluate the complexity of the navigation resource allocation algorithm. Assume there are \(N\) LEO satellites, \(M\) GNSS satellites, and \(P\) ground stations. There are a total of \(Y\) visible links between LEO satellites and ground stations, and \(Z\) visible links between the LEO constellation and the GNSS constellation. On average, each LEO satellite has \(Y/N\) visible links to ground stations and \(Z/N\) visible links to GNSS satellites. Each ground station has \(Y/P\) visible links to LEO satellites, and each GNSS satellite has \(Z/M\)