# Navigation Resource Allocation Algorithm for LEO Constellations Based on Dynamic Programming
## 3 Navigation Resource Allocation Algorithm Based on Dynamic Programming
### Algorithm Process
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Algorithm**} & \multirow{2}{*}{
\begin{tabular}{c} **Number of Satellites in the** \\ **Resource Allocation Scheme** \\ \end{tabular} } & \multicolumn{3}{c}{**Coverage Multiplicity for**} & \multicolumn{3}{c}{**Coverage Multiplicity for**} \\ \cline{3-8}  & & \multicolumn{3}{c}{**Ground Stations**} & \multicolumn{3}{c}{**BDS Satellites**} \\ \cline{3-8}  & & \multicolumn{1}{c}{**Minimum**} & **Average** & **Maximum** & **Minimum** & **Average** & **Maximum** \\ \hline NRNA-DP & 118 & 1.2 & 4.5 & 8.7 & 3 & 6 & _7.7_ \\ GA & 165 & 3.2 & 7.9 & 13.2 & 3 & 8 & 11.3 \\ DCA & 201 & 2.5 & 7.5 & 12.7 & 2 2.7 & 30.3 & _37.4_ \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Coverage performance of different navigation resource allocation schemes. Figure 17: Coverage performance of different navigation resource allocation schemes for BDS satellites. (**a**) NRNA-DP. (**b**) GA. (**c**) DCA. visible links to LEO satellites. The number of LEO satellites required for the allocation obtained by different algorithms is \(S_{1}+S_{2}\), where \(S_{1}\) is the number of LEO satellites used for navigation signal transmission, and \(S_{2}\) is the number of LEO satellites used for SBM. As shown in Algorithm 1, in the NRAA-DP, the first Step is to determine the LEO satellite allocation for navigation signal transmission. Step 3 and Step 4 each require one logical operation, Step 5 requires \(Y\) addition operations and \(N\) logical operations, Step 6 requires \(4Y/N\) logical operations, and Step 8 requires one addition operation. Throughout the entire process, Steps 4 to 6 are repeated \(S_{1}\) times and Steps 3 and 8 are repeated \(P\) times. Next, the LEO satellite allocation for SBM is determined. Step 11, Step 12, and Step 13 each require one logical operation, Step 14 requires \(Z\) addition operations and \(N\) logical operations, Step 15 requires \(4Z/N\) logical operations, and Step 19 requires one addition operation. Throughout the entire process, Steps 12 to 15 are repeated \(S_{2}\) times, and Steps 11 and 19 are repeated \(M\) times. In the GA, the LEO satellites are first sorted based on their visibility to the ground stations from best to worst, requiring \(Y\) addition operations and \(N\) logical operations. Then, LEO satellites are sequentially selected and added to the navigation signal transmission satellite set. For each additional LEO satellite, the current coverage situation needs to be evaluated, requiring \(2 PY/N\) logical operations. This Step is repeated \(S_{1}\) times. Next, the LEO satellites are sorted based on their visibility to the GNSS satellites from best to worst, requiring \(Z\) addition operations and \(N-S_{1}\) logical operations. LEO satellites are then sequentially selected and added to the SBM satellite set. For each additional LEO satellite, the current coverage situation needs to be evaluated, requiring \(2 MZ/N\) logical operations. This Step is repeated \(S_{2}\) times. In the DCA, each ground station's requirement for single coverage by LEO satellites is solved individually, requiring \(YP/S_{1}\) addition operations and \(P/S_{1}\cdot(N+2Y/N+1)\) logical operations each time. This step is repeated \(P\) times. Then, for each GNSS satellite, the requirement for triple coverage by LEO satellites is solved individually, requiring \(ZM/S_{2}\) addition operations and \(M/S_{2}\cdot(N-S_{1}+2Z/N+1)\) logical operations each time. This step is repeated \(M\) times. Table 5 compares the computational complexity of these three algorithms. The values in parentheses below each cell indicate the computational complexity of the simulation cases discussed in this section. As shown in Table 5, the NRAA-DP has the lowest complexity among the three algorithms. Moreover, this advantage in computational complexity increases with the number of LEO satellites and GNSS satellites.