research-article

A distributed and self-organizing scheduling algorithm for energy-efficient data aggregation in wireless sensor networks

Authors:

Supriyo Chatterjea,

Nirvana Meratnia,

Paul HavingaAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 4, Issue 4

Article No.: 20, Pages 1 - 41

https://doi.org/10.1145/1387663.1387666

Published: 04 September 2008 Publication History

Abstract

Wireless sensor networks (WSNs) are increasingly being used to monitor various parameters in a wide range of environmental monitoring applications. In many instances, environmental scientists are interested in collecting raw data using long-running queries injected into a WSN for analyzing at a later stage, rather than injecting snap-shot queries containing data-reducing operators (e.g., MIN, MAX, AVG) that aggregate data. Collection of raw data poses a challenge to WSNs as very large amounts of data need to be transported through the network. This not only leads to high levels of energy consumption and thus diminished network lifetime but also results in poor data quality as much of the data may be lost due to the limited bandwidth of present-day sensor nodes. We alleviate this problem by allowing certain nodes in the network to aggregate data by taking advantage of spatial and temporal correlations of various physical parameters and thus eliminating the transmission of redundant data. In this article we present a distributed scheduling algorithm that decides when a particular node should perform this novel type of aggregation. The scheduling algorithm autonomously reassigns schedules when changes in network topology, due to failing or newly added nodes, are detected. Such changes in topology are detected using cross-layer information from the underlying MAC layer. We first present the theoretical performance bounds of our algorithm. We then present simulation results, which indicate a reduction in message transmissions of up to 85% and an increase in network lifetime of up to 92% when compared to collecting raw data. Our algorithm is also capable of completely eliminating dropped messages caused by buffer overflow.

References

[1]

AIMS. 2006. Reef at our fingertips. http://www.aims.gov.au/pages/about/communications/waypoint/headlines-04 .html.

[2]

Ambient. 2006a. Ambient systems. http://www.ambient-systems.net/ambient/index.htm.

[3]

Ambient. 2006b. AmbientRT operating system. http://www.ambient-systems.net/ambient/technology-rtos.htm.

[4]

Begum, S., Wang, S.-C., Krishnamachari, B., and Helmy, A. 2004. Election: energy-efficient and low-latency scheduling technique for wireless sensor networks. In Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04). IEEE Computer Society, 60--67.

Digital Library

[5]

Bondarenko, O., Kininmonth, S., and Kingsford, M. 2007. Underwater sensor networks, oceanography and plankton assemblages. In Proceedings of ISSNIP. Melbourne, Australia.

[6]

Bulusu, N., Estrin, D., Girod, L., and Heidemann, J. 2001. Scalable coordination for wireless sensor networks: self-conguring localization systems. In Proceedings of the International Symposium on Communication Theory and Applications (ISCTA). Cumbria, UK.

[7]

Burrell, J., Brooke, T., and Beckwith, R. 2004. Vineyard computing: sensor networks in agricultural production. IEEE Peruas. Comput. 03, 1, 38--45.

Digital Library

[8]

Chatterjea, S., Kininmonth, S., and Havinga, P. J. M. 2006. Sensor networks. GeoConnexion 5, 9, 20--22.

[9]

Chatterjea, S., Nieberg, T., Zhang, Y., and Havinga, P. J. M. 2007. Energy-efficient data acquisition using a distributed and self-organizing scheduling algorithm for wireless sensor networks. In Proceedings of DCOSS. 368--385.

Digital Library

[10]

Chu, D., Deshpande, A., Hellerstein, J. M., and Hong, W. 2006. Approximate data collection in sensor networks using probabilistic models. In Proceedings of ICDE. 48.

Digital Library

[11]

Coman, A., Sander, J., and Nascimento, M. A. 2005. An analysis of spatio-temporal query processing in sensor networks. In Proceedings of the 21st International Conference on Data Engineering Workshops (ICDEW'05). IEEE Computer Society, Washington, DC, 1190.

Digital Library

[12]

Crescenzi, P. and Kann, V. 2005a. A compendium of np optimization problems: maximum independent set. http://www.nada.kth.se/~viggo/wwwcompendium/node34.html.

[13]

Crescenzi, P. and Kann, V. 2005b. A compendium of np optimization problems: minimum independent dominating set. http://www.nada.kth.se/~viggo/wwwcompendium/node14.html.

[14]

Dam, T. and Langendoen, K. 2003. An adaptive energy-efficient MAC protocol for wireless sensor networks. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. Los Angeles, CA.

Digital Library

[15]

Deshpande, A., Guestrin, C., Madden, S., Hellerstein, J. M., and Hong, W. 2005. Model-based approximate querying in sensor networks. VLDB J. 14, 4, 417--443.

[16]

Deshpande, A., Guestrin, C., Madden, S. R., Hellerstein, J. M., and Hong, W. 2004. Model-driven data acquisition in sensor networks. In Proceedings of the 30th VLDB Conference. Toronto, Canada.

Digital Library

[17]

Dijkstra, E. 1974. Self-stabilizing systems in spite of distributed control. Comm. ACM 17, 11, 643--644.

Digital Library

[18]

Dolev, S. 2000. Self-Stabilization. The MIT Press, Cambridge, MA.

Digital Library

[19]

Dulman, S., Chatterjea, S., Hoffmeijer, T., Havinga, P., and Hurink., J. 2006. Architectures for wireless sensor networks. In Embedded Systems Handbook, R. Zurawski, Ed. CRC Press, Florida, 31--1--31--10.

[20]

Emekci, F., Tuna, S. E., Agrawal, D., and Abbadi, A. E. 2004. Binocular: a system monitoring framework. In Proceeedings of the 1st International Workshop on Data Management for Sensor Networks (DMSN'04). ACM Press, New York, NY, 5--9.

Digital Library

[21]

Ganesan, D., Estrin, D., and Heidemann, J. 2003. Dimensions: why do we need a new data handling architecture for sensor networks&quest; SIGCOMM Comput. Comm. Rev. 33, 1, 143--148.

Digital Library

[22]

Greenstein, B., Ratnasamy, S., Shenker, S., Govindan, R., and Estrin, D. 2003. Difs: a distributed index for features in sensor networks. Ad Hoc Netw. 1, 2-3, 333--349.

[23]

Heinzelman, W. R., Chandrakasan, A. P., and Balakrishnan, H. 2002. An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. Wirel. Comm. 1, 4, 660--670.

Digital Library

[24]

Herman, T. 2003. Models of self-stabilization and sensor networks. In Proceedings of IWDC. 205--214.

[25]

Intanagonwiwat, C., Estrin, D., Govindan, R., and Heidemann, J. 2002. Impact of network density on data aggregation in wireless sensor networks. In Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS'02). IEEE Computer Society, 457.

Digital Library

[26]

Intanagonwiwat, C., Govindan, R., Estrin, D., Heidemann, J., and Silva, F. 2003. Directed diffusion for wireless sensor networking. IEEE/ACM Trans. Netw. 11, 1, 2--16.

Digital Library

[27]

Liu, C., Wu, K., and Pei, J. 2007. An energy efficient data collection framework for wireless sensor networks by exploiting spatiotemporal correlation. IEEE Trans. Parall. Distr. Syst.

Digital Library

[28]

Lu, G., Krishnamachari, B., and Raghavendra, C. S. 2004. An adaptive energy-efficient and low-latency MAC for data gathering in wireless sensor networks. In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS). 13. 224a.

[29]

Lynch, N. 1996. Distributed Algorithms. Morgan Kaufmann Publishers.

Digital Library

[30]

Madden, S. 2003. The design and evaluation of a query processing architecture for sensor networks. Ph.D. thesis, University of California, Berkeley.

Digital Library

[31]

Madden, S. R., Franklin, M. J., Hellerstein, J. M., and Hong, W. 2005. Tinydb: an acquisitional query processing system for sensor networks. ACM Trans. Datab. Syst. 30, 1, 122--173.

Digital Library

[32]

Mainwaring, A., Culler, D., Polastre, J., Szewczyk, R., and Anderson, J. 2002. Wireless sensor networks for habitat monitoring. In Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02). ACM Press, New York, NY, 88--97.

Digital Library

[33]

Manjeshwar, A. and Agrawal, D. P. 2001. Teen: A routing protocol for enhanced efficiency in wireless sensor networks. In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS). 03. 30189a.

Digital Library

[34]

Matlab. 2006. MATLAB—the language of technical computing. http://www.mathworks.com/products/matlab/.

[35]

Nieberg, T. 2006. Independent and dominating sets in wireless communication graphs. Ph.D. thesis, University of Twente, The Netherlands.

[36]

Palazzi, C., Woods, G., Atkinson, I., and Kininmonth, S. 2005. High speed over ocean radio link to great barrier reef. In Proceedings of TENCON. IEEE.

[37]

Ratnasamy, S., Karp, B., Shenker, S., Estrin, D., Govindan, R., Yin, L., and Yu, F. 2003. Data-centric storage in sensornets with ght, a geographic hash table. Mob. Netw. Appl. 8, 4, 427--442.

Digital Library

[38]

RF Monolithics, I. 2007. Rfm tr1001 868.35MHZ hybrid transceiver. http://www.rfm.com/products/data/tr1001.pdf.

[39]

Sharaf, A., Beaver, J., Labrinidis, A., and Chrysanthis, K. 2004. Balancing energy efficiency and quality of aggregate data in sensor networks. VLDB J. 13, 4, 384--403.

Digital Library

[40]

Smyth, A. W., Pei, J.-S., and Masri, S. F. 2003. System identification of the Vincent Thomas suspension bridge using earthquake records. Earthqu. Eng. Struct. Dyn. 32, 3, 339--367.

[41]

TI. 2006. Msp430 ultra-low power microcontrollers overview from texas instruments. http://focus.ti.com/mcu/docs/mcuprodoverview.tsp?sectionId=95&tabId=140&familyId=342.

[42]

Tolle, G., Polastre, J., Szewczyk, R., Culler, D., Turner, N., Tu, K., Burgess, S., Dawson, T., Buonadonna, P., Gay, D., and Hong, W. 2005. A macroscope in the redwoods. In Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems (SenSys'05). ACM Press, New York, NY, 51--63.

Digital Library

[43]

Tulone, D. and Madden, S. 2006a. An energy-efficient querying framework in sensor networks for detecting node similarities. In Proceedings of the 9th ACM International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems (MSWiM'06). ACM Press, New York, NY, 191--300.

Digital Library

[44]

Tulone, D. and Madden, S. 2006b. Paq: time series forecasting for approximate query answering in sensor networks. In Proceedings of EWSN. 21--37.

Digital Library

[45]

van Hoesel, L. and Havinga, P. 2004. A lightweight medium access protocol (IMAC) for wireless sensor networks: reducing preamble transmissions and transceiver state switches. In Proceedings of INSS. Tokyo, Japan.

[46]

Vuran, M. C., Akan, B., and Akyildiz, I. F. 2004. Spatio-temporal correlation: theory and applications for wireless sensor networks. Comput. Netw. 45, 3, 245--259.

Digital Library

[47]

Vuran, M. C. and Akyildiz, I. F. 2006. Spatial correlation-based collaborative medium access control in wireless sensor networks. IEEE/ACM Trans. Netw. 14, 2, 316--329.

Digital Library

[48]

Wen, J. 2006. A smart indoor air quality sensor network. In Proceedings of SPIE, Vol. 6174. M. Tomizuka, C. Yun, and V. Giurgiutiu, Eds. 1277--1290.

[49]

Yao, Y. and Gehrke, J. 2002. The cougar approach to in-network query processing in sensor networks. In SIGMOD Rec. 31, 3, 9--18.

Digital Library

[50]

Ye, W., Heidemann, J., and Estrin, D. 2002. An energy-efficient MAC protocol for wireless sensor networks. In Proceedings of INFOCOM.

Cited By

Li HDong WWang YGao YChen C(2020)Enhancing the Performance of 802.15.4-Based Wireless Sensor Networks With NB-IoTIEEE Internet of Things Journal10.1109/JIOT.2020.29725127:4(3523-3534)Online publication date: Apr-2020
https://doi.org/10.1109/JIOT.2020.2972512
Sarode PNandhini R(2018)Intelligent Query-Based Data Aggregation Model and Optimized Query Ordering for Efficient Wireless Sensor NetworkWireless Personal Communications: An International Journal10.1007/s11277-018-5646-0100:4(1405-1425)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s11277-018-5646-0
Shanmukhi MEshwarawaka RRenuka KDurga Preethi K(2018)Energy-Efficient Data Aggregation Using Cluster-Based Comb–Needle Model in Wireless Sensor NetworksSoft Computing for Problem Solving10.1007/978-981-13-1595-4_53(665-678)Online publication date: 31-Oct-2018
https://doi.org/10.1007/978-981-13-1595-4_53
Show More Cited By

Index Terms

A distributed and self-organizing scheduling algorithm for energy-efficient data aggregation in wireless sensor networks

Recommendations

Distributed Multilevel k-Coverage Energy-Efficient Fault-Tolerant Scheduling for Wireless Sensor Networks
Abstract
The expected k-coverage, prolonged network lifetime, and fault-tolerance capabilities play a vital role in the success of various application operations in Wireless Sensor Networks (WSNs), as they are the key performance indicators of WSNs. The k-...
Achieving Scalable Privacy Preserving Data Aggregation for Wireless Sensor Networks
CIT '10: Proceedings of the 2010 10th IEEE International Conference on Computer and Information Technology

A sink node must be aware of the identifications (node IDs) of those all sensor nodes which contribute in aggregated value of sensors data in order to derive exact result of them in privacy preserving data aggregation scheme for wireless sensor networks ...
An Energy Efficient Clustering Approach in Wireless Sensor Networks
ICCSEE '12: Proceedings of the 2012 International Conference on Computer Science and Electronics Engineering - Volume 01

A wireless sensor network (WSN) consists of a large number of low-power micro-sensors. The data collected by each sensor is communicated through the network to a single sink node. Data gathering is a key work of the wireless sensor network. To prolong ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 4, Issue 4

August 2008

295 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/1387663

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 04 September 2008

Accepted: 01 December 2007

Revised: 01 September 2007

Received: 01 February 2007

Published in TOSN Volume 4, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
1,916
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li HDong WWang YGao YChen C(2020)Enhancing the Performance of 802.15.4-Based Wireless Sensor Networks With NB-IoTIEEE Internet of Things Journal10.1109/JIOT.2020.29725127:4(3523-3534)Online publication date: Apr-2020
https://doi.org/10.1109/JIOT.2020.2972512
Sarode PNandhini R(2018)Intelligent Query-Based Data Aggregation Model and Optimized Query Ordering for Efficient Wireless Sensor NetworkWireless Personal Communications: An International Journal10.1007/s11277-018-5646-0100:4(1405-1425)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s11277-018-5646-0
Shanmukhi MEshwarawaka RRenuka KDurga Preethi K(2018)Energy-Efficient Data Aggregation Using Cluster-Based Comb–Needle Model in Wireless Sensor NetworksSoft Computing for Problem Solving10.1007/978-981-13-1595-4_53(665-678)Online publication date: 31-Oct-2018
https://doi.org/10.1007/978-981-13-1595-4_53
Anisi MAbdul-Salaam GIdris MWahab AAhmedy I(2017)Energy harvesting and battery power based routing in wireless sensor networksWireless Networks10.1007/s11276-015-1150-623:1(249-266)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s11276-015-1150-6
Hussain MShafeeq MJabbar SAkbar AKhalid S(2016)CRAM: A Conditioned Reflex Action Inspired Adaptive Model for Context Addition in Wireless Sensor NetworksJournal of Sensors10.1155/2016/63198302016(1-24)Online publication date: 2016
https://doi.org/10.1155/2016/6319830
Chhieng VWong RFong SMohammed S(2016)Autonomous path based data acquisition in sensor networksThe Journal of Supercomputing10.1007/s11227-016-1745-472:10(4021-4042)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s11227-016-1745-4
Diallo ORodrigues JSene MLloret J(2015)Distributed Database Management Techniques for Wireless Sensor NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.20726:2(604-620)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TPDS.2013.207
Liu CFang KTeng J(2015)Optimum wireless sensor deployment scheme for structural health monitoring: a simulation studySmart Materials and Structures10.1088/0964-1726/24/11/11503424:11(115034)Online publication date: 22-Oct-2015
https://doi.org/10.1088/0964-1726/24/11/115034
Sinha ALobiyal D(2015)Prediction Models for Energy Efficient Data Aggregation in Wireless Sensor NetworkWireless Personal Communications: An International Journal10.1007/s11277-015-2690-x84:2(1325-1343)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1007/s11277-015-2690-x
Shao ZZhang L(2014)Water Quality Monitoring Based on Mobile Measurable SystemApplied Mechanics and Materials10.4028/www.scientific.net/AMM.692.22692(22-27)Online publication date: Nov-2014
https://doi.org/10.4028/www.scientific.net/AMM.692.22
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents