## 4 Network Partition Algorithm for the Joint Placement Problem
### Simulated Annealing Partition-Based K-Means Algorithm
```
0:
1:\(\mathbf{G}(\mathcal{V},\mathcal{E})\): the target topology of a certain physical network. 2:\(k\): the target number of satellite gateways. 3:\(\mathcal{W}_{\text{opt}}\): the optimized placement of \(k\) satellite gateways. 4:\(L_{\text{ave}}\): the average network latency between gateways and switches. 5:Select one node randomly from \(\mathcal{U}\) as \(\mathcal{W}_{\text{new}}\) of \(\mathbf{G}\). 6:Generate the initial \(\mathcal{W}_{\text{opt}}\) of \(\mathbf{G}\). 7:while the number of sub-domains is less than \(k\)do
8: Searching for the next target sub-domain to be partitioned, which has the longest shortest path distance from the internal nodes to its centroid. The node that has the longest distance to its centroid is denoted as the next _center_\(w^{*}\). 9:\(\mathcal{W}_{\text{new}}=\mathcal{W}_{\text{new}}\cup\{w^{*}\}\). 10: Generate the updated \(\mathcal{W}_{\text{opt}}\) by updating the _centroid_ of each sub-domain. 11:endwhile
12:Compute \(L_{\text{ave}}\) according to \(\mathcal{W}_{\text{opt}}\). 13:return\(\mathcal{W}_{\text{opt}}\), \(L_{\text{ave}}\)
```  
**Algorithm 1** Partition-based K-Means algorithm (PKM). Similar to GPP, the Optimal Enumeration Algorithm for the Joint placement problem (OEAJ) is the most intuitive method for obtaining an optimal solution. The authors in [32] proved the effectiveness of SAA in CPP, which is a probabilistic technique for approximating the global optimum of a given function. Here, we propose the Simulated Annealing Partition-based K-Means algorithm (SAPKM) as an efficient method to deal with the joint placement problem. The details of SAPKM are described in Algorithm 2. Note that the gateway placement has an impact on both network latency and reliability, while the controller placement only affects the network reliability. Therefore, determining the locations of controllers in each sub-domain while fixing the gateways is preferable than determining the locations of the gateways while fixing controllers in the network. In other words, we should first deploy gateways, then consider the deployment for controllers. As shown in Algorithm 2, the first step is to select two initial sets, \(\mathcal{W}_{\text{opt}}\) and \(\mathcal{C}_{\text{opt}}\), which consist of the centroids of the sub-domains separated by the occupied nodes. Then, the network reliability \(R_{\text{max}}\) is calculated. At every iteration of the while-loop, new neighbor solutions, \(\mathcal{W}_{\text{new}}\) and \(\mathcal{C}_{\text{new}}\), are generated with the updated network reliability \(R_{\text{new}}\) obtained. Obviously, the new solution will be accepted if the updated solution's reliability is larger when satisfying the latency constraints. Besides, the new solution with worse reliability will also be accepted with the acceptance probability \(P(\Delta)=e^{-\frac{\Delta}{T}}\), where \(\Delta=R_{\text{new}}-R_{\text{max}}\) and \(T\) denotes the current temperature. ```
0:\(\mathbf{G}(\mathcal{V},\mathcal{E})\): the target topology of a certain physical network. \(k\): the target number of satellite gateways. \(m\): the target number of SDN controllers. \(L_{\text{cst}}\): the network latency constraint. 0:\(\mathcal{W}_{\text{opt}}\): the optimized placement of \(k\) satellite gateways. \(\mathcal{C}_{\text{opt}}\): the optimized placement of \(m\) SDN controllers. \(L_{\text{ave}}\): the average network latency between gateways and switches. \(R_{\text{max}}\): maximum path reliability of the network. 1:Initialize \(T=T_{0},T_{\text{final}},\alpha\). 2: Partition the topology into \(k\) sub-domains, and obtain the \(k-\)_centroids_ set \(\mathcal{W}_{\text{ctd}}\). 3: Partition the topology into \(m\) sub-domains, and obtain the \(m-\)_centroids_ set \(\mathcal{C}_{\text{ctd}}\), where \(\mathcal{W}_{\text{ctd}}\cap\mathcal{C}_{\text{ctd}}=\varnothing\). 4:Compute the average reliability \(R_{\text{max}}\). 5:while\(T>T_{\text{final}}\)do
6: Generate a new gateway set \(\mathcal{W}_{\text{new}}\). 7: Compute the average network latency \(L_{\text{ave}}\).