VANET中基于分布式的分簇的路由机制

郑鑫　徐慧娟

摘 要： 车载自组网（VANET）是一种将高速移动车辆作为通信节点的自组网，动态的拓扑结构致使传统的自组网路由机制不再适用。为此，提出基于分布式的分簇路由机制（DCRM）。DCRM首先引用RTB/CTB握手策略，源节点利用RTB/CTB数据包，获取其一跳邻居的信息，然后源节点根据每两个邻近节点间的距离小于门限值的原则，以分布式方式对这些邻居节点进行簇划分。随后，将每个簇中选择一个离源节点最远的节点作为簇头，源节点将消息传输至簇头。接收消息后，簇头成了源节点，重复此过程直至消息传输至目的节点。仿真结果表明，提出的DCRM提高了消息传输效率、降低了消息传输时延。

关键词： RTB； CTB； 簇； 路由机制； 车载自组网

中图分类号： TN911?34； TPT393 文献标识码： A 文章编号： 1004?373X（2016）04?0016?05

Abstract： Vehicle?mounted Ad hoc network （VANET） is one kind of Ad hoc network， in which the rapidly moving vehicles are taken as communication nodes. Due to the dynamic topology structure， the traditional Ad hoc network routing mechanism is no more suitable for the current situation. Therefore， the distributed clustering?based routing mechanism （DCRM） is proposed in this paper. Firstly， the RTB/CTB handshake strategy is introduced into DCRM， and the RTB/CTB data package is utilized by source node to obtain the information of neighbor nodes. Secondly， if the distance between each couple of nearby vehicles is lower than a threshold value， the two vehicles will be considered to be the same cluster. The furthest vehicle inside each cluster is selected as the cluster?head （CH）， to which the data message is transmitted only. Upon receiving the data message， each CH will become the message source for the next contention phase， and the DCRM is repeated until data message is transmitted to the destination. The simulation result shows that the proposed DCRM can improve the efficiency of message transmission and reduce the time delay of message transmission.

Keywords： RTB； CTB； clustering； routing mechanism； VANET

0 引 言

车载自组网VANET（Vehicular ad Hoc Network）被认为是应用于未来智能交通系统的最有前景的技术，提供了多类的应用服务，实现了车间短距离通信。如图1所示，VANE中车辆装有车载单元OBU（On?Board Unit），实现了车间通信V2V（Vehicle to Vehicle）和车与基础设施通信V2I（Vehicle to Infrastructure）。有效的V2V通信能够增强车辆行驶安全、提高交通效率[1?4]。然而，由于动态的拓扑，变化的车速以及不均匀的车辆分布，维持不同簇内的V2V通信存在巨大的挑战。因此，多数路由机制采用广播传输，进而实现快速、实时地分享交通信息。但是，广播传输一方面提高了共享消息的速率，另一方面引发信道频繁的竞争以及数据包的碰撞，导致大量的冗余数据包，即广播风暴问题[5]。这直接影响了V2V通信效率。当车辆广播了一条消息，很有可能邻居车辆之前已经接收了此消息，这就导致消息传输冗余，降低信道资源利用率。

目前，已有较多针对传统的MANET环境下的广播风暴的处理方案的文献资料，但是针对VANET环境的文献较少[6]。多数研究工作是以VANET作为连通顺畅的网络为前提。在间歇式连接的VANET中，设计一个可靠、有效的路由协议仍是一个挑战。为此，提出基于分布式的分簇路由机制（Distributed Clustering?based Routing Mechanism，DCRM）。它充分利用车辆分布不均匀的特性，将邻近的车辆看成一簇，并为每个簇选择一个簇头，由簇头传输数据。DCRM采用源节点对其一跳邻居节点进行簇划分，这种分布式的簇划分有利用消息的快速传输，降低消息的传输时延、提高消息的传输效率。

1 相关工作

在VANET中，通常假定车间通信被分割成多个簇。簇内的车辆能够通过一跳或多跳方式与簇内其他车辆通信，但是，簇与簇之间不存在直接连接，这便形成了基于簇的路由协议[7]，如图2所示。

基于地理位置、移动方向以及其他信息，车辆形成不同的簇。簇提高了消息广播、转发效率，减少了不必要消息的复本的数目，降低了系统开销。Ni等认为每个簇内有三类节点（车辆）[8]：簇头、网关以及成员。网关车辆扮演着簇与簇间的连接角色。簇头车辆是指其通信范围能够遍历到簇内的任何一个节点的车辆。簇内成员就是非簇头、网关的簇内其他车辆。当网关车辆从其他车辆接收到消息，就立即向簇头传递，再通过簇头向簇内成员传输。但是，作者在文中并没有给出簇头的选择过程。Fasolo等提出了智能广播协议[9]。假定网络被分割成不同的分区（Sector）。每个车辆能够估计自己的位置，并且知道自己在哪个分区域。该协议利用竞争机制选择转发节点。尽管该协议看似有效，但是作者并没有证实其网络性能以及系统开销。此外，Luo等也考虑了车辆的位置信息，提出了基于簇的路由协议[10]。将地理区域划分为正方形网格（Foursquare gird）。簇头依据邻近的网格传输数据包。Sun等提出了基于RSU辅助的簇头选择机制[11]。通过部署RSU，并维持RSU与车辆间的连接，进而选择簇头。上述研究并没有考虑车辆的移动信息。实际上，车辆的移动影响了簇头的选择过程以及簇的稳定性。Benslimane等利用车辆的移动方向、车间距离以及信号强度RSS（Received Signal Strength）信息构建簇[12]。Gunter等在簇的碰撞阶段考虑了车辆移动，并且簇头具有最低的移动性以及离邻居车辆的距离最近的特性[13]。此外，Kayis等将车辆分为速度群[14]。在同一个速度群内的车辆在同一个簇内。Koyamparambil等提出了基于簇的MAC协议，形成稳定的簇[15]。利用车辆的位置、移动方向以及车道、速度信息划分簇。Hafeeze等利用相对速度、车间距离选择簇头[16]。据此，本文以分布式方式，并充分结合车辆位置，提出了DCRM。

2 系统场景及约束条件

考虑混合交通场景：车辆的行驶速度随机，车辆分布随机，以接收真实的交通场景。提出的DCRM，基于以下假设：假定有N个车辆，每个车辆标识为[υi]，[i=1，2，???，N，]其位置坐标为[xi，yi]，本文车辆与节点概念等同，可以互换；所有车辆都具备GPS定位功能和无线局域网络功能（WLAN capabilities）；每个车辆利用GPS系统获取自己的位置；每个车辆通过交互beacon 消息，能够获取邻居数；仅当车辆[υi]与[υj]的距离[dij]小于通信范围[R]，车辆[υi]与[υj]的通信链路才被建立。

3 DCRM

提出DCRM有两个目的：避免重播消息，缓解广播风暴问题；快速、有效地进行簇划分。在DCRM中，仅选择部分车辆进行消息转发，降低消息被重传的次数。首先对网络进行簇划分，每个簇产生一个簇头。簇头承担着簇与簇之间的消息传递的任务。提出的DCRM主要分为四个阶段：RTB传输，CTB传输、簇划分以及簇头选择，如图3所示。图3（a）中，源节点（车辆）向一跳邻居节点传输RTB控制包。随后，邻居节点通过设置等待时间轮流回复CTB控制包，如图3（b）所示。源节点接收CTB控制包，从中提取邻居节点的位置信息，并计算邻近车辆间的距离，进行簇划分，并选择离自己最远的车辆作为簇头，如图3（c）所示。最后，源节点向簇头传输数据包，如图3（d）所示。

3.1 RTB传输

当源节点需要传输数据时，先向所有邻居节点传输请求广播RTB（Request?to?Broadcast）控制消息。RTB属于MAC广播包，包含了节点的地理位置信息，约7.5 B。

3.2 CTB传输

一旦接收到RTB消息，车辆就计算离源车辆的距离[d]，[d]能够用于计算退避时间[tw]：

[tw=rtx-drtx?CWmax-CWmin+CWmin?tslot ]（1）式中：[rtx]为传输半径；[CWmax]，[CWmin]分别表示竞争窗口的最大、最小尺寸。

当退避时间[tw]计时完毕，车辆就向源节点回复CTB（Clear?to?Broadcast）数据包，其包含车辆ID以及离源车辆的距离，大小7.5 B。一旦收到有效了CTB数据包，车辆就退出竞争阶段。

3.3 簇划分

通过接收CTB数据包，源车辆获取了邻近车辆的位置以及距离信息，通过测量CTB消息的到达方向DOA（Direction of Arrival），源车辆计算邻近车辆间的距离。如果邻近区域的每两辆车辆的距离小于门限值[Dmin]，这两辆车辆将纳入同一个簇。[Dmin]的选择直接影响簇的数量。[Dmin]过大，每个簇内成员数就越多，若[Dmin]趋近于零，每车辆能够独立形成一个簇如图4所示。首先源节点对一跳邻居节点的所有车辆依据DOA按降序从“0”开始编号，假定有N个一跳邻居节点，对这些节点进行0至N的编号。设定[N×N]维零矩阵A，相应矩阵元素[Aij]的值为1，否则为0，如下所示：

依据矩阵A，算法2进行簇划分。矩阵[A]内每一行元素值表示该行所对应的节点离其他节点的距离是否小于门限值。检测连续出现“1”的行（假定[i]行），然后将该行元素[Ai，：]与下一行元素[Ai+1，：]值一一对应进行或运算，并进行相加，如式（4）所示。

[Ii=j=0NAi，jAi+1，j] （3）

其中：[I]表示一维数组。如果[Ii=m]表示[m]个节点构成一个簇，这[m]个节点的编号分别为[i]，[i]+1，…，[i+m-1]。

以式（3）为例，共检查到有3行出现连续1，并且[I0=4]，[I4=2]，[I6=1]。因此，节点编号0，1，2，3为一簇；4，5为一簇，6为一簇，如下所示：

3.4 簇头选择

源节点对源节点进行簇划分后，就给每个簇选择一个簇头CH。每个簇内离源车辆最远的车辆作为该簇的簇头CH。随后，源节点就将数据包传输到簇头。数据包大小约1 526 B。一旦接收到了数据包，簇头就变成下一轮源节点，类似，重复此过程，直接将数据包传输至目的节点。

4 数值分析

4.1 仿真场景

考虑高速场景，其基于中国上海的方形地图，区域面积为15 km2。如图5所示，该地图来源于OSM（Open Street Map）网址，仿真时间为300 s，具体的仿真参数如表1所示。

选择数据包传输率PDR（Packet Delivery Ratio）、端到端传输时延EED（End?to?End Delay）以及吞吐量（Through）三个性能指标考察路由机制。数据包传输率PDR表示源节点发送的数据包与目的节点成功接收的比率，是衡量网络拓扑结构中信息包正确接收的性能参数。数据包传输率越大，路由机制的性能越好。端到端传输时延衡量传输效率，时延越短，表示传输效率越好。同时，与BBC[17]，SRB[18]进行比较。仿真结果如图6～图8所示。

4.2 仿真结果分析

图6描述了数据包传输率随PDR随节点数的变化曲线。从图6可知，提出的DCRM的数据包传输率优于BBC和SBP方案，随着节点数的增加，优势随之增加。原因在于DCRM充分利用节点的移动特性，通过簇头转发数据，提高路由的稳定性，降低链路断裂的概率，提高数据包传输的效率。

图7显示了吞吐量随节点数的变化情况。从图7可知，DCRM，BBC，SBP的吞吐量随节点数的变化趋势相同。当车辆数少时，BBC的吞吐量略优于DCRM，SBP。这主要是因为车辆密度小，发生信道竞争概率小，采用直接广播的BBC存在优势。然而，随着车辆密度的增加，DCRM的优势突显出来，当节点数达到120时，吞吐量是BBC，SBP的3倍。

图8绘制了端到端传输时延EED随节点数的变化情况。与图7类似，DCRM，BBC，SBP的EED端到端传输时延随节点数的变化情况相同。在车辆密度较大时，DCRM的EED明显下降，比BBC下降约70%。

5 结 语

针对车载自组网VANET的消息传输机制问题，展开分析，并提出了基于分布式的分簇路由机制DCRM。DCRM以分布式方式对网络节点进行簇划分。每个簇内邻近车辆间的距离小于门限值，并选择离源节点最远的节点作为簇头CH。簇头CH承担接连簇与簇间的通信，构建了通信的主线。仿真结果表明，提出的DCRM在吞吐量、数据包传输率以及端到端传输时延方面的性能良好。将进一步研究基于簇的路由机制，将其拓展至任何一个先应式路由协议，进而提高路由协议的性能。

参考文献

[1] MISRA S， KRISHNA P V， SARITHA V. LACAV： an energy?efficient channel assignment mechanism for vehicular ad hoc networks [J]. Journal of supercomput， 2012， 62， （3）： 1241–1262.

[2] 夏梓峻，刘春凤，赵增华，等.基于链路预测的VANET路由算法[J].计算机工程，2012，38（4）：110?114.

[3] KRISHNA P V， MISRA S， SARITHA V， et al. Learning automata?based virtual backoff algorithm for efficient medium access in vehicular Ad hoc networks [J]. Journal of systems architecture， 2013： 59（10）：968?975.

[4] 常促宇，向勇，史美林.车载自组网的现状与发展[J].通信学报，2007，11（5）：116?127.

[5] TONGUZ O， WISITPONGPHAN N， BAI F， et al. Broadcasting in VANET [C]// Proceedings of Mobile Networking for Vehicular Environment. [S.l.]： [s.n.]， 2007： 7?12.

[6] BUR K M. Evaluation of elective broadcast algorithms for safety application sin vehicular adhoc networks [J]. International journal of veh technol， 2011， 3（9）： 23?31.

[7] PALMA M E， VEGNI A M， NERI A. A fountain codes?based data dissemination techniqueinv ehicularad?hoc networks [C]// Proceedings of IEEE 11 International Conference on ITS Telecommunications. Saint?Petersburg， Russia： IEEE， 2011： 750?755.

[8] NI S， TSENG Y， CHEN Y， et al. The broadcast storm problem in a mobile Ad hoc network [C]// Proceedings on the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking（MobiCom）. [S.l.]： ACM， 2009： 151?162.

[9] FASOLO E， ZANELLA A， ZORZI M. An effective broadcast scheme for alert message propagation in vehicular ad hoc networks [C]// Proceedings on IEEE international conference on communications. [S.l.]： IEEE， 2006： 3960?3965.

[10] LUO Y， ZHANG W， HU Y. A new cluster based routing protocol for VANET [C]// Proceedings on Second International Conference on Networks Security Wireless Communications and Trusted Computing. [S.l.]： NSWCTC， 2010： 176?180.

[11] WU Y， XU J， XU Y. An RSU?assisted cluster head selection and backup protocol [C]// Proceedings on 26th International Conference on Advanced Information Networking and Applications Workshops. [S.l.]： WAINA， 2012： 581?587.

[12] BENSLIMANE T T， SIVARAJ R. Dynamic clustering?based adaptive mobile gatey management in integrated VANET?3G heterogeneous wireless networks [J]. IEEE journal of sel Areas Commun， 2011， 29（3）： 559?570.

[13] GUNTER Y， WIEGEL B， GROSSMANN H. Cluster?based medium access scheme for VANETs [C]// Proceedings on Intelligent Transportation Systems Conference. [S.l.]： [s.n.]， 2007： 34?45.

[14] KAYIS O， ACARMAN T. Clustering formation for inter?vehicle communication [C]// Proceedings on IEEE Intelligent Transportation Systems Conference. [S.l.]： ITST， 2007： 636?641.

[15] KOYAMPARAMBIL MAMMU A S， HERNANDEZ?JAYO U， SAINZ N. Cluster?based MAC in VANETs for safety applications [C]// Proceedings on International Conference on Advances in Computing， Communications and Informatics. [S.l.]： IEEE， 2013： 1424?1429.

[16] HAFEEZ K A， ZHAO L， LIAO Z， et al. A Fuzzy?logic?based cluster head selection algorithm in VANETs [C]// Proceedings on IEEE International Conference on Communications. [S.l.]： IEEE， 2012： 203?207.

[17] 宋军，杨露霞，孙建乐，等.城市道路环境下的车载自组网分簇路由机制[J].重庆交通大学学报（自然科学版），2013，32（1）：108?113.

[18] MARIA V A， NATALIZIO E. Forwarder smart selection protocol for limitation of broadcast storm problem [J]. Journal of network and computer applications， 2015， 47（2）： 61?71.