车载自组织网络中基于贪婪算法的地理位置路由

基金项目：国家自然科学基金项目(60971082、60872049)

    以IEEE 802.11p标准为基础的车辆间通信(IVC)技术已经成为目前智能交通系统(ITS)[1]研究的主流之一。通过将城市或高速公路上的汽车组成移动自组织网络(Ad Hoc)，能有效地降低交通事故发生率，缓解道路拥堵，满足人们对车载办公和娱乐的需求。推动车载自组织网络(VANET)的普及应用，需要开发适用于该网络环境下的通信协议。其中，路由协议的研究对提高车载自组织网络中数据传输的实时性和有效性，具有关键的作用。

    对于目前已经提出的Ad Hoc网络路由协议，可以从不同的角度进行不同的分类。从路由发现策略的角度出发，可分为先应式路由协议与反应式路由协议；从网络结构的角度出发，可分为平面路由与分层路由协议；从是否使用地理位置信息的角度出发，可以分地理位置辅助路由协议和非地理位置辅助路由协议。

    (1)先应式和反应式路由协议
    先应式路由协议又称为表驱动路由协议。

    先应式路由协议一般包括邻居节点探测和路由广播两个过程。节点向各通信端口周期广播“HELLO”报文，来实现邻居节点探测。在距离矢量基本算法中，虽然没有显式的邻居节点探测过程，但在与邻居节点交换路由表时，隐含了邻居节点探测的过程。路由广播常采用“洪泛”的方式向全网扩散。在先应式路由协议中，由于每个节点需要实时地维护到其他节点的路由信息，这样在网络规模较大、拓扑变化较快的环境中，大量的拓扑更新消息会占用过多的信道资源，使得系统效率急剧下降。

    反应式路由协议又称为按需路由协议，它根据网络分组的传输请求，被动地搜索从源节点到目的节点的路由。当没有分组传递请求时，节点处于静默状态，并不需要交换路由信息。

    反应式路由协议主要包括路由发现和路由维护两个过程。当源节点需要获得到目的节点的路由，而该路由没有在路由表中时，源节点路由发现过程将被激活。节点采用“洪泛”的方式，向整个网络广播路由请求分组。当路由请求分组到达目的节点时，目的节点向源节点发出路由应答分组。这样，在源与目的节点之间会建立起双向路由。随着拓扑结构的变化，当已经激活的路径上的某段链路发生中断时，路由维护过程被启动。路由维护可以采用两种不同的策略，分别是从断点处开始修复路径和通知源节点重新启动路由建立过程。典型的反应式路由协议如图1所示。

    反应式路由协议是Ad Hoc网络特有的路由协议类型，在以往中心网络中并不存在。它可以降低路由开销，提高网络的吞吐量。但是，反应式路由协议具有潜在的不确定性，包括目的节点是否可达的不确定性和路由建立延迟的不确定性。在反应式路由协议中，每条激活路由建立的平均开销要远远高于先应式路由协议的平均开销。在只有少数节点之间需要通信的情况下，按需路由协议的路由开销才比先应式路由协议小。
在VANET中，由于网络的规模庞大以及节点高速移动，使得实时维护一个到其他节点的路由表变得非常困难。因此，在VANET中，更适宜使用反应式路由协议。

    (2)平面路由和分层路由协议
    在Ad Hoc网络中，网络结构可以分为平面式和分层式两种。平面式网络中使用平面路由协议，而分层结构中使用分层路由协议。分层路由协议采用簇的概念对节点进行层次划分。若干个在空间上相邻的节点构成一个簇，每个簇有一个簇头。簇之间可以通过网关节点进行通信，簇头和网关节点构成了网络的上层。
分层结构路由协议包括分簇算法、簇维护协议、簇内路由协议和簇间路由协议4个部分。分簇算法解决的是如何在动态分布式网络环境下使移动节点高效地聚集成簇，它是分层路由协议的关键。簇维护协议主要解决节点移动过程中的簇结构维护问题，包括移动节点退出和加入簇、簇的产生和消亡等功能。簇内路由和簇间路由则主要解决节点之间发现路由和维护路由的问题。常见的分层路由协议如图2所示。

    分层结构路由协议适用于超大规模网络。在分层路由协议中，上层网络节点的路由可以参考甚至直接使用平面路由协议。在VANET网络中，由于网络规模和节点移动性的因素，更适宜使用分层路由协议。

    (3)地理位置辅助路由协议
    由于车辆通信环境中，非地理位置辅助的路由算法开销大，路由发现慢且不稳定，所以基于地理位置的路由算法具有明显优势，故这里只讨论基于地理位置辅助的路由协议。

    随着定位技术的发展，节点可以方便地获得自己的地理位置信息。利用这些位置信息，可以改善Ad Hoc网络的路由性能。根据节点在发送数据前是否先建立路由，可以将地理位置辅助路由协议分为两类：一类是位置辅助的路由协议，该类协议的特点是仅仅使用地理位置辅助路由发现的过程，节点在发送数据前仍然先寻找路由，寻找路由成功后保存路由表；另一类是基于位置信息的路由协议，该类协议的特点是节点在发送数据前不寻找路由，不保存路由表。移动节点直接根据自己的位置信息、邻居节点的位置信息和目的节点的位置信息制订数据转发策略。中间节点在收到数据之后根据数据分组中所包含的目的节点位置信息进行相应的转发。

    根据对位置信息的表示方式和利用程度的不同，基于位置信息的路由协议一般可归为3类：贪婪路由(如GPSR、GEDIR和GRA)、定向“洪泛”路由(如DREAM)和分层路由。在前两种路由协议中，源节点或中间节点将数据分组传送给一个(贪婪转发)或多个邻节点(定向“洪泛”)。这些节点相对自己而言距离目的节点的距离更近，从而可以一步步将数据转发至目的节点。而在分层网络结构下，网络的不同层次可以采用不同的路由协议，但某些层次的路由转发需要位置信息的支持。常见的地理位置辅助路由协议如图3所示。

    地理位置辅助路由协议的前提条件是节点必须能够获得地理位置信息，这些地理位置信息一般通过GPS等设备获得。在VANET中，由于车辆节点很容易配备GPS设备，因此地理位置辅助路由协议比较可行。在这类协议中，以基于贪婪算法的路由协议发展最为全面。

1 地理位置辅助路由
    迄今为止，许多专家学者已经对VANET中基于地理位置信息辅助的路由协议进行了较为全面的研究。根据其改进和丰富的历程，地理位置辅助路由的发展可以分为3个阶段：第一个阶段仅仅考虑网络中节点的实时定位信息，其核心机制是贪婪路由；第二个阶段在地理位置信息的基础上，利用车辆具有的导航、电子地图等功能，发展出了利用道路拓扑信息的锚路由机制；第三个阶段进一步综合和改进了前人的成果，在道路拓扑信息的基础上添加了车流密度信息，利用车辆自主发现的方式实现了地标覆盖路由机制。地理位置辅助路由的演进过程，可以用图4来直观体现。

2 贪婪路由
    传统的Ad Hoc网络路由协议，路由发现和建立的时间往往较长，无法适应车载自组织网络中节点移动速度快、网络拓扑结构变化迅速等特点。2000年诞生的贪婪路由思路，较好地解决了这一问题，取得了满意的性能表现。该类协议的特点是节点在发送数据前不寻找路由，不保存路由表。移动节点直接根据自己的位置信息、邻居节点的位置信息和目的节点的位置信息制订数据转发策略。中间节点在收到数据之后根据数据分组中所包含的目的节点位置信息进行相应的转发。由于省略了路由寻找的过程，因此能满足较高的实时性要求。

2.1 典型贪婪路由协议
    2000年，哈佛大学的Brad Karp等人提出了贪婪边界无状态路由(GPSR)[2]协议，成功地将贪婪算法与地理位置信息的实时获取相结合，为Ad Hoc网络路由开辟了新的思路，成为了车载自组织网络中一系列以地理位置为核心机制的路由协议的先驱和源头。该协议的实现思路是，网络中每个节点都周期性地广播一条信标消息，消息中包含自身的标识信息和实时位置坐标。同时，每个节点都维护一个直接邻居列表。所谓直接邻居，就是节点在一跳的传输范围之内可以达到的其他节点。节点之间通过交换信标消息，将直接邻居的身份标识和位置信息添加到自己的邻居列表中，由此获得对自身周围网络拓扑情况的认知。当一个节点需要发送数据时，首先，它通过网络服务获取目的节点的位置信息，并将该信息加入包头。接着，发送节点通过查找自己的邻居列表，选择距离目的节点最近的直接邻居，并将数据包传输给它。收包的节点继续以同样的方式，选择下一跳并发送数据。以此类推，直到数据包到达目的节点。

2.2 贪婪路由协议的优势和不足
    由于地理位置信息的恰当引入，贪婪路由开拓了VANET路由协议的设计思路。基于地理位置信息的机制也成为了VANET路由设计中最为普遍采用的设计思想。由于在该类协议中，每一跳的接收节点都是由发送节点根据地理位置信息而临时决定的。从全局来看，该类算法选择的路径并不一定是最优解，而是一个由所有中继节点的局部最优解构成的满意解。然而正因如此，它节省了穷尽所有可能和回溯需要耗费的大量时间，使路由得到迅速的建立。这正是贪婪算法的思想所在。相比传统的Ad Hoc路由协议，如按需距离矢量路由算法(AODV)[3]算法而言，以GPSR为代表的这类协议具有极大的灵活性和抗毁性，即使网络中两两节点间的交互时间很短，也能迅速地发现和建立路由，具有较高的实时性和可靠性，特别适合于节点移动速度较快的网络，如车载自组织网络。然而，仅仅基于地理位置信息的路由协议同样具有缺陷。在多跳传输中，由于节点分布不均匀，发送节点可能会遭遇局部最大现象，即需要发包的节点周围，没有任何比它自身更接近目的节点的直接邻居。由于无法选择下一跳，此时需要改用周界路由机制来进行转发。该机制往往导致路径跳数过多，传输时延增大，路由协议的效率降低。

3 锚路由
    由于车载自组织网络中信号传输采用的频率较高，穿透力弱，因此，道路两边的建筑物对信号的屏蔽效应较强，信道条件差。为了克服这一问题，同时充分利用车载网络节点运动的规律性，将道路拓扑信息引入路由选择成为了VANET路由新的发展方向。该类协议的特点是：节点在发送数据前仍然先寻找路由，寻找路由成功后保存路由表。但这条路由指的并非是中间节点序列，而是一条空间上数据传输的通路，由一系列十字路口构成。由于多跳传输避免了穿越路边障碍物，因此提高了数据传输的可靠性。

3.1 典型锚路由协议
    2003年，Christian Lochert等人在若干车载项目的支持下提出了地理位置源路由(GSR)[4]协议，将道路拓扑信息引入路由选择过程，进一步提高了地理位置路由算法的可实现性。基于道路拓扑结构的车载路由协议同样源于对GPSR协议的改进。在GPSR协议中，发送节点选择下一跳的时候，仅仅考虑自己的直接邻居与目的节点之间的距离。在传统的Ad Hoc网络中，由于节点位置随机分布，这种选择方式比较合适。然而，车载环境有其特殊性，车辆仅能沿着道路行驶，路边障碍物对无线电波的屏蔽效应很强。为了避开建筑物的阻挡，同时充分利用车辆节点运动轨迹可预测的特点，GSR这类协议定义了锚节点序列，由从源节点到目的节点路径上的一系列十字路口组成。在两个锚节点之间，仍然采用贪婪路由。也就是说，发包节点在选择下一跳的时候，将计算直接邻居和目的节点之间的距离，改为计算直接邻居和距离目的节点较近的下一个锚节点之间的距离，最终选择距离锚节点较近的邻居车辆节点作为下一跳。这种选择方式使得数据包只能沿着道路进行传输，无线信号无需穿越路边的障碍物，改善了信道条件。同时，由于道路的延伸方向也正是节点运动的方向，通过选择同向运动的节点作为下一跳，可以进一步降低多普勒频移效应带来的不良影响。当数据包传输到十字路口时，继续选择距离目的节点较近的相邻路口作为下一个锚节点。以此类推，直到数据包到达目的节点。

3.2 锚路由协议的优势和不足
    基于道路拓扑的地理位置路由协议充分利用了车载网络中移动节点的运动规律，将地理位置信息和道路结构很好地结合起来，改善了信道条件，提高了数据传输的可靠性，进一步开拓了VANET路由协议的设计思路。然而，GSR这类算法采用的锚节点序列仍然无法解决GPSR协议遭遇的局部最大问题。由于车辆节点分布不均匀，两个十字路口之间的道路上未必有足够的中继节点来提供多跳所需的连通性，因此，一旦数据包传输至车辆稀少的区域，就可能因为无法找到合适的下一跳而启用周边路由，从而产生更大的时延甚至丢包。

4 地标覆盖路由
    GSR协议之后，出现了很多利用道路拓扑信息的改进协议，如采用锚路径加权值和局部最大恢复策略的A-STAR协议[5]等。这些协议尝试把道路车辆密度、车辆之间相对运动的方向和速度等各种信息加入路由选择，均取得了一定的成效，获得了许多有用的实验数据。2008年，出现了一种新的利用车流密度信息辅助路由选择的思路。这类协议兼具上述两类协议的特点，同时综合吸收了前人的经验成果。由于其完整利用了地理位置、道路拓扑和道路密度信息，因此成为VANET路由研究中最具代表性的成果之一。

4.1 典型地标覆盖路由协议
    2008年，Kevin C Lee等人提出了城市车在环境下的地标覆盖路由(LOUVRE)[6-7]协议，利用一种车辆自主发现密度的方式辅助路由选择。LOUVRE协议同样继承了GPSR算法的贪婪路由思想，其机制可以概括为以下几点：第一，车辆与车辆之间，采用基于地理位置信息的贪婪算法进行数据包的路由转发，而贪婪算法所采用的核心机制，是“洪泛”的信标消息广播和周期性更新的邻居列表。第二，引入道路拓扑信息辅助路由选择，延续了锚节点路由的理论，将其升级为地标覆盖的概念。每一个道路交叉口都被看作是一个地标，通过选择一条最优的地标序列来得到满意的路由，在地标和地标之间建立路径，数据包在地标之间贪婪传递。而决定路径是否有效的依据，就是两个地标之间的道路车辆密度分布情况。第三，提出了一种车辆自主发现道路密度的算法。车辆通过观察直接邻居的数量，得到对身边道路密度的评估值。再利用贪婪路由中固有的信标消息，将该评估结果散播出去。通过“洪泛”传播，全网的所有车辆就能建立起对两两地标之间是否具有传输通路的认识。

4.2 地标覆盖路由协议的优势和不足
    通过上述3个机制，LOUVRE协议充分吸收了前人研究成果的优势，能够很好地适应车载自组织网络的环境。同时，由于车辆在选择地标路由的时候，仅仅考虑那些车辆密度分布达到一定要求的道路，因此最大可能地降低了发送节点缺乏直接邻居的风险，避免了因道路上车辆稀少或者车辆密度分布不均匀而产生的局部最大现象。在对时延和效率要求极高的车载网络中，这是一个重要的性能提升。由于LOUVRE协议能够很好地适应VANET快速变化的网络拓扑结构、迅速的节点移动，同时对抗网络中普遍存在的屏蔽效应和GPSR算法固有的局部最大难题，较好地满足车载自组织网络中的数据传输要求，因此非常适合车载网络下的路由选择。然而，在实际应用的可靠性和可行性方面，它仍然存在一些不容忽视的不足之处：第一，为了实现贪婪算法和道路密度信息的自主获取，网络中所有车辆节点都要周期性地广播信标消息，消息的内容不仅包括自身的标识信息，还要包括自己收集到的道路密度信息。随着网络规模的扩大，车辆数目的增多，网络中的信标消息数量将呈膨胀式增长。在网络容量有限的VANET中，如此众多的消息极易引起网络拥塞，使得基于竞争机制的信道利用发生冲突，产生较大的发送时延。在繁忙的城市环境下，这种现象将尤为严重。第二，由于LOUVRE协议采用车辆自主评估的道路密度发现机制，因此车辆密度信息的传播完全依赖于信标消息的顺利送达。然而，VANET中的车流分布往往非常不均匀，在车辆稀疏的路段，就会出现多跳的断点，导致信标消息无法及时被传送出来，其载有的密度信息也就无法让其他车辆收到。这种断点的存在将会产生众多密度评估的盲区，降低道路密度信息的准确性和全面性，最终引起路由选择的错误，降低数据包传输的可靠性。

5 路由协议内容和性能对比
    基于贪婪算法的地理位置辅助路由，由一开始的仅仅利用地理位置信息，发展到综合利用道路拓扑信息，再丰富为综合利用车流密度信息，其性能不断提升，对VANET特性的适应能力也不断变强。上述3个阶段的路由协议，其核心内容和主要性能对比如表1所示。

6 结束语
    车载自组织网络技术能提供车辆之间高速、可靠、廉价的数据传输，具有组网灵活自由、信息传播实时性高等优点，能极好地解决道路交通安全问题，因此受到了通信和汽车工业领域的广泛关注。然而，VANET特殊的应用环境，决定了其具有较为复杂的网络拓扑结构和较差的信道传输条件。综上考虑，开发适用于车载网络的性能优良的通信协议，对VANET技术的可实现性有着重要的影响，甚至成为决定车辆通信系统能否推广应用的关键环节。

    由于VANET通信协议的设计、开发和改进仍然是现今通信领域和汽车工业领域研究的一个热门课题，因此，对路由协议以及车载自组织网络中其他层协议的研究始终具有相当大的发展空间。如在LOUVRE算法中，车辆自主发现密度的方式仍具有效率低下、准确度不高的问题，需要研究新的思路加以对抗。此外，通过引入一些细节上的改进，比如多跳时综合考虑车辆间的相对运动方向和运动速度等，能进一步提高路由协议的性能。在将来，利用越来越全面和先进的各类车载设备，车辆间通信技术必然具有一个良好的应用前景，实现其在交通安全、运输方面的价值。

7 参考文献
[1] 杨东凯, 吴金培, 张其善. 智能交通系统及其信息化模型 [J]. 北京航空航天大学学报, 2000,26(3): 270-273.
[2] KARP B, KUNG T H. GPSR: Greedy perimeter stateless routing for wireless networks [C]//Proceedings of the 6th annual International Conference on Mobile Computing and Networking (MOBICOM’00), Aug 6-11,2000, Boston, MA,USA. New York, NY,USA: ACM, 2000: 243-254.
[3] PERKINS C E, ROYER E M. Ad-hoc on-demand distance vector routing [C]//Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications(WMCSA’99),Feb 25-26,1999, New Orleans, LA, USA. Los Alamitos, CA,USA:IEEE Computer Society, 1999: 90-100.
[4] LOCHERT C, HARTENSTEIN H, TIAN J, et al. A routing strategy for vehicular Ad Hoc networks in city environments [C]//Proceedings of the IEEE Intelligent Vehicles Symposium (IVS’03),Jun 9-11,2003, Columbus, OH, USA. Piscataway, NJ, USA: IEEE,2003: 156-161.
[5] SEET B C, LIU Genping, LEE Bu Sung, et al. A-STAR: A mobile Ad Hoc routing strategy for metropolis vehicular communications [C]//Networking Technologies, Services, and Protocols, Performance of Computer and Communication Networks, Mobile and Wireless Communications: Proceedings of the 3rd International IFIP-TC6 Networking conference (Networking’04),May 9-14,2004, Athens, Greece. LNCS 3042. Berlin, Germany: Springer-Verlag, 2004: 989-999.
[6] LEE C K, LE M, HARRI J. LOUVRE: Landmark overlays for urban vehicular routing environments [C]//Proceedings of the 68th Vehicular Technology Conference (VTC-Fall’08), Sep 21-24, 2008, Calgary, Canada. Piscataway, NJ,USA:IEEE, 2008: 5p.
[7] LEE C K, ZHU Jiajie, FAN Jih Chung. Histogram-based density discovery in establishing road connectivity [C]//Proceedings of the 2009 IEEE Vehicular Networking Conference(VNC’09), Oct 28-30,2009, Tokyo, Japan. Piscataway, NJ,USA: IEEE,2009: 7p.

收稿日期：2011-03-18

[摘要] 车载自组织网络(VANET)技术发展迅速，但由于其特殊的节点类型和信道特性，采用传统Ad Hoc网络路由协议无法取得满意的性能。实现高速可靠的数据传输速率，需要研究新兴的路由算法。基于贪婪算法的地理位置辅助路由是目前VANET路由的主流思路。文章认为基于这类思路的协议利用车载GPS装置、电子地图和下一代网络导航技术，能使路由发现和建立的时间大大缩短；结合已知的道路拓扑结构，选择多跳传输的最优路径，能避免路边建筑物的屏蔽效应，改善信道条件；动态评估道路上的车流密度，选择可靠性最高的传输路径，能很好地降低传输时延，提高网络吞吐能力

[关键词] 车载自组织网络；路由；地理位置；道路拓扑；车流密度

[Abstract] Vehicular ad hoc networks (VANETs) are developing rapidly. However, existing routing protocols in the ad hoc network cannot perform satisfactorily because of the particular node type and channel conditions in VANET. New routing protocols need to be developed for high-speed transmission and reliability. Making full use of geographic position information is the mainstream way of thinking about VANET routing protocols. Protocols based on this kind of thinking take advantage of GPS, electronic map and next generation network (NGN) to shorten the time of routing discovery and establishment. By using the known road topology and choosing the optimal path of the multihop transmission, the screening effect of roadside buildings can be avoided and channel conditions can be improved. Dynamic evaluation of road traffic density can also be used to choose the surest transmission route. This significantly reduces transmission delay and improves network throughput.

[Keywords] vehicular ad hoc network; routing; geographic position; road topological; traffic density