# A Space-Interconnection Algorithm for Satellite Constellation Based on Spatial Grid Model
## 1 Introduction
The biggest challenge in this process is that the satellites move very quickly, and their network topology (the topological structure of network which may be depicted physically or logically) is much more complex compared to the topologies of mid-orbit and high-orbit satellites [18]. In addition, the fast movement between the satellites will cause a Doppler frequency shift, which considerably affects communication quality. This is one reason for the importance of building a high-quality \"space interconnection link\" [19; 20]. Therefore, choosing the appropriate routing path has become the key to effective data transmission from the satellite to the ground. Summarizing the existing research work, satellite routing algorithms can be divided into a centralized routing algorithm (CRA) and distributed routing algorithm (DRA) according to routing decisions [21; 22; 23]. In CRA, the satellite network control center periodically collects \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Plan of RS** & **Number of** & **Spatial** & **Time** & **Satellite Payload** & **Main Technical Characteristics** \\
**Satellite** & **Satellite** & **Resolution** & **Resolution** & **Satellite Payload** & **Main Technical Characteristics** \\ \hline Planet-Dove & 140\(\pm\) & 3\(\cdot\)5 m & / & Multi-spectral & 3D observation, global coverage \\ SkySat & 24 (14) & 0\(\cdot\)7\(\cdot\)1 m & 6\(\cdot\)8 h & Video/Multi-spectral & The first sub-meter optical satellite \\ BlackSky & 60 & 1 m & 10\(\cdot\)60 min & Video/Multi-spectral & Multi-orbit constellation \\ EarthNow & 500 & Unknown & / & Unknown & Provide images and videos anywhere on the earth \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Plans of Remote Sensing Satellite Constellations [7; 9; 12]. the status of each link, calculates and plans the routing path, and sends the results to the nodes in the network topology model [24]. By dividing the time between status collection events into several intervals, the topology within each time interval is considered to be static, and the stored routing table and the path planning algorithm, such as the Dijkstra algorithm, are then used for route planning [25]. However, routing algorithms based on the virtual topology algorithm will use considerable storage resources to contain the topology, and when the satellite node fails, the algorithm requires a large amount of calculation and thus has poor adaptability. DRA is a connectionless routing algorithm that does not consider global nodes, and it reduces the need for large on-board storage. The main steps of DRA include: (1) dividing the earth surface into several areas, such as spatial grids, (2) constructing a virtual network node at the center of each area; and (3) selecting the next step of the node by calculating the neighboring spatial area [23]. This algorithm requires nodes to have high processing ability, but it may not be able to obtain the best path [26]. Currently, low-orbit satellites that do not build inter-satellite links have become a new source for real-time observation and communication with the ground station [4; 27]. For low-orbit satellite constellations that do not have inter-satellite links, there is an urgent need to optimize more efficient inter-satellite calculation methods [4; 21]. The real-time calculation of the relative position between satellites is therefore required both in the satellite visibility and path planning algorithms, especially in large constellation networks, such as Star Link and OneWeb (including hundreds or even thousands of plans). It is necessary to develop a more efficient satellite inter-communication method for the real-time computing needs of large constellations. The grid-code-calculating method based on the spatial grid model is an efficient position calculation system that extends the range of the global spatial grid to the aerospace region [28; 29; 30].