Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks

摘要

The rapid advances in processor, memory, and radio technology have enabled the development of distributed networks of small, inexpensive nodes that are capable of sensing, computation, and wireless communication. Sensor networks of the future are envisioned to revolutionize the paradigm of collecting and processing information in diverse environments. However, the severe energy constraints and limited computing resources of the sensors, present major challenges for such a vision to become a reality. We consider a network of energy-constrained sensors that are deployed over a region. Each sensor periodically produces information as it monitors its vicinity. The basic operation in such a network is the systematic gathering and transmission of sensed data to a base station for further processing. During data gathering, sensors have the ability to perform in-network aggregation (fusion) of data packets enroute to the base station. The lifetime of such a sensor system is the time during which we can gather information from all the sensors to the base station. A key challenge in data gathering is to maximize the system lifetime, given the energy constraints of the sensors. Given the location of n sensors and a base station together with the available energy at each sensor, we are interested in finding an efficient manner in which data should be collected from all the sensors and transmitted to the base station, such that the system lifetime is maximized. This is the maximum lifetime data gathering problem. In this paper, we describe novel algorithms, with worst-case running times polynomial in n, to solve the data gathering problem with aggregation in sensor networks. Our experimental results demonstrate that the proposed algorithms significantly outperform previous methods in terms of system lifetime.