基于链路稳定度的车载网路由协议研究

李南南， 张曦煌

(江南大学 物联网工程学院，江苏 无锡 214122)



基于链路稳定度的车载网路由协议研究

李南南， 张曦煌

(江南大学 物联网工程学院，江苏 无锡 214122)

针对车载网中节点移动速度快，拓扑结构变化速度快的特点，以及AODV协议广播式路由链路存活时间短、平均端到端时延大等问题，提出了一种通过计算链路稳定度的方式来改进AODV协议。在节点进行广播时，首先计算转发角度，然后，再将投影最长和链路生存时间最长作为综合选择条件，以此高效地选择路径相对较短以及链路相对稳定的路由。通过这种方式，改进后的AODV协议很好地解决了网络中链路易断裂的问题，提高了数据包的投递率，降低了平均端到端的时延。利用NS2仿真软件进行性能仿真，结果表明：改进后的AODV协议在包递率、平均时延和吞吐量方面优于传统模型。

车载网； AODV协议； 链路稳定度； 端到端时延； NS2

0 引 言

近年来，车载自组织网VANET(vehicular Ad Hoc network)作为现代智慧交通系统(intelligent transportation system,ITS)的重要组成部分越来越引起人们关注，其通过车辆与车辆(V2V)之间以及车辆与基站(V2I)之间的交互，实现车辆与车辆、车辆与公众网络的动态通信，在现代交通管理、交通信息查询等方面有很大的应用前景。

VANET属于一种特殊的移动自组织网络[1]，特殊性在于网络中的车辆节点高速移动。正因如此，整个网络的拓扑结构不稳定，随时改变，车载网的链路稳定性较差，所以，选择高效的路由协议成为了亟待解决的问题。根据车载网的特点，目前，普遍使用的协议有基于拓扑结构的路由协议[2]和基于地理位置的路由协议[3]，其中，基于拓扑结构的路由协议包括无线自组织网按需平面距离矢量路由(Ad Hoc on-demand distance vector routing，AODV)协议[4,5]、动态源路由(dynamic source routing，DSR)协议[6]等;基于地理位置的路由协议包括贪婪转发与周边转发相结合的无状态路由(greedy perimeter stateless routing，GPSR)协议[7]、图形源路由(graphic source routing，GSR)协议[8]等。由于在城市环境中的车辆并不是随机分布的，运动轨迹具有规律性，并且存在建筑物阻挡信号的问题，只考虑位置信息并不能得到最佳的传输路径，因此，在城市场景中应用GPSR协议是不适合的。GSR协议通过电子地图获取道路拓扑结构，并利用Dijkstra算法[9]选取最优的数据传输路径，但是GSR协议只根据道路拓扑结构选择数据传输路径，当网络状态不好，车辆节点分散且周围障碍物较多时，路由的可靠性难以保证。在城市车载网中普遍使用基于拓扑结构的路由协议，又因为DSR协议只适合于稀疏网络，对于城市场景中的密集车辆节点运动不具有适用性，因此，相比于DSR协议，AODV协议更适合在城市场景中使用。然而，由于车辆高速移动，网络中的拓扑结构也随时发生变化，AODV协议的链路存活时间变短，链路容易断裂，网络中的包交付率和端到端时延大大降低。因此，针对城市环境下车载网的特点，考虑到AODV协议的不足，在原有协议基础上提出了一种考虑链路稳定度[10]的路由协议。该协议将链路生存时间和链路投影长度作为限定因素进行考虑，在选择数据传输路径的时候能够保证链路稳定性更高，路径相对较短。

1 AODV协议的改进方案

1.1 AODV协议

AODV协议的工作过程分为路由发现、路由本地修护和路由删除三部分。如果源车辆有数据要传输给目的车辆，源车辆就开始路由发现过程，源车辆通过广播RREQ分组到目的车辆来寻找数据传输路径，在此广播过程中，所经过的每个中间车辆节点都要建立反向路由，当目的车辆收到RREQ分组后，就沿着反向路由发送应答分组RREP，直到源车辆收到RREP分组，此时，源车辆到目的车辆的数据传输路径建立完成。传输路径建立完成后，进入路由维护状态，当路径中有车辆节点移出传输范围，或者由于某种原因不能进行数据传输时，启动路由修复过程。路由修复过程中寻找路由的方式与路由发现过程中寻找路由的方式相同，修复状态维持到这条路径不再被需要或者路径断开为止。在车载网中，车辆高速运动，数据传输路径极易断裂，当路径断裂后，如果源车辆还要和目的车辆进行数据通信，那么源车辆将再次启动路由发现过程，寻找一条合适的路径进行数据传输。当不再需要数据通信时启动路由删除过程。

1.2 AODV协议的改进

根据AODV协议的工作过程，传统的AODV协议使用广播方式进行路由选择，没有对路由进行对比，再加上车载网本身的特点，传递路径很容易断裂以至于链路失效。本文改进了传统的AODV协议。在车辆进行路由探测时，首先根据每个车辆节点的坐标来计算每个待转发车辆节点的转发角，如图1所示，θ为节点B的转发角。如果|θ|的取值范围在(0°，90°)之间，符合要求;否则，舍去。图中源车辆节点S会选择B作为转发车辆节点而不选择车辆节点A。

图1 转发角的选择

计算转发角后，根据投影最长和链路生存时间2个方面计算链路稳定度，并将链路稳定度p作为衡量标准。下一跳选择邻居表中p值最大的节点

(1)

式中 Ti为自身节点到节点i的链路生存时间；Li为自身节点与节点i的连线在自身节点到目的节点连线上的投影长度；Tmin为Ti中的最小值；Tmax为Ti中的最大值；Lmin为Li中的最小值；Lmax为Li中的最大值。

相邻节点i和j之间的链路存活时间的计算如下

(2)

式中 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之间的最大通信距离。

计算各邻节点的投影长度

(3)

式中 (x1,y1)为待转发车辆节点的坐标;(x2,y2)为目的车辆节点的坐标;(x3,y3)为邻节点的坐标。在邻居表中比较各个邻节点的投影长度，下一跳选择投影较长的邻节点。

2 改进协议的关键数据结构与算法流程

2.1 关键数据结构

由于改进后的路由协议要在路由探测时根据式(1)计算节点间的链路稳定度，因此，节点必须将自身的位置和速度信息发送给邻节点，那么原来的HELLO分组就要作相应的修改，修改后的分组中应该加入节点的位置、速度、IP地址以及生存时间等信息。由于在传统的AODV协议中邻节点的IP地址和链路生存时间已经存储在邻居表中了，并且链路生存时间一般默认为40s,因此,在改进后的AODV协议中，邻居表里还要加入邻节点的坐标和速度，所以修改后的邻居表的结构体定义如下：

structnbnode_location

{

doublenode_x;

doublenode_y;

doublenode_speed;

};

structAODV_Neighbor

{

structnbnode_locationnb_node_location;

nsaddr_tneighbor_IP;

doublelifetime;

AODV_Neighbor*next;

}

其中，邻节点的横坐标用node_x表示;邻节点的纵坐标用node_y表示;邻节点的运动速度用node_speed表示; 邻节点的IP地址用neighbor_IP表示; 邻节点的默认链路生存时间用lifetime来表示。

2.2 算法流程

根据现实生活中的情况，目前，大量车辆都装有GPS定位系统，所以,每个车辆节点均能方便地获取自身以及目的车辆节点的位置和速度等各种息。当源车辆和目的车辆之间进行通信时，源车辆开始查询自身的邻居表中是否有可直接抵达目的车辆节点的路由，如果存在，就直接进行数据传输；否则，源车辆节点将发送路由请求，并采用广播的方式进行路由探测。算法流程如下：1)根据各个待转发节点的坐标计算待转发节点的转发角，如果满足提前设定的角度范围，则作为可供转发的节点;否则，舍弃该节点。2)根据链路稳定度来选取路由，通过计算其所有邻节点的p值，并选取p值最大的节点发送消息。3)该邻节点再查看自身的邻居表，确定是否探测到到达目的节点的路由，如果有则确立从源车辆到达目的车辆的传输路径，并进行数据传输；如果没有探测到路由，这时,还要考虑该节点是否超时，如果没有超时，则依照上述相同的方式进行路由探测;否则,将超时信息反馈给源车辆，源车辆重新进行广播探测。AODV改进协议的算法流程如图2所示。

图2 算法流程

3 协议仿真与性能分析

为了验证改进后的AODV协议的有效性，采用Network Simulator(NS2)模拟实验，并用VanetMobiSim交通流量仿真器模拟车辆运动模型。实验从网络中的数据包投递率、平均端到端时延以及吞吐量三个指标对传统的AODV协议和改进后的AODV协议进行了分析。实验选择不同的节点密度，仿真数据的车辆节点个数分别为30，60，90，120，150，180；网络传播模型为TwoRayWay，天线类型为OmniAntenna，数据包的发送率为5个/s，包的大小为512 B，数据包类型为CBR，节点间的数据传输使用UDP协议。其他主要的仿真参数设置:仿真区域大小1 500 m×1 500 m;红绿灯数9个;车道数为双车道；车加速最大加速度0.6 m/s2;车减速最大加速度0.5 m/s2;平均速度30 m/s;红绿灯交替时间10 s;最大传输范围250 m;仿真时间300 s。

图3为数据包投递率随着车辆节点密度的增加而不断变化的曲线。由于改进后的协议在路由探测时，将链路的生存时间作为选择因素，所以网络中数据传输路径的维持时间更久，稳定性增强，链路断裂的次数减少，因此，网络中的数据包投递率在改进后的AODV协议中明显提高。而且随着节点密度的增大，网络的连通性增强，网络中可供转发的节点增多，节点更容易找到合适的下一跳，所以，数据包的投递率呈上升趋势。当网络的连通性比较高时，网络中的数据包投递率趋于稳定，并且稳定在95 %左右。

图3 数据包投递率比较

图4为在车辆密度不同时，平均端到端的时延的变化曲线。由于改进后的AODV协议在广播探测路由时，首先计算了转发角度，极大地降低了广播冗余，提高了转发效率。然后，再将链路长度作为选择因素，通过对比之后选择较短的路径，大大地降低了端到端的时延，在平均端到端时延方面，改进后的AODV协议比传统AODV协议效果要好，时延降低。当节点数目的增加时，网络中可供转发的节点增多，这样更容易选择投影长度较长的路径，因此，平均端到端时延随着节点密度的增大会越来越低。

图4 端到端时延比较

图5为随着车辆节点密度的不断变化，网络吞吐量的变化曲线。由于改进后的协议在进行数据传输时的链路稳定性增强，所以改进后的AODV协议在单位时间内成功传送数据的数量(吞吐量)比较高，随着节点数目的增加，链路的稳定性更强，传输路径更短，吞吐量会更大，因此，吞吐量随着节点密度的增大会越来越高。

图5 吞吐量比较

4 结 论

对目前普遍使用的车载网路由协议进行了分析，并针对基于拓扑结构的路由协议的不足，结合城市场景的特殊性，对传统AODV协议进行了改进。在原有的AODV协议中加入车辆节点的位置和速度信息，在寻找路由建立数据传输路径时先计算转发角度，再综合考虑链路的生存时间和链路长度2方面，将链路稳定度作为数据通信的节点。通过分析仿真结果表明：改进后的AODV协议在数据包的投递率、平均端到端的时延和吞吐量方面都得到了明显改进。但是改进后的协议也存在着一点不足，即由于节点在路由探测时要计算转发角度、链路生存时间和路径长度，增大了路由开销。所以，下一步工作将选择合适的方法减小路由开销。

[1] Ranjan P，Ahirwar K K.Comparative study of VANET and MA-NET protocols[C]∥Proc of International Conference on Advance Computing and Communication Technology,2011:517-523.

[2] 于海宁，张宏莉.VANETs路由协议的研究进展[J].电子学报，2011，12(39)：2868-2879.

[3] 马志欣，刘海英，谢显中.基于地理位置的车载网络地理路由算法[J].计算机应用，2013，41(5)：107-110,128.

[4] Cai J,Zhu Y B.An improved AODV routing protocol in urban vehicular Ad Hoc networks[J].Computer Engineering and Science,2013,35(1):61-66.

[5] 郭彦芳.一种改进的基于能量优化的AODV路由协议[J].无线电通信技术，2016,42(4)：25-28.

[6] 卢 颖，陈日莉.基于多描述编码和距离的车载网DSR路由技术研究[J].传感器与微系统，2011，30(10)：15-18.

[7] 黄文静.自组织车联网中GPSR路由协议的研究发展[J].传感器与微系统,2014,33(4):1-5.

[8] 黄 弘，汤 祤.基于地理位置的VANET可靠路由协议[J].研究与开发，2015，12(1)：18-20,38.

[9] Zhou J,Shen Y,Xia Y,et al.Intelligent transportation Dijkstra shortest path analysis of fuzzy dynamic method[J].Technology & Economy in Areas of Communications,2014,16(4):9-12.

[10] Zhou P.Based on the weighted link stability of vehicular Ad-Hoc network on-demand routing protocol[J].Application Research of Computers,2015,32(6):1811-1815.

张曦煌，男，教授，主要从事无线传感网，嵌入式系统，计算机网络，图形与图像处理，计算机分布式控制与智能控制等研究工作。

Research on routing protocol for vehicular network based on link stability

LI Nan-nan， ZHANG Xi-huang

(School of IOT Engineering,Jiangnan University,Wuxi 214122,China)

Since vehicular network has characteristics such as node move fast,topology change rapidly,and AODV protocol broadcast-style routing has the problems such as short link survival time,long average end-to-end delay,a mode is proposed by calculating the link stability to improve AODV protocol.The new protocol choose shorter route and relatively stable routing efficiently by calculating angle forwarding considering two factors which are the longest projection and the longest link survival time when the node is broadcasting.In this way,the improved AODV protocol solves the problem of the network link fracture well,increases the packet delivery ratio and reduces average end-to-end delay.By using the NS2 network simulation software,the results show that the improved AODV protocol is superior to conventional model in packet delivery ratio,average end-to-end delay and throughput.

vehicular network; AODV protocol; link stability; end-to-end time delay; NS2

10.13873/J.1000—9787(2017)07—0012—04

2016—07—07

TP 393

A

1000—9787(2017)07—0012—04

李南南(1991-)，女，硕士研究生，主要研究方向为无线传感网络，嵌入式系统，计算机网络。