Keywords

1 Introduction

With the rise of LEO communication constellations in recent years, the LEO navigation augmentation technology developed through integration with communication satellites has become a hot spot in the field of satellite navigation augmentation. The satellite-ground link planning problem is to reasonably arrange when the ground station will establish a satellite-ground link with which satellite, its purpose is to maximize the data transmission efficiency of the entire network.

At present, relevant research focuses on satellite handover and satellite mission planning. Since the user's service demand time may be longer than the coverage time of a LEO satellite, the user needs to switch from the current access satellite to another visible satellite [1, 2], this process is the handover between satellites. The current connection should continue uninterrupted, this will bring some conflicts on resources [3]. Literature [4] proposed three handover criteria. In the literature [5, 6], the signal strength is also a satellite handover criterion which is related to the pitch angle of the link. Literature [7] analyzed the user coverage time of the LEO satellite network, and theoretically proposed the lower limit of the number of handovers. Literature [8] proposes a handover strategy based on graph theory. In order to solve the multi-link state that the satellite changes with the movement of the user, the dynamic satellite handover prediction problem is studied in the literature [9]. The differences between satellite handover and satellite-ground link planning are as follows: ① Former is for communication data, while the latter is for navigation augmentation data. ② Former is to study how to access the handover satellite, as far as possible to ensure that user services on the ground are not interrupted. However, the latter is to study how to build a link to improve data transmission efficiency.

Satellite mission planning can usually be regarded as a constraint optimization problem rather than a constraint satisfaction problem [10]. Several satellite scheduling schemes are defined under different satellite types and application requirements: LEO satellite scheduling [11, 12], satellite distance scheduling [13, 14], satellite downlink scheduling [15], satellite broadcasting scheduling [16], data downloading[17]. All satellite scheduling variables are NP-hard to solve, so heuristics and meta-heuristics can be used to solve these [18]. In the literature [19], the various priorities of different tasks are considered, and the literature [20] proposes a mixed integer linear programming model for multi-satellite scheduling. Satellite mission planning belongs to application-level planning. It focuses on how to maximize the communication service demand between the satellite and the ground station during the corresponding visible window. However, the satellite-ground link planning belongs to the link layer, each satellite has no specific task.

Because in the case of a single ground station, the number of visible satellites, the number of satellite-ground links and their bandwidth are all limited. It may cause the data from many satellites to converge to a single ground station, resulting in congestion of satellite-ground link data transmission, and even completely unable to meet the data landing requirements of the entire network. In order to further improve the satellite-ground data transmission efficiency of the LEO satellite navigation augmentation network, it is necessary to build multiple ground stations on the ground section of the network. Therefore, it is necessary to conduct research on the satellite-ground link planning problem for LEO satellite navigation augmentation network in the case of multiple ground stations.

First, we describes and mathematically model the problem. Then we designs a satellite-ground link planning method based on the need to quickly solve the approximate optimal solution of the above model, and theoretically proves the performance of the solution result. Finally, we conduct simulation verification and summarize the full text.

2 Problem Modeling

In the case of multiple ground stations, the visible relationship between satellites and ground stations in the network is shown in Fig. 1.

Fig. 1.
figure 1

The satellite-ground visible relationship

Full size image

In order to further clarify the boundary of the problem in this article, we make the following assumptions: ①The same satellite cannot build links with multiple ground stations at the same time. ②The satellite handover time is temporarily ignored in this study, and it is considered that handover can be seamlessly connected, that is, handover does not require time. ③If there is a feasible link planning scheme, it must be satisfied that at any time in the planning period, the number of satellites covering the ground station is greater than the number of satellites to be planned.

When there is only one ground station in the network, only how ground station choose the satellite within their visual range needs to be considered. This article studies the situation where there are multiple ground stations in the network. It also includes how satellites choose the ground station within their coverage area.

2.1 Variable Definitions

First, we should define the variables used in the mathematical model:

  1. 1.

    The collection of all satellites in the network is expressed as \(\Psi =\{{\mathrm{S}}_{1},{\mathrm{S}}_{2},\dots ,{\mathrm{S}}_{\mathrm{M}}\}\), the collection of all ground stations in the network is expressed as \(\mathrm{K}=\{{\mathrm{GS}}_{1},{\mathrm{GS}}_{2},\dots ,{\mathrm{GS}}_{\mathrm{N}}\}\).

  2. 2.

    The visual relationship between the ground station and the satellite is described by a series of visual time slices. For example, a visible time slice of the satellite \({\mathrm{S}}_{\mathrm{i}}\) and the ground station \({GS}_{j}\) is represented by the quadruple \( { v}_{i,j}^{k}=<i,j,{t}_{s},{t}_{e}>\). \(k\) is the time slice number, \(i\) is the satellite number (\(\forall {S}_{i}\in \Psi \)), \(j\) is the ground station number \((\forall {GS}_{j}\in \mathcal{K})\), \({t}_{s}\) is the start time of the visible time slice, \({\mathrm{t}}_{\mathrm{e}}\) is the end time of the visible time slice, \( {\mathrm{t}}_{\mathrm{s}}<{\mathrm{t}}_{\mathrm{e}}\).

  3. 3.

    The satellites that establish satellite-ground links with the ground station \({GS}_{j}\) are called landing satellites, and their number is recorded as \({\mathrm{m}}_{\mathrm{j}}\). Satellites that have inter-satellite links with landing satellites in the network are called secondary landing satellites, and their number is recorded as \({\mathrm{n}}_{\mathrm{j}}\). Assuming that the link planning period is \(T\), the number of landing satellites \({m}_{j}\) varies according to the number of real − time visible satellites during the planning period, and \({\mathrm{n}}_{\mathrm{j}}\) will also change accordingly.

  4. 4.

    The satellite-ground link planning scheme is composed of time slices for establishing links between all ground stations and different satellites. A time slice can also be represented by the quadruple \({\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{k}}=<\mathrm{i},\mathrm{j},{\mathrm{p}}_{\mathrm{s}},{\mathrm{p}}_{\mathrm{e}}>\). \(k\) is the time slice number, \(i\) is the satellite number, \(j\) is the ground station number, \({p}_{s}\) is the start time of the time slice, \({p}_{e}\) is the end time of the time slice, \( {p}_{s}<{p}_{e}\). The entire link planning scheme of the ground station \({GS}_{j}\) can be expressed as \(G(j)=\{{g}_{i,j}^{k}|k=\mathrm{1,2},3\cdots \}\). The elements in the link planning scheme are sorted in ascending order according to the end time of the link establishment time slice, namely: \({\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{k}}.{\mathrm{p}}_{\mathrm{e}}\le {\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{k}+1}.{\mathrm{p}}_{\mathrm{e}}\). The entire link planning scheme of all ground stations can be expressed as \(G={\bigcup }_{j}G(j)\).

2.2 Constraint Enumeration

How ground stations choose the satellite within their visual range should satisfy the following constraints:

  1. 1.

    All feasible link establishment time slices must be within the visible time slice range of the ground station and the corresponding satellite. If \({\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{k}}\) is feasible, the condition that should be satisfied is the existence of \({\mathrm{v}}_{\mathrm{i},\mathrm{j}}^{\mathrm{a}}\), which satisfies:

    $${g}_{i,j}^{k}.{p}_{s}\ge {v}_{i,j}^{a}.{t}_{s}, {g}_{i,j}^{k}.{p}_{e}\le {v}_{i,j}^{a}.{t}_{e} $$
    (1)

    denoted as \({g}_{i,j}^{k}\subset {v}_{i,j}^{a}\).

  2. 2.

    In order to eliminate invalid visible satellites with short remaining visible time, assuming that the shortest chain-building time threshold is \(\epsilon \), the feasible link establishment time slice is required to satisfy:

    $${\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{k}}.{\mathrm{p}}_{\mathrm{e}}-{\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{k}}.{\mathrm{p}}_{\mathrm{s}}\ge\upepsilon (\forall {\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{k}}\in \mathrm{G})$$
    (2)
  3. 3.

    The transmission of satellite-ground data can only be completed through landing satellites, secondary landing satellites, and the inter-satellite links between them. Therefore, in order to avoid serious congestion in satellite-ground data transmission, the number of landing satellites and secondary landing satellites should meet the minimum threshold requirements:

    $$\sum\nolimits_{1}^{\mathrm{N}}{\mathrm{m}}_{\mathrm{j}}\ge {\mathrm{R}}_{\mathrm{th}}, \sum\nolimits_{1}^{\mathrm{N}}{\mathrm{n}}_{\mathrm{j}}\ge {\mathrm{SR}}_{\mathrm{th}}$$
    (3)

    How satellites choose the ground station within their coverage area should satisfy the following constraints: The same satellite cannot build links with multiple ground stations at the same time. There are no two link establishment time slices \(\forall {\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{k}},{\mathrm{g}}_{\mathrm{i},\mathrm{n}}^{\mathrm{k}}\in \mathrm{G}\), ground station number \(j=n\).

2.3 Optimization Goal

First, we should consider minimizing the total number of satellite-ground link handovers: \(\mathrm{min}(\left|\mathrm{G}\right|)\). Second, since the bandwidth of each satellite-ground link is the same, the larger the number of antennas used by a ground station, the greater the amount of data falling from the satellite to it, and the more serious the data congestion of the ground station. Therefore, the number of antennas used by each ground station should be as uniform as possible to ensure the balanced transmission of satellite-ground data. The uniformity of the antennas used by each ground station is expressed as follows: \(\mathrm{h}=\sqrt{\frac{\sum_{1}^{\mathrm{N}}{({\mathrm{m}}_{\mathrm{j}}-\overline{\mathrm{m} })}^{2}}{\mathrm{N}}}\). \(\mathrm{N}\) is the total number of ground stations in the entire network, and \(\overline{\mathrm{m} }\) is the arithmetic mean of antennas used by ground stations. The smaller \(h\) means the more uniform the antennas used by ground stations, which is recorded as \(\mathrm{min}(\mathrm{h})\).

In summary, the model is transformed into a multi-objective programming problem with the two functions \(\mathrm{min}(\left|\mathrm{G}\right|)\) and \(\mathrm{min}(\mathrm{h})\) as the optimization objectives under all constraints. For such problems, there are mature algorithms that can be solved, such as priority setting method.

3 Planning Method

Because it takes a lot of time and resources to search for solutions within the constraint domain of the above model. But in practical applications, satellite resources are limited and the satellite-ground link handover schedule needs to be updated quickly. So this article proposes a planning method based on graph theory: multiple ground stations satellite-ground link planning method (MSGLP). It can quickly solve the approximate optimal solution of the above model, which is generally divided into the following steps. First, consider how ground stations choose the satellite within their visual range. Second, consider how satellites choose the ground station within their coverage area.

3.1 Ground Stations Choose Satellite

According to the visibility relationship between the satellite and the ground station, we construct a special capacity network directed graph. When building the graph, it is necessary to remove the invalid candidate satellites whose remaining visible time is less than the shortest chain-building time threshold \(\upepsilon \). The overall example of constructing directed graph is shown in Fig. 2, which is divided into the following four steps:

Fig. 2.
figure 2

The overall example of constructing directed graph

Full size image
  1. 1.

    Construct node: Construct each visible time slice of all ground stations and satellites as a node, and assign node numbers to these nodes in turn. Since the visible time slice contains the satellite number and ground station number information, it needs to be assisted by this information later to transform the result into a link planning scheme. The start node and the end node do not represent a specific visual time slice, but serve as the source and destination nodes of the entire directed graph.

  2. 2.

    Edge addition: For a certain ground station, there is a visible time slice \(a\). If the visible time slice \(b\) satisfies: \(\mathrm{a}.{\mathrm{t}}_{\mathrm{s}}<\mathrm{b}.{\mathrm{t}}_{\mathrm{s}}<\mathrm{a}.{\mathrm{t}}_{\mathrm{e}}\), then an edge is connected between these two nodes, as shown in the Fig. 3.

Fig. 3.
figure 3

Example of connected edges in directed graph

Full size image
  1. 3.

    Set edge cost and capacity: Assuming that the cost of an edge in the capacity network represents the number of link handovers, the traffic on each edge is non-negative and the maximum can only reach the capacity limit, so the capacity of each edge is set to 1, and the cost is set to 1. Each ground station \({\mathrm{GS}}_{\mathrm{j}}\) has \({\mathrm{m}}_{\mathrm{j}}\) connected edges with the start node and the end node, the cost of each edge is set to 0, and the capacity is set to 1.

  2. 4.

    Node split: In order to avoid finding the same point when solving the problem with graph theory, the capacity of each node must be limited to 1. The construction of the current network graph does not consider the capacity of the nodes, so each node \(v\) in the graph except the start node and the end node is split into two nodes \({\mathrm{v}}_{1}\) and \({\mathrm{v}}_{2}\). The two points are connected by an edge, the capacity of the edge is 1, and the cost is 0. The edge that flows into \(v\) in the original graph is connected to \({\mathrm{v}}_{1}\), and the edge that flows out of \(v\) is connected to \({\mathrm{v}}_{2}\).

Therefore, how ground stations choose the satellite within their visual range is transformed into the problem of finding the minimum cost path with a flow value of \({\mathrm{R}}_{\mathrm{th}}\) in the constructed capacity network. There are mature algorithms to solve this problem. Then, according to the satellite number and ground station number information, and the start and end time information contained in the visible time slice, the path calculated by the algorithm can be transformed to obtain the pre-built chain planning scheme \({\mathrm{G}}^{*}\) with the least total number of link handovers. In \({\mathrm{G}}^{*}\), there will be a situation where the same satellite and multiple ground stations will build links at the same time. The number of active antennas for each ground station is not balanced, so you need to proceed to the next step.

3.2 Satellites Choose Ground Station

\({G}^{*}\) contains the pre-built chain time slice information of each ground station, the start time and end time of each time slice are called handover time. Sort all the handover time from small to large to get the handover event time list \({\{\mathrm{t}}_{1},{\mathrm{t}}_{2},\dots ,{\mathrm{t}}_{\mathrm{L}}\}\). At each handover event time \({\mathrm{t}}_{\mathrm{i}}\), there may be a handover between the old and new satellites. So we establish the visibility bipartite graph \({\mathrm{G}}_{\mathrm{ti}}\) of the ground station and the satellite at each handover time.

\({G}_{ti}\left(X,Y,E\right)\) is an undirected graph, \(E\) represents the edge set, the vertex set is divided into two disjoint subsets \(X\) and \(Y\). There are no edges within the subsets, and edges are connected between the subsets. The two vertex subsets \(X\) and \(Y\) respectively correspond to the set \(\Psi \) of all satellites and the set \(\mathrm{K}\) of all ground stations. If a ground station and a satellite are visible, the two points will be connected. An example is shown in Fig. 4.

Fig. 4.
figure 4

Example of bipartite graph \({G}_{ti}\) and extension method

Full size image

Since \(\mathrm{N}\ll \mathrm{MN}\ll \mathrm{M}\), the ground station node set needs to be expanded according to the method shown in Fig. 4 to obtain set \(Y\), so that the number of nodes in set \(X\) and set \(Y\) is equal. When a satellite and a ground station are visible, there is no need to draw the connecting line between the two repeatedly when expanding, just draw one at random.

If there is a subgraph in the bipartite graph \({G}_{ti}\), denoted as \(M\), when any two edges in the edge set of \(M\) have no common endpoints, then \(M\) is said to be a match. If the vertices in a match cover all the vertices of the entire graph, then it is said to be a perfect match of the graph. The perfect match \({\mathrm{M}}_{\mathrm{ti}}\) of the bipartite graph \({G}_{ti}\) can be searched using the Hungarian algorithm. If \(x\) is a satellite node in the set \(X\), \({M}_{ti}(x)\) is the ground station node matched by \(x\) at this handover moment. The obtained matching \({\mathrm{M}}_{\mathrm{ti}}\) satisfies that a satellite only establishes a link with one ground station at the handover time, and the number of landing satellites allocated to each ground station is basically uniform. Combining all matching \({\mathrm{M}}_{\mathrm{ti}}\) can be transformed into the final satellite-ground link planning scheme. Check whether the total number of secondary landing satellites in plan \(G\) meets the threshold requirement, and continue to adjust the plan if it does not meet the requirement.

3.3 Performance Analysis

Suppose the exact solution of the model solved by the search method is \(\overline{\mathrm{G}}\), and the model optimization objective function is \({f}_{1},{f}_{2}\). Knowing the solution result \(G\) of the MSGLP method, we will perform theoretical analysis on the data accuracy and the time complexity.

Theorem 1.

Suppose a scheme \(\mathrm{G}\) with the least number of handovers, if it exists:\({\exists \mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{a}}\in \mathrm{G},{\exists \mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{b}}\in \mathrm{G},\exists {\mathrm{v}}_{\mathrm{c},\mathrm{j}}^{\mathrm{k}}\in \mathrm{V}, {\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{a}}\subset {\mathrm{v}}_{\mathrm{c},\mathrm{j}}^{\mathrm{k}},{\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{a}}.{\mathrm{p}}_{\mathrm{e}}={\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{b}}.{\mathrm{p}}_{\mathrm{s}}.\) If you replace the two time slices \({g}_{i,j}^{a},{g}_{i,j}^{b}\) in \(\mathrm{GG}\) with: \({g}_{i,j}^{\overline{a}}=<{g}_{i,j}^{a}.i,{g}_{i,j}^{a}.j,{g}_{i,j}^{a}.{p}_{s},{v}_{c,j}^{k}.{t}_{e}>,{g}_{i,j}^{\overline{b}}=<{g}_{i,j}^{b}.i,{g}_{i,j}^{b}.j,{v}_{c,j}^{k}.{t}_{e},{g}_{i,j}^{b}.{p}_{e}>.\) \(\mathrm{G}\) is still the planning scheme with the least number of handovers.

Proof.

Obviously there is \({\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{a}}.{\mathrm{p}}_{\mathrm{e}}<{\mathrm{v}}_{\mathrm{c},\mathrm{j}}^{\mathrm{k}}.{\mathrm{t}}_{\mathrm{e}}<{\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{b}}.{\mathrm{p}}_{\mathrm{e}}{\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{a}}.{\mathrm{p}}_{\mathrm{e}}<{\mathrm{v}}_{\mathrm{c},\mathrm{j}}^{\mathrm{k}}.{\mathrm{t}}_{\mathrm{e}}<{\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{b}}.{\mathrm{p}}_{\mathrm{e}}\), otherwise if \( {\mathrm{v}}_{\mathrm{c},\mathrm{j}}^{\mathrm{k}}.{\mathrm{t}}_{\mathrm{e}}>{\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{b}}.{\mathrm{p}}_{\mathrm{e}}{\mathrm{v}}_{\mathrm{c},\mathrm{j}}^{\mathrm{k}}.{\mathrm{t}}_{\mathrm{e}}>{\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{b}}.{\mathrm{p}}_{\mathrm{e}}\), then\({\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{b}}\subset {\mathrm{v}}_{\mathrm{c},\mathrm{j}}^{\mathrm{k}}{\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{b}}\subset {\mathrm{v}}_{\mathrm{c},\mathrm{j}}^{\mathrm{k}}\). At this time, \({g}_{i,j}^{a},{g}_{i,j}^{b}\) can be combined into one time slice. Therefore, the number of handovers can be reduced by one, which contradicts that scheme \(G\) has the least number of handovers. And \({\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{b}}\in {\mathrm{Gg}}_{\mathrm{i},\mathrm{j}}^{\mathrm{b}}\in \mathrm{G}\), so the time slice \(<{\mathrm{v}}_{\mathrm{c},\mathrm{j}}^{\mathrm{k}}.{\mathrm{t}}_{\mathrm{e}},{\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\mathrm{b}}.{\mathrm{p}}_{\mathrm{e}}>\) must also be within the visible time slice of the ground station. Therefore, \({\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\overline{\mathrm{b}}}\) is the feasible time slice for chain establishment. And \({\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\overline{\mathrm{a}}}\subset {\mathrm{v}}_{\mathrm{c},\mathrm{j}}^{\mathrm{k}}\), so \({\mathrm{g}}_{\mathrm{i},\mathrm{j}}^{\overline{\mathrm{a}}}\) is also a feasible time slice for chain establishment. Obviously, after the replacement, the number of handovers is equal to the original scheme, so it is still the scheme with the least number of handovers.

Theorem 1 shows that the handover time in the link planning scheme selects the end time of the visible time slice, which can reduce the number of switching to the greatest extent. However, the planning scheme with the least total number of handovers does not mean that all handover moments are at the end of the visible time slice. In the process of constructing the capacity network, the rule for adding edges is based on the end time of the visible time slice. Therefore, all feasible flows whose traffic is \({\mathrm{R}}_{\mathrm{th}}\) correspond to a scheme, and the link planning scheme with the least number of handovers must be in it. According to the weight and capacity settings of the edges, the total cost of each feasible flow is equal to the number of handovers, so the minimum cost flow with a flow rate of \({\mathrm{R}}_{\mathrm{th}}\) corresponds to the minimum number of handovers.

Therefore, \({G}^{*}\) satisfies all the constraints on how ground stations choose the satellite within their visual range, and since \(G\) is adjusted from the process of satellites choose ground station on the basis of \({G}^{*}\), \(G\) also satisfies all the constraints on how ground stations choose the satellite within their visual range. At the same time, because \(G\) is a combination of multiple matching \({\mathrm{M}}_{\mathrm{ti}}\), and the graph theory characteristics of each match can ensure that each satellite is connected to only one ground station, so that \(G\) satisfies the constraints on how satellites choose the ground station within their coverage area. In summary, \(G\) and \({\mathrm{G}}^{*}\) both satisfy the same constraints.

The process of satellites choose ground station only adjusts the satellite numbers in some time slices, so it is guaranteed that the number of handovers is unchanged when \({G}^{*}\) is adjusted to \(G\). So \(G\) corresponds to the minimum number of handovers, \({\mathrm{f}}_{1}\left(\mathrm{G}\right)={\mathrm{f}}_{1}\left(\overline{\mathrm{G}}\right)\).

For the exact solution\(\overline{\mathrm{G}}\), since the number of satellites allocated to each ground station is the same, there is \({\mathrm{f}}_{2}\left(\overline{\mathrm{G}}\right)=0\). The MSGLP method ensures that the number of satellites allocated to each ground station is \(\frac{\mathrm{M}-\upmu }{\mathrm{N}}\frac{\mathrm{M}-\upmu }{\mathrm{N}}\) or\(\frac{\mathrm{M}-\upmu }{\mathrm{N}}+1\frac{\mathrm{M}-\upmu }{\mathrm{N}}+1\), where \(\upmu \) represents the remainder of \(\frac{\mathrm{M}}{\mathrm{N}}\). The number of satellites (the number of active antennas \({m}_{j}\)) allocated to the ground station \(\left\{{\mathrm{GS}}_{1},{\mathrm{GS}}_{2},\dots ,{\mathrm{GS}}_{\upmu }\right\}\) is\(\frac{\mathrm{M}-\upmu }{\mathrm{N}}+1\), and the number of satellites (the number of active antennas \({\mathrm{m}}_{\mathrm{j}}\)) allocated to the ground station \(\left\{{\mathrm{GS}}_{\upmu +1},{\mathrm{GS}}_{\upmu +2},\dots ,{\mathrm{GS}}_{\mathrm{N}}\right\}\) is \(\frac{\mathrm{M}-\upmu }{\mathrm{N}}.\) Therefore, the uniformity of the antennas used by each ground station is: \(\mathrm{h}=\sqrt{\frac{\sum_{1}^{\mathrm{N}}{({\mathrm{m}}_{\mathrm{j}}-\overline{\mathrm{m} })}^{2}}{\mathrm{N}}}=\sqrt{\frac{\upmu }{\mathrm{N}}}\), and \(\upmu \ll \mathrm{N}\), so \({\mathrm{f}}_{2}\left(\mathrm{G}\right)=\sqrt{\frac{\upmu }{\mathrm{N}}}\approx 0\).

The exact solution \(\overline{G}\) and the approximate solution \(G\) solved by the MSGLP method only have a small error on \({\mathrm{f}}_{2}\), and there is no error on \({\mathrm{f}}_{1}\). We can conclude that the two are very close in data accuracy.

If the Bellman-Ford algorithm is used to find the smallest cost path with a flow value of \({\mathrm{R}}_{\mathrm{th}}\) in the constructed capacity network, the time complexity is O(|V||E|). If the Hungarian algorithm is used to search for the perfect match \({\mathrm{M}}_{\mathrm{ti}}\) of the graph \({\mathrm{G}}_{\mathrm{ti}}\), and the graph \({\mathrm{G}}_{\mathrm{ti}}\) is stored in the form of an adjacency list, and its time complexity is also O(|V||E|).

In summary, the exact solution \(\overline{\mathrm{G}}\) and the approximate solution \(\mathrm{G}\) have very close data accuracy, and the MSGLP method is more efficient than the search solution method. Therefore, it is suitable for the fast and effective demand of satellites in practical applications.

4 Simulation

The simulation tools use OPNET, MATLAB, and STK. The experiment in this paper is based on an actual LEO navigation augmentation satellite network system to be constructed.

The overall network parameters are as follows: ① The satellite constellation is a Walker 120/12/1 configuration with an orbital altitude of 970 km and an orbital inclination of 55°. ② A total of 8 ground stations are built in the network, all of which are selected in China, and the minimum elevation angle of each station's antenna is 10°. ③ Each satellite has four fixed inter-satellite links, two of which are inter-satellite links in the same orbit, and two are inter-satellite links in different orbits. ④ The satellite-ground link bandwidth is 5 Mbps, the inter-satellite link bandwidth is 1 Mbps, the communication link is a bidirectional link, and the size of each data packet is 512 Bytes. ⑤ The downlink data generation rate of each satellite is 1kbps, and the uplink data generation rate of the ground station for each satellite is 1kbps.

In the above simulation network, the following methods are used for satellite-ground link planning: the MSGLP method, and the SMST method, SMRU method, and SC-SMRU method. The latter three methods are proposed based on the single ground station, so they are used separately for each ground station in the network.

Use MSGLP, SMST, SMRU, SC-SMRU to obtain the satellite-ground link planning scheme, and the comparison of the total number of link handovers is shown in Fig. 5. It can be seen that the total number of link handovers of MSGLP and SMST are almost the same, the former is slightly higher than the latter, and both are much lower than the other two methods. This result not only shows that the MSGLP method optimizes the total number of link handovers index, but also verifies the optimality of the SMST method in optimizing the number of link handovers index. However, the SMST method does not consider the simultaneous establishment of links between the same satellite and multiple ground stations, and the number of antennas activated on ground stations is not balanced.

Fig. 5.
figure 5

Comparison of the total number of link handovers obtained by each method

Full size image

Use MSGLP, SMST, SMRU, SC-SMRU to obtain the satellite-ground link planning scheme, the uniformity \(h\) of the antennas used by each ground station is shown in Fig. 6. It can be seen that the parameter \(h\) value of the MSGLP method is the smallest, and it is much lower than the other three methods. This is because the MSGLP method uses the method of uniformly expanding the set of ground station nodes when establishing the visibility bipartite graph at each handover time. So that in the obtained matching \({M}_{ti}\), the satellites can be approximately evenly distributed to the ground stations.

In addition, we uses OPNET to record the average delay of all data packets after they operate in the LEO satellite navigation augmentation network. The results are shown in Fig. 7. It can be seen that the average delay of the MSGLP method is always lower than that of the other three methods. This is because the MSGLP method not only tries to avoid the delay jitter caused by handover, but also avoids data congestion caused by uneven distribution of traffic among ground stations, thereby reducing the average delay of data packets.

Fig. 6.
figure 6

Comparison of \(h\) obtained by each method

Full size image
Fig. 7.
figure 7

Comparison of average packet delay obtained by each method

Full size image

In summary, compared with the other three methods, the MSGLP method considers multiple ground stations as a whole, and considers satellite-ground link planning problem on its basis. The simulation results verify the effectiveness of the method actually applied to the LEO satellite navigation augmentation network in the case of multiple ground stations.

5 Conclusion

We mathematically model the satellite-ground link planning problem for LEO satellite navigation augmentation network in the case of multiple ground stations. Then proposes a planning method based on graph theory (MSGLP), it can quickly solve the approximate optimal solution of the above model. According to the visibility relationship between the satellite and the ground station, we first construct a special capacity network directed graph. In this way, how ground stations choose the satellite within their visual range is transformed into the problem of finding the minimum cost path with a flow value of \({\mathrm{R}}_{\mathrm{th}}\) in the constructed graph. The pre-built chain planning scheme \({\mathrm{G}}^{*}\) with the least total number of satellite handovers can be obtained through simple conversion. \({G}^{*}\) contains the pre-built chain time slice information of each ground station, the start time and end time of each time slice are called handover time. Establish a bipartite graph of ground station and satellite visibility at each handover time, find the perfect match of the graph. This match satisfies that a satellite is only building a link with one ground station at this moment, and the number of active antennas in each ground station is basically uniform. Combine all the obtained matches and transform them into the final satellite-ground link planning scheme \(G\).