Topology-adapting routing strategy for global navigation satellite system

Abstract

In order to implement global precision navigation, the global navigation satellite system must rely on information exchange with the ground station to achieve system time synchronization and inter-satellite ranging. For the limitations of ground stations located in territory and actual communication requirements, it is essential to study the routing problem of navigation satellite network, which indicates that traditional routing technology cannot meet the requirements of global navigation satellite system. Aiming to control the dynamic topology of global navigation satellite system and satisfy communication constraints, we investigate the topology-adapting strategy for inter-satellite link constructing and routing. First, we propose the design method of the inter-satellite link scheme based on fixed topology to satisfy the requirements for delay and relay hops. Then, we build the constraint programming model of the global navigation satellite system routing problem. In further, we design the routing calculation framework and optimization strategies to enhance the routing performance of the transmission scheme. Through the simulation and numerical results, we demonstrate that the fixed topology scheme can meet the navigation requirements, and the proposed strategy can effectively improve the routing performance.

Introduction

Global navigation satellite system (GNSS) has the ability to provide full-time global navigation and high-precision positioning, not only meeting the requirements of mobile vehicle navigation but also serving the fields of geodesy, precision timing, meteorological observation, and security defense. ¹ In order to achieve global precision navigation, GNSS must have functions of precise orbit determination, time synchronization, and constellation autonomous navigation. According to the current design and construction, space constellation depends on information exchange with the ground station to achieve system time synchronization and inter-satellite ranging. It needs ground station processing to complete navigation tasks, because of the limited onboard resource, while the efficient link is required between ground station and navigation satellite. However, on one hand, time synchronization and inter-satellite ranging require the quick communication between satellites and stations, which put forward higher requirements for delay and relay hops; on the other hand, the ground stations are located in territory which brings strict constraints for constructing information transmission path in space constellation.

The inter-satellite link (ISL) is the core technology to complete navigation information transmission for GNSS, which can not only significantly improve the network geometric layout and the accuracy of orbit determination and synchronization but also support autonomous navigation and maintain system reference time. The ISL can provide support to construct the global network of navigation constellation, which brings multiple choices for routing decision making; moreover, the constraints of path backup and relay alignment must be considered, leading to path-specifying problem. Navigation satellite network adopts ultra-long wireless communication, producing long transmission delay. With the relative motion of satellites, the link distance and connection relationship keep changing, which causes dynamic changes for transmission delay. Long delay and dynamic changes directly affect data transmission, which is even interrupted when it fails to meet the constraints of establishing ISLs. GNSS based on ISL has the capacity of onboard processing and link switching, which achieves efficient information transmission between ground stations and navigation satellites. But the topology of space network becomes more complex and variable, and communication links switch frequently. Therefore, the routing calculation is becoming an urgent problem for global navigation information transmission.

For the routing complexity and serious delay, we study the topology-adapting routing strategy for the GNSS. The topology-adapting strategy consists of the design method of fixed topology ISL scheme and routing strategy, which achieve the dynamic topology control and satisfy communication constraints. First, we propose the mode based on fixed topology, which designs the connection-oriented ISL scheme according to the system composition, resource constraints, and assignment requirements, so that navigation information is transmitted via the routing in topology-adapted ISL scheme. In this article, the topology-adapted ISL scheme controls the network dynamic by designing the ISL scheme based on fixed topology. This can effectively simplify the network connection and reduce the selection scale of information transmission path. Besides, it effectively solves the delay problem of navigation information transmission, not only improving geometric dilution precision through the rational construction of ISL but also ensuring maximum connectivity of space constellation via relay forwarding of the shortest path.

The current satellite network routing discrete the dynamic topology of satellite network using topology control strategy which is mainly based on the periodicity and predictability of network operating. Then, optimization methods of ground network can be applied to calculate the routing scheme in each time slice, in which network topology can be considered to be stable. Topology control strategy includes virtual topology,^2,3 virtual nodes,^4,5 and coverage-domain partition, ⁶ which is subjected to the actual network scope and limited condition. It will produce more topology change and larger computational load. In addition, the actual communication tasks put forward higher requirements on delay and relay hops. Thus, for the actual requirement and the limitation of traditional method, the routing strategy based on fixed topology mode is designed for navigation information transmission.

The research is constructed for the limitations of traditional routing technology and the actual communication requirements. The main contribution of this article is to study the topology-adapting routing strategy for the GNSS. In particular, we propose a design method of the ISL scheme based on fixed topology. Then, based on the designed ISL scheme, we formulate a multi-objective optimization and multi-constraint routing model. In further, we explore the calculation framework and optimization strategy. Through the simulation and numerical results, we demonstrate that the fixed topology scheme can meet the navigation requirements, and the proposed strategy can effectively improve the routing performance. The rest of this article is organized as follows: In section “Related work,” we briefly present some related works, and we introduce a design method for the ISL scheme in section “Design method of ISL scheme.” In section “Routing problem model,” we formulate the optimal routing model adapting to fixed topology scheme. In section “Optimization formulation,” we present the optimization formulation. In section “Simulation and numerical results,” we introduce the simulation and numerical results. Finally, we conclude our main work in section “Conclusion.”

Related work

GNSS has great significance of political, economic, and military, so many countries are striving to develop global or regional satellite navigation system. The current GNSS includes global positioning system (GPS), GLONASS, Galileo, and Beidou satellite navigation system, and their space constellation mainly consists of geosynchronous equatorial orbit (GEO), inclined geosynchronous orbit (IGSO), and medium earth orbit (MEO) satellites. Compared with low earth orbit (LEO) satellite system, the GNSS constellation has greater coverage and stable operating speed, which effectively meet the navigation requirements of coverage and the link establishment.

The transmission mechanism of navigation information is based on the topology constructing and routing of satellite communication network. The ISL technology was originally applied in satellite communication system, with microwave or laser link between the satellites. For the LEO satellite network developed by European and American countries, Iridium and Teledesic system have achieved ISL communication. Most countries cannot deploy ground stations in the global scope for the political and economic facts. In order to decrease the dependence of ground station, the GNSS tends to develop ISL and onboard processing to achieve information transmission, inter-satellite ranging, and autonomy navigation.

The existing research on the ISL focuses on constellation construction and configuration, antenna design, and operating mode. In fact, the key problem of ISL lies in the inter-satellite networking, so considerable research has been conducted to design inter-satellite topology. Chang et al. ⁷ simplified the dynamics of network topology according to the finite state automation (FSA) and proposed a link assignment and routing algorithm based on link load balancing. Harathi et al. ⁸ described some of the algorithm variations to meet different objective functions and proposed an optimal link assignment algorithm for self-reconfiguring satellite networks. Noakes et al. ⁹ presented an adaptive link assignment algorithm for distributed optimization of dynamical changing network to emphasize robustness in stressed environments. Cain et al. ¹⁰ examined the link assignment problem for a mid-course, space-based spatial data infrastructure (SDI) architecture and proposed a link assignment algorithm designed to recover from predictable link outages. Ito et al. ¹¹ discussed the time slot scheduling problem for a satellite switched/time-division multiple access system. Then, they abstracted link assignment problem into the decomposition of optimization matrix and presented a greedy algorithm based on rearrangeable multistage matrix. Wang et al. ¹² proposed an ISL topological design method based on three-dimensional matrix for GNSS constellation and explored a link assignment and optimal routing problem considering antenna beam coverage and relative velocity.

For the routing algorithm, there are more works on the LEO satellite network than other orbital satellites such as MEO constellation. The routing in LEO satellite communication systems can be classified into different categories, ¹³ and several solution and implementation strategies have been proposed utilizing information on expected traffic characteristics and handover possibilities. These routing algorithms are described in the following. There are some works involving load balancing routing algorithm in previous studies.^14–16 The work in Karapantazis et al. ¹⁴ proposed a location-assisted on-demand routing (LAOR) protocol which is a typical centralized algorithm for LEO satellite systems. This protocol can be viewed as a variant of the ad hoc on-demand distance vector (AODV) routing protocol, tailored to the requirements imposed by the characteristics of LEO satellite system topology. The work in Taleb et al. ¹⁵ proposed a distributed load balancing routing algorithm by allocating the sending tasks of congested satellites to their neighbors. This method reduces the packet dropping probability but existing hidden danger of signaling congestion due to feedback packets. The work in Rao et al. ¹⁶ proposed a multipath quality of service (QoS) routing (MPQR) scheme for polar-orbit LEO satellite networks, which was a QoS aware algorithms. The traffic class-dependent routing algorithm attempts to guarantee QoS for different routing classes and may heavily overload the chosen path with unbalanced assignments, which affect the traffic distribution over the entire LEO constellation. Besides the centralized algorithm, there are other works which consider the handover optimizing and multicast routing problem. The work in Sarddar et al. ¹⁷ proposed billboard manager–based handover (BMBHO) technique to overcome the higher blocking probability and force call termination probability. The work in Yang et al. ¹⁸ proposed a bandwidth-efficient multicast routing mechanism using rectilinear Steiner trees for IP-based LEO satellite networks. This algorithm must have the information of all the multicast users before constructing the multicast tree, which is constructed on the virtual static topology and makes their signaling and memory overhead very high.

Design method of ISL scheme

GNSS is composed of region enhanced network containing GEO and IGSO constellation and global navigation network of MEO constellation. Topology of GEO and IGSO constellation is relatively simple with continuous link to ground stations, while MEO constellation has relative movement with the earth and cannot access domestic stations continually. Thus, MEO network protocol and routing are more complex and important for GNSS.^19,20 In this article, our research focuses on the construction of MEO constellation. For MEO constellation, each navigation satellite establishes intra-plane ISL $(\mathrm{IS}{L}_{\mathrm{tra}})$ with the corresponding satellite in the same plane and inter-plane ISL $(\mathrm{IS}{L}_{\mathrm{ter}})$ with satellites in adjacent planes. Navigation information is transmitted to ground stations with ISL and satellite-ground link (SGL) of MEO constellation.

Navigation information transmission based on ISL adopts disconnect-oriented operating mode. The space constellation is converted to approximate grid network through topology control strategy based on the periodicity and predictability of dynamical changing network topology. Then, routing algorithms and strategies are applied to calculate and choose the best transmission path. In order to solve complex route, long delay, and method limitations of navigation information transmission, we design the topology-adapting operating mode, which is based on fixed ISL scheme. The routing scheme is obtained by the combination and optimization of fixed links, when choosing information transmission paths. Therefore, the core of fixed topology operating mode is to design ISL scheme, so we focus on constructing process of the ISL scheme in the following.

In order to construct the ISL scheme for each constellation, it must first define constellation characteristics, assignment requirements, and resource constraints and then determine the link type, number of links, and topology to complete the ISL scheme. The detailed constructing process includes (1) according to the composition and structure of the system, determine the allowable link type and maximum number of each satellite through the constellation characteristic analysis. Then, the performance requirements are analyzed according to the assignment tasks and resource constraints; (2) select the link type in the allowable types and determine the number of links in the allowable range according to the assignment requirements and resource constraints; (3) design the topology of $\mathrm{IS}{L}_{\mathrm{tra}}$ , $\mathrm{IS}{L}_{\mathrm{ter}}$ , and inter-layer link, respectively based on the system components.

For the $\mathrm{IS}{L}_{\mathrm{tra}}$ , inter-satellite position is relatively fixed, so each satellite establishes the $\mathrm{IS}{L}_{\mathrm{tra}}$ with neighbors in the same orbit based on the geometric relationship. The specific rules can be uniformly described as each satellite establishes the required number of links to satellites with $i$ intervals in the same plane ( $i=0,1,\dots ,n$ , determined by the number of satellites), as shown in Figure 1.

Figure 1.

Constructing rule of $\mathrm{IS}{L}_{\mathrm{tra}}$ topology.

For the $\mathrm{IS}{L}_{\mathrm{ter}}$ , navigation satellites establish $\mathrm{IS}{L}_{\mathrm{ter}}$ between adjacent planes. The neighboring relationship of inter-plane satellites is evolving, which establishes the desired type and number of $\mathrm{IS}{L}_{\mathrm{ter}}$ based on the accessing and geometric parameters. The specific construction rule can be uniformly described as each satellite establishes the required number of $\mathrm{IS}{L}_{\mathrm{ter}}$ with satellites in the adjacent planes, as shown in Figure 2.

Figure 2.

Constructing rule of $\mathrm{IS}{L}_{\mathrm{ter}}$ topology.

For the inter-layer link, GNSS establishes inter-layer link between GEO, MEO, and IGSO constellation. In order to optimize the system structure and meet the requirements, the high-layer satellite establishes an inter-layer link to a plane of the next layer. The low-layer satellites in the same orbit only establish an inter-layer link with a high-layer satellite. Besides, no cross-layer link is established, and the high-layer satellites establish control links with the low-layer satellites, maintaining the less inter-layer link.

Routing problem model

Constraint programming model

The GNSS routing problem based on fixed topology is to find the link scheme between each satellite and ground stations in the system period. The navigation satellite can access ground stations at intervals in the system period. When the satellite can access ground stations directly, the communication is completed via SGL; when the satellite cannot access the ground station, the communication is completed via ISLs. Every link selection interval can be defined as a decision window, in which selection and combination are carried on between SGL and ISL. During the routing decision process, the link selection and combination must satisfy the constraints and obtain the optimal routing scheme according to certain rule and strategy. The problem constraint, optimization objective, and multi-objective decision method are described in detail.

According to the network model and link quality formulas, the mathematical programming model is built for the multi-constraint and multi-objective routing problem:

• Objective function

$$F\left(p\right)=min(\mathrm{MUL}\_\mathrm{OPT}(\mathrm{CTD},\mathrm{SF},\mathrm{LLBR}))$$

(1)

• Restrictions

$$M_{\mathrm{BD}}\le \mathrm{BD}\left(p\right)$$

(2)

$$\mathrm{PLR}\left(p\right)\le M_{\mathrm{PLR}}$$

(3)

$$\mathrm{STC}\left(p\right)\le M_{\mathrm{STC}}$$

(4)

The optimal routing scheme not only needs to meet the constraints of bandwidth, packet loss rate (PLR), and scheme transmission cost (STC) but also obtains the best comprehensive evaluation of optimization objectives. The GNSS routing is a multi-constraint and multi-objective combinatory optimization problem. A set of alternatives are combined by multiple link selections from every decision, and the optimal scheme is selected with the application of multi-objective optimization method. Maintaining the diversity of alternatives increases the probability of obtaining the optimal scheme. According to the problem model, the scheme is evaluated by communication delay (CD), switching frequency (SF), and link loading balance rate (LLBR), but each metric can indicate single particular performance. Thus, the comprehensive evaluation method is applied to obtain the optimal scheme.

We study the methods of multiple attribute decision making based on the optimization objectives. For the relationship between the individual objectives of the routing scheme, the ELECTRE is chosen to achieve the comprehensive evaluation for the routing scheme based on high-level relationship. Considering the features of the optimization objective and routing scheme, a multi-objective decision-making method is designed for the routing scheme based on traditional method and integrated application of fuzzy environment correction model and net advantage value. ²¹ First, calculate the evaluation of the options and obtain decision matrix and index weight; then build harmony and coefficient matrix and corrected disharmony coefficient matrix by comparing the indicators; and, finally, calculate the total value of weighted net advantages of alternatives and obtain optimal the routing scheme by sorting.

Decision variable

The routing scheme of the satellites and ground stations in the system period is the decision-making process of selection and combination of SGLs and ISLs within the decision window. The system period can be divided into a series of decision-making windows according to the access analysis of the ground station. In the decision window, communication task is completed via SGL at visible intervals; communication task is completed via the selection and combination of ISLs at invisible intervals.

The decision variables, formulas of constraints, and optimizing objectives are defined as follows: first of all, we define $p(s_{\mathrm{ij}})$ as the routing scheme of satellite $s_{\mathrm{ij}}$ in the system period. Then, we introduce the decision variables $x_{\mathrm{ij}}(i=1,2,\dots ,m;j=1,2,\dots ,n)$ , $m$ is the number of orbit planes, and $n$ is the number of satellites in each orbit planes. $x_{\mathrm{ij}}$ is defined as

$$x_{\mathrm{ij}}=\{\begin{array}{c}0,\mathrm{via\; the\; SGL\; directly}\hfill \\ \multicolumn{1}{c}{\mathrm{number\; of}\mathrm{IS}{L}_{\mathrm{tra}},\mathrm{via\; the}\mathrm{IS}{L}_{\mathrm{tra}}}\\ \multicolumn{1}{c}{\mathrm{number\; of}\mathrm{IS}{L}_{\mathrm{ter}},\mathrm{via\; the}\mathrm{IS}{L}_{\mathrm{ter}}}\end{array}$$

(5)

The establishment of mapping is defined as

$$f\left(x_{\mathrm{ij}}\right)=\{\begin{array}{c}{C}_{\mathrm{SDL}}\left(s_{\mathrm{ij}}\right),x_{\mathrm{ij}}=0\hfill \\ \multicolumn{1}{c}{C_{\mathrm{SDL}}(s_{\mathrm{ij}})+C_{\mathrm{ISL}}\left(s{s}_{\mathrm{ij}}\right),x_{\mathrm{ij}}\ne 0}\end{array}$$

(6)

which corresponds to a specific link based on the decision variables. So, $p(s_{\mathrm{ij}})$ can be expressed as a sequence of decision variables which is defined as

$$p\left(s_{\mathrm{ij}}\right)=\{x_{\mathrm{ij}}(t_0,t_1),x_{\mathrm{ij}}(t_1,t_2),\dots ,x_{\mathrm{ij}}(t_{n-1},t_n)\}$$

(7)

It means that each satellite selects the feasible link by $n$ times in the system period.

Optimization objective

For the GNSS routing problem based on fixed topology, CD, SF, and LLBR are considered as optimization objectives, which are cost-oriented metrics. That is, the smaller the metric, the superior the routing scheme.

CD

Definite the alignment and tracking delay $D_a$ , link transmission delay $D_t$ , onboard processing delay $D_p$ , and the variable $g(x_{\mathrm{ij}})=\{\begin{array}{c}1,x_{\mathrm{ij}}=0\hfill \\ \multicolumn{1}{c}{2,x_{\mathrm{ij}}\ne 0}\end{array}$ . The SGL needs alignment, tracking, and onboard processing once, while the ISLs require twice. So, in the system period, CD of the routing scheme for satellite $s_{\mathrm{ij}}$ is defined as

$$\begin{array}{c}\mathrm{CTD}\left(s_{\mathrm{ij}}\right)=\sum _{n=1}^T{D}_a·g\left(x_{\mathrm{ij}}(t_{n-1},t_n)\right)\hfill \\ \multicolumn{1}{c}{+\sum _{n=1}^T{D}_t\left(f\left(x_{\mathrm{ij}}(t_{n-1},t_n)\right)\right)}\\ \multicolumn{1}{c}{+\sum _{n=1}^T{D}_p·g\left(x_{\mathrm{ij}}(t_{n-1},t_n)\right)}\end{array}$$

(8)

Tracking delay and processing delay take a fixed value, and each SGL accumulates once, while each ISL accumulates twice; the $\mathrm{IS}{L}_{\mathrm{tra}}$ distance takes a fixed value, while the distances of the $\mathrm{IS}{L}_{\mathrm{ter}}$ and SGL take the average in their transmission interval. The link delay is equal to the distance divided by communication velocity, and CD of the routing scheme is obtained by adding up the delay of each satellite.

SF

In the system period, every satellite can access ground stations at intervals, so communication task is completed via SGL at visible intervals while ISLs at invisible intervals. Due to the access intermittent and scheme optimization, it requires switching multiple ISLs to complete the communications between each satellite and ground stations. Link switching needs to adjust antenna pointing, re-track, and realign the targeting which increases the CD and causes the link interruption. So, it must reduce the link SF, when the routing scheme is built. For the initial state, the link is idle, and it requires a switching with a new establishing link. The SGL needs one switching, and the ISL requires switching twice. The SF of routing scheme is calculated by the cumulative switching with traversing the decision window according to the decision variables

$$\mathrm{SF}\left(s_{\mathrm{ij}}\right)=\sum _{n=1}^{T}g\left(x_{\mathrm{ij}}(t_{n-1},t_n)\right)$$

(9)

LLBR

LLBR refers to the balance extent of the satellite communication time allocated to ISL and SGL. LLBR is calculated as standard deviation of link relay time for each task, which is expressed as “std” in equation (11). The task links of satellite $s_{\mathrm{ij}}$ are, respectively, $c_1,c_2,\dots ,c_n$ ( $n$ is the total number) in the system period. The cumulative task time for each link is defined as

$$t\left(c_i\right)=\sum _{n=1}^{T}t(x_{\mathrm{ij}}(t_{n-1},t_n)=c_i)$$

(10)

so the LLBR is

$$\mathrm{LLBR}=\mathrm{std}(t\left(c_1\right),t\left(c_2\right),\dots ,t\left(c_n\right))$$

(11)

Constraint condition

GNSS routing based on fixed topology is necessary to consider the ground station priority, ISL hop, link type selection, and QoS parameters:

1. Ground station priority. For the ground station, Beijing station is the master station, while Kashi and Sanya stations are auxiliary control station. Three stations achieve high-quality and fast communication through terrestrial network. Therefore, the navigation satellite can select any one of the accessed stations to complete satellite-ground communication, and information is transmitted to the Beijing station through terrestrial network.

2. Relay hop. The researched system has strict demand for low delay, and each satellite must communicate with the ground station no more than one relay. The designed ISL scheme based on fixed topology meets relay requirement (within two hops) to complete the satellite-to-ground communication.

3. The link type selection. For the $\mathrm{IS}{L}_{\mathrm{tra}}$ , the link geometry parameters do not change over time, without the satellite relative movement and the adjusted antenna angle, which saves the alignment and tracking delay; for the $\mathrm{IS}{L}_{\mathrm{ter}}$ , alignment and tracking delay increases with inter-satellite relative movement, while the link average distance is short enough to reduce the transmission delay. Because different types of links have different features and properties, the appropriate ISL must be selected to complete communication tasks according to the actual task and resource.

4. QoS. For satellite communication network, it must meet the requirements of users and administrators, including PLR, network throughput, link distance, transmission cost, and other QoS indicators. The bandwidth, PLR, and transmission cost are selected as QoS constraints according to satellite network and routing algorithm.

Bandwidth (BD) is the data quantity in the unit of time passing through the link, and satellite network bandwidth follows the “Barrel Effect.” The link bandwidth is equal to the bandwidth of the minimum hop in the multi-hop link, namely

$$\mathrm{BD}\left(x_{\mathrm{ij}}(t_a,t_b)\right)=min\left\{\mathrm{BD}\left(f\left(x_{\mathrm{ij}}(t_a,t_b)\right)\right)\right\}$$

(12)

For the routing scheme, take the link bandwidth average of all the decision windows as the scheme bandwidth

$$\mathrm{BD}\left(s_{\mathrm{ij}}\right)=\frac{1}{n}\sum _{n=1}^T\mathrm{BD}\left(x_{\mathrm{ij}}(t_{n-1},t_n)\right)$$

(13)

PLR is the ratio between the number of lost packets and sending packets during the information transmission, which is related to packet length and sending frequency. The link PLR within the decision window is defined as

$$\mathrm{PLR}\left(x_{\mathrm{ij}}(t_a,t_b)\right)=\{\begin{array}{c}\mathrm{Loss}\left(f\left(x_{\mathrm{ij}}(t_a,t_b)\right)\right)\hfill \\ \multicolumn{1}{c}{1-\Pi (1-\mathrm{Loss}\left(f\left(x_{\mathrm{ij}}(t_a,t_b)\right)\right))}\end{array}$$

(14)

For the routing scheme, take the average of link PLR within all the decision windows as the PLR of the scheme

$$\mathrm{PLR}\left(s_{\mathrm{ij}}\right)=\frac{1}{n}\sum _{n=1}^T\mathrm{PLR}\left(x_{\mathrm{ij}}(t_{n-1},t_n)\right)$$

(15)

STC is also taken into consideration. Communication link includes SGL, $\mathrm{IS}{L}_{\mathrm{tra}}$ , and $\mathrm{IS}{L}_{\mathrm{ter}}$ , which is composited of the link construction and information transmission. Set the cost weight for each type of link and calculate task time for each link, so the STC is the weighted sum of task time for each link.

In accordance with the link classification of the system, the communication links of each satellite in the system period are defined as $C_1$ , $C_2$ , and $C_3$ , respectively. The weight vector of link cost is $w(C_i),i=1,2,3$ , and the cumulative task time for each link is

$$t\left(C_i\right)=\sum _{n=1}^{T}t(x_{\mathrm{ij}}(t_{n-1},t_n)=C_i),i=1,2,3$$

(16)

So, the transmission cost of routing scheme is

$$\mathrm{STC}=\sum _{i=1}^{3}w\left(C_i\right)*t\left(C_i\right)$$

(17)

Optimization formulation

Through the analysis of the typical algorithm, we find the current algorithms schedule the routing scheme without considering the performance of different optimization objectives. Furthermore, the existing algorithms cannot solve the routing problem adapting to the GNSS topology. According to the problem description and model, we propose the calculation framework and optimization strategy. For the researched GNSS, every satellite can access ground stations at intervals in the system period, and each interval is defined as a decision window. As the system operates, SGL and ISL are selected and combined to complete communication tasks in the decision window. The routing scheme of satellite $s_{\mathrm{ij}}$ is the link sequence selected from all the decision windows. The system routing scheme is obtained by calculating the routing scheme of each satellite sequentially.

Calculation framework

1. Initialization. According to the system composition and topology, the scenario of fixed topology scheme is built, and the access and range conditions of ISL and SGL are calculated. The bandwidth, PLR, and CD of each link are determined with the system operating parameters. For the multi-objective and multi-constraint optimization problem, the objective weights and constraints threshold are determined according to the system status and indicator attributes.

2. Divide decision window. According to the link access between each satellite and ground stations, decision windows are divided in the system period. Take the satellite $s_{\mathrm{ij}}$ , for example, and the access condition to ground stations in the system period is shown in Figure 3. The solid line represents visible interval and dotted line represents invisible interval. Thus, the decision window of satellite $s_{\mathrm{ij}}$ is shown in Table 1. The routing scheme of satellite $s_{\mathrm{ij}}$ is obtained by selecting ISLs and SGL in each decision window according to the access condition.

3. Build alternatives set by the selection and combination of links. According to the system operation period, ISL and SGL are selected and combined sequentially to complete communication in each decision window. For the decision window, the decision is divided into two situations:

4. Select and combine ISLs without available SGLs. The satellite $s_{\mathrm{ij}}$ includes the $\mathrm{IS}{L}_{\mathrm{tra}}$ of $C_{11}(s_{\mathrm{ij}})$ and $C_{12}(s_{\mathrm{ij}})$ and $\mathrm{IS}{L}_{\mathrm{ter}}$ of $C_{21}(s_{\mathrm{ij}})$ and $C_{22}(s_{\mathrm{ij}})$ . According to the ISL access distribution in the decision window, make decisions and the decision variables are

   $$x_{\mathrm{ij}}(t_a,t_b)=\{\begin{array}{c}\mathrm{identifier\; of}\mathrm{IS}{L}_{\mathrm{tra}},\mathrm{via}\mathrm{IS}{L}_{\mathrm{tra}}\hfill \\ \multicolumn{1}{c}{\mathrm{identifier\; of}\mathrm{IS}{L}_{\mathrm{ter}},\mathrm{via}\mathrm{IS}{L}_{\mathrm{ter}}}\end{array}$$
   (18)

Choose the best scheme by multi-objective optimization method. There exist multiple combinations of ISLs in the relay decision window, which makes a set of alternatives. The optimal scheme is selected with the application of multi-objective optimization method. For the relationship between the individual objectives of the system routing scheme, the ELECTRE is chosen to achieve the comprehensive evaluation for the routing scheme based on high-level relationship.

Figure 3.

The access condition between satellite $s_{\mathrm{ij}}$ and stations in the system period.

Table 1.

The routing scheme of satellite $s_{\mathrm{ij}}$ .

Decision window	Access between satellite and station	Decision variables
$(t_0,t_1)$	Satellite $s_{\mathrm{ij}}$ can access the ground station directly	$x_{\mathrm{ij}}(t_0,t_1)=0$
⋮	⋮	⋮
$(t_{11},t_{12})$	Satellite $s_{\mathrm{ij}}$ cannot access the ground station	$x_{\mathrm{ij}}(t_{11},t_{12})=\{\begin{array}{c}\mathrm{identifier\; of}\mathrm{IS}{L}_{\mathrm{tra}},\mathrm{via\; the}\mathrm{IS}{L}_{\mathrm{tra}}\hfill \\ \multicolumn{1}{c}{\mathrm{identifier\; of}\mathrm{IS}{L}_{\mathrm{ter}},\mathrm{via\; the}\mathrm{IS}{L}_{\mathrm{ter}}}\end{array}$

Link selection and combination strategy

For the routing algorithm, parameter setting and data input are made through the initialization, and the decision window is divided by the satellite-ground access. The system routing scheme is obtained by calculating routing scheme of each satellite sequentially. Without considering the impact between the satellite routing schemes, the core is ISL selection and combination according to the algorithm steps. For the visible interval between satellite and ground station, select the SGL directly to complete the communication task. There is a need for an ISL combination according to the access distribution in the decision window without available SGLs:

1. Select one link directly, and the decision variables are assigned with the corresponding values when there exists a link to cover the decision window;

2. Select a combination of two or more links to complete the communication task without a link to cover the decision window.

ISL selection strategy includes the following aspects:

1. The number of ISL. In the decision window, give priority to one ISL to complete communication tasks, while it usually requires two links to cover the entire decision window. Three or four links will not be selected unless both one and two links are unavailable. Add an extra relay link for each decision window, which increases SF, alignment and processing delay while increasing the probability of the scheme without meeting the constraints. Besides, the choice of multiple links will balance the link load theoretically with more SF.

2. Link combination. Specific combinations of ISL include average allocation strategy, which distributes decision window to the covering links evenly; maximum coverage-completion strategy, which gives priority to the link with the maximum coverage and replenishes the remaining part by another link; and fixed percentage allocation strategy, which assigns communication time to each link in certain proportion, such as the golden ratio. Allocation process of decision window will be divided into a series of intervals, which is relayed by an ISL and distributed a decision variable.

3. Link type selection. When the satellite can access ground station, select the SGL directly to complete the communication task, and select ISLs without available SGLs in the decision window. The ISL includes $\mathrm{IS}{L}_{\mathrm{tra}}$ and $\mathrm{IS}{L}_{\mathrm{ter}}$ with different characteristics and advantages. Preference to the $\mathrm{IS}{L}_{\mathrm{tra}}$ will reduce the SF but increase transmission delay because of the larger inter-satellite distance; preference to the $\mathrm{IS}{L}_{\mathrm{ter}}$ will reduce transmission delay with the shorter inter-satellite distance, while the alignment delay increases with the relative movement between different satellites. There is no distinction between two $\mathrm{ISL}{s}_{\mathrm{tra}}$ , either is the $\mathrm{ISL}{s}_{\mathrm{ter}}$ . After satisfying the constraints, either link is selected to build the alternatives.

4. The link maintaining strategy. In the ISL relay decision window, it usually contains multiple combination schemes of ISLs. Give priority to one ISL covering the entire decision window and keep the ISL covering the decision window. This strategy can reduce the SF and alignment delay, at the expense of link loading balance, which ensures the comprehensive performance of the routing scheme.

Simulation and numerical results

An actual MEO satellite network is taken as an example for validating the significance of topology-adapting routing strategy for GNSS. First of all, we build the ISL scheme based on fixed topology according to the constructing process. Then, numerical results are compared to evaluate the performance of link selection and combination strategy.

ISL scheme for instance system

Space constellation of the MEO system adopts Walker 24/3/1 configuration, and the ground segment includes Beijing, Kashi, and Sanya stations. The STK scenario is built with the detailed network parameters in Table 2.

Table 2.

MEO satellite communication network parameters.

Parameter	Value
Number of satellites	24
Orbit height	21,540 km
Orbital inclination	55°
Orbital period	46,423.8 s
Constellation type	Walker Delta 2
ISL	2 $\mathrm{ISL}{s}_{\mathrm{tra}}$ and 2 $\mathrm{ISL}{s}_{\mathrm{ter}}$
ISL status	Permanent
Coverage range	Global
Single satellite cycle	46,423.8 s
Constellation periodic	7 days return period on
Orbit	Lap 13

First of all, we make the constellation characteristic analysis for the instance system. The difficulty and composing elements of the ISL scheme are analyzed through the access and geometric parameters by the STK. The MEO system adopts the constellation configuration of Walker, and three orbits are symmetrical. The intra-plane links of three orbits have complete access and stable geometric parameters in the system period, so intra-plane satellites can establish permanent links. Most inter-plane links have complete access apart from some links with intermittent access, and the changing rate of geometric parameters is small. Therefore, part of inter-plane satellites can be selected to establish permanent links.

Then, we build the ISL scheme according to the constructing process. The global communication between the instance system and ground stations has stricter demand for the CD and relay hops. Thus, for the link type, the permanent link is chosen to construct the ISL scheme. Through the constellation characteristic analysis, it indicates that intra-plane satellites with complete access can establish permanent links, while part of inter-plane satellites can establish permanent links. The system constellation consists of 24 satellites in three orbits, which has a larger scale. Each satellite should establish less links to meet the resource constraints. In particular, each satellite in the scheme establishes four links, including two $\mathrm{ISL}{s}_{\mathrm{tra}}$ and two $\mathrm{ISL}{s}_{\mathrm{ter}}$ . The system adopts constellation configuration of Walker 24/3/1, each satellite of which is in the circular orbit with the same altitude and inclination. The orbits are distributed symmetrically along the equatorial plane, and the intra-plane satellites are distributed symmetrically in the orbit. There exists a certain relationship for the adjacent satellites in different orbits in the phase.

According to the designed capacity and requirements, each MEO satellite has built two $\mathrm{ISL}{s}_{\mathrm{tra}}$ and two $\mathrm{ISL}{s}_{\mathrm{ter}}$ . In the scheme, the $\mathrm{IS}{L}_{\mathrm{tra}}$ employs star structure, taking the first intra-plane topology as an example shown in Figure 4.The star topology of ISL has an advantage over other structures (such as the annular link) to communicate with the ground station directly no more than single hop. The $\mathrm{IS}{L}_{\mathrm{ter}}$ employs adjacent structure (shown in Figure 5) with better performance in transmission delay, which is used as an auxiliary when the $\mathrm{IS}{L}_{\mathrm{tra}}$ cannot have full-time access to the ground station. Two $\mathrm{ISL}{s}_{\mathrm{tra}}$ and two $\mathrm{ISL}{s}_{\mathrm{ter}}$ are numbered from 1 to 4, and the SGL is numbered as 0.

Figure 4.

The $\mathrm{IS}{L}_{\mathrm{tra}}$ topology.

Figure 5.

The $\mathrm{IS}{L}_{\mathrm{ter}}$ topology.

Fixed topology of ISL consists of basic pairing based on the fixed combination of link establishments. In this article, the link combination contains two $\mathrm{ISL}{s}_{\mathrm{tra}}$ and two $\mathrm{ISL}{s}_{\mathrm{ter}}$ with full-time access. The fixed topology can satisfy the requirements of precise orbit determination and time synchronization with redundancy and simple structure. The $\mathrm{IS}{L}_{\mathrm{tra}}$ is built with the furthest visible satellite to improve link geometric distribution, which ensures maximum connectivity so that overseas satellite can be relayed back to the territory as soon as possible. The $\mathrm{IS}{L}_{\mathrm{ter}}$ is built with the nearest visible satellite to improve the precision and reliability.

Performance analysis with numerical results

According to the system composition and topology, build the system scenario of fixed topology and then the access and range conditions of ISL and SGL are calculated. The bandwidth, PLR, and tracking and processing delay of each link are determined with the system actual operating parameters. For the multi-objective and multi-constraint optimization problem, the objective weights and constraints threshold are determined according to the system status and indicator attributes.

According to the access condition between the satellite $s_{\mathrm{ij}}$ and ground stations, the system period is divided into a series of decision windows. As the system operates, SGL and ISL are selected and combined to complete communication tasks in the decision window. The routing scheme of satellite $s_{\mathrm{ij}}$ is the link sequence selected from all the decision windows. The system routing scheme is obtained by calculating routing scheme of each satellite sequentially.

Taking the satellite $s_{\mathrm{ij}}$ , for example, we calculate the routing scheme and optimization indicators, as shown in Tables 3 and 4. In Table 3, the system is divided into 23 decision windows, different link selections are made at intervals in each decision window, and the decision variables are the identifier of SGL and ISLs.

Table 3.

Routing scheme of satellite $s_{11}$ .

Decision window	Interval(s)	Decision variables
1	0–13,986	0
2	13,986–31,85031,850–49,713	31
3	49,712–109,293	0
4	109,293–127,790127,790–146,287	41
5	146,287–167,572	0
6	167,572–174,174	3
7	174,174–205,950	0
8	205,950–241,564	4
9	241,564–256,904	0
10	256,904–269,161	1
11	269,161–304,413	0
12	304,413–320,628320,628–336,843	23
13	336,843–343,875	0
14	343,875–364,374	3
15	364,374–401,830	0
16	401,830–430,797430,797–459,764	23
17	459,764–496,973	0
18	496,973–505,502505,502–514,031	24
19	514,031–522,492	0
20	522,492–539,136539,136–555,780	31
21	555,780–592,042	0
22	592,042–599,478	2
23	599,478–604,800	0

Table 4.

Optimal indicators of satellite $s_{11}$ routing scheme.

Routing scheme	CD (s)	SF	LLBR
$s_{11}$	6.3148	29	0.4998

CD: communication delay; SF: switching frequency; LLBR: link loading balance rate.

In accordance with the steps above, routing schemes of each satellite are accurately calculated in the system period, indicating that the proposed method can effectively solve the routing problem based on fixed topology. The experiment is carried on to validate the practical effect of link selection and combination strategy.

Link selection and combination strategy adopted in the simulation include the following: give priority to one ISL or two links to cover the entire decision window; the link combination selects the average allocation strategy, and adopt the link maintain strategy without the link type selection strategy. The above proposed strategy is considered to have better performance. Accordingly, we select three strategies, random strategy, sequence strategy, and reverse strategy as the comparison methods. In particular, the random strategy is just to select the feasible ISLs to cover the decision windows randomly without the proposed link selection and combination strategy. The sequence strategy is to select and combine the ISLs to cover the invisible intervals sequentially in the serial number of each satellites links. In the simulation, each MEO satellite has built two $\mathrm{ISL}{s}_{\mathrm{tra}}$ and two $\mathrm{ISL}{s}_{\mathrm{ter}}$ , and the links are numbered in sequence. Similarly, the reverse strategy is to select and combine the ISLs to cover the invisible intervals in the inverted sequence. The simulation is as follows: first obtain the routing schemes according to the four strategies and then analyze the performance of optimization strategies by comparing the individual and comprehensive indicators:

1. Comparison of CD: The routing scheme of each satellite is calculated, and CD comparison of four strategies is shown in Figure 6. From the experimental results, we can see that the proposed strategy has a better performance over other strategies in the CD. For one reason, the proposed strategy gives priority to fewer links to complete the communication task within the entire decision window when different combinations meet the constraints. Besides, select the ISL in priority which covers the task interval continuously. Compared with the random strategy and sequence strategy, the proposed strategy greatly reduces the alignment and tracking delay caused by link switching, which ultimately reduces CD of the routing scheme. According to the definition, the essence of sequence strategy is to select the $\mathrm{IS}{L}_{\mathrm{tra}}$ in priority, while the reverse strategy is to select the $\mathrm{IS}{L}_{\mathrm{ter}}$ in priority. The reverse strategy reduces transmission delay with the shorter inter-satellite distance, so that it is close to the proposed strategy in CD.

2. Comparison of SF: The routing scheme of each satellite is calculated, and SF comparison of four strategies is shown in Figure 7. From the experimental results, we can see that the proposed strategy has a better performance over other strategies in the SF. This is because the proposed strategy prefers fewer links to complete the task and select the ISL to cover the entire decision window, which effectively reduces the number of link switching.

3. Comparison of link loading balance: The routing scheme of each satellite is calculated, and the comparison of LLBR is shown in Figure 8. From the experimental results of four strategies, we can see that the proposed strategy has a moderate performance in the link loading balance. On one hand, the average allocation strategy distributes the task time evenly to the adjacent links, which will improve LLBR of the scheme; on the other hand, it prefers fewer links to complete the task and maintains links covering task interval, which will concentrate traffic loading on some link and reduce the LLBR; therefore, the proposed strategy ensures the routing scheme is moderate in LLBR. However, the random strategy selects the feasible ISLs to cover the decision windows randomly, which also maintains better LLBR.

4. Comparison of comprehensive valuation: The comprehensive evaluation of each satellite routing scheme is calculated based on individual indicators, and the result comparison of four strategies is shown in Figure 9. From the experimental results, we can see that the proposed strategy has a better performance over other strategies in the comprehensive evaluation. By comparing the individual indicator, the proposed strategy has an outstanding performance in CD and SF, while the LLBR is moderate; therefore, the proposed strategy is effectively applied to calculate the optimum routing scheme in comprehensive evaluation.

Figure 6.

Communication delay comparison of four strategies.

Figure 7.

Switching frequency comparison of four strategies.

Figure 8.

Link loading balance rate comparison of four strategies.

Figure 9.

Comprehensive evaluation comparison of four strategies.

Through the four experiments, the link selection and combination strategy is analyzed from the effectiveness of individual and comprehensive optimization indicators. The results show that the proposed strategy has an outstanding performance in CD and SF while ensuring the LLBR is moderate. Therefore, the proposed strategy can calculate the optimized routing scheme of comprehensive evaluation effectively. In order to solve the GNSS routing problem effectively, the ISL scheme based on fixed topology should be built in advance. Then, the optimal routing scheme is obtained with the link selection and combination strategy according to the designed method.

Conclusion

Due to the dynamic topology of GNSS and navigation requirements, the routing technology of terrestrial network is not adaptable to solve the navigation information transmission of GNSS. Therefore, we study the topology-adapting routing strategy for the communication constraints of time synchronization and inter-satellite ranging. In this article, we propose the design method of the ISL scheme for the research status of GNSS and limitations of traditional topology control strategy. It is found that the designed scheme can establish the stable ISL quickly and effectively through the geometric characteristics analysis of the ISL in simulation scenario. Then after describing the routing system problem in detail, we build a multi-constraint and multi-objective mathematical model and design the routing method based on fixed topology. Finally, simulation experiments illustrate that the proposed method can effectively solve the GNSS routing problem based on fixed topology to meet the actual requirements. The further comparative analysis of the routing scheme verifies whether the link combination and selection strategy has an optimized performance in terms of CD, SF, and link loading balance.