.png){kind=icon}
.png){kind=icon}
Return
Minimum weight clustered dominating tree problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2022.08.014.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 cen-tral 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 dis-tances. 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 be-tween 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.(c) 2022 Elsevier B.V. All rights reserved.
Keywords:
Combinatorial optimization
Clustered network design
Valid inequalities
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W