We consider the problem of maximizing the lifetime of sensor networks with data aggregation, which was previously investigated by Kalpakis et al. [1]. They propose an exact polynomial-time algorithm, which however is very slow -O n15 logn , and faster heuristics. In this paper, we demonstrate an alternative approach based on the Garg-K ¨onemann algorithm [2] for packing linear programs, combined with the exact computation of minimum cost arborescence. For any varepsilon gt 0, our approach obtains a solution achieving at least 1 - varepsilon times the optimum lifetime, with running time o(n^3 frac{1} {varepsilon }log 1 + varepsilon ^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.
展开▼
