# Continuous Space Wireless Communication Tower Placement by Hybrid Simulated Annealing
## 4 Hybrid Simulated Annealing Algorithm
### Local Optimization
#### 4.6.2 Design of the Local Optimization Algorithm  
The basic ideas behind it are as follows: first, it searches for uncovered users that are close to the location of a wireless communication tower currently found by the SA; then, it relocates the wireless communication tower so that the wireless communication tower can cover more uncovered users, if possible. In order to find uncovered users that are close to a wireless communication tower, the local optimization algorithm finds all uncovered users in the radius of \(\lambda\), which is a control parameter of the search. Experimental results have shown that when \(\lambda=2d_{max}\), the local optimization algorithm gives the best results. Figure 4 illustrates this idea. In order to find a new location to build a wireless communication tower to cover more users, we initially tried moving the wireless communication tower to the geographically central location of its covered users. However, this method did not work very well because sometimes, after moving the wireless communication tower to the geographical center, the number of covered users becomes smaller. Figure 5 shows this scenario. It can be seen that, in the new location, the wireless communication tower can cover only one user. From a computational perspective, this problem can be formulated as a so-called _constrained maximum covering problem_. Given a circle of radius \(d_{max}\) and a set of points in the Euclidean plane, \(S\), which are enclosed in the circle, and another set of points in the Euclidean plane, \(S^{\prime}\), the constrained maximum covering problem is to find a new enclosing circle of radius \(d_{max}\) such that it encloses the maximum number of points in \(S^{\prime}\) in addition to those points in \(S\). We designed an algorithm to solve the constrained maximum coverage problem, as described in Algorithm 2. Figure 4: Search for uncovered users that are close to a wireless communication tower. Figure 5: Geographical center method. In this figure, **(a)** shows the initial location of the wireless communication tower, \(l_{1}\), in which the wireless communication tower can cover three users; **(b)** illustrates the situation where the wireless communication tower has been moved to the geographical center of the three users, \(l_{2}\). The basic idea behind the constrained maximum enclosing circle algorithm is simple. It iterates \(|S^{\prime}|\) times, and in each iteration, it randomly picks up a point \(p\) from \(S^{\prime}\) and then uses the randomized algorithm for the minimum enclosing circle problem proposed by [PERSON] [29] to find the minimum enclosing circle that encloses all points in \(S\) and the randomly selected point from \(S^{\prime}\), \(p\). If the radius of the minimum enclosed circle is less than or equal to \(d_{max}\), we move the randomly selected point \(p\) from \(S^{\prime}\) to \(S\); if the radius of the minimum enclosing circle is greater than \(d_{max}\), then we remove the randomly selected point \(p\) from \(S^{\prime}\). After \(S^{\prime}\) iterations, this algorithm finds a circle of radius \(d_{max}\) that encloses the maximum number of points in \(S^{\prime}\) in addition to those points in \(S\). The time efficiency of Algorithm 2 is \(O((|S|+|S^{\prime}|)|S^{\prime}|)\). Proof. : The while statement iterates \(|S^{\prime}|\) times, and in each of the iterations, one user is removed from \(S^{\prime}\). Assume that \(S^{\prime}  
```
1:for\(r=<x^{r},y^{r}>\in P\)do
2:\(S=\emptyset\)
3:\(S^{\prime}=\emptyset\)
4:for\(u=<x^{u},y^{u}>\in U\)do
5:\(d=\sqrt{(x^{u}-x^{r})^{2}+(y^{u}-y^{r})^{2}}\)
6:if\(d\leq d_{max}\)then
7:\(S=S\cup\{u\}\)
8:else
9:if\(d\leq 2\times d_{max}\)then
10:\(S^{\prime}=S^{\prime}\cup\{u\}\)
11:endif
12:endif
13:\(r=ConMaxCoverCircle(S,S^{\prime},d_{max})\)
14:endfor
15:endfor
```  
**Algorithm 3** Maximum coverage-based local optimization (P)  
The local optimization algorithm optimizes the location of wireless communication towers one by one using the constrained maximum cover circle algorithm.