RBP: Robust Broadcast Propagation in Wireless Networks Fred Stann John Heidemann Rajesh Shroff Muhammad Zaki Murtaza USC/ISI 4676 Admiralty Way, Marina Del Rey, CA, USA [email protected], [email protected], [email protected], [email protected] 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. Categories and Subject Descriptors C.2.1 Network Protocols—wireless communications. C.2.2 Network Protocols—routing protocols. General Terms Algorithms, Reliability, Experimentation, Performance Keywords Broadcasting, Reliability, Wireless communications, Sensor Networks 1 Introduction Flooding is an integral part of many protocols and applications in wireless networks. Wireless routing protocols such as DSR [16], AODV [28], and ODRMP [19] flood route discovery messages. In sensor-networks, routing protocols (such as in [39]), resource discovery (such as directed diffusion [12]), and network-integrated database systems (such as TinyDB [22]) all depend on flooding to construct efficient data collection trees. Flooding-limitation protocols like SPIN [17] and BARD [34] resort to flooding when query history is not applicable. A range of applications, including query response [31], target tracking [15, 41], and signal processing [21], build on these systems or flood at the application-level. These systems depend on the completeness and timeliness of flooding to identify available resources, discover efficient paths, and coordinate in-network computation. Flooding in wireless networks is most often achieved via each node broadcasting1 the request to its neighbors, taking advantage of the shared wireless media [26]. While many wireless MAC protocols use link-layer ARQ (automatic repeat-request, often via an RTS-CTS-data-ACK exchange) to protect unicast traffic from collisions and corruption, they generally do not use ARQ for broadcast traffic because of the need to avoid control-traffic implosion [18]. Broadcast reliability often therefore directly reflects the reliability of the wireless channel. Numerous studies have documented a wide variance in broadcast reliability in low-power [33, 39, 40] and 802.11 [1] networks, thus it is not uncommon for individual broadcast messages to be lost or received by an incomplete subset of neighbors. Broadcast packet losses can result in performance problems for flooding, and ultimately in routing and applications. In networks where density varies, broadcast failures near the source or in sparser areas can effectively disconnect a large portion of the network from a flood. Reliability of a flood can be defined as the percentage of all nodes that successfully receive the information [35]. An unreliable flood can result in slow setup for query-response applications [31], slow discovery of new routes, create inferior data collection trees, or provide incomplete information for target tracking or signal processing [21]. Prior work has sought to improve broadcast reliability, either by reducing sources of loss or providing broadcast retransmission. Examples of loss reduction include PHY- 1 Prior work uses several definitions of the term “broadcasting.” In this paper, we use broadcasting only for single-hop wireless transmission from a node to all its reasonably available neighbors. (We clarify the definition of neighbor in Section 3.) We use flooding, by contrast, for network-level approaches that send information to all nodes in a connected, multi-hop network. 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, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SenSys'06, November 1–3, 2006, Boulder, Colorado, USA. Copyright 2006 ACM 1-59593-343-3/06/0011...$5.00 85layer capture [37], MAC-layer TDMA [7], random slot selection [38], and application-layer jitter. These approaches may address collisions, but do not protect against other sources of loss, particularly in sparse topologies. Retransmission of broadcasts can be done at the MAC, routing, or application layers, but each can incur unnecessary overhead. It is difficult for the MAC layer to know when neighbors are unimportant or use implicit ACKs, and for applications to track the local topology. We review related work in detail in Section 2. The contribution of this paper is to develop RBP, the Robust Broadcast Protocol, to provide adaptive reliability for broadcasts and improve the end-to-end reliability of flooding. RBP operates between the MAC and routing layers, taking information from both. It is distributed in the sense that every node makes its own decisions about retransmissions without any global or hard state. RBP exploits two observations. First, the level of reliability required of a broadcast is dependent on the local network density. Lower density requires a higher likelihood of retransmission after