johnh: research teaching PAPERS software other contact about

RBP: Robust Broadcast Propagation in Wireless Networks

Fred Stann, John Heidemann, Rajesh Shroff, and Muhammad Zaki Murtaza
USC/Information Sciences Institute

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.

Availability

This paper is available in several formats: abstract web page with pointers and cites, PDF, paper copies can be obtained by mail to the authors. Copyright terms for this paper appear below.

Reference

Stann06b: Fred Stann, John Heidemann, Rajesh Shroff, and Muhammad Zaki Murtaza. RBP: Robust Broadcast Propagation in Wireless Networks. In Proceedings of the Fourth ACM SenSys Conference , pp. 85-98. Boulder, Colorado, USA, ACM. November, 2006. <http://www.isi.edu/~johnh/PAPERS/Stann06b.html>.

@inproceedings{Stann06b,
	author = "Fred Stann and John Heidemann and Rajesh
 Shroff and Muhammad Zaki Murtaza",
	title = "{RBP}: Robust Broadcast Propagation in Wireless Networks",
	booktitle = "Proceedings of the Fourth {ACM} {SenSys} Conference ",
	year = "2006",
	publisher = "{ACM}",
	address = "Boulder, Colorado, USA",
	month = "November",
	pages = "85--98",
	url = "http://www.isi.edu/~johnh/PAPERS/Stann06b.html",
	pdfurl = "http://www.isi.edu/~johnh/PAPERS/Stann06b.pdf",
	myorganization = "USC/Information Sciences Institute",
	copyrightholder = "{ACM}",
}

Copyright

This paper is copyright © 2006 by ACM. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.