Hood: a neighborhood abstraction for sensor networks

ABSTRACT

This paper proposes a neighborhood programming abstraction for sensor networks, wherein a node can identify a subset of nodes around it by a variety of criteria and share state with those nodes. This abstraction allows developers to design distributed algorithms in terms of the neighborhood abstraction itself, instead of decomposing them into component parts such as messaging protocols, data caches, and neighbor lists. In those applications that are already neighborhood-based, this abstraction is shown to facilitate good application design and to reduce algorithmic complexity, inter-component coupling, and total lines of code. The abstraction as defined here has been successfully used to implement several complex applications and is shown to capture the essence of many more existing distributed sensor network algorithms.

REFERENCES

• 1: Kenneth P. Birman, The process group approach to reliable distributed computing, Communications of the ACM, v.36 n.12, p.37-53, Dec. 1993 [doi>10.1145/163298.163303]
• 2: Linda Briesemeister and Gunter Hommel. Localized Group Membership Service for Ad Hoc Networks. In International Workshop on Ad Hoc Networking (IWAHN), pages 94--100, AUG 2002.
• 3: William Joseph Butera , V. Michael Bove, Jr., Programming a paintable computer, 2002
• 4: David Chaiken , John Kubiatowicz , Anant Agarwal, LimitLESS directories: A scalable cache coherence scheme, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.224-234, April 08-11, 1991, Santa Clara, California, United States
• 5: D. D. Corkill. Blackboard Systems. AI Expert, pages 40--47, 1991.
• 6: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 7: Armando Fox , Eric A. Brewer, Harvest, Yield, and Scalable Tolerant Systems, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.174, March 28-30, 1999
• 8: 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
• 9: David Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.80-112, Jan. 1985 [doi>10.1145/2363.2433]
• 10: Milan Jovanovic , Veljko Milutinovic, An Overview of Reflective Memory Systems, IEEE Concurrency, v.7 n.2, p.56-64, April 1999 [doi>10.1109/4434.766965]
• 11: Philip Levis , David Culler, Maté: a tiny virtual machine for sensor networks, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 12: Dragos Niculescu and Badri Nath. Ad Hoc Positioning System (APS). In GLOBECOM (1), pages 2926--2931, 2001.
• 13: Sanjay Raina, Virtual Shared Memory: A Survey of Techniques and Systems, University of Bristol, Bristol, UK, 1992
• 14: Gruia-Catalin Roman , Qingfeng Huang , Ali Hazemi, Consistent group membership in ad hoc networks, Proceedings of the 23rd International Conference on Software Engineering, p.381-388, May 12-19, 2001, Toronto, Ontario, Canada
• 15: Chia Shen , Ichiro Mizunuma, RT-CRM: Real-Time Channel-Based Reflective Memory, IEEE Transactions on Computers, v.49 n.11, p.1202-1214, November 2000 [doi>10.1109/12.895937]
• 16: John F. Shoch , Jon A. Hupp, The “worm” programs—early experience with a distributed computation, Communications of the ACM, v.25 n.3, p.172-180, March 1982 [doi>10.1145/358453.358455]
• 17: Matt Welsh and Geoff Mainland. Programming Sensor Networks Using Abstract Regions. In The First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI '04), March 2004.
• 18: Kamin Whitehouse. The Design of Calamari: an Ad-hoc Localization System for Sensor Networks. Master's thesis, University of California at Berkeley, 2002.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Patterns (e.g., client/server, pipeline, blackboard)

General Terms:
Design

Keywords:
abstraction, data sharing, distributed algorithms, neighborhood, sensor networks