Dynamic Satellite Network Routing Algorithm Based on Link Scheduling

Abstract

Inter-satellite link (ISL) in dynamic satellite network, due to its characteristics like wide coverage area, large population of users, and the motion of satellites in orbit planes, is easy to be interfered with. In order to solve above problems, this paper proposed a dynamic satellite network routing algorithm based on the link scheduling model. First, the geometric characteristics of ISL were analyzed, and the distance, elevation angle, azimuth of ISLs were calculated respectively based on spatial characteristics of constellation. Then we established a time-slot scheduling model of ISL based on TDMA system and proposed a routing algorithm of ISL based on hop threshold with a minimum transmission time. The final simulation results indicated that this routing algorithm can not only reduce the frequency of link switching in the path of information transmission effectively, but also complete most of the information transmission within half a superframe.

1 Introduction

Satellite networking, which can greatly enhance the transmission performance of dynamic satellite networks, has become an important part of the global mobile communication system and is going to make global coverage come into reality. In recent years, with the increasing demand for space broadband communications, the study of key technologies in the new generation of broadband satellite communication networks with ISL and onboard processing functions, especially the study of routing algorithms have received widespread attention [1, 2].

Inter-Satellite Link (ISL) ISL is a link in the satellite network through which the exchange of information is completed via radio. It can achieve autonomous navigation by ranging and communication and improve the reliability of the system through cooperation with the ground segment [3, 4].

How to chose a routing between satellites is a crucial issue when using ISL for satellite networking. As for the satellite network, due to the constant movement of satellite nodes, the changes of network topology are too frequent to use ground routing algorithm directly. Instead, a routing algorithm in accordance with the characteristics of satellite networks need to be designed.

At present, domestic and foreign scientific researchers have proposed a variety of satellite network routing algorithms for the characteristics of satellite networks. Chang et al. [5] proposed the Finite-state Automation (FSA) routing algorithm based on virtual topology. On the other hand, Ekici et al. [6] designed the datagram routing algorithm (DRA) for LEO satellite network.

This paper is organized as follows. In Sect. 2, we analyze the characteristics of topology of the MEO/GEO double-layer satellite constellation. A time-slot allocation model for ISL based on TDMA system is established in Sect. 3, and a routing algorithm which sets a threshold of the information transmission hop and selects the routing with minimum transmission time is designed in Sect. 4. In Sect. 5, stimulation is conducted to validate the performance of this routing algorithm. Conclusion is provided in Sect. 6.

2 Constellation Configuration and ISL Parameter Analysis

2.1 Constellation Configuration

This paper used GPS satellite constellation whose structure is 24/6/1 Walker constellation. 24 MEO satellites are distributed in six orbital planes with 55° of orbit inclination, 20200 km in orbital height and an orbital period of 11 h 58 min. In order to facilitate the analysis of data, 24 MEO satellites are named MEO11–MEO64 respectively. The high part of the number indicates the orbital plan number, and the low part of the number indicates the number of the satellite on the orbital plane. We also added three GEO satellites to the GPS satellite constellation to optimize the performance of satellite network. The three GEO satellites named GEO1, GEO2, and GEO3 are evenly distributed in the equatorial plane and the angle between each of them is 120°. Besides, a sensor is placed on each satellite to limit its visible range.

2.2 ISL Parameter Analysis

As the position of the satellites constantly changes, the geometric parameters of the ISL, such as the direction and distance, will also change. These time-varying parameters can have an impact on the allocation and routing algorithm of ISL.

The directivity of ISL is characterized by the following two parameters: elevation angle and azimuth between satellites. The definition of elevation angle and azimuth is shown in Fig. 1, in which satellites S_1, S₂ are non-geostationary satellites and they are not in the same orbital plane. Circle S₁ indicates the tangent plane when the satellite S₁ runs to the current position. The tangent plane intersects the plane OS₁S₂ (O is the center of the earth), and the straight line S₁P is the intersection line of them. Observed from the satellite S₁, angle ∠S₁S₂P is the elevation angle. If it is specified that the azimuth of due north is zero degree, then the azimuth between satellite S₁ and satellite S₂ is greater than 180°.

Fig. 1.

The elevation angle and azimuth between Satellite S₁ and Satellite S₂

By calculating the specific values of the elevation angle and azimuth of the satellites, the directivity of ISL can be estimated. The calculation method is as follows:

Elevation angle $\phi_{r}$:

$$ \begin{aligned} \phi_{r}\, {=} & - \frac{1}{2}\arccos \{ [\cos^{2} \left( {\Delta\Omega /2} \right) - \cos^{2} \beta \sin^{2} \left( {\Delta\Omega /2} \right)]\cos (\gamma_{1} - \gamma_{2} ) \\ + & \cos \beta \sin \Delta\Omega \sin (\gamma_{1} - \gamma_{2} ) - \sin^{2} \beta \sin^{2} (\Delta\Omega /2)\cos (\gamma_{1} + \gamma_{2} + 2x) \\ \end{aligned} $$

(1)

In formula (1), $\Delta\Omega$ represents the longitude difference between the ascending nodes of the orbits where the satellite S₁ and the satellite S₂ are located. $\gamma_{1} \gamma_{2}$ represents the phase difference between the two satellites at the initial time, and x means the phase of the satellite at the time t from its initial position.

Azimuth from satellite S₁ to satellite S₂ $\left( {i = 1,\,j = 2} \right)$:

$$ \begin{aligned} \tan \psi_{ij} & = [\sin \beta \sin \Delta \lambda \cos (\gamma_{j} + x) - \sin 2\beta \sin^{2} (\Delta \lambda /2)\sin (\gamma_{j} + x)]/ \\ & [\sin^{2} \beta \sin^{2} (\Delta \lambda /2)\sin (\gamma_{i} + \gamma_{j} + 2x) + 2\cos \beta \cos (\Delta \lambda /2)\sin (\Delta \lambda /2) \times \\ & \cos (\gamma_{i} - \gamma_{j} ) + \cos^{2} (\Delta \lambda /2) - \cos^{2} \beta \sin^{2} (\Delta \lambda /2)\sin (\gamma_{i} - \gamma_{j} )] \\ \end{aligned} $$

(2)

According to the spherical triangle formula, the formula for the distance d between S₁ and S₂ on the sphere is

$$ d = 2r\left| {\sin (\phi_{r} )} \right| $$

(3)

3 Dynamic Satellite Network Link Scheduling Strategy

3.1 ISL Visibility Processing

Visibility between two satellites is a physical prerequisite for establishing ISL. As satellites are in a state of constant motion, the relative positions of them will change with time, which leads to dynamic changes of the visibility between satellites.

Based on TDMA system, this paper designs the ISL scheduling scheme and establishes the ISL time-slot scheduling model. The orbital period of satellite is divided into a number of equally spaced superframes, then each superframe is further divided into a number of equally long time slots.

Definition 1

The inter-satellite visibility in the k-th superframe is defined as

$$ v_{ij} = \left\{ {\begin{array}{*{20}c} {1,satellite\;S_{i} \;and\;S_{j} \;{\text{are continuously visible at the k}} - {\text{th superframe}}} \\ {0,satellite\;S_{i} \;and\;S_{j} \;{\text{are intermittently visible at the k}} - {\text{th superframe}}} \\ \end{array} } \right. $$

(4)

$$ V_{k} = \left[ {\begin{array}{*{20}c} {v_{11} } & {v_{12} } & \ldots & {v_{1M} } \\ {v_{21} } & {v_{22} } & \ldots & {v_{2M} } \\ \vdots & \vdots & \ddots & \vdots \\ {v_{N1} } & {v_{N2} } & \ldots & {v_{NM} } \\ \end{array} } \right]_{N \times M} $$

(5)

$V_{k}$ is the inter-satellite visibility matrix of the k-th superframe. N is the total number of satellites in the satellite network, and M is the number of time slots per superframe.

Definition 2

Internal satellite and External satellite: Ground stations are set up in the satellite scene for transmitting signals to and receiving signals from satellites. Then, satellites visible to the ground station are defined as the internal satellites, and satellites which are invisible to the ground station are the external satellites.

Definition 3

Static ISL and Dynamic ISL: ISLs between satellites which are visible throughout the satellite operation cycle are defined as static ISLs, and ISLs between satellites which are intermittently visible during the operation cycle are defined as dynamic ISLs.

Static ISL has the advantages of wide distribution, large elevation angle, and high link budget, so its performance is better than that of dynamic ISL.

3.2 ISL Time-Slot Scheduling Model

This ISL time-slot scheduling model used is based on TDMA system. In each time slot: (1) There are mutually uninterrupted links between the satellites; (2) Each satellite can only have one link of them [7].

First, in order to facilitate data analysis and collation, satellites MEO11–MEO64 are numbered from1 to 24, and satellites GEO1–GEO3 are numbered from 25 to 27. The links of satellite S_i are classified, of which the static ISLs are put into set $Q_{i}$ and the dynamic ISLs are put into set $D_{i}$.

Second, for the k-th superframe, the ISL time- slot matrix $P_{k}$ is established. Because the performance of the static ISL is better than that of the dynamic ISL, the static ISL is preferentially placed into the time-slot matrix. The main function of the ISL is to relay information between invisible internal satellites and external satellites. Therefore, the smaller the probability that they exist at the same time, the better.

According to the order of the probability that the satellites are present in the territory at the same time from small to large, the satellites in set $Q_{i}$ are sequentially placed in the i-th row of the time-slot matrix $P_{k}$. The satellites in set $D_{i}$ are then sorted in the same way as described above and are placed in the subsequent time slot of the i-th row of slot matrix $P_{k}$. The slot matrix $P_{k}$ is represented as

$$ P_{k} = \left[ {\begin{array}{*{20}c} a & d & \ldots & f \\ c & 0 & \ldots & e \\ \vdots & \vdots & \ddots & \vdots \\ 0 & r & \ldots & g \\ \end{array} } \right] = \left[ {\lambda_{ij} } \right]_{m \times n} $$

(6)

In formula (6), the element $\lambda_{ij}$ in matrix $P_{k}$ represents the satellite number pointed to by satellite i in the j-th time slot of the k-th superframe. If $\lambda_{ij}$ is zero, it means that satellite i did not establish an ISL in the k-th time-slot of the k-th superframe. m represents the number of satellites in the constellation, and n represents the number of time slots in a superframe.

Then, based on the inter-satellite visibility matrix $V_{k}$ in this superframe, the inter-satellite links between the invisible satellites in the k-th superframe in the time-slot matrix $P_{k}$ are deleted, and the corresponding position elements are set to zero. Finally, the GEO satellites visible with the MEO satellites in the k-th superframe are placed in the position of the zero elements in the time-slot matrix $P_{k}$ according to certain rules. At this point, the ISL time-slot allocation matrix of the k-th superframe is obtained.

4 ISL Routing Algorithm

4.1 Information Transmission Time Analysis

At present, various researches are basically based on virtual topology control strategies to study routing algorithms. However, the ISL scheduling model established in this paper is based on the TDMA system, and inter-satellite links are arranged in fixed time slots according to the rules of the scheduling model. When information is routed according to the routing algorithm, there is a double limitation of space and time. Therefore, the information transmission time is no longer only related to the distance between satellite nodes. For the ISL time-slot scheduling model of this paper, the time from starting looking for the dissemination path to arriving the destination satellite node includes the following three parts:

• (1) The delay $t_{w}$ when the source satellite node waits to send information;

• (2) The delay $t_{a}$ when the information dissemination in free space;

• (3) The number of time slots $t_{r}$ that the information spent on the transmission path

Three delays are not the simple superposition relationship. The second delay $t_{a}$ is much less than the third delay $t_{r}$, and $t_{a}$ and $t_{r}$ are inclusion relations. Therefore, the total time of information transmission is

$$ t_{delay} = t_{w} + t_{r} $$

(7)

4.2 ISL Routing Algorithm Steps

For ISL, link stability is a very important but difficult problem to solve. The routing algorithm studied in this paper can effectively solve the contradiction between link switching times and information transmission time. That is, within a limited number of hops c, the minimum transmission time is found, and an inter-frame transmission mechanism is added to solve the packet loss caused by the link switching between each frame. The specific algorithm process is as follows:

• step 1 For the satellite scene studied in this paper, the visibility relationship between satellites is analyzed and the number of time slots and the length of time slots in a frame are set reasonably. Based on the analysis results, the ISL time-slot scheduling model is established, and the time-slot matrix P for each frame in the constellation operation cycle is obtained.

• step 2 According to the slot matrix P, the simulation finds a reasonable limited hop count c so that the hop count value not only satisfies the proper number of link switching, but also enables the information to find the path from the source satellite node to the destination satellite node.

• step 3 The source satellite node S_s numbered S generates information at time t and needs to transmit the information to the destination satellite node S_d numbered d. Calculate the superframe number k and time-slot number q where time t is located. First, look for all one hops in the k-th superframe to reach the destination satellite node’s path set $L_{1}$, then look for all two hops to reach the destination satellite node’s path set $L_{2}$……until you find all c hops to reach the destination satellite node’s path set $L_{c}$. Calculate the total transmission time of each path in all sets $t_{delay1} ,t_{delay2} , \ldots \ldots ,t_{delayn}$. The corresponding paths are $l_{{t_{delay1} }} ,l_{{t_{{_{delay2} }} }} , \ldots \ldots ,l_{{t_{delayn} }}$. Select the path with the shortest total transmission time as the final information propagation path, namely:

$$ L = \left\langle {l_{{t_{delay1} }} ,l_{{t_{delay2} }} , \ldots \ldots ,l_{{t_{delayn} }} } \right\rangle $$

(8)

If no transmission path is found in the k-th superframe, go to the fourth step.

• step 4 If no dissemination path is found in k-th superframe, the inter-frame transmission mechanism is started. The information is generated in time slot numbered q and the first nonzero element after time slot q in the s-th row of the time-slot matrix $P_{k}$ is sought—satellite S_s1, which is considered as the first hop of the path and is treated as a temporary source satellite node. Then, the shortest transmission time path from the temporary source satellite node S_s1 to the destination satellite node S_d is found in the superframe numbered $k + 1$ according to the method of the third step.

4.3 Multiple Service Information Queuing Processing Mechanism on the Satellite

When multiple service information are transmitted in the satellite network, it is highly likely that multiple service information arrive at a satellite node at the same time. If the routing algorithm does not include the multiple service information queuing processing mechanism, channel congestion is likely to occur, resulting in increased transmission delay or even packet loss. For this situation, the following mechanism is used for processing:

• 1. If a plurality of service information simultaneously start from a certain source satellite node, the transmission paths of the plurality of service information are sequentially calculated according to the order of arrival at the source satellite node. Then according to the path allocated by the routing algorithm, the service information with less waiting time slots is transmitted first. If multiple service information need to use the same time slot, they are transmitted in order according to the sequence of arrival at the satellite.

• 2. If multiple service information arrive at a certain intermediate satellite node at the same time according to paths allocated by the routing algorithm, the information that can be sent in the time slot closest to the current time is transmitted first according to the original route calculated by the routing algorithm. If multiple service information need to use the same time slot, they are transmitted in order according to the sequence of arrival at the satellite. If the queuing delay of a service information exceeds the time threshold set in the algorithm, the intermediate satellite node recalculates the transmission path to avoid packet loss.

5 Simulation and Analysis

This paper makes use of STK and MATLAB software to verify the designed routing algorithm. Based on the stability of ISL, the time and number of hops of the information are briefly evaluated.

The service flow network scenario set in the simulation is used to verify the routing algorithm’s ability to unicast service flow. Since the Walker constellation established in this paper has symmetry, the satellites MEO11 and MEO13 on the same orbit plane, the satellites MEO13 and MEO63 on the different orbit planes are selected respectively as the source satellite node and the destination satellite node of the service information flow in this scenario. During the satellite constellation operation cycle, packets are evenly sent from the source satellite node at a packet sending rate of 20 packets/min. The calculation time of the routing algorithm is negligible. The ISL routing algorithm designed in this paper is used to calculate the transmission path of the packet. If the multi-service information arrive at an intermediate satellite node at the same time, the onboard service information queuing processing mechanism is started. Simulation shows the average transmission time probability histogram and the average transmission hop probability histogram of the service information flow in the satellite constellation operation cycle, as shown in Figs. 2 and 3.

Fig. 2.

Average transmission time probability histogram and the average transmission hop probability histogram of the service information flow from MEO11 to MEO13

Fig. 3.

Average transmission time probability histogram and the average transmission hop probability histogram of the service information flow from MEO13 to MEO63

From Figs. 2 and 3, the average transmission time of the service information flow between the satellites in the same orbit is 5–20 s, and the proportion of 10–15 s is very large. The average transmission time of the service information flow between the satellites in the different orbits is 5–25 s. The proportion of the same 10–15 s accounts for a large proportion. Regardless of whether the information is transmitted between satellites in the same orbit or between satellites in the different orbit, their average transmission hops are between 1 and 3 hops. The number of inter-satellite link switching is measured by the number of hops of information. This shows that the ISL routing algorithm studied in this paper ensures that most information can be transmitted from the source satellite node to the destination satellite node through a small number of link switching. And because of the inter-frame transmission mechanism, the shortest transmission time path of information is always found from the source satellite node to the destination satellite node according to routing algorithm, even if it is generated in the last time-slot of each superframe, which greatly improves the stability of ISLs.

6 Conclusion

In this paper, a time-slot scheduling model for ISL is established based on TDMA system, and a new dynamic satellite network routing algorithm is designed for this model. The routing algorithm sets a threshold of information propagation hops, and then finds the path with shortest transmission time, which enables most of the information generated at any time during the satellite’s orbital period to be transmitted in a limited number of hops within half a superframe. The inter-frame transmission mechanism is also added to this routing algorithm to reduce the impact of link switching on information transmission. After simulation analysis, this algorithm is proved to greatly improve the stability of information transmission in dynamic satellite networks. This dynamic satellite network routing algorithm designed in this paper is only a preliminary result. Further study and optimization of the routing algorithm will be conducted in the near future. For instance, in order to enhance the performance of information transmission, services with different priories will adopt different rules to choose routing.