Approximation Algorithm for Maximum Lifetime in Wireless Sensor Networks with Data Aggregation

We consider the problem of maximizing the lifetime of sensor networks with data aggregation, which was investigated by Kalpakis et al. (2003). They propose an exact polynomial-time algorithm, which however is very slow $O(n¹⁵log n), and faster heuristics. In this paper, we demonstrate an alternative approach based on the Garg-Konemann algorithm (1998) for packing linear programs, combined with the exact computation of minimum cost arborescence. For any epsiv > 0, our approach obtains a solution achieving at least 1 - epsiv times the optimum lifetime, with running time O(n^3/1epsivlog_{1 + epsiv} n). The simulation result shows that our algorithm achieves a solution that is within 2.5% of optimum and is not slower than the heuristics previously proposed by Kalpakis et al