Constraint chaining: on energy-efficient continuous monitoring in sensor networks

ABSTRACT

Wireless sensor networks have created new opportunities for data collection in a variety of scenarios, such as environmental and industrial, where we expect data to be temporally and spatially correlated. Researchers may want to continuously collect all sensor data from the network for later analysis. Suppression, both temporal and spatial, provides opportunities for reducing the energy cost of sensor data collection. We demonstrate how both types can be combined for maximal benefit. We frame the problem as one of monitoring node and edge constraints. A monitored node triggers a report if its value changes. A monitored edge triggers a report if the difference between its nodes' values changes. The set of reports collected at the base station is used to derive all node values. We fully exploit the potential of this global inference in our algorithm, CONCH, short for constraint chaining. Constraint chaining builds a network of constraints that are maintained locally, but allow a global view of values to be maintained with minimal cost. Network failure complicates the use of suppression, since either causes an absence of reports. We add enhancements to CONCH to build in redundant constraints and provide a method to interpret the resulting reports in case of uncertainty. Using simulation we experimentally evaluate CONCH's effectiveness against competing schemes in a number of interesting scenarios.

REFERENCES

• 1: K. Chintalapudi and R. Govindan. Localized edge detection in sensor fields. In Proc. of the 2003 IEEE Sensor Network Protocols and Applications, May 2003.
• 2: 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 (ICDE'06), p.48, April 03-07, 2006 [doi>10.1109/ICDE.2006.21]
• 3: Chuck Conner. Modeling Heat Transfer in Parallel. http://www.cas.usf.edu/~cconnor/parallel/2dheat/2dheat.html.
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: Crossbow Inc. MPR-Mote Processor Radio Board User's Manual.
• 6: Antonios Deligiannakis , Yannis Kotidis , Nick Roussopoulos, Compressing historical information in sensor networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007628]
• 7: 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]
• 8: Ankur Jain , Edward Y. Chang , Yuan-Fang Wang, Adaptive stream resource management using Kalman Filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007573]
• 9: Yannis Kotidis, Snapshot Queries: Towards Data-Centric Sensor Networks, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.131-142, April 05-08, 2005 [doi>10.1109/ICDE.2005.134]
• 10: 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]
• 11: Amit Manjhi , Suman Nath , Phillip B. Gibbons, Tributaries and deltas: efficient and robust aggregation in sensor network streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066191]
• 12: X. Meng, L. Li, T. Nandagopal, and S. Lu. Event contour: An efficient and robust mechanism for tasks in sensor networks. Technical report, UCLA, 2004.
• 13: Sundeep Pattem , Bhaskar Krishnamachari , Ramesh Govindan, The impact of spatial correlation on routing with compression in wireless sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984627]
• 14: D. Petrovic, R. Shah, K. Ramchandran, and J. Rabaey. Data funneling: Routing with aggregation and compression for wireless sensor networks. In Proc. of the 2003 IEEE Sensor Network Protocols and Applications, May 2003.
• 15: 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]
• 16: 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]
• 17: Ignacio Solis , Katia Obraczka, Ef.cient Continuous Mapping in Sensor Networks Using Isolines, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.325-332, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.26]
• 18: 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]
• 19: 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]
• 20: Z. Zhou, S. Das, and H. Gupta. Connected k-coverage problem in sensor networks. In Proc. of the 2004 IEEE Intl. Conf. on Computer Communications and Networks, Oct. 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Algorithms, Design

Keywords:
continuous queries, sensor networks