## 4 Network Partition Algorithm for the Joint Placement Problem
### Simulated Annealing Partition-Based K-Means Algorithm  
By incorporating the network partition scheme, two partition-based algorithms are proposed to address the gateway placement problem and joint placement problem in this subsection, respectively. The core of the network partition is to separate the integrated networks into multiple sub-domains by using appropriate methods. In the standard K-means algorithm, the initial nodes are randomly selected, and the network partition varies from each iteration. Meanwhile, the main idea of SAA is to iterate a new neighbor solution every execution to optimize the objective function continuously, with a random initialization. There are two kinds of nodes in the ground segment of the network topology, i.e., satellite gateways and SDN controllers. In order to obtain available joint placement solutions with the maximized network reliability under latency constraints, we should partition the network in terms of the gateways and the controllers, respectively, while previous works were only concerned with the network partition in terms of the controllers. In other words, not only the sub-domains for gateways and controllers, but also the purposes of the partitions were different. The partition results in terms of the gateways were \(k\) sub-domains with all available nodes, while those for the controllers were \(m\) sub-domains with all the nodes except the ones occupied by the gateways. The purpose of the gateway placement was the minimization of network latency, while the purpose of the controller placement in the second phase was the maximization of network reliability. For solving the satellite gateway placement problem, a simple solution is to enumerate all possible combinations of \(k\) satellite gateways of \(n\) nodes in \(\mathcal{U}\) and then choose an optimal solution that achieves the minimum average network latency. However, due to its exponential computational complexity, this Optimal Enumeration Algorithm (OEA) has to run for a very long time, especially when the number of nodes in a certain topology is large. Thus, enlightened by the idea of the clustering-based network partition algorithm in [23], we reconsidered the placement problem and proposed the Partition-based K-Means algorithm (PKM) to address GPP, which is summarized in Algorithm 1. The main idea of PKM is to divide the given topology into a certain number of sub-domains by iteratively partitioning the topology and updating the centroids of them. \begin{table}
\begin{tabular}{l l} \hline \hline
**Notation** & **Definition** \\ \hline \(\mathbf{G}(\mathcal{V},\mathcal{E})\) & a physical network with node set \(\mathcal{V}\) and link set \(\mathcal{E}\) \\ \(\mathcal{V}\) & \(\mathcal{V}=\mathcal{U}\cup\{s\}\) \\ \(\mathcal{U}\) & the set of terrestrial switch nodes \\ \(\mathcal{W}\) & the set of satellite gateways \\ \(\mathcal{C}\) & the set of SDN controllers \\ \(s\) & the satellite node \\ \(w\) & a satellite gateway in \(\mathcal{W}\) \\ \(c\) & an SDN controller in \(\mathcal{C}\) \\ \(u\) & a switch node in \(\mathcal{U}\) \\ \(k\) & the number of satellite gateways \\ \(m\) & the number of SDN controllers \\ \(n\) & the number of switch nodes \\ \(P_{u}\) & failure probability of terrestrial nodes \\ \(P_{e}\) & failure probability of terrestrial links \\ \(P_{e_{m}}\) & failure probability of the satellite link from \(s\) to \(w\) \\ \(I_{uv}^{s}\) & propagation latency from \(u\) to \(s\) via \(w\) \\ \(L_{uv}\) & propagation latency from \(u\) to \(w\) \\ \(L_{sw}\) & propagation latency from \(w\) to \(s\) \\ \(L_{\text{cost}}\) & propagation latency constraint: maximum latency the terrestrial networks can tolerate \\ \(L_{uc}\) & propagation latency from \(u\) to \(c\) \\ \(R_{uc}\) & reliability of the shortest path from \(u\) to \(c\) \\ \(R_{\text{inv}}^{s}\) & reliability of \(s\) to \(c\) via \(w\) with the shortest terrestrial path \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Notations and definitions.