基于密度和距离的多跳广播转发节点选择方案

张 浩1，王桂芝2

（1.河南牧业经济学院软件学院，郑州 450000；2.河南牧业经济学院信息与电子工程系，郑州 450044）

基于密度和距离的多跳广播转发节点选择方案

张 浩1，王桂芝2

（1.河南牧业经济学院软件学院，郑州 450000；2.河南牧业经济学院信息与电子工程系，郑州 450044）

多数车联网VANET（……Vehicular Ad Hoc Network）的安全应用均采用多跳广播方式分发安全消息。现已提出了许多的多跳广播转发节点选择方案，但它们以减少转发节点数为目的；为此，提出基于密度和距离的多跳广播转发节点选择方案DDBFS（density －distance based multi－hop broadcast forwarder selection scheme），记为DDBFS；DDBFS方案主要解决两个问题：密集区域的冗余广播和稀疏区域的高的传输时延；在提出的DDBFS方案中，节点在决策是否转播接收的消息前，依据距离和网络密度设置定时器，一旦定时完毕，且在定时期间，没有其他节点转发该消息，该节点就成为下一跳转发节点；仿真结果表明，与现有的方案相比，提出的DDBFS协议在重播次数和传输时延性能得到显著提高。在密集区域，消息重播次数下降了约57%，在稀疏区域，传输时延缩短了约82%。

紧急消息；广播协议；密度；距离；车联网

0 引言

车联网VANET（vehicular ad hoc network）被认为是应用于未来智能交通系统的最有前景的技术。通过车辆间通信提高交通效率和安全［1 2］。众多的车辆应用被广泛讨论，特别有关车辆安全的应用，如减少交通事故、提高行车安全。此外，天气预警、道路实况、碰撞预警等应用也可通过车与车V2V （vehicle to vehicle）通信或车与路边的基础设施V2I（vehicle to infrastructure）通信实现，而这些应用中最为关键在于广播技术。

与传统Internet接入网络采用的单播方式不同，由于消息涉及某区域多个车辆，VANET的安全应用需采用广播方式传输消息。此外，可能某些车辆离消息发送较远，不在一跳通信范围内，需要采用多跳广播传输消息。一个理想的广播机制需要及时地将消息传输至相关车辆。即以低时延、传输率高为性能要求。然而，无线通信通常不可靠，并且存在节点隐藏问题、数据包碰撞、信道衰落以及障碍物等问题，这些问题给广播机制提出挑战。

为此，针对VANET安全应用的多跳广播问题，面向高速场景的紧急消息传输问题，提出基于密度和距离的多跳广播转发节点选择DDBFS（density－distance based multi－hop broadcast forwarder selection scheme）方案，记为DDBFS。消息接收节点在转播消息前，依据距离设置等待时间。此定时时间被限定于一个间隔，间隔的边界反比于离发送节点的距离。与其他的方案不同，DDBFS方案在推导间隔边界时考虑了车辆密度。具体而言，当网络密度比较高时，DDBFS方案采用更宽的间隔，进而降低多个车辆同时转发消息的概率，当网络密度较低时，减少等待时间，从而降低传输时延。DDBFS方案引用两个函数去计算等待时间边界，最终实现两个目的：1）当网络密度比较高时，减少转播消息的数量；2）当网络密度比较低时，降低消息传输时延。

1 相关工作

为了减少传输跳数和降低传输时延，多数多跳广播协议均采用发送节点与接收节点间距离选举转发节点，离发送节点最远的节点具有最短的等待时间，或者依据网络密度、信道条件等，自适应调整传输功率或数据传输率。

文献［3］提出了基于RTB／CTB握手机制的智能广播SB （smart broadcasting）协议。然而，SB协议依赖一些参数，如竞争窗口CW（contention window）。文献［4］提出FREDM协议，为了提高消息传输的可靠性，在预定的范围内重复广播消息。而文献［5］提出Bi－Zone协议，其利用距离门限值，将转发节点的传输范围划分两个相邻的区域，离转发节点距离大于距离门限值的节点具有更短的等待时间。

此外，一些研究人员利用广播概率降低转播消息的数量。在这些协议中，每个节点依据概率转播消息。转播概率越低分发消息的成本越少，消息被传输至其他车辆的概率也越低。反之，若转播概率越高，分发消息成本就随之增加，相应地，消息被传输至其他车辆的可能性越高。因此，这存在分发消息成本与分发概率间的平衡问题。现有的协议采用了不同的方式推导转播概率：固定的概率值。如文献［6-7］依据信道条件设定，而文献［8］依据在一定时间间隔内接受消息的数量计算设置此值。此外，文献［9-10］利用一跳邻居数设定此值。这些概率计算模型并不是针对VANET的安全应用而设的。

与VANET其他应用不同，在VANET安全应用中，有效地传输数据是非常重要的，其关系到生命安全。因此，在广播消息时，必须考虑了消息传输的时延和可靠性。然而，满足这两个性能具有极大的挑战性，也必须权衡传输时延与传输可靠性间的关系。

现在的多数协议采用优化下一跳转发节点选择机制，降低传输时延。这些协议不同之处在于：计算等待时间间隔方式不同。然而，这些协议仍然遭受在密集区域的消息碰撞、在稀疏区域的消息传输时延高的问题。它们在计算时间间隔时，没有考虑网络密度问题。例如，以文献［5］的方案为例，在转播消息前，每个节点设置一个定时器，定时时间边界为［Tlower，Tupper］。如果节点离发送节点的距离大于预定的距离门限值dth，Tlower＝0，而定时时间上限Tupper：

其中：R表示车辆传输距离，Tmax表示最长的等待时间。d表示离发送节点的距离。

而对于离发送节点距离小于距离门限值dth的节点，定时时间上限Tupper设为最大，即Tupper＝Tmax，而下限Tlower：

考虑这样场景：若多个节点均在传输距离的边界上，依据式（1）可知，，即Tupper＝0，这些节点的定时时间的上限、下限均为0。那么它们一旦接收了信息，无需等待，就同时转播消息，这会引起大量消息冗余，也增加了信道开销，必然会引起信道竞争。特别是在密集区域，这些问题更为严重。即使这些节点离发送节点的距离不同，但是它们的定时时间也非常相近，在这种情况下，它们的定时时间相互重叠较多，消息碰撞概率仍较高。

而文献［11］采用了基于竞争窗口CW的定时时间设置。竞争窗口CW的值在［CWmin，CWmax］区间变化，取决于距离和传输范围，如式（3）所示。

上述的这些协议在选择下一跳转发节点没有充分考虑网络密度和紧急消息类型。由于VANET的车辆分布具有时空特性，分布随时间变化，因此，在决策下一跳转发节点时，需考虑车辆分布，进而有效地缩短传输时延。此外，不同的消息类型，对传输时延具有不同的要求。为此，本文提出DDBFS方案。在选择下一跳转发节点时，考虑距离、车辆密度信息，并结合不同紧急消息类型，最终实现降低传输时延的目的。

2 DDBFS方案

为了减少转发节点数目，并降低时延，DDBFS方案在计算定时时间时考虑了距离和网络密度信息，并利用两个函数计算Tlower、Tupper。

2.1 约束条件

提出DDBFS方案以高速公路车辆为研究对象，并基于下列约束条件：

1）所有车辆均装有GPS设备，能够获取自己的地理位置；

2）所有车辆具有短距离通信系统DSRC，能够以直接或多跳方式与其他车辆进行通信；

3）每个车辆周期地广播协作预示消息CAM（Cooperative Awareness Message），其包含车辆的位置、方向和速度信息［12］，且广播周期为T。

4）一旦检测到紧急情况，车辆就立即发送环境通知消息DENM（decentralized environment notificationmessage）［13］，其包含紧急事件的位置、消息传输方向等。

2.2 DDBFS方案

提出的DDBFS方案引用距离作为选择转发节点性能指标，试图选择离发送节点距离最远的节点作为消息的转发节点。一旦车辆发现了事故，就立即产生DENM消息，并向后向车辆广播此消息。接收到此消息的车辆首先检测是否之前已接收了该消息，若是新消息，再判断消息保鲜期，若没有过期，则自己的位置坐标加入DENM消息，并设置定时器，再等待定时器计时完毕。若在定时器计时完毕期间，已有车辆已经转发了DENM消息，表明已有车辆转发了DENM消息，则放弃本次转发消息的竞争。

2.3 非均匀化段

将车辆后向传输距离划分为不同段segment，总的段数K：

其中：ρavg可按式（5）计算。

其中：hi表示车头时距、Vi表示车辆i速度。

2.4 DENM消息的分类及保鲜度

依据不同DENM消息对时间要求的不同的特性，将其分6类，如碰撞预警 （Collision warning）、突然刹车预警（Sudden break warning）等，如表1所示。每一类DENM消息对传输时延的要求不一，例如，碰撞预警 （Collision warning）类和突然刹车预警（Sudden break warning）类消息对时间要求苛刻，需要快速传输至后续车辆，其保鲜期短。从安全角度，与碰撞预警消息相比，左转辅助（Left Turn Assistant）消息的传输时延允许大些，其保鲜期可更宽。

表_1 DENM消息的分类及对应的保鲜度

2.5 定时器设置

每个节点的定时器定时时间是从区间［Tlower，Tupper］内随机选择。之所以从区间内随机选择定时时间，是为了降低节点具有相同的定时时间的概率，缓解信道竞争。而每个节点的区间的上限Tupper、下限Tlower值取决于距离和局部密度信息。

节点i的上限Tiupper定义如式 （6）所示。

其中：Tmin、Tmax分别表示最短、最长的等待时间。而ρ表示局部车辆密度，如式（8）所示：

其中：Nmax表示在交通堵塞时一跳邻居数。而N表示一跳邻居数，其等于在T内所收到的CAM消息数。而CWlength、Δd分别如式（9）、（10）所示：

2.6 DENM消息转发

一旦检测到紧急事件，车辆（假定节点i）就产生DENM消息，其包含紧急事件的地理位置（Event Position）、DENM消息传输方向（Direction）、保鲜期（Fresh time）、跳数（Num－hop）以时间戳（Timestamp），其格式如表2所示。

表2 DENM消息格式

其中：Event Position表示事件的地理位置，Direction表示DENM消息的传输方向，且为一比特，若是1，表示后方；若是0，表示前／后。对于高速公路而，紧急消息均是向后方车辆传输。Fresh time表示此消息的保鲜期，依据表1进行设置。而Num－hop表示DENM消息被转发的次数。每次被转发，就加1，初值为零。Timestamp表示产生DENM的时间。

节点i的一跳邻居节点Ni将收到DENM消息，以节点j为例。一旦节点j收到DENM消息，就检测之前是否收到些消息，若已收过，则直接丢弃，否则，再判断此消息保鲜期是否已过，若保鲜度已过，也直接丢弃。否则，就依据式（6）和式（7）计算Tlower、Tupper，再从［Tlower，Tupper］区间随机选择一个定时时间。然后，待定时完毕。若在定时完毕期间，已有其他节点转发了此消息，表明已有节点成功转发消息，在这种情况下，就直接丢弃此消息。否则的话，就待定时器定时完毕，就将Num－hop自加1，再广播DENM消息。DDBFS协议流程如图1所示。

图1 DDBFS协议总体流程

3 性能仿真及分析

3.1 仿真参数及性能指标

利用NS－2.34［14］仿真器分析提出的DDBFS协议性能。首先，修改NS－2.34的MAC层参数，摒弃ACK／RTS／CTS机制。然后，再利用SUMO仿真器［15］产生移动轨迹文件。此外，选择双向6车道的高速公路为仿真场景，且长路为4公里。车流量密度从每公里20～120变化。车辆速度范围为［80，120］km／h变化。具体的仿真参数如表3所示。

表3 仿真参数

同时从消息重播次数、传输时延和传输可靠性三方面分析提出的DDBFS方案性能，并以随机选择距离转发方案SDR （Selection Distance－based Relay scheme）［11］作为参照。RDS方案在计算等待时间间隔时没有考虑车辆密度。

3.2 数值分析

3.2.1 平均重播次数

SDR方案和DDBFS方案的消息平均重播次数随车流密度变化曲线如图2所示。从图可知，SDR方案的重播次数随着车流密度的增加而上升。原因在于：当网络密度增加，两节点间的距离减少，节点相邻更紧密。在这种情况下，多个节点的定时器定时时长相近，导致它们同时重播的概率增加，这就提升了消息碰撞的概率，使得更多消息需要被重播。与SDR方案相比，提出的DDBFS方案的性能得到提升。例如，当车流量100 vehicles／km和120 vehicles／km时，DDBFS方案的消息被重播次数分别下降了50%和57%。

图2 平均重播次数

3.2.2 平均传输时延

两个方案的平均传输时延情况如图3所示。从图3可知，SDR方案的平均传输时延高于提出的DDBFS方案，且SDR方案在初始时，平均传输时延较大。例如，在车流量20 vehicles／km时，SDR的传输时延高达336 ms，而在车流量60 vehicles／km时，其时延降低为133 ms。确实，在网络稀疏环境下，在有限的通信范围内寻找一个转发节点是非常困难的。因此，离发送节点近的节点具有更高的概率去转播消息，这就增加了传输时延。随着车流量的增加，车辆间更容易形成连接，提高寻找下一个转发节点的概率，进而缩短了传输时延。

提出的DDBFS方案的传输时延性能较好，原因在于：当车流量较低时，DDBFS方案的Tupper较小，降低了传输时延。当车流量越大，Tupper就越宽，减少了两个节点具有相同定时时间的概率，缓解了信道竞争。当车流量为120 vehicles／km时，DDBFS方案的平均传输时延小于120 ms，这是可以接受的。

图3 平均每跳时延随车辆密度的变化情况

3.2.3 传输跳数

此外，图4显示了消息的平均传输跳数。从图4可知，提出的DDBFS协议的传输跳数低于SDR协议。特别是在车流量100 vehicles／km和120 vehicles／km时，SDR协议的传输跳数高达12。这主要是因为：SDR协议的定时器呈随机性，被选择的下一跳转发节点并不是离发送节点最远的节点。此外，提出的DDBFS方案的传输跳数并不随车流量变化，保持在7跳左右。

图4 平均传输跳数随车辆密度的变化情况

4 总结

针对VANET紧急消息的广播问题，提出基于密度和距离的多跳广播转发节点选择DDBFS方案。在DDBFS方案中，节点在转发消息前，依据离发送节点的距离和局部密度设置定时器，当定时完毕，且没有其他节点转发消息，该节点就立即转发。仿真结果表明，与SDR方案相比，DDBFS方案在网络分布密集区域，重播次数下降了近57%，而在稀疏区域，传输时延缩短了近82%，实现了预计的目标。

［1］Misra S，Venkata Krishna P，Saritha V.LACAV：an energy－efficient channel assignment mechanism for vehicular ad hoc networks ［J］.J.Supercomput.，2012，62（3）：1241-1262.

［2］Misra S，Venkata K，Saritha P.Learning automata－based virtual backoff algorithm for efficient medium access in vehicular ad hoc networks［J］.J.Syst.Architect.，2013：1383-7621.

［3］Fasolo E，Zanella A，Zorzi M.An effective broadcast scheme for alert message propagation in vehicular ad hoc networks［A］.Proceedings of the IEEE International Conference on Communications ［C］.Istanbul，Turkey，2006：3960-3965.

［4］Lee J F，Wang C S，ChuangMC.Fats and reliable emergency message disseminationmechanism in vehicular ad hoc networks ［A］.Proceedings of the IEEEWireless Communications and Networking Conference［C］.Sydney，Australia，2010：1-6.

［5］Hrizi F，Bonnet C，Harri J，et al.Adapting contention－based forwarding to urban vehicular topologies for traffic safety applications ［J］.Annals of Telecommunications，2013，68（5）：267-285.

［6］Jiang H，Guo H，Chen L.Reliable and efficient alert message routing in VANET［A］.Proceedings of the 28th International Conference on Distributed Computing Systems［C］.Beijing，2008：186 -191.

［7］Slavik M，Mahgoub I.Statistical broadcast protocol design for unreliable channels in wireless ad－hoc networks［A］.Proceedings of the IEEE Global Telecommunications Conference［C］.Miami，FL，USA，2010：1-5.

［8］Hafeez K A，Zhao L，Liao Z，et al.A new broadcast protocol for vehicular ad hoc networks safety applications［A］.Proceedings of the IEEEGlobal Telecommunications Conference［C］.Miami，FL，USA，2010：1-5.

［9］Bako B，E.Schoch，F.Kargl，and M.Weber.Optimized position based gossiping in VANETS［A］.Proceedings of the 68th IEEE Vehicular Technology Conference［C］.VTC，Calgary，Canada，2008：1-5.

［10］SlavikM，Mahgoub I.Stochastic broadcast for VANET［A］.Proceedings of the 7th IEEE Conference on Consumer Communications andNetworkingConference［C］.LasVegas，Nevada，USA，2010：205-209.

［11］Palazzi C E，Roccetti M，Ferretti S.An intervehicular communication architecture for safety and entertainment［J］.IEEE Trans.Intell.Transport.Sys.，2010，11（1）：90-99.

［12］Kesting A，Treiber M，Helbing D.Connectivity statistics of storeand－forward intervehicle communication［J］.IEEETrans.Intell.Transp.Syst.，2010，11（1）：172-181.

［13］Pascoe－Chalke M，Gomez J，Rangel V，et al.Route duration modeling formobile ad－hoc networks［J］.WirelessNetw，2010，16（3）：743-757

［14］Network simulator—ns（version 2）.［Online］.Available：http：／／isi.edu／nsnam／ns／，2013.

［15］Sumo project.［Online］.Available：http：／／sourceforge.net／projects／sumo，2013.

Density－distance Based Multi－hop Broadcast Forwarder Selection Scheme in VANET

Zhang Hao1，Wang Guizhi2

（1.Software Institute，Henan University of Animal Husbandry and Economy，Zhengzhou 450000，China；2.Department of Information＆Electronic Engineering，Henan University of Animal Husbandry and Economy，Zhengzhou 450044，China）

Most VANET（Vehicular Ad Hoc Network）safety applications use multi－hop broadcast communications to disseminate safety information.Many multi－hop broadcast forwarder selection schemes have been proposed.Their aim is to reduce the number of forwarders.In this paper，we propose a density－distance based multi－hop t forwarder selection scheme（DDBFS）to address the problems of（i）redundant broadcasts particularly in dense network and（ii）the high latency in sparse networks.We present a solution where both the distance and the network density are considered in calculating the waiting time before deciding whether to rebroadcast received messages or not.Once the waiting time is over and the messages have been not forwarded by other nodes，the node is considered as to be next－hop node.Simulation results show that our scheme achieves better performance in terms of number of rebroadcasts and dissemination delay compared to existing solutions.Our protocol results in improvement up to 57%in message rebroadcast when the network density is high，and 82%in dissemination delay when the network is sparse.

emergency messages；broadcasting；density；distance；VANET

1671-4598（2016）08-0275-04

10.16526／j.cnki.11－4762／tp.2016.08.075

：TPT393

：A

2016-03-01；

：2016-03-25。

河南省教育厅2015年度《河南省高等学校重点科研项目计划》（15A520077）。

张 浩（1981-），男，河南长葛人，硕士，讲师，主要从事网络管理与安全，路由交换方向的研究。

王桂芝（1970-），女，河南郑州人，硕士，副教授，主要从事数据挖掘、聚类分析方向的研究。