The design and implementation of a declarative sensor network system

ABSTRACT

Sensor networks are notoriously difficult to program, given that they encompass the complexities of both distributed and embedded systems. To address this problem, we present the design and implementation of a declarative sensor network platform, DSN: a declarative language, compiler and runtime suitable for programming a broad range of sensornet applications. We demonstrate that our approach is a natural fit for sensor networks by specifying several very different classes of traditional sensor network protocols, services and applications entirely declaratively -- these include tree and geographic routing, link estimation, data collection, event tracking, version coherency, and localization. To our knowledge, this is the first time these disparate sensornet tasks have been addressed by a single high-level programming environment. Moreover, the declarative approach accommodates the desire for architectural flexibility and simple management of limited resources. Our results suggest that the declarative approach is well-suited to sensor networks, and that it can produce concise and flexible code by focusing on what the code is doing, and not on how it is doing it.

REFERENCES

• 1: Dsn programming tutorial. http://db.cs.berkeley.edu/dsn.
• 2: Omega testbed. http://omega.cs.berkeley.edu.
• 3: Tinyos. http://www.tinyos.net.
• 4: Serge Abiteboul , Zoë Abrams , Stefan Haar , Tova Milo, Diagnosis of asynchronous discrete event systems: datalog to the rescue!, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065214]
• 5: Cassandra: Distributed Access Control Policies with Tunable Expressiveness, Proceedings of the Fifth IEEE International Workshop on Policies for Distributed Systems and Networks, p.159, June 07-09, 2004
• 6: David Chu , Arsalan Tavakoli , Lucian Popa , Joseph Hellerstein, Entirely declarative sensor network systems, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 7: David Chu , Arsalan Tavakoli , Lucian Popa , Joseph Hellerstein, Entirely declarative sensor network systems, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 8: David Culler , Prabal Dutta , Cheng Tien Ee , Rodrigo Fonseca , Jonathan Hui , Philip Levis , Joseph Polastre , Scott Shenker , Ion Stoica , Gilman Tolle , Jerry Zhao, Towards a sensor network architecture: lowering the waistline, Proceedings of the 10th conference on Hot Topics in Operating Systems, p.24-24, June 12-15, 2005, Santa Fe, NM
• 9: C. Ee, R. Fonseca, S. Kim, A. Tavakoli, D. Culler, S. Shenker, and I. Stoica. A Network Layer Architecture for Sensornets. In Under Submission, 2006.
• 10: Cheng Tien Ee , Sylvia Ratnasamy , Scott Shenker, Practical data-centric storage, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.24-24, May 08-10, 2006, San Jose, CA
• 11: Rodrigo Fonseca , Sylvia Ratnasamy , Jerry Zhao , Cheng Tien Ee , David Culler , Scott Shenker , Ion Stoica, Beacon vector routing: scalable point-to-point routing in wireless sensornets, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.329-342, May 02-04, 2005
• 12: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 13: Omprakash Gnawali , Ki-Young Jang , Jeongyeup Paek , Marcos Vieira , Ramesh Govindan , Ben Greenstein , August Joki , Deborah Estrin , Eddie Kohler, The Tenet architecture for tiered sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182823]
• 14: Ben Greenstein , Eddie Kohler , Deborah Estrin, A sensor network application construction kit (SNACK), Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031505]
• 15: Ramakrishna Gummadi , Nupur Kothari , Ramesh Govindan , Todd Millstein, Kairos: a macro-programming system for wireless sensor networks, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom [doi>10.1145/1095810.1118600]
• 16: Joseph M. Hellerstein , Michael Stonebraker, Readings in Database Systems: Fourth Edition, The MIT Press, 2005
• 17: X. Jiang, J. Taneja, J. Ortiz, A. Tavakoli, P. Dutta, J. Jeong, D. Culler, P. Levis, and S. Shenker. An architecture for energy management in wireless sensor networks. In International Workshop on Wireless Sensor Network Architecture (WSNA07), 2007.
• 18: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 19: Robert Morris , Eddie Kohler , John Jannotti , M. Frans Kaashoek, The Click modular router, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.217-231, December 12-15, 1999, Charleston, South Carolina, United States
• 20: Joel Koshy , Raju Pandey, VMSTAR: synthesizing scalable runtime environments for sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098945]
• 21: Ravi Krishnamurthy , Raghu Ramakrishnan , Oded Shmueli, A framework for testing safety and effective computability of extended datalog, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.154-163, June 01-03, 1988, Chicago, Illinois, United States
• 22: Butler Lampson, Getting computers to understand, Journal of the ACM (JACM), v.50 n.1, p.70-72, January 2003 [doi>10.1145/602382.602404]
• 23: Ben Leong , Barbara Liskov , Robert Morris, Geographic routing without planarization, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.25-25, May 08-10, 2006, San Jose, CA
• 24: Philip Levis , David Gay , David Culler, Active sensor networks, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.343-356, May 02-04, 2005
• 25: Philip Levis , Nelson Lee , Matt Welsh , David Culler, TOSSIM: accurate and scalable simulation of entire TinyOS applications, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958506]
• 26: Philip Levis , Neil Patel , David Culler , Scott Shenker, Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.2-2, March 29-31, 2004, San Francisco, California
• 27: Boon Thau Loo , Tyson Condie , Minos Garofalakis , David E. Gay , Joseph M. Hellerstein , Petros Maniatis , Raghu Ramakrishnan , Timothy Roscoe , Ion Stoica, Declarative networking: language, execution and optimization, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142485]
• 28: Boon Thau Loo , Tyson Condie , Joseph M. Hellerstein , Petros Maniatis , Timothy Roscoe , Ion Stoica, Implementing declarative overlays, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 29: Boon Thau Loo , Joseph M. Hellerstein , Ion Stoica , Raghu Ramakrishnan, Declarative routing: extensible routing with declarative queries, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 30: 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]
• 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: G. Mainland, M. Welsh, and G. Morrisett. Flask: A language for data-driven sensor network programs. Technical Report TR-13-06, Harvard Tech Report, May 2006.
• 33: Ryan Newton , Matt Welsh, Region streams: functional macroprogramming for sensor networks, 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.1052213]
• 34: S. Oh, P. Chen, M. Manzo, and S. Sastry. Instrumenting wireless sensor networks for real-time surveillance. In Proc. of the International Conference on Robotics and Automation, May 2006.
• 35: James Ong , Dennis Fogg , Michael Stonebraker, Implementation of data abstraction in the relational database system INGRES, ACM SIGMOD Record, v.14 n.1, p.1-14, 1983 [doi>10.1145/984540.984541]
• 36: Joseph Polastre , Jonathan Hui , Philip Levis , Jerry Zhao , David Culler , Scott Shenker , Ion Stoica, A unifying link abstraction for wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098928]
• 37: Joseph Polastre , Robert Szewczyk , David Culler, Telos: enabling ultra-low power wireless research, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 38: R. Ramakrishnan and J. D. Ullman. A survey of research on deductive database systems. Journal of Logic Programming, 23(2):125--149, 1993.
• 39: Ananth Rao , Sylvia Ratnasamy , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 40: Atul Singh , Petros Maniatis , Timothy Roscoe , Peter Druschel, Using queries for distributed monitoring and forensics, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 41: R. Szewczyk, J. Polastre, A. Mainwaring, and D. Culler. Lessons from a sensor network expedition. In 1st European Workshop on Wireless Sensor Networks (EWSN), 2004.
• 42: G. Tolle and D. Culler. Design of an application-cooperative management system for wireless sensor networks. January 2005.
• 43: Matt Welsh , Geoff Mainland, Programming sensor networks using abstract regions, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.3-3, March 29-31, 2004, San Francisco, California
• 44: Geoff Werner-Allen , Konrad Lorincz , Jeff Johnson , Jonathan Lees , Matt Welsh, Fidelity and yield in a volcano monitoring sensor network, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.27-27, November 06-08, 2006, Seattle, WA
• 45: John Whaley , Monica S. Lam, Cloning-based context-sensitive pointer alias analysis using binary decision diagrams, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 46: K. Whitehouse, J. Liu, and F. Zhao. Semantic streams: a framework for composable inference over sensor data. In The Third European Workshop on Wireless Sensor Networks (EWSN), Springer-Verlag Lecture Notes in Computer Science, February 2006.
• 47: A. Woo and D. Culler. Evaluation of efficient link reliability estimators for low-power wireless networks, 2003.
• 48: Heng Zeng , Carla S. Ellis , Alvin R. Lebeck , Amin Vahdat, Currentcy: a unifying abstraction for expressing energy management policies, Proceedings of the annual conference on USENIX Annual Technical Conference, p.4-4, June 09-14, 2003, San Antonio, Texas

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

General Terms:
Design, Languages, Performance

Keywords:
declarative programming, sensor networks