基于车流密度的VANETs路由协议*

周美丽, 余 敏

(江西师范大学 计算机信息工程学院,江西 南昌 330022)

基于车流密度的VANETs路由协议*

周美丽, 余 敏

(江西师范大学 计算机信息工程学院,江西 南昌 330022)

在节点高速移动的车载自组织网络(VANETs)中，道路交通状况极大地影响着网络中的数据传输性能。在贪婪周边无状态路由(GPSR)协议的基础上加以改进，提出了基于车流密度的VANETs由协议。考虑了车流密度以及节点运动速度、方向等影响因素，设计车流密度的计算方法，利用新的转发策略替代GPSR的贪婪转发策略，能够选择车流密度较好的路径进行数据转发，避免因车流密度分布不均匀而产生的局部最大现象。同时能够对由于节点高速运动引起的链路中断进行预测，提出有效的修复机制，从而建立链路稳健的VANETs路由。采用Matlab仿真平台进行仿真实验，与已有的GPSR，GPCR协议进行比较分析。仿真结果表明:提出的路由协议相比于其它2种路由协议在时延和分组转发率方面得到显著改善，性能优越，非常适合在城市场景中。

车载自组织网络； 车流密度； 链路中断

0 引 言

车载自组织网络(vehicle Ad-Hoc networks,VANETs), 是移动自组织多跳网路中极具应用价值的研究方向。利用 VANETs可以实现事故告警、辅助驾驶、道路交通信息查询、车辆间通信、自动缴费和Internet 信息服务等应用，不仅能提高交通效率，还为司机的通行提供可靠安全的支持和多重便利。由于VANETs网络拓扑结构的高度动态变化在传输数据时很具有挑战性，越来越受到工业界和学术界的高度关注，因此,VANETs路由协议的研究成为了当前的热点方向。

在VANETs的路由协议中，基于地理位置信息的路由协议是最为普遍采用的设计思想。以贪婪周边无状态路由(GPSR)[1]为代表的基于地理位置的路由协议采用贪婪转发的思想，选择离目标节点最近的下一跳进行路由转发，能迅速发现和建立路由，具有高效、低路由开销和良好的可扩展性等特点，特别适合于节点移动速度较快的VANETs。但是在城市道路中，道路两边的建筑物阻挡无线信号的传播，造成空洞的形成，严重影响已有的基于位置的路由协议的性能, 文献[2,3]中对该问题已有介绍。Lochert C等人提出了贪婪周边协调器路由(greedy perimeter coordinator routing，GPCR)[4]协议，通过在十字路口部署固定节点做出数据转发决策，解决了建筑物对无线信号的屏蔽作用。但该协议没有考虑道路上车辆稀少、密度分布不均匀而产生的局部最大现象，路由时可能发生中断，而自动回退，增大时延和跳数，降低路由效率。2008 年，Lee K C等人提出了城市VANETs环境下的地标覆盖路由(LOUVRE)[5]协议。利用车辆自主发现密度的方式辅助路由选择，提出了车辆自主发现道路密度的算法。通过“洪泛”方式传播道路密度的评估值，使全网的所有车辆都能建立起各路段是否具有传输通路的认识，如此众多的洪泛消息极易引起网络拥塞，产生较大的发送时延。除此之外，在VANETs中由于节点的快速移动的特性，会使得已经建立的路由链路发生中断，出现链路不稳定等问题[6～10]。因此，本文在GPSR协议的基础上加以改进，提出了基于车流密度的VANETs路由协议。仿真实验结果表明：该路由协议在时延和分组转发率方面得到显著改善。

1 基于车流密度的VANETs路由协议

1.1 3种类型节点

为了避开建筑物对无线信号的屏蔽效应，在十字路口部署固定的节点称为十字路口节点。在此假设每辆车(节点)都安装了GPS，除了获得位置信息还能获得节点所在的路段信息。对于路段的划分，以十字路口的节点为分界点，2个十字路口的连线即为同一路段。每个节点需要广播自己的位置和所在路段(记为ID)，对于十字路口节点信标的广播信息将会“+”号来表示十字路口。节点可划分为三类：

1)普通节点

该节点的信标广播的ID与所有邻居节点的ID号一致，即为普通节点。

2)预测节点

该节点的邻居表中存在一个十字路口节点，即为预测节点。

3)十字路口节点

该节点邻居表中各个路段的ID都有，自身ID标记为“+”，即为十字路口节点。每个十字路口节点存储并维护一张与其相邻的各个十字路口节点所组成的路段的车流密度表。

1.2 计算道路车流密度的算法

十字路口节点广播Query查询信息至与之相连路段的所有节点，节点将返回自身的节点号和邻居节点数到十字路口节点。十字路口节点通过返回的信息包，计算路段中响应的节点数和所有节点的邻居数之和。

假设路段的长度为L，有n个节点响应十字路口节点的Query查询信息,节点的通信半径为r,n个节点的邻居数之和为m(十字路口节点不作为邻居节点数计算)，那么该路段连通必须满足n≥L/2r;否则,数据经此路段无法成功传输。原理如图1所示。

图1 原理图Fig 1 Principle diagram

图1中路段长度为8r,节点通信半径为r,可看出此路段数据要经过路段两端成功传输至少保证有4个节点。车流密度ρ的计算公式如下

(1)

如图2所示的十字路口节点a维护的车流密度表可表示为：

1)a—b路段：{nodes:3,ρ:4/3},十字路口节点不作为邻居节点数计算，A,B,C的邻居节点数分别为1，2，1；

2)a—f路段：{nodes:0;ρ:0}；

3)a—e路段：{nodes:0;ρ:0}；

4)a—d路段：{nodes:2;ρ:1} 。

其中,nodes表示路段中的节点数，ρ为节点密度。由于a—f路段和a—e路段均只有一个节点,会出现传输中断，可判断此路段车流密度稀疏，不适宜进行路由传输。这种情况将nodes和ρ均设为0。

图2 车流密度示意图Fig 2 Diagram of vehicle density

1.3 设计路由转发机制

在新协议中，针对定义的3种不同节点采用新的转发机制替代GPSR的贪婪转发策略，如下：

1)普通贪婪转发模式

普通节点仍采取贪婪转发模式。

2)受限的贪婪转发模式

当数据包转发至预测节点时，通过判断预测节点与目的节点的位置关系。如果在同一路段则执行贪婪转发模式，则无需经过十字路口节点;否则，将数据包传给十字路口的节点进行路由选择。

3)决策转发模式

当数据包转发至十字路口节点时，决策转发策略如下：

(1)若目的节点在十字路口所相连的路段，则选择与目的节点在同一路段的下一跳节点进行贪婪转发。

(2)若目的节点不在十字路口所处路段，则采取如下步骤：

a.首先，十字路口节点根据自身坐标和目的节点的坐标，判断目的节点在十字路口节点的哪个方位(将方位分为左上、左下、右上、右下)。每一个方位对应2个路段(如图3所示，目的节点H在十字路口节点a左上方位对应a—b，a—d2个路段)。

b.十字路口节点根据步骤(a)判断的方位所对应的2条路段进行选择，查找车流密度表，选择车流密度ρ较大连通性好的路段进行贪婪转发。

c.若这2条路段的车流密度ρ均为0，则等待一个时间T。如果T时间后可以传输，则转到步骤(b)；如果T时间后ρ仍然为0，则采用GPSR经典的右手周边转发模式。

如图3所示，A为源节点，H为目的节点。根据本文的路由协议，源节点A将数据包传输到十字路口节点a时，节点a进行决策转发，选择车流密度大的a—b路段进行传输，传输路径为A—a—C—D—b—F—G—h—H。如果按照GPSR贪婪转发，十字路口节点会选择离目的节点最近的节点E，传输路径为选择A—a—E,由于没有下一跳可进行选择，发生中断，而自动回退，大大降低了传输效率。从图3中可以看出：基于车流密度的VANETs协议考虑了车流密度对数据传输的影响，通过十字路口节点选择车流密度大、局部最优的路段进行数据转发，达到全局较优，明显减少了跳数和传输时延，提高了传输效率。

图3 新协议中的决策转发Fig 3 Decision making and forwarding in new protocol

1.4 链路中断预测和局部路由修复机制

由于VANETs中节点高速移动的特点，可能会发生链路中断。传统的路由协议中，都是在链路中断发生以后再重新进行路由发现，这肯定会对数据的传输带来一定的延时，尤其是对时间要求比较严格的系统，如碰撞避免系统，带来的严重后果不堪设想，为了避免由于链路中断而重新进行路由发现时带来的延时，本文提出一种链路中断预测和修复机制。

当节点处于某路段中时，以十字路口节点为标杆，节点根据自身的位置移动可判断自己的运动方向，将包含自身位置信息的信标信息中加入方向信息广播给邻居节点，因此，节点可以预测自己与邻居节点间的相对距离，是否超出了通信半径，可对链路中断进行提前预测。当一条链路即将发生中断，开始局部修复过程。该协议中，对链路中断分为2种情况，因此，修复过程也分为2种：

1)有可以选择的下一跳节点：此时，则根据动态源路由(dynamic source routing,DSR)[6]算法，选择合适的下一跳，并向源节点发送一个包含中断链路信息的路由错误信息，源节点在路由表中将此路由删除。

2)没有可以选择的下一跳节点：但如果发生中断的节点距离源节点的跳数少于m，则发回一个包含链路中断信息数据包给源节点，重新进行路由发现；否则，在中断处进行 2 跳范围内广播，进行局部修复处理，并将包含错误链路信息的数据包转发回给源节点，让源节点删除此路由信息，以免在下一次路由选择时再选择此路径。

2 实验仿真

本文采用Matlab对改进后的基于车流密度的VANETs路由协议和GPSR,GPCR协议进行大量仿真实验，在传输延迟和分组投递成功率性能方面进行比较分析。应用VanetMobiSim来产生接近现实交通情况的拓扑结构仿真模型。设置场景大小为1 000 m×1 000 m，选择节点数从40～180个随机分布，随机选择一对节点进行通信。节点间的最大有效通信距离为250 m，信道容量为2 MB/s。节点的最大运动速度为50 m/s，仿真持续时间为600 s。

从图4中可以看出:当节点个数增加时，3种协议平均端到端时延变化的比较。当节点个数增多时，节点连通性更好，平均时延均在减小。本文所研究的路由协议，由于考虑到车流密度即连通性对路由的影响，在数据转发时选择连通性好的路径转发，传输时延大大减少。比GPSR的平均时延减少40 %，与GPCR比较也减少了25 %，实时性好。图5显示了数据分组成功投递率的比较情况，相比之下，可以看出：采用本文的协议的数据分组成功投递率基本持续在90 %以上较高水平，在节点较少时仍能保持较高成功率，且较稳定。因此，从实验结果可以看出：本文所研究的基于车流密度的VANETs路由协议在数据分组的成功转发率基本高达90 %多，时延也明显减少，实时性强，远远优于GPSR和GPCR协议，整体性能显著提高。

图4 平均端到端时延比较Fig 4 Comparison of average end-to-end time delay

图5 数据分组成功投递率比较Fig 5 Comparison of data packet successful delivery rate

3 结 论

为了解决道路交通状况极大地影响VANETs路由传输性能和链路稳定性的问题，提出了基于车流密度的VANETs路由协议。充分考虑了车流密度和节点运动速度、方向等因素，能够根据车流密度信息，选择车流密度较好、局部最优的路径进行数据转发，达到全局较优，避免由于道路稀疏引起路由中断而自动回退的问题，大大减少时延和跳数。同时对由于节点高速运动引起的链路中断进行预测，及时有效地修复，保证了链路的实时性和稳定性。通过仿真实验验证：该协议在数据传输中在性能方面得到显著提高，具有高实时性和可靠性。

[1] Karp B,Kung T H.GPSR:Greedy perimeter stateless routing for wireless networks[C]∥Proceedings of the 6th Annual Internatio-nal Conference on Mobile Computing and Networking(MOBICOM’00),Boston,MA,USA:ACM,2000:243-254.

[2] Lochert C,Hartenstein H,Tian J,et al.A routing strategy for vehicular Ad Hoc networks in city environments[C]∥Proceedings of the IEEE Intelligent Vehicles Symposium，IVS’03,Columbus,OH,USA,2003:156-161.

[3] Shu Zhengzheng,Yu Min,Zou Chengwu.An improved clockwise grid routing protocol based on geographic location information[C]∥2012 Second International Conference on Electric Information and Control Engineering，ICEICE 2012,Lushan,China,2012.

[4] Lochert C,Mauve M,Fussler H,et al.Geographic routing in city scenarios[J].ACM SIGMOBLE Mobile Computing and Communications Review,2005,9(1):69-72.

[5] Lee C K,Le M,Harri J.LOUVRE:Landmark overlays for urban vehicular routing environments[C]∥Proceedings of the 68th IEEE Vehicular Technology Conference，VTC-Fall’08,Calgary,Canada:2008-5.

[6] 符媛柯，唐 伦.车载自组织网络路由协议及研究进展[J].计算机应用，2013，33(7)：1793-1797，1801.

[7] Kouah Riad,Moussaoui Samira,Aissani Mohamed. Direction-based greedy forwarding in mobile wireless sensor networks[C]∥The Eighth Advanced International Conference on Telecommunications,AICT 2012,2012:69-74.

[8] Lai Liangli,Wang Qianping,Wang Qun.Research on one kind of improved GPSR algorithm[C]∥2012 International Conference on Computer Science and Electronics Engineering,2012:715-718.

[9] Singh Pranav Kumar, Lego Kapang, Tuithung Dr Themrichon. Simulation-based analysis of Ad Hoc routing protocol in urban and highway scenario of VANET[J].International Journal of Compu-ter Application,2011,12(10):42-49.

[10] 徐会彬,夏 超.VANETs路由综述[J].计算机应用研究,2013(1):1-6.

Routing protocol based on vehicle density in VANETs*

ZHOU Mei-li, YU Min

(School of Computer and Information Engineering,Jiangxi Normal University,Nanchang 330022,China)

In the VANETs of high-speed movement of nodes,road traffic conditions greatly affect the performance of data transmission in the network.On the basis of greedy perimeter stateless routing(GPSR) routing protocol,propose a routing protocol based on vehicle density in VANETs.The new protocol considers the factor of vehicle density and speed and direction of node movement,then designs the calculation method of vehicle density and makes new forwarding strategy instead of the greedy forwarding strategy of GPSR,which can select the path of better vehicle density to forwarding data to avoid phenomena of local maxima caused by uneven distribution of vehicle density.And can predict about link interruption caused by high-speed movement of nodes,then proposes effective repair mechanism to establish a stable VENETs routing of robust link.The performance of GPSR,and GPCR is compared by simulation using Matlab.The simulation results show that the capability of the new protocol is improved significantly compared with the other two routing protocols on delay time and forwarding rate and it is suitable to be applied in city scenes.

VANETs； vehicle density； link interruption

2013—08—15

国家自然科学基金资助项目(41164001)；国际科技合作专项项目(35—14)

TP 393

A

1000—9787(2014)04—0118—04

周美丽(1990-)，女，江西抚州人，硕士研究生，研究方向为无线传感器网络。