基于GPSR协议的一种改进车载网路由协议

张 好， 郑世慧， 杨 榆(北京邮电大学信息安全中心，北京100876)

0 引言

车载自组网(Vehicular Ad Hoc Network，VANET)是一种特殊的无线自组网。基本思想是在一定通信范围内的车辆自动地相互连接建立起一个移动的网络，用于交换各自信息(如车速、位置等)和车载传感器感知的数据。车载自组织网络在事故预警、保障交通安全、智能驾驶、收费站缴费、乘客办公与娱乐化及电子商务等很多方面有着良好的应用前景。近年来，随着车辆的飞速普及，车载网已经引起了越来越多的研究者，其路由协议也成为一个研究的热点。

通过改进传统的GPSR车载网路由协议，获得一种新的连通率较高，适应不同道路情况的新车载网路由协议。仿真测试表明，新协议能很好的适应车载网中车辆节点高速移动的特性，降低道路间障碍物对数据传输的影响，并且能够根据车流密度自动调节数据包的流向，从而提高路由协议的连通率。同时，新的路由协议也能够自动区分乡村高速公路、城市路况等不同的道路环境，并依据不同的路况采用不同的策略进行数据的传输。

1 GPSR协议

1．1 GPSR协议简介

GPSR(Greedy Perimeter Stateless Routing)路由协议是一种地理位置辅助路由协议。该协议中，每个节点需要在一定周期T内向一跳范围内的节点广播自己的位置信息，这样每个节点就知道自己和自己一跳范围内所有邻居节点的位置。节点在发送数据前不寻找路由，不保存路由表，移动节点直接根据包括自己、邻节点以及目的节点的位置信息制定数据转发决策，其数据转发模式有贪婪模式和周边模式两种。当一个节点收到数据分组时，首先采用的是贪婪模式转发，如果贪婪模式失败则转为周边模式转发。

图1所示为贪婪转发示意图。图中以节点x为中心的圆代表x的一跳通信范围，以节点z为中心的圆代表z的一跳通信范围。x收到一个要转发至z的数据包，首先查找邻居节点表中距离自身最远(即最接近目的节点)的邻居节点，发现y是满足条件的节点，因此将数据包转发给y。y重复贪婪转发模式直至数据包到达z。

图1 GPSR协议的贪婪模式

周边转发模式是指这样一种情况，当节点查找邻居节点表发现没有比自身更接近目的节点的邻居节点时，就按照右手规则转发分组。右手规则是指数据分组沿着路径转发，目的节点始终在转发路径的右侧。在图2中，由于x在其通信范围内的邻居节点中没有发现比它自身更接近于目的节点z的节点，贪婪转发失败，因此采用右手规则转发数据分组，其分组发送的路径是x-＞a-＞b-＞c-＞z。

图2 GPSR协议的周边模式

1．2 GPSR协议性能分析

在VANET中，通信节点处于高速移动状态，一条链路的有效时间非常短，所以一旦存储路由表，就必须不停地更新路由表，才能保证链路的有效性，这种方式在通信量和通信时间上的开销非常大，而GPSR协议采用边发包边找路的策略就能很好地避免上述问题，这使由于位置改变带来的丢包现象的可能性大大缩小。

但是，同时GPSR协议也存在着适用性不强、连通率不高的缺点。原因如下:

(1)GPSR协议将地图信息简单的当做一个二维图进行处理，而忽视三维空间中的道路间障碍物对数据传输的阻碍。

(2)GPSR协议根据存储在节点本地位置信息表的位置信息选择一跳范围内的最优节点作为数据传输的下一跳节点。每一个节点只能根据每隔T时间接收的广播信息记录一跳范围内其他位置节点的信息，也就是说S节点只能获取处于自己一跳范围内R节点T，2T，3T，…，NT时刻的位置信息。如果在NT+t(0＜t＜T)时刻S节点收到数据包，它只能根据NT时刻记录的位置信息选取一跳范围内的最优节点R，但是，如果S和R处于高速移动状态，那么NT+t时刻，最优节点R很有可能已经移出S节点的通信范围，在这种情况下S节点发出的数据包必定无法传送到R节点。

(3)在原始的GPSR协议中，一旦节点发现周围一跳范围内没有合适的的节点作为数据的下一跳，那么节点将会直接丢弃数据，从而导致数据的传输失败。

2 改进的GPSR协议

GPSR协议存在着适用性不强、连通率不高缺点。因此，为进一步提高协议的适用性，保证协议能够在各种道路环境下运行良好，提高协议的连通率，保证数据传输过程中的完整性，对GPSR路由协议进行改进，称新协议为NGPSR。

2．1 NGPSR路由协议

NGPSR协议流程如下:

角色:发送者 S、经过的路口节点 C1，C2，…，Ct、参与转发的车辆 N1，N2，…，Ns、接收者 R。

第一步:所有车辆节点产生一个记录自己位置信息和自身标示(如车牌号等)的广播数据包，每隔时间T向一跳范围内的车辆节点广播该数据包;节点收到一跳范围内的其他节点广播的位置信息后，将一跳范围内所有节点的标示信息和位置信息记录在本地位置信息表中。

第二步:发送者S产生一个数据包，通过GPS获取接收者R的位置信息，并从本地位置信息表中获取一跳范围内的所有节点信息。S节点判断自己一跳范围内是否存在目的节点(此时S节点并不是直接以位置信息表中的位置信息作为判断依据，而是先对一跳范围内的所有车辆节点进行位置预测，然后以预测的位置信息作为判断依据，文中所有的位置判断操作过程都是指先位置预测再判断)。若存在，则将数据发送给目的节点R;若不存在，S节点判断自己一跳范围内是否存在路口节点。若存在，则将数据发送给路口节点C1;若不存在，S节点判断自己一跳范围内是否存在比自己更接近目的节点的车辆节点。若存在，则用贪婪模式将数据转发给自己一跳范围内的车辆节点N1;若不存在，则用周边转发模式将数据转发给自己一跳范围内的车辆节点N1。

第三步:路口节点Ci(1≤i≤t)收到数据包后，Ci节点判断自己一跳范围内是否存在目的节点R，若存在，则将数据发送给目的节点R;若不存在，Ci节点通过GPS获得离目标节点R最近的路口节点的信息，判断自己是不是离目标节点R最近的路口节点。若Ci节点是离目的节点R最近的路口节点，则将数据转发给行驶在自己和目标节点所处路上离路口节点Ci一跳范围内的车辆节点Nj(1≤j≤s);若Ci节点不是离目标节点R最近的路口节点，Ci获取自己所处的几条道路的车流密度信息，判断几条道路离目的节点R的距离。综合这2个信息，选择一条道路，并将数据转发到选定的这条道路上处在Ci节点一条范围内的车辆节点 Nj(1≤j≤s)。

第四步:车辆节点Nj(1≤j≤s)收到数据包后，Nj节点判断自己一跳范围内是否存在目的节点R。若存在，则将数据发送给目的节点R;若不存在，Nj节点判断自己一跳范围内是否存在路口节点。若存在，则将数据发送给路口节点Ci+1;若不存在，Nj节点自己一跳范围内是否存在比自己更接近目的节点的车辆节点。若存在，则用贪婪模式将数据转发给自己一跳范围内的车辆节点Nj+1;若不存在，则用周边转发模式将数据转发给自己一跳范围内的车辆节点Nj+1。

第五步:接收者R收到发送者S发送的数据。有以下几种情况。

在第一步的操作中就R收到数据，此时t=0，s=0，没有参与转发的路口节点和参与转发的中间车辆节点，S直接将数据发送给R;

在第二步的操作中就R收到数据，此时t≥1，s≥0，路口节点参与数据的转发，目标节点在路口节点Ct一跳范围内;

在第三步的操作中就R收到数据，此时t＞0，s＞=1，车辆节点参与数据的转发，数据经过多跳到达接收者R节点。

图3和图4是具体的NGPSR协议流程图。

图3 模式一车辆节点协议流程

图4 模式二路口节点协议流程

2．2 NGPSR协议的改进

相对于原始GPSR协议，新协议有4个方面的改进。

(1)增加位置预测功能。可以通过节点存储在本地位置信息表中的数据预测节点在t时刻的位置。S节点选取接收到的R节点最近两次的广播信息，获取R节点T时刻前和2T时刻前的位置信息:(x1，y1)，(x2，y2)。通过这两个位置信息，S节点可以计算R节点的速度

运动方向是

因此，节点S可以利用公式获取R节点t时间后的位置信息

以此类推，节点S可以预判其通信范围内所有节点的运动方向及与节点S的距离，进而做出更加可靠有效的转发节点选择。

(2)引入路口节点，使路由协议由无中心的转发模式升级为分层次的无中心转发模式。路口节点负责将一条道路上的数据转发至相邻的道路，起数据中转站的作用，保证数据只在一条路上进行传输，避免数据由一条路直接向另一条路传输时由于路口障碍物的阻挡导致的连通率下降的情况。

(3)考虑车流密度对连通率的影响。NGPSR在路口节点处统计车流密度，并根据车流密度选择数据的传输路径，避免数据包被转发到封闭的小网络中，从而提高连通率。

采用下面的方法统计车流密度:处于一条路两端的两个路口节点A，B彼此定期(间隔时间T)向对方发送一个特殊格式数据包，这条路上的车辆节点收到这种格式的数据包后，把自己存储在本地的邻节点的信息添加到这个特殊格式数据包的数据段部分，然后再通过GPSR协议转发数据包，直至数据包发送到目的地。当A节点收到B节点发来的数据包，A统计该数据包数据段中的节点信息(出现多少个不同的车辆节点)。

(4)NGPSR协议对传输数据进行缓存。一旦节点A发现自己一条范围内没有任何节点可以传输数据，那么就在本地缓存该数据;T时间后，A节点再次在本地位置信息表中选择合适的节点作为下一个传输节点，若仍然没有合适的节点，就继续缓存该数据;若直到3T时间后仍然没有将数据传输出去，则丢弃数据包。在拓扑高速变化的车载网中，数据缓存能够有效地降低数据丢包的概率。

3 仿真结果

图5 实验所用的城市地图信息

图6 实验所用的乡村高速地图信息

图5中有12条道路和4个路口，每一条道路的长度为5 KM;在每一个路口处都有一个路口节点;图6中有一条长度为10 KM的道路。

在NS2软件中分别模拟城市道路和乡村高速公路进行5个实验，前2个实验分析制约GPSR协议性能的几个因素，后3个实验比较GPSR协议和NGPSR协议的性能。

3．1 速度对连通率的影响

实验过程:在乡村高速公路的环境下，针对GPSR协议，分别测量在不同车速情况下(10 m/s，20 m/s，30 m/s，40 m/s)下的连通率。实验结果如图7所示。

图7 乡村高速公路情况下不同速度下的连通率

图7可以看出，随着节点移动速度的增加，车载网连通率不断下降。这是由于随着速度的增大，目标节点R在传输时间内移出发送者S的通信范围的概率也逐渐增大，从而导致连通率随着速度的增加而下降。从实验中可以看出车辆节点的高移动性是GPSR协议性能的一个重要制约因素。

3．2 路口障碍物对连通率的影响

实验过程:在乡村高速公路和城市道路的环境下，针对 GPSR协议，分别测量在不同车速情况下(10 m/s，20 m/s，30 m/s，40 m/s)下的连通率。实验结果如图8所示。

图8 两种道路环境下不同车速的连通率对比

从图8中可以看出，在同样的车流密度和速度的前提下，乡村高速公路的连通率明显高于城市道路道路时的连通率。通过测试得到的数据和对GPSR路由协议的分析发现，在这两种情况下连通率出现差异的主要原因在于在城市道路上，数据的传输会出现换路。而在换路的过程中，由于路与路之间存在着大量的障碍物，导致传输受到阻碍，在这种情况下很有可能出现丢包。因此，实验中可以看出路口障碍物是GPSR协议性能的重要制约因素。

3．3 乡村道路下两种协议连通率比较

图9 乡村高速公路GPSR和NGPSR算法的连通率

实验过程:在乡村高速公路的环境下，针对原始算法GPSR和改进算法NGPSR这两个算法，分别测量在不同车速情况下(10 m/s，20 m/s，30 m/s，40 m/s)下的连通率。实验结果如图9所示。

从图9可以看出，NGPSR协议的连通率不管在哪种速度条件下都要高于GPSR协议，并且随着车辆节点速度的增大这种趋势也越来越明显。同时，随着车速的加快，两种算法的连通率都会下降，但是NGPSR算法下降的较为缓慢，GPSR算法则下降得较快。这是因为，在引入位置预测功能和数据缓存功能后，即使出现目标接收节点不在通信范围内的情况，NGPSR协议也能在保证连通率的情况下处理数据，而GPSR协议在这些情况下直接导致数据的丢包，因此NGPSR协议的连通率较高;而随着速度的加快，接收者跑出发送者一跳范围的概率随之增大，所以GPSR算法的连通率下降得很快;另一方面随着速度的加快，对车辆位置的预测的准确性也随之下降，所以NGPSR算法的连通率也缓慢下降。因此可以看出，引入位置预测功能和数据缓存功能后，能够在一定程度上提高协议的连通率。

3．4 城市道路下两种协议连通率比较

(1)实验过程:在车流密度适中的城市道路环境下，针对GPSR和NGPSR这两个协议，分别测量在不同车速情况下(10 m/s，20 m/s，30 m/s，40 m/s)下的连通率。实验结果如图10所示。

图10 城市道路GPSR和NGPSR算法的连通率

在车流密度适中的情况下，在城市道路中，GPSR和NGPSR的主要区别在于:在这种情况下，NGPSR协议通过引入路口节点避免了一条路上的车辆节点直接向另一条路上的车辆节点发送数据而导致传输被路口障碍物中断的情况出现。从图10可以看出，NGPSR协议的连通率明显高于GPSR协议。因此可以看出，引入路口节点后，能够在一定程度上提高协议的连通率。

(2)实验过程:在道路1上选取一个车辆节点作为发送者，在道路12上选取一个车辆节点作为接收者(确保数据包经过路口节点1，并在道路2和道路8之间做出选择)。分别调整道路8的车流密度为每5000 m距离有(10/20/30/40)辆车，测出NGPSR协议和GPSR协议在这些不同的情况下的连通率。实验结果如图11所示。

图11 不同车流密度下GPSR和NGPSR连通率对比

通过图11发现，NGPSR连通率总是保持在一个很高额水准上，而GPSR的连通率则随着道路8的车流密度的增大而上升。这是因为，改进协议在选路策略中考虑了车流密度这一因素，因而总能确保数据包向车流密度较大的道路2进行转发，而道路2的车流密度适中，能够确保数据包的良好转发;而原始协议，当数据包被转发至临近路口节点1的车辆节点时，通过贪婪模式和周边模式选取离目的节点更近的道路8中的车辆节点作为转发节点，当道路8的车流密度为每5000 m距离有10辆车时，难以保证每一个车辆节点通信范围内存在其他车辆节点，因此连通率极低，随着道路8车流密度的增大，连通率上升。因此说明改进协议能够避免数据包进入车流密度比较小的道路，从而实现连通率的提升。

从实验中可以看到不管是在乡村高速公路环境下还是在城市道路环境下，NGPSR协议的性能都要明显优于GPSR协议，而且还分析了NGPSR协议性能优于GPSR协议的原因，这也进一步从理论上证明NGPSR协议的优越性。

4 结束语

通过对比分析现有的VANET路由协议的优缺点，选择了通信量小、通信时间短、无需建立路由GPSR的路由协议作为基础，通过理论分析和实验，找出车辆节点的高移动性、数据在传输的过程中换路、车流密度这些制约GPSR协议性能的因素，并针对这几个制约因素对GPSR协议进行改进，在GPSR协议的基础上添加位置预测功能和数据缓存功能，并引入路口节点、考虑车流密度，提出一种新的适应性强、连通率高的NGPSR协议，最后通过大量的实验数据证明NGPSR协议不管实在城市道路环境下还是在乡村高速公路环境下的性能都明显优于GPSR。

［1］ KARPB，KUNGHT.GPSR:greedy perimeter stateless routing for wireless networks［C］.MobiCom:Proceedings of the 6th Annual International Conference Oil Mobile Computing And Networking.New York，USA，2000.

［2］ Tsu-Wei Chen.Global State Routing:A new routing scheme for Ad-hoc wireless networks［C］.Proc IEEE ICC’98.1998.

［3］ C.E.PERKINS，BHAGWAT P.Highly Damie Destination-Sequenced Distance-Vector Routing(DSDV)for Mobile Computers［C］.In:Proceedings of the ACM SIGCOMM＇94 Conference on Communications Architectures，Protocols and Applications，London，UK，August 1994:234-244.

［4］ Johnson D B，Maltz D A.Dynamic source routing in Ad Hoc wireless networks［C］.Proc of The International Series in Engineering and Computer Science.New York:Kluwer Academic Publishers，1996:153-181.

［5］ Perkins C，Belding-Royer E，Das.Ad Hoc On-Demand Distance Vector(AODV)Routing［C］.IETF RFC 3561，2003.

［6］ 戴其进.车载网的路由协议研究［D］.北京:北京邮电大学，2013.

［7］ 张帆.城市场景下车载自组网中GPSR路由协议的研究［D］.长春:吉林大学，2011.

［8］ 朱二华.一种自适应的城市场景VANET路由协议［D］.广州:广州华南师范大学，2010.

［9］ 刘江永，张洋祥，韩鹏.不同场景中VANET路由协议的仿真研究［J］.计算机工程与应用，2009(18).

［10］ 王健，刘衍珩，焦玉.VANETs信任传播建模［J］.北京邮电大学学报，2009(S1).

［11］ 常促宇，向勇，史美林.车载自组网的现状与发展［J］.通信学报，2007(11).