Experimental evaluation of synchronization and topology control for in-building sensor network applications

ABSTRACT

While multi-hop networks consisting of 100s or 1000s of inexpensive embedded sensors are emerging as a means of mining data from the environment, inadequate network lifetime remains a major impediment to real-world deployment. This paper describes several applications deployed throughout our building that monitor conference room occupancy and environmental statistics and provide access to room reservation status. Because it is often infeasible to locate sensors and display devices near power outlets, we designed two protocols that allow energy conservation in a large class of sensor network applications. The first protocol, Relay Organization (ReOrg), is a topology control protocol which systematically shifts the network's routing burden to energy-rich nodes, exploiting heterogeneity. The second protocol, Relay Synchronization (ReSync), is a MAC protocol that extends network lifetime by allowing nodes to sleep most of the time, yet wake to receive packets. When combined, ReOrg and ReSync lower the duty cycle of the nodes, extending network lifetime. To our knowledge, this paper presents the first experimental testbed evaluation of energy-aware topology control integrated with energy-saving synchronization. Using a 54-node testbed, we demonstrate an 82-92% reduction in energy consumption, depending on traffic load. By rotating the burden of routing, our protocols can extend network lifetime by 5-10 times. Finally, we demonstrate that a small number of wall-powered nodes can significantly improve the lifetime of a battery-powered network.

REFERENCES

• 1: Baker D.J., and Ephremides, A. The architectural organization of a mobile radio network via a distributed algorithm. IEEE Trans. on Comm., 29, 11 (Nov. 1981).
• 2: Chris Barrett , Achla Marathe , Madhav V. Marathe , Martin Drozda, Characterizing the interaction between routing and MAC protocols in ad-hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513812]
• 3: Cerpa, A., and Estrin, D. ASCENT: Adaptive self-configuring sensor networks topologies in Proc. INFOCOM '02 (NY, NY, June 2002).
• 4: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 5: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O ]
• 6: Conner, W.S., Chhabra, J., Yarvis, M., Krishnamurthy, L., "Experimental Evaluation of Topology Control and Synchronization for In-Building Sensor Network Applications," WSN Technical Report, Intel Corporation (Aug. 2003). http://www.intel.com/research/people/bios/yarvis_m.htm
• 7: W. Steven Conner , Lakshman Krishnamurthy , Roy Want, Making Everyday Life Easier Using Dense Sensor Networks, Proceedings of the 3rd international conference on Ubiquitous Computing, p.49-55, September 30-October 02, 2001, Atlanta, Georgia, USA
• 8: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844143]
• 9: Laura Marie Feeney, An energy consumption model for performance analysis of routing protocols for mobile ad hoc networks, Mobile Networks and Applications, v.6 n.3, p.239-249, June 2001 [doi>10.1023/A:1011474616255 ]
• 10: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 11: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 12: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 13: LAN MAN Standards Committee of the IEEE Computer Society. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, ANSI/IEEE Std. 802.11 (1999).
• 14: Infrastructured Ad Hoc Networks, Proceedings of the 2002 International Conference on Parallel Processing Workshops, p.64, August 18-21, 2002
• 15: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 16: Min, R., Bhardwaj, M., Ickes, N., Wang, A., and Chandrakasan, A. The hardware and the network: Total-system strategies for power aware wireless microsensors in Proc. 2002 IEEE CAS Workshop (Sept. 2002).
• 17: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 18: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 19: Raghunathan, V., Schurgers, C., Park, S., and Srivastava, M.B. Energy aware wireless microsensor networks in IEEE Signal Processing Magazine, 19, 2 (Mar. 2002).
• 20: R. Rozovsky , P. R. Kumar, SEEDEX: a MAC protocol for ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501426.501427]
• 21: Royer, E.M., Lee, S., and Perkins, C.E. The effects of MAC protocols on ad hoc network communications in Proc. IEEE Wireless Comm. and Networking Conference (Chicago IL, Sept. 2000).
• 22: Schurgers, C., Tsiatsis, C., and Srivastava, M. STEM: Topology management for energy efficient sensor networks in Proc. 2002 IEEE Aerospace Conference (Mar. 2002).
• 23: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 24: Sohrabi, K., Gao, J., Ailawadhi, V., and Pottie, G. Protocols for self-organization of a wireless sensor network in IEEE Personal Communications (Oct. 2000).
• 25: Trujillo, S., CEO Graviton. UCSD Connect SENSORNET Conference Keynote (April 29, 2002).
• 26: Alec Woo , David E. Culler, A transmission control scheme for media access in sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.221-235, July 2001, Rome, Italy [doi>10.1145/381677.381699]
• 27: Wu, J., Dai, F., Gao, M., and Stojmenovic, I. On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks in Journal of Comm. and Networks, 4, 1 (Mar. 2002).
• 28: Xu, Y., Bien, S., Mori, Y., Heidemann, J., and Estrin, D. Topology control protocols to conserve energy in wireless ad hoc networks. Center for Embedded Networked Computing Technical Report 6, University of California, Los Angeles (Jan. 2003).
• 29: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 30: Jasmeet Chhabra , Brent Elliott, Real-World Experiences with an Interactive Ad Hoc Sensor Network, Proceedings of the 2002 International Conference on Parallel Processing Workshops, p.143, August 18-21, 2002
• 31: Ye, W., Heidemann, J., and Estrin, D. An energy-efficient MAC protocol for wireless sensor networks in Proc. IEEE INFOCOM 2002 (New York NY, June 2002).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

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

Keywords:
synchronization, topology control, wireless sensor networks