一种AdHoc中基于位置路由的改进算法-王堃

:2007-07-15:“863”(2006AA01Z208);(200701);(BK2004149&BK2007236):　(1981-),,,E-mail:[e-mail]王　堃,吴　蒙(南京邮电大学通信与信息工程学院,江苏南京　210003):无线AdHoc网络中节点的移动性会导致路由更新,因此就需要进行新的路由发现.基于此,提出一种基于距离的位置路由改进算法,利用对目的节点位置信息的跟踪,根据节点之间距离的变化来动态调整路由发现,使得在位置辅助路由协议路由发现失败时避免采用全网洪泛机制.此外,设置距离更新门限来达到节点位置信息实时性与更新负载的平衡.仿真结果表明相比于位置辅助路由协议,所提的改进算法在分组成功投递率、平均端到端时延和路由负载上有一定提高.:自组织网;位置路由;位置信息:TN915.04　　:A　　:1001-2400(2008)02-0367-06Novellocation-aidedroutinginAdHocnetworksWANGKun,WUMeng(Inst.ofCommunicationandInformationEng.,NanjingUniv.ofPostsandTelecommunications,Nanjing　210003,China)Abstract:　Themovementofnodesinmobileadhocnetworksresultsinachangeinroutes,requiringsomemechanismfordeterminingnewroutes.Inthispaper,anoveldistance-basedlocation-aidedroutingforMANETisproposed.Bytracingthelocationinformationofdestinationnodesandthechangeofdistancebetweennodestoadjustroutediscoverydynamically,theproposedroutingalgorithmcanavoidfloodinginthewholenetworks.Besides,thedistanceupdatethresholdissetuptoreachthebalancebetweenreal-timeabilityandaccuracyoflocationinformationofnodes.PerformanceresultsbysimulationrevealthatthenewalgorithmperformsbetterthanLAR1intermsofthepacketsuccessfuldeliveryratio,averageend-to-enddelayandrouting-load.KeyWords:　AdHocnetwork;location-basedrouting;locationinformationAdHoc[1],,.AdHoc,,,[2].AdHoc,DSR[3]AODV[4],.,.,,,,();,.,,,.,.,,.,.,,,,、,Ad2008435　2　()JOURNAL　OF　XIDIAN　UNIVERSITY　Apr.2008Vol.35　No.2Hoc[5].,3:、[6].LAR[7],.LAPAR[8],,.Rango[9]LAR,RequestZone.LOTAR[10],LAR.LABGR[11],,.GLFCFR[12]RNG,.LBGR[13],,、.LMLAR[14]“”.LAAR[15],,.(LAR),,,,LAR.1　模型定义G=(V,E)AdHoc,V,E.:1),GPS[16];2),,,;3),;4),DUT(DistanceUpdateThreshold),(3)DUT,;,.5);,、ID,IC(IndexCounter),,IC,,..1　NS;ND;NI;NP.2　SD(XS,YS)(XD,YD),D(NS,ND),D(NS,ND)=(XS-XD)2+(YS-YD)21/2　.(1)　　3　AdSS.St(Xt,Yt),,St1t2AdS=(Xt2-Xt1)2+(Yt2-Yt1)21/2　.(2)　　4　1,NIDID;Pos;IC.图1　位置数据表格式图2　RREQ分组格式　　5　RREQ2,SIDID;DIDID;SeqN;SrcPos,DstPosPrePosNS,NDNP;IC.2　算法描述2.1　　　NSND,LAR,Requestzone,NS368　　　　　　　　　　　　　　　　　　西安电子科技大学学报(自然科学版)　　　　　　　　　　　　　　第35卷,Requestzone:I)NSRequestzone(LREQ)ND.LREQ,ND.,IC(LREP)NS,(LERR).图3　中间节点转发流程图II)NSLERR,ND,.LREP,NSNDIC,(RREQ).,RREQPrePosNS,,PrePosNI.NI3,:Algorithm:ReceivePacketforForwardingifNIreceivesaRREQfromNPthen　ifNIreceivedthisRREQbeforethen　　NIdropsoutthisRREQandsendsRERRtoNP　else　　ifDIDequalstoNDthen　　　sendsRREPtoNP　　else　　　ifICisexpiredthen　　　　NIbuffersthisRREQandsendsLREQinlocalandwaitsLREPtocheckformula(3)　　　else　　　　ifformula(3)issatisfiedthen　　　　　NIsendsRREQtoitsrelativeneighbornode　　　　else　　　　　NIdropsoutthisRREQandsendsRERRtoNP　　　　endif　　　endif　　endif　endifIII)NIRREQ,ND,IC,ND.IC,,NI.NIRREQ369第2期　　　　　　　　　　　　　　王　堃等:一种AdHoc中基于位置路由的改进算法LREQ.LREP.,.IV),NINDNPND.D(NI,ND)≤αD(NP,ND)+β　,(3)NI.RREQNI.D(NI,ND)NIND,(1),αβ.αβ,,.RREQNIND,NDRREQRREPNS..2.2　IC,AdS.SAdSDUT,.,IC1.,IC,,.NSND,NDICNS.RREQ,ICND.,.,NIICND.,NILREQND.IC,ND.2.3　AdHoc,,,.1)NSLARRequestzone,4(a),,4(b)(c),NIND,NIRERRNS,NINILAR,Requestzone.图4　数据包发送过程中的路由失败处理2)NSLREQLERR,ND,.NS,,,.3　性能分析NS-2.29[17],LAR1..:TransmissionRange250units;SimulationDuration200s;MobilityModelRandomWayPoint[17];MediumAccessProtocolIEEE802.11;LinkBit-rate256kb/s;PacketSize64bytes;TrafficSourcesCBR;Sendingrate4packets/s.50,70100;CBR;64bytes;4packet/s;randomwaypointmodel[18];1000×1000(unit);,;(0unit/s,50unit/s);DUT100unit;,α1,β0;IC0.3,,:Packetsuccessfuldeliveryratio=datapacketsdeliveredtothedestinationdatapacketsgeneratedbytheCBRsources　,370　　　　　　　　　　　　　　　　　　西安电子科技大学学报(自然科学版)　　　　　　　　　　　　　　第35卷Routingloadratio=controlpacketsdeliveredbyDBLARcontrolpacketsgeneratedbyLAR　,Averageend-to-enddelay=queueingdelay+transmissiondelay+propagationdelay+processingdelay+retransmissiondelay　.5～7(DBLAR(Distance-BasedLAR)).图5　不同节点数目的分组成功投递率5,.,,.,LAR1,LAR1,.LAR.,,.图6　改进算法与LAR1的路由负载比率图7　节点数为50时的平均端到端时延　　(LREQ,LREPLERR)(RREQ,RREPRERR),LAR1.6,LAR1.,,LAR1.,,.,,LAR1,LAR1,.750..,,LAR1.LAR1,Requestzone,LAR1,.LAR1,,,.4　结束语,,,LAR.LAR1,371第2期　　　　　　　　　　　　　　王　堃等:一种AdHoc中基于位置路由的改进算法、.,,.,.:[1]DavidR,IgnasGN.AdHocNetworkinginFutureWirelessCommunications[J].ComputerCommunications,2003,26(1):36-40.[2],.MANET[J].,2000,28(11):88-92.ZhangLulin,LiChengshu.ComparisonAnalysisforMANETRoutingProtocol[J].ActaElectronicaSinica,2000,28(11):88-92.[3]PerkinsCE,BhagwatP.HighlyDynamicDestination-SequencedDistance-Vector(dsdv)RoutingforMobileComputers[C]//ProceedingsoftheACMSIGCOMM94ConferenceonCommunicationsArchitectures.NewYork:ACMPress,1994:234-244.[4]BrochJ,MaltzDA,JohnsonDB,etal.APerformanceComparisonofMulti-HopWirelessAdHocNetworkRoutingProtocols[C]//Proceedingsofthe4thAnnualACM/IEEEInternationalConferenceonMobileComputingandNetworking.NewYork:IEEEPress,1998:85-97.[5]MauveM,WidmerJ,HartensteinH.ASurveyonPositionBasedRoutinginMobileAdHocNetworks[J].IEEENetworkMagazine,2001,15(6):30-39.[6]ChengX,HuangX,DuDZ.AdHocWirelessNetworking[M].Kluwer:AcademicPublishers,2003:103-136.[7]KoY,VaidyaNH.Location-aidedRouting(LAR)inMobileAdHocNetworks[C]//Proceedingsofthe4thACM/IEEEInternationalConferenceonMobileComputingandNetworking.Dallas:ACMPress,1998:66-75.[8]XueY,LiBC.ALocation-ai