Navigation Resource Allocation Algorithm for LEO Constellations Based on Dynamic Programming (2024)

2.1. Network Model

The navigation resource allocation for the LEO constellation needs to consider two primary types of LEO navigation enhancement functions: navigation signal transmission and SBM. The system architecture is shown in Figure 1.

As depicted in Figure 1, individual LEO satellites are dedicated to a single function—either navigation signal transmission or SBM—but not both simultaneously. This segregation is essential because the power of navigation signals significantly exceeds that of the signals received for SBM. Consequently, if the frequencies of SBM and navigation signal transmission are similar or overlap, substantial interference ensues. To mitigate this, satellites are configured with transceiver isolation, whereby different satellites within the constellation are assigned to either navigation signal transmission or SBM. This ensures that each satellite is optimized for its specific function without cross-interference.

2.2. Constraints and Objective Functions

From the above analysis, it can be seen that the LEO constellation navigation enhancement system has both navigation signal transmission and SBM functions, and its resource allocation algorithm must comprehensively consider the navigation signal transmission and SBM performance.

The constraints of the navigation signal transmission network are as follows:

The constraints of the SBM network are as follows:

3.1. Algorithm Principle

Dynamic Programming, as an operational research method, is adept at resolving complex decision processes across multiple stages [26,27,28]. Central to this method is Bellman’s principle of optimality, which simplifies the problem-solving process by breaking down a multi-stage Decision problem into manageable, single-stage problems. This is achieved through a fundamental recursive relationship that allows for the continuous transformation of the Decision process. Each stage builds upon the previous one, enabling a systematic approach to solving each segment in sequence. As illustrated in Figure 7, Bellman emphasized that the optimal strategy for a multi-level Decision process possesses a critical characteristic: irrespective of the initial state and decision, if any stage and state are considered the initial point, the subsequent decisions must align to form an overall optimal strategy. Specifically, if there is a Decision process whose initial state is $K$ level, and its optimal strategy is $\left\{w(0),w(1),\cdots ,w(K-1)\right\}$, then, for $w(0)$$K-1$ the level-level Decision process whose initial state is, the decision set $\left\{w(1),\cdots ,w(K-1)\right\}$ must be the optimal strategy. The principle of optimality provides a simple and effective method for solving optimization problems in multi-level Decision processes and provides a theoretical basis for deriving recursive equations.

Next, we outline the parameters commonly employed in dynamic programming algorithms [29]:

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:

3.2. 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:

Step 1: Initialize Parameters. Initialize the active link sets for both the navigation signal transmission network, $W{S}_1$, and the SBM network, $W{S}_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 $V{S}_1$. Calculate the set of visible links, $V{S}_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 $V{S}_1$ to calculate the LEO satellite that can cover the ground station $S{N}_{r_0}$ for the longest duration within the time interval $T_0$, denoted as $S{L}_{i_0}$;

Step 3.2: Update $V{S}_1$ and $W{S}_1$. Remove all visible links containing $S{L}_{i_0}$, denoted as $V(t,S{L}_{I_0},S{N}_r)$, from $V{S}_1$ and add them to $W{S}_1$;

Step 3.3: Update $U{S}_1$ sum $T_0$. Add LEO satellites $S{L}_{i_0}$ to $U{S}_1$ and remove the duration that satellite $S{L}_{i_0}$ can cover ground station $S{N}_{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 $U{S}_1$;

Step 4: Determine the visible link set $V{S}_2$. Calculate the set of visible links, $V{S}_2$, between the remaining LEO satellites, excluding $U{S}_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 $V{S}_2$, calculate the LEO satellite that can monitor $S{G}_{j_0}$ for the longest duration within the given time period $T_0^{\prime }$, denoted as $S{L}_{i_0}$;

Step 5.2: Update $V{S}_2$ and $W{S}_2$. Remove all visible links containing $S{L}_{i_0}$, denoted as $V(t,S{L}_{i_0},S{G}_j)$, from $V{S}_2$ and add them to $W{S}_2$;

Step 5.3: Update $U{S}_2$ and $T_0^{\prime }$. Add the LEO satellite $S{L}_{i_0}$ to $U{S}_2$ and remove the duration when GNSS satellites $S{G}_{j_0}$ can be monitored by $S{L}_{i_0}$ from $T_0^{\prime }$.

Step 5.4: Determine whether $T_0^{\prime }$ is 0. If $T_0^{\prime }\ne 0$, go to Step 5.1; otherwise, go to the next Step.

Step 5.5: Check if triple coverage of the GNSS satellite $S{G}_{j_0}$ has been achieved. If it is satisfied, $\left|\right\{V(t,S{L}_i,S{G}_{j_0})\left\}\right|$, $\left|\right\{V(t_0,S{L}_i,S{G}_{j_0})\left\}\right|\in W{S}_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 $S{G}_{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 $U{S}_2$.

Step 6: Obtain the optimal navigation resource allocation scheme for the LEO constellation. The optimal allocation scheme for LEO navigation signal transmission and SBM is denoted as $U{S}_2\cup U{S}_1$, and $nS=|U{S}_2\cup U{S}_1|$ represents the number of LEO satellites used.

The visibility matrix between LEO satellites and ground stations in Step 2 and the visibility matrix between LEO satellites and GNSS satellites in Step 10 can be calculated through analytical algorithms [25] or obtained via STK 11.6 software simulation. Steps 4 to 8 will repeat $P$ times, each time calculating the minimum additional LEO satellites required to achieve single coverage for the ground stations and adding them to $U{S}_1$. Steps 12 to 19 will repeat $M$ times, each time calculating the minimum additional LEO satellites required to achieve triple coverage for the current GNSS satellites and adding them to $U{S}_2$. Finally, output the final $U{S}_1$, $U{S}_2$, and $nS$. $U{S}_1\cup U{S}_2$ represents the optimal allocation scheme for LEO navigation signal transmission and SBM in the LEO constellation, and $nS$ represents the minimum number of LEO satellites required.

4.1. 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 10th LEO satellite in the 10th inclined orbital plane.

Through simulation analysis using STK 11.6 software, it was found that over a period of 7 days, there are a total of 556,021 visible links between the two constellations, all of which are intermittent, with durations ranging from 0.6 s to 5.8 h. For example, Figure 10 shows the set of visible links between the LEO satellite I0101 and BDS satellites over a period of 4 h. For the LEO satellite I0101, there are a total of 77 intermittent links within this 4-h period. Similarly, the visibility situation between 216 LEO satellites and BDS satellites over 7 days is even more complex and variable.

Due to the symmetrical characteristics of global coverage in the east-west and north-south hemispheres within a complete orbital period of the constellation, only 19 ground stations in the northern hemisphere along the 0° longitude from 0° to 90°N, sampled every 5°, are selected for simplicity when evaluating global coverage performance [31], as shown in Figure 11.

Through simulation analysis using STK 11.6 software, it was found that over a period of 7 days, there are a total of 152,190 visible links between the LEO constellation and the 19 ground stations, all of which are intermittent, with durations ranging from 1.1 s to 14.8 min. For example, Figure 12 shows the set of visible links between the LEO satellite I0101 and a ground station over a period of 4 h. For the LEO satellite I0101, there are a total of 19 intermittent links within this 4-h period. Similarly, the visibility situation between 216 LEO satellites and the ground stations over 7 days is even more complex and variable.

4.2. Resource Utilization

The proposed dynamic programming algorithm, the Greedy Algorithm (GA), and the Divide and Conquer Algorithm (DCA) are used for navigation resource allocation of the LEO constellation. The number of LEO satellites required to achieve global single coverage and triple coverage for the BDS constellation are 118, 165, and 201, respectively. The specific constellation allocation results of different algorithms are shown in Table 3.

To more intuitively display the constellation allocation results, the results from Algorithm 1 are shown in Figure 13, Figure 14 and Figure 15. In these Figures, the horizontal axis represents the orbital plane number, and the vertical axis represents the satellite number within each orbital plane.

Based on the resource allocation schemes obtained from different algorithms in Table 3, the set of visible links between the LEO constellation and the ground stations can be used to derive the global coverage performance of the different constellation resource allocation schemes, as shown in Figure 16. The results indicate that all three constellation allocation schemes meet the requirement for single coverage at all times. Additionally, the average minimum coverage multiplicities for ground stations achieved by the constellation allocation schemes obtained from the three algorithms are 1.2, 3.2, and 2.5, respectively; the average coverage multiplicities are 4.5, 7.9, and 7.5, respectively; and the maximum coverage multiplicities are 8.7, 13.2, and 12.7, respectively.

Based on the resource allocation schemes obtained from different algorithms in Table 3 and the set of visible links between the two constellations, the coverage performance of different constellation allocation schemes for the BDS satellites can be derived, as shown in Figure 17. The results indicate that all three constellation resource allocation schemes meet the requirement for triple coverage at all times. Additionally, the average minimum coverage multiplicities for all BDS satellites achieved by the constellation allocation schemes obtained from the three algorithms are 3, 3, and 22.7, respectively; the average coverage multiplicities are 6, 8, and 30.3, respectively; and the maximum coverage multiplicities are 7.7, 11.3, and 37.4, respectively.

As shown in Table 4, the navigation resource allocation schemes obtained from all three algorithms can simultaneously achieve LEO satellites’ navigation signal transmission and SBM functions, meeting the requirements for global single coverage and triple coverage of GNSS satellites. The NRAA-DP proposed in this paper yields the optimal solution, with the least number of satellites in the constellation allocation and the highest utilization of LEO satellite resources. The satellite numbers in the resource allocation schemes obtained from the GA and the DCA are 1.4 times and 1.7 times that of the NRAA-DP, respectively, leading to redundant navigation resources, occupying communication resources, and reducing the overall resource utilization of the LEO constellation.

This inefficiency arises because the DCA isolates the multi-stage problem into several single-stage problems without considering the solutions of other stages while optimizing each stage. This results in locally optimal solutions for each single-stage problem rather than a globally optimal solution. Similarly, as a centralized algorithm, the GA is prone to getting trapped in local optima. In contrast, the NRAA-DP considers the solution of the previous stage in each single-stage problem, thus achieving an approximate global optimum.

4.3. Computational Complexity

As shown in Figure 10, the visibility between LEO satellites and BDS satellites is highly complex and variable, with 556,021 visible links observed over 7 days. To ensure triple coverage at any given moment, it is necessary to calculate the least common multiple (LCM) of the orbital periods of the LEO constellation and the BDS constellation, which can span several months. During this period, the number of visible links between LEO satellites and BDS satellites can reach millions. Therefore, it is essential to evaluate the complexity of the navigation resource allocation algorithm.

Assume there are $N$ LEO satellites, $M$ GNSS satellites, and $P$ ground stations. There are a total of $Y$ visible links between LEO satellites and ground stations, and $Z$ visible links between the LEO constellation and the GNSS constellation. On average, each LEO satellite has $Y/N$ visible links to ground stations and $Z/N$ visible links to GNSS satellites. Each ground station has $Y/P$ visible links to LEO satellites, and each GNSS satellite has $Z/M$ 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 $2PY/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 $2MZ/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·\left(N+2Y/N+1\right)$ 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·\left(N-S_1+2Z/N+1\right)$ 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. Running the above three algorithms on the same MATLAB simulation platform on the same computer, the program execution times were 145 s, 562 s, and 1807 s, respectively, further validating this conclusion.

In summary, the DCA exhibits moderate resource utilization but has high computational complexity due to its recursive nature. Specifically, it requires significantly more iterations and computations to achieve optimal coverage, leading to longer processing times. Conversely, the GA demonstrates lower computational complexity by following a heuristic approach, which involves sequentially selecting satellites based on visibility criteria. However, this method may result in suboptimal resource utilization, as it does not consider the global optimum solution.