# Onboard Centralized ISL-Building Planning for LEO Satellite Constellation Networks
## 1 Introduction
### Literature Review
For the entire constellation, each ISL visibility segment's start and end time points may not be aligned with the fixed equal-length time segments. As a result, if the system period is divided into several time segments with the inappropriate length, many available visible time segments are partially or entirely cut off, resulting in decreased network performance. Therefore, choosing an appropriate length for the fixed equal-length time segments is essential. The Manhattan Street Network (MSN) has been used to build ISLs in [17; 18], and the commercial Starlink and Indium net networks prefer the MSN topology [19]. With the MSN, although the locations of satellites and ISLs change over time, the link relationship remains constant; that is, there is no dynamic link establishment and dismantlement. As the link length variation range and relative speed are easier to be managed, MSN is simple and beneficial and can be implemented in an onboard manner. It should be noted that different researchers have proposed different methods for MSN to obtain the fixed satellite pairs; for example, each satellite was connected to its closest neighbor in the same or adjacent plane in [19], while [PERSON] and [PERSON] [17] selected the satellite with the same phase in the adjacent plane. The longest coverage time strategy (LCTS) in [12; 20] has been employed to build ISLs. This method helps to improve the total number of ISLs in the network. It is a non-random method with low computational complexity, and is thus suitable for onboard link-building planning. Meanwhile, the integer linear programming (ILP) model has high computational complexity and is unsuitable for the onboard ISL-building planning. ISL-building planning with heuristic algorithms, such as the ant colony algorithm [21] and the simulated annealing algorithm [15; 22], may require a large number of iterations, and these methods do not easily converge for large-scale networks [10]. Moreover, most of these methods are not deterministic, and the results obtained under the same input conditions may be different, which means that it is difficult to manage the network topology onboard. Therefore, they are not considered to be suitable in onboard ISL-building planning scenarios. [PERSON] et al. [8], [PERSON] et al. [11], [PERSON] et al. [23] have proposed the use of graph matching methods to solve ISL-building planning problem. However, although these methods produce relatively good link terminal utilization and average point-to-point distance, the calculations are non deterministic and relatively complex. Therefore, they are also unsuitable for scenarios such as those where satellite computing and storage resources are extremely limited. [PERSON] et al. [24] provided insights into state-of-the-art artificial intelligence techniques across various layers of the communication link and stated that reinforcement learning techniques have been widely used in the traffic scheduling, resource allocation and network planning. Artificial intelligence will definitely become a very important technical approach to solving satellite network ISL-building planning and routing calculation in the future. However, the deep network learning or reinforcement learning need to deploy GPU (Graphics Processing Unit) or FPGA (Field-Programmable Gate Array) to realize learning and fast updating of parameters. The computational cost is unacceptable for low-cost satellites with only one single-core CPU (Central Processing Unit). During the deployment of network protocols or network algorithms onboard the satellites, two difficulties that need to be solved are dynamicity and lightweight. Among all these ISL-building algorithms, MSN forms a static topology, which does not solve the difficulty of dynamicity. Meanwhile, ILP, heuristic algorithms, graph matching and AI require high computing resources, so these algorithms do not solve the difficulty of lightweight, and they are not suitable for onboard ISL-building planning usage.