The regiment macroprogramming system

ABSTRACT

The development of high-level programming environments is essential if wireless sensor networks are to be accessible to non-experts. In this paper, we present the Regiment system, which consists of a high-level language for spatiotemporal macroprogramming, along with a compiler that translates global programs into node-level code. In Regiment, the programmer views the network as a set of spatially-distributed data streams. The programmer can manipulate sets of these streams that may be defined by topological or geographic relationships between nodes. Regiment provides a rich set of primitives for processing data on individual streams, manipulating regions, performing aggregation over a region, and triggering new computation within the network.

In this paper, we describe the design and implementation of the Regiment language and compiler. We describe the deglobalization process that compiles a network-wide representation of the program into a node-level, event-driven program. Deglobalization maps region operations onto associated spanning trees that establish region membership and permit efficient in-network aggregation. We evaluate Regiment in the context of a complex distributed application involving rapid detection of spatially-distributed events, such as wildfires or chemical plumes. Our results show that Regiment makes it possible to develop complex sensor network applications at a global level.

REFERENCES

• 1: Amol Bakshi , Viktor K. Prasanna , Jim Reich , Daniel Larner, The Abstract Task Graph: a methodology for architecture-independent programming of networked sensor systems, Proceedings of the 2005 workshop on End-to-end, sense-and-respond systems, applications and services, June 05-05, 2005, Seattle, Washington
• 2: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 3: E. A. Cowen and K. B. Ward. Chemical plume tracing. Environmental Fluid Mechanics, 2(1-2), June 2002.
• 4: D. M. Doolin and N. Sitar. Wireless sensors for wildfire monitoring. In Proc. SPIE Symposium on Smart Structures and Materials, 2005.
• 5: Conal Elliott , Paul Hudak, Functional reactive animation, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.263-273, June 09-11, 1997, Amsterdam, The Netherlands
• 6: R. Gummadi, O. Gnawali, and R. Govindan. Macro-programming wireless sensor networks using. In Proc. Int. Conference on Distributed Computing in Sensor Systems (DCOSS), 2005.
• 7: J. M. Hellerstein, W. Hong, S. Madden, and K. Stanek. Beyond average: Towards sophisticated sensing with queries. In Proc. the 2nd International Workshop on Information Processing in Sensor Networks (IPSN'03), March 2003.
• 8: 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
• 9: L. Luo, T. Abdelzaher, T. He, and J. Stankovic. Envirosuite: An environmentally immersive programming framework for sensor networks. ACM Transactions on Computational Logic, V(N), October 2005.
• 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: S. Nath, Y. Ke, P. B. Gibbons, B. Karp, and S. Seshan. IrisNet: An architecture for enabling sensor-enriched Internet service. Technical Report IRP-TR-03-04, Intel Research Pittsburgh, June 2003.
• 12: R. Newton. Normalizing regiment queries. http://www.regiment.us/docs, Nov 2006.
• 13: Ryan Newton , Arvind , Matt Welsh, Building up to macroprogramming: an intermediate language for sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 14: 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]
• 15: G. M. M. Welsh and G. Morrisett. Flask: A language for data-driven sensor network programs. Technical Report TR-13-06, Harvard University Technical Report, May 2006.
• 16: 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
• 17: Kamin Whitehouse , Cory Sharp , Eric Brewer , David Culler, Hood: a neighborhood abstraction for sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990079]
• 18: K. Whitehouse, F. Zhao, and J. Liu. Semantic streams: a framework for composable semantic interpretation of sensor data. In Proc. European Workshop on Wireless Sensor Networks (EWSN), 2006.
• 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

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

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Data-flow languages; Applicative (functional) languages

General Terms:
Design, Languages

Keywords:
functional macroprogramming, sensor networks