车联网中基于路边设施的广播协议研究

程晗晗，樊秀梅

(1. 天津科技大学计算机科学与信息工程学院，天津 300222；2. 北京理工大学计算机学院，北京 100081)

在车间通信(inter-vehicle communication，IVC)系统中，车辆间依靠广播共享紧急事变、交通状况、天气和道路数据以及传播广告和通知．然而，车辆移动的高速度减少了可以进行信息交换的时间，并引起快速和频繁的拓扑变化，导致无线信道的更加不稳定．因此，能够适应 VANET(vehicular Ad hoc network)基本特征、满足驾乘人员需求的交通信息广播协议需要具备以下条件[1]：支持节点的高速移动；保证信息分发的实时性、可靠性和可达性；具有较高的资源利用率；适应无线网络恶劣信道环境；具有较强的可扩展性和鲁棒性；为多种应用信息提供资源公平共享机会．

MANET(mobile Ad hoc network)已开发出大量的单播路由协议．然而，这些协议有其独特的特点，在VANET中不能被有效地利用．研究人员已经针对VANET开发了单播路由协议[2–6]．这些协议中的大部分使用基于位置的贪婪方法来实现车与车之间的通信．基于位置的方法是利用节点的坐标或与相对位置有关的信息，通过网络来生成一个有效的路由[2–3]．在稀疏的车载网中，以路由数据包为目的协议被称为延迟–容忍路由协议．在一些特定的网络环境下，如星际网络、军事 Ad hoc网络、传感器网络、车辆 Ad hoc网络会经常出现网络断开的现象，导致报文在传输过程中不能确保端到端的路径，这类网络被称为容迟网络或DTN．在这种情况下，建立端到端的路由也许是不可能的，因此文献[6]和文献[7]使用携带转发的方法来实现节点间的重新愈合．

大多数车载自组网研究专注于高密度网络拓扑结构下广播风暴问题的协议算法，这些研究都是基于VANET网络连接良好的情形下进行的．文献[8]根据加利福尼亚州 I-80高速公路上的车辆交通数据得出，在 100%的设备配备率下(即所有的车辆都配备了无线通信功能)，深夜公路上的网络断开概率达到35%；而在网络连接良好的上下班高峰期，即使使用大的设备配备率，也可以观察到网络断开现象．可见，网络断开问题是一个重要的研究内容，因此需要开发一个可靠高效的路由协议，以支持高度多样化网络拓扑结构．

针对车联网中存在的网络断开问题，旨在缩短节点间的重新愈合时间，本文在已有携带转发机制的基础上，提出基于路边设施(road side units，RSU)的广播协议．

1 常用携带转发机制

1.1 SCF(store-carry-forward)机制

SCF[9–10]机制利用反方向行驶的车辆作为转发者将消息传递给下一簇(在相同方向上行驶并且只能以单跳或多跳的方式彼此通信的车辆属于同一簇)内的车辆，然而只能传递给下一簇内的第 1辆车．当DSRC(dedicated short-range communications)设备的普及率很低时断开节点的数量就会增加，由反方向转发者执行的 SCF机制的操作数量增加，从而导致SCF开销增大．

1.2 SCB(store-carry-broadcast)机制

为了减少 SCF开销，当一个转发者能够在连续的断开节点间执行多次 SCF操作时，就需要避免分派多个转发者，因此提出 SCB[9]机制，S与随后的节点 V1断开，SCB操作为(图 1)：S将消息发送给X(反向转发者)→V1，…，Vk(2,R广播范围内的节点)→X 检查是否有邻节点 X′距离 Vk+1较近，若存在 X′就成为新的转发者；若不存在 X保持．Vk+1与Vk断开，那么转发者就会对从 Vk+1开始的下一簇广播消息→当转发者发现广播范围外的第 1辆车与它前面的车辆保持连接，那么它就会丢掉此消息．

图1 SCB机制示意图Fig.1 Schema of SCB

以上 2种机制都无法保证簇尾车辆遇到反方向转发者的等待时间，尤其是在 DSRC设备的普及率较低时就会有更长的时间延迟．

2 基于RSU的广播协议模型

当研究VANET中的数据包传送问题时，需要区分开以下 2种情形：(1)向后方车辆广播安全消息，即源车辆检测到事故后产生1个警告信息，并将其传播给后方车辆，后方车辆在到达潜在危险区之前能够得到此警告信息；(2)当目标节点离源车辆较远时，将消息发送到远方的特定节点，这时数据包到达目的地所需跳数取决于多种因素，如发送者与目的地之间的距离和传递数据包的路径．

2.1 向后方车辆广播安全消息及其重新愈合时间计算

对于向后方传递安全信息的情况，基于以下6个规则可以将固定设施RSU应用于广播协议模型：

(1)当源车辆V0检测到危险或事故，它向簇内的下一邻节点广播安全消息，邻节点可能是部署在公路上的RSU或者与V0同方向行驶的后方车辆(V0方向作为目的地方向)．

(2)如果RSU接收到安全信息，将定期向行驶而来的车辆广播安全消息．通过 RSU广播安全消息，可以减少大量广播负载量．

(3)当消息不再是必要的，RSU将丢弃消息，停止广播，放弃安全警告．

(4)如果 V0的簇内未部署 RSU，车辆 Vk(即 V0簇的尾车辆)将承担指定消息传递转发者的责任．

(5)行驶在与 Vk相反方向中的相邻车辆被选择为转发器．

(6)转发器接收了安全信息后将携带消息，然后传递到一个重新愈合节点(RSU或断开车辆 Vk+1)．通过此规则可以减少重新愈合的跳数，这对于减少VANET中车辆密度较高区域的广播分支是非常重要的．

事故发生后，源车辆生成并向后方车辆传递安全信息，根据车辆与 RSU的位置，可以分为路边设备在源车辆簇的传输范围内和不在其传输范围内 2种情况进行讨论．

2.1.1 路边设备在源车辆簇的传输范围内

因为 RSU(U1)在源车辆簇的传输范围内，所以当交通安全消息由源车辆 V0发出后，该消息可以通过簇内的节点传递到U1，如图2所示．需要注意的是车辆Vn不需要是簇内最后一辆车．

图2 路边设备在源车辆簇的传输范围内Fig.2 Illustration and diagram of RSU in the transmission range of source vehicle cluster

根据文献[11]的实验数据可知，车辆密度服从指数分布．沿公路上东行线行进的两辆车间的距离可以用车辆密度eλ计算．位于间隔Ur(源车辆到后方第1个 RSU间的距离)中车辆的数目eU()N r 服从泊松分布

假设间隔Ur中有n辆车，第i－1辆车与第i辆车

之间的距离为iw，根据泊松分布的递增方式，n辆车均匀分布在Ur范围内，因此基于文献[12–13]中区间的随机划分结果，得到

下一个RSU在源车辆的传输范围内的概率为

式中：UD为两个相邻RSU之间的距离；为Ur的密度函数．

2.1.2 路边设备不在源车辆簇的传输范围内

当U1不在源车辆簇的传输范围内，即U1与源车辆簇的最后一辆车 Vk之间的距离大于 R时(图3(a))，交通安全消息被存储并转发到在相反方向上移动的车辆X，由X将该消息中继到U1或下一簇中的第1辆车Vk+1．

图3 路边设备不在源车辆簇传输范围内Fig.3 Illustration and diagram of RSU not in the transmission range of source vehicle cluster

当下一个节点是 RSU 时(图 3(b))，随后的 U1为重新愈合节点，U1和车辆 X之间的距离为此时，将安全消息传送到下一个节点的重新愈合时间U[]Et 近似为

式中：wx为车辆 X与源簇中最后一辆车的覆盖范围之间的距离；西行道中车辆之间的距离wλ是西行道上的车辆密度．在间隔cr中车辆V0—Vk均紧密相连(即连续两车的间距都小于 R)，此情况概率为c()Wr．在这种情况下，如果 V0后方没有连接的车辆(k＝0)，则rc=0，概率为如果V0后面至少有1个连接的车辆(即0wR＜)，则rc＞0，概率为因此

下一节点是 Vk+1时(图 3(c))，Vk+1是重新愈合节点，Vk与Vk+1间距离kw ＞R，X和Vk+1之间的距离是车辆 X和 Vk+1的速度分别为 ve和 vw，假设可得此时将安全消息传送到下一节点的重新愈合时间V[]Et 为

结合式(5)、式(6)，安全消息传递到愈合节点的重新愈合时间为

式(7)所得结果为重新愈合时间的上限．

2.2 发送消息至特定节点

当车辆 VA需要发送 1个数据包到车辆 VD，若VD在 VA的附近区域，VA将数据包广播到 VD；若不在，VA发送该数据包到其最近的 RSU(U1)．如果 U1具有 VD(表示 VD在 U1的周边)的位置，则将数据包发送到 VD，如果 U1没有 VD的位置，它会向所有RSU的邻居发送包含 VD的位置查询数据包，如果U1的邻居 RSU之一(U2)具有的 VD的位置，它发送1个确认字符ACK到U1，U1将数据包转发到U2，由U2发送到 VD．如果 U1在一定时限 T内没有收到ACK，它向 2跳之外的所有RSU发送位置查询报文(即 RSU邻居的所有 RSU邻居)，然后 3跳外的RSU，并依此类推．该操作继续进行，直到 U1接收到有关VD位置的ACK或者检查过所有的RSU．

RSU将数据包发送到车辆，首先需要预测车辆的位置．如图4所示，RSU(U)根据得到的车辆V的位置、平均速度和最后一次发送信标的方向来预测V接收到数据包P时的位置．

图4 车辆位置预测原理Fig.4 Diagram of estimating the distance of vehicle from RSU

假设U最后一次接收到V发来的信标显示，U、V 间的距离为1d、时间戳为1t、并以速度1v向左行驶．经过时间ct后，V行驶的距离为(ds为考虑安全而设的附加距离)，U、V 间距为若V背离U行驶，则间距为，又由(其中 r为 U的传输范围，0t为两个邻节点间的平均传输时间，dt和d∗分别为车辆携带数据包的平均时间和平均距离，st为安全时间)，因此P发送途中V行驶的距离接收到P时距U的距离为V行驶的总距离为然后根据此距离推测 P可能被发送到的区域 Ae，若 V行驶的路段没有交叉路口，则将 Ae定义为以 V接收 P的预测坐标为圆心，d的误差因子(可设为 0.3,d)为半径的圆；若 V 的行驶路段内有交叉路口，则将Ae定义为以路口坐标为圆心，ar为半径的圆．U将数据包传送给 Ae区域内的车辆，然后再转发给V．

3 仿真实验

在Qualnet实验环境中对SCF、SCB以及本文提出的方法进行仿真测试．实验场景中的 Pathloss model 配置为使用 Street microcell模型．

Mobility And Placement 配置如下：

Node-position-file Opportunity.nodes

Mobility files NONE

Mobility-position-granularity 1.0

节点无线子网和网络接口参数格式配置如下：

Subnet N8-169.0.0.0 {0 thru 40} default

[N8-169.0.0.0] PHY-RX-model PHY802.11b

NETWORK-PROTOCOL IP

其他参数设置：路段长度为 300,km；车辆速度范围为 10～40,km/h；节点数量为 100；Hello消息间隔为10,s；MAC协议采用802.11b．

在所有车辆都配备 DSRC设备条件下，不同的RSU数量、车辆密度时采用本文方法的仿真结果见图 5(a)；在 DSRC设备配备率ρ分别为 10%、50%、100%的情况下测试SCF、SCB机制的重新愈合时间，仿真结果见图5(b)．

由图 5(a)可以看出：重新愈合时间随着车辆密度λe和λw的增加而减少；当辆/km时，重新愈合时间＜0.1,s．这是因为：对于 RSU 数量在大多数情况下交通安全信息可以被传递到1个RSU；对于UN＝0，如果eλ和wλ足够大，也可以使得在高速公路上大多数车辆相连接，所以重新愈合时间均较短．对比本文方法与 SCB、SCF可知，本文方法的重新愈合时间最短，以车辆密度 λ＝10辆/km为例，SCF的重新愈合时间为 4～6,s，SCB约为20,s，而应用 RSU 的重新愈合时间小于 1,s，当车辆密度更小时本文方法的优势更加明显．

图5 仿真结果Fig.5 Results of simulation

4 结 语

本文针对车联网中存在的网络断开问题，通过对携带转发机制的分析，提出将固定设施 RSU应用于广播协议．仿真表明，部署 RSU之后很大程度上降低了 VANET的传输时延，且路段上的行驶车辆越多，重新愈合时间就越短，考虑到城市区域的车辆密度较高，可以借助路边设施来减小市区 VANET的广播风暴问题．虽然部署 RSU的密度可以控制在一定范围内，但由于 RSU的成本较高，无法广泛部署，因此对于RSU的部署方案还需进一步研究．

［1］ 李丽君，刘鸿飞，杨祖元. 车用自组网信息广播[J]. 软件学报，2010，21(7)：1620–1634.

［2］ 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.Piscataway：IEEE，2003：156–161.

［3］ Lochert C，Mauve M，Füÿler H，et al. Geographic routing in city scenarios[J]. ACM SIGMOBILE Mobile Computing and Communications Review，2005，9(1)：69–72.

［4］ Mo Z，Zhu H，Makki K，et al. MURU：A multi-hop routing protocol for urban vehicular ad hoc networks[C]//Proceedings of the 3rd IEEE International Conference on Mobile and Ubiquitous Systems Workshops. Piscataway：IEEE，2006：1–8.

［5］ Naumov V，Gross T R. Connectivity-aware routing(CAR)in vehicular ad-hoc networks[C]//Proceedings of the 26th IEEE International Conference on Computer Communications. Piscataway：IEEE，2007：1919–1927.

［6］ 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.

［7］ Ding Y，Wang C，Xiao L. A static-node assisted adaptive routing protocol in vehicular networks[C]//Proceedings of the 4th ACM International Workshop On Vehicular Ad Hoc Networks(VANET’07). New York：ACM，2007：59–68.

［8］ Wisitpongphan N，Tonguz O，Bai F，et al. On the routing problem in disconnected vehicular ad-hoc networks[C]//Proceedings of the 26th IEEE International Conference on Computer Communications. Piscataway：IEEE，2007：2291–2295.

［9］ Sou S，Lee Y. SCB：Store-Carry-Broadcast scheme for message dissemination in sparse VANET[C]// Proceedings of the 75th IEEE Vehicular Technology Conference.Piscataway：IEEE，2012：1–5.

［10］ 王美琛，唐伦，陈前斌. 基于自适应选路策略的VANETs路由协议[J]. 计算机应用与软件，2013，30(3)：62–66.

［11］ 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.

［12］ David H A ，Nagaraja H N. Order Statistics[M].Hoboken，NJ：John Wiley & Sons Inc，2003.

［13］ Darling D A. On a class of problems related to the random division of an interval[J]. The Annals of Mathematical Statistics，1953，24(2)：239–253.