Enhamcing Ad hoc Routing with Dynamic VirtualInfrastructuresPrasun Sinha, Raghupathy Sivakumar, Vaduvur BharghavanCoordinated Science Laboratory, University of Illinois at Urbana-Champaign1308 W. Main Street, Urbana, IL 61801{prasun, sivakumr, bharghav}~timely. crhc.uiuc.eduAbstract— Several routing algorithms for mobile ad hocnetworks (MANETs) have been proposed in the recent past[1], [2], [3].With the exception of a few, these protocols (i) involveall nodes in the route management process, (ii) rely on theuse of broadcast relays for route computation, and (iii) areprimarily reactive in nature. Related work [4], [5] has shownthat the capacity utilization in ad hoc networks decreasessignificantly when broadcast relays or “broadcast storms”are performed frequently. This effect is compounded whenall nodes in the network take part in the route computation.We propose and study an approach based on overlayinga virtual infrastructure (adaptation of the core, proposed in[3]) on an ad hoc network and operating routing protocolsover the infrastructure. The core enables routing protocolsto use only a subset of nodes in the network for route man-agement and avoid the use of broadcast relays. Using thens-2 simulator [6] , we evaluate the performance of two adhoc routing protocols, DSR [1] and AODV [2], when theyare operated over the core and compare their performanceagainst those of their basic versions.Keywords— Virtual Infrastructures, Ad hoc Routing.I. IPJTRODUCTIONAd hoc networks are multi-hop wireless networks thatare composed of mobile hosts communicating with eachother through wireless links. These networks are typicallycharacterized by scarce resources (e.g. bandwidth, batterypower etc.), lack of any established backbone infrastruc-ture, and a dynamic topology. A challenging but criticaltask that researchers have tried to address over the past fewyears has been the development of routing protocols thatsuit the characteristics clf ad hoc networks. The scarcity ofresources, lack of an infrastructure for performing routing,and the constantly changing topology render conventionalrouting protocols inappropriate for the target environment.While several ad hoc routing protocols have been pro-posed in recent years [It, [2], [3], [7], [8], we choose two ofthese protocols, DSR and AODV, because of their promi-nence in the ad hoc networking research community andready availability y of ns-2? code. While DSR andAODVhave consistently been ;shown to perform well under var-ied network characteristics [4], [5], [9], the protocols sharetwo fundamental traits that inherently bound their per-formance: (i) both protocols require flooding of route re-quests, and (ii) they perform the flooding using broadcastrelays which use “local broadcasts. We now briefly presentintuitive reasons for why the two protocol characteristicscause performance degradation:●✎●High Protocol Overhead: The number of messages isof the order of the number of nodes in the network.Unreliability of Broadcasts: Several studies [5], [10]in the past have demonstrated the inefficacy of usinglocal broadcasts - because of their unreliability - toconvey information to all nodes in a wireless network.Interference dueto Broadcasts: Since local broadcastsare not transmitted with the otherwise required RTS-CTS handshakel they can potentially result in colli-sions with the other packets (including other broad-casts) in the network resulting in an overall reductionin the network utilization.In this paper, we study the impact of overlaying a vir-tual infrastructure on the ad hoc network and operatingthe routing protocols over the infrastructure. The infras-tructure should ideally have a minimal number of nodes(subject to some constraints that we elaborate upon in thenext section) and should support an efficient and robustmeans of propagating information to all nodes in the in-frastructure. In CEDAR[3], a related work that proposesa QoS routing protocol for ad hoc networks, the authorspropose a virtual infrastructure called the core2 that ap-proximates a minimum dominatingset of the underlyingnetwork, and a QoS routing protocol that resides on thecore. We propose a dynamic self-configuring infrastruc-ture that is an adaptation of the core infrastructure, andschemes in which DSR and AODV can be made to operateover the core. We show through extensive simulation re-sults that the core infrastructure enhances the performanceof the two protocols under varied network characteristics.The rest of the paper is organized as follows: In Section2, we present an overview and characterization of AODVand DSR, and motivate the need to address the problemsthat arise because of network wide floods and broadcaststorms. In Section 3, we present our approach by describ-ing the core infrastructure and demonstrate how the corealleviates the fundamental problems identified in Section2. In Section 4, we present the changes made to the basiclWe assume the use of an IEEE 802.11 MAC protocol in the restof thepaper. However, we discuss some MAC layer enhancementsspecific to our approach later in the paper.‘Similar approaches have also been proposed in [11], [12], [13], [14],[15], [16].0-7803-7018-8/01/$10.00 (C) 2001 IEEE IEEE INFOCOM 2001versions of DSR and AODV in order to operate them overthe core infrastructure. In Section 5, we present simula-tion results to evaluate the performance of AODV and DSRwhen they operate over the core infrastructure against thatof their vanilla versions and in Section 7 we conclude thepaper.II.MOTIVATIONIn this section, we first present an overviewof DSR andAODV, the two ad hoc routing protocols that we considerin this work. We then characterize the protocols and iden-tify common characteristics that limit their performance.Finally, we identify the key goals that need to be achievedto alleviate the problems.A. Overview of Routin~g ProtocolsA.1 Dynamic Source Routing (DSR)DSR is an on demand routing protocol that makes useof source routing and an aggressive caching policy. Detailson mechanisms of DSR can be found in [1].Several features of DSR including on-demand route re-quests, source routing, and aggressivecaching are desir-able in ad hoc networks. On-demand routing optimizes therouting traffic by performing route computation only whennecessary; Source routing precludes the need for route-loopdetection mechanisms; and the aggressive caching policy isuseful for limiting the number of nodes to which a route re-quest
View Full Document