# Energy-Efficient Controller Placement in Software-Defined Satellite-Terrestrial Integrated Network
## 4 Heuristic Placement Algorithm  
The most intuitive way to solve the EECP problem is to enumerate all the possible controller placement schemes and select the best among them as the final result. However, due to its high time complexity, this method is not suitable for such large-scale STINs. In this paper, we focus on a heuristic-based algorithm to solve the EECP problem proposed in Section 3.2. The SA [40] is regarded as a heuristic approach based on Monte Carlo, which searches for the global optimal solution for the decrease in temperature. The proposed modified simulated annealing placement (MSAP) algorithm introduces the greedy method into the SA algorithm to obtain the optimal controller placement with minimum energy consumption. The greedy initial (GI) algorithm is used to obtain the initial set of controller placements for the MSAP algorithm. The details of the GI algorithm are shown in Algorithm 1. The input consists of the network topology graph \(G(V,E)\) and preset controllers \(k\) deployed on STIN. We initialize the set of controllers (line 1) and then calculate the minimum energy consumption by Equation (9) between any two nodes (line 2). The energy consumption is stored in the matrix. The initial placement solution is obtained by iterating \(k\) times (line 3). In each iteration of the for-loop, we choose a new potential node as a controller from the candidate controllers and add it to the list of controllers (line 5). We need to calculate the energy consumption using Equation (9) under the current controller deployment (line 6) and record the minimum value (line 8). Once all the candidate nodes have been traversed (line 9), we find the placement scheme with the minimum energy consumption (line 10). The set of controllers can be available initially (line 12). ```
0:\(G=(V,E),k\)
0:\(\mathbb{C}_{initial}\)-the initial controller placement
1:Initialize:\(\mathbb{C}_{initial}=\emptyset\), \(canlist=V\)
2:Computing Equation (9) to calculate the energy consumption of \(cur\_\mathbb{C}_{initial}\)
3:for\(i=1\) to \(k\)do
4:for\(candidate\in canlist\)do
5:\(cur\_\mathbb{C}_{initial}=\mathbb{C}_{initial}+\{candidate\}\)
6:Computing Equation (9) to calculate the energy consumption of \(cur\_\mathbb{C}_{initial}\)
7:endfor
8:Record candidate when the energy consumption of \(cur\_\mathbb{C}_{initial}\) is minimum
9:\(canlist=canlist-\{candidate\}\)
10:\(\mathbb{C}_{initial}=\mathbb{C}_{initial}+\{candidate\}\)
11:endfor
12:return\(\mathbb{C}_{initial}\)
```  
**Algorithm 1** Greedy Initial Algorithm (GI). The details of the MSAP algorithm are described in Algorithm 2, in which the input is the same as Algorithm 1. We first initialize the parameters, including the initial temperature \(T_{0}\), the final temperature \(T_{final}\), and the annealing coefficient \(\alpha\) (line 1). The output of Algorithm 1 is the initial state of the set of controllers (line 2), and the energy consumption is calculated (line 3). In each while-loop, the temperature decreases until the system reaches a balance point (line 4). We find the placement solution with the minimum energy consumption in all the new neighbor solutions at this stage (line 5). The set of controllers and energy consumption will be updated if the new solution achieves lower energy consumption (line 6 to line 9). In order to avoid falling into the local optimal, the probability of the current worse solution \(P(\Delta)=e^{-\frac{\alpha}{T}}>\xi\) is accepted, where \(\Delta=P_{new}-P_{min}\) and \(\xi\) belong to \((0,1)\) (line 10 to line 14). When the temperature decreases until the solid reaches its stable state, the while-loop ends (line 16). In this way, we obtain the set of controllers and energy consumption (line 18). The computational complexity of the MSAP algorithm is discussed as follows. The time complexity of the minimum energy consumption between any two nodes is \(O\Big{(}\left|V\right|^{3}\Big{)}\). Thus, the running time of the initial set of controllers is \(O\Big{(}k^{2}\cdot\left|V\right|^{3}\Big{)}\).