RBP: robust broadcast propagation in wireless networks

ABSTRACT

Varying interference levels make broadcasting an unreliable operation in low-power wireless networks. Many routing and resource discovery protocols depend on flooding (repeated per-node broadcasts) over the network. Unreliability at the broadcast-level can result in either incomplete flooding coverage or excessive re-flooding, making path maintenance either unreliable or expensive. We present RBP, a very simple protocol that bolsters the reliability of broadcasting in such networks. Our protocol requires only local information, and resides as a service between the MAC and network layer, taking information from both. We show that RBP improves reliability while balancing energy efficiency. RBP is based on two principles: First, we exploit network density to achieve near-perfect flooding reliability by requiring moderate (50-70%) broadcast reliability when nodes have many neighbors. Second, we identify areas of sparse connectivity where important links bridge dense clusters of nodes, and strive for guaranteed reliability over those links. We demonstrate, through both testbed experiments and controlled simulations, that this hybrid approach is advantageous to providing near-perfect reliability for flooding with good efficiency. Testbed experiments show 99.8% reliability with 48% less overhead than the level of flooding required to get equivalent reliability, suggesting that routing protocols will benefit from RBP.

REFERENCES

• 1: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 2: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 3: Anonymous Gossip: Improving Multicast Reliability in Mobile Ad-Hoc Networks, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.275, April 16-19, 2001
• 4: Adam Chlipala, Jonathan Hui and Gilman Tolle, \Deluge: Data Dissemination in Multi-Hop Sensor Networks," UC Berkeley CS294-1 Project Report, December 2003.
• 5: I. Cidon , M. Sidi, Distributed Assignment Algorithms for Multihop Packet Radio Networks, IEEE Transactions on Computers, v.38 n.10, p.1353-1361, October 1989 [doi>10.1109/12.35830]
• 6: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 7: A. Ephremides and T.V. Truong. Scheduling Broadcasts in Multihop Radio Networks. IEEE Transactions on Communications, 3 (4):456--60, April 1990.
• 8: Sally Floyd , Van Jacobson , Ching-Gung Liu , Steven McCanne , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.784-803, Dec. 1997 [doi>10.1109/90.650139]
• 9: L. Girod, J. Elson, A. Cerpa, T. Stathopoulos, N. Ramanathan, and D. Estrin. Em*: a Software Environment for Developing and Deploying Wireless Sensor Networks. In Proceedings of the 2004 USENIX Technical Conference. 2004
• 10: Z. Haas, J. Halpern, L. Li. Gossip-Based Ad Hoc Routing. In Proceedings of the IEEE Infocom. Pages 1707--1716. New York, NY, June 2002.
• 11: John Heidemann , Fabio Silva , Deborah Estrin, Matching data dissemination algorithms to application requirements, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958517]
• 12: John Heidemann , Fabio Silva , Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , Deepak Ganesan, Building efficient wireless sensor networks with low-level naming, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 13: John Heidemann, Fabio Silva, Yan Yu, Deborah Estrin, and Padma Haldar. Diffusion Filters as a Flexible Architecture for Event Notification in Wireless Sensor Networks. USC/ISI Technical Report 2002-556
• 14: 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
• 15: Qingfeng Huang , Chenyang Lu , Gruia-Catalin Roman, Spatiotemporal multicast in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958516]
• 16: D. Johnson, and D. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. in Mobile Computing, pages 153--181. Kluwer Academic, 1996.
• 17: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 18: LAN MAN Standards Committee of the IEEE Computer Society, Wireless LAN medium access control (MAC) and physical layer (PHY) specification. IEEE Std. 802.11, IEEE 1997
• 19: Sung Ju Lee , William Su , Mario Gerla, On-demand multicast routing protocol in multihop wireless mobile networks, Mobile Networks and Applications, v.7 n.6, p.441-453, December 2002 [doi>10.1023/A:1020756600187]
• 20: P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A self-regulating algorithm for code maintenance and propagation in wireless sensor networks. In Proceedings of the 1st USENIX/ACM Symposium on Network Systems Design and Implementation (NSDI), 2004.
• 21: D. Li, K. Wong, Y.H. Hu, and A. Sayeed. Detection, Classification and Tracking of Targets in Distributed Sensor Networks. IEEE Signal Processing Magazine, vol. 19, no. 2, March 2002.
• 22: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 23: M. Murtaza, J. Heidemann, F. Stann. Studying the Spatial Correlation of Loss Patterns among Communicating Wireless Sensor Nodes. USC/ISI Directed Research Report 2005.
• 24: Nitin Nahata , Priyatham Pamu , Saurabh Garg , Ahmed Helmy, Efficient resource discovery for large scale ad hoc networks using contacts, ACM SIGCOMM Computer Communication Review, v.32 n.3, p.32-32, July 2002 [doi>10.1145/571697.571721]
• 25: 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]
• 26: K. Obraczka & K. Viswanath, Flooding for Reliable Multicast in Mutlti-Hop Ad Hoc Networks, PARSEC Workshop'99
• 27: S. Paul, K.K. Sabnani, J.C. Lin, S. Bhattacharyya. Reliable Multicast Transport Protocol (RMTP). In IEEE Journal on Selected Areas in Communications, Vol. 15 No. 3, Pages 407--421, April 1997
• 28: 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
• 29: Larry L. Peterson , Bruce S. Davie, Computer Networks: A Systems Approach, 3rd Edition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 30: J. Pu, E. Manning, G. Shoja, Routing Reliability Analysis of Partially Disjoint Paths, In Proceedings of PACRIM'01, Victoria, 2001.
• 31: Abhishek Rajgarhia, Fred Stann, and John Heidemann. Privacy-Sensitive Monitoring With a Mix of IR Sensors and Cameras. In Proceedings of the Second International Workshop on Sensor and Actor Network Protocols and Applications, pages 21--29, Boston, August 2004
• 32: Y. Sasson, D. Cavin, A. Schiper. Probabilistic Broadcast for Flooding in Wireless Mobile Ad hoc Networks. IEEE Wireless Communications and Networking Conference (WCNC) - March 2003
• 33: Fred Stann and John Heidemann. RMST: Reliable Data Transport in Sensor Networks. In Proceedings of the First IEEE Intl. Workshop on Sensor Network Protocols and Applications, pages 102--112, Alaska, May 2003.
• 34: Fred Stann, and John Heidemann. BARD: Bayesian-Assisted Resource Discovery In Sensor Networks. In Proceedings of the 24th IEEE INFOCOM Conference. Miami, Florida, USA. March, 2005.
• 35: Kumar Viswanath, and Katia Obraczka. Modeling the Performance of Flooding in MultiHop Ad Hoc Networks, Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS'04)
• 36: Chieh-Yih Wan , Andrew T. Campbell , Lakshman Krishnamurthy, PSFQ: a reliable transport protocol for wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570740]
• 37: K. Whitehouse, A. Woo, F. Jiang, J. Polastre, and D. Cutler. Exploiting the Capture Effect for Collision Detection and Recovery. The Second IEEE Workshop on Embedded Networked Sensors (EmNetS-II). Sydney, Australia. May 30-31, 2005.
• 38: Brad Williams , Tracy Camp, Comparison of broadcasting techniques for mobile 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.513825]
• 39: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958494]
• 40: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
• 41: F. Zhao, J. Shin, and J. Reich. Information-Driven Dynamic Sensor Collaboration for Tracking Applications. In IEEE Signal Processing Magazine, 19(2):61--72, March 2002

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Experimentation, Performance, Reliability

Keywords:
broadcasting, reliability, sensor networks, wireless communications