SADV

SADV:Static-Node-AssistedAdaptiveDataDisseminationinVehicularNetworks

YongDingandLiXiao,SeniorMember,IEEE

Abstract—Vehicularnetworkshaverecentlyattractedgreatin-terestintheresearchcommunity,andmultihopdatadisseminationhasbecomeanimportantissue.Toimprovedata-deliveryperfor-mance,weproposedeployingstaticnodesatroadintersectionstohelprelaydata.Inthispaper,wepresentSADV,whichisastatic-nodeassistedadaptivedata-disseminationprotocolforvehicularnetworks.Withtheassistanceofstaticnodesatintersections,apacketisforwardedtothestaticnodewhentherearenovehiclesavailabletodeliverthepacketsalongtheoptimalpath.Thestaticnodeisabletostorethepacketandtransmititwhentheoptimaldeliverypathbecomesavailable.Inaddition,weletadjacentstaticnodesmeasurethedelayofforwardingdatabetweeneachotherinrealtimesothattheroutingdecisionthatismadeatstaticnodescanadapttothechangingvehicledensities.Moreover,amultipathroutingmechanismisalsoadoptedinSADV,whichiseffectiveinreducingthedata-deliverydelay.OursimulationresultsshowthatSADVoutperformsothermultihopdatadisseminationprotocols,particularlyundermedianorlowvehicledensitywherethenet-workisfrequentlypartitioned.Inthispaper,wealsopresentsomeheuristicdeploymentstrategiestomaximizeSADVperformanceunderpartialdeploymentofstaticnodesandanalyzethembysimulations.

IndexTerms—Geographicrouting,mobileadhocnetworks(MANETs),multihoprouting,vehicularnetworks.

I.INTRODUCTION

EHICULARnetworkshaverecentlyattractedgreatin-terestintheresearchcommunity.Manypotentiallyuse-fulapplicationshavebeenenvisionedinvehicularnetworks[1]–[3].Theserangefromsafetyapplications,suchasvehiclecollisionavoidance,toothervaluableapplications,suchasreal-timetrafficestimationfortripplanning,informationretrieval,andmediacontentsharing.Moreover,byembeddingsensorsinvehicles,amobilesensornetworkcanbeestablishedtomon-itorroadsandotherenvironmentalconditions.Thevehicularnetworkscanactas“deliverynetworks”totransferdatafromremotesensornetstoInternetservers.

Mostofthepreviousresearchonintervehiclecommunicationislimitedtovehicleswithinonehoporafewhopsaway[1],[2][4]–[6],suchascommunicatingwithnearbyupstreamtraffic

ManuscriptreceivedJune7,2009;revisedNovember12,2009andJanuary31,2010;acceptedFebruary9,2010.DateofpublicationMarch15,2010;dateofcurrentversionJune16,2010.ThisworkwassupportedinpartbytheU.S.NationalScienceFoundationunderGrantCCF-0514078,GrantCNS-0551464,andGrantCNS-0721441.ThereviewofthispaperwascoordinatedbyDr.L.Cai.

TheauthorsarewiththeDepartmentofComputerScienceandEngineer-ing,MichiganStateUniversity,EastLansing,MI48824-1226USA(e-mail:dingyong@cse.msu.edu;lxiao@cse.msu.edu).

Colorversionsofoneormoreofthefiguresinthispaperareavailableonlineathttp://ieeexplore.ieee.org.

DigitalObjectIdentifier10.1109/TVT.2010.2045234

V

vehiclestoavoidcollisions.However,itisalsoimportanttosenddatafromavehicletoadestinationthatisseveralmilesawaythroughmultihoprelaybyanumberofintermediatevehicles.Forexample,thesensingdatafromavehiclemayneedtobesenttoasinkthatisdeployedmilesaway,oravehiclemaywanttosendqueriestoaremotesitesuchasagasstation.Thus,amultihoproutingalgorithmisneededinalargevehicularnetworkfortheseapplications.

Avehicularnetworkcanberegardedasaspecialtypeofmobileadhocnetworks(MANETs)withsomeuniquefeatures.First,asvehiclesmoveathighspeed,thetopologyofthevehicularnetworkchangesrapidly.Second,unlikeMANETswhereanend-to-endconnectionisusuallyassumed,vehicularnetworksarefrequentlydisconnected,dependingonthevehicledensity.Inaddition,themovementofvehiclesisconstrainedbytheroads,whichrendersmanytopologyholesinthenetwork.ThesecharacteristicsmaketheclassicalMANETroutingalgo-rithmssuchasAdHocOn-DemandDistanceVector[7]andGreedyPerimeterStatelessRouting[8]inefficientinvehicularnetwork,andsignificantlyinfluencethedesignofalternativeroutingprotocols.

Duetotherapidlychangingtopologyinvehicularnetworks,geographicroutingmechanismsbecomemorepreferablethantopology-basedroutingmechanismsbecauseofthelatter’shighmaintenanceoverheadofroutingtables.“Opportunisticfor-warding”[9]–[11]hasbeenproposed,targetingnetworkswheretheexistenceofanend-to-endpathcannotbeassumed.Specif-ically,avehiclewillcarrythepacketandforwardittoanewvehiclewhentheymeet.“Trajectory-basedforwarding”[12],[13]isanextensiontogeographicroutingmechanism,whichtriestodeliverpacketsalongasequenceofpredefinedroadsoratrajectory.Itisparticularlysuitableforvehicularnetworkswherevehiclesarerestrictedonroadswithstaticstructures.Mobility-centricdatadissemination(MDDV)[14]andvehicle-assisteddatadelivery(VADD)[15]aretwomultihoproutingprotocolsinvehicularnetworks,whichcombinegeo-graphicforwarding,opportunisticforwarding,andtrajectory-basedforwardingtodeliverdatafromamobilevehicletoastaticpositionbesidetheroad.Theyabstracteachroadasalinkwherethepacket-deliverydelaydependsonthevehicledensityontheroad.Therefore,apacketwillbedeliveredalongtheshortestdelaytrajectorytothedestination.However,asavehic-ularnetworkconsistsofhighlymobilenodes,itispossiblethatwhenapacketreachesanintersection,itcannotbedeliveredalongtheshortestdelaytrajectorybecausethereisnovehiclewithinthewirelesscommunicationrangeinthenextroadalongthetrajectorytorelaythepacketatthatmoment.VADDcopeswiththisproblembyselectingthebestcurrentlyavailablepath,

0018-9545/$26.00©2010IEEE

Authorized licensed use limited to: HUNAN UNIVERSITY. Downloaded on June 26,2010 at 02:57:23 UTC from IEEE Xplore. Restrictions apply.

2446IEEETRANSACTIONSONVEHICULARTECHNOLOGY,VOL.59,NO.5,JUNE2010

whereanavailablepathmeansthattherearevehicleswithinthecommunicationrangeonthatpathtocontinuedeliveringthepacket.

Therearetwoproblemsinthecurrentroutingprotocolsforvehicularnetworks.1)TheperformanceofVADDisquitesensitivetothevehicledensity.Underhighvehicledensity,thereisahighprobabilitythatthenextpathalongtheshortestdelaytrajectorytowardthedestinationisavailablewhenthepacketreachesanintersection.However,whenthevehicledensityismedianorlow,thesecondbest,thethirdbest,oreventheworstpathmaybetakenatanintersectionbecausetheyaretheonlyavailablepathsatthemoment.Thismakestheactualpacket-deliveryroutedeviatefarfromtheoptimalone,leadingtoadramaticincreaseinthepacket-deliverydelay.2)Therealshortestdelaytrajectorymaynotbetakenunderinaccuratedelayestimationofeachroad.BothMDDVandVADDestimatethepacket-deliverydelayalongeachroadbasedonsomeofflinestatisticalparameters,suchastheaveragevehiclevelocityandvehicledensityontheroadatdifferenttimesofaday.Nevertheless,astheseparametersvarywithtime,thestatisticalresultisnotanaccurateestimationofthecurrentpacket-deliverydelayalongeachroad.

Inthispaper,weproposeSADV,whichisastatic-nodeassistedadaptivedatadisseminationprotocolforvehicularnet-works.DifferentfromMDDVandVADD,thispaperfocusesondatadeliveryinlarge-scaleanddynamicVANETsunderlowvehicledensities,whereVADDexperiencesdramaticper-formancedegradationinthepacket-deliverydelay,andMDDVevenrenderspoorreliability.Thecontributionsofthispaperareinthefollowingaspects.

•Weproposedeployingstaticnodesatintersections,whichenablespacketstobestoredatanintersectionuntiltheoptimalpath(thepathwiththeminimumexpecteddatadeliverydelaytothedestination)isavailable.Oursimu-lationshowsthattheproposedstatic-nodeassistedroutingprotocolcandramaticallyimprovethepacket-deliveryper-formancecomparedwiththepreviouswork.

•Tobetterestimatethedelayofforwardingpacketsalongeachroad,thestaticnodesaredesignedtobeabletomeasurethepacket-forwardingdelayandpropagatethelinkdelayinformation.Therefore,theroutingdecisionineachstaticnodecanadapttothechangingvehicledensities.Weanalyzetheconvergingspeedofthelink-delayupdate(LDU)bysimulations.

•Wealsoproposeamultipathroutingalgorithm,whichcanfurtherdecreasethepacket-deliverydelaywithoutanexponentialincreaseintheprotocoloverhead.

•Furthermore,westudyintelligentpartialdeploymentstrategiesofstaticnodeswhenitisnotpossibletodeployastaticnodeateachintersection.Therestofthispaperisorganizedasfollows.PreviousstudiesaresummarizedinSectionII.ThemotivationofthispaperisintroducedinSectionIII.ThedetaileddescriptionofourroutingprotocolSADVisinSectionIV.SADVunderpartialdeploymentofstaticnodesisdiscussedinSectionV.InSectionVI,weevaluateourproposedapproachbycomparingitwithVADD.WeconcludethispaperinSectionVII.

II.RELATEDWORK

TherehavebeenmanystudiesondeliveringmessagesinsparseMANETswithsporadicconnectivityandever-presentnetworkpartitions.Inthesenetworkswithextremeconditions,traditionalroutingalgorithmsthatassumethefullyconnectedpathbetweenhostsbecomeinefficient.Incaseoftheran-dommovementofmobilenodes,“opportunisticforwarding”hasbeenproposedin[10],[16],and[17].Someotherstud-iesemployedcontrolledmobilitytohelpmessagedelivery[18]–[20].

Avehicularadhocnetwork(VANET)isaspecialtypeofMANETs.SeveralstudieshavefocusedonmultihoproutinginVANETsinadditiontotheworkwehavediscussedinSectionI.Greedyperimetercoordinatorrouting[21]isaposition-basedroutingprotocol,whichusestheknowledgeofthestreetmapstructure.Oncethepacketreachestheintersection,theroutingdecisionismadetoforwardthepackettotheneighboringvehiclewiththelargestprogresstowardthedestination.Greedytrafficawarerouting[22]usesthevehicledensityaswellasthedistancefromthedestinationforroutedecisionatintersec-tions.Whenapacketreachestheintersection,itwillselecttheneighboringintersection,whichisgeographicallyclosesttothedestinationandhasthehighestvehicletraffic.

Louvre[23]abstractsthestreetmapintoanoverlaynetworkbasedonthevehiclesatintersectionsandthevehicledensityineachroad.Thereexistsalinkifandonlyifthevehicledensityontheroadishigherthanthepredefinedthreshold.Aroutingprotocolthatusesthesimilarideaofoverlayroutinghasbeenproposedin[24].However,theyarenotsuitableforscenariosoflowvehicledensitiesbecausetheoverlaynetworkmaybedisconnectedmostofthetime.Incontrast,thispaperdealswiththeVANETunderlowvehicledensitiesaswell.Throwbox[25],whichisadevicethatcanstoreandforwarddata,hasbeendesignedtoimprovethenetworkthroughputandreducethepacketdelayindelay-tolerantnetworks.Theplacementofthrowboxesandthedeterminationofpacketforwardingtrajectoryarebasedonthecontactopportunitiesbetweeneachpairofmobilenodes,whichcanbeeffectiveinsmall-scalenetworks.However,theassumptionofknowncontactopportunitieslimitsitsextensibilitytolargerscalenetworks.Thestaticnodeinthispapertakesthesimilarideawiththrowboxinthatitcanstoreandforwarddatawhennecessary.Differentfromthrowbox,oursolutiondoesnotrequirethenodecontactopportunities.Instead,boththedeploymentofstaticnodesandtheroutingalgorithmutilizethestreetmapstructureandvehicledensitiesofeachroadinvehicularnetworks.TheSADVroutingprotocolisageographic-basedroutingprotocol,wheretheroutingdecisionateachvehicleorstaticnodeisbasedontheknowledgeofitspositiononthestreetmapanditscommunicationwithneighbors.Asaresult,theproposedSADVisapracticalsolutionforlarge-scalenetworks.

ToevaluateroutingprotocolsinVANETsbysimulation,varioustrafficmobilitymodelshavebeenstudied.Somestud-iesusedvehiclemovementmodelstosimulatetraffic[24],[26]–[28],whileNaumovetal.[29]evaluatedroutingprotocolsbasedonrealisticpublicandprivatetrafficovertherealregionalroadmapsofSwitzerland.Weusethemodelin[26]toevaluate

Authorized licensed use limited to: HUNAN UNIVERSITY. Downloaded on June 26,2010 at 02:57:23 UTC from IEEE Xplore. Restrictions apply.

DINGANDXIAO:SADV:STATIC-NODE-ASSISTEDADAPTIVEDATADISSEMINATIONINVEHICULARNETWORKS2447

Fig.1.PacketdeliverydelayofVADD.(a)Meanpacket-deliverydelay.(b)Packet-deliverydelay(100vehicles).

Fig.2.Static-nodeassistedroutinginaVANET.

ourprotocolbecausewebelievethatitcancapturethedynamicsoftheproblemthatwewanttoaddressinthispaper.

III.DATADISSEMINATIONUNDERDIFFERENTVEHICLEDENSITIES

ToevaluatetheperformanceofVADDwithregardtothepacket-deliverydelay,weusethedelayofepidemicflooding[16]asabaseline.Inepidemicflooding,twovehiclesexchangethepacketsthattheydonothaveincommonwhenevertheycancommunicatewitheachother.Assumethatthereisnopacketlossduetotransmissioncollision;epidemicfloodingisthequickestwaytodeliverapackettoitsdestination.Therefore,weusethisvalueasthelowerboundinouranalysis.Inthefollowing,werefertothismethodas“flooding.”

Fig.1illustratesourexperimenttoevaluatetheperformanceofVADDunderdifferentvehicledensities.Weextractare-gionalroadmapfromTiger[30],whichisshowninFig.6.Thesimulationisperformedonthisroadtopologywithdifferentnumbersofvehicles(thedetailedexperimentsettingisex-plainedinSectionVI).AsshowninFig.1(a),whenthevehicledensityishigh,themeanpacket-deliverydelayofVADDisclosetothatofflooding.However,thegapincreaseswiththedecreaseinthevehicledensity.Moreover,VADDbecomesunstableunderlowvehicledensities.Fig.1(b)showsthecom-parisonofthedeliverydelayofindividualpacketsbetweenVADDandfloodingwhen100vehiclesaresimulatedinthearea.Wecanobservethatthepacket-deliverydelayofsomepacketsismuchlargerthanthatofflooding,whilethedelayofsomeotherpacketsiscloseorevenequaltotheoptimalvalue.Therearetworeasonsforthisperformancedegradation.1)VADDchoosesthebestcurrentlyavailablepathateach

intersection.However,whenthevehicledensityislow,theoptimalpathmaynotalwaysbeavailableatthemoment.Thus,VADDhastodeliverpacketsviadetouredpaths.Intheworstcase,thepacketmaygothroughamuchlongerpathasindicatedbythepeaksinFig.1(b).2)Theestimationofthepacketforwardingdelaythrougheachroadisbasedonsomeofflinestatisticaldatasuchastheaveragevehicledensitybecauseitisexpensivetohaveeachvehiclegetup-to-datevehicledensitiesfromsomeinfrastructures.Asthevehicledensityoneachroadmayvarywithtime,whichgreatlyinfluencesthepacket-forwardingdelay,theshortestdelaypaththatiscalculatedbasedonthestatisticaldatamaynotreflecttherealoptimalone.Duetothesereasons,weproposeSADVinthispaper,whichcanimprovetheperformanceofdatadisseminationunderlowvehicledensitiesinVANETs.

IV.SADVDESIGN

Astheshortestdelaypathisnotalwaysavailableatthemomentwhenapacketreachesanintersection,wecandeployastaticnodeateachintersectiontoassistpacketdelivery.Thestaticnodecanstorethepacketforsometimeuntiltheshortestdelaypathbecomesavailable.AsillustratedinFig.2,apacketissentfromAtoaremotelocation.OncethepacketisrelayedfromAtoB,Bneedstodeterminethenextvehicletoforward.Assumethattheshortestdelaypathtodeliverthepacketisnorthward.However,thereisnovehiclewithinthecommunicationrangeofBthatcandeliverthepacketalongthedirection.Thus,Brelaysthepackettothestaticnode.ThestaticnodestoresthepacketforawhileandforwardsittoCwhenitpassestheintersectionandgoestowardthenorthwardroad.Fromthefigure,wecanseethatwithoutthehelpofthe

Authorized licensed use limited to: HUNAN UNIVERSITY. Downloaded on June 26,2010 at 02:57:23 UTC from IEEE Xplore. Restrictions apply.

2448IEEETRANSACTIONSONVEHICULARTECHNOLOGY,VOL.59,NO.5,JUNE2010

staticnode,thepacketwillbecarriedbyBtotheeastwardroadifBdoesnotmeetCattheintersection,whichmayleadtoamuchlongerpacket-deliverypath.

WeassumethateachvehicleknowsitslocationthroughtheGlobalPositioningSystemservice,whichisalreadyavailableinmostnewcarsandwillbecommoninthefuture.Eachvehicleorstaticnodeisequippedwitharadiothatiscapableofshort-rangewirelesscommunication(100–250m).Allvehiclesandstaticnodesbroadcastbeaconmessagesperiodically,sothattheycanknowtheirneighboringvehiclesandstaticnodes.Inaddition,eachstaticnodeknowsitsownpositionandhasadigitalstreetmap,basedonwhichthepacket-forwardingtrajectoryisdetermined.Here,wefocusonthecriticalissueofhowtoreducethepacket-deliverydelaybytheassistanceofstaticnodes.Efficientroutingalgorithmsneedtobedesignedforbothvehiclesandstaticnodes,whilecaremustbetakentoalleviatetheloadsinstaticnodes.Inthefollowing,wepresentthedesignofSADV,whichisastatic-node-assistedadaptivedata-disseminationprotocolforvehicularnetworks.Itconsistsofthreemodules:static-nodeassistedrouting(SNAR),LDU,andmultipathdatadissemination(MPDD).A.SNAR

SystemModel:Giventheroadmapoftheregion,wecanabstractitasadirectedgraphG(V,E),whereVisthesetofintersections,andEisthesetofdirectedroads.Assumethateachintersectionviisdeployedwithastaticnodesi.Letsiandsjbethestaticnodesattwoadjacentintersectionsviandvj.Then,theexpecteddelayofdeliveringapacketfromsitosjthroughthevehiclesonroadvivj,whichisdenotedasd(sisj),canbecalculatedas

d(sisj)=w(sisj)+t(vivj)

(1)

wherew(sisj)denotestheexpectedwaitingtimeofapacketatsiforvehiclescomingintothecommunicationrangetodeliverthepackettowardsjalongroadvivj,andt(vivj)denotestheexpectedtimetakentodeliverapacketthroughroadvivjgiventhatvehiclesarecurrentlyavailablefortransmittingthepacketatsialongvivj.

Supposethatvehiclesenterroadvivjfromviwithanaveragerateofλij.Then,λij=vij×ρij,wherevijandρijrepresenttheaveragevehiclevelocityandtheaveragevehicledensityontheroad,respectively.Therefore,theexpectedwaitingtimecanbecalculatedas

w(sisj)=

11=.λijvij×ρij

(2)

Ontheotherhand,t(vivj)isdependentonthevehicleden-sity,thevehiclevelocity,thelengthofroad,andthemaximum

wirelesstransmissionrange.Weusethefollowingformulain[15]tocalculatethisvalue,wherelijdenotesthelengthofroadvivj,andRrepresentsthemaximumwirelesstransmissionrange,i.e.,

󰀁

α·lij,ifρ1≤Rij

t(vivj)=lij(3)1

−β·ρif>R.ijvijρij

Authorized licensed use limited to: HUNAN UNIVERSITY. Downloaded on June 26,2010 at 02:57:23 UTC from IEEE Xplore. Restrictions apply.

DINGANDXIAO:SADV:STATIC-NODE-ASSISTEDADAPTIVEDATADISSEMINATIONINVEHICULARNETWORKS2449

withinRofthestaticnode),letstbetheneareststaticnodeofthepacket’sdestination.Then,sicancalculatetheoptimalpathfromsitostbasedondelaymatrixd.Thus,SNARshoulddeliverthepackettowardthenextstaticnodealongtheoptimalpath.Thisway,thepacketcanbedeliveredalongtheminimumexpecteddelaypath.Moreprotocoldetailsarediscussedinthefollowing.

DataForwardinginVehicles:SNARoperatesintwomodes,thatis,in-roadmodeandintersectionmode,whenapacketisinavehicle.

Uponreachingtheintersection(orthevehicleisintheradiocommunicationrangeofthestaticnodeintheintersection),theSNARstackonthevehicleworksintheintersectionmode.As-sumethatthevehiclehaspacketswithdestinationdst.Denotethestaticnodeattheintersectionbysi.Thevehiclefirstsendsaroutingquerytosifordestinationdst.Nodesicalculatestheoptimalnextintersection,whichisdenotedbysj,thatthepacketshouldbedeliveredtoandrepliestothevehicle.(Asthecalculationoftheoptimalpathinstaticnodesisbytheshortestpathalgorithm,itonlytakesseveralmillisecondstofinishthequery.)Thevehiclethendeterminesthenextvehicletodeliverthepacketto.Itwillforwardthepackettothevehiclethatisbothmovingtowardsjandclosesttosj.Ifsuchavehicleexists,thepacketwillbedeliveredtothenexthop.Aspecialcaseisthatthevehicleitselfisthebestvehicletofurtherdeliverthepacket;therefore,thevehiclewillcontinuetocarrythepacket.Iftherearenosuchvehicles,whenthevehiclestartstoleavetheintersection,itwilldeliverthepackettosisothatthestaticnodecandeliverthepacketalongthebestdirectionwhentherearevehiclesavailable.ThealgorithmisillustratedinAlgorithm1.Whenapacketiscarriedbyavehicleinaroad,whichhasnotenteredthecommunicationrangeofstaticnodesyet,theSNARstackonthevehicleoperatesinthein-roadmode.Assumethatthenextadjacentintersectiontodeliverthepacketissi.Wethenusegeographicforwardingtogreedilydeliverthepackettosi,thatis,ifthevehiclefindsanotherneighboringvehicle,whichisclosertosi,itwilldeliverthepackettothatvehicle.Algorithm1PacketDeliveryforVehicleIntersectionMode1:Denotethevehiclebycandthestaticnodebysi.2:Assumethatchaspacketsthataredestinedfordst.

3:Querysiforthenextintersectionfordst,whichisdenotedbysj.

4:whilechasnotpassedtheintersectiondo

5:LetN(c)denotetheneighborsofcthataregoingtowarddirectionsisj(c∈N(c)).Thesecanbevehiclesalreadyinroadsisj,orvehiclesthatwillturnintosisjafterpassingsi.6:ifN(c)isnotemptythen

calculatedk=(−1)p·7:Forck∈N(c),

distance(ck,si),wherep=0ifckisinroadsisjnow,orp=1otherwise(ckhasnotenteredtheroadyet).8:Letk∗=argmin({dk}).9:ifck∗=cthen10:Deliverthepacketstock∗.11:return12:endif13:endif14:endwhile

Authorized licensed use limited to: HUNAN UNIVERSITY. Downloaded on June 26,2010 at 02:57:23 UTC from IEEE Xplore. Restrictions apply.

2450IEEETRANSACTIONSONVEHICULARTECHNOLOGY,VOL.59,NO.5,JUNE2010

road.Forexample,ifvihasfouradjacentroads,[2,1,3,4]meansthatthefirstadjacentroadcorrespondstothesecond-bestpath,whilethesecondadjacentroadcorrespondstothebestpath,andsoon.Thestaticnodewillscanforcurrentlyavailableroads;thus,therankofthecurrentlybestpathcanbedeterminedforeachpacket,whichwecalltheinstantrank.Asfortheexampleabove,ifthefirstandfourthadjacentroadsareavailable,thenthefirstroadcorrespondstothecurrentlybestpathofdeliveringthepacket,andthus,theinstantrankis2.Inourstrategy,thepacketswiththehighestinstantrankwillbeeliminatedfromthebufferfirst.Insteadofbeingdirectlydropped,thesepacketswillbeforwardedalongthebestcurrentlyavailablepaths.Intuitively,thisstrategytriestoforwardsomepacketsalongsuboptimalpathsinthehopethattheywillnotsignificantlydifferfromtheoptimalpaths.Therefore,thisstrategyisfavorabletopreservethelowpacketdeliverydelayinVANETs.B.LDU

InSectionIV-A,theroutingdecisionismadeonadelaymatrix,wherethedelayofeachlinkisestimatedbasedonthestatisticalvehicledensityoveralongperiodoftimeineachroad.However,theestimationisofteninaccuratebecauseofthevariabilityofthevehicledensitywithtime.Here,weintroducetheLDUmodule,whichmeasuresthedelayofeachlinkinrealtimeandpropagatestheup-to-dateestimationamongstaticnodes.

Letsiandsjbetwoadjacentstaticnodes.Wecanmeasurethedelayofsisjbypiggybackingsomefieldsinthedatapacketthatisforwardedfromsitosj.Tomeasurethedelay,weinsertasinglefieldstimeintothepackethead.Whensireceivesthepacketforfurtherdelivery,itimmediatelyrecordsthecurrenttimeinstime.Then,whenthepacketreachessj,sjcancalculatethemeasuredpacketforwardingdelay,i.e.,

d󰀁(sisj)=etime−stime

whereetimeisthecurrenttime.Therefore,eachstaticnodesjisabletoobtainthemeasureddelayofallitsincominglinks{sisj}.

Letthedelaymatrixmaintainedbyeachsibedi.Initially,thedelayofeachlinkinthematrixiscalculatedby(1)basedonstatisticaldata.Letd󰀁(sjsi)bethemeanofthemeasureddelayd󰀁(sjsi)overtimeintervalI.Eachsicanobtaind󰀁(sjsi)forallofitsincominglinks.InSADV,eachstaticnodeexchangeswithothernodesthemeanmeasureddelaythatithasmeasuredsothateachnodegetsamorecompleteup-to-datedelaymatrix.Thepropagationofthemeanmeasureddelaythatisobservedineachstaticnodeisintheformofadelayupdatemessage,whichconsistsofrecordsinthefollowingform:

󰀆src_id,dst_id,delay,seq,expire󰀇

wheresrc_idanddst_idaretheIDsofthestartingandendingstaticnodes,respectively,delayisthemeanmeasuredpacketforwardingdelayfromsrc_idtodst_id,seqisthesequencenumberindicatingthefreshnessofthemessage,andexpire

denotesthetimewhentheinformationinthemessagebecomesinvalid.

Onceeachstaticnodesiobtainsd󰀁(sjsi),itencapsulatesthemintothedelayupdatemessageandinformsothernodesbybroadcast.Thebroadcastisrealizedbywirelesstransmissionorthecarryandforwardofvehiclesfromonestaticnodetoitsadjacentnodes.Theprocessissimilarwiththelink-statebroadcast[31].Topreventfloodingthenetwork,welimittheLDUinthelocalarea.Forexample,wesettheTTLofeachLDUpackettoK,whichisdecreasedby1ineachstaticnode.Theoptimalpathwillberecalculatedateachstaticnode;therefore,oncethepacketgetsnearthedestination,itwillgetmoreaccurateoptimalpaths.Tofurtherreduceoverhead,eachstaticnodeonlybroadcaststhefreshestdelaymeasurementforthesamelink,whichisidentifiedbyseq,andeachmessageisbroadcastonlyonceateachnode.Uponreceivingadelayupdatemessage,eachstaticnodeaccordinglymodifiesitsdelaymatrix.Supposethatskreceivesthedelaymeasurementofthelinksmsn.Then,dkwillbemodifiedbythefollowingformula:

¯󰀁(smsn)dk(smsn)=k1·dk(smsn)+k2·d

wherek1andk2aretwocoefficientssatisfyingk1+k2=1.C.MPDD

Inclassicalstudies,multipathroutinghasoftenbeenused

toimprovedatadeliveryreliabilityorachieveloadbalanceinnetworkcommunications.Inthispaper,weareinterestedindecreasingthepacketdeliverydelaybyroutingpacketsthroughmultiplepaths.

InaVANET,ifthepacketforwardingdelaybetweeneachtwoadjacentstaticnodescannotbeestimatedcorrectly,theshortestdelaypaththatiscomputedbasedontheestimateddelaymatrixmaynotbetherealoptimalone.Asthepacket-forwardingdelaythroughdifferentroadsmayvarydramati-cally,dependingonthevehicledistributionontheroads,thedifferentpathsthatapacketgoesthroughmaygreatlydifferinthetotaldeliverydelay.Thismotivatesustoutilizemultipathrouting,whenthepacketloadintheVANETisnothigh,todecreasethepacket-deliverydelaybytryingtohitafasterpaththanthesingle-pathrouting.

Packetsaredeliveredthroughmultiplepathsonlyatinter-sections.Therefore,multipathroutingcanberealizedbyonlysomeadditionalsupportinstaticnodes,withnomodificationsoftheprotocolstackinvehicles.Assumethatapacketisinsiatpresent.LetN(si)bethesetofstaticnodesthatareadjacenttosi.NodesiselectsasubsetofN(si),whichisdenotedbyNs(si),andthensendsacopyofthepackettoeachstaticnodeinNs(si).Thisway,thepacketwillbedeliveredalongmultiplepaths.Toreducetheoverheadcausedbymultipathrouting,weleteachintermediatestaticnodeskrememberthepacketsthatithassentoutforsometimeTm.Ifthesamepacketarrivesatskfromotherpathslater,itsimplyignoresthispacket.

WeusethefollowingstrategytochooseNs(si)outofN(si).Letsicomputethepriorityvector[p1,p2,...,pm]forthepacket.Then,siwillsendthepacketthroughtheroadscorrespondingtothebestandsecond-bestpaths.Forexample,

Authorized licensed use limited to: HUNAN UNIVERSITY. Downloaded on June 26,2010 at 02:57:23 UTC from IEEE Xplore. Restrictions apply.

DINGANDXIAO:SADV:STATIC-NODE-ASSISTEDADAPTIVEDATADISSEMINATIONINVEHICULARNETWORKS2451

Fig.5.Multipathdatadelivery.

ifthepriorityvectorisp=[2,3,1,4],thenthepacketwillbeforwardedtoboththefirstandthirdadjacentstaticnodes.Thisstrategyapplieswhentheestimationofthelinkdelayisnotaccuratesothatitwillincreasethechanceofhittingabetteroreventherealoptimalpath.Fig.5illustrateshowmultipathroutingworksintheVANET.ApacketisdeliveredfromStoD.Ineachstaticnodeattheintersection,thepacketisrelayedalongthebestandsecond-bestpathscomputedbasedontheestimateddelaymatrix.Theroadsthatthepacketgoesthroughareindicatedinbold.Asshowninthefigure,mostpathsconvergeintheend.Asastaticnodewillignorethepacketifithasrelayeditbefore,themultipathpacketdeliverydoesnotincurexponentialexplosionofthepacketdeliveryoverhead.

V.PARTIALDEPLOYMENTOFSTATICNODES

InSectionIV,weassumethateachintersectionisequippedwithastaticnode.However,whenitisimpossibletoputanodeateachintersection,thenode-deploymentstrategybecomesimportant,whichgreatlyinfluencestheaveragepacket-deliveryperformanceintheVANET.

Here,wegivesomeheuristicprinciplesfornodedeployment.Wewillanalyzethesenodedeploymentstrategiesbysimula-tionsinSectionVI.Notethatweonlyconsiderthestaticstreetmapstructureinthispaper.Theconsiderationofotherfactors,suchasthevehicledensity,isapromisingaspectoffutureresearch.

•Thestaticnodesshouldbedeployeduniformly.Thisisquiteintuitive.Asthevehicledensityvarieswithtimeandspace,ifwegivemorepreferencetoaspecificarea,thenthepacket-deliveryperformanceinotherareaswillbepoor.

•Theintersectionswithmoreconnectedroadsshouldpreferablybeequippedwithstaticnodes.Thereasonisthatifthedegreeoftheintersectionishigh,apackethasmorechoicesofroutestobeforwardedalongwhenitreachestheintersection.Ifthenearbyvehicledensityhappenstobelowandtheintersectionhasnostaticnode,thepacketwillprobablymissseveralbetterpaths.How-ever,iftheintersectionisequippedwithastaticnode,thepacketcanbestoredinthenodetowaitforamuchbetterchoice.Inotherwords,thedeploymentofstaticnodesintheseintersectionscanleadtomoredramaticimprovement

inpacket-deliveryperformancethanthoselowerdegreeintersections.

•Theintersectionsalonghigh-speedroadsshouldprefer-ablybedeployedwithstaticnodes.Astheaveragespeedishigherandthereareusuallymorevehiclesinthemainroadsbecausevehiclestendtotakethesefasterroadstogettotheirdestinations,thepacket-deliverydelaythroughtheseroadsisusuallylowerthantheothersmallroads.Thus,morepacketstendtobedeliveredtodestinationsviathesehigh-speedroads.However,ifapacketisdeliveredtoanintersectionofthemainroadfromsomesmallroads,andtherearenovehicleswithinthecommunicationrangetocontinueforwardingthepacketalongthemainroadatthemoment,thepacketwillmissthisbestdeliverypathandwillberoutedthroughothersmallroads,whichsubstantiallyincreasesthepacket-deliverydelay.There-fore,deployingstaticnodesattheseintersectionsmayhaveadramaticeffectinimprovingthepacket-deliveryperformance.

VI.PERFORMANCEEVALUATION

Here,weevaluatetheperformanceofSADV,ascomparedwithVADD.Weperformthesimulationonarealstreetmap,whichweextractfromTiger[30].TheTigerdatabasecontainsdetailedinformationofeachroad,suchasthepositionsofthetwoendsofeachroadandthetypeofeachroad.AsshowninFig.6,weextractaregionalurbanareafromtheTigerdatabasewitharangeof4000×5000m,whichcontains70intersections.Thespeedlimitofeachroadisdeterminedbasedontheroadtype.Inthefigure,therearetwohigh-speedroads(paintedinbold)withspeedlimitsover50mi/h,andtheotherroadsareoflocalspeedrangingfrom25to45mi/h.AstheTigerdatabasedoesnotidentifyone-waystreets,weregardallroadsinthemapastwo-waystreets.

WeimplementthesimulationprograminMATLAB.Weevaluateourprotocolunderdifferentnumbersofvehiclesinthearea.Themobilitymodelforeachvehicleisbasedon[26].Whenthesimulationstarts,eachvehicledeterminesarandomdestinationandthenselectsthequickestpathortheshortestpathwithequalprobabilitytothedestination.Uponarrivingatitsdestinationfollowingthepredeterminedpath,eachvehiclereselectsarandomdestinationandmovesonagain.Inourexperiments,weassumethateachvehicleorstaticnodehasawirelesscommunicationrangeof200mandbroadcastsabeaconmessageevery0.5ssothateachvehicleorstaticnodecangetanupdatedlistofneighbors.Fordata-packetgeneration,eachpacketisgeneratedbyarandomvehiclewitharandompositioninthemapasthedestination.Thedatapacketsizeissetto1024B.TheparametersarelistedinTableI.A.PacketDeliveryDelay

Inoursimulation,werandomlyselectvehiclestogeneratepacketswithrandomdestinationsinthemap.Wecontrolthetotalpacket-generationrateinthemapat10packetspersecond.Weusedifferentdata-disseminationprotocolstodeliverthepacketsandfinallycomputethemeanpacket-deliverydelayof

Authorized licensed use limited to: HUNAN UNIVERSITY. Downloaded on June 26,2010 at 02:57:23 UTC from IEEE Xplore. Restrictions apply.

2452IEEETRANSACTIONSONVEHICULARTECHNOLOGY,VOL.59,NO.5,JUNE2010

TABLEI

SIMULATIONSETUP

Fig.6.Roadtopologyusedinthesimulation.

Fig.7.Packet-deliverydelayofSADV.(a)Meanpacket-deliverydelay.(b)Delayforanindividualpacket.

allthepacketstocomparedifferentprotocols.Here,weassumethateachstaticnodehasenoughbuffersuchthatnopacketeliminationoccurs.WewillevaluateSADVwithlimitedbuffercapacityofstaticnodeslater.Thetotalsimulationtimeissetto1h.Thesimulationisrepeatedunderdifferentvehicledensities,andtheresultsareshowninFig.7.

AsshowninFig.7(a),thebottomcurvecorrespondstotheperformanceofepidemicflooding(wenoteitasfloodinginthispaper),whichcanberegardedasthelowerboundofthepacket-deliverydelayinvehicularnetworks.VADDsuffersfromahighpacket-deliverydelay,particularlyunderlowvehicledensities.When50vehiclesaresimulatedinthearea,themeanpacket-deliverydelayofVADDismorethantwiceofthelowerbound.ThisisbecauseVADDmayroutepacketsthroughdetouredpathsinsteadoftheoptimalpaths.SNARdeliverspacketswiththeassistanceofstaticnodesatintersections.IftheLDUisnotused,thepacket-forwardingdelaythrougheachlinkcanonlybeestimatedbythestatisticalvehicledensity,whichissimilarwithVADD.WecanobservethatSNARdecreasesthepacket-deliverydelaytosomeextent,whichindicatesthatthestaticnodescanhelpimprovethepacket-deliveryperformance.IfweusetheLDUtoinformthestaticnodesoftheup-to-datepacket-forwardingdelaythrougheachlink,theperformancecanbefurtherimproved.Oneexceptionisthatwhenthetrafficdensityisverylow,suchasbelow100vehicles,theLDUdoesnotbenefitthepacket-deliveryperformancethatmuchbecausetheLDUmessagemaynotbepropagatedtothenearbystaticnodesintime.Furthermore,whentheMPDDisused,theperformancecanbefurtherimproved,whichisclosetothatofflooding.Fig.7(b)showsthedeliverydelayofindividualpacketsbyusingdifferentroutingprotocols.Inthisexperiment,thetrafficdensityisfixedat100vehicles.Ascanbeseenfromthefigure,VADDsometimesexperiencesverylargedelay.Incontrast,

Authorized licensed use limited to: HUNAN UNIVERSITY. Downloaded on June 26,2010 at 02:57:23 UTC from IEEE Xplore. Restrictions apply.

DINGANDXIAO:SADV:STATIC-NODE-ASSISTEDADAPTIVEDATADISSEMINATIONINVEHICULARNETWORKS2453

Fig.8.Data-packetoverhead.

Fig.9.Control-packetoverhead.

numberofdatapacketsthatarerelayedviathestaticnodes,thatis,theloadofstaticnodes.Themust-forwardstrategyrelayseverypacketthatreachestheintersection,whereastheforward-as-neededstrategydramaticallyreducestheloadofstaticnodes.Forexample,whenthereare200vehicles,theloadofstaticnodesisreducedbyaround70%.

Fig.12illustratesthetrafficloadatintersectionsforbothstrategies.Wemeasurethetrafficloadbythenumberofdatapackettransmissionsintheintersectionarea.Forthemust-forwardstrategy,thereisonlyonecaseofdatatransmissionatintersections,thatis,apacketisforwardedfromavehicletothestaticnodewhenitreachestheintersectionandthenforwardedfromthestaticnodetoavehicleintheoptimalpathwhenitisavailable.Fortheforward-as-neededstrategy,therearethreecases:1)Whenapacketreachestheintersection,thereisnovehicleavailableintheoptimalpathdirection,whichisthesameasthemust-forwardstrategycaseandtakestwodatatransmissions.2)Ifthereisavehicleavailableintheoptimalpathdirection,thepacketisdirectlyforwardedtothevehicle,whichtakesonedatatransmission.3)Ifthereisavehicleavailableintheoptimalpathdirection,whichisitself,thepacketisnotforwardedandstaysinthevehicle.Fromthefigure,wecanobservethattheforward-as-neededstrategydecreasesthetrafficloadbyover50%comparedwiththemust-forwardstrategybecausecases2and3oftheforward-as-neededstrategysavedatatransmissionscomparedwiththemust-forwardcase.D.ConvergenceoftheLDU

Fig.10.Totaloverhead.

onlyincludeshellopackets(every0.5s),whichisthesameasVADD.

AlthoughSNAR+LDUcausesmorecontroloverhead,itdramaticallydecreasesboththedata-transmissionoverheadandthedata-deliverydelaycomparedwithVADD.Asdatapackets(1024Bperpacket)aremuchlongerthancontrolpackets(20–80Bperpacket),SNAR+LDUactuallyreducestheoveralloverhead.ThetotalnumberofbytesforbothdataandcontrolpackettransmissionisshowninFig.10.C.LoadofStaticNodes

Comparedwithourpreviouswork[32],wehavemadesomeenhancementstoreducetheloadofstaticnodes.In[32],whenapacketreachestheintersectionbythedeliveryofvehicles,itmustbeforwardedtothestaticnode.Thismethodmightmakethestaticnodesthebottleneckofthenetworkbecauseeverypacketneedstobedeliveredthroughthem.Toalleviatethisproblem,weforwardapackettothestaticnodeonlywhentherearenovehiclesavailabletodeliveritfurtheralongtheoptimalpath(seethedetailsinSectionIV-A).Tocomparetheirperformance,wecallthepreviousstrategymust-forwardandthelateroneforward-as-needed.

Fig.11illustratestheloadofstaticnodesforusingSNAR+LDUroutingwithbothstrategies.Wesettheoverallnetworkpacketgenerationrateto100packetspersecondunderdifferentvehicledensities.Foreachstrategy,wecalculatetheaverage

AsdiscussedinSectionIV-B,weletstaticnodesperiodicallypropagatethemeasuredlinkdelays(every10min)sothateachstaticnodecangetmoreaccuratelinkdelayestimations.Topreventflooding,wesetTTLto10ineachupdatemessagesothatlinkdelaysareupdatedinthelocalarea.Here,weanalyzehowfastthelinkdelaymatrixcangetupdatedineachstaticnode.Intheexperiment,wefirstset100vehiclesintheroadmapandthenadd100morevehicles.Oncethevehicledensitychanges,wecomputepathsbasedontwolinkdelaymatrices:1)thelocaldelaymatrixinastaticnode,whichisupdatedbytheLDUwithtime,and2)animaginaryglobaldelaymatrix,whereeachlinkdelayismeasuredinrealtime.Thepathscomputedbasedontheglobaldelaymatrixshouldbetherealoptimalpath,whichwewilluseasthebenchmarktocomparewiththepathsthatarecalculatedbyourproposedmethod.AsthereisdelayintheLDU,thelocaldelaymatrixneedssometimeforconvergence.

Wefirstcomparetheoptimalpathsthatarecomputedfromthelocaldelaymatrixandtheglobaldelaymatrix.Thereisamatchingoptimalpathifthepathsthatarecomputedfrombothmatricesarethesame.Wetestwith100randomsource–destinationpairsineachtime.Fig.13showstheper-centageofmatchingpaths.WecanobservethatthepercentageofmatchingpathsincreaseswithtimebecausethelocalmatrixisbecomingmoreaccuratewhenthedelaysofmorelinksgetupdatedbytheLDU.Wealsocalculatetheratioofthedelayoftheoptimalpaththatiscomputedfromthelocalmatrixoverthatoftheglobalmatrix,andtheresultsareillustrated

Authorized licensed use limited to: HUNAN UNIVERSITY. Downloaded on June 26,2010 at 02:57:23 UTC from IEEE Xplore. Restrictions apply.

2454IEEETRANSACTIONSONVEHICULARTECHNOLOGY,VOL.59,NO.5,JUNE2010

Fig.11.Trafficloadinstaticnodes.

Fig.14.

ConvergenceoftheLDU(optimalpathdelays).

Fig.12.Trafficloadatintersections.

Fig.15.

Analysisofbuffer-managementstrategies.

Fig.13.ConvergenceoftheLDU(theoptimalpath).

Fig.16.Analysisofnode-deploymentstrategies.

inFig.14.Theratioof1meansthatthelocalmatrixcangivepathswiththesameestimateddelayasthatoftheglobalmatrix.Wecanobservethattheratiodecreasestoalmost1after80s,whichindicatesthattheLDUneeds80stoconverge.Thisisareasonableamountoftimebecausethevehicletrafficisusuallystableinhours.

E.BufferManagementinStaticNodes

Welimitthebuffercapacityofeachstaticnodeandeval-uateSADV(SNAR+LDU)withdifferentpacket-eliminationstrategiesunderdifferentvehicledensities.Wesetthebuffercapacityto55packetsforeachstaticnodeandthenumberofvehiclesto100.Wevarythetotalpacket-generationrateinthenetworkandcomparethemeanpacket-deliverydelaycorrespondingtodifferentpacket-eliminationstrategies.ThesimulationresultsareshowninFig.15.Whenthepacketgenerationrateislow,thebufferisrarelyoverflowed.Thus,theperformanceissimilarfordifferenteliminationstrategies.However,whenthepacketgenerationrateisincreased,theleastdelayincreasestrategyapparentlyoutperformstheothertwostrategies.

F.SADVUnderPartialDeploymentofStaticNodes

AsshowninFig.6,thereareatotalof70intersectionsintheroadmap.Wedeploy35staticnodesbasedonthethreedifferentstrategiesmentionedinSectionVandsimu-

lateSADVunderdifferentvehicledensities.TheresultsareshowninFig.16.Thebottomcurvecorrespondstothecasewhereeachintersectionisdeployedwithastaticnode.Inthefigure,strategies1–3correspondtothethreedifferentnode-deploymentstrategies,i.e.,uniformdeployment,high-degreepreferred,andhigh-speedpreferredstrategies,respectively.Wecanobservethatgivenaspecificnumberofstaticnodes,placingstaticnodesathigh-degreeandhigh-speedintersectionshasabettereffectofreducingthedata-deliverydelaythantheuniformdeploymentofnodes.

VII.CONCLUSION

Asthevehicularnetworkiscompletelycomposedofmobilenodes,themultihopdata-deliveryperformancemaydegradeundermedianorlowvehicledensitieswherethenetworkisfrequentlydisconnected.Insuchcases,theperformancemaybeimprovedbyaddingsomestaticnodesatintersectionstoassistdatadelivery.Inthispaper,wehavepresentedSADV,whichreducesthedata-deliverydelaybythreemechanisms.InSNAR,apacketisforwardedtothestaticnodeiftherearenovehiclesavailabletodeliverthepacketalongtheoptimalpathatthemoment,andthus,thepacketcanwaitinthestaticnodeuntiltheoptimalpacketdeliverypathbecomesavailable.IntheLDU,theadjacentstaticnodesmeasurethelinkdelaybetweeneachotherinrealtimesothattheroutingdecisioncanbemadeadaptivetothechangingvehicledensities.Inaddition,the

Authorized licensed use limited to: HUNAN UNIVERSITY. Downloaded on June 26,2010 at 02:57:23 UTC from IEEE Xplore. Restrictions apply.

DINGANDXIAO:SADV:STATIC-NODE-ASSISTEDADAPTIVEDATADISSEMINATIONINVEHICULARNETWORKS2455

MPDDcanbeusedtofurtherdecreasethepacket-deliveryde-laybytryingtohitafasterdeliverypath.OursimulationresultshaveshownthatSADVdramaticallydecreasesthedatadeliverydelayundermedianandlowvehicledensitiesascomparedwithVADD,wherenostaticnodesareusedtoassistdatarouting.Furthermore,ourprotocolcanalsoadapttothecaseofpartialdeploymentofstaticnodes.Simulationresultshaveshownthatsomeintelligentdeploymentstrategiesperformbetterthantherandomdeploymentstrategy.

ACKNOWLEDGMENT

TheauthorswouldliketothankChenWangforhishelpfulcommentsintheearlystageofthispaper.

REFERENCES

[1]Q.Xu,T.Mark,J.Ko,andR.Sengupta,“Vehicle-to-vehiclesafetymes-saginginDSRC,”inProc.VANET,Oct.2004,pp.19–28.

[2]J.Yin,T.ElBatt,G.Yeung,B.Ryu,S.Habermas,H.Krishnan,and

T.Talty,“PerformanceevaluationofsafetyapplicationsoverDSRCve-hicularadhocnetworks,”inProc.VANET,Oct.2004,pp.1–9.

[3]B.Hull,V.Bychkovsky,Y.Zhang,K.Chen,M.Goraczko,E.Shih,

E.S.A.Miu,H.Balakrishnan,andS.Madden,“CarTel:Adistributedmobilesensorcomputingsystem,”inProc.4thACMSenSys,Nov.2006,pp.125–138.

[4]X.Yang,J.Liu,F.Zhao,andN.Vaidya,“Avehicle-to-vehicle

communicationprotocolforcooperativecollisionwarning,”inProc.MOBIQUITOUS,Aug.2004,pp.114–123.

[5]T.Nadeem,P.Shankar,andL.Iftode,“Acomparativestudyofdata

disseminationmodelsforVANETs,”inProc.MOBIQUITOUS,Jul.2006,pp.1–10.

[6]S.Ghandeharizadeh,S.Kapadia,andB.Krishnamachari,“PAVAN:A

policyframeworkforcontentavailabilityinvehicularad-hocnetworks,”inProc.VANET,2004,pp.57–65.

[7]C.Perkins,E.Royer,andS.Das,“AdHoconDemandDistanceVector

(AODV)Routing,”InternetDraft,IETF,2002.[Online].Available:draft-ietf-manet-aodv-10.txt

[8]B.KarpandH.Kung,“GPSR:Greedyperimeterstatelessroutingfor

wirelessnetworks,”inProc.MobiCom,2000,pp.243–254.

[9]A.Khelil,C.Becker,J.Tian,andK.Rothermel,“Anepidemicmodelfor

informationdiffusioninMANETs,”inProc.MSWiM,2002,pp.54–60.[10]Z.Chen,H.Kung,andD.Vlah,“Adhocrelaywirelessnetworksover

movingvehiclesonhighways,”inProc.MobiHoc,2001,pp.247–250.[11]K.Fall,“Adelay-tolerantnetworkarchitectureforchallengedInternets,”

inProc.SIGCOMM,2003,pp.27–34.

[12]J.Tian,L.Han,K.Rothermel,andC.Cseh,“Spatiallyawarepacket

routingformobileadhocinter-vehicleradionetworks,”inProc.IEEE6thITSC,2003,pp.1546–1551.

[13]D.NiculescuandB.Nath,“Trajectorybasedforwardinganditsapplica-tions,”inProc.MobiCom,2003,pp.260–272.

[14]H.Wu,R.Fujimoto,R.Guensler,andM.Hunter,“MDDV:Mobility-centricdatadisseminationalgorithmforvehicularnetworks,”inProc.VANET,2004,pp.47–56.

[15]J.ZhaoandG.Cao,“VADD:Vehicle-assisteddatadeliveryinvehicular

adhocnetworks,”IEEETrans.Veh.Technol.,vol.57,no.3,pp.1910–1922,May2008.

[16]A.VahdatandD.Becker.Epidemicroutingforpartiallyconnectedad

hocnetworks.DukeUniv.,Durham,NC,Tech.Rep.CS-200006,2000.[Online].Available:citeseer.ist.psu.edu/juang02energyefficient.html

[17]P.Juang,H.Oki,Y.Wang,M.Martonosi,L.Peh,and

D.Rubenstein,“Energy-efficientcomputingforwildlifetracking:Designtradeoffsandearlyexperienceswithzebranet,”inProc.ASPLOS,Oct.2002,pp.96–107.[Online].Available:citeseer.ist.psu.edu/juang02energyefficient.html

[18]Q.LiandD.Rus,“Sendingmessagestomobileusersindisconnectedad-hocwirelessnetworks,”inProc.MobileComput.Netw.,2000,pp.44–55.[Online].Available:citeseer.ist.psu.edu/li00sending.html

[19]W.Zhao,M.Ammar,andE.Zegura,“Amessageferryingapproach

fordatadeliveryinsparsemobileadhocnetworks,”inProc.5thACMMobiHoc,2004,pp.187–198.

[20]I.Chatzigiannakis,S.Nikoletseas,andP.Spirakis,“Anefficientcom-municationstrategyforad-hocmobilenetworks,”inProc.DISC,2001,pp.285–299.

[21]C.Lochert,M.Mauve,H.Füßler,andH.Hartenstein,“Geographicrout-ingincityscenarios,”ACMSIGMOBILEMobileComput.Commun.Rev.,vol.9,no.1,pp.69–72,Jan.2005.

[22]M.Jerbi,S.-M.Senouci,T.Rasheed,andY.Ghamri-Doudane,“Towards

efficientgeographicroutinginurbanvehicularnetworks,”IEEETrans.Veh.Technol.,vol.58,no.9,pp.5048–5059,Nov.2009.

[23]K.Lee,M.Le,J.Haerri,andM.Gerla,“Louvre:Landmarkoverlays

forurbanvehicularroutingenvironments,”inProc.IEEEWiVeC,2008,pp.1–5.

[24]W.Wang,F.Xie,andM.Chatterjee,“Small-scaleandlarge-scalerouting

invehicularadhocnetworks,”IEEETrans.Veh.Technol.,vol.58,no.9,pp.5200–5213,Nov.2009.

[25]W.Zhao,Y.Chen,M.Ammar,M.Corner,B.Levine,andE.Zegura,“Ca-pacityenhancementusingthrowboxesinDTNs,”inProc.IEEEMASS,2006,pp.31–40.

[26]A.K.SahaandD.B.Johnson,“Modelingmobilityforvehicularadhoc

networks,”inProc.VANET,2004,pp.91–92.

[27]R.Mangharam,D.Weller,R.Rajkumar,D.Stancil,andJ.Parikh,

“GrooveSim:Atopography-accuratesimulatorforgeographicroutinginvehicularnetworks,”inProc.VANET,2005,pp.59–68.

[28]D.ChoffnesandF.Bustamante,“Anintegratedmobilityandtrafficmodel

forvehicularwirelessnetworks,”inProc.VANET,2005,pp.69–78.

[29]V.Naumov,R.Baumann,andT.Gross,“Anevaluationofinter-vehicle

adhocnetworksbasedonrealisticvehiculartraces,”inProc.7thACMMobiHoc,2006,pp.108–119.

[30][Online].Available:http://www.census.gov/geo/www/tiger/

[31]J.F.KuroseandK.W.Ross,ComputerNetworking:ATop-DownAp-proachFeaturingtheInternet.Reading,MA:Addison-Wesley,2004.[32]Y.Ding,C.Wang,andL.Xiao,“Astatic-nodeassistedadaptiverouting

protocolinvehicularnetworks,”inProc.VANET,2007,pp.59–68.

YongDingreceivedtheB.S.andM.S.degreesfromSoutheastUniversity,Nanjing,China,in2001and2004,respectively.HeiscurrentlyworkingtowardthePh.D.degreeincomputersciencewithMichiganStateUniversity,EastLansing.

Hisresearchinterestsincludetheareasofdistrib-utedsystemsandcomputernetworking,includingwirelesssensornetworks,vehicularadhocnetworks,andwirelessmeshnetworks.

LiXiao(M’04–SM’10)receivedtheB.S.andM.S.degreesincomputersciencefromNorthwesternPolytechnicUniversity,Xi’an,China,andthePh.D.degreeincomputersciencefromtheCollegeofWilliamandMary,Williamsburg,VA,in2002.

SheiscurrentlyanAssociateProfessorofcom-puterscienceandengineeringwithMichiganStateUniversity,EastLansing.Herresearchinterestsin-cludetheareasofdistributedandnetworkingsys-tems,overlaysystemsandapplications,andwirelesssensorandmeshnetworks.

Authorized licensed use limited to: HUNAN UNIVERSITY. Downloaded on June 26,2010 at 02:57:23 UTC from IEEE Xplore. Restrictions apply.