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

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: Shamim Begum , Shao-Cheng Wang , Bhaskar Krishnamachari , Ahmed Helmy, ELECTION: Energy-efficient and Low-latEncy sCheduling Technique for wIreless sensOr Networks, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks, p.60-67, November 16-18, 2004 [doi>10.1109/LCN.2004.49]
• 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: Jenna Burrell , Tim Brooke , Richard Beckwith, Vineyard Computing: Sensor Networks in Agricultural Production, IEEE Pervasive Computing, v.3 n.1, p.38-45, January 2004 [doi>10.1109/MPRV.2004.1269130]
• 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.
• 10: David Chu , Amol Deshpande , Joseph M. Hellerstein , Wei Hong, Approximate Data Collection in Sensor Networks using Probabilistic Models, Proceedings of the 22nd International Conference on Data Engineering, p.48, April 03-07, 2006 [doi>10.1109/ICDE.2006.21]
• 11: Alexandru Coman , Jorg Sander , Mario A. Nascimento, An Analysis of Spatio-Temporal Query Processing in Sensor Networks, Proceedings of the 21st International Conference on Data Engineering Workshops, p.1190, April 05-08, 2005 [doi>10.1109/ICDE.2005.186]
• 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: Tijs van Dam , Koen Langendoen, An adaptive energy-efficient MAC protocol for wireless 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.958512]
• 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: Amol Deshpande , Carlos Guestrin , Samuel R. Madden , Joseph M. Hellerstein , Wei Hong, Model-driven data acquisition in sensor networks, Proceedings of the Thirtieth international conference on Very large data bases, p.588-599, August 31-September 03, 2004, Toronto, Canada
• 17: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 18: Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
• 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: Fatih Emekci , Sezai E. Tuna , Divyakant Agrawal , Amr El Abbadi, BINOCULAR: a system monitoring framework, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052201]
• 21: Deepak Ganesan , Deborah Estrin , John Heidemann, Dimensions: why do we need a new data handling architecture for sensor networks?, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.143-148, January 2003 [doi>10.1145/774763.774786]
• 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.
• 24: Herman, T. 2003. Models of self-stabilization and sensor networks. In Proceedings of IWDC. 205--214.
• 25: 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
• 26: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 27: Chong Liu , Kui Wu , Jian Pei, An Energy-Efficient Data Collection Framework for Wireless Sensor Networks by Exploiting Spatiotemporal Correlation, IEEE Transactions on Parallel and Distributed Systems, v.18 n.7, p.1010-1023, July 2007 [doi>10.1109/TPDS.2007.1046]
• 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: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 30: Samuel Ross Madden , Michael J. Franklin, The design and evaluation of a query processing architecture for sensor networks, University of California at Berkeley, Berkeley, CA, 2003
• 31: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 32: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 33: Arati Manjeshwar , Dharma P. Agrawal, TEEN: ARouting Protocol for Enhanced Efficiency in Wireless Sensor Networks, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.189, April 23-27, 2001
• 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: Sylvia Ratnasamy , Brad Karp , Scott Shenker , Deborah Estrin , Ramesh Govindan , Li Yin , Fang Yu, Data-centric storage in sensornets with GHT, a geographic hash table, Mobile Networks and Applications, v.8 n.4, p.427-442, August 2003 [doi>10.1023/A:1024591915518]
• 38: RF Monolithics, I. 2007. Rfm tr1001 868.35MHZ hybrid transceiver. http://www.rfm.com/products/data/tr1001.pdf.
• 39: A. Sharaf , Jonathan Beaver , Alexandros Labrinidis , K. Chrysanthis, Balancing energy efficiency and quality of aggregate data in sensor networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.384-403, December 2004 [doi>10.1007/s00778-004-0138-0]
• 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: Gilman Tolle , Joseph Polastre , Robert Szewczyk , David Culler , Neil Turner , Kevin Tu , Stephen Burgess , Todd Dawson , Phil Buonadonna , David Gay , Wei Hong, A macroscope in the redwoods, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098925]
• 43: Daniela Tulone , Samuel Madden, An energy-efficient querying framework in sensor networks for detecting node similarities, Proceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems, October 02-06, 2006, Terromolinos, Spain [doi>10.1145/1164717.1164768]
• 44: Tulone, D. and Madden, S. 2006b. Paq: time series forecasting for approximate query answering in sensor networks. In Proceedings of EWSN. 21--37.
• 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: Mehmet C. Vuran , Özg¨r B. Akan , Ian F. Akyildiz, Spatio-temporal correlation: theory and applications for wireless sensor networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.45 n.3, p.245-259, 21 June 2004 [doi>10.1016/j.comnet.2004.03.007]
• 47: Mehmet C. Vuran , Ian F. Akyildiz, Spatial correlation-based collaborative medium access control in wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.14 n.2, p.316-329, April 2006 [doi>10.1109/TENT.2006.872544]
• 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: Yong Yao , Johannes Gehrke, The cougar approach to in-network query processing in sensor networks, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601861]
• 50: Ye, W., Heidemann, J., and Estrin, D. 2002. An energy-efficient MAC protocol for wireless sensor networks. In Proceedings of INFOCOM.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.4 Communications Management
          Subjects: Network communication
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Algorithms, Measurement, Performance

Keywords:
Wireless sensor network, cross-layer optimization, in-network data aggregation, scheduling, self-organizing, spatio-temporal correlation