车载传感网中基于群特性的MaxProp路由协议改进

王雪丽 张琳娟 张 迪

1(内蒙古赤峰学院 内蒙古 赤峰 024000)2(国网河南省电力公司经济技术研究院 河南 郑州 450052)

车载传感网中基于群特性的MaxProp路由协议改进

王雪丽1张琳娟2张 迪1

1(内蒙古赤峰学院 内蒙古 赤峰 024000)2(国网河南省电力公司经济技术研究院 河南 郑州 450052)

车载传感网中信息传输面临的主要难题是网络间歇性连通和拓扑高度动态变化，以往常常采用机会转发的思想设计路由协议来解决此难题。但现有的机会路由协议忽略了网络中部分车辆节点具有群组移动的特点，从而导致协议在群组移动场景下的性能急剧下降。为此，通过对最大相遇概率路由进行改进，提出了一种基于群特性的MaxProp路由协议。该协议利用群组内成员节点之间极好的连通性，通过群内消息扩散，间接提高群内节点与群外节点之间的相遇概率，从而增加了消息转发机会。并在ONE仿真平台上，与其他几种经典的机会路由协议相对比，改进后的MaxProp路由协议在消息传输成功率、网络开销比方面具有明显提升。

车载传感网 机会转发 最大相遇概率路由 群组移动

0 引 言

目前，随着我国工业与国民经济的快速发展，城市道路上的车辆数目急剧增加，导致城市拥堵和环境问题变得日益严重。车载传感器网络VSNs(Vehicular Sensor Networks)是智能交通系统的重要组成部分[1-2]，主要由安装在不同车辆内的无线传感器节点自组织形成网络，在保障行车安全[3]、城市道路监测[4-5]、提高行车效率[6]以及改善乘车质量[7]等方面具有广泛的应用。在VSNs中，车载传感器节点实时感知和采集行驶途中车辆自身和道路环境信息，并利用车辆专用无线通信技术将这些信息传输给所需用户。

典型的车载传感器网络结构如图1所示，携带无线传感设备的车辆节点和路边网关是核心成员[8]。车载无线传感器节点能够感知车辆内、外各种信息，如：车辆运行的内在状态、汽车的位置、速度等车内信息，或涵盖温度、湿度、大气指数的车外环境信息，以及行驶路途中交通流量、路面条件等信息。路边网关，作为车辆用户的无线访问节点，具有比车载传感节点更为强大的计算和存储能力，在汇聚车辆传感信息的同时，常以有线(光纤)或者宽带无线技术接入Internet核心网，从而提供更稳定的数据传输通道。

图1 车载传感器网络的组成

VSNs一般采用车辆间通信和车辆与路边单元通信[9]两种模式。车载传感设备可选择的无线通信技术有：Zigbee、Bluetooth、WIFI、DSRC[10-11]等。与传统的无线传感器网络WSNs相比，车载传感器网络具有如下显著特征：

(1) 节点资源无严格限制 在传统的WSNs中，节点的计算、存储和能量资源有限，促使众多路由设计者将关注点集中在节能、消息队列管理算法方面。相反，在VSNs中，车载传感设备的硬件配置成本较高，同时也有能量补给，故节点资源无严格限制。

(2) 网络拓扑高度动态变化 传统的WSNs节点多数为静态，很少考虑节点移动性问题。相反，在VSNs中，车辆节点具有高速移动性，导致网络拓扑频繁变化，使得传统的WSNs、移动自组织网络路由协议性能急剧下降。

(3) 网络传输数据量更大 在节点数量上，二者均具有大规模部署特点。唯一不同的是VSNs传输的数据量大大增加了。因为VSNs中需要传输的信息，还包括车载摄像头记录的图像、视频流等多媒体数据。

(4) 网络构成方式多样化 VSNs在网络体系结构上属于混合型的网络结构。在该网络中，除了大量移动的车辆节点外，还包括部署在路边的网关单元。一方面，移动的车辆节点通过Ad hoc方式自组织形成网络；另一方面，车辆节点利用路边网关接入核心网，实现推送数据或者查询数据的功能。

由此可见，虽然车载传感节点在硬件性能上具有优势，但鉴于网络间歇性连通和拓扑结构频繁动态变化的特点，使得VSNs中的信息传输仍面临着诸多问题，尤其对路由协议设计提出了很大挑战。针对上述问题，现有的车载传感网的路由协议大多借鉴“机会转发”策略[12]，即，节点在未遇到合适的消息中继节点或通信范围内无其他节点时，暂时存储消息，等待时机选择性转发。

1 经典的机会路由协议

1.1 泛洪路由协议Epidemic

Epidemic最初由Duke University的Amin Vahdat 和David Becker在文献[13]中提出，是一种基于复制的路由机制，主要用于解决类似与网络非实时连接的节点传输数据包的问题。其设计目标是尽量提高数据包的传输成功率和减少发送时延，在一定的时间内或者跳数内，它通过复制、扩散数据包来达到上述目的，属于泛洪式协议[14]。该协议工作时，每个节点都会维护一个矢量表SV来记录自身节点缓冲区存储的数据包。当两个节点各自进入对方的通信范围后，将交换彼此的SV。然后，节点将采用遍历的方式比较对方和自己的SV，找到自己缓存区没有的消息，并向对方发送接收对方数据包的请求，最后更新自己的SV。

如图2所示，当节点A进入节点B的通信范围时，主动向B传输SVA，B对SVB“取反”运算得到(SVB)′，并将(SVB)′与SVA作逻辑“与”运算，从而获取B未存储数据包的ID。然后，B向A请求传输这些数据包，A完成传输后，本次传输结束。以此类似，B也会将自己的数据包按照上述流程向其它节点扩散。这样，随着车辆节点间的相遇，数据包就会像传染病一样在网络中扩散。为了限制网络中数据包的拷贝数，研究人员设置了跳数限制，当达到规定的跳数上限值时，数据包将停止发送。

图2 两个节点基于Epidemic的通信流程

1.2 扩散与等待协议SprayandWait

SprayandWait是由USC的ThrasyvoulosSpyropoulos等在文献[15]中提出的，其实质也是泛洪式路由协议，但它对数据包的扩散方式定义了新的规则。该协议的工作流程分为扩散和等待两个阶段。在扩散阶段，每个消息将会产生L份拷贝，且这L份拷贝将会被分发到L个中间节点上。若消息在扩散阶段未传送到目的地节点，它将直接进入等待阶段。在等待阶段，携带有该消息拷贝的中间节点将采用单一拷贝的方式向目的地节点进行直接传输。消息分发的整体流程如图3所示。

图3 Spray and Wait协议消息分发图

假设节点N1有数据包发送给目的节点N5，且设定拷贝上限为L份。在扩散阶段初期(step1)，N1与无消息拷贝的N2相遇，此时N1将一半的消息拷贝(L1=L/2)分给N2，并保留一半消息拷贝(L2=L/2)。在扩散阶段中期(step2),N1与N3相遇、N2与N4相遇，按照上述规则，N1将L2/2份消息拷贝分给N3,并保留L2/2份消息拷贝；N2将L1/2份消息拷贝分给N4,并保留L1/2份消息拷贝。该过程将持续到L份拷贝被分配完毕为止，若目的节点N5仍未收到消息，则消息进入等待阶段(step3)。当节点N4在之后的某一时刻与节点N5相遇时，将消息拷贝传递给目的节点N5，此次消息传输结束，N4删除自己缓存里的消息拷贝。

1.3 历史相遇概率路由协议PROPHET

PROPHET是由AndersLindgren，AvriDoria等在文献[16]中提出的路由协议。研究人员认为网络中运动节点的移动规律可以通过概率统计的方式体现出来，故在该协议中定义一个“到达概率”参数P(a,b)∈(0,1)，用来表达节点a向节点b传输消息成功的概率统计。鉴于消息传输是一个动态的过程，该参数将有两种更新方式：

(1) 在每次传输成功后更新，更新公式如式(1)所示：

(1)

(2) 若节点(a，b)在很长一段时间内没有成功传输消息，则与它们有关的历史统计概率将衰减：

(2)

其中：γ∈(0,1]是衰减系数。当对Pinit和γ参数修改时，可获得协议不同的性能表现。

1.4 最大相遇概率路由协议MaxProp

MaxProp[17]是在PROPHET协议的基础上发展而来，不仅重新定义了更新公式，而且利用一些额外机制来提高消息的传输成功概率，并降低传输时延。其本质也是一种基于概率统计的路由协议[18]。类似的，基于相遇概率的路由算法在文献[19]中也有提到。

在MaxProp协议中，最为重要的是利用节点过去的相遇信息，估算每个信息到达目的地节点的开销，然后利用这些开销值对节点存储的消息进行排序，最后优先转发那些最有可能到达目的地节点的消息。同时，为保证那些新产生的消息能够得到传输，提出了一些相关方法来修正上述的排序算法，因此本文将该协议作为详细说明和改进的对象。

MaxProp协议中，将根据携带消息的节点与其它节点的历史相遇关系来选择转发节点，而不是简单的“先进先出”(FIFO)原则。如图4所示，MaxProp协议的核心是消息调度机制，存储消息的缓存被分为两个部分。跳数小于门限值t的消息，其优先级将高于跳数大于门限值t的消息；若消息所经过的跳数小于门限值，则会根据跳数来对消息进行排序，跳数愈大，优先级愈低；若消息所经过的跳数大于门限值，则会根据消息估算的开销进行排序，开销值愈低，优先级愈高。门限值和消息传输开销的计算方法如下：

图4 MaxProp消息调度机制示意图

(1) 门限值t(跳数)

其值等于在消息缓存中包含第p个字节的消息(数据包)所经过的跳数。而p的值由式(3)决定。

(3)

其中，x是每次传输机会到来时传输的平均字节数，b是消息缓存的大小。

(2) 消息传输开销

其估算值基于节点相遇的历史记录信息表。具体步骤为：

if (i第一次与其它任意节点j相遇，j∈s){

}

if(与节点k相遇){

//相遇节点对应概率加α

for(j∈s){

}

}//非第一次相遇，此时概率序列的和为1+α，归一化处理

Step2 如果消息m位于节点i0，目的节点为ij，则节点i0将会利用Dijkstra算法计算出一条开销最小的路径p(i0,i1,i2,…,ij)，且消息m的开销值如式(4)所示。

(4)

MaxProp协议根据车辆节点的移动规律和链路状态信息，对缓存中的消息进行分类和排序，优先传输最大可能到达目的节点或网络中新产生的消息。但该算法并不适用群组移动场景,即，将消息传输成功概率与节点相遇概率完全等同这一本质问题，需要对其进行进一步的优化和改进。

2 基于群特性的MaxProp协议改进

车辆群组是车载传感网络中大量OBU车辆节点的逻辑集合，在智慧交通网中有着广泛的应用场景，如组队行驶的物流运输群组、城市公交车群组、出租车群组等。鉴于车辆群组的目的地或行驶路线的相似性，以及车队管理的需要，网络中车辆群组节点具有群移动的特性。但现有的车辆机会路由协议常常忽略了该特点，导致协议在群组移动场景下的性能下降。本文针对MaxProp协议进行了改进，提出了一种基于群特性的MaxProp协议。

图5 群组外节点与群组内节点相遇示意图

if (节点i或j中，有且仅有一个属于某一群组){

使用HashMap做路由映射;

按着HashMap取出群组内成员;

更新所有群组的所有相遇概率统计;

计算消息开销;

}

else{

只更新相遇两节点的相遇概率统计;

使用Dijkstra计算消息开销;

}

第一，利用群组内的节点之间良好的连通性，将其它群组内节点也列入了开销较小的备选节点之内。这样，外部节点，如节点M，在使用Dijkstra算法寻找路径时，也会将这些组内其它节点考虑在内。其结果是，可利用的节点将会变多，且该节点与群组内的成员节点之间的路径开销将会减少，经过或到达这些节点的消息排序将会上升。

第二，由于在软件实现的时候，节点增加了群组属性，所以按照这样的更新方式，可以认为更新的是节点与“整个”群组相遇的概率统计。

3 实验仿真

最后，本文在网络仿真平台ONE[20]下，对改进后的MaxProp路由协议进行性能测试，并与原协议和其它几种经典的机会路由协议进行对比。实验场景设置如下：导入矩形区域大小的地图文件后，所有车辆节点被分为两组，并限制在地图中的道路上移动。具体地，组1内的15个成员节点均采用群组移动模型行驶[21]，组2内的30个成员节点没有群移动特性，均采用基于地图文件的最短路径移动模型行驶。

如图6所示，在ONE仿真平台下，节点比较密集的区域就是群组移动的节点，组编号为t，组成员之间的距离d设定为100m。协议运行时，消息的产生间隔为25～35s，通信范围r分别为{150,170,190,220,240}。发送节点设定为群组移动节点，目的节点设为群组外节点。

由于现实生活中，常常遇到高架道路的上层车流密度较高，但速度不快，形成了群组移动模式；而下层道路车速高，车流量少，没有群组移动特征的情况。为此，本实验环境设置兼顾了高架道路的应用场景，可模拟上层车辆与下层车辆之间的通信，更具有实际意义。在上述实验环境下，本文主要选择消息传输成功率、网络开销比两个参数，作为路由协议性能的评估指标。实验结果分别如图7和图8所示。

图7 传输成功率与通信范围

图8 网络中的开销比与通信范围

图8给出了网络中的开销比与节点通信范围的关系变化曲线(其中，开销比=网络中传输的消息总数/传输成功的消息总数)。由图8可知，除SprayandWait协议外，改进后的MaxProp路由协议占用网络开销比最少。因为改进后的MaxProp路由协议，利用车辆节点的群移动性选择转发节点，消息传输目的性更强，从而降低了整体网络开销。而Epidemic路由协议在传输数据包时比较盲目，需要占用更多的网络资源；其它协议仅仅采用了一些计算路径的算法，只能降低一部分不必要的消息传输开销。SprayandWait协议在消息扩散后，直接进入等待状态，网络开销极少(开销比在4左右，其它协议均大于100)。

综上所述，经过改进后的MaxProp协议在群组移动模型下能获得较高的消息传输成功率，并通过较低的网络开销完成消息传输，修正了原协议在群组移动模型下的不完善之处，改进了其主要性能。

4 结 语

针对车载传感网中节点的群组移动特性，本文提出了一种基于群特性的MaxProp改进路由协议。该协议利用群组内成员节点之间极好的连通性，通过群内消息扩散，间接提高群内节点与群外节点之间的相遇概率，从而增加了消息转发机会。最后，借助网络仿真平台ONE，将基于群特性的MaxProp路由协议，与原协议和其他几种经典的机会路由协议进行对比，实验结果表明，改进后的MaxProp路由协议能通过较低的网络传输开销，获得较高的消息传输成功率，进而弥补了原有协议在群组移动应用场景下的不足。

[1]PottySP,JoseS.Decisionfusioninvehicularsensornetworksforintelligenttrafficmanagement[C]//InternationalConferenceonControl,Instrumentation,CommunicationandComputationalTechnologies.IEEE,2014:394-401.

[2]DimitrakopoulosG,BravosG,NikolaidouM,etal.Proactive,knowledge-basedintelligenttransportationsystembasedonvehicularsensornetworks[J].IetIntelligentTransportSystems,2013,7(4):454-463.

[3]ChenLW,PengYH,TsengYC.AnInfrastructure-lessFrameworkforPreventingRear-EndCollisionsbyVehicularSensorNetworks[J].IEEECommunicationsLetters,2011,15(3):358-360.

[4]MednisA,ElstsA,SelavoL.Embeddedsolutionforroadconditionmonitoringusingvehicularsensornetworks[C]//InternationalConferenceonApplicationofInformationandCommunicationTechnologies.IEEE,2012:1-5.

[5]ReshiAA,ShafiS,KumaravelA.VehNode:WirelessSensorNetworkplatformforautomobilepollutioncontrol[C]//IEEEConferenceonInformation&CommunicationTechnologies,2013:963-966.

[6]ZhangL,GaoD,FohCH,etal.ASurveyofAbnormalTrafficInformationDetectionandTransmissionMechanismsinVSNs[J].InternationalJournalofDistributedSensorNetworks,2014,10(2014):1-13.

[7] 李蓉,宋飞,张琳娟.基于VANET叫车系统的路由算法研究[J].计算机应用与软件,2015,32(5):153-156.

[8] 李旭.车载传感器网络的应用及关键技术研究[D].上海:上海交通大学,2009.

[9]FernandezJA,BorriesK,ChengL,etal.Performanceofthe802.11pPhysicalLayerinVehicle-to-VehicleEnvironments[J].IEEETransactionsonVehicularTechnology,2012,61(1):3-14.

[10]BazziA,MasiniBM,ZanellaA,etal.Vehicle-to-vehicleandvehicle-to-roadsidemulti-hopcommunicationsforvehicularsensornetworks:Simulationsandfieldtrial[C]//IEEEInternationalConferenceonCommunicationsWorkshops.IEEE,2013:515-520.

[11]FriesenM,JacobR,GrestoniP,etal.VehicularTrafficMonitoringUsingBluetoothScanningOveraWirelessSensorNetwork[J].CanadianJournalofElectrical&ComputerEngineering,2014,37(3):135-144.

[12]ZhangL,GaoD,ZhangS.Areliableandlightweightopportunisticroutingprotocolforinter-regiondatagatheringinVSNs[C]//WirelessandOpticalCommunicationConference,2013:399-404.

[13]VahdatA,BeckerD.Epidemicroutingforpartiallyconnectedadhocnetworks[R].TechnicalReportCS-2000-6,DepartmentofComputerScience,DukeUniversity,2000.

[14]LimKW,JungWS,KoYB.Multi-HopDataDisseminationwithReplicasinVehicularSensorNetworks[C]//VehicularTechnologyConference,2008.VTCSpring2008.IEEE.IEEE,2008:3062-3066.

[15]SpyropoulosT,PsounisK,RaghavendraCS.Sprayandwait:anefficientroutingschemeforintermittentlyconnectedmobilenetworks[C]//ACMSIGCOMMWorkshoponDelay-TolerantNETWORKING.ACM,2005:252-259.

[16]LindgrenA,DoriaA,SchelenO.MobiHocPoster:Probabilisticroutingprotocolinintermittentlyconnectednetworks[J].ACMSIGMOBILEMobileComputingandCommunicationsReview,2003,7(3):19-20.

[17]BurgessJ,GallagherB,JensenD.MaxProp:RoutingforVehicle-BasedDisruption-TolerantNetworks[C]//Proceedings-IEEEINFOCOM,2006,6:1-11.

[18] Tong H,Wu X,Zheng J.A destination information based probabilistic routing protocol for vehicular sensor networks[C]//IEEE International Conference on Communications.IEEE,2013:1419-1423.

[19] Wang N,Sun Z,Cruickshank H.A Reliable and Efficient Encounter-Based Routing Framework for Delay/Disruption Tolerant Networks[J].IEEE Journal of Sensors,2015,15(7):4004-4018.

[20] Keranen A,Ott J,Karkkainen T.The ONE simulator for DTN protocol evaluation[C]//International Conference on Simulation TOOLS and Techniques for Communications,Networks and Systems,Simutools 2009,Rome,Italy,March,2009.

[21] 彭辉,沈林成.一种Ad Hoc网络群组移动模型[J].软件学报,2008,19(11):2999-3010.

IMPROVEMENT OF MAXPROP ROUTING PROTOCOL BASED ON
GROUP FEATURES IN VSNS

Wang Xueli1Zhang Linjuan2Zhang Di1

1(ChifengUniversity,Chifeng024000,InnerMongolia,China)2(StateGridHenanEconomicResearchInstitute,Zhengzhou450052,Henan,China)

The main problem of information transmission in VSNs is intermittent network connectivity and highly dynamic topology. In the past we often used the idea of forwarding the design of routing protocols to solve this problem. However, the existing opportunistic routing protocol ignores the features of some nodes in the network with group mobility, which leads to a sharp decrease of the performance of the protocol in the group moving scene. To solve this problem, a MaxProp routing protocol based on group features is proposed by improving the maximum probability of encounter. This protocol increases the message forwarding opportunities by increasing the probability of encounter between the nodes in the group and the external nodes indirectly through the inter-group message diffusion by using the excellent connectivity among the members of the group. In the ONE simulation platform, compared with other several classical opportunistic routing protocols, the improved MaxProp routing protocol has a significant improvement in message transmission success rate and network overhead ratio.

Vehicular sensor networks Opportunistic forwarding MaxProp routing Group mobility

2016-05-26。内蒙古自治区自然科学基金项目(2013MS0916)。王雪丽，讲师，主研领域：物联网。张琳娟，博士。张迪，讲师。

TP3

A

10.3969/j.issn.1000-386x.2017.05.044