基于公交节点的VANET路由算法研究

王永福

摘要：城市公交车具有遍布街区道路、行驶线路固定等特点，VANET网络中的数据分组传输可通过公交车自组织网络实现，但公交车网络能否在数据传输中发挥作用取决于对公交车运行规律的利用程度。提出一种公交车自组织网络路由算法，该算法建立了公交节点数据传输模式，给出了路由选择优化准则。与已有研究相比，该路由算法具有很好的数据分组投递率和可靠性，能获得高质量的数据传输路径。实验结果表明，该路由算法提高了数据分组投递率，降低了数据分组传输延迟，具有较强的可伸缩性。

关键词：VANET；路由算法；平均时延

DOIDOI：10.11907/rjdk.171668

中图分类号：TP312文献标识码：A文章编号：16727800（2017）010007203

0引言

车载自组织网络（Vehicular adhoc Network，VANET）是一种特殊的移动自组织网络。VANET有两种通信方式：车辆节点与路边基础设施（V2I）通信和车辆节点与车辆节点（V2V）间的通信[12]。车辆通信时路由选择是VANET网络的关键问题之一，其目的是找到源节点与目的节点间传输数据包的有效路径。

本文提出一种基于拓扑结构的路由算法（BCR），该路由算法将公共汽车总线作为移动骨干网。公共汽车作为城市环境下的特殊节点具有独特优势：①与普通汽车相比具有较低的运行速度；②城市环境下公共汽车数量有限；③公共汽车的运行线路固定，其运行轨迹可循[34]。本文路由算法将公交总线作为网络的移动骨干网，采用MIVANET架构[5]，选择具有最少节点数的路径，减少了端到端的平均时延，增加了网络中数据包投递率，同时减少了目的节点数量。与传统的基于距离矢量（AODV）路由协议[6]相比，本文算法减少了传输数据时控制分组的数量，提高了城市环境下路由的整体性能。采用仿真软件NS2模拟实验表明，相比于VANET中现有的AODV路由协议算法，本算法在数据投递率和平均延迟方面都得到显著改善。

1相关工作

VANET路由协议通常分为3类：基于拓扑结构的路由协议、基于地理位置的路由协议以及基于簇的路由协议，此外还有将几种路由方案综合在一起的混合路由算法[79]。对于一般的VANET路由協议，请参考文献[10]。这里仅简要阐述使用公交总线转发数据包的算法。

文献[11]提出了基于上海地图的公交网络方案。通过使用公交线路时间表、公交线路信息等，对其进行时空模式建模。公交网络路由算法类似于VANET中的混合路由算法[1213]。文献[14]对AODV路由协议进行了修改，提出一种公交车AODV路由协议（BCR）。BCR路由协议选择的公交线路数相对较少，但由于周期性广播消息而导致额外的带宽消耗。文献[15]中，将公交车作为所有道路的中继节点，研究了公交车辅助车载自组织网络的组播能力。

在MIVANET结构[5]中，公交车起到数据传输的骨干作用。提出了一种两层的MIVANET模型结构，将公共汽车作为消息传播的移动骨干网。

定义1每个公交车配备有两种无线接口。低层用于与普通节点间通信。用于公交车节点内部专用通信，信道上具有较大的传输范围。

定义2普通节点构成MIVANET模型的低层结构。当车辆节点要发送消息时，必须在一辆公交车节点上注册。

在MIVANET模型中，路由机制是一种基于位置的算法，它假设车辆节点均匀分布在道路上，每条公交车线路都有一条包含所有公交线路信息的数字街道地图。本文提出的方法即基于这种模型，但路由却是基于拓扑结构的算法。

2城市交通特点

城市交通环境下车辆节点特征：普通车辆约占全部汽车的80%，公交车所占不到20%。公共汽车路线规则，与出租车和私家车相比，其运行速度较慢，它们之间很容易建立通信。

选择5条公交线路的区域路段研究公交线路特征。每条线路的公交车发车时间间隔约为10min。每条道路有两个方向，两条相邻公交车之间的平均时间约为10/5/2=1min。假设随机乘坐10辆公交车，公交车的最高行驶速度约为40km/h。由于公交车站台和交通信号灯的频繁变化，其平均车速仅为15km/h，因而网络中的公共汽车可以保持良好连通状态。

3BCR路由方案

本文提出一种基于表驱动的路由协议算法，将公共汽车作为移动主干网来转发消息，称为BCR，下面阐述具体步骤。

3.1邻居节点发现过程

周期性广播Hello消息，收到Hello消息的节点把发送节点注册为其邻居节点。在节点表中设置一个超时参数值并记录相关邻居节点信息。如果节点在一个超时周期内没有收到从邻居发来的任何Hello消息，就将该邻居节点从列表中删除。

3.2消息传播机制

消息传播过程中，包含邻居链路信息的链路状态分组（Link State Packet，LSP）将发送给网络中的其它节点。该过程由两部分组成：①处理LSP的完整性。当一个节点生成新的LSP后，必须通过广播机制将其发送给所有节点。节点接收到该数据分组后，将其发送到除该分组的源节点之外的所有邻居节点；②当节点检测到链路发生变更时，每个离开链路的节点通过链路状态数据包（LSP）将其离开的消息广播到所有其它节点。这些LSP被洪泛到网络中的所有节点。当每个节点接收到该信息时，将更新自己的网络视图。

3.3路由算法

该算法灵感来源于人工智能领域的规划方法，具体阐述如下。

路线选择4条准则：

准则1：如果网络中的两个节点B和节点C具有相同的链接，且链路状态表也相似，则删除两个节点中的一个，如图1所示。

准则2：如图2所示，如果在一个节点的LS表中呈现的节点也呈现在另一个节点的LS表中，则删除不会扩展任何新路由的那个节点。endprint

準则3：如果一个节点可从其它节点的LS表中组合生成其LS表，则将从LS表中删除冗余的那个节点。如图3所示，节点B可以与节点E和F通信，同时这两个节点可通过A和C连通，所以删除节点B不会影响路由。

准则4：如果一个节点只有一个链接节点，那么该节点将自动从LS表中删除，这将简化促进路由。如图4所示，节点B将从LS表中删除，因为它只有一个节点。

算法步骤如下：定义S表示源节点，D表示目的节点，表示节点S的LS表，为路由表。在初始状态下，W=，C=φ，路径长度为零，节点S的路由表中无其它节点信息。假设D∈，则当Di时，对于W里面的每个节点Ni，如果Ni是Nj的邻居节点，同时Ni且Nj∈，则有C=C∪{Ni}，此时W=W-C。对于C中的每个节点Ni，C=C-Ni。如果Ni没被准则1、准则2及准则3删除，则将Ni节点添加到中，并将网络路径长度k加1。k表示路径长度，当k>0、Ni可从中删除时，则通过删除Ni更新，同时路径长度k减1。

4路由性能评估

4.1仿真参数设置

仿真实验使用NS2.35[18]。为了更好地评估本文所提算法性能，在相同的仿真场景下对经典的路由算法AODV和GSR算法加以实现，仿真环境设置如表1所示。对网络拓扑进行多组实验，抽取其中10次仿真结果并生成其平均值。

本文算法性能评估实验，主要对数据包投递率、端到端平均时延及平均链路持续时间进行分析比较。

4.2仿真结果分析

初始阶段没有路由表信息，致使开始过程中会有数据包丢失。如图5所示，所有路由算法投递率都低于60%，在节点数量较低时，网络会出现分离现象，导致大量的数据包不能成功交付，故数据包投递率最低。其中基于拓扑结构的AODV路由算法数据丢失率最高，因为AODV路由算法只考虑了城市环境中网络的拓扑变化，没有考虑VANET网络节点特性。采用Dijkstra最短路径算法进行路由选择，随着节点数量的增大，其数据投递率也明显下降。BCR则实现了最高的分组投递率，因其考虑了VANET特征，当网络节点密度增加时，借助公交车辆节点，明显减少了网络中参与路由节点数目，所以该算法在数据投递率方面表现优异。

图5数据投递率

如图6所示，与其它路由算法相比，BCR呈现最低的延迟，主要原因是与普通车辆节点相比，公交车的通信半径范围较大。此外，BCR的控制分组开销较小，因为只有公交车发送数据包。当网络中的节点从100增加到500时，其端到端平均时延从47ms增长到103ms。相比其它两种路由算法，其性能表现最佳。

图6端到端平均时延

图7表明，在节点数量较少的情况下，AODV算法和GSR具有更长的链路持续时间，但是随着网络中节点数量的增加，AODV路由算法的链路有效时间急剧下降，而GSR基于地理位置，所以相对来说较为稳定。本文的BCR虽不及前两种算法，但随着网络中节点数量的增加，其变化平缓，性能稳定，因而能更好地适应车辆节点数目巨大的城市环境。

图7链路持续有效时间

5结语

在网络规模较小时，本文所提出的BCR路由协议性能与其它两种算法相差不大，但当网络规模较大且节点数较多时，性能有明显提升，这表明本文所提路由协议具有良好的扩展性。本文算法降低了网络中端到端平均延迟，提高了数据分组投递率，同时减少了城市环境中选定路由时节点的数量。

参考文献参考文献：

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

[2]郑少仁，王海涛，赵志峰.Ad Hoc网络技术[M].北京：人民邮电出版社，2005.

[3]刘业，吴国新.基于802.11p/WAVE的车联网连通性模型及其应用研究[J].通信学报，2013，34（6）：8591.

[4]LUO J， GU X， Zhao T， et al.Mivanet： a new mobile infrastructure based vanet architecture for urban environment[C]. In： 2010 IEEE 72nd Vehicular Technology Conference Fall （VTC 2010Fall），2010：15.

[5]MOSTAFA A， VEGNI A M， AGRAWAL D P. A probabilistic routing by using multihop retransmission forecast with packet collisionaware constraints in vehicular networks[J]. Ad Hoc Networks，2014，14（3）：118129.

[6]PERKINS C， BELDINGROYER E， DAS S. Rfc 3561ad hoc ondemand distance vector （aodv） routing[C]. In： Internet RFCs，2003：138.

[7]CHENG P， WENG J， TUNG L， et al.GeoDTN+NAV： a hybrid geographic and dtn routing with navigation assistance in urban vehicular networks[C]. In： MobiQuitous/ISVCS，2008.

[8]LI F， ZHAO L， FAN X， et al.Hybrid positionbased and dtn forwarding for vehicular sensor networks[J]. International Journal of Distributed Sensor Networks，2012（6）：152158.endprint

[9]ZHAO L， LI F， WANG Y.Hybrid positionbased and dtn forwarding in vehicular ad hoc networks[C]. In： 2012 IEEE Vehicular Technology Conference （VTC Fall），2012：15.

[10]吴振华，胡鹏.VANET中路由协议分析[J].通信学报，2015，36（Z1）：7584.

[11]SEDE M， LI X， LI D， et al. Routing in largescale buses ad hoc networks[C]. In： IEEE Wireless Communications and Networking Conference，WCNC 2008：27112716.

[12]VAHDAT A， BECKER D.Epidemic routing for partially connected ad hoc networks[R]. Technical report， Technical Report CS200006， Duke University，2000.

[13]PARK H， JANG H， LEE S， et al.Positionbased dtn routing in metropolitan bus network[C]. In： 2012 International Conference on Systems and Informatics （ICSAI），2012：14491453.

[14]Al JANABI F， YASEEN Y， ASKWITHB.The bus ad hoc ondemand distance vector （BAODV） routing protocol[C]. In： Proc. of Annual Post Graduate Symposium on the Convergence of Telecommunications， Networking and Broadcasting， PGNet 2012.

[15]HUAN Y， GUAN X， CAI Z，et al.Multicast capacity analysis for socialproximity urban busassisted vanets[C]. In： 2013 IEEE International Conference on Communications （ICC），2013：61386142.

[16]The Network simulatorns2[EB/OL].http：//www.isi.edu/nsnam/ns.

責任编辑（责任编辑：杜能钢）endprint