BDNC:基于网络编码的车载网商业消息传输协议*

2016-12-01 03:57赵志刚万荣泽
电子技术应用 2016年8期
关键词:队列解码时延

黄 欣,赵志刚,万荣泽

(1.广西农业职业技术学院 网络信息中心,广西 南宁 530007;2.广西大学 计算机与电子信息学院,广西 南宁 530004)

BDNC:基于网络编码的车载网商业消息传输协议*

黄欣1,赵志刚2,万荣泽1

(1.广西农业职业技术学院 网络信息中心,广西 南宁 530007;2.广西大学 计算机与电子信息学院,广西 南宁 530004)

通常采用网络编码技术提高VANETs中商业应用的带宽利用率。然而,网络编码会引入额外的消息传输时延,这就存在带宽利用率和消息传输时延的权衡问题。为此,针对车载商业应用中的消息传输,提出了面向带宽和基于网络编码时延的消息传输协议(BDNC)。当两个源节点同时向同一区域广播消息时,转发节点(Relay)就利用网络编码技术降低重播次数和带宽消耗。当转发节点接收到消息时,它有两个选择:等待编码机会,节省带宽;或直接转发消息,降低时延。BDNC采用了两个不同的时延控制策略:缓冲区域控制(BSC)策略和时间控制(TCS)策略,以降低传输消息每一跳的时延和提高带宽利用率。仿真结果表明,两个策略较好地控制时延,且带宽利用率提高了38%。

车载网;网络编码;商业应用;时延;带宽利用率

0 引言

车载网 VANETs(Vehicle Ad hoc Networks)被认为是实现智能交通最有前景的技术之一[1-3]。在 VANETs中,道路上的车辆组成分布式网络,车辆与车辆进行通信,并交互信息,为此,VANETs在各类应用中得到广泛使用,包括辅助驾驶类、信息共享类以及商务娱乐类。然而,部署车联网VANET的根本目的在于提高交通应用,但随着无线技术的发展,VANET在辅助驾驶、信息共享和商务方面广泛应用,包括广告、促销等通知类消息以及天气预报等[1]。

商业应用与安全应用的最主要区别在于它们对于消息响应时间的要求。显然,安全应用有很苛刻的时间要求,而商业应用对时间要求相对宽裕[2-3]。但是,商业应用需要更宽的带宽。

例如,酒店和加油站两个商家都向道路行驶人员传输各自商业信息。酒店分为促销信息,而加油站宣称营业时间以及实时优惠油价。这两个商家服务的对象均是道路上的行驶者,即它们有共同的兴趣区域。在这种情况下,提高带宽利用率、减少网络堵塞以及降低数据包被重播的次数成为需要解决的问题。

网络编码是提高带宽利用率的有效技术之一[4]。网络编码允许转发节点对数据进行简单的操作,进而降低重转的数据包数。网络编码技术受到广泛关注。NGUYEN D等[5]分析了网络编码在单跳无线网络的应用特性。随后,LI L等[6]提出基于网络编码的广播协议。在多跳网络中,利用邻居节点间的协作提高网络传输性能,但是文献[5-6]并没有考虑这点。此外,文献[7]提出面向VANET的基于秩的网络编码算法。节点依据邻居节点的竞争接收状态,自适应地向网络输入数据包。而文献[8]也提出随机编码方案。然而,这些基于网络编码方案并不是针对多跳广播应用,它们均没有考虑节点间的协作性。

为了提高带宽利用率,在消息转发前对其进行网络编码。然而,网络编码会额外增加消息传输时延。这就存在带宽利用率和传输时延的权衡问题。即当转发节点接收了一条消息后,它面临一个主要问题:是直接转发消息,降低时延,还是等待接收到其他消息,然后进行编码,提高带宽利用率。为此,本文以VANETs的商业消息传输为研究对象,考虑两个商家具有多跳共同的兴趣区域,它们均分道路车辆分发消息,为了提高带宽利率和降低传输时延,提出面向带宽和基于网络编码时延的消息传输协议(Bandwidth and Delay-Network Coding,BDNC)。

1 系统模型及问题描述

以图1为研究场景,两个商家分别位于道路两侧,它们服务对象是由一跳或多跳长的道路区域构成,均在这两个商家信号覆盖区域内[9]。

图1 VANETs的商用场景模型

考虑两个源节点(RSU1、RSU2)代表两个商家,并且假定RSU1的传输速率快于RSU2。每个转发节点有缓存区域,能够储存消息。若来自两个商家的消息包被同一个转发节点转发,那在转发前,采用网络编码,提高带宽利用率。然而,在网络内使用网络编码技术具有随机性和交通流量的不对称性。由于消息到达时间的随机性,来自不同商家的消息不可能同时到达转发节点。因此,转发节点接收了一个消息后有两种处理方式:(1)若需要编码,它需要等待一段时间,直到接收到另一条消息;(2)不进行编码,直接转发消息,降低了时延。显然,若采用第一种方式,等待时间增加了消息传输时延,多数应用是难以接受的。

当转发节点从快的源节点(RSU1)接收了消息 Mes,则查询缓存区域。如果区域不是空的,那么将刚接收的消息Mes与缓存域单元内的第一个消息 Mes进行编码。反之,若缓存区域是空的,则立即转发消息Mes。

然而,如果是从慢的源节点(RSU2)接收了消息Mes,那么转发节点可等待机会进行编码或立即转发消息Mes。

为此,提出BDNC协议,并考虑两种策略降低因网络编码所增加的额外时延,即缓冲区域控制(Buffer Size Control,BSC)和时间控制(Time Control,TC)两种策略。BSC策略是通过控制缓冲区域大小降低因编码所带来的额外时延,而TC策略是通过设定定时器来控制时延。

2 BDNC协议

2.1编码规则

采用简单的基于或操作网络编码规则,如图2所示。节点X需要向节点Z转发消息包P0,而节点Z正在向节点X转发消息包P1。那么,节点Y需要向节点X和Z转发消息。传统路由中,节点Y分别向节点X、Z转发数据包。若使用网络编码,节点Y将需要转发的消息包P0、P1进行或操作,然后向X、Z转发。X、Z节点接收被编码后的消息包后,进行或操作,就能恢复原来的消息包。通过简单的网络编码,带宽利用率提高了50%。

图2 网络编码示例

2.2BSC策略

BSC策略目的在于通过控制缓存区大小,降低时延。通常,队列内消息数越多,每条消息的时延就长[10]。为此,在BSC策略中,转发节点依据队列内消息的条数决定是否储存消息。换而言之,储存的概率p与当时队列的大小成正比。

其中ω表示队列的大小。

然而,这样简单的操作会导致最新到达的消息被立即转发,而之前的消息仍在队列内等待编码机会。这就颠倒了消息次序,加大了队列内的消息时延。因此,转发节点以概率p对新接收的消息编入队列,而以概率1-p释放队列内的第一条消息。

2.3TC策略

尽管商业应用对消息的传输没有严厉的时间要求,但长的传输时延也是难以接受的[11]。因此,从时延角度选择TC策略。转发节点将来自慢速率源节点的消息缓存于队列中,且保留于队列中的时间不超过 Tmax。当转发节点从源节点接收了一条消息,直接缓存于队列,并设置一个定时器,定时时长为 Tmax。在定时器计时完毕后,若该条消息仍在队列中,则立即转发消息,且不进行编码。

2.4消息传输流程

提出的BDNC协议流程如图3所示,当一旦接收了新的消息,就判断是否来自快节点,若是就进一步判断缓存区域是否为空,若是就直接转发,否则就与区域内第一条消息进行或编码,再转发已编码的消息。如果是来自慢节点,有两种选择,一种是采用BSC策略,另一种是TC策略。

图3 BDNC协议消息传输流程图

3 性能分析

3.1仿真场景

考虑图1所示的仿真场景,利用NS3进行模拟仿真,仿真参数如表1所示。两个源节点随机地产生消息,且产生消息的间隔服从泊松分布,即利用泊松分布计算两条相邻消息之间的间隔[12-13]。在仿真过程中,假定λ2=1 packet/sec,而 λ1是变化的。而车辆的速度从 36~ 54 km/h变化。在仿真初期,250辆车随机分布于长为4 km的双向车道,20 s后,两个源节点开始发送消息包。

表1 仿真参数

在仿真过程中,分析两个不同策略的平均每跳时延、消息传输成功率以及未编码消息数。其中,未编码消息条数表示在所接收的已编码消息中因各种原因,不能解码的消息数。

两个策略目的在于提高带宽利用率,并控制因编码所导致的时延。因此,选择每跳时延、带宽节省率、消息传输成功率和未解码的消息条数作为评估协议的性能指标。其中,每跳时延表示消息在传输过程中每跳的平均时延;消息传输成功率表示消息被成功传输的几率,数值等于节点所收到的消息条数与两个源节点所广播的消息数之比;而未解码的消息数表示节点收到已编码消息后而不能解码的消息条数。

为了更好地分析BSC、TC策略性能,选择一个参照策略进行对比分析,其中参照策略是指:转发节点对所有消息均进行编码再转发,不考虑两个源节点的传输速度率,也不控制编码时延[10]。在仿真中,将参照方案记为纯网络编码(Pure Network Code,PNC)。

此外,在仿真过程中,同时考虑两种场景:静态的源节点和动态移动的源节点,在下列仿真图中标记为Staionary和 Mobile。将基于 BSC策略、TC策略的 BDNC协议分别记为BDNC-BSC、BDNC-TC。

图4 BDNC-TC的带宽节省率随Tmax的变化曲线

3.2Tmax参数

为了确认TC策略的Tmax参数,评估了它对吞吐量的影响,如图4所示。从图可知,随着Tmax的增加,带宽节省率也随之增加,这有利于更合适地设置 Tmax。当Tmax=0.3时,带宽节省率增加缓慢,为此,在下面仿真中,设定Tmax=0.3。

3.3数值分析

3.3.1时延

图5显示了由源节点RSU2发送的消息每跳的平均传输时延,其中图5(a)表示静态的源节点场景,而图5(b)表示动态的源节点场景。从图中可知,在λ1=1 packet/s时,PNC策略会导致大的时延,而BSC和TC策略有效地控制了时延。随着λ1的增加,BSC和PNC时延下降。当时,BSC和 PNC策略的时延分别为 1 s、2 s。而当时,这两个策略的时延约为0.75 s。原因在于λ1是反映队列的释放数据概率,随着 λ1的增加,队列的平均时延就下降。此外,TC策略的时延最低,若从时延角度,TC策略是不错的选择,TC策略的时延维持在0.3 s,与 Tmax持平。

图5 基于3种不同策略的BDNC协议每跳传输时延

当转发节点移动时,转发节点动态的特性影响了网络的稳定性。从图5(b)可知,PNC方案的时延波严重,但是BSCS方案和TCS方案时延均低于PNC。这也进一步说明,BSCS和 TCS方案能够有效地控制因编码所带来的时延。

3.3.2带宽节省率

3.3.3消息传输成功率

图7描述了平均消息传输成功率随λ1变化曲线。图7比较了静态转发节点和动态转发节点两种情况下的平均消息传输成功率,从图中可知,静态转发节点有利于数据转发,平均数据包传递率明显高于动态转发节点环境。此外,在动态转发节点环境下,当 λ1<1.5时,PNC的消息传输成功率最低,并且随着λ1的增加,消息传输成功率慢慢上升,且略优于BSC策略。

图6 基于3种不同策略的BDNC协议带宽节省率

图7 基于3种不同策略的BDNC协议的消息传输成功率

图8 未编码的消息数

3.3.4未解码的消息数

最后,分析了未解码的消息条数。图8描述了平均每个车辆不能解码的消息条数。未解码的数据包是指:车辆收到编码的消息,但是由于没有其他消息,无法解码。这种情况多数由于车辆的移动所引起的。从图8可知,TCS方案的未编码消息条数最少。随着 λ1的增加,未编码消息条数下降,这主要因为λ1的增大,消息就不用在队列中等待过长的时间,相应地,就降低了已编码消息不能被解码的概率。

4 总结

针对车联网的商业应用,其有两个源节点向同一个兴趣区域传输数据。为了提高网络带宽利用率,采用网络编码技术。为了降低因网络编码所增加的额外时延,提出BSC和TC策略。BSC策略从控制缓存区域大小角度控制时延,而TC策略采用定时器原则。仿真结果表明,网络编码技术可以有效地提高带宽利用率,带宽节省率高达38%;而TC策略更能有效地控制时延,在时延控制方面优于BSC策略。

[1]HARRI J,FIORE M,FILALI F,et al.Vehicular mobility simulation with VanetMobiSim[J].Simulation,2011,87(4):275-300.

[2]JARUPAN B,EKICI E.PROMPT:A cross-layer positionbased communication protocol for delay-aware vehicular access networks[J].Ad Hoc Networks,2010,8(5):489-505.

[3]LA R,SEO E.Expected routing overhead for location service in MANETs under flat geographic routing[J].IEEE Trans. Mobile Comput.,2011,10(3):434-448.

[4]熊飚,张小桥.VANET网络中小尺度衰落信道仿真[J].通信技术,2010,43(12):56-57.

[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 adhoc networks[C].in Proc.IWCMC,2006:1-5.

[9]CHEN J W.A vote-based position verification method in VANET[J].Communications technology,2012,11(54):50-55.

[10]HAMATO S,ARIFFIN S,FISAL N.Contention free time efficient broadcasting protocol for safety applications in VANETs[J].International Review on Computers and Software,2014,9(11):1923-1931.

[11]AHMED S A M,ARIFFIN S H S,FISAL N.Survey on broadcasting in VANET[J].Research Journal of Applied Sciences,Engineering and Technology,2014,7(18):23-32.

[12]LI M,YANG Z,LOU W.Code on:cooperative popular content distribution for vehicular networks using symbol level network coding[J].IEEE Journal.Sel.A.Commun.,2011,29(1):223-235.

[13]ZHOU L,CHAO H C,VASILAKOS A V,et al.Joint forensics-scheduling strategy for delay-sensitive multimedia applications over heterogeneous networks[J].IEEE Journal. Selected Areas in Communications,2011,29(7):1358-1367.

BDNC:Network coding-based message transmission protocol in VANETs business application

Huang Xin1,Zhao Zhigang2,Wan Rongze1
(1.Network Information Center,Guangxi Agriculture Vocational and Technical College,Nanning 530007,China;2.College of Computer and Electronics Information,Guangxi University,Nanning 530004,China)

Network coding is an emerging technique known to improve the bandwidth utilization for non-safety applications in VANETs. However,the delay of message transmission is increased by network coding,and it results in tradeoff problem between bandwidth and delay.Therefore,for message transmission in VANETs business application,the Bandwidth and delay-Network coding-based message transmission protocol is proposed in this paper,which is marked as BDNC.When there are two sources broadcasting the data into the same area at the same time,the relay will use the network coding technique to decrease the number of rebroadcasting events and the consumption of the bandwidth.However,a fundamental problem for the relay when it receives a packet,is whether to wait for a coding opportunity and save the bandwidth or send the packet directly and reduce the delay.In order to address such tradeoff,two versions of the protocol named buffer size control(BSC)and time control(TC)are introduced to control the delay that is experienced by the packet at each hop,while achieving better bandwidth utilization.Up to 38%improvement in the bandwidth utilization has been recorded,and both schemes have shown a considerable amount of control on the imposed delay.

VANETs;network coding;business application;delay;bandwidth utilization

TN915;TP393

A

10.16157/j.issn.0258-7998.2016.08.031

国家自然科学基金资助项目(61363067);2013年广西高校科研项目(2013LX194);广西 2016年度中青年教师基础能力提升项目(KY2016YB684)

2016-03-01)

黄欣(1983-),男,硕士,讲师,主要研究方向:计算机网络安全。

赵志刚(1973-),通信作者,男,博士,教授,硕导,主要研究方向:计算机应用技术,E-mail:zzgmail2002@163.com。

万荣泽(1974-),男,硕士,教授,主要研究方向:计算机技术及应用。

中文引用格式:黄欣,赵志刚,万荣泽.BDNC:基于网络编码的车载网商业消息传输协议[J].电子技术应用,2016,42 (8):125-129.

英文引用格式:Huang Xin,Zhao Zhigang,Wan Rongze.BDNC:Network coding-based message transmission protocol in VANETs business application[J].Application of Electronic Technique,2016,42(8):125-129.

猜你喜欢
队列解码时延
《解码万吨站》
队列里的小秘密
基于多队列切换的SDN拥塞控制*
解码eUCP2.0
基于GCC-nearest时延估计的室内声源定位
NAD C368解码/放大器一体机
Quad(国都)Vena解码/放大器一体机
在队列里
基于改进二次相关算法的TDOA时延估计
丰田加速驶入自动驾驶队列