CN105722176A - 城市场景中有基础设施的车联网大规模异构网络的连通性方法 - Google Patents

Abstract

一种城市场景中有基础设施的车联网大规模异构网络的连通性方法，步骤一、路口网关基于相邻的交叉路口建立向目标车辆的转发路径，即为主干路网。基于在源车辆与目标车辆之间所有可能的主干路网，路口网关将依次应用车联网连通性模型，计算比较各主干路网的连通可能性，从中选择连通可能性最大的主干路网作为转发路径，计算转发路径的流程如算法1所示。步骤二、当源车辆收到路口网关发回的用主干路网表示的转发路径后，就开始进行数据分组的转发，算法2具体描述数据分组的转发过程。本发明能够满足上层应用的服务质量要求，利用遗传算法求解该连通性模型的近似最优解，以期快速找到满足应用程序需求的转发路径。

Description

城市场景中有基础设施的车联网大规模异构网络的连通性方法

技术领域

本发明涉及车联网技术领域。

背景技术

在新型车联网大规模网络体系中，如何实时构建互联互通网络，保持稳定状态为应用层提供实时数据，从而支撑应用层智能化服务，是车联网大规模网络动态演化机制研究所面临的一个难点。

目前在车辆自组织网络VANET中，研究人员对路由维护进行了相关研究，取得了一定成果，主要表现在VANET的三类路由协议上，包括单播(Unicast)，地理组播(Geocast)和广播(Broadcast)路由，具体总结如图1所示。单播路由又可以根据其所需要的信息类型分为四类，如图1右半部分所示。第一类是传统的基于拓扑的路由协议(Topology-basedroutingprotocol)，第二类是基于位置的路由协议(Positionbasedroutingprotocol)，第三类是基于地图的路由协议(Mapbasedroutingprotocol)，第四类是基于路径的路由协议(Path-basedroutingprotocol)。

早期自组织网络的路由协议都属于基于拓扑的路由协议。在该类协议中，网络中源节点通过路由表建立到目的节点的连通路径并发送数据。目的序列距离矢量路由(DestinationSequencedDistanceVectorRouting,DSDV)[1]协议的思想是每个节点都必须时时维护一张完整的路由表。但是在网络拓扑频繁变化的VANET中，由于维护和更新路由信息的开销太大，且路由信息生命周期非常短，DSDV并不适合VANET。源路由协议(DynamicSourceRouting,DSR)[2]协议基于源路由发现机制，通过消除表驱动方式所需要的周期性表更新消息，限制网络控制报文的大小，大大减少无线网络带宽的开销，并有效避免网络中大规模路由更新，有效提高实际传输效率。但是，全网范围内的洪泛路由方式还是导致网络负载开销非常大。Adhoc按需距离矢量(Ad-hocOnDemandDistanceVector,AODV)[3]协议结合了DSR算法和DSDV算法优点，每个节点不需要或者只维护部分路由表，数据包头部不需要携带路径信息，需要连接网络的节点通过广播发送连接请求，其他节点转发该消息，并记录它们是从哪个节点接收到这个消息，并往回创建临时路由到发起请求的节点。它的缺点在于：首先，节点保存的路由表不存在候选路径；其次，仅适用于双向传输信道的网络环境；再次，采用的“超时删除”路由机制，容易造成尚未失效的路由在超过生命周期后被删除。文献[4]在基于合作机制的VANET网络中，考虑合作机制产生的通信增益来计算链路发送时延，综合链路冲突数和发送时延作为路由判据，设计了MCCM(Multi-ChannelContention-awareCooperativeMetirc)，将其替代AODV中以跳数作为路由判断依据，设计了一种分布式路由选择协议MCCR(Multi-ChannelContention-awareCooperativeRouting)。总之，在这类协议中，网络节点无论是否有通信需求都需要维护全部或者部分路由信息，而VANET中高速移动的车辆节点和频繁变化的拓扑结构，将会导致这类协议无法发挥其作用。

于是，人们提出了基于位置的路由协议，依靠车辆节点定位系统获得路由和传输数据。装有定位装置的车辆节点周期性地广播本节点的位置信息，车辆终端接收其通信半径范围内一跳节点的位置信息，即路由建立仅仅通过维护单跳拓扑信息完成。源节点与目的节点的传输过程只需要知道下一跳节点和目的节点地理位置，且在数据传输中不需要节点保存和更新路由信息。所以其更能适应网络大小和拓扑结构都在频繁变化的VANET。贪婪边缘无状态路由协议(GreedyPerimeterStatelessRouting，GPSR)[5]，通过路由节点位置和数据包的目的地址来进行数据转发。GPSR协议利用贪婪转发模式(GreedyForwardingMode)进行数据包的传输，当其失效时启用周边转发模式(PerimeterForwardMode)，并在链路状态正常后恢复贪婪转发方式，直至目的节点收到源节点的数据包。然而GPSR在寻找下一跳节点时仅仅根据直线距离，并没有考虑到城市场景中道路、路口、建筑物等的实际影响，因此它并不适用于城市道路场景。贪婪边缘协调路由协议(GreedyPerimeterCoordinatorRouting，GPCR)[6]协议则对GPSR协议进行了改进，使其更适用于复杂的城市场景。它主要考虑了街道的路口部分，将数据包选择传送方向的功能限制在街道路口的车辆，在发现交叉路口存在转发方向的节点时，不用贪婪转发算法而是将数据包直接转发送给该节点，否则仍然使用贪婪转发方式。文献[7]提出了一种适用于城市场景VANET的路由算法，通过采用定时器的竞争转发策略选择合适的下一跳节点，计时器的超时时长和本节点地理位置上的优秀程度成反比。在岔路口区域利用Dijkstra算法进行下一个岔路口的选择，优先选择物理长度小车辆密度大的街道，其与带有缓存的GPSR和PBRP协议的仿真对比中具有更高的数据包递交率和较低的数据延迟。文献[8]提出了基于交叉路口的地理路由协议(Intersection-basedGeographicalRoutingProtocol,IGRP)，以解决城市场景中VANET的QoS路由问题，在计算量上优于GPSR和GPCR。

目前的研究热点集中在基于地图的路由协议。地理源路由协议(GeographicSourceRouting)[9]根据转发路径转发数据包，该路径基于坐标位置和在地图上的位置计算而来，但不能解决车辆密度太低导致的稀疏连接问题。文献[10]提出地理无状态VANET路由(GeographicStatelessVANETRouting,GeoSVR)，通过将节点位置与数字地图和一种改进的限制转发算法相结合，克服不可靠的无线信道问题。文献[11]提出了一种DRES(DistributedReal-timedelayEvaluationScheme)机制，用于车辆获取实时性的网络延时信息，并设计了一种采用携带转发机制的基于分布式实时信息的VANET路由协议。该协议采用源选径的路由方式，车辆根据对各道路网络延时的估计，采用Dijkstra算法在电子地图上计算出数据传递延时最短的转发路径。文献[12]提出了基于道路使用车辆交通的(Road-BasedusingVehicularTraffic,RBVT)路由协议，该协议采集实时车辆交通信息，创建由较高网络连接概率的连接道路交叉口组成的路径。

车辆辅助数据传输协议(Vehicle-AssistedDataDelivery,VADD)采用了携带转发机制[13]，利用可预测的车辆移动性来计算数据包传送的延迟，找到接下来转发数据包的道路。位置优先探查(LocationFirstProbe,L-VADD)、方向优先探查(DirectionFirstProbe,D-VADD)和混合式VADD(H-VADD)等三种不同的转发协议可以用来选择最优路径。

地理组播路由(Geocastrouting)[14]本质上是一个基于位置的多播路由，其目标是从源节点将数据包传送到一个指定的地理区域中的所有其他节点，称为关联区，很多VANET应用程序可以从中受益。文献[15]提出了车间地理组播协议(Inter-VehiclesGeocastprotocol,IVG)，广播报警信息给高速公路上所有基于延迟时间算法的危险区域中的车辆。文献[16]提出了一个分布式鲁棒的地理组播协议，用于车间通信，它的目标是将数据包传送到位于特定的静态地理区域的车辆，车辆仅根据其目前的位置接收或丢弃数据包。

文献[17]在分区的公路上基于地理路由提出了一个紧急广播协议BROADCOMM，安装在汽车上的传感器不断地收集重要信息，检测到任何紧急情况将直接触发广播，该协议在消息广播时延和路由开销方面优于类似的基于泛洪的路由协议。城市多跳广播协议(UrbanMulti-HopBroadcastprotocol,UMB)[18]是为了解决广播风暴、隐藏节点和市区多跳广播的可能性问题，发送方节点在没有任何先验拓扑信息的情况下，尽量选择广播方向上最远的节点来进行转发并应答数据包，当该消息传播的路径上有交叉口时，由位于交叉口的中继器初始化新的定向广播。文献[19]提出了VANET中多跳广播路由协议DV-CAST，同时适用于密集和稀疏的交通场景。

针对目前主要集中在VANET路由协议上的研究，从路由类型、转发策略、恢复策略、路径维护以及适用场景等方面进行了具体比较，如表1所示。

表1VANET相关路由协议比较结果

从现有国内外研究现状分析，目前车联网路由协议主要针对同一种无线接入手段的车对车(V2V)通信，并不能适应如今应用的需求。

参考文献：

[1]PerkinsCE，BhagwatP.HighlydynamicDestination-SequencedDistance-Vectorrouting(DSDV)formobilecomputers.in：NewYork,NY,USA：ACM，1994：234～244.

[2]JohnsonD，MaltzD.DynamicSourceRoutinginAdHocWirelessNetworks.in：IMIELINSKIT，KORTHH.MobileComputing.SpringerUS，1996，353：153～181.

[3]PerkinsCE，RoyerEM.Ad-hocon-demanddistancevectorrouting.in：1999：90～100.

[4]揭志忠，黄传河，韩亚辉，等.VANET中一种分布式路由协议MCCR.湖南大学学报(自然科学版)，2012，39(11)：93～98.

[5]KarpB，KungHT.GPSR:greedyperimeterstatelessroutingforwirelessnetworks.in：NewYork,NY,USA：ACM，2000：243～254.

[6]LochertC，MauveM，FüβlerH，etal.Geographicroutingincityscenarios.SIGMOBILEMob.Comput.Commun.Rev.，2005，9(1)：69～72.

[7]李元振，廖建新，李彤红，等.一种基于竞争转发的城市场景车载AdHoc网络路由算法.电子学报，2009，37(12)：2639～2645.

[8]SaleetH，LangarR，NaikK，etal.Intersection-BasedGeographicalRoutingProtocolforVANETs:AProposalandAnalysis.IEEETransactionsonVehicularTechnology，2011，60(9)：4560～4574.

[9]LochertC，HartensteinH，TianJ，etal.Aroutingstrategyforvehicularadhocnetworksincityenvironments.in：2003：156～161.

[10]XiangY，LiuZ，LiuR，etal.GeoSVR:Amap-basedstatelessVANETrouting.AdHocNetworks，2013，11(7)：2125～2135.

[11]宋超，刘明，龚海刚，等.基于分布式实时信息的车载网络路由协议.软件学报，2011，22(3)：466～480.

[12]NzouontaJ，RajgureN，WangG，etal.VANETRoutingonCityRoadsUsingReal-TimeVehicularTrafficInformation.IEEETransactionsonVehicularTechnology，2009，58(7)：3609～3626.

[13]ZhaoJ，CaoG.VADD:Vehicle-AssistedDataDeliveryinVehicularAdHocNetworks.IEEETransactionsonVehicularTechnology，2008，57(3)：1910～1922.

[14]MaihoferC.Asurveyofgeocastroutingprotocols.IEEECommunicationsSurveysTutorials，2004，6(2)：32～42.

[15]BachirA，BenslimaneA.Amulticastprotocolinadhocnetworksinter-vehiclegeocast.in：2003，4：2456～2460vol.4.

[16]KihlM，SichitiuM，JoshiHP.Designandevaluationoftwogeocastprotocolsforvehicularad-hocnetworks.JournalofInternetEngineering，2008，2(1).

[17]DurresiM，DurresiA，BarolliL.EmergencyBroadcastProtocolforInter-VehicleCommunications.in：2005，2：402～406.

[18]KorkmazG，EkiciE，F，etal.UrbanMulti-hopBroadcastProtocolforInter-vehicleCommunicationSystems.in：NewYork,NY,USA：ACM，2004：76～85.

[19]TonguzO，WisitpongphanN，BaiF，etal.BroadcastinginVANET.in：2007：7～12.

[20]SaleetH，BasirO，LangarR，etal.Region-BasedLocation-Service-ManagementProtocolforVANETs.IEEETransactionsonVehicularTechnology，2010，59(2)：917～931.

发明内容

本发明目的在于克服现有技术的不足，公开一种城市场景中有基础设施的车联网大规模异构网络的连通性方法，如此，更好的支撑车联网应用发展，适用于未来车联网智能服务所需要的连通性。

本发明给出的技术方案为：

一种城市场景中有基础设施的车联网大规模异构网络的连通性方法，为了实现车联网的连通，源车辆需要知道数据包转发到目标车辆的转发路径，这一信息由路口网关提供，路口网关时时掌握本地路口的网络拓扑结构，路口网关作为位置服务器，负责保存在其附近的所有的车辆的当前位置信息，

其特征在于，

步骤一、

采用基于区域的位置服务管理协议为连通性方法提供位置管理服务，每辆车每次相比原来的位置移动超过传输范围时就向最近的路口网关报告其位置信息，这一信息包括车辆ID、车辆的传输范围Tr、车辆所在位置的横坐标与纵坐标、上次更新的时间、以及车辆运动的速度和方向，根据这些位置信息，路口网关随时根据需要构建一条源车辆到目标车辆之间的转发路径，

路口网关基于相邻的交叉路口建立向目标车辆的转发路径，即为主干路网。所述主干路网可以用交叉路口的编号序列表示：

路口网关IG_s在收到源车辆v_s发出的到目标车辆v_d的转发路径请求时计算转发路径的流程如算法1所示，

基于在源车辆与目标车辆之间所有可能的主干路网，路口网关将依次应用车联网连通性模型，计算比较各主干路网的连通可能性，从中选择连通可能性最大的主干路网作为转发路径，同时保证主干路网的其他连通性质不超过源车辆中应用程序给出的阈值(第3～8行)；路口网关所选的主干路网将被发送到源车辆，存储在数据分组报头中，使得中间车辆在路口之间转发数据包，

步骤二、

当源车辆收到路口网关发回的用主干路网表示的转发路径后，就开始进行数据分组的转发，算法2具体描述数据分组的转发过程:

当车辆朝着某一路口行驶时，它基于贪婪转发策略选择下一跳，即最接近主干路网中下一个交叉路口的车辆，

当移动车辆已接近路口，它会根据贪婪转发策略选择最接近下一个路口，即主干路网中的下一跳的车辆(第2行)，

当确实在通信范围内没有可供转发的下一跳车辆时，转发模式切换为携带转发模式(第9～22行)，

此时首先判断当前车辆的携带缓存是否还有空间暂时存储这一数据报文，如果没有就只能立即丢弃这一个数据分组了，

在满足携带转发的条件后，当前中继车辆开始携带该数据分组，同时每隔一段时间重新尝试进行转发；

从属技术方案2：

当每组目标路口相同，同时有相同应用程序需求并且都位于彼此附近的车辆计算并缓存最优主干路网，采用算法3所示：

每辆车在开始发送消息之前，会首先向周围车辆广播查询到目标车辆的最优主干路网(第4～9行)，如果周围车辆有所需的信息，它们将被发送回源车辆，否则，查询将被中继到路口网关根据应用的需求来计算最佳主干路网(第10～21行)

从属技术方案3：

路口网关也可以作为主干路网中的中继车辆转发数据，源车辆向目标车辆车发送消息，但源车辆的传输无法覆盖到目标车辆，并且两辆车是沿着相反方向行驶的，此时，近距离路口网关会将自身作为中继车辆的建议回复给源车辆，由源车辆将数据发送给近距离路口网关，再由其转发给目标车辆，在这一个过程中，近距离路口网关充当了固定中继车辆的作用。

从属技术方案4：

路口网关通过求解连通性模型决定在其附近的车辆发出的数据包所使用的主干路网，

采用遗传算法：

编码时，将主干路网中每个交叉路口定义为基因。主干路网中包含了所选各个交叉路口的编号。然后，一条路径中的有序交叉路口可以表示为一条染色体。每一个可行解y包含一条染色体，其被表示为v₁,v₂,...,v_m。因此，一条染色体是一个包含有序交叉路口的向量。

遗传搜索从一组解的初始种群开始。最初的种群是由随机选择可行解生成的。每个解起始于与源车辆相邻的交叉路口。下一个基因从相邻路口随机选择构造而成。然后，继续在主干路网中随机选择下一个相邻路口，直到下一个路口与目标车辆相邻为止。为了确保该解是可行的，它必须满足下列两个条件：i)路径中每两个连续的路口都是由一条道路连接。ii)主干路网的连通的性质满足约束。继续执行这一过程，直到产生了一定数量的主干路网构成种群，这一数量称为种群规模p_z。

目标是(1)式中的连通可能性最大化，适应度函数f(y)的定义如下：

f(y)＝P_c(y)(1)

选择运算采用轮盘赌选择策略。其中，主干路网被选中的概率于主干路网的归一化适应度值成正比，即选择某条主干路网y的概率等于

其中p_z是备选的主干路网数量。

交叉运算采用单点交叉，即从当前种群中选择两条主干路网，然后随机地选择一个共同的中间路口，称为交叉点。然后，它交换交叉点的后半部分主干路网，以形成两个新的后代。

突变运算采用了均匀变异运算符，即以相同概率从种群中选择任意个体后，随机地挑选中间基因(路口)，然后随机选择相邻的路口。

随后验证新个体是否为可行解是非常重要的，最后使用世代的最大数目作为为终止标准。

本发明的连通性方法是指为了解决车联网中互联互通问题的技术方法。本发明提出的城市场景中有基础设施的车联网大规模异构网络的连通性方法能够满足上层应用的服务质量要求。

本发明利用遗传算法求解该连通性模型的近似最优解，以期快速找到满足应用程序需求的转发路径。

附图说明

图1VANET路由协议分类。

图2路口网关构成主干路网。

图3是绿色轿车至红色轿车的转发路径。

图4是路口网关参与转发。

图5是对交叉路口进行编号的抽象路网图。

图6是单点交叉运算符(a)两条主干路网以8为交叉点(b)两条新的后代。

图7是均匀变异运算符(a)主干路网以2为突变点(b)新的后代。

G表示绿色轿车，R表示红色轿车，Y表示黄色轿车。

具体实施方式

以下结合附图对本发明技术方案做进一步说明。

连通性方法是指为了解决车联网中互联互通问题的技术方法。本发明提出的城市场景中有基础设施的车联网大规模异构网络的连通性方法，能够在满足上层应用的服务质量要求的前提下，选择合适的连通策略，包括决定采用何种通信接口，具体的转发路径和转发方式(立即转发或携带转发)。

本发明连通性方法的基本思想

为了实现车联网的连通，源车辆需要知道数据包转发到目标车辆的转发路径，这一信息由路口网关提供。路口网关时时掌握本地路口的网络拓扑结构。路口网关作为位置服务器，负责保存在其附近的所有的车辆的当前位置信息。本发明采用基于区域的位置服务管理协议(Region-BasedLocation-Service-ManagementProtocol，RLSMP)[20]为连通性方法提供位置管理服务。具体来说，每辆车每次相比原来的位置移动超过一个传输范围时就向最近的路口网关报告其位置信息。这一信息包括车辆ID，车辆的传输范围Tr，车辆所在位置的横坐标与纵坐标，上次更新的时间，以及车辆运动的速度和方向。

根据这些位置信息，路口网关可以随时根据需要构建一条源车辆到目标车辆之间的转发路径。但是这些转发路径中间通常包括移动中的车辆，由于车辆的移动性，转发路径是不稳定的。为了提高其稳定性，路口网关基于相邻的交叉路口建立向目标车辆的转发路径，即主干路网。所述主干路网可以用交叉路口的编号序列表示，例如在图2中从路口A到路口F有三条可行的主干路网：A-B-D-F、A-C-D-F和A-C-E-F。

路口网关IG_s在收到源车辆v_s发出的到目标车辆v_d的转发路径请求时计算转发路径的流程如算法1所示。基于在源车辆与目标车辆之间所有可能的主干路网，路口网关将依次应用车联网连通性模型，计算比较各主干路网的连通可能性，从中选择连通可能性最大的主干路网作为转发路径，同时保证主干路网的其他连通性质不超过源车辆中应用程序给出的阈值(第3～8行)。路口网关所选的主干路网将被发送到源车辆，存储在数据分组报头中，使得中间车辆在路口之间转发数据包。

当源车辆收到路口网关发回的用主干路网表示的转发路径后，就开始进行数据分组的转发。算法2具体描述数据分组的转发过程。当车辆朝着某一路口行驶时，它基于贪婪转发策略选择下一跳，即最接近主干路网中下一个交叉路口的车辆。当移动车辆已接近路口，它会根据贪婪转发策略选择最接近下一个路口(即主干路网中的下一跳)的车辆(第2行)。需要注意的是“下一个路口”对中继车辆来说是已知的，因为如前所述，这些信息是存储在所接收的数据分组报头内的。在这一方法中，主干路网是由路口网关选择的连通可能性最高的转发路径，因此发现向“下一路口”的中继移动车辆的概率是很高的。当确实在通信范围内没有可供转发的下一跳车辆时，转发模式切换为携带转发模式(第9～22行)。此时首先判断当前车辆的携带缓存是否还有空间暂时存储这一数据报文，如果没有就只能立即丢弃这一个数据分组了。另外为了防止由于长时间无法发送报文导致缓存被长期占用，当尝试转发的次数超过某个阈值时也立即丢弃该数据分组。在满足携带转发的条件后，当前中继车辆开始携带该数据分组，同时每隔一段时间重新尝试进行转发。

为了能更好的在大规模车联网这样的高度动态环境中满足应用程序多种多样的需求，考虑到路口网关的计算能力毕竟是有限的，应该避免单独为每辆车计算合适的主干路网。因此本算法3为每组目标路口相同，同时有相同应用程序需求并且都位于彼此附近的车辆计算并缓存最优主干路网，如算法3所示。在实际操作中，每辆车在开始发送消息之前，会首先向周围车辆广播查询到目标车辆的最优主干路网(第4～9行)。如果周围车辆有所需的信息，它们将被发送回源车辆。否则，查询将被中继到路口网关根据应用的需求来计算最佳主干路网(第10～21行)。

案例一

为了演示连通性方法的功能，下面给出一个简单的例子，如图3所示。假设绿色轿车往南行驶。为了发送消息给红色轿车，有四条可行的主干路网，即B-D-F、B-D-C-E-F、B-A-C-D-F和B-A-C-E-F。在图中的情况下，路口网关B会选择主干路网B-A-C-E-F，因为它的连通可能性是最高的。事实上，通过这个主干路网转发数据包会比通过其他路径更快，因为其他那些路径中都有一部分链路是断开的。导致慢的主要原因是，车辆如果在转发数据包的过程中碰到断链，该数据包只能由车辆携带继续等待以后的转发机会，显然车辆的移动速度比无线电波的传播速度慢了许多。

在某些情况下，路口网关也可以作为主干路网中的中继车辆转发数据。例如图4中红色轿车准备向黄色轿车发送消息，但红色轿车的传输无法覆盖到黄色轿车，并且两辆车的是沿着相反方向行驶的，携带转发策略也会失效。此时，路口网关C会将自身作为中继车辆的建议回复给红色轿车，由红色轿车将数据发送给路口网关C，再由其转发给黄色车辆。在这一个过程中，路口网关充当了固定中继车辆的作用。考虑到路口网关的数据转发能力也是有限的，并且它主要承担这管理路口周围车辆位置信息和计算反馈最优主干路网的功能，是否启用这一功能需要根据应用程序数据的需求来判断。

尽管有了上述主干路网选择，以及路口网关转发辅助，很显然真实城市场景中一定还是存在无法找到可用的满足应用程序需求的情况。例如源车辆或目标车辆所在的道路车辆密度极低，携带转发策略又无法满足所需传递数据的应用程序的需求或者由于所在道路车辆过于密集，无线电波相互干涉导致连通的不可靠性提高，无法满足一部分应用程序对于服务质量的需求。针对这些情况，传统的同构车联网连通性方法就无能为力了，因为这些方法的设计前提均是在一种非常理想化的场景下，只具备了单一无线网络接入手段。在本发明所提出的城市场景中基于基础设施的车联网大规模异构网络中，车辆不仅可以配备传统的WAVE通信装置，也可以装载支持蜂窝网络通信的终端设备，如4G上网卡等。当WAVE通信无法满足应用需求时，连通性方法可以选择将数据包通过蜂窝网络传输。即本发明方法可以针对数据包进行WAVE和其他通信方式的垂直切换(verticalhandover)。这样一来，就可以充分利用蜂窝网络等无线广域网大覆盖范围的优势，并结合车载通信大吞吐量高实时性的特点，即满足了各类车联网应用的不同需求，又降低了使用蜂窝网络所需的资费。

案例二

路口网关通过求解连通性模型决定在其附近的车辆发出的数据包所使用的主干路网。为了解决这个问题本发明采用遗传算法。

编码方案很自然地是将主干路网中每个交叉路口定义为基因。主干路网中包含了所选各个交叉路口的编号。然后，一条路径中的有序交叉路口可以表示为一条染色体。因此，每一个可行解y包含一条染色体，其被表示为v₁,v₂,...,v_m。例如，图5中路线1-2-3-7-14-20，1-2-8-13-19-20和1-9-12-18-19-20等均为染色体。因此，一条染色体是一个包含有序交叉路口的向量。

遗传搜索从一组解的初始种群开始。最初的种群是由随机选择可行解生成的。每个解起始于与源车辆相邻的交叉路口。下一个基因从相邻路口随机选择构造而成。然后，继续在主干路网中随机选择下一个相邻路口，直到下一个路口与目标车辆相邻为止。为了确保该解是可行的，它必须满足下列两个条件：i)路径中每两个连续的路口都是由一条道路连接。ii)主干路网的连通的性质满足约束。继续执行这一过程，直到产生了一定数量的主干路网构成种群，这一数量称为种群规模p_z。

因为本发明的目标是(1)式中的连通可能性最大化，适应度函数f(y)的定义如下：

f(y)＝P_c(y)(1)

选择运算采用轮盘赌选择策略。其中，主干路网被选中的概率于主干路网的归一化适应度值成正比，即选择某条主干路网y的概率等于

其中p_z是备选的主干路网数量。

交叉运算采用单点交叉，即从当前种群中选择两条主干路网，然后随机地选择一个共同的中间路口，称为交叉点。然后，它交换交叉点的后半部分主干路网，以形成两个新的后代。图6中，(a)表示两个随机选择的主干路网以7为交叉点，图6中，(b)表示出两个新的后代。需要注意的是必须要检查新的个体是否是可行解。

突变运算采用了均匀变异运算符，即以相同概率从种群中选择任意个体后，随机地挑选中间基因(路口)，然后随机选择相邻的路口，如图7所示。

随后验证新个体是否为可行解是非常重要的，最后使用世代的最大数目作为为终止标准。

创新点

创新之一：提出了解决城市场景中有路口基础设施的车联网大规模异构网络连通性问题的方法。本发明的连通性方法是指为了解决车联网中互联互通问题的技术方法。本发明提出的城市场景中有基础设施的车联网大规模异构网络的连通性方法能够满足上层应用的服务质量要求。

创新之二：基于城市场景中有基础设施的车联网动力学规律及其连通性模型，利用遗传算法求解该连通性模型的近似最优解。利用遗传算法这种类型的启发式方法，求解连通性模型，以期快速找到满足应用程序需求的转发路径，并在必要的情况下提供垂直切换使用蜂窝数据网络的决策功能。

Claims (4)

1.一种城市场景中有基础设施的车联网大规模异构网络的连通性方法，为了实现车联网的连通，源车辆需要知道数据包转发到目标车辆的转发路径，这一信息由路口网关提供，路口网关时时掌握本地路口的网络拓扑结构，路口网关作为位置服务器，负责保存在其附近的所有的车辆的当前位置信息，

其特征在于，

步骤一、

采用基于区域的位置服务管理协议为连通性方法提供位置管理服务，每辆车每次相比原来的位置移动超过传输范围时就向最近的路口网关报告其位置信息，这一信息包括车辆ID、车辆的传输范围Tr、车辆所在位置的横坐标与纵坐标、上次更新的时间、以及车辆运动的速度和方向，根据这些位置信息，路口网关随时根据需要构建一条源车辆到目标车辆之间的转发路径，

路口网关基于相邻的交叉路口建立向目标车辆的转发路径，即为主干路网。所述主干路网可以用交叉路口的编号序列表示：

路口网关IG_s在收到源车辆v_s发出的到目标车辆v_d的转发路径请求时计算转发路径的流程如算法1所示，

基于在源车辆与目标车辆之间所有可能的主干路网，路口网关将依次应用车联网连通性模型，计算比较各主干路网的连通可能性，从中选择连通可能性最大的主干路网作为转发路径，同时保证主干路网的其他连通性质不超过源车辆中应用程序给出的阈值(第3～8行)；路口网关所选的主干路网将被发送到源车辆，存储在数据分组报头中，使得中间车辆在路口之间转发数据包，

步骤二、

当源车辆收到路口网关发回的用主干路网表示的转发路径后，就开始进行数据分组的转发，算法2具体描述数据分组的转发过程:

当车辆朝着某一路口行驶时，它基于贪婪转发策略选择下一跳，即最接近主干路网中下一个交叉路口的车辆，

当移动车辆已接近路口，它会根据贪婪转发策略选择最接近下一个路口，即主干路网中的下一跳的车辆(第2行)，

当确实在通信范围内没有可供转发的下一跳车辆时，转发模式切换为携带转发模式(第9～22行)，

此时首先判断当前车辆的携带缓存是否还有空间暂时存储这一数据报文，如果没有就只能立即丢弃这一个数据分组了，

在满足携带转发的条件后，当前中继车辆开始携带该数据分组，同时每隔一段时间重新尝试进行转发；

2.如权利要求1所述的一种城市场景中有基础设施的车联网大规模异构网络的连通性方法，其特征在于，当每组目标路口相同，同时有相同应用程序需求并且都位于彼此附近的车辆计算并缓存最优主干路网，采用算法3所示：

每辆车在开始发送消息之前，会首先向周围车辆广播查询到目标车辆的最优主干路网(第4～9行)，如果周围车辆有所需的信息，它们将被发送回源车辆，否则，查询将被中继到路口网关根据应用的需求来计算最佳主干路网(第10～21行)

3.如权利要求1所述的一种城市场景中有基础设施的车联网大规模异构网络的连通性方法，其特征在于，路口网关也可以作为主干路网中的中继车辆转发数据，源车辆向目标车辆车发送消息，但源车辆的传输无法覆盖到目标车辆，并且两辆车是沿着相反方向行驶的，此时，近距离路口网关会将自身作为中继车辆的建议回复给源车辆，由源车辆将数据发送给近距离路口网关，再由其转发给目标车辆，在这一个过程中，近距离路口网关充当了固定中继车辆的作用。

4.如权利要求1所述的一种城市场景中有基础设施的车联网大规模异构网络的连通性方法，其特征在于，路口网关通过求解连通性模型决定在其附近的车辆发出的数据包所使用的主干路网，

采用遗传算法：

编码时，将主干路网中每个交叉路口定义为基因。主干路网中包含了所选各个交叉路口的编号。然后，一条路径中的有序交叉路口可以表示为一条染色体。每一个可行解y包含一条染色体，其被表示为v₁,v₂,...,v_m。因此，一条染色体是一个包含有序交叉路口的向量。

遗传搜索从一组解的初始种群开始。最初的种群是由随机选择可行解生成的。每个解起始于与源车辆相邻的交叉路口。下一个基因从相邻路口随机选择构造而成。然后，继续在主干路网中随机选择下一个相邻路口，直到下一个路口与目标车辆相邻为止。为了确保该解是可行的，它必须满足下列两个条件：i)路径中每两个连续的路口都是由一条道路连接。ii)主干路网的连通的性质满足约束。继续执行这一过程，直到产生了一定数量的主干路网构成种群，这一数量称为种群规模p_z。

目标是(1)式中的连通可能性最大化，适应度函数f(y)的定义如下：

f(y)＝P_c(y)(1)

其中Pc是主干路网的连通可能性。

选择运算采用轮盘赌选择策略。其中，主干路网被选中的概率于主干路网的归一化适应度值成正比，即选择某条主干路网y的概率等于

其中p_z是备选的主干路网数量。

交叉运算采用单点交叉，即从当前种群中选择两条主干路网，然后随机地选择一个共同的中间路口，称为交叉点。然后，它交换交叉点的后半部分主干路网，以形成两个新的后代。

突变运算采用了均匀变异运算符，即以相同概率从种群中选择任意个体后，随机地挑选中间基因(路口)，然后随机选择相邻的路口。

随后验证新个体是否为可行解是非常重要的，最后使用世代的最大数目作为为终止标准。