基于局部梯度场的VANET路由研究

马 逍

(同济大学 电子与信息工程学院，上海 201804)

0 引言

近年来为保证车辆安全行驶，在移动自组织网络的基础上出现了车辆自组织网络。VANET中现有的安全消息传播机制大都是在移动自组织网络的基础上演化而来的。但自组织网络[1]没有考虑网络拓扑的动态高度变化，因此现有的自组织网络路由机制无法很好地适应VANET安全消息传播的要求。

现有的路由协议包括地理源路由协议、基于GPSR的广播协议、限制洪泛区域的路由协议[2]和空间感知路由协议[3]等，但这些路由协议均依赖于准确的位置信息，一方面增加了路由成本，另一方面，路由性能也受限于位置信息准确性。

针对城市的应用场景，文献[4]提出了一种全局状态路由协议（GSR，Geographic Source Routing），该协议具有较好的包传送率、低带宽利用率，但没有考虑在2个连续的交叉点之间车辆的连通性。基于概率的路由协议（PBR，Probability Based Routing）[5]能够在密集的自组织网络中提高包传送率，但是在具有拓扑空洞的网络中，其路由性能急剧下降。

目前研究中出现较多的是GPSR协议。GPSR协议在高速公路上有良好的性能，但是在城市交通场下，贪婪转发经常受到道路拓扑的限制，信道质量也受到道路两旁的建筑物等障碍物的影响，同时高动态网络拓扑也会引起很多问题，其中典型的就是婴儿步问题。针对VANET中的网络割裂，研究人员通常借助于机会路由的方法来转发安全消息。典型的机会路由协议都是采用单一指标作为选取最佳下一跳候选节点的评估参量，如以硬件地址作为评估参量的极端机会路由（ExOR，Extremely Opportunistic Routing）[6]。

1 基于LGFR的VANET安全消息传播机制

1.1 梯度的概念

在向量微积分中，标量场的梯度是一个向量场。标量场中某一点上的梯度指向标量场增长最快的方向，梯度的数值是变化最快的变化率。梯度场构建后，数据沿着梯度场进行传播。当遇到故障节点或是链路断开时，数据将自动通过新的中继点转发。这种不依赖于某一特定邻居节点为下一跳的传输方式，隐性地维持了所有可用路径，因而显示出健壮性，从而有效的改善了网络能耗，延长了网络生命周期，即使在网络拓扑不断变化的情况下仍然保有较高的包投递率。

基于上述特点，引入局部梯度场的概念，通过多维度参量计算源节点周围每个节点的梯度值，从而建立起源节点的局部梯度场，其中梯度值最大的节点即为下一跳的最佳转发节点。安全消息就沿着梯度场转发至目标节点。

1.2 基于LGFR的VANET安全消息传播机制

为建立VANET中局部梯度场，在计算梯度值时综合了多维度参量。梯度值越大意味着向该方向继续搜索到达目的节点的几率越大，以同样的方式，在整个网络中建立一个临时的局部梯度场，安全消息沿梯度最大的方向传播，这种方案称为基于LGFR的VANET安全消息的多跳路由机制。

假设VANET中所有的节点可以通过全球定位系统和数字地图获得车辆坐标、运动速度和运动方向等信息。每个车辆知道自身的地理位置信息，并通过电子地图可获得自身所处城市区域内的相关道路拓扑情况; 同时每个车辆可辅助计算车辆周围邻居节点的密度；车辆本身还应具备记录自身数据包处理负载情况。

由于源节点只需向同一车道方向的节点发送安全消息，源节点只收集与自己同方向的车辆的位置信息，如图1所示，节点A收到的周围邻居节点B、C的广播包后，从广播包中提取邻居节点B、C的移动方向信息与路段ID。如果邻居节点的路段ID与自身的路段ID相同，则建立下一跳转发邻居关系，另一方面，节点B、C移动方向与节点A自身的移动方向相比较，在图1的情景下，得到结果为节点B与节点A反方向行驶，且节点C与节点A移动方向相同，故A节点只接收C节点发送的位置信息，而忽略节点B发送的位置消息。

图1 源节点定向接收位置消息示意

1.2.1 VANET中梯度场的构建

1.2.1.1 VANET中梯度场考虑的因素

（1）邻居节点与目标节点的距离

在转发过程中尽可能地将数据包传输至距离目标节点尽可能近的节点，以减少转发次数。假设 di表示目标节点和邻居节点的距离，则 di可由式（1）计算得到：

将当前节点CN与目标节点DN 的距离cd与id进行比较，当id小于cd的时候，即邻居节点iN比当前节点CN离目标节点DN 更近时才进行数据转发。

（2）邻居节点当前数据处理负载状况

假设iT为节点iN转发数据包的处理时延，jTr是数据包j到达节点iN的时刻，jTs是节点iN将数据包j再次发送出去的时刻。则iT可由以下公式计算得到：

（3）邻居节点移动速度以及移动方向

当一个节点高速向目标节点移动时，该节点将数据包成功地转发到目标节点的可能性最大。如图2所示，设定节点 Ni在t1时刻的位置为，在 t2时刻它移动到了位置。拥有数据包的节点 NC的位置是，目标节点 Nd的位置为。在该情况下，邻居节点 Ni的移动速度，数据包转发方向与节点移动方向之间的切角由式（3）和式（4）给出。

（4）邻居节点周围节点密度

在VANET中，下一跳转发节点iN自身周围的邻居节点密度越高，则iN转发数据包成功的概率越大。在实际转发过程中，节点iN通过Beacon数据包周期性的广播的形式采集周围节点密度iρ，并将iρ通告至准备向其转发数据包的节点。当iN的邻居节点密度大于邻居节点密度的阈值sρ时，iN才有可能成为下一跳转发节点。

图 2 节点移动速度与移动方向评估场景

1.2.1.2 梯度值的计算

梯度值就是在单独计算所有的评估尺度参量后，通过联合分析评估所有的尺度参量权值计算得出的，其中1C、2C、3C、4C、5C为加权系数，如式（5）所示：

满足所有评估参量的节点都会根据以上公式计算得到自身的梯度值(Ni)。通过对梯度值的比较，梯度值最大的 Ni即被选择为最佳转发节点。由于梯度是个矢量，梯度值是由2.5式算出的标量值，而梯度的方向为从当前节点指向梯度值最大节点的方向。

1.2.2 LGFR协议

当前节点根据一跳内的节点的梯度值进行转发，将数据包转发至最佳转发节点，并且通告周围邻居节点最佳转发节点的控制信息。当最佳转发节点成功接受数据包，完成校验后，将成功接受数据包的控制信息，通告至本次转发过程中的其他节点。如果在其他转发候选节点在数据包过期前未收到该数据包已被成功接受的控制信息，系统会依次选择在优先级队列存储起来的其他候选节点重复上述过程。如果所有节点都已完成这次转发，但仍没有成功收到数据包的通告，则判定此次转发过程失败，开始新一周期的转发流程。接收到转发包的节点重复上一节点的过程，选取自己的最佳下一跳转发节点，直到传播到第五跳节点停止继续向前转发，这是因为安全消息的特殊性，不需要一直向远方车辆转发，第五跳节点即为目的节点。通过基于LGFR的转发方法最终在整个传播过程中形成一条梯度值的最大路径，这样数据包就会沿着此条路径传输。基于LGFR协议的路由建立过程的流程图如图3所示。

图3 基于LGFR协议的路由建立过程

2 仿真实验与结果分析

如表1所示，为了评估所提出的基于LGFR的VANET安全消息传播机制的性能，采用Network Simulator 2.31[7-8]作为仿真平台来验证LGFR的性能。仿真场景采用曼哈顿移动模型，每次仿真随机设定20对源节点与目标节点，通过运行200次仿真测试，最终的仿真结果取统计平均值。

表1 网络仿真参数列表

如图4所示，LGFR的丢包率最低，这是由于GPSR较少考虑道路拓扑对于路径选择的影响，而AODV必须频繁修复中断的转发链路，LGFR在选择数据包转发链路上依据局部梯度场的策略，并不是仅仅依靠地理信息或者网络拓扑的情况来判断下一跳节点是否为最佳转发节点，极大的提高了数据包在VANET中的转发概率。如图5所示，在转发第五跳至第六跳的过程中，三种路由协议都有一个阶段性的时延峰值出现，这是某一处的路口转角造成的阴影信道衰弱，导致在这两跳数据包转发的丢包率急速上高。LGFR考虑到下一跳节点的移动速度与移动方向，可选择新出现的邻居节点作为最佳下一跳转发节点，快速建立高可靠性的数据包转发链路，并且从整个时延峰值变化区间来观察，LGFR同样具有更小的时延抖动。如图6所示，随着节点转发跳数的增加，三种路由协议的全局数据吞吐量都呈下降趋势。在此情况下，LGFR的全局数据吞吐量下降速率是三者中最慢的。

图4 丢包率与转发跳数

图5 数据包端到端平均时延与转发跳数

图6 全局数据吞吐量与转发跳数

对于AODV，城市交通环境下的复杂性决定了AODV必须频繁修复中断的转发链路，建立新的路由。GPSR由于婴儿步问题极大影响了路由转发效率，导致吞吐量瓶颈。LGFR依靠最佳机会转发节点机制，建立了高可靠性的转发链路，因此其数据包转发较少受到移动网络拓扑的影响。

3 结语

在分析了典型的VANET路由协议后，提出了基于LGFR的VANET安全消息传播机制。首先，提出基于距离、数据包处理时延、移动速度、移动方向、邻居节点密度等参量生成局部场梯度值的策略。然后，根据梯度值大小进行安全消息转发的优先级排序，从中选取最佳路由转发节点。最后，选择AODV和GPSR作为比较对象，利用NS2作为仿真平台，以曼哈顿移动模型作为仿真城市道路场景，测试了三种协议在城市交通环境下的路由性能表现。仿真结果表明，LGFR相对其他两种路由协议能更加好地适应城市道路应用场景，其各项网络指标也在三种路由协议中拥有最佳的性能表现。

[1] 曹亮,蒋兴浩. 一种改进型Ad hoc网络安全路由协议[J].信息安全与通信保密,2008(06):112-114.

[2] KAREDAL J, CZINK N, PAIER A, et al. Pathloss Modeling for Vehicle-to-Vehicle Communications[J].IEEE Trans. Vehicular Technology,2011,60(01):323-328.

[3] FAN L, YU W. A Survey of Routing in Vehicular Ad Hoc Networks[J]. IEEE Vehicular Technology Magazine, 2007,2(02):12-22.

[4] ZHAO J, CAO G. VADD: Vehicle-assisted Data Delivery in Vehicular Ad hoc Networks[J]. IEEE Transaction On Vehicular Technology, 2008, 57(03): 1910-1922.

[5] JARUPAN B, EKICI E. A Survey of Cross-layer Design for Vanets[J]. Journal of Ad Hoc Networks, 2011(09):966-983.

[6] WU C, KUMEKAWA K, KATO T. A Novel Multi-hop Broadcast Protocol for Vehicular Safety Applications[J]. Journal of Information Processing, 2010(18):110-124.

[7] 陈春梅.基于NS2的网络仿真与性能分析[J].通信技术,2010,43(08):48-50.

[8] 熊飚,张小桥.VANET网络中小尺度衰落信道仿真[J].通信技术,2010,43(12):56-58.