# Navigation Resource Allocation Algorithm for LEO Constellations Based on Dynamic Programming
## 3 Navigation Resource Allocation Algorithm Based on Dynamic Programming
### Algorithm Process
Running the above three algorithms on the same MATLAB simulation platform on the same computer, the program execution times were 145 s, 562 s, and 1807 s, respectively, further validating this conclusion. In summary, the DCA exhibits moderate resource utilization but has high computational complexity due to its recursive nature. Specifically, it requires significantly more iterations and computations to achieve optimal coverage, leading to longer processing times. Conversely, the GA demonstrates lower computational complexity by following a heuristic approach, which involves sequentially selecting satellites based on visibility criteria. However, this method may result in suboptimal resource utilization, as it does not consider the global optimum solution. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Algorithm** & **Logical Operation** & **Addition Operation** \\ \hline NRAA-DP & \((1+N+4Y/N)S_{1}+P+(1+N+4Z/N)S_{2}+M\) & \(YS_{1}+P+ZS_{2}+M\) \\  & \((8.6\times 10^{6})\) & \((2.1\times 10^{5})\) \\ GA & \(2S_{1}PY/N+2S_{2}MZ/N+2N-S_{1}\) & \(Y+Z\) \\  & \((5.8\times 10^{7})\) & \((7.1\times 10^{5})\) \\ DCA & \((N+2Y/N+1)P^{2}/S_{1}+(N-S_{1}+2Z/N+1)M^{2}/S_{2}\) & \(YP^{2}/S_{1}+ZM^{2}/S_{2}\) \\  & \((1.1\times 10^{8})\) & \((1.2\times 10^{7})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Comparison of the computational complexity of three algorithms. ## 5 Conclusions

This paper proposes a navigation resource allocation algorithm based on dynamic programming (NRAA-DP) for the problem of navigation resource allocation in LEO constellations. Under this algorithm, a network model for LEO constellation navigation resource allocation is first established. Within the constraints of visibility time windows and on-board transceiver isolation, the objective is to use the minimum number of LEO satellites to achieve navigation signal transmission and SBM. The mathematical expressions for the resource allocation constraints and optimization objectives are derived, and the dynamic programming method is used to solve the optimal resource allocation scheme. The analysis results indicate that this algorithm can obtain the global optimal solution with relatively low computational complexity. Compared to the Greedy Algorithm (GA) and the Divide and Conquer Algorithm (DCA), the resource allocation scheme obtained by this algorithm has the highest resource utilization rate and the lowest computational complexity. When the GNSS constellation is the BDS constellation, and the LEO constellation size is 216 satellites, the resource utilization rate of the NRAA-DP algorithm is 1.4 times and 1.7 times higher than that of the GA and DCA, respectively, and it has the lowest computational complexity among the three algorithms. This advantage increases with the size of the constellation. By optimizing the allocation of navigation resources, the NRAA-DP algorithm enhances the overall efficiency of the LEO constellation. In addition, efficient resource allocation translates to fewer satellites required to achieve the desired coverage and performance. This reduction in the number of satellites can substantially lower the operational and maintenance costs associated with managing large LEO constellations. In summary, the NRAA-DP algorithm not only improves the efficiency and effectiveness of the LEO constellation but also offers substantial cost savings. Future research will focus on incorporating more complex constraints, such as multi-mission requirements and inter-satellite communication limits. Additionally, we plan to test the algorithm with different GNSS constellations to evaluate its adaptability and robustness. **Author Contributions:** Methodology, S.W. ; validation, [PERSON], [PERSON] ([PERSON]), [PERSON] ([PERSON]), [PERSON], and [PERSON] ([PERSON]); writing--original draft preparation, [PERSON] and J.L. ([PERSON]); writing--review and editing, [PERSON], [PERSON] ([PERSON]), [PERSON] and [PERSON]. ([PERSON]); supervision, [PERSON] All authors have read and agreed to the published version of the manuscript.