车联网络车辆结点路由算法研究

刘 云，顾 群

（1.南通大学杏林学院，江苏启东 226236；2.南通大学，江苏南通 226019）

在2003 年召开的汽车通信标准化会议上，一个全新的概念——车载Ad hoc 网络（Vehicular Ad hoc Networks，简称VANETs）应运而生。VANETs 技术在这个新兴领域的相关研究称为车联网技术，路由协议作为车联网技术中的关键技术得到了国内外研究人员的广泛关注。国外对VANETs 的相关研究开始比较早，文献[1] 改进了VANETs 路由协议中获得相邻位置的方法，研究了一种自适应更新策略。文献[2]介绍了一种预测地理路由协议（PGRP），每辆车根据车辆的方向和角度为其邻居赋予重量。文献[3]介绍了一种在VANETs 城市场景中进行路由协议可靠仿真的方法。2004 年以后，我国各高校和研究机构开始对VANETs 及其关键技术展开研究。文献[4]引入粒子群算法对VANET 网络的GPSR 路由协议进行改进。文献[5]分析了车载自组织网络中GPSR 路由算法存在的缺陷，提出了改进措施。文献[6]分别对通信半径相同情况下和通信半径不同情况下的GPSR 路由协议进行了改进，提高了服务质量。

1 路由算法理论基础

1.1 贪婪转发算法

源结点在转发data 数据包前，首先判断是否存在最靠近目的地的下一跳邻结点。遍历邻居列表，如果源结点可以查找到距离目的地结点最近的下一跳结点，则选择贪婪转发策略对数据包进行转发，如图1 所示，图中结点S要向结点D发送数据包，以结点S为圆心的圆内所有结点是结点S的下一跳邻结点，通过计算可知下一跳结点K距目的结点D最近。

图1 贪婪转发情况

1.2 修正转发算法

若源结点遍历完邻居结点列表后无法找到距离目的地结点最近的下一跳结点，则调用修正转发算法。如图2 所示，结点X在进行贪婪转发时，结点W和结点Y到达目的结点D的距离都比结点X到结点D远，不符合贪婪转发规则，无法确定转发数据包的下一跳结点，此时需要调用修正策略进行data 包转发。

图2 修正转发情况

综合考虑下一跳结点与目的地之间的距离和下一跳结点的信任值，选择具有最大权重的下一跳结点进行数据转发。结点的权重根据其与目的地的距离和结点信任值计算。

2 算法设计

基于地理位置和结点信任值的路由算法在传输数据时，首先要通过信标广播获得目的地结点的地理位置和邻居结点的地理位置，然后结点根据收集到的地理位置信息选择调用转发算法进行数据包转发。目的地结点定期广播（sink）包，每个结点在收到sink 包后更新自己的目的地列表。当结点要发送数据时，就会去自己的目的地列表里进行查找目标结点的地理位置。源结点通过信标（beacon）包的周期性互传可以得知其一跳通信范围内所有邻居结点的位置信息，每个结点在收到beacon 包后更新自己邻居结点信息。若一个结点在一定的时间间隔内（本方案将此时间设为常量DEFAULT_GPSR_TIMEOUT）没有接收到某一个邻居结点的beacon 包信息，则结点会认为该邻居结点已经移出了结点的通信范围，把该邻居结点的信息从邻居列表中删除。由于车辆结点始终处于高速运动中，在进行数据转发时网络拓扑中邻居关系不稳定，这可能导致下一跳结点在收到发送结点发来的数据包之前先离开传输范围，所以需要对未来邻居结点的位置进行预测。假设存在一个最大允许距离λ×ds，d，当ds，b≤λ×ds，d时，下一跳在接收到发送结点发来的数据包之前一般不会超出其所在的传输范围。其中，ds，b表示发送结点s（xs，ys）和下一跳结点B（xb，yb）之间的距离，ds，b计算公式如式（1）所示

式中：ds，b表示发送结点s（xs，ys）和目的结点D（xd，yd）之间的距离，ds，d计算公式如式（2）所示

λ 为常量。遍历邻居结点列表，将邻居结点列表中处于最大允许范围内的所有结点放入下一跳允许结点列表。

在进行data 数据包转发时，路由算法使用两种转发策略，贪婪转发策略和修正转发策略。转发的具体过程如下。

Step1：判断当前结点是否是目的地结点，若不是则转step2，否则算法终止。

Step2：判断是否存在最靠近目的地的下一跳邻结点，若存在则转step3 进入，否则转step4。

Step3：在自己的下一跳允许列表中寻找信任值最大的结点作为数据转发的下一跳结点，下一跳结点接收到数据包后，转step1。

Step4：在自己的邻居列表中寻找具有最大权重的结点作为数据转发的下一跳结点，下一跳结点接收到数据包后，转step1。结点的权重根据其与目的地的距离和结点信任值计算。当这2 个因子结合时，这2 个因子的权重由w1和w2表示，且w1+w2=1。权重计算公式如式（3）所示

式中：dk，d表示下一跳k（xk，yk）和目的地D（xd，yd）之间的距离，dk，d计算公式如式（4）所示

tv表示下一跳结点的信任值信息。间隔一定时间后，源结点再次发送data 数据包，重复上述步骤。

3 实验仿真

3.1 仿真场景

本文设计了一个基于地理位置和车辆信任值的车联网络路由算法，当存在最靠近目的地的邻居结点时，选择贪婪转发，否则使用修正转发。为了研究路由算法的可行性及算法性能，使用OMNeT++仿真工具、SUMO交通仿真器和veins 框架搭建仿真环境，并对得出的结果进行分析。其中，OMNeT++控制网络模拟，SUMO 模拟实际交通场景，veins 协调OMNeT++和SUMO 一起工作。模拟的区域为5 000 m×5 000 m，SUMO 交通仿真器对实验仿真场景的细节描述包括：道路、车辆数量、车辆行驶规则等。

3.2 测量参数

车联网络路由算法的性能指标主要包括：平均端到端时延和丢包率，这2 个性能指标可以反映路由算法在网络中的性能。其定义如下。

平均端到端时延：源结点到目的结点的传输时延总和与成功接收的数据包数量之和的比值，这个性能指标反映路由有效性。

丢包率：丢失的数据包数量之和与发送的数据包数量之和的比值，这个性能指标反映路由可靠性。

3.3 仿真设计及结果分析

3.3.1 仿真设计

仿真结果包括矢量仿真结果、标量仿真结果、唯一的运行ID 和属性。输出的矢量仿真结果是时间序列数据，可以用来记录任何对获得模型在仿真期间运行的具体情况有帮助的数据。在omnetpp.ini 文件中加入语句“**.vector-recording = true”，启用矢量记录。标量结果记录在recordScalar（）函数调用中，这种调用通常在finish 模块中完成，若要启用标量记录则需在omnetpp.ini 文件中加入语句“**.scalar-recording =true”。

运行仿真程序，仿真结束后在results 文件夹下会保存新生成的结果文件*.sca 和*.vec。双击打开*.sca文件或*.vec 文件会生成一个*.anf 分析文件，如图3所示。接下来就是对*.anf 文件获得的数据进行分析，得到当前rou.xml 文件描述情景下路由算法的端到端时延和丢包率。

图3 *.anf 分析文件

3.3.2 车辆结点数量对算法性能的影响

仿真参数配置：设置仿真区域为5 000 m×5 000 m，数据链路（MAC）层采用IEEE 802.11p 协议，数据流配置为车载通信仿真框架（Veins）生成的data 数据流，每间隔5 s 开始发送一次data 数据包，基于实际拓扑图的车辆运动场景由SUMO 生成，仿真过程中依次随机放入15、20、25、30、35、40 个结点进行仿真，设置结点的最大速度为14 m/s（50.4 km/h），配置仿真时间为2 000 s。在网络内车辆结点最大速度相同的情况下，车辆结点数目不同，对每一种情况进行多次实验，最后取多次实验结果的平均值。

图4 是车辆结点数目不同的情况下路由算法的平均端到端时延对比图。从图4 中可以发现随着车辆结点数目的增加，平均端到端时延逐渐减小。这是因为随着网络内车辆结点数量的增加，结点的邻居结点数量同时增多，结点之间的邻居关系的稳定性显著提高，通信链路稳定性增强，平均端到端时延自然就下降了。

图4 数目不同时端到端时延的对比图

图5 是车辆结点数目不同的情况下路由算法的丢包率对比图。从图5 中可以发现，当前实验仿真的各个场景下路由算法的丢包率均为0，这证明此路由算法是可行且可靠的。理想情况下，随着车辆结点数量的增加，路由算法的丢包率应下降。而图5 中路由算法的丢包率始终为0，这是因为SUMO 使用交通“流”方式“编写”车流文件，车辆结点密度一直很高，路由算法较容易找到下一跳转发结点。

图5 数目不同丢包率的对比图

3.3.3 车辆结点最大速度对算法性能的影响

仿真参数配置：设置仿真区域为5 000 m×5 000 m，MAC 层采用IEEE 802.11p 协议，数据流配置为Veins 生成的data 数据流，每间隔5 s 开始发送一次data 数据包，基于实际拓扑图的车辆运动场景由SUMO生成，仿真实验中结点的最大速度依次设置为4m/s（14.4 km/h）、9 m/s（32.4 km/h）、14 m/s（50.4 km/h）、19 m/s（68.4 km/h）、24 m/s（86.4 km/h）、29 m/s（104.4 km/h），结点的数量为25，仿真时间设置为2 000 s。在网络中车辆结点数量相同的情况下，车辆结点最大速度不同，对每一种情况进行多次实验，最后取多次实验结果的平均值。

图6 是车辆结点最大速度不同的情况下路由算法的平均端到端时延。从图6 中可以看出，随着网络内车辆结点最大速度不断提高，路由算法的平均端到端时延不断增大。这是因为，随着网络内结点速度的变大，结点之间的地理位置关系变化更加频繁，导致邻居关系不稳定，造成平均时延增加。

图6 最大速度不同时端到端时延对比图

图7 是车辆结点最大速度不同的情况下路由算法的丢包率。从图7 中可以看出，当前实验仿真场景下的路由算法丢包率均为0。理想情况下，随着结点速度的增大，路由算法丢包率应上升。而图7 中，路由算法始终为0，这是因为当前仿真场景下，使用flow 定义的车流中车辆结点始终“聚集”在一起，邻居关系相对稳定，网络通信链路稳定性较好。

图7 最大速度不同时丢包率对比图

4 结束语

本文设计了一个基于地理位置和结点信任值的路由算法，路由算法在传输数据时，首先要通过信标广播获得目的地结点的地理位置信息和邻居结点的地理位置信息，然后结点按照收集到的地理位置信息调用贪婪转发策略和修正转发策略两种路由转发算法进行数据包转发。使用SUMO、OMNeT++、veins 搭建车联网仿真环境，在veins 框架中编写并编译本文提出的路由算法，通过实验仿真获得特定情境下路由算法的平均端到端时延和丢包率。仿真结果表明，路由算法是有效可行的，且车辆结点数量和车辆结点最大速度对路由算法性能有影响。