适应城市交通环境的改进型车载路由优化方法设计

摘 要： 为了优化城市交通环境中车载自组织网络中路由协议的链路存活时间、吞吐量等性能指标，在拓扑反应式路由协议的基础上，引入车载网络节点的位置信息，设计基于动态实时位置信息变化的车载路由协议优化模型。该模型按照十字路口车辆优先和相对位置为同方向节点优先转发的原则，根据路由信息表中位置信息区分转发控制包，并给出该路由算法的面向C++语言的UML建模图及其算法流程图。通过NS2仿真平台仿真表明，与传统的路由模型相比，该模型优化了VANETs网络中链路存活时间、时延、吞吐量等性能指标。

关键词： 路由协议； M⁃AODV； 十字路口； UML建模； NS2仿真

中图分类号： TN926⁃34； TP393 文献标识码： A 文章编号： 1004⁃373X（2016）14⁃0100⁃06

Design of improved vehicle⁃mounted routing optimization method suiting for

city traffic environment

XUE Ming， HU Yan

（Henan University of Technology， Zhengzhou 450001， China）

Abstract： In order to optimize the performance indexes of routing protocol link survival time and throughput in vehicle⁃mounted Ad Hoc network of city traffic environment， and on the basis of the topology reactive routing protocol， the position information of the vehicle⁃mounted network nodes is introduced to design the vehicle⁃mounted routing protocol optimization model （M⁃AODV） based on the dynamic change of real⁃time location information. This model is based on the priority forwarding principle of the crossroad vehicles and the relative location as the nodes in the same direction， and used to distinguish the forwarding control packets according to the position information in routing information table. The UML modeling graph of the routing algorithm and algorithm flow chart oriented to C++ language are given. The simulation results obtained from NS2 simulation platform show that， in comparison with the traditional routing model， the proposed model can optimize the performance indexes in VANETs， such as network link survival time， time delay， throughput， etc.

Keywords： routing protocol； M⁃AODV； crossroad； UML modeling； NS2 simulation

随着道路数目和车辆数目的比例严重失衡的情况愈发严重，中国的交通拥堵难题亟待解决，车载自组织网络（VANETs）应运而生。VANETs作为智能交通系统的信息传送平台，可以获得即时的交通信息和道路状况等信息，很大程度上提高驾驶过程中的安全性，继而进一步地减少交通问题[1]。但是目前作为VANETs 中的核心工作内容的认证安全、路由协议等仍然存在一定问题，比如网络负载过大、自私节点拒绝合作、间断性等[2⁃3]。

这里所设计的路由协议M⁃AODV（Improved Ad Hoc on⁃demand Distance Vector Routing）主要是在基于拓扑的反应式路由协议AODV原理，引入动态实时相对位置信息，通过路由表中的位置信息区分转发，区分分类转发的原则是根据车辆间相对位置进行节点分类，采用十字路口车辆优先和相对位置为同方向节点优先转发的方式实现控制包的寻路，进而优化VANETs网络中链路存活时间、时延、吞吐量等性能指标。

1 车载优化路由模型建立与分析

1.1 车载网路由优化模型的基本原理

不同拓扑的位置、节点方向、速度等在很大程度上会影响路由性能，越是临近车辆的方向，其连通度的制约性越强[4]。这一模型按照各个节点位置关系进行划分，主要涉及到[α]类、[90°α]类、[β]类三种节点，其中，对于它们的相对位置关系，第一种是同一路段同向/异向；第二种是同一路段夹角[90°]；第三种是在某角度的偏离节点。具体情况见图1，自E开始，其第一种节点主要是包括A，C，F，I，它的第二种节点主要是涉及到B，D，G，H。对于C来说，其属于十字路口节点（或者称做协调交叉节点，专指处在十字交叉路口范围内的节点，其特殊地方在于，其同时拥有[α]类、[90°α]类节点），B，D是它的第二种，而A，E，F，I属于它的第一种类型。在这里通过三个参数进行表达（M，N，K），其中字母M代表的意思是路段，而字母N主要代表的是行驶方向，而字母K主要代表是否是十字路口，各节点利用位置服务器得到其所在处所的相关数据资料。假定所有车均配备了GPS导航，那么它就能够非常轻松的将自己的地址得到，各节点也会将自己的路段告知临近节点。划分路段过程中，分界点主要是十字路口的节点，各节点仅仅对其位置与路段ID进行广播，十字路口节点信标的广播信息将以“[+]”号表示十字路。

其具体的转发步骤如下：某节点接到路由包，第一步需要判定自身到底属于哪一种节点，要是属于普通节点，那么将会先转向十字路口邻居节点，然后才开始先[α]后[β]类邻居节点进行；要是自己属于十字路口节点，在这种情况下，将会先[α]和[90°α]节点，完成之后，接着选择第二类实施转发。主要操作步骤如图2所示。转发过程按照这个顺利进行，旨在充分确保十字路口优先、同路段同向/反向优先、最后是各个路段与本地节点非[0°]或[90°]的节点。这样有助于路由包以相对较高的速度进行传送，在一定程度上增加了链路存活时间，同时能够在一定程度上降低端到端时延。

1.2 [α]类节点链路存活时间

VANETs中，两节点不间断连接的时间即为链路存活时间。假定没有包丢失率，时间[t0=0]，在[i]与[j]间有某链路，假定[X]所指代的是在建立链路过程中两节点的距离，其值处于[0，300]这一个区间之中。通常而言，[X]符合对数正态分布[5]，假定[μ∈-∞，+∞，σ≥0]，同时一切节点均没有出现超速。在这里通过[vt]和[at]分别指代节点在[t≥0]的速度与加速度，这样就能够得出：

[at=0， a0=0at=a0， a0>0，t≤vmax-v0a00， otherwiseat=a0， a0<0，t<-v0a00， otherwise] （1）

对于式（1），其节点速度比[vmax]小，同时在零以上。假定节点刚开始是[v0]，那么就得出下面的公式：

[vt=v0+0taxdx ] （2）

式中：[ax]是[t=x]的加速度，那么就会得出式（3）：[vt=v0， a0=0vt=v0+a0⋅t， a0>0vmax， otherwisevt=v0+a0⋅t， a0<0 0， otherwise] （3）

通过上文中对于加速度与速度的界定，则[0，t]范围中的行驶距离[st]可以表示如下：

[st=0tvxdx] （4）

对[i]，[j]节点，[t] 时刻的行驶距离、速度和加速度三者依次可以通过下面的方式进行表达：也就是[sit]，[vit]，[ait]与[sjt]，[vjt]，[ajt]，那么就能够得出：

[sit=0tvixdx， sjt=0tvjxdx] （5）

所以，[i]与[j]两者距离就能够通过下式进行表达：

[Δs=sjt-sit+X] （6）

在这里，只有正、逆向行驶两种，对于第一种，此时的[st≥0]，[vt≥0；]而对于第二种，此时的[st≤0]，[vt≤0]，沿正方向，[j]在[i]之前时[X≥0]，即：

[p（t）=1， Δs≥0-1， otherwise]

对链路存活概率计算，因[vt=v0+at∙t]，所以就能够得：

[st=0tvxdx=0tv0+a0∙xdx =v0∙t+12a0t2 ] （7）

假定[sjt-sit=at2+bt+c]，所以就能够得到下面的方程：

[at2+bt+c+X-300=0]

由于链路在[t]时刻将断开[6]，要是[a≠0]，那么对上面的方程求解，则能够得出：[t=-b±b2-4ac+X-3002a]，即解[t1]，[t2]。在这里，要是[a=0]，那么就能够求出：[t=300-c-Xb]。[X]符合对数正态分布，其累计分布函数可通过下式表达：

[Fxx=12+12erflnx-μσ2 ] （8）

所以就能够求出它的概率分布函数，具体为：

[Ptt0=Pt≤t0=P-b±b2-4ac+X-3002a≤t0 =X≥-at20+bt0+c-300， a>0X≤-at20+bt0+c-300， a<0 =1-FX-at20+bt0+c-300， a>0FX-at20+bt0+c-300， a<0] （9）

当[a=0]时，在这种情况下，就能够获得以下结果：

[Ptt0=Pt≤t0=P300-c-Xb≤t0 =1-FX-bt0+c-300， b>0FX-bt0+c-300， b<0] （10）

继而求出其分布函数具体如式（11）所示：

[Ptt0=1-FX-at20+bt0+c-300，a>0，b∈-∞，∞FX-at20+bt0+c-300， a<0，b∈-∞，∞1-FX-bt0+c-300， a=0，b>0FX-bt0+c-300， a=0，b<0 ] （11）

给定[t0]，则能够对[Ptt0]进行计算。按照对数正态分布均值是[eμ+σ22]，则能够得出相应的存活时间。

1.3 [90°α]和[β]类节点链路存活时间

在移动过程中，[90°α]与[β]类节点位置关系，存在大量不同的情况，此处仅仅对下列几种场景进行阐述。

1.3.1 场景 1：单节点移动

假定有节点[i]与[j]，对于[j]来说，其保持固定，它的起始距离是[d0]，对于[i]来说，其速度是[vi]，首次自[I] 传至[I′]的时间是[t1，]两者之间间距是[s1]，第二次所用的时间和距离分别是[t2]和[s2，]同时[I′]和[I″]为同向，具体情况如图3所示。

图中，[α=180°-β]，通过余弦定律就能够得到：

式中：[s1=vi∙t1]，[s2=vi∙t2]，按照文献[7]能够得出[vi]，[st]是二次多项式，基于[vi（t）=v（0）+a（t）∙t]就能够得出式（14），如下：

假定[sjt-sit=at2+bt+c]，符合：[at2+bt+c+X-][300=0]，根据[α]与[90°α] 类节点链路存活时间的求解步骤，就能够计算出[Ptt0]。

1.3.2 场景 2：双节点同时异向等速移动

[i]与[j]在同一个时间内移动，假定[vi=vj=v，]见图3（b）。[i]从[I]传至[I′]，[j]从[J]传至[J′]的时间是[t1]；[i]从[I′]传至[I″]，[j]从[J′]传至[J″]历时[t2]；[I′]和[J′]两者距是[a1]，[I″]和[J″]两者距[a2]；因此，可得到：

[s1=vj∙t1]，[s2=vi∙t2]且存在[vi=vj，]按照文献[8]就能够解出[vi]与[vj]。按照[α]与[90°α]类节点链路存活时间的求解步骤，就能够计算出[Ptt0]。

1.4 M⁃AODV模型的UML结构及算法实现流程图

图4中Routing_model为接口，其中定义Get_routng_model（），Create_Location（）等抽象方法。类AODV_routing_model继承Routing_model接口，实现接口的抽象方法。其中AODV_routing_model（）、～AODV_routing_model（）为自身的构造函数和析构函数。接口Forward_mode与类M_AODV_forward_mode，还有Node_informatio与Get_node_information类似于接口Routing_model与类AODV_routing_model的关系。类Routing_table，Location，Attribution用于作为类AODV_routing_mode，M_AODV_forward_mode，Get_node_information的属性成员。类MainClass为整个程序的入口，其中包括一些变量的定义与赋值、对其他类的方法的调用等操作。M⁃AODV算法流程如图5所示。以上UML建模图及算法流程图可供下一步通过C++语言在NS2仿真平台进行建模仿真实验分析使用。

2 仿真实验及性能比较

本文的仿真主要在NS2仿真平台上进行。为了尽可能模仿真实的城市环境，在NS2上的移动模型是节点随机于没有障碍的平面中移动，与具体移动情况不一致，特别是与城市场景存在着很大的差异，无法真正体现路由协议的性能。所以通过MOVE软件快速生成真实运动模型。MOVE这款软件有三项模型生成功能，分别是地图模型、交通模型和移动模型。通过该软件平台，可以利用其三项功能较好地模拟城市场景。对应三项功能[6]，在该方法中最后得到城市地图、车辆移动模型、NS2交通模型。结合SUMO和NS2的模拟城市场景的框架图，见图6。

本文的十字路口覆盖范围参照文献[7]，设定了一个包含十字路口由4段1 000 m长路段组成的简单路网，其主要涉及到场景与车辆运动模型的生成这两个方面内容。本文所用的仿真模型具体如表1所示。

在表1中，应用环境在NS2中的仿真模拟是通过上文提到的MOVE实现，在运动模式上本文是采用IDM[9]，该模型是一种微观交通流模型，在仿真中将车辆视为移动的节点，因此能够在任意时刻获取仿真中任意车辆的状态，即车辆所处的位置、速度、加速度、所处车道等。

此处仿真主要是通过拓扑反应式的AODV，DSR开展，将模型M⁃AODV下AODV，DSR性能表现和其在业内常用模型[10]的表现加以对比分析，其中涉及到：传输率、链路存活时间等。

2.1 链路存活时间和时延仿真

考虑到车载自组织网络的动态实时变化特性，其网络覆盖范围不是一个静态参数，而是一个与节点行驶速度密切相关的变量，在节点发射功率一定的情况下，决定节点覆盖范围的是节点速率与自组织网络链路存活时间。所以本文在这里着重分析网络链路存活时间与节点速率之间的关系，以此来表现网络覆盖范围对本文所设计方案的影响。图7（a）是平均链路存活时间和速度关系的仿真结果，通过这个图形能够看出传统模型的AODV，DSR链路存活时间比M⁃AODV的小，但是其AODV，DSR值不存在显著的不同。究其根由：因M⁃AODV中，同路段、同直线方向的链路优先级高，该情况是由城市特殊应用环境所决定的，路由包传至十字路口时，在这种应用环境下，一定比例的[β]类变成[90°α]节点，这样就在很大程度上提高了输送质量，正是由于这个原因，其存活时间有所增加。

图7（b）是端到端时延和数据发送速率关系的仿真结果，在这里速率被归一化了，假定原值是[x Kb/s]，那么归一化后为[x800]。通过图7（b）能够看出：传统DSR的端到端时延比传统AODV大，而对于M⁃AODV来说，前者性能指数同样比后者要好，其相同路由协议端到端平均时延比传统的模型要大。究其根由：M⁃AODV主要是通过多次转发进行，这就在一定程度上使得端到端时延有所增加。DSR协议对一个路由中到的一切路由请求RREQ分组做应答。所以源节点了解抵达目的节点的若干个路由。AODV里面，目的节点仅对首个抵达的路由请求分组RREQ应答，对其他RREQ可以忽略，所以DSR时延比AODV大。

2.2 路由开销仿真

对于路由开销来说，其和速度关系具体如图8所示，它是一个源节点至目的路由需求下，一切节点发生交互的包的总量，其数量级处在[105]。随速度的提高其个数呈2次指数提升，且DSR比AODV路由开销大。这是因为，在源节点进行一次路由请求和应答过程中，目的节点路由和所到达过各中间节点的路由信息都会明晰。但是DSR协议即使是最新版之中不存在删除失效的路由机制，同时不存在优先选择路由的机制。这样肯定会增大路由开销。

2.3 吞吐率仿真

图9（a），（b）分别是吞吐量和发送速率、节点速度的关系。

通过图9可以看出吞吐量与发送速率呈正比例关系，而与节点速度成反比例关系，在传统模型和本文所优化的M⁃AODV路由条件下，DSR吞吐量比AODV大，且M⁃AODV的DSR和AODV两个指标要优于传统模型。因为对于DSR来说，其通过源节点访问的路由协议比AODV多，所以DSR路由协议可以在一定程度上有利于吞吐量的提高。第二，M⁃AODV注重十字路口及[α]类邻居节点优先，提高了多数路由的抵达成功率与传播效率，从而使其在一定程度上提高了吞吐量。

3 结 语

本文在传统的AODV路由协议中，引入实时相对位置信息对车辆节点进行分类，采用十字路口优先、多次转发等方式，优化VANETs网络中链路存活时间、时延、吞吐量等性能指标。在实验中，搭建了基于NS2的仿真环境，该环境利用MOVE方法构造城市环境，利用IDM模型构造车流量，通过仿真分析对比表明，本文所在设计的模型，在VANETs实践应用中，DSR，AODV等关键指标得到明显提升。下一步研究将会基于可重构思想对不同试验场景，及其所对应的车在网络传输协议引入上述思想进行分析，以期能够针对不同的应用场景提供最合适的路由协议。

参考文献

[1] 沈永增，姚敏杰，李晓凤.基于城市路网的VANET按需路由策略研究[J].计算机应用与软件，2012，29（6）：236⁃238.

[2] 蔡菁，王腾飞.基于移动模型的车载自组织网络仿真技术研究[J].华中科技大学学报（自然科学版），2013，41（z2）：213⁃217.

[3] 何莉.车载自组织网络中的匿名签名及批验证方案[J].计算机应用与软件，2013，30（1）：306⁃309.

[4] 周娜，刘南杰，赵海涛.一种基于地理位置的车载自组网快速可靠广播算法[J].计算机应用与软件，2014，31（1）：108⁃110.

[5] 唐艳玲.二项分布及其应用、正态分布[J].数学教学通讯（数学金刊），2014（5）：25⁃27.

[6] 林航.车载自组织网络移动模型研究[D].西安：西安电子科技大学，2013.

[7] 崔萌.城市场景下车载自组织网络路由协议的改进[D].哈尔滨：哈尔滨工业大学，2012.

[8] SAGAR S， JAVAID N， SAQIB J， et al. On probability of link availability in original and modified AODV， FSR and OLSR using 802.11 and 802.11p [C]// Proceedings of 2012 IEEE International Conference on Open Systems. Kuala Lumpur： IEEE， 2012： 1⁃6.

[9] 白艳.汽车易驾驶性评价的随机驾驶员模型方法[D].长春：吉林大学，2012.

[10] SURESH M， MOHANRAJ S， KAMALNATHAN C， et al. Performance analysis of AODV， DSR and ZRP protocols in vehicular Ad⁃Hoc network using Qualnet [J]. International journal of application or innovation in engineering management， 2013， 2（4）： 416⁃420.