Improved solution strategies for dominating trees. (15th June 2018)

• Record Type: Journal Article
• Authors: Adasme, Pablo; Andrade, Rafael; Leung, Janny; Lisser, Abdel
• Is Part Of: Expert systems with applications. Volume 100(2018)
• Page Start: 30
• Page End: 40
• Publication Date: 2018-06-15
• Subjects: Wireless sensor network -- Dominating tree -- Primal-dual model -- Cutting plane.; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2018.01.031
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: We present an improved formulation of the dominating tree problem for designing wireless sensor networks. Theoretical results are discussed. We adapt dominating set reduction techniques to the connected case. We solve efficiently benchmark instances with up to one hundred nodes. Abstract: 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.