On a Wireless Sensor Network Problem with Spanning Tree Backbone

Let G = (V, E) be a complete graph with set of nodes V = {1,. .., n} and edge set E = {1,. .., m} representing a wireless sensor network. In this paper, we consider the problem of finding a minimum cost spanning tree backbone formed with p ∈ Z+ out of n nodes where p < n in such a way that the n − p remaining nodes of G are connected to the leaf nodes of the backbone structure at minimum connectivity cost. Notice that this problem arises as a combination of two classical combinatorial optimization problems, namely the p-Median and spanning tree problems. We propose two mixed-integer linear programming (MIP) formulations for this problem as well as a local search heuristic. The proposed models and algorithm can be used as a reference source for comparison purposes when designing future network protocols. We consider complete graph instances with Euclidean and random uniform costs. Our preliminary numerical results indicate that one of the proposed models performs slightly better than the other one in terms of solution quality and CPU times obtained with the Gurobi solver. Finally, the proposed heuristic allows one to obtain near-optimal solutions in remarkably less CPU time compared to the MIP models. Copyright © 2021 by SCITEPRESS – Science and Technology Publications, Lda. All rights reserved