基于位置信息的车联网路由恢复方法

杨永军

（安徽四创电子股份有限公司，安徽 合肥 230088）

有关ad hoc网络的研究大多基于全向天线，在选择路由时，经常出现冗余信息量过大，延迟时间过长等特点［1］。随着无线自组网对于方向性天线应用需求的增长，设计适用于方向性天线的路由协议和路由恢复方法非常重要。引入方向性天线的ad hoc网络不仅能提高无线资源的空间复用性，而且通信范围可得到有效的扩展［2－3］。

车 联 网 （Vehicular Ad Hoc Networks，VANETs）作为ad hoc的一项主流技术，融入了汽车、通信、IT等领域的前沿技术，成为学术界研究的热点。VANETs中节点具有强大的计算能力和存储能力，几乎无能量限制，并且节点移动速度快，移动轨迹可预测［4－5］。文献［6］研究表明，传统无线自组网路由协议用于VANETs时会因拓扑结构变化频繁导致通信链路容易断、链路生命期短。文献［7－9］研究表明，VANETs节点的高速运动导致无线自组网按需平面距离矢量路由协议（Ad hoc On－demand Distance Vector（AODV）Routing）［10］和 动 态 路 由 协 议 （Dynamic Source Routing，DSR）［11］不能及时收敛，并且产生大量不可靠路由。文献［12］提出了一种基于选播策略的路由恢复方法，把断后路径上节点分成源节点组和目的节点组，寻求原节点组到目的节点组的最短路径。文献［13］利用网络中路径的交叉节点，寻找能代替故障链路的链路，路由开销较大且适用条件苛刻。当前活跃的下一跳发生方向性链路中断后，文献［14］根据链路断开处上游节点与目的节点的距离采用基于位置信息的贪婪转发方法进行修复。

本文提出了一种基于位置信息的车联网路由恢复方法 （route recovery method based on the location information，RRBLI），主要用于高速公路无基站情况下车与车之间的通信。该方法利用全球定位系统（Global Positioning System，GPS）定位装置提供的行车参数信息，对路由修复过程中目标节点的移动轨迹进行了预测，并对目标节点位置进行修正。

1 算法介绍

RRBLI算法约定待研究的VANETs节点均配置了完全相同的自适应阵列天线系统和GPS定位装置。RRBLI中发起路由修复的节点为“发起节点”，链路断开前与“发起节点”相连接且此刻已失去连接的节点为“目标节点”。RRBLI算法在活跃路径刚刚建立时加入了路由稳定性预测方法，最大限度避开行驶方向相反的车辆以减少路由断开的概率。在方向性天线形成波束时，控制其传输距离，假设由GPS得到发送节点和接受节点之间的距离为S，自由空间模型中发射功率Ps与接受功率Pt之间关系为：

其中，Gt、Gs分别为发射天线和接受天线的增益；λ为波长。

1.1 路径信息

设置方向性天线发射功率为最大发射功率以获得最远传输距离、减小传输跳数。约定网络中节点接收数据采用全向模式。活跃路径上的每个节点都要维护一个路径信息表，包括的字段如图1所示。

图1 路径信息表

（1）路径ID。记录当前节点所属路径的ID，用于解决1个节点同时属于多条活跃路径的情况。

（2）上游节点ID。记录活跃路径中与当前节点相连的靠近源节点的节点ID。

（3）下游节点ID。记录活跃路径中与当前节点相连的靠近目的节点的节点ID。

（4）更新时刻。记录路径信息表中当前表项的更新时间，以获得节点的最新信息，为了保证信息的实时性，要求网络中节点时间与GPS同步，因为GPS能满足实时性要求。

（5）节点位置。记录表项更新时刻、车辆的地理位置。

（6）移动速度。记录表项更新时刻、车辆的移动速度。

（7）移动方向。记录表项更新时刻、车辆的移动方向。

1.2 路由分组

RRBLI方法中定义RREQ（路由请求）和RREP（路由回应）2种分组。

1.2.1 路由修复请求分组

RREQ为路由修复请求分组，当目前活跃路径中检测到有断开链路时，由链路断开处靠近活跃路径前端（行车方向）的节点初始化RREQ分组。RREQ分组定义如图2所示。

图2 路由修复请求分组

（1）数据包类型。即数据包种类，不同类型的数据包接收节点对它做不同的处理。

分组中“当前节点参数”字段由RREQ所达到节点更新并传送给活跃路径上的下一个节点。分组中“目标节点参数”由RREQ所到节点根据校正后的位置信息更新，然后发送给下一个中间节点，下一个中间节点就可以根据校正后的链路断开处节点信息进行更精确的校正。

（3）中间节点数。RREQ分组每被中间节点转发1次，该字段值加1。

1.2.2 路由修复应答分组

RREP为路由修复应答分组，当RREQ分组找到与目标节点相连的活跃路径上的节点时，由该节点初始化并回复一个RREP分组，表示路径修复成功。RREP分组定义如图3所示。

图3 路由修复应答分组

（1）字段“节点ID1”为初始化RREP分组的节点的ID，“节点ID2”为初始化RREQ节点的ID，RREP分组中字段“路径ID”、“节点ID1”和“节点ID2”可唯一地标识一个RREP分组。生存时间与RREQ的中间节点数对应。

（2）RREP分组中字段“节点位置”、“移动速度”和“移动方向”由初始化RREP分组的节点赋初值，并在RREP发送过程中由中间节点取出对应字段值存入路径信息表，并用节点当前行车参数对其更新，这样在路由修复过程中就可以由RRPQ和RREP完成对各中间节点的路径信息表进行更新。

1.3 修复过程

当VANETs中检测到有断开链路时，需经过几个修复过程。

（1）链路断开处靠近活跃路径前端节点初始化一个RREQ分组，由发起节点沿其与目标节点连线所形成直线（以下称参考线）的方向以方向性传输模式发送，如图4所示。

将平均含水率为32.53%的物料按照试验设置的薄层厚度平铺在托盘上；当DHG-9240A型热风干燥试验装置中的温度和风速达到恒定时，将托盘放置于干燥室中；在干燥过程中定时测定物料的含水率，并观察其变化情况。参照国家小麦籽粒入库储藏标准，将干燥最终干基含水率确定在11.5%～12.5%的范围内。每个处理重复进行3次, 取其平均值。

图4 最大前程

假如节点S和D之间链路断开，以车辆行驶方向为参考，节点S在通信路径前端，所以S为路由恢复的“发起节点”。节点S在发送RREQ分组时，沿D所在方向即沿直线SD方向形成波束。在形成RREQ分组时，若链路断开处2节点移动方向有1个与活跃路径前端不同，则取其在活跃路径中相邻节点（上游或下游节点）进行路由的恢复。

（2）判断收到RREQ分组的节点中是否含有与目的节点相连的节点，若存在与目的节点相连的节点，就由该节点沿RREQ分组发来方向返回1个RREP分组并更新自己的路径信息表，路由修复完成；否则选择在参考线投影较长的节点作为中间节点，并由中间节点更新自身的路径信息表。

在方向性天线波束范围内有2个节点A和B，选择在发起节点（S）和目标节点（D）连线上投影较长，且移动方向与发起节点相同的节点作为中间节点，此处为节点A。投影长度可根据节点位置信息计算得到。

（3）中间节点对链路断开处下游节点的位置进行修正，并把修正后的位置信息和中间节点自己的行车参数信息更新到RREQ分组中发送给下一个中间节点。

不同于其他移动自组网，VANETs中节点移动速度较快，从网络中检测到有断开链路到路由恢复完成有很大的延迟，其中包括报文传输时延与传播时延。由图4可以看出，参考线方向会直接影响方向性天线的波束方向，从而直接影响路径恢复成功率。而目标节点又始终以较高的速度运行，所以对目标节点的位置校正显得十分重要。

恢复方法中由RREQ分组所得到的中间节点自行对目标节点的位置进行预测。RRBLI要求网络中节点记录RREQ分组到达自身的时刻，分组每到一个中间节点，该字段值被当前中间节点更新1次。

中间节点预测目标节点位置的算法如下：

假如在链路断开的t时刻，发起节点与目标节点的速度分别为vd（t）和vs（t），两节点距离为d（t），为避免两车相撞，目标车辆的安全速度应满足：

其中，τ为司机反应时间；为两车平均速度；b为与相关的减速函数。

目标节点的理想速度vr应满足：

其中，vmax为路段的最大限速；a为最大加速度。

因实际情况下司机的驾驶习惯以及外界的干扰，引入误差系数ω，则目标车辆的实际速度还应满足：

经计算，最终可得后车的下个时刻位置为：

第1个中间节点根据收到的RREQ中发起节点和目标节点的行车参数信息计算目标节点的位置，其中Δt为分组由发起节点到第1个中间节点的时间差。预测完成后更新RREQ分组中“目标节点参数字段”，然后第1个中间节点充当发起节点以同样方式寻找第2个中间节点，直到修复完成或失败。

（4）中间节点沿修正后的目标节点所在方向形成波束，并以自己和修正后的目标节点的连线为参考线来选择下一个中间节点。

在中间节点完成了目标节点的位置校正后，将更新RREQ分组中的位置信息作为校正后的位置信息。在中间节点转发RREQ分组时，波束方向也会有新的调整，如图5所示。

图5 车辆位置修正

图5中节点D1位置节点A为对节点D修正后的位置，中间节点A转发RREQ分组时，将沿自己位置和修正后的目标节点位置之间的连线所成直线的方向形成波束，图中波束方向沿直线AD1方向，相邻节点投影也变成在直线AD1上的投影。

当RREQ分组传送到与目的节点相连的路径上的任何一个节点时，当前节点将回复一个RREP分组表示路由修复完成。

（5）若路由修复仍未成功则跳转到步骤（2）。若在路由修复定时器规定的时间内初始化路由修复请求分组的节点未收到路由修复应答分组，则认为路由修复失败，在路由修复期间，上游节点可多次尝试修复路由，以增加路由修复成功率。

2 系统仿真

为了评估算法的性能，使用NS2（Nework Simulator，version 2）进行模拟实验，在NS2环境下建立双向四车道的高速公路模型，在长度为5km的公路上均匀分布400辆车，为了使仿真接近现实模型，设置车辆的平均速度为v，车辆速度的随机变化幅度为30km／h。仿真中路由协议采用基于定向天线的位置信息辅助按需距离矢量路由协议［14］（directional antennas and location－aided ad hoc on－demand distance vector routing，DLAODV），并在其路由修复部分做了修改，以对比位置信息修正的贪婪转发策略（locaton correction－based greedy forwarding strategy，LCGF）与本文提出的RRBLI路由修复方法的性能特征。对应的介质访问控制（media access control，MAC）层采用D－载波侦听多路访问／冲突避免（carrier sense multiple access with collision avoidance，CSMA／CA）协议［15］。取波束宽度为60°，信道速率为2Mb／s；仿真时间为500s；方向性天线全向通信半径为500m；数据包大小为512Byte；数据包发送频率为10包／s；修复超时定时器为2s；业务源数为20。为了更准确地得到修复算法的性能参数，仿真中只研究传输路径断裂情况下端到端的延迟、路由修复开销（协议发送的控制分组）、路由修复成功率3个方面，结果如图6～图8所示。

图6 端到端延迟

端到端的延迟是指目的节点收到数据分组的时间与源节点产生数据分组的时间之差；路由修复开销是指为了修复断开的链路而发送的控制分组数量；路由修复成功率是指路由修复成功的次数与尝试路由修复的总次数的比值。

图7 路由修复成功率

由图7可以看出，加入了对路由断开处下游节点的位置信息修正的RRBLI，在方向性天线波束宽度不变的情况下，路由修复成功率有了明显的提高，因为每次发送的RREQ分组方向更加准确。与LCGF路由恢复方法相比，RRBLI在路由恢复开销和路由恢复效率上也有明显的改善。在行车速度较低的情况下，2种恢复方法的路由恢复开销都基本稳定，当行车速度较快时，LCGF会因路由的频繁断开或方向性天线形成波束时的方向误差而导致开销剧增，而RRBLI仍然较稳定。

图8 路由修复开销

3 结束语

VANETs作为移动自组网的一个大分支，已成为当前学术界的研究热点。本文对车联网的路由恢复方法进行了研究，并提出了基于位置信息的车联网路由恢复方法。在方向性天线和GPS定位装置的辅助下，减少了路由恢复过程中因控制分组的传送耗时对路由恢复成功率造成的影响，为解决高速运行状态下路由恢复方法的设计提供了新的入口。

［1］ 任品毅，冯 佳，王熠晨.Ad Hoc网络中具有远距离通信能力的方向性 MAC协议［J］.中国科学：信息科学，2011，41（10）：1238－1250.

［2］ Abdullah A A，Lin C，Gebali F.DSDMAC：dual sensing directional MAC protocol for ad hoc networks with directional antennas［J］.IEEE Vehicular Technology Society，2012，61（3）：1266－1275.

［3］ 闫鲁生，王 涛，李 威.一种基于多天线的动态TDMA协议仿真研究［J］.通信技术，2011，44（12）：107－110.

［4］ Lee K C，Lee U，Geral M.Geo－pportunistic routing for vehicular networks ［J］.IEEE Communications Magazine，2010，48（5）：164－171.

［5］ 张建军，杨永军，刘征宇，等.基于行车参数信息的车联网网络分割解决方法［J］.电子测量与仪器学报，2013，27（9）：831－836.

［6］ Blum J，Eskandarian A，Hoffman L.performance characteristics of inter－vehicle ad hoc networks［C］／／The IEEE 6th International Conference on Interlligent Transactions Systems，2003：114－119.

［7］ Wang S Y，Lin C C，Hwang Y W，et al.A practical routing protocol for vehicle－formed mobile ad hoc networks on the roads［C］／／Proceedings of the 8th IEEE International Conference on Intelligent Transportation Systems，2005：161－165.

［8］ Hao Y，Cheng Y，Zhou C，et al.A distributed key management framework with cooperative message authentication in VANETs［J］.IEEE Journal on Selected Areas in Communication，2011，29（3）：616－629.

［9］ Santos R A，Edwards A，Edwards R M，et al.Performance evaluation of routing protocols in vehicular ad hoc networks［J］.The International Journal of Ad Hoc and Ubiquitous Computing，2005，1（1）：80－91.

［10］ Chandm P，Soni K.Performance comparison of AODV and DSR on－demand routing protocols for mobile Ad－Hoc networks［J］.International Journal of Computer Applications，2012，49（18）：1－5.

［11］ Khabazian M，Aissa S，Mustafa－Ali M.Performance modeling of Message dissemination in vehicular Ad Hoc networks with priority［J］.IEEE Journal on Selected Areas in Communications，2011，29（1）：61－67.

［12］ 王建新，邓曙光，陈松乔，等.移动自组网络中的一种基于选播策略的路由恢复方法［J］.通信学报，2003，24（10）：172－176.

［13］ Wu C H，Hu S C，Hsu C S.Design of fast restoration multi－path routing in VANETs［C］／／IEEE Conference，2010：73－78.

［14］ 于 全，吴克军.采用方向性天线的ad hoc网络路由协议研究［J］.通信学报，2008，29（8）：69－76.

［15］ 吴克军.采用方向性天线的ad hoc网络媒体接入控制和路由协议研究［D］.南京：解放军理工大学，2007.