# Navigation Resource Allocation Algorithm for LEO Constellations Based on Dynamic Programming
## 3 Navigation Resource Allocation Algorithm Based on Dynamic Programming
### Algorithm Process
The optimal allocation scheme for LEO navigation signal transmission and SBM is denoted as \(US_{2}\cup US_{1}\), and \(nS=|US_{2}\cup US_{1}|\) represents the number of LEO satellites used. Based on the above scheme, the pseudocode for the NRAA-DP is shown in Algorithm 1. ```
Input: \(VS_{1}\), \(VS_{2}\), \(VS_{1}\), \(VS_{2}\), \(VS_{1}\), \(VS_{2}\), \(VS_{3}\), \(VS_{4}\), \(VS_{5}\), \(VS_{6}\), \(VS_{7}\), \(VS_{8}\), \(VS_{9}\), \(VS_{10}\), \(VS_{11}\), \(VS_{2}\), \(VS_{10}\), \(VS_{11}\), \
```
1:Constellation parameters, \(P\), \(M\), \(T_{1}\), \(T_{2}\)
2:\(US_{1}\), \(US_{2}\) and \(nS\)
3:begin
4:Initialization:\(WS_{1}=WS_{2}=\{\}\),\(r_{0}=j_{0}=1\), \(T_{0}=T_{1}\), \(T_{0}^{\prime}=T_{2}\). 5:Generate \(VS_{1}\). 6:while\(r_{0}\leq P\)do. 7:while\(T_{0}\
eq 0\)do. 8: Get the best satellite \(SL_{i_{0}}\) for covering \(SN_{r_{0}}\). 9: Update \(VS_{1}\), \(WS_{1}\), \(US_{1}\) and \(T_{0}\). 10:end while
11:\(T_{0}=T_{1}\), \(r_{0}=r_{0}+1\). 12:end while
13:Generate \(VS_{2}\). 14:while\(j_{0}\leq M\)do. 15:while\(\left|\left\{V\left(t,SL_{i_{j}}SG_{j_{0}}\right)\right\}\right|<3\)do. 16:while\(T_{0}^{\prime}\
eq 0\)do. 17: Get the best satellite \(SL_{i_{0}}\) for monitoring \(SG_{j_{0}}\). 18: Update \(VS_{2}\), \(WS_{2}\), \(US_{2}\) and \(T_{0}^{\prime}\). 19:end while
20: Update \(T_{0}^{\prime}\). 21:end while
22:\(T_{0}^{\prime}=T_{2}\), \(j_{0}=j_{0}+1\). 23:end while
24:\(nS=\left|US_{1}\cup US_{2}\right|\)
```

**Algorithm 1** Pseudocode of the NRAA-DP: Navigation Resource Allocation Algorithm based on Dynamic Programming

## 4 Performance Analysis

### Parameter Settings

To evaluate the performance of the NRAA-DP, this section primarily assesses the algorithm's resource utilization and computational complexity. The results are compared with those of the Divide and Conquer Algorithm (DCA) [30] and the Greedy Algorithm (GA) [17]. The core concept of the DCA is to divide the multi-stage problem into multiple single-stage problems, with no interrelation between the stages. Each stage is solved individually to obtain a subset of LEO satellites that can achieve single coverage for each ground station and triple coverage for each GNSS satellite. The union of all these subsets forms the final solution. The core concept of the GA is to first sort the LEO satellites based on their visibility to the ground stations from best to worst. LEO satellites are then sequentially selected and added to the constellation allocation set until single coverage for all ground stations is achieved. The remaining LEO satellites are subsequently sorted based on their visibility to the GNSS satellites from best to worst. LEO satellites are again sequentially selected and added to the constellation allocation set until triple coverage for all GNSS satellites is achieved. The constellation allocation set at this point represents the final solution. The GNSS constellation simulated in this paper is the BDS constellation, including 3 GEO satellites, 3 IGSO satellites, and 24 MEO satellites. The simulated low Earth orbit constellation consists of 216 satellites, including 72 satellites in near-polar orbits and 144 satellites in inclined orbits. In order to reduce the calculation amount, the simulation time is set to 7 days, from 9 October 2021 12:00:00 to 16 October 2021 13:00:00, with a step of 1 min. The parameters of the BDS constellation and LEO constellation are shown in Table 2.

Figure 9 shows the three-dimensional spatial allocation of the two constellations based on a comprehensive of the above constellation parameters. The near-polar orbital LEO satellites are labeled as P0101-P0612, and the inclined orbital LEO satellites are labeled as I0101-I1212. The first two digits represent the orbital plane number, while the last two digits represent the satellite number within each orbital plane. For example, P0506 indicates the sixth LEO satellite in the fifth near-polar orbital plane, and I1010 indicates the 10 th LEO satellite in the 10 th inclined orbital plane.