基于负载均衡的VANET跨层贪婪路由算法.pdf 7页

'中国科技论文在线http://www.paper.edu.cn基于负载均衡的VANET跨层贪婪路由算法**徐哲鑫，吴玮玮，吴怡5（医学光电科学与技术教育部重点实验室，福建师范大学，福州350007）摘要：针对GPSR路由协议中VANET节点负载不均衡的问题，本文提出一种基于负载均衡的跨层贪婪路由算法。该算法中将路由选择参数分为运动参数和通信参数。运动参数用于筛选出稳定的候选节点集，而通信参数用于选择负载轻的下一跳转发节点。在通信参数选择中，10本文跨层结合了MAC层的发送队列占用率，以及刷新次数作为路由选择的参考因素。仿真结果表明，该路由算法在端到端时延、分组投递率两方面的表现都优于GPSR。关键词：车载自组织网络；GPSR；跨层；负载均衡中图分类号：TN929.5215Cross-layerGreedyRoutingAlgorithmBasedonLoad-balanceforVANETXUZhexin,WUWeiwei,WUYi(KeyLaboratoryofOptoElectronicScienceandTechnologyforMedicineofMinistryofEducation,FujianNormalUniversity,Fuzhou350007)20Abstract:AimingattheproblemofunbalancedloadofVANETnodesinGPSR,thispaperproposesacross-layergreedyroutingalgorithmbasedonloadbalance.Inthealgorithm,theroutingparametersaredividedintomotionparametersandcommunicationparameters.Themotionparametersareusedtofilteroutthestablecandidatenodeset,whilethecommunicationparametersareusedtoselectthenexthopforwardingnode.Inthecommunicationparameterselection,thispapercombinesthesending25queueoccupancyrateoftheMaclayerandtherefreshtimesasthereferencefactorsofrouting.ThesimulationresultsshowthattheproposedroutingalgorithmperformsbetterthanGPSRintermsofend-to-enddelayandpacketdeliveryratio.Keywords:VANET;GPSR;Cross-layer;Load-balance300引言VANET（VehicleAd-hocNetwork）,又称车载自组织网络，是利用车辆上安装无线收发装置、智能计算机系统和GPS定位系统等装置搭建的车辆通信网络来实现车辆间交通信息[1]的交换。作为一种新的无线通信网络，VANET具有广泛的应用前景，是现代智能交通系35统的重要组成部分。在VANET中，路由算法的优劣很大程度上决定了通信质量，因此，设计一个合适有效的车辆移动路由协议是发展VANET的关键任务。随着定位技术的飞速发展，以及GPS定位系统在交通工具上的普及，基于地理位置的路由协议也相应成为了VANET路由协议的研究热点。其中，GPSR是经典的基于地理位置[2]的路由协议。GPSR（GreedyPerimeterStatelessRouting）采用了两种机制来维护路由：贪40婪转发机制和周边转发机制。贪婪转发机制中，当前节点根据邻居节点到目的节点的距离作为选路标准。若当前节点到目的节点的距离最短时，GPSR陷入空洞状态，此时则采用周边转发机制直至脱离空洞状态，再重新使用贪婪转发机制。数据转发过程中，两种机制循环切作者简介：徐哲鑫，男，副教授，硕导，主要研究方向：无线通信网络通信联系人：吴怡(1970-)，教授，硕导，主要研究方向：无线通信网络.E-mail:wuyi@fjnu.edu.cn-1- 中国科技论文在线http://www.paper.edu.cn换，直至数据到达目的节点。贪婪机制的选路参数单一，没有考虑到节点的通信特点，因此在拓扑高动态变化的VANET环境下，节点的高速移动性、车辆密度的动态变化都会使GPSR45算法的性能下降。因此，本文将对上述问题进行深入分析。在此之前，本节将对GPSR算法改进的现有研究成果进行简单总结。[3]文献提出了基于节点缓存长度的强化GPSR算法，该算法在节点到目的节点的距离的基础上，结合了节点的缓存队列长度，计算得出一个转发概率，转发概率大的节点优先转发[4]数据，有效解决了网络拥塞问题。文献为确保节点之间通信的稳定性，提出了基于运动矢[5]50量的改进算法，在转发数据包前对邻居节点的运动方向和速度进行预测。文献通过运动方向和与当前节点的相对速度差设置邻居节点的优先级，筛选出候选节点集，再根据速度和距[6]离两个因素计算出转发概率，这样有效降低高速环境下数据包的丢失率。文献利用多种参数求得一个权重值选择最优转发节点，其中包括车辆密度、节点方向和速度、到目的节点的[7]距离以及可利用带宽。为了避免贪婪转发的不合理引导，文献提出了一种考虑实时道路车55辆密度的路由算法，该算法中节点利用周期性信标分组携带道路的车辆密度信息，从而选择[8]适当的节点。文献将数据转发场景分为了直路场景和岔路口场景，在直路场景中节点通过矢量坐标来筛选最优节点；在岔路口场景中，节点通过预测邻居节点的运动轨迹选择下一跳[9]节点。文献在距离、方向、队列使用情况等参数的基础上，跨层结合了MAC层帧错率和物理层的信噪比，计算得出一个权重值，从而进行路由选择。60综上所述，现有的GPSR改进路由算法没有将节点的运动参数和通信参数分开考虑，而是集中地计算出一个权重值。这样的做法，使得单个参数的影响可能被其他参数掩盖。因为，运动参数对网络拓扑变化起着决定性的作用，因此本文将运动参数和通信参数分开考虑。此外，在通信参数的选择上，本文跨层结合了MAC层的发送队列占用率，并使得节点可通过自身的发送队列占用率动态调整Hello包的发送频率，从而自主响应数据转发。651城市场景下的跨层贪婪路由算法优化模型1.1路由选择考虑到不同度量对路由的影响不同，本文将选路度量参数分为：运动参数和通信参数。运动参数用于预测节点的移动性，筛选出可靠的邻居节点集，以确保未来通信过程中，这些节点不会移动出当前节点的通信范围，造成通信中断。而通信参数用于进行最优选路决策，70确保下一跳节点低负载、链路稳定。1.1.1运动参数为了保证在转发时刻，被选中的下一跳节点仍在通信范围内，本文对邻居节点的距离、相对加速度以及方向进行预测，选择在转发时刻T时，仍在在通信范围的邻居节点形成候0选节点集S{N}。ij75由式(1)可知，首先，根据车辆节点上配备的电子地图系统可以得知邻居节点在T时刻0的运动方向，从而在分叉路口时，可以排除方向不一致的节点，确保数据转发方向是向着目的节点方向。其次，参考GPSR贪婪转发机制，在选择下一跳转发节点时，考虑T时刻邻0居节点到目的节点距离。最后，为了保证下一跳转发节点和当前节点之间的行驶速度相对稳-2- 中国科技论文在线http://www.paper.edu.cn定，因此考虑T时刻两者之间的相对加速度。0w0,方向不同j80w1,方向一致(1)jimoveTTVw((pDp001)AS){N}jjjjjimove其中，p为权重值；Vj为邻居节点j的运动权重价值；Si{Nj}为节点i的候选节点集；DT0为T时刻，邻居节点j到目的节点的距离；AT0为T时刻，邻居节点j与当前转发j0j0节点i之间的相对加速度。1.1.2运动参数851.发送队列占用率在路由转发过程中，如果数据包被转发至一个发送队列占用率较高的节点，这势必会产生额外的排队时延，从而增加了数据包的端到端时延。同时，忽略节点发送队列的占用率可能导致短时间内大量数据包的流入，而其服务速度若低于数据包流入速度，则会造成发送队列溢出因此引发不必要的丢包，从而降低了路由性能的投递率。在此引入一种MAC层和网90络层之间交换信息的跨层机制。使用MAC层发送队列中缓存的分组数量的占用率作为标准来衡量当前节点的负载情况。如式(2)所示，节点i的发送队列占用率f(C)定义如下：icurrentQf(C)i(2)imaxQicurrentmax其中，Q是节点i当前发送队列长度，Q是节点i的发送队列总长度。ii2.刷新次数95在GPSR协议中，节点通过周期性地广播Hello包，获取邻居节点的位置信息和状态信息。当节点i的发送队列占用率f(C)较低时，表明节点当前的负载较轻，有能力转发更多i的数据包，从而避免数据包流入负载较重的节点。因此，本文提出根据节点自身的发送队列占用率，动态调整发送Hello包的频率。函数曲线如图1所示，随着节点i的发送队列占用率f(C)的降低，节点自适应地增大自身的Hello包发送频率Fg，以提高在邻居节点中的ii100感知度，因此f(Fgi)为凹函数。为了符合实际应用，当f(Ci)接近于1时，Fgi为VANET紧急消息最低发送频率，即10Hz；而当f(C)接近于0时，意味着节点i有足够的发送队i列空间进行数据转发，因此本文对应设置了最大的发送频率上限Fg=20Hz。节点i的发送max队列占用率f(C)和Hello包发送频率Fg的公式如下：ii2(3)f()FgiiFgmaxFgfCi1Fgi105其中，表示向上取整-3- 中国科技论文在线http://www.paper.edu.cn201918171615包发送频率14Hello/Hz1312111000.10.20.30.40.50.60.70.80.91发送队列占用率图1Hello包发送频率与发送队列占用率的关系图Fig.1TheRelationshipbetweenHelloPacketTransmissionFrequencyandTransmissionQueueOccupancy110相应地，节点i可根据在一定时间T内收到邻居节点j的Hello包的次数，即刷新次数f(N)，来判断邻居节点j的转发意愿，以及两者之间链路的稳定性，因为信道质量环境也ij会影响Hello包的刷新次数。对于刷新次数的统计，本文采取平滑窗口方式。nTfi(Nj)HelloPacketkk1(4)如式(5)可知，通过计算节点的发送队列占用率f(Ci)和刷新次数fi(Nj)可得出当前节点iicom115与邻居节点j之间的通信权重价值V：jicomVqf(C)(1q)f(N)(5)jjij1.1.3最优下一跳节点选择在选路过程中，当前转发节点i首先根据邻居节点的运动状态筛选出一个候选节点集合imoveSi{Nj}，并按照运动权重价值Vj从大到小排序；再通过通信参数计算得出节点i与候icomimoveicom120选节点j之间的通信权重价值V。结合V和V进行权重计算，得出最优下一跳节jjj点的综合价值，公式如下：iicomimoveVkV(1k)V(6)jjji其中，k为权重；V是当前节点i和邻居节点j之间的综合权重价值。j2仿真结果与分析1252.1仿真环境及参数设置本文采用NS3作为仿真平台，场景模型使用曼哈顿模型，仿真场景为2000m×2000m。车辆节点随机放置到城市环境的格状网上随机移动，当走到1个岔路口时随机选择1条街道继续运动。其他参数设置参见表1：表1仿真实验参数设置130Tab.1Simulationofexperimentalparametersset-4- 中国科技论文在线http://www.paper.edu.cn参数设定值MAC层类型MAC/802.11无线电传播类型Propagation/TwoRayGround无线类型Antenna/OmniAtenna信道类型Channel/WirelessChannel接口队列类型Queue/DropTail/PriQueue无线物理层类型Phy/WirelessPhy仿真平台Ubuntu13.10+ns-allinone-3.17+sumo运动模型ManhattanMobilityModel仿真场景2000m×2000m车辆节点数量6080100120140车辆节点最大速度20km/h30km/h40km/h50km/h60km/h仿真时间300s最大传输距离250m分组类型CBR分组发送速率1packet/s2.2仿真结果分析为了验证算法的合理性，本文主要采用了数据包投递率（packetdeliveryratio）和平均端到端时延（averageend-to-enddelay）两个指标，来分析评价GPSR和改进后的跨层贪婪135路由算法的性能，以验证本文所提出的跨层贪婪路由算法的有效性和准确性。(1)数据包投递率数据包投递率是目的节点所收到的所有数据包数量与源节点发送的所有数据包数量的比值。这个参数反映的是网络的吞吐量，同时验证传输的可靠性。(2)平均端到端时延140平均端到端时延是目的节点接收到的所有数据包的传输时延之和与收到的数据包个数的比值，它侧面反映了网络拥塞情况，平均端到端时延越小，表明路由选择的决策越佳。同时，本文将GPSR算法和跨层贪婪路由算法运用于两种不同的仿真场景中进行比较，一种是车辆速度相同，但车辆节点个数不同；另一种是车辆节点个数相同，但是车辆速度不同。图2、图3分别给出两种仿真场景下的数据包投递率和平均端到端时延的仿真对比结果。145图中蓝色实心圆点曲线表示GPSR算法；红色空心圆点曲线是本文所提的跨层贪婪路由算法。-5- 中国科技论文在线http://www.paper.edu.cn11GPSRGPSR0.9跨层贪婪路由算法0.9跨层贪婪路由算法0.80.80.70.70.60.60.50.50.40.4数据包投递率数据包投递率0.30.30.20.20.10.10060801001201402030405060车辆节点个数车辆节点速度(km/h)图2数据包投递率Fig.2Packetdeliveryratio150如图2所示，GPSR算法和跨层贪婪路由算法的数据包投递率都随着车辆节点个数的增加总体呈上升趋势。其中，跨层贪婪路由算法的数据包投递率明显优于GPSR算法。GPSR算法的数据包投递率的峰值在120个车辆节点处，后期有所下降，这是因为随着车辆节点的增加，网络数据吞吐量加大，GPSR算法在路由选择上没有考虑节点的负载情况，仅根据节点到目的节点的距离作为唯一的参考标准，因此在网络吞吐量增大的情况下，数据包投递率155不理想。在车辆节点速度与数据包投递率关系图中，GPSR算法的曲线随着车辆节点速度的增大而下降，但跨层贪婪路由算法的曲线较为平稳，这是因为跨层贪婪路由算法在运动参数中考虑了邻居节点的行驶速度、相对加速度，确保了数据传输过程中车辆节点的相对稳定性。100100GPSRGPSR90跨层贪婪路由算法90跨层贪婪路由算法80807070(ms)60(ms)6050504040平均端到端时延30平均端到端时延30202010100060801001201402030405060车辆节点个数车辆节点速度(km/h)图3平均端到端时延160Fig.3Averageend-to-enddelay如图3所示，在两个仿真场景下GPSR算法和跨层贪婪路由算法的曲线都呈上升趋势。但是，跨层贪婪路由算法的平均端到端时延都明显优于GPSR算法。这是因为在路由选择过程中，跨层贪婪路由算法根据邻居节点的发送队列占用率将数据包引导至负载较轻的节点，这有效缩短了数据包的排队时延，从而整体缩短了数据包的端到端时延。而GPSR算法忽视165了节点的负载情况，因此平均端到端时延的性能较差。-6- 中国科技论文在线http://www.paper.edu.cn3结论本文提出了跨层贪婪路由算法，该算法在GPSR算法的基础上跨层结合了MAC层参数，并将路由选择参数分为了运动参数和通信参数。其中，运动参数确保了节点之间的通信稳定性，通信参数考虑到在路由选择时节点的负载情况，均衡网络中各节点的负载，避免了数据170包的溢出丢弃。最后，通过NS-3仿真验证可知，跨层贪婪路由算法在数据包投递率和平均端到端时延两个性能指标上的表现都优于GPSR算法。[参考文献](References)[1]冯勇,梁浩.车载自组织网络中一种有效的匿名认证方法[J].计算机工程与应用,2010,46(23):126-128.175[2]KarpB,KungHT.GPSR:greedyperimeterstatelessroutingforwirelessnetworks[C]//InternationalConferenceonMobileComputingandNETWORKING.ACM,2000:243-254.[3]HuT,LiwangM,HuangL,etal.AnenhancedGPSRroutingprotocolbasedonthebufferlengthofnodesforthecongestionprobleminVANETs[C]//InternationalConferenceonComputerScience&Education.IEEE,2015:416-419.180[4]TuH,PengL,LiH,etal.GSPR-MV:AroutingprotocolbasedonmotionvectorforVANET[C]//InternationalConferenceonSignalProcessing.IEEE,2014:2354-2359.[5]HuL,DingZ,ShiH.AnImprovedGPSRRoutingStrategyinVANET[C]//InternationalConferenceonWirelessCommunications,NETWORKINGandMobileComputing.2012:1-4.[6]TrippbarbaC,UrquizaaguiarL,IgartuaMA,etal.AMultimetric,Map-AwareRoutingProtocolforVANETs185inUrbanAreas[J].Sensors,2014,14(2):2199.[7]YuH,YooJ,AhnS.AVANETroutingbasedonthereal-timeroadvehicledensityinthecityenvironment[C]//FifthInternationalConferenceonUbiquitousandFutureNetworks.IEEE,2013:333-337.[8]WangYB,WuTY,LeeWT,etal.ANovelGeographicRoutingStrategyoverVANET[C]//IEEE,InternationalConferenceonAdvancedInformationNETWORKINGandApplicationsWorkshops.IEEE190ComputerSociety,2010:873-879.[9]KatsarosK,DianatiM,TafazolliR,etal.CLWPR—Anovelcross-layeroptimizedpositionbasedroutingprotocolforVANETs[J].2011:139-146.-7-'