AIDA: Adaptive application-independent data aggregation in wireless sensor networks

ABSTRACT

Sensor networks, a novel paradigm in distributed wireless communication technology, have been proposed for various applications including military surveillance and environmental monitoring. These systems deploy heterogeneous collections of sensors capable of observing and reporting on various dynamic properties of their surroundings in a time sensitive manner. Such systems suffer bandwidth, energy, and throughput constraints that limit the quantity of information transferred from end-to-end. These factors coupled with unpredictable traffic patterns and dynamic network topologies make the task of designing optimal protocols for such networks difficult. Mechanisms to perform data-centric aggregation utilizing application-specific knowledge provide a means to augmenting throughput, but have limitations due to their lack of adaptation and reliance on application-specific decisions. We, therefore, propose a novel aggregation scheme that adaptively performs application-independent data aggregation in a time sensitive manner. Our work isolates aggregation decisions into a module that resides between the network and the data-link layer and does not require any modifications to the currently existing MAC and network layer protocols. We take advantage of queuing delay and the broadcast nature of wireless communication to concatenate network units into an aggregate using a novel adaptive feedback scheme to schedule the delivery of this aggregate to the MAC layer for transmission. In our evaluation we show that end-to-end transmission delay is reduced by as much as 80% under heavy traffic loads. Additionally, we show as much as a 50% reduction in transmission energy consumption with an overall reduction in header overhead. Theoretical analysis, simulation, and a test-bed implementation on Berkeley's MICA motes are provided to validate our claims.

REFERENCES

• 1: Abdelzaher, T. F., et al. 2003. EnviroTrack: An Environmental Programming Model for Tracking Applications in Distributed Sensor Networks. Tech. Rep. CS-2003-02, University of Virginia.
• 2: Maria Adamou , Sanjeev Khanna , Insup Lee , Insik Shin , Shiyu Zhou, Fair Real-Time Traffic Scheduling over a Wireless LAN, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.279, December 03-06, 2001
• 3: ANSI/IEEE. 1999. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. ANSI/IEEE Std 802.11, 1999 Edition.
• 4: Vaduvur Bharghavan , Alan Demers , Scott Shenker , Lixia Zhang, MACAW: a media access protocol for wireless LAN's, Proceedings of the conference on Communications architectures, protocols and applications, p.212-225, August 31-September 02, 1994, London, United Kingdom
• 5: Sagnik Bhattacharya , Hyung Kim , Shashi Prabh , Tarek Abdelzaher, Energy-conserving data placement and asynchronous multicast in wireless sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.173-185, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066120]
• 6: Brian Blum , Prashant Nagaraddi , Anthony Wood , Tarek Abdelzaher , Sang Son , Jack Stankovic, An entity maintenance and connection service for sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.201-214, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066122]
• 7: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 8: CrossBow. 2003. Available from http://www.xbow.com/Products/Product_pdf_files/MICA%20data%20sheet.pdf.
• 9: Chane L. Fullmer , J. J. Garcia-Luna-Aceves, Floor acquisition multiple access (FAMA) for packet-radio networks, ACM SIGCOMM Computer Communication Review, v.25 n.4, p.262-273, Oct. 1995
• 10: Guo, C., Zhong, L. C., and Rabaey, J. M. 2001. Low power distributed MAC for ad hoc sensor radio networks. In Proceedings of IEEE GlobeCom 2001, San Antonio.
• 11: He, T., Gu, L., and Blum, B. 2002. Nest Project Source Code Base. Available from http://sourceforge.net/projects/vert/.
• 12: Tian He , John A. Stankovic , Chenyang Lu , Tarek Abdelzaher, SPEED: A Stateless Protocol for Real-Time Communication in Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.46, May 19-22, 2003
• 13: John Heidemann , Fabio Silva , Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , Deepak Ganesan, Building efficient wireless sensor networks with low-level naming, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 14: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 15: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 16: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 17: Chalermek Intanagonwiwat , Deborah Estrin , Ramesh Govindan , John Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.457, July 02-05, 2002
• 18: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 19: Johnson, D. B. and Maltz, D. A. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing. Kluwer Academic Publishers, Boston, MA, 153--181, Chapter 5.
• 20: V. Kanodia , C. Li , A. Sabharwal , B. Sadeghi , E. Knightly, Distributed multi-hop scheduling and medium access with delay and throughput constraints, Proceedings of the 7th annual international conference on Mobile computing and networking, p.200-209, July 2001, Rome, Italy [doi>10.1145/381677.381697]
• 21: Karn, P. 1990. MACA---A new channel access method for packet radio. In ARRL/CRRL Amateur Radio 9th Computer Networking Conference. 134--140.
• 22: Brad Nelson Karp , H. T. Kung, Geographic routing for wireless networks, 2000
• 23: Bhaskar Krishnamachari , Deborah Estrin , Stephen B. Wicker, The Impact of Data Aggregation in Wireless Sensor Networks, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.575-578, July 02-05, 2002
• 24: Lim, A., 2001. Distributed services for information dissemination in self-organizing sensor networks. Special Issue on Distributed Sensor Networks for Real-Time Systems with Adaptive Reconfiguration, Journal of Franklin Institute.
• 25: Chenyang Lu , Brian M. Blum , Tarek F. Abdelzaher , John A. Stankovic , Tian He, RAP: A Real-Time Communication Architecture for Large-Scale Wireless Sensor Networks, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02), p.55, September 25-27, 2002
• 26: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 27: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 28: Min, R., Bhardwaj, M., Cho, S.H., Sinha, A., Shih, E., Wang, A., and Chandrakasan, A. 2000. An architecture for a power-aware distributed microsensor node. In IEEE Workshop on Signal Processing Systems (SiPS '00).
• 29: Nagpal, R. and Coore, D. 1998. An algorithm for group formation in an amorphous computer. In Proceedings of the 10th International Conference on Parallel and Distributed Computing Systems (PDCS'98), Nevada.
• 30: Takagi, H. and Kleinrock, L. 1984. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Trans. Commun. 32, 3, 246--257.
• 31: Alec Woo , David E. Culler, A transmission control scheme for media access in sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.221-235, July 2001, Rome, Italy [doi>10.1145/381677.381699]
• 32: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 33: Ting Yan , Tian He , John A. Stankovic, Differentiated surveillance for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958498]
• 34: Ye, W., Heidemann, J. and Estrin, D. 2002. An energy-efficient MAC protocol for wireless sensor networks. In Proceedings of the 21st International Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002), New York, NY.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

General Terms:
Algorithms, Design, Performance

Keywords:
Data aggregation, adaptive algorithms, congestion control, energy conservation, feedback control, sensor networks