车联网中基于拓扑感知的分布式广播路由研究

  • 来源:物联网技术
  • 关键字:挑战,算法,分析
  • 发布时间:2019-08-11 22:50

  摘 要:针对车联网基于距离等待转发的广播路由存在“慢反应”和“局部广播风暴”的问题,研究了基于MAC的广播路由和基于概率的广播路由,提出了一种发送节点依靠beacon消息以自组织方式感知局部拓扑信息,并将抽象出的邻居节点的数量和分布等特征信息嵌入到广播报文中,接收节点基于概率广播路由动态分配转发优先级的分布式广播路由协议。该协议无需路边单元的协助,节点以自适应方式分布转发安全消息,网络开销较小。仿真结果表明,所设计的广播协议具有更低的时延和更少的冗余,能更好地适应车联网拓扑的动态变化。

  关键词:广播协议;转发策略;局部信息感知;车联网;TSBP协议;拓扑

  中图分类号:TP393.04 文献标识码:A 文章编号:2095-1302(2019)05-00-06

  0 引 言

  车联网的安全应用在减少交通事故、提高道路交通效率、保证国民经济发展、保障人民生命财产安全方面起到举足轻重的作用,安全消息快速分发到事故后方数千米区域内,使得驶向事故位置的车辆能够避免连环碰撞,保障车辆安全行驶[1]。由于车载设备的通信距离有限,通常通过多跳广播来实现安全消息快速、可靠地分发,而多跳广播的核心是中繼转发节点的选择。现有的多跳广播策略按照中继节点的确定方式主要分为两类:一类是基于发送端指定中继(Sender-based)的多跳转发策略;另一类是基于接收端分布式中继(Receiver-based)的多跳转发策略。Sender-based策略的优点是能够实现安全消息的快速分发,且车流密度的变化对网络冗余影响较小,其缺点是在车辆拓扑快速变化的网络中传输可靠性下降,这是因为该策略的成功依赖于精准的邻居信息,在车辆拓扑快速变化的网络中信道衰落和干扰严重,导致发送端指定的中继节点接收报文失败,从而造成广播中断。Receiver-based策略的优点是能最大限度覆盖安全消息的广播范围,原因在于这类转发策略规定地理上最远的候选接收节点优先转发;这类策略的另一优点是节点在正确接收报文后以分布式方式协作转发,以保证多跳转发的连续性。基于上述优点,Receiver-based策略受到了研究者的广泛关注,但该类策略中候选节点并非对发送节点的所有候选邻居节点全部彻知,当车辆处于密集网络中时会发生“局部广播风暴”,而当车辆处于稀疏网络中时会产生“慢反应”的问题。

  针对Receiver-based策略存在的问题,本文在前人研究成果的基础上,对车联网局部拓扑信息感知技术进行了研究,提出了基于拓扑感知的分布式广播路由协议(Topology Sensing Broadcast Protocol,TSBP)。TSBP不依赖路边单元,是完全自组织的路由协议,发送节点将TSBP包头添加到beacon消息中感知其局部拓扑信息,这些信息能够协助接收节点统一分配转发概率和转发时延。这种获取车联网内车辆分布状况用于中继决策的方法,网络开销代价较小,能够适应车联网中车辆拓扑快速变化的环境,如城市道路和高速道路,应用前景较为广阔。

  1 问题与挑战

  由于Receiver-based中继转发策略合理利用了空间信道的广播特性,适合安全消息的定向扩散,因而是研究者最为关注的一类安全消息广播策略。而接收端分布式转发的广播协议中最常见的是基于距离的优先级调度机制,其转发等待时延Dwait的经典公式见式(1):

  式中:R表示车载设备最大通信距离;d表示收发节点间的距离;Dmax表示接收节点最大等待时延。由式(1)可知,接收节点与上一跳发送节点距离越远,其等待时延越小,意味着其转发优先级越高,这种机制使等待时延大的节点的转发受到了抑制,从而减少了网络冗余。另外,在每一跳中都是与发送节点距离最远的节点优先转发,这样能够使安全消息快速覆盖事故车辆之后的风险区域。由于相邻车辆并发数据会加剧碰撞,加之信道衰落等影响可能导致广播中断,针对这种情况,Omar H A[2]等人提出了改进算法—时隙1坚持算法(Slotted-1)。Slotted-1算法在广播方向上把风险区域划分为许多小段(segment),每个小段内的车辆节点转发优先级相同,与事故车辆距离越远的小段内的车辆转发优先级越高,其转发等待时延Dwait见公式(2):

  式中:σ为一跳最小时延;Ns为一跳通信范围内划分的segment数,其余参数与式(1)相同。在该算法中某节点接收到上一跳节点广播的报文后,首先等待一个静态时延Dintend,在这段时间内该节点接收来自低优先级节点广播的副本。当静态时延等待计时器超时后,该节点确定了离自己最近的节点,用它们之间的距离代入公式(2)计算Dwait。对于接收节点而言,距离自己最近的节点实际上就是距离上一跳发送节点最远的节点,这一过程意味着让距离事故车辆最远的segment内的节点具有最小的等待时延(如图1所示的节点E和F),在减少冗余的同时最大限度覆盖了地理范围。Slotted-1优先级调度示意如图1所示。

  然而这类基于等待的广播路由性能易受固定参数Dintend和Ns的影响。图2所示为稀疏网络,该网络中车辆分布不均匀,虽然高优先级segment内没有车辆,但是位于低优先级segment内的车辆节点也不能立即转发消息,必须在静态时延等待计时器超时后才能转发,延缓了消息的广播,此即“慢反应”问题。又如图3所示为密集的网络,处于同一segment内的车辆节点较为聚集,因为它们具有相同的转发优先级,所以会同时转发数据,这种数据并发会加剧信道竞争。如此一来,会导致两个问题:一是会使消息接入信道的时延增加,降低广播有效性;二是会产生大量无效副本,使广播碰撞概率增加,导致广播可靠性降低,此即“局部广播风暴”问题。

  在城市和高速道路中,VANET具有车流密度高度动态变化、车辆移动速度快、信道干扰和衰落严重的特性,对快速、可靠地广播安全消息提出了严峻挑战,“慢反应”和“局部广播风暴”等问题广泛存在于Receiver-based分布式转发协议中,不利于“与生命相关”的安全消息的快速扩散,其广播性能亟需优化。

  2 相关工作

  为了实现安全消息的快速、可靠扩散,研究者提出了许多性能优良的广播协议,其中Receiver-based分布式等待竞争转发策略得到了广泛关注,针对分布式转发策略中广泛存在的“慢反应”和“局部广播风暴”问题,涌现出许多优化方案,其中较常见的包括基于MAC的广播路由和基于概率的广播路由。

  VANET中广泛存在的隐藏终端问题为克服隐藏终端对通信的影响。研究者基于MAC层进行了转发路由的优化,如Ekici提出UMB算法[3],该算法将单播路由中的RTS/CTS握手机制引入消息广播过程中,可有效减少隐藏终端的影响,提高广播的可靠性。然而频繁的握手必然会引入额外的控制时延,不利于安全消息的快速扩散。对此,研究人员分别从车流密度[4]、多信道[5]、应用场景[6]、优先级配置[7]等方面对控制时延进行了优化。为了避免引入额外的控制时延,Yi C W[8]等通过给用户分配不同的最小竞争窗(CWmin)来区分其转发优先级,一般是与发送节点距离越远的接收节点具有更小的CWmin值,在竞争中优先转发。为了控制冗余,TDC Little等规定只在某一个窄带内的节点参与竞争转发[9],相似的优化方案也出現在文献[10-11]中。虽然基于竞争窗的转发策略可避免引入控制开销和时延,但由于接入机制的随机性,最远的候选转发节点可能会竞争失败,导致覆盖相同的范围需要更多次中继,由此降低了转发效率。另外,在密集网络中,众多候选节点竞争共享信道也会让接入时延剧增,降低广播路由算法的有效性和拓展性。

  在基于等待的广播策略中,广播方向上所有的节点都可参与转发,这一机制导致同优先级的节点并发数据造成无效网络冗余。为控制无效网络冗余,N Wisitpongphan等人率先提出了基于概率的广播策略[12],这类策略通过给每个车辆节点分配不同转发概率的方式允许一部分节点参与转发权的竞争,转发概率越高的节点,其成为实际中继转发节点的机会就越大,因此基于概率的广播策略最关键的问题是节点转发概率的分配。加权p坚持算法(Weighted-p)和时隙p坚持算法(Slottedp)是基于概率的广播策略中比较有代表性的算法。在Weighted-p算法中,车辆节点的转发概率与收发双方的距离成正比,即与上一跳节点距离越远的节点,其转发概率越高,从而实现最大的地理范围覆盖;Slottedp算法是在最远距离优先转发的基础上,首先让节点等待一定的时延,等待时延结束后以概率P转发。Oh S[13]等通过观测车辆节点的竞争水平动态调整节点的转发概率,以降低网络中的竞争和冗余。还有研究者综合考虑距离和车流密度[14-15]等分配车辆节点的转发概率,其策略是距离上一跳节点越远的节点或处于稀疏网络中的节点具有更高的转发概率。基于概率的广播策略的优点是有效降低了相邻节点并发数据的可能性,一定程度上降低了竞争和碰撞,从而减少网络冗余。其缺点是广播效率降低,这是因为最优候选节点成为实际转发节点具有一定的概率,如果地理上最远的邻居不是实际参与中继转发的节点,广播的一跳范围就被缩小了。

  3 广播协议设计

  如前所述,在基于距离等待的广播策略中因Dintend和Ns的固定配置导致了“慢反应”和“局部广播风暴”问题的产生,而基于概率的广播策略具有抑制冗余的优势,为避免前者的劣势,发挥后者的优势,发送节点可利用车联网中已有的beacon消息感知局部拓扑信息,从而协助接收节点统一分配转发时延并动态分配转发概率。根据以上思路,本文提出了一种基于局部拓扑感知的快速广播路由协议TSBP,该协议无需路边单元协助,在完全自组织的方式下,能够适应车联网拓扑结构的快速变化和车流密度的动态变化。

  3.1 拓扑感知技术

  beacon(DSRC中定义为BSM消息)是VANET中广泛使用的基本安全应用。运动中每一个车辆节点通过beacon消息以一定的周期广播其基本状态,当其一跳邻居收到beacon消息后便更新邻居列表。邻居列表表达的是每辆车对其局部拓扑的认知,主要包括邻居的ID、位置、速度大小和方向、时间戳等信息。每辆车感知到邻居信息后,维护一张包含邻居的ID和位置的候选邻居拓扑图。发送节点通过广播自己的候选邻居拓扑图,使所有接收节点都知道发送节点的候选邻居分布情况,从而避免“慢反应”和“局部广播风暴”问题。但这种方式会产生大量网络负载,增加网络传输时延。为减少网络负载,我们提出了一种发送节点F在广播报文中嵌入用于接收节点中继决策的有效邻居数NeF、有效通信距离dmax、车流密度指示器TIF等特征信息的低负载解决方案,数据帧如图4所示。

  TSBP包头由三部分组成:第一部分是安全消息基本信息,包括消息传播的方向Direction,消息的类型typep,消息初始产生的地点(xp,yp)和时间tp,上一跳转发节点F广播消息的地点(xF,yF)和时间tF;第二部分是广播路由需要使用的安全路由信息NeF,dmax和TIF;第三部分为扩展域。

  TSBP协议中beacon消息的安全传输是成败的关键之一,很多能够保证beacon消息较可靠传输的方案被提出,其中比较常见的方案是在一个广播周期内多次重播beacon消息,这一方法能使beacon消息的收包率达到90%以上[16]。

  3.2 候选中继优先级调度算法

  上一跳车辆节点Vj统计其感知信息,包含有效通信距离dmax、有效邻居数Nej等,并嵌入到安全消息报文头部,然后广播,其一跳邻居Vi收到广播报文后转发等待时延TWi,见式(3):

  从公式(3)可以看出,考虑dmax后,在最远segment内的车辆以最高优先级转发,它们无需等待一个随机时间来接收网络内的其他副本,即转发等待时延为0,从而避免了转发误判;考虑Nej后,TSBP协议能根据候选邻居的分布情况以及车流密度动态调整通信范围内的segment数量,处于不同segment内的候选节点的转发优先级也得以区分。

  为了控制无效网络冗余,在获取了车流密度指示器TI的估值后,TSBP协议给所有候选节点分配了一个转发概率PTI,如式(4):

  为尽可能减少网络副本,降低无效网络冗余,在公式(4)中规定1≥P1>P2>P3>0,即车辆处于越是密集的网络,其转发概率越低。

  此外,在VANET中,随着地域和时间的变化,车辆节点的分布也在高度动态变化中,根据车辆节点位置的不同,其转发优先级也应有一定的区分,与上一跳转发节点距离越远的接收节点其转发概率越大。本文采用公式(5)给不同位置的车辆节点分配不同的转发概率,以减少低优先级车辆节点转发数据产生的无效网络冗余。

  有效通信距离的计算受邻居列表准确性的直接影响,当收发节点之间的距离比有效通信距离大时,本文将其等待时延设置为0,即该节点转发优先级最高,此时转发概率只由PTI控制,这样设计的好处首先是每一跳的转发都覆盖了最大的地理范围,有利于消息快速传播;其次在一定程度上能适应整个网络拓扑的车流密度变化。

  3.3 TSBP工作流程

  根据前述内容,TSBP协议的流程如图5所示。

  网络中每辆车首先利用车载设备获取方向、速度、经纬度、时间戳等基本状态信息,并将这些信息封装在beacon消息中定期向邻居节点广播。当邻居车辆收到beacon消息后,会根据基本状态信息立即更新其邻居列表。根据该邻居列表,节点的网络层感知拓扑信息,分析特征信息—有效邻居数、有效通信距离、车流密度指示器,进行分布式中继决策,之后把这些信息嵌入到报文头部并广播。每个邻居节点接收到数据包后,立即分析上一跳发送节点的拓扑信息,然后根据自己与发送节点之间的距离,分配候选中继节点的转发概率和转发时延。距离上一跳越远的节点,分配的等待时延越少,可优先转发。如果某些车辆节点未通过概率测试,那么他们不能参与等待竞争转发的过程。若有节点在计时器到期之前接收到确认帧(ACK)或广播副本则取消等待。其他候选节点转发报文时,重复上述过程,更新广播报文中的拓扑信息,执行逐跳转发,直到整个风险区域的车辆都获得安全消息。另外,TSBP协议在网络层还引入了重传机制,以尽可能地减少广播副本,同时保障安全消息的连续分发。只有包含消息源节点在内的上一跳节点在最大等待时间内没有收到ACK或任何转发的副本时,才开启重传过程,此时安全消息被重新广播,如果收到ACK或副本,则取消重传过程。

  4 仿真与分析

  为了分析TSBP的广播性能,本文使用实验室仿真软件工具NS2+SUMO来模拟实际车辆的运动和通信环境。

  4.1 仿真场景设置

  在SUMO软件中设定一条宽度为40 m,长度为3 000 m的双向六车道直行道路,让20~100辆车先后随机进入该道路,并满足车辆拓扑的连通性。车辆移动符合karuosi智能跟车方式,车辆时速取值在30~100 km之间,当车辆到达道路尽头时掉头反向运动以保证道路上一定的车流密度。处于网络中的车辆的理论通信半径设定为300 m,每辆车随机生成多跳广播消息,每秒生成一个报文,并且以0.5的概率发送。其他主要仿真参数见表1所列,配置好参数后使用NS2[17]进行仿真。

  4.2 仿真结果及分析

  为了验证TSBP的广播性能,本文选择了具有代表性的泛洪广播算法(Mflood)、最远节点转发算法(FARTHEST)、时隙1坚持算法(Slotted-1)、时隙p坚持算法(Slottedp)等典型广播算法与TSBP进行对比分析。

  对比的算法性能指标主要包括报文投递率(Packet Delivery Ratio,PDR)、端到端时延(End-to-End Delay,E2ED)、一跳平均时延(One Hop Delay,OHD)、广播冗余(Broadcast Redundancy,BR)、转发效率(Forwarding Efficiency,FE)。报文投递率PDR与车流密度的关系曲线如图6所示。

  如图6所示,隨着车流密度的增加,广播协议的报文投递率递增,原因是有更多的车辆节点参与转发。当增加到100车/3 km的密集网络时,由于报文碰撞的增加将导致投递率递减。Slottedp和TSBP通过引入转发概率在一定程度上减少了碰撞,因而在高密度时投递率优于Slotted-1,但是在低密度时,转发存在一定的概率性,因而投递率略低,虽然TSBP通过感知车流密度来动态调整转发概率,在一定程度上提高了投递率,却依然低于Slotted-1,原因是车联网拓扑高度动态变化,因而自适应算法性能有待进一步优化。由于FARTHEST规定节点在收到报文后按照距离分配等待时延,相比Slotted-1少了一个静态等待时延用来消除多个副本的转发,因而广播会因为频繁的碰撞而中断,FARTHEST的投递率在几类广播协议中更低。

  广播协议的时延随车流密度的变化曲线如图7、图8所示。为了减少上一跳转发节点并发数据导致广播中断,Slotted-1和Slottedp在节点转发前分配静态等待时延,每一跳转发都引入了额外的等待时延,因而转发时延较高,尤其在低密度网络中,“慢反应”现象更明显。Mflood,FARTHEST和TSBP规定节点收到报文后无需静态等待,按照优先级转发,在高密度时竞争加剧,广播时延递增。TSBP通过发送节点感知邻居的分布和数量计算有效通信距离,来替代固定值计算等待时延,适应了拓扑的动态变化特性,减少了实际参与竞争转发的冗余节点数,等待时延和转发跳数都得以优化。由以上分析可知,与其他几种典型的广播协议相比,本文提出的TSBP算法能有效缓解稀疏网络中的“慢反应”问题造成的影响,优化了广播协议的时延性能。

  图9显示了广播协议的冗余量随车流密度的变化情况,图中显示随着车流密度的增加,网络的连通性逐渐变好,实际参与报文转发的节点也随之增加,网络中增加了大量无效副本,广播冗余增加。同时无效冗余导致无效转发次数大量增加,因而转发效率递减,如图10所示。从图10可以看出,转发效率恶化的速度随着碰撞的加剧而增加,“局部广播风暴”在高密度时凸显,使得广播性能恶化。FARTHEST通过收发节点之间的距离配置转发优先级,抑制了一部分节点的转发,较Mflood冗余性能在更大程度上得以优化。Slotted-1则通过把一跳通信范围划分成优先级不同的区域,使得低优先级区域内的冗余量进一步减少,从而提升其转发效率。由于Slotted-1,Slottedp通过引入概率机制进一步减少了冗余,所以在几类算法中冗余性能最优。但是Slottedp协议中概率配置是固定的,这导致其不能适应网络的密度变化,在低密度网络中报文投递率较低,所以其广播效率随着车流密度的增加先增后减。TSBP通过计算有效邻居数来动态配置划分的路段数,通过计算收发节点之间的距离以及局部车流密度指示器来分配转发概率,较大程度上抑制了无效副本的产生,在密集网络中依然保持较少的冗余和较高的转发效率,较大程度上缓解了密集网络下的“局部广播风暴”问题。由于针对拓扑的感知是基于周期性的beacon消息建立的邻居列表,因而广播性能受信道衰落和干扰影响较大,尤其在低密度条件下,网络拓扑的变化更激烈,邻居感知的准确性有待进一步提高。

  5 結 语

  基于接收节点竞争转发的策略被广泛应用于车联网中安全紧急消息的多跳转发,然而,这种策略在密集网络和稀疏网络中分别存在“局部广播风暴”和“慢反应”问题,对此,本文将基于接收节点竞争转发的策略与基于概率广播的协议,发挥基于概率广播协议在降低无效网络冗余方面的优势,提出了一种基于车联网局部拓扑感知的分布式广播路由协议TSBP。仿真结果表明:相对于经典的广播协议,TSBP在保障广播可靠性的同时,时延和冗余性能更优。由于TSBP性能受邻居拓扑信息感知技术的影响较大,下一步研究的方向是跨物理层、MAC层和应用层优化协议,进一步提高协议对车流密度和拓扑变化的适应性。

  参 考 文 献

  [1]刘辉元,董春阳,黄琼.基于VANETs下的决策树多副本机会路由协议[J].重庆邮电大学学报(自然科学版),2016,28(6):769-776.

  [2] OMAR H A,ZHUANG W,ABDRABOU A,et al. Performance evaluation of VeMAC supporting safety applications in vehicular networks[J].IEEE transactions on emerging topics in computing,2013,1(1):69-83.

  [3] G?KHAN K,EKICI E. Urban multi-hop broadcast protocol for inter-vehicle communication systems[C]// Proc. ACM Workshop on Vehicular Ad Hoc Networks. 2004:76-85.

  [4] IBRAHIM K,WEIGLE M C,ABUELELA M. p-IVG: Probabilistic Inter-Vehicle Geocast for Dense Vehicular Networks[C]// Vehicular Technology Conference,Vtc Spring 2009. IEEE,2009:1-5.

  [5] AKKHARA P,SEKIYA Y,WAKAHARA Y. Efficient alarm messaging by multi-channel cut-through rebroadcasting based on inter-vehicle communication[J].Iaeng International journal of computer science,2009,36(2).

  [6] VIRIYASITAVAT W,BAI F,TONGUZ O K. UV-CAST: An urban vehicular broadcast protocol[J].IEEE communications magazine,2011,49(11):116-124.

  [7] LI M,LOU W,ZENG K. OppCast: Opportunistic broadcast ofwarning messages in VANETs with unreliable links[C]// IEEE,International Conference on Mobile Adhoc and Sensor Systems. IEEE,2009:534-543.

  [8] YI C W,CHUANG Y T,YEH H H,et al. Streetcast: An Urban Broadcast Protocol for Vehicular Ad-Hoc Networks[C]// Vehicular Technology Conference. IEEE,2010:1-5.

  [9] A J. An information propagation scheme for VANETs[C]// Intelligent Transportation Systems,2005. Proceedings. IEEE,2005:155-160.

  [10] CHEN R,JIN W L,REGAN A. Broadcasting safety information in vehicular networks: issues and approaches[J]. Network IEEE,2010,24(1):20-25.

  [11] ZHU,LINA,ZHAO,et al. Hello scheme for vehicular ad hoc networks: analysis and design[J]. Eurasip journal on wireless communications & networking,2013(1):1-11.

  [12] WISITPONGPHAN N,TONGUZ O K,PARIKH J S,et al. Broadcast storm mitigation techniques in vehicular ad hoc networks[J].Wireless communications IEEE,2007,14(6):84-94.

  [13] OH S,KANG J,GRUTESER M. Location-Based Flooding Techniques for Vehicular Emergency Messaging[C]// Third International Conference on Mobile and Ubiquitous Systems: Networking & Services,IEEE,2006:1-9.

  [14] HAFEEZ K A,ZHAO L,LIAO Z,et al. A New Broadcast Protocol for Vehicular Ad Hoc Networks Safety Applications[C]// Global Telecommunications Conference. IEEE,2011:1-5.

  [15] FARNOUD F,VALAEE S. Reliable Broadcast of Safety Messages in Vehicular Ad Hoc Networks[C]// INFOCOM. IEEE,2009:226-234.

  [16] XU Q,MAK T,KO J,et al. Medium access control protocol design for vehicle-vehicle safety messages[J].Vehicular technology IEEE transactions on,2007,56(2):499-518.

  [17] NS2,the network simulator[EB/OL]. http://www.isi.edu/nsnam/ns.

  马金忠 王文杰 田彦山?

……
关注读览天下微信, 100万篇深度好文, 等你来看……
阅读完整内容请先登录:
帐户:
密码: