基于实时道路信息感知的VANET路由算法

陈潘航，周宏伟

(1.杭州电子科技大学 计算机学院，浙江 杭州 310018；2.泰瑞机器股份有限公司，浙江 杭州 310018)

0 引 言

车辆网是实验智慧城市的重要研究领域，基于IEEE 802.11p的VANET[1,2]是车联网的主要研究方向。VANET是由车载单元OBU(on board unit)、路边单元RSU(road side unit)组成的自组织网络，并支持在缺少基础设施环境下建立通信网络是VANET的特点。然而，由于车辆移动速度快、时空分布不均[3,4]，造成路由拓扑变化快、路由路役失效限制了VANET网络的优势[5]。

针对VANET网络的客观条件，研究者设计了多种VANET专用路由协议[5-7]，其中地理信息路由GRP(geographic routing protocols)由于无需进行源结点和目标结点间的路由建立与维护，较传统的AODV等路径路由有较大的优势。进一步的发展中，研究者针对GRP路由断裂后路由恢复操作开销较大的问题，提出了分段感知路由协议[8]，协议将道路按交叉路口分割为道路段RS(road segment)，通过信息搜集报文ICP(information collector packet)搜集实时的RS网络状态作为路由规划的依据。然而，由于缺少ICP报文生成频率的调节机制，该类协议的维护开销较大。

针对这一这问题，本文设计了一种地理路由算法，记为RSAR。该算法设计了有效期机制VPM(verity period mechanism)控制每个OBU的路由信息更新频率以减少路由维护的开销，量化的RS网络状态则用于路由规划。仿真结果表明了RSAR的有效性。

1 系统建模

1.1 系统建模

考虑到支持IEEE 802.11p的基础设施的铺设成本及现有规模等问题，RSAR研究基于无RSU的车辆自组织网络，如图1所示。RASR对研究的车辆进行了若干合理假设：

(1)配备IEEE 802.11p的通信设备；

(2)配备GPS或北斗导航系统，可以获取自身的经纬度并计算出当前的矢量速度；

(3)配备运算能力，可以维护邻居表、RS信息表等数据。

图1 RSAR的研究环境

图1中源结点即当前ICP报文的发起者，由于802.11p的通信能力有限，故采用多个中继结点进行ICP的转发。

1.2 描述约定

本文中，对于车辆结点n有统一的参数定义：①坐标 (xn,yn)； ②行驶速度vn； ③行驶方向θn。

2 路由算法

2.1 路由有效期计算

(1)

LTD是结点间通过无线信号进行直接通信的最长有效时间估值，对于任意车辆s和n，据文献[9]，LTD由式(2)计算给出。特别的，当s和n的矢量速度一致时，分母为0，即链路寿命为无限大，在实际编码过程中须进行特殊判断

(2)

SD是路段上运行的车辆数量的量化指标，对于VANET网络，结点密度越大，就存在更多的备用链路以维持网络的连接[10]。SD的计算由式(3)给出，其中Nv为当前ICP发送方向同向的车辆数量，Nov为与当前ICP传输方向反向的车辆数量

SD=Nv+Nov

(3)

SFRC是特定路段内的车流量在单位时间内的分差，如式(4)所示，Vt是计算路段t时刻车辆的平均速度

SFRC=SDt*Vt-SDt-1*Vt-1

(4)

2.2 路由质量计算

RSAR将特定RS的当前网络状态量化表示为Ss， 以作为路由规划的依据。RS的网络状态则量化表示为段密度Sd、 段连接度Sc和段负载Sl。 为适应不同交通情况及方便后期调节，在本节公式中引入加权参数α、β、γ，以方便根据仿真或实际测试结果进行优化。

段密度表示路段车辆的路由密度，表现为段中移动车辆的路由可用数量与ICP包中继开销的比值，具体公式见式(5)，其中Nh为参与ICP转发的车辆结点数，Cm为常数度量，数值设置为12。由式(1)可知，同向车辆的LTD更高更有有利于维持路由，故算法中设置α=0.8，β=0.2，Sd的取值区间为[0,1]，若计算结果Sd大于1则设置Sd为1

(5)

段连接度是段中路由稳定的量化指标，其表示路中路由无故障的运行可能性。段连接度受设备故障概率、路由断裂率等因素，通常无法直接获取，故本文中段连接度的计算见式(6)，其为有效期和ICP每跳平均网络延迟的比值，其中Ttime是CP包的传输时间，通过计算ICP生成时间与接收时间差获得。SC的取值区间为[0,1]，SC值越高，网络连通程序越好

(6)

段负载表示段内网络负载的量化指标，计算方法见式(7)，其中ALv和ALov为通过CP包广播中获取的接收值，Cll为常数值表示网络缓冲区队列中容量上限，在IEEE 802.11p设置为50。同段密度的计算参数用值，α1=0.8，β1=0.2，Sl的取值区为[0,1]，段的数值越高其网络负载越大

(7)

综上，Ss的最终计算见式(8)，不失一般性的设置α2=β2=λ=0.33

Ss=(α2×Sd)+(β2×Sc)-(λ×Sl)

(8)

2.3 路由协议

路数包的路由决策较为简单，与传统分段感知路由协议[8]的策略相似，在分支路口通过式(8)获取Ss进行选择合适的RS进行路由即可。本章节主要阐述路由信息的维护流程，即ICP报文的生成、转发及广播。

2.3.1 ICP报文设计

ICP的报文是RSAR进行数据搜集的基础，综合2.1节和2.2节的计算需求，设计了图2所示ICP报文。在计算所需要的基础上增加了Vid和RSid字段以分别标识报文的源结点和当前RS， (Vid，RSid) 共同组成了对车辆Vid的路由路径。VStime为ICP的生成时间戳，另外默认接收方可以直接获得发送方的ID。

图2 ICP的报文字段

2.3.2 ICP传输协议

ICP报文的段内组播流程如图3所示，源结点Vid生成新的ICP报文，利用改进的贪婪算法计算出当前最有效的Vnext， 并将ICP交付于适当的邻居结点Vnext，Vnext利用式(1)计算自有效值V′p并与接收到的ICP中Vp进行比较，取最小值并进行自身邻居表的更新操作，再将ICP中的Nh加1后传递给一个邻居直到RS的末端结点。

图3 ICP的段内组播流

当ICP到RS的末端，即邻居的交叉路口后，ICP的段内广播结束，最后的结点Vend将按图4进行处理。当Vend对Vid无记录，即Vid第一次到达Vend时，若ICP的漫游时间在Vp有效期内，即当前时间T与所接收的ICP的时间戳满足T-VStimeVp， 即上个ICP所对应的路由路径失效则重新广播当前路由信息，若否，即ICP包过度重传，不进行广播处理。当进行叉口广播后，Vend都向源结点发送ICP-ACK确认报文。

图4 ICP的路口广播流程

3 仿真实验

3.1 仿真环境及评估方法

仿真环境利用网络仿真器OMNET++[11]和道路仿真器SUMO[11]联合完成，参照相关研究[12]设置了一个边长 2 km 的正方形网格模型，车辆的移动模型为经典的随机旅游模型，具体参数设置见表1。作为对比，使用了iCAR[13]、TFOR[14]的公开PBR协议进行参照，部分的参数设置如下。针对车辆的移动速度、密度存在较大的时间差距，故使用低密度LOW(6veh/km/lane)和高密度HIGH(50veh/km/lane)两种模型分别测试路由算法在两种情况下的表现。

评估主要涉及两方面，第一是路由维护开销，第二是数据包传输质量。路由维护开销量化表示为仿真时间内的ICP包生成数量，ICP的数量越少则路由的维护开销越低，对数据包的影响越小。

表1 仿真参数设置

数据包传输质量的传输质量由数据包交付率和数据延迟量化表示，考虑到网络负载对网络传输的影响，采用恒定比特率(CBR)用户数据报协议应用进行性能测试，该协议允许通过传输固定大小的分组以固定速率创建流量模式。实验中通过控制OBU上CBR并发连接的数量，测试在负载下跟帖算法的效果。

3.2 分 析

图5给出了3种路由协议的ICP生成数，其中纵轴用“算法名-密度类型”进行分类，如RSAR-LOW表示RSAR算法在低密度情况下的ICP生成数量。

图5 ICP的生成数量统计

具体到数据对比，由于引入了VPM机制RSAR在高密度环境下较iCAR降低了70.5%的ICP报文生成量，但在低密度环境下只降低了47.3%，较TFOR亦有明显的优秀。对于RSAR在低密度环境下表现劣于高密度环境，经过分析认为低密度环境下，网络路由变化后缺少备用路线导致路由故障的概念更高即Vp数值较低，必需多次使用ICP报文发送以维护网络质量。

图6和图7给出了3种算法在进行数据传输时的数据包交付率，可以看出RSAR在不同密度环境下有较好的表现。具体到数值，可以发现RSAR在CBR并发数小于8以内时有较好的绝对表现，数据包交付率始终维持在80%以上，较其它两种路由提高了近5个百分点；在CBR并发数大于8后有较好的相对表现。RSAR综合考虑了网络负载，在数据传输量较多时可以选用负载较低的路经，除在CBR大量并发至整体网络负载过高的情况下，其表现十分出色。

图6 低密度环境下的数据包交付率

图7 高密度环境下的数据包交付率

图8和图9给出了3种路由算法在进行数据传输时的平均分组延迟可以发现，在低密度环境下SRAR的表现是3种算法中最差的，其平均延迟比其在低数据通信时比其余两种高11.3%和12.5%，而在高数据通信服务下，则皆大于50%；在密度环境下，RSAR的表现是三者中最好，尤其在高并发通信时，降低了50%以上的延迟。进一步研究后认为，由于RSAR高度依赖RS的通信质量，而没有量化引入RS通信距离对延迟的影响，导致在低密度环境下以保证数据包交付率为代价增大了延迟，而在高密度结点情况下，由于充分使用了整体VANET网络的通信能力，相对降低了特定RS上的网络负载，间接保证了低延迟通信。

图8 低密度环境下的数据包延迟

图9 高密度环境下的数据包延迟

3.3 实验小结

结合数据包交付率、网络时延，认为RSAR可以较低的网络维护开销保证较高的数据包交付率，并在高车辆密度下有效降低了数据延迟，可以适用于大城市的VANET网络路由服务。但RSAR在低车辆密度环境下数据延迟较大，不适用于紧急安全消息的应用，故RSAR仍存在较大的改进空间。

4 结束语

本文介绍了RSAR路由算法的系统建模、算法设计及仿真结果，这是一种主要针对城市交通环境下的分段感知路由算法。RSAR综合考虑了影响道路网络质量的因素，引入段密度、段连接度及段负载计算段网络状态，避开低质量路由路线；设计有效期机制有效控制了路由的维护代价。仿真结果表明，RSAR在网络开销、数据包交付率方面明显优于现有算法，同时在高车辆密度下，RSAR亦能有效降低网络延迟。不足之处主要在于，RSAR的延迟控制在低密度环境下表现欠佳，需要进一步完善。