基于VANET的改进型AODV路由协议研究*

邱 岚

(江西科技学院 信息工程学院，江西 南昌 330098)

基于VANET的改进型AODV路由协议研究*

邱 岚

(江西科技学院 信息工程学院，江西 南昌 330098)

在车载自组织网络中，常使用AODV路由协议，但是由于车载自组织网络的网络拓扑易变性、节点运动快速性、数据交叉性、网络连通间歇性等特点，传统的AODV路由协议存在数据接收率低、路由重建次数多、传输延时时间长等问题。为此，提出一种基于车载自组织网络的改进型AODV路由协议。采用Dijkstra算法，找出源节点和目的节点之间连通概率最大的路径，对传统的AODV协议进行改进。然后通过仿真软件进行验证和分析，证明改进型AODV路由协议比传统的AODV协议数据接收率更高、路由重建次数更少、传输延时更短。

车载自组织网络；AODV路由协议； Dijkstra算法

0 引言

车辆自组织网络(Vehicular AdHoc Network,VANET)是移动自组织网络(Mobile AdHoc Network,MANET)在智能交通方面的一种应用。在VANET中，AODV(AdHoc On-demand Distance Vector)是一种常用的按需路由协议，主要采用的是DSR(Dynamic Source Routing)中的广播路由发现机制以及DSDV(Destination Sequenced Distance Vector)中的周期更新机制[1]。在AODV中节点的数据传输，只有在没有有效通信链路时，才会启动路由请求信息，这样可以减少广播量，提高效率[2]。

目前，很多学者采用AODV协议，但是对于VANET网络来说，因其具有车辆数量多、网络拓扑结构复杂等特性，传统的AODV协议已经不能满足VANET网络的需求。所以，国内外很多研究者开始研究AODV协议的改进方法，以适应VANET网络的需求，目前取得了不少的成就。例如，ASENOV H等人提出一种基于地理位置的GeoAODV协议[3]，KUMMAKASIKIT M等人提出一种MAODV路由协议[4]， AYASH M等人提出AODV_LAR和AODV_Line两种协议[5]。和文献[3]中的GeoAODV协议一样，AODV_LAR协议和AODV_Line协议没有考虑链路的网络连通性。在国内，也有不少学者对AODV协议展开研究。例如，詹巧昕提出一种紧急报警和查询消息的改进型路由协议EIM-AODV (Emergency warning and Inquire Message based on AODV)[6]，谢波等人提出一种位置预测算法[7]，姜飞提出一种改进型AODV路由协议V-SARP (Stability AODV Routing Protocol for VANET)[8]。

AODV路由协议的改进可以分为两大方向，一是从链路质量方面来改进，二是从位置信息方面来改进。前者可以提高数据接收率但是路由重建次数多，后者可以减少路由重建次数但是数据接收率低。为了综合各方面的因素，本文提出一种基于VANET的改进型AODV路由协议。选取道路长度、车辆数、车辆平均速度作为三个交通参数，建立VANET网络连通性模型。根据模型，采用Dijkstra算法，找到源节点和目的节点之间的VANET网络连通概率最大的路径为最优路径，作为AODV协议信息转发的控制区域，并增加节点位置信息，对传统的AODV协议进行改进。实验表明，这种改进型AODV路由协议比传统的AODV协议数据接收率更高、路由重建次数更少、传输延时更短。

1 VANET网络连通性模型的建立

选取道路长度、车辆数、车辆平均速度这三个参数为主要的交通参数，采用最小二乘法[9]，找到VANET网络连通性和交通参数之间的关系。设道路长度为L，车辆数为C，车辆平均速度为V，则可以通过公式(1)计算出源节点和目的节点的网络连通概率。

P=f{L,C,V}

(1)

式中，f为最小二乘法的逼近函数[9]。

2 最优路径的选择

2.1 Dijkstra算法简介

Dijkstra算法是由DIJKSTRA E D在1959年提出的，因其具有完备的理论和较强的鲁棒性而广泛被使用[10]。Dijkstra算法是一种寻找最优路径的算法。最优路径是指拓扑结构中权值最小的节点组成的路径集合[11]，如公式(2)所示：

(2)

式中，D为源节点到目的节点的一条路径，F(Di)为D的权，N为从源节点到目的节点的路径个数，Dmin为所有路径D中权值最小的路径。

2.2 最优路径的寻找方法

根据前面建立的VANET网络连通性模型，采用Dijkstra算法，求出源节点和目的节点之间的VANET网络连通概率乘积最大的路径集合。具体的方法如下：

(1)通过车载设备采集道路长度L、车辆数C、车辆平均速度V。

(2)根据VANET网络连通性模型求出源节点到目的节点之间所有路径的网络连通概率。

(3)各路径的权值是网络连通概率的对数的绝对值。

(4)采用Dijkstra算法寻找到最优路径。

3 基于VANET的改进型AODV路由协议

假设道路长度、车辆数、车辆平均速度三个交通参数可以通过车载设备获得。另外，各个节点的位置信息已经被采集到。

3.1 设计思路

在VANET中，传统的AODV路由协议存在数据接收率低、路由重建次数多、传输延时长等缺点[12]。本文针对这些缺点，提出了一种基于VANET的改进型AODV路由协议。具体的设计思路如下：

(1)在建立路由之前，可以通过车载设备事先获得道路长度、车辆数、车辆平均速度等信息，源节点到目的节点之间所有路径的网络连通概率由VANET网络连通性模型求出，并且采用Dijkstra算法寻找到最优路径。

(2)在路由请求的过程中，首先由源节点向与之相连的节点发送路由请求分组(RREQ)报文，然后根据路由表，接收到报文的节点可以判断自己是否在最优路径中。如果不在，则丢弃RREQ报文；如果在，则转发RREQ报文。重复上述步骤，直到要传送的信息到达目的节点为止。

(3)在路由应答的过程中，目的节点若收到RREQ报文，则将路由应答RREP报文送回给源节点。若中间节点收到RREP报文，它会先判断自己是否处于最优路径中。如果在，还要确定路由表中有没有源节点的反向路由。若有，则转发RREP消息给源节点并建立反向路由；若没有，则只建立反向路由。

3.2 设计方法

3.2.1 报文格式

在路由请求阶段，源节点所发送的改进型RREQ的报文格式如图1所示。在传统的RREQ报文基础上增加了最优路径集合(ROAD_IDs)，是源节点和目的节点之间的VANET网络连通概率乘积最大的路径集合。在路由应答阶段，目的节点发送回源节点的路由应答RREP报文的格式如图2所示。

图1 改进型RREQ的报文格式

图2 改进型RREP的报文格式

3.2.2 路由请求流程

路由请求流程如下：

(1)节点收到路由请求分组(RREQ)报文。

(2)查看路由表，判断ROAD_IDs中是否包含本节点。

(3)如果没有，则丢弃RREQ报文；如果有，则进一步判断目的节点路由是否存在，是否有效。

(4)若目的节点路由存在并有效，则设置RREQ_ID和目的节点的序号，增加自身序号的条数，最后发送RREQ报文信息。

3.2.3 路由应答流程

路由应答流程如下：

(1)节点收到路由请求RREQ报文。

(2)更新路由表，设置路由应答RREP报文信息，并将该信息发送回源节点。

(3)收到RREP报文的节点首先需要先判断是否包含在ROAD_IDs中。

(4)如果在，就继续确定路由表有没有源节点的反向路由。

(5)若有，则转发RREP消息给源节点并建立反向路由；若没有，则只建立反向路由。

4 仿真验证与结果分析

本文采用VanetMobiSim仿真软件模拟真实的交通路况，选取车辆数为100～400，车辆的平均速度为5～30 m/s，并采用NS2仿真软件仿真网络性能。从数据接收率、路由重建次数和传输延迟时间三个方面来对基于VANET的改进型AODV路由协议的优势进行分析和验证。

4.1 数据接收率的分析

数据接收率指的是目的节点接收的数据量和源节点发出的数据量的百分比。

从图3和图4所示的仿真结果可以看出，不管是在不同速度还是在不同车辆数的情况下，本文所设计的改进型AODV路由协议的数据接收率明显要高于传统的AODV协议。可见，利用网络连通性模型和Dijkstra算法找最优路径的这种改进方法是可行的，不仅提高了链路质量，也提高了数据接收率。

图3 不同速度时的数据接收率

图4 不同车辆数时的数据接收率

4.2 路由重建次数的分析

路由重建次数主要反映的是网络的拥塞程度。

从图5和图6所示的仿真结果中可以看出，车辆平均速度越快，车辆数越多，路由重建次数越多。这是因为车辆平均速度越快，链路断裂就会越频繁，而车辆数的增多，意味着从源节点到目的节点的转发点也会增多，所以增加了路由的重建次数。不过，本文所设计的改进AODV协议比传统AODV协议的路由重建次数少。因为传统的AODV协议采用的是洪泛广播的方式，只要接收到数据的节点都会进行转发，产生大量的浪费。而基于VANET的改进型AODV协议只有在最优路径上的节点才会转发信息，所以可以减少路由重建次数，避免不必要的浪费。

图5 不同速度时的路由重建次数

图6 不同车辆数时的路由重建次数

4.3 传输延迟时间的分析

传输延迟时间指的是接收信息的时间和发送信息的时间之差。

从图7和图8所示的仿真结果中可以看出，速度越快，车辆数越少，延迟时间越长。因为节点的移动速度越快，路由重建次数越多，所以传输延迟时间越长。而车辆数越多，路由的有效时间越长，所以传输延迟时间越短。不过，从图中可以看出，本文所设计的改进型AODV路由协议的传输延迟时间明显要小于传统的AODV协议。因为改进型AODV路由协议选取的是连通概率最大的路径，减少了路由重建次数，从而减少了传输延迟时间。

图7 不同速度时的传输延迟时间

图8 不同车辆数时的传输延迟时间

5 结论

由于传统的AODV路由协议存在数据接收率低、路由重建次数多、传输延迟时间长等问题，本文提出了一种基于VANET的改进型AODV路由协议。采用Dijkstra算法，找到源节点和目的节点之间的VANET网络连通概率最大的路径为最优路径，作为AODV协议信息转发的控制区域，并增加节点位置信息，对传统的AODV协议进行改进。实验结果表明，基于VANET的改进型AODV路由协议比传统的AODV协议数据接收率更高，路由重建次数更少、传输延时更短。当然，本文中的设计还存在一些不足，例如采用Dijkstra算法所得到的最优路径无法判断路径中的每一个节点是否是最优，后续的研究将对这一部分进行优化，使AODV路由协议更加适应VANET网络。

[1] 叶波. 面向车载网的基于AODV优化路由协议的研究[J].电子技术应用,2014,40(12):110-114.

[2] 沈永增,姚敏杰,李晓凤.基于城市路网的VANET按需路由策略研究[J].计算机应用软件,2012,29(6):236-238.297.

[3] HOSSEINI-POZVEH M, NEMATBAKHSH M A, MOVAHHEDINIA H. GPS-enhanced AODV routing[C].International Conference on Wireless Networks, 2009: 651-656.

[4] KUIMNAKASIKIT M, THIPCHAKSURAT S, VARAKULSIRIPHUNTH R. Performance improvement of associativity-based routing protocol for mobile ad hoc networks[C].Fifth International Conference on Information, 2005:16-20.

[5] AYASH M, MIKKI M, YIM K B. Improved AODV routing prcrtocol to cope with high overhead in high mobility[C].2012 Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, 2012:244-251.

[6] 詹巧昕.适用于高速公路车辆预警信息传递的改进型VANET路由协议[J].第八届中国智能交通年会优秀论文集,2012:838-845.

[7] 谢波,肖晓强,徐明,等.基于速度向量的VANET位置预测路由协议[J].计算机工程,2009,35(23):112-114.

[8] 姜飞.车载AdHoc网络按需路由协议的改进及仿真[D].北京:北京邮电大学,2010.

[9] 吴宗敏.散乱数据拟合的模型、方法和理论[M].北京:科学出版社,2007.

[10] 冯欣欣.Dijkstra算法在嵌入式GIS中的优化实现[J].北京理工大学学报,2009,29(10):873-876.

[11] 夏梓峻,刘春风,赵増华,等.基于链路预测的VANET路由算法[J].计算机工程,2012，38(4):110-111.

[12] 熊炜,李清泉.高速公路场景中车用自组织网络连通的必要条件[J].软件学报,2010，21(11):2906-2919.

The improvement AODV routing procol based on VANET

Qiu Lan

(Department of Information Engineering, Jiangxi University of Technology, Nanchang 330098, China)

In VANET, AODV routing protocol is often used. But because of the characteristics of network topology change ability, node movement celerity, data intersectionality, and VANET network connectivity intermittence, the traditional AODV routing protocol has problems such as the data receiving rate is low, the number of rerouting is high and transmission delay time is long etc. This paper proposes an improved AODV routing protocol based on VANET. Dijkstra algorithm is used to find the path between the source node and the destination node, and the traditional AODV protocol is improved. Then through the simulation software to verify and analyze, it is proved that compared to the traditional AODV protocol, the improved AODV routing protocol has leigher data receiving rate, less routing reconstruction times, and shorter transmission delay time.

VANET; AODV routing protocol; Dijkstra algorithm

江西省教育厅科学技术研究项目(GJJ151149)

TN929.5

A

10.19358/j.issn.1674- 7720.2017.16.018

邱岚.基于VANET的改进型AODV路由协议研究[J].微型机与应用，2017,36(16)：63-66.

2017-02-16)

邱岚(1984-)，通信作者，女，硕士研究生，讲师，主要研究方向：无线通信、车联网技术。E-mail:79041684@qq.com。