一种基于AODV改进的城市车载自组网路由协议研究＊

蔡 菁，朱余兵

（武汉理工大学计算机科学与技术学院，湖北武汉430063）

1 引言

车载自组网VANET（Vehicular Ad hoc NETwork）是专门为车辆间通信而设计的自组织网络，它创造性地将移动自组网技术应用于车辆间通信［1］。车载自组网的特点有：车辆节点沿道路移动并呈“带”状分布，可安装GPS和电子地图来准确获得自己的位置信息等。城市车载自组网相对一般VANET还具有以下特点：车辆的移动速度大致在5～20 m/s，车辆的运动受红绿灯的限制，城市道路基本上都是横竖相交，车辆密度比较大等。

车载自组网作为智能交通的核心已经成为近年来无线网络及智能交通领域的研究热点，但专门针对城市车载自组网的研究还比较少，特别是对网络层路由协议的研究相对缺乏。文献［2］对两种按需路由协议—DSR协议和AODV协议在节点密度不同的VANET下进行了仿真分析和对比，仿真实验结果表明，AODV协议比DSR协议更加适合车辆密度大的VANET环境。文献［3］对DSR协议和AODV协议在城市环境下的VANET环境中进行了仿真分析和对比，仿真实验结果表明，在城市环境下的VANET中，AODV协议优于DSR协议。但是，在城市车载自组网中，AODV协议广播式路由探测方式随着网络规模的增大，发送的冗余帧会迅速增加，极大地降低了协议的性能［4］。因此，本文针对城市环境下车载自组网的特点，考虑到AODV协议广播式路由探测的不足，提出一种改进的新的AODV协议。该协议采用先单播后广播的方式进行路由探测，以减少路由探测帧的发送，从而达到提高协议性能的目的。此外，在单播路由探测阶段同时考虑贪婪转发和路由稳定两个因素，使得探测到的路由稳定性高，平均跳数少。

2 AODV协议改进的基本方案

传统的贪婪转发算法GPSR［5］（Greedy Perimeter Stateless Routing）发送数据时，下一跳都是临时决定的，而不需要维护路由表。但是，AODV协议是需要维护路由表的。如果AODV采用贪婪转发的思想进行路由探测，那么探测到的路由很可能是不稳定的。因为贪婪转发的思想是尽可能地接近目的节点，中间节点总是将路由探测发送到尽可能远离当前节点的邻节点，那么探测到的路由中相邻节点之间的生存时间会比较短，也就是说，探测到的路由会经常断裂，这样会降低AODV协议的性能。因此，用贪婪转发进行路由探测还应该考虑链路的生存时间。

因此，本文在用贪婪转发进行单播路由探测时，在选择下一跳时同时考虑投影最长和链路生存时间最长两个因素，用w衡量。下一跳节点应该是邻节点表中w值最大的那个节点。可以确定按照本文思想找到的路由的跳数将比按照传统贪婪转发思想找到的路由的跳数少。

其中，Ti表示邻节点表中节点i到本节点的链路生存时间；Li表示邻节点表中节点i与本节点的连线在本节点到目的节点连线上投影的长度；Tmin表示Ti中的最小值；Tmax表示Ti中的最大值；Lmin表示Li中的最小值；Lmax表示Li中的最大值。

只要取得合适的α值，改进后的算法能够选择一个跳数相对较少，链路相对稳定的路由。

相邻节点i与节点j之间链路生存时间的计算公式为：

其中，a＝vicosθi－vjcosθj；b＝xi－xj；c＝visinθi－vjsinθj；d＝yi－yj，（xi，yi）为节点i的坐标；（xj，yj）为节点j的坐标；vi、vj分别为节点i和节点j的移动速度；θi、θj分别为节点i和节点j的移动方向；R为节点i和节点j之间的最大通信距离。

转发节点A与其邻节点B的连线在转发节点A到目的节点D连线的投影长度的计算公式为：

其中，（x1，y1）为转发节点A的坐标，（x2，y2）为目的节点D的坐标，（x3，y3）为邻节点B的坐标。在邻节点表中选择当前节点和邻节点的连线在当前节点和目的节点连线上的投影越长的邻节点作为下一跳，更适合城市环境下的车载自组网。

3 改进协议的路由算法及关键数据结构

假设在城市环境下的车载自组网中，车辆节点能够通过电子地图和安装的GPS系统获得自己和目的车辆节点的位置信息。当源节点有数据需要发送时，如果它没有到达目的节点的路由，那么源节点会发起路由探测。如果是第一次向该目的节点发起路由探测，则启动单播路由探测。源节点首先按照公式（1）计算自己邻节点表中所有邻节点的w值，并将路由探测消息发送给w值最大的邻节点。该邻节点查看能否到达目的节点，如果能够到达目的节点，则建立到达目的节点的路由，源节点将开始数据的发送。如果不能到达目的节点，则按照同样的方式将路由请求发送给自己邻节点表中w值最大的邻节点。如果在一段时间内不能探测到目的节点的路由，则将该消息报告给源节点；源节点将启动广播式路由探测方式进行路由探测。AODV改进协议的算法流程如图1所示。

（1）HELLO分组格式。

按照本文的思想，必须按照公式（1）计算节点之间的链路生存时间，那么需要将自己的位置、速度信息通过HELLO分组发送给邻节点。新的HELLO分组包含目的节点坐标、目的节点速度、目的节点IP地址、目的节点序列号、生存时间等主要信息。

（2）邻节点表的数据结构。

Figure 1 Flowchart of the improved AODV routing protocol图1 AODV改进协议的算法流程

在经典AODV协议中，每个节点的邻节点表中的每个条目记录了该节点的一个邻节点的IP地址和链路失效时间。按照本文的思想，邻节点表还应该存储邻节点的位置坐标、邻节点的速度信息。那么，新的邻节点表的数据结构可以使用下面的结构体定义：

其中，nb＿ad dr表示某一个邻节点的编号（IP地址），nb＿expire表示邻节点的默认链路失效时间，next指向邻节点表的下一个条目，x＿coordinate表示某一个邻节点的横坐标，y＿coordinate表示某一个邻节点的纵坐标，d x＿coordinate表示某一个邻节点移动方向与x轴夹角的余弦值，dy＿coordinate表示某一个邻节点移动方向与y轴夹角的正弦值，node＿speed表示某一个邻节点的移动速度。

4 协议仿真及分析

本文采用NS－2仿真平台进行仿真，并采用Vanet Mobisim定义节点移动模型。仿真实验将在不同节点密度、不同最大速度、不同CBR流数值的情况下，从平均端到端时延、丢包率、吞吐量及路由开销四个方面比较经典AODV协议和改进后的AODV协议的性能。主要仿真参数如表1所示。

Table 1 Primary simulation parameter settings表1 主要仿真参数设置

（1）不同节点密度下的性能比较。

在不同节点密度（50，60，70，80，90，100）、车辆速度为3.33 m/s～13.89 m/s、CBR数为5对的情况下的仿真结果如图2所示。

改进后AODV协议在路由探测阶段采用先单播后广播的方式，随着节点数目的增加、城市环境连通性的加强，单播方式探测到的路由的成功率增加了。改进后AODV协议由于先采用单播路由探测的方式发送request分组，如果探测成功那么目的节点只会发送一个reply分组。所以，改进后AODV协议的路由开销会比经典AODV协议少。由于单播方式探测到的路由考虑了路由的平均跳数和路由的稳定性，在经典AODV协议和改进后AODV协议探测到的路由跳数差不多相同的情况下，改进后AODV协议探测到的路由考虑了链路的生存时间，这样会减少路由断裂的次数、降低端到端的时延和丢包率、增加吞吐量，所以改进后AODV协议在平均端到端时延、丢包率、吞吐量方面会优于经典AODV协议。同时，随着节点数目的增加，城市的连通性加强，网络中的分组不会因为没有从源节点到目的节点的路由而丢包，所以经典AODV协议和改进后AODV协议的平均端到端时延呈现下降的趋势，丢包率会基本呈现下降趋势，吞吐量也会基本呈增长趋势。由于网络中HELLO分组会随着节点数目的增加而增加，所以路由开销会随着节点数目的增加而增加。

Figure 2 Performance under different number of nodes图2 不同节点密度下的性能

（2）不同最大速度下的性能比较。

在不同车辆最大速度（m/s）（5，9，13，17，21，25m/s）、车辆数为100辆、CBR数为5对的情况下的仿真结果如图3所示。

Figure 3 Performance under different max speed of nodes图3 不同最大速度下的性能

随着节点速度的增加，网络的拓扑结构变化加剧，路由断裂的次数会增加。由于路由断裂而必须重新发现新的路由，使得平均端到端时延升高、丢包率升高、吞吐量降低。由于仿真实验是在比较连通的城市环境下进行（节点数目为100个），所以改进后AODV协议单播探测到的路由的成功率比较大，路由表中单播探测到的路由条目比例比较大，广播探测到的路由条目比例相对较少。经典AODV协议没有考虑链路的生存时间，所以改进后AODV路由的稳定性会比经典AODV高，路由的断裂次数会相对降低，所以改进后AODV协议会比经典AODV协议的网络时延低、丢包率低、吞吐量高。改进前后的AODV协议在节点数目相同的情况下，网络中的HELLO分组数量会几乎相同，但是由于网络的连通性使得单播探测成功率增加。改进后AODV协议单播探测发送的request分组和reply分组数量会比经典的AODV协议少，所以改进后AODV协议比经典AODV协议的路由负载小。

（3）不同业务流下的性能比较。

在不同CBR数值（5，9，13，17，21，25）、车辆速度为3.33 m/s～13.89 m/s、车辆数为100辆的情况下的仿真结果如图4所示。

Figure 4 Performance under different number of CBR图4 不同业务流下的性能

改进后AODV协议探测路由时考虑了链路稳定性，所以改进后AODV协议探测到的路由断裂次数会比经典AODV协议少。路由断裂后改进前后的协议都会修复或者重新探测路由，这会使得网络的时延增加、丢包率升高、吞吐量降低。由于仿真实验是在比较连通的城市环境下进行（节点数目为100个），所以改进后AODV协议单播探测到的路由的成功率比较大。改进后AODV协议采用单播的方式探测到的路由的稳定性比经典AODV协议的高，发送的request分组和reply分组比经典AODV协议少。所以，改进后AODV协议会比经典AODV协议的平均端到端时延低、丢包率低、吞吐量高、路由开销低。随着CBR数目的增加，网络的吞吐量在网络未饱和之前会增加，网络中的request分组和reply分组会增加，在节点数目相同的情况下，网络中HELLO分组会相同，所以改进前后的AODV协议的路由开销、吞吐量都会增加。

5 结束语

本文针对城市车载自组网的特点，在AODV协议的基础上进行了协议的改进，改进协议采用贪婪转发的单播式路由探测和经典AODV的广播式路由探测相结合的路由探测方式，且单播路由探测在选择下一跳转发节点时同时考虑贪婪转发和链路稳定两个因素，减少了广播帧的发送，提高了路由的稳定性。本文同时利用NS－2对改进后的AODV协议和经典AODV协议进行了仿真分析与性能对比。通过仿真实验可以看出，改进后的AODV协议相比较经典的AODV协议，具有平均端到端时延小、丢包率小、路由开销小、吞吐量大的特点，更加适合城市环境下的车载自组网。

［1］ Chang Cu－yu，Xiang Yong，Shi Mei－lin.Development and status of vehicular ad hoc networks［J］.Journal on Communications，2007，28（11）：116－126.（in Chinese）

［2］ Zhang Yang－xiang，Yi Yu－yan，Han Peng.Simulation study of the feasibility and routing protocol of VANET［J］.Experimental Technology and Management，2009，7（26）：81－83.（in Chinese）

［3］ Paul B，Ibrahim M，Bikas M A N.Experimental analysis of AODV ＆DSR over TCP ＆CBR connections with varying speed and node density in VANET［J］.International Journal of Computer Applications，2011，24（4）：1204－1206.

［4］ Ren Jie，Yuan Dao－hua，Zeng Xiang－hong，et.al.Research and implementation of location aided AODV routing protocol［J］.Computer Engineering and Applications，2008，44（32）：116－119.（in Chinese）

［5］ Karp B，Kung H T.GPSR：Greedy perimeter stateless routing for wireless networks［C］∥Proc of the 6th Annual International Conference on Mobile Computing and Networking（MobiCom 2000），2000：243－254.

附中文参考文献：

［1］ 常促宇，向勇，史美林.车载自组网的现状与发展［J］.通信学报，2007，28（11）：116－126.

［2］ 张洋祥，易玉燕，韩鹏.VANET可行性及路由协议的仿真研究［J］.实验技术与管理，2009，7（26）：81－83.

［4］ 任杰，袁道华，曾祥洪，等.基于位置辅助的AODV路由协议的研究与实现［J］.计算机工程与应用，2008，44（32）：116－119.