Integer Programming Models for Wireless Networks with Star Backbone Topology

In this paper, we propose two mixed integer linear programming (MILP) models for wireless networks (WNs) under star backbone topology configuration. For this purpose, let the graph $G(V,E)$ represent a WN with set of nodes V and edge set E. Set V represents all nodes (wireless devices) which can be part or not of the star backbone whereas set E represents the connection links between all pairs of nodes. Additionally, we consider a set K of users. Only, a subset of nodes from V should be active to form the star backbone and each user should be connected to a unique terminal (leaf) node. This problem represents a more general variant of a previous work reported in the literature where only a fixed number of nodes from V is required to be active. Our first model corresponds to a novel Miller-Tucker-Zemlin constrained version whilst the second one is a novel flow based formulation. Then, we further propose an iterative greedy algorithm that allows to obtain feasible solutions for the problem. Our preliminary numerical results indicate that the flow model allows one to obtain optimal solutions in less CPU time for Euclidean complete and disk graph instances. Whilst the greedy algorithm allows to obtain near optimal and optimal solutions in significantly less computational cost compared to the MILP models and with gap values which are lower than 2% for most tested instances. © 2019 IEEE.