近年来,随着电子通信、计算机网络和汽车工业等领域的飞速发展,智能交通系统(Intelligent Transportation System, ITS[1])正处于蓬勃发展阶段,车载自组网(vehicular ad-hoc networks, VANETs[2-4])已经成为实现城市场景下智能交通的有效手段,并逐渐成为只能领域研究方面的热点。车载自组网就是利用车辆与车辆之间(vehicles to vehicles, V2V)以及车辆与道路设施之间(vehicles to road side units, V2R)的信息交换来实现信息的传递[5-7]。在不同的实际环境下,许多专家和学者提出很多的VANETs路由协议,但是这些路由协议在投递率(packet delivery ratio, PDR[8])和平均端到端时延(average end to end delay, AE2ED[9])方面并未达到要求技术实现的要求。目前,VANET路由协议主要面临的问题包含:道路稀疏性导致丢包率大、节点时延过大、数据包转发易陷入局部最优。因此,本文将对这3个方面来改进路由协议。
1 相关工作传统的路由协议根据通信源和通信目标数量的不同,可分为广播路由协议、单播路由协议和组播路由协议。其中单播路由协议是一种最基本点对点的路由协议,按照时间的发展顺序可分为以下3类经典的路由协议:基于拓扑的路由协议、基于地理位置的路由协议和基于RSU辅助的路由协议。
文献[10-11]中提出基于拓扑的先应式路由协议目的节点序列距离矢量协议(destination sequenced distance vector, DSDV)和优化链路状态路由协议(optimized link state routing, OLSR),网络中所有的节点通过广播的方式与网络中的其他节点进行信息交互,从而达到主动地维护全网路由表的目的。文献[12-13]中提出的反应式路由协议需求距离矢量路由协议(ad hoc on-demand distance vector routing, AODV)和动态源节点路由算法(dynamic source routing, DSR),这类路由按照需要进行路由发现和路由维护的过程,从而降低了整个通信网络开销。文献[14]提出DAODV(direction AODV,DAODV)在高速车辆环境下,相比于AODV路由协议提高了路由的稳定性。但这类基于拓扑结构的路由协议在车载网络中有很大局限性:当车辆节点速度高、拓扑结构变化快时,会造成通信链路中断或延迟增大等问题,并且增大了网络路由表的维护开销。
随着GPS、导航定位设备的优化与升级,相比于基于拓扑类的路由协议,在复杂环境下基于地理位置的或者基于电子地图的路由协议有更强地通信能力。文献[15]提出基于贪婪周边转发协议(greedy perimeter stateless routing, GPSR),采用传统的贪婪转发算法和改进的周边转发算法,在一般情况下,优先使用贪婪算法;一旦贪婪转发算法找不到合适的中继节点时,则采用周边转发算法来进行弥补。文献[16]针对GPSR忽略车载城市环境特点的不足,提出基于贪婪周边合作路由协议(greedy perimeter coordinator routing, GPCR),设置道路交叉口节点为协调节点,提高数据传输的连通性。文献[17]提出基于竞争转发路由(contention-based forwarding, CBF)协议,基于当前现实存在的邻居节点决定下一跳转发节点,并采用转发节点的感知体制。文献[18-19]使用不同方式的分簇,提出适应不同场景的路由算法。文献[20]提出基于道路的车辆交通路线反应模式(reactive mode of road-based using vehicular traffic routing, RBVT-R)路由协议,充分考虑VANETs网络中车辆节点的高速运动的特点,优先选择链路持续时间较长的通信路线,这样保证了信息传输的可靠性。这类路由协议与传统的基于拓扑的路由协议性能上有所提升。但是这类协议多采用局部优化算法,很容易陷入局部最优情况,从而失去了全局的控制,忽视了车辆移动轨迹选择的问题。
更多的路由协议设计不仅考虑车辆自身因素,还考虑到道路及基础设施因素。文献[21-22]提出自适应消息路由(adaptive message routing, AMR)算法与基于路口地理路由(intersection based geographical routing protocol, IGRP)协议,通过在交叉路口设置RSUs,基于服务质量(quality of service,QoS)利用遗传算法计算出由源节点到目标RSU的最优路径。文献[23]提出GSR协议,考虑城市道路因素,将整个交通环境划分为“交叉路口和道路段”,基于城市道路信息和Dijkstra算法,最优化源节点到目标节点路径。文献[24]提出改进基于贪婪交通的意识路由协议(improved greedy traffic aware routing, GyTAR),通过添加交叉路口的固定锚节点序列,根据各路段车辆密度动态不同选择的转发车辆。文献[25]提出基于连接感知路由协议(connectivity-aware routing, CAR),考虑从源节点到目的节点的最优路径中,优先考虑存在锚节点间的道路段,作为贪婪算法传输数据包的转发节点,从而提高数据传输的成功率和减少数据包传输的时延。这类路由协议采用全局设计思想,依据路由策略选择由源节点到目标节点的最优路径。但却忽视了城市环境下车车辆节点的高速移动性、城市道路车辆分布的时段性、以及车辆节点信息传递的实时性等问题。本文提出的VCNCM协议针对以上问题,设计基于车辆速度和密度的动态信标机制和基于RSU辅助路由选择算法,通过物理层的建模提高数据传输成功率。
2 VANETs场景建模本节介绍VANETs无线信道传播模型和真实地图选取与模型抽象。不同的场景和移动性模型会影响路由协议的性能。构建合适的车辆运动模型和设计无线传输模型对仿真结果具有重要意义。
2.1 无线信道传播模型无线信道大多处于复杂的传播环境中,研究其特性并建立一个与实际传输环境相符合的无线信道仿真模型,有着十分重要的现实意义。由于建筑物、树木和其他车辆的阻碍,导致信号的传输产生反射、衍射、绕射等结果,信号会有很大的损耗。如图 1所示,在城市环境下,车载自组网信息传输主要有车辆与车辆之间以及车辆与道路设施之间传输。无线信道传播模型一般可分为视距(line of sight, LOS)传输和非视距(not line of sight,NLOS)传输。虚线箭头表示两辆车通过LOS进行通信。实线表示两辆车通过NLOS进行通信。
Download:
|
|
为了更准确地描述车载自组网的衰落特性,通常采用车辆间经典的Nakamagi-m衰落信道。该模型可以描述车辆与其他车辆之间的无线通信信道关系。接收机车辆信号强度h的概率分布函数f(h)如式(1):
$ f\left( h \right) = \frac{{2{m^m}}}{{\mathit{\Omega} {{\left( d \right)}^m}\Gamma \left( m \right)}}{h^{2m - 1}}{\rm{exp}}(\frac{m}{{\mathit{\Omega} \left( d \right)}}{h^2}) $ | (1) |
式中:m是概率分布函数的形状因子,表示发射信号衰落的严重程度; Γ(·)表示是Gamma函数;Ω(d)是信号传输功率损耗,其影响因素如式(2):
$ \mathit{\Omega} \left( d \right) = \frac{{{P_t}{G_r}{G_t}h_t^2h_r^2}}{{{d^\theta }L}} $ | (2) |
式中:L为发送与接收车辆之间的直线距离; ht和hr分别表示发送与接收车辆的天线高度;Pt表示发送节点的发送信号的有效功率;发送与接收车辆节点的天线的平均增益为Gt和Gr;θ是衰落模型的损耗系数。
2.2 真实场景的地图处理选取真实地图的二维框架,对工程领域的研究有一定现实意义。本文通过选取特定的地图场景,使用典型的微观交通仿真器SUMO,可以真实模拟单个车、单个车道,可以明确指定需求,建立大规模仿真情景。为此,本文选取哈尔滨市区的街道进行处理分析,并给出了SUMO处理真实地图的步骤,处理结果如图 2所示。图 2(a)显示从OpenStreetMap下载哈尔滨市区道路情况;图 2(b)显示是SUMO软件处理XML格式图。
Download:
|
|
地图处理步骤为:
1) 从openstreetmap下载所选地图的.OSM文件, 命名为map.osm。
2) 在终端输入语句netconvert--osm-files map.osm -o map.net.xml生成map.net.xml。
3) 复制之前的已经实现的地图文件的两个文件夹,typemap.xml和map.sumo.cfg。
4) 在终端内输入polyconvert --net-file map.net.xml --osm-files map.osm --type-file typemap.xml -o map.poly.xml,生成map.poly.xml文件。
5) 输入python/sumo-0.29.0 /tools/randomTrips.py-n map.net.xml -r map.rou.xml-e 10-l
6) 输入python/sumo-0.29.0/tools/randomTrips.py-n map.net.xml -r map.rou.xml-e 10-l
7) 最后运行.cfg文件,可以实景看整个网络的车辆的运行状态。
3 VCNCM路由协议 3.1 VCNCM工作流程本文提出一种改进的基于Nakagami-m信道模型的V2X通信协议(V2X communication protocol based on Nakagami-m channel model, VCNCM)。
VCNCM路由协议主要分为两个阶段:通信路径选择阶段和V2X转发阶段。VCNCM的流程图如图 3所示。本节介绍实现VCNCM路由协议实现的过程。首先,道路上的驾驶车辆采用动态广播机制来获取其他周边车辆及周围RSUs信息。然后,如果道路上的驾驶车辆想要发送消息,则这些车辆将应用基于RSU辅助的路径选择机制以找到更好的路径。最后,使用VCNCM路由协议选取最佳下一跳。如果源节点找不到最佳路径,则需要重启路由重试,成功恢复信息在进行路由转发阶段,重试失败后将放弃转发,直到碰到合适的转发节点再进行信息传递。
Download:
|
|
信标机制含义是相邻车辆在其传输范围内进行周期性交换信标的机制,网络中的所有车辆可以在一跳范围信息中,获取信息并将邻近车辆建立通信的直接邻居列表。当需要将信息发送到其他车辆时,可以直接从邻居表中选择合适车辆。不同的信标机制对VANET路由协议的性能有重大影响。与使用固定周期信标机制的经典路由协议不同,VCNCM采用动态信标机制,通过考虑车辆速度和密度来修改信标周期,从而达到维持实时邻居列表目标。
在城市环境中,道路上车辆的分布是不均匀的,车辆速度是不确定的。快速移动的车辆具有较少的邻居车辆,并且这些车辆不能频繁地进行信息的交换。该情况下的路由策略不能达到最优。相反,当车辆缓慢移动或具有更多相邻车辆时,这些车辆会经常通过信标机制来交换信息。然而,这种情况很容易引起“广播风暴”。因此,动态信标交换机制可以有效地减少“广播风暴”,动态信标周期TBeacon如式(3)中所定义。
$ {T_{{\rm{Beacon}}}} = \left[ {\lambda \cdot \frac{N}{{{N_{{\rm{max}}}}}} + \left( {1 - \lambda } \right) \cdot \frac{{{V_{{\rm{max}}}} - {V_{{\rm{ave}}}}}}{{{V_{{\rm{max}}}}}}} \right] \times {T_0} $ | (3) |
式中:λ和1-λ分别表示速度因子和车辆密度因子的权重;N是当前邻居车辆的总数;Nmax是处于整个环境中的车辆总数;T0是一个固定的更新周期,可以根据实际交通状况来进行调整;Vmax和Vave表示在实际城市交通环境下车辆最大速度和车辆的平均速度。
3.3 基于路边基础单元辅助的路径选择机制当源节点与目标节点直线的距离很远时,源节点和目的节点传输数据包就会需要一些辅助通信设备来进行多跳传输。选择最佳的车车通信链路就是首要任务。大多数路由算法都是基于历史数据来选择预测最优的路径,但是,城市场景下的车辆拓扑结构是时变的,因此基于历史数据的预测成功率很低。因此,本协议采用路边基础单元辅助的路径选择机制,确保可以获得一条从源节点、目的节点之间路径和节点间的充分连通性。
图 4(a)是一个截取的小型仿真交通网络,其中A1~A20表示20辆车,RSU1~RSU8表示8个路边基础通信单元。图中的交通网络由道路段和交叉口组成,可以将其抽象为连通平面图,下面对这个连通平面图进行定义。首先,交通网络的交叉点是连通图的顶点,两个交叉点之间的路段是连通图的边缘,任意一条道路上的车辆密度定义为该条路的密度权重。然后,每个路段被分成一个或多个连接的图形区域。区域的大小由道路的长度,车辆的数量和RSU的传输范围共同决定。因此,可以将每个连通图区域内的车辆分布近似地视为均匀分布,并且可以计算该区域内的道路密度。如图 4(b)所示,可以通过获得连通图区域中的道路密度来组合道路密度分布。
Download:
|
|
车辆通过GPS设备可以轻松获得连接的地图序列号,每个RSU的位置信息和RSU的数量等相关信息。每辆车实时向周围的RSU报告信息。每个RSU可以周期性获得该范围内路段的车辆分布,并且可以计算该区域的车辆密度。每个RSU通过接收到的实时车辆情况来添加、删除和更改更新车辆列表。该协议遵循最短路径原理,在获得路径之后,将路径信息添加到数据分组的报头中,在建立的路径上找到合适的基于单播多跳传输的最佳下一跳。
3.4 V2X路由转发算法VCNCM采用通信路径选择机制来获得最优路径。因此,该协议提出V2X路由转发算法来表示通信路径中的最小单元。从源节点到目的节点的路径可以分成许多段。如图 5所示,可以用这种路由转发算法来选择最佳下一跳。
Download:
|
|
ni是当前车辆,fi是当前节点的跳跃范围内的邻居车辆,dk1是路边的通信单元。在图 5中,ni想要将信息发送到dk1,并且有两条路径可以完成通信任务,通过选择不同的中继节点来传递信息,在这种情况下,如何选择最优的中继节点就需要合适路由转发算法。
本协议在选择转发中继时,采用V2X路由转发算法,主要考虑两方面因素,首先考虑中继节点与目的节点的距离因素,当存在几个中继节点接近时,再考虑相对速度这个因素,选择最优的转发节点。
车辆两者之间距离关系函数用g(Dfidk)表示,其中当前节点ni到目标节点dk的距离用Dnidk表示,Dfidk表示ni的任意一个邻居节点fi到dk的距离,在符合条件下,fi到达dk越小,距离关系函数值越大,则优先被选中为下一跳转发中继节点,如式(4):
$ g({D_{{f_i}{d_k}}}) = \left\{ {\begin{array}{*{20}{l}} {\frac{{{D_{{n_i}{d_k}}} - {D_{{f_i}{d_k}}}}}{{{D_{{n_i}{d_k}}}}},\;\;\;{D_{{f_i}{d_k}}}}&{ < {D_{{n_i}{d_k}}}}\\ {0,\;\;\;{D_{{f_i}{d_k}}} > {D_{{n_i}{d_k}}}} \end{array}} \right. $ | (4) |
式中f(vfi)表示速度关系函数,当邻居节点fi的速度与当前节点ni的速度越相近时,速度关系函数值越大,则优先被选中成为下一跳转发节点。速度函数f(vfi)如式(5)所示,vni表示当前节点ni的速度。
$ f({v_{{f_i}}}) = \left\| {{v_{{f_i}}} - {v_{{n_i}}}} \right\| $ | (5) |
本节对VCNCM路由协议在仿真平台上进行模拟,获得一系列仿真数据并通过对这些数据的归纳处理。通过与路由协议GPSR、GPCR、CAR、GSR在不同影响因素仿真对比,反应VCNCM路由协议的相关性能。本文在NS-3平台下,场景选择为哈尔滨市区的地图,其仿真区域范围是5 369 m ×4 902 m。在网络中车辆节点分别为200、400、600。车辆的速度分别为0,5、10、15、20 m/s,使用IEEE802.11p协议预仿真时间为2 000 s,动态信标周期为1~3 s,节点传输半径为500 m,数据包大小为512 bytes。无线传播模型采用的Nakagami-m衰落模型,将本文提出的VCNCM路由协议与经典的GPSR、GPCR、CAR、GSR等路由协议进行性能对比。
4.2 仿真结果分析图 6显示当在该区域车辆速度分别为5、10和15 m/s时,研究车辆密度对PDR的影响。当车速不同时,PDR随着车辆密度的增加而变高。车辆密度的增加使得许多可替代路径的数量增加,并且连通性变得更好,该协议的性能得到改善。在不同的速度下,VCNCM协议的PDR比其他通信协议好,因为VCNCM考虑动态广播机制,目的车辆可以很容易获取信息。因此,VCNCM具有比其他协议更大的PDR。
Download:
|
|
图 7显示了当网络中的车辆数量为200、400、600时,随着车速的增加,5种协议的PDR随着车速的增加而减小,主要原因是基于拓扑的通信协议由于车速的增加而不能适应快速变化的网络拓扑。GPSR可以在一定程度上适应网络拓扑的变化,但是在选择车辆的过程中考虑的因素较少,随着车速的增加,车辆的位置变化变快,导致链路连接的稳定性、数据传输的成功率迅速下降。VCNCM的平均数据传输速率高于其他传输速率,VCNCM采用基于信道模型的路由协议,可以在选择通信链路较好的转发节点作为中继节点,对信息转发有促进作用。图 8给出了速度一定时,AE2ED与车辆密度的关系。图 9给出了车辆密度一定时,AE2ED与车辆速度的关系。
Download:
|
|
Download:
|
|
Download:
|
|
图 8显示了当车辆速度为5、10和15 m/s时,车辆密度对AE2ED的影响。随着模拟网络的密度增加,每个通信协议的AE2ED大大降低。与GPSR协议相比,由于优选的中继节点来传递信息的原因,GPCR协议选择更好的下一跳车辆,导致GPSR和GPCR协议之间的平均AE2ED性能出现差异。与前两者相比VCNCM还考虑物理层的信道模型,这提高了下一跳车辆选择的准确性,并有效地减少了到目的车辆的总跳数。
图 9表示网络中的车辆数量为200、400和600时,随着车辆速度的增加,5个协议的AE2ED的不同趋势。随着车辆密度的恒定,每个协议的AE2ED随着车辆速度的增加而增加。主要原因是车速的增加将导致网络拓扑的变化,使得通信链路的可靠性降低,因此,到达目的车辆的延迟增加。VCNCM采用的实时道路密度分析和最短路径的优先原则,在通信路径选择中,它减少在转发过程中产生的冗余跳数。此外,随着车辆的速度增加,VCNCM的AE2ED得到改善,其稳定性比其他通信协议更强。
5 结论针对城市高速动态的车辆环境,提出一种基于Nakagami-m信道模型的V2X通信协议。在VCNCM协议中,提出了动态广播机制和RSU辅助通信路径选择机制来提高找到合适中继节点的概率;在仿真中,使用实际地图和建立通信信道的模型可以真实反映的VANETs环境。最后,在NS3上设计并实现VCNCM协议的仿真,仿真结果表明,在城市环境下车速在0~15 m/s,车辆节点在200~600,本文提出的VCNCM协议在数据传输率和平均端到端延迟两种性能方面均优于GPCR、GPSR、CAR、GSR协议。
[1] | 杨琪, 王震. 浅析车联网的关键技术及未来在我国的发展趋势[J]. 科技风, 2018(3): 74-74. (0) |
[2] | HUANG Lijie, JIANG Hai, ZHANG Zhou, et al. Efficient data traffic forwarding for infrastructure-to-infrastructure communications in VANETs[J]. IEEE transactions on intelligent transportation systems, 2018(99): 1-15. (0) |
[3] | WANG Tong, WANG Yunfeng, LIU Bingyi, et al. A novel cross-layer communication protocol for vehicular sensor networks[J]. Int J communication systems, 2018, 31(7): 25-29. (0) |
[4] | CAO Yue, WANG Tong, OMPRAKSH K, et al. An EV charging management system concerning drivers' Trip duration and mobility uncertainty[J]. IEEE transactions on system, man, and cybernetics:systems, 2018, 48(4): 596-607. DOI:10.1109/TSMC.2016.2613600 (0) |
[5] | WANG Tong, CAO Yue, ZHOU Yongzhe, et al. A survey on geographic routing protocols in delay/disruption tolerant Networks[J]. International journal of distributed sensor networks, 2016, 12(2): 1-12. (0) |
[6] | WANG Tong, WU Jiyi, HE Xu, et al. A cross unequal clustering routing algorithm for sensor network[J]. Measurement science review, 2013, 13(4): 200-205. DOI:10.2478/msr-2013-0029 (0) |
[7] | HAASN K F, FENG Yanming, TIAN Yuchu. GNSS time synchronization in vehicular ad-hoc networks:benefits and feasibility[J]. IEEE transactions on intelligent transportation systems, 2018(99): 1-10. (0) |
[8] | 王桐, 王鹏, 柳冰忆. 城市环境下跨层VANET路由协议研究[J]. 计算机工程, 2017, 43(11): 55-65. DOI:10.3969/j.issn.1000-3428.2017.11.010 (0) |
[9] | 王鹏.VANET中基于连通性的多因素决策路由协议[D].哈尔滨: 哈尔滨工程大学, 2017. http://cdmd.cnki.com.cn/Article/CDMD-10217-1018082769.htm (0) |
[10] | PERKINS C E, BHAGWAT P. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers[C]//Proceedings of ACM SIGCOMM'94, London, UK, 1994: 234-244. (0) |
[11] | CLAUSEN T, JACQUET P. Optimized Link State Routing Protocol (OLSR)[S]. IETF RFC 3626, 2003. (0) |
[12] | PERKINS C, BELDING-ROYER E, DAS S. Ad hoc on demand distance vector(AODV) routing[S]. IETF RFC 3561, 2003. (0) |
[13] | JOHNSON D, MALTZ D, HU Y C. The Dynamic source routing protocol for mobile ad hoc networks (DSR)[S].IETF Internet Draft, draft-ietf-manet-dsr-10. txt, 2004. (0) |
[14] | ABEDI O, FATHY M, TAGILOO J. Enhancing AODV routing protocol using mobility parameters in VANET[C]//Proceedings of the 6th ACS/IEEE, International Conference on Computer Systems and Applications (AICCSA-08), Doha, Qatar, March, 2008: 229-235. (0) |
[15] | KARP B, KUNG H T. GPSR: greedy perimeter stateless routing for wireless networks[C]//Proc. ACM/IEEE MobiCom, 2000. (0) |
[16] | 黄文静. 自组织车联网中GPSR路由协议的研究进展[J]. 传感器与微系统, 2014, 33(4): 1-5. DOI:10.3969/j.issn.1000-9787.2014.04.001 (0) |
[17] | RONDINONE M, OZALVEZ J. Contention-based forwarding with multi-hop connectivity awareness in vehicular ad-hoc networks[J]. Computer networks, 2013, 57(8): 1821-1837. DOI:10.1016/j.comnet.2013.02.019 (0) |
[18] | BLUM J, ESKANDRIAN A, HOFFMAN L. Mobility management in IVC networks[C]//Proceedings IEEE Intelligent Vehicles Symposium. Columbus, USA, 2003: 150-155. (0) |
[19] | JAAP S, BECHLER M, WOLF L. Evaluation of routing protocols for vehicular ad hoc networks in typical road traffic scenarios[C]//11th EUMICE Open European Summer School on Networked Applications, Madrid, Spai, 2005: 584-602. (0) |
[20] | SHAFIGH A S, ABDOLLAHI K, KOUCHAKI M. Developing a fuzzy logic based on demand multicast routing protocol[J]. Journal of electrical and computer engineering, 2012: 812-826. (0) |
[21] | 郭显, 冯涛, 袁占亭. Ad hoc网络节点不相交多路径距离矢量路由协议[J]. 计算机科学, 2011, 38(2): 86-90. DOI:10.3969/j.issn.1002-137X.2011.02.020 (0) |
[22] | SALEET H, LANGAR R, NAIK K. Intersection-based geographical routing protocol for VANETs:a proposal and analysis[J]. IEEE transactions on vehicular technology, 2011, 60(9): 4560-4574. DOI:10.1109/TVT.2011.2173510 (0) |
[23] | LOCHERT H, TIAN J. A routing strategy for vehicular ad hoc networks in city environments[C]//Proceedings of the IEEE Intelligent Vehicles Symposium, Columbus, USA, 2003: 156-161. (0) |
[24] | 蔡震. 一种基于GyTAR道路连通性预测模型的改进算法[J]. 科技风, 2017(6): 131-131. (0) |
[25] | SHAFIEE K. Connectivity-aware minimum-delay geographic routing with vehicle tracking in VANETs[J]. Ad hoc networks, 2011, 9(2): 131-141. (0) |