摘要：VANET是一种具有高度移动性的无线ad hoc网络，将在公共通信安全和商业运用中扮演重要角色。由于高速变化的拓扑结构和车辆的移动性，传统的MANET（mobile AD hoc network）路由协议无法完全解决车辆网络的这种特殊性问题。该文中，我们提出了基于位置路由的贪婪路由算法，即在传输距离有限范围内，把转发节点到朝着目标方向的边缘节点作为最适合下一跳来转发数据包。仿真结果表明，与现在的VANET路由协议相比，在数据包传输中端到端的传输时延大大减小。
关键词：车载通信网络；地理位置路由；贪婪边界无状态路由GPSR
中图分类号：TP 393.09 文献标识码：A 文章编号：1009-3044（2014）17-4159-05
An Improved Geographic Location Routing Strategy Method in VANET
MA Zhi-xin1， LIU Hai-ying1， LI Xin1， XIE Xian-zhong2
（1.Computer Engineering Department， Changji Institute， Changji 831100， China； 2.Institute of Broadband Access Network， Chongqing University of Posts and Telecommunications， Chongqing 400065， China）
Abstract： VANET is a highly mobile wireless ad hoc networks， and will play an important role in public communication security and commercial use. Due to the high speed change topology and the mobility of vehicles，the traditional MANET （mobile ad-hoc network） routing protocol can not completely solve the special problem of the vehicle network. In this article， we put forward the greedy routing algorithm based on location routing， namely within the scope of the limited transmission distance，the forwarding nodes toward the direction of the target edge nodes as the most suitable for the next jump to forward packets .The simulation results show that compared with the present VANET routing protocols， that end-to-end delay in Data packets transmission is greatly reduced.
Key words： vehicle communication network； Location routing； Greedy Perimeter Stateless Routing
1 概述
Vehicular Ad hoc Network （VANET）是应用在短距离道路通信、道路安全以及信息交流。预计在不久的将来更多的车辆将安装计算机和无线通信设备。文中假定车辆安装了无线通信设备、GPS、数字地图来报告车辆的状态，车辆与其他车辆和路边的基础设施通信时要在无线传输范围之内。一个车辆网络是一个移动ad hoc网络，它的特点可以高度概括为高动态性、流动性约束、移动预测性、大规模性和能量性约束不高，因为每个车辆都有一个足够大容量的电池；较高的计算能力：运行车辆可以负担大量计算、通信和传感能力。一种可行的VANET 移动模型可以使访真结果更准确，在MANET中运用的节点随机移动模型用来分析VANET中的路由是不合适的。
2 与VANET相关的路由协议
1）MANET的路由协议
MANET的路由协议可以根据属性分类，可分为主动和被动。主动路由是使用表驱动的方法。它们保留所在网络中的路由信息，主要缺点是：未使用的路由信息可能成为可用带宽的重要组成部分，如果网络拓扑结构变化频繁将不好维护。被动路由是基于实际需求，它们仅保留现在所使用的路由，从而减少了网络的负荷，在任何时间，仅保留一小部分高度利用的路由信息。VANET是高动态的，这种被动性更符合VANET路由协议。路由协议还可以分为基于拓扑的和基于位置的方案。基于拓扑路由仅考虑拓扑中的结点连接，其缺点是延迟大。基于位置路由需要获得加入结点的物理位置信息，路由选择是建立在目的地位置和转发结点位置的基础上的基于位置的路由，不需要路线的建立和维护。
2） 用于VANET的路由协议路由算法
GSR（Geographic Source Routing 地理源路由协议）：是基于位置的路由拓扑信息的。这种方法应用贪婪转发，沿着事先选定的最短路径。[1]仿真结果表明GSR在数据包投递率和延迟方面要优于AODV和DSR。但这种方法忽视了在交通密度低时没有足够结点转发数据包的情况。低交通密度将很难找到一条预先选定的路径来建立端到端的连接。
GPCR（Greedy Perimeter Coordinator Routing 贪婪周边协调员路由）：为了应对城市场景的挑战，文献2中采用一个限制性沿着预先路径的贪婪转发算法，当选择下一跳时，一个协调员（在路口节点）是首选的一个非协调员节点，即使它不是地理上最接近目的地的结点。GPCR 通过路口节点优先转发机制较好的解决了障碍物引起的信号屏蔽问题，可有效地获取移动节点更多的当前状态。和GSR相似，GPCR同样忽视了低交通密度的情况。
A-STAR（Anchor-based Street and Traffic Aware Routing锚-基于街道与交通感知路由）：为了保证即使在低密度车辆交通网络状况下端到端的连接，Seet.B.C 提出了A-STAR，[3] A-STAR利用城市公交路线信息，以（识别）确定一个锚路径与高连接道路的包交付。通过使用一个锚的路径，A-STAR 确保找到一个端到端的连接，即使在交通密度低的情况。这个基于位置的方法也采用了路由恢复策略，也就是说当数据包路由到局部最大时计算新的锚路径促使局部路径最优。仿真结果表明：A-STAR与GSR 和 GPSR相比，实现了网络性能的提高。但是，路由路径可能不是最优的，因为它沿锚路径结果导致较大时延。
MDDV（Mobility-Centric Data Dissemination Algorithm for Vehicular Networks 移动为中心的车辆网络数据传播算法）：为了实现可靠和有效的路由，Wu.H 提出了MDDV，[4]结合机会转发、地理转发和轨迹的转发。MDDV考虑到交通密度。指定一个转发轨迹从源头延伸到目的地（轨迹的转发），消息将被移动到地理上更接近的目的地（地理转发）。转发轨迹的选择使用地理信息和交通密度。MDDV假定是静态的交通密度。信息的转发是通过中间的结点沿着转发轨迹存储转发信息。如果交通密度按时间而变化，这个基于轨迹的转发将导致大量转发延迟。
VADD（Vehicle-Assisted Data Delivery 车载辅助数据交付）：为了保证在一个稀疏网络中在可容忍时延范围内的端到终端的连接，文献5中通过使用可预测的移动性稀疏网络特点，提出了VADD，基于携带和转发的思想。路由不是沿着预先选择的道路，VADD选择最接近目的的下一跳是基于最高预先定义的优先方向。仿真结果表明在分组投递率，数据包延迟和交通开销方面VADD优于GPSR。这种方法预测了车辆的运动方向。但这不能预测未来环境的变化。
PDGR（（Predictive Directional Greedy Routing 预测定向贪婪路由）：定向贪婪路由转发数据包是基于车辆的位置和移动方向。加权值的计算就是基于这个方面的信息，选择计算值最高的结点作为下一跳。如果没有可选的最好下一跳，传送转发方法也同样在这个路由协议中运用。该方法可以降低数据包交付的延迟。在文献6所提出的PDGR协议中，从当前的邻居和未来可能的携带包的邻居中计算出加权值。 随着预测DGR，下两跳的结点的加权数提前计算出来。这里的下一跳是通过预测完成的，并不是在所有情况下都可靠。由于车辆的高动态性，它不能保证数据包在边缘区域中被转发到最适合的下一跳。
文献[7]为了克服GPSR 由于不受限的贪婪转发和路网的平面化处理以及因为路口的建筑物信号遮挡和拓扑结构的快速变化造成贪婪转发失败而转为周边路由转发而造成丢包的问题。引入交叉路口固定节点参与路由转发，但该算法可提高城市场景下的网络传输性能，没有考虑稀疏节点的路由问题。
3 所提出的路由算法
该算法是一个基于边缘节点的贪婪路由算法，有三个基本功能单元。首先是邻居节点标识（NNI）算法，第二是节点方向识别（NDI）算法，第三是边缘节点选择算法ENS。NNI算法是负责来收集在任何时间在传输范围内的源结点或转发结点的信息。NDI算法是负责确定正在向目的地移动的结点的方向。ENS算法是在有限的传输范围内负责为某一数据包选择做进一步转发的具体边缘结点。假设所有节点都配备了GPS接收机，数字地图，可选的传感器和单元。所有车辆的位置或节点信息可以借助全球定位系统GPS识别。唯一可用的通信路线是通过ad-hoc网络，没有其他通信基础设施。节点功率不是设计的限制因素。通信是面向消息。每个结点的最大传输范围是250米。
1）邻居节点识别算法
邻居节点标识的过程，是在一个汽车/节点的传输范围内确定其目前的邻居。对于一个特定的车辆，在传输范围内的其他任何车辆都称作邻居。所有车辆都拥有其邻居的信息。由于所有车辆可能都在移动，一个特定移动结点的邻居总是在变的。邻居表是动态的且需要频繁更新。一般而言，邻居节点的识别是通过使用周期性信标消息实现的。信标消息由节点ID，节点位置和时间戳组成。每个结点通过定期的发送标识信息来通知其它结点自己的存在。
每μ秒发送一个信标信息来通知所有在传输范围内的源结点/转发结点宣布自己的存在。 接到信标信息以后，每个结点都会更新自己的邻居表。如果一个结点位置变化了，那么它将通过发送信标信号向所有邻居更新其位置。如果一个已知的邻居，超时a *μ秒后没有收到一信标信息（a是一个结点允许丢失的信标数）那么这个邻居将从邻居表中删除。
2）结点方向识别算法
在结点识别算法中，目前在有限的传输范围内的源节点或包转发节点的预测数值（PS）被计算出来。计算出来的预测数值用来识别结点移动方向。拥有最大预测数值的合适边缘结点将被考虑是朝向目的地结点D方向运动的，是往目的结点D转发的下一跳结点。预测数值通过以下式子的数学模型计算出来的。
[psi=ρ×（1-DiDc）+ω×cos（vvll，d）]
式中：psi 表示结点i的预测数值；ρ、ω是两个预测因子，ρ+ω=1并且ρ>ω，可以在转发时的位置和方向之间权衡；Di 表示从边缘结点i到目的地D的最短距离；Dc表示从数据包转发结点c到目的地D的最短距离；Di/Dc表示邻近的下一跳；[vi]表示边缘结点i的速度向量；[ll，d]表示边缘结点i位置到目的地D的位置的向量；[cos（vl，ll，d）]表示两个向量夹角的余弦值。
3）边缘结点选择算法
在边缘结点选择算法中，被选中的边缘节点用来转发数据包。在有限的传输范围RL内和其它结点相比，边缘结点是到目的结点距离最短的结点。RL被认为是在数据包传向边缘结点期间避免数据丢失的范围。一个边缘节点负责将接收到的数据保存到转发表里，当这些结点有新的邻居时稍后转发。以下的算法的总体目标是尽快的转发数据来最小化端到端的延时和避免数据丢失。
一个车辆/结点的最大传输距离MTR是250米。有限的传输距离要小于250米。有限的传输范围中包括不同的层次：1级的传输范围RL1=200m；2级的传输范围RL2=150m；3级的传输范围RL3=100m；4级的传输范围RL4=50m，为了便于描述算法，我们做如下约定：
Currentnode=当前数据包携带结点；Locc=当前结点的位置； [vc]=当前结点的速度矢量；Dest=数据包的目的地； Locd =目的地的位置；nextHop=被选为下一跳的结点；Neighi =第i个邻居；
Loci =第i个邻居的位置；[vi]=第i个邻居的速度矢量；
本算法描述如下：
1. Locc ← 获取当前结点位置
2. [vc]←获取当前结点速度
3. Locd←获取目的结点位置
4. Dc=距离（Locc，Locd）
5. [lc，d]= Locd - Locc
6. 预测数值ps = ω×cos（[vc]，[lc，d]）
7. 下一跳 = 当前结点
8. For all当前结点的所有邻居 do
9. Loci ← 获取位置（第i个邻居）
10. [vi] ← 获取速度（第i个邻居）
11. Di=距离（目的结点，第i个邻居节点）
12. Dci = 距离（当前结点，第i个邻居节点）
13. for all Dci内的当前所有邻居结点
14. if （Dci< RL1 and Dci> RL2）
15. [ll，d]= Locd — Loci
16. PSi=ρ×（1-Di/Dc）+cos（[vi]，[ll，d]）
17. For 有着更高的预测数值的第i个邻居 do
18. PS = PSi
19. 下一跳=第i个邻居
20. end for
21. else if （Dci< RL2 and Dci> RL3）
22. [ll，d]= Locd — Loci
23. PSi=ρ×（1-Di/Dc）+cos（[vi]，[ll，d]）
24. For 有着更高的预测数值的第i个邻居 do
25. PS = PSi
26. 下一跳=第i个邻居
27. end for
28. else if （Dci< RL3 and Dci> RL4）
29. [ll，d]= Locd — Loci
30. PSi=ρ×（1-Di/Dc）+cos（[vi]，[ll，d]）
31. For 有着更高的预测数值的第i个邻居 do
32. PS = PSi
33. 下一跳=第i个邻居
34. end for
35. else if （Dci< RL4）
36. [ll，d]= Locd — Loci
37. PSi=ρ×（1-Di/Dc）+cos（[vi]，[ll，d]）
38. For 有着更高的预测数值的第i个邻居 do
39. PS = PSi
40. 下一跳=第i个邻居
41 end for
42. else
43. 数据包→当前节点
44. end if
45. end for
46 end for
距离当前结点距离150米到200米的邻居结点在RL1 和 RL2之间。所有在RL1 和 RL2传输距离之间的结点的预测数值（PS）被计算出来。拥有预测数值最高的结点被认为是RL1的边缘结点。所以数据包从当前结点转发到那个指定的边缘结点。如果在 RL1 和 RL2之间没有结点，那么就考虑RL2和RL3之间。
距离当前结点距离150米到100米的邻居结点在RL2 和 RL3之间。所有在RL2 和 RL3传输距离之间的结点的预测数值（PS）被计算出来。拥有预测数值最高的结点被认为是RL2的边缘结点。所以数据包从当前结点转发到那个指定的边缘结点。如果在 RL2 和 RL3之间没有结点，那么就考虑RL3和RL4之间。
距离当前结点距离50米到100米的邻居结点在RL3 和 RL4之间。所有在RL3 和 RL4传输距离之间的结点的预测数值（PS）被计算出来。拥有预测数值最高的结点被认为是RL3的边缘结点。所以数据包从当前结点转发到那个指定的边缘结点。如果在 RL3 和 RL4之间没有结点，那么就考虑RL4。
距离当前结点距离在50内的邻居结点落在RL4里。所有在RL4传输距离内的结点的预测数值（PS）被计算出来。拥有预测数值最高的结点被认为是RL4的边缘结点。所以数据包从当前结点转发到那个指定的边缘结点。如果在RL4内没有结点，那么数据包就由当前结点携带。如果在以上提到的范围内都没有结点，那么当前结点就把数据包储存起来直到它发现传输范围内的其他结点。
4 仿真结果及分析
在前述的路由协议中，我们选择GPSR，PDGR和本文所提出的协议作比较，使用曼哈顿移动模型来模拟移动在街道或在地图中定义配备了GPS的车辆的运动模式。道路是由一些横向和纵向组成的高速公路，该移动节点可以沿着横向和纵向的街道网格移动。在一个水平和垂直路口，车辆可左转，右转或以一定的概率直行，直行的概率5%，左、右行概率各占0.25%。仿真使用NCTUns 5.0网络模拟器。通过改变节点的数目进行仿真。
NCTUns 5.0是一个网络仿真器，[8]它包括提供交通车辆的仿真，是开源的并在Linux上运行。它能直接使用Linux的TCP / IP协议簇，确保高保真的模拟结果。现在的5.0版本中可实现IEEE 802.11p标准定义的无线车载自组织网络。它可以直接使用UNIX应用程序作为通信量发生器。能使用UNIX网络测试和监控工具，节约实验时间。利用图形用户界面（GUI）完成网络拓扑构建，GUI支持所期望的路网构建、可将道路信息存储在路网文件中；车辆的运动通过设置车辆的移动和与存储在节点运动场景配置文件中有关信息来控制。针对不同数量的节点与特定的参数对每个路由协议进行了仿真。介质访问控制协议采用IEEE 802.11DCF。如表1所示仿真进行了70秒。数据包大小固定为512字节。最初的节点被放置在某些特定地点，然后结点以不同的速度移向新的位置。节点移动的速度从5至25米/秒。仿真参数具体见表1。
表1 仿真参数
[参数＼&量值＼&仿真场景＼&1000m * 1000m＼&车辆数目＼&0 - 120＼&车辆的平均车速（米/秒）＼&5-25＼&传输范围＼&250米＼&恒定比特率（包/秒）＼&2＼&数据包大小（字节）＼&512＼&车辆信标间隔（秒）＼&0.25 0.50 1.0＼&MAC协议＼&802.11 DCF＼&车辆移动模型＼&曼哈顿移动模型＼&]
我们采用端到端的延迟来评价车载通信网路由协议性能。端到端延迟表示从源节点发送数据包到目的地收到所经历的时间。如图1 所示，节点的数量随着固定CBR率而变化。开始时端到端延迟是在所有路由方案中都比较大。这主要是由于较低的分组递交率。当有更多的网络节点，数据包投递率增加了，并且端到端的延迟也越来越小。GPSR的终端到端到的时延比其它协议要大的多。当没有可用的节点时，GPSR切换到周边模式，它增加了数据包的传输时延。当结点多时，与GPSR相比，PDGR端到端的延迟相对要小。这是因为当有更多的节点存在时更容易转发数据包，而下一跳的选择是预测而得，并没有在所有情况下都可靠。当车辆密度足够高（n=120）本算法协议的端至端延迟相对于PDGR要小。更多的网络节点将提供更多的机会找到一些合适的结点，更高效的转发数据包。随着结点群密度增高，与 PDGR 和GPSR相比，所提出的协议（modified）传输延迟大大减小了。
5 总结
在本文中，首先总结研究了基于地理位置的VANET的路由问题。提出了一个新的基于地理位置的贪婪路由方法。仿真结果表明在减少端到端的数据包的传输时延方面，所提出的路由算法优于其他的路由协议。今后的工作需要进一步考虑城市环境特点和车辆的分布情况，使改进的算法更适合于车载通信网。
参考文献：
[1] C. Lochert，H. Hartenstein，J. Tian，D. Herrmann，H. Fubler，M. Mauve.A Routing Strategy for Vehicular Ad Hoc Networks in City Environments[J].IEEE Intelligent Vehicles Symposium （IV2003）.
[2] C. Lochert，M. Mauve，H. Fler，H. Hartenstein.Geographic Routing in City Scenarios[J].ACM SIGMOBILE Mobile Computing and Communications Review （MC2R），2005，9（1）：69–72.
[3] B.-C. Seet，G. Liu， B.-S. Lee， C. H. Foh， K. J. Wong， K.-K. Lee.ASTAR： A Mobile Ad Hoc Routing Strategy for Metropolis Vehicular Communications[J].NETWORKING，2004.
[4] H. Wu， R. Fujimoto，R. Guensler and M. Hunter.MDDV： A Mobility-Centric Data Dissemination Algorithm for Vehicular Networks[J].ACM VANET，2004-10-01：47-56.
[5] J. Zhao and G. Cao.VADD： Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks[J].Vehicular Technology， May 2008，57（3）：1910-1922.
[6] Jiayu Gong，Cheng-Zhong Xu and James Holle.Predictive Directional Greedy Routing in Vehicular Ad hoc Networks[J].Distributed Computing Systems Workshops，2007.ICDCSW "07. 27th International Conference on.
[7] 郑敏，沈永增，张先平.一种城市环境下的地理位置路由策略改进方法[J].计算机系统应用，2013，22（9）.
[8] 王雷.NCTUns：一种新的网络模拟技术[J].计算机技术与发展，2008，18（7）：80-82.
推荐访问： 路由 地理位置 网中 改进 策略