Building efficient wireless sensor networks with low-level naming

Abstract

In most distributed systems, naming of nodes for low-level communication leverages topological location (such as node addresses) and is independent of any application. In this paper, we investigate an emerging class of distributed systems where low-level communication does not rely on network topological location. Rather, low-level communication is based on attributes that are external to the network topology and relevant to the application. When combined with dense deployment of nodes, this kind of named data enables in-network processing for data aggregation, collaborative signal processing, and similar problems. These approaches are essential for emerging applications such as sensor networks where resources such as bandwidth and energy are limited. This paper is the first description of the software architecture that supports named data and in-network processing in an operational, multi-application sensor-network. We show that approaches such as in-network aggregation and nested queries can significantly affect network traffic. In one experiment aggregation reduces traffic by up to 42% and nested queries reduce loss rates by 30%. Although aggregation has been previously studied in simulation, this paper demonstrates nested queries as another form of in-network processing, and it presents the first evaluation of these approaches over an operational testbed.

References

1. 1 W. Adjie-Winoto, E. Schwartz, H. Balakrishnan, and J. Lilley. The design and implementation of an intentional naming system. In Proceedings of the 17th Symposium on Operating Systems Principles, pages 186-201, Kiawah Island, SC, USA, Dee. 1999. ACM.]]
2. 2 E. Amir, S. McCanne, and R. H. Katz. An active service framework and its application to real-time multimedia transcoding. In Proceedings of the ACM SIGCOMM Conference, pages 178-189, Vancouver, Canada, Sept. 1998. ACM.]]
3. 3 F. Bennett, D. Clarke, J. B. Evans, A. Hopper, A. Jones, and D. Leask. Piconet: Embedded mobile networking. IEEEPersonal Communications Magazine, 4(5):8-15, Oct. 1997.]]
4. 4 K.P. Birman. The process group approach to reliable distributed computing. Communications of the ACM, 36(12):36-53, Dec. 1993.]]
5. 5 P. Bonnet, J. Gehrke, T. Mayr, and P. Seshadri. Query processing in a device database system. Technical Report TR99-1775, Cornell University, Oct. 1999.]]
6. 6 M. Bowman, S. K. Debray, and L. L. Peterson. Reasoning about naming systems. ACM Transactions on Programming Languages and Systems, 15(5):795-825, Nov. 1993.]]
7. 7 J. Broth, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jeteheva. A performance comparision of multi-hop wireless ad hoe network routing protocols. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, pages 85-97, Dallas, Texas, USA, OCt. 1998. ACM.]]
8. 8 R.R. Brooks and S. S. Iyengar. Robust distributed computing and sensing algorithm. IEEE Computer, 29(6):53-60, June 1996.]]
9. 9 N. Carriero and D. Gelernter. The S/Net's Linda kernel. In Proceedings of the Tenth Symposium on Operating Systems Principles, laages 110-129. ACM, Dec. 1985.]]
10. 10 CCITT. The directory: Overview of concepts, models and service. Recommendation X.500, CCITt, 1988.]]
11. 11 A. Cerpa, J. Elson, D. EsWin, L. Girod, M. Hamilton, and L Zhao. Habitat monitoring: Application driver for wireless communications technology. In Proceedings of the ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, San Jose, Costa Rica, Apr. 2001. ACM.]]
12. 12 I. Clarke, O. Sandberg, B. W'dey, and T. W. Hong. Freenet: A distributed anonymous information storage retrieval system. In Proceedings of the ICSI Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, USA, July 2000.]]
13. 13 D. Coffin, D. V. Hook, R. Govindan, J. Heidemarm, and F. Silva. Network Routing Application Programmer's Interface (API) and Walk Through. Mrr/LL and USC/ISI, Dec. 2000.]]
14. 14 D.A. Coffin, D. J. V. Hook, S. M. McGarry, and S. R. Kolek. Declarative ad-hoe sensor networking. In Proceedings of the SPIE Integrated Command Environments Conference, San Diego, California, USA, July 2000. SPIE. (part of SPIE International Symposium on Optical Science and Technology).]]
15. 15 S.E. Czerwinski, B. Y. Zhao, T. D. Hodes, A. D. Joseph, and R. H. Katz. An architecture for a secure service discovery service. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, pages 24-35, Seattle, WA, USA, Aug. 1999. ACM.]]
16. 16 J. Elson and D. Estrin. Random, ephemeral transaction identifiers in dynamic sensor networks. In Proceedings of the International Conference on Distributed Computing Systems, pages 459--468, Phoenix, Arizona, USA, Apr. 2001. IEEE.]]
17. 17 S. Floyd and V. Jaeobson. Link-sharing and resource management models for packet networks. ACM/IEEE Transactions on Networking, 3(4):365-386, Aug. 1995.]]
18. 18 V. Fuller, T. Li, J. Yu, and K. Varadhan. Classless inter-domain routing (CIDR): an address assignment and aggregation strategy. RFC 1519, Internet Request For Comments, Sept. 1993.]]
19. 19 W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocols for wireless mierosensor networks. In Proceedings of the Hawaii International Conference on Systems Sciences, Jan. 2000.]]
20. 20 W.R. Heinzelman, J. Kulik, and H. Balakrishnan. Adaptive protocols for information dissemination in wireless sensor networks. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, pages 174-185, Seattle, WA, USA, Aug. 1999. ACM.]]
21. 21 J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister. System architecture directions for network sensors. In Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 93-104, Cambridge, MA, USA, Nov. 2000. ACM.]]
22. 22 T. Imielinski and S. Goel. DataSpace: QueryIng and Monitoring Deeply Networked Collections in Physical Space. 1EEE Personal Communications. Special Issue on Smart Spaces and Environments, 7(5):4--9, October 2000..,]]
23. 23 C. Intanagonwiwat, R. Govindan, and D. Esttin. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, pages 56--67, Boston, MA, USA, Aug. 2000. ACM.]]
24. 24 V. Jacobson. Compressing TCP/1P headers for low-speed serial finks. RFC 1144, Internet Request For Comments, Feb. 1990.]]
25. 25 S. Michel, K. Nguyen, A. Rosenstein, L. Zhang, S. Floyd, and V. Jaeobson. Adaptive web caching: Towards a new global caching architecture. In Proceedings of the 3rd International Worm Wide Web Conference, Manchester, England, June 1998.]]
26. 26 P. Moekapetris. Domain names--concepts and facilities. RFC 1034, Internet Request For Comments, Nov. 1987.]]
27. 27 B. Oki, M. Pfluegl, A. Siegel, and D. Skeen. The information bus---an architecture for extensible distributed systems. In Proceedings of the 14th Symposium on Operating Systems Principles, pages 58--68, Asheville, North Carolina, USC, Dec. 1993. ACM.]]
28. 28 L.L. Peterson. A yellow-pages service for a local-area network. Proceedings of the ACM SIGCOMM Conference "87, pages 235-242, Aug. 1987.]]
29. 29 G.J. Pottle and W. J. Kaiser. Embedding the internet: wireless integrated network sensors. Communications of the ACM, 43(5):51-58, May 2000.]]
30. 30 Y. Rekhter, P. Lothberg, R. I-linden, S. Deoring, and J. Postel. An IPv6 provider-based unieast address format. RFC 2073, Internet Request For Comments, Jan. 1997.]]
31. 31 P. Sharma, D. Estrin, S. Floyd, and V. Jacobson. Scalable timers for soft state protocols. In Proceedings of the IEEE lnfacom, Kobe, Japan, Apr. 1997. IEEE.]]
32. 32 S. Singh and C. Raghavendra. PAMAS: Power aware multi-access protocol with signalling for ad hoe networks. ACM Computer Communication Review, 28(3):5-26, July 1998.]]
33. 33 K. Sohrabi, J. Gao, V. Ailawadhi, and G. Pottie. A self-organizing sensor network. In Proceedings of the 37th Allerton Conference on Communication, Control, and Computing, Monticello, ill., USA, Sept. 1999.]]
34. 34 D.L. Tennenhonse, J. M. Smith, W. D. Sincoskie, D. J. Wetherall, and G. J. Minden. A survey of active network research. IEEE Communications Magazine, 35(1):80-86, Jan. 1997.]]
35. 35 J. Waldo. The Jini architecture for network-centric computing. Communications of the ACM, 42(10):76--82, Oct. 1999.]]
36. 36 L. Wang, A. Terzis, and L. Zhang. A new proposal for RSVP refreshes. In Proceedings of the IEEE International Conference on Network Protocols, Toronto, Canada, Oct. 1999. IEEE.]]
37. 37 Y. Xu, J. Heidemann, and D. Estrin. Geography-informed energy conservation for ad hoe routing. In Proceedings of the ACMAtEEE International Conference on Mobile Computing and Networking, pages 70-84, Rome, Italy, July 2001. ACM.]]
38. 38 W. Yeong, T. Howes, and S. Kille. Lightweight directory access protocol. RFC 1777, Internet Request For Comments, Mar. 1995.]]
39. 39 Y. Yu, D. Estrin, and R. Govindan. Geographical and energy-aware routing for wireless sensor networks: A recursive data dissemination protocol. Work in Progress, Mar. 2001.]]
40. 40 Y. Zhao, R. Govindan, and D. Estrin. Residual energy scans for monitoring wireless sensor networks. Technical Report 01-745, May 2001.]]

Index Terms

• Networks

  • Network types

    • Packet-switching networks

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems