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. G. Calinescu, C. G. Fernandes, and B. Reed. Multicuts in unweighted graphs with bounded degree and bounded tree-width. LNCS 1998.
2. B. D. Carlstrom, A. McDonald, H. Chafi, J. Chung, C. C. Minh, C. Kozyrakis, and K. Olukotun. The atomos transactional programming language. In PLDI 2006.
3. D. E. Culler, A. C. Arpaci-Dusseau, S. C. Goldstein, A. Krishnamurthy, S. Lumetta, T. von Eicken, and K. A. Yelick. Parallel programming in split-c. In Supercomputing, 1993.
4. A. K. Elmagarmid. A survey of distributed deadlock detection algorithms. SIGMOD Rec., 1986.
5. D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, and D. Culler. The nesC Language: A Holistic Approach to Networked Embedded Systems. In PLDI 2003.
6. D. Gelernter and N. Carriero. Coordination languages and their significance. Commun. ACM, 1992.
7. O. Gnawali, BGreenstein, K.-Y. Jang, A. Joki, J. Paek, M. Vieira, D. Estrin, R. Govindan, and E. Kohler. The tenet architecture for tiered sensor networks. In SenSys 2006.
8. R. Gummadi, O. Gnawali, and R. Govindan. Macro-programming wireless sensor networks using kairos. In DCOSS 2005.
9. R. Gummadi, N. Kothari, T. Millstein, and R. Govindan. Declarative failure recovery for sensor networks. In AOSD 2007.
10. T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. Composable memory transactions. In PPoPP 2005.
11. J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister. System architecture directions for networked sensors. SIGOPS Oper. Syst. Rev., 2000.
12. G. C. Hunt and M. L. Scott. The coign automatic distributed partitioning system. In OSDI 1999.
13. P. Keleher, A. L. Cox, and W. Zwaenepoel. Lazy release consistency for software distributed shared memory. In ISCA 1992, 1992.
14. C. Koelbel. An overview of high performance fortran. SIGPLAN Fortran Forum, 11(4), 1992.
15. L. Krishnamurthy, R. Adler, P. Buonadonna, J. Chhabra, M. Flanigan, N. Kushalnagar, L. Nachman, and M. Yarvis. Design and Deployment of Industrial Sensor Networks: Experiences from a Semiconductor Plant and the North Sea. In SenSys 2005.
16. B. J. Kuipers and Y.-T. Byun. A Robust Qualitative Method for Spatial Learning in Unknown Environments. In AAAI 1988.
17. B. Liskov. Distributed programming in argus. Commun. ACM, 31(3), 1988.
18. H. Liu, T. Roeder, K. Walsh, R. Barr, and E. G. Sirer. Design and implementation of a single system image operating system for ad hoc networks. In MobiSys 2005.
19. S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. The design of an acquisitional query processor for sensor networks. In SIGMOD 2003.
20. B. McCloskey, F. Zhou, D. Gay, and E. Brewer. Autolocker: synchronization inference for atomic sections. In POPL 2006.
21. G. C. Necula, S. McPeak, S. Rahul, and W. Weimer. CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs. In Conference on Compilier Construction, 2002.
22. M. Neubauer and P. Thiemann. From sequential programs to multi-tier applications by program transformation. In POPL 2005.
23. R. Newton, Arvind, and M. Welsh. Building up to macroprogramming: an intermediate language for sensor networks. In IPSN 2005.
24. R. Newton and M. Welsh. Region streams: Functional macroprogramming for sensor networks. In DMSN 2004.
25. Y. Ni, U. Kremer, A. Stere, and LIftode. Programming ad--hoc networks of mobile and resource-constrained devices. In PLDI 2005.
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. G. Tolle, J. Polastre, R. Szewczyk, D. Culler, N. Turner, K. Tu, S. Burgess, T. Dawson, P. Buonadonna, D. Gay, and W. Hong. A Macroscope in the Redwoods. In SenSys 2005.
28. M. Welsh and G. Mainland. Programming sensor networks using abstract regions. In NSDI 2004.

Index Terms

• Computing methodologies

  • Distributed computing methodologies

    • Distributed programming languages

• Software and its engineering

  • Software notations and tools

    • Context specific languages

      • Specialized application languages

    • General programming languages

      • Language types

        • Distributed programming languages