Event-based constraints for sensornet programming

ABSTRACT

We propose a sensornet programming model based on declarative spatio-temporal constraints on events only, not sensors. Where previous approaches conflate events and sensors because they are often colocated, a focus on events allows programmers to specify their intent more directly, and better supports remote sensing devices such as cameras, microphones, and rangefinders. In our model, complex events are specified as aggregations of events in time or space, without regard to sensor locations or communication paths. New techniques are required to aggregate events based on these constraints without knowledge of nearby nodes.

We present a decentralized, scalable event detection framework that allows for efficient in-network aggregation without coupling events and sensors. First, we describe a SQL-style declarative language with spatio-temporal constraints between events that can be used to express complex events. Next, we show how these complex events can be assembled efficiently. The distributed event detection mechanism scales to very large networks, load balances work across sensors, and is fault tolerant to network partitions and node failure.

REFERENCES

• 1: B. Brumitt, B. Meyers, J. Krumm, A. Kern, and S. A. Shafer. Easyliving: Technologies for intelligent environments. In HUC, 2000.
• 2: S. Chakravarthy and D. Mishra. Snoop: An expressive event specification language for active databases. Data Knowledge Engineering, 14(1), 1994.
• 3: S. Gatziu and K. R. Dittrich. Detecting composite events in active database systems using petri nets. In RIDE-ADS, 1994.
• 4: B. Karp and H. T. Kung. GPSR: greedy perimeter stateless routing for wireless networks. In MobiCom '00: Proceedings of the 6th annual international conference on Mobile computing and networking. ACM Press, 2000.
• 5: L. Luo, T. F. Abdelzaher, T. He, and J. A. Stankovic. Envirosuite: An environmentally immersive programming framework for sensor networks. ACM Trans. Embedded Comput. Syst., 5(3), 2006.
• 6: S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. Tag: A tiny aggregation service for ad-hoc sensor networks. In OSDI, 2002.
• 7: R. Newton, G. Morrisett, and M. Welsh. The regiment macroprogramming system. In IPSN, 2007.
• 8: The Network Simulator - ns-2. http://www.isi.edu/nsnam/ns/.
• 9: N. Paton and O. Diaz. Active Database Systems. ACM Computing Surveys, 1(31):63--103, 1999.
• 10: S. Ratnasamy, B. Karp, S. Shenker, D. Estrin, R. Govindan, L. Yin, and F. Yu. Data-centric storage in sensornets with ght, a geographic hash table. Mob. Netw. Appl., 8(4), 2003.
• 11: S. Ratnasamy, B. Karp, L. Yin, F. Yu, D. Estrin, R. Govindan, and S. Shenker. GHT: a geographic hash table for data-centric storage. In WSNA '02: Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications. ACM Press, 2002.
• 12: G. Simon, M. Maróti, Á. Lédeczi, G. Balogh, B. Kusy, A. Nádas, G. Pap, J. Sallai, and K. Frampton. Sensor network-based countersniper system. in Proc. SenSys, 2004.
• 13: M. Welsh and G. Mainland. Programming sensor networks using abstract regions. In NSDI, 2004.
• 14: K. Whitehouse, C. Sharp, D. E. Culler, and E. A. Brewer. Hood: A neighborhood abstraction for sensor networks. In MobiSys, 2004.
• 15: Y. Yao and J. Gehrke. The cougar approach to in-network query processing in sensor networks. SIGMOD Record, 31(3), 2002.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Design, Languages, Performance

Keywords:
complex event, constraints, programming model, sensor networks