Keywords

1 Introduction

1.1 A Subsection Sample

At present, a variety of constellation plans with global coverage have been proposed, aiming to make the Internet more convenient for users all over the world, such as iridium and O3b constellation that are already in orbit, and Starlink constellation plan of SpaceX, oneweb constellation plan, Kuiper constellation plan of Amazon, Hongyun project and Hongyan constellation plan of China, etc. Among them, Starlink plans to launch about 12000 LEO satellites in three phases to achieve global redundant coverage, and use laser inter satellite links to build satellite networks. The blueprint created by Starlink will greatly promote the development process of the space-ground integrated network.

Because the data communication among satellites, near space vehicles, air vehicles and ground terminals are all considered in the space-ground integrated networks, the mobile and data transmission characteristics of space segment and ground segment should be considered in the initial stage of routing design. In the satellite network system with geographic location routing algorithm, the ground terminal is usually equipped with GPS module to realize fast addressing and positioning. At the same time, the system divides the earth surface into multiple geographic units by means of equal interval division of longitude and latitude. When the ground control center finds the geographic unit through the longitude and latitude information of the ground terminal, it guides the satellite network to send the data to the satellite which is currently covering the geographical unit [10]. However, the traditional method of longitude and latitude division results in nonuniform geographical units. For example, the unit area near the equator is far larger than the unit area near the polar region, and large area units need more satellites or spot beams to cover, which increases the complexity of satellite coverage handover.

Compared with the regular icosahedron model, the discrete global grids coordinate calculation based on the regular octahedron model is simpler. The earth surface can be divided into triangular elements with approximately equal area, which are mainly used for efficient earth data processing and visualization. In this paper, the octahedron discrete global grids technology is introduced into the design of the space-ground integrated routing algorithm. Based on the predictability of satellite movement, the satellite-ground coverage time series of each grid is pre-calculated. At the same time, the snapshot routing algorithm for satellite network space segment is integrated to realize the real-time routing addressing function of the space-ground integrated network, to reduce complexity of calculating the satellite earth coverage by the traditional way. In this paper, STK and VC++ 6.0 software are used to realize the level-three subdivision of octahedral for satellite-grid coverage time series in iridium constellation, and relevant numerical analysis is given.

2 Related Works

2.1 Discrete Global Grids

In order to effectively store, extract and analyze the constantly updated global massive data, and fundamentally solve the limitations of the traditional data model, scholars put forward the spherical discrete grid model, which has the characteristics of uniform spatial location distribution, supporting multi-scale transformation, and is very suitable for the route addressing of the space-ground integrated networks. According to the method of grid generation and the shape of grid elements, the discrete global grids model can be divided into three parts: the longitude latitude spherical discrete grid model (short for latlon), the adaptive spherical discrete grid model and the polyhedron spherical discrete grid model [1].

The longitude latitude spherical discrete grid model is the earliest and used most widely. The typical models include VGIS (Virtual GIS) [2] of Georgia Institute of technology, VPE (Virtual Planetary Exploration) [3] of NASA, and the SIMG (Spatial Information Mulit-Grid) technology adapted to grid computing environment of Li Deren in China [4, 5]. The longitude latitude spherical discrete grid model meets people’s use habits and can be simple transformed to other coordinate systems, but there are also some shortcomings, such as the area of grid between high and low latitude is inconsistent, the coordinates of North and south poles are changing and oscillating, the data density of high and low latitude is inconsistent with the coverage area, and it is difficult to establish regional spatial index.

Based on the solid elements on the sphere, the adaptive spherical discrete grid model divides the spherical elements according to some characteristics of the solid elements. Its main theory is the Voronoi diagram with dynamic stability characteristics, and the main schemes are the LOD model of the global digital elevation model data [6], the spatial data management tool vordll [7] of Laval University in Canada, etc. Due to the special shape of the adaptive grid, it has more flexibility than the regular grid, but it is also difficult to achieve recursive segmentation and multi-scale massive data association.

The spherical discrete grid model of regular polyhedron mainly projects the shapes of regular tetrahedron (4 equilateral triangles), regular hexahedron (6 squares), regular octahedron (8 equilateral triangles), regular dodecahedron (12 pentagons) and regular icosahedron (20 equilateral triangles) on the sphere to produce spherical polygons with the same shape. It overcomes the defects of the non-uniformity and the singularity of the two poles of the longitude latitude grid model, and has the characteristics of good stability and approximately uniform division in the global scope. At the same time, it supports the direct positioning of the grid on the global surface and the mutual transformation of the sphere and the geographical coordinates. At present, the octahedron QTM (Quad triangle mesh) [8] and the icosahedron sphere [9] discrete grid models have become effective tools for building a global hierarchical grid model.

2.2 Spatial Network Geographic Information Routing

Geographic information routing algorithm has a long history in the space-ground integrated networks. This kind of algorithm usually divides the ground surface into regions of the same size, and assigns a fixed logical address to each region. Each packet carries the logical address as the source/target address. The satellite node judges the user’s region according to the logical address carried by the packet, and then forwards the packet to the satellite covering the user’s region using the route based on geographical location, and finally forwards it to the user. The actual area division can be different according to the different application scenarios, and the hierarchical structure can also be adopted for area division. Typical satellite network geographic routing algorithms include DGRA algorithm [10], SIPR algorithm [11], etc. However, the scheme proposed mainly uses the way of binding the ground terminal to the access satellite to realize the location management of the terminal. All the binding information will be continuously updated in the ground control center with the satellite moving, resulting in a large amount of data update costs.

To solve this problem, Tsunoda [12] proposed a handover independent mobile management mechanism for IP/LEO satellite network. This mechanism can shield the impact of satellite handover on terminal addressing by storing the geographic location information of the ground terminal, effectively reducing the update cost of binding information. Meanwhile they take the orbit information of satellite into account to solve the confusion problem of the last hop selection of adjacent satellites [13], improving the accuracy of ground terminal addressing. However, although GPS positioning information is used to record the location of the ground terminal, and the ground is divided into multiple cells to determine the coverage area of the satellite, the real-time coverage sequence of the satellite network to the ground unit is not given, so it is difficult to quickly locate the satellite covered by the ground unit. In recent years, although software defined network [17], network function virtualization [18], software defined radio [19] and other new network technologies have been widely introduced into satellite network, but in general, they have not changed the essential law of satellite ground coverage, and optimizing the performance of satellite ground coverage is still very important for improving the networking performance of the above-mentioned new technologies in the space-ground integrated network.

Therefore, this paper intends to introduce the discrete global grids technology into the space-ground integrated networks, and realize the reasonable satellite ground coverage distribution through the uniform and hierarchical spherical division. At the same time, based on the regularity and predictability of the satellite movement, the coverage time series of the satellite to the ground grid can be calculated in advance, to improve the fast addressing ability independent of the satellite-ground handover.

3 Introduction to Discrete Global Grid

3.1 Division of Discrete Global Grid

In order to achieve the uniform coverage for the ground, this paper proposes to use the regular octahedron discrete grid model to divide the earth surface. The vertex of the octahedron coincides with the main position points (including poles) of the earth. Take the original spherical triangle of the octahedron ABC for example, vertex A coincides with the pole, and the other two vertices are located at the equator (Fig. 1).

Fig. 1.
figure 1

Schematic diagram of level 3 (left) and level 6 (right) division of octahedron [1]

Full size image

Literature [1] compared the basic properties of discrete global grids based on octahedron at different levels of subdivision (n = 0–13). It was found that with the increase of subdivision levels, the ratio (the ratio of the maximum to the minimum edge of the spherical triangle with the largest deformation in each level, the ratio of the maximum to the minimum angle, the ratio of the maximum to the minimum perimeter as well as the ratio of the maximum to the minimum sphere triangle area) increases gradually from 1, which represents the uniform division, and then tends to be stable. At last, the ratios keep 1.559394, 2, 1.370207 and 2.105921 respectively. Furthermore, the closer to the vertex of the octahedron, the larger the deformation is, and the farther away from the vertex, the smaller the deformation is. Although the multi-level discrete grid based on the regular octahedron is not a uniform sphere division, it is still superior to the longitude latitude sphere discrete grid model and the adaptive sphere discrete grid model. Therefore, the spherical discrete grid model based on the regular octahedron division is employed in this paper. At the same time, considering the orbit altitude of the experiment satellite constellation, the spherical area is divided by the level n = 2.

3.2 Coding of Discrete Global Grid

In order to accurately represent each discrete grid, a unique code is assigned to each grid. With this code, not only the location of the grid, but also the subdivision level (or resolution) of the grid are reflected, ensuring that any area on the ground can be mapped into a given grid.

Referred to [1, 14], QTM grid can code any grid as follows, that is, q = a0ala2a3…an, where a0 is represented by eight fractions from 0 to 7, and ai (i = 1, 2, 3, …) are represented by four fractions of 0–3. The specific determination method is shown in Figs. 2 and 3. In order to save storage space, binary code can be used for storage in practical application, that is, 3-bit binary code (000-111) is used for a0 level, and 2-bit binary code (00-11) is used for subsequent level. Therefore, the QTM code used is a binary string with uncertain length. For example, the QTM code of level 2 grid ‘a0a0a1’ is mapped to the binary code ‘000 00 01’.

Fig. 2.
figure 2

Coding method of a0

Full size image
Fig. 3.
figure 3

Coding method of ai (i ≠ 0)

Full size image

3.3 Coordinate Calculation of Discrete Global Grid

In order to facilitate the use and intuitive analysis, in most cases, we need to convert the coding of octahedral discrete global grids into longitude and latitude coordinates for positioning and operation. The existing conversion methods mainly include ETP projection method, zot projection method and row/column approximation method. Among them, row/column approximation method [15] recursively approximates the coding according to the row and column of QTM in a certain direction. This method has fast operation speed and good accuracy related to the size of the grid, but has global stability characteristics. Therefore, this paper uses this method to calculate the longitude and latitude coordinates of the discrete grid.

In order to simplify the calculation complexity of satellite ground coverage, this paper intends to perform satellite ground coverage strategy calculation based on the triangular vertex of each grid. Therefore, after completing the discrete global grids division, we need to calculate the longitude and latitude coordinates of each grid vertex. This paper mainly uses the method described in reference [1] to convert QTM code to longitude and latitude, and adds the definition and calculation method of grid vertex. This method transfers by means of triangle unit coordinate system, that is, first convert QTM code to triangle unit coordinate, and then convert from triangle unit coordinate to longitude and latitude. In reverse, we firstly convert longitude and latitude to triangle unit coordinate, and then, the triangle unit coordinate is converted to QTM code.

The coordinate system of the triangle unit vertex is shown in Fig. 4. The data pairs in each unit represent the coordinates of triangle unit. The origin of the coordinate system is (0, 0) unit, the Y axis lies with the leftmost column unit, and the X axis extends along the unit with the same y value. The coordinate of each unit is represented as (y, x). The larger the value of y is, the larger the value range of x is. For example, when y = 1, x can be taken as [0, l, 2]. Any coordinate (y, x) of level n partition satisfies the relation \( \left\{ {\left( {\text{y, x}} \right) \, |{\text{ y}} \in \left[ {0, \, 2{\text{n}} - {\text{l}}} \right],{\text{x}} \in [0, \, 2{\text{y}}],{\text{ n }} > \, 0} \right\} \).

Fig. 4.
figure 4

Coordinate system of the triangular unit vertex

Full size image
  1. (1)

    Transformation from triangle unit coordinates to QTM code

    The process of transforming triangle unit coordinates (y, x) into QTM code is to make \( {\text{m }} = {\text{ l }}\left( {1 \, \le {\text{ m }} \le {\text{ n}}} \right) \), and calculate the QTM code layer by layer from level 1 depth to level n depth. The algorithm is as follows [1]:

    1. (1)

      Judge the relative position of the four parts of the parent unit for the current unit. If \( {\text{y }} < \, 2^{{ ( {\text{n}} - {\text{m)}}}} \), it will be in the 0th sub unit, and the corresponding code of the depth is am = 0 and go to (3);

    2. (2)

      If \( {\text{x }} \le \, 2{\text{y}} - 2^{{({\text{n}} - {\text{m }} + \, 1)}} \), code am = 1 and \( {\text{y}} = {\text{y}} - 2^{{({\text{n}} - {\text{m}})}} \), go to (3); if \( {\text{x }} < \, 2^{{({\text{n}} - {\text{m }} + \, 1)}} \), in 2nd sub unit, code am = 2 and \( {\text{x}} = {\text{x}} - 2{\text{y }} + \, 2^{{({\text{n}} - {\text{m }} + \, 1)}} - \, 1 \), \( {\text{y}} = \, 2^{{({\text{n}} - {\text{m }} + \, 1)}} - {\text{y}} - 1 \), go to (3); otherwise, in 3rd sub unit, code \( {\text{am}} = \, 3,{\text{ x }} = {\text{x}} - 2\left( {{\text{n}} - {\text{m}} + \, 1} \right) \) and \( {\text{y }} = {\text{y}} - 2\left( {\text{n}} - {\text{m}} \right) \), turn to 3;

    3. (3)

      If m > n, the conversion process is terminated and exited; otherwise, m = m + 1, and go to (1) for the next depth calculation.

  2. (2)

    Transformation from triangle unit coordinate to longitude latitude coordinate

    Suppose that the up vertex of grid cell a0 of level 0 is at the north pole (90° north latitude), the longitude and latitude of the left vertex are (0°, 0°), the right vertex is (90°, 0°), and the sub unit A is obtained by level n subdivision. Suppose that the triangle unit coordinates of A are (y, x), and the maximum Y-axis coordinates of level n subdivision are \( 2^{\text{n}} - {\text{l}} \) (starting from 0), so the latitude occupied by each unit is 90/2n. Since there are 2y sub units in the row A lies in, the longitude width took up by each triangle unit is 90/2y.

The vertex coordinate calculation formula of level 0 grid unit a0 is shown in Table 1, where the grid a0a0a0 triangle faces up, and the up vertex is node1, lower left vertex is node2, the lower right vertex is node3, while the grid a0a1a1 triangle faces down, and the up vertex is node1, the upper left point is node2, and the upper right point is node3.

Table 1. Example of grid vertex coordinate calculation in a0 (level 2 division)
Full size table

4 Satellite Ground Coverage Division Optimization and Addressing Procedure

4.1 Greedy Selection Algorithm for Grid-Satellite Coverage Time Series

In order to optimize the performance of satellite-ground coverage division, this paper proposes the greedy selection algorithm for satellite-grid coverage time series in Table 2. The algorithm sets the total coverage time as D, the coverage time set Ci of grid i as 0, and each time selects the satellite with the longest remaining coverage time to all the vertexes of grid i. After selecting this coverage, the coverage time Ci of grid i is extended, and the switching time is set according to the sequence of the adjacent coverage time series. For example, the first selected satellite needs to last until it cannot be covered and then switch to the next selected satellite to reduce the number of handovers. When the coverage time Ci of grid i reaches the total coverage time D or all the coverage has been selected, the selection operation is completed and the algorithm ends.

Table 2. Greedy algorithm for satellite-grid coverage time series selection
Full size table

4.2 End to End Addressing Process Based on Discrete Global Grid

Before sending data, the source and destination terminals need to register with the currently covered satellite. Assumed that each terminal is equipped with a global positioning module and can report its own longitude and latitude position attribute, the satellite network can bind the terminal to the corresponding grid unit code through coordinate system conversion based on the longitude and latitude information. When the access satellite of the source ground terminal obtains the grid code of the destination ground terminal through the ground control center, the access satellite needs to address based on the internal route of the satellite network segment and the satellite-ground coverage route. At the same time, based on the periodicity and predictability of the satellite movement, the end-to-end transmission path including the satellite segment and the satellite ground segment are integrated into consideration, to improve the routing performance and availability.

For example, when the source terminal A needs to send data to the destination terminal B, the source terminal A first reports the terminal identification of the destination terminal to the ground network operation and control center (NOCC) through the current coverage satellite SA, and obtains the corresponding grid unit code QB of the destination terminal by querying the terminal registration database. The data of source terminal A can be real-time addressed and forwarded in satellite network based on the grid code. The route of space segment in satellite network can adopt the snapshot route described in reference [16]. At this time, the route of space segment should consider the snapshot route table switching caused by the inter satellite link connection and the destination satellite change caused by the grid coverage switching, both of which can be based on the precise time synchronization function for the whole network. When the data reaches satellite SB which is covering the grid of the destination terminal, satellite SB selects corresponding transponder and downlink based on the grid code to transmit the data to the destination terminal B.

5 Performance Analysis

5.1 Numerical Analysis of Grid Coverage by Satellites

In this paper, iridium constellation and level 3 normal octahedron discrete global grids model are used for testing. There are no restrictions on the elevation angle and azimuth angle of ground terminal, and no restrictions on the elevation and azimuth angle of satellite downlink coverage. The number of visibility coverage time series comparison between the original one and the greedy algorithm is shown in Fig. 5, where the test time is an orbit period (about 6027 s). In this figure, Y-axis represents the number of satellite coverage time series of each grid in the test time, and X-axis represents the sequence number corresponding to the grid. The triangle code of the grid is defined as (y, x), the sequence number is calculated as follows:

Fig. 5.
figure 5

Comparison of the number of coverages between discrete global grids and longitude latitude division model (6027 s)

Full size image
$$ {\text{SeqNo}} = \sum\limits_{i = 1}^{y - 1} {\left( {2i - 1} \right) + x + 1} $$

It can be seen from Fig. 5 that the average number of original visibility coverage in an orbital period of level 3 subdivision (DGG, which is 23.73) is lower than the longitude latitude grid division model with 10° (latlon10, 34.13), and the longitude latitude grid division model with 12° (latlon12, 31.48). Although the number of greedy selected coverage of DGG (12.19) is larger than latlon10 (11.77) model and smaller than latlon12 (12.36) model, some grid of the latlon12 model near the equator could not be continuously covered by the Iridium system, which will badly affect the satellite-ground communication.

At the same time, we can also see that the closer the polar area is, the more frequent the switching between the grid and the satellite, resulting in a very large number of coverage time series. For example, the average original coverage number in one orbit cycle of grid code a0a0a0a3, a1a0a0a2, a2a0a0a1, a3a0a0a3, a4a0a0a3, a5a0a0a2, a6a0a0a2, a7a0a0a1 (serial number as 4, 67, 130, 196, 260, 323, 387, 450) is about 71.5, which is much higher than that of greedy algorithm.

Finally, the standard deviation of coverage number of DGG model (13.92 and 1.22) is smaller than latlon10 model (21.40 and 1.27) and latlon12 model (19.99 and 1.68). The stabilization of satellite-grid coverage of DGG is better than longitude latitude division model.

5.2 Analysis of Satellite-Grid Coverage Time

The duration of satellite coverage sequence of some grid in a single orbital period (6027 s) is shown in Fig. 6. It can be seen from the figure that the satellite coverage time of the grid has changed in stages, which is related to the changing relative position between the satellite and the earth, and the decrease of the coverage time of the last sequence is due to the end of the test time. At the same time, we can see that DGG model owns much closer curves than latlon model, which is because the average coverage time of DGG model is more stable than latlon model.

Fig. 6.
figure 6

Analysis of satellite coverage time of some units in the case of discrete global grids and division of longitude and latitude (6027 s)

Full size image

6 Concluding Remarks

Aiming at the complex relative motion between the space segment and the ground segment of the satellite-ground integrated network, this paper introduces the discrete global grids technology into the design of the satellite-ground integrated routing algorithm. This method divides the earth surface into triangular grid units of approximate size by level n subdivision, and pre-plan the satellite coverage time series of each grid in advance based on the predictability of satellite movement, and propose the greedy algorithm to reduce the handover numbers between satellites and grids. In this paper, STK software is used to simulate the coverage scene of iridium constellation to the level 3 normal octahedron discrete global grids, and the effectiveness of the algorithm for the grid satellite coverage time series generation and greedy selection is verified.