# Navigation Resource Allocation Algorithm for LEO Constellations Based on Dynamic Programming
## 2 Model Analysis of LEO Constellation Navigation Resource Allocation
### Constraints and Objective Functions
The complete return period of the two constellations of the LEO constellation and the GNSS constellation is expressed as \(T_{2}\). When the satellite constellation is determined, its trajectory is periodic and fixed, so the visibility of the two constellations within a time period \(T_{2}\) includes the visibility of the two constellations at any time. All visible links between LEO satellites and GNSS satellites within the time period \(T_{2}\) constitute the visible link set of the SBM network, which is defined as \(VS_{2}\) and can be expressed as  
\[VS_{2}=\big{\{}V_{1}\big{(}t,SL_{i},SG_{j}\big{)}\big{\}}_{t\in T_{2},i\in[1,2,\cdots,N],j\in[1,2,\cdots,M]} \tag{6}\]  
Some links are selected from the visible link set \(VS_{2}\) as SBM links. All links used for SBM in the time period \(T_{2}\) constitute the activated link set of the SBM network, which is defined as \(WS_{2}\), which can be expressed as  
\[WS_{2}=\big{\{}V_{2}\big{(}t,SL_{i},SG_{j}\big{)}\big{\}}_{t\in T_{2},i\in[1,2,\cdots,N],j\in[1,2,\cdots,M]} \tag{7}\]  
The constraints of the SBM network are as follows:  
(1) The SBM link must first be a visible link; that is, the activated link set of the SBM network is a subset of the visible link set, expressed as  
\[WS_{2}\subseteq VS_{2} \tag{8}\]  
(2) In order to achieve integrity monitoring and multiple voting of GNSS and improve the global integrity of GNSS, LEO constellations should have at least triple coverage of GNSS satellites [25]. At least triple coverage is required for SBM performance to ensure redundancy and reliability in signal monitoring. This level of coverage allows for cross-verification of data from multiple satellites, enhancing the accuracy and robustness of the monitoring process. In this condition, there are at least three monitoring links for any GNSS satellite \(SG_{j}\) at any time \(t\), which can be expressed as  
\[\text{card}\big{(}\big{\{}V\big{(}t_{0},SL_{i_{0}},SG_{j_{0}}\big{)}\big{\}} \big{)}\geq 3,V\big{(}t_{0},SL_{i_{0}},SG_{j_{0}}\big{)}\in WS_{2},\forall j_{0} \in[1,2,\cdots,M],\forall t_{0}\in T_{2} \tag{9}\]  
where the 'card(0' function is used to represent the cardinality of a set, which is the number of elements in the set. The set of LEO satellites \(US_{2}\) used for SBM is expressed as  
\[US_{2}=\big{\{}SL_{i_{0}}\big{\}},i_{0}\in[1,2,\cdots,N] \tag{10}\]  
Since LEO satellites need to be isolated from receiving and transmitting, SBM or navigation signal transmission functions are implemented on different LEO satellites. Therefore, a certain LEO satellite can only be used to realize one function of SBM or navigation signal transmission at the same time, that is, a collection of LEO satellites for navigation signal transmission \(US_{1}\) and a collection of LEO satellites for SBM. The sets \(US_{2}\) have no intersection, expressed as  
\[WS_{1}=\left\{V_{2}(t,SL_{i},SN_{r})\right\}_{t\in T_{1},i\in[1,2,\cdots,N],r \in[1,2,\cdots,P]} \tag{2}\]0  
The number of LEO satellites used for navigation enhancement is expressed as \(nS\). Since the optimization goal of low-orbit constellation navigation resources is to use the least number of satellites to achieve navigation signal broadcast and SBM functions, the objective function is expressed as  
\[WS_{1}=\left\{V_{2}(t,SL_{i},SN_{r})\right\}_{t\in T_{1},i\in[1,2,\cdots,N],r \in[1,2,\cdots,P]} \tag{2}\]1  
The objective function is subject to the constraints of the above Equations (1)-(11). By sorting out the constraints, we can obtain  
\[\left\{ \begin{array}{l}WS_{1}\subseteq VS_{1}\\ \left|\left\{V\left(t_{0},SL_{i_{0}},SN_{t_{0}}\right)\right\}\right|\geq 1, \ V\left(t_{0},SL_{i_{0}},SN_{t_{0}}\right)\in WS_{1},\forall v_{0}\in[1,2, \cdots,P],\forall t_{0}\in T_{1}\\ WS_{2}\subseteq VS_{2}\\ \left|\left\{V\left(t_{0},SL_{i_{0}},SG_{i_{0}}\right)\right\}\right|\geq 3, \ V\left(t_{0},SL_{i_{0}},SG_{i_{0}}\right)\in WS_{2},\forall j_{0}\in[1,2, \cdots,M],\forall t_{0}\in T_{2}\\ US_{1}\cap US_{2}=\varnothing\end{array} \right. \tag{13}\]