Minimum weight clustered dominating tree problem

Pablo Adasme and Rafael Castro de Andrade

European Journal of Operational Research, 2023, vol. 306, issue 2, 535-548

Abstract: We discuss minimum weight clustered dominating trees that find applications in the wireless sensor network design based on a clustered independent set structure. A cluster consists of a master sensor and the sensors belonging to its sensing radius. Masters collect, filter, and transmit the sensed data to a central sensor responsible for processing all sensed information. The data sent from a cluster to the central sensor follow a unique path. It alternates between a master and a bridge node, in this order. A bridge allows data communication between two neighboring clusters. The larger the distance between masters and bridges, the higher the energy consumption for data transmission. To reduce energy consumption and increase the network lifetime, we investigate a clustered tree structure of minimum total link distances. We propose hop- and flow-based models, introduce valid inequalities for them, and discuss five exponential families of cuts when embedded into the branch-and-cut framework of the CPLEX solver. Our models benefit properly of the CPLEX Benders’ decomposition. We also highlight the differences between the topology of the clustered tree of minimum cost and the one of the (non-clustered) minimum dominating tree of the corresponding instances in terms of cost and number of solution nodes.

Keywords: Combinatorial optimization; Clustered network design; Valid inequalities (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722006579
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:306:y:2023:i:2:p:535-548

DOI: 10.1016/j.ejor.2022.08.014

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().