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

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


Fred Stann, John Heidemann, Rajesh Shroff and Muhammad Zaki Murtaza. RBP: Reliable Broadcast Propagation in Wireless Networks. Technical Report ISI-TR-2005-608. USC/Information Sciences Institute. [PDF] [alt PDF]


Low-powered radios, interference patterns, and multi-hop connections make most wireless networks inherently unreliable. While MAC protocols provide high reliability for unicast via mechanisms such as ARQ, higher-layer network protocols often require broadcast transmissions as well. Prior work on broadcast improvements has focused on efficiency and generally not related reliability to general routing protocols. Existing broadcast protocols often require multi-hop topology information. Instead, we present a very simple protocol, requiring only local information, and highlight the performance impact of our protocol on routing with a secondary evaluation of energy efficiency. We develop our protocol as a service between the MAC and network layer, taking information from both. Our approach is based on two principles: First, we exploit network density to achieve near-perfect end-to-end reliability by requiring moderate (50–70%) reliability when nodes have many neighbors. Second we identify areas of sparse connectivity where important links bridge clusters of dense nodes, and guarantee connectivity over those links. Routing performance depends on wireless propagation, so we develop a new error model that considers both correlated and independent loss in broadcast traffic based on testbed experiments. We demonstrate, through controlled simulations using this model, and through complete testbed experiments, that this hybrid approach is necessary to provide near-perfect accuracy with good efficiency. In a real testbed we show 99.8% accuracy with 48% less overhead than through repeated flooding. The contributions of this paper are the introduction of our protocol Reliable Broadcast Propagation, definition of metrics that balance efficiency and reliability, and introduction of a more accurate model for broadcast error.

Bibtex Citation

  author = {Stann, Fred and Heidemann, John and Shroff, Rajesh and Murtaza, Muhammad Zaki},
  title = {RBP: Reliable Broadcast Propagation in Wireless Networks},
  institution = {USC/Information Sciences Institute},
  year = {2005},
  sortdate = {2004-11-01},
  project = {ilense, snuse},
  jsubject = {chronological},
  number = {ISI-TR-2005-608},
  month = nov,
  location = {johnh: pafile},
  keywords = {reliable broadcast, wireless broadcast,
                           sensor network routing, diffusion},
  url = {},
  pdfurl = {},
  otherurl = {},
  myorganization = {USC/Information Sciences Institute},
  copyrightholder = {authors}
Copyright © by John Heidemann