VANET场景下的GPSR－R路由算法

李 超， 韩江洪，2， 魏振春，2， 卫 星，2

（1.合肥工业大学 计算机与信息学院，安徽 合肥 230009；2.安全关键工业测控技术教育部工程研究中心，安徽 合肥 230009）

VANET场景下的GPSR－R路由算法

李 超1， 韩江洪1，2， 魏振春1，2， 卫 星1，2

（1.合肥工业大学 计算机与信息学院，安徽 合肥 230009；2.安全关键工业测控技术教育部工程研究中心，安徽 合肥 230009）

路由选择是实现VANET的关键技术之一，没有合适而高效的路由选择算法，VANET就无法工作。由于路由在长距离通信时多跳易断裂，通信链路只需满足通信需求即可。文章对GPSR路由协议进行了改进，提出了VANET场景下的GPSR路由算法：GPSR－R。GPSR－R根据移动节点间链路建立的网络需求进行综合考虑，充分利用不稳定但满足需求的路由完成信息的传递。分析结果表明，GPSR－R在数据包传递率、丢包率方面优于GPSR和GPSR－AD。

GPSR－R算法；通信需求；VANET场景

随着“车联网”概念的提出，在如何进一步发展智能交通系统ITS（intelligent transport system）应用的问题上，世界各国不约而同地将注意力集中到车载通信系统上。近年来，将移动ad hoc自组网技术应用于车辆，组成ad hoc网络VANET（vehicular ad hoc networks）以实现车辆间的信息交互已经成为一个研究热点［1－4］。

路由协议处于网络体系结构的核心位置，为2个节点建立交换的路径是网络性能的重要影响因素之一。VANET作为移动自组网的一种特殊的形式，有其自身的特点，若直接采用传统的移动自组网路由协议则难以取得良好的网络性能。

在VANET中，研究较多的有2类：基于拓扑的路由协议和基于位置的路由协议。AODV是最具代表性的基于拓扑的路由协议；GPSR是最具代表性的基于位置的路由协议。GPSR路由算法在查找过程中，为了避免空洞的产生，利用右手法则沿空洞周围传输来解决此问题，采用周边邻居节点保存路由信息，是一个无状态的协议；在右手法则寻找路由的过程中，抛弃了备用节点，因为这些节点在链路和路由跳数上不是最优节点。

在GPSR路由协议中，节点下一跳选择采用贪婪转发方式进行信息的传递。贪婪转发方式在网络节点密度很高的情况下具有传输时延小、转发成功率高的特点，但是在传递距离长、路由需要多跳的情况下，贪婪转发会由于通信空洞的存在而导致分组转发失败。

本文提出一种VANET场景下的路由选择算法GPSR－R，在路由的寻找过程中参考节点的网络需求，充分利用不稳定信道来完成任务，既满足了消息传输的基本需要，也避免了在长距离传输中路由由于多跳信息传递率下降的情形。

1 VANET模型

对VANET作出如下假设［7］：

（1）车辆能获知自己的速度、加速度、位置和方位角。

（2）车辆都有无线通信接口，通信距离为300～1 000 m，VANET为一个平面网络。

（3）在VANET中车辆的能量被认为是不会耗尽的，且通信消耗的能量忽略不计。

蒸发法的原理是从液态转化为气态，利用产生的热能将液体蒸发，最后再回收冷却水蒸汽的方法，此种方法的优势是得到的淡水水质较好。目前，海水脱盐淡化技术经过发展演化的蒸发法脱盐技术被广泛应用于工业生产中[15]。多效蒸馏法是一项20世纪中期重要的脱盐技术，虽然工艺比较成熟并且运行稳定，然而存在一些问题如能耗高、设备易腐蚀结垢等缺点[16]。20世纪70年代末,以色列研发了低温多效蒸馏技术，有效缓解了多效蒸馏法的缺点[17]。利用多效蒸馏法可以获得较大的产水量，但是高效率也代表着更高的单位产水量的成本和投资费用。郭卫平[18]研究表明，对于成分复杂以及污染性强的污染物，不适合用膜法脱盐处理。

（4）在VANET中，车辆通过周期性广播的状态信息（如位置、速度、加速度等）实现对周围车辆的感知。

以上假设反映了VANET的本质特性。

2 问题描述

某十字路口情形如图1所示，虚线圈表示车辆的通信范围，车辆1为源节点，车辆2为目的节点。在图示时刻，车辆2即将左转，进入与车辆1行驶公路垂直的公路；一方面，车辆1和车辆2之间可以进行通信，另一方面，可以借助车辆3作为转发节点构建更为稳定的路由。但是由于信息传递时间很短，不需要构建很稳定的路由，所以车辆1可以直接向车辆2发送信息。

图1 十字路口情形

某线状公路情形如图2所示，虚线圈表示车的通信范围，车辆1为源节点，车辆n为目的节点，在图示时刻，车辆1和2中间有很多车辆，但是车辆2处于车辆1通信范围能覆盖到的最远的地方，车辆1和2之间建立的通信链路虽然不是很稳定，但也能满足通信的需求；同理可以选择车辆3作为车辆2通信的下一车辆，依次传递，直到消息发送到车辆n，通信完成。通过这样的方式构建的路由虽然不是很稳定，但是可以满足通信的需求。

图2 线状公路情形

车辆位置动态路由如图3所示。车辆1为源节点，车辆4为目的节点，2个虚线圈分别表示车辆1和2的通信范围。当车辆1向车辆4发送数据时有路由1→2→3→4和1→2→4可以选择。由图3可知，车辆4在下一时刻即将驶离车辆2的通信范围，但是考虑到不稳定信道能满足通信需求即可，链路1→2→4可以作为选择。

在路由选择中，将对网络通信速度和信号衰减等进行评估，以上节点在计算理论可行的最大通信速率时，可能成为最优的路由节点。在进行上述路由选择时均未考虑需求所要持续的时间，仅仅选择出一条可通信的路由。

图3 车辆位置动态路由图

GPSR－R算法综合考虑车辆的行驶速度、相对位置、行车方位等来评估行车路由存活时间，根据目的节点发送数据的应用需求，依靠车间通信速率得到需求时间，建立GPSR路由改进算法。

3 VANET场景下的GPSR－R算法

3.1 GPSR路由协议

GPSR路由协议使用贪婪转发算法建立路由。贪婪转发算法是选择邻居节点中距离目的节点最近的作为下一跳路由转发节点［8］。协议流程图如图4所示。

3.2 邻居路由表更新策略

源车辆把Hello数据包预先传递给其一跳的邻居车辆，一方面，移动车辆能追踪每个车辆的位置，另一方面，数据包也告诉其在邻居路由表中当前车辆的位置，这样就能粗略地估计出中间邻居车辆。

Hello数据包如图5所示。

图5 Hello数据包格式

数据包格式中，ID为车辆的ID号；X、Y为当前车辆所处平面中的坐标位置；vx、vy为车辆在X和Y方向上的速度；F为一个标志位；θx、θy分别为车辆行驶的方位角；r为车辆的通信半径。

经过时间t后，车辆准确的位置信息可以通过传递Hello数据包进行预测。如果同样车辆的信息被接收，那么在同一时间对应数据包中位置信息将被更新。通过速度来估计周围邻居车辆在一段时间以后的位置，每一辆车都能确定在通信范围内可通信车辆的数量；如果一辆车当前位置在源车辆通信范围内未被找到，那么这辆车将不会成为一个邻居车辆。

因此，该策略用Hello数据包来帮助源车辆和下一跳邻居车辆预先进行信息交换。基于从Hello数据包中获取的信息，每个车辆都能定时更新它自身邻居路由表中的信息。

3.3 GPSR－R算法的主要思想

GPSR－R算法是基于网络需求的GPSR路由选择算法，将每个车辆作为一个移动的节点，每个节点只维护其发射范围内的节点的位置、行驶速度、方位角信息；通过网络收敛、贪婪转发、路径优化进行筛选，并将节点通信时间与路由维护时间进行比较，自动选择出只需满足通信需求而对链路稳定性要求不高的路由。

3.3.1 路由存活时间RMT计算模型

路由存活时间RMT（routing maintenance time）是指从源车辆1到目的车辆n的路由维护时间。假设每个节点对信号的传输能力相同，则任意2个相邻节点的距离小于传输半径时，都可以认为节点间是保持连接的。

如果考虑2辆车i和j（1≤i≤j≤n），它们的通信半径为r，速度分别为vi和vj，位置分别为（xi，yi）和（xj，yj），速度的方位角分别为θi和θj，则这2辆车之间链路维护时间为：

3.3.2 节点间通信时间T计算模型

节点通信时间是指信息从1→n传递所需要的时间，主要包括由节点到下一跳发送所需的时间和在每一个路由节点上的等待时间；计算这2个时间，再将从节点1→2→…→n传递的时间片累加，即可得到总时间。

若T（i，j）表示数据从节点i→j传输所需的时间，S（i，j）表示数据在j点停留等待转发的时间，则有：

其中，S（i，j）＝j中待传输数据堆栈长度×获取时间片需要等待的时间／一次发送长度。

其中，G为数据包大小；C（i，j）为i→j的传输速率。

信道传输速率C＝W lb2（1＋SINR），SINR＝Pre／N0，W 为常量，SINR为信噪比，N0为无线通信中的固有噪声，Pre为接收节点j收到i的信号强度。

时间片等待时间由于媒体接入方式不同而有所不同，如果对此时间评估，与实际情况严重不符。路由选择上采用的是按需执行，因此在每个节点开始承担转发任务时，可以估计到自己能够得到的时间片的时间，再逐步累加进行预估，作为参考数据。

3.4 GPSR－R算法描述

GPSR－R路由查找采用以下步骤：

（1）在群体节点中，一定周期Δt内进行一次位置更新。

（2）节点1向节点n发起一个服务请求，先发送RREQ路由请求数据包，请求信息中包含发起车辆的应用请求所需的通信时间T。

（3）节点1周围的节点收到信息后，首先要判断本节点是否转发过此数据包，若未转发过，则将下一节点设置为邻居节点，同时将自身现在维持的链路堆栈信息加入RREQ数据包中，查找自己通信范围内的节点位置信息，将RREQ转发给下一节点。

（4）当查找完成后，若节点1信息传递到节点n所需的通信时间T小于路由维护时间RMT，则选择该路由；否则转至步骤（1），直到RREQ发送到目标节点得到路由，做出回应。

在路由节点选择方向上采用以下办法进行初步判定：① 当前节点累计的传输速率已经低于预定阈值比例a，停止转发该请求；②当前节点与上一节点链路维护时间低于应用需求时间的，停止转发该请求。

GPSR－R算法路由选择中，当节点收到一个RREQ请求时，为了避免形成循环链路，需解包检验是否接收过此请求。

为了避免形成“空洞”，路由推进路径如图6所示。节点A收到RREQ数据包，目的节点为D；车A坐标为（0，0），R为A的无线通信范围；收到转发数据包的请求后，A向通信范围内的车辆发送转发请求；B、F节点首先收到，B、F再次转发时，需要做出判断，如果链路F已经处理过此请求信息，则F对B的转发不做任何处理。

图6 路由推进路径示意图

4 仿真实验与结果分析

本文采用台湾交通大学研制的NCTUns软件，它将交通仿真和网络仿真紧密耦合在一个模块中，提供单一的车辆网络环境［9］。对改进算法GPSR－R和GPSR路由算法以及GPSR－AD算法进行仿真实验，为了更准确地说明本文所提出的路由改进算法的优势，在实验过程中，选取车辆间的距离作为横坐标，对其数据包传递成功率以及丢包率进行比较，实验结果表明，本文改进算法的数据包传递率以及丢包率要优于GPSR路由算法和GPSR－AD算法。

仿真场景为宽50 m、长3 000 m的公路，车辆移动速度范围为20～30 m／s，MAC层协议为802.11，车辆通信覆盖半径为300 m，车辆节点数为1 000，要传递数据包大小为512 B，仿真时间为150 s。GPSR－R和 GPSR、GPSR－AD算法性能比较如图7所示。

由图7a可知，随着车辆间距的增加，3种算法的数据包传递成功率均逐渐减小，GPSR－R算法的数据包传递成功率比GPSR和GPSR－AD算法下降得更为缓慢。这是因为GPSR具有贪婪转发的特点，路由跳数相对较少，当距离增大以后，数据包传递的成功率就会显著降低；GPSRAD考虑了距离和角度的关系，所以下降并没有GPSR算法大；而GPSR－R则考虑了路由跳数较多的因素，通过算法的改进，减小因为距离增大而对数据包传递成功率的影响。

由图7b可知，随着车辆间距的增加，3种算法在丢包率方面均逐渐上升，GPSR－R的丢包率上升缓慢，而GPSR－AD和GPSR算法则上升较快。这是因为在长距离传输中，GPSR－R算法考虑了满足传输需求的通道也可以作为传输信道，减少了路由开销，提高了效率，使得丢包率上升并不明显。

图7 GPSR－R和 GPSR、GPSR－AD算法性能比较

5 结束语

针对GPSR协议应用于车联网实际场景时因传输距离长而造成数据传递率下降的情形，本文提出了VANET场景下的GPSR路由改进算法GPSR－R。GPSR－R算法充分利用不稳定但满足需求的路由完成信息的传递。实验结果表明，车辆间数据在长距离传输情形下，GPSR－R在数据包传递率、丢包率方面要优于GPSR和GPSRAD。

［1］Fang S，Luo T.A novel two－timer－based broadcast routing algorithm for vehicular Ad－hoc Networks［C］／／International Conference on Green Computing and Communications（GreenCom）and IEEE Internet of Things（iThings）and IEEE Cyber，Physical and Social Computing（CPSCom），2013：1518－1522.

［2］Sou S I，Lee Y.SCB：store－carry－broadcast scheme for message dissemination in sparse VANET［C］／／Vehicular Technology Conference（VTC Spring），Yokohama，2012：1－5.

［3］Rak J.Providing differentiated levels of service availability in VANET communications［J］.Communications Letters，IEEE，2013，17（7）：1380－1383.

［4］胡小建，王景刚.云物流服务及其协作机制研究［J］.合肥工业大学学报：自然科学版，2014，37（5）：631－635.

［5］李道全，刘海燕，曹齐光，等.基于地理位置的路由算法：GPSR－AD［J］.计算机应用，2009，29（12）：3215－3217.

［6］Dhurandher S K，Misra S，Obaidat M S，et al.Efficient angular routing protocol for inter－vehicular communication in vehicular ad hoc networks［J］.Communications，IET，2010，4（7）：826－836.

［7］陈 振，韩江洪，刘征宇.基于VANET分簇的车辆碰撞警告信息传输［J］.电子测量与仪器学报，2013，27（5）：396－401.

［8］Kyunghwik K，Wonjun L.MBAL：a mobile beacon－assisted localization scheme for wireless sensor networks［C］／／Proceedings of 16th International Conference on Conputer Communications and Networks，2007：57－62.

［9］王丽娟，梁海涛，秦建敏，等.贪婪周边无状态路由转发算法GPSR的分析及改进［J］.太原理工大学学报，2012，43（5）：587－590.

GPSR－R routing algorithm in VANET scenario

LI Chao1， HAN Jiang－hong1，2， WEI Zhen－chun1，2， WEI Xing1，2

（1.School of Computer and Information，Hefei University of Technology，Hefei 230009，China；2.Engineering Research Center of Safety Critical Industrial Measurement and Control Technology of Ministry of Education，Hefei 230009，China）

Routing is a key technology of vehicular ad hoc networks（VANET）.VANET will not work without appropriate and efficient routing algorithm.Because the long－distance multi－hop routing is breakable，the communication link only need to satisfy the basic need of communication.In this paper，a GPSR－R routing algorithm in VANET scenario is proposed to make an improvement in GPSR routing protocol.GPSR－R takes comprehensive consideration of network requirements which is built up by the mobile nodes，and makes full advantage of routing which is unstable but can complete transmission of information.The simulation results show that GPSR－R does better than GPSR and GPSRAD in packet delivery rate and packet loss rate.

GPSR－R algorithm；basic need of communication；vehicular ad hoc networks（VANET）scenario

TP393.02

A

1003－5060（2015）02－0181－05

10.3969／j.issn.1003－5060.2015.02.009

2014－02－17；

2014－06－01

国家自然科学基金资助项目（61370088）；高等学校博士学科点专项科研基金资助项目（20100111110004）和安徽省自然科学基金资助项目（1208085QF113）

李 超（1990－），男，浙江金华人，合肥工业大学硕士生；

韩江洪（1954－），男，安徽合肥人，合肥工业大学教授，博士生导师.

（责任编辑 胡亚敏）