Reliable and efficient programming abstractions for wireless sensor networks

ABSTRACT

It is currently difficult to build practical and reliable programming systems out of distributed and resource-constrained sensor devices. The state of the art in today's sensornet programming is centered around a component-based language called nesC. nesC is a node-level language-a program is written for an individual node in the network-and nesC programs use the services of an operating system called TinyOS. We are pursuing an approach to programming sensor networks that significantly raises the level of abstraction over this practice. The critical change is one of perspective: rather than writing programs from the point of view of an individual node, programmers implement a central program that conceptually has access to the entire network. This approach pushes to the compiler the task of producing node-level programs that implement the desired behavio.

We present the Pleiades programming language, its compiler, and its runtime. The Pleiades language extends the C language with constructs that allow programmers to name and access node-local state within the network and to specify simple forms of concurrent execution. The compiler and runtime system cooperate to implement Pleiades programs efficiently and reliably. First, the compiler employs a novel program analysis to translate Pleiades programs into message-efficient units of work implemented in nesC. The Pleiades runtime system orchestrates execution of these units, using TinyOS services, across a network of sensor nodes. Second, the compiler and runtime system employ novel locking, deadlock detection, and deadlock recovery algorithms that guarantee serializability in the face of concurrent execution. We illustrate the readability, reliability and efficiency benefits of the Pleiades language through detailed experiments, and demonstrate that the Pleiades implementation of a realistic application performs similar to a hand-coded nesC version that contains more than ten times as much code.

REFERENCES

• 1: Gruia Calinescu , Cristina G. Fernandes , Bruce Reed, Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.137-152, June 22-24, 1998
• 2: Brian D. Carlstrom , Austen McDonald , Hassan Chafi , JaeWoong Chung , Chi Cao Minh , Christos Kozyrakis , Kunle Olukotun, The Atomos transactional programming language, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 3: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 4: Ahmed K. Elmagarmid, A survey of distributed deadlock detection algorithms, ACM SIGMOD Record, v.15 n.3, p.37-45, Sept. 1986 [doi>10.1145/15833.15837]
• 5: 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
• 6: David Gelernter , Nicholas Carriero, Coordination languages and their significance, Communications of the ACM, v.35 n.2, p.96, Feb. 1992 [doi>10.1145/129630.376083]
• 7: 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]
• 8: R. Gummadi, O. Gnawali, and R. Govindan. Macro-programming wireless sensor networks using kairos. In DCOSS 2005.
• 9: Ramakrishna Gummadi , Nupur Kothari , Todd Millstein , Ramesh Govindan, Declarative failure recovery for sensor networks, Proceedings of the 6th international conference on Aspect-oriented software development, March 12-16, 2007, Vancouver, British Columbia, Canada [doi>10.1145/1218563.1218583]
• 10: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 11: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, ACM SIGOPS Operating Systems Review, v.34 n.5, p.93-104, Dec. 2000
• 12: Galen C. Hunt , Michael L. Scott, The Coign automatic distributed partitioning system, Proceedings of the third symposium on Operating systems design and implementation, p.187-200, February 1999, New Orleans, Louisiana, United States
• 13: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 14: Charles Koelbel, An overview of High Performance Fortran, ACM SIGPLAN Fortran Forum, v.11 n.4, p.9-16, Dec. 1992 [doi>10.1145/140734.140736]
• 15: Lakshman Krishnamurthy , Robert Adler , Phil Buonadonna , Jasmeet Chhabra , Mick Flanigan , Nandakishore Kushalnagar , Lama Nachman , Mark Yarvis, Design and deployment of industrial sensor networks: experiences from a semiconductor plant and the north sea, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098926]
• 16: B. J. Kuipers and Y.-T. Byun. A Robust Qualitative Method for Spatial Learning in Unknown Environments. In AAAI 1988.
• 17: Barbara Liskov, Distributed programming in Argus, Communications of the ACM, v.31 n.3, p.300-312, March 1988 [doi>10.1145/42392.42399]
• 18: Hongzhou Liu , Tom Roeder , Kevin Walsh , Rimon Barr , Emin Gün Sirer, Design and implementation of a single system image operating system for ad hoc networks, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067187]
• 19: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 20: Bill McCloskey , Feng Zhou , David Gay , Eric Brewer, Autolocker: synchronization inference for atomic sections, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.346-358, January 11-13, 2006, Charleston, South Carolina, USA
• 21: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 22: Matthias Neubauer , Peter Thiemann, From sequential programs to multi-tier applications by program transformation, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.221-232, January 12-14, 2005, Long Beach, California, USA
• 23: 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
• 24: 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]
• 25: Yang Ni , Ulrich Kremer , Adrian Stere , Liviu Iftode, Programming ad-hoc networks of mobile and resource-constrained devices, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 26: C. Sharp, S. Schaffert, A. Woo, N. Sastry, C. Karlof, S. Sastry, and D. Culler. Design and implementation of a sensor network system for vehicle tracking and autonomous interception. In EWSN 2005.
• 27: Gilman Tolle , Joseph Polastre , Robert Szewczyk , David Culler , Neil Turner , Kevin Tu , Stephen Burgess , Todd Dawson , Phil Buonadonna , David Gay , Wei Hong, A macroscope in the redwoods, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098925]
• 28: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

General Terms:
Design, Experimentation, Languages, Performance, Reliability

Keywords:
deadlocks, energy efficiency, macroprogramming, serializability, wireless sensor networks