车联网中基于多优先级的自适应动态路由协议*

徐 婷,王新红,王 平

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

车联网中基于多优先级的自适应动态路由协议*

徐 婷,王新红,王 平

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

本论文介绍了一种车联网中的多优先级的自适应动态路由协议(MPDAR),着重介绍了不同优先级等级消息的分发机制,该路由协议利用了车辆的地理位置和速度信息,并保证了1)车联网中不同类型消息具有不同的QoS要求;2)完全分布式路由协议。最后,本论文应用ViSSIM交通仿真软件和NS-2网络模拟软件,对MPDAR协议进行仿真。结果表明,MPDAR路由协议较其他路由协议性能有所改进。

多优先级 自适应 队列控制 路由协议

0 引 言

车联网作为新兴的通信技术,可以实现车与车之间,车与路边基础设施间的多跳无线通信,以提供多种车辆安全应用与非安全应用[1]。相对于传统的移动自组织网络,车联网有自身独有的特点:①高动态拓扑结构,车辆的高速移动导致车联网的拓扑结构快速变化甚至网络中断;②足够的能量和存储空间。车联网中的通信节点是车辆,它们具有足够的存储空间和数据处理能力;③移动轨迹可预测。车辆的移动受限于已经建好的道路,只要提供了速度和街道地图,车辆的未来状态就可以在一定时间内被预测;④车联网的应用场景多样化,包括车辆安全、道路交通效率、信息与娱乐等应用。以上特点使得车联网的路由方法存在很多新问题和新挑战,传统路由协议在车联网中难以获得理想的性能。

1 研究背景

前期的车联网路由协议主要集中在基于拓扑的路由协议,如AODV、DSR、DSDV等。随着GPS和电子地图的广泛应用,基于地理位置的路由协议成为主流研究方向,如GPSR、A-STAR等。文献[2-3]分别提出了一种基于可靠性和实时性的路由协议,这些路由协议主要用于单一场景,具有局限性。文献[4]提出了一种基于Qos的网格化路由协议GVGrid,它把地理区域分为网格,然后将数据包沿着道路穿过不同的网格转发。但GVGrid是在密集网络假设下提出的,不能完全适用于复杂的VANET环境。文献[5]提出高速公路中基于优先级的安全消息的传输,文中的优先级分类方式参考了IEEE802. 11e中的消息优先级分类方案,满足了对安全消息的快速可靠传输。但文中对非安全消息未做讨论。文献[6]提出了一种应用更广泛的基于优先级路由协议,该路由方案根据802.11p将消息分成了两类:高优先级和低优先级。协议中对低优先级的消息转发方式实际上是一种机会转发,有很大的时延和不可靠性。文献[7]提出针对不同优先级的消息,采取不同的下一跳节点选择方式,保证了紧急消息的快速传输,但该方案采用普通的优先权队列控制方式,容易导致低优先级队列中的分组很久得不到处理,引起“饥饿”。从路由协议发展来看,车联网下的大部分路由协议设计的重点放在保证所有消息的时延、可靠性等方面,而不同的消息有不同的QoS要求,因此这会导致紧急的安全消息,往往不能够得到及时转发,而对于非安全消息,往往处于“饥饿”状态。因此,本论文将对不同的业务范围产生的数据包划分不同的优先级,并放入不同的控制队列中,并自适应的选择路由方式,由此保证较好的网络性能。

2 MPDAR算法设计

首先,本文假设:

1)车联网中的车辆都配备GPS、电子地图设备,可以获取自身的位置、速度等信息。

2)车辆间通过定期广播信标消息,可以获取其他车辆的位置、速度等信息。

3)若车辆处于繁忙状态,则其会广播告知周围节点。

参照欧洲DSRC标准SAE-J2735[8],车联网中的消息可以划分为8个等级:0-7(暂时无消息划分为0等级),等级越高,消息的优先级越高。消息的优先级划分有两个指标:重要性和紧急程度,如表1所示。

表1 消息优先级等级划分机制Table 1 Priority classification mechanism of message

对于高优先级消息,如车辆碰撞预警,需要快速、可靠的分发,而对于低优先级消息,如电子地图下载、娱乐消息等,只需尽力传输即可。另有一类低优先级消息,虽重要性程度低,但时延要求高,需要快速分发,如ETC电子支付。

2.1 多优先级消息队列控制

对于多种优先级消息的队列控制,采用改进的加权公平队列。如图1所示,高优先级队列High-Priority Quene采用先进先出机制,且当该队列中有消息时,优先发送该队列消息;低优先级队列Low-Priority Quene有三种分队列,每个分队列都采用先进先出的排队机制,且其发送时间权值比为3:2:1。

图1 改进的加权公平队列Fig.1 Improved WFQ

传输层的消息分类器将不同优先级的packet放入不同的控制队列。其中,优先级等级为7或6的packet放入High-Priority Quene队列;优先级等级为5或4的packet放入发送时间权值为3的Low -Priority Quene分队列;优先级等级为3或1的packet放入发送时间权值为2的Low-Priority Quene分队列;优先级等级为2的packet放入发送时间权值为1的Low-Priority Quene分队列。

2.2 不同优先级消息的路由转发机制

不同优先级消息QoS要求不同,因此采用不同的转发机制。当车辆需要转发消息时,首先会查找周围车辆节点,并收集其位置、速度、繁忙状态等信息,再根据消息的优先级等级,选取最佳下一跳转发节点,直到到达目的节点。

图2应用场景中,车辆节点3处于繁忙状态,并通过信标消息告知周围节点。车辆S为源节点,D为目的节点。S通过查找路由表,发现其邻居节点有车辆1、3、4、5四个节点。以下为S到D的所有可能路径:R1(S-3-D)、R2(S-1-2-D)、R3(S-1-3-D)、R4(S-4-5-3-D)、R5(S-4-5-6-D)、R6(S-5-3-D)、R7(S-5-6-D)。

图2 场景Fig.2 Scenario

(1)低优先级队列消息分发机制

由于节点4比源节点S距离目的节点D更远,时延加大;车辆1虽比5更接近目的节点,但车辆5与D是同向而车辆1与D是反向而行,连接稳定性差;节点3为繁忙节点,可能导致高时延。通过比较后,源节点将选择邻居节点5作为下一跳转发节点。同理,车辆5将选择节点6作为下一跳转发节点,直到到达目的节点D。由此可知,若消息进入低优先级队列,则转发过程中选择的路径为S-5-6-D。

(2)高优先级队列消息分发机制

由于该队列消息要求可靠性高、时延小,因此采用广播的消息分发机制。繁忙节点3接到该广播消息后,由于该广播消息进入高优先级队列,节点3将停止转发正在发送的消息,优先转发该高优先级消息。同时,为防止所有车辆都在同一时间内转发该广播消息,产生广播风暴,需要规定消息生存时间并限制转发跳数。根据源节点和目的节点的车辆位置、速度方向,判断消息的广播方向,若邻居节点在转发节点的反向广播方向,则该邻居节点无需对该广播消息进行转发。由此可知,若消息进入高优先级队列,则转发过程中选择的路径为S-3-D。

3 性能仿真及分析

3.1 VISSIM以及NS-2仿真工具

VISSIM是一种微观交通系统模拟软件,用以建模和分析各种交通条件下,城市交通和公共交通的运行状况。既可以在线生成可视化的交通运行状况,也可以离线输出各种统计数据,如:位置、速度、方向等。

NS-2[9]是一种面向网络的离散事件模拟器,它以OTcl脚本语言作为前台,C++语言作为后台,可以进行LAN、WAN和无线等网络的仿真。

3.2 仿真结果

在仿真实验中,MAC层使用的协议为IEEE802.11,场景参数配置如表2所示。

表2 仿真试验场景Table 2 Simulation scenario

图3、图4和图5为仿真结果图。

图3 不同通信量时的丢包率Fig.3 Packet-loss rates for different number of traffics

图4 不同通信量时的吞吐量Fig.4 Throughputs for different number of traffics

图5 不同通信量时的端到端平均时延Fig.5 Average delay for different number of traffics

图3～5可以看出,当通信量低时,MPDAR的优势并不明显,但仍然优于AODV和GPSR两种协议.随着通信量的加大,MPDAR的优势逐渐增强,原因是MPDAR引入多种数据包控制队列,优先级高的数据包能够得到及时转发,优先级低的数据包也能得到公平转发。随着通信量的继续增大,繁忙节点增加,网络逐渐产生拥塞,因此丢包率、时延随之增加,但由于MPDAR的多种改进队列控制机制,使得在高通信量情况下,仍能保证相对较高的通信质量。仿真结果表明,MPDAR的性能较AODV和GPSR两种协议都有所改进。

4 结 语

综上所述,MPDAR算法重点在于根据不同消息的优先级,提供了两种不同的发送队列,并自适应的采取不同的路由转发方式。仿真结果表明,MPDAR的网络性能有所提高,确保了安全消息的低时延、高可靠性的要求,又同时保证了非安全消息的吞吐量要求,有效满足车联网不同业务的Qos需求。

[1] 王非,王新红,李想,等.VANET自适应门限MAC层退避算法研究[J].通信技术.2012,45(10):46-49.

WANG Fei,WANG Xin-hong,LI Xiang,et al.The MAC Layer Backoff Algorithm Based On Adaptive Threshold For VANET[J].Communications Technology.2012, 45(10):46-49.

[2] EIZA M H,NI Qiang.A Reliability-Based Routing Scheme For Vehicular Ad Hoc Networks(VANETs)On Highways[C]//Proceedings of the 2012 IEEE 11th International Conference on Trust,Security and Privacy in Computing and Communications.Liverpool,United Kingdom:The IEEE Computer Society,2012:1578-1585.

[3] NZOUONTA J,RAJGURE N,WANG Gui-ling,et al. VANET Routing On City Roads Using Real-Time Vehicular Traffic Information[J].IEEE Transaction OnVehicular Technology,Sept.2009,58(07):3609-3626.

[4] SUN Wei hua,HIROZUMIY,KUSUMOTO Y,et al.GVGrid:A QoS Routing Protocol For Vehicular Ad Hoc Networks[C]//Proceedings of the 14th International Workshop on Quality of Service(IWQoS′06).New Haven, CT,USA:The IEEE Computer Society,2006:130-139.

[5] CHAKKAPHONG S,AURA G.Priority-BasedInter-Vehicle Communication ForHighway Safety Messaging Using IEEE802.11e[C]//Proceedings of 65th IEEE Vehicular Technology Conference,VTC spring 2007.Dublin,Ireland:The IEEE Computer Society,2007:2595-2599.

[6] JIN Zhi-gang,DENGWei,YAN Ning-xiao,et al.A Study of Multi-Priority Opportunistic Directional Routing For VANET[C]//Proceedings of the2010 Wireless Communications and Signal Processing(WCSP).Suzhou,China: IEEE Xplore Digital Library,2010:184-188.

[7] CHEN Jian,ZHOU Mi,LI Deshi,et al.A Priority Based Dynamic Adaptive Routing ProtocolFor Wireless Sensor Networks[C]//Proceedings of the First Intelligent Networks and Intelligent Systems,ICINIS2008. Wuhan,China:International Journal of Intelligent Engineering and Systems,2008:160-164.

[8] DSRC Committee of the SAE.PA 1596-001(SAEJ2735 -2008)Dedicated Short Range Communications(DSRC) Message Set Dictionary[S].[s.l.]:Society of Automotive Engineers,2008:230-235.

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

CHEN Chun-mei.Network Simulation And Performance Analysis based on NS-2[J].Communications Technology,2010,43(08):48-50.

XU Ting(1989-),female,M.Sci., mainly engaged in broadband wireless communications.

王新红(1974—),女,博士,副教授,主要研究方向为宽带无线通信;

WANG Xin-hong(1974-),female,Ph.D.,associate professor,mainly engaged in broadband wireless communications.

王 平(1978—),男,博士,副教授,主要研究方向为宽带无线通信。

WANG Ping(1978-),male,Ph.D.,associate professor, mainly engaged in broadband wireless communications.

Multi-Priority Dymamic Adaptive Routing Protocol for VANET

XU Ting,WANG Xin-hong,WANG Ping
(College of Electronics and Information Engineering,Tongji University,Shanghai 201804,China)

This paper describes a MPDAR(Multi-Priority Dynamic Adaptive Routing)protocol for VANET,focusing on distribution mechanism for messages with different priorities.By using the geographic and speed information of vehicles,the routing protocol could provide different QoSs for different types of messages and fully-distributed routing protocol.The proposed MPDAR protocol is simulated and evaluated with two simulation software called VISSIM and NS-2.The results show that the performance of MPDAR protocol is better than that other routing protocols.

multi-priority;adaptive;queue control;routing protocol

TP316.8

A

1002-0802(2014)02-0163-04

10.3969/j.issn.1002-0802.2014.02.009

徐 婷(1989—),女,硕士,主要研究方向为宽带无线通信;

国家高技术研究发展计划(863计划)(No.2012AA111902);中央高校基本科研业务费专项资金项目(No.0800219162);国家自然科学基金青年科学基金项目(No.61103179)

Foundation Item:National High Technology Research and Development Program of China(863 Program)(No.2012AA111902);The Fundamental Research Funds for the Central Universities(No.0800219162);The National Natural Science Foundation of China (No.61103179)