Title: Approximation algorithm for maximum lifetime in wireless sensor networks with data aggregation

Authors: Jeffrey Stanford, Sutep Tongngam

Addresses: Department of Computer Science, Illinois Institute of Technology, Chicago, Illinois 60616, USA. ' School of Applied Statistics, National Institute of Development Administration (NIDA), Bangkok, Thailand

Abstract: We consider the problem of maximising the lifetime of sensor networks with data aggregation, which was previously investigated by Kalpakis et al. (2003). They propose an exact polynomial-time algorithm, which is however very slow, and faster heuristics, where an approximation ratio is not guaranteed. In this paper, we demonstrate an alternative approach based on the Garg and Konemann (1998) algorithm for packing linear programs, combined with the exact computation of minimum cost arborescence. For any ε > 0, our approach obtains a solution achieving at least 1-ε times the optimum lifetime with significantly faster running time than that of the exact algorithm. The simulation result also shows that our algorithm achieves a solution that is within 0.02% of optimum and is not slower than the heuristics previously proposed by Kalpakis et al. (2003).

Keywords: WSN lifetime; wireless sensor networks; data aggregation; approximation; wireless networks.

DOI: 10.1504/IJSNET.2009.028024

International Journal of Sensor Networks, 2009 Vol.6 No.1, pp.44 - 50

Published online: 29 Aug 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article