Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks (Kalpakis, Dasgupta, Namjoshi; 2003)

The maximum lifetime data gathering with aggregation (MLDA) problem is defined as follows:

Given a collection of sensors and a base station, together with their locations and the energy of each sensor, find a data gathering schedule with maximum lifetime, where sensors are permitted to aggregate incoming data packets.

From a schedule telling when to send which packets we get a flow network with edge capacities being the total number of packets sent through that edge in the schedule. If a schedule has lifetime T (i.e., the network survives for at least T rounds), for each sensor the maximum flow to the base station is at least T as each of the T packets has to eventually reach the base station.
The idea is to find such a flow network (a so-called admissible flow network) and then to construct the schedule (a collection of directed aggregation trees, one for each round) from it.

@article{KDN2003,
author = {Konstantinos Kalpakis and Koustuv Dasgupta and Parag Namjoshi},
title = {Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks},
journal = {Comput. Networks},
volume = {42},
number = {6},
year = {2003},
pages = {697--716},
}