张晓丽, 赵 谦, 张 彤

(1.西安航空学院 计算机学院, 陕西 西安 710077；2.西安理工大学 计算机科学与工程学院, 陕西 西安 710048)



车载自组网中对GPSR路由协议的改进

张晓丽1, 赵 谦2, 张 彤2

(1.西安航空学院 计算机学院, 陕西 西安 710077；2.西安理工大学 计算机科学与工程学院, 陕西 西安 710048)

针对车载自组网具有节点移动速度快、网络拓扑变化频繁的特点，在现有的GPSR协议基础上进行改进，提出了基于速度-密度模型的改进路由协议GPSR-SD。该协议结合速度-密度模型，对行驶该车辆节点所在路段的车辆密度值进行估算，在路由选择过程中综合考虑车辆节点的行驶速度和车辆密度信息值两个因素来选择下一跳转发节点, 进而提高转发节点选择的正确性来增加通信链路可靠性，从而减小了节点移动过程中所产生的空洞现象问题，提高了平均封包送达率，有效地降低了平均端到端的时延。通过NS2平台仿真对比试验，验证了GPSR-SD具有较好的性能。

智能交通系统;车载自组网；路由协议；速度-密度模型；网络仿真

0 引言

车载自组网(Vehicular Ad Hoc Network，VANET)[1-3]是一种高流动性的无线自组织网络，它创造性地将移动自组网技术应用于车辆间通信，其目的是保证车辆安全、监控流量和其他商业应用。节点车辆均配备有各种传感器，通过这些传感器系统获取节点车辆的相关信息，如位置信息、速度信息等，以便与其他节点进行数据交换。通过获取其他节点车辆的速率及位置等信息，估算出实时路况信息，以极大地提高交通通行效率，同时也为车辆的通行提供更加可靠、安全和便利的服务。由于节点的单跳通信范围最多只有1 000 m，所以应该采用多跳通信来传输数据，进而转发给更远的节点。在此过程中，每个车辆节点不仅仅是一个数据接收器，同时还要具有路由的功能。

由于车辆节点具有高移动性，VANET网络拓扑结构变化频繁，网络中通信链路易断裂，难以保证移动节点间持续稳定的连接，因此路由选择在VANET中非常重要，如何快速选择下一跳路由节点成为VANET中的热点问题，国内外的诸多学者对此做了大量的研究，提出了众多适合的路由协议，这些路由协议能够实现在VANET中高效的数据转发。

文献[4]通过若干个节点，周期性地估算全网的车流密度，汇总后通知给所有节点，该协议达到了良好的传输率。文献[5]提出了Vehicle Location Service(VLS)协议，将网络划分为多个区域，并使用哈希算法为各节点在每个区域选择一个位置服务器。文献[6]提出了基于车辆的分布式实时路段延时估计机制协议，通过获取每条路段网络状态的实时信息,并根据对各路段网络延时的实时估计,保证了数据的有效传递。文献[7]提出了一种改进的新ADOV协议，该协议采用先单播后广播的方式进行路由探测，有效地提高了路由的稳定性。

传统的贪婪周边无状态路由(Greedy Perimeter Stateless Routing，GPSR)算法[8]是一种经典的地理位置的路由协议，该协议使用贪婪算法来建立路由，当转发出现路由空洞时，就采用边缘转发，GPSR算法依赖直接邻节点进行路由选择，节点不需维护和存储路由表，简单易实现，但由于节点移动速度快，网络拓扑不稳定，GPSR算法面临着路由选择错误和路由中断的问题。文献[9]对GPSR进行了改进，对于过期的邻居信息进行了删除，同时增加了预测目的节点的位置变化。张继永等[10]改进了GPSR算法，提出了以最大通信时间为策略来选择下一跳节点的KMCT路由算法。文献[11]提出的GPSR-L算法，通过lifetime概念来解决速度对 GPSR 路由的影响。文献[12]提出的RRMLI算法优化了GPSR的路由机制，在链接断开后采用贪婪算法向目的节点发送RREQ消息分组来修复路由。文献[13]提出的基于交通信息感知的TGPSR-WI路由算法改进了GPSR算法的贪婪转发策略，适合城市环境车载自组织网络。文献[14]提出的GPSR-R算法在路由的寻找过程中根据节点的网络需求进行考虑，提高了在长距离传输中的数据传送率。

本文针对城市环境下车载自组网的特点，在研究传统GPSR算法的基础上，依据速度-密度关系模型[15]进行车辆密度估算，提出一种基于速度-密度模型的VANET路由协议算法 (GPSR with Speed-density Direction, GPSR-SD)。GPSR-SD算法中各车辆节点根据邻居节点发送的Beacon信息，及时更新自己的路由表，然后依据贪婪算法选择距离目的节点最近的一个邻居节点作为临时下一跳节点，并判断其密度值，最后优先选择满足条件的节点作为下一跳进行转发。仿真对比试验表明，改进后的算法减小了节点移动过程中所产生的空洞现象，并且在提高平均封包送达率的同时可兼顾较低的平均端到端的时延。

1 GPSR-SD协议

1.1 假设条件

假设道路中的每个车辆节点均配有GPS设备，根据该设备，节点随时都能得到自己的准确位置。同时，安装了现在最流行的具有精确电子地图的导航软件，能够将车辆获取的位置信息与其行驶的城市道路相互关联。另外，每个车辆节点也是一个小型的车载嵌入式系统，配备了802.11x无线网络模块，可以实现与其他车辆间的通信。

1.2 相关数据计算

行驶在道路上车辆，在不同的路段面临的路况可能很复杂。当某条道路畅通，即车辆密度很小时，车辆可以自由行驶，并且行驶速度可达到该路段的最大可行驶时速；而当该道路发生拥堵时，即车辆密度逐渐增大时，车速会随着拥堵的严重程度逐渐减小，当发生严重拥堵时，车速将减至为零。所以，行驶在该道路上车辆的速度值和车辆密度将直接决定道路的通行情况。本文依据速度-密度的关系模型进行密度估算，模型如下：

(1)

式中，V为车辆的行驶速度;vf为道路畅通时车辆的行驶速度；k为该道路的车辆密度；kj为道路的阻塞密度值；n为大于零的实数，取n=0.5，当n=1时，该表达式变为线性表达式。

(2)

结合式(1)、式(2)，可根据道路行驶车辆的平均速度计算该路段的车辆密度k：

(3)

1.3 相关定义

定义1(邻居节点)：车辆节点的邻居节点指其通信范围内的所有车辆节点，节点通过Beacon消息获取邻居车辆的信息，包括位置、速度及运动方向、车辆密度等。

定义2(Beacon信息)：依照上文的速度-密度线性关系模型，可以计算出每条路段的密度信息，保存在Beacon信息中。该Beacon信息的内容包括{Nn,Ln,Vn,Rij,Kij,Tn}，即：

NnLnVnRijKijTn

其中Nn为节点标号；Ln为节点定位信息；Vn为节点速度信息；Rij为路段标号；Kij为当前路段的密度信息；Tn为节点时间戳信息。

节点的具体位置可以通过传递Beacon信息进行预测，每个节点能确定在通信范围内可通信节点的数量，如果某节点的当前位置在源节点通信范围内不存在，那么该节点将不会成为一个邻居节点。为保证信息的时效性，将依据时间戳周期性地更新该路段节点的密度信息，同时路段中的各车辆节点根据邻居节点发送的Beacon信息，及时更新自己的路由表。

1.4 GPSR-SD协议转发策略

GPSR-SD协议是基于网络需求的GPSR路由选择算法。在该算法中，可以根据车辆速度信息计算该路段中车辆密度的情况及网络拓扑变化的情况。当源节点需要传输数据时，如果不存在到达目的节点的路由，则源节点会发起路由探测查找最优传输路径。

GPSR-SD具体的转发步骤如下：

S1：处在网络中的各节点周期性地广播发送Beacon数据包，收到该数据包的各节点及时更新自己的路由表，若节点的路由表中存在相关的节点信息，则用收到的该信息替换以前的节点信息。若不存在，则将该信息增加到节点的路由表中，然后转到S2。

S2：依据路由表，根据贪婪转发原则选取距离目的节点最接近的一个邻居节点作为暂定下一跳节点，接着判断该节点所在道路的密度值信息，若其路由表中密度值不大于该道路的阻塞密度值kj，则继续选择距离目的节点次近的节点，判断其密度值。该判断过程一直重复，若该区域内无可转发的节点，则利用车辆的行进特性，采用携带-存储-转发的方式来传输数据包，直到遇到满足条件的下一跳节点时转发。

S3：在转发的过程中，根据节点的时间戳，优先选择实效性强的节点进行转发，以保证传输路径的高实效性。

S4：重复以上步骤，直到找到目的节点。下次传输时，则按照优化后的路径进行传输；若未发现优化路径，则继续采用本方法或按照边缘转发方式传输。

如图1所示，A为源节点，F为目的节点，圆圈为节点的传输半径。

图1 路由步骤示意图Fig.1 Schematic diagram of routing steps

所有节点将周期性地发送Beacon数据包。节点A会定期收到节点B和C发送的数据包，并将收到的这些节点信息与自己路由表中原有的数据和信息进行比较，判断写入或更新路由表信息。

然后，由于在传输范围内，节点C距离目的节点F最近，则先选择节点C作为下一跳节点，并判断其密度值。由于节点C当前所在的道路发生阻塞，经过计算，其密度值小于该道路的阻塞密度值kj，不满足转发条件，故放弃该节点。接着选择次近节点B，判断其密度值，由于节点B所在道路并未发生拥堵，即节点B的密度值大于该道路的阻塞密度值kj，故节点B为满足条件的节点，所以节点A将数据首先发送至节点B。同样，节点B在发送数据时，将数据发送至并未发生拥堵的节点E，而未发送至节点D。

最后，目的节点F在节点E的传输范围中，故节点E将数据发送至目的节点F，完成传输。在传输过程中，及时更新各节点路由表中的时间戳信息，若再有相同的传输路径时，则按照本次的传输路径传输数据。

由此可知，使用GPSR-SD路由协议成功地找到了A→B→E→F这条节点最优路径，并且为以后的传输进行了优化。如果使用现有的GPSR协议进行路由传输，则很有可能将源节点A的数据，通过贪婪算法传输到了节点C或节点D，从而影响数据的传输，增大端到端的延时。

GPSR-SD协议的流程图如图2所示。

图2 GPSR-SD协议流程图Fig.2 Flowchart of GPSR-SD protocol

2 仿真试验分析

本文使用网络仿真器NS-2仿真平台对本文协议(GPSR-SD)和GPSR协议、GPSR-R协议进行仿真对比，并使用VanetMobiSim定义节点移动模型。仿真试验在不同节点速度的情况下，从平均端到端时延、平均封包送达率、路由负载3个方面比较经典GPSR协议、GPSR-R协议和本文GPSR-SD协议的性能。Network Simulator Version 2 (NS2)是一种离散事件驱动的、面向对象的、开源的网络模拟器[16]，它既可模拟有线网络环境，又可模拟无线网络环境。

试验选取某1 800 m×1 800 m区域作为仿真区域，并使用VanetMobiSim产生交通流，设置100个仿真节点，并分别设置移动速度为20～80 km/h，使用CBR流，每条每秒送出10个封包，每隔30 s采集1次仿真数据并进行比较，如图3所示。

图3 仿真区域选取Fig.3 Selecting simulation area

仿真所采用的平台是WindowsXP+Cygwin+NS-2.29+VanetMobiSim-2.0，添加 Otcl 仿真配置脚本，并设置相关仿真参数。主要仿真参数设置如表1所示。

表1 仿真参数设置

在仿真试验中，分别测试3种算法的平均端到端时延、平均封包送达率和路由负载，将仿真获得的数据进行统计，求出平均值作为结果，测试对比结果如图4～图6所示。

图4 不同节点速度时的平均端到端时延Fig.4 Average end-to-end time delay at different node speeds

图5 不同节点速度时的平均封包送达率Fig.5 Average packet delivery rates at different node speeds

图6 不同节点速度时的路由负载Fig.6 Routing overloads at different node speeds

试验对比结果表明，在相同的试验场景下，使用GPSR-SD路由协议取得了较好的性能。由于GPSR-SD路由协议在选择下一跳节点时考虑了速度、密度因素，能选择更有效的节点，减少路由开销，明显改善了平均端到端时延和封包送达率，同时路由负载也相对有一定的减小。

从图4、图5可以看出，当仿真场景中的车辆节点在较低速度下行驶时，3种协议均有着较低的平均端到端时延和较高的平均封包送达率。而随着节点速度的增加，仿真场景情况越来越复杂，路由断裂的次数也会相应增加，因此必须重新寻找新的路由，而端到端的时延也随之增大。使用GPSR-SD协议仍然保持着比GPSR协议和GPSR-R协议较低的时延。图5反映出在不同速度下平均封包送达率的情况，可以看出，GPSR-SD协议有着较好的送达率，这是由于GPSR使用贪婪转发，而贪婪转发的思想是为了接近目的节点而尽可能地将路由探测发送到远离当前节点的邻节点，这样相邻节点之间的生存时间会比较短，使得路由经常断裂，因此数据包传递的成功率就会显著降低。GPSR-R算法在选择路由时综合考虑移动节点间链路建立的网络需求，提高了封包送达率，但在节点处于高速行驶时增大了丢包率。改进后的GPSR-SD协议在探测路由时考虑了节点的速度信息和道路的密度信息，根据路段的密度情况动态调整数据转发策略，使得路由的生存时间更长，这样能减少节点之间一些不必要的传输，更准确、更迅速地传输数据包。当没有探测到路由节点时采用携带-存储-转发的方式，避免了GPSR协议中的一些局部最优问题。并且由图5可知，即使节点处于很高的行驶速度时，GPSR-SD协议仍能保持一个较高的送达率。

图6反映了3种算法在不同速度下的路由负载情况。可以看到，当节点速度增大时，使用3种协议的路由负载都在增大，但是使用改进的GPSR-SD协议时的路由负载增长比较均匀。由于GPSR-SD协议在探测路由时不需要频繁为新建立的路由发送数据，从而保证了路由负载不会急剧增加。

3 结论

根据车载自组网的特点，提出了一种改进的路由协议GPSR-SD，该协议改进了GPSR算法，依据速度-密度计算车辆密度，并以此为依据选择下一跳的路由节点。仿真试验对比表明，该协议有较好的性能，能很好地适用于节点较多、交通状况较复杂的环境中。但现实交通环境中存在许多高大建筑物等障碍物的干扰，因此同时考虑障碍物对传输的干扰是未来研究的重点，也是车载自组网中的难点。

[1] ZEADALLY S, HUNT R, CHEN Y S. Vehicular Ad Hoc Networks (VANETS): Status, Results, and Challenges[J]. Telecommunication Systems, 2012,50(4):217-241.

[2] BOUKERCHE A, OLIVEIRA H A B F, NAKAMURA E F, et al. Vehicular Ad Hoc Networks: A New Challenge for Localization-based Systems[J]. Computer Communications, 2008, 31(12):2838-2849.

[3] 常促宇,向勇,史美林.车载自组网的现状与发展[J].通信学报,2007,28(11):116-126.

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.

[4] NZOUONTA J, RAJGURE N, WANG G, et al. VANET Routing on City Roads Using Real-time Vehicular Traffic Information[J]. IEEE Transactions on Vehicular Technology, 2009, 58(7):3609-3626.

[5] 白翔宇，叶新铭，李军. 感知实时车流信息的 VANET 路由仿真研究[J]. 系统仿真学报，2012,24(2):429-434,440.

BAI Xiang-yu,YE Xin-ming, LI Jun. Simulation Research on VANET Routing with Real-time Vehicular Traffic Aware [J]. Journal of System Simulation, 2012,24(2):429-434,440.

[6] 宋超, 刘明, 龚海刚, 等. 基于分布式实时信息的车载网络路由协议[J]. 软件学报,2011,22(3):466-480.

SONG Chao, LIU Ming, GONG Hai-gang，et al. Distributed Real-time Information Based Routing Protocol in Vehicular Ad Hoc Networks [J]. Journal of Software, 2011,22(3):466-480.

[7] 蔡菁,朱余兵.一种基于AODV改进的城市车载自组网路由协议研究[J].计算机工程与科学，2013,35(1):61-66.

CAI Jing, ZHU Yu-bing. An Improved AODV Routing Protocol in Urban Vehicular Ad Hoc Networks [J]. Computer Engineering and Science, 2013,35(1):61-66.

[8] KARP B, KUNG H T. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks[C]// International Conference on Mobile Computing and Networking. Boston: ACM, 2005:243-254.

[9] NAUMOV V, BAUMANN R, GROSS T. An Evaluation of Inter-vehicle Ad Hoc Networks Based on Realistic Vehicular Traces[C]// Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2006. Florence: ACM, 2010:108-119.

[10]张继永,杨斌.无线车联网WAVE车-车通信中的一种路由算法实现[J].通信技术, 2013(9):55-57.

ZHANG Ji-yong, YANG Bin. A Routing Algorithm for Car-to-car Communication in Wireless Access Vehicular Environment[J]. Communications Technology,2013 (9): 55-57.

[11]RAO SA, PAI M, BOUSSEDJRA M, et al. GPSR-L: Greedy Perimeter Stateless Routing with Lifetime for VANETS[C]// Proceedings of the 8th International Conference on Intelligent Transport System Telecommunications. Phuket: IEEE, 2008:299-304.

[12]刘国田, 杨永军, 刘征宇,等. 基于位置信息的车联网路由恢复方法[J].电子测量与仪器学报, 2012, 26(8):716-720.

LIU Guo-tian,YANG Yong-jun, LIU Zheng-yu,et al. A Route Recovery Method Based on Location Information in Vehicular Ad Hoc Networks[J]. Journal of Electronic Measurement and Instrument, 2012, 26(8): 716-720.

[13]肖德贵,彭李翔,宋丹,等.混合VANET环境下一种改进的GPSR路由算法[J].软件学报,2012,23(增1):100-107.

XIAO De-gui,PENG Li-xiang, SONG Dan,et al. Improved GPSR Routing Algorithm in Hybrid VANET Environment[J]. Journal of Software,2012,23(S1):100-107.

[14]李超,韩江洪,魏振春,等.VANET场景下的GPSR-R路由算法[J].合肥工业大学学报,2015,38(2):181-185.

LI Chao, HAN Jiang-hong,WEI Zhen-chun,et al. GPSR-R Routing Algorithm in VANET Scenario[J].Journal of Hefei University of Technology, 2015,38(2):181-185.

[15]WANG H Z, LI J, CHEN Q Y, NI D H. Logistic Modeling of the Equilibrium Speed-density Relationship[J]. Transportation Research Part A Policy & Practice, 2011,45(6):554-566.

[16]FALL K, VARADHAN K. The Ns Manual (Formerly Ns Notes and Documentation) [EB/OL].[2011-11-05]. http://www.isi.edu/nsnam/ns/doc/index.html.

Improving GPSR Routing Protocol in Vehicular Ad Hoc Network

ZHANG Xiao-li1, ZHAO Qian2, ZHANG Tong2

(1.School of Computer, Xi’an Aeronautical University, Xi’an Shaanxi 710077, China;2. School of Computer Science and Engineering, Xi’an University of Technology, Xi’an Shaanxi 710048, China)

According to the characteristics of high mobility of nodes and vast frequent changes of network topology of ad hoc networks, we improved the existing GPSR protocol and given an improved routing protocol GPSR-SD (GPSR with Speed-density Direction) based on the GPSR protocol. The protocol combines with the speed-density model to estimate the information of density value of the road section that the vehicle node traveling, and considers both the vehicle node’s traveling speed and the vehicle density to select the next hop forwarding node,and then improves the forwarding right node selection to increase the communication link reliability. Thus, it reduced the cavitation caused by the node’s moving process, improved the average packet delivery rate and reduced the average end-to-end delay effectively. The simulation result on NS2 platform indicates that the GPSR-SD performs well.

ITS; vehicular ad hoc network; routing protocol; speed-density model; network simulation

2016-01-27

陕西省网络计算与安全技术重点实验室项目 ( 15JS078); 西安市科技计划资助项目(CXY1518(1))

张晓丽(1980-), 女，重庆人，硕士. (zhangxl319@126.com)

10.3969/j.issn.1002-0268.2016.09.017

U491, TP393

A

1002-0268(2016)09-0106-06