Introduction

We are investigating high level languages for programming diverse, distributed networks of sensors. Our goal is to greatly simplify sensor network application design by providing high-level programming abstractions and primitives that automatically compile down to the complex, low-level operations implemented by each sensor node. Sensor networks are an emerging computing platform consisting of large numbers of small, low-powered, wireless "motes" each with limited computation, sensing, and communication abilities. Sensor networks are being investigated for applications such as environmental monitoring, seismic analysis of structures, and tracking moving vehicles. Still, sensor network programming is incredibly difficult, due to the limited capabilities and energy resources of each node as well as the unreliability of the radio channel. As a result, application designers must make many complex, low-level choices, and build up a great deal of machinery to perform routing, time synchronization, node localization, and data aggregation within the sensor network. Little of this machinery carries over directly from one application to the next, as it encapsulates application-specific tradeoffs in terms of complexity, resource usage, and communication patterns. We are interested in exploring programming language support for sensor networks. Currently, sensor network applications are implemented as complex, low-level programs that specify the behavior of individual motes. Rather, we would like to provide a high-level, global programming model where the application can be specified in terms of system-wide behavior, which is then compiled down to the per-device program. We have been developing Regiment, a spatial macroprogramming language that abstracts the sensor network state as time-varying streams, which can be groupd into regions. Regions provide a means of expression spatial and logical relationships between sensor nodes, transparent data sharing between nodes, and efficient reduction operations within regions. Our earlier work on abstract regions exposes the tradeoff between resource usage and the accuracy of collective operations, allowing applications to tune energy and bandwidth consumption to meet accuracy targets. We are also investigating the use of market-based techniques for distributed resource allocation in sensor networks. Such an approach models the network as a set of agents that operate to maximize their profit for performing simple, local actions in response to globally-advertised price information. Sensor nodes run a very simple cost-evaluation function, and global behavior is induced throughout the network by advertising price information that drives nodes to react. This project is funded by the National Science Foundation (CNS-0519675) and generous gifts from Microsoft Corporation.

Publications and Talks

LiveNet: Using Passive Monitoring to Reconstruct Sensor Network Dynamics, Bor-rong Chen, Geoffrey Peterson, Geoff Mainland, and Matt Welsh. To appear in Proceedings of the 4th IEEE/ACM International Conference on Distributed Computing in Sensor Systems (DCOSS 2008), Santorini Island, Greece, June 2008. A Utility-Based Approach to Bandwidth Allocation and Link Scheduling in Wireless Networks, Qicheng Ma, David C. Parkes, and Matt Welsh. In Proceedings of the First International Workshop on Agent Technology for Sensor Networks (ATSN-07), Honolulu, May 2007. (PDF) The Regiment Macroprogramming System, Ryan Newton, Greg Morrisett, and Matt Welsh. In Proceedings of the International Conference on Information Processing in Sensor Networks (IPSN'07), Cambridge, MA, April 2007. (PDF) Flask: A Language for Data-driven Sensor Network Programs, Geoffrey Mainland, Matt Welsh, and Greg Morrisett. Harvard University Technical Report TR-13-06, May 2006. (PDF) Decentralized, Adaptive Resource Allocation for Sensor Networks, Geoff Mainland, David C. Parkes, and Matt Welsh. To appear in Proceedings of the 2nd USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2005), May 2005. (PDF) Building up to Macroprogramming: An Intermediate Language for Sensor Networks, Ryan Newton, Arvind, and Matt Welsh. To appear in Proceedings of the Fourth International Conference on Information Processing in Sensor Networks (IPSN'05), April 2005. (PDF) Region Streams: Functional Macroprogramming for Sensor Networks, Ryan Newton and Matt Welsh. To appear in Proceedings of the First International Workshop on Data Management for Sensor Networks (DMSN), Toronto, Canada, August 2004. (PDF) Using Virtual Markets to Program Global Behavior in Sensor Networks, Geoff Mainland, Laura Kang, Sebastien Lahaie, David C. Parkes, and Matt Welsh. To appear in Proceedings of the 11th ACM SIGOPS European Workshop, Leuven, Belgium, September 2004. (PDF) Programming Sensor Networks Using Abstract Regions, Matt Welsh and Geoff Mainland. In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI '04), March 2004. (PDF) Exposing Resource Tradeoffs in Region-Based Communication Abstractions for Sensor Networks, Matt Welsh. In Proceedings of the 2nd ACM Workshop on Hot Topics in Networks (HotNets-II), November 2003. (PDF) Experimental Results and Theoretical Analysis of a Self-Organizing Global Coordinate System for Ad Hoc Sensor Networks, Jonathan Bachrach, Radhika Nagpal, Micheal Salib, and Howard Shrobe. Telecommunications Systems Journal, Special Issue on Wireless System Networks, Kluwer Academic Publishing, (in press) 2003. (PDF) TOSSIM: Accurate and Scalable Simulation of Entire TinyOS Applications, Philip Levis, Nelson Lee, Matt Welsh, and David Culler. In Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys) 2003, November 2003. (PDF) The nesC Language: A Holistic Approach to Networked Embedded Systems, David Gay, Phil Levis, Rob von Behren, Matt Welsh, Eric Brewer, and David Culler. In Proceedings of Programming Language Design and Implementation (PLDI) 2003, June 2003. (PDF) Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network, Radhika Nagpal, Howard Shrobe, and Jonathan Bachrach. In Proceedings of the 2nd International Workshop on Information Processing in Sensor Networks (IPSN '03), April 2003. (PDF) Programming Methodology for Biologically-Inspired Self-Assembling Systems, Radhika Nagpal, Attila Kondacs, and Catherine Chang. In the AAAI Spring Symposium on Computational Synthesis: From Basic Building Blocks to High Level Functionality, March 2003, published as AAAI Technical Report. (PDF) Programmable Self-Assembly Using Biologically-Inspired Multiagent Control, Radhika Nagpal. Proceedings of the 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), Bologna, Italy, July 2002. (PS) An Auction-Based Method for Decentralized Train Scheduling, David C. Parkes and Lyle H. Ungar. In Proc. 5th International Conference on Autonomous Agents (Agents'01), 2001. (PDF) An Algorithm for Group Formation in an Amorphous Computer, Radhika Nagpal and Daniel Coore. In Proceedings of the 10th International Conference on Parallel and Distributed Computing Systems (PDCS'98), Nevada, Oct 1998. (PS) Talks Where do we go from here? The Big Problems in sensor networks. Keynote, Wireless Sensing Solutions Conference, Chicago, IL, September 28, 2005. Decentralized, Adaptive Resource Allocation for Sensor Networks. Presented at NSDI'05, May 4, 2005. Market-Based Programming Paradigms for Sensor Networks. Presented at Brown University, October 27, 2004. Programming Sensor Networks Using Abstract Regions. Presented at the First Symposium on Networked Systems Design and Implementation (NSDI'04), San Francisco, March 29, 2004. Programming Primitives for Wireless Sensor Networks. Presented at Boston University Computer Science Colloquium, October 1, 2003. nesC: A Component-Oriented Language for Networked Embedded Systems. Presented at Microsoft Research, Redmond, WA, March 25, 2003.

M. Welsh, Harvard University