LinksinMultihopWirelessNetworks
DepartmentofECECSUniversityofCincinnati
Cincinnati,OH45221-0030USA
MaheshK.Marina
DepartmentofECECSUniversityofCincinnati
Cincinnati,OH45221-0030USA
SamirR.Das
mmarina@ececs.uc.edu
ABSTRACT
Weexaminetwoaspectsconcerningtheinfluenceofunidirectionallinksonroutingperformanceinmultihopwirelessnetworks.Inthefirstpartofthepaper,weevaluatethebenefitfromutilizingunidirectionallinksforrouting,asopposedtousingonlybidirec-tionallinks.Ourevaluationsarebasedonthreetransmitpoweras-signmentmodelsthatreflectsomerealisticnetworkscenarioswithunidirectionallinks.Ourresultsindicatethatthemarginalbenefitofusingahigh-overheadroutingprotocoltoutilizeunidirectionallinksisquestionable.
Mostcommonroutingprotocols,however,simplyassumethatallnetworklinksarebidirectional,andthusmayneedadditionalprotocolactionstoremoveunidirectionallinksfromroutecom-putations.Inthesecondpartofthepaper,weinvestigatethisis-sueusingawellknownon-demandroutingprotocol,AdhocOn-demandDistanceVector(AODV),asacasestudy.WestudytheperformanceofthreetechniquesforAODVforefficientoperationinpresenceofunidirectionallinks,viz.,BlackListing,Hello,andReversePathSearch.WhileBlackListingandHellotechniquesex-plicitlyeliminateunidirectionallinks,theReversePathSearchtech-niqueexploitsthegreaternetworkconnectivityofferedbytheexis-tenceofmultiplepathsbetweennodes.Performanceresultsusingns-2simulations,undervaryingnumberofunidirectionallinksandnodespeeds,showthatallthreetechniquesimproveperformancebyavoidingunidirectionallinks,theReversePathSearchtechniquebeingthemosteffective.
sdas@ececs.uc.edu
1.INTRODUCTION
Aunidirectionallinkarisesbetweenapairofnodesinanetworkwhenonlyoneofthetwonodescandirectlycommunicatewiththeothernode.Inmultihopwirelessnetworks(alsoknownasadhocnetworks),unidirectionallinksoriginatebecauseofseveralrea-sons.Theseincludedifferenceinradiotransceivercapabilitiesofnodes,theuseoftransmissionrangecontrol,differenceinwirelesschannelinterferenceexperiencedbydifferentnodes.Dependingonsuchconditions,unidirectionallinkscanbequitecommon.
Thispaperaddressesroutinginthepresenceofunidirectionallinks.Mostofthepreviousworkonthisproblemconcentratedondevelopingroutingprotocols[1,10,39,31,33,2],ortechniquessuchastunneling[23]toallowtheuseofunidirectionallinks.Buttheresultingperformanceadvantagesandtradeoffsarenotwellun-derstood.Ourapproachinthisworkistoempiricallystudytheinfluenceofunidirectionallinksonroutingperformance.
Utilizingunidirectionallinksalongwithbidirectionallinksforroutinghastwoconceivableadvantagesoverusingonlybidirec-tionallinks.First,theycanimprovethenetworkconnectivity.Forexample,removalofunidirectionallinksinFigure1partitionsthenetwork.Second,theycanprovidebetter,i.e.,shorter,paths.InFigure1,nodecancommunicatetonodedirectlyinonehopbyusingtheunidirectionallinkwhereasthealternate
requirestwohops.bidirectionalpath
Butroutingusingunidirectionallinksiscomplexandentailshighoverheads.Maindifficultycomesfromtheasymmetricknowledgeaboutaunidirectionallinkatitsendnodes.Anodedownstreamofaunidirectionallink(forexample,nodeinFigure1)immediately
)onknowsabouttheincomingunidirectionallink(link
hearingatransmissionfromtheupstreamnode(node);buttheupstreamnodemaynotknowaboutitsoutgoingunidirectionallinkuntilthedownstreamnodeexplicitlyinformsitoveramultihop
path).Learningaboutthereversepath(say,
unidirectionallinkthusincurshigheroverheadthanwhenthelinkisbidirectional.
Thereisevidenceintheliteraturethatroutingprotocolsfindingunidirectionalpaths(pathswithoneormoreunidirectionallinks)aresubjecttohigheroverheadsthanthosefindingonlybidirec-tionalpaths.Fordistance-vectorprotocols,Gerlaetal.[10]andPrakash[33]independentlymakethisobservation.Intherealmofon-demandprotocolsforadhocnetworksalso,similarobservationcanbemade.DSR[15]requirestworoutediscoveriestodiscoverunidirectionalpaths—onefromthesourceandtheotherfromthedestination,asopposedtoasingleroutediscoverytofindbidi-rectionalpaths.Althoughpurelink-stateprotocolssuchasOSPF[21]maybeabletosupportunidirectionallinkswithleastaddi-tionaloverhead,theyalreadyhaveveryhighoverheadscompared
CategoriesandSubjectDescriptors
C.2.2[Computer-CommunicationNetworks]:NetworkProto-cols.
GeneralTerms
Performance,Algorithms.
Keywords
Multihopwirelessnetworks,Adhocnetworks,Unidirectionallinks,Asymmetriclinks,Routing,On-demandrouting,Multipathrout-ing.
Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.
MOBIHOC’02,June9-11,2002,EPFLLausanne,Switzerland.Copyright2002ACM1-58113-501-7/02/0006...$5.00.
12
B
C
D
A
F
E
eliminateunidirectionallinksinAODV.Usingns-2simulations,weevaluatetheperformanceofthesethreetechniquesrelativetobasicAODV.
Therestofthepaperisorganizedasfollows.Section2eval-uatestheidealizedperformanceadvantageofroutingusingunidi-rectionallinks.Section3investigatestheissueofavoidingunidi-rectionallinksfromroutecomputationsinthecontextofAODV.HerewepresentandevaluatethreetechniquestoimprovebasicAODVperformanceinnetworkswithunidirectionallinks.Section4reviewsrelatedwork.Finally,wepresentourconclusionsinSec-tion5.
Figure1:Anetworkwithunidirectionallinks.
2.BENEFITOFUNIDIRECTIONALLINKS
FORROUTING2.1UnidirectionalLinkScenarios
Generallyspeaking,therearetwoprincipalreasonsbehindthepresenceofunidirectionallinksinmultihopwirelessnetworks.First,differenceinradiotransmissionpowerlevel(orreceiversensitiv-ity)ofthenodesgiverisetounidirectionallinks.Whentwonodes(sayAandB)havewidelydifferentradiotransmissionranges1sothatnodeAcantransmittonodeBbutnottheotherway,auni-directionallinkformsfromnodeAtonodeB.Nodesmaynatu-rallyhavedifferenttransmissionrangesinaheterogenousnetworkwherethereisaninherentdifferenceinradiocapabilities.Alter-natively,theymayhavedifferenttransmissionrangeswhenpowercontrolalgorithmsareusedforenergysavingsortopologycontrol.Second,differenceininterference(ornoise)atdifferentnodescauseasymmetriclinks.Asymmetriclinksoccurbetweenapairofnodesifthelinkqualityisdifferentineachdirection.Anextremecaseoflinkasymmetryleadstounidirectionallinks.Nodesmayexperiencedifferentinterferencelevelsbecauseofwirelesschan-nelimperfectionssuchasmultipathfadingandshadowing.Hiddenterminalscanbeanothercauseofwidevariationininterferencelevels(asalsomentionedin[33]).
Tostudythebenefitofunidirectionallinksforrouting,weonlyconsiderunidirectionallinksarisingfromdifferenceintransmis-sionranges.Notethatforunidirectionallinkstobeeffectiveforrouting,theyshouldexistlongenoughfortheroutingprotocoltocomputeroutesthroughthemandtolaterusesuchroutestofor-wardsomedata.Unidirectionallinkscausedbyvariationinin-terferencelevelspresumablyhappenonmuchsmallertime-scalesthanwouldbeneededforrouting.Soherewelimitourselvestounidirectionallinksfromvariabletransmissionranges.However,laterinthepaper,wedotakeintoaccounttheissueofinterferencetosomeextent,specificallyfromhiddenterminals,whenstudyingthenegativeinfluenceofunidirectionallinksonrouting.
Amongthepowercontrolalgorithms,onlyaparticularclassisrelevanthere.Somepowercontrolalgorithmsprescribeacom-monpowerlevelforallnodesinthenetwork(e.g.,[22]).Thesealgorithmsdonotcreateanyunidirectionallinks.Otheralgorithmsthatdoallowvariablepowerlevelseitherassignpowerlevelsonaper-transmissionbasis(e.g.,[41,20]),orassignpowerlevelsin-dependentofanysingletransmission,butmaybeusedforseveralsuccessivetransmissions(e.g.,[13,37,34,40]).Sincetheformersetofalgorithmsmayresultinshort-termunidirectionallinks,welimitourattentiontothelatterclassonly.
Wewillsometimesusetransmissionrangeinsteadoftransmissionpowertosimplifydescription.Notethatitisusuallystraightfor-wardtocomputethe“nominal”transmissionrangeofanodegiventhetransmissionpower,large-scalepathlossmodel,andtheradioparameters.
toothercompetingprotocolsforadhocnetworks[6].Exactlyforthisreason,efficientvariantsoflink-stateprotocols(e.g.,TBRPF[24],OLSR[5])havebeendeveloped.Buttheseprotocolsworkonlywithbidirectionallinks.
Besides,theuseofunidirectionallinksposesproblemstoexist-inglink-layerprotocols.Manycommonlink-layerprotocolsformediumaccessandaddressresolutionnotonlyassumebidirec-tionallinks,butalsoverymuchdependontwo-wayhandshakesandacknowledgmentsfortheiroperation.Forexample,thewell-knownIEEE802.11DCFMACprotocol[14]dependsontheex-changeofRTS-CTScontrolpacketsbetweenthesenderandthereceivertopreventhiddenterminalcollisions,andalsoexpectsac-knowledgmentfromthereceivertojudgecorrectpacketreceptionofunicasttransmissions.
Thusitisimportanttoevaluatethepotentialbenefitofunidirec-tionallinkstoknowwhetheremployingaseeminglyhighoverheadunidirectionallinkroutingprotocolisjustified.Weevaluatethisbenefitinthefirstpartofthepaper.Wecomparetworoutingap-proaches:(i)usingbothunidirectionalandbidirectionallinks;(ii)usingonlybidirectionallinks.Welookattheidealizedroutingper-formanceobtainedfromthesetwoapproaches—independentofspecificroutingprotocolsorassociatedoverheads—tofindoutanyperformanceadvantagesofutilizingunidirectionallinks.Toaccomplishthisgoal,wesimulatealargenumberofrandommul-tihopnetworktopologieswithunidirectionallinks.Westudytheconnectivityandpathcostmetricsofthesetopologieswhenuni-directionallinksareused,andwhentheyareignored.Inordertocreateunidirectionallinks,weusethreemodelsthatassignvariabletransmissionrangestonodes.Thesemodelsreflectsomerealisticwirelessnetworkscenarioshavingunidirectionallinks.Ourresultsshowthattheconnectivityadvantageusingunidirectionallinksisalmostnon-existent,butshortestpathcostsshowsomeimprove-mentwithunidirectionallinks.However,theseimprovementstoogoawaywhenhop-by-hopacknowledgmentcostsareaccounted.Utilizingunidirectionallinksforroutingpurposesmaynotbeef-ficient,andmostroutingprotocolsindeedworkwithonlybidirec-tionallinks.Buttheseprotocolsmuststillneedadditionalmecha-nismsto“eliminate”unidirectionallinksfromroutecomputationswhentheyarepresent.Weinvestigatetheimportanceofsuchmech-anismsusingawell-knownon-demandroutingprotocolcalledAdhocOn-demandDistanceVector(AODV)[29,28].ThebasicAODVprotocolworksonlywithbidirectionallinks.WeproposeanewtechniquecalledReversePathSearchtohandleunidirectionallinksinAODV.Thistechniquetakesadvantageofmultiplepathsbe-tweennodestoovercomeunidirectionallinks.Wealsoconsidertwoothertechniques—BlackListingandHello—thatexplicitly
13
2.2ModelsforVariableTransmitPowerAs-signment
Basedontheabovediscussion,weusethefollowingmodelsinourevaluationstocreatenetworkswithunidirectionallinks.TwoPowerInthismodel,thetransmissionrangeofanodecan
takeoneoftwopossiblevalueswithequalprobability.Anodecanhaveeitherashortoralongrangecorrespondingtolowandhightransmissionpowerlevels,respectively.Thefractionoflowpowernodesisthevariableparameter.Asimilarmodelwasusedin[38,26].Thismodelrepresentsaheterogenousnetworkwithtwowidelydifferentradiocapa-bilities.Forexample,transmissionpowerlevelsofvehicularandman-packradiosinabattlefieldscenariocandifferbyasmuchas10dB.RandomPowerWiththismodel,eachnodeisassignedarandom
transmissionrangethatisuniformlydistributedbetweenmin-imumandmaximumrangevalues.Thismodelisrepresen-tativeoftwopracticalscenarioswhereunidirectionallinksmightoccur:(i)ageneralizationofTwoPowerlevelmodeldescribedabove,i.e.,anetworkofnodeswithmultipledif-ferentpowerlevels;(ii)asnapshotofanetworkinwhicheachnodeadjustsitstransmitpowerbasedontheavailableenergysupplytoconserveitsbatterypower.RodopluandMeng(R&M)Thismodelisbasedonthedistributed
topologycontrolalgorithmproposedbyRodopluandMeng[37].Topologycontrolalgorithms(e.g.,[13,37,34,40])adjustnodetransmitpowersinordertoobtainatopologythatoptimizesacertainobjectivesuchasnetworkcapacity,networkreliabilityornetworklifetime.Almostalltopol-ogycontrolalgorithmsintheliteraturetrytoguaranteesomeformofnetworkconnectivitywhileoptimizingoneoralloftheabovecriteria.WehavechosentheR&Malgorithmbe-causeitistheonlyalgorithminourknowledgethatconsidersunidirectionallinksandensuresstrongconnectivitypossiblyusingsomeunidirectionallinks.Thisfeatureofthealgo-rithmprovidesafavorablecasefortheuseofunidirectionallinksforroutingtopotentiallyprovidebetternetworkcon-nectivity.Allotheralgorithmsguaranteeconnectivityusingbidirectionallinksaloneandthusarenotgoodcandidatesforourevaluation.
HerewebrieflyreviewtheR&Malgorithmforthebene-fitofthereaders.Thealgorithmaimsatachievingenergyefficiencythroughtransmitpoweradjustment.Becauseofthenatureofwirelesscommunication,itissometimesen-ergyefficientforanodetousealowertransmitpowerandcommunicatewithafarthernodeusingintermediaterelayingnodesthantousehigherpowerandcommunicatedirectly.Thealgorithmusesthisobservationtoadvantage.Centraltothealgorithmisthenotionofanenclosure.Enclosureofanoderepresentsitsimmediatelocality.Aslongaseachnodemaintainslinkswithnodesinitsenclosure,strongconnec-tivityisguaranteed.Soeachnodereducesitstransmitpowerfromthemaximumvaluetoalevelwhereitcanreachonlynodesinitsenclosure.Thealgorithmassumesthateachnodeknowsitsposition.Everynodecomputesitsenclosuresetbyexchangingpositioninformationwithallreachablenodes(usingmaximumpower).
complishthisgoal,weevaluatetheidealizedroutingperformanceoftwoapproaches:(i)utilizingunidirectionalaswellasbidirec-tionallinks;(ii)utilizingonlybidirectionallinks.Ourevaluationprocessinvolvesstaticsimulationoflargenumber(overathousandforeachdatapoint)ofrandommultihopnetworktopologiescon-tainingunidirectionallinks,andcomparingtheaverageconnectiv-ityandpathcostmetricswithandwithoutunidirectionallinks.Thethreemodelsfortransmitpowerassignmentdescribedinthepre-vioussubsectionareusedtogeneratenetworkswithunidirectionallinks.
Tomeasureconnectivity,wecomputetheaveragenumberofstronglyconnectedcomponentsandlargeststronglyconnectedcom-ponentoverallrandomgraphsamples.Forcomparingthepathquality,weconsidertheaverageshortestpathcost,per-hopac-knowledgmentcostandthetotalcommunicationcost.Notethatallpathcostsareinnumberofhopsandareaveragedoverallnodepairshavingabidirectionalpathbetweenthem,foreachrandomgraphsample—averagedoverallsuchsamples.Theper-hopac-knowledgmentcostiscomputedastheaveragecostoftraversingashortestpathbetweenapairofnodeshop-by-hopinthereversedirection.Thetotalcommunicationcostissimplythesumoftheshortestpathandacknowledgmentcosts.
Weexperimentwithawidevarietyofnodedensitiesandra-dioranges.Allourexperimentsarefor100nodenetworks.Eachrandomnetworktopologyconsistsofnodesrandomlyplacedinasquarefield.Tovarynodedensity(measuredasnodes/sq.km),thedimensionsofthefieldarevaried.Inallthreerangeassignmentmodels,afixedmaximumtransmissionrangeof250misused.IntheTwoPowermodel,thefractionoflowpowernodesisvariedtogetdifferentrangeassignments.Thelongrangeissameasthemax-imumrange,whiletheshortrangeisalwayssetto125m.Notethatweexperimentedwithdifferentshortrangevalues,buttheresultsarenotverysensitivetothesevalues.IntheRandomPowermodel,theminimumrangeischangedforvariationinranges.IntheR&Mmodel,theradiorangeofanodeiscontrolledbythealgorithm,andcannotbeartificiallyvaried.
2.4SimulationResults
2.4.1VariationinNodeDensity
Herewestudytheeffectofnodedensityonconnectivityandpathcostmetricsinallthreerangeassignmentmodels.ThefractionoflowpowernodesintheTwoPowermodelissetto0.5asthisvalueresultsinthemostnumberofunidirectionallinks.IntheRandom-Powermodel,theminimumrangevalueiskeptconstantat125mwhichischosensomewhatarbitrarily.Wedidexperimentswithothervaluesofminimumrange,buttheresultsdidnotvarymuch.Nodedensityisvariedsothatallnetworkconfigurationsarecov-eredstartingfromverysparseanddisconnectednetworkstohighlydenseandconnectednetworks.Notethatnumberofunidirectionalandbidirectionallinks(datanotshown)increasewithincreaseindensityinallthreemodels.However,therelativenumberoftheselinksandtheirrateofincreasewithdensityisverymuchdependentonthespecificmodelused.Also,wenoticedthatthemeanradiorangeintheR&Mmodelshrankasnodesbecomedenser.Thisisexpected,however,giventhenatureoftheunderlyingalgorithm.Thefirstsetofplots(Figure2)studythenetworkconnectivitypropertieswithandwithoutusingunidirectionallinks.Thenumberofstronglyconnectedcomponentsandthesizeofthelargestcom-ponentsareverysimilarregardlessofwhetherornotunidirectionallinksareused.Notethatunidirectionallinksdonotimprovecon-nectivityintheR&Mmodeleventhoughtheyareexplicitlytakenintoaccountbythealgorithm.Furthermore,wefoundthatconnec-
2.3EvaluationMethodology
Ourgoalhereistoassessthebenefitattainablefromusinguni-directionallinksforroutinginmultihopwirelessnetworks.Toac-
14
50Strongly connected components4540353025201510500
Strongly connected components40353025201510500
50100150200250300350400450500
Density (nodes/sq. km)
Strongly connected componentsWith unidirectional linksWithout unidirectional links
5045
With unidirectional linksWithout unidirectional links
18161412108200
With unidirectional linksWithout unidirectional links
50100150200250300350400450500
Density (nodes/sq. km)50100150200250300350400450500
Density (nodes/sq. km)
(a)TwoPower
Largest strongly connected componentLargest strongly connected component1009080706050403020100
With unidirectional linksWithout unidirectional links
50100150200250300350400450500
Density (nodes/sq. km)
1009080706050403020100
(b)RandomPower
Largest strongly connected component100908070605040300
(c)R&M
With unidirectional linksWithout unidirectional links
50100150200250300350400450500
Density (nodes/sq. km)
With unidirectional linksWithout unidirectional links
50100150200250300350400450500
Density (nodes/sq. km)
(d)TwoPower(e)RandomPower(f)R&M
Figure2:Connectivitymetricsinallthreemodelswithvaryingdensity.
tivitymetricsinthismodelareexactlyidenticaltothecasewhereallnodesusethemaximumrange.Boththeseobservationssuggestthatitmaybesomewhatunlikelyinrandomtopologiesfortwosub-componentstobeconnectedbytwounidirectionallinks(betweendifferentnodepairs).
Thesecondsetofplots(Figure3(a,b,c))showstheaveragecostoftheshortestpath.Theinitialhumpintheplotsisbecauseofthesharptransitionfromdisconnectedtoconnectednetworkswithinasmallrangeofdensities.ObservethatignoringunidirectionallinksonlymarginallyincreasestheshortestpathcostinTwoPowerandRandomPowermodels(Figure3(a,b))exceptwhenthedensityisbetween50–100nodes/sq.km,wheretheincreaseismoresignifi-cant.IntheR&Mmodel(Figure3(c)),theincreaseismarginalforlowerdensity,butincreaseswithincreasingdensity.
However,notethattheshortestpathcostisonlyapartoftheoverallpicture.Manyadhocnetworkprotocolsusesomesortofper-hopacknowledgmenteitherinthenetworkorthelinklayertoguaranteereliabletransmissionandalsotodetectlinkbreaks.Useofunidirectionallinkswillcausesuchacknowledgmentstotraversemultiplehops–possiblyinthenetworklayer(see[23]foranideabasedontunneling).Thiswillincreasetheoverallcommunica-tioncost.Asexpected,thehop-by-hopacknowledgementcostsaremoreinallthreemodelswhenunidirectionallinksareused(Figure3(d,e,f)).TheoverallcommunicationcostinTwoPowerandRan-domPowermodels(Figure3(g,h))isapproximatelythesamewithorwithoutunidirectionallinks.IntheR&Mmodel(Figure3(i)),theyarestillsimilarforlowerdensity,buttheuseofunidirectionallinksbringsdownthecostabit(upto10%)whenthenodedensityisveryhigh.
workwhenallnodesusethemaximumrange.Usingthisdensityvalueallowsustomeaningfullyevaluatetheconnectivityadvan-tagefromunidirectionallinks.Ahighervalueofdensitywillpro-ducemorenumberofbidirectionallinksandthusbenefitsthecasewithoutunidirectionallinks.Ontheotherhand,alowerdensityvaluewillnotallowustoexplorethewholerangeofconnectivi-ties,asnetworkwillnotgetconnectedforanyrangeassignment.Figure4showsallmetricswithvaryingfractionoflowpowernodesintheTwoPowermodel.Notethatconnectivity(Figure4(a,b)improvesonlyslightly(lessthanafewpercents)byusingunidirectionallinks.Ontheotherhand,theaveragetotalcommu-nicationcost(Figure4(e))improves(uptoabout7%,butmostlylower)whenalargefractionofnodesislowpower;thecostsaresimilarwhenasmallfractionofnodesislowpower.
TheeffectofvariabilityinnoderangesintheRandomPowermodelisshowninFigure5fordifferentvaluesoftheminimumrange.Thereissomenoticeableimprovement(about15%)inthelargestcomponents(Figure5(b))withunidirectionallinkswhenminimumrangeisverysmall.However,forhighervaluesofmin-imumrange,theimprovementsstarttodrop.Thisissomewhatexpectedbecausethevariabilityinnoderangesdecreaseswithin-creaseintheminimumrange.Similarobservationappliesforcom-municationcost(Figure5(e))aswell;thereisupto10%improve-mentwithunidirectionallinkswhentheminimumrangeissmall.Thegeneralobservationfromtheforegoingevaluationsisthatunidirectionallinksprovideonlyincrementalbenefit.Theydonotimproveconnectivityinmostcases.Theydoimproveshortestpathcostingeneral.Butwithper-hopacknowledgments,theoverallbenefitissmallandisrestrictedtoonlycertaindensitiesandradioranges.
2.4.2VariationinRadioRange
Tillnow,inTwoPowerandRandomPowermodels,thevariabil-ityinrangehasbeenfixedandnodedensityhasbeenvaried.Herewestudytheeffectofvariationinrangesforafixeddensity.Wesetthenodedensityto100nodes/sq.kmwhichyieldsaconnectednet-
3.ELIMINATIONOFUNIDIRECTIONAL
LINKSFROMROUTECOMPUTATIONS
Majorityoftheprotocolsdevelopedformultihopwirelessnet-worksassumebidirectionallinks(e.g.,[17],DSDV[27],AODV[28],
15
65.5Avg. shortest path cost54.543.532.521.5
0
With unidirectional linksWithout unidirectional links
Avg. shortest path cost765432
With unidirectional linksWithout unidirectional links
Avg. shortest path cost987654
With unidirectional linksWithout unidirectional links
50100150200250300350400450500
Density (nodes/sq. km)
050
100150200250300350400450500
Density (nodes/sq. km)
050
100150200250300350400450500
Density (nodes/sq. km)
(a)TwoPower
65.5Avg. hop-by-hop ack cost54.543.532.521.5
0
50100150200250300350400450500
Density (nodes/sq. km)
With unidirectional linksWithout unidirectional links
Avg. hop-by-hop ack cost7654320
50
(b)RandomPower
With unidirectional linksWithout unidirectional links
Avg. hop-by-hop ack cost987654
100150200250300350400450500
Density (nodes/sq. km)
0
50
(c)R&M
With unidirectional linksWithout unidirectional links
100150200250300350400450500
Density (nodes/sq. km)
(d)TwoPower
1211Avg. communication cost1098765430
50100150200250300350400450500
Density (nodes/sq. km)
With unidirectional linksWithout unidirectional links
Avg. communication cost14121080
(e)RandomPower
With unidirectional linksWithout unidirectional links
Avg. communication cost18161412108
50100150200250300350400450500
Density (nodes/sq. km)
0
(f)R&M
With unidirectional linksWithout unidirectional links
50100150200250300350400450500
Density (nodes/sq. km)
(g)TwoPower(h)RandomPower(i)R&M
Figure3:Pathcostmetricsinallthreemodelswithvaryingdensity.
TBRPF[24],OLSR[5]).Butforcorrectoperationinthepresenceofunidirectionallinks,theyrequireadditionalmechanismstoelim-inateunidirectionallinksfromroutecomputations.Ourgoalinthissectionistounderstandtheimportanceofsuchmechanismsandtheireffectontheoverallperformanceoftheroutingprotocol.WeinvestigatethisissueusingAODVasacasestudy.Whilegeneralcommentsaredifficulttomake,wedobelievethatotherprotocolswillalsobenefitfromthemechanismswedevelopandourobser-vationsfromtheperformanceevaluation.
ThedestinationonreceivingthefirstcopyofaRREQpacketformsareversepathinthesamewayastheintermediatenodes;italsounicastsaRREPbacktothesourcealongthereversepath.AstheRREPproceedstowardsthesource,itestablishesaforwardpathtothedestinationateachhop.AODValsoincludesmechanismsforerasingbrokenroutesfollowingalinkfailure,andforexpiringoldandunusedroutes.Wedonotdiscussthem,astheyarenotrelevanthere.
Theaboveroutediscoveryprocedurerequiresbidirectionallinksforcorrectoperation.OnlythenRREPcantraversebacktothesourcealongareversepathandformaforwardpathtothedes-tinationatthesource.ManycommonMACprotocolschecklinkbidirectionalityonlyforunicasttransmissions.Forexample,IEEE802.11DCFMAC[14]protocolusesanRTS-CTS-Data-ACKex-changeforunicasttransmissions;receiptofCTSfollowinganRTSorACKfollowingthedatatransmissiononalinkensuresthatitisbidirectional.Broadcasttransmissions,however,cannotdetectthepresenceofunidirectionallinks.SinceAODVRREQpacketstyp-icallyuselink-layerbroadcasttransmissions,someunidirectionallinkscangoundetectedandasaresultreversepathsmaycontainunidirectionallinks(directedawayfromthesource).RREPtrans-missionsalongsuchreversepathswillfail,astheyareunicast.RoutediscoveryfailswhennoneoftheRREPsreachthesource.
3.1AODVProtocol
AODVisanon-demandroutingprotocol.Itislooselybasedonthedistance-vectorconcept.Inon-demandprotocols,nodesobtainroutesonanasneededbasisviaaroutediscoveryprocedure.Routediscoveryworksasfollows.Wheneveratrafficsourceneedsaroutetoadestination,itinitiatesaroutediscoverybyfloodingaroutere-quest(RREQ)forthedestinationinthenetworkandthenwaitsforaroutereply(RREP).WhenanintermediatenodereceivesthefirstcopyofaRREQpacket,itsetsupareversepathtothesourceus-ingtheprevioushopoftheRREQasthenexthoponthereversepath.Inaddition,ifthereisavalidrouteavailableforthedesti-nation,itunicastsaRREPbacktothesourceviathereversepath;otherwise,itre-broadcaststheRREQpacket.DuplicatecopiesoftheRREQareimmediatelydiscardeduponreceptionateverynode.
16
Strongly connected components765432100
0.2
With unidirectional linksWithout unidirectional links
Largest strongly connected component810095908580757065600
0.2
With unidirectional linksWithout unidirectional links0.40.60.8Fraction of low power nodes
1
0.40.60.8Fraction of low power nodes
1
(a)
76.5
Avg. hop-by-hop ack costAvg. shortest path cost65.554.543.532.5
0
0.2
With unidirectional linksWithout unidirectional links0.40.60.8Fraction of low power nodes
1
76.565.554.543.532.5
0
0.2
With unidirectional linksWithout unidirectional links0.40.60.8Fraction of low power nodes
1
(b)
1413Avg. communication cost121110987650
0.2
With unidirectional linksWithout unidirectional links0.40.60.8Fraction of low power nodes
1
(c)(d)(e)
Figure4:TwoPowermodel:connectivityandpathcostmetricswithvaryingfractionoflowpowernodes.
Strongly connected components18161412108200
With unidirectional linksWithout unidirectional links
Largest strongly connected component2010095908580757065600
With unidirectional linksWithout unidirectional links50100150200Minimum transmission range (m)
250
50100150200Minimum transmission range (m)
250
(a)
6.56Avg. shortest path cost5.554.543.532.5
0
50
100
150
200
250
6.56Avg. hop-by-hop ack cost5.554.543.532.5
0
50
100
150
200
(b)
1312Avg. communication cost11109876
250
50
50
100
150
200
250
With unidirectional linksWithout unidirectional linksWith unidirectional linksWithout unidirectional linksWith unidirectional linksWithout unidirectional links
Minimum transmission range (m)Minimum transmission range (m)Minimum transmission range (m)
(c)(d)(e)
Figure5:RandomPowermodel:connectivityandpathcostmetricswithvaryingvaluesofminimumrange.
17
SADSettingittoasmallvaluemayreducetheeffectivenessofthetechnique.Ontheotherhand,settingittoaverylargevalueaffectsconnectivitywhentherearemanyshort-termunidi-rectionallinks.
HelloInthecontrasttotheBlackListingtechnique,thistechnique
proactivelyeliminatesunidirectionallinksbyusingperiodicone-hopHellopackets.AsimilarideahasalsobeenusedinOLSR[5]torecordonlybidirectionallinks.IneachHellopacket,anodeincludesallnodesfromwhichitcanhearHel-los(i.e,itssetofneighbors).IfanodedoesnotfinditselfintheHellopacketfromanothernode,itmarksthelinkfromthatnodeasunidirectional.JustasintheBlackListingtech-nique,everynodeignoresRREQpacketsthatcomeviasuchunidirectionallinks.Notethatthishellopacketsareidenti-caltotheAODVhellopackets[29]exceptfortheadditionalneighborhoodinformation.
Theadvantageofthistechniqueisthatitautomaticallyde-tectsunidirectionallinksbyexchangingHellopackets.Buttheperiodic,largeHellopacketscanbeasignificantover-head.AlthoughthesizeoftheHellopacketsmaybereducedbyusing“differential”Hellos[24],theperiodicpacketover-headisstillaconcern.However,insituationswhenHellosmustbeusedformaintaininglocalneighborhoodandtode-tectlinkfailures(e.g.,whenthelinklayercannotprovideanyfeedbackaboutlinkfailures),incrementaloverheadforunidirectionallinkdetectionmaynotbeverymuch.ReversePathSearchUnliketheabovetwotechniques,thistech-niquedoesnotexplicitlyremoveunidirectionallinks.In-stead,ittakesacompletelydifferentapproach.Eachunidi-rectionallinkisviewedasa“fault”inthenetworkandmulti-plepathsbetweenthenodesarediscoveredtoperformfault-tolerantrouting.Thebasicideaisasfollows.DuringtheRREQflood,multipleloop-freereversepathstothesourceareformedatintermediatenodesandthedestination.Us-ingadistributedsearchprocedure,multipleRREPsexplorethismultipathroutingstructureinanattempttofindoneormorebidirectionalpathsbetweenthesourceandthedestina-tion.Thissearchprocedureissomewhatsimilartothewell-knowndepthfirstsearchalgorithm.WhenRREPfailsatanode,thecorrespondingreversepathiserasedandtheRREPisretriedalonganalternatereversepath,ifoneisavailable;whenallreversepathsfailatanodeduringthisprocess,thesearchbacktrackstoupstreamnodes2ofthatnodewithre-specttothesourceandtheytoofollowthesameprocedure.Thiscontinuesuntileitheroneormorebidirectionalpathsarefoundatthesource,orallreversepathsareexplored.Thistechniqueisdescribedinmoredetailinthefollowingsubsection.
BCFigure6:Alllinksarebidirectionalexcepttheonewithanar-row.receivesfirstcopyofRREQfromforviapath,andformsareversepath;subsequentRREPtrans-missionfromtowillfail.Thisscenariowillrepeatforlaterroutediscoveryattemptsfrom.Thealternate,longerpath
)willneverbediscovered.(
Itcanfailevenwhenthereisabidirectionalpathbetweenthesource
andthedestination.ThisisbecauseonlythefirstcopyofaRREQpacket—whichmayarriveviaaunidirectionalpathfromthesource—isconsideredbyintermediatenodesandthedestinationtoformreversepathsandsendbackRREPs;latercopiesaresimplydis-cardedeveniftheytakebidirectionalpaths.SeeFigure6foranillustration.
Intheworstcase,thisscenariowillresultinrepeatedroutedis-coveryfailures.Thusadditionalmechanismsareneededtoavoidtheaboveprobleminnetworkswithunidirectionallinks.
3.2TechniquesforHandlingUnidirectional
LinksinAODV
Inthefollowingwedescribethreetechniquestoalleviatethisproblem.Thefirsttwotechniques—“BlackListing”and“Hello”—areknowntechniques.Thethirdtechnique,“ReversePathSearch”isourcontributioninthispaper.
BlackListingThistechniquereactivelyeliminatesunidirectional
links.ItisincludedinthelatestAODVspecification[29].Here,wheneveranodedetectsaRREPtransmissionfailure,itinsertsthenexthopofthefailedRREPintoa“blacklist”set.Theblacklistsetatanodeindicatesthesetofnodesfromwhichithasunidirectionallinks.Forexample,inFig-ure6nodewillblacklistnode.Laterwhenanodere-ceivesaRREQfromoneofthenodesinitsblacklistset,itdiscardstheRREQtoavoidformingareversepathwithunidirectionallink.ThisgivesachanceforRREQfromanalternatepath(e.g.,viainFigure6)toprovideadifferentreversepath.BLACKLISTTIMEOUTspecifiestheperiodforwhichanoderemainsintheblacklistset.Bydefault,thisperiodissettotheupperboundofthetimeittakestoperformthemaximumallowednumberofroutediscoveryattemptsbyasource.
3.3ReversePathSearchTechnique
Inapriorwork[19],wehaveinvestigatedamultipathextensiontoAODV,calledAOMDV,whererouteupdaterulestomaintainmultipleloop-freepathsaredescribed.WeusethesameAOMDVrouteupdateruleshereintheReversePathSearchtechniquetomain-tainmultipleloop-freepathstoadestinationateverynode.
IntheReversePathSearchalgorithm,allRREQcopiesincludingduplicatesareexaminedatintermediatenodesandthedestinationforpossiblealternatereversepathstothesource.However,reverseAnodeXisupstreamofanodeYwithrespecttoanodeDifYappearsonapathfromXtoD.Conversely,YisadownstreamnodeofXforD.
Thistechniqueissimpleandhaslittleoverheadwhentherearefewunidirectionallinks.However,whentherearemanyunidirectionallinks,thisapproachisinefficientbecausetheselinksareblacklistediterativelyoneatatime.Severalroutediscoveriesmaybeneededbeforeabidirectionalpath,ifex-ists,isfound.Anotherdifficultywiththistechniqueisinset-tinganappropriatevaluefortheBLACKLISTTIMEOUT.
18
GHBSACEDFFigure7:Demonstrationofreversepathsearch.Multiplere-formedduringtheRREQfloodversepathstothesource
areshown;someofthereversepathscontainunidirectional
.ConsidertheRREPpropagationlinkssuchas
via.Thetransmissionfromtofailscausing
erasesthereversepathviaaBRREPtransmissionat.
andtransmitsaRREPtoinordertoexplorethereversepath
.Thisalsofails,causingtotransmitBRREP.
thenerasesthereversepathviaandtransmitsRREPtoinordertoexplorepath.Thiswillbesuccessful.
pathsareformedonlyfromthosecopiesthatsatisfyrouteupdaterulesandprovideloop-freepaths[19].Othercopiesaresimplydiscarded.NotethatthisisdifferentfrombasicAODVwhereonlythefirstcopyislookedat.
WhenaRREQcopyatanintermediatenodecreatesorupdatesareversepath,andtheintermediatenodehasnovalidpathtothedestination,theRREQcopyisre-broadcastedprovideditisthefirstcopythatyieldsareversepath;thisissomewhatsimilartobasicAODVwhereonlyfirstcopiesofRREQareforwardedtopreventloopingduringtheflood.Onthecontrary,iftheintermediatenodedoeshaveavalidpathtothedestination,itcheckswhetherornotaRREPhasalreadybeensentforthisroutediscovery.Ifnot,itsendsbackaRREPalongthenewlyformedreversepathandremembersthenexthopusedforthisRREP;otherwise,theRREQcopyisdropped.
WhenthedestinationreceivescopiesofRREQs,italsoformsreversepathsinthesamewayasintermediatenodes.However,un-likeintermediatenodes,thedestinationsendsbackaRREPalongeachnewreversepath.Multiplerepliesfromdestinationallowex-plorationofmultiplereversepathsconcurrently—thusspeedingupthesearchforabidirectionalpath.Incontrast,allowingmulti-pledestinationrepliesinbasicAODVhaslittlebenefitunlessthoserepliestakenon-overlappingpathstothesource.Thisisbecausein-termediatenodeshaveatmostonereversepathbacktothesource.WhenanintermediatenodereceivesaRREP,itfollowsrouteupdaterulesin[19]toformaloop-freeforwardpathtothedesti-nation,ifpossible;else,theRREPisdropped.Supposingthattheintermediatenodeformstheforwardpathandhasoneormorevalidreversepathstothesource,itchecksifanyofthosereversepathswaspreviouslyusedtosendaRREPforthisroutediscovery.Ifnot,itchoosesoneofthosereversepathstoforwardthecurrentRREP,andalsoremembersthenexthopforthatreversepath;otherwise,theRREPissimplydropped.
RREPtransmissionfailure(asaresultoftransmissionoveraunidirectionallink,forexample)atanintermediatenoderesultsinthatnodeerasingthecorrespondingreversepath,andretryinganalternatereversepath.Ifnosuchalternatepathisavailable,thein-
termediatenodetransmits(broadcasttransmission)anewmessagecalledthe“backtrackroutereply”(BRREP)toinformitsupstreamnodes(withrespecttothesource)totryotherreversepathsatthosenodes.ABRREPisalsogeneratedbyanintermediatenode,ifthatnodedoesnothaveanyreversepathuponaRREPreception.OnreceivingaBRREP,anintermediatenodeupstreamoftheBRREPsource(meaningithaslastsentaRREPtotheBRREPsourceforthisroutediscovery)takesasimilaractionasonaRREPfailure;nodesthatarenotupstreamoftheBRREPsourcesimplydiscardthepacketonreception.WhenthedestinationencountersaRREPfailure,orreceivesaBRREP,itonlyerasescorrespondingreversepaths.SeeFigure7foranillustration.
Notethattheaboveprocedureisguaranteedtoterminate.Toseethis,observethateveryRREPfailureerasesthecorrespondingreversepath.Soreversepathscannotbeexploredindefinitelysincethereareonlyfinitenumberofthem.Ontheotherhand,alternatereversepathsarenotexploredattheintermediatenodesaslongasRREPssuccessfullygothrough.Alsonotethatintheabovedescription,somedetailshavebeenomittedforthesakeofbrevity.Forinstance,algorithmsactionstocopewithBRREPlossarenotmentioned.
Multipleloop-freereversepathsusedbytheabovealgorithmareingeneralasubsetofallpossiblereversepaths.Thus,sometimesitispossiblethatthemultiplereversepathsexploredbythealgorithmdonotincludeabidirectionalpathbetweensourceanddestinationalthoughsuchapathexists.Butindensenetworksthatwecon-sider,oftenthereismorethanonebidirectionalpathandtheabovepossibilityisrare.
Finally,multiplerepliesfromthedestinationinthealgorithmyieldmultipleforwardpathsatintermediatenodesandthesource.Thisabilitytocomputemultiplebidirectionalpathsinasingleroutediscoveryishighlybeneficialinmobilenetworksforefficientre-coveryfromroutebreaks.
3.4PerformanceEvaluation
Inthissectionweevaluatetheperformanceofthethreetech-niquesdescribedintheprevioussubsectionrelativetobasicAODVundervaryingnumberofunidirectionallinksandnodespeeds.Twoprimarygoalsfromthisevaluationare:(i)tounderstandtheim-pactofunidirectionallinksonbasicAODVperformance;and(ii)toevaluatetheeffectivenessofthethreetechniquesinhandlinguni-directionallinks.
3.4.1SimulationEnvironment
Weuseadetailedsimulationmodelbasedonns-2[8].TheMonarchresearchgroupinCMUdevelopedsupportforsimulat-ingmulti-hopwirelessnetworkscompletewithphysical,datalinkandMAClayermodels[4]onns-2.Thedistributedcoordinationfunction(DCF)ofIEEE802.11[14]forwirelessLANsisusedastheMAClayer.Theradiomodelusescharacteristicssimilartoacommercialradiointerface,Lucent’sWaveLAN.WaveLANisashared-mediaradiowithanominalbit-rateof2Mb/sandanom-inalradiorangeof250meters.Moredetailsaboutthesimulatorcanbefoundin[4,8].Thissimulatorhasbeenusedforevaluat-ingperformanceofearlierversionsoftheAODVprotocol(e.g.,[4,30]).
TheAODVmodelinoursimulationsisbasedonthelatestpro-tocolspecification[29],exceptthattheexpandingringsearchisdisabledforallprotocolvariations.Notethattheexpandingringsearchintroducesanadditionalreasonforroutediscoveryfailures,i.e.,whenasmallerringsize(TTLvalue)isusedforthesearch.Thismakesanalysissomewhatdifficult.SoinourAODVmodel,asourcedoesnetwork-wideroutediscoveriesappropriatelyspaced
19
intimeuntileitherarouteisobtainedoramaximumretrylimit(3)isreached;whenthelimitisexceeded,sourcereportstotheap-plicationthatthedestinationisunreachableanddropsallbufferedpacketsforthedestination—wetermthiseventas“routesearchfailure”inourevaluations.Besides,linklayerfeedbackisusedtodetectlinkfailuresinallprotocolvariations.The802.11MAClayerreportsalinkfailurewhenitfailstoreceiveCTSafterseveralRTSattempts,ortoreceiveACKafterseveralretransmissionsofDATA.NotethatintheHellotechnique,linkfailuresaredetectedusinghellomessagesaswellasthefeedback,whicheverdetectsthelinkbreakagefirst.
TwoPowermodelisusedtocreateunidirectionallinks,primarilybecauseitdoesnotperformpowercontrol.Useofpowercontrolmakestheanalysisheredifficultasthenumberofunidirectionallinksthenwillbecomeheavilydependentonthechoiceoftheac-tualpowercontrolalgorithmandthefrequencyatwhichthealgo-rithmisinvoked.Notethatthefrequencyofinvocationdidnotplayanyroleinourearlierevaluationsasweusedonlystatictopolo-gies.Wemodifiedthens-2simulatortoallowvariabletransmis-sionrangesfornodes.Inallourexperiments,shortandlongrangesintheTwoPowermodelaresetto125mand250m,respectively.Wevarythefractionoflowpowernodestovarythenumberofunidirectionallinks.
Weconsider100nodenetworkswithnodesinitiallyplacedatrandominarectangularfieldofdimensions575mx575m.Thefieldsizeischosentoguaranteeaconnectednetworkacrossthepa-rameterspace.Weuserandomwaypointmodel[4]tomodelnodemovements.Pausetimeisalwayssettozeroandthemaximumspeedofthenodesischangedtochangemobility.
TrafficpatterninourexperimentsconsistsoffixednumberofCBRconnections(20)betweenrandomlychosensource-destinationpairsandeachconnectionstartsatarandomtimeatthebeginningofthesimulationandstaysuntiltheend.EachCBRsourcesendspackets(eachofsize512bytes)atafixedrateof4packets/s.
Allourexperimentsuse500secondsimulationtimes.Inthecaseofstaticnetworks,eachdatapointintheplotsisanaverageofatleast50runswithdifferentrandomlygeneratedinitialnodepositionsandrangeassignmentsineachrun.Inthemobilityexper-iments,weaverageover25randomlygeneratedmobilityscenariosandrangeassignments.Identicalscenariosareusedacrossallpro-tocolvariations.
3.4.2PerformanceMetrics
Weevaluatefourkeyperformancemetrics:(i)Packetdeliveryfraction—ratioofthedatapacketsdeliveredtothedestinationtothosegeneratedbytheCBRsources;(ii)Averageend-to-enddelayofdatapackets—thisincludesallpossibledelayscausedbybufferingduringroutediscovery,queuingdelayattheinterface,retransmissiondelaysattheMAC,propagationandtransfertimes;(iii)Routesearchfailures—totalnumberofroutesearchfailureevents(seeprevioussubsection)atsources;(iv)Normalizedroutingload—thenumberofroutingpackets“transmitted”perdatapacket“delivered”atthedestination.Eachhop-wisetransmissionofaroutingpacketiscountedasonetransmission.
3.4.3SimulationResults
Wepresenttwosetsofexperiments.Inthefirstset,thenetworkisstaticandthenumberofunidirectionallinksisvaried.Inthesecondset,nodemobilityisconsidered.Figure8showsthepacketdeliveryfraction,averagedelay,andtheroutesearchfailuresasafunctionofthenumberofunidirectionallinks.Wechangethefractionoflowpowernodesfrom0to0.5toincreasethenumberofunidirectionallinks.Withincreaseinunidirectionallinks,basic
AODVdropsthehighestnumberofpackets(asmanyas20%)andalsoexperiencesmostnumberofroutesearchfailures(Figure8(a,c)).ThisisbecausethebasicAODVprotocoldoesnottakenoticeoftheunidirectionallinksandrepeatedlyperformsroutediscover-ieswithoutanybenefit.Notethataftereveryroutesearchfailure,allpacketsbufferedforthedestinationatthesourcearedropped.ThedropinpacketdeliveryislessdrasticforBlackListingcom-paredtobasicAODV.Butitstilldropsasmanyas14%ofthepack-etsbecauseofitsslownessineliminatingunidirectionallinksonebyone.Itstillhasalargenumberofroutesearchfailures;butper-formssomewhatbetterthanbasicAODV.ThedelayperformanceofAODVandBlackListing(Figure8(b))issimilarasroutedis-coverylatencydominatesthedelayinbothcases.
BothHelloandReversePathSearchdeliveralmostallpacketsal-ways(Figure8(a)),asbothareabletosuccessfullyfindroutesalways(Figure8(c)).However,theirdelayperformance(Figure8(b))isquitedifferent.DelayfortheHellotechniqueissimilartoba-sicAODVandBlackListing,whileReversePathSearchhassignifi-cantlylowerdelaythanothers.ThisshowsthatReversePathSearchcaneffectivelyovercomeunidirectionallinksbyexploringmultiplereversepaths.However,thedelayperformanceoftheHellotech-niqueiscounter-intuitive.Onewouldnormallyexpecttheperfor-manceofHellotobeindependentofunidirectionallinksbecauseitproactivelyeliminatesunidirectionallinksinthebackgroundwith-outburdeningAODVroutediscoverymechanism.Belowwewillanalyzethereasonbehindthisunexpectedbehavior.
Byadditionalinstrumentation,wefoundthatthesharpincreaseinroutediscoveryattemptswithincreaseinunidirectionallinks(Figure9(a))explainsthedelayperformanceoftheHellotech-nique.Whatismoreinterestingisthereasonbehindtheriseinroutediscoveriesitself.Thiswefoundwasbecauseofanundesir-ableinteractionofthisprotocolwiththe802.11MAClayer.WenoticedthatingeneralMACcollisionsincreasedwithincreaseinthenumberofunidirectionallinks.Thisisbecauseofthehiddenterminalinterferenceviaunidirectionallinks,andtheinsufficiencyoftheRTS-CTShandshakein802.11MACtoavoidsuchhiddenterminals(See[32]forasimilarobservation).FortheHellotech-nique,however,theincreaseincollisionsisquitedramatic(Figure9(c))becauseoflargeandperiodic(everysecond)broadcasthellopackets.Consequently,theefficiencyoftheMAClayerisnega-tivelyaffectedresultinginmorenumberofunsuccessfultransmis-sionsandtriggeringoflinkfailuresignalstotheroutingprotocol.Suchlinkfailuresignalscauseroutebreaks(Figure9(b)).NotethatinthebasicAODVprotocol,everyroutebreakwillresultinanewroutediscoveryattempt.SincetheHellotechniqueisidenticaltobasicAODVexceptfortheadditionalhelloexchanges,itdoesmorenumberofroutediscoveryattemptsasunidirectionallinksgrowinnumber.NotethatbasicAODVandBlackListingarenotaffectedverymuchbytheabovephenomenon,astheyspendmostoftheireffortfindingaroute.EventhoughReversePathSearchissubjecttothisproblemtosomeextent,theavailabilityofredundantforwardpathspreventsabigdropinitsperformance.
Figure10showstheroutingloadcomparisonforthefourproto-cols.Overall,ReversePathSearchhasthelowestoverheadfollowedbyBlackListing,basicAODVandHello.ThehighoverheadoftheHellotechniqueisexpectedbecauseoftheperiodichellomessages.Also,lowroutingoverheadinReversePathSearchindicatesthatthehigherperroutediscoverycostsinReversePathSearchduetomore(backtrack)routerepliesisverywelloffsetbythesignificantre-ductioninroutediscoveries(Figure9(a)).Relativeperformanceintermsofthebyteoverhead(notshown)issameasabove.Insum-mary,theReversePathSearchtechniqueallowsforamuchmoreef-fectiveeliminationofunidirectionallinksfromroutecomputations
20
10.95
Avg. delay (ms)0.90.850.80.75
Basic AODVBlackListing
Hello
ReversePathSearch
0
100
200
300400500Unidirectional links
600
700
120100806040200
Packet delivery fractionRoute search failuresBasic AODVBlackListing
Hello
ReversePathSearch
1009080706050403020100
Basic AODVBlackListing
Hello
ReversePathSearch
0100200
300400500Unidirectional links
6007000100200
300400500Unidirectional links
600700
(a)Packetdeliveryfraction(b)Averagedelay(c)Routesearchfailures
Figure8:Performancewithvaryingnumberofunidirectionallinks.
400350Route discovery attempts3002502001501005000
100
200
300
400
500
600
700
Route breaksHelloReversePathSearch
350300
MAC collisions2502001501005000
100
200
300
400
500
600
700
Hello300002500020000150001000050000
Hello0100200300400500600700
Unidirectional linksUnidirectional linksUnidirectional links
(a)Routediscoveries(b)Routebreaks(c)MACcollisions
Figure9:Routediscoveries,routebreaksandMACcollisionsfortheHellotechniquewithvaryingnumberofunidirectionallinks.
startstoplayadominantrole.ReversePathSearch,however,con-tinuestoperformsignificantlybetterthantherest.Withthebuilt-inredundancyintheroutediscoveryprocess,itnotonlyeliminatesunidirectionallinksfromtheroutecomputationsbyexploringalter-natereversepaths,butalso,inasimilarvain,avoidsbrokenreversepathsduetomobility(Figure11(c)).Inaddition,bycomputingmultipleforwardpathsatthesourceandintermediatenodes,itob-viatestheneedforfrequentroutediscoveryattemptsinresponsetoroutebreakscausedbynodemobility.
600
700
3Normalized routing load2.521.510.50
Basic AODVBlackListing
Hello
ReversePathSearch
0100200
300400500Unidirectional links
(a)Routingload
4.RELATEDWORK
Althoughmanycommonroutingprotocolsassumebidirectionallinks,thereisstillconsiderableamountofliteratureavailableonroutingusingunidirectionallinks(e.g.,[1,10,39,31,2]).Theseprotocolsaremainlytargetedtowardstwonetworkenvironments,namely,mixedsatelliteandterrestrialnetworks,andmultihopwire-lessnetworks,whereunidirectionallinkscommonlyoccur.OftheseveralunicastroutingproposalsformultihopwirelessnetworkswithintheIETFMANETworkinggroup[18],onlyDSR[15]andFSR[9]canfullysupportunidirectionallinks,whileZRP[12,11]andTORA[25]canpartiallysupportunidirectionallinks.Therehavealsobeenattemptstoextendexistingprotocolstosupportuni-directionallinks[33,38,16].Butnoneoftheaboveeffortscontainanysimulationorexperimentalevaluationoftheimpactofunidi-rectionallinksonroutingperformanceinrealisticscenarios.
Supportforunidirectionallinksbelowthenetworklayeralsore-ceivedsomeattention.Link-layertunnelingapproachhasbeenex-ploredin[7,23].Themainmotivationbehindthisapproachistohidetheunidirectionalnatureofalinkfromhigherlayerpro-tocolssothattheycanoperateoverunidirectionallinkswithoutanymodifications.Thisisbasicallyachievedbyformingareverse
Figure10:Routingloadwithvaryingnumberofunidirectionallinks.
comparedtoBlackListing,howeverwithmuchloweroverheadcostcomparedtoHello.
TheeffectofnodemobilityonallmetricsisshowninFigure11.Herewevarythemaximumnodespeedbetween0and20m/s.Tostresstheprotocols,wesetthefractionoflowpowernodesto0.5whichresultsinthemostnumberofunidirectionallinksinstaticnetworks.Mobilityalsoaffectsthenumberanddurationofunidi-rectionallinks.Butthesearesomewhathardtoquantifyinmobilenetworks.Asexpected,performanceintermsofpacketdelivery,delayandoverheaddegradesforallprotocolswithincreaseinmo-bility(Figure11(a,b,d)).However,observationsabouttherelativeperformanceofthefourprotocolsprettymuchremainsameasinthestaticnetworkcase.NotethatthedifferenceinroutingloadbetweenbasicAODV,BlackListing,andHelloshrinksasmobility
21
tunnel(possiblyviaamultihoppath)foreachunidirectionallinkusinginformationgatheredbytheroutingprotocol.In[36],analternativeapproachtotunneling,butwithasimilargoalispro-posed.Theideahereistointroduceasub-layerbeneaththenet-worklayertofindandmaintainmultihopreverseroutesforeachunidirectionallink.Thereisalsosomeworkonusingmultihopacknowledgementstodiscoverunidirectionallinks[26],andGPS-basedapproachesforenablinglink-levelacknowledgements[16]overunidirectionallinks.
Workonchannelaccessprotocolsformultihopwirelessnet-workswithunidirectionallinksisstartingtogetattention[35,3].Ramanathan[35]makesanimportantobservationthatmanyuni-directionallinkshurtchannelaccessprotocolperformance.Thisissomewhatrelatedtoourobservationthatutilizingunidirectionallinksdoesnotprovideanysignificantadditionalbenefit.
5.CONCLUSIONS
Unidirectionallinkscommonlyoccurinwirelessadhocnet-worksbecauseofthedifferencesinnodetransceivercapabilitiesorperceivedinterferencelevels.Unidirectionallinkscanpresum-ablybenefitroutingbyprovidingimprovednetworkconnectivityandshorterpaths.Butpriorworkindicatesthatroutingoveruni-directionallinksusuallycauseshighoverheads.Withthisinmind,weevaluatedperformanceadvantages,intermsofconnectivityandpathcosts,ofroutingusingunidirectionallinksunderidealcon-ditions.Ourevaluationsweredonewithrespecttothreevariabletransmissionrangeassignmentmodelsthatreflectsomerealisticnetworkscenarioswithunidirectionallinks.Mainconclusionfromthisstudyisthatunidirectionallinksprovideonlyincrementalben-efit.Thus,protocolsthatavoidunidirectionallinksdemandacloserlook.
Manycommonroutingprotocols,however,simplyassumethatlinksarebidirectional.Theywillrequiresomeadditionalproto-coloperationstodetectandeliminateunidirectionallinksfromroutecomputations.Toassessthedifficultyofdoingthis,wehavepresentedacasestudywiththeAODVprotocolwherethreesuchtechniquesarepresentedandevaluated.ItisobservedthattheRe-versePathSearchtechniqueperformsthebestbecauseofitsabilitytoexploremultiplepaths.Itexhibitsadualadvantage,bothintermsofimmunityfromunidirectionallinksandfrommobility-inducedlinkfailures.WhilethiscasestudyhasbeenperformedonlyforAODV,weexpectthatotherprotocolsthatsharecertaincharacter-isticswithAODV,suchastheon-demandnatureorthedistancevectorframework,willalsobenefitfromtheseideas.
Besides,ourperformancestudyalsorevealedthat802.11MACperformancedegradesinthepresenceofunidirectionallinks.Asimilarobservationwasalsomadein[32].Theseobservationssug-gesttheneedformoreefficientMACprotocolstohandleunidi-rectionallinks,assuchlinksmaybeinevitableincertainadhocnetworkscenarios(forexample,anetworkofnodeswithheteroge-nouspowers).
Acknowledgments
ThisworkispartiallysupportedbyNSFCAREERgrantACI-00961-86andNSFnetworkingresearchgrantANI-00962.MaheshMarinaissupportedbyanOBRcomputingresearchawardintheECECSdepartment,UniversityofCincinnati.
6.REFERENCES
[1]Y.AfekandE.Gafni.DistributedAlgorithmsforUnidirectional
Networks.SIAMJournalofComputing,23(6):1152–1178,1994.
[2]L.BaoandJ.J.Garcia-Luna-Aceves.Link-stateRoutingin
NetworkswithUnidirectionalLinks.InProceedingsofInternationalConferenceonComputerCommunicationsandNetworks(IC3N),pages358–363,1999.
[3]L.BaoandJ.J.Garcia-Luna-Aceves.ChannelAccessSchedulingin
AdHocNetworkswithUnidirectionalLinks.InProceedingsofWorkshoponDiscreteAlgorithmsandMethodsforMobileComputingandCommunications(DIALM),pages9–18,2001.[4]J.Broch,D.Maltz,D.Johnson,Y.-C.Hu,andJ.Jetcheva.A
PerformanceComparisonofMulti-HopWirelessAdHocNetworkRoutingProtocols.InProceedingsofIEEE/ACMMOBICOM,pages85–97,1998.
[5]T.Clausenetal.OptimizedLinkStateRoutingProtocol.
http://www.ietf.org/internet-drafts/draft-ietf-manet-olsr-06.txt,Mar2002.IETFInternetDraft(workinprogress).
[6]S.R.Das,R.Castaneda,andJ.Yan.Simulation-basedPerformance
EvaluationofRoutingProtocolsforMobileAdhocNetworks.ACM/BaltzerMobileNetworksandApplications(MONET),5(3):179–1,2000.
[7]E.Duros,W.Dabbous,H.Izumiyama,N.Fujii,andY.Zhang.A
Link-LayerTunnelingMechanismforUnidirectionalLinks.RFC3077,2001.
[8]K.FallandK.Varadhan(Eds.).ThensManual.
http://www.isi.edu/nsnam/ns/ns-documentation.html,2002.[9]M.Gerla,X.Hong,andG.Pei.FisheyeStateRoutingProtocol
(FSR)forAdHocNetworks.
http://www.ietf.org/internet-drafts/draft-ietf-manet-fsr-02.txt,Dec2001.IETFInternetDraft(workinprogress).
[10]M.Gerla,L.Kleinrock,andY.Afek.ADistributedRouting
AlgorithmforUnidirectionalNetworks.InProceedingsofIEEEGLOBECOM,1983.
[11]Z.J.Haas,M.R.Pearlman,andP.Samar.TheInterzoneRouting
Protocol(IERP)forAdHocNetworks.
http://www.ietf.org/internet-drafts/draft-ietf-manet-zone-ierp-01.txt,June2001.IETFInternetDraft(workinprogress).
[12]Z.J.Haas,M.R.Pearlman,andP.Samar.TheIntrazoneRouting
Protocol(IARP)forAdHocNetworks.
http://www.ietf.org/internet-drafts/draft-ietf-manet-zone-iarp-01.txt,June2001.IETFInternetDraft(workinprogress).
[13]L.Hu.TopologyControlforMultihopPacketRadioNetworks.IEEE
TransactionsonCommunications,41(10):1474–1481,1993.
[14]IEEEStandardsDepartment.WirelessLANmediumaccesscontrol
(MAC)andphysicallayer(PHY)specifications,IEEEstandard802.11–1997.
[15]D.B.Johnson,D.A.Maltz,Y.Hu,andJ.G.Jetcheva.TheDynamic
SourceRoutingProtocolforMobileAdHocNetworks(DSR).http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-07.txt,Feb2002.IETFInternetDraft(workinprogress).
[16]D.Kim,C.K.Toh,andY.Choi.OnsupportingLinkAsymmetryin
MobileAdHocNetworks.InProceedingsofIEEEGLOBECOM,pages2798–2803,2001.
[17]G.Lauer.Packet-RadioRouting.InM.Steenstrup,editor,Routingin
CommunicationNetworks,chapter11.PrenticeHall,1995.[18]J.MackerandS.Corson.MobileAdhocNetworks(MANET).
http://www.ietf.org/html.charters/manet-charter.html,1997.IETFWorkingGroupCharter.
[19]M.K.MarinaandS.R.Das.On-demandMultipathDistanceVector
RoutinginAdHocNetworks.InProceedingsofIEEEInternationalConferenceonNetworkProtocols(ICNP),pages14–23,2001.[20]J.P.Monks,V.Bharghavan,andW.W.Hwu.APowerControlled
MultipleAccessProtocolforWirelessPacketNetworks.InProceedingsofIEEEINFOCOM,pages219–228,2001.[21]J.Moy.OSPFversion2.RFC1247,1991.
[22]S.Narayanaswamy,V.Kawadia,R.S.Sreenivas,andP.R.Kumar.
PowerControlinAd-HocNetworks:Theory,Architecture,AlgorithmandImplementationoftheCOMPOWProtocol.In
ProceedingsofEuropeanWirelessConference,pages156–162,2002.[23]S.NesargiandR.Prakash.ATunnelingApproachtoRoutingwith
UnidirectionalLinksinMobileAd-HocNetworks.InProceedingsofInternationalConferenceonComputerCommunicationsandNetworks(IC3N),pages522–527,2000.
22
[24]R.Ogier,F.L.Templin,B.Bellur,andM.G.Lewis.Topology
BroadcastBasedonReverse-PathForwarding(TBRPF).
http://www.ietf.org/internet-drafts/draft-ietf-manet-tbrpf-05.txt,Mar2002.IETFInternetDraft(workinprogress).
[25]V.ParkandS.Corson.Temporally-orderedroutingalgorithm
(TORA)version1functionalspecification.
http://www.ietf.org/internet-drafts/draft-ietf-manet-tora-spec-04.txt,July2001.IETFInternetDraft(workinprogress).
[26]M.R.Pearlman,Z.J.Haas,andB.P.Manvell.UsingMulti-Hop
AcknowledgementstoDiscoverandReliablyCommunicateoverUnidirectionalLinksinAdHocNetworks.InProceedingsofWirelessCommunicationsandNetworkingConference(WCNC),pages532–537,2000.
[27]C.E.PerkinsandP.Bhagwat.HighlyDynamic
Destination-SequencedDistance-VectorRouting(DSDV)forMobileComputers.InProceedingsofACMSIGCOMM,pages234–244,1994.
[28]C.E.PerkinsandE.M.Royer.AdHocOn-DemandDistanceVector
Routing.InProceedingsofIEEEWorkshoponMobileComputingSystemsandApplications(WMCSA),pages90–100,1999.[29]C.E.Perkins,E.M.Royer,andS.R.Das.AdhocOn-Demand
DistanceVector(AODV)Routing.
http://www.ietf.org/internet-drafts/draft-ietf-manet-aodv-10.txt,Jan2002.IETFInternetDraft(workinprogress).
[30]C.E.Perkins,E.M.Royer,S.R.Das,andM.K.Marina.
PerformanceComparisonofTwoOn-demandRoutingProtocolsforAdHocNetworks.IEEEPersonalCommunications,8(1):16–28,2001.
[31]C.Pomalaza-Raez.ADistributedRoutingAlgorithmforMultihop
PacketRadioNetworkswithUni-andBi-DirectionalLinks.IEEETransactionsonVehicularTechnology,44(3):579–585,1995.[32]N.Poojary,S.V.Krishnamurthy,andS.Dao.MediumAccess
ControlinaNetworkofAdHocNodeswithHeterogeneousPowerCapabilities.InProceedingsofIEEEICC,pages872–877,2001.[33]R.Prakash.ARoutingAlgorithmforWirelessAdHocNetworks
withUnidirectionalLinks.ACM/KluwerWirelessNetworks,7(6):617–625,2001.
[34]R.RamanathanandR.Rosales-Hain.TopologyControlofMultihop
WirelessNetworksusingTransmitPowerAdjustment.InProceedingsofIEEEINFOCOM,pages404–413,2000.
[35]S.Ramanathan.AUnifiedFrameworkandAlgorithmforChannel
AssignmentinWirelessNetworks.WirelessNetworks,5(2):81–94,1999.
[36]V.Ramasubramanian,R.Chandra,andD.Mosse.Providinga
BidirectionalAbstractionforUnidirectionalAdHocNetworks.InProceedingsofIEEEINFOCOM,2002.Toappear.
[37]V.RodopluandT.Meng.MinimumEnergyMobileWireless
Networks.IEEEJournalonSelectedAreasinCommunications,SpecialIssueonAdHocNetworks,17(8):1333–1344,Aug1999.[38]P.Sinha,S.V.Krishnamurthy,andS.Dao.ScalableUnidirectional
RoutingwithZoneRoutingProtocol(ZRP)ExtensionsforMobileAd-hocNetworks.InProceedingsofWirelessCommunicationsandNetworkingConference(WCNC),pages1329–1339,2000.
[39]G.Tel.DirectedNetworkProtocols.InProceedingsofInternational
WorkshoponDistributedAlgorithms(WDAG),pages13–29,1987.[40]R.Wattenhofer,L.Li,P.Bahl,andY.Wang.DistributedTopology
ControlforPowerEfficientOperationinMultihopWirelessAdHocNetworks.InProceedingsofIEEEINFOCOM,pages1388–1397,2001.
[41]J.E.Wieselthier,G.D.Nguyen,andA.Ephremides.Onthe
ConstructionofEnergy-EfficientBroadcastandMulticastTreesinWirelessNetworks.InProceedingsofIEEEINFOCOM,pages585–594,2000.
23
1n0.9oitcarf y0.8reviled 0.7tekcaP0.6Basic AODVBlackListing
Hello
0.5
ReversePathSearch
0
5
10
15
20
Max. node speed (m/s)
(a)Packetdeliveryfraction
600Basic AODV500BlackListing
Hello
ReversePathSearch
)sm400( yale300d .gvA2001000
0510
1520
Max. node speed (m/s)
(b)Averagedelay
200
Basic AODVBlackListing
Hello
se150
ReversePathSearch
ruliaf hcra100
es etuoR50
0
05
1015
20
Max. node speed (m/s)
(c)Routesearchfailures
7Basic AODVBlackListing
dHello
a6oReversePathSearch
l gn5ituor4 dezil3amro2N100
5
10
15
20
Max. node speed (m/s)
(d)Routingload
Figure11:Performancewithvaryingmobility.
因篇幅问题不能全部显示，请点此查看更多更全内容