车联网中基于距离的多转发者广播协议

2015-06-27 08:26韩江洪魏振春

计算机工程 2015年1期

关键词：时延分组广播

韩江洪,李超,卫星,魏振春

(1.合肥工业大学计算机与信息学院,合肥230009;2.安全关键工业测控技术教育部工程研究中心,合肥230009)

进一步抑制转发,并使转发节点尽力向源节点的覆盖区域边缘集中。在交通阻塞的节点密集场景下进一步减少参与转发的节点数量,设计概率计算公式:

车联网中基于距离的多转发者广播协议

韩江洪1,2,李超1,卫星1,2,魏振春1,2

(1.合肥工业大学计算机与信息学院,合肥230009;2.安全关键工业测控技术教育部工程研究中心,合肥230009)

为实现安全信息在车载自组织网络中快速、有效的传播,提出一种基于距离的多转发者广播协议。将上一跳转发节点信号边缘处的节点作为最优转发节点,以增加单次转发覆盖新节点的数量。选择信号覆盖范围中点处节点和次接近信号覆盖范围边缘处节点作为备选转发节点,以降低因隐蔽站或车辆脱离信号覆盖范围导致转发失败的概率,并通过反向车辆存储转发广播分组恢复路由。仿真结果表明,该协议能够适应多种车辆密度的车载自组织网络,满足不同交通流密度情况下紧急信息的分发要求,降低车辆间通信的平均端到端延时和转发率,提高转发效率,并且负载上升缓慢,能有效抑制广播风暴。

车载自组织网络;广播协议;存储转发;多转发;隐蔽站冲突;路由恢复

1 概述

高速公路环境车速快、封闭性强的特点使高速公路事故多发、救援困难。依靠多跳Ad-hoc网络广播前方道路信息将有效减少交通事故和交通阻塞。由于车载自组织网络(Vehicular Ad-hoc Network, VANET)节点移动快,链路存活时间短,传统的移动网络广播协议在车载自组织网络应用中存在诸多问题,适用于车载自组织网络的广播协议已经成为VANET研究热点问题。

在VANET中,最简单的信息分发方式是泛洪式广播,任何接收到新信息的节点都向其邻居节点转发,随着网络节点数量的增加,其效率会急速下降,在车流密度大的区域冗余会造成严重的碰撞,形成广播风暴,消耗有限的信道资源。针对泛洪式广播协议的不足,已有许多研究者提出一系列改进协议。文献[1]通过可变的自适应帧长,实现对竞争节点的定量传输,与传统协议相比,可以提升网络的健壮性,减少传输时间,但同时也增加了分组丢失率,未实现对已接收信息进行反馈,效率较低。文献[2]通过贪心选择具有最大额度的节点作为广播转发节点以减少信息转发次数。文献[3-5]通过计算接收节点与源节点距离和最大传输半径的比值得出一个转发延时,离广播节点较远的节点有较短的等待时隙以达到减小冗余转发的目的,但在网络稀疏时若干等待时隙中不存在转发节点,转发延时较大。文献[6-7]研究了稀疏网络的广播消息传播问题,提出了一种存储-携带-广播的策略,一定程度上解决了在道路车辆较少情况下广播信息不可达问题。文献[8]通过增设路基设备,解决稀疏网络不连通以及信息传播时延高问题。文献[9-10]分析了某特定路段上任意两车之间的联通概率问题,设计了一种车联网报文格式,应用连通性模型中的相关参数解析式给出了广播消息报文的TTL字段的初始值设定方案,从而有效控制广播报文的泛滥。文献[11-12]论述了车联网以及常见的车联网路由协议及其比较。文献[13]通过选取最佳中继节点来最大限度提高车联网的端到端吞吐量。

由于节点密集和节点稀疏在高速公路上都有可能存在,在节点密集区域需要抑制广播分组,而在节点稀疏区域需要进行存储转发以提高广播消息送达成功率。因此,本文提出一种基于距离的多转发者广播协议(DBMSB),主要用于高速公路无基站环境下车辆安全消息的分发,该方法结合高速公路环境下车辆分布特性,由上一跳转发节点确定多个下一跳转发节点,在某次转发不成功时利用备选转发节点减少转发失败而引起的时延,并利用反向车辆解决链路断开信息不可达问题。

2 DBMSB协议

2.1 DBMSB协议相关定义

DBMSB协议约定待研究的VANET节点都安装有GPS和相同的全向天线[14],其通信半径为R。道路上的每个节点维持2个1跳范围内节点信息表、同向节点信息表(Node towards the Same Direction,NSD)和反向节点信息表(Node towards the Opposite Direction,NOD),NSD表和NOD表包含节点信息类型相同,其节点信息由周期性交换HELLO分组更新,其格式如图1所示。

图1 节点信息分组格式

相关变量参数定义:

(1)广播包ID:该ID为反向车辆暂存广播包的ID。

(2)发送者ID:用以标识LRSP分组发送者。

2.2 协议设计思想

由于高速公路道路宽度小于节点信号覆盖半径,某辆车接收到广播消息则与其并行行驶的车辆也能接收到广播消息。如图4所示,为了便于表述,规定由东往西行驶车辆为正向行驶车辆,由西往东行驶车辆为反向车辆。

图4 广播域示意图

当某位置发生事故时,正驶向事故地点一定距离内的车辆将受事故影响,需要通过广播提前告知这些车辆前方路况信息,而反向车道车辆和正向车辆正在驶离事故地点的车辆不受事故影响,因此,在广播消息转发具有方向性和区域限制性。为了减少广播转发次数,每次转发所覆盖的新节点需尽可能多,本协议从车辆节点地理位置分布出发,选择距离广播上游节点地理位置最远且在上游广播节点信号覆盖范围内节点作为下一跳转发节点,由于广播节点信号边缘处节点可能无法正确接收广播消息,选择2个备选转发节点,当最优转发节点未能成功转发广播消息时,备选转发节点将替代最优转发节点转发广播消息。考虑到同向行驶的车辆存在稀疏的情况,广播消息在到达某一节点后无法找到下一跳转发者时将借助于反向车辆存储转发广播消息恢复路由。

2.3 广播转发节点以及转发等待时延的选定

DBSMB协议由某跳转发节点确定其下一跳最优转发节点和2个备选转发节点,其过程如下:

根据节点信息表中节点位置坐标、速度向量和HELLO发送时间利用式(1)计算出当前各节点实际坐标。

其中,xcurr(i)和ycurr(i)为节点i当前坐标估算值;xprev(i)和yprev(i)为节点i在节点信息表中的坐标;vx(i)和vy(i)分别为节点i速度在坐标轴x轴方向和y轴方向速度分量;tcurr为当前进行计算时系统时间;tsnd(i)为HELLO分组发送时间。

为了使DBMSB协议在节点密度饱和的条件下

进一步抑制转发,并使转发节点尽力向源节点的覆盖区域边缘集中。在交通阻塞的节点密集场景下进一步减少参与转发的节点数量,设计概率计算公式:

其中,Pi表示节点i转发概率;Lij表示从接收节点i到上一跳的发送节点j之间的距离;R表示节点的平均传输距离;n表示幂参数。

当n=0时,此方法等同于泛洪;当n≥1时,转发节点数会进一步减少,而且转发节点会继续向传输的边缘集中,n越大,转发节点的数量就越少且向上一跳节点覆盖区域边缘集中的趋势就越明显,幂参数值可根据具体情况进行调节。由式(2)可以看出,接收节点与发送节点间的距离越远,其转发概率越大,而且这种趋势会随幂参数n值的增加而增大。

当Pi＞1/2时,则选择节点i为下一跳节点,否则按照上述方式重新查找、计算。

当前节点位置信息可以计算出广播转发节点到其他节点距离,选择广播传播方向距离当前广播节点最大的节点为最优转发节点,其Index=0,距离次大的节点为备选广播节点1,其Index=1,最优转发节点和当前广播节点连线中点位置的节点为备选广播节点2,其Index=2,上一跳转发节点Index=3。

接收到广播分组的节点其转发等待延时由式(3)确定:

其中,waittime(i)为节点i转发等待时延;Index(i)为广播数据分组BDP中记录的候选节点索引值;τ为信号传播时延发送时延。

2.4 协议执行过程

所有节点以t1为周期发送HELLO分组,所有接收到HELLO分组的节点更新节点信息表的数据,下面分别说明协议在车辆密集和车辆稀疏2种情况下的转发策略:

(1)广播传播方向相邻车辆均在通信范围内,如图5所示。

图5 车辆完全连通分布

V1为当前将要进行转发节点。节点V1遍历NSD表,利用2.3节所述方法计算出1个最优转发节点和2个备选转发节点,更新BDP分组广播控制信息部分,监听信道t1时间,如果信道空闲则进行转发。如果NSD表中不存在等待广播消息的节点则按照策略(2)进行路由恢复。当节点V1转发BDP分组后,各节点进行如下操作:

V1监听信道waittime时间,如果接收到相同ID的BDP分组且其上一跳转发节点ID与自身相同则取消重传,否则使用二进制指数退避算法重传BDP分组。非转发节点监听信道,如果接收到BDP分组,则提取允许转发ID信息,如果与本节点ID相同,则该节点成为新的转发节点等待waittime时间后进行转发。

某备选转发节点在waittime时间内接收到对相同ID广播信息则取消对该消息的转发。

(2)广播传播方向存在两节点间距离超过节点最大通信半径R导致将车辆节点分割成2个不连通的区域,如图6所示。

图6 车辆链路断开示意图

当节点V3进行转发时在NSD表中无法找到合适的下一跳转发节点时,则遍历NOD表,利用式(1)计算出NOD表中各节点当前位置,选择正在驶向节点V3且距离V3最远的节点作为消息携带节点,如图中Vw,V3更新BDP分组广播控制部分信息,将允许转发节点修改为Vw,将传播车道标志位取反,侦听信道t1时间,如果信道空闲则进行转发。Vw接收到BDP分组后发送LRSP分组,表明已有反向车辆成功携带BDP分组,V3接收到LRSP分组后取消重传。Vw检查NOD表,如果存在正向行驶车辆,其在广播传播方向并且位置比上一跳转发节点更远则更新BDP分组,进行转发,正向车辆接收到BDP分组后回复LRSP分组,链路恢复完成。

分组转发和路由恢复过程的伪代码如下:

算法1分组转发算法

算法2路由恢复算法

3 协议性能分析

如果BDP分组指定的最优转发节点未能成功转发广播消息,存在以下2种可能:

(1)在BDP分组发送时最优转发节点已经离开当前广播节点信号覆盖范围。由于备选转发节点1和最优转发节点距离相近,近似认为通过备选转发节点1转发时上一跳转发覆盖节点数和通过最优转发节点转发覆盖节点数相同,假定最优转发节点和备选转发节点脱离上游广播节点信号覆盖范围概率相同,则由于原因(1)导致的转发失败概率将降低3/4。

(2)由于隐蔽站信号碰撞。越接近上一跳广播节点的节点,其进行转发时受到隐蔽站的影响越小,但是选择靠近上一跳转发节点的节点作为新的转发节点单次转发覆盖的新节点数比较少,为了平衡降低隐蔽站冲突和增大单次转发覆盖新节点数,将上一跳转发节点信号半径中点处的节点作为一个备选转发节点。为简化证明,在这里说明车流量密度最大情况下成功转发的概率。

假定场景为单车道,车辆处于一种最密集的状态,每R范围存在N个节点等距离分布,每个节点以概率p随机发送数据分组,某节点发送数据时,其通信范围内的节点能侦听到数据发送而取消发送数据,上一跳通信半径中点处的节点其能否成功转发只受隐蔽站影响。

如图7所示,节点A为上一跳转发节点,节点C为A通信范围边缘节点,节点B为A-C中点处节点,则影响C的隐蔽站有个,C点成功转发概率为:

而B点成功转发概率为:

相对于基于最大距离的转发协议,由于原因(2)导致的发送失败概率将降低

图7 隐蔽站冲突示意图

4 仿真与结果分析

4.1 仿真实验

如上文所述,DBSMB协议能适应节点密集和节点稀疏的网络,在节点密集区域能抑制广播风暴,减少转发次数,在节点稀疏区域能够尽可能送达广播消息。本文使用NS2对该协议在不同密度下的性能进行检验。其中目标广播区域为一条长5 km,宽50 m的双向4车道长直公路,取节点数为100,200, 300,400,500,1 000,1 500,2 000,2 500,3 000是根据文献[8]所述交通阻塞状态下每车道每公里有133辆车确定。仿真MAC层采用802.11p协议,单跳最远通信半径为500 m,传输速率为1 Mb/s,每个节点的运动速度在80 m/s～120 m/s随机选择,节点随机分布于广播区域内并且每个节点以0.01概率随机发送数据。

仿真实验将从以下3个方面对比本协议与简单泛洪广播协议和SCB协议的性能。

(1)平均端到端时延(Average End to End Delay,AEED):指从包生成到其下一跳节点成功转发所经历的时间平均值,其中反向车辆成功暂存广播数据包视为成功转发,其时间由转发延时waittime和二进制指数退避算法确定。

(2)转发比率(Forwarding Ratio,FR):指广播中参与转发的节点占总节点数的比率。该性能反映广播协议执行效率,在成功转发的前提下,转发比越低转发效率越高。

(3)负载(Load):指单位时间内网络的平均数据流量,完成一次广播转发产生的数据流量越少,其效率越高。

4.2 结果分析

端到端时延是衡量协议通信实时性的一个主要性能指标,能够反应通信协议的实际应用效果。图8对比了简单泛洪广播协议、SCB协议和本协议平均端到端时延,在节点数较少时简单泛洪广播协议时延比 DBMSB协议和 SCB协议大,由第 3节原因(1)导致的转发失败使得SCB协议的平均端到端时延略大于本协议,在节点较为密集时由第3节原因(2)导致的发送失败使得简单泛洪广播协议和SCB广播协议时延较大。DBMSB协议的时延在不同的密度下变化较小,其主要时延由转发不成功造成重传、进行转发节点选择时的询问、声明等待过程的时间构成,由于有效避免了“广播风暴”引起的冲突,其在竞争信道时用于退避重传的时间很少,因此其时延受密度增长的影响不大。适用于交通密度不断变化的VANET广播场景。

图8 平均端到端时延比较

图9对比了简单泛洪广播协议、SCB协议和本协议转发率。在能够满足覆盖率要求的前提下,参与转发的节点越少,即转发比率越小,则协议的执行效率越高。泛洪协议的每个节点都参与转发,所以其转发比率接近100%。SCB协议并非每个节点都参与转发,因而转发比率并不高。DBMSB协议进行广播时其参与转发的节点个数在各个密度度条件下变化不大,在每一跳中其转发节点一般为离上一跳节点距离远的节点,所以,参与转发的节点数量由传输距离和广播目标范围决定,由于密度增大,在特定范围内的节点数增加,因此其转发比率随密度增加而递减。在节点密度较大时由于DBSMB协议采用多候选转发节点机制,其性能相对于简单泛洪广播协议和SCB协议有所提升。

图9 转发率比较

图10对比了简单泛洪广播协议、SCB协议和本协议负载。泛洪协议的特点决定了其负载会随节点的增加而增大,泛洪协议的负载与网络密度成正比,在特定的广播区域内,密度大时其网络负载也大,因为在泛洪广播中每个收到广播数据的节点都要进行转发,而通信节点过多产生的冲突与竞争会引发更多的重传。SCB协议的网络负载上升不大,只有泛洪协议的20%左右。DBMSB协议的负载在各种车辆密度也都远低于泛洪协议,且比SCB协议的网络负载要小,其负载随密度增长缓慢,仅为泛洪通信在同密度下负载的 10%左右,其原因在于采用DBMSB协议进行数据广播能够有效避免大量转发时产生的冲突。从图中可以看出DBSMB协议转发数据分组时占用网络资源较少。随着节点密度增大,其负载上升较为平稳,能抑制广播风暴。

图10 负载比较

5 结束语

本文提出一种基于距离的多转发节点广播协议,在进行广播数据转发时选择多个转发节点以减少转发失败情况下的等待延时,并且通过反向车辆存储转发广播分组,解决正向车道链路断开使信息不可达问题。仿真结果表明,该协议能满足不同交通流密度情况下紧急信息的分发要求,降低分组投递的平均端到端延时和分组转发次数。下一步将研究不同交通流密度情况下多转发节点的选择方法,以提高分组投递成功率。

[1] Sou S,Tonguz O K.A-ADHOC:An Adaptive Real-time Distributed MAC ProtocolforVehicularAd Hoc Networks[J].Mobile Networks&Applications,2011, 16(5):576-585.

[2] 周连科.基于交通流密度的 VANET广播技术研究[D].哈尔滨:哈尔滨工业大学,2011.

[3] Fan C W,Su K C,Wu H M,et.al.An Effective Multihop Broadcast Control Mechanism for Emergency Alert Message in VANET[C]//Proceedings of the 12th International Conference on ITS Telecommunications. Taipei,China:[s.n.],2012:791-795.

[4] Slavik M,Mahgoub I,Alwakeel M M.Analysis and Evaluation of Distance-to-mean Broadcast Method for VANET[J].Journal of King Saud University:Computer and Information Sciences,2014,10(26):153-160.

[5] Song Fang,Tao Luo.A Novel Two-timer-based BroadcastRouting Algorithm for Vehicular Ad-hoc Networks[C]//Proceedings of GreenCom’13,iThings/ CPSCom’13,IEEE International Conference on and IEEE Cyber,Physical and Social Computing.Beijing, China:IEEE Press,2013:1518-1522.

[6] Sou S I,Lee Y.SCB:Store-Carry-Broadcast Scheme for MessageDisseminationinSparseVANET[C]// Proceedings of Vehicular Technology Conference. Yokohama,Japan:[s.n.],2012:1-5.

[7] 蒋建国,苏兆品,张国富,等.多任务联盟形成中的Agent行为策略研究[J].控制理论与应用,2008, 25(5):853-856.

[8] Sou S I,Tonguz O K.Enhancing VANET Connectivity Through Roadside Unitson Highways[J].IEEE Transactions on Vehicular Technology,2011,60(8): 3586-3602.

[9] 刘业,吴国新.基于802.11p/WAVE的车联网连通性模型及其应用研究[J].通信学报,2013,34(6): 85-91.

[10] 任刚,刘晓庆,顾程.基于起讫点的均衡交通分配改进算法[J].系统工程理论与实践,2012,32(10): 2315-2322.

[11] Williams B,Tracy C.Comparison ofBroadcasting Techniques forMobileAd HocNetworks[C]// Proceedings of MOBIHOC’02.Lausance,Switzerland: ACM Press,2002:194-205.

[12] 常促宇,向勇,史美林.车载自组网的现状与发展[J].通信学报,2007,28(11):116-126.

[13] 赵海,彭海霞,朱剑,等.基于组确认机制的车联网中最佳中继节点的选择[J].东北大学学报:自然科学版,2013,34(1):35-39.

[14] 韩江洪,杨帆,刘征宇,等.路基设备辅助下的高速公路车辆信息方向性传输协议[J].电信科学,2013,(1): 57-62.

编辑金胡考

Multi Senders Broadcast Protocol Based on Distance in Internet of Vehicles

HAN Jianghong1,2,LI Chao1,WEI Xing1,2,WEI Zhenchun1,2
(1.School of Computer and Information,Hefei University of Technology,Hefei 230009,China; 2.Engineering Research Center of Safety Critical Industry Measure and Control Technology of Ministry of Education,Hefei 230009,China)

In order to make safety messages broadcast fast and efficiently in Vehicular Ad-hoc Network(VANET),this paper proposes a multi senders broadcast protocol based on distance(DMSBM).In order to cover the most new nodes, DBMSB protocol selects the signal coverage bounder node of pre-node as the best forwarding node,and selects the midpoint node of the signal coverage and the secondary node close to the edge point as alternative forwarding node to avoid forwarding failure rate caused by hidden stations and nodes out of the signal coverage.It also uses the reverse vehicle to store and forward broadcast packet to restore routing.Simulation results show that this protocol can adapt to VANET with a variety of vehicle density,and it can also meet the distribution of emergency information under various traffic densities.It can reduce the average end to end delay and enhance the forwarding efficiency.Routing load rises slowly in this protocol,which can effectively inhibit broadcasting storm.

Vehicular Ad-hoc Network(VANET);broadcast protocol;store and forward;multiple forward;confliction of hidden station;routing restoration

1000-3428(2015)01-0006-06

TP393

10.3969/j.issn.1000-3428.2015.01.002

国家自然科学基金资助面上项目(61370088);高等学校博士学科点专项科研基金资助项目(20100111110004);安徽省自然科学基金资助项目(1208085QF113)。

韩江洪(1954-),男,教授、博士生导师,主研方向:分布式控制,车联网;李超,硕士研究生;卫星,讲师;魏振春,副教授。

2014-02-19

2014-03-26 E-mail:lchao1990@126.com

中文引用格式:韩江洪,李超,卫星,等.车联网中基于距离的多转发者广播协议[J].计算机工程,2015,41(1):6-11.

英文引用格式:Han Jianghong,Li Chao,Wei Xing,et al.Multi Senders Broadcast Protocol Based on Distance in Internet of Vehicles[J].Computer Engineering,2015,41(1):6-11.