Dual bounds for a maximum lifespan tree problem

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.