车辆贪婪bt

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2016,27(2):432450[doi:10.
13328/j.
cnki.
jos.
004839]http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel:+86-10-62562563车载自组织网络中基于停车骨干网络的数据传输朱金奇1,2,马春梅2,刘明2,陈贵海3,龚海刚2,刘斌21(天津师范大学计算机与信息工程学院,天津300387)2(电子科技大学计算机科学与工程学院,四川成都611731)3(上海交通大学电子信息与电气工程学院,上海200240)通讯作者:朱金奇,E-mail:jingpei719@163.
com摘要:车载自组织网络(vehicularadhocnetworks,简称VANETs)具有网络间歇连通、节点高速移动及动态的网络拓扑结构等特性,如何有效地实现车辆间的数据传输,成为VANETs的重大挑战.
现有研究工作基于历史交通流量或历史延迟预测路段当前交通状况的方法并不可靠.
此外,要实现高效的数据路由传输,配置大量路边基础设施节点(deployingroadsideunit,简称RSU)是一种可行方案,但通常需要额外开销.
基于城市区域长时间拥有大量地上停放车辆这一事实,提出了基于停车骨干网络的数据传输策略PBBD(parkingbackbonebaseddatadelivery),不需要配置任何地面基础设施,而是把地面的停放车辆组成一个虚拟的停车覆盖网络,通过该停车覆盖网实现数据的传输.
为此,首先,对于每一条道路,把路边和非路边停放车辆组成一个尽可能长的停车簇,并基于这些停车簇组织城市停车骨干网络.
其次,设计基于停车覆盖网络的全新数据传输算法来实现车辆间的有效数据传输.
基于真实城市地图和交通数据的模拟实验结果表明,与现有的几种数据传输算法相比,PBBD能够以较低的网络传输开销和较小的传输延迟获得较高的数据传输成功率.
关键词:车载自组织网络;簇;停放车辆;覆盖网;数据传输中图法分类号:TP393中文引用格式:朱金奇,马春梅,刘明,陈贵海,龚海刚,刘斌.
车载自组织网络中基于停车骨干网络的数据传输.
软件学报,2016,27(2):432450.
http://www.
jos.
org.
cn/1000-9825/4839.
htm英文引用格式:ZhuJQ,MaCM,LiuM,ChenGH,GongHG,LiuB.
Datadeliveryforvehicularadhocnetworksbasedonparkingbackbone.
RuanJianXueBao/JournalofSoftware,2016,27(2):432450(inChinese).
http://www.
jos.
org.
cn/1000-9825/4839.
htmDataDeliveryforVehicularAdHocNetworksBasedonParkingBackboneZHUJin-Qi1,2,MAChun-Mei2,LIUMing2,CHENGui-Hai3,GONGHai-Gang2,LIUBin21(SchoolofComputerandInformationEngineering,TianjinNormalUniversity,Tianjin300387,China)2(SchoolofComputerScienceandEngineering,UniversityofElectronicScienceandTechnologyofChina,Chengdu611731,China)3(SchoolofElectronicInformationandElectricalEngineering,ShanghaiJiaotongUniversity,Shanghai200240,China)Abstract:Vehicularadhocnetworks(VANETs)arecharacterizedbyintermittentconnectivity,highmobilityofvehiclenodesanddynamictopology.
ThismakesdatadeliveryinVANETsverychallenging.
Perviousworksthatbasedonhistoricaltrafficpatternorhistoricaldatadeliverydelaytopredictcurrenttrafficconditionsontheroadsarenotaccurate.
Deployingroadsideunits(RSUs)isapossiblesolutiontoovercomethechallenges,butitoftenrequiresinvestment.
Drivenbythefactthattherearelargeamountsofoutsideparkedvehiclesinurbanareas,thispaperproposesaparkingbackbonebaseddatadeliveryparadigm(PBBD)forVANETs.
PBBDdoes基金项目:国家自然科学基金(61103227,61272526,61170256,61103226,61173172,61173171,61370204);天津师范大学引进人才基金(5RL133)Foundationitem:NationalNaturalScienceFoundationofChina(61103227,61272526,61170256,61103226,61173172,61173171,61370204);ImportFoundationofTianjinNormalUniversityofChina(5RL133)收稿时间:2014-04-21;修改时间:2014-06-29,2015-02-17;采用时间:2015-04-05朱金奇等:车载自组织网络中基于停车骨干网络的数据传输433notneedanyRSUs,butleveragesavirtualoverlaynetworkformedbyoutsideparkedvehiclestohelptransmittingmessagesamongvehicles.
Thisschemeconsistsoftwoparts.
First,toeachroad,parkedvehiclesbothatroadsideandoff-streetaregroupedintoaclusteraslargeaspossible.
Anurbanoverlaynetworkisestablishedbasedonthistypeofclustersfordatatransmission.
Secondly,novelmessagedeliveryschemesaredesignedtoefficientlytransmitmessagestodestinationvehiclesthroughtheproposedvirtualoverlaynetwork.
SimulationresultsbasedonarealcitymapandrealistictrafficsituationsshowthatPBBDachievesahigherdeliveryratiowithlowernetworktransmissionoverheadandreasonabletransmissiondelay.
Keywords:VANETs(vehicularadhocnetworks);cluster;parkedvehicle;overlaynetwork;datadelivery随着无线通信技术的迅速发展,如今越来越多的汽车制造商为汽车安装了智能计算和无线通信设备,以及电子地图和GPS系统,用于部署大规模的车载自组织网络,以提供安全、有效、方便的驾驶环境.
车载自组织网络已经成为当今的一种新兴技术.
在车载自组织网络中,车辆之间不仅能够相互通信,而且车辆还能直接与路边基础设施通信,应用领域包括安全驾驶、智能传输以及信息服务和娱乐等方面.
车载自组织网络是以数据为中心的网络,数据的传输和节点之间的通信是车载自组织网络的基本功能.
由于车辆的高速运动、动态的网络拓扑结构以及车辆节点之间的间歇连通特性,如何以较低的网络开销在车辆节点之间高效的进行数据消息的路由传输成为研究的挑战.
针对这一问题,很多研究提出了相应的解决方案[13],这些解决方案大多数采取根据各路段的历史传输延迟预测当前传输延迟,而后把数据消息沿着传输延迟最小的路段传输给目的地的方法.
比如,VADD[1]利用对车辆移动的预测和预载入的历史交通流量状态,车辆节点就能找到适合转发数据包的下一条路段,从而降低延时和提高协议性能.
事实上,由于道路的车流量变化迅速,利用历史延迟预测路段的当前传输延迟并不准确.
此外,泛洪机制和机会性传输[4]是解决移动物体间数据通信的两种可行方法,然而泛洪机制通常会产生大量的网络传输开销,而机会性路由的数据传输延迟会很长,所以这两种方法都不是解决移动车辆之间数据传输的有效方法.
为了有效地进行移动车辆间的数据传输,可以在路边放置大量的基础设施节点RSU(deployingroadsideunit),通过RSU辅助完成车辆间的通信.
相对于无基础设施支持的移动车辆通信方式,上述方法容易实现且能获得较高的数据传输性能.
然而此方法存在以下缺陷:(1)RSU的传输范围有限,很难适应快速变化的网络拓扑结构;(2)数据传输的性能受RSU影响巨大,当RSU节点数目较多时,数据传输的性能较好.
相反,若RSU节点数量有限,则协议性能较差;(3)兴建RSU需要额外开销;(4)城市的某些区域可能没有RSU且固定基础设施节点在灾害(洪水、断电、飓风)发生时容易失效.
比如,2013年四川暴雨导致7个城市的输电线路和大量城市基础设施严重受损,此时基于基础设施的网络全面瘫痪[5].
为此,本文提出基于停车骨干网络(又称停车覆盖网)的数据传输策略(parkingbackbonebaseddatadelivery,简称PBBD),不需要安装任何基础设施节点,而是把地面的停放车辆组成一个虚拟的停车覆盖网,并通过覆盖网络实现城市范围内车辆间的有效数据传输.
由于城市区域内停放车辆数目众多,分布广泛,且平均停放时间较长[6],一旦把这些停放车辆组织成稳定的覆盖网络,该网络就能高效地实现数据消息的存储、处理和转发.
本文的基本思想包括两部分:对于每一条道路,首先把路边和非路边的停放车辆组成一个尽可能长的停车簇,再把这些停车簇组织成一个城市停车骨干网.
其次,设计基于停车骨干网络的全新数据传输算法实现车辆间的有效数据传输.
调查和仿真模拟验证,相对于现有的几种数据传输算法,本文的策略能够以较低的传输延迟和传输开销达到较高的数据传输成功率.
本文第1节介绍相关工作.
第2节描述假设和停车覆盖网的网络结构.
第3节介绍停车覆盖网络的设计思路.
第4节介绍如何基于所建立的停车覆盖网实现高效数据传输算法的设计.
最后基于调查和仿真模拟验证所提的协议和算法.
1相关工作近年来,VANETs的数据传输和路由策略得到了广泛研究.
如文献[7]的RBVT协议中,源节点在发送数据消息前先在网络中广播一个路由请求消息RR(routingrequestmessage),用来建立一条到达目的节点的传输路径,434JournalofSoftware软件学报Vol.
27,No.
2,February2016目的节点收到RR消息后发送包含传输路径的回复消息给源节点.
由于只有当传输路径可用时才进行数据消息的传输,RBVT的数据传输率通常较低.
针对车载自组织网络的特性和城市交通状况,Skordylis等人提出了D-greedy[8]路由算法.
该算法根据消息的生存时间和携带该消息的车辆与路边设施节点RSU的距离决定是转发消息还是让车辆携带该数据消息继续行驶.
目前,大量研究者提出基于固定基础设施实现车辆之间的数据传输.
文献[9]令源车辆把数据消息先传给附近的RSU节点,再利用RSU网络转发这些数据消息,最终通过RSU节点把消息传递给目的车辆.
然而兴建RSU存在额外的开销,并且该方法中消息的传输延迟主要取决于车辆在行驶过程中遇到公共RSU节点的频率.
RSU节点布置得越稀疏,该方法的性能就越差.
此外,很少有研究提及基于车载网络的覆盖网络结构.
Hsieh等人[10]提出了车载多播覆盖网的思想,其中源车辆和所有目的车辆组成一个以源车辆为根的多播路由树,并通过该路由树实现源和目的节点的数据传输.
然而该思想的缺点是,车辆的动态移动性及网络的间歇连通性导致路由树的维护相当困难.
文献[6,11]指出,城市范围内数目众多的停放车辆可以作为有相当大的容量和处理能力的数据中心,对车辆用户和外部用户提供全面的信息收集和数据处理等服务.
由于车辆每天的平均停放时间占一天总时间的95%[11],允许停放的车辆彼此通信可以显著提高VANETs的连通性.
2网络架构2.
1基本假设(1)由于车载计算与通信模块为低功耗设备,车辆在停放过程中车辆电瓶的电量足够为这些设备供电,所以假设车辆在停放过程中仍具有计算和通信能力.
(2)假设每个车辆都配备有GPS和电子地图,且这些设备在车辆停放时也可以使用.
GPS设备不仅可以提供车辆的准确位置,还可以确保时间同步.
电子地图则提供了城市各街道道路拓扑图,这样的地图目前已经非常普遍.
(3)部分停放车辆的车主愿意共享车辆的无线通信功能和存储功能.
这一假设可以建立在一定的激励机制上,如提供免费停车位等.
文献[12]表明,商家愿意提供各种服务来激励停放车辆的车主共享他们停放车辆的资源.
这方面的激励机制在不久的将来会得到广泛的研究和应用.
(4)假设车辆节点的缓冲区极大,能够存储大量数据.
2.
2网络基本架构基于真实的城市停车调查统计报告,路边停车、外部停车和内部停车分别占总停放车辆的69.
2%,27.
1%和3.
7%[13].
其中,27.
1%的外部停车属于非路边停车,车辆节点与道路有一定的距离.
如果这一距离小于车辆无线通信距离而且无障碍物阻隔,停放车辆仍可以与道路上的行驶车辆通信.
因此本文主要关注于路边停车和非路边停车,我们的目标是建立一个网络拓扑结构高度动态变化的车载自组织网络上的停车骨干网络,并基于此虚拟覆盖网络实现车辆的数据路由传输.
由于城市范围的停放车辆数量庞大,停车时间较长且分布广泛,它们能够替代固定基础设施RSU节点进行通信,为车载自组织网络提供各种服务.
本文的3层网络结构如图1所示,自底向上为物理层、逻辑层和应用层.
物理层:物理层为城市范围内所有车辆构成的车载自组织网络.
其中,车辆之间通过车载无线通信装置实现彼此通信.
逻辑层:逻辑层是由大量路边和非路边停放车辆组织的停车覆盖网络.
这些广泛分布的静态停放车辆既能作为数据存储单元又能作为数据传输单元,与移动车辆进行通信.
虚拟覆盖网络包含若干中继单元(relayunits)和虚拟链路(virtuallinks),中继单元为停车簇,虚拟链路为移动车辆的存储转发(carry-and-forward).
该虚拟骨干网提供基于VANETs的车辆路由传输服务.
应用层:应用层主要是基于虚拟停车覆盖网络为车辆用户提供安全舒适的信息收集、数据处理、消息发布、朱金奇等:车载自组织网络中基于停车骨干网络的数据传输435车辆追踪等各种车载服务,满足车辆用户的各种应用需求.
由于应用层的各种服务均是基于停车覆盖网络进行的,因此如何建立和维护停车覆盖网络是本文要解决的关键问题之一.
下面我们将提出相应的解决方法,即停车骨干(parkingbackbone)网络.
Fig.
1Layerednetworkarchitecture图1分层网络架构3停车骨干网络的设计停车骨干网络的设计主要包括3部分:停车簇的管理、骨干网的构建和骨干网络的连通性分析.
本节将逐一加以介绍.
3.
1停车簇管理通常城市道路的两边设有大量的非路边停车场,且路边也有大量停车位.
从而带来了大量的停放车辆.
我们把同一条道路路边和非路边的停放车辆组织成一个尽可能长的停车簇.
这是可行的,因为对于路边停车,一个停车位的宽度通常为5m,而车辆的通信范围为250m左右,由于停车位的平均占用率很高[14],所以对于一辆路边停放车辆,在它的通信范围内找到一辆邻居路边停放车辆的概率非常大.
尽管极特殊情况下有些停放车辆与其他停放车辆相距较远不能实现相互通信,但是道路上的移动车辆可以作为它们之间通信辅助的中间节点.
此外,对于城市中非路边停车场内的停放车辆,它们与最近道路的距离通常不会超过250m,所以大部分非路边停放车辆可以与簇中其他停放车辆建立连接.
一个典型的停车簇如图2所示,其中,H1和H2为该簇的两个簇头(clusterhead),M1~M10为成员节点.
停车簇的建立过程如下:首先,位于道路最尽头的两个路边节点被选举为簇头,这样,进入或离开该道路的移动车辆必会遇到其中的一个簇头.
簇头负责整个簇内的网络管理,处理节点加入和离开等事件.
簇头确定后,各簇成员周期性地报告自己的位置、ID号和剩余存储空间到两个簇头,由簇头维护整个簇,并进行簇内资源的管理和数据的转发.
考虑到簇头随时都有可能离开停车簇,我们规定两个备用簇头节点,如图中QH1和QH2所示.
备用簇头为同一停车簇中紧邻簇头的停放车辆,备用簇头始终保持簇头收集信息的复本.
当簇头要离开停车簇时(汽车引擎发动),会触发新簇头的选举以及旧簇头把收集的簇信息转发给新簇头.
可见,备用簇头增强了整个停车簇的鲁棒性.
簇内信息的传输按以下方式进行:对于与簇头相互连通的成员节点,在确定簇头后,簇成员首次报告自己的436JournalofSoftware软件学报Vol.
27,No.
2,February2016信息给簇头时采取广播方式进行.
在进行信息广播时,令这些广播信息每经过一跳就记录所经过该跳节点的ID号.
对于不能与簇头直接通信的成员节点,簇头在接收它们的广播消息时,对源节点相同的广播消息,接收最先到达的n个该广播消息的复本,并把该n个复本的传输路径按照这些复本到达簇头的先后顺序标记为最佳路径,次佳路径,…,第n佳路径.
簇头在收到n个广播消息复本后沿最佳路径回复一个带有该n条路径信息的ACK消息给这个成员节点.
上述过程如图3所示,图中节点i为簇成员节点,H1为簇头节点,路径(i,j,k,H1)为i到簇头的最佳路径.
H1H2M1M2M4M5(QH1)M6M7M8M9M10M5(QH2)VFig.
2Atypicalroadcluster图2停车簇H1ijki,j,k,H1ACKACKACKFig.
3Datatransmissioninacluster图3簇内传输为了减小簇内数据传输的开销,以后成员节点周期性地报告信息给簇头以及簇头向成员节点发送消息首先选择最佳路径进行,最佳路径若不存在(最佳路径上的停放车辆开走),则选择次佳路径传输消息.
只有当n条路径均不存在时,该成员节点才发起下一轮广播过程,寻找新的传输路径.
此外,对于极个别不能与其他簇内成员连通的孤立簇成员节点,数据传输需要移动车辆辅助.
这些节点在与簇头进行消息通信时,会选择移动方向朝向数据传输方向的车辆作为下一跳传输节点,由该车辆通过存储转发方式把数据传输给目的点.
若簇头隔一段时间收不到某个成员节点的报告消息,则认为该成员已经驶出簇并删除相应成员的路径信息.
具体路径数目n的取值与网络的规模和簇的稳定程度有关.
当网络规模较小或簇结构越稳定时,n应取小一些.
相反,当网络规模较大且簇较不稳定时(进出停车簇的车辆频繁),n应取大一些.
此外,由于广播消息很小,在停车簇内广播成员的信息并不会带来很大的网络开销.
实验结果表明,当簇的大小为200时,所有车辆广播一次的消息大小将近1KB.
3.
2骨干网的构建为了实现数据消息的传输,首先要建立一个车载自组织网络上的虚拟停车骨干网.
本文的停车骨干网是建立在停车簇基础上的,具体构建步骤如下:1.
首先,每个停车簇发起一个邻居发现过程.
例如,停车簇J的簇头节点把一个带有簇头地理位置和该簇朱金奇等:车载自组织网络中基于停车骨干网络的数据传输437ID号信息的Nei.
REQ消息广播给簇外2,3跳内的其他停车簇(即把生存时间TTL设定为2或3).
另一个停车簇(如停车簇I)收到此Nei.
REQ消息后,把停车簇J设为自己的邻居簇.
如果两个邻居簇之间能够直接连通,则上述邻居发现过程可以直接完成;若两个簇之间不能连通,就需要通过移动车辆协助完成消息的广播.
经过一段时间的邻居发现,每个停车簇都知道自己周围一定范围内的邻居停车簇分布情况.
另外可能会存在没有任何邻居簇的孤立停车簇,其主要原因是,某些停车簇可能位于相对较远的城市区域,该区域附近没有其他停放车辆;另外一个原因可能是城市的某些主要干道不允许路边停车.
如果某一停车簇被这些主要干道包围,就可能造成该停车簇相距其他停车簇的距离较远,那么上述邻居发现过程就很可能发现不到其他停车簇节点.
2.
为了把所有停车簇(孤立停车簇除外)组织成停车骨干网络,我们让每个停车簇与它所有的邻居停车簇建立虚拟连接.
通过此过程,停车覆盖网络形成了一个连通图G(V;E),其中,V作为成员节点是停车簇的集合,E作为边节点是相邻停车簇的虚拟路径集合(每条路径可能包含多个路段或不包含任何路段.
组织成的停车骨干网络结构如图4所示.
3.
假设骨干网络中的每个成员均了解所有其他成员的存在信息和地理位置.
这可以通过一个简单的机制来实现,例如,各成员簇节点周期性地将自身掌握的停车簇信息(编号和位置)以Hello消息的方式广播到邻居停车簇,然后各邻居停车簇交换自己掌握的停车簇信息(类似于文献[15]中提出的链路更新机制).
此过程一直进行,直到每个成员节点掌握的其他成员信息不再更新为止.
由于簇的位置固定不变且停车簇在全天的利用率都很高,每个停车簇周围有哪些停车簇基本上是固定不变的,也就是说,覆盖网络结构很稳定.
完成上述成员信息更新后,在某个成员停车簇为空(停放的车辆全部开走)或空停车簇中驶入车辆的情况下,会再以刚才所述的Hello消息形式通知它的邻居停车簇,邻居停车簇再以上述类似链路更新形式更新其他成员停车簇掌握的成员信息.
虚拟覆盖网停车簇2停车簇3VANET中显示出的停车簇没有在VANET中显示的停车簇Fig.
4Virtualoverlaynetwork图4虚拟覆盖网络文献[14]对路边停车的调查显示,路边停车位一天的平均利用率达到了93%.
文献[16]对西安市的停车状况进行了调查统计,结果显示,西安市路边停车位一天的平均利用率高达70%,路边车辆的平均停放时间为57分钟.
报告[17]提供了2013年武汉市停车调查情况,调查结果表明,路边和非路边停车位利用率非常高,相对于地下停车,车主更愿意把车辆停放于地上.
这些调查结果均表明了停车覆盖网络的稳定性.
此外,文献[18]提供了加拿大蒙特利尔市(市中心)面积为5500km2区域的停车状况统计,表明一天内广泛的停放车辆资源.
通过该统计数据还可以得出该市路边停放车辆的密度为7.
58m/每停放车辆.
文献[19,20]分别提供了新加坡2013年路边停放车辆总量统计和道路建设情况统计,据此推断,新加坡地上停放车辆的平均密度为438JournalofSoftware软件学报Vol.
27,No.
2,February201652.
63m道路长度/每停放车辆.
另有报告[16]显示,西安市建成区地面停放车辆密度为29.
164m2/每停放车辆,具体见表1.
如此高的停放车辆密度表明,移动车辆在整个运动过程中遇到停放车辆的概率很大,且遇到停放车辆的数量会很多.
基于这些事实,我们认为停车骨干网络辅助移动车辆进行数据传输是一个可行方案.
该覆盖网络有如下优点:(1)停车覆盖网络能够在底层车载自组织网络拓扑结构不断变化的情况下保持一个相对稳定的网络拓扑结构.
(2)作为覆盖网的成员节点,我们可以像类似因特网的静态IP地址一样给每个停车簇指定一个静态网络地址,在此基础上设计类似于因特网的链路状态路由协议完成数据的高效路由.
(3)消息捆绑,即发往同一目的地的数据消息可以在停车簇内捆绑成一个消息,以便降低消息处理的开销和网络带宽消耗.
Table1On-Streetparkinginthreecities表13个城市的路边停车状况AreaTotalparkingspaceTotalroadlength(m)ortotalarea(m2)Density蒙特利尔市439926660m7.
58m/veh新加坡169009045000m52.
63m/veh西安市17350505*106m229164m2/veh3.
3覆盖网络的连通性分析我们采用渗透理论来分析停车骨干网的连通性.
作为传统理论模型,渗透理论[21]曾被用来分析很多临界现象,首先,如图5所示,假设整个城市区域被划分成大小相同的格子区域,每一格子代表一个社区(block),相邻两个格子的边代表一个路段.
根据squarebond渗透模型,我们把图中每一路段定义为一个bond,规定当路段被一系列连通车辆覆盖时,bond为开放(open)状态,否则该bond为关闭(close)状态.
此外,设概率p为路段被车辆连通的概率.
Fig.
5Bondpercolationtheoryinsquarearea图5平方区域的bond渗透理论渗透理论证明bond的连通性与p密切相关,若p≥0.
5,则网络的连通性强;若pD[k]+Dsi)13.
D[j]=D[k]+Dsi;//调整s到剩余节点的估计距离14.
}此外,当与目的车辆最近的停车簇收到源车辆发送的数据消息P后,首先查看目的车辆D是否是自己的成员节点,若是则通过簇内消息传输机制把P传给D,否则通过第4.
2节的数据传输方法把P传输给目的车辆.
另外,数据消息在簇中的存储可以通过簇头进行管理.
当有新的数据p到达簇时,接收p的簇成员车辆(如车辆L)向簇头发送包含新消息大小的到达通知消息,簇头接收到该通知消息后检查每个簇成员的存储空间,然后将可提供存储服务的簇成员节点的ID和位置返回给车辆L.
总之,PBBD始终把数据消息尽量沿着有路边停放车辆的路段传递,在没有停放车辆辅助传输时才把消息传递给移动车辆,由移动车辆沿着延迟尽可能小的道路进行传输.
由于城市范围内路边停放车辆具有分布范围广泛、停车位全天的占用率高和平均停车时间较长的特点,相对于现有的数据路由策略不考虑停放车辆,基于路边停放车辆进行数据传输更加可靠,数据传输延迟受交通流量和当前交通状况的影响较小,更能实现稳定高效的数据传输.
5性能模拟本节我们首先对城市环境的停车情况实际进行调查,然后对PBBD进行性能分析.
444JournalofSoftware软件学报Vol.
27,No.
2,February20165.
1调查我们对中国成都的城市区域进行了为期6周的调查,调查区域如图10所示.
该区域是大小为1600m*1400m,包含10个十字路口(图中编号为0~9)和14个长度总和为7860m的双行道.
该区域总共包含8个非路边停车场.
我们对被调查区域内所有路段每周二、周四、周六的停车情况做出了调查,对所有沿路5m内停放的车辆按16:00,18:00.
和22:00,分时段进行了统计.
在统计中我们排除了周围有障碍物环绕、明显不易通信的车辆.
调查结果见表2.
在3类有不同停车限制的街道中,停放车辆的密度有很大的区别.
在允许免费停车的路段R04,R15和R26,停车密度非常高.
在缺少公共停车位的路段R37和R79,停车密度较低,且这些停放车辆主要来自专用停车和违章停车.
在其他路段,停车密度比较适中.
总体而言,在一天不同时段,各路段的停车数量相对稳定.
在调查中,我们还对被调查区域内随机位置单位时间内行驶经过的车辆数目进行了统计.
结果发现,不同时间段的行驶车辆密度在300辆/小时~2200辆/小时之间变化.
区域内行驶车辆的数目在60~400之间,且车辆平均行驶速度在4040km/h~80km/h之间.
Fig.
10Roadtopologyusedinthesimulation图10仿真采用的街道拓扑Table2Roadsideparkingsurveyresult表2路边停车调查结果StreetPolicyDensityAverageR04,R15,R26Nolimits280~320veh/km308veh/kmR37,R79Strictlimits15~25veh/km21veh/kmR01,R12,R23,R45,R56,R67,R48,R68,R89ModerateLimits72~180veh/km95veh/km5.
2仿真环境我们用NS-2.
33工具实现仿真,同时,为了准确地刻画车辆的移动,我们使用开源软件VanetMobiSim-1.
1[24]来生成真实的城市车辆移动轨迹.
在默认情况下,我们在图8所示的仿真地图上设置车辆的数量为200辆,车辆的传输范围设为250m,且车辆的平均移动速度在40km/小时~80km/小时.
底层的MAC协议采用2M的802.
11.
在仿真中,停放车辆随机分布于路边停车位或者非路边停车场,对于分布在路边停车位的停放车辆,它们严格按照表2中的密度随机分布于各道路.
每辆车的平均停放时间约为41.
40分钟(标准差为27.
17)[25].
车辆平均每30s产生一个消息,且每辆车均随机选择一辆车作为消息的目的地.
假设停车簇在仿真之前就已建立,并以60s为周期进行维护.
其他默认参数设置见表3.
Table3Simulationparameters表3模拟参数ParameterDefaultvalueSizeofdatamessage1KBIntervalofbeaconmessage1sDatasurvivaltime20minsSimulationtime1hourn3朱金奇等:车载自组织网络中基于停车骨干网络的数据传输445我们把PBBD与CANDELIVER[9],RBVT[7]协议和VADD协议进行了分析对比.
为了提高RBVT的性能,我们在实验中对RBVT协议进行了修改,令中间车辆发现下一跳传输路径损坏时继续携带保持数据10s.
在对CANDELIVER协议进行性能仿真时,我们在仿真区域中设置4个平均分布的RSU节点,每个RSU节点的通信范围为250m.
我们关注如下3个性能:(1)数据平均传输成功率:在规定的模拟时间内被目的车辆成功收到的数据占车辆发送数据的比值的均值.
(2)数据平均传输延迟:目的车辆收到消息所需时间的均值.
(3)车辆传输开销:规定的模拟时间内车辆为了进行数据传输产生的平均通信开销.
5.
3默认参数下的结果比较默认参数下,PBBD,CANDELIVER,VADD和RBVT的性能对比如图11和表4所示.
Fig.
11Averagedeliveryratiounderdefaultparameters图11默认参数下的平均传输成功率Table4Simulationresultscomparisonwithdefaultparameters表4默认参数下仿真结果的对比PBDDVADDCANDELIVERRBVTAveragedeliveryratio(%)85.
771.
576.
251.
1Averagedeliverydelay(s)14.
625.
821.
540.
5Networktrafficoverhead(KB/s)8.
319.
715.
411.
2可以看出,PBBD的平均传输成功率比其他3个协议要高,传输延迟和传输开销比其他3个协议要小.
这主要因为PBBD依靠稳定且广泛分布的地上停放车辆进行数据的传输和存储,稳定且广泛分布的地上停放车辆可以使数据消息以较快的速度和较高的概率被传输给目的车辆.
虽然极少的路段不允许路边停车,数据消息仍会通过移动车辆,选择沿着延迟最小的路段传输,因此仍然能够保证消息传输的效率,此外,消息传输的确认机制也保证了数据消息传输的可靠性.
由于CANDELIVER协议配置的RSU数量有限(4个),车辆与距离最近的RSU通信花费的时间较长,致使车辆和RSU通信的概率不高,车辆携带的消息在传输给RSU之前可能已经过期或被丢弃,所以CANDELIVER协议的平均传输成功率低于PBBD,平均传输延迟较大.
RBVT的平均传输成功率最低,平均传输延迟最大,因为只有当路径连通时RBVT才进行数据的传输.
对于VADD,其主要依靠历史数据选择数据递交路径,并依靠移动节点进行数据维持和数据传输,由于车辆具有高速移动的特性,移动车辆之间需要频繁地进行数据移交,因此数据传输代价和传输延迟均较大.
此外,由于依靠历史记录选择路径并不准确,且在个别路段可能存在携带数据的车辆在其通信范围内没有邻居节点,数据被携带的时间较长导致数据消息过期,因此数据递交成功率低于PBBD.
5.
4车辆数量对性能的影响本组实验主要研究车辆数量对协议性能的影响.
我们把移动车辆节点的总数从50增加到300,各种算法的性能变化如图12(a)~图12(c)所示.
9080706050403020100Deliveryratio(%)RBVTVADDCANDELIVERPBBD446JournalofSoftware软件学报Vol.
27,No.
2,February2016(c)传输开销Fig.
12Impactofvehiclenumber图12车辆数量的影响图12(a)显示,随着车辆密度的增大,4种算法的传输成功率均提高,尤其是CANDELIVER,VADD和RBVT协议.
这是因为车辆的增多可以在一定程度上增大网络的连通性.
并且随着车辆数量的增多,网络连通性越来越好且可供选择的下一跳传输车辆的数量增大,此时能够以更大的概率找到最佳的中继车辆,把数据消息传递给目的车辆.
从车辆密度变化过程中可以看出,PBBD的传输成功率略有增长并始终高于其他3个协议,尤其是当车辆比较稀疏时,PBBD仍能保持较高的数据传输成功率.
其原因是,PBBD主要依靠城市范围内广泛且稳定分布的地面停放车辆进行数据消息的传输,这些停放车辆组成了一个具有稳定通信几率的停车覆盖网络.
由于较少依靠移动车辆进行路由,所以移动车辆数量的变化对PBBD的影响不是特别大.
此外,如图12(b)所示,随着车辆密度的增加,PBBD的传输延迟变化不大而其他3种协议的平均延迟均减小.
当车辆数量较多时,CANDELIVER协议的平均传输延迟低于VADD和RBVT,显示了利用固定基础设施节点进行消息传输的速度更快.
从图12(c)中还可以看出,车辆数量的增加导致CANDELIVER和VADD的车辆传输开销增大,主要是参与扩散消息的车辆数量增多了,消息之间的传递会造成更大的开销.
而PBBD主要利用停放车辆传输数据,所以车辆传输开销变化不大且具有最合理的网络负载.
5.
5车辆产生消息的速率对性能的影响本组实验研究车辆产生数据消息的速率对协议性能的影响.
当其他参数保持默认值时,数据产生速率从每分钟1个包到每分钟60个包变化.
如图13所示.
CANDELIVERRBVTPBBDVADDDatadeliverydelay(s)70605040302010Numberofverhicle50100150200250300350400(a)平均传输成功率(b)平均传输延迟5010015020025030035040010090807060504030Datadeliveryratio(%)NumberofverhicleCANDELIVERRBVTPBBDVADDCANDELIVERRBVTPBBDVADDDatadeliveryoverhead(KB/s)403530252015105Numberofverhicle50100150200250300350400朱金奇等:车载自组织网络中基于停车骨干网络的数据传输447(c)传输开销Fig.
13Impactofvehicle'messagegenerationrate图13车辆产生消息速率的影响图13(a)显示车辆产生消息的速率变化时,PBBD协议的数据传输成功率始终高于其他3个协议.
随着产生消息速率的增大,PBBD协议的传输成功率稍有下降,而其他3个协议的平均传输成功率下降趋势大于PBBD.
其原因是,对于CANDELIVER,VADD和RBVT协议,网络中产生的消息增多,数据移交占用的带宽增大,同时加大了无线传输冲突的可能性,导致数据传输率降低.
此外,由于RBVT只沿着特定的路径发送,当单位时间产生的消息增多时,路径不可用会导致丢弃的消息增多,所以成功率下降最快.
而PBBD在进行消息传输时尽量选择停放车辆,由于尽量将数据维持在静止的停放车辆节点并只把消息发送给邻近的停车簇节点,从而降低了无线传输的冲突.
图13(b)显示随着车辆产生消息的速率增大,4种协议的延迟均有所增大,由于主要利用地上分布广泛的停放车辆传输数据,PBBD的延迟增长较慢且低于其他3个协议.
此外,如图13(c)所示,随着消息产生率的增加,VADD的传输开销增长最大,因为需要频繁地进行数据移交.
由于CANDELIVER限制了消息传输的范围,传输开销的增长比VADD稍慢.
5.
6数据包大小对性能的影响本组实验讨论数据包大小对不同协议性能的影响,数据包越大,消耗的网络带宽相应地越多.
图14(a)~图14(b)为在不同协议下,传输成功率和传输延时与数据包大小的变化关系.
无论是传输成功率还是延时,PBDD,VADD,CANDELIVER和RBVT随数据包大小变化均相对稳定,且PBDD明显优于其他3种协议.
原因是它们对带宽资源的要求相对较小且都有各自的数据扩散控制策略,因而受数据包大小变化的影响也很小.
图14(c)是网络传输代价与数据包大小的关系,显示随着数据包的增大,由于传输的数据量相对增大,4种协议的网络传输代价稍有上升.
50454035302520151050Deliveryoverhead(KB/s)RBVTCANDELIVERVADDPBBD01020304050RequestrateDatadeliveryratio(%)RBVTCANDELIVERVADDPBBD908070605040302010001020304050RequestrateRBVTCANDELIVERVADDPBBD706050403020100Deliverydelay(s)01020304050Requestrate(a)平均传输成功率(b)平均传输延迟448JournalofSoftware软件学报Vol.
27,No.
2,February2016(c)传输开销Fig.
14Impactofpacketsize图14数据包大小的影响5.
7配置RSU的数量对性能的影响固定基础设置节点RSU的数量决定CANDELIVER的性能.
所以本实验中,我们把固定基础设置节点的总数量分别设置为1,4,10和20个,并测试不同RSU节点数目对CANDELIVER协议的影响,实验结果如图15所示.
PBBD协议的性能高于RSU配置4个时CANDELIVER协议的性能,却低于RSU节点10个和20个时CANDELIVER的性能.
这是合理的,因为对于基于RSU的车载路由协议CANDELIVER,仿真区域内配置的基础设施节点数量越多,车辆在移动过程中遇到RSU节点的概率就越大,也就越容易把数据传输给RSU节点.
当RSU节点数量增大到一定程度时,仿真区域内的所有车辆在移动过程中均能很容易地遇到与之通信的RSU节点并通过RSU节点之间的交互直接完成数据路由,此时CANDELIVE的数据平均传输成功率将显著增长,数据的传输延迟将显著降低.
3020100Deliveryoverhead(KB/s)RBVTVADDPBBDCANDELIVER12345Packetsize(KB)RBVTCANDELIVERVADDPBBDDatadeliveryratio(%)10090807060504012345Packetsize(KB)CANDELIVERRBVTPBBDVADD8070605040302010Deliverydelay(s)1234Packetsize(KB)(a)平均传输成功率(b)平均传输延迟Fig.
15ImpactofRSUnumber图15RSU数量的影响Datadeliveryratio(%)1009080706050403020RBVT1RSUPBBD20RSUsVADD4RSUs10RRSUs朱金奇等:车载自组织网络中基于停车骨干网络的数据传输4496结论与下一步工作车载自组织网络是以数据为中心的网络,数据的路由传输是VANETs的基本功能.
VANETs具有节点高速移动、拓扑结构高度动态变化等特点,使得如何有效地解决移动车辆间的数据传输问题成为挑战.
针对城市范围内天然存在、广泛分布且结构稳定的地面停车场资源,本文提出了停车覆盖网络方案PBBD,即把一条道路的路边和非路边停放车辆组织成停车簇,再把众多停车簇组成停车骨干网,利用停车骨干网完成源车辆到目标车辆的数据路由.
本文通过现实的停车调查和大量的仿真实验对提出的PBBD策略进行了验证.
仿真结果表明,PBBD以较小的传输代价和传输延迟实现了较高的数据传输成功率.
为了更加准确地分析网络的连通性,下一步将根据实际的停车调查数据进一步完善停放车辆的具体分布.
此外,如何实现目的地未知情况下的数据路由,也是下一步我们的研究工作的重点.
References:[1]ZhaoJ,CaoG.
Vadd:Vehicle-Assisteddatadeliveryinvehicularadhocnetworks.
IEEETrans.
onVehicularTechnology,2008,57(3):19101922.
[doi:10.
1109/TVT.
2007.
901869][2]TomHL,ShenXM,BaiF.
Integrity-Orientedcontenttransmissioninhighwayvehicularadhocnetworks.
In:Proc.
oftheIEEEInfocom.
Turin:IEEEPress,2013.
25622570.
[doi:10.
1109/INFCOM.
2013.
6567063][3]SongC,LiuM,GongHG,ChenGH,WangXM.
Distributedreal-timeinformationbasedroutingprotocolinvehicularad-hocnetworks.
RuanJianXueBao/JournalofSoftware,2011,22(3):466480(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/3808.
htm[doi:10.
3724/SP.
J.
1001.
2011.
003808][4]WangY,WuH.
Delay/Fault-Tolerantmobilesensornetwork(DFT-MSN):Anewparadigmforpervasiveinformationgathering.
IEEETrans.
onMobileComputing,2006,6(8):10211034.
[doi:10.
1109/TMC.
2007.
1006][5]TanXP.
Sichuanfight"2013.
7.
9"stormflood.
JournalofChinaFloodControlandDrought,2013:23(5):12.
[6]LiuNB,LiuM,LouW,ChenG,CaoJ.
PVAinVANETs:Stoppedcarsarenotsilent.
In:Proc.
oftheIEEEInfocom.
Shanghai:IEEEPress,2011.
431435.
[doi:10.
1109/INFCOM.
2011.
5935198][7]NzouontaJ,RajgureN,WangG,BorceaC.
Vanetroutingoncityroadsusingreal-timevehiculartrafficinformation.
IEEETrans.
onVehicularTechnology,2009,58(7):36093626.
[doi:10.
1109/TVT.
2009.
2014455][8]SkordylisA,TrigoniN.
Efficientdatapropagationintraffic-monitoringvehicularnetworks.
IEEETrans.
onIntelligentTransportationSystems,2011,13(3):680694.
[doi:10.
1109/TITS.
2011.
2159857][9]MershadK,ArtailH,GerlaM.
Wecandelivermessagestofarvehicles.
IEEETrans.
onIntelligentTransportationSystems,2012,13(3):10991115.
[doi:10.
1109/TITS.
2012.
2183124][10]HsiehYL,WangK.
Roadlayoutadaptiveoverlaymulticastforurbanvehicularadhocnetworks.
In:Proc.
ofIEEEthe73rdonVTC.
Yokohama:IEEEPress,2011.
15.
[doi:10.
1109/VETECS.
2011.
5956505][11]OlariuS,KhalilI,AbuelelaM.
Takingvanettotheclouds.
Int'lJournalofPCC,2011,7(1):721.
[12]EltoweissyM,OlariuS,YounisM.
Towardsautonomousvehicularclouds.
In:ProcoftheAdHocNets.
Victoria:ACMPress,2010.
116.
[doi:10.
1007/978-3-642-17994-5_1][13]SchonfelderS,SamagaU.
Wheredoyouwanttogotoday—Moreobservationsondailymobility.
In:Proc.
ofthe3rdSwissTransportResearchConf.
2003.
111.
[14]AdivA,WangW.
On-Streetparkingmeterbehavior.
TransportationQuarterly,1987,(41):81307.
[15]KuroseJF,RossKW.
ComputingNetwork:ATop-DownApproachFeaturingtheInternet.
2nded.
,NewYork:PearsonEducation,358369.
[16]NieTT,WangXL,CaiHe.
ParkingbehaviorsurveyandanalysisofXi'an.
ArchitecturalEngineeringTechnologyandBesign,2014,13:711.
[doi:10.
3969/j.
issn.
2095-6630.
2014.
13.
673][17]ChengB.
ResearchonthesolutionstotheparkingprobleminWuhan.
BuildingMaterialsWorld,2011,32(3):135140.
[doi:103963/j.
cn.
42-1783.
TU.
2011.
03.
037][18]ZhuJQ,LiuM,WenYG,MaCM,LiuB.
Parkingbackbone:TowardefficientoverlayroutinginVANETs.
Int'lJournalofDistributedSensorNetworks,2014,2014:113.
[doi:10.
1155/2014/291308]450JournalofSoftware软件学报Vol.
27,No.
2,February2016[19]http://www.
lta.
gov.
sg/content/ltaweb/en/publications-and-research.
html[20]http://www.
onemotoring.
com.
sg[21]StaufferD,AharonyA.
IntroductiontoPercolationTheory.
2nded.
,Lewiston:TaylorandFrancis,1991.
120.
[22]ShiodaS.
Connectivityofvehicularadhocnetworksindowntownscenarios.
AdHocNetworks,2012,89:177192.
[doi:10.
1007/978-3-642-29096-1_13][23]LiuNB,LiuM,ChenGH,CaoJN.
Thesharingatroadside:Vehicularcontentdistributionusingparkedvehicles.
In:Proc.
oftheIEEEINFORCOM.
Urlando:IEEEPress,2012.
26412645.
[doi:10.
1109/INFCOM.
2012.
6195670][24]FilaliF,BonnetC,FioreM.
Vanetmobisim:Generatingrealisticmobilitypatternsforvanets.
In:Proc.
oftheVANET2006.
LosAngeles:ACMPress,2006.
9697.
[doi:10.
1145/1161064.
1161084][25]AlbaneseB,MatlackG.
UtilizationofparkinglotsinHattiesburg,Mississippi,USA,andimpactsonlocalstreams.
EnvironmentalManagement,1999,24(2):265271.
[doi:10.
1007/s002679900231]附中文参考文献:[3]宋超,刘明,龚海刚,陈贵海,王晓敏.
基于分布式实时信息的车载网络路由协议.
软件学报,2011,22(3):466480.
http://www.
jos.
org.
cn/1000-9825/3808.
htm[doi:10.
3724/SP.
J.
1001.
2011.
003808]朱金奇(1980-),女,天津人,博士,副教授,主要研究领域为无线传感器网络,车载自组织网络.
陈贵海(1963-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为无线网络,移动计算.
马春梅(1985-),女,博士,CCF学生会员,主要研究领域为车载自组织网络,移动计算.
龚海刚(1974-),男,博士,副教授,博士生导师,CCF专业会员,主要研究领域为无线传感器网络,车载自组织网络,移动计算.
刘明(1972-),男,博士,教授,博士生导师,主要研究领域为无线传感器网络,车载自组织网络,移动计算.
刘斌(1986-),男,硕士,主要研究领域为无线网络,人工智能.