Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420568 | Discrete Applied Mathematics | 2009 | 15 Pages |
Abstract
Efficient data gathering is an important challenge in sensor networks. In this paper we address the problem of gathering sensed data to the sink of a sensor network minimizing the time to complete the process. We present optimal time data gathering algorithms for any sensor network topology, in the half-duplex with directional antennas model, when each sensor has one data packet to be gathered and merging of packets is not allowed at intermediate nodes. Our results improve on existing approximation algorithms. We approach the gathering problem by obtaining optimal solutions to a path coloring problem in graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Luisa Gargano, Adele A. Rescigno,