# Onboard Centralized ISL-Building Planning for LEO Satellite Constellation Networks
## 4 Link-Building Planning
### Modeling  
In the preceding subsections, we clearly described how to generate the link visibility three-dimensional Boolean matrix and the network ISL-building planning constraints. Based on these constraints, in this subsection, we model the link-building planning problem. The planned topology should have the characteristics of low link switching frequency, high topology stability, low average delay, and low maximum delay. To achieve these optimization goals, the problem is modeled as shown in (26):  
\[\min_{T}\left(\sum_{k}^{K}(\lambda p_{k}+\eta q_{k}+\mu h_{k,\text{max}}+\sigma h _{k,\text{mean}})\right), \tag{26}\]  
where \(\lambda\) is the weight of the number of link-switches \(p_{k}\), compared with the previous time segment; \(\eta\) is the weight of the parameter that indicating whether there is a topology change \(q_{k}\), compared with the previous time segment (we define that the topology is changed when at least a single ISL changes); \(\mu\) is the weight of the maximum end-to-end delay \(h_{k,\text{max}}\); \(\sigma\) is the weight of the average end-to-end delay \(h_{k,\text{mean}}\); and \(\lambda,\eta,\mu\) and \(\sigma\) are determined based on the usage requirements of different constellations. If one constellation has strong demand for low delay, \(\mu\) and \(\sigma\) should be set to large numbers; meanwhile, if a stable topology is important for the constellation, the weights \(\lambda\) and \(\eta\) should be large. These weights remain same among the periods.  
The smaller the number of link switches \(p_{k}\) and topology changes \(q_{k}\), the higher the topology stability.  
Satellite networks are not only used for ground communications, but also for efficient collaboration among satellites, especially for remote sensing satellite constellations. In some use-cases, each ISL in the constellation is used and plays an important role. Therefore, the link-switching number and ISL duration can be considered as important performance indicators to characterize the network topology.  
The maximum end-to-end delay \(h_{k,\max}\) can be further expressed as  
\[h_{k,\max}=\max_{i,j}\Bigl{\{}h_{i,j,k}\Bigr{\}}, \tag{27}\]  
where \(h_{i,j,k}\) represents the delay from node \(i\) to node \(j\) in the \(k\)th time segment. The average end-to-end delay \(h_{k,\text{mean}}\) can be expressed as  
\[h_{k,\text{mean}}=\frac{\sum_{i}^{N}\sum_{j}^{N}h_{i,j,k}}{N\times N}. \tag{28}\]  
In this study, the end-to-end delay includes the table-lookup delays of all forwarding nodes and ISL latency of wireless signal propagation on the routing path. For the end-to-end delay, we adopt the hop-count metric [14; 31; 32].  
Equation (26) falls into the category of ILP that is NP-hard and, so, the time complexity to find the optimal solution for such a multi-constrained integer linear programming problem is very high [8; 10]. The topology \(T\) is a three-dimensional matrix; thus, the time complexity to solve this problem is \(O(2^{N\times N\times K})\), which is unacceptable in the context of limited onboard computing resources. When \(N=32\) and \(K=32\), this problem may take more than years, even when using a supercomputer. As a result, an algorithm with lower time complexity is required to realize optimal link-building planning without compromising the performance.