Abstract

In this article, the problem of achieving the minimum backbone connectivity cost while simultaneously maximizing user coverage for 5G millimeter-wave (mmWave)-based networks is considered. Let G=(N,E) be an input graph instance with a set of nodes N (base stations) and a set of edges E. It is assumed that G represents a wireless backbone network. Let M represent a set of users to be covered by G. Note that mmWave technology has been considered in the literature as an important candidate solution for 5G networks due to its low latency. However, there remain some problems to be addressed before using this technology. A serious one is that millimeter waves cannot cover large transmission distances. In this article, the proposed methodology consists of formulating mixed-integer programming models to deal with the problem from a management point of view. Our models allow the determination of which of the nodes of G should be active and connected while simultaneously maximizing the total number of covered users. The models are solved with the CPLEX solver using its branch and cut and automatic Benders decomposition algorithms. For this purpose, symmetric complete and sparse graphs are considered. Using the symmetry concept, it is considered that the distances between base stations and users and between base stations themselves are symmetrical. Finally, an efficient local search meta-heuristic is proposed that allows for finding near-optimal solutions. Our numerical experiments indicate that the problem is hard to solve optimally. Thus, instances with up to 40 nodes and 500 users have been solved to optimality so far. In particular, it is observed that one of the models presents slightly better performance in terms of CPU time. Finally, the heuristic approach allows us to obtain tight solutions with less computational effort when dealing with even larger instances of the problem.