车载自组织网络路由协议研究进展与比较*

2013-07-01许富龙刘志建

电讯技术 2013年10期

关键词：路由车载消息

许富龙,刘志建

(中国西南电子技术研究所,成都610036)

车载自组织网络路由协议研究进展与比较*

许富龙**,刘志建

(中国西南电子技术研究所,成都610036)

车载自组织网络(VANET)是一种新型移动自组织网络。作为移动无线网络的热点研究领域,车载自组织网络的间歇连通性使路由设计充满挑战。首先阐述了车载自组织网络的主要特征和应用;在对车载网络路由协议进行分类的基础上,详细描述了一批有代表性的路由协议;对比和总结了各类路由协议的特点,并提出相关研究建议,可为车载网络路由协议研究提供一定的参考价值。

移动自组织网络;车载自组织网络;路由协议;间歇连通

1 引言

近年来,随着无线通信技术的快速发展和汽车信息化程度的不断提高,车载自组织网络(VANET)应运而生。作为智能交通系统(ITS)的重要组成部分,车载自组织网络是由道路上的车辆之间、车辆与固定接入点之间相互通信组成的移动自组织网络。因为能够提供安全、舒适、方便的驾驶环境,并能有效促进交通运输效率的提高,车载自组织网络有着广泛的应用前景和实用价值[1-2]。

路由技术是车载自组织网络的关键技术之一。作为各种应用的基础,路由协议的好坏直接影响着车载自组织网络的整体性能,因此是车载网络研究的重要热点问题。然而,车载自组织网络的动态拓扑和由此导致的网络间歇连通性,为路由协议设计带来了很大的困难。

当前在世界范围内,包括路由在内的车载自组织网络相关问题研究受到各国研究机构和科研人员的密切关注。在学术领域,著名的网络领域国际会议如MobiCom、InfoCom等,都将车载自组织网络列为一个重要的无线网络研究领域,MobiCom甚至为此成立了专题讨论会。随着人们对车载自组织网络关注度的增加,相关的重要研究成果逐年增多,作为车载网络关键问题的路由技术也取得了很大进展,涌现出一些具有代表性的路由协议。

在国内,随着科研水平的不断提升以及国际学术活动的增多,相关学者在车载自组织网络路由研究方面也取得了一些重要成果。但是从国内期刊相关文章的发表情况来看,我们与国外相比仍有一定的差距,主要体现在对研究问题的认识程度、研究深度以及创新性上的不足。为了促进国内车载自组织网络路由技术研究的不断进步,缩小在该领域与国外的差距,追踪并总结车载组织网络路由技术的最新研究进展很有必要。

本文其余内容安排如下:第2节介绍车载自组织网络的基本概念;第3节对车载自组织网络路由协议进行分类,着重介绍一些经典的、有代表性的路由协议,并对协议进行对比和分类总结;第4节提出车载网络路由研究建议;最后总结全文。

2 车载自组织网络概述

2.1 车载自组织网络的概念

车载自组织网络是运行于道路交通环境中的新型移动自组织网络,可提供交通事故预警、道路信息查询、互联网访问等服务,具有极高的应用前景和价值。如图1所示,车载自组织网络是由行驶在道路网络中的车辆组成的,各车辆节点之间利用DSRC (Dedicated Short Range Communication)技术进行通信。

图1 车载自组织网络示意图Fig.1 An exemple of VANET

在车载自组织网络中,高速运动的车辆节点造成了高度动态的网络拓扑和网络的间歇连通。为了增强连通性,同时出于实际应用的需要,路边固定节点成为车载自组织网络中较常使用的一种辅助设施。因此,与其他移动自组织网络不同,车载自组织网络中不仅存在车辆到车辆的通信(V2V),还可能存在车辆与路边固定基础设施的信息交互(V2I)。两种通信方式中,V2V在邻居车辆之间直接通信,具有组网灵活、可扩展性好等优点,但网络的间歇连通会使V2V的性能受到影响。相比之下,V2I利用路边固定设施和车辆通信,不但可用于互联网接入、不停车收费等应用,而且能够为整个网络拓扑引入部分的静态节点,从而提高间歇连通环境下的网络性能。

2.2 车载自组织网络的特点和应用

2.2.1 车载自组织网络的特点

车载自组织网络是应用于道路交通领域的移动自组织网络,所以具有自组织、动态拓扑等特点。但是交通运输环境的特殊性,也使车载自组织网络具有区别于传统自组织网络的其他特点:一是节点的高速移动性,相比其他网络的节点,车辆具有非常高的行驶速度,导致了网络拓扑高度动态;二是网络的间歇连通性,节点的高速移动和较小的通信半径使节点间的链路只能短暂存在,网络的连通时断时续;三是节点运动受道路限制,道路网络具有固定的拓扑结构,而车辆的移动和分布受道路拓扑的限制,节点的移动具有一定的规律性和可预测性;四是电量充足、计算能力较强。传统的移动自组织网络中节点体积小巧,能量和计算能力非常受限,而车载网络中的车辆节点采用蓄电池供电,能量充足且具有更强的计算能力。

2.2.2 车载自组织网络的应用

车载自组织网络作为智能交通领域的重要组成部分,应用前景十分广阔。按照应用性质的不同,车载自组织网络的应用可分为以下几类。

(1)交通安全类应用

这是车载自组织网络最重要、最有价值的应用。通过车载传感器实时监测车辆的行驶状态并向周围车辆实时报告,可以在危险时刻及时警示周围汽车,提醒驾驶员做出安全应对操作。此外,在事故频发的危险路段,利用车载自组织网络实时向车辆分发危险告警,可以使驾驶员提前调整车辆行驶状态,保障驾驶安全。

(2)交通运输效率类应用

通过收集和传播道路网络的交通状况信息(如拥堵情况等),车载网络可以协助车辆制定合理的出行路线,避免交通拥塞,提高交通运输的效率。此外,交通信息的收集和统计还能帮助交通管理部门合理调整交通设施和交通规则,从根本上提高道路交通的效率。

(3)信息服务类应用

车载自组织网络能够帮助车辆查询周边服务信息,并提供商业广告发布、公交车到站时间预测等服务。此外,借助路边的网络基础设施,车载自组织网络还能提供互联网接入,满足乘客的舒适性要求和通信需求。

3 车载自组织网络的路由协议

路由是车载自组织网络各种应用的基础。然而车载自组织网络的特性(如间歇连通性等)使传统自组织网络的路由协议不能适用。如何在车载网络环境中实现高效的路由,成为车载自组织网络研究中的一个关键问题。

近年来,具有间歇连通特性的机会网络[3]概念被提出并获得了广泛关注。事实上,车载自组织网络也属于机会网络的范畴,因此机会网络中的携带-转发(Carry and Forward)机制同样适用于车载网络间歇连通的网络环境,已在协议设计中普遍采用。目前,通过研究者的不断努力和探索,车载自组织网络路由问题研究已取得了较丰硕的成果,出现了许多针对或利用车载网络不同特性而设计的路由方法。受制于车载网络的现实复杂性,这些网络路由协议呈现出技术和应用上的多样性。同时,网络环境的复杂性也使得对这些协议的归纳、分类和分析讨论存在多种不同的方法和角度,例如可按照应用场景、路由决策信息类型、是否存在路边固定设施等进行分类。为便于讨论,本节首先把路由协议分为单播(unicast)路由和广播(broadcast)路由,然后进一步从协议设计者的角度出发,依据路由决策信息对单播路由协议分类讨论,并针对高速公路和城市道路两种场景介绍广播路由。最后,本节从多个方面对这些协议进行对比和分析总结。

3.1 单播路由

单播路由主要用于点对点的数据通信。车载自组织网络环境的特殊性,使得单播路由协议研究存在丰富多样的思路和方法。按照不同的路由决策依据,本文将单播路由协议分为以下几类。

3.1.1 基于连通路径的路由

因为车载自组织网络是一种特殊的移动自组织网络,所以在研究之初,人们很自然地将移动自组织网络的基于连通路径的路由协议用于车载网络环境。然而研究表明,车载网络高度动态的网络拓扑使移动自组织网络的路由协议难以适应。例如,在车载网络中使用AODV[4]时,由于不能快速发现和维持长距离路由,消息会被大量丢弃,导致网络吞吐量很低。

事实上,作为一种典型的机会网络,车载网络节点之间的通信时机和持续时间都难以确定,使得建立并维持长距离的路由非常困难。因此,基于连通性的路由协议只适用于跳数有限的小范围通信。考虑到AODV创建的连接在车载网络环境下中断频繁,研究者提出两种改进的协议——PRAODV和PRAODVM[5],利用备用连接来减少路由中断对传输的影响。根据车辆的行驶速度和位置信息,新的协议能够预测链路的寿命。在此基础上,通过评估连通路径的存在时间,PRAODV能够在当前路径失效前就建立起一个新的替换路由,而PRAODV-M则在多个可选路径中选择预测寿命最长的路径进行替换。因此,与AODV在路由失败时才寻找新的路径相比,PRAODV和PRAODV-M具有更好的网络性能。

CAR[6]是另一种基于连接的路由协议,用于实现城市道路和高速公路环境下的车辆间通信。CAR由以下四部分组成:一是目标定位和连通路径的建立;二是经由连通路径的数据传输;三是连通路径的维护;四是错误恢复机制。当需要传输数据时,CAR首先利用优化的广播来发现目标车辆并建立源车辆到目标车辆的连通路径,随后数据将采用贪婪方式沿该路径传输。与前述协议频繁更换连通路径不同,CAR协议中的连通路径一旦建立,就会利用一种称为guard的实体根据变化进行调整和保持,而不再搜索其他路径。尽管如此,利用连通路径传递消息仍可能出现路由失败,此时错误恢复机制将引导消息传递。实验结果表明,CAR在车流密度较高时性能较好,而在低密度网络中表现较差。

3.1.2 基于地理位置的路由

由于道路拓扑的确定性和GPS设备的广泛使用,利用地理位置信息进行路由是车载网络中另一种常见方法。高速公路的网络拓扑比较简单,更适合利用地理位置信息进行路由。而城市场景的道路拓扑变化多样,车辆间的位置关系更加复杂,且路边建筑物易导致无线电障碍,这些都会对基于地理位置的路由产生不利影响。

作为一种经典的基于地理位置的路由协议, GPSR[7]采用贪婪方式转发消息,并选择在地理位置上更靠近目标的邻居节点作为下一跳节点。然而,当地理位置最接近目标的节点由于种种原因(如通信半径有限)不能将消息传递至目的地时,就会导致路由失败,陷入局部最优问题。如图2所示,在将消息由节点S向节点D传递的过程中,节点2将陷入局部最优,因为它找不到比它自己更加靠近目标点D的邻居节点。此时GPSR将转入周边路由(perimeter rou-ting),网络拓扑被视作一个平面图,而消息则采用右手规则进行传递,直到一个新的最接近目标的节点被发现时路由才重新转回贪婪转发模式。由于GPSR没考虑交通状况,因此无法优先选择车辆密度较高的路段来传递数据。此外,城市场景中的无线电干扰也使GPSR的路由修复机制不够可靠。

图2 GPSR的局部最优问题Fig.2 The local optimum problem in GPSR

GPCR[8]是另一种著名的基于地理位置的路由协议。通过beacon消息,每个节点持续不断地广播自己的位置信息。此外,beacon消息还对发送者当前是否处于路口进行标识。当节点需要发送消息时,首先利用定位服务对目标的位置进行判断,随后消息被发送至一跳范围内最靠近目标位置的邻居节点。与其他协议不同的是,GPCR采用受限的贪婪路由来选择下一跳车辆节点,即处于路口处的邻居节点将优先作为转发节点,哪怕它们距离目标点更远一些(这是由于路口节点能够接触到所有相连路段的邻居节点)。对于路由恢复策略,GPCR使用右手规则使处于路口处的节点决定消息传递的下一个路口,而消息在两个路口中的传递则采用贪婪路由。实验表明,与GPSR相比,GPCR能以更多的路由跳数获得更高的消息递交率。

上述简单的基于地理位置的路由常常遭遇局部最优问题,而恢复策略在城市场景中效率较低。为解决这个问题,文献[9]提出IGRP协议。IGRP首先利用车辆密度、速度、通信半径以及道路拓扑等信息,建立路段连通性、错误比特率、传输延迟等性能参数的数学模型。然后,IGRP采用多目标优化方法,在满足延迟、带宽利用率,错误率等QOS约束的条件下,获得连通性最佳的消息传输路径(由路口序列标识)。沿此最佳路径,IGRP在相邻路口之间,采用基于地理位置的方法来传递消息,直至消息到达目标点。由于IGRP只在相邻路口间使用基于地理位置的路由,有效避免了前述协议中的局部最优问题;而优化路径的使用,使协议能够“智能”选择连通性好的路段传递消息,因此具有比GPSR和GPCR更好的性能。

3.1.3 基于传输延迟的路由

在车载自组织网络中,较低的传输延迟是路由协议设计的一个重要目标。为使消息快速传递至目的地,一些协议采用传输延迟作为消息路由的决策依据,我们称之为基于延迟的路由协议。

由于网络的间歇连通性,到达路口处的消息可能遇不到合适的车辆以进入预期路段。因此,Ding等人提出SADV算法[10],在每个路口处设置静态节点,用于对消息进行缓存并等待与期望传输方向相一致的车辆经过。因为采用了路口静态节点,消息经过每个路段的传输延迟,不仅包含了消息在路段中传递的时间,也包含了消息在静态节点中的等待时间。根据每个路段的传输延迟,SADV采用最短路径算法计算消息路由的路径。静态节点的加入使SADV具有较好的网络性能,但同时也增加了成本投入和实施难度。

为了更好地选择较低延迟的路径传递消息, Zhao等人提出VADD协议[11]。VADD将消息路由分为直路模式和路口模式,直路模式用于消息在一个路段中的传递,此时采用贪婪算法使消息尽可能快地传输到路口,并进入路口模式;路口模式决定消息在路口时,将被传输至与该路口相连的哪一路段。由于路段选择对路由延迟具有重要影响,VADD主要研究路口模式。利用车流量统计信息,VADD首先评估消息从路口Ii出发,经由路段rij(即连接路口Ii和Ij的路段)并传递到目的地所需的端到端(E2E)期望延迟Dij。如图3所示,在一个简单道路网络中,假设消息传递的目的地是路口Ic,对该道路网络中任一路段rmn所对应的E2E期望延迟Dmn(m、n为路口编号且m≠n),可通过公式(1)的方程组计算(其中dmn是消息从路口Im传递到路口In所需时间, Pmn是指消息在路口Im处被传往路段rmn的概率)。随后,路口模式的规则是:处于路口的消息,将总是选择当前可传递的各路段中具有最小E2E延迟的路段。实验结果表明,与GPSR等协议相比,VADD具有更低的消息传输延迟。

图3 一个简单的道路网络示意图Fig.3 A simple exemple of VANET

虽然VADD在车流密度较高时性能较好,但它没有考虑个体车辆用于消息传输时的性能差异。随着GPS导航设备的广泛使用,获取车辆行驶的轨迹(trajectory)信息已非常容易。以VADD为基础, Jeong等人提出TBD协议[12],通过引入车辆的行驶轨迹,使消息传递经由更加有效的车辆节点。和VADD针对路段来评估消息传输的E2E期望延迟不同,TBD针对每个车辆来评估消息传输的E2E期望延迟。假设车辆a的行驶路线是路口1,路口2,…,路口M,若由车辆a传输消息,考虑在其行驶过程中的每个路口遇到其他车辆(转发消息)和遇不到其他车辆(继续携带)两种情况,其E2E期望递交延迟可利用概率求得。每个车辆都周期性地计算自身传递消息的E2E期望延迟,并利用beacon消息不断地向邻居广播,从而能够使消息总是传递至具有最低E2E延迟的邻居车辆。实验表明,TBD具有比VADD更好的路由性能。

上述VADD和TBD都只适用于静止目标点的消息传递,而当消息的目标接收者是移动车辆时,对目标车辆的定位和下一跳节点的选择都将非常困难。为解决这个问题,Jeong等人提出了TSF协议[13],用于从固定的接入点(AP)向移动车辆传递消息。TSF假定道路网络的每个路口处都部署一个静态节点,用于暂时缓存消息。此外,为了对车辆进行追踪和预测,TSF要求车辆将自身的行驶轨迹报告给AP。相关研究表明,车辆驶过特定长度的路段所需时间满足gamma概率分布,而消息沿道路传输的时间也具有类似的概率分布。因此,通过计算“在目标车辆行驶轨迹上的每个路口处,消息先于目标车辆到达的概率”,就可找出车辆行驶路线与消息传输路线的最佳交汇点,从而能够在保障消息递交率的同时获得最小的传递延迟。

3.2 广播路由

车载自组织网络的广播路由主要用于公共信息(例如突发事故告警、道路交通流量、天气情况等)的快速散播。此外,一些单播路由协议在路由发现阶段也需利用广播来建立到目标点的有效路径。

用于信息广播的最简单协议是泛洪(flooding),它要求接收到广播消息的每个车辆都重新广播该消息,从而实现信息的可靠散播。虽然泛洪易于实现,但每个节点的重复广播会带来很大的开销,因此仅适用于规模很小的网络。随着网络中节点数量的不断增加,泛洪消息的带宽消耗和传输冲突将急剧增加,造成网络拥塞并使性能急剧恶化。

为了在高速公路实现紧急事件的广播,Durresi等人提出BROADCOMM协议[14]。该协议将高速公路分成不同的虚拟单元(virtual cell),且随着车辆的移动而移动。为管理和处理紧急消息,协议将网络中的车辆节点分为两层:第一层由虚拟单元内的所有车辆节点构成;第二层是单元反射体(cell reflector),通常由单元内处于中央位置的节点担任。单元反射体负责处理自身单元或邻居单元内的近距离车辆发出的紧急消息,同时也为来自其他反射体的紧急消息提供路由中继。在路由转发过程中,反射体还需要对各紧急消息的发送优先级进行管理。与泛洪类协议相比,BROADCOMM具有较小的消息广播延迟和路由开销。

DV-CAST[15]是另一种用于高速公路场景的广播路由协议,它采用分布式设计,使节点无需获取全局信息即可处理消息的传递。DV-CAST协议主要包括三个部分:邻居探测、广播抑制,以及存储转发。邻居探测是指,通过接收相邻车辆的HELLO消息,每个车辆感知自身周围的局部拓扑,并判断周边连通性的强弱。当节点周围连通性较好时,对接收到的广播消息进行广播抑制;反之,若节点处于弱连通性环境,则采用存储转发机制,以保证广播消息的传递。上述机制的使用,使DV-CAST对各种网络连通状况都具有较好的鲁棒性。

城市场景道路拓扑复杂,且路边建筑易形成无线电阻碍,因此城市中的广播路由设计不同于高速路。作为一种典型的城市道路广播协议,UMB[16]主要解决多跳广播中的广播风暴、隐藏节点等问题。考虑城市道路的实际环境,UMB包括两种广播阶段:定向广播和路口广播。在定向广播阶段,消息发送者不需事先获取拓扑信息,只需选择在当前广播方向上相距最远的节点,作为消息转发和确认的实施者。当定向广播的消息到达路口时,安装于路口的中继器将向各路段方向发起新的定向广播,即路口广播。采用中继器的原因是,城市高大建筑的阻隔使消息只能沿道路进行可视传播,而路口的中继器具有相邻各路段的最佳“视角”,有利于消息向各路段散播。由于只利用广播方向上的一个节点转发消息,UMB能够有效利用信道并具有较高的可靠性,而且其性能在网络处于高广播负载和高车辆密度时仍然较好。

针对城市场景中车载网络的广播风暴和网络间歇连通问题,文献[17]提出UV-CAST广播协议。与UMB不同,UV-CAST不引入路边基础设施,采用分布式方式来应对各种网络连通状况时的消息广播。考虑到在一个连通区域中,处于区域边缘的车辆比区域内车辆更容易(或者更能够在较短的时间内)遇见其他离散车辆,UV-CAST令处于连通区域边缘的车辆节点,作为SCF(Store-Carry-Forward)任务的承担者。这些被称作SCF代理的车辆携带广播消息,并在遇到其他离散车辆时向其广播。相反地,处于区域内部的车辆节点,则对接收的广播消息进行抑制处理。由于节点仅利用局部信息来判断自己是否为SCF代理,使得UV-CAST开销较小。

除了上述广播路由,车载网络中还存在区域内的多播路由(Geocast Routing)[18]。这种基于区域的多播路由是将数据发送至指定地理区域内的所有节点,而该区域被称作相关区域(zone of relevance)。在车载网络中,区域内的多播主要用于交通安全类通信。例如,当实施危险路段警告时,处于危险路段的所有车辆都应收到该警告消息(区域外的车辆不应被警示)。大多数的区域多播路由协议都基于定向泛洪,通过定义传输范围并对泛洪进行约束,来避免网络拥塞并减少传输开销。因此,区域多播路由在一定程度上也可视作特殊的广播路由。

3.3 路由研究的分析总结

本节从路由机制、有无路边固定设施、适用场景、网络性能等方面综合比较上述路由协议,分析总结各类协议的特点,并指出研究需解决的关键问题。

(1)基于连通路径的路由

此类协议设计的重点是如何建立并维护连通路径,以及当消息传递失败时如何进行路由恢复。由于车载网络高度的动态性使节点间的连通链路极不稳定,此类协议很难建立起从源到目的的连通路径,而且即使建立,也仍需花费很大代价来维护或寻找替换路径,从而使性能受到影响。考虑到车载网络的实际环境,基于连通路径的路由协议只适用于车流密度大且跳数有限的小范围通信场景。

尽管基于连通路径的路由在性能和应用场景上都受到一定的限制,但对间歇连通的车载网络来说,连通性仍是一种非常重要的可用资源,因此适当并合理地利用连通性,仍然是提升路由性能的一个重要手段,而且也是路由协议研究的一项重要内容。

(2)基于地理位置的路由

与基于连通路径的路由相比,基于地理位置的路由不需维护路由状态,实施方便,并且对网络规模变化具有良好的适应性。例如当网络规模增大时,基于地理位置的路由仍能保持较小的开销。但是,由于路由以节点位置作为消息传递依据,局部最优的产生和相应的恢复机制大大增加了消息传递的延迟,使得单纯的基于地理位置的路由性能受到限制。目前,将基于地理位置的路由技术与其他技术相结合,已成为车载网络路由研究的一个新趋势,该类研究的关键问题是:如何利用地理位置路由的规模鲁棒性来获得对不同规模网络的良好适应性,以及如何采用其他技术突破地理位置路由的性能制约,提升路由可靠性并降低路由延迟。

(3)基于传输延迟的路由

此类路由以延迟作为路由依据,目的是将消息尽快送达目的地。消息的传输延迟,通常取决于协议设计的传输行为模式;反过来,传输延迟的计算结果及其准确性也将影响到具体消息的传输行为决策,从而影响协议性能。因此,此类路由研究的重点有:一是如何设计合理有效的消息传输行为模式,即采用何种机制和方法实现消息从源到目的的传递;二是如何基于消息传输的行为模式和可用信息,准确评估消息传输的延迟。以上两点相辅相成,互相影响,须在协议设计中共同考虑。就消息传输延迟的计算而言,如何获取准确的消息传输延迟是影响协议性能的关键,而传输延迟的准确与否,与可用信息的选取和计算密切相关。一定程度上,可用信息越具体详细,计算模型越精确,传输延迟计算就越准确(例如引入车辆行驶轨迹计算延迟比单纯采用路段延迟统计更加准确),但另一方面,采用更详细的可用信息必然会带来更多的开销和实现代价,因此需要在协议设计中进行平衡和折衷考虑。

(4)车载网络的广播路由

车载网络的广播路由看似简单,但要在如此动态的网络环境中实现广播消息的全覆盖,并保证较小的延迟和系统开销,实现起来并不容易。广播路由的最简单协议是泛洪,虽然该方法在理想情况下的传输延迟最小,但只要网络稍具规模,开销就会急剧增大并导致网络拥塞。所以,车载网络的广播路由通常采用可控泛洪,有选择地使部分节点作为消息的转发者,从而有效减少网络开销和拥塞,并获得较低的传输延迟。对于此类广播路由而言,研究者需解决的关键问题是:在降低传输延迟和网络开销的目标前提下,如何使车辆感知自身周围网络环境,如何设计分布式算法来确定网络中的广播中继车辆节点,以及如何合理设计中继节点的消息转发机制。

上述路由协议的比较如表1所示。

表1 路由协议的比较Table 1 The comparison among routing protocols

4 研究建议

本节从场景假设、运动模型和仿真软件、可用信息和获取信息等4个方面,提出车载自组织网络路由研究的相关建议。

(1)良好的场景假设

城市道路与高速公路在道路拓扑、车辆行驶速度、周围环境等方面相差迥异,对路由协议设计提出了不同要求。此外,不同应用也往往具有不同的路由需求,例如语音应用要求高实时性,而信息查询应用更侧重消息传递的高到达率。因此,路由设计者必须首先设定合理的场景和需求前提,在此基础上开展路由协议设计。

(2)选择合适的运动模型和仿真软件

车载自组织网络发展至今,在相关研究领域已形成了一些被广泛认可和采用的运动模型和仿真软件。采用这些模型和软件,一方面可减少自行设计开发的工作量,另一方面其结果数据也能够相对合理地反映出研究工作的真实特点和独特之处。因此,除非对自己的运动模型和仿真过程有足够充分和合理的分析讨论来说服其他研究者,否则采用广泛认可的运动模型和仿真软件将使研究工作更易获得研究同行的认同和接受。

(3)获取适当的可用信息

车载网络路由研究的多样性,一定程度体现在研究者对可用信息的广泛挖掘和使用上。一般而言,电子地图和车辆位置信息是目前车载网络研究最基本的可用信息。此外,通过“灯塔”消息感知周围车辆状况,采用智能交通设施或商业服务获取道路车流统计数据、道路实时交通状况,利用路边固定节点提供定制信息或消息中继服务,以及通过制定出行计划获得车辆自身行驶路线等,也都是常见的可用信息及其获取方式。对车载网络而言,选择一组适当且易于获取的可用信息,是路由研究获得成功的基础。因此,为了给消息传递提供路由依据,协议设计者必须仔细考虑和选择路由可用信息。

(4)合理使用获取信息

在可用信息获取之后,如何进行信息加工处理,从中提取有用信息并指导消息路由,是路由协议研究的中心内容,也是设计者研究能力和创新能力的集中体现。在可用信息确定的前提下,路由算法设计仍然有足够的灵活性和创新空间,并且很大程度地决定着协议最终的特点和性能。因此,研究者应充分发挥自身的创造性,结合车载自组织网络的固有特点,合理使用可用信息,来设计符合实际需求的高效路由算法。

5 结语

车载自组织网络的间歇连通等特性为路由协议设计带来了很大的困难。由于路由问题与实际应用需求密切相关,其性能取决于道路场景、车辆密度等多种因素,所以不可能找到一种通用的路由策略和评价标准以适用于所有车载应用,这就使得车载自组织网络的路由协议研究存在多样性。本文阐述了车载自组织网络的基本概念和特征,并对现有的路由协议进行了分析和比较。作为当今无线移动网络的热点问题,车载自组织网络的路由研究仍然面临着效率、开销、安全等诸多问题,有待我们根据实际应用需求开展更深入的研究。

[1] Xu Qing,Mark T,Jeff K,et al.Vehicle-to-vehicle safety messaging in DSRC[C]//Proceedings of VANET. Philadelphia:ACM,2004:19-28.

[2] Eriksson J,Balakrishnan H,Madden S.Cabernet:Vehicular content delivery using WiFi[C]//Proceedings of 2008 MobiCom.San Francisco:ACM,2008:199-210.

[3] 熊永平,孙利民,牛建伟,等.机会网络[J].软件学报,2009,20(1):124-137. XIONG Yong-ping,SUN Li-min,NIU Jian-wei,et al. Opportunistic networks[J].Journal of Software,2009, 20(1):124-137.(in Chinese)

[4] Perkins C,Royer E.Ad hoc on-demand distance vector routing[C]//Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications.New Orleans:IEEE,1999:90-100.

[5] Namboodiri V,Agarwal M,Gao L.A study on the feasibility of mobile gateways for vehicular ad-hoc networks [C]//Proceedings of the First International Workshop on Vehicular Ad Hoc Networks.Philadelphia:ACM,2004, 66-75.

[6] Naumov V,Gross T R.Connectivity-aware routing(CAR) in vehicular ad doc networks[C]//Proceedings of 2007 IEEE INFOCOM.Anchorage:IEEE,2007:1919-1927.

[7] Karp B,Kung H T.GPSR:greedy perimeter stateless routing for wireless networks[C]//Proceedings of 2000 MOBICOM.Boston:ACM,2000:243-254.

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

[9] Saleet H,Langar R,Naik K,et al.Intersection-Based Geographical Routing Protocol for VANETs:A Proposal and Analysis[J].IEEE Transactions on Vehicular Technology,2011,60(9):4560-4574.

[10] Yong Ding,Li Xiao.SADV:Static-Node-Assisted A-daptive Data Dissemination in Vehicular Networks[J]. IEEE Transactions on Vehicular Technology,2010,59 (5):2445-2455.

[11] Zhao Jing,Cao Guohong.VADD:Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks[J].IEEE Transactions on Vehicular Technology,2008,57(3): 1910-1922.

[12] Jeong J,Guo S,Gu Y,et al.Trajectory-Based Data Forwarding for Light-Traffic Vehicular Ad Hoc Networks[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(5):743-757.

[13] Jeong J,Guo S,Gu Y,et al.Trajectory-based Statistical Forwarding for Multi-hop Infrastructure-to-Vehicle Data Delivery[J].IEEE Transactions on Mobile Computing,2012,11(10):1523-1537.

[14] Durresi M,Durresi A,Barolli L.Emergency broadcast protocol for intervehicle communications[C]//Proceedings of the International Conference on Parallel and Distributed Systems.Fuduoka:IEEE,2005:402-406. [15] Tonguz O K,Wisitpongphan N,Bai F.DV-CAST:A Distributed Vehicular Broadcast Protocol for Vehicular Ad Hoc Networks[J].IEEE Wireless Communications, 2010,17(2):47-57.

[16] Korkmaz G,Ekici E,Zgüner F,et al.Urban multi-hop broadcast protocol for inter-vehicle communication systems[C]//Proceedings of 2004 ACM International Workshop on Vehicular Ad Hoc Networks.Philadelphia:ACM,2004:76-85.

[17] Wantanee Viriyasitavat,Ozan K.Tonguz,Fan Bai.UV -CAST:An Urban Vehicular Broadcast Protocol[J]. IEEE Communications Magazine,2011(11):116-124. [18] Allal S,BoudjitS.GeocastRoutingProtocolsfor VANETs:Survey and Guidelines[C]//Proceedings of International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing.Palermo:IEEE, 2012:323-328.

XU Fu-long was born in Zhumadian, Henan Province,in 1980.He received the M. S.degree and the Ph.D.degree from University of Electronic Science and Technology of China in 2006 and 2011,respectively.His research concerns computer network and software architecture.

Email:fulongxu@hotmail.com

刘志建(1972—),男,四川广安人,2000年于西南交通大学获硕士学位,主要研究方向为计算机应用。

LIU Zhi-jian was born in Guang′an,Sichuan Province,in 1972.He received the M.S.degree from Southwest Jiaotong U-niversity in 2000.His research concerns computer application.

Routing Protocols for Vehicular Ad Hoc Network: Research Advances and Comparisons

XU Fu-long,LIU Zhi-jian
(Southwest China Institute of Electronic Technology,Chengdu 610036,China)

Vehicular Ad Hoc Network(VANET)is a new type of Mobile Ad Hoc Network.As an active research field in wireless mobile networks,it has been a big challenge to design effective routing protocols in VANET because of the intermittent connectivity of the network.The characteristics and applications of VANET are introduced,and the routing protocols are classified.On this basis,some typical routing protocols for VANET are discussed,their features are compared and summarized,and several research suggestions are presented,which can provide reference for researches on VANET routing protocol.

MANET;VANET;routing protocol;intermittent connectivity

date:2013-01-04;Revised date:2013-06-24

**通讯作者:fulongxu@hotmail.com Corresponding author:fulongxu@hotmail.com

TN915.04;TP393

1001-893X(2013)10-1393-08