自组织车联网中GPSR路由协议的研究进展

黄文静

(重庆交通大学 信息科学与工程学院，重庆 400074)

综述与评论

自组织车联网中GPSR路由协议的研究进展

黄文静

(重庆交通大学 信息科学与工程学院，重庆 400074)

由于贪婪周边无状态路由(GPSR)对于拓扑结构频繁变化的自组织车联网(VANETs)具有最适性，为此，针对GPSR提出了许多改进协议。首先对VANETs网络层路由协议进行分类比较，然后分析和总结近年来基于位置路由协议的核心路由机制和优缺点，重点分析典型的基于位置的路由协议GPSR在城市场景中存在的问题。最后，提出了GPSR未来可能的研究策略和发展方向。

自组织车联网； 路由协议； 贪婪周边无状态路由

0 引 言

近年来，由于无线网络技术的迅猛发展和交通智能化的需求，自组织车联网(VANETs)这一专门为汽车间通信设计的自组织网络受到了广泛的关注。该网络不仅有助于改善交通拥塞问题，还能进行紧急事件处理、辅助驾驶、交通信息共享、娱乐等。在VANETs发挥巨大作用的同时VANETs路由协议为其提供重要的数据通信支持，因此，路由协议很大程度上决定了VANETs的性能[1]。基于地理位置贪婪周边无状态路由(GPSR)协议算法较为简单,不需要储存维护路由表,网络开销小,且对于车辆高速移动的拓扑网络具有更好的可扩展性和适应性。但是在城市交通环境应用中，GPSR仍然存在很多不足和缺陷。总之，针对GPSR路由协议在城市交通环境下的研究是一个挑战与机遇的共存的过程，受到了广大学者的关注。

本文主要是对典型的VANETs层路由协议进行归纳分类，总结基于位置路由协议的优缺点，并重点对基于位置的GPSR协议在城市交通环境下存在的问题进行分类，同时指出可能研究的策略和未来发展方向，为GPSR协议在城市交通环境下的应用研究提供广阔的视角。

1 VANETs协议分类

VANETs路由协议根据数据包目的节点数的不同可分为单播路由、广播路由、多播路由三类,其具体分类如图1。单播路由协议是将数据包一对一地从源节点转发到目的节点。目前，大体可分为基于拓扑的路由协议、基于位置的路由协议和基于电子地图的路由协议三类。早期的自组织网络路由基本上都是基于拓扑的路由协议，网络中的节点通过周期性地交互信息得到其他节点的信息，进而转发数据包。这类路由协议大体可以分为先应式、反应式和混合式路由协议。先应式路由中无论当前是否要求通信，每个节点都会周期性地广播路由分组、交换路由信息、维护路由表。典型的先应式路由代表是DSDV协议。相对于先应式路由，按需路由协议根据源节点是否需要获得目的节点路由才进行洪泛广播请求分组，因此，降低了路由开销。按需路由协议的典型代表是AODV，DSR。文献[2]中通过对3种路由协议(DSDV,AOMDV,AODV)在搭建的真实场景中进行仿真和性能分析，得到DSDV这类先应式路由协议周期性地广播信息，占用带宽过多，影响数据的传输，而AODV使用洪泛发现路由将产生大量的冗余，对于规模越大的网络，冗余现象越明显。因此，效果良好的传统自组织网路由协议不一定适宜拓扑频繁变化的VANETs。

图1 VANETs路由协议分类Fig 1 Classification of VANETs routing protocol

与传统的自组织路由协议相比，基于位置的路由协议不需要储存和维护路由，节点利用GPS等方法获取自己的位置，通过“位置服务”和分组转发策略来获取信宿节点的位置和选择下一跳。针对高速移动的城市场景，基于位置的路由协议具有较好的性能。其中基于位置路由协议的典型代表是由Karp Brad, Kung H T 于2000年提出的GPSR协议[3],该协议初始化是根据贪婪法则转发数据包，当贪婪转发陷入局部优化时采用边界转发。文献[4]对GPSR基于NS3进行深入的研究分析，并分别对贪婪模型和恢复模型进行仿真，验证该算法确实能够选择正确的路径。文献[5]提出了通过计算源、目的节点之间的距离，根据Dijkstra算法选择最小路径的路由协议GSR。虽然GSR减少了网络开销和路径，但是没有考虑实际的交通环境中的速度和车流密度。Lochert C，Mauve M 于2005年提出了改进的GPCR[6],该协议将GPSR的贪婪转发方式改进为受限的贪婪转发，当转发节点发现转发方向存在节点处于十字路口时，直接将数据包转发给该节点，而不执行贪婪转发；反之，仍然进行贪婪转发。虽然GPCR更适应于城市交通环境，具有较高的交付率，但是路径和延迟有所增加。Seet B C，Liu G等人在2004年提出的A-STAR路由协议为每条路径分配一个与公交线路数量呈反比的权值，根据Dijkstra算法选择最短路径，当出现局部优化时，重新计算新的最短路径和地理标识该点不参与计算。该协议在选择路径时参考了车辆密度因素，提高了数据投递率，但是这里的车辆密度是统计值而不是实时的，因此，不具有实时性和准确性[7]。针对A-STAR实时性差的问题进行改进提出了GyTAR路由协议，根据各个路段实时车流密度选取路径，进而通过速度向量预测下一跳的位置进行转发数据包。该协议有效地解决了实时性问题，而且进一步提高了数据投递率，但是对外界提高车流信息服务要求较高，较适宜于城市场景[8，9]。基于位置的路由协议的分析比较如表1。

根据VANETs的网络特点，未来的VANETs路由协议的方向应该是位置与电子地图相结合的基于地图的路由协议，根据电子地图获取整个网络的交通情况做出合理、高效的路由选择。

表1 VANETs基于地理位置路由协议的分析比较Tab 1 Analysis and comparison of routing protocol based on geographic location for VANETs

2 城市交通环境下GPSR协议存在问题

基于位置的典型路由协议GPSR使用地理位置信息，通过贪婪算法获得局部最优解，同时采用边界转发机制来解决贪婪算法引起的最佳主机问题，其主要流程如图2。

图2 GPSR流程图Fig 2 Flow chart of GPSR

虽然GPSR协议具有算法简单、不需要储存和维护路由表开销小等优点，但是在城市交通环境中仍然存在着一些问题。针对基于位置典型的GPSR协议存在的问题，国内外学者都提出的一些相应的改进方案。

2.1 解决空洞问题时右手法则开销大

在遇到空洞问题时，GPSR协议会启动边界转发模式，根据右手法则会出现盲目绕路和三角形问题。文献[10]提出了分段贪婪路由算法，该算法选取一个与目标节点之间直接贪婪可达的节点作为一个中间目标节点，不断迭代直到找到某个中间节点使得源节点到该中间目标节点之间是直接贪婪可达的。它克服了周边转发引起的绕路和三角形问题，减少了路由和开销。文献[11]提出了一种新的路由协议，该协议将每个路段分成不同的块并在每个交叉路口设置锚点，当节点发现当前路径上存在空洞则通过锚点选择剩下块中相对目的节点最近的块内节点进行转发，在块内则根据节点的速度和位置选择下一跳，它同时解决了空洞问题和链路稳定的问题。针对右手法则开销大，文献[12]提出了双手法则，该法则分别根据左手和右手选择2个节点，若两节点是同一节点，则直接转发给该节点；否则，选择距离目的节点近的节点作为下一跳。针对文献[12]在处理空洞问题采取左、右手法则引起的绕路和开销较大问题，提出了基于节点权重的机制，该机制通过选择由该节点的距离、丢包率和转发成功率共同决定的节点权重值大的作为下一跳。虽然该机制提高了交付率，但计算量太大，需要的信息繁多[13]。文献[14]提出了另一种解决问题的思想，在面对空洞问题时不是立即平面化采用边界转发，而是将节点退回前一个转发点在剩下的节点中重新选择下一跳，直至没有遇到空洞。

2.2 自适应性差

针对GPSR在不同场景中无法采取正确的转发模式导致数据包丢失的问题，文献[15]根据车流密度自适应采取不同转发机制，在稀疏模式下，容易出现空洞问题，从而采用基于稳定的路由协议机制。文献[16]根据格林布尔茨的速度—密度线性关系式，通过计算车辆的平均速度得到实时车流量密度信息，从而选择最佳路径。基于自适应选路策略的VANETs路由协议ASVP[17]针对 VANETs的链路频断性，提出了一种自适应路由协议,该协议引入携带—转发机制使协议能够适用于间歇性连接的延迟容忍网络，通过对道路模型分析计算，获得路段连通性度量指标用于选取最优路径。

2.3 容错性差

文献[18]提到GPSR协议是在假设每个节点都是无故障的情况下，但是在实际交通情况下是不可能的，而容错处理有助于减少能量消耗、维持稳定路径。因此，针对GPSR协议进行了改进，得到了EFGPSR，该协议主要分为错误检测、平面化、高效贪婪转发和高效周边转发4个阶段。改进的协议在网络寿命、成功交付率方面都有所改善。文献[19]介绍的故障容错能提高无线传感器网络的稳定性和可靠性，并总结网络层容错技术主要分为多路由传输、纠删编码/网络编码、数据重传机制、跨层协同优化与复合容错和仿生智能容错等。文献[20]指出引起链路断裂的因素主要有邻居节点位置不定移动出了传播范围或者中间节点出现故障。而目前针对链路断裂的处理方法包括计算链路稳定度、多条路径等。针对大多数基于稳定的路由算法都没有考虑对节点的保护，本文提出了一种将节点和链路保护相结合提高稳定度的多路径节点保护路由协议GBR-NP。该协议在贪婪后备路由协议的基础上增加了节点保护，每一个节点在原路径中绕过出现故障的节点生成新的后备路径。

2.4 无法感知障碍物

在真实的城市交通场景中，存在着大量的建筑物和树木等障碍物，然而GPSR协议没有障碍物感知能力，仍然根据固有的机制转发数据包，导致数据包无法成功发送。如图3所示，源节点S要向目的节点D发送数据包，根据贪婪转发S先把数据包转发给A，由于存在障碍物,A将无法转发数据包给D，导致转发失败。

图3 无法感知障碍物效果图Fig 3 Effect diagram of lack of obstacle-aware ability

文献[21]中指出在真实城市场景中存在着障碍物和受限的道路，而大多数移动模型节点都是自由移动的，因此不适宜真实场景的仿真。针对这一问题，作者提出了一种新的基于锚点的移动模型(AMM)，该模型将锚点设置在障碍物每个凸面的角落，这样就能形成一个曲线图，节点可以通过选择任意的锚点作为下一跳。通过将GPSR协议在AMM中进行仿真得到该模型更接近于真实场景，得到的仿真数据更有效，但该方法需要大量外界硬件的支持。文献[22]设计了一种躲避障碍物的分布式地理路由算法GRdo，在使用该算法前，首先提出一种建立虚拟坐标的方法并引入可见图，通过该图辅助路由沿着障碍物的凸点建立路径决策，通过该方法能够较准确地判断两点之间是否存在障碍物并以较短的路径绕开障碍物。针对文献[21，22]需要大量的外界硬件支持，以及建立虚拟坐标较复杂等问题，文献[23]提出了将障碍物的信息设置在路网属性中，根据障碍物的坐标和两节点连接之间是否存在交点，即可感知节点之间是否存在障碍物，进而根据障碍物的障碍度与阈值比较判断是否转发数据包。该算法能够使协议更适应真实的城市场景，但门限值的选取有一定难度。

2.5 节点位置不定和分布不均引起的链路断裂问题

GPSR协议中每个数据分组中都携带一个被称作标志位的位置信息，用M表示。在数据从源节点向目的节点传递过程中，目的节点的位置信息始终保持不变同时转发给每个中间节点，而在这个过程中VANETs中的目的节点是移动的。因此，每个中间节点可能是按照错误的目的节点位置进行转发，导致数据包丢失。

如图4(a)所示，S是源节点，D是目的节点，A,B,C都在S的通信范围内，根据GPSR路由协议的贪婪法则，S节点应该选择A节点作为下一跳。由于在VANETs中，每个节点都在移动，且方向和速度不同，在更新邻居节点表的时间段里，节点的位置发生了剧烈的变化。如图4(b)，B已经移动出S的通信范围，A,C虽然仍在通信范围内，但A不断远离目的节点D。如果仍然坚持选择A作为转发节点，那么成功转发的几率就会大大降低。文献[24]针对GPSR协议中贪婪转发选择离目的节点最近的节点作为下一跳，当选择好下一跳准备转发时，该节点已经运动出了源节点的转发范围，导致数据包丢失的问题,即邻居无线链路断裂(neighbor wireless link break,NWLB)，提出影响NWLB的网络因素有间隔时间、节点运动速度、网络密度、节点转发范围和网络的大小。综合上述因素，文中基于GPSR提出了一种NWLBP预测模型，该模型对端到端延迟和丢包率有很大的改善。但是该模型没有考虑运动方向，加速度对NWLB问题的影响。文献[25]在文献[24]的基础上提出了将车流速度、移动方向、车辆密度的加入选择下一跳的影响因素，针对车辆的运动方向和速度设置优先权，并在具有优先权的节点中根据距离和速度概率选择下一跳从而减少NWLB问题。文献[26]通过链路稳定性地进行路由决策，它首先根据邻居节点的成功交付率选择交付率较高的作为候选节点，再跟据节点的方向和所处的状态是静止还是移动选择下一跳。该方法能够有效地提高数据包的成功交付率，但是计算每一个邻居节点的交付率工作量太大，特别是在拓扑变化频繁和车流密集的情况下。文献[27]提出了一种新的基于链路生存时间选择下一跳的方法，该方法与文献[26]的不同在于，它根据节点位置和速度方向与大小的信息计算出链路的生存时间，并通过选择由加权的生存时间和中间节点与目的节点之间的距离综合决定的度量值大的作为下一跳进行转发数据包。文献[28]介绍到车辆流密度小，表明区域速度高，拓扑变化频繁容易产生NWLB问题。因此，提出了一种改进的贪婪转发路由协议，该协议根据车流密度大小选择距离远、中、近三区域中的邻居节点进行转发，也就是车流密度大(小)就选远(近)区域中邻居节点。

图4 链路断裂效果图Fig 4 Effect diagram of link break

3 结束语

结合国内外对GPSR协议的改进研究现状，存在的主要问题有以下几个方面：

1) 目前许多研究把引起链路断裂的主要因素归结于节点位置不定和节点分布不均匀，忽略了障碍物的阻挡因素。

2)对于链路断裂这个问题，大多解决策略忽略了影响链路断裂的根本因素到底是速度方向、速度大小还是车流密度，而是一味地将方向作为首要因素选择下一跳。

3)目前，解决无法感知障碍物的方法往往计算量较大且需要外接硬件支持，在此基础上基于障碍物的路径选择计算繁杂，不适用于真实场景。

4)许多路由协议的仿真车辆运动模型过于简单，试验场景和现实场景之间的巨大差异可能导致路由协议的失效，路由协议的实验仿真平台还有待进一步研究和开发。

理想的路由协议的应该具有以下几个方面：算法简单、自适应能力强、控制开销少、普适度高、时延小。通过对当前各类协议的分析比较，基于位置的路由协议对于VANETs频繁变化的拓扑结构具有最适性。而其中典型的路由协议GPSR具有算法简单、开销小等优点，但在城市交通环境下仍存在着一些缺陷，对于它的普遍应用有一定阻碍作用。因此，针对其存在的问题进行改进设计高性能的GPSR是一个研究的重点。目前，许多国内外学者针对GPSR不足进行单一的改进，而没有根据其不足进行综合有效地改进，因此，在真实场景中改进的效果往往差强人意。总的来说，GPSR在VANETs中的有效应用仍在研究阶段，仍然有很多问题亟需解决，许多新的研究课题有待发现。

[1] 徐会彬, 夏 超.VANETs路由综述[J].计算机应用研究,2013 (30):1-6.

[2] Vidhale B,Dorle S S.Performance analysis of routing protocols in realistic environment for vehicular Ad Hoc networks[C]∥Proceedings of 2011 21st International Conference on Systems Engineering (ICSEng),2011:267-272.

[3] Karp Brad,Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C]∥Proceedings of the Annual International Conference on Mobile Computing and Networking,2000:243-254.

[4] Fonseca António,Camões André.Geographical routing implementation in NS3[C]∥Proceedings of the 5th International ICST Conference on Simulation Tools and Techniques,2012:353-358.

[5] Lochert C,Hartenstein H.A routing strategy for vehicular Ad Hoc networks in city environment[C]∥Proceedings of IEEE Intelligent Vehicles Symposium,2003:156-161.

[6] Lochert C,Mauve M.Geographic routing in city scenarios[J].ACM SIGMOBILE Mobile Computing and Computing and Communications Review,2005(1):69-72.

[7] Seet Boon Chong,Liu Genping,Lee Bu Sung,et al.A-STAR:A mobile Ad Hoc routing strategy for metropolis vehicular communications[J].Lecture Notes in Computer Science,2004 (3042):989-999.

[8] Jerbi M,Meraihi R.GyTAR：Improved greedy traffic aware routing protocol for vehicular Ad Hoc networks in city environments[C]∥Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Network,2006:88-89.

[9] Yang Q,Lim A.ACAR ：Adaptive connectivity aware routing protocol for vehicular Ad Hoc networks[C]∥Proceedings of 17th International Conference on Computer Communications and Networks,2008:1-9.

[10] 喻 嘉,闻英友,赵 宏.无线传感器网络中分段贪婪地理路由算法[J].控制与决策,2011(2):196-206.

[11] Kim Jung Hun,Lee Su Kyoung.Reliable routing protocol for vehicular Ad Hoc networks[J].International Journal of Electronics and Communications，2011 (65):268-271.

[12] Lai Liangli,Wang Qianping.Research on one kind of improved GPSR algorithm[C]∥International Conference on Computer Science and Electronics Engineering,2012:715-718.

[13] Xu Huibin,Zhou Lijie.An improved greedy perimeter stateless routing protocol for VANETs[J].International Journal of Advancements in Computing Technology (IJACT),2012(4):442-448.

[14] Wang Lijuan,Liang Haitao.Research and improvement of the wireless sensor network routing algorithm GPSR[J].Computer Society,2012(22):83-86.

[15] 钱 钊,刘宏伟,左德承,等.移动自组网中基于位置信息的路径优化路由算法[J].哈尔滨工程大学学报,2013(3):345-349.

[16] 李 新,吴学文.一种基于实时车流密度信息的VANET路由协议[J].电子设计工程,2013(9):69-72.

[17] 王美琛,唐 伦.基于自适应选路策略的VANETs路由协议[J].计算机应用于软件,2013(30):62-66.

[18] Jaiswal Jyotsana,Khilar Pabitra Mohan.Energy efficient and fault tolerant GPSR in Ad Hoc wireless network[J].Trends in Computer Science,Engineering and Information Technology Communications in Computer and Information Science,2011(204):683-692.

[19] 李洪兵,熊庆宇.无线传感器网络中网络层故障容错技术研究进展[J].计算机应用研究,2013 (7):1921-1928.

[20] Zadin bedalmotaleb,Fevens Thomas.Maintaining path stability with node failure in mobile Ad Hoc networks[J].Procedia Computer Science,2013 (19):1068-1073.

[21] Ahmed Sabbir,Karmakar Gour C.An environment-aware mobility model for wireless Ad Hoc network[J].Computer Networks,2010(54):1470-1489.

[22] 李金宝,郭晓行,张守娟.无线传感器网络中一种躲避障碍物的地理路由算法[J].黑龙江大学工程学报,2010(1):97-103.

[23] 张 帆.城市场景下车载自组网中GPSR路由协议的研究[D].长春：吉林大学,2011.

[24] Alsaqour Raed A,Abdelhaq Maha S.Effect of network parameters on neighbor wireless link breaks in GPSR protocol and enhancement using mobility prediction model[J].Wireless Communications and Networking,2012 (171):1-15.

[25] Hu Lili,Ding Zhizhong,Shi Huijing.An improved GPSR routing strategy in VANET[C]∥2012 8th International Conference on Wireless Communications,Networking and Mobile Computing,2012:1-4.

[26] Wang Hao,Tan Guozhen,Yang Jixiang.An improved VANET intelligent forward decision-making routing algorithm[J].Journal of Networks,2012 (7):1546-1553.

[27] Noureddine Hadi,Ni Qiang,Min Geyong,et al.A new link lifetime estimation method for greedy and contention-based routing in mobile Ad Hoc networks[J].Telecommunication Systems,2013(69):269-284.

[28] Wen Huaqing,Rhee Kyung Hyune.An improved greedy forwar-ding routing protocol for cooperative VANETs[J].Information and Communication Technology Lecture Notes in Computer Science,2013 (7804):502-506.

Research progress of GPSR routing protocol in VANETs

HUANG Wen-jing

(School of Information Science & Engineering，Chongqing Jiaotong University，Chongqing 400074，China)

Because greedy perimeter stateless routing(GPSR) adapts to frequent changes of topological structure，many improved GPSR routing protocol are presented aiming at VANETs.Firstly, classify and compare network layer routing protocol in VANETs.Then,analyze and summarize core routing scheme of routing protocol based on position and advantages and disadvantages,analyze existing problems of typical GPSR based on position in cityscape.Finally, present research strategy and development directions of GPSR in future.

VANETs； routing protocol； GPSR

2014—01—14

TN 919.2

A

1000—9787(2014)04—0001—05

黄文静(1989-)，女，重庆人，硕士研究生，研究方向为宽带无线网络。