DOC PREVIEW
UConn CSE 3300 - The Broadcast Storm Problem in a Mobile Ad Hoc Network

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Wireless Networks 8, 153–167, 2002 2002 Kluwer Academic Publishers. Manufactured in The Netherlands.The Broadcast Storm Problem in a Mobile Ad Hoc NetworkYU-CHEE TSENGDepartment of Computer Science and Information Engineering, National Chiao-Tung University, Hsin-Chu, 30050, Taiwan, R.O.C.SZE-YAO NIDepartment of Computer Science and Information Engineering, National Central University, Chung-Li, 32054, Taiwan, R.O.C.YUH-SHYAN CHENDepartment of Statistics, National Taipei University, Taipei, 104, Taiwan, R.O.C.JANG-PING SHEUDepartment of Computer Science and Information Engineering, National Central University, Chung-Li, 32054, Taiwan, R.O.C.Abstract. Broadcasting is a common operation in a network to resolve many issues. In a mobile ad hoc network (MANET) in particular,due to host mobility, such operations are expected to be executed more frequently (such as finding a route to a particular host, paging aparticular host, and sending an alarm signal). Because radio signals are likely to overlap with others in a geographical area, a straightforwardbroadcasting by flooding is usually very costly and will result in serious redundancy, contention, and collision, to which we call the broadcaststorm problem. In this paper, we identify this problem by showing how serious it is through analyses and simulations. We propose severalschemes to reduce redundant rebroadcasts and differentiate timing of rebroadcasts to alleviate this problem. Simulation results are presented,which show different levels of improvement over the basic flooding approach.Keywords: broadcast, communication, mobile ad hoc network (MANET), mobile computing, wireless network1. IntroductionThe advancements in wireless communication and economi-cal, portable computing devices have made mobile comput-ing possible. One research issue that has attracted a lot ofattention recently is the design of mobile ad hoc networks(MANET). A MANET is one consisting of a set of mobilehosts which may communicate with one another and roamaround at their will. No base stations are supported in suchan environment. Due to considerations such as radio powerlimitation, channel utilization, and power-saving concerns, amobile host may not be able to communicate directly withother hosts in a single-hop fashion. In this case, a multihopscenario occurs, where the packets sent by the source hostare relayed by several intermediate hosts before reaching thedestination 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 MANEThas been studied in several articles [7,8,15,16,23,25]. A work-ing group called “manet” has been formed by the Internet En-gineering Task Force (IETF) to study the related issues andstimulate research in MANET [22].This paper studies the problem of sending a broadcastmessage in a MANET. Broadcasting is a common operationin 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 par-ticular, due to host mobility, broadcasting is expected to beperformed more frequently (e.g., for paging a particular host,sending an alarm signal, and finding a route to a particularhost [7,15,16,25]). Broadcasting may also be used in LANemulation [3] or serve as a last resort to provide multicast ser-vices in networks whose topologies change rapidly.In this paper, we assume that mobile hosts in the MANETshare a single common channel with carrier sense multipleaccess (CSMA), but no collision detection (CD), capability.Synchronization in such a network with mobility is unlikely,and global network topology information is unavailable to fa-cilitate the scheduling of a broadcast. So one straightforwardand obvious solution is broadcasting by flooding. Unfortu-nately, in this paper we observe that serious redundancy, con-tention, and collision could exist if flooding is done blindly.First, because the radio propagation is omni-directional and aphysical location may be covered by the transmission rangesof several hosts, many rebroadcasts will be redundant. Sec-ond, heavy contention could exist because rebroadcastinghosts are probably close to each other. Third, collisions aremore likely to occur because the RTS/CTS dialogue is inap-plicable and the timing of rebroadcasts is highly correlated.Collectively, we refer to these problems associated withflooding as the broadcast storm problem. Through analy-ses and simulations, we demonstrate how serious the prob-lem is. Two directions to alleviate this problem are to reducethe possibility of redundant rebroadcasts and to differentiatethe timing of rebroadcasts. Following these directions, wedevelop several schemes, called probabilistic, counter-based,154 TSENG ET AL.distance-based, location-based,andcluster-based schemes,to facilitate MANET broadcasting. Simulation results are pre-sented to study the effectiveness of these schemes.To the best of our knowledge, the broadcast storm problemhas not been addressed in depth for MANET before. It is how-ever worth summarizing some results for broadcasting thatare for other environments. Works in [4,5,10–12,21] assumea packet-radio network environment. Most of these resultsrely on time division multiple access (TDMA, which requirestiming synchronization) and certain levels of topology infor-mation. Their goal is to find a slot assignment. Obtainingan optimal assignment has been shown to be NP-hard [10].The broadcast scheduling problem studied in [9,17,26,27],although carrying a similar name, is not intended to solvethe problem addressed in this paper. Its goal is to assign acontention-free time slot to each radio station.The rest of this paper is organized as follows. Section 2 de-fines and analyzes the broadcast storm problem. Mechanismsto alleviate the storm are proposed in section 3. Simulationresults are presented in section 4 and conclusions are drawnin section 5.2. Preliminaries2.1. Broadcasting in a MANETA MANET consists of a set of mobile hosts that may com-municate with one another from time to time. No base sta-tions are supported. Each host is equipped with a CSMA/CA(carrier sense multiple access with collision avoidance) [20]transceiver. In such environment, a host may communicatewith another directly or indirectly. In the latter case, a multi-hop scenario occurs, where the


View Full Document

UConn CSE 3300 - The Broadcast Storm Problem in a Mobile Ad Hoc Network

Download The Broadcast Storm Problem in a Mobile Ad Hoc Network
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view The Broadcast Storm Problem in a Mobile Ad Hoc Network and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view The Broadcast Storm Problem in a Mobile Ad Hoc Network 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?