一种基于立体交通场景的CAB广播路由算法

袁学松， 张 静， 袁 涛， 韦佳佳

(1.安徽机电职业技术学院 信息工程系， 安徽 芜湖 241000; 2.合肥工业大学 计算机信息学院， 合肥 230009)

一种基于立体交通场景的CAB广播路由算法

袁学松1，2*， 张 静1， 袁 涛1， 韦佳佳1

(1.安徽机电职业技术学院 信息工程系， 安徽 芜湖 241000; 2.合肥工业大学 计算机信息学院， 合肥 230009)

针对立体交通环境下，经典车载自组网广播协议可能出现的数据误传率高、网络延时大、传输不可靠等问题.提出了一种基于路侧单元装置(RSU， Road Side Unit)的准确高效的广播算法CAB(Cubic traffic Adaptive Broadcast Routing Algorithm).该算法根据立体交通不同的应用场景，将广播分为前向、后向和全向类型.同时，通过特殊hello包交换邻居节点信息.通过统计邻居表信息来选择下一跳转播节点，以达到缩短广播时延，提高广播效率的目的.针对立体交通中数据误传率高的问题，引入了车道判别方案和一跳广播确认机制提高其传输的可靠性.使用NS-3和VanetMobiSim仿真结果表明，与现有经典的广播算法相比，该协议在立体交通场景下有更好的包到达率、更轻的网络负载和更低的传输时延.

车载自组网； 广播协议； 网络负载； 包到达率； 传输时延

近年来，随着机动车的逐渐增多，很多城市的交通状况逐渐恶化，导致各大中型城市均开始立体交通的建设.立体交通系统可以解决城市中交通拥挤、空间紧缺等问题.传统的车联网(Vanet)通常研究简单的平面道路(如：高速公路场景、具有十字路口的交通场景、具有建筑物阻碍场景等)，很多经典的路由广播协议也是基于上述场景构建的.在立体交通中，这些协议可能会出现节点选择错误导致的误传现象，会使广播路由协议效率降低，同时增加网络的负担.若能针对传统经典Vanet广播路由协议进行改进并将其应用到立体交通中去，必将提高Vanet在该场景下的广播效率.

1Vanet广播协议与相关场景问题描述

1.1相关广播协议分析

在Vanet中广播路由协议一直是一个较为热门的研究领域.由于当广播节点较为密集时，很容易重复广播，产生冗余数据.轻则影响Vanet的性能，导致网络负载过重，重则会产生广播风暴[1]，导致网络崩溃.为了避免广播风暴的产生，近年来国内外的研究人员针对不同场景研发出不同的广播路由算法.其中文献[2-3]提出的基于概率和基于距离-位置的方法已被广泛应用在普通公路的广播算法中；Lim在文献[4]中提出了使用Hello包来交换广播节点间信息，建立邻居表方案；此类方法还有很多，如SBA(Scalable Broadcast Algorithm)[5]、LFRB(A Location-based Fast and Reliable Multi-hop Broadcast Algorithm)[6]等.这些路由协议通常情况下可以减少重传次数，减低网络负载.但在负载较重的Vanet环境中，快速变化的拓扑会导致路由维护成本大大增加，造成网络拥塞，降低广播的可靠性.Korkmaz等提出的UMB(urban multi-hop broadcast)[7]协议和AMB(Ad hoc Multi-hop Broadcast)[8]协议针对直行道路场景和具有十字路口的场景，提出了RTS/CTS的握手机制和车辆节点充当中继器的机制.有效的提高了广播数据传输的可靠性，减少了硬件的开销，取得了良好的效果.但是上述协议均是在传统道路场景中提出的，不适合当前城市立体交通的状况.

本文针对立体交通中存在误广播与无效广播、转播节点丢失、稀疏交通流场景下节点找不到转播节点的问题，提出了一种基于立体交通广播自适应路由算法(CAB).该算法使用特殊的Hello包检测机制、邻居节点预测机制并使用了携带转发策略[9]和RSU[10-11]装置有效的解决了上述问题.

1.2立体交通场景相关问题描述

城市立体交通与普通城市道路在很多方面有不同之处.在对普通道路设计广播算法时，需要考虑十字路口、建筑障碍物等因素，而在设计城市高架、下穿桥的广播算法时需考虑城市立体交通相关行驶准则.CAB算法将针对城市中立体交通的相关地理特性和车辆运动的相关规律提出以下3个设计要点.

1) 误广播与无效广播问题

图1是某市一个简单的下穿桥式立体交通.当车辆在下穿桥下发起广播时，桥上的车辆由于在广播区域内，会作为目的广播节点，收到该广播信息.但由于车辆行驶在不同的道路上，将桥下车辆的消息广播给桥上车辆是没有意义的，这样就会产生“误广播现象”.如果在同一个道路上，车辆想通知自己后向车辆该路段发生了交通事故，但由于广播是全向广播，消息同时被传送给了前方车辆，前方车辆已经过该路段，得到的消息是无意义的，这样就会浪费网络资源导致“无效广播”现象.

2) 转播节点丢失问题

当行驶中的车辆A要广播数据包时，首先通过hello包找到距离自己较远的转播节点B.如果B在A通信的边缘地带且高速运动，当A转播消息给B时，B已经不在A的通信范围内了，这种情况就会导致转播节点丢失问题.

3) 稀疏交通流[12]的广播问题

在一些特殊的时段(如：凌晨)，城市高架路车辆较少，如果车辆节点想广播信息，可能在广播区域内找不到可以转播的节点，传统的做法是该节点将数据包携带转播，当有节点可以广播时再进行广播操作.这样可能导致广播效率低下，许多节点不能及时得到消息.

2CAB广播算法

算法假设在城市立体交通中行驶的车辆均有GPS和电子地图装置，这些装置可以获取汽车的实时位置信息和海拔信息，这些信息有利于算法判断其是否在同一个平面上行驶.同时，车辆节点内还需有可获得车辆行驶速度、加速度、车辆行驶方向等信息的传感器，这些重要信息也将被应用到算法中.

2.1立体交通场景的广播模型

在CAB算法中，设定了3种场景广播模型(前向广播、后向广播和全向广播).通常，在不同维度和方向行驶的车辆广播的意义不大.在同向车道中行驶的车辆的前向广播常用于通知前方车辆后发有突发事件和重要车辆如：救护车、救火车等，希望前方车辆可以让出某个车道.后向广播常用于通知后方车辆前方有事故发生，希望后方减速或者绕行.全向广播在本算法中主要是用于稀疏车流场景下携带转播和路侧装置(RSU)进行的广播.

本算法定义了节点广播数据包的包头格式如图2所示.

通过在经典协议的数据包包头增加了域，来实现算法的场景自适应.其中，在广播节点的基本信息中增加了地理位置信息，该信息是通过车载GPS获得的广播节点具体经纬度和海拔信息.节点的运动速度和运动方向也是车载设备获取的.当在广播范围内的节点，海拔不同的时候，说明两车不在同一个维度，也就没有必要进行广播.包头的FLAG位表示数据包的传播方向(前向、后向还是全向).当FLAG为0是表示广播包的传播对象是与该节点同运动方向的前向节点；当FLAG为1时.表示广播包的目标节点为和其同向运动的后方节点；当其为-1时，表示全向传播.算法如何确定FLAG位是决定算法成功的关键.BR为广播的范围，为该数据包广播的区域.当在稀疏车流场景下，源节点未能找到下一跳的目的的节点时会携带转播.当到达路侧单元(RSU)还未找到任何转播节点时，会将数据包转发给RSU.算法为了提高传输效率设计了RSU节点，广播数据包包头格式如图3所示.在RSU广播包头中由于删除了运动节点的信息，数据包传输过程中网络负载有所降低.

图4模拟了两个运动节点在车道上行驶的过程，在该过程中A和B通过hello包来交换相互的节点运动信息.广播源节点A(X，Y)以速度运动，节点B(X1，Y1)以速度同向运动，A节点的运动方向角度为，而B节点的运动方向角度为.当表示A与B节点同向运动，否则为反向运动(如本算法不研究反向运动的广播包传输).两个节点的相对位置为矢量K=(X1-X，Y1-Y)，那么K的方向决定了A，B节点的前后位置.假设K的方向为，那么表示节点B为A的前向节点，否则为反向节点.这样只要通过hello包相互交换各个节点的运动方向，就可以了解到各节点与广播源的前后关系，使数据传播更有目的性.

2.2Hello包机制与邻居信息检测[13]维护机制

算法采用hello包机制来维护广播网络的拓扑结构.在hello包机制中重要的是高效而又准确的维护邻居转播节点.每个节点都会周期性的广播自己的hello包，各节点间通过该信标来交换信息，从而维护局部网络拓扑信息.在CAB算法中hello包结构如图5所示，它包含了自身的节点运动信息、1跳邻居表信息和2跳邻居个数信息.

各节点首先通过交换hello包信息来确定广播模型.源节点希望花费最少的时间将自己的信息广播到最远端，并且能广播给更多的节点.这样就需要合理的选择下一跳转播节点.传统的方法是选择离源节点最远的一个节点进行传输，这样可能造成“低效率传输”和“传输不可达”的情况.如图6当t时刻C节点时A节点理想的下一跳节点，但在转播时，网络的拓扑已发生变化.C′明显不是A′最合适的下一跳节点.图7中，在t时刻A选择了B作为自己的转播节点，在转播时，B′已超出了A′的通信范围，造成了传输不可达.这两种情况都是忽略节点的移动性所造成的，都会造成局部网络的重新构建，数据包的重发，进而引起网络的拥塞.

CAB算法充分考虑到节点的移动特性，使用提前预测的机制来进行下一跳转播节点的选择.高效而又准确的维护网络拓扑的邻居节点.如图8，该图是一个典型的邻居转播预测图.在t时刻，A的转播节点应该是C节点.但节点A并不会马上选择C作为下一跳转播节点，而是对网络拓扑进行预测.A通过交流的hello包了解到各节点的速度和运动方向，计算经过Δt的路由存活时间各节点的可能位置，再来判定谁是可靠的、最远的转播节点.这时A会选择D节点作为自己的转播节点.由于广播节点在选择下一跳时不仅需要考虑可靠的传输到下一跳，而且希望尽快扩散到广播区域.这就需要下一跳节点具有更多的下1跳邻居和2跳邻居.所以，给hello包增加了这两个域，当hello包周期性交换信息时，广播节点会选择在可靠距离范围内的、传播距离最远的、且1跳和2跳节点较多的转播节点去转发数据包.

2.3可靠的一跳广播确认机制

在数据包传输过程中，为了能可靠的传输广播包，节点和节点间将采用“1跳确认握手”机制.局部拓扑数据广播过程都是由若干跳过程组成的，只要保证每一跳都是可靠的，整个数据广播过程就是可靠的.当广播节点A经过hello包信息交换后，选择了B作为其转播节点.算法会按照图2的包头格式进行数据包的发送.在发送过程中将自己的ID信息放入Source域，表示广播是由A发起.同时，确定几个备用的转播节点，将信息放在BRN域中.节点A会启动定时器和计数器，定时器设定为超时时间，计数器设定为超时次数.在一定时间内A未收到B的回复包，A会启动重发机制，计数器自减一，当计数器为0时表示B不在A的传输范围内，A会通过交流hello包及时改变自己的转播节点.

2.4算法描述

CAB广播算法是通过Hello包机制来维护邻居和确定转发节点的.同时，节点交流hello包可以避免不同海拔(不在一个道路)上的节点进行数据包的误传输.在立体交通中增加了RSU装置，以保证在稀疏的交通流场景下数据更可靠的传输.图9为车辆节点和路侧装置的数据包转发方案和邻居节点的维护方案流程图.

算法具体可描述为：

1) 源节点广播数据包，首先通过各邻居节点通过Hello包的信息交换判断车辆节点的海拔高度(由于城市交通的坡度影响，允许一定误差).如果海拔高度不同，说明节点不在同一道路上，行驶互不干扰，不进行数据的转发.如果在一个海拔高度上则进行过程2)操作；

2) 通过hello包机制和邻居维护机制，根据场景的需要更新源节点的FN域和BN域.将在通信范围内，广播节点前向的节点放入hello包的FN域，将后向节点放入BN域.同时，通过邻居hello包计算源节点2跳节点的数目，并将其存放在hello包中.源节点更新完hello包后进入3)；

3) 通过节点运动预测机制判断是否有合适的转播节点，若有进入4)，若没有进入5)；

4) 通过“1跳确认机制”可靠的传送数据给转播节点；

5) 判断在节点广播区域是否有路侧装置，如果没有进入(1)，如果有进入(2)；

(1) 车辆节点将数据包携带转播，同时周期性的更新hello包，寻找合适的广播节点和RSU.转至过程3)；

(2) 广播数据包通过“1跳确认机制”发送给RSU.RSU根据广播包中FLAG标志位，确定是前向还是后向广播.通过自身高功率发射至相应区域，同时，通过有线机制传送给前向或者后向的RSU装置，并由该装置进行全向广播.

3仿真实验分析

为了验证CAB算法在立体交通场景工作的有效性，本文将使用交通仿真工具VanetMobiSim[14-15](VehicularAdHocNetworksMobilitySimulator)对真实场景进行构建，并将产生的节点轨迹文件使用离散时间模拟器NS-3进行网络性能仿真.将仿真结果与较适合城市道路，经典的UMB协议和AMB协议进行各种网络性能的比较.

3.1交通环境模型与车辆运动模型的参数

本文分别对较为简单立体交通模型和稍复杂的立体交通场景进行仿真实验.仿真的场景如图10和图11所示，在图10描述的是只有一个长3km、宽2km的立交桥场景的模型.图11是一个立体交通由A、B、C、D四条路组成，每条路长3km.其中，C与A、B交汇时采用下穿桥式道路模型，D与A、B交汇时采用高架式道路模型.仿真参数分别如表1所示.

在仿真中，广播数据包发送速率为1packet/s，数据包类型为CBR，且广播节点、广播时间和广播方向都是随机的.在该场景中RSU设置为每公里1个，且在两条道路交汇处必有1个RSU.通过分车道控制节点在道路上行驶的速度和加速度模拟车辆随机分布的运动形态.

3.2仿真结果与分析

本次仿真实验主要采用广播包到达率、平均广播开销以及平均延时3个指标来衡量算法在简单和复杂立体交通场景下的优劣性.在车辆密度不断变化下，比较UMB协议、AMB协议和CAB算法的性能.

在简单的交通场景中，由图12～14可以看出，CAB算法的各个网络性能指标与UMB和AMB协议差异不大.由于CAB算法加入了邻居节点的预测方案减少了无效传输，节点的平均时延降低明显.但由于采用了RSU导致在平均广播开销的指标上略高于其他协议.在复杂的交通场景下由图15可知，平均广播开销为某一个广播包传输给各节点的数据总量，它的计算方法为将场景中传输数据总量除以广播包数据总量.CAB算法由于增加了RSU节点，同时采用“1跳确认机制”，这些因素都会导致额外的数据包的产生.而其他两种协议，由于数据为全向传播，也会产生很多无用的数据包.总体上，CAB算法在场景中的平均广播开销要略小于AMB和UMB协议.图16为广播包到达率，由于采用了可靠的“1跳确认机制”，CAB算法几乎达到100%的包到达率，较其他两种算法有更好的性能.图17中，CAB算法的节点平均延时也较为稳定，随着车辆密度的增加始终保持在20ms，其他两种协议在立体交通场景下由于会产生误传，会导致重传增加了节点传输的平时延时.

4结束语

本文将Vanet广播协议应用于城市立体交通通信领域，提出了一种新的CAB算法，该算法无论是在稀疏车流还是在稠密车流的场景中都能够保证广播包的到达率，但由于增加了hello控制包和广播包的控制字段，并使用了RSU节点和保证可靠性的“1跳确认机制”，平均广播开销性能与经典协议相当.算法增加的RSU节点可能会使硬件成本提升.通过仿真表明，CAB算法较其他类似算法更适合于城市立体交通场景的可靠数据传输，具有较大的应用价值.

[1]TSENGYC，NISY，CHENYS，etal.Thebroadcaststormprobleminamobileadhocnetwork[C]// 5thAnnualACM/IEEEInternationalConferenceonMobileComputingandNetworking， 1999: 153-167．

[2]LOCHERTC，HARTENSTEINH，TIANJ，etal.AroutingstrategyforvehicularAdHocnetworksincityenvironments[J].ProcofIntelligentVehiclesSymposium， 2003:156-161．

[3]WILLIAMSB，CAMPT.ComparisonofbroadcastingtechniquesformobileAdHocnetworks[C]//ProceedingsoftheInternationalSymposiumonMobileAdHocNetworkingandComputing(MobiHoc)，Lausanne，Switzerland， 2002:194-205．

[4]LIMH，KIMC.MulticastTreeconstructionandfloodinginwirelessAdHocnetworks[C]//Proceedingsofthe3rdACMInternationalWorkshoponModeling，AnalysisandSimulationofWirelessandMobileSystems，Boston，USA， 2000:61-68．

[5] 彭 伟， 卢锡城. 移动自组网络中采用连通支配集的有效广播技术[J]. 软件学报. 2001， 12(4):529-535．

[6] 周 娜， 刘南杰， 赵海涛. 一种基于地理位置的车载自组网快速可靠广播算法[J]. 计算机应用与软件. 2014， 3(1)：108-110．

[7]KORKMAZG，EKICIE，OZGUNERF，etal.Urbanmulti-hopbroadcastprotocolforinter-vehiclecommunicationsystems[C]//ACMInternationalWorkshoponVehicularAdHocNetworksACM， 2004:2062-2063．

[8]KALININM，ZEGZHDAP，ZEGZHDAD，etal.Softwaredefinedsecurityforvehicularadhocnetworks[C]// 2016InternationalConferenceonInformationandCommunicationTechnologyConvergence(ICTC)，JejuIsland，SouthKorea， 2016: 533-537．

[9]TONGUZO，WISITPONGPHANN，FANB，etal.BroadcastinginVANET[C]//IEEE， 2007:7-12．

[10]DUBEYB，CHAUHANN，CHANDN.EfficientdataschedulingtechniqueatRSUforvehicularad-hocnetworks[C]//2016InternationalConferenceonInformationCommunicationandEmbeddedSystems(ICICES)，Chennai， 2016: 1-7．

[11]ALIG，RAHMANMA，CHONGPHJ，etal.OnefficientdatadisseminationusingnetworkcodinginMulti-RSUvehicularAdHocnetworks[C]// 2016IEEE83rdVehicularTechnologyConference(VTCSpring)，Nanjing， 2016: 1-5．

[12] 周连科. 基于交通流密度的VANET广播技术研究[D].哈尔滨：哈尔滨工业大学， 2011:14-16．

[13] 郭炼祥. 城市车载自组网路由协议的研究[D].广州：华南理工大学， 2011:32-35．

[14]ASHTAIWIA，ALTAYESHA，BELGHETK.IEEE802.11pperformanceevaluationatdifferentdrivingenvironments[C]//2015WorldSymposiumonComputerNetworksandInformationSecurity(WSCNIS)，Hammamet， 2015: 1-8．

[15]PERDANAD，SARIRF.PerformanceevaluationofcorruptedsignalcausedbyrandomwaypointandGauss-MarkovmobilitymodelonIEEE1609.4standards[C]//2015InternationalSymposiumonNext-GenerationElectronics(ISNE)，Taipei， 2015: 1-4．

A CAB broadcast routing algorithm based on 3D transportation scene

YUAN Xuesong1，2， ZHANG Jing1， YUAN Tao1， WEI Jiajia1

(1.Department of Information Engineering， Anhui Technical College of Mechanical and Electrical Engineering， Wuhu， Anhui 241000； 2.School of Computer and Information， Hefei University of Technology， Hefei 230009)

In this paper the vehicle self-organized network broadcasting protocol is studied under 3D transportation environment. In order to handle the data error， network delay， unreliable transmission， we propose a novel accurate and efficient algorithm Cubic traffic Adaptive Broadcast Routing (CAB) based on the Road Side Unit (RSU). In this algorithm， the broadcasting is divided into forward， backward and all-direction types according to the application in 3D transportation environment. Meanwhile， neighboring note information is exchanged using hello package exchange. By choosing the next broadcasting node based on the neighboring node statistics， the broadcasting efficiency is improved. For the data error problem in 3D transportation， the vehicle lane classification and the first jump confirmation method are introduce. Using NS-3 and VanetMobiSim to simulate the results， the proposed algorithm exhibits better package arrival rate， lower network loads， and smaller network delay， compared with the traditional broadcasting algorithms．

vehicle self-organized network; broadcasting protocol; network load; package arrival rate; transmission delay

2016-10-20.

安徽省教育厅2016年度高校领军人才引进与培育计划项目(gxfxZD2016324)；安徽省教育厅省级教学团队项目(2014jxtd99)；2016安徽机电职业技术学院院级重点科研项目(2016zdzr10)．

1000-1190(2017)02-0143-08

TP393.02

A

*E-mail: ahjdyxs@126.com．