Minimum weight clustered dominating tree problem

doi:10.1016/j.ejor.2022.08.014

Return

Minimum weight clustered dominating tree problem

2023-04-01

PRE

Pablo Adasme

Rafael Andrade *

DOI：10.1016/j.ejor.2022.08.014

Original

Original request for help

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