# Navigation Resource Allocation Algorithm for LEO Constellations Based on Dynamic Programming
## 3 Navigation Resource Allocation Algorithm Based on Dynamic Programming
### Algorithm Principle
Performance index function: The objective function used to compare the quality of selected strategies is known as the performance index function. Therefore, according to the dynamic programming algorithm, the problem of optimal allocation of LEO constellation navigation resources can be decomposed into multiple single-stage navigation resource allocation sub-problems. In this paper, each ground station coverage sub-problem and each GNSS satellite monitoring sub-problem are treated as a single-stage process. Since there are \(P\) ground stations and \(M\) GNSS satellites, there are a total of \(P+M\) sub-problems. The goal is to find the optimal resource allocation for each sub-problem, which involves determining the minimum number of LEO satellites required to achieve single coverage for each ground station and triple coverage for each GNSS satellite. When solving each sub-problem, the solutions obtained from the previous stages are considered. For example, when solving for the optimal satellite configuration for the \(P\)-th ground station, the optimal satellite configurations for the previous \(P-1\) ground stations are taken into account. If the optimal satellite configuration for the previous \(P-1\) ground stations already covers the \(P\)-th ground station, then no additional satellites are needed. By integrating the solutions of the P+M sub-problems in this manner, we can obtain an approximate optimal solution for the overall problem, which covers \(P\) ground stations and \(M\) GNSS satellites. From the constraints and objective functions described in the previous section, the parameters of the navigation resource allocation algorithm based on dynamic programming (NRAA-DP) are as follows:  
1. Stage: Each coverage sub-problem for ground stations and each monitoring sub-problem for GNSS satellites constitutes a single-stage process, resulting in a total of \(P+M\) stages, denoted as the stage variable \(k=P+M\). Different low Earth orbit navigation enhancement systems prioritize tasks differently; in this section, LEO navigation signals transmission is considered a higher priority than SBM. This means achieving uniform global coverage of the constellation takes precedence over uniform coverage of GNSS. Thus, in dynamic programming, the first \(P\) stages cover ground stations, followed by MM stages covering GNSS satellites;
2. Status: When \(k\leq P\), the state variable \(s_{k}\) represents that LEO satellites have achieved at least single-layer coverage for \(k\) ground stations. When \(P<k\leq M\), \(s_{k}\) indicatesthat LEO satellites have achieved at least single-layer coverage for \(P\) ground stations and at least triple-layer coverage for \(k\) GNSS satellites;
3. State space: \(S_{k}\) is the set of all possible values for the state variable \(s_{k}\);
4. Decision: The decision variable \(\mu_{k}(s_{k})\) for stage \(k\) needed to achieve state \(s_{k}\) is the set of LEO satellites required for that state;
5. State transition: The state transition function \(T_{k}(s_{k},\mu_{k})\) defines the set of additional LEO satellites required to transition from state \(s_{k}\) to state \(s_{k+1}\);
6. Strategy: The permissible decision set \(D_{k}(s_{k})\) includes all available LEO satellites, denoted as \(D_{k}(s_{k})=\left\{SL_{i_{0}}\right\}\), \(i_{0}=1,2,\cdots,N\), thus the decision variable \(\mu_{k}(s_{k})\in D_{k}(s_{k})\);
7. Stage indicator function: The stage indicator function \(v_{k}(s_{k},\mu_{k})\) aims to minimize the number of LEO satellites used to achieve the state \(s_{k}\), represented as Minimize : \(|\mu_{k}(s_{k})|\). The stage indicator function is constrained by Equation (13);
8. Performance index function: The performance index function quantifies the minimum number of LEO satellites required to achieve the final state, which includes at least single coverage for \(P\) ground stations and at least triple coverage for \(M\) GNSS satellites. This corresponds to the objective function in Equation (12), denoted as Minimize : \(nS=|US_{1}\cup US_{2}|\).