基于位置和定向泛洪的车联网区域路由协议

孙友伟, 孙小田, 王　楠

(西安邮电大学 通信与信息工程学院, 陕西 西安 710121)

基于位置和定向泛洪的车联网区域路由协议

孙友伟, 孙小田, 王楠

(西安邮电大学 通信与信息工程学院, 陕西 西安 710121)

摘要:为提高车载自组网通信中路由发现和数据传输的效率，对区域路由协议进行改进。在分组中加入节点坐标、速度和时间字段，各节点接收分组后，记录或更新此信息到自身位置缓存表。路由发现阶段，节点位移大于位置更新半径时才更新路由，以此减少路由发现次数；非目的节点查询位置缓存表或路由表后直接应答，以此加快路由发现时间。数据传输阶段，节点通过定向区域转发以限制泛洪，以此降低控制开销。通过搭建车联网场景，对60个节点在5～50 m/s速度下进行仿真实验，结果显示，改进方案可使时延降低6%～13%，分组投递率增加6%～20%。另当节点速度大于35 m/s时，可使控制开销减少7%～14%。

关键词:车载自组网;区域路由协议;位置信息;位置缓存表;定向限制泛洪

车载自组网(VehicleAdhocNetwork,VANET)是指车人、车车、车路和车云之间，通过实时交通信息的采集、共享、发布和处理，更好地对道路和车辆进行实时监控和调度，以保障人们的出行安全和出行效率[1-2]。在VANET中，汽车节点随机运动具有很高移动性，对路由技术有着更为严苛的要求，以适应快速变化的网络拓扑重构[3]。VANET路由协议可分为先应式、反应式和混合式3种[4-5]，大部分由移动自组网路由协议改进而来，因各有侧重，缺乏普遍适用性，难以满足VANET不同场景的实际需求[6-7]。

作为混合路由协议的代表，区域路由协议(ZoneRoutingProtocol,ZRP)[8]将网络划分为若干虚拟区域，区域内采用先应式路由，区域间采用反应式路由。当源节点存在通信需求时，首先查询源节点和目的节点是否处在同一区域内。若在，则直接发送；若不在，启动区域间路由发现，由边界传播分解协议(BordercastResolutionProtocol,BRP)构造边界广播树，将路由请求直接扩散到边界节点，由边界节点进行区域内查找，直至找到目的节点。ZRP继承并结合了先应式和反应式路由的优点，可用于VANET。目前，关于ZRP协议的研究主要集中在优化区域半径和引入位置辅助方面[9-10]。

ZRP中分组传播均通过广播形式全向扩散，占用大量信道资源，开销较大。借鉴现实生活中寻找目标的方法，假设知道目标位置，即可有针对性地只在目标活动轨迹范围内进行查找，从而更快更省地找到目标。

本文拟对ZRP进行改进，利用节点位置信息(坐标、速度和时间)指导路由发现过程，继而通过计算定向区域转发进行精细化限制泛洪，给出基于位置和定向泛洪的区域路由协议(Location-basedandRestricted-floodingZRP,LR-ZRP)，以求提高ZRP协议路由发现和数据传输的效率，满足VANET对时延、开销的特殊需求。

1区域路由协议改进

1.1位置更新

ZRP协议中，区域内路由协议(IntrazoneRoutingProtocol,IARP)使用先应式路由，周期性交换路由信息，将由拓扑变化产生的信息传播限制在区域内部，区域间路由协议(InterzoneRoutingProtocol,IERP)使用反应式路由，需要时才开始路由发现[11]。ZRP区域划分重叠度较高，若网络拓扑变化较慢，节点相对位置变化较小，则频繁盲目地发起路由更新，容易导致多余网络开销，增加延时。

LR-ZRP引入位置触发机制，结合周期性更新和位置更新，继而指导路由更新。LR-ZRP能够根据节点运动状况，对寻路过程作出及时自适应修复或优化路由，从而更准确有效地维护区域内路由。

1.1.1位置触发更新机制

借鉴无线通信手机寻找基站的方式，当节点发现自己的位置区移动到一个新地方，就主动告知，向周围节点发起位置更新。例如，设置位置更新半径R，节点在时刻t0位于(X0，Y0)，时刻t1运动到(X1，Y1)，若

则主动广播一个位置更新分组(LocationUpdatePacket,LUDP)给周围节点，其中包括节点当前速度、时间和坐标字段，否则，不更新位置。如此，则可保证位置信息的实时性。

1.1.2周期性更新机制

由于累积效应，各节点自身位置变化不大，但是节点之间间距变大，链路可能发生变化。或者由于位置变更消息存在时效性，节点位置并没有变化，但受网络信号影响，无法找到该节点。保留周期性位置更新，要求节点每隔一定时间，不管位置区有没有变化，都发起向周围节点发起位置更新，可保证位置信息的有效性。

当LR-IARP结合位置触发和周期性位置更新，获知到区域内节点位置信息引起的路由发生变化后，主动通知LR-IERP进行路由更新。LR-IERP可及时进行无效路由修复和最佳路由优化。

1.2位置缓存表

定位设备只可帮助节点获知到自身位置信息[12]，包括当前速度、时间和坐标，但路由发现时，还需知道其他节点位置信息，且位置信息越即时，路由就越精确。LR-ZRP协议中，通过位置触发和周期性更新机制，各节点需要维护一张位置缓存表和一张路由表。位置缓存表记录着周围节点的位置信息，并定期清除无效信息，它就像是一张局部网络拓扑图。

LR-ZRP协议请求分组分为位置请求分组(LocationRequest,LREQ)和路由请求分组(RoutingRequest,RREQ)2种。每个LREQ分组均记录自身节点、目的节点以及所经过中间节点的即时位置信息。当节点接收到LREQ分组后，都会对比时间字段的值，判断时间新旧程度，创建或更新此信息到自己的位置缓存表，继而优化或修复路由表。各节点位置信息实时更新，为定向精细化限制路由提供有效保障。

ZRP协议规定，只有目的节点所在区域内的节点，才可对接收到的路由请求回送路由应答，所以路由发现所用时间比较长。LR-ZRP协议中，源节点查找目的节点时，只需查询当前节点位置缓存表或路由表，存在目的节点位置信息或路由信息，即可直接进行应答，能减小路由查询时间。

1.3路由定向查找转发

ZRP协议中，当目的节点处在本地区域之外时，IERP只能发起全向广播进行盲目寻找，网络开销太大。LR-IERP利用节点实时位置信息，按位置区进行分区域寻找，能有目的地定向精准查找，有助减少广播风暴产生。

源节点S通过查询位置缓存表，获知目的节点D在时刻t0所处位置和速度，估算D在时刻t1的可能活动范围。最佳路由请求区域必须尽可能覆盖S和D的有效活动区域，以及包含寻路所必须的中间节点。综合考虑各节点位置估计误差和时刻t1目的节点D可能区域预测误差，以及搜索区域必须尽可能覆盖必需的中间节点，还要充分限制无效泛洪，确定较为合理的路由请求区域。

若目的节点D在时刻t0位于(X0，Y0)，Vmax是t0到t1时间段内D的最大速度，则在时刻t1，D的可能活动区域是以r=Vmax×(t1-t0)为半径的圆形区域。以该圆形区域的外接四边形3个顶点和过S与D连线L的垂线,确定矩形区域ABCE，即为路由请求区域(图1)。点A，B，C和E的纵横坐标分别为

图1　LR-ZRP请求区域

中间节点通过计算自己到矩形框各顶点的距离和，对比A点到B、C和E的距离和，从而判断自己是否处在区域内。位于路由请求区域内节点才能参与转发，若在区域之外，则不再继续传播，由此限制泛洪。

由于GPS设备各节点位置估计误差、t1时刻D节点可能区域预测误差以及有限搜索范围未覆盖有效中间节点等原因，都可能导致规定时间内未找到路由，则要修正搜索范围重新查找，极端情况下回归ZRP协议广播查找。

边界传播分解协议LR-BRP工作机制类似于BRP，在此不再赘述。

2改进协议的路由转发过程

2.1源节点获取目的节点位置信息

源节点S存在通信需求时，需先获知D位置，具体过程描述如下。

步骤1S查找自身位置缓存表中是否存在D的位置信息。若有，转步骤4。若无，转步骤2。

步骤2LR-IARP在本地区域内广播位置请求。若成功，回送位置应答给S，并转步骤4；若不成功，转步骤3。

步骤3沿着BRP边界树，广播位置请求。若成功，放入D位置信息，回送位置应答，转步骤5；若不成功，回送位置错误。

步骤4判断S和D是否同处一个区域。若是，直接转发；否则，转步骤5。

步骤5依据S和D的坐标计算路由请求区域，并加入S和D位置信息后生成路由请求，借助BRP边界树转发。

具体流程如图2所示。

图2LR-ZRP中S的寻路流程

2.2中间节点的处理

中间节点可能是区域内部节点或广播树边界节点，对其处理过程可描述如下。

步骤1 中间节点根据接收到的路由请求所携带信息和自身位置缓存表，对比信息新旧程度，互相更新。其中包括S、D的位置信息。

步骤2中间节点判断是否为重复接收。若是，丢弃；若否，转步骤3。

步骤3中间节点对比自身和路由请求所携带的D位置信息。若是目的节点，沿先前累积路由回送路由应答；若否，转步骤4。

步骤4中间节点通过计算判定自己是否存在于确定的请求区域内部。如果不在，丢弃；如果在，转步骤5。

步骤5中间节点标记所经路由记录，继续转发。直至找到目的节点D。

步骤6S接收路由应答之后，确定路由已经成功建立，开始传输。至此，LR-ZRP寻路结束。

以上流程如图3所示。

图3　LR-ZRP中中间节点的寻路流程

3性能评估

使用NetworkSimulator(version2)进行仿真分析，具体参数见表1。节点随机运动生成场景。由于LR-ZRP加入了位置触发更新机制，需要设置检测周期:节点速度小于30m/s时，每2s检测一次; 其余设置为1s。

表1　仿真参数

3.1分组投递率

节点运动加快导致位移范围增大，网络中无效链路增多，分组投递率均随之减小。同等速度状况，LR-ZRP的分组投递率较之ZRP的分组投递率更好，如图4所示，这是因为：ZRP区域内是周期性路由更新，无法根据节点当前实时运动状况，针对性自适应修复和优化路由，链路失效导致分组投递率较低：LR-ZRP结合位置触发和周期性更新方式，借助位置缓存表信息，及时修正路由发现，能更加准确、有效地维护区域内外路由，分组投递率也相应较高。

图4　分组投递率

3.2控制开销

LR-ZRP协议引入了位置信息，控制开销包括位置控制开销和路由控制开销两部分。ZRP与LR-ZRP控制开销随速度的变化情况如图5所示。随着最大移动速度增加至大约35m/s，LR-ZRP控制开销开始小于ZRP控制开销，说明当节点移动稍快时，LR-ZRP控制开销增加幅度较小。仿真初始，节点运动较慢，相应位移变化范围也较小，相较于ZRP只有路由开销，LR-ZRP包函了位置更新开销和路由开销两部分，总的控制开销自然大于ZRP；但当节点运动速度逐渐增加时，节点位置变化开始有些剧烈，ZRP没有位置控制分组，但节点快速移动可能导致路由失效，需要重新发起路由，开销增大，而此时LR-ZRP优势渐显，根据频繁的节点位置更新，路由及时修复或优化，确定出来的路由请求区域也更加精确，相较于ZRP盲目全向泛洪，LR-ZRP控制开销更小。

图5　控制开销

3.3平均端到端时延

ZRP与LR-ZRP的平均端到端时延均呈增长趋势。同等速度状况，LR-ZRP平均端到端时延少于ZRP，如图6所示，这是因为：ZRP协议的节点运动状态变化会造成原路由失效，只有目的节点所在区域内的节点接收到路由请求之后才可回送路由应答，时延较大；LR-ZRP引入位置缓存表，只需当前节点位置缓存表或路由缓存表中存在目的节点位置信息或路由信息，即可进行应答，减小了路由查询时间。LR-ZRP利用节点实时性位置信息，及时调整路由，网络自适应能力较之ZRP更优，所以平均端到端时延少于ZRP。

图6　平均端到端时延

4结语

VANET旨在保障道路交通安全、提高出行效率和防范治理拥堵，更好地应对车辆数量激增带来的各类挑战。通过分析VANET常见路由协议，结合当前实际问题，对ZRP进行改进，得出一种基于位置信息和定向泛洪的新型区域路由协议(LR-ZRP)。仿真分析显示，LR-ZRP在控制开销和分组投递率方面均优于ZRP。另在节点较高速度下，LR-ZRP控制开销增长幅度趋于平缓。

参考文献

[1]许富龙,刘志建.车载自组织网络路由协议研究进展与比较[J/OL].电讯技术,2013,53(10):1393-1400[2015-12-24].http://mall.cnki.net/magazine/article/DATE201310027.htm.DOI:10.3969/j.issn.1001-893x.2013.10.027.

[2]张瑞锋.车载自组网通信技术研究综述[J/OL].汽车工程学报,2014,4(2):79-85[2015-12-24].http://mall.cnki.net/magazine/article/QCYK201402001.htm.DOI:10.3969/j.issn.2095-1469.2014.02.01.

[3]姬兴民,李金龙,卢光跃,等.基于AODV的平面多径路由协议[J/OL].西安邮电大学学报,2015,20(2):21-25[2015-12-24].http://mall.cnki.net/magazine/article/XAYD201502005.htm.DOI:10.13682/j.issn.2095-6533.2015.02.005.

[4]BLUMJJ,ESKANDARIANA,HOFFMANLJ.Challengesofintervehicleadhocnetwork[J/OL].IEEETransactionsonIntelligentTransportationSystems,2004,5(4):347-351[2015-12-24].http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1364012.DOI:10.1109/TITS.2004.838218.

[5]田红燕,徐成,刘彦.一种基于方向优先的车载Adhoc路由策略[J/OL].计算机应用研究,2010,27(04):1416-1418[2015-12-24].http://mall.cnki.net/magazine/article/JSYJ201004057.htm.DOI:10.3969/j.issn.1001-3695.2010.04.058.

[6]GUPTAP,KUMARPR.Thecapacityofwirelessnetworks[J/OL].IEEETransactionsonInformationTheory, 2000,46(2):388-404[2015-12-24].http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=825799.DOI:10.1109/18.825799.

[7]TZENGSF,HORNGSJ,LITR,etal.Enhancingsecurityandprivacyforidentity-basedbatchverificationschemeinVANET[J/OL].IEEETransactionsonVehicularTechnology.[2015-12-24].http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7047920.DOI:10.1109/TVT.2015.2406877.

[8]马明辉,武晓庆,武穆清.ZRP路由协议的NDP优化与仿真分析[J/OL].无线电工程,2007,37(7):4-6[2015-12-24].http://mall.cnki.net/magazine/article/WXDG200707001.htm.DOI:10.3969/j.issn.1003-3106.2007.07.002.

[9]李琳,武穆清.ZRP区域路由协议分析[J/OL].数字通信世界,2007(11):52-55[2015-12-24].http://mall.cnki.net/magazine/article/SZTJ200711028.htm.DOI:10.3969/j.issn.1672-7274.2007.11.021.

[10] 邱朋义,王洪玉.基于位置信息的AODV路由协议[D].大连:大连理工大学,2008:23-28.

[11] 施荣华,罗棋峰.一种MANET中基于位置信息的ZRP路由协议[J/OL].湖南大学学报(自然科学版),2009,36(8):38-42[2015-12-24].http://mall.cnki.net/magazine/article/HNDX200908007.htm.

[12] 张棋飞,刘威,杨宗凯.基于位置信息的自适应AdHoc路由协议[J/OL].计算机科学,2007,34(5):20-24[2015-12-24].http://mall.cnki.net/magazine/article/JSJA200705005.htm.DOI:10.3969/j.issn.1002-137X.2007.05.005.

[责任编辑:瑞金]

Location-basedandrestricted-floodingzoneroutingprotocolforvehicleadhocnetwork

SUNYouwei,SUNXiaotian,WANGNan

(SchoolofCommunicationandInformationEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China)

Abstract:In order to improve the efficiency of data transmission and routing discovery in the process of the vehicle ad hoc network communication, the zone routing protocol(ZRP) is improved by adding coordinates, speed, and time fields in data packets. After receiving the packet, the node records or updates its own position cache table according to the position information. In the route discovery phase, when the position shift is bigger than the radius of the location update, then the node update the route, which can reduce the times of route discovery. According to the location cache table and routing table, the non-destination node replies directly to the route requests, which can reduce the route discovery time. In the data transmission phase, the node can transmit data by restricting flooding range to reduce the control overhead. Simulation experiments are carried out by building the car networking scene on the 60 nodes at 5～50 m/s speed. Results show that the improved protocol can reduce the delay about 6%～13%, and increase the packet delivery rate about 6%～20%. Besides, when the node speed is greater than 35 m/s, the control overhead can be reduced by 7% to 14%.

Keywords:vehicle ad hoc network, zone routing protocol, location information, position cache table, restricted flooding

doi:10.13682/j.issn.2095-6533.2016.02.009

收稿日期：2015-11-28

作者简介：孙友伟(1956-)，男，教授，从事下一代通信网研究。E-mail:syw@xupt.edu.cn 孙小田(1990-)，女，硕士研究生，研究方向为物联网技术及应用。E-mail:627877256@qq.com

中图分类号：TN913.6

文献标识码：A

文章编号：2095-6533(2016)02-0046-06