Improved Solution Strategies for Dominating Trees

Intelligent systems in Wireless Sensor Networks (WSN) allow to eliminate duplicated sensed data and to efficiently route them to a central processing unit. Thus, augmenting WSN lifetime while keeping sensors connectivity and routing the sensed information through an optimized network structure. This work discusses a set of improved exact solution strategies that were effective to the design of a minimum energy consumption structure for the sensors data communication. We present an extended version of a primal-dual model for the minimum cost dominating tree (DT) problem, as well as valid inequalities to improve its linear relaxation. We discuss structural properties of dominating sets and trees used to conceive efficient cutting plane strategies. We adapt accordingly reduction techniques from dominating sets to the DT problem. The new solution techniques allow to handle to optimality challenging benchmark and new randomly generated DT instances with up to 100 nodes, which was not possible to achieve with state-of-the-art models for the problem. © 2018 Elsevier Ltd