John Heidemann

RBP: Reliable Broadcast Propagation in Wireless Networks

TitleRBP: Reliable Broadcast Propagation in Wireless Networks
Publication TypeTechnical Report
Year of Publication2005
AuthorsF. Stann, J. Heidemann, R. Shroff, and M. Z. Murtaza
Date Publishednov

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.