Mathematical Models for Coverage with Star Tree Backbone Topology for 5G Millimeter Waves Networks

Abstract

This paper proposes mathematical optimization models for solving the network planning problem using millimeter wave technology for 5G wireless communications networks. To this end, it is assumed that a set of users, $M=\{1,\dots ,m\}$, and a set of base stations, $N=\{1,\dots ,n\}$, are deployed randomly in a square area. In particular, the base stations should be connected, forming a star backbone so that users can connect to their nearest active base stations forming the backbone where the connections are symmetric. In particular, the first two models maximize the number of users connected to the backbone and minimize the distance costs of connecting users to the base stations, and distances of connecting the base stations themselves. Similarly, the last two models maximize and minimize the same objectives and the number of base stations to be activated to form the star backbone. Each user is allowed to connect to a unique active base station. In general, the millimeter wave technology presents a high path loss. Consequently, the transmission distances should be no larger than 300 m at most for different radial transmissions. Thus, a direct line of sight between users and base stations is assumed. Finally, we propose local search-based algorithms that allow finding near-optimal solutions for all our tested instances. Our numerical results indicate that we can solve network instances optimally with up to $k=100$, $n=200$, and $m=5000$ users.

1. Introduction

The evolution of wireless communications has gone through several generations. In each novel generation, transformative advancements have been introduced. The first generation, 1G, appeared in the late 1970s and early 1980s, providing analog voice communication with a large transmission radius of several kilometers. However, 1G suffered from minimal security, interference, and pure voice utility. In the 1990s, 2G emerged as a digital revolution marked by the introduction of the Global System for Mobile Communications (GSMC), improving voice quality and encryption, and also enabling novel features like the Short Message Service (SMS). Smaller cell sizes were able to enhance the capacities, leading to the third generation (3G) in the early 2000s. Subsequently, with 3G, the mobile internet and video calling became the mainstream, supported by the Universal Mobile Telecommunications System (UMTS). Despite its data-centric advances, managing higher interference due to reduced cell sizes was still a challenge. Around 2010, 4G brought in the broadband era, offering internet speeds of up to 1 Gbps, thanks to Long-Term Evolution (LTE) technology. Later, 4G supported video streaming and cloud computing while using smart systems to save energy and reduce interference. In the late 2010s and early 2020s, 5G was introduced, bringing faster internet, reliable low-latency connections for critical tasks, and support for the Internet of Things (IoT) and smart cities. It uses smaller coverage areas, like mmWave, needing many closely spaced towers. Looking to the future, 6G aims to create smarter networks using Artificial intelligence (AI), super-fast terahertz communication, eco-friendly technologies, and immersive experiences like the holographic internet, enabling a highly connected and intelligent world. In particular, the yet development of 5G and 5G+ requires significant infrastructure to be complete [1].

It can be observed that 5G technology allows mobile users an enhanced service experience compared with earlier generations of cellular and coverage networks. In addition, the number of devices connected to the Internet has been growing notoriously within the last few decades, resulting in challenging scenarios to deal with the ever-increasing data traffic. Additionally, there is a growing demand related to the bit rates supporting applications that require higher bandwidths by the Internet of Things (IoT) too [2,3,4]. As such, millimeter wave (mmWave) technology emerges as a good candidate to make it possible to connect billions of devices and to create new and innovative applications [5,6]. Examples of new applications include domains of mobile health, manufacturing and entertainment, education, smart grids, autonomous-driving cars, smart cities and homes, aerospace, ocean exploration, emergency response, and mobile platforms, to name a few [7]. This technology offers high-speed data transfer and supports advanced applications, thanks to its wide bandwidth and small antenna size. Unfortunately, the transmission radius of mmWaves BSs is not very long in distance yet, and the technology has other challenges such as high signal loss and difficulty generating signals at very high frequencies, like 96 GHz, using electronic components. Consequently, the research community is still exploring optical methods, such as combining light signals, to generate mmWave frequencies more efficiently. For a deeper understanding of this technology, we refer the reader to the works by [8,9].

From the literature, transmission distances with up to a radius of approximately 200 m or up to 300 m while using 5G mmWave technology have been reported [10]. Consequently, the experimental evidence suggests that deploying base stations (BSs) with a radius of at least 200 m can solve the coverage problem in outdoor scenarios utilizing direct line-of-sight communication. However, opting for smaller radius values would certainly increase the number of BSs to cover a complete user area [7,10]. We argue that the density of nodes needed for 5G and 6G systems depends on the area and data needs. For 5G, in urban areas, one might need about 10 to 100 small cells per square kilometer, whereas for 6G one would need even more data and faster speeds. The latter could raise the number from 1000 to 10,000 small cells per square kilometer in crowded areas. To support this high density, technologies like UDWDM-PON can help by managing data transmission efficiently between nodes, making it easier to handle a large amount of data traffic in these networks [11,12].

In this paper, we are concerned with the network planning problem of 5G mmWave networks mentioned above while achieving a minimum star backbone connectivity cost and maximizing user coverage. For this purpose, let $G=(N,E)$ denote a network graph composed of a set of $N=\{1,\dots ,n\}$ possible locations for a subset of BSs to be activated, and a set $E=\left\{\right\{i,j\},i,j\in N,(i<j\left)\right\}$ denoting the set of symmetric connection links between these BS nodes. Consequently, it is assumed that a wired or a wireless star backbone network can be represented by graph G. We also aim that the coverage of a set of users $M=\{1,\dots ,m\}$ has to be maximally covered. Due to the above-mentioned problems of radius transmission, our paper contribution is thus to propose four mathematical optimization models that allow maximizing user coverage while simultaneously minimizing the connectivity costs of users to the star topology, the connection of the star topology nodes themselves, and the number of base stations in the last two models. The first two models impose a constraint in which a predefined number of nodes, k, out of n must be chosen to form the star topology. In particular, two of the proposed models are mixed-integer linear programming (MILP) models, whereas the remaining ones are mixed-integer quadratic programming (MIQP) models. Our paper assumes that the network nodes remain stationary, as in most sensor networks. For example, in catastrophic scenarios, installing a wireless network as fast as possible is sometimes required. Naturally, if the network cannot reach some users or a particular one, they or he will not be covered. This can happen in rural areas for instance. Notice that creating star networks can be of relevant importance for several reasons depending on the context in which they are used. Some of the main advantages can be enumerated as the simplicity and ease of configuration, simplicity during implementation or maintenance, ease of fault detection and isolation, scalability, centralized control, performance and efficiency, and specific applications such as cellular base stations or drones acting as base stations, to name a few.

Generally, we represent a wireless network employing a graph network. It is remarked that all our graph instances are solved with near-optimal gaps using the Gurobi solver that allows for solving MILP and MIQP models [13]. To this end, we limit the maximum CPU time for the Gurobi solver to one hour for solving each instance. Finally, two efficient local search-based algorithms are proposed that allow for finding tight solutions in significantly low CPU time compared with the proposed models, for small- or large-sized instances of the problem. To the best of our knowledge, the proposed models and solution approaches are new to the literature and therefore complement positively the existing literature to deal with the network design planning problem from a management point of view. Lastly, we mention that our proposed models are able to cover all users for most tested instances. Total coverage is achieved using several candidate site locations for the mmWaves BSs antennas in the star topology network. Notice that a direct comparison with state-of-the-art models is hard since our models use the star topology configuration, which has not been addressed in the literature. Thus, a direct comparison with other methods is not easy as the modeling and algorithmic approaches are new. From the literature, only a few articles were found to be similar to the connectivity problem we are dealing with. Moreover, two of our proposed models allow us to determine the optimal number of BSs to be active to form the backbone network structure. The latter considers the characteristics of 5G mmWave technology. It is worth noting that the literature has not also considered the aspect of wireless networks within random deployments, as is the case of a sensor network. Note that the reason for using the Gurobi solver is justified by its exceptional uniqueness and potent algorithmic capabilities, as evidenced by its success in tackling challenging optimization problems in the literature [13]. Finally, this work corresponds to a larger version of the article presented at the IEEE conference [14].

The organization of the paper is as follows. In Section 2, some related literature work is presented and discussed. Works similar to the optimal network planning problem considered in our article are reviewed. Then, in Section 3, the network planning optimization problem is briefly explained, and each proposed mathematical formulation is presented and explained in detail. Then, in Section 4, the two proposed algorithms are presented. Next, in Section 5, we conduct extensive numerical experiments, presenting and discussing the results obtained from the proposed models and algorithms. Finally, in Section 6, we conclude the article and discuss insights for potential future research.

2. Related Work

The network planning problem of locating base stations (BSs) using 5G mmWave technology has not yet been addressed in depth in the literature, either for outdoor or indoor scenarios. In this paper, we focus on the outdoor scenario. Some work similar to our problem published so far can be described as follows. In [14], the authors propose two mathematical optimization models to solve problems in the network planning problem of 5G wireless communications networks using the mmWave frequency spectrum. The first model allows for maximizing the number of covered users, minimizing the distances between each pair of BSs and the distances required to connect each user to a unique BS. In this model, the number of BSs is assumed to be fixed. The second model allows for optimizing the same objective function as in the first model with the additional term used to minimize the total number of BSs. The authors also assume the existence of direct line-of-sight (LOS) for the pair of links between users and base stations. Finally, they consider 10 instances with a maximum of 50 candidate location sites for the BSs and a maximum of 300 users for radial transmission distances of 150 and 200 m. Their numerical results show that the proposed models could solve all the instances to optimality in a short CPU time. Consequently, the models proposed in our article now change in structure significantly to deal with the network planning problem from a management point of view, as in reference [7].

The authors in reference [15] state that 5G is the wireless network technology to achieve significantly higher speeds, and they expect that every new generation of wireless networks should be even faster in terms of data throughput than previous technologies. Then, they describe the millimeter wave technology as a new candidate that allows a very high-frequency spectrum, upwards of 20 GHz to nearly 96 GHz. However, the higher the frequency of any wave is, the shorter is the transmission range [15]. Thus, to take advantage of 5G, they clarify that one needs a 5G device with an appropriate antenna and a dense network of 5G BSs. Consequently, they deal with the process of planning and deployment of 5G networks, emphasizing the planning process to optimize the locations and minimize the number of BSs in a selected geographical area using a genetic algorithm [16,17]. Thus, they consider a Multi-Objective Genetic Algorithm incorporating multiple factors like cost, coverage, and interference in its fitness function to reach a near-global optimal solution for the problem.

In reference [18], the authors present research focused on optimizing 5G base station deployment and visualization, addressing the escalating demands for high data rates and low latency. Their paper compares the effectiveness of different meta-heuristics such as Genetic Algorithm, Particle Swarm Optimization, Simulated Annealing, and Grey Wolf Optimizer for various deployment scenarios, which allow adopting non-standalone architectures. Their optimization process approach eliminates redundant base stations to enhance efficiency. Finally, their numerical results indicate that the Particle Swarm and the Genetic Algorithm achieve better balances between coverage and capacities. Another interesting work is the one published in reference [19]. Here, the authors deal with proper planning procedures to provide cost-effective and quality telecommunication services. They focus on planning 5G network deployment in two frequency ranges, 3.5 GHz and 28 GHz, using a mixed cell structure. Meta-heuristic approaches such as Grey Wolf Optimization, Sparrow Search Algorithm, Whale Optimization Algorithm, Marine Predator Algorithm, Particle Swarm Optimization, and Ant Lion Optimization approaches for optimizing the locations of remote radio units are considered. Their comparative numerical analysis shows that the proposed network is efficient in providing an average data rate of 50 Mbps while meeting the coverage requirements of at least 98%.

Similarly, in reference [20], the authors reduce power consumption as a pivotal challenge in 5G millimeter wave networks due to the density of the base stations. The paper focuses on the joint user and power allocation problem in 5G mmWave networks, aiming to minimize power consumption while maintaining the user Quality of Service (QoS), considering the BSs switching on/off strategy. The authors formulate the problem as an integer linear program to obtain the optimal solution. They further propose a Genetic Algorithm-based heuristic strategy. Finally, extensive simulations are conducted to evaluate the performance of the Genetic Algorithm. The obtained results demonstrate the efficiency of the proposed GA in providing close to optimal solutions. Finally, they conclude the effectiveness in residential and office areas in terms of energy savings.

Ultimately, to close this section, we observe that the network planning problem in the literature has not been covered from a management point of view with sufficient detail yet. Moreover, we observed only a few works directly related to the network planning problem using 5G mmWave technology. Thus, it is expected that this work contributes to a new dimension of the problem, that is, taking into account optimal connectivity and star topology configuration using 5G mmWave technology.

Lastly, for a more panoramic view related to wireless network studies, the reader is referred to the recent papers by [21,22,23] and to references therein.

3. System Description and Mathematical Formulations

In this section, we provide a brief system description of the network planning problem we are dealing with from a management point of view. For this purpose, Figure 1 and Figure 2 are discussed and explained. Subsequently, each proposed model is presented and described in logical order.

3.1. System Description

It is considered a random deployment of possible location sites for a set of $N=\{1,\dots ,n\}$ BSs, from which k out of n must form a star backbone. We also consider a set of $M=\{1,\dots ,m\}$ users that should be covered, i.e., connected to their nearest BSs according to a radial transmission radius of the BSs. To be more precise, in  Figure 1 and Figure 2 we present two feasible solutions for the optimization problem we are dealing with. In particular, in  Figure 1, we assume that the network can be represented by the graph $G=(N,E)$, where E denotes the set of links for an output solution of the problem. This network graph is composed of ten nodes and 30 users. Notice that the black node is the sink of the star topology and the star is connected with blue edges. Next, we observe that each user is connected to its nearest BS with a green-colored edge. Finally, we see that, in this case, no element of the set of user nodes is isolated, meaning that all of them are fully covered. Lastly, and for the sake of clarity, we mention that for this example we have intentionally coincided the number of BSs, k, to be activated with the total candidate sites, n.

This is the aim of the first two proposed mathematical formulations. However, in the last two models, we further consider the situation in which the proposed models also determine the minimum number of base stations required to cover the maximum number of users at minimum connectivity costs. The four proposed models are constructed for a star network configuration.

Similarly, in  Figure 2, we arbitrarily do the same to avoid confusion about a feasible solution, although in this case the network is larger and composed of 50 BSs and 1000 users. The rest of the explanations are the same as for Figure 1.

Next, we proceed with the proposed mathematical formulations for the network planning problem. We present each of them and explain them in detail, together with their correctness.

3.2. Mathematical Formulations

The first mixed-integer linear programming formulation to tackle the network planning problem with star topology can be constructed as follows. First, notice that the domain variables in constraints (9) are $x\in {\{0,1\}}^m$, $y\in {\{0,1\}}^n$, $z\in {\{0,1\}}^{nm}$, $\alpha \in {\{0,1\}}^n$, and $\varphi \in {\{0,1\}}^{n^2-n}$. In turn, variable $x_j$ equals one if user $j\in M$ is attended to, and equals zero otherwise. Next, $y_i$ with $i\in N$ equals one if BS i is active. Similarly, variable $z_{ij}$ for all $i\in N$, $j\in M$ equals one if BS i connects to user j. Also, variable ${\alpha }_i$$i\in N$ equals one if BS i is the sink black node of the star. Finally, variable ${\varphi }_{ij}$$i,j\in N,(i\ne j)$ equals one if BS i is connected to BS j, forming the star. Thus, the model is as follows

$$\begin{array}{ccc}\hfill M_1:\underset{\left\{x,y,z,\alpha ,\varphi \right\}}{max}& & \sum _{j\in M}{x}_j-\sum _{\begin{array}{c}i,j\in N\\ (i\ne j)\end{array}}{D}_{ij}{\varphi }_{ij}-\sum _{\begin{array}{c}i\in N\\ j\in M\end{array}}{W}_{ij}{z}_{ij}\hfill \end{array}$$

(1)

$$\begin{array}{ccc}\hfill \mathrm{st}:& & \sum _{i\in N}{C}_{ij}{y}_i\ge x_j,\forall j\in M\hfill \end{array}$$

(2)

$$\begin{array}{ccc}& & \sum _{i\in N}{C}_{ij}{z}_{ij}=x_j,\forall j\in M\hfill \end{array}$$

(3)

$$\begin{array}{ccc}& & \sum _{i\in N}{y}_i=k\hfill \end{array}$$

(4)

$$\begin{array}{ccc}& & {\alpha }_i\le y_i,\forall i\in N\hfill \end{array}$$

(5)

$$\begin{array}{ccc}& & \sum _{i\in N}{\alpha }_i=1\hfill \end{array}$$

(6)

$$\begin{array}{ccc}& & {\alpha }_i+y_j\le 1+{\varphi }_{ij},\forall i,j\in N,(i\ne j)\hfill \end{array}$$

(7)

$$\begin{array}{ccc}& & {\varphi }_{ij}+{\varphi }_{ji}\le 1,\forall i,j\in N,(i\ne j)\hfill \end{array}$$

(8)

$$\begin{array}{ccc}& & x\in {\{0,1\}}^m,y\in {\{0,1\}}^n,z\in {\{0,1\}}^{nm}\hfill \end{array}$$

(9)

$$\begin{array}{ccc}& & \alpha \in {\{0,1\}}^n,\varphi \in {\{0,1\}}^{n^2-n}\hfill \end{array}$$

(10)

Proposition 1.

Model $M_1$ allows for finding an optimal solution for the network planning problem while forming a star backbone with k out n nodes with maximum objective value while maximizing the number of users, and minimizing the connectivity of the star backbone and the connection of users to their nearest k activated BSs.

Proof. 

To allow a correct star configuration and users connected as above mentioned, constraints (2) ensure that user j for all $j\in M$ can be reached by at least one of the BSs; for this purpose, matrix $C=\left(C_{ij}\right)$ for all $i\in N,j\in M$ is a zero–one matrix. If an entry equals one, it means that BS i reaches user j; it equals zero otherwise. Next, constraints (3) impose that each user should be connected to a unique BS. The next constraint (4) guarantees that exactly k BSs are actively forming the star. Subsequently, constraints (5) indicate that, for all $i\in N$, if a BS acts as a sink for the star, it should be one of the active BSs. The next constraint (6) and the previous constraint ensure that only one sink is allowed for the star configuration. To form the star, constraints (7) for all $i,j\in N,(i\ne j)$ ensure that ${\alpha }_i+y_j\le 1+{\varphi }_{ij}$. Observe that, in the case ${\alpha }_i=0$ and $y_j=0$, the constraint is redundant. Next, in the case ${\alpha }_i=1$ and $y_j=0$, the constraint is also redundant. However, in the case of both ${\alpha }_i=1$ and $y_j=1$, then a connection must exist between BSs i and j, forcing variable ${\varphi }_{ij}$ to be equal to one. Notice that variable ${\varphi }_{ij}$ is being minimized. The connection must exist as it means BS i acts as the sink node, whilst node j is an active BS, being part of the solution star. Finally, constraints (8) ensure that only one link must be considered in the connection of constraints (7) for all $i,j\in N,(i\ne j)$. The latter is valid since the input matrix $D=\left(D_{ij}\right)$ for all $i,j\in N$, $\left(ij\right)$ is a symmetric distance matrix. Lastly, matrix $W=\left(W_{ij}\right)$ for all $i\in N,j\in M$ is also an Euclidean distance matrix between BS i and user j.    □

Corollary 1.

The following quadratic formulation, $M_2$, allows for finding an optimal solution for the network planning problem that provides the same optimal objective value of model $M_1$, since both models are equivalent. We prove the equivalence as follows:

$$\begin{array}{ccc}\hfill M_2:\underset{\left\{x,y,z,\alpha ,\varphi \right\}}{max}& & \sum _{j\in M}{x}_j-\sum _{\begin{array}{c}i,j\in N\\ (i\ne j)\end{array}}{D}_{ij}{\varphi }_{ij}-\sum _{\begin{array}{c}i\in N\\ j\in M\end{array}}{W}_{ij}{z}_{ij}\hfill \\ \hfill st:& & \sum _{i\in N}{C}_{ij}{y}_i\ge x_j,\forall j\in M\hfill \\ & & \sum _{i\in N}{C}_{ij}{z}_{ij}=x_j,\forall j\in M\hfill \\ & & \sum _{i\in N}{y}_i=k\hfill \\ & & {\alpha }_i\le y_i,\forall i\in N\hfill \\ & & \sum _{i\in N}{\alpha }_i=1\hfill \\ & & 2{\alpha }_i{y}_j\le 1+{\varphi }_{ij},\forall i,j\in N,(i\ne j)\hfill \\ & & {\varphi }_{ij}+{\varphi }_{ji}\le 1,\forall i,j\in N,(i\ne j)\hfill \\ & & x\in {\{0,1\}}^m,y\in {\{0,1\}}^n,z\in {\{0,1\}}^{nm}\hfill \\ & & \alpha \in {\{0,1\}}^n,\varphi \in {\{0,1\}}^{n^2-n}\hfill \end{array}$$

(11)

Proof. 

The proof is immediate. Notice that the constraints (7) in $M_1$ ensure that ${\alpha }_i+y_j\le 1+{\varphi }_{ij}$, for all $i,j\in N,(i\ne j)$. The statement is thus to prove that the latter constraints are equivalent to constraints (11), i.e., $2{\alpha }_i{y}_j\le 1+{\varphi }_{ij},\forall i,j\in N,(i\ne j)$. These latter constraints are equivalent since the only case in which the product ${\alpha }_i{y}_j$ equals one is when both ${\alpha }_i=1$ and $y_j=1$, thus forcing the variables ${\varphi }_{ij},\forall i,j\in N,(i\ne j)$ to be equal to one.    □

Notice that this small change in model $M_2$ transforms the model into a mixed-integer quadratic problem different from $M_1$, which is a mixed-integer linear one. It turns out that the solver will show a different performance in terms of CPU times, best objective values, and number of branch and bound nodes when solving both $M_1$ and $M_2$ [13].

Another model that consists of a variant of model $M_1$ is $M_3$. In $M_3$, notice that we do not impose that k BSs must be active to form the star topology out of the n total number of BSs. Instead, we remove the constraint (4) from $M_1$ and add the left-hand side of this constraint to the objective function in $M_3$ with a minus sign. This is done to minimize the number of BSs for the star. Thus, the new model can be written as

$$\begin{array}{ccc}\hfill M_3:\underset{\left\{x,y,z,\alpha ,\varphi \right\}}{max}& & \sum _{j\in M}{x}_j-\sum _{\begin{array}{c}i,j\in N\\ (i\ne j)\end{array}}{D}_{ij}{\varphi }_{ij}-\sum _{\begin{array}{c}i\in N\\ j\in M\end{array}}{W}_{ij}{z}_{ij}-\sum _{i\in N}{y}_i\hfill \\ \hfill \mathrm{st}:& & \sum _{i\in N}{C}_{ij}{y}_i\ge x_j,\forall j\in M\hfill \\ & & \sum _{i\in N}{C}_{ij}{z}_{ij}=x_j,\forall j\in M\hfill \\ & & {\alpha }_i\le y_i,\forall i\in N\hfill \\ & & \sum _{i\in N}{\alpha }_i=1\hfill \\ & & {\alpha }_i+y_j\le 1+{\varphi }_{ij},\forall i,j\in N,(i\ne j)\hfill \\ & & {\varphi }_{ij}+{\varphi }_{ji}\le 1,\forall i,j\in N,(i\ne j)\hfill \\ & & x\in {\{0,1\}}^m,y\in {\{0,1\}}^n,z\in {\{0,1\}}^{nm}\hfill \\ & & \alpha \in {\{0,1\}}^n,\varphi \in {\{0,1\}}^{n^2-n}\hfill \end{array}$$

(12)

We do not explain each of the constraints of model $M_3$ as they are equivalent to $M_1$. Similarly, we do the same for the quadratic model $M_2$ to obtain model $M_4$, stated as follows

$$\begin{array}{ccc}\hfill M_4:\underset{\left\{x,y,z,\alpha ,\varphi \right\}}{max}& & \sum _{j\in M}{x}_j-\sum _{\begin{array}{c}i,j\in N\\ (i\ne j)\end{array}}{D}_{ij}{\varphi }_{ij}-\sum _{\begin{array}{c}i\in N\\ j\in M\end{array}}{W}_{ij}{z}_{ij}-\sum _{i\in N}{y}_i\hfill \\ \hfill \mathrm{st}:& & \sum _{i\in N}{C}_{ij}{y}_i\ge x_j,\forall j\in M\hfill \\ & & \sum _{i\in N}{C}_{ij}{z}_{ij}=x_j,\forall j\in M\hfill \\ & & {\alpha }_i\le y_i,\forall i\in N\hfill \\ & & \sum _{i\in N}{\alpha }_i=1\hfill \\ & & 2{\alpha }_i{y}_j\le 1+{\varphi }_{ij},\forall i,j\in N,(i\ne j)\hfill \\ & & {\varphi }_{ij}+{\varphi }_{ji}\le 1,\forall i,j\in N,(i\ne j)\hfill \\ & & x\in {\{0,1\}}^m,y\in {\{0,1\}}^n,z\in {\{0,1\}}^{nm}\hfill \\ & & \alpha \in {\{0,1\}}^n,\varphi \in {\{0,1\}}^{n^2-n}\hfill \end{array}$$

Finally, we do not explain each of the constraints of model $M_4$ either since they are equivalent to model $M_2$.

4. Algorithmic Approaches

This section presents Algorithm 1 and explains it line by line for solving the first two optimization models, $M_1$ and $M_2$. Recall that these models impose that k out of the n BSs should be active to form the star topology. Then, a second procedure in Algorithm 2, a variant of the first one, is presented for finding near-optimal solutions, explained, and discussed in detail for models $M_3$ and $M_4$.

Algorithm 1: Proposed Local Search Heuristic Algorithm for models $M_1$ and $M_2$.

Algorithm 2: Proposed Local Search Heuristic Algorithm for models $M_3$ and $M_4$.

4.1. A Local Search-Based Heuristic for Finding Feasible Solutions for $M_1$ and $M_2$

The procedure for solving $M_1$ and $M_2$ is depicted in Algorithm 1. It works as follows. It requires as input an instance of model $M_1$ (or $M_2$) for the network planning problem and returns a feasible solution to the problem and its objective function value. The algorithm initializes arbitrarily the variables $MaxTime=value$ and $MaxGlobal=-\infty$. The first parameter, $MaxTime$, is set to an arbitrary amount of time, while the second one, $MaxGlobal$, saves within each iteration of the procedure the best objective value found during the algorithm’s execution time.

Then, it randomly generates a permutation of the index set of N and splits it into two lists, $L_1$ and $L_2$, with dimensions k and $n-k$, respectively. Subsequently, it enters into a while loop using the condition that the current time minus the starting time must be larger than the $MaxTime$ parameter is set to. The latter is controlled with the variables $StarTime$ and $EndTime$. Inside the loop, the number of iterations is incremented and generates a list, L, with a random size, v, a number between the integer values a and b ($a<b$). List L is composed of numbers ranging from one to v, i.e., $[1,\dots ,v]$. Subsequently, for each value, we find a random index in $L_1$ and another in $L_2$ and interchange the content values of these positions between lists $L_1$ and $L_2$. Once this is performed, the shortest star with values in $L_1$ is evaluated, forcing each node to act as a potential sink node. Next, each covered user is connected to its nearest BSs in $L_1$. Finally, the solution obtained according to the objective function of $M_1$ (or $M_2$) is evaluated and denoted by $Obj$. Afterward, we ask if the new objective value, $Obj$, is greater than or equal to $MaxGlobal$. If so, we save the best new solution obtained and restart the CPU time variables $StarTime$ and $EndTime$. The latter is performed to provide Algorithm 1 with a new amount of $MaxTime$ units of time to be running to find even better solutions. Lastly, the algorithm returns the best feasible solution obtained and its objective function value.

4.2. A Local Search-Based Heuristic for Finding Feasible Solutions for $M_3$ and $M_4$

The procedure for solving $M_3$ and $M_4$ is depicted in Algorithm 2. It works similarly to Algorithm 1 as follows. It requires as input an instance of model $M_3$ (or $M_4$) for the network planning problem and returns a feasible solution to the problem and its objective function value. For the sake of space, we omit the same explanations and focus on the main differences compared with Algorithm 1.

The main difference is that, when performing the inner for each (·) loop inside the while loop, we randomly generate a value, v, to create a list containing elements from one to v that will be used to perform a predefined number of interchanges between lists $L_1$ and $L_2$. Subsequently, we find randomly an index number in $L_1$ or $L_2$, taking care that both lists contain at least two elements. If the index number is from $L_1$, we remove the element from $L_1$ in the position index and add it to $L_2$. Otherwise, if the index number is from $L_2$, we remove from $L_2$ the element in the position index and add it to $L_1$. The rest is analogous to Algorithm 1. Notice that this part of Algorithm 2 is because now the size of lists $L_1$ and $L_2$ is not fixed within each iteration of Algorithm 2.

5. Results and Discussion

In this section, substantial numerical results are obtained to compare the performances of models $M_1$, $M_2$, $M_2$, $M_4$, and the proposed Algorithms 1 and 2. A Python code is implemented using the Gurobi solver [13] with default options. Only the maximum CPU time is fixed to one hour of CPU time. Thus, if a solution reports its objective function value in less than 3600 s, it means the solver is reporting the optimal solution. Otherwise, it corresponds to the best solution found in one hour. Notice that the optimization models we are dealing with belong to the NP-hard complexity class due to their discrete nature. The numerical experiments are performed on a 12th Gen Intel(R) Core(TM) i7-12700H, 64 bits x64, with 2.30 GHz and 16.0 GB of RAM. We also assume that all the active BSs can be connected using cables or wirelessly. The dimensions of the tested instances are $k=\{50,70,100\}$, $n=\left\{200\right\}$, and $m=\{1000,2000,3000,4000,5000\}$. Also, it is assumed that each user can be connected to an active BS if and only if located inside a radial transmission range of at most $\{150,200,300\}$ meters. We further mention that each coordinate for the nodes is generated within a square area of 1 km² according to a uniform distribution function. Each entry of matrix $D=\left(D_{ij}\right)$$i,j\in N$ denotes the distance between BSs. Similarly, each entry in matrix $W=\left(W_{ij}\right)$, $i\in N,j\in M$ denotes the distance between BS i and user j. Finally, matrix $C=\left(C_{ij}\right)$ is a zero–one matrix with value one if BS i reaches user j within its radial transmission radius. Otherwise, it has a zero value.

In

Table 1. Numerical results obtained with models $M_1$ and $M_2$ using a radial transmission distance of 150 m.

#	k	n	m	${\mathit{M}}_1$					${\mathit{M}}_2$
				Best Sol.	B&B	CPU (s)	Gap (%)	# of Users	Best Sol.	B&B	CPU (s)	Gap (%)	# of Users
1	50	200	1000	951.4	569	311.26	0.0	1000	951.4	773	176.34	0.0	1000
2	50	200	2000	1900.29	9900	1274.76	0.0	1986	1900.29	7047	1066.56	0.0	1986
3	50	200	3000	2877.27	3110	529.79	0.0	3000	2877.27	2562	213.87	0.0	3000
4	50	200	4000	3839.63	2499	322.63	0.0	4000	3839.63	2045	348.58	0.0	4000
5	50	200	5000	4812.77	663	224.18	0.0	5000	4812.77	2609	359.9	0.0	5000
6	70	200	1000	945.82	685	281.64	0.0	1000	945.82	440	124.55	0.0	1000
7	70	200	2000	1905.98	3515	313.95	0.0	1999	1905.98	1804	222.37	0.0	1999
8	70	200	3000	2877.38	514	192.26	0.0	3000	2877.38	558	169.77	0.0	3000
9	70	200	4000	3833.49	1245	275.75	0.0	4000	3833.49	2824	500.58	0.0	4000
10	70	200	5000	4796.03	932	231.38	0.0	5000	4796.03	678	209.82	0.0	5000
11	100	200	1000	935.18	1	38.55	0.0	1000	935.19	403	74.4	0.0	1000
12	100	200	2000	1898.22	283	79.47	0.0	2000	1898.22	468	89.96	0.0	2000
13	100	200	3000	2863.93	718	97.86	0.0	3000	2863.93	8519	2114.73	0.0	3000
14	100	200	4000	3827.04	898	202.15	0.0	4000	3827.04	555	99.99	0.0	4000
15	100	200	5000	4790.66	385	112.47	0.0	5000	4790.66	355	113.8	0.0	5000

,

Table 2. Numerical results obtained with models $M_1$ and $M_2$ using a radial transmission distance of 200 m.

#	k	n	m	${\mathit{M}}_1$					${\mathit{M}}_2$
				Best Sol.	B&B	CPU (s)	Mipgap (%)	# of Users	Best Sol.	B&B	CPU (s)	Mipgap (%)	# of Users
1	50	200	1000	953.65	1247	194.58	0.0	1000	953.65	507	97.42	0.0	1000
2	50	200	2000	1911.54	963	113.2	0.0	1997	1911.54	1833	123.1	0.0	1997
3	50	200	3000	2879.55	958	131.12	0.0	3000	2879.55	487	94.66	0.0	3000
4	50	200	4000	3842.21	410	96.0	0.0	4000	3842.21	649	120.04	0.0	4000
5	50	200	5000	4814.53	453	102.93	0.0	5000	4814.53	391	78.25	0.0	5000
6	70	200	1000	947.4	1	29.54	0.0	1000	947.42	377	170.17	0.0	1000
7	70	200	2000	1908.57	344	72.44	0.0	2000	1908.57	1900	130.24	0.0	2000
8	70	200	3000	2878.9	336	77.1	0.0	3000	2878.9	1769	123.69	0.0	3000
9	70	200	4000	3835.21	825	136.29	0.0	4000	3835.21	852	99.58	0.0	4000
10	70	200	5000	4797.58	348	86.27	0.0	5000	4797.58	781	107.43	0.0	5000
11	100	200	1000	936.21	1	39.34	0.0	1000	936.21	316	60.89	0.0	1000
12	100	200	2000	1899.01	356	57.46	0.0	2000	1899.01	388	60.13	0.0	2000
13	100	200	3000	2865.16	321	66.09	0.0	3000	2865.16	565	79.02	0.0	3000
14	100	200	4000	3828.28	437	84.81	0.0	4000	3828.28	363	74.6	0.0	4000
15	100	200	5000	4791.75	381	71.87	0.0	5000	4791.75	392	76.09	0.0	5000

and

Table 3. Numerical results obtained with models $M_1$ and $M_2$ using a radial transmission distance of 300 m.

#	k	n	m	${\mathit{M}}_1$					${\mathit{M}}_2$
				Best Sol.	B&B	CPU (s)	Mipgap (%)	# of Users	Best Sol.	B&B	CPU (s)	Mipgap (%)	# of Users
1	50	200	1000	954.83	1	59.12	0.0	1000	954.83	3043	157.07	0.0	1000
2	50	200	2000	1915.17	2322	126.56	0.0	2000	1915.17	813	82.13	0.0	2000
3	50	200	3000	2880.92	2594	160.62	0.0	3000	2880.92	1301	118.05	0.0	3000
4	50	200	4000	3843.63	1389	106.06	0.0	4000	3843.63	5901	207.83	0.0	4000
5	50	200	5000	4815.78	1647	124.92	0.0	5000	4815.78	678	100.77	0.0	5000
6	70	200	1000	948.55	1	69.71	0.0	1000	948.55	869	167.56	0.0	1000
7	70	200	2000	1909.89	790	86.43	0.0	2000	1909.89	903	67.44	0.0	2000
8	70	200	3000	2880.05	1261	139.72	0.0	3000	2880.05	1155	95.08	0.0	3000
9	70	200	4000	3836.09	351	89.91	0.0	4000	3836.09	1192	96.04	0.0	4000
10	70	200	5000	4798.7	1224	147.49	0.0	5000	4798.7	465	69.97	0.0	5000
11	100	200	1000	936.92	1	49.53	0.0	1000	936.92	277	54.82	0.0	1000
12	100	200	2000	1899.73	332	55.11	0.0	2000	1899.73	1636	112.5	0.0	2000
13	100	200	3000	2865.93	341	69.19	0.0	3000	2865.93	452	82.02	0.0	3000
14	100	200	4000	3828.97	339	78.65	0.0	4000	3828.97	426	84.95	0.0	4000
15	100	200	5000	4792.57	301	73.1	0.0	5000	4792.57	375	77.46	0.0	5000

the legends are as follows. Column 1 presents the instance number. Columns 2, 3, and 4 correspond to the parameter k in models $M_1$ and $M_2$, the number of candidate sites for the nodes forming the star backbone network, and the number of users to be attended. Next, in columns 5–9 and 10–14, we report the best or optimal objective function value, the number of branch and bound nodes, the CPU time in seconds, the Mipgaps in percentages given by Gurobi, and the number of users attended, respectively, by the two models $M_1$ and $M_2$. Table 1 reports numerical results for a radial transmission distance of 150 m. In Table 2 and Table 3, the numerical results are reported for radial transmissions of 200 and 300 m, respectively.

From these tables, we observe that all the solutions are the optimal ones. This is ensured by the Mipgaps when these are equal to zero. This parameter reported by the Gurobi solver is the difference between the relaxed solution and the integer one. Consequently, if it equals zero, the solution obtained is indeed the optimal one [13]. Next, we observe that these objective values are larger when using 300 m than 200 m, and even larger when using 150 m. Concerning the number of branch and bound nodes obtained, we appreciate that these values in the three tables are in the same order of magnitude. Regarding the CPU time in seconds in Table 1, Table 2 and Table 3, we observe that linear model $M_1$ exhibits a slightly better performance than quadratic model $M_2$. Finally, we see that almost all users are covered, as shown by the solutions obtained, in particular when using a radial transmission distance of 300 m in Table 3, although in Table 1 and Table 2 more than 99% of users are covered.

In

Table 4. Numerical results obtained with models $M_3$ and $M_4$ using a radial transmission distance of 150 m.

#	n	m	${\mathit{M}}_3$						${\mathit{M}}_4$
			Best Sol.	B&B	CPU (s)	Gap (%)	# of Users	# of BSs	Best Sol.	B&B	CPU (s)	Gap (%)	# of Users	# of BSs
1	200	1000	931.37	755	3600.3	0.42	1000	23	931.33	2566	3600.32	0.38	1000	23
2	200	2000	1880.93	2237	3600.29	0.06	1984	22	1880.93	2526	3600.38	0.06	1984	22
3	200	3000	2856.02	39,789	3600.92	0.22	2998	23	2856.02	39,983	3600.8	0.14	2998	23
4	200	4000	3818.93	3146	2379.22	0.0	4000	24	3818.93	2216	3218.11	0.0	4000	24
5	200	5000	4792.22	39,890	3601.6	0.1	5000	24	4792.22	39,257	3602.63	0.15	5000	24

,

Table 5. Numerical results obtained with models $M_3$ and $M_4$ using a radial transmission distance of 200 m.

#	n	m	${\mathit{M}}_3$						${\mathit{M}}_4$
			Best Sol.	B&B	CPU (s)	Gap (%)	# of Users	# of BSs	Best Sol.	B&B	CPU (s)	Gap (%)	# of Users	# of BSs
1	200	1000	945.75	39,268	3601.29	0.06	999	12	945.64	39,657	3607.87	0.27	1000	13
2	200	2000	1903.75	40,372	3608.11	0.12	1996	13	1903.75	38,996	3631.13	0.11	1996	13
3	200	3000	2871.13	40,872	3600.73	0.01	2999	13	2871.1	40,686	3600.71	0.01	2999	13
4	200	4000	3833.39	42,449	3601.18	0.05	4000	14	3833.39	40,446	3602.66	0.04	4000	14
5	200	5000	4806.72	38,596	3605.6	0.07	5000	14	4806.72	39,540	3601.37	0.07	5000	14

and

Table 6. Numerical results obtained with models $M_3$ and $M_4$ using a radial transmission distance of 300 m.

#	n	m	${\mathit{M}}_3$						${\mathit{M}}_4$
			Best Sol.	B&B	CPU (s)	Gap (%)	# of Users	# of BSs	Best Sol.	B&B	CPU (s)	Gap (%)	# of Users	# of BSs
1	200	1000	954.01	52,344	762.63	0.0	999	6	954.01	4086	652.62	0.0	999	6
2	200	2000	1915.35	34,452	791.63	0.0	2000	7	1915.35	39,196	757.76	0.0	2000	7
3	200	3000	2880.8	47,665	997.48	0.0	3000	7	2880.8	37,643	1056.65	0.0	3000	7
4	200	4000	3843.29	30,368	1245.66	0.0	4000	7	3843.29	34,779	1229.89	0.0	4000	7
5	200	5000	4816.49	17,977	1025.92	0.0	5000	7	4816.49	17,777	785.91	0.0	5000	7

, we report numerical results obtained with models $M_3$ and $M_4$ for radial transmission distances of 150, 200, and 300 ms. The legends of these three tables are again the same.

Notice that only the value of k is not present now because models $M_3$ and $M_4$ minimize the total number of BSs to be activated. Consequently, in columns 9 and 15, we report the number of BSs related to the solutions obtained for each row instance of the network planning problem for models $M_3$ and $M_4$, respectively.

From Table 4, Table 5 and Table 6, we first observe that the Mipgap values that are near to zero ensure that the solutions obtained are near-optimal. When the Mipgaps are zero, we ensure that the optimal solution for each row instance has been reached. Also, notice that in many cases, particularly in Table 4 and Table 5, we cannot solve optimally in one hour of CPU time the instances. This clearly shows that it is harder to solve $M_3$ and $M_4$ optimally than $M_1$ and $M_2$, i.e., these instances require a higher computational effort to certify optimality. Another interesting observation is that, independently of the transmission distance, most of the users are attended to by the BSs of the network output solutions. Finally, we see that the larger the transmission distances are, the lower is the number of BSs required to form the star backbone network.

To provide more insights regarding Algorithm 1 and model $M_1$, in Figure 3, Figure 4 and Figure 5 we report objective values, CPU time in seconds, number of attended users, and gaps obtained for each instance of Table 1, Table 2, and Table 3, where the radial transmission distance are 150, 200, and 300 m, respectively.

From Figure 3, Figure 4 and Figure 5, we see that independently of the radial transmission distance Algorithm 1 obtains tight near-optimal solutions for all the tested instances. Next, we observe that the users are always covered in about 99% to 100% of the time. Subsequently, we notice that the smaller the radial transmission distance is, the tighter are the CPU times obtained with Algorithm 1, and, in general, the CPU times of Algorithm 1 are not larger than 140 s for all the tested instances. Regarding the gaps obtained in percentages, which are measured by subtracting to the optimal objective function value, the value obtained with Algorithm 1, and dividing by the optimal function value times 100, we observe a decreasing trend, which is an interesting result. The latter verifies the effectiveness of Algorithm 1 as it approaches the optimal values, and these gaps are even smaller for larger-size instances of the problem. Finally, we mention that model $M_1$ obtains the optimal solutions of the network planning problem for all the instances too, although, at a slightly higher computational cost.

Similarly, to provide more insights regarding Algorithm 2 and model $M_3$, in Figure 6, Figure 7 and Figure 8 we report objective function values, CPU time in seconds, number of attended users, number of active BSs, and gaps obtained for each instance of Table 4, Table 5 and Table 6, respectively, where the radial transmission distance are 150, 200, and 300 m.

From Figure 6, Figure 7 and Figure 8, we observe that the objective function values are very tight again. Next, it is observed that the CPU time is significantly smaller for Algorithm 2 when compared with those obtained with model $M_3$ for all tested instances. The percentage of attended users is 100% with model $M_3$ and Algorithm 2. The number of active BSs for the solutions obtained with Algorithm 2 presents an increasing behavior. This is also an interesting observation as it shows the existence of solutions with a larger number of BSs that are also near-optimal. Finally, we see a decreasing behavior from the gaps obtained in the percentages. The latter verifies the effectiveness of Algorithm 2 also when approaching optimal solutions. Lastly, it is also worth mentioning that these gap values decrease for the larger size instances of the problem. Notice that model $M_3$ cannot obtain the optimal solution of the network planning problem for most of the tested instances using one hour of CPU time. The latter empirically shows that solving the network planning problem when simultaneously minimizing the number of BSs makes the optimization models significantly harder to solve optimally.

6. Conclusions

This paper proposes mathematical formulations for solving the network planning problem while using millimeter wave technology for 5G wireless communications. To this end, we assume that a set of users, M, and a set of base stations, N, are deployed randomly in a square area of 1 km². The main goal of the proposed models is to connect the base stations forming a star backbone so that users can connect to their nearest active base stations. We propose four optimization models to maximize the number of users connected to the backbone and minimize the distance costs of connecting users to the base stations, and distances of connecting the base stations themselves. Since millimeter wave technology presents a high path loss, the transmission distances cannot be larger than 300 m. Thus, a direct line of sight between users and base stations is also assumed. Finally, two local search-based algorithms are proposed to find near-optimal solutions for all our tested instances. Our numerical results indicate that we can solve network instances optimally with up to $n=200$, and $m=5000$ users. In general, we conclude that all the proposed models allow us to obtain optimal or near-optimal solutions for all test cases. Similarly, the proposed algorithms obtain optimal and near-optimal solutions with less CPU time and effort.

In future research, we plan to consider new layout implementations related to 5G networks in rural, urban, and semi-urban configurations. We also plan to propose novel mathematical models and algorithms to solve instances considering a higher density of base stations and users. Finally, it is also important to consider in the future metrics of the objective function factors such as the noise depending on weather conditions.