# A Space-Interconnection Algorithm for Satellite Constellation Based on Spatial Grid Model
## 4 Discussion  
First, we analyzed the time complexity of the satellite interconnection algorithms proposed in this study. In the traditional inter-satellite visibility analysis algorithm, we assumed that there are \(N\) satellites in the aerospace industry. For each satellite, it is necessary to measure the distance to other satellites to determine whether its angle is within the visible range and whether the elevation is obstructed by the earth and the atmosphere. The time complexity is \(O(N)\), and it increases linearly with the number of satellites. However, when querying in the BigTable based on the grid's visibility, the 3-dimensional space coordinates of the satellite are stored in the database in code format. The idea at the basis of this method is to employ the \"space for time\" concept to convert the high-dimensional floating operations into one-dimensional matching operations by querying the inherent \"visible\" attribute of the grid. The time complexity of the code query is \(O(log~{}N)\). Especially, when the number of satellites increases, the time complexity of algorithm is greatly reduced compared to O(\(N\)). In addition, in the grid network topology model and routing algorithm, we established an association matrix containing the topology information of satellites and ground targets. The size of the matrix is \((M+N)\times(M+N)\), where \(M\) and \(N\) represent the number of satellites and ground targets established, respectively. The matrix is then transformed into the topological matrix of the corresponding cells, and their visibilities are set to be the necessary conditions for communication to reduce the size of the correlation matrix and further reduce the cost of the algorithm and storage.  
According to the analysis of the experiment results, we created an aerospace grid indexing BigTable that verifies the feasibility of gridding satellite trajectory data, the efficiency of inter-satellite visibility analysis, the feasibility of grid network topology, and the high efficiency of path planning. In the inter-satellite visibility analysis, by calculating the visible grid lookup table in advance, we only need to query the visible cells of the grid, which is 23.62 times faster than traditional algorithms. In route planning calculations, path planning is based on visibility analysis, which is 29.74 times faster than traditional algorithms. In particular, after the construction of BigTable is completed, the large increase  
Figure 11: Comparison of route planning.  
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline  & **500** & **1000** & **2000** & **4000** & **6000** & **8000** & **10,000** & **12,000** \\ \hline Grid distance & 0.00005 & 0.0001 & 0.00028 & 0.00056 & 0.00153 & 0.00385 & 0.00835 & 0.0145 \\ Grid step & 0.00011 & 0.00018 & 0.00035 & 0.00051 & 0.00101 & 0.00191 & 0.00289 & 0.00547 \\ Formal distance & 0.0012 & 0.00241 & 0.01205 & 0.02209 & 0.04818 & 0.08937 & 0.23128 & 0.46256 \\ Formal step & 0.00208 & 0.00277 & 0.00554 & 0.01109 & 0.02218 & 0.03913 & 0.07392 & 0.13306 \\ \hline \end{tabular}
\end{table}
Table 5: Routing planning results (ms).  
in the number of satellites should have a much smaller impact on the calculation of the grid algorithm than traditional methods. This \"space-for-time\" method has efficiency advantages in inter-satellite interconnection calculations, and is an efficient satellite interconnection calculation method.  
In addition, it should be noted that in practical applications, the complexity of the connection situation, and other factors such as delay and interference should also be considered. The existing experimental results were completed without considering the input/output (io) overhead of database and other factors, and theoretically improved more. Further study should be combined with a variety of possible influencing factors in practical applications for a more accurate analysis.