基于网络编码的转发节点协作多跳广播协议

李文娟，赵瑞玉

(重庆邮电大学移通学院 通信与信息工程系，重庆 401520)

基于网络编码的转发节点协作多跳广播协议

李文娟，赵瑞玉

(重庆邮电大学移通学院 通信与信息工程系，重庆 401520)

车载网VANETs的车间通信V2V为车间紧急消息的传递提供了平台。为此，提出了基于网络编码的转发节点协作广播协议NCFMB。NCFMB协议首先利用节点的距离、方向以及局部密度信息计算节点的竞争权值，并择优选择节点作为转发节点。然后，再利用网络编码技术，在广播数据包前对数据包进行编码，进而提高数据包传输率。最后，通过仿真数据表明，提出的NCFMB协议能够有效地提高数据包传输率，并降低了端到端传输时延。与FUZZBR协议相比，数据包传输成功率提高了近10%，而时延降低了近50%。

车载网；多跳广播；网络编码；紧急消息；转发节点

0　引言

随着专用短程通信 DSRC(Dedicated Short-Range Communications)标准的成熟，车载网 VANETs(Vehicle Ad hoc Networks)成为研究的焦点。VANETs网络通过车间通信V2V(Vehicle-to-Vehicle)实现消息的传递。车辆间传递的消息分为两类：紧急消息(Emergency Message)和非紧急消息。当前方车辆发现交通事故、路面有障碍物等紧急情况，需向周围车辆发布这一情况，即紧急消息，提醒周围车辆采取必要的措施［1-3］。

由于紧急消息对时间相当敏感，必须快速、可靠地传输，否则就失去意义。目前，常采用广播机制传递紧急消息，如城市多跳广播［3］，是一个有效传递紧急消息的方案。当出现紧急情况，源节点(第一个发现该紧急情况的车辆)向邻居节点广播消息，接收节点再重播，直到所有相关的节点均收到此消息。然而，这种简单的广播策略会引起信道拥挤，导致广播风暴［4］。又由于无线信道的不稳定性，消息传输成功率低。这些问题给紧急消息的有效传输提出挑战。

由于无线信道的广播特性，网络编码技术受到广泛关注。Nguyen等［5］分析了网络编码在单跳无线网络的应用特性。随后，Li等［6］提出基于网络编码的广播协议。在多跳网络中，利用邻居节点间的协作提高网络传输性能，但是文献［5-6］并没有考虑这点。此外，文献［7］提出面向VANET的基于秩的网络编码算法，节点依据邻居节点的竞争接收状态，自适应地向网络输入数据包。文献［8］也提出随机编码方案。然而，这些基于网络编码方案并不是针对多跳广播应用，它们均没有考虑节点间的协作性。

为此，针对 VANETs多跳广播，提出基于网络编码的转发节点协作广播协议NCFMB(Network Coding-basedcooperative Forwarding Multi-hop Broadcasting protocol)。首先，源节点利用节点距离、方向以及局部密度信息，选择下一跳转发节点，然后，将要传输的数据包进行线性编码。网络编码以2个数据包为一批。因此，源节点需选择两个转发节点。通过网络编码和转发节点间的协作，提高数据包传输成功率，并降低了数据包传输时延。

1　预备知识

线性网络编码就是在数据发送前对其进行线性变换［9］。由于无线通信的广播特性，可利用网络编码技术降低数据包被传输的次数，减少系统开销。

假定发送节点有m个原始数据包（未编码），需要发送至多个接收节点。假定 X=(x1，x2，…，xm)T表示这m个原始数据包。发送节点利用Y=CX对数据包进行编码：

其中C表示编码矢量。当接收了m个或以上的线性编码数据包时，接收节点就能够恢复原始数据包。此外，可通过伽罗瓦域GF（Galois Field）选择编码矢量C。如果该域足够大，可随机选择m个独立的组合。

2　NCFMB协议

2.1转发节点的选择

为了缩短传输时延和缩短传输跳数，引用贪婪地理思想，将离发送节点的距离作为选择下一跳转发节点的指标之一。假定节点i为源节点，节点j为其邻居节点，那么节点i与节点j的距离因子：

其中 D(i，j)表示节点 i与节点 j间的距离，R表示源节点i的传输范围。从式(2)可知，数值越大，表示离源节点越远。

其中θj表示节点i与节点j的连线与水平方向上的夹角，如图1所示。

图1　θj计算示意图

依据角度计算公式，可得 θj值：

其中d表示节点j离水平线的距离。

其中ni表示节点j的邻居节点数，N为网络内总的节点数。反映了节点j周围的节点密度情况。在选择下一跳节点时，尽量从高密度区域内选择下一跳转发节点，节点密度可依据在规定时间内，接收到HELLO消息数量计算。

最终，将距离因子、方向因子以及密度因子融合在一个变量，称为竞争权值CW。节点j的竞争权值CW(j)：

其中 α、β、γ分别为距离因子、方向因子、密度因子的权值系数，其取决于不同的环境。

源节点计算了所有邻居节点的竞争权值后，比较邻居节点的竞争相对值，并选择两个具有最大竞争权值的节点作为消息的转发节点。

2.2编码矢量

NCFMB协议选择的编码矢量C：

因此，当原始数据包为 a和 b，在 GF(23)域内，所有可能的编码包：

由于第一轮产生的只有两个数据包，只需从编码矢量C中选择任何两个元素对数据包进行编码。使用这些编码矢量的优势在于：可将任何已编码的数据包转换成其他两个编码数据包。例如，从(y1，y2)可得(y3，y4)。通过邻居节点间的协作，这个优势可极大地提高数据包传输率，原因在于：每个节点只需接收任意两个编码数据包就能解码，进而获取原始数据包。此外，所有的节点共享相同的编码矢量C。

2.3编码规则

源节点首先依据2.1节的转发节点选择算法产生两个转发节点，然后将两个原始数据包a、b进行编码，得到两个编码数据包，再广播。一旦邻居节点接收这两个编码包，就可解码，得到原始包。若只成功接收了一个编码包，则广播自己所接收的数据包。

如图2所示，源节点S首先对原始数据包(a，b)进行编码，得到线性编码组合(a+a，a+2b)。然后，从邻居节点中选择两个转发节点r1和R1。假定由于信道原因，节点r1仅接收了a+b，而R1仅接收了 a+2b。在这种情况下，节点r1和R1重播自己接收的数据包，那么，节点r1和R1就能够从对方接收到一个编码数据包，最终能够解码，得到原始数据包。

图2　数据包编码转发示意图

2.4重传机制

尽管利用网络编码技术能够提高下一跳的数据包接收率，但是由于无线链路的不稳定性以及数据包碰撞等原因，仍会丢失一些数据包。为了提高数据包接收率，NCFMB协议规定：当源节点在规定的时限内没有检测到其广播的数据包被转发，就重播之前的数据包。预设的时限 T=40 ms。这不同于其他的重播机制，传统的重播算法只重播丢失的数据包，而NCFMB协议重播新的编码包。如图3所示，源节点S第一次转播了两个编码包a+b、a+2b。若编码包 a+2b丢失，源节点 S就重播新的编码包2a+3b，其不同于a+b、a+2b。假定节点r1只接收了编码包a+b，未能接收到a+2b。由于源节点S重播新的编码包2a+3b，节点r1可利用a+b和2a+3b两个编码包解码，获取原始包。因此，在重播之前，对数据包进行编码，NCFMB协议比传统的重播协议降低了传输次数，也提高了数据包接收率。

图3　重播示意图

3　系统仿真以及性能分析

3.1仿真参数

采用微观的交通仿真软件 SUMO［10］和 TraNS［11］两个仿真软件产生街道场景。在仿真过程中，车辆最大行驶速度为20 m/s。每个街道场景区域为 1 700 m×1 700 m，且由5条水平车道和5垂直车道组成。两个相邻十字路口间距为400 m。

在仿真过程中，有两个源节点，且为相邻节点，它们每秒产生15个数据包。仿真目的在于：考查两个邻居节点同时发送数据包的环境下的路由性能。每次实验独立重复100次，取平均值作为最终的实验数据。此外，本文假定距离因子与密度因子具有同等的权重系数，而方向因子的权重较小，即α、β、γ分别为0.4、0.2、0.4。具体的仿真参数如表1所示。

表1　仿真参数

同时选择 FUZZBR［12］和 Un-RE-FUZZBR协议，与NCFMB进行同步仿真，并进行性能比较。与其他协议相比，如 Weighted p-persistence［13］和 MPR broadcast［14］以及Flooding相比，FUZZBR协议具有好的性能。在 FUZZBR中，当转发节点转发的数据包在预定的时间内未被检测到，发送节点就重传此数据包，且限定了数据包被重传的上限。而Un-RE-FUZZBR协议是无重传，当数据包被丢失后，发送节点不再重传。

3.2仿真数值分析

3.2.1重传次数

图4显示了每个数据包被重传次数。从图可知，FUZZBR协议的重传次数随着源节点数的增加而增加，原因在于：源节点增加，信道中传输的数据包也随之增加，加大了数据包碰撞的概率，使得多个数据包被重传。而Un-RE-FUZZBR协议和NCFMB协议具有较低的重传次数。Un-RE-FUZZBR协议没有重传机制，即使数据包丢失了，也不进行重传，即以数据包丢失率换取低的重传次数。而提出的NCFMB协议利用网络编码技术，降低了重传次数，减少了系统开销。

图4　重传次数

3.2.2数据包传输成功率

图5显示了3个算法的数据包传输成功率。从图5可知，提出的NCFMB协议具有高的传输成功率，远高于FUZZBR协议。这主要是因为NCFMB协议的重传次数远低于FUZZBR协议，极大地降低了数据包被碰撞的概率。而Un-RE-FUZZBR协议的数据包传输率最低。原因在于它没有重传机制，即使数据包丢失也不重传。结合图4和图5可知，NCFMB协议与 Un-RE-FUZZBR协议的重传次数相近，但是传输成功率相差甚大，进一步网络编码能够有效地提高传输成功率。

3.2.3端到端传输时延

3个协议的端到端传输时延如图6所示。从图可知，随着源节点数的增加，3个协议的传输时延也随之增加，这主要是因为源节点数增加，意味着有更多的数据包需要传输，这必然加大了数据包碰撞的概率，从而提高了传输时延。正如预料，FUZZBR协议的传输时延最高，它只采用了简单的重传机制，一旦数据包丢失就重传，肯定加大了传输时延。而Un-RE-FUZZBR协议的传输时延最低，但是它的数据包传输成功也是最低了。提出的NCFMB协议利用网络编码技术以及转发节点间的协作，在保证较高的数据包传输成功率时，传输时延也得到极好的限制。

图5　数据包传输成功率

图6　端到端传输时延

4　总结

本文针对车载网的多跳广播协议的数据包传输率低的问题，提出基于网络编码的转发节点协作的多跳广播NCFMB协议。NCFMB协议充分利用网络编码特性，提高降低数据包重传次数。首先，依据节点的距离、移动方向以及局部密度信息，选择转发节点。然后，再利用线性编码，将需转发的数据进行编码。仿真数据验证表明，提出的NCFMB协议能够有效地降低传输时延，提高了数据包传输成功率。

［1］KENNEY J B.Dedicated short-range communications(DSRC) standards in the United States［J］.Proceedings of the IEEE，2011，99(7)：1162-1182.

［2］RAZVAN C，HAMZA A，HUANG F.Fast and reliable broadcasting in VANETs using SNR with ACK decoupling［C］.IEEE ICC 2014-Ad-hoc and Sensor Networking Symposium，2014：574-579.

［3］KESTING A，TREIBER M，HELBING D.Connectivity statistics of storeand-forward intervehicle communication［J］.IEEE Trans.Intell.Transp.Syst.，2010，11(1)：172-181.

［4］WU C，SATOSHI O.Joint fuzzy relays and network-codingbased forwarding for multihop broadcasting in VANETs［J］.IEEE Transactions on Intelligent Transportations Systems，2015，16(3)：1415-1428.

［5］NGUYEN D，TRAN T，NGUYEN T，et al.Wireless broadcast using network coding［J］.IEEE Trans.Veh.Technol.，2009，58 (2)：914-925.

［6］LI L，RAMJEE R，BUDDHIKOT M，et al.Network codingbased broadcast in mobile ad hoc networks［C］.in Proc.IEEE INFOCOM，2014：1739-1747.

［7］YU T X，YI C W，TSAO S L.Rank-based network coding for content distribution in vehicular networks［J］.IEEE Wireless Commun.Lett.，2012，1(4)：368-371.

［8］LEE U，PARK J S，YEH J，et al.VANETCODE：Network coding to enhance cooperative downloading in vehicular ad-hoc networks［C］.in Proc.IWCMC，2006：1-5.

［9］LI S，YEUNG R，CAI N.Linear network coding［J］.IEEE Trans.Inf.Theory，2013，49(2)：371-381.

［10］KRAJZEWICZ D，HERTKORN G，ROSSEL C，et al.SUMO (Simulation of Urban MObility)：An open-source traffic simulation［C］.In Proc.4thMESM，2012：183-187.

［11］TraNS(Traffic and Network Simulation Environment)，Accessed on Oct.15，2012.［Online］.Available：http://trans.epfl.ch/.

［12］WU C，OHZAHATA S，KATO T.VANET broadcast protocol based on fuzzy logic and lightweight retransmission mechanism［J］.IEICE Trans.Commun.，2012(2)：415-425.

［13］WISITPONGPHAN N，TONGUZ K O.Broadcast storm mitigation techniques in vehicular ad hoc networks［J］.IEEE Wireless Commun.，2007，14(6)：84-94.

［14］WU C，KUMEKAWA K，KATO T.A novel multi-hop broadcast protocol for vehicular safety applications［J］.J.Inf.Process.，2010(18)：110-124.

Network coding-based cooperative forwarding multi-hop broadcasting protocol in VANETs

Li Wenjuan，Zhao Ruiyu
(Department of Telecommunications and Information Engineering，College of Mobile Telecommunications Chongqing University of Posts and Telecom，Chongqing 401520，China)

In Vehicle Ad hoc Networks(VANETs)，Vehicle-to-Vehicle(V2V)communication is able to transmit emergency message.Therefore，NCFMB protocol is proposed in this paper.In NCFMB,firstly,the distance between nodes,direction and local density are used to compute the contention weight of nodes.The node with max contention weight is considered to be forwarding node.Secondly,the data is encoded before broadcasting the data in order to improve the data transmission ratio.Finally,the simulation results show thatproposed NCFMB protocol performs 10%better than FUZZBR protocol in terms of data transmission ratio,and about 50%in term of end-to-end delay.

VANETs；multi-hop broadcast；network coding；emergency message；forwarding node

TN926

A

10.16157/j.issn.0258-7998.2016.04.028

2015-12-17)

李文娟（1983－），女，硕士，讲师，主要研究方向：移动通信、通信技术。

赵瑞玉（1979－)，女，硕士，讲师，主要研究方向：信号与系统。

中文引用格式：李文娟，赵瑞玉.基于网络编码的转发节点协作多跳广播协议［J］.电子技术应用，2016，42(4)：99-102.

英文引用格式：Li Wenjuan，Zhao Ruiyu.Network coding-based cooperative forwarding multi-hop broadcasting protocol in VANETs［J］.Application of Electronic Technique，2016，42(4)：99-102.