# A Spectral Gap-Based Topology Control Algorithm for Wireless Backhaul Networks
## 4 SGTC: The Spectral Gap-Based Topology Control Algorithm
### The Feasible Solution Space  
To implement the local search, we define the _1-feasible neighborhood_ of a network topology \(G=(V,E)\) as the set \(N_{F}(G)\) composed of _feasible_ network topologies \(G^{\prime}=(V,E^{\prime})\) such that \(E^{\prime}\) can be obtained from \(E\) by adding or removing a single feasible link according to Definition 1. This way, the solution space can be organized as a graph with a vertex for each feasible network topology, and two vertices of this graph are adjacent if their corresponding network topologies differ in a single link. As shown in the pseudocode of Algorithm 2, SGTC starts the simulated annealing process from an initial network topology \((V,E_{0})\) that is provided as an input parameter. The algorithm uses function isFeasible() (see Line 2 of Algorithms 2 and 3) to check whether the initial topology is valid. If \((V,E_{0})\) is not feasible, the annealing process will start from an empty graph. From this point, SGTC performs a walk over the solution space graph by randomly selecting as the new candidate solution a network topology \(G_{i}\) from the 1-feasible neighborhood of the current solution \(G_{current}\). By using function getFeasibleRandomNeighbor() (see Line 8 of Algorithms 2 and 4) to select candidate solutions, the search performed by SGTC is restricted to feasible network topologies. **Input:** A set of stations \(V=M\cup S\), an initial set of links \(E_{0}\), a function \(l\) that determines the stations' position in the plane, radio ranges \(R_{M}\) and \(R_{S}\), the initial temperature \(\alpha_{0}\), and number of iterations \(Max\_Itera\)  
**Output:**\(G_{best}\)  
```
1:\(G_{current}\leftarrow(V,E_{0})\); \(\mathcal{F}\leftarrow\emptyset\)
2:if\(isFeasible(G_{current},l,R_{M},R_{S})\)then
3:\(\mathcal{F}\leftarrow\mathcal{F}\cup\{G_{current}\}\)
4:else
5:\(\mathcal{F}\leftarrow\mathcal{F}\cup\{(V,\emptyset)\}\)
6:endif
7:for\(i=1\) to \(Max\_Itera\)do
8:\(G_{i}\gets getFeasibleRandomNeighbor(G_{current},l,R_{M},R_{S})\)
9:\(\lambda_{2}^{candidate}\gets LSG(G_{i})\)
10:\(\Delta\leftarrow\lambda_{2}^{candidate}-\lambda_{2}^{current}\)
11:\(p_{accept}=e^{(-\Delta/\alpha)}\)
12:if\(\Delta>0\)then
13:\(G_{current}\gets G_{i}\), \(\lambda_{2}^{current}\leftarrow\lambda_{2}^{candidate}\), \(\mathcal{F}\leftarrow\mathcal{F}\cup\{G_{current}\}\);
14:else with probability \(p_{accept}\)
15:\(G_{current}\gets G_{i}\), \(\lambda_{2}^{current}\leftarrow\lambda_{2}^{candidate}\)
16:endif
17:\(\alpha=\alpha_{0}/(i+1)\)
18:endfor
19:\(\mathcal{P}\leftarrow ParetoFront(\mathcal{F},min(D_{G}),max(R_{G}),max(S_{G}))\)
20:return\(G_{best}\leftarrow\arg\min_{G\in\mathcal{P}}\{C_{G}\}\)
```  
**Algorithm 2** SGTC Algorithm  
We decided to constrain the search to the feasible solution space because if an unfeasible link that increases the LSG is added to the network, the annealing process would be highly unlikely to remove it in future iterations to obtain a feasible topology. In such a scenario, from the point an unfeasible link is added to a solution, it will likely remain unfeasible until the end of the annealing process. ```
0: A network topology \(G=(M\cup S,E)\), a function \(l\) that determines the stations' position in the plane, and radio ranges \(R_{M}\) and \(R_{S}\)
0: True if the topology is feasible according to Definition 1, false otherwise.