DOC PREVIEW
Berkeley COMPSCI 294 - The Broadcast Storm Problem in a Mobile Ad Hoc Network

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 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 12 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 12 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 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Berkeley COMPSCI 294 - The Broadcast Storm Problem in a Mobile Ad Hoc Network

Documents in this Course
"Woo" MAC

"Woo" MAC

11 pages

Pangaea

Pangaea

14 pages

Load more
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?