Research on Hopping Routing of Periodic Multiorbit LEO Satellites

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Compared to traditional high-orbit large satellites, low Earth orbit microsatellites have remarkable advantages such as shorter development cycles, lower launch costs, and flexible launch methods. In particular, in recent years, with advancements in microelectronics technology, the development of lightweight materials, and the emergence of high-power solar cells, microsatellites have experienced rapid growth and found widespread applications in global civilian communications, remote sensing meteorology, and space science. For example, SpaceX’s Starlink program is aimed at achieving global coverage with a low Earth orbit constellation of 4425 satellites and a very low Earth orbit constellation of 7518 satellites, providing various services such as communication, meteorology, and mapping. China’s “GW” project is also expected to launch 12,992 satellites to provide more reliable and comprehensive communication services globally [1]. With the rapid development of microsatellite technology, the number of satellites in the network continues to increase, as well as the number of orbits. Due to the fast-changing topology of the satellite network, significant variations in link delays, high probabilities of node and link failures, limited resources, and dynamic changes in traffic load, the quality of routing algorithms has a tremendous impact on intersatellite communication [2].

Many effective studies have been conducted by previous researchers on this subject. Zhao, Long, and Wang considered factors such as satellite transmission capacity and intersatellite link reliability and modeled the satellite network routing problem as a selective problem of intersatellite link selection. They established a multiconstrained optimization problem and proposed an improved ant colony algorithm to solve the routing problem [3]. Wang from Beijing University of Posts and Telecommunications proposed a routing algorithm scheme for low-orbit satellite based on DDQN [4], which effectively combined the perception ability of deep learning and the decision ability of reinforcement learning. By driving the reward function and the two-hop link state perception strategy, the routing algorithm can effectively adapt to the dynamic change of satellite network traffic and select the optimal next hop according to the two-hop link state. Wang, Kishk, and Alouini [5] proposed a routing algorithm for LEO satellite networks based on stochastic geometry, which is well suited as an effective mathematical work for system-level analysis of satellite network topology. The first two algorithms are highly intelligent algorithms that are decentralized and well suited for dynamic optimization of routing, while the latter algorithm is more of a system-level analysis of the network topology from a mathematical perspective. However, for complex algorithms based on machine learning, deep learning, and other techniques, although they can plan excellent routing paths and achieve very low propagation delays, the algorithms are extremely complex. It imposes high computational and information storage requirements on each intersatellite node and does not consider the single-step distance for each hop. Therefore, it is difficult to effectively reduce hardware costs. Reference [6] proposed the ITO scheme, which utilizes digital twins to map the satellite network into virtual space and improves the efficiency of intersatellite data transfer by verifying and selecting the optimal routing paths based on the time-varying graphs in advance, in order to reduce the end-to-end ISL paths and communication delays. Inspired by this, this paper proposes a time-slice–based predictive routing algorithm. The operational time of the satellite network within one cycle is divided into multiple time slices, assuming that the relative distance between satellites does not change within each minimal time slice. The algorithm makes predictions and selects the routing path with the minimum single-step distance.

2. System Model

2.1. Model Composition

2.1.1. Basic Model

In this model, satellites are considered to be assigned to orbits with the same altitude but different inclinations, with a total of $M$ orbit planes and $N$ satellites in each orbit. The relative positions of satellites in orbit are fixed. These satellites are in motion all the time, and the relative positions of satellites in different orbits are changing all the time. In our study, it is assumed that the motion of the satellite is periodic, and every $Q$ hour is a complete cycle. The $m$ orbits are different planes, so no strict rules are made for the inclination angles of the orbits, which makes the research in this paper more universal. In this model, the first orbit can be named orbit $A$, the second orbit can be named orbit $B$, and so on for the others. However, there is a high probability that these two satellites cannot be sent directly, because they are blocked by the contour of the Earth. At this time, it is necessary to rely on the forwarding of other satellites. This paper researches the routing design of this problem. The core research topic of this paper is to reduce the transmission distance of single step.

Table topo: $$\begin{array}{}& \text{topo}=\begin{array}{ccc}{a}_{1\_1}& \cdots & a_{1\_MN}\\ a_{2\_1}& \cdots & a_{2\_MN}\\ ⋮& ⋮& ⋮\\ a_{MN\_1}& \cdots & a_{MN\_MN}\end{array}\end{array}$$

In the table, $a_{i\_j}$ represents the direct connection distance between No. $i$ satellite and No. $j$ satellite. If two satellites cannot communicate directly, the corresponding bits are represented by symbol inf, indicating that two satellites are shielded from each other and cannot be directly connected. Here, there is an orbit for satellites numbered 1 to $n$, an orbit for satellites numbered $n+1\text{to}2n$, and so on. Of course, this topo list is constantly changing.

Table node: $$\begin{array}{}& \text{node}=b_1,b_2,\cdots b_{MN-1},b_{MN}\end{array}$$

The data in the node table represents the waiting processing delay of data processed inside the node at that time. Of course, the data in the table is also constantly changing.

2.2. Contrast Algorithm

As shown in Figure 1, this is a schematic diagram of a low Earth orbit satellite constellation system, which includes multiple operational orbits.

[figure(s) omitted; refer to PDF]

In order to compare and evaluate the algorithm proposed in this paper, two other typical algorithms are selected for comparison. One is the flooding algorithm that traverses all possible paths, which calculates the path with the shortest delay, and the other is the fixed gateway node routing algorithm, which is currently widely used because of its high practicality.

2.2.1. Fixed Gate Node Routing Algorithm

The fixed gate node routing algorithm requires the use of the Dijkstra algorithm and selects fixed satellite nodes within each orbit to communicate with satellites from other orbits, as shown in Figure 2. The detailed steps are as follows:

1. Three gateway node satellites are fixed in each orbit. Communication between different orbits is possible only using the gateway node satellites, and only gateway nodes can communicate with each other. The gateway node satellites store information about their communications with gateway nodes in other orbits.

2. When both the source satellite and the destination satellite are in the same orbit, the Dijkstra algorithm is used to calculate the route directly. The path here is the path of the signal transmission, which is a straight-line distance.

3. When the source node and destination node are not in the same orbit, the source node ($S$) first sends data to the three gateway nodes ($F1$, $F2$, and $F3$) within the orbit. After all three passing nodes receive data, they start to determine whether the data can be sent within the time range. If this is the time period that a pass node can send, then it will be sent to the passing node of another orbit. The other two gateway nodes discard information directly. When the information is transmitted to the gateway node ($F4$) of the target node’s orbit, the information is sent to the target node ($D$) through the Dijkstra algorithm [7–9].

[figure(s) omitted; refer to PDF]

2.2.2. A Time-Slice–Based Predictive Estimation Routing Algorithm

By utilizing the principle of topological snapshots, time is divided into time slots, as shown in Figure 3, and the following steps are performed:

1. Split time slice: The time during a motion cycle of a satellite is cut into many uniform time slices. The relative positions of the satellites do not change during the time slices.

2. In-orbit algorithm: If both the source node and the destination node are within the orbit, at this time, it is only necessary to calculate a short path according to the idea of ring routing algorithm and pass it along other satellite nodes one by one until the target node.

[figure(s) omitted; refer to PDF]

As shown in the flowchart in Figure 4, if the source node and destination node are in the same orbit, the routing path is planned directly. If they are not in the same orbit, the following steps are taken.

3. Routing design of nodes of different orbits:

Step 1.

The source node needs to find the three pairs of nodes closest to the two orbits where the source node $S$and destination node $D$ are located according to the data in the time slice at this time. All three pairs can be used as transit nodes, so there are three alternative paths. The transit nodes of the orbit where the source node $S$ is located are denoted as $s_1$, $s_2$, and $s_3$, respectively, and the corresponding is that the transit nodes of the orbit where the destination node $D$ is located are denoted as $d_1$, $d_2$, and $d_3$. The reason for choosing three alternate paths here is that it is possible that the message encounters congestion during intraorbital transmission, and by the time it is transmitted to the intended $s_2$, the link between $s_2$ and $d_2$ is no longer the closest link between the two orbits. At this point, the alternative paths can be enabled and adjusted in both directions when three alternative paths are available. It is also stated that in the few specific cases where there are only two alternative paths, the procedure is the same as when there are three alternative paths. Considering that satellites may fail, more alternative paths are beneficial to enhance the robustness of the network.

Step 2.

The source node needs to calculate and select the best from the three alternative paths.

1. $\text{S}⟶\cdots ⟶s_1⟶d_1⟶\cdots ⟶D$

2. $\text{S}⟶\cdots ⟶s_2⟶d_2⟶\cdots ⟶D$

3. $\text{S}⟶\cdots ⟶s_3⟶d_3⟶\cdots ⟶D$

Considering the transmission time of the message between the nodes of the satellite, by the time the message is transmitted between two different orbits, it may not be in the current time slice; the algorithm needs to account for this time and predict the time slice to select the best path: $$\begin{array}{}& \text{S}⟶\cdots ⟶\text{s}⟶d⟶\cdots ⟶D\end{array}$$

Step 3.

Fine adjustment: If the relay node $s$ finds that due to a small deviation in the estimate, it is no longer the two closest satellites between the two orbits. At this time, the relay node $s$ that has received the information will calculate the estimate and choose to send left or right to a satellite near itself.

[figure(s) omitted; refer to PDF]

2.2.3. Flooding Algorithm

For source and destination nodes, traverse all paths. However, some paths that pass through too many forwarding nodes are discarded for the sake of efficiency, because a path that passes through too many forwarding nodes is basically unlikely to be the best path. Compare among them and select the best path [10, 11].

3. Analysis and Results

In this section, the algorithms are analyzed at two levels. This includes analyzing the complexity of each algorithm and the actual simulation performance of each algorithm [12].

3.1. Complexity Analysis

In this portion, we will discuss the computational complexity of the algorithm. This is discussed in two parts; one is the comparison of the amount of information that needs to be stored in the satellite itself, and the other is the comparison of the amount of computation involved in implementing the algorithm [13].

3.1.1. Node Storage Information Analysis

This section analyzes the basic information that nodes need to store for route calculation under different algorithms. Note that the amount of information is quantified here. For example, if a node stores information about its location and distance from another node, that is a piece of information. Suppose there are $N$ satellite nodes per orbit and $M$ orbits, and time is cut into $K$ time slices in one period. The amount of information is denoted by $S$.

3.1.1.1. Fixed Gate Node Routing Algorithm

For fixed node routing algorithm, it is divided into two cases: whether it is a gateway node or not.

Not gateway node:

Nodes only need to store information about the relative position of each node in the same orbit and which are gateway nodes. $$\begin{array}{}\text{(1)}& S_{\text{fixed}\_\text{normal}}=N·N-1+p\end{array}$$

In this case, $p$ means the number of gateway nodes in the orbit, so that the source node knows where to send the information.

Gateway node: $$\begin{array}{}\text{(2)}& S_{\text{fixed}\_\text{gateway}}=N·N-1+pq+p\end{array}$$

In addition to the information that ordinary nodes need to store, gateway nodes also need to store additional information ($q$) with other orbit’s gateway nodes.

3.1.1.2. A Time-Slice–Based Predictive Estimation Routing Algorithm

$$\begin{array}{c}\text{(3)}& S_{\text{time}\_\text{slice}\text{based}}=N·M-1·K+N-1+NM·K^{\gamma }\gamma >1\end{array}$$

The first item here is the location information of this node and the nodes in other orbits, recording $K$ time slices. The second term is the position information with other nodes in this orbit; because this is relatively stable, there is no need to record $K$ time slices. The third item is the queued processing delay of each node in the system, which usually needs to record more than one cycle of data.

3.1.1.3. Flooding Algorithm

In this paper, we only consider the case where the algorithm is computed and learned on individual satellites. For a node, this paper has to think about the global situation. The information to be stored includes the location information of each node and the queuing delay information within each node. $$\begin{array}{c}\text{(4)}& S_{\text{flooding}}=NM-1·NM·K^{\alpha }+NM-1·K^{\beta }\alpha >1,\beta >\alpha \end{array}$$

To summarize the above analysis, in the algorithm proposed in this paper, the time within a cycle is cut into $K$ time slices, but in the algorithm to complete the flooding, the data needed for each time slot will be more, which is generally said to be divided into smaller time slices, the need for massive data, far more than the amount of $K$ time slices, so this paper uses exponential times. In the above formula, the former term is the amount of information to store the relative position information between this node and other nodes, and the latter term is the processing delay within the storage node. Because the relative position and distance of the satellite change periodically, while the processing delay within the node is not strictly in accordance with the periodic change, more data is needed to build the model, so here $\beta >\alpha$. Therefore, from this metric, the highest complexity is flooding algorithm, followed by the algorithm proposed in this paper, and the lowest is fixed gate node routing algorithm.

3.1.2. Algorithm Complexity Analysis

This section analyzes the amount of computation involved in implementing the above three algorithms. When analyzing the complexity of the amount of computation, it will be divided into two cases whether the source and destination nodes are in the same orbit or not [14].

3.1.2.1. Fixed Gate Node Routing Algorithm

Same orbit: $$\begin{array}{}\text{(5)}& C_{\text{fixed}\_\text{same}}=NN-1\end{array}$$

According to the Dijkstra algorithm, $N-1$ operations are to be performed on $N$ nodes.

Different orbit: $$\begin{array}{}\text{(6)}& C_{\text{fixed}\_\text{different}}=p·NN-1+p^2+NN-1\end{array}$$

The first item is that the source node needs to send a message to $p$ gateway nodes at the same time and perform the routing computation of the Dijkstra algorithm. The second term is the computation of the attempted docking between the $p$ gateway nodes that received the message and the $p$ nodes in the other orbit. The third item is the routing process from the gateway node that received the message to the destination node in the other orbit.

3.1.2.2. A Time-Slice–Based Predictive Estimation Routing Algorithm

Same orbit: $$\begin{array}{}& {\text{C}}_{\text{time}\_\text{slice}\text{based}\_\text{same}}=\text{N}-1\end{array}$$

In-orbit routing is calculated using ring routing algorithm.

Different orbit: $$\begin{array}{}\text{(7)}& C_{\text{time}\_\text{slice}\text{based}\_\text{different}}=N^2+3·\frac{N-1}{2}+1·\frac{N·M-1}{NM-1}+\frac{N-1}{NM-1}·\delta \end{array}$$

Here, $3·N-1/2+1$ is the amount of computation needed to calculate to the three target nodes, and $N^2$ is traversing the two orbits to find the three pairs of satellites that are relatively close to each other.

3.1.2.3. Flooding Algorithm

Same orbit: $$\begin{array}{}\text{(8)}& C_{\text{flooding}\_\text{same}}=FN=\sum _{m=0}^{N-2}\frac{N-2!}{N-2-m!}\end{array}$$

Different orbit: $$\begin{array}{}\text{(9)}& C_{\text{flooding}\_\text{different}}=FN=\sum _{m=0}^{N-2}\frac{N-1!}{N-2-m!}·{N-1}^2·\sum _{m=0}^{N-2}\frac{N-2!}{N-2-m!}\end{array}$$

The flooding algorithm is to traverse each path and choose the best one, but the actual experiments will only traverse paths that pass through a relatively small number of nodes, so here is only a mathematical demonstration of the theory.

3.2. Algorithm Analysis

This section analyzes the possible performance of each algorithm in practical applications from a mathematical point of view, mainly in the following indicators [15, 16]:

1. Number of junction points

Here, it refers to the number of satellite nodes that the message passes through during the propagation process.

2. Total path length

The total path length refers to the total distance traveled in the process of information dissemination.

3. Maximum step length

Because the information transmission process may be forwarded by other satellites, this refers to the maximum sending distance of a single forwarding.

4. Total path latency

The total path latency refers to the total message transfer time spent.

In order to generalize the study in this paper, it is assumed here that the delay within the node conforms to normal distribution $\mu ,{\sigma }^2$. In the following analysis, whether the source node and the destination node are in the same orbit will be discussed. The following are theoretical estimates.

3.2.1. Fixed Gate Node Routing Algorithm

1. Number of junction points:

Same orbit: $$\begin{array}{}& \frac{2\pi }{\alpha }·\frac{1}{4}\end{array}$$

Different orbit: $$\begin{array}{}& \frac{2\pi }{\alpha }·\frac{1}{4}·2+1\end{array}$$

$\alpha$ represents the maximum angle formed by the line between the two neighboring satellites and the Earth’s center to ensure that the two satellites can communicate directly.

2. Total path length:

Same orbit: $$\begin{array}{}& \frac{2\pi }{\alpha }·\frac{1}{4}·2·\sin \frac{4\pi }{\alpha }·R\end{array}$$

Different orbit: $$\begin{array}{}& \le \frac{2\pi }{\alpha }·\frac{1}{4}·2·\sin \frac{4\pi }{\alpha }·R·2+2·\frac{\pi \text{R}}{5}·\sin \frac{\theta }{2}\end{array}$$

$R$ is the Earth’s radius and $\theta$ is the angle between two orbits.

3. Maximum step length:

There are two possibilities. $$\begin{array}{c}& 2·\frac{\pi \text{R}}{5}·\sin \frac{\theta }{2}2·\sin \frac{4\pi }{\alpha }·R\end{array}$$

4. Total path latency:

Same orbit: $$\begin{array}{}& \frac{2\pi }{\alpha }·\frac{1}{4}·\mu +\frac{2\pi /\alpha ·1/4·2·\sin 4\pi /\alpha ·R}{c}\end{array}$$

Different orbit: $$\begin{array}{}\text{(10)}& \frac{2\pi }{\alpha }·\frac{1}{4}·2+1·\mu +\frac{2\pi /\alpha ·1/4·2·\sin 4\pi /\alpha ·R·2+2·\pi \text{R}/5·\text{sin}\mathrm{\theta /}/2}{c}\end{array}$$

$c$ is the speed of the light.

3.2.2. A Time-Slice–Based Predictive Estimation Routing Algorithm

1. Number of junction points:

Same orbit: $$\begin{array}{}& \frac{N-1}{4}\end{array}$$

Different orbit: $$\begin{array}{}& \frac{N-1}{2}+1\end{array}$$

2. Total path length:

Same orbit: $$\begin{array}{}& \frac{2\pi \text{R}}{N}·\frac{N-1}{4}\end{array}$$

Different orbit: $$\begin{array}{}& \le \frac{2\pi R}{N}·\frac{N-1}{4}+2·\frac{\pi \text{R}}{N}·\sin \frac{\theta }{2}\end{array}$$

3. Maximum step length:

$$\begin{array}{}& \frac{2\pi R}{N}+\partial \end{array}$$

$\partial$ is small amount of bias.

4. Total path latency:

Same orbit: $$\begin{array}{}& \frac{N-1}{4}·\mu +\frac{2\pi R/N·N-1/4}{c}\end{array}$$

Different orbit: $$\begin{array}{}\text{(11)}& \frac{N-1}{2}+1·\mu +\frac{2\pi R/N·N-1/4+2·\pi R/N·\text{sin}\mathrm{\theta /}/2}{c}\end{array}$$

3.2.3. Flooding Algorithm

Objectively speaking, since the flooding algorithm traverses all possible paths, the above four indexes must be optimal. Because it is extremely difficult to analyze these metrics of the flooding algorithm specifically from a mathematical point of view and is not the focus of this paper, it will not be analyzed too much here [17].

3.3. Simulation and Analysis

In the simulation, the four indicators mentioned in Section 3.2 are simulated. In this experiment simulation, there are a total of 60 satellites, distributed in four orbits; each orbit has 15 satellites. The four orbits are named as $A$, $B$, $C$, and $D$. The parameter information of the four orbits is shown in Table 1.

Table 1

Orbital parameters.

Orbit	Inclination	Eccentricity	Altitude	Cycle
$$A$$	$$0^{°}$$	0	1675 km	2 h
$$B$$	$${45}^{°}$$	0	1675 km	2 h
$$C$$	$${90}^{°}$$	0	1675 km	2 h
$$D$$	$${135}^{°}$$	0	1675 km	2 h

The experiments conducted covered various nodes communicating with each other for a total of 3600 communications.

Note that under the simulation of the fixed node routing algorithm, we set the number of gateway nodes per orbit to three. In the subsequent simulation experiments, Algorithm 1 represents the fixed node routing algorithm and sets the number of gateway nodes per orbit to three, Algorithm 2 represents a time-slice-based predictive estimation routing algorithm proposed in this paper, and Algorithm 3 represents the flooding algorithm.

The first is the simulation of the number of passing nodes.

As can be seen from Figure 5, Algorithm 3 passes through the least number of nodes, while Algorithm 2 passes through the most. From the simulation results, the algorithm proposed in this paper is required to go through more nodes to forward, and more forwarding nodes are used in order to reduce the step length of a single step. Then, the next index is average simulated path length.

[figure(s) omitted; refer to PDF]

From the simulation (Figure 6), the routing path calculated by Algorithm 2 is the longest and significantly longer than the other two algorithms, while Algorithm 1 and Algorithm 3 are more similar, with Algorithm 1 being a bit longer. It shows that the algorithm proposed in this paper has a disadvantage in the metric of routing path length because the algorithm has to go through a lot of forwarding nodes and the algorithm within the orbit uses a ring routing algorithm, so it increases the length of the routing path. Algorithm 1 uses the Dijkstra algorithm within the orbit, which is very beneficial in reducing the total routing path length. Algorithm 3 would have traversed almost all the paths, and the resulting total path length is surely optimal.

[figure(s) omitted; refer to PDF]

Finally, the simulation is performed for the single-step maximum step length and the total delay.

As can be seen from Figures 7 and 8, compared with the other two algorithms in terms of main indicators, the algorithm proposed in this paper has an excellent performance in the maximum step length of a single step and a mediocre performance in other aspects. This means that the algorithm proposed in this paper can indeed largely reduce the maximum step length of a single step of the planned routing path and reduce the requirements for hardware devices such as transmitter–receiver. However, the other three indicators do not perform as well as the other two algorithms. The algorithm proposed in this paper is suitable for constellation projects with small information transmission load and low requirements for delay but sensitive to economy.

[figure(s) omitted; refer to PDF]

3.4. Hardware Cost Analysis

The free-space path loss equation is studied here first; the equation for free-space path loss describes the amount of power loss when a signal propagates in free space (vacuum) at a specific frequency. $$\begin{array}{}\text{(12)}& \text{FSPL}\text{dB}=20{\log }_{10}d+20{\log }_{10}f+20{\log }_{10}\frac{4\pi }{c}\end{array}$$

The above equation can be simplified to $$\begin{array}{}\text{(13)}& \text{FSPL}\text{dB}=20{\log }_{10}d+20{\log }_{10}f-147.55\end{array}$$

Here, $d$ is the propagation distance in meters. $f$ is the transmission frequency in hertz. $c$ is the speed of light.

Since FSPL is the ratio (in decibel (dB)), we can use it to calculate the relationship between the transmitted power and the received power. If we know the satellite’s transmit power ($P_t$) in watts, we can calculate the expected receive power ($P_r$) by using the following equation. $$\begin{array}{}\text{(14)}& P_r=P_t·{10}^{-\text{FSPL}/10}\end{array}$$

If the propagation distance ($d$) is increased, FSPL will increase, causing $P_r$ to decrease. In order to keep $P_r$ constant, $P_t$ must increase to compensate for the higher FSPL. If the distance is doubled, the FSPL increases by an amount equal to about 6 dB, which means that the transmit power needs to be increased by a factor of 4 in order to maintain the same receive power.

This formula illustrates that path loss is expressed in dB, which increases proportionally to the logarithm of the distance. The loss of signal power is proportional to the square of the propagation distance.

The increase in transmit power required with increasing distance also implies higher energy consumption and requires more expensive components such as transmit antennas and power amplifiers, which take up more space and weight. Therefore, reducing the transmitting distance in a single step has great significance in reducing the hardware cost.

4. Further Optimization for Algorithm

Although the above simulations show that the algorithm proposed in this paper has a large advantage in key metrics, it is still explored in this section to improve the algorithm and increase the balance of the algorithm. There are two optimization directions. One direction is to partially sacrifice the maximum single-step length and change the in-orbit algorithm from the original ring routing algorithm to the Dijkstra algorithm. Another direction is to further simplify the algorithm and introduce notification mechanism [18, 19].

4.1. In-Orbit Algorithm Optimization

In the algorithm proposed in the previous part of this paper, the routing algorithm inside the orbit is a ring routing algorithm, where information is relayed by neighboring nodes in pursuit of the minimum single-step length. The advantages of this algorithm are obvious, but the disadvantages are also obvious, which will increase many transit nodes and the routing path becomes longer. Therefore, this section tries to change the original ring routing algorithm within the orbit to the Dijkstra algorithm to improve the performance in other aspects and improve the algorithmic balance. It is worth emphasizing that in-orbit here does not mean that the source and destination nodes are in the same orbit, but simply means planning routes within an orbit [20].

Therefore, with exactly the same conditions as the other experiments in the previous section, the comparison is between the algorithm before optimization and the algorithm after this optimization, and the simulation diagram is as follows.

In the following simulation, Algorithm 1 is unoptimized and Algorithm 2 is optimized.

As can be seen from Figure 9, the calculation path of the algorithm is optimized to a large extent after the change, and the single-step length increases slightly. This shows that the optimized algorithm can indeed improve the algorithm performance to a large extent and can be a beneficial supplement in some scenario.

[figure(s) omitted; refer to PDF]

4.2. Simplification of Algorithm Complexity

Then, we try to simplify the algorithm further by introducing a notification mechanism. In the model presented in this paper, all satellite nodes are in motion from time to time. Moreover, this paper introduces the concept of time slice. For two orbits, in some adjacent time slices, there are two fixed nodes in the two orbits, the distance between them is the closest, and each satellite node has the chance to become the closest node between the two orbits [21].

The flow of improved algorithm is as follows: (1) Each satellite node stores the information when it is the closest node between two orbits, including the docking node, the corresponding time slice, and the distance. (2) Each node has a system that broadcasts its information to the whole network several time slices in advance when it is about to become the closest node between two orbits. (3) When each node receives such information, it will know where to send the information for the next orbital communication.

Next, calculate the length of the time slice for the advance broadcast. There are $N$ satellites in each orbit, and the satellites that need to be broadcast in advance will broadcast in both clockwise and counterclockwise directions to satellites throughout the orbit. There may be at most $\text{N}-1/2+1$ satellites broadcasting passes in one direction (brackets represent rounded numbers). In order to ensure that early broadcasting is reliable, we need to consider the most extreme cases.

The time that elapses from the satellite that sends the broadcast to this last satellite in the system that receives the broadcast: $$\begin{array}{}\text{(15)}& \frac{\sin \pi /N·2R·N-1/2+1}{c}+N-1/2+1·\mu \end{array}$$

The final satellite that receives the broadcast takes the same amount of time to send the message back to the satellite that sent the broadcast at the source.

Then, the total time spent is $$\begin{array}{}\text{(16)}& \frac{\sin \pi /N·4R·N-1/2+1}{c}+N-1/2+1·2\mu \end{array}$$

Considering the need to deal with unforeseen circumstances, there should be an appropriate amount of redundancy, in this case 20%. $$\begin{array}{}\text{(17)}& \frac{\sin \pi /N·4R·N-1/2+1}{c}+N-1/2+1·2\mu ·1.2\end{array}$$

The complexity of the improved algorithm is analyzed next. The amount of information required to store is as follows:

Original: $$\begin{array}{c}& S=N·M-1·K+N-1+NM·K^{\gamma }\gamma >1\end{array}$$

Now: $$\begin{array}{}\text{(18)}& S=N·N-1+\omega \end{array}$$

Here, $N·N-1$ in the equation represents all the satellite node information within this orbit that needs to be stored within the node, and $\omega$ refers to the time slices in which the node is acting as the nearest node of this orbit to other orbits.

Computational complexity:

Original: $$\begin{array}{}& C=N^2+3·\frac{N-1}{2}+1·\frac{N·M-1}{NM-1}+\frac{N-1}{NM-1}·N-1\end{array}$$

Now: $$\begin{array}{}\text{(19)}& C=\frac{N·M-1}{NM-1}·2N-1+\frac{N-1}{NM-1}·N-1\end{array}$$

Obviously, it can be easily seen from the above equation that the complexity of the improved algorithm is greatly reduced compared to the previous one.

Therefore, with exactly the same conditions as the other experiments in the previous section, the comparison is between the algorithm before optimization and the algorithm after this optimization, and the simulation diagram is as follows.

In the following simulation, Algorithm 1 is unoptimized and Algorithm 2 is optimized.

From the simulation (Figure 10), the optimized algorithm performs a little worse in the overall index relative to the previous one, but the gap is very small overall except for the index average simulated path length, which is still very promising for application relative to the significant optimization of the computational complexity. Next is a summary of the pros and cons.

[figure(s) omitted; refer to PDF]

The advantages of this approach are obvious. (1) The storage pressure of each node is less, and only the information of each node in the same orbit needs to be stored, which greatly reduces the storage pressure. (2) When calculating node routing, the calculation amount is greatly reduced, and no more complicated calculation is needed to determine the two closest nodes between two tracks.

The disadvantage is as follows: (1) The accuracy of the algorithm will be slightly decreased, because there is a certain lag. This is because when a node receives a broadcast and sends the signal to the corresponding node according to the information in the broadcast, some nodes may be busy in the middle, leading to a large delay. By the time the signal is sent to the corresponding node, the corresponding node is no longer the nearest node in the two tracks needed. It also increases the burden of link processing, because signals need to be broadcast on the network as a whole, occupying more tape resources.

5. Conclusion

This paper presents a new algorithm for predicting the shortest path step size based on time slice. From a mathematical point of view, this paper analyzes the algorithm, the traversal algorithm which can calculate the optimal path, and the typical fixed node routing algorithm and compares its routing path length, propagation delay, maximum single-step path step size, average number of nodes through the path, and other indexes. The main findings are as follows:

1. Simulation results show that the algorithm proposed in this paper has obvious advantages in the index of maximum single-step path length. This can greatly reduce the requirements of satellite node transmission power and other indicators and reduce the cost of satellite hardware.

2. In the second part of this paper, the algorithm is further optimized. Optimizing the route calculation method on the track can greatly reduce the number of passing nodes and delays, while slightly increasing the step size. The second optimization direction is the introduction of notification mechanism, which greatly reduces the computing power requirements for satellite nodes, and the small number of paths added is almost negligible. The application scenarios of this algorithm are enriched.

3. In general, the algorithm proposed in this paper can effectively reduce the hardware cost of intersatellite nodes, has good adaptability, and can be used as a useful supplement to the existing satellite networking algorithms.

Funding

The authors acknowledge the financial support provided by Micro-Satellite Research Center, Zhejiang University, and National Natural Science of China (62073289 and U21A20443).

Acknowledgments

The authors acknowledge the financial support provided by the National Natural Science of China (62073289 and U21A20443).

Glossary

Nomenclature

$M$the number of orbits

$N$the number of satellite in each orbit

$Q$the time of a complete cycle

$K$the number of time slices

$a$the direct connection distance between two satellite nodes

$b$internal wait delay of a node

$S$the amount of information stored in the node

$p$the number of gateway nodes in each orbit

References

[1] M. Giordani, M. Zorzi, "Non-terrestrial networks in the 6G era: challenges and opportunities," 2019. https://arxiv.org/abs/1912.10226

[2] Z. Zhang, Y. Xiao, Z. Ma, M. Xiao, Z. Ding, X. Lei, G. K. Karagiannidis, P. Fan, "6G wireless networks: vision, requirements, architecture, and key technologies," IEEE Vehicular Technology Magazine, vol. 14 no. 3, pp. 28-41, DOI: 10.1109/MVT.2019.2921208, 2019.

[3] N. Zhao, X. Long, J. Wang, "A multi-constraint optimalrouting algorithm in LEO satellite networks," Wireless networks,DOI: 10.1007/978-3-030-64054-5, 2021.

[4] H. Wang, Research on Routing Strategies for Low-Orbit Satellites Based on Deep Reinforcement Learning, 2020.

[5] R. Wang, M. A. Kishk, M. S. Alouini, "Stochastic geometry-based low latency routing in massive LEO satellite networks," IEEE Transactions on Aerospace and Electronic Systems, vol. 58 no. 5, pp. 3881-3894, DOI: 10.1109/TAES.2022.3199682, 2022.

[6] L. Zhao, C. Wang, K. Zhao, D. Tarchi, S. Wan, N. Kumar, "INTERLINK: a digital twin-assisted storage strategy for satellite-terrestrial networks," IEEE Transactions on Aerospace and Electronic Systems, vol. 58 no. 5, pp. 3746-3759, DOI: 10.1109/TAES.2022.3169130, 2022.

[7] H. S. Chang, B. W. Kim, C. G. Lee, Y. Choi, S. L. Min, H. S. Yang, C. S. Kim, "Topological design and routing for low-earth orbit satellite networks," Proceedings of GLOBECOM '95, pp. 529-535, DOI: 10.1109/GLOCOM.1995.501983, .

[8] N. T. Rao, D. Bhattacharyya, T. Kim, "5G network model analysis by NS2 simulation: an extensive review," Journal of Engineering and Applied Sciences, vol. 14 no. 15, pp. 5160-5166, DOI: 10.36478/jeasci.2019.5160.5166, 2019.

[9] T. Yoshida, Takata, "Uncertainty simulation of wood chipping operation for bioenergy based on queuing theory," Forests, vol. 10 no. 9,DOI: 10.3390/f10090822, 2019.

[10] L. Shuaijun, F. Xu, L. Lixiang, D. Wang, "Development history and performance analysis of the first phase of Starlink constellation," Satellites and Networks, vol. 12 no. 3, pp. 46-49, 2020.

[11] C. Placido, Y. Shen, "SpaceX shows the development of Starlink," Satellites and Networks, vol. 9 no. 5, pp. 38-41, 2020.

[12] Q. Chen, G. Giambene, L. Yang, C. Fan, X. Chen, "Analysis of inter-satellite link paths for LEO mega-constellation networks," IEEE Transactions on Vehicular Technology, vol. 70 no. 3, pp. 2743-2755, DOI: 10.1109/TVT.2021.3058126, 2021.

[13] F. Zhu, Y. Hao, B. Haitong, "Routing Complexity Analysis of Interstellar Algorithms," Application of Electronic Technique, vol. 509 no. 11, pp. 24-28, 2019.

[14] D. Bhattacherjee, A. Singla, "Network topology design at 27, 000 km/hour," Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies, pp. 341-354, DOI: 10.1145/3359989.3365407, .

[15] C. Jiang, X. Zhu, "Reinforcement learning based capacity management in multi-layer satellite networks," IEEE Transactions on Wireless Communications, vol. 19 no. 7, pp. 4685-4699, DOI: 10.1109/TWC.2020.2986114, 2020.

[16] H. Tsuchida, Y. Kawamoto, N. Kato, K. Kaneko, S. Tani, S. Uchida, H. Aruga, "Efficient power control for satellite-borne batteries using Q-learning in low-earth-orbit satellite constellations," IEEE Wireless Communic- ations Letters, vol. 9 no. 6, pp. 809-812, DOI: 10.1109/LWC.2020.2970711, 2020.

[17] I. Leyva-Mayorga, B. Soret, P. Popovski, "Inter-plane inter-satellite connectivity in dense LEO constellations," IEEE Transactions on Wireless Communications, vol. 20 no. 6, pp. 3430-3443, DOI: 10.1109/TWC.2021.3050335, 2021.

[18] B. K. Chen, F. A. Tobagi, "Network topology design to optimize link and switching costs," 2007 IEEE International Conference on Communications, pp. 2450-2456, DOI: 10.1109/ICC.2007.354, .

[19] Z. Han, H. Shaoqing, "Minimum hop routing method in wireless sensor networks based on improved ant colony algorithm," Telecommunication Science, vol. 32 no. 3, pp. 113-117, 2016.

[20] Z. Bin, H. Wei, B. Li, "Calculation and analysis of prediction model based on cascade neural network," Electronic Technology, vol. 50 no. 2, pp. 70-71, 2021.

[21] L. Yingying, Research on satellite network routing algorithm based on SDN, 2020.