We investigate a Maximum Lifespan Tree Problem arising in wireless sensor networks. A network is given where each node represents a sensor; at each duty cycle they collect data, and transmit it towards a sink node through multi-hop paths on wireless links. Sensors are powered by a battery, which is partially consumed at each transmission. A tree of links spanning all the sensors must be designed such that the lifespan of the entire network, computed as the minimum lifespan among all nodes, is maximized. We study three mathematical programming formulations and we propose a comparison of the dual bounds obtained exploiting them. In particular, one of the formulations is path-based: to optimize it we design ad-hoc column generation algorithms.
Dual bounds for a maximum lifespan tree problem / M. Casazza, A. Ceselli - In: 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization[s.l] : CNAM, 2018. - pp. 108-111 (( convegno 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 tenutosi a Paris nel 2018.
Dual bounds for a maximum lifespan tree problem
M. Casazza;A. Ceselli
2018
Abstract
We investigate a Maximum Lifespan Tree Problem arising in wireless sensor networks. A network is given where each node represents a sensor; at each duty cycle they collect data, and transmit it towards a sink node through multi-hop paths on wireless links. Sensors are powered by a battery, which is partially consumed at each transmission. A tree of links spanning all the sensors must be designed such that the lifespan of the entire network, computed as the minimum lifespan among all nodes, is maximized. We study three mathematical programming formulations and we propose a comparison of the dual bounds obtained exploiting them. In particular, one of the formulations is path-based: to optimize it we design ad-hoc column generation algorithms.File | Dimensione | Formato | |
---|---|---|---|
ctw18-proceedings.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
5.17 MB
Formato
Adobe PDF
|
5.17 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.