Data Gathering Schedule for Minimal Aggregation Time in Wireless Sensor Networks

Abstract

Data aggregation promises a new paradigm for gathering data via collaboration among wireless sensors deployed over a large geographical region. Many real-time applications impose stringent delay requirements and ask for time-efficient schedules of data gathering in which data sensed at sensors are aggregated at intermediate sensors along the way towards the data sink. The Minimal Aggregation Time (MAT) problem is to find the schedule that routes data appropriately and has the shortest time for all requested data to be aggregated and sent to the data sink.

In this article we consider the MAT problem with collision-free transmission where a sensor can not receive any data if more than one sensors within its transmission range send data at the same time. We first prove that the MAT problem is NP-hard even if all sensors are deployed on a grid. We then propose a (Δ − 1)-approximation algorithms for the MAT problem, where Δ is the maximum number of sensors within the transmission range of any sensor. By exploiting the geometric nature of wireless sensor networks, we obtain some better theoretical results for some special cases. We also simulate the proposed algorithm. The numerical results show that our algorithm has much better performance in practice than the theoretically proved guarantees and outperforms other existing algorithms.

Keywords:

• Wireless Sensor Networks
• Data Aggregations
• Convergecast
• Collision-free Transmission
• Unit Disk Graphs
• Approximation Algorithm

This work was supported in part by the NSF of China under Grant No. 10531070 and 70221001 and Chinese Academy of Sciences under Grant No. kjcx-yw-s7.