程青青 陈戈珩

摘要

车载网络最重要的应用就是安全信息的传播。不受控制的重播导致相同信息的冗余重传、频繁的信道冲突以及网络资源耗尽。为了使网络冗余和延迟最小化，同时确保整个网络的高可靠性，本文采用了基于概率的多跳广播方法来解决可靠性和延迟的问题在本文中，给出了一种新的基于概率的多跳广播协议，与现有的概率分配方案不同，本协议不仅考虑了本地的信息，还考虑了转发概率中一跳范围内的车辆数量，可以通过调整转发概率的基本参数来获得更高的转发成功率。在参数设定的过程中，将更高的转发概率分配给更靠近源节点的传输边界的节点。我们比较了网络转发成功概率、平均次数和平均信道访问延迟时间通过对仿真参数的记录，证明了所给出的广播协议具有高可靠性和有效性。

【关键词】车载网络 概率 网络密度 多跳广播

1 VANET介绍

依据车载自组织网络对于紧急信息必须及时、可靠地传播到相关区域内的所有车辆的特性提出了多种多跳广播方案来增强紧急消息传播的性能。这种多跳广播方案解决了单跳广播的覆盖区域不够大的问题，可以保证目标区域内的每个车辆都能够成功的接收消息。现有的多跳广播可以分为三类：基于时间、基于编码和基于概率的方法，这三类多跳广播方案都能增强紧急消息传播协议的性能。在本文中，主要专注于研究基于概率的多跳广播。

1.1 基于时间的多跳广播

文献[1]中给出一种适应于高速公路的基于时间的快速转发协议，称为DEEP。假设在高速公路上运行的每一辆车的位置和所属的区域都是已知的，当车辆接收到紧急消息，会依据与源车辆之间的距离来计算延迟时间。通过实验测试，DEEP多跳广播协议有效的解决了广播风暴问题，大大缩短了广播延迟时间，具有较高的可靠性，唯一不足之处是这种多跳广播机制需要依賴于高精度GPS定位和本地地理信息。为了解决这种不足，文献[2]z中提出了一种健壮性较好的快速转发协议（ROFF）。它通过计算等待时间来避免潜在的转发器候选（PFC）之间的传输冲突。ROFF令每个PFC的等待时间与其转发优先级成反比，该转发优先级是基于空白空间分布（ESD）的位图计算的。ESD位图存储了前一个转发器和转发器候选者之间距离的信息。

1.2 基于编码的多跳广播

文献[3]中提出了一种关于V2V通信的网络编码方法，这种网络编码为每个中间节点提供转发前不同接收分组的能力。在文献[4]中将XOR和RS编码技术应用于确定性广播方法（CODEB），有效的降低了整个网络的传输次数。文献[5]中提出了一种新的协议（EBNC），它将网络编码技术与概率转发算法相结合，这种结合方式可以运用网络编码来减少协议开销，提高分组接收概率。研究表明，CODEB和EBNC多跳广播协议在节点移动速度较快的情况下具有脆弱性，在高速变化的车载网络中，这两种方法显现出很大的劣势。

1.3 基于概率的多跳广播

基于概率的多跳广播协议在重新广播消息之前不需要额外的等待时间，允许每个节点以预定的概率立即重新广播。最简单的基于概率的多跳广播称为泛洪，在泛洪中，每个节点在源节点接收到紧急消息之后会立即以概率1重新广播该分组，这种广播方法会导致广播风暴和过多的数据冗余，在密集的无线车载网络中这一缺陷也表现的更加明显。文献[6]中提出了一种加权p的持续广播（WPB）方案来避免重复广播的问题，可以表示为：

p=（d/R）（1）

d：表示从当前位置到源车辆的距离;

R：表示每辆车的传输半径;

P：表示重播的概率;

这种转发方案实现了从传播范围一半到范围边界之间的所有节点的转发概率超过了50%，因此，在密集的VANET中会导致严重的冲突和端到端的延迟。在文献[7]中，L.Zhou改进了WPB方案并提出了NPPB协议，此时的转发概率为：

K：表示NPPB协议中的转发概率系数。

其中K的值越大，分配给源节点附近的转发概率越小，NPPB在密集的VANET环境中，协议的性能要优于WPB，但是当传输范围附近的区域内没有足够的车辆时，能够传输成功的概率将明显降低。文献[8]中提出了基于概率的不确定转发方案（IF），此时的转发概率变为：：表示一般车辆间距下分布的均值指数假设值。

研究表明，此时的转发概率分布可以适应车辆密度[9]。在对IF方案进行真实车辆间距分布的评估中发现IF方案的节点难以察觉间距分布[10]，该方案仍然无法解决当传输范围的边界区域车辆较少时导致的传输成功概率低的问题。

2 算法模型

本文提出了一种新的多跳广播算法来解决密集VANET中的网络冲突问题。为了更好地应用于不同的车辆密度发挥网络性能的优越性，转发概率会依据实时车辆密度的变化而变化。不仅可以在第一时间成功转发紧急消息还减少了数据包的延迟，在转发的过程中减少了重复消息的传播，还引入了参数k来提高消息转发成功的概率。

2.1 网络建模

给出假定情景下的网络模型：

（1）假设车辆的传输范围R;

（2）假设车辆均匀地分布，车辆间空间为V_S=N/R，其中N指的是一跳范围内的节点总数;

（3）每辆车都会配备全球定位系统（GPS），所以每辆车都可以随时随地知道的自己的精准定位。

如图1所示，假设笔直的公路为一维模型。定义f_i，i∈{1，2，…，N）函数，其中N表示在一跳范围内的最大车辆数，节点i到源节点的距离用d_i表示，源节点用s表示，源节点的传输范围用R表示。当源节点S遇到紧急情况，它会广播一个紧急包给传输范围内的所有邻居节点，当所有邻居节点接收到源节点发送的数据包会开始存储并计算转发概率。这里将源节点传播的最远范围记为一跳的传播距离，在分配转发概率时，给最远的节点分配最高的转发概率。在设计多跳广播协议时，要最大化提高转发成功概率、减少单跳广播中的广播延迟和增强单跳转发的可靠性。定义RE来表示单跳转发的可靠性，p_i，i∈（1，2，…，N）表示节点的转发概率，P_S表示一跳的转发成功概率，系数用λ，λ∈（0，1）。在传播的过程中，要保证至少有一个节点能够把紧急消息传播至源节点的传播边界。因此，可以得到：

其中λ_opt表示λ的最优值。

2.2 理论分析

给出新的转发概率公式，定义为：将距离源节点最远的距离定义为d₁，N表示一跳范围内的节点总数，λ用于调整转发成功概率的系数。

2.2.1 转发成功的概率

由于传输距离足够短，假设每个节点接收到数据包的时段是相同的。当数据包传来之后，所有的节点就会共同竞争信道，此时信道的状态有三种可能的情况：空闲、成功传输或者冲突。信道处于空闲、成功传输或者冲突对应的三种情况分别是没有节点、只有一个节点或者超过一个节点在一个空时隙开始的时候请求信道发送。我们将只有一个节点在一个空时隙开始时请求信道发送，并获得信道成功发送紧急消息的概率记为P_S。当每个节点都以相同的转发概率p转发数据包时，得到公式：

定义成功转发概率的公式为：

另外，平均副本数量的定义如下：

其中P_cn表示n个节点在没有任何退避情况下转发接收到的数据包概率，当节点计算的转发概率大于随机生成的概率时，该节点就获得了转发权。

2.2.2 平均时延

在IEEE802.11（WIFI）的标准修订版本，DSRC在PHY和MAC层中将IEEE802.11p无线协议用于车载自组织网络（VANET）中，IEEE802.11p是基于分布式协调函数（DCF）的广播协议，在DCF中使用载波感知多址机制（CSMA/CA）来争夺信道。为了减少碰撞的发生，DCF采用信道感知检测信道活动和截断二进制指数退避随机化分组传输的開始时间[11].其中信道的访问延迟可以表示为：

其中：

P_bi表示信道忙时数据包占用第i个信道时的概率，Q表示最大回放级的数目，T⁰是一个随机变量，表示成功发送数据包占用的信道时间。Ts表示一个时隙，CW₀表示竞争窗口值，那么一跳的延迟时间就可以表示为：

2.3 多跳广播协议

源节点车辆遇到紧急情况时，需要尽快向车流量的相反方向节点广播紧急消息，假设整个车辆网络有效连接，传输范围内的所有车辆都可以有效地接收广播包。

（1）源节点会将数据包广播到传输范围内的所有节点，包括事件ID、GPS坐标和行驶方向，还会把紧急数据包存储到缓冲区。

（2）在广播紧急消息包后，源节点会启动倒计时（这个计数器的初始值是在网络中预先确定的），在计数器时间减为零后，如果还没有任何节点接收到原始广播数据包，源节点会重新发送存储在缓冲区的数据包，否则将删除缓冲区存储的数据包。

（3）邻居节点接收到紧急包之后，每一个节点都会通过公式（6）来计算自己的转发概率，另外，节点还会生成一个0到1之间的随机概率。如果计算出来的转发概率值大于生成的随机概率，则该节点转向转发过程。

（4）当有多个节点进入转发过程时，会发生网络冲突进入二进制指数退避，最大退避指数的数目为3。

（5）如果有且仅有一个节点成功竞争该信道，它将转发紧急消息，成为源节点的下一跳。

（6）如果在最大数量的退避指数和源节点的延迟计数器计时结束之后转发过程失败，源节点会重新发送原始紧急消息。

3 仿真验证

3.1 实验环境

本实验使用MATLAB仿真模拟器来验证基于概率的多跳广播算法的性能[12]，跟其它不同的基于概率的多跳广播方案的转发成功率作比较。实验时，车辆处在源节点传输范围均匀分布的车联网中，在单跳范围内车辆数N为10-100之间，传输范围为300米。将WPB协议和NPPB协议作为比照对象，当NPPB协议作为比较对象时选取了具有代表性的两个参数k=3和k=5.本文中给出的算法，也设定了两种情况：λ=1和λ=0.6。首先，依据公式R/（N+1）来计算车辆之间的距离，从而得到每个车辆之间的距离，再计算出每个节点的转发概率。表1中给出了部分仿真参数的设置[13]。

3.2 仿真结果分析

计算转发成功概率时，需要考虑每个节点在第一次尝试转发消息没有任何退避的情况。由于转发概率考虑了车辆密度因子，从图2可以看出，随着车辆数量的增加，转发成功的概率始终很高，而WPB、NPPB（k=3）和NPPB（k=5）的转发成功率则显著下降。λ=1的网络转发成功率高于λ=0.6的网络转发成功率。

实验也进行了平均副本数的对比。为了简化计算的复杂性，将在传输范围内的车辆数N设为10-28。如图3所示，网络的平均副本数不会随着车辆密度的增加而增加，甚至看起来会略有减少。

平均信道接入延迟的仿真结果如图4所示。由于WPB和NPPB分配的接近节点的转发概率不够小，使得节点在信道竞争过程中具有较高的繁忙概率，因此平均信道接入延迟随车辆密度的增加呈指数增长。

4 结论

通过仿真实验的模拟，给出的基于概率的多跳广播协议在不需要网络拓扑的先验知识情况下，每个节点以一定的概率转发紧急消息，不仅提高了数据包转发成功的概率、减少了平均副本数也降低了信道访问延迟。与此同时，所给出的转发概率也可以根据车辆密度自适应地进行调整，能够保证网络性能不会因为车辆密度的增加而面临急剧下降的问题，显著的改善了车载网络转发的可靠性也减少了时间延迟。

（通信作者：陈戈琦）

参考文献

[1]M.-C.Chuang，and M.C.Chen，”DEEP：Density-awareemergencymessageextens ion protocolfor VANETs，”IEEE Transactionson WirelessCommunications，12.10（2013）：4983-4993.

[2]H. Yoo and D. Kim，”ROFF：RObustand Fast Forwarding in vehicularad-hoc networks，”IEEE Transactions onMobile Computing，14.7 （2015）：1490-1502.

[3]I.Achour，T.Bejaoui，andS.Tabbane.”Network codingapproachforvehicle-to-vehiclecommunication：Principles，protocols and benefits.”Software，Telecommunications and ComputerNetworks（SoftC0M），2014 22ndInternational Conference on. IEEE，2014.

[4]L.Li，R.Ramjee，M.Buddhikot，andS.Miller，”Network codingbasedbroadcast in mobile ad-hocnetworks.”INFOCOM 2007-26thIEEE International Conference onComputer Communications.IEEE，2007，pp.1739-1747.

[5]C.Fragouli，J.Widmer，and J.-Y.L.Boudec.”Efficient broadcastingusingnetwork coding.”IEEE/ACMTransactions on Networking（TON）16.2（2008）：450-463.

[6]N.Wisitpongphan，et al，”Broadcaststorm mitigation techniquesinvehicular ad hoe networks，”IEEE Wireless Communications，14.6 （2007）：84-94.

[7]L.Zhou，et al，”NPPB：A broadcastscheme in dense VANETs，”InformationTechnology Journal，9.2（2010）：247-256.

[8]S.Panichpapiboon and G.Ferrari，”Irresponsible forwarding，”ITSTelecommunications，2008.ITST2008.8th International Conferenceon.IEEE，2008.

[9]S.Panichpapiboon”Irresponsibleforwarding under general intervehiclespacing distributions，”ElectricalEngineering/Electronics，Computer，Telecommunications and InformationTechnology（ECTI-CON），2011 8thInternational Conference on. IEEE，2011.

[10]S.Panichpapiboon and L.Cheng，”Irresponsible forwardingunderreal intervehicle spacingdistributions，”IEEE Transactionson VehicularTechnology，62.5 （2013）：2264-2272.

[11]X.Li，et al.”Multi-hop delayreduction for safety-related messagebroad-casting in vehicle-to-vehiclecommunications.”IET Communications9.3（2015）：404-411.

[12]The Network Simulator-ns-2.[Onlinel，Available：http：//www.isi.edu/nsnam/ns/.

[13]Y.Bi，ff.Shan，X.S.Shen，N.Wangand H.Zhao，"A Multi-Hop BroadcastProtocol for Emergency MessageDissemination in Urban Vehicular AdHoe Networks，"in IEEE Transactionson Intelligent TransportationSystems，Vol.17，no.3，pp.736-750，March 2016.