A Spectral Gap-Based Topology Control Algorithm for Wireless Backhaul Networks

Abstract

This paper presents the spectral gap-based topology control algorithm (SGTC) for wireless backhaul networks, a novel approach that employs the Laplacian Spectral Gap (LSG) to find expander-like graphs that optimize the topology of the network in terms of robustness, diameter, energy cost, and network entropy. The latter measures the network’s ability to promote seamless traffic offloading from the Macro Base Stations to smaller cells by providing a high diversity of shortest paths connecting all the stations. Given the practical constraints imposed by cellular technologies, the proposed algorithm uses simulated annealing to search for feasible network topologies with a large LSG. Then, it computes the Pareto front of the set of feasible solutions found during the annealing process when considering robustness, diameter, and entropy as objective functions. The algorithm’s result is the Pareto efficient solution that minimizes energy cost. A set of experimental results shows that by optimizing the LSG, the proposed algorithm simultaneously optimizes the set of desirable topological properties mentioned above. The results also revealed that generating networks with good spectral expansion is possible even under the restrictions imposed by current wireless technologies. This is a desirable feature because these networks have strong connectivity properties even if they do not have a large number of links.

1. Introduction

The demand for wireless bandwidth with Quality of Service (QoS) and ubiquitous network connectivity is continuously increasing due to the explosive growth in data traffic caused by a new generation of innovative high data rate services and applications accessed from a wide variety of wireless devices [1,2].

To address this issue, wireless backhaul networks that connect Macro Base Stations (MBSs) and Small Cells (SCs) are becoming popular as they use multiple-input multiple-output (Massive MIMO) and millimeter-wave (mmWave) transmission technologies [3,4,5,6] that use multiple antennas to provide significant improvements in wireless data transmission rates, link efficiency, network reliability, and energy efficiency [7,8]. They achieve high spectral efficiency by serving many users simultaneously and enabling the placement of a dense number of SCs within the MBSs coverage area [9]. These SCs consist of low-power radio transmitter nodes that can handle the traffic of fixed and low-mobility users, which results in improved Quality of Service (QoS) in terms of throughput and outage as the distance between the access points and users is relatively short [10,11].

Although current wireless backhaul networks utilizing Massive MIMO and mmWave technologies show great potential in meeting the demands of current and future mobile Internet users, they require innovative network topology-control mechanisms that surpass those implemented in conventional cellular networks such as LTE or LTE-Advanced [12]. This is essential for establishing a robust network backbone that fosters scalability and energy efficiency.

Topology control (TC) mechanisms aim to adapt the topology of a network to optimize performance metrics such as energy consumption while maintaining connectivity requirements throughout the network [13,14]. TC schemes were initially designed for Wireless Sensor Networks (WSNs), Mobile Ad Hoc Networks (MANETs), and Wireless Mesh Networks (WMNs) to improve overall performance [15,16,17]. In wireless backhaul networks, the topology is adjustable by modifying parameters such as transmission power and antenna radiation patterns [18,19].

TC is generally challenging because there are several objective metrics to optimize, some potentially conflicting (e.g., energy consumption and robustness). To make the problem more tractable, we propose focusing the search for feasible topologies on expander-like graphs, which are sparse graphs with “good” connectivity properties [20,21]. More specifically, we propose to search for topologies with high Laplacian Spectral Gap (LSG), which measures the strength of network connectivity and entanglement [22].

The proposed algorithm takes advantage of the directional beamforming capability of Massive MIMO systems to activate a set of feasible non-interfering communication links, which allows the efficient incorporation of a significant number of SCs within the MBS coverage, increasing the spatial reuse of bandwidth and increasing spectral efficiency.

To the best of our knowledge, SGTC is the first topology control algorithm that effectively employs the information provided by the LSG to optimize the network topology by simultaneously minimizing the number of links and network diameter while maximizing the network entropy and the number of edge-disjoint paths connecting any two stations in the backhaul network. All these topological properties are desirable for backhaul networks because sparse topologies are energy-efficient, the network diameter impacts the upper bound of the end-to-end delay, the network entropy is related to the network’s ability to distribute data traffic evenly across the network and promotes seamless traffic offloading from the MBSs to the SCs, and a higher number of edge-disjoint paths leads to better throughput and robustness.

The rest of the paper is organized as follows. Section 2 presents and discusses related work on massive MIMO systems, Small Cells, topology control, and expander graphs in the context of our work. Section 3.1 presents a set of definitions and assumptions that are used in the rest of the paper. Section 3.3 presents the problem formulation. Section 4 and Section 4.3 present the details of the proposed topological control scheme. Section 5 presents the results of a series of experiments characterizing the impact of the LSG of the topology on the overall network performance. Lastly, we present our concluding remarks in Section 6.

2. Related Work

In the past, topology control mechanisms have been studied mainly in Wireless Mesh Networks, Wireless Mobile Ad Hoc Networks, and Wireless Sensor Networks. The main objective of this type of mechanism is to modify the network topology to induce connectivity properties and improve the overall network performance [23,24].

Recently, topology-control mechanisms have also become relevant in wireless backhaul networks because they can help improve efficiency, promote traffic offloading from the core network, and avoid bottlenecks in the backhaul network. For instance, in [25], the authors propose planning schemes for microwave-based wireless backhaul networks based on tree topologies that jointly optimize multiple performance metrics, such as traffic hops (delay), long links, link crosses, small angles, and the sum of the link distances. In [26], the authors propose an iterative heuristic algorithm that constructs topologies that maximize the total backhaul flow in wireless multi-hop backhaul networks composed of SCs and networked flying platform (NFP) hubs. In [27], the authors show that if the topologies for Ultra-High-Dense Networks (UDN) combine MBSs and a dense tier of SCs, they can accomplish objectives of 5G networks such as meeting traffic demand while providing seamless coverage, high data rate for low-mobility users and spatial reuse. In [10], a comprehensive survey about the architecture, performance metrics, and guidelines of 5G networks is presented. The authors show that accommodating Massive MIMO with Small Cells improves performance metrics such as energy efficiency, coverage, capacity, resource efficiency, and spectral efficiency.

In the context of topology control schemes, some works have proposed inducing expander-like topologies in networks [28,29]. The rationale behind these works is that expander graphs are sparse graphs with strong connectivity properties [20], and therefore, networks with expander-like topologies will tend to be robust even if they do not have a large number of links. In [30], the authors investigate the relationship between the properties of expander topologies implemented by wireless networks (called Wireless Expanders ) and the performance of such wireless networks in terms of enabling efficient broadcast solutions. In [31,32], the authors model dynamic peer-to-peer (P2P) networks using expander graphs in which the spectral gap property is preserved under node insertions and deletions. In [33], the authors show that communication networks with expander-like topologies tend to be flexible and easy to reconfigure and optimize.

Simulated annealing (SA) has been successfully used to solve complex problems in wireless networks. For example, in [34], the authors use SA for wireless backhaul planning to maximize system performance regarding network throughput and delay while reducing infrastructure utilization. Similarly, in [35], the authors propose an SA-based algorithm to solve a power consumption problem. The idea is to use SA to minimize the total power consumed by MBSs and SCs serving access and wireless backhaul links. Other works on the use of SA to optimize the performance of wireless networks are [36,37,38]. All these works show the effectiveness of simulated annealing as an optimization technique in the context of wireless networks.

This literature review shows that, unlike our proposal that uses the LSG to find expander-like topologies that simultaneously optimize the network’s energy cost, robustness, diameter, and entropy, previous topology control algorithms for backhaul networks either restrict their search to three-based topologies [25], or do not consider multiple objective functions [26,27,28,29,30,31,32]. Although SA has been used in the past for wireless backhaul planning [35], our algorithm is the first to incorporate the information provided by the LSG to find network topologies with low energy costs and strong connectivity properties.

3. System Model and Problem Formulation

In this section, we introduce the notation used in the paper and provide a detailed description of the system model. We also present the problem formulation for finding a network topology that minimizes the number of links and the network’s diameter while maximizing the network’s entropy and robustness.

3.1. System Model

We use a graph $G=(M\cup S,E)$ to model the topology of a wireless backhaul network composed of sets of Macro Base Stations (MBSs) M, Small Cells (SCs) S, and bidirectional wireless communication links $E\subseteq V\times V$ between them, where $V=M\cup S$ is the set of all the stations. The position of the stations in the plane is determined by a function $l:V\to {\mathbb{R}}^2$ that assigns x and y coordinates to them. We use $N\left(u\right)=\{v:(u,v)\in E\}$ to denote the one-hop neighborhood of u.

We assume that the SCs have a coverage range of $R_S$ distance units, whereas the MBSs have a coverage range of $R_M$ distance units. From the values of the coverage ranges, we have the following two definitions.

Definition 1.

A communication link $(u,v)\in E$ between stations $u,v\in V$ is feasible if $dist(l\left(u\right),l\left(v\right))\le R_S$ when $u,v\in S$ or $dist(l\left(u\right),l\left(v\right))\le R_M$ when either u or v is in M; where $dist$ is the Euclidean distance.

Definition 2.

A network topology $G=(M\cup S,E)$ is feasible if every link $(u,v)\in E$ is feasible.

We further assume that:

• All the stations are static; namely, they have fixed positions.
• All the MBs have the same capabilities and coverage range. They are implemented by a Massive MIMO system with $N_M$ antenna elements.
• All the SCs have the same capabilities and coverage range. They are equipped with $N_S$ antenna elements capable of supporting multiple parallel data streams.
• MBSs and SCs can support all the possible links with the other MBs and SCs placed in their corresponding coverage area. More specifically, for an MBS $u\in M$, the inequality $N_M\ge \left|N\left(u\right)\right|$ holds. Similarly, for a SC $v\in S$, the inequality $N_S\ge \left|N\left(v\right)\right|$ also holds.
• The energy cost of establishing a link from station u to station v is proportional to $dist\left(l\right(u),l(v\left)\right)$.
• All the SCs have relay functionality; namely, they can communicate with any of their one-hop neighbors.

For a given network topology $G=(M\cup S,E)$, we use the following performance metrics:

• Network Diameter ($D_G$): Defined as the longest shortest path between any two stations in G. Networks with a small diameter tend to induce lower delays and reduce the energy used to transport a packet from sources to destinations.
• Network Robustness ($R_G$): Defined as the cardinality of the global minimum cut-set, which is equivalent to the minimum number of edge-disjoint paths connecting any two stations in the network. Networks with high robustness are more tolerant to link breaks due to interference or channel effects. This metric indicates the minimum number of edges that need to be removed to partition the network.
• Network Cost ($C_G$): Defined as the sum of the length of the edges in the graph (see Equation (1)). This metric is related to the power used by the network to establish and maintain all the communication links.

  $$\begin{array}{c}\hfill C_G=\sum _{e=(u,v)\in E}dist(l\left(u\right),l\left(v\right))\end{array}$$

  (1)
• Network Entropy ($S_G$): Defined as the entropy (see Equation (2)) over the probability mass function (see Equation (3)) of using a particular link $e\in E$ as part of the shortest path connecting an arbitrary source-destination pair. Network entropy measures the amount of information about how data traffic will be distributed across a particular network by a specific shortest-path routing protocol. High values of network entropy indicate that a given shortest-path routing protocol will tend to distribute data traffic evenly across the network. On the other hand, low values of network entropy indicate that this shortest-path routing protocol will tend to concentrate data traffic on a subset of the links (those with a high probability of being part of the shortest path). Similar to the betweenness centrality [39], $Pr\left(e\right)$ (see Equation (2)) provides information about the influence of an edge over the data flows in a network. In this context, network entropy can also be considered a measure of the ability of the network topology to distribute the traffic load evenly among all the active links and, hence, among all the stations (MBSs and SCs) that compose the network.

$$\begin{array}{c}\hfill S_G=-\sum _{e\in E}Pr\left(e\right){log}_{2}Pr\left(e\right)\end{array}$$

(2)

$$\begin{array}{c}\hfill Pr\left(e\right)=\frac{f\left(e\right)}{{\sum }_{e\in E}f\left(e\right)}\end{array}$$

(3)

In Equation (3), $f:E\to \mathbb{N}$ is a function that counts the shortest paths that include link e and ${\sum }_{e\in E}f\left(e\right)$ is a normalization constant. Algorithm 1 shows the pseudocode to compute the value of function f for a given $e\in E$. The call to $ShortestPath(G,a,b)$ (see line 4) returns a shortest path connecting two stations using a given shortest path algorithm. We assume that the implementation of the shortest path algorithm breaks ties arbitrarily but consistently and, hence, that it always computes the same shortest path for a given source-destination pair.

Algorithm 1 f(e)

Input  A network $G=(V,E)$, an edge $e\in E$. Output The value of $f\left(e\right)$.  1: $f\left(e\right)\leftarrow 0$  2: $AllSourceDest=\left\{\right(a,b)\mid a\ne b\&a,b\in V\}$  3: for all$(a,b)\in AllSourceDest$do  4:     $P\leftarrow ShortestPath(G,a,b)$  5:     if $e\in P$ then  6:         $f\left(e\right)\leftarrow f\left(e\right)+1$  7:     end if  8: end for  9: return $f\left(e\right)$;

3.2. Laplacian Spectral Gap

Let $A\left(G\right)=\left[a_{ij}\right]$ be the adjacency matrix of a network $G(V,E)$ where $a_{ij}=1$ if there is an edge from station i to station j and $a_{ij}=0$ otherwise. Let $D\left(G\right)$ be the degree matrix $D\left(G\right)=\left[d_{ij}\right]$ of G which is a diagonal matrix with $d_{ij}=\left|N\left(i\right)\right|$ if $i=j$ and, $d_{ij}=0$ otherwise. From these two matrices, we can compute the Laplacian Matrix of the network $L\left(G\right)$ as $D\left(G\right)-A\left(G\right)$ [40]. Since a simple graph can represent the networks under consideration (links are bidirectional), $L\left(G\right)=D\left(G\right)-A\left(G\right)$ is a symmetric, positive semidefinite matrix that is also known as the combinatorial Laplacian matrix or Kirchoff matrix. For this type of network, $L\left(G\right)$ has a set of $n=\left|V\right|$ real eigenvalues ${\lambda }_1$, ${\lambda }_2$,..,${\lambda }_{\left|V\right|}$ where the second smallest eigenvalue (${\lambda }_2$) is called the Laplacian Spectral Gap, LSG [40] of the network G. A large value of LSG implies a higher expansion, meaning that the network is generally well connected [20]. This type of graph is associated with Expander Graphs, a family of sparse graphs with strong connectivity properties [41].

3.3. Problem Formulation

From the previous concepts and definitions, we formally state the problem of computing optimized wireless backhaul network topologies composed of MBs and SCs as follows.

Problem Formulation 1. Given a set of wireless backhaul entities $V=M\cup S$ located at positions in the plane designated by function l, and radio ranges $R_S$ for SCs and $R_M$ for MBSs, find a set $E^{\prime }\subseteq V\times V$ of feasible communication links, according to Definition 1, such that the Laplacian Spectral Gap${\lambda }_2$ of $G=(V,E^{\prime })$ is maximized.

As we have already mentioned, the objective of maximizing the Laplacian Spectral Gap is to jointly optimize:

• the Network Diameter $D_G$ of $G=(V,E^{\prime })$;
• the Network Robustness $R_G$ of $G=(V,E^{\prime })$;
• the Network Cost $C_G$ of $G=(V,E^{\prime })$ and;
• the Network Entropy $S_G$ of $G=(V,E^{\prime })$ as defined in Section 3.1.

In this first formulation, the location of all stations is part of the input and is specified a priori by the function l.

Another interesting network design problem is to find suitable locations for the Macro Base Stations, i.e., to find a function $l_M:M\to {\mathbb{R}}^2$ that assigns a location in the plane to the MBSs such that the network performance is optimized. In this case, only the number of MBSs, not their locations, is part of the input.

Problem Formulation 2. Given a set of SCs S located at positions in the plane designated by the function $l_S:S\to {\mathbb{R}}^2$, a number m of MBSs, and radio range $R_S$ for SCs and $R_M$ for MBSs; find a function $l_M:M\to {\mathbb{R}}^2$ that assigns a location in the plane to the MBSs and a set $E^{\prime }\subseteq V\times V$ of feasible communication links such that the Laplacian Spectral Gap ${\lambda }_2$ of $G=(M\cup S,E^{\prime })$ is maximized.

Table 1. Summary of notation.

$G=(M\cup S,E)$	A network.
$V=M\cup S$	Set of stations, including the set M of MBSs and the set S of SCs.
E	Set of unidirectional links connecting the stations.
$E_0$	Initial set of links in the annealing process.
$l:V\to {\mathbb{R}}^2$	Function that determines the position of the stations.
$l_S:V\to {\mathbb{R}}^2$	Function that determines the position of the SCs.
$l_M:V\to {\mathbb{R}}^2$	Function that determines the position of the MBSs.
$N\left(u\right)$	One-hop neighborhood of station u.
$N_F\left(G\right)$	Set of one-hop feasible neighbors of network G.
$R_M$	Radio range of the Macro Base Stations.
$R_S$	Radio range of the Small Cells.
$N_M$	Number of antenna elements in an MBS.
$N_S$	Number of antenna elements in an SC.
$D_G$	Diameter of network G.
$R_G$	Robustness of network G.
$C_G$	Cost of network G.
$S_G$	Network entropy of G.
$f:E\to \mathbb{N}$	Function that counts the number of shortest paths that include $e\in E$.
$A\left(G\right)=\left[a_{ij}\right]$	Adjacency matrix of G.
$D\left(G\right)=\left[d_{ij}\right]$	Degree matrix of G.
$L\left(G\right)$	Laplacian matrix of G.
${\lambda }_2$	Second smallest eigenvalue of $L\left(G\right)$ (Laplacian Spectral Gap).
$Max\_Itera$	Maximum number of iterations of the SGTC algorithm.
${\alpha }_0$	Initial value of the temperature in the annealing process.
$\alpha$	Value of the temperature during the annealing process.
$dist\left(l\right(u),l(v\left)\right)$	Euclidean distance between stations u and v.
$dist(l_S\left(u\right),M)$	Euclidean distance between station u an its closest MBS in M.
$r\left(M\right)$	Covering radius of a set M of MBS.

summarizes the notation used throughout the paper.

4. SGTC: The Spectral Gap-Based Topology Control Algorithm

This section introduces the proposed spectral gap-based topology control (SGTC) algorithm for wireless backhaul networks. The SGTC algorithm employs the information provided by the LSG to optimize the network topology with respect to the four performance metrics defined in Section 3.3. SGTC takes as input the set of network entities $V=M\cup S$ (generically referred to as stations), an initial set $E_0$ of links, functions $l_M$ and $L_S$ that map stations to positions in the plane, radio ranges for MBSs and SCs, and the value of $\mathit{Max\_Itera}$ which determines the maximum number of iterations.

The SGTC algorithm employs the simulated annealing (SA) meta-heuristic technique to explore the feasible solution space, seeking network topologies that yield a high LSG (${\lambda }_2$). As we describe in more detail in the following paragraphs, the annealing process implements a random walk over the feasible solution space where a new candidate solution is accepted with a probability proportional to its LSG value and the current temperature of the annealing process. Initially, the temperature is set to a high value to promote a broad search of the solution space, and on each iteration, it is reduced to direct the random walk towards strictly better solutions.

After the annealing process is completed, SGTC calculates the Pareto front of the best feasible network topologies that were visited during the process. This calculation is based on three criteria: minimizing the network diameter and maximizing network robustness and entropy. SGTC returns the Pareto efficient solution with the lowest energy cost as its output.

4.1. 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\left(G\right)$ 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.

Algorithm 2 SGTC Algorithm

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 $\mathit{Max\_Itera}$ Output:  $G_{best}$  1: $G_{current}\leftarrow (V,E_0)$; $\mathcal{F}\leftarrow \varnothing$  2: if$isFeasible(G_{current},l,R_M,R_S)$ then  3:     $\mathcal{F}\leftarrow \mathcal{F}\cup \left\{G_{current}\right\}$  4: else  5:     $\mathcal{F}\leftarrow \mathcal{F}\cup \left\{\right(V,\varnothing \left)\right\}$  6: end if  7: for $i=1$ to $\mathit{Max\_Itera}$ do  8:     $G_i\leftarrow getFeasibleRandomNeighbor(G_{current},l,R_M,R_S)$  9:     ${\lambda }_2^{candidate}\leftarrow LSG\left(G_i\right)$  10:     $\Delta \leftarrow {\lambda }_2^{candidate}-{\lambda }_2^{current}$  11:     $p_{accept}=e^{(-\Delta /\alpha )}$  12:     if $\Delta >0$ then  13:         $G_{current}\leftarrow G_i$, ${\lambda }_2^{current}\leftarrow {\lambda }_2^{candidate}$, $\mathcal{F}\leftarrow \mathcal{F}\cup \left\{G_{current}\right\}$;  14:     else with probability $p_{accept}$  15:         $G_{current}\leftarrow G_i$, ${\lambda }_2^{current}\leftarrow {\lambda }_2^{candidate}$  16:     end if  17:     $\alpha ={\alpha }_0/(i+1)$  18: end for  19: $\mathcal{P}\leftarrow ParetoFront(\mathcal{F},min\left(D_G\right),max\left(R_G\right),max\left(S_G\right))$  20: return $G_{best}\leftarrow arg{min}_{G\in \mathcal{P}}\left\{C_G\right\}$

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.

Algorithm 3 is Feasible

Input:  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$ Output:  True if the topology is feasible according to Definition 1, false otherwise.  1: for all  $e=(u,v)\in E$do  2:     if $\{u,v\}\cap M\ne \varnothing$ then  3:         if $dist(l\left(u\right),l\left(v\right))>R_M$ then  4:            return false  5:         end if  6:     else  7:         if $dist(l\left(u\right),l\left(v\right))>R_S$ then  8:            return false  9:         end if  10:     end if  11: end for  12: return true

Algorithm 4 obtain Feasible Random Neighbor

Input:  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$ Output:  A network topology $G^{\prime }\in N_F\left(G\right)$ or G if $N_F\left(G\right)=\varnothing$  1: $V\leftarrow M\cup S$  2: for ${\left|V\right|}^2$ iterations do  3:     $e=(u,v)\leftarrow getWithoutReplacementUniformlyatRandomFrom(V\times V)$  4:     if $e\in E$ then  5:         return $G^{\prime }=(V,E\setminus \left\{e\right\})$  6:     else  7:         if $\{u,v\}\cap M\ne \varnothing$ then  8:            if $dist(l\left(u\right),l\left(v\right))\le R_M$ then  9:                return $G^{\prime }=(V,E\cup \left\{e\right\})$  10:            end if  11:         else  12:            if $dist(l\left(u\right),l\left(v\right))\le R_S$ then  13:                return $G^{\prime }=(V,E\cup \left\{e\right\})$  14:            end if  15:         end if  16:     end if  17: end for  18: return  G

4.2. The Annealing Process

Following the simulated annealing strategy, on each iteration of SGTC, a candidate solution $G_i$ is accepted as the new current solution with probability one if $G_i$ has a larger value of ${\lambda }_2$ than that of the current solution $G_{current}$, namely if $\Delta ={\lambda }_2^{candidate}-{\lambda }_2^{current}>0$ (Line 12). It also accepts a candidate solution following the Metropolis criterion, with probability $p_{accept}$, if $\Delta \le 0$ (Line 14). The control parameter $\alpha$, used in Line 11 of Algorithm 2 to compute the probability $p_{accept}$, takes the role of the temperature in the annealing process and is reduced at each iteration (see Line 17) to gradually force the search towards strictly better solutions.

SGTC stores in $\mathcal{F}$ the feasible network topologies $G_{current}$ visited during the annealing process. Then, it uses ParetoFront() (see Line 19 of Algorithm 2) to determine the Pareto front $\mathcal{P}$ composed of the solutions in $\mathcal{F}$ that minimize the network diameter and maximize the network robustness and entropy.

Lastly, SGTC returns the network in $\mathcal{P}$ of minimum energy cost (see Line 20 of Algorithm 2) as the output of the algorithm.

4.3. SGTC with Optimized MBS Placement

To address Problem Formulation 2, where the network designer can determine the location of the MBSs, we propose to find a set of locations that minimizes the maximum distance between any SC and its closest MBS. More formally, let $dist(l_S\left(u\right),M)={min}_{m\in M}\left\{dist(l_S\left(u\right),l_M\left(m\right))\right\}$ be the distance between an SC $u\in S$ and the set M of MBSs. We propose to find a function $l_M$ that assigns locations to the MBSs that minimize M’s covering radius $r\left(M\right)$, which equals $ma{x}_{u\in S}\left\{dist(l\left(u\right),M)\right\}$.

This latter formulation corresponds to the vertex k-center problem (for $k=\left|M\right|$), a well-known NP-hard problem originally proposed by Hakimi in 1964 [42]. Since the vertex k-center problem cannot be solved in polynomial time within an approximation factor of $\rho <2$ [43], unless P = NP, we propose using the Critical Dominating Set algorithm that has shown good performance in practice [44,45].

Once we have determined optimized locations for the MBSs, we can use the SGTC algorithm to look for a topology with a large Laplacian Spectral Gap.

4.4. Computational Complexity

The following theorem establishes the temporal complexity of the SGTC algorithm.

Theorem 1.

The temporal complexity of the SGTC algorithm (Algorithm 2) is $O(\mathit{Max\_itera}\times |V{|}^2)$.

Proof of Theorem 1. 

The main loop of Algorithm 2 (lines 7–18) iterates $\mathit{Max\_itera}$ times and contains calls to isFeasible() (Algorithm 3), getFeasibleRandomNeighbor() (Algorithm 4), and LSG() to compute the LSG of a network $G=(V,E)$.

The complexity of Algorithm 3 is $O\left(\right|V{|}^2)$ because it checks whether all the $e\in E$ are feasible, and the maximum number of edges in a graph is in $O\left(\right|V{|}^2)$. Similarly, the complexity of Algorithm 4 is $O\left(\right|V{|}^2)$ because, in the worst case, it performs ${\left|V\right|}^2$ iterations to identify a feasible link $e\in V\times V$ that will be either added or removed from E. Computing the LSG of a graph $G=(V,E)$ is dominated by the cost of determining its eigenvalues, which is $O\left(\right|V{|}^2)$ because the Laplacian Matrices are symmetric. Therefore, the total complexity of the main loop is $O(\mathit{Max\_itera}\times |V{|}^2)$.

The complexity of computing the Pareto front of N data points and three objective functions is $O(NlogN)$ when we use Kung’s algorithm [46]. So, if we select $N\in \Theta \left(\right|V\left|\right)$ we obtain $O\left(\right|V|log|V\left|\right)$.

Therefore, the overall complexity of the SGTC algorithm is $O(\mathit{Max\_itera}\times |V{|}^2+\left|V\right|log\left|V\right|)$ which is the same as $O(\mathit{Max\_itera}\times |V{|}^2)$. □

5. Experimental Results

In this section, we present the results of a series of experiments that characterize the ability of the SGTC algorithm to find network topologies that optimize the performance metrics presented in Section 3.3, namely, that minimize the network diameter $D_G$, maximize the network robustness $R_G$, minimize the network cost $C_G$, and maximize the network entropy $S_G$.

For a given network topology $G=(V,E)$, and function $l_M$ and $l_S$ that assign the positions of the nodes in the plane, we compute its robustness $R_G$ as the cardinality of the global minimum cut-set. To this end, we execute an instance of the Ford–Fulkerson algorithm [47] over the $O\left(\right|V{|}^2)$ pairs of nodes. To compute the network entropy, we run Dijkstra’s algorithm [48] for every pair of nodes and count the number of times (denoted by $f\left(e\right)$) that a given $e\in E$ belongs to one of these shortest paths. Then, we use Equation (3) to compute the probability of using a particular edge e in the shortest path and compute $S_G$ according to Equation (2). The network diameter is easily obtained from the lengths of the shortest paths of all the pairs of nodes, and the network cost is computed according to Equation (1).

For the experiments presented in this section, we generate problem instances by assuming an uncorrelated position of the network entities (stations) within a normalized squared region of $1\times 1$. Specifically, we compute each station’s x and y coordinates by sampling the continuous uniform distribution with bounds $[0,1]$, which assumes an uncorrelated position of the nodes [49,50].

As shown in

Table 2. Experimental parameters.

Parameter	Values
Total number of stations	{100, 150, 200}
Number of MBSs	$10\%$ of the stations
Normalized radio range of MBSs ($R_M$)	{0.3, 0.5}
Normalized radio range of SCs ($R_S$)	{0.15, 0.2}
Iterations of SGTC ($Max\_Itera$)	10,000
Initial temperature (${\alpha }_0$)	1.0
Initial set of links ($E_0$)	{∅, Feasible fully connected, Voronoi}

, we vary the total number of stations $\left|V\right|$ from 100 to 200, the normalized radio range of the MBSs from 0.3 to 0.5, and the normalized radio range of the SCs from 0.15 to 0.2. The number of MBSs equals $\lfloor 0.1\times \left|V\right|\rfloor$ to have scenarios where approximately $10\%$ of the stations are MBSs. We further assume that all the stations have enough antennas to establish all the links determined by the SGTC algorithm.

The results presented in all the figures include the output of the proposed algorithm when using the following initial network topologies.

• Disconnected: $E_0=\varnothing$. The initial network has no links.
• Feasible fully connected: $E_0=\{e=(u,v)\in V\times V:e$ is $feasible\}$. The initial network contains all the feasible links.
• Voronoi topology [51]: $E_0=\{e=(u,v)\in M\times M:e$ is $feasible\}\bigcup \{e=(u,v)\in S\times M:v={argmin}_{v\in M}\left\{dist(l\left(u\right),l\left(v\right))\right\}\wedge e$ is $feasible\}$. The initial network contains all the feasible links connecting MBSs among themselves, and the SCs are connected to their closest MBSs if the corresponding link is feasible.

In all the experiments, the maximum number of iterations of the SGTC algorithm equals 10,000, and the initial temperature ${\alpha }_0$ of the simulated annealing process equals 1.0. Each experiment is run for 20 independent seeds.

The experimental workflow composed of the instance generator, the SGTC algorithm, and a set of algorithms that compute the performance metrics is illustrated in Figure 1. The instance generator algorithm takes the number of stations $\left|V\right|$, the percentage of MBSs, and the type of MBS placement (random or k-center) as input parameters. It returns functions $l_M$ and $l_S$ that determine the locations of MBSs and SCs, respectively.

Next, the SGTC algorithm uses the functions $l_M$, $l_S$, the initial set of links $E_0$, and the values of the radio ranges $R_M$ and $R_S$ as input parameters to compute the resulting topology $G=(V,E)$ of the backhaul network. The initial temperature ${\alpha }_0$ and the number of iterations $\mathit{Max\_Itera}$ are the hyper-parameters of SGTC.

Lastly, a set of algorithms compute the diameter $D_G$, robustness $R_G$, cost $C_G$, and entropy $S_G$ of network G.

5.1. Performance as a Function of the LSG

Figure 2, Figure 3, Figure 4 and Figure 5 illustrate the behavior of the four performance metrics as a function of the value of the LSG. In the figures, each data point corresponds to a network topology found by SGTC during the annealing process, and the solid lines represent curves fitting the data points computed using logarithmic regression. The data points that belong to the Pareto front of the solutions that minimize the network diameter and maximize the network robustness and entropy are highlighted in black. For these results, we set the value of the normalized radio ranges $R_M$ and $R_S$ to 0.5 and 0.2, respectively. For the sake of clearness, the figures only present a representative sample of all the results; however, the tendencies shown in the figures hold across all our experiments.

From Figure 2, we can observe that for all the values of the network size and the two types of MBS placement, the value of the network entropy $S_G$ increases as the value of the LSG increases. This result indicates that networks with larger LSG distribute the shortest paths connecting the stations evenly among all the data links. This is important because this type of topology will promote the even distribution of the data traffic among the whole network, thus offloading traffic from the MBSs to the SCs and reducing the probability of contention hot spots.

From Figure 3, we can observe that, in general, the value of the network diameter $D_G$ decreases as the value of the LSG increases, which indicates that the network gets better connected in terms of the length of the network’s largest shortest path. This positively impacts the upper bounds of the end-to-end delay and the energy needed to support an end-to-end data flow. Similarly, Figure 4 shows that the network robustness $R_G$, measured as the cardinality of the network’s global minimum cut-set, increases as the LSG increases. This result indicates that networks with a larger value of LSG tend to be more robust to link breaks.

Lastly, Figure 4 shows that the network cost $C_G$ also increases as the LSG increases; however, for the case of networks of size 100 and 150, the rate at which the cost increases is reduced as the value of the LSG becomes larger. We can observe a similar trend for the networks of size 200 but with some exceptions for values of LSG larger than four. It is important to point out that SGTC avoids selecting these high-cost networks by selecting the Pareto efficient solution of minimum cost.

5.2. Performance Evaluation

Figure 6, Figure 7, Figure 8 and Figure 9 show the performance attained by SGTC when increasing the network size from 100 to 200 stations; MSBs are placed either at random or by solving the related k-center problem to minimize their covering radius; and for values of the stations’ radio ranges $R_M\in \{0.3,0.5\}$ and $R_S\in \{0.15,0.2\}$. In order to have a performance baseline, we include the results of a traditional Voronoi-based algorithm that adds to the network all the feasible links connecting two MBSs and the feasible links connecting every SC to its closest MBS. In the figures, each point corresponds to the average result computed over 20 independent experiments, and the error bars correspond to the standard deviation value. Missing points in the graphs indicate that the corresponding algorithms could not connect the network in at least one of the twenty independent experiments.

From Figure 6, we can observe that SGTC outperforms the traditional Voronoi-based algorithm by consistently achieving a higher value of network entropy $S_G$. The figure also shows that the network entropy benefits from having higher values of radio ranges. The reason is that the number of feasible links increases as the radio range increases, which also increases the space of feasible topologies that SGTC can investigate. From the figure, we can also notice that the MBS placement has no noticeable effect on this metric. Lastly, this figure does not include results for the Voronoi-based algorithm when $R_M=0.3$ and $R_S=0.15$ because the algorithm did not produce connected networks.

Figure 7 shows the network diameter $D_G$ attained by the algorithms under the different scenarios. Similar to the case of the network entropy, SGTC produces the networks with the smallest diameters when $R_M=0.5$ and $R_S=0.2$, which indicates that the algorithm can take advantage of a large space of feasible topologies to find well-connected networks. For $R_M=0.3$ and $R_S=0.15$, the Voronoi-based algorithm achieves smaller values of network diameters by predominantly using the sub-network consisting of links between MBSs. This, however, has the disadvantage of concentrating the traffic in the MBSs. As for the previous metric, this figure shows that the MBS placement has no noticeable effect on the network diameter.

Figure 8 shows that the network robustness $R_G$ follows a similar trend to that of the previous metrics. SGTC produces the most robust networks when the space of feasible topologies is larger, namely, when $R_M=0.5,R_S=0.2$, and there are many stations. However, unlike the case of the previous metrics, SGTC finds more robust networks for the case of $R_M=0.3,R_S=0.15$ when the MBSs are placed using the k-center algorithm. The reason is that by reducing the covering radius of the MBS, the probability that all the SCs are within the radio range of an MBS is increased, which increases the probability of having more paths connecting the SCs to the rest of the network.

Lastly, Figure 9 shows that the network cost $C_G$ attained by the traditional Voronoi-based algorithm is smaller than that of SGTC. This result was expected because the Voronoi-based algorithm’s topologies include fewer links; the SCs are only connected to their closest MBS. As we saw in the previous metrics, this reduced cost comes at the expense of fragile, weakly connected networks that tend to concentrate traffic in the MBSs, increasing the probability of contention hot spots. This behavior becomes apparent when $R_M=0.3$, $R_S=0.15$ because the links selected by the Voronoi-based algorithm are not enough to connect the network. On the other hand, even though the topologies generated by SGTC are more costly, we can observe that the rate at which this cost increases is similar to that of the Voronoi topologies. The reason is twofold. First, given that the cost of a network topology grows sublinearly with respect to the value of the LSG, the annealing process will not produce arbitrarily costly networks. Second, SGTC selects the Pareto efficient topology of minimum cost as its output.

6. Conclusions

We introduced the spectral gap-based topology control (SGTC) algorithm for wireless backhaul networks that uses simulated annealing guided by the value of the Laplacian Spectral Gap (LSG) to look for expander-like graphs, which are sparse graphs with strong connectivity properties such as small diameter, large value of the cardinality of its global minimum cut-set, and high shortest-path diversity. These are desirable properties for backhaul networks composed of Macro Base Stations and Small Cells because sparse topologies require less energy to establish and maintain their links, the diameter of a network impacts the upper bound of the end-to-end delay, the value of the cardinality of the global minimum cut-set determines the network robustness against link failures, and the shortest-path diversity promotes seamless traffic offloading from the MBSs to the Small Cells.

We presented network entropy as a measure of shortest-path diversity, which determines the amount of information about how data traffic is distributed across a particular network, where high values of network entropy indicate that data traffic will be evenly distributed across the network.

A series of experiments confirmed that the three connectivity metrics—diameter, robustness, and network entropy—improve as the value of the LSG increases, notably without requiring a significant increase in the number of links. This trend becomes more pronounced as the radio range of the stations increases because it increases the size of the space of feasible solutions. Our experimental results also showed that the topologies produced by SGTC are superior to those provided by a traditional Voronoi-based algorithm and that carefully placing the MBSs can improve the network robustness.

Future work includes conducting analytical and simulation-based analyses to determine the impact of expander-like topologies on the performance of upper-layer network functions, such as channel access and routing. We also plan to extend our algorithm to dynamically adapt the network’s topology to respond to the instantaneous traffic conditions. This is particularly important in the context of modern and future Internet applications where data traffic is bursty in nature, with large periods of low or no activity followed by sudden surges of high-intensity traffic.