John Heidemann / Papers / RBP: Robust Broadcast Propagation in Wireless Networks

RBP: Robust Broadcast Propagation in Wireless Networks
Fred Stann, John Heidemann, Rajesh Shroff and Muhammad Zaki Murtaza
USC/Information Sciences Institute

Citation

Fred Stann, John Heidemann, Rajesh Shroff and Muhammad Zaki Murtaza. RBP: Robust Broadcast Propagation in Wireless Networks. Proceedings of the Fourth ACM SenSys Conference (Boulder, Colorado, USA, Nov. 2006), 85–98. [PDF] [alt PDF]

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.

Bibtex Citation

@inproceedings{Stann06b,
  author = {Stann, Fred and Heidemann, John and Shroff, Rajesh and Murtaza, Muhammad Zaki},
  title = {RBP: Robust Broadcast Propagation in Wireless Networks},
  booktitle = {Proceedings of the Fourth ACM {SenSys} Conference },
  year = {2006},
  sortdate = {2006-11-01},
  project = {ilense, snuse},
  jsubject = {sensornet_data_dissemination},
  publisher = {ACM},
  address = {Boulder, Colorado, USA},
  month = nov,
  pages = {85--98},
  jlocation = {johnh: pafile},
  url = {https://ant.isi.edu/%7ejohnh/PAPERS/Stann06b.html},
  pdfurl = {https://ant.isi.edu/%7ejohnh/PAPERS/Stann06b.pdf},
  supporting = {The software used in this paper is
                           available as diffusion-3.3.0 at \url{https://ant.isi.edu/ilense/software/diffusion}.},
  myorganization = {USC/Information Sciences Institute},
  copyrightholder = {ACM},
  copyrightterms = {
  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.
  }
}

Copyright

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.
Copyright © by John Heidemann