Efficient Flooding in Ad hoc Networks using On-Demand (Passive) Cluster Formation

EfficientFloodinginAdhocNetworksusingOn-Demand(Passive)ClusterFormation

Abstract—Manyadhocnetworkprotocols(e.g.,routing,servicediscovery,etc.)usefloodingasthebasicmechanismtopropagatecontrolmessages.Inflooding,anodetransmitsamessagetoallofitsneighbors.Theneighborsinturntransmittotheirneighborsandsoonuntilthemessagehasbeenpropagatedtotheentirenet-work.Typically,onlyasubsetoftheneighborsisrequiredtofor-wardthemessageinordertoguaranteecompletefloodingtotheentirenetwork.Ifthenodegeographicdensity(i.e.,thenumberofneighborswithinanode’sradioreach)ismuchhigherthanwhatisstrictlyrequiredtomaintainconnectivity,onecaneasilyseethatfloodingbecomesinefficientbecauseofredundant,“superfluous”forwarding.Infact,superfluousfloodingincreaseslinkO/Handwirelessmediumcongestion.Inalargenetwork,withheavyload,thisextraO/Hcanhavesevereimpactonperformanceandshouldbeeliminated.

Clusteringand,moregenerally,routeaggregationtechniqueshavebeenproposedinthepasttoreducethefloodingO/H.Thesetechniquesoperateinaproactive,backgroundmode.Theyuseexplicitcontrolpacketstoelectasmallsetofnodes(cluster-heads,gatewaysor,moregenerally,floodforwardingnodes)andrestricttosuchsetthefloodforwardingfunction.TheproblemofsuchproactiveschemesistheconstanttrafficO/Hintroducedinthenetwork.

Inthispaper,weproposeanewfloodingmechanismbasedonpassive,on-demandclustering.Thismechanismreducesfloodingoverheadwithoutlossofnetworkperformance.Passivecluster-ingdynamicallypartitionsthenetworkinclustersinterconnectedbygateways.Passiveclusteringisan”ondemand”protocol.Itexecutesonlywhenthereisuserdatatraffic;itexploitsdatapack-etsforclusterformation.Passiveclusteringhasmanyadvantagescomparedwith“active”clusteringandrouteaggregationtech-niques:(1)iteliminatesclustersetuplatencyandextracontroloverhead(byexploitingon-goingpackets);(2)itusesanovel,effi-cientgatewayselectionheuristictoelecttheminimumnumberofforwardingnodes(thusreducingsuperfluousflooding);(3)itre-ducesnodepowerconsumptionbyeliminatingtheperiodic,back-groundcontrolpacketexchange.

Simulationresultsshowthatpassiveclusteringcanreducere-dundantfloodingbyupto70%withnegligibleextraprotocolover-head.Moreover,weshowthatpassiveclusteringcanbeappliedtoseveralreactive,on-demandroutingprotocols(e.g.,AODV,DSRandODMRP)withsubstantialperformancegains.

I.INTRODUCTION

Multi-hopadhocnetworks(MANETs)haverecentlybeenthesubjectofactiveresearchbecauseoftheiruniqueadvantages.MANETsareself-creating,self-organizingandself-administratingwithoutdeployinganykindofinfrastructure.Theyofferspecialbenefitsandversatilityforwideapplicationsinmilitary(e.g.,battlefields,sensornetworksetc.),commercial(e.g.,dis-tributedmobilecomputing,disasterdiscoverysystems,etc.),andeducationalenvironments(e.g.,conferences,conventions,etc.),wherefixedinfrastructureisnoteas-ilyacquired.Withtheabsenceofpre-establishedinfras-tructure(e.g.,norouter,noaccesspoint,etc.),twonodes

communicatewithoneanotherinapeer-to-peerfash-ion.Twonodescommunicatedirectlyiftheyareinthetransmissionrangeofeachother.Otherwise,nodescancommunicateviaamulti-hoproutewiththecooperationofothernodes.Tofindsuchamulti-hoppathtoan-othernodes,eachMANETnodewidelyusefloodingorbroadcast(e.g.,hellomessages).Manyadhocroutingprotocols[10][12][13][27][28],multicastschemes[25],orservicediscoveryprogramsdependonmassiveflooding.

Inflooding,anodetransmitsamessagetoallofitsneighbors.Theneighborsinturnrelaytotheirneigh-borsandsoonuntilthemessagehasbeenpropagatedtotheentirenetwork.Inthispaper,wecallsuchfloodingasblindflooding.Asonecaneasilysee,theperformanceofblindfloodingiscloselyrelatedtotheaveragenum-berofneighbors(neighbordegree)intheCSMA/CAnetwork.Astheneighbordegreegetshigher,theblindfloodingsuffersfromtheincreasesof(1)redundantandsuperfluouspackets,(2)theprobabilityofcollision,and(3)congestionofwirelessmedium[1].Performanceofblindfloodingisseverelyimpairedespeciallyinlargeanddensenetworks[2].

Whentopologyorneighborhoodinformationisavail-able,onlyasubsetofneighborsisrequiredtopartic-ipateinfloodingtoguaranteethecompleteflooding.Wecallsuchfloodingefficientflooding.Thechar-acteristicsofMANETs(e.g.,nodemobility,thelim-itedbandwidthandresource),however,makecollect-ingtopologicalinformationverydifficult.Itgenerallyneedshugeextraoverheadduetotheperiodicmes-sageexchangesoreventdrivenupdateswithoptionaldeploymentofGPS(GlobalPositioningSystem)-likesystem.Forthatreasonmanyon-demandadhocrout-ingschemesandservicediscoveryprotocolssimplyuseblindflooding[10][12][25].Withperiodicroutetableexchanges,proactiveadhocroutingschemes,unlikeon-demandroutingmethods,cangathertopologicalinfor-mationwithoutbigextraoverhead(throughpiggyback-ingtopologyinformationorlearningneighbors).Thus,afewproactiveadhocroutingmechanismsproposedrouteaggregationmethodssothattherouteinformationispropagatedbyonlyasubsetofnodesinthenetwork[27][28].

Inthispaper,weproposemechanismforefficient

MOBIHOC2002floodingsuitableforon-demandprotocolsbasedonpas-siveclustering.WerequireneitherthedeploymentofGPS-likesystemnorexplicitperiodiccontrolmessages.Ourschemehasseveralcontributionscomparedwithpreviousefficientfloodingmechanisms(suchasmulti-pointrelay,neighbor-coverage,etc).(1)Itdoesnotneedanyperiodicmessages.Instead,passiveclusteringex-ploitsexistingtraffictopiggybackitssmallcontrolmes-sages.Basedonpassiveclusteringtechnique,itisveryresource-efficientregardlessofthedegreeofneighbornodesorthesizeofnetwork.Toourknowledge,pas-siveclusteringistheonlyschemethatprovidesscala-bilityandpracticalityforchoosingtheminimalnumberofforwardingnodesinthepresenceofdynamictopol-ogychanges.Therefore,itcanbeeasilyappliedtoon-demandroutingschemestoimprovetheperformanceandscalability.(2)Itdoesnothaveanysetuplatency,anditsavesenergywithnotraffic.(3)Itsmaintenanceiswelladaptivetodynamictopologyandresourceavail-abilitychanges.

Theorganizationoftherestpartofthepaperisasfollows.Wewillpresentbriefrelatedworksandmotiva-tionsofourworkinChapterII,anddescribethedetailedalgorithminchapterIII.Thereafter,wedemonstratethecontributionsofourworkthroughanalysisandextensivesimulationstudiesinChapterIVandChapterV.Finally,weconcludethepaperinChapterVI.

II.RELATEDWORKSANDMOTIVATIONSSeveralrecentpapers[1][6][7][8]haveaddressedtheproblemofblindfloodingandproposedsolutionstoprovideefficientflooding.However,theproblemoffindingasubsetofdominantforwardingnodesinMANETsisNP-complete[1].Thus,alltheworkaboutefficientfloodinghasbeenfocusingondevelopingef-ficientheuristicsthatselectasub-optimaldominantsetwithlowforwardingoverhead.

[1][6]proposedseveralheuristicstoreducerebroad-casts.Intheiridea,uponreceivingafloodingpacket,anodedecideswhetheritrelaysthepackettoitsneigh-borornotusingoneoffollowingheuristics:(1)prob-abilisticschemewherethisnoderebroadcastthepacketwiththerandomlychosenprobability;(2)counter-basedschemewherethisnoderebroadcastifthenumberofreceivedduplicatepacketsislessthanathreshold;(3)distance-basedschemethatusestherelativedistancebe-tweenhoststomakethedecision;(4)location-basedschemebasedonpre-acquiredlocationinformationofneighbors;(5)cluster-basedschemewhereonlyclus-terheadsandgatewaysforwardagain.Ourapproach,passiveclustering,isdifferentfromthoseideasinthatitprovidesaplatformofefficientfloodingbasedonlo-callycollectedinformation(e.g.,neighborinformation,

2

clusterstates,etc.).Eachnodeparticipatesinfloodingbasedontheroleorstateintheclusterstructureinsteadofheuristicsusedin[1][6].

Anotherapproachofefficientfloodingistoexploittopologicalinformation[6][8][7][24].Withthenodemobilityandtheabsenceofpre-existinginfrastructureintheadhocnetwork,allworks,asfarasweknow,usetheperiodichellomessageexchangemethodtocollecttopologicalinformation.Ourapproachisdivergingfromthoseworksbecausepassiveclusteringdoesnotrequireperiodiccontrolmessagestocollecttopologicalinfor-mation.Passiveclustering,instead,exploitson-goingdatapacketstoexchangecluster-relatedinformation.[8]suggestedtwoschemescalledself-pruninganddominant-pruning.Self-pruningissimilartotheneighbor-coverageschemein[6].Withself-pruningscheme,eachforwardingnodepiggybacksthelistofneighborsofitselfonoutgoingpacket.Anoderebroad-casts(becomesaforwardingnode)onlywhenthisnodehasneighborsnotcoveredbyforwardingnodes.

Whileself-pruningheuristicutilizesinformationofdi-rectlyconnectedneighborsonly,thedominant-pruningschemeextendstherangeofneighborinformationtotwo-hopawayneighbors.Thedominant-pruningschemeissimilartoMultipointRelayscheme[7].InMultipointRelayscheme(MPR),anodeperiodicallyexchangesthelistofadjacentnodeswithitsneighborssothateachnodecancollecttheinformationoftwo-hopawayneighbors.Eachnode,basedonthegatheredinformation,selectstheminimalsubsetofforwardingneighbors,whichcoversallneighborswithintwo-hopaway.Eachsenderpiggybacksitschosenforwardingnodes(MPRNs)ontheoutgoingbroadcastpacket.

Moreover,basedontopologicalinformation,manyschemeshaveproposedtheschemetochooseadomi-nantset[21][22][23].They,still,dependontheperi-odichellomessagestocollecttopologicalinformation.

0.5In a single hop network0.45In a two hop network 0.40.35eta0.3R nois0.25illoC0.20.150.10.0500102030405060708090100Number of Neighbor NodesFig.1.Thecollisionrateofbroadcast

MOBIHOC2002Theextrahellomessages,however,consumeresourcesanddropthenetworkthroughputinMANETs[14].Theextratrafficbringsaboutcongestionandcollisionasge-ographicdensityincreases[1].

Figure1depictsthecollisionprobabilityofhellomes-sagesinasinglehopandatwohopnetworkasthenum-berofneighborsincreases.Thisresultclearlyshowsthattheneighbordegreeincreasesthecollisionprobabilityofbroadcast(note,thecollisionprobabilityismorethan0.1withmorethan15neighbors)andhiddenterminalaggravatesthecollisioninthemultihopnetwork.

NotethatFigure1assumesnoothertrafficexceptforhellomessagesinthenetwork.Withuser-datapackets,thecollisionprobabilityofhellomessageswillbein-creased.Thus,itisveryhardtocollectthecompleteneighbortopologyusinghellomessages.

Theaforementionedschemes(e.g.,neighbor-coverage,MPR,etc.),consequently,arenotscalabletoofferedloadandnumberofneighbors.

CLUSTER HEADGATEWAYORDINARY NODESFloodingS SourceFig.2.AnExampleofEfficientFloodingwithClustering.Onlyclus-terheadsandgatewaysrebroadcastandordinarynodesstopfor-warding.

A.BriefOverviewofClustering

Clusteringisanothermethodtoselectforwardingnodesasaddressedin[1].Clusteringinthispapercanbedescribedasgroupingnodesintoclusters.Arepre-sentativeofeachgroup(cluster)isnamedasaclusterheadandanodebelongingtomorethantwoclustersatthesametimeiscalledagateway.Othermembersarecalledordinarynodes.Thetransmissionareaoftheclusterheaddefinesacluster.Weusea2-hopclusteringwhereanynodeinaclustercanreachanyothernodeinthesameclusterwithatmost2hopsasdefinedin[9].Withclustering,non-ordinarynodescanbethedomi-nantforwardingnodesasinFigure2.

Figure3illustratesthedifferencebetweenacluster-ingandtheMPRscheme.Theclusteringpartitionsthenetworkintoseveralgroupsbasedontheradiorangeofaclusterhead.Thenetworktopology,therefore,doesnothaveaseriousimpactontheclusteringperformance.MPR,ontheotherhand,choosesthedominantsetusingtopologicalinformationsothattheperformanceofMPR

3

Flooding Tree AlgorithmCLUSTERINGA sourceCluster HeadRebroadcast nodesGatewayLinkOrdinary NodeFig.3.Infloodingtreealgorithms,everyneighborofasourcehas

torebroadcastssinceeachneighborisatmostoneadjacentnodeofsomenode.Inclustering,howeverordinarynodesarenotfor-wardingnodes.

iscloselyrelatedtothenetworktopology.

Clusteringinadhocnetworkshasbeenextensivelystudiedforhierarchicalroutingschemes[9][5][3],themasterelectionalgorithms[4],powercontrol[3],re-liablebroadcast[20]andefficientbroadcast[1][16].However,toourknowledge,theclusterarchitecturehasnotbeencommonlyusedforefficientfloodinginspiteofthepotentialbenefits.Firstofall,previouscluster-ingschemesarebasedonthecompleteknowledgeofneighbors.However,thecompleteknowledgeofneigh-borinformationinadhocnetworksishardtocollectandrequireshugecontroloverheadcausedbyperiodicexchangesofhellomessages.Secondly,noneoftheclusteringalgorithmshasproposedagatewayreductionmechanismtoselecttheminimalnumberofgateways.Thus,theclusteringsuffersfromthelargenumberofgatewaysinthedensenetwork.Lastly,thepreviousclusteringrequireshugemaintenancecostinhighmo-bility.

Wecansummarizethreeimportantobservationsasfollows.

1.Theselectionmechanismtochoosethedominantsetshouldbeefficientanddynamic.Otherwise,theschemecannotbeusedeffectivelyandpractically.2.InaMANET,collectingaccuratetopologicalin-formationisveryhardandcarriesthehugeoverhead.3.Clusteringschemeisindependentofthenetworktopologyunlikerouteaggregationprotocols(e.g.,MPR[7],SPAN[22],GAF[23]).

Thosefactsmotivateournewclusterformationpro-tocolcalledon-demand(passive)clustering.Withkeep-ingadvantagesofclustering,ourschemeeliminatesthemaincontroloverhead.

MOBIHOC2002III.PASSIVECLUSTERING

A.OverviewofPassiveClustering

Passiveclusteringisan“ondemand”protocol.Itcon-structsandmaintainstheclusterarchitectureonlywhenthereareon-goingdatapacketsthatpiggyback“cluster-relatedinformation”(e.g.,thestateofanodeinacluster,theIPaddressofthenode).Eachnodecollectsneigh-borinformationthroughpromiscuouspacketreceptions.Passiveclustering,therefore,eliminatessetuplatencyandmajorcontroloverheadofclusteringprotocols.Passiveclusteringhastwoinnovativemechanismsfortheclusterformation:FirstDeclarationWinsruleandGatewaySelectionHeuristic.WiththeFirstDeclara-tionWinsrule,anodethatfirstclaimstobeaclusterhead“rules”therestofnodesinitsclusteredarea(radiocoverage).Thereisnowaitingperiod(tomakesurealltheneighborshavebeenchecked)unlikethatinalltheweight-drivenclusteringmechanisms[3][5].Also,theGatewaySelectionHeuristic(SectionIII.C)providesaproceduretoelecttheminimalnumberofgateways(in-cludingdistributedgateways)requiredtomaintaintheconnectivityinadistributedmanner.

Passiveclusteringmaintainsclustersusingimplicittimeout.Anodeassumesthatsomenodesareoutoflocalityiftheyhavenotsentanydatalongerthantime-outduration.Withreasonableofferedload,anodecancatchdynamictopologychanges.B.ConstructionandMaintenance

Whenanodejoinsnetwork,itsetstheclusterstatetoINITIAL.Moreover,thestateofafloatingnode(anodedoesnotbelongtoaclusteryet)alsosetstoINITIAL.Becausepassiveclusteringexploitson-goingpackets,theimplementationofpassiveclusteringresidesbe-tweenlayer3and4.

TheIPoptionfieldforclusterinformationisasfollows:

NodeID:TheIPaddressofthesendernode.ThisisdifferenttothesourceaddressoftheIPpacket.Stateofcluster:TheclusterstateofthesendernodeIfasendernodeisagateway,thenittagstwoIPaddressesofclusterheads(CHs)whicharereachablefromthegateway.

Wesummarizethepassiveclusteringalgorithmasfol-lows:

Clusterstates

Thereare6possiblestates;INITIAL,CLUS-TERNODE,GATEWAY,CHREADYandDIST

4

READY(acandidateclusterhead)whenapacketarrivesfromanothernodethatisnotaclusterhead.Withoutgoingpacket,aCH

READY,foracandidategateway

nodethathasnotyetdiscoveredenoughneighborgateways.Recallthatwedevelopagatewayselec-tionmechanismtoreducethetotalgatewaysinthenetwork.ThedetailedmechanismwillbeshowninthenextSection.Acandidategatewayfinalizesitsroleasagatewayuponsendingapacket(announcingthegateway’srole).Notethatacandidategatewaynodecanbecomeanordinarynodeanytimewiththedetectionofenoughgateways.

C.GatewaySelectionHeuristic

Agatewayisabridgenodethatconnectstwoadja-centclusters.Thus,anodethatbelongstomorethantwoclustersatthesametimeiseligibletobeagate-way.Onecaneasilyconcludethatonlyonegatewayisneededfortheeachpairoftwoadjacentclusters.Withthisobservation,weinventgatewayselectionmecha-nismthateventuallyallowsonlyonegatewayforeachpairoftwoneighboringclusterheads.However,itispossiblethatthereisnopotentialgatewaybetweentwoadjacentclusters.Inotherwords,twoclusterheadsarenotmutuallyreachableviaatwo-hoproute.Ifthereisathree-hoproutebetweentwonodes,thentheclusteringschemeshouldselectthoseintermediatenodesasdis-tributedgateways.Withouttheknowledgeofcompletetwo-hopneighbors’information,choosingminimalbutenoughnumberofdistributedgatewaysseemstobeverydifficult.Asweexaminedinthepreviouschapter,thetopologicalknowledgecarrieshugeoverheadandworksinefficiently.Therefore,weproposeacounter-baseddis-tributedgatewayselectionmechanisminstead.

MOBIHOC2002Insummary,ourgatewayselectionmechanismcanbesummarizedasfollows.

Gateway

Anodebelongstomorethantwoclustersatthesametimeisacandidategateway.Uponsendingapacket,apotentialgatewaydecidestwoclusterheadsamongknownclusterheads.Thisnodewillserveasanin-termediatenodebetweenthosechosenclusterheads.Thisnodecannotbeanintermediatenodeoftwoclus-terheadsthathaveannouncedbyanotherneighborgatewaynode.Ifthenodefindstwoclusterheads,thenitfinalizesitsroleasagatewayandannouncestwoclusterheads(CHs)toneighbors.

Ifagatewayhasreceivedapacketfromanothergate-waywhichhasannouncedthesamepairofCHs,thenthisnodecomparesthenodeIDofitselfwiththatofthesender.IfthisnodehasthelowerID,itkeepsitsroleasthegateway.Otherwise,itchangesthepairofCHsorchangesitsstate.IfthisnodecanfindanotherpairofneighborCHsthatisnotannouncedbyanyothergateway,thenitkeepsitsstateasGATEWAYforthenewpairofCHs,otherwiseitchangesitsstatetoORDINARY

5

where

)(

)/,when

),0when

and

+

,

since

=

computationalcomplexityuponreceivingapacket.Withoutgoingpacket,eachnodesimplypiggybacks

cluster-relatedinformation.Thecomplexityis

.B.ReductionofRebroadcastwithPassiveClusteringPassiveclusteringdividesnodesintoseveralgroups

basedonthetransmissionrangeoftherepresentative

MOBIHOC2002node(clusterhead).Thus,thenumberofforwardingnodesisstableregardlessofthegeographicaldensityofthenetwork.Inotherwords,thereductionrateimprovesinproportiontothegeographicaldensity.

Figure5illustratesthemostdenseandaveragecaseof

TxRRTyRR/Root(2)TyTxFig.5.Theaverageandmostdensecaseofaclusterarchitecture

clusterconstructionwiththeassumptionthatthereareinfinitenumberofnodesplacedrandomly,andthenet-worksizeis(xthevertical)sizewhereisthehorizontalsizeandisofthenetworkarea.Givenofthetransmissionrangeofnode“A”,thenumberofclusterheadsandgateways,inthemostdenseclustercase,is

(1)

Theaveragenumberofclusterheadsandgatewaysis

(2)

Forexample,giventheroamingspace1000x1000(=1000,=1000),transmissionrange250(=250),thenumberofforwardingnodeswillbe21intheaverageand56intheworstcase.Iftherearetotally1000nodesinthenetwork,wecansavemorethan94.4%ofrebroadcastintheaverage.

Thereductionrateofpassiveclustering,conse-quently,is1-intheworstcasesuchthatdenotesthetotalnum-berofnodesinthenetwork.

6

V.SIMULATIONSTUDIES

WesimulatepassiveclusteringusingGlobalMobileSimulation(GloMoSim)library[11],whichisascalablesimulationenvironmentforwirelessnetworksusingPar-sec[15].First,weillustratefloodingefficiencywithpas-siveclustering.Weemployanewfloodingapplicationwheresourcessendfloodingpacketstothewholenet-workwithconstantbitrate.Second,weapplypassiveclusteringtorepresentativereactiveadhocroutingpro-tocols(AODV,DSRandODMRP),andshowthebene-fitsinroutingO/Hreductionandthroughput.

Forsimulation,weuseUDP(UserDataProtocol),IEEE802.11DCFandtwo-raypropagationmodel.Theradiopropagationofeachnodereachesupto250metersandchannelcapacityis2Mbits/second.Therandom-waypointmodelisusedfornodemobility.

Eachsimulationrunsfor600seconds(10minutes).Theresultsareaveragedover20randomlygeneratednodetopologies.

A.FloodingExperiments

Weanalyzefloodingefficiencywithpassivecluster-ingintermsofthefloodingreductionrateandthedeliv-eryratio.Eachmetriciscomputedasfollows.

TNP(TheTotalNumberofPacketssentforonebroadcast):Thetotalnumberofpacketssentfromallnodesisdividedbythetotalnumberofissuedbroad-castpacketsfromthesource.Thetotalpacketsin-cludethenumberofrebroadcastpacketsandthecon-troloverheadoftheprotocol(suchashelloorcluster-ingmessagesinthecaseofactiveschemes).

NDB(theNumberofnodesDeliveredtheBroad-cast):Theaveragenumberofnodestowhichthebroadcastpackethasbeendelivered.IfNDBisequaltothetotalnumberofnodesinthenetwork(),thenthedeliveryratioofbroadcast(RDB)is1.(Note,weexcludethesourcenode)

Wedemonstratethesuperiorityofpassiveclustering

bycomparisonwithoneofthemostefficientflood-ingtreeschemes:multipointrelay(MPR)andoneofthemostpopularactiveclusteringprotocols:LowestID(LID)[5].Forreference,wealsosimulateblindfloodingaswell.Notethatinblindflooding,eachnodebroad-castsatmostoncethesamepacket.

WerefineLowestID(LID)algorithmtobeap-pliedforefficientfloodingasfollows:First,weaddUN

MOBIHOC2002clusterswheneveraclusterheaddetectsthatanymem-berofthisclusterhasmovedoutthisnode’slocality.Suchmaintenanceisverypooroverthehighmobil-ityenvironmentduetoexcessiveoverhead.Thus,wemodifymaintenancetorestrictre-constructionofclus-tersonlyafterexchangingofhellomessages.Lastly,toimprovethefloodingefficiency,wedevelopandaddagatewayreductionmethodtoLIDalgorithm.AsolutiontofindtheoptimalgatewaysanddistributedgatewaysinadistributedsystemisNP-complete(setcoverproblem)[19].Thus,weusetheheuristicofMPRscheme.Aclusterheadchoosesthelistofgatewaysandsendsthatlistwhenitbroadcaststheclusterinformation.Aclusterheadchoosesasubsetofnodesamongneighborswhichcoversupallofnodeswithintwohopaway.Aclus-terheadbroadcaststhelistofgatewaysbypiggyback-ingthechosensetofnodesontheclusteringbroadcastpacket.Wecaneasilyprovethatthoseselectedgate-waysareenoughtoguaranteethecompletecoveragewithassumptionofthereliablepacketdelivery.LikeMPRscheme,eachnodepiggybackstheneighborlistonhellomessagestoexchangetwohopneighbors’in-formation.

Insummary,fourfloodingschemesarerunasfol-lows:BF(BlindFlooding),MPR-F(FloodingwithMPRscheme),AC

LID))andPC

LIDsendhellomessagesinevery2sec-ondsfollowing[7].PC

LIDuse5secondstimeouttoallowthe

1.5packetslosspereachhellomessage.

Throughthissimulation,weaimtoshowthatpassiveclusteringisworkingsuccessfullywithscenarios:nodemobilityandscale.Thus,wefirstfixthenetworksizeandvarynodemobility.Then,weteststaticnetworks(i.e.,nonodemobility)ofincreasingdensity.A.1FixedNetworkSizewithNodeMobility

Wesimulate100mobilenodesplacedrandomly

within1000x1000

.Withthesenetworksizes,7

10090 )PNT( PC_LID Nodes 100 BF Nodes 100 tne80s AC_LID Nodes 100 MPR Nodes 100 tekcaP 70fo rebmuN60 latoT50400246810121416Mobility (meter/sec)Fig.6.TheTNPofEachProtocolwithasinglesourceandthedata

rate1pkt/sec.The100nodesareplacerandomlyover1000x1000.Thereachablerangeofeachradiopoweris250.

10090 )PN80PC_LID Nodes 100 BF Nodes 100 T( tnAC_LID Nodes 100 MPR Nodes 100 es 70tekcaP 60fo rebm50uN lato40T30200246810121416Mobility (meter/sec)Fig.7.TheTNPofEachProtocolwiththepacketrateof4pkts/sec.

The100nodesareplacerandomlyover1000x1000

.theaverageneighborswillbe8nodes.Weincrease

nodemobilityfrom0m/sto16m/swith100secondspausetime.Figure6and7indicatethetotalnumberofpacketsrequiredtofinishonefloodingatdifferentspeeds.Inthoseexperiments,threeremarkablefactsareobserved.First,floodingefficiencywithpassiveclus-teringisfarbetterthanwiththeotherschemes.Thisismainlybecausepassiveclusteringchoosesthesub-optimaldominantforwardingnodesliketheothertwoschemesbutitdoesnotrequireextracontroloverhead.Theotherschemesalsoimprovetheefficiencyofflood-ing.They,however,aresufferingfromcontrolover-headduetohellomessagesorprotocolmessages.Notethat,inspiteofextracontroloverheadandthelowdatarate(1pkt/sec),eachschemestillprovidesperformancegainintermsofTNPmetricwithdeployinganefficientfloodingmechanism.Secondly,AC

MOBIHOC2002TABLEI

THENUMBEROFFLOATINGNODESOFAC

0

4

16LID-F(1pkt/sec)14.1

14

AC

13.2

14.8

17.6

TABLEII

THENUMBEROFNODESFLOATINGNODESOFPC

0

4

16LID-F(1pkt/sec)23

25PC

3.7

4.3

5.2

(*FloatingnodesarethenodeswhoseclusterstateisGW

LIDtendstohavemoreforwardingnodes

thanMPR.TableIclearlyshowsthatthenumberoffloatingnodesisproportionaltotheofferedloadbecausetheincreaseinofferedloadreducesthepacketdeliveryratio.AC

LID-Fsufferperformancedegradationsdueto

incompleteneighborknowledge.Anotheroutstandingoutcomeintheresultsisthattheperformanceofpassiveclusteringisnotsignificantlyaffectedbymobilitydiffer-entfromotherschemes.Thisobservationverifiesthatpassiveclusteringmaintainsclustersdynamicallywithtopologychanges.Furthermore,theMPR-Fsuffercon-siderableperformancedamagewithhighlyofferedloadasFigure9.Thisismainlycausedbyheavycontentionwiththehighdatarate.WithAC

8

LID-FisbetterthanAC

MOBIHOC20021009896)#( )B94DN( t92nuoC y90revile88D8684PC_LID Nodes 100 BF Nodes 100 AC_LID Nodes 100 MPR Nodes 100 822004006008001000120014001600X terrain size (meter)Fig.10.TheNDBofEachProtocolwithsinglesourceandthedata

rate4pkt/sec.The100nodesareplacerandomlyover”x”x1000.

10095)#( )B90DN( tnuo85C yrevile80D75PC_LID Nodes 100 BF Nodes 100 AC_LID Nodes 100 MPR Nodes 100 702004006008001000120014001600X terrain size (meter)Fig.11.TheNDBofEachProtocolwithsinglesourceandthedata

rate4pkt/sec.The100nodesareplacerandomlyover”x”x1000.

AsinFigure9,AC

LIDrequireperiodicmaintenance

andcontrolpacketexchangeandthusarenotagoodmatchforreactiveroutingprotocols.

Weusethefollowingmetricstoshowtheperformancegainwithpassiveclustering.

9

DeliveryRatio:Thetotalnumberofpacketdeliv-eredtodestinationsisdividedbythetotalnumberofsentpacketfromsources.

CtrlOH(NormalizedControlOverhead):Theto-talnumberofcontrolpacketisdividedbythetotalnumberofdeliveredpacketstodestinations.

B.1UnicastRouting

WeuseCBR(ConstantBitRate)sources.Wesim-ulate100nodesplacedrandomlywithina1500x500

terrain.Nodesaremovingrandomlywithminimumspeed2m/s,maximumspeed20m/sand100secondspausetime.Weincreasetheofferedloadusingthenum-berofCBRsessionsfrom10to50.EachCBRsourcestartsasessionrandomlywiththedataratio2pack-ets/secondand512bytespayloadsize.Notethatwein-cludethenoiseaccumulationfeatureinGloMoSim[11]forthisexperiment.Namely,eachnodeaccumulatesthepowerofsignalsbelow“receivethreshold”asnoise.

AODV

WeapplypassiveclusteringtoourimplementationofAODV[10].AODVhastwophasestosetuparoute:RouteRequestandRouteReply.ThemajorcontroloverheadofAODViscausedbyroutequeries(RREQ).Therefore,wechangetherouterequestphasetoapplyefficientfloodingwithpassiveclustering.Inclusterar-chitecture,eachnoderebroadcastsanewRREQonlywhenthisnodeisnotanordinarynode.Consequently,ordinarynodesareexcludedfromintermediatenodesforaroute.NotethateachnodecouldrebroadcastonlywhentheTTL(TimeToLive)fieldofthepacketisvalid.

Figure12and13(AODV-PC

LID-F)demonstratetheper-formancegainwithpassiveclustering.Passivecluster-ingsignificantlyreducesthefloodingoverheadandim-provesthedeliveryratio(N20).Astheofferedloadbecomesheavy,thecontroloverheadofAODVgrowssharply.Itisknownthatreactiveroutingprotocolstendtogenerateexcessivevolumeofroutequeriesinclud-ingre-issuingroutequeriesinheavyofferedload[17].Withpassiveclustering,AODVcanimprovetheperfor-manceandscalabilitysincepassiveclusteringmitigatesthescalabilityproblemofAODVwithefficientflooding.

DSR

DSRhastwomechanisms:RouteDiscoveryandRouteMaintenance[18].Routediscoverymechanismhastwophases:RouteRequestandRouteReply.

AsinAODV,DSRprotocolreducesthenumberofrouterequestpackets(RREQ)usingaggressivecaching

MOBIHOC20020.90.80.7)%0.6( oita0.5R yrev0.4ileAODV-PC_LID Nodes 100 AODV Nodes 100 D0.30.20.10101520253035404550Offered load (N) (# of connection)Fig.12.TheDeliveryRatioofAODVwithPassiveClusteringand

withoutPassiveClustering(100nodesplacedrandomlywithin

1500x500

)600AODV-PC_LID Nodes 100 AODV Nodes 100 500daehr400evO lrtC 300dezilamro200N1000101520253035404550Offered load (N) (# of connection)Fig.13.TheControlOverheadofAODVwithPassiveClustering

andwithoutPassiveClustering(100nodesplacerandomlywithin

1500x500

)ofroutes.Tocachetheroutes,DSRgeneratesmore

routerepliesanderrors.Therefore,weapplyefficientfloodingplatformstotheroutereplyphaseaswellastherouterequestphase.SametoAODV,onlynon-ordinarynodescanforwardroutequeries(RREQ)fortherouterequestphase.Fortheroutereplyphase,wechangetheDSRprotocolasfollows:

RouteReplyphase:InconventionalDSR,anodecaninitiatearoutereplywhenitreceivesanewRREQifithascachedroutestothedestination.Butwithaclusterarchitecture,onlynon-ordinarynodescaninitiatethisroutereply.

GratuitousRouteReply[18]:EachnodeinDSRprotocolsendsgratuitousroutereplieswhenithasfoundashorterpaththroughthisnodethanthesourcerouteintheIPpacket.Werestrictthisfeaturetoonlynon-ordinarynodesinaclusterarchitecture.

Figure14and15showthatpassiveclusteringimprovesthescalabilityofDSRbyreducingroutingoverhead().Passiveclusteringincursdeliveryratio

degradationwithlowofferedload(

).Themain10

0.650.6DSR-PC_LID Nodes 100 DSR Nodes 100 0.550.5)%0.45( oitaR0.4 yre0.35vileD0.30.250.20.150.1101520253035404550Offered load (N) (# of connection)Fig.14.TheDeliveryRatioofEachProtocolofDSRwithPassive

ClusteringandwithoutPassiveClustering(100nodesplacedran-domlywithin1500x500

)109DSR-PC_LID Nodes 100 DSR Nodes 100 8dae7hrevO6 lrtC 5dezila4mroN3210101520253035404550Offered load (N) (# of connection)Fig.15.TheControlOverheadofDSRwithPassiveClusteringand

withoutPassiveClustering(100nodesplacedrandomlywithin1500x1500)

reasonisthatpassiveclusteringrestrictsrouteoptimiza-tionandcaching.Thus,theaveragehopcounttendstoincreaseandtheroutequeriesaretriggeredmorefre-quentlywithpassiveclusteringthanoriginalDSR.

B.2MulticastRouting

Wesimulate50nodesplacedrandomlywithina1500

x300

terrain.Thenodemobilityisincreasedfrom0m/s(i.e.,nonodemobility)to16m/swith10sec-ondspausetime.Nodesaremovingbasedonrandom-waypointmodel.5sourcesaremulticastingdatapacketwith1024bytes/seconddatarateand16nodesarethetotalmembersof5sources.

Weapplypassiveclusteringtoourimplementationof

ODMRP[25].ODMRPhastwophasestosetupamul-ticast:JoinQueryandJoinReply.AsourcefloodsJoinQuerypacketperiodicallytofindthemembersofthismulticastgroup.Thus,weusepassiveclusteringtore-ducethefloodingoverheadofJoinQuery.Onlynon-ordinarynodesareforwardingJoinQuerypacketupon

MOBIHOC2002receivingtheJoinQuerypacket.Consequently,ordi-narynodesareexcludedfromForwardingGroupsforanymulticastgroup.

7.57ODMRP + PC_NET Nodes 100 ODMRP Nodes 100 6.56 LR5.5TC d5ezilam4.5roN43.532.520246810121416Mobility (meter/sec)Fig.16.ThenormalizedcontroloverheadofODMRPwithPassive

ClusteringandwithoutPassiveClustering.50nodesplacedran-domlyover1500x300

.Theradiorangeis250Figure16illustratesthereductionofcontroloverhead

forJoinQueryPacket.Thethroughputperformanceisaboutthesamewithandwithoutpassiveclustering.Wecanconcludethatpassiveclusteringcanbeap-pliedtoseveralreactiveunicastormulticastroutingpro-tocolstoreducecontroloverheadandimprovetheper-formanceandscalability.

VI.CONCLUSION

Inthispaper,wehaveintroducedanenhancedver-sionofthePassiveClusteringprotocol.Wehaveappliedittofloodingandhaveshowedthatitperformsaswellas(ifnotbetterthan)existingfloodrebroadcastcontrolschemes.Finally,wehaveappliedittoondemanduniandmulticastrouting.

Thispaperincludesseveralcontributions.First,weimprovetheclusteringschemewithaneffectivegatewayselectionheuristic.Ourgatewayreductionmechanismpermitstheuseoftheclusterarchitectureasarobustandefficientfloodingplatformoverdense,largemobilenetworks.

Secondly,weinvestigatetheproblemofefficientfloodingbasedontopologicalinformation.Tocollectneighbortopology,thenetworkincursaheavycon-troloverheadpenalty-itisverycostlytocollectaccu-ratetopologyinformationwithnodemobilityanddy-namicresources.Theaforementionedtopology-basedschemes,inconsequence,havethelimitingfactorofscalabilityandperformanceduetotheburdenofmes-sageandprocessingoverhead.Basedonthoseobserva-tions,wehaveconceivedanewfloodingschemebasedonpassiveclustering.Ourfloodingschemeisefficient,scalableandrobust.

11

Finally,weshowtheapplicabilityofpassiveclus-teringtoafewreactiveroutingprotocols(suchasAODV,DSRandODMRP).Passiveclusteringreducesthefloodingoverheadandimprovestheperformanceandscalability.

REFERENCES

[1]Sze-YaoNi,Yu-CheeTseng,Yuh-ShyanChen,Jang-PingSheu,

Thebroadcaststormprobleminamobileadhocnetwork,Mobi-Com,1999.

[2]JinyangLi,CharlesBlake,DouglasS.J.,DeCouto,HuImmLee,

RobertMorris,CapacityofAdHocWirelessNetworks,Mobicom,2001.

[3]C.R.LinandM.Gerla,AdaptiveClusteringforMobileWireless

Networks,IEEEJournalonSelectedAreasinCommunications,Vol.15,No.7,Sep.1997,pp.1265-1275.

[4]DennisJ.BakerandAnthonyEphremides,TheArchitecturalor-ganizationofamobileradionetworkviaadistributedalgorithm,IEEETransactiononcommunications,Vol.com-29,No.11,Nov.1981

[5]Gerla,MandTasi,J.,AMulticluster,mobile,multimediaradio

network,ACM-BaltzerJournalofWirelessNetworks,Vol.1No.3,1995

[6]Yu-CheeTseng,Sze-YaoNi,En-YuShih,AdaptiveApproaches

toRelievingBroadcastStormsinaWirelessMultihopMobileAdHocNetwork,Infocom,2001.

[7]AmirQayyum,LaurentViennot,AnisLaouiti,Multipointrelay-ing:Anefficienttechniqueforfloodinginmobilewirelessnet-works,INRIAreport,March2000.

[8]H.LimandC.Kim,Floodinginwirelessadhocnetworks,IEEE

computercommunications2000.

[9]Krishna,P.,Vaidya,N.H.,Chatterjee,M.,Pradhan,D.K.,A

cluster-basedapproachforroutingindynamicnetworks,Com-puterCommunicationReview,vol.27,(no.2),ACM,April1997.[10]C.Perkins,E.Royer,S.Das,Adhocondemanddistancevec-tor(AODV)routing,http://www.ietf.org/internet-drafts/draft-ieft-manet-aodv-03.txt,1999

[11]UCLA,Glomosim:Ascalablesimulationenvironmentfor

WirelessandWiredNetworksystems,http://pcl.cs.ucla.edu-/projects/glomosim.

[12]D.B.JohnsonandD.A.Maltz,Dynamicsourceroutinginad

hocwirelessnetworks,MobileComputing,AcademicPublishers,1996.pp.153-181.

[13]Z.J.Haas,Anewroutingprotocolforthereconfigurablewireless

networks,ICUPC’97pp.562-566

[14]GiuseppeBianchi,PerformanceanalysisoftheIEEE802.11

distributedcoordinationfunction,IEEEJournalonselectedareasincommunications,vol.18.March2000.

[15]R.Bagrodia,R.Meyer,M.Takai,Y.Chen,X.Zeng,J.Martin,

B.Park,H.Song,Parsec:Aparallelsimulationenvironmentforcomplexsystems,Computer,Vol.31(10),October1998,pp.77-85.

[16]M.Jiang,J.Li,Y.C.Tay,Clusterbasedroutingprotocol(CBR)

functionalspecification,IETFdraft1998.

[17]YunjungYi,TaekJinKwon,MarioGerla,Aloadawarerouting

(LWR)basedonlocalinformation,PIMRC2001accepted.

[18]J.Broch,D.Maltz,D.Johnson,Y.Hu,J.Jetcheva,Aperfor-mancecomparisonofmulti-hopwirelessadhocnetworkroutingprotocols

[19]A.V.Aho,J.E.Hopcroft,J.D.Ullman,Thedesignandanalysis

ofcomputeralgorithms,Addison-WesleyPublication.1974.[20]E.Pagani,G.P.Rossi,Reliablebroadcastinmobilemultihop

packetnetworks,Mobicom97(1997)

[21]J.WuandH.Li,Oncalculatingconnecteddominatingsetfor

efficientroutinginadhocnetworks,DIALM.1999

[22]B.Chen,K.H.Jamieson,andR.MorrisAnenergy-efficientco-ordinationalgorithmfortopologymaintenanceinAdHocwire-lessnetworks,Mobicom,2001

[23]Y.Xu,J.HeidemannandD.EstrinGeography-informedEnergy

ConservationforAdHocRoutingMobicom,2001

MOBIHOC200212

[24]M.Seddigh,J.SolanoandI.Stojmenovic,Internalnodesbased

broadcastingalgorithmsinwirelessnetworks,Proceedingsofthe34thAnnualHICSS2001

[25]S.-J.Lee,W.Su,andM.GerlaOn-DemandMulticastRouting

Protocol(ODMRP)forAdHocNetworks,InternetDraft,draft-ietf-manet-odmrp-02.txt,Jan.2000.

[26]YunjungYi,TaekJinKwonandMarioGerlaPassiveClustering

(PC)inAdHocNetworks,InternetDraft,draft-ietf-yi-manet-pac-00.txt,Nov.2001.

[27]T.Clausen,P.Jacquet,A.Laouiti,P.Minet,P.Muhlethaler,A.

Qayyum,L.ViennotOptimizedLinkStateRoutingProtocol,In-ternetDraft,draft-ietf-manet-olsr-05.txt,Nov.2001.

[28]R.G.Ogier,F.L.Templin,B.Bellur,M.G.LewisTopology

BroadcastBasedonReverse-PathForwarding(TBRPF),InternetDraft,draft-ietf-manet-tbrpf-03.txt,Nov.2001.