Optimizing lifetime for continuous data aggregation with precision guarantees in wireless sensor networks

ABSTRACT

This paper exploits the tradeoff between data quality and energy consumption to extend the lifetime of wireless sensor networks. To obtain an aggregate form of sensor data with precision guarantees, the precision constraint is partitioned and allocated to individual sensor nodes in a coordinated fashion. Our key idea is to differentiate the precisions of data collected from different sensor nodes to balance their energy consumption. Three factors affecting the lifetime of sensor nodes are identified: 1) the changing pattern of sensor readings; 2) the residual energy of sensor nodes; and 3) the communication cost between the sensor nodes and the base station. We analyze the optimal precision allocation in terms of network lifetime and propose an adaptive scheme that dynamically adjusts the precision constraints at the sensor nodes. The adaptive scheme also takes into consideration the topological relations among sensor nodes and the effect of in-network aggregation. Experimental results using real data traces show that the proposed scheme significantly improves network lifetime compared to existing methods.

REFERENCES

• 1: I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Commun. Mag., vol. 40, no. 8, pp. 102-114, Aug. 2002.
• 2: Robert Szewczyk , Eric Osterweil , Joseph Polastre , Michael Hamilton , Alan Mainwaring , Deborah Estrin, Habitat monitoring with sensor networks, Communications of the ACM, v.47 n.6, June 2004 [doi>10.1145/990680.990704]
• 3: J. Gehrke and S. Madden, "Query processing in sensor networks," IEEE Pervasive Comput, vol. 3, no. 1, pp. 45-55, Jan.-Mar. 2004.
• 4: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 5: Victor Shnayder , Mark Hempstead , Bor-rong Chen , Geoff Werner Allen , Matt Welsh, Simulating the power consumption of large-scale sensor network applications, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031518]
• 6: Chris Olston , Jing Jiang , Jennifer Widom, Adaptive filters for continuous queries over distributed data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872825]
• 7: Mohamed A. Sharaf , Jonathan Beaver , Alexandros Labrinidis , Panos K. Chrysanthis, TiNA: a scheme for temporal coherency-aware in-network aggregation, Proceedings of the 3rd ACM international workshop on Data engineering for wireless and mobile access, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/940923.940937]
• 8: Qi Han , Sharad Mehrotra , Nalini Venkatasubramanian, Energy Efficient Data Collection in Distributed Sensor Environments, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.590-597, March 24-26, 2004
• 9: A. Deligiannakis, Y. Kotidis, and N. Roussopoulos, "Hierarchical in-network data aggregation with quality guarantees," in Proc. EDBT'04, Mar. 2004, pp. 658-675.
• 10: 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
• 11: Jianping Pan , Y. Thomas Hou , Lin Cai , Yi Shi , Sherman X. Shen, Topology control for wireless sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939015]
• 12: 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]
• 13: Fan Ye , Haiyun Luo , Jerry Cheng , Songwu Lu , Lixia Zhang, A two-tier data dissemination model for large-scale wireless sensor networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570664]
• 14: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in 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.958494]
• 15: Wei Ye , John Heidemann , Deborah Estrin, Medium access control with coordinated adaptive sleeping for wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.12 n.3, p.493-506, June 2004 [doi>10.1109/TNET.2004.828953]
• 16: 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]
• 17: Y. Yao and J. Gehrke, "Query processing for sensor networks," in Proc. CIDR'03, Jan. 2003.
• 18: Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in 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.958500]
• 19: Adam Silberstein , Rebecca Braynard , Jun Yang, Constraint chaining: on energy-efficient continuous monitoring in sensor networks, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142492]
• 20: Jianliang Xu , Xueyan Tang , Wang-Chien Lee, A New Storage Scheme for Approximate Location Queries in Object-Tracking Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, v.19 n.2, p.262-275, February 2008 [doi>10.1109/TPDS.2007.70740]
• 21: 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]
• 22: Jeffrey Considine , Feifei Li , George Kollios , John Byers, Approximate Aggregation Techniques for Sensor Databases, Proceedings of the 20th International Conference on Data Engineering, p.449, March 30-April 02, 2004
• 23: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031525]
• 24: 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
• 25: 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]
• 26: Michael B. Greenwald , Sanjeev Khanna, Power-conserving computation of order-statistics over sensor networks, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055597]
• 27: Nisheeth Shrivastava , Chiranjeeb Buragohain , Divyakant Agrawal , Subhash Suri, Medians and beyond: new aggregation techniques for sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031524]
• 28: Yannis Kotidis, Snapshot Queries: Towards Data-Centric Sensor Networks, Proceedings of the 21st International Conference on Data Engineering, p.131-142, April 05-08, 2005 [doi>10.1109/ICDE.2005.134]
• 29: Gregory Hartl , Baochun Li, infer: A Bayesian Inference Approach towards Energy Efficient Data Collection in Dense Sensor Networks, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.371-380, June 06-10, 2005 [doi>10.1109/ICDCS.2005.43]
• 30: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 31: D. Niculescu and B. Nath, "Ad hoc positioning (APS) using AoA," in Proc. IEEE INFOCOM'03, Apr. 2003, pp. 1734-1743.
• 32: O. Younis and S. Fahmy, "Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach," in Proc. IEEE INFOCOM'04 , Mar. 2004, pp. 629-640.
• 33: Y. Thomas Hou , Yi Shi , Hanif D. Sherali, Rate allocation in wireless sensor networks with network lifetime requirement, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989469]
• 34: C. Buragohain, D. Agrawal, and S. Suri, "Power aware routing for sensor databases," in Proc. IEEE INFOCOM'05, Mar. 2005, pp. 1747-1757.
• 35: Intae Kang , Radha Poovendran, Maximizing network lifetime of broadcasting over wireless stationary ad hoc networks, Mobile Networks and Applications, v.10 n.6, p.879-896, December 2005 [doi>10.1007/s11036-005-4445-5]
• 36: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 37: The Network Simulator--ns-2 [Online]. Available: http://www.isi.edu/ nsnam/ns/
• 38: NRL's Sensor Network Extension to ns-2 [Online]. Available: http:// www.nrlsensorsim.pf.itd.nrl.navy.mil/
• 39: Deepak Ganesan , Sylvia Ratnasamy , Hanbiao Wang , Deborah Estrin, Coping with irregular spatio-temporal sampling in sensor networks, ACM SIGCOMM Computer Communication Review, v.34 n.1, January 2004 [doi>10.1145/972374.972396]
• 40: G. K. Zipf, Human Behavior and the Principles of Least Effort. Reading, MA: Addison-Wesley, 1949.
• 41: Live From Earth and Mars (LEM) Project [Online]. Available: http:// www.k12.atmos.washington.edu/k12/grayskies/

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
      C.2.4 Distributed Systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Experimental design

General Terms:
Design, Experimentation, Performance, Reliability

Keywords:
data accuracy, data aggregation, energy efficiency, network lifetime, sensor network