基于单播和无比率编码的地域性多播路由协议

从继成，张韧志

(黄淮学院 a.动画学院;b.信息工程学院，河南 驻马店463000)

作为智能交通系统的最有前景应用技术之一，车联网VANETs(Vehicular Ad Hoc Networks)的相关技术成为研究焦点［1－2］。VANETs 提供了车间通信和车与基础设施的通信平台，便捷了车间信息的交互。行驶中的车辆通过相互共享实时的交通信息，提高行驶安全。车辆是VANETs 网络的重要组成部分，然而车辆的快速移动导致VANETs 网络拓扑动态变化，给数据传输提出了挑战。据此，VANETs 的路由技术成为研究热点。依据数据包的目的节点数的不同，可将VANETs 路由协议分为单播路由(Unicast Routing)、广播路由以及多播路由［3］，其中地域性多播路由GR(Geocast Routing)是属于多播路由的一个子类。在单播路由协议中，数据包的目的节点仅一个。而地域性多播路由中数据包的目的节点数是多个，将多个目的节点所在的位置称为目标区域。换而言之，目标区域由多个车辆构成，而非某单一车辆。当前方车辆发现事故，需将这一紧急消息传递后方车辆，那么后方所有车辆均是紧急消息传输的目标。这些车辆所在位置便构成了消息传输的目标区域。

IVG(Inter Vehicle Geocast)［4］属于典型的GR 协议，依据车辆的行驶方向和位置设定目标区域。IVG 协议利用泛洪机制向目标区域转发数据包，并采用传输时延防止数据包重传。若在给定的时间间隔内，某一节点收到一个数据包的复本，表明此数据包已被其他节点转发了，因此该节点就不再重转。通过这种防止重传数据包的机制，减少数据传输开销。然而利用泛洪转发数据包，仍大大增加了系统开销。

此外，文献［5］提出了分布式鲁棒多播DRG(Distributed Robust Geocast)协议。它利用快速、可靠方式转发消息，减少了传输的控制包数量，进而降低了网络开销。然而，DRG 路由仍采用了泛洪机制，无法避免因泛洪而引起的开销，特别是在密集的城市环境。

文献［6］提出了基于空间信息的GR 路由。该路由采用了存储－转发，并利用车辆的历史轨迹构建移动模型。尽管降低了路由开销，但是实时获取车辆的轨迹是非常复杂的，特别是在车辆高速移动的环境下，这降低了数据包传输速率。

传统的GR 路由常引用泛洪机制，这极大地增加了开销，特别是当源节点与目标区域相距较远时，泛洪机制会极大增加传输开销。这些开销降低了系统的吞吐量。此外，车辆的高速移动，对数据包传输率提出了挑战。

为此，本文基于单播和无比率编码的地域性多播路由URC－GR(Unicast and Rateless Coding based Geocast Routing)协议。URC－GR 协议仍属GR 协议，但是在向目标区域转发数据包时不再使用泛洪机制，而是利用AODV 协议的单播机制，降低路由开销。同时，为了解决低的数据包传递率，引用了无比率编码。当源节点向目标区域传输数据时，就对这些数据进行无比率编码，增加了对不稳定路由的鲁棒性，提高数据包传输率。

1 约束条件

提出URC－GR 协议主要基于以下假设条件:

1)所有车辆均有全球定位系统GPS(Global Positioning System)，车辆知道自己的位置。同时，每个车辆周期性向邻居车辆广播beacon 消息;

2)对于无比率编码，假定产生已编码数据包的数据块足够大，致使产生完全相同的编码数据包的概率非常小;

3)在目的区域，至少有一个车辆接收消息;

4)由于消息在目标区域广播，如果目标区域内有一条消息被接收，那么区域内所有车辆均能接收此消息;

5)车间通信采用DSRC(Dedicated Short Range Communication)标准。

2 URC－GR 协议

在VANET 的地域性多播路由GR 协议中，路由开销和数据包传递率是两个非常重要的参数，特别是当目标区域远离源节点时，保持低开销和高数据包传递率是非常具有挑战性的工作。为此，提出的URC－GR 协议从两个方面解决了问题。引用单播的AODV 的路由发现机制，降低开销，再利用无比率编码提高数据包传递率。

2.1 消息转发

为了减少开销，提出的URC－GR 协议利用AODV 路由发现机制，实施向目标区域的单播传输。当源节点需要向目标区域传输一个数据包时，首先利用AODV 路由协议产生一个路由请求RREQ(Route Request)包，并在网络内泛洪。RREQ包含有源节点地址、数据包ID 以及目标区域以及转发了RREQ 数据包的节点，如图1 所示，其中List_Forward 表示转发RREQ 包节点ID。

图1 RREQ 消息格式

邻居节节点接收了RREQ 包后，首先检测是否是第一次接收RREQ 包，若是，则自己的ID 号加入List_Forward，否则丢弃RREQ 包。

经过多个节点转发，RREQ 包能够传递至目标区域。当目标区域内有节点接收了RREQ 包，就沿着传输RREQ 的路径向源节点传递路由回复RREP(Route Reply)包。如图2 所示。

图2 数据传输路径的选择

如图2a 所示，源节点先在传输范围内广播RREQ 包，邻居节点接收后，再转发，直至目标区域。一旦目标区域内有节点接收了RREQ 包，就沿着传输RREQ 包的路径回复RREP，如图2b 所示。采用单播机制向源节点传输RREP。一旦接收了RREP，源节点就沿着传递RREP 路径发送数据包，如图2c 所示。利用这种方式传输数据，一旦目标区域内的某一节点接收了数据包，就在目标区内泛洪，从而保证目标区域内所有节点均能接收到数据包。利用这种方式，可降低路由开销。

2.2 无比率编码

在VANET 中，车辆的快速移动，导致拓扑动态变化，降低了数据包传递率。为此，提出的URC－GR 协议利用无比率编码提高数据包传递率。在容错编码中，无比率编码因易编码、解码的特性，被广泛应用于具有不可预知信道特性的网络。

无比率编码是一种特殊信道冗余编码，其编码规则为:将原始数据转换成无限多个不重复编码的数据单元［7］。无比率编码特性在于:不论接收节点何时开始接收编码数据单元，其收到的每个数据包都是有用的，并且无需考虑接收数据单元的顺序。此外，无比率编码不易受网络带宽条件的限制而导致部分数据包丢失情况的影响［8］。简之，无比率编码具有如下特性:1)源节点无需掌握信道先验知识;2)接收节点可以在任何时刻接收，无需考虑所接收的编码数据单元的顺序，只要所收集的编码数据单元数量足够重构原始信息就行。

无比率编码原理如图3 所示。假定源节点有一消息数据F 待传输。首先将其划分成n 个相等尺寸的消息块(Blocks)B1，B2，…，Bn。然后，对消息块进行按位异或运算，产生相应的编码数据单元。例如，编码数据单元e2由B1和B2进行异或运算得到，则e2=B1⊕B2，编码数据单元e2的度数为2。度数表示参与异或运算的消息块数量。经过编码后，原消息数据F 就由一系列的编码数据单元构成。这些编码数据单元经有损信道传输至接收端。接收端接收了这些数据单元后，经反复迭代运算恢复消息数据。

图3 无比率编码数据原理

无比率编码的效率η 满足

其中，ε 取决于具体纠错编码。

当接收端接收了K 个编码数据单元，若满足式(2)便可解码。

目前流行的无比率编码有Tornado［8］、LT 编码等［9］。本文引用LT 编码。源节点首先将原始数据分成n 个同尺寸的数据块D1，D2，…，Dn。然后编码器再按预设的“度数分布”函数为每个编码数据EDi随机地产生度数di。当明确了度数后，便等概率地从n 个数据块中随机地选择di个数据块进行按位求和运算，便可得到第i 个编码数据单元。LT 编码原理如图4 所示。

图4 LT 编码示意图

2.3 数据传输流程

本小节的数据传输流程是从接收了编码数据的车辆i 的角度分析。当车辆i 接收了编码数据后，首先检测是否在目标区域内，如果是，则存储编码数据。否则就沿着单播路径转发。然后再检测存储的编码数据是否满足式(2)。若满足，则解码，并向源节点回复ACK 确认消息，同时将解码后的数据在目标区域内广播，致使目标区域内的车辆均能收到消息。若不满足，则广播编码数据包，流程图如图5 所示。

图5 数据包传输流程

3 仿真分析

3.1 仿真环境及性能指标

利用SUMO(Simulation of Urban Mobility)［10］模拟车辆移动，SUMO 的输出就是车辆的移动轨迹，然后将SUMO 的输出作为NS2 的输入，进而利用NS2 仿真网络性能。表1 列举了仿真参数，仿真区域面积为2.05 km×1.4 km，由4 条垂直、2条水平方向的双向车道构成。在每个交叉口设有交通灯。

同时，选择IVG 和DRG 协议进行同步仿真，并从数据包传递率PDR(Packet Delivery Ratio)、路开销、平均端到端传输时延E2E(Average End to End Delay)3 方面分析协议性能。

表1 仿真参数

3.2 实验一

本次实验考察数据包传输速率对各性能指标的影响。数据包传输速率从32 ～512 kbit/s 变化，大小为1 500 byte。

3 个协议的PDR 变化曲线如图6 所示。从图6 可知，提出的URC－GR 协议的PDR 性能最优，分别比IVG 提高了近10%、比DRG 提高了15%。此外，URC－GR 协议随数据包传输速率变化的波动性小，具有稳定的数据包传递率。URCGR 协议的这些优势归功于引用了无比率编码，提高了数据传输效率。

图6 数据包传递率(实验一)

图7 分析了3 个协议的端到端传输时延。从图7 可知，URC－GR 协议的端到端传输时延最低，原因在于URC－GR 协议在向目标区域转发消息时，并非采用泛洪机制，降低因泛洪而引起的广播风暴的发生概率，提高了数据传输的流畅性。

3.3 实验二

本次实验考查了数据包的大小对路由协议的性能影响。数据包大小在500 ～3 000 变化，而数据传输速率为128 kbit/s。

图8 描述了数据包传递率随数据包尺寸的变化曲线。从图8 可知，URC－GR 协议的数据包传递率性能最高，并且随数据包尺寸的变化波动小。而IVG 和DRG 协议的数据包传递率随数据包尺寸的增加而下降，这主要因为大的数据包是分散传输，任一分组数据包的传输失效，都可能导致整个数据包传输的失败。而IVG 和DRG 协议并没有数据进行容错编码。

图7 平均端到端传输时延(实验一)

图8 数据包传递率(实验二)

最后，分析了IVG 和DRG 以及URC－GR 协议由端到端传输时延，如图9 所示。从图9 可知，URC－GR 协议的端到端传输时延并不随数据包尺寸变化的影响，在整个数据包尺寸变化区间，时延均在0.001 s 邻近。与IVG 和DRG 协议相比，URC－GR 协议的端到端传输时延性能分别提高了近在3倍、1 倍。

图9 平均端到端传输时延(实验二)

3.4 实验三

本次实验主要考查URC－GR 协议在路由开销方面的性能。在仿真区域内，车辆数目在25 ～100 变化，数据包大小为800 byte，而数据传输速率为128 kbit/s。仿真结果如图10所示。

图10 路由开销

从图10 可知，URC－GR 协议开销最少，远低于IVG 和DRG。原因在于URC－GR 协议在向目标区域转发数据包时，没有采用泛洪，而是利用单播机制。同时，URC－GR 协议引用无比率编码，降低了数据包重传概率，减少了控制包的重传次数，进而降低了开销。

4 结论

针对车联网VANETs 的地域性多播路由协议，展开分析，讨述了传统地域性多播路由在路由开销及数据包传递率的不足，并提出了URC－GR 协议。URC－GR 协议引用了两个机制解决高的路由开销以及低的数据包传递率的不足。首先利用单播机制向目标区域转发数据，避免了应泛洪机制而导致额外的路由开销，其次，利用无比率编码机制，增加了协议对不稳定链路的鲁棒性，提高了数据包传递率。仿真结果表明，提出的URC－GR 协议能够有效地降低路由开销，并提高了数据包传递率。

［1］THILAGAVATHE V，DURAISWAMY K.Prediction based reliability estimation in MANETs with Weibull nodes［J］.Eur.J.Sci.Res.，2011，64(2):325－329.

［2］SONG C，ZHANG W，ZHANG Y M.Analysis of access and connectivity probabilities in vehicular relay networks［J］.IEEE Trans. Information Forensics and Security，2011，29(1):140－150.

［3］于海宁，张宏莉.VANETs 路由协议的研究进展［J］.电子学报，2011，39(12):2868－2880.

［4］BACHIR A，BENSLIMANE A. A multicast protocol in ad hoc networks inter－vehicle geocast［C］//Proc.IEEE Vehicular Technology Conference.［S.l.］:IEEE Press，2013:2456－2460.

［5］JOSHI H P.Distributed robust geocast:a multicast protocol for intervehicle communication［J］.IEEE Trans. Information Forensics and Security，2014，29(1):140－150.

［6］赵鑫.P2PI 流媒体内容分发的关键技术研究［D］.北京:北京邮电大学，2010.

［7］叶晖.机会网络数据分发关键技术研究［D］.长沙:中南大学，2010.

［8］JUNG Y H，LI Q C.Short dynamic group signature scheme supporting controllable link ability［J］.IEEE Trans. Information Forensics and Security，2013，32(6):1－14.

［9］STAMPOULIS A，CHAI Z. Survey of security in vehicular networks［J］.Project CPSC 534，2011，2(3):12－20.

［10］KRAJZEWICZ D，ERDMANN J，BEHRISCH M. Recent development and applications of SUMO－simulation of urban mobility［J］.International Journal on Advances in Systems and Measurements，2013，3(5):128－138.