0 引言

近年来出现的车载自组织网络(Vehicular Ad Hoc Networks，VANETs)是由一组运动的车辆所组成，也可以包含一些固定的通信基础设施，支持车辆-车辆(Vehicular to Vehicular，V2V)或者车辆-通信设施(Vehicle to Infrastructure，V2I)之间的通信^[1]。使用VANETs可以提供交通拥堵告警、交通事故报警等服务，以提高通行效率、增强驾乘人员的安全性，还可以提供住宿餐饮、加油站信息以及驾乘人员的休闲娱乐等服务，正在受到汽车制造商、政府和研究机构等的广泛关注^[2-5]。

不同于移动自组网(Mobile Ad Hoc Networks，MANETs)，VANETs具有节点移动速度更快，链路拓扑结构变化剧烈，节点的网络连接经常处于断开和分割状态；信号传播受到路旁建筑的阻挡而具有沿道路传播等特点。

目前，关于VANETs路由算法的研究已经取得了很多成果，但是现有的VANETs路由算法很少考虑使用路旁设施辅助路由。路旁设施属于智能交通系统和智慧城市的必要组成部分，据美国ITS协会发布的车联网指南预测，美国30万个信号控制路口将采用路旁设施运行V2I应用^[6]。利用路口设施中继辅助可以大大提高VANETs路由算法的性能。

相关研究成果表明，VAHDAT A等人提出的感染路由（Epidemic）算法^[7]在网络负载较低的环境中表现出优良的性能。但是在高网络负载条件下，Epidemic会产生较严重的信道竞争和冲突，引起其性能的急剧恶化^[1，8-10]。因此出现了很多针对Epidemic算法的改进方案。

所提出的路口设施辅助车载自组织网络感染路由（Intersection-Relay-Assisted Epidemic Routing，IRAER）算法，将车辆的邻居节点按所在的道路方向的不同，分别划分为不同的区域，在每个区域选择一个距离自己最远的邻居节点感染消息，直到将消息投递给目标节点。IRAER设计实现了区域贪婪感染方案、消息感染机制等。另外，通过所建立的随机模型，将IRAER产生的副本数量与Epidemic算法进行了对比分析，并通过实验进行了验证。

由于现有的单副本单播路由算法均不能适用于目标节点不停运动的场景，故仿真实验选择与低负载条件下路由性能最优的Epidemic算法进行对比。仿真结果表明，所提出的IRAER算法在各种场景下实现的投递成功率、投递时延性能均优于Epidemic算法。即使在低负载条件下，IRAER亦实现与Epidemic算法相当的路由性能。

1 相关工作

为了在不同节点密度以及负载情况下实现最优的消息可达性，研究工作者做了很多针对Epidemic算法的改进工作。

概率感染(Probabilistic Epidemic)路由算法^[11]，持有消息的节点仅以概率p感染邻居节点，故可以在一定程度上减少副本数量，降低信道竞争和冲突。(p，q)Epidemic路由算法^[12]，源节点以概率p感染邻居节点，其余节点以概率q感染。这两种感染算法虽然也可适用于VANETs，但均没有结合的道路特点。为了降低高负载下的资源竞争，SAMOR^[13]使用了限制副本数量的策略。此方案显著降低了信道竞争，但牺牲了消息的可达性。

结合智慧交通和智慧城市的建设和发展，有些文献也引入了路旁设施辅助路由策略。LEE W H等人假设城市道路的路口均安装有路旁设施，用以估算路口之间的消息转发时延^[14]。SADV^[8]同样引入了路口设施，当在最优方向的道路上没有车辆可供转发时，将消息转发到路口设施缓存。SRR^[9]则提出在部分路口使用路旁设施缓存消息。但是，由于缺乏及时可靠的位置服务支持，这些算法仅适用于目标节点固定且已知的V2I通信。

区别于以上研究成果，本文所提出的IRAER算法一方面充分考虑了城市道路环境消息转发的特点，另一方面大大降低了高负载场景下消息产生的副本数量，进而减少了对网络带宽等资源的竞争，保证了高负载下的消息可达性。再者，所提出的IRAER算法属于感染路由算法，可适用于目标节点移动且位置未知的V2V通信场景。

2 IRAER算法

2.1 假设条件

IRAER假设城市道路的路口均安装有路由辅助设施。同时假设道路上的车辆均安装了一套无线通信设施，并通过这套设施与其他位于无线通信半径R范围内的车辆以及路口设施进行通信。车辆同时内置电子地图，供路由计算使用。车辆位置定位可通过车载GPS系统实现。

2.2 信标消息

与Epidemic算法以及其他类Epidemic算法相同，IRAER同样使用周期性广播的信标消息进行邻居发现和消息摘要矢量（Summary Vector，SV）的交换。

在信标消息中包含节点ID、当前位置坐标以及本地所缓存消息的SV。IRAER的每个节点都维持一个邻居列表，当节点收到一个信标消息后，如果信标消息携带的ID在邻居列表中不存在，表明一个新的邻居进入通信范围，则将其ID、位置坐标、SV以及时间戳作为一个条目插入到邻居列表中；如果信标消息中的节点ID在邻居列表中已经存在，则更新该ID对应的条目；如果超过一个信标周期仍然没有收到来自于某一邻居车辆的信标消息，则认为该邻居已经离开通信范围，将其从邻居列表中删除。

2.3 邻居节点的区域划分

与其他感染算法不同，IRAER根据节点的邻居所在的不同道路方向划分为不同的区域。位于两个路口之间的道路上的节点，其邻居节点可以划分为两个区域。位于路口的节点（包括路由辅助设施），由于在每个相邻路口方向都可以进行感染，则位于该节点和每个相邻路口之间的邻居均为一个区域。

在节点N的一个邻居区域Z_i中，距离它最远的一个节点称为节点N在Zi的候感节点。

2.4 区域贪婪感染

与其他感染算法不同，IRAER使用贪婪感染机制，在每一个邻居区域中选择一个候感节点进行感染。这样，在一簇车辆节点中，对于新产生的消息，该消息将以步长R逐一选择候感节点进行感染。

对于在节点本地所缓存的消息，通过与邻居节点之间进行SV交换，获取需要感染的消息集合并实现消息交换。如果一个节点N所缓存的消息在它的邻居区域中的某一个节点中缓存，由于该邻居节点可以感染距离更远的节点，所以节点N不需要触发感染。

假设ZSV_i为节点N的一个邻居区域Z_i中的所有节点SV的集合，SV_N表示节点N的SV，则在SV_N中缓存且在ZSV_i中没有缓存的消息集合S_i，节点N才可以将这些消息转发给Z_i中的候感节点。

ZSV_i可以表示为：

为了使得消息在路口可以向其他路口方向感染，消息必须感染位于路口的辅助设施，而不能跨越路口。即，节点N在Z_i中如果存在辅助设施节点A，N在Z_i中的候感节点将被设置为A。IRAER算法的消息感染过程可以表示为图1所示。

图1中，空心圆代表道路上的车辆，空心圆的编号代表车辆ID，箭头代表消息感染的方向，位于路口中央的空心圆代表路由辅助设施。从道路左边转发过来的一个新的消息M的副本位于节点1，节点1的邻居区域中的候感节点为2，因此节点1将M的副本转发给节点2。由于节点A是路由辅助设施，因此节点2会将M的副本转发给节点A。由于节点A在路口的北向道路中只有一个邻居车辆3，故A将M的副本转发给邻居节点3。由于节点3同时在节点A的东向邻居区域，故在节点A的东向邻居区域ZSV中已经包含了消息M的ID，则节点A不向其东向邻居区域感染其他邻居节点，消息M由节点3感染节点4。由于节点5是节点A的南向邻居区域的候感节点，故节点A将M的副本转发节点5。

2.5 感染机制

由于IRAER算法中一个节点对自己是否为候感节点毫不知情，故不能主动请求消息集合S_i。因此与Epidemic算法不同，IRAER适用于使用“推”机制触发感染^[15]。

Epidemic算法虽然采用的是“拉”机制进行感染，但由于信标消息的广播是异步的，故可以保证消息几乎可以在产生之后及时感染其他节点。IRAER为了使得消息可以及时感染候感节点，故在节点N感染消息之后，立即根据S_i将消息感染给候感节点。如果感染失败，或者候感节点刚好离开了节点N的无线覆盖范围，则在下一个广播周期通过交换SV重新感染。

3 IRAER副本数量分析随机模型

WISITPONGPHAN N等人^[16]和TIAN D X等人^[17]分别根据探测数进行统计分析发现，在车辆密度较稀疏的情况下，道路上的车辆间距分布符合指数分布规律。利用此规律，可以对IRAER在感染过程中产生的副本数量与Epidemic进行对比分析。

根据WISITPONGPHAN N等人的研究结果，车辆簇的平均长度可表示为：

其中，λ_S为车辆间距指数分布的参数。假设地图上道路的总长度为L，节点的数量为K，则λ_S可表示为：

4 仿真

现有的VANETs单副本单播路由算法如VADD^[1]、IBFP^[10]、GFAVR^[18]，以及路口设施辅助路由算法如SADV^[8]、SRR^[9]等，由于缺乏及时可靠的位置服务，不能适应于目标节点不停运动的通信场景。而IRAER不需要目标节点的位置信息。且众多理论和仿真实验表明，Epidemic路由算法在低负载条件下的路由性能是最优的^[1，8-10]，因此仿真实验选择了与Epidemic路由算法进行对比。

4.1 仿真设置

仿真实验平台采用的是网络协议仿真器NS-2^[19]，仿真实验地图环境采用常用的曼哈顿网格地图^[1，20-22]。车辆运动数据集使用开源软件VanetMobiSim^[23]所产生，道路设置为双向两车道，限速为22 m/s(80 km/h)。

仿真过程中，节点之间使用CBR应用层协议进行通信，CBR的源和目标都是随机产生。CBR的负载分别设置为50 B和600 B以评估不同消息负载下的协议性能。车辆数量为100~400，以产生不同节点密度的道路环境。仿真参数如表1所示。

4.2 投递成功率

投递成功率定义为CBR消息在给定时间内成功投递到目标节点的比例。图2所示为车辆数量为100、CBR负载为50 B的低信道竞争网络环境以及车辆数量为400、CBR负载为600 B高信道竞争网络环境下的投递成功率累积概率密度分布。

从图中可以看出，在Epidemic最适合的低信道竞争网络环境下，IRAER实现的投递成功率仍然优于Epidemic；而在信道竞争较大的网络环境下，IRAER的投递成功率则大大高于Epidemic。

4.3 投递时延

投递时延定义为消息投递成功需要的平均时间。图3为两种CBR负载（50 B、600 B）分别在不同车辆密度条件下实现的平均投递时延。

从图3可见，IRAER在高车辆密度和高负载条件下实现的投递时延大大低于Epidemic，且IRAER受负载条件的影响更小。

4.4 副本数量

副本数量定义为CBR消息投递成功时，在网络中所有节点中所缓存CBR副本数量的平均值。IRAER与Epidemic在仿真过程中产生的副本数量比例与理论分析结果的对比如图4所示。

从图4可知，随着车辆密度的增加，IRAER与Epidemic产生的副本数量比例越接近于理论分析结果。其原因在于车辆密度增加后，消息平均投递时延较低，因而由于车辆簇成员的变化引起的感染数量也较低。

5 结束语

车载自组织网络由于节点的运动速度快，网络连接经常处于断开状态，因而消息的投递时延较长、性能较差。在路口增加路由辅助设施则可以显著提高消息投递性能。本文提出的IRAER算法利用路口设施辅助路由，同时分析并利用了车辆簇的特点，将邻居节点划分为不同的区域，在每个邻居区域中仅选择一个距离最远的候感节点进行感染，故而在车辆密度较大的场景下大大降低了感染所产生的副本数量，进而降低了对带宽资源的竞争和冲突，提高了路由性能。

本文利用道路上车辆分布的统计规律，分析了IRAER与Epidemic产生的副本数量的关系，并通过仿真实验进行了验证。仿真实验结果同时表明，所提出的IRAER路由算法在高负载环境下实现的投递成功率和投递时延性能指标均显著高于Epidemic算法，同时在Epidemic最适合的低负载环境下性能亦可相匹敌。

参考文献

[1] ZHAO J，CAO G.VADD：Vehicle-assisted data delivery in vehicular Ad hoc networks[J].IEEE Transactions on Vehicular Technology，2008，57(3)：1910-1922.

[2] HUANG C M，LIN S Y.An early collision warning algorithm for vehicles based on V2V communication[J].International Journal of Communication Systems，2012，25(6)：779-795.

[3] 李东颖.车联网将成产业革命推动力[N].北京青年报，2014-08-06(1).

[4] CUNHA F，VILLAS L，BOUKERCHE A，et al.Data communication in VANETs：Protocols，applications and challenges[J].Ad Hoc Networks，2016，44：90-103.

[5] AZEES M，VIJAYAKUMAR P，DEBORAH L J.Comprehensive survey on security services in vehicular ad-hoc networks[J].IET Intelligent Transport Systems，2016，10(6)：379-388.

[6] BAYLESS S H，GUA A.Connected vehicle technical insights[EB/OL].(2015-07-27)[2016-10-11].http：//www.itsinternational.com/sections/nafta/features/its-america-publishes-connected-vehicle-guidance/.

[7] VAHDAT A，BECKER D.Technical report CS-200006[R].Durham，USA：Duke University，2000.

[8] DING Y，XIAO L.SADV：Static-node-assisted adaptive data dissemination in vehicular networks[J].IEEE Transactions on Vehicular Technology，2010，59(5)：2445-2455.

[9] TIAN R，ZHANG B X，LI C，et al.Sparsely-deployed relay node assisted routing algorithm for vehicular ad hoc networks[J].Wireless Communications & Mobile Computing，2015，15(9)：1309-1319.

[10] GUAN X，HUANG Y，CAI Z P，et al.Intersection-based forwarding protocol for vehicular ad hoc networks[J].Telecommunication Systems，2016，62(1)：67-76.

[11] ZHANG X，NEGLIA G，KUROSE J，et al.Performance modeling of epidemic routing[J].Computer Networks，2007，51(10)：2867-2891.

[12] MATSUDA T，TAKINE T.(p，q)-Epidemic routing for sparsely populated mobile ad hoc networks[J].IEEE Journal on Selected Areas in Communications，2008，26(5)：783-793.

[13] 孙海峰，罗光春，秦科.社会感知多副本车载自组织网络机会路由协议[J].计算机应用研究，2014，31(3)：857-859，887.

[14] LEE W H，HWANG K P，WU W B.An intersection-to-intersection travel time estimation and route suggestion approach using vehicular ad-hoc network[J].Ad Hoc Networks，2016，43：71-81.

[15] AKDERE M，BILGIN C C，GERDANERI O，et al.A comparison of epidemic algorithms in wireless sensor networks[J].Computer Communications，2006，29(13-14)：2450-2457.

[16] WISITPONGPHAN N，BAI F，MUDALIGE P，et al.Routing in sparse vehicular ad hoc wireless networks[J].IEEE Journal on Selected Areas in Communications，2007，25(8)：1538-1556.

[17] TIAN D X，LEUNG V C M.Analysis of broadcasting delays in vehicular ad hoc networks[J].Wireless Communications & Mobile Computing，2011，11(11)：1433-1445.

[18] BAZZI A，ZANELLA A.Position based routing in crowd sensing vehicular networks[J].Ad Hoc Networks，2016，36：409-424.

[19] NSNAM.Network Simulator(ns-2)[CP/OL].(2014-12-19)[2015-03-06].http：//nsnam.isi.edu/nsnam/index.php/Main_Page.

[20] WU T Y，WANG Y B，LEE W T.Mixing greedy and predictive approaches to improve geographic routing for VANET[J].Wireless Communications & Mobile Computing，2012，12(4)：367-378.

[21] SUN H F，LUO G C，CHEN H.JTAR：Junction-based traffic aware routing in sparse urban VANETs[J].IEICE Transactions on Communications，2012，E95B(3)：1007-1010.

[22] JERBI M，SENOUCI S-M，RASHEED T，et al.Towards efficient geographic routing in urban vehicular networks[J].IEEE Transactions on Vehicular Technology，2009，58(9)：5048-5059.

[23] HARRI J，FIORE M，FILALI F，et al.Vehicular mobility simulation with VanetMobiSim[J].Simulation，2009，87(4)：275-300.