The Broadcast Storm Problem in a Mobile Ad Hoc Network * Sze-Yao Ni, Yu-Chee Tseng, Yuh-Shyan Chen, and Jang-Ping Sheu Department of Computer Science and Information Engineering National Central University Chung-Li, 32054, Taiwan Tel: 886-3-4227 15 1 ext. 45 12, Fax: 886-3-422268 1 Email: [email protected] URL: http://www.csie.ncu.edu.tw/~yctseng/ Abstract Broadcasting is a common operation in a network to resolve many issues. In a mobile ad hoc network (MANET) in par- ticular, due to host mobility, such operations are expected to be executed more frequently (such as finding a route to a particular host, paging a particular host, and sending an alarm signal). Because radio signals are likely to overlap with others in a geographical area, a straightforward broad- casting by flooding is usually very costly and will result in serious redundancy, contention, and collision, to which we refer as the broadcast storm problem. In this paper, we iden- tify this problem by showing how serious it is through anal- yses and simulations. We propose several schemes to reduce redundant rebroadcasts and differentiate timing of rebroad- casts to alleviate this problem. Simulation results are pre- sented, which show different levels of improvement over the basic flooding approach. Keywords: broadcast, communication, mobile ad hoc net- work (MANET), mobile computing, wireless network. 1 Introduction The advancement in wireless communication and economi- cal, portable computing devices have made mobile comput- ing possible. One research issue that has attracted a lot of attention recently is the design of mobile ad hoc network (MANET). A MANET is one consisting of a set of mo- bile hosts that may communicate with one another and roam around at their will. No base stations are supported in such ‘This work is supported by the National Science Council of the Republic of China under Grants #NSC88-2213-E-008-013 and #NSC88-2213-E-008-014. Permission to make digital or hard copies ol‘ all or part of this work for Personal Or classmom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage at,d that copies bear this notice and the full citation oll the tirst page:e. ~~ copy otherwise, to republish, to post on servers or to redistehute Lo lists. rcqoircs prior spCCifiC permission and/or a fee, Mobicom ‘99 Seattle Washington USA ‘%‘yright ACM 1999 1-58113-142-g/gg/o8...$5.oo an environment. Due to considerations such as radio power limitation, channel utilization, and power-saving concerns, a mobile host may not be able to communicate directly with other hosts in a single-hop fashion. In this case, a multihop scenario occurs, where the packets sent by the source host are relayed by several intermediate hosts before reaching the destination host. Applications of MANETs occur in situations like battle- fields or major disaster areas where networks need to be de- ployed immediately but base stations or fixed network in- frastructures are not available. Unicast routing in MANET has been studied in several articles [6,7, 14, 15,231. A work- ing group called “manet” has been formed by the Internet Engineering Task Force (IETF) to study the related issues and stimulate research in MANET [21]. This paper studies the problem of sending a broadcast message in a MANET. Broadcasting is a common operation in many applications, e.g., graph-related problems and dis- tributed computing problems. It is also widely used to re- solve many network layer problems. In a MANET in partic- ular, due to host mobility, broadcastings are expected to be performed more frequently (e.g., for paging a particular host, sending an alarm signal, and finding a route to a particular host [6, 14, 15,231). Broadcasting may also be used in LAN emulation [2] or serve as a last resort to provide multicast services in networks with rapid changing topologies. In this paper, we assume that mobile hosts in the MANET share a single common channel with carrier sense multiple access (CSMA), but no collision detection (CD), capability. Synchronization in such a network with mobility is unlikely, and global network topology information is unavailable to facilitate the scheduling of a broadcast. So one straight- forward and obvious solution is broadcasting by flooding. Unfortunately, in this paper we observe that serious redun- dancy, contention, and collision could exist if flooding is done blindly. First, because the radio propagation is omni- directional and a physical location may be covered by the transmission ranges of several hosts, many rebroadcasts are considered to be redundant. Second, heavy contention could exist because rebroadcasting hosts are probably close to each 151other. Third, collisions are more likely to occur because the RTSKTS dialogue is inapplicable and the timing of rebroad- casts is highly correlated. Collectively, we refer to these problems associated with flooding as the broadcast storm problem. Through analy- ses and simulations, we demonstrate how serious the storm is. Two directions to alleviate this problem is to reduce the possibility of redundant rebroadcasts and differentiate the timing of rebroadcasts. Following these directions, we de- velop several schemes, called probabilistic, counter-bused, distance-bused, locution-bused, and cluster-bused schemes, to facilitate MANET broadcasting. Simulation results are presented to study the effectiveness of these schemes. To the best of our knowledge, the broadcast storm prob- lem has not been addressed in depth for MANET before. It is however worth of summarizing some results for broadcast- ing that are for other environments. Works in [3,4,9, 10, 11, 201 assume a packet-radio network environment. Most of these results rely on time division multiple access (TDMA, which requires timing synchronization) and certain levels of topology information. Their goal is to find a slot assign- ment. Obtaining an optimal assignment has
View Full Document