文献标识码: A
DOI:10.16157/j.issn.0258-7998.2016.04.028
中文引用格式: 李文娟,赵瑞玉. 基于网络编码的转发节点协作多跳广播协议[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.
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-based cooperative 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的距离因子
其中θj表示节点i与节点j的连线与水平方向上的夹角,如图1所示。
依据角度计算公式,可得θj值:
其中d表示节点j离水平线的距离。
最终,将距离因子、方向因子以及密度因子融合在一个变量,称为竞争权值CW。节点j的竞争权值CW(j):
其中α、β、γ分别为距离因子、方向因子、密度因子的权值系数,其取决于不同的环境。
源节点计算了所有邻居节点的竞争权值后,比较邻居节点的竞争相对值,并选择两个具有最大竞争权值的节点作为消息的转发节点。
2.2 编码矢量
NCFMB协议选择的编码矢量C:
由于第一轮产生的只有两个数据包,只需从编码矢量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.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.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所示。
同时选择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协议利用网络编码技术,降低了重传次数,减少了系统开销。
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协议利用网络编码技术以及转发节点间的协作,在保证较高的数据包传输成功率时,传输时延也得到极好的限制。
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-coding-based 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 coding-based 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.4th MESM,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.