Programming sensor networks using abstract regions

ABSTRACT

Wireless sensor networks are attracting increased interest for a wide range of applications, such as environmental monitoring and vehicle tracking. However, developing sensor network applications is notoriously difficult, due to extreme resource limitations of nodes, the unreliability of radio communication, and the necessity of low power operation. Our goal is to simplify application design by providing a set of programming primitives for sensor networks that abstract the details of low-level communication, data sharing, and collective operations.

We present abstract regions, a family of spatial operators that capture local communication within regions of the network, which may be defined in terms of radio connectivity, geographic location, or other properties of nodes. Regions provide interfaces for identifying neighboring nodes, sharing data among neighbors, and performing efficient reductions on shared variables. In addition, abstract regions expose the trade-off between the accuracy and resource usage of communication operations. Applications can adapt to changing network conditions by tuning the energy and bandwidth usage of the underlying communication substrate. We present the implementation of abstract regions in the TinyOS programming environment, as well as results demonstrating their use for building adaptive sensor network applications.

References

1. {1} S. Adlakha, S. Ganeriwal, C. Schurgers, and M. B. Srivastava. Density, accuracy, latency and lifetime tradeoffs in wireless sensor networks - a multidimensional design perspective. In review, 2003.]]
2. {2} A. Adya, J. Howell, M. Theimer, W. J. Bolosky, and J. R. Douceur. Cooperative task management without manual stack management, or, event-driven programming is not the opposite of threaded programming. In Proc. the USENIX 2002 Annual Conference, June 2002.]]
3. {3} C. Borcea, C. Intanagonwiwat, P. Kang, U. Kremer, and L. Iftode. Spatial programming using smart messages: Design and implementation. In Proc. the 24th International Conference on Distributed Computing Systems (ICDCS 2004), March 2004.]]
4. {4} A. Boulis, S. Ganeriwal, and M. B. Srivastava. Aggregation in sensor networks: An energy - accuracy tradeoff. In Proc. IEEE workshop on Sensor Network Protocols and Applications, 2003.]]
5. {5} R. Brooks, P. Ramanathan, and A. Sayeed. Distributed target classification and tracking in sensor networks. Proceedings of the IEEE, November 2003.]]
6. {6} Center for Embedded Network Sensing. Contaminant transport monitoring. http://cens.ucla.edu/Research/ Applications/ctm.htm.]]
7. {7} Center for Information Technology Research in the Interest of Society. Smart buildings admit their faults. http: //www.citris.berkeley.edu/applications/ disaster_response/smartbuil%dings.html, 2002.]]
8. {8} A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao. Habitat monitoring: Application driver for wireless communications technology. In Proc. the Workshop on Data Communications in Latin America and the Caribbean, Apr. 2001.]]
9. {9} R. X. Cringely. Chase Cringely: Finding Meaning in a Lost Life. http://www.pbs.org/cringely/pulpit/ pulpit20020425.html.]]
10. {10} D. Ganesan, B. Greenstein, D. Perelyubskiy, D. Estrin, and J. Heidemann. An evaluation of multi-resolution search and storage in resource-constrained sensor networks. In Proc. the First ACM Conference on Embedded Networked Sensor Systems (Sen-Sys 2003), November 2003.]]
11. {11} 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 Proc. Programming Language Design and Implementation (PLDI), June 2003.]]
12. {12} B. Greenstein, D. Estrin, R. Govindan, S. Ratnasamy, and S. Shenker. DIFS: A distributed index for features in sensor networks. In Proc. the First IEEE International Workshop on Sensor Network Protocols and Applications, May 2003.]]
13. {13} W. Gropp, E. Lusk, and A. Skjellum. Using MPI: Portable Parallel Programming with the Message Passing Interface. MIT Press, Cambridge, Massachusetts, 1994.]]
14. {14} J. S. Heidemann, F. Silva, C. Intanagonwiwat, R. Govindan, D. Estrin, and D. Ganesan. Building efficient wireless sensor networks with low-level naming. In Proc. the 18th SOSP, Banff, Canada, October 2001.]]
15. {15} W. Heinzelman, J. Kulik, and H. Balakrishnan. Adaptive protocols for information dissemination in wireless sensor networks. In Proc. the 5th ACM/IEEE Mobicom Conference, August 1999.]]
16. {16} 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.]]
17. {17} J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. E. Culler, and K. S. J. Pister. System architecture directions for networked sensors. In Proc. the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 93-104, Boston, MA, USA, Nov. 2000.]]
18. {18} C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proc. International Conference on Mobile Computing and Networking, Aug. 2000.]]
19. {19} B. Karp and H. T. Kung. GPSR: Greedy perimeter stateless routing for wireless networks. In Proc. the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA, August 2000.]]
20. {20} V. A. Kottapalli, A. S. Kiremidjian, J. P. Lynch, E. Carryer, T. W. Kenny, K. H. Law, and Y. Lei. Two-tiered wireless sensor network architecture for structural health monitoring. In Proc. the SPIE 10th Annual International Symposium on Smart Structures and Materials, San Diego, CA, March 2000.]]
21. {21} P. Levis, N. Lee, M. Welsh, and D. Culler. TOSSIM: Accurate and scalable simulation of entire TinyOS applications. In Proc. the First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003), November 2003.]]
22. {22} D. Li, K. Wong, Y. H. Hu, and A. Sayeed. Detection, classification and tracking of targets in distributed sensor networks. IEEE Signal Processing Magazine, 19(2), March 2002.]]
23. {23} X.-Y. Li, P.-J. Wan, Y. Wang, and O. Frieder. Sparse power efficient topology for wireless networks. In Proc. 35th Annual Hawaii International Conference on System Sciences, January 2002.]]
24. {24} J. Liu, P. Cheung, L. Guibas, and F. Zhao. A dual-space approach to tracking and sensor management in wireless sensor networks. In Proc. the First ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), Atlanta, Georgia, September 2002.]]
25. {25} S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. TAG: A Tiny AGgregation Service for Ad-Hoc Sensor Networks. In Proc. the 5th OSDI, December 2002.]]
26. {26} S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. The design of an acquisitional query processor for sensor networks. In Proc. the ACM SIGMOD 2003 Conference, June 2003.]]
27. {27} A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson. Wireless sensor networks for habitat monitoring. In ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02), Atlanta, GA, USA, Sept. 2002.]]
28. {28} S. Nath, Y. Ke, P. B. Gibbons, B. Karp, and S. Seshan. Iris-Net: An architecture for enabling sensor-enriched Internet service. Technical Report IRP-TR-03-04, Intel Research Pittsburgh, June 2003.]]
29. {29} K. S. Pister. Tracking vehicles with a uav-delivered sensor network. http://robotics.eecs.berkeley.edu/ ~pister/29Palms0103/, March 2001.]]
30. {30} S. Ratnasamy, B. Karp, L. Yin, F. Yu, D. Estrin, R. Govindan, and S. Shenker. GHT: A geographic hash table for data-centric storage in sensornets. In Proc. the First ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), Atlanta, Georgia, September 2002.]]
31. {31} J. Shewchuk. Delaunay refinement algorithms for triangular mesh generation. Computational Geometry: Theory and Applications , 22(1-3):21-74, May 2002.]]
32. {32} T. von Eicken, D. E. Culler, S. C. Goldstein, and K. E. Schauser. Active messages: a mechanism for integrating communication and computation. In Proc. the 19th Annual International Symposium on Computer Architecture, pages 256-266, May 1992.]]
33. {33} M. Welsh. Exposing resource tradeoffs in region-based communication abstractions for sensor networks. In Proc. the 2nd ACM Workshop on Hot Topics in Networks (HotNets-II), November 2003.]]
34. {34} M. Welsh, D. Myung, M. Gaynor, and S. Moulton. Resuscitation monitoring with a wireless sensor network. In Supplement to Circulation: Journal of the American Heart Association, October 28, 2003.]]
35. {35} K. Whitehouse, C. Sharp, E. Brewer, and D. Culler. Hood: A neighborhood abstraction for sensor networks. In Proc. the International Conference on Mobile Systems, Applications, and Services (MOBISYS '04), June 2004.]]
36. {36} A. Woo, T. Tong, and D. Culler. Taming the underlying challenges of reliable multihop routing in sensor networks. In Proc. the First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003), November 2003.]]
37. {37} Y. Xu and W.-C. Lee. On localized prediction for power efficient object tracking in sensor networks. In Proc. 1st International Workshop on Mobile Distributed Computing, May 2003.]]
38. {38} Y. Yao and J. E. Gehrke. The Cougar approach to in-network query processing in sensor networks. ACM Sigmod Record, 31(3), September 2002.]]

Index Terms

• Hardware

  • Communication hardware, interfaces and storage

    • Signal processing systems

• Networks

  • Network services

    • Network monitoring

  • Network types

    • Mobile networks

    • Wireless access networks

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

        • Organizing principles for web applications