# Navigation Resource Allocation Algorithm for LEO Constellations Based on Dynamic Programming
## 3 Navigation Resource Allocation Algorithm Based on Dynamic Programming
### Algorithm Process  
The complete process of NRAA-DP is shown in Figure 8. This algorithm can be summarized into six specific steps, detailed as follows:  
Figure 8: Flowchart of the NRAA-DP. Step 1: Initialize Parameters. Initialize the active link sets for both the navigation signal transmission network, \(WS_{1}\), and the SBM network, \(WS_{2}\), to be empty. Set the initial identifier for the ground stations as \(r_{0}=1\), with the required coverage time denoted by \(T_{0}\), where \(T_{0}=T_{1}\). For GNSS satellites, set the initial identifier as \(j_{0}=1\), with the monitoring duration required indicated by \(T_{0}^{\prime}\), where \(T_{0}^{\prime}=T_{2}\);  
Step 2: Determine the visible link set \(VS_{1}\). Calculate the set of visible links, \(VS_{1}\), between the LEO constellation and ground stations within the time interval \(T_{0}\);  
Step 3: Determine the optimal LEO satellite allocation to achieve single-layer coverage of ground stations. The specific steps are as follows:  
Step 3.1: Determine the optimal LEO satellite for covering the ground station. Utilize the visible link set \(VS_{1}\) to calculate the LEO satellite that can cover the ground station \(SN_{r_{0}}\) for the longest duration within the time interval \(T_{0}\), denoted as \(SL_{i_{0}}\);  
Step 3.2: Update \(VS_{1}\) and \(WS_{1}\). Remove all visible links containing \(SL_{i_{0}}\), denoted as \(V(t,SL_{i_{0}},SN_{r})\), from \(VS_{1}\) and add them to \(WS_{1}\);  
Step 3.3: Update \(US_{1}\) sum \(T_{0}\). Add LEO satellites \(SL_{i_{0}}\) to \(US_{1}\) and remove the duration that satellite \(SL_{i_{0}}\) can cover ground station \(SN_{r_{0}}\) from the time interval \(T_{0}\);  
Step 3.4: Determine \(T_{0}\) whether it is 0. If \(T_{0}=0\), let \(T_{0}=T_{1}\), \(r_{0}=r_{0}+1\), then go to Step 3.1; otherwise, go to Step 3.1 directly;  
Step 3.5: When \(r_{0}=P\), the optimal LEO satellite allocation that achieves single-layer coverage of all ground stations can be obtained, denoted as \(US_{1}\);  
Step 4: Determine the visible link set \(VS_{2}\). Calculate the set of visible links, \(VS_{2}\), between the remaining LEO satellites, excluding \(US_{1}\), and the GNSS constellation within the time interval \(T_{0}^{\prime}\);  
Step 5: Determine the optimal allocation of LEO satellites to achieve triple coverage of GNSS satellites. The specific steps are as follows:  
Step 5.1: Determine the best LEO satellite for monitoring GNSS satellites. According to \(VS_{2}\), calculate the LEO satellite that can monitor \(SG_{j_{0}}\) for the longest duration within the given time period \(T_{0}^{\prime}\), denoted as \(SL_{i_{0}}\);  
Step 5.2: Update \(VS_{2}\) and \(WS_{2}\). Remove all visible links containing \(SL_{i_{0}}\), denoted as \(V(t,SL_{i_{0}},SG_{j})\), from \(VS_{2}\) and add them to \(WS_{2}\);  
Step 5.3: Update \(US_{2}\) and \(T_{0}^{\prime}\). Add the LEO satellite \(SL_{i_{0}}\) to \(US_{2}\) and remove the duration when GNSS satellites \(SG_{j_{0}}\) can be monitored by \(SL_{i_{0}}\) from \(T_{0}^{\prime}\). Step 5.4: Determine whether \(T_{0}^{\prime}\) is 0. If \(T_{0}^{\prime}\
eq 0\), go to Step 5.1; otherwise, go to the next Step. Step 5.5: Check if triple coverage of the GNSS satellite \(SG_{j_{0}}\) has been achieved. If it is satisfied, \(|\left\{V(t,SL_{i_{0}},SG_{j_{0}})\right\}|\), \(|\left\{V(t_{0},SL_{i_{0}},SG_{j_{0}})\right\}|\)\(\in WS_{2}\), \(\forall t_{0}\in T_{2}\), let \(T_{0}^{\prime}=T_{2}\),\(j_{0}=j_{0}+1\), and then go to Step 5.1; if it is not satisfied, let \(T_{0}^{\prime}\) equal to the time period in which triple coverage of \(SG_{j_{0}}\) has not been achieved, and then go to Step 5.1. Step 5.6: When \(j_{0}=M\), the optimal allocation of LEO satellites for achieving triple coverage of all GNSS satellites is obtained, denoted as \(US_{2}\). Step 6: Obtain the optimal navigation resource allocation scheme for the LEO constellation.