CN106535282A - 车载自组织网络中基于遗传算法的QoS感知路由协议 - Google Patents

Abstract

本发明的车载自组织网络中基于遗传算法的QoS感知路由协议，所述协议包括如下步骤：1）将道路进行分块，分析连通性模型和延迟模型，得到路段的平均延迟；2）根据基于十字路口的路由协议探索源点车辆与目的车辆之间的所有可用路径；3）通过以QoS为目标函数的遗传算法对所述所有可用路径进行路由优化，得到最佳路径。有益效果：延迟性能更优，数据包传输性能更好，通信性能更佳。

Description

车载自组织网络中基于遗传算法的QoS感知路由协议

技术领域

本发明属于智能交通系统领域，尤其涉及一种车载自组织网络中基于遗传算法的QoS感知路由协议。

背景技术

VANETs是一种特殊的移动自组织网络(Mobile Ad-Hoc Network,MANET)，智能交通系统(Intelligent Transportation Systems,ITS)的重要部分。VANETs中的车辆沿道路行驶，遵守交通规则；其次，由于道路的多样性以及车辆不同的速度与密度，网络拓扑结构频繁变化；最后，网络中的通信分为两类：车与车通信、车与基础设施通信。路由协议的主要内容分为两类：(1)基于网络拓扑的路由协议根据拓扑信息做出路由决策，但是不断变化的拓扑结构会导致链路的断开；(2)基于地理位置信息的路由协议只需要通过GPS获得车载的位置来做出数据递交的决策；因此相比于基于网络拓扑的路由协议，基于地理位置信息的路由协议更适合于多变的车载自组织网络。但此类协议仍然面临许多挑战，比如不具备实时性与准确性，开销大，应用成本增加等。其中CAR是一种基于连通性感知路由，源点利用广播信息探索路径，最终获得一条固定的路由路径，因此无法应对VANETs快速变化的拓扑结构。IBR协议是一种基于十字路口的路由协议，利用实时信息动态地选择下一跳十字路口，根据车辆方向传输十字路口内数据包，但未考虑道路的连通性，因此可能会导致数据包的丢失。GyTAR是一种利用局部街道动态信息的路由协议，利用车辆密度和前进方向进行路由决策，但是并未考虑全局信息，因此在数据转发过程中可能会导致网络分区。

发明内容

本发明的目的是克服上述背景技术的不足，为了改善VANETs中路由协议的QoS，优化路由路径，提供了一种车载自组织网络中基于遗传算法的QoS感知路由协议，具体由以下方案实现：

车载自组织网络中基于遗传算法的QoS感知路由协议，所述协议包括如下步骤：

1)将任意两个相邻十字路口之间的路段进行分块，分析连通性模型和延迟模型，得到路段的平均延迟；

2)根据基于十字路口的路由协议探索源点车辆与目的车辆之间的所有可用路径；

3)通过以QoS为目标函数的遗传算法对所述所有可用路径进行路由优化，得到最佳路径。

所述车载自组织网络中基于遗传算法的QoS感知路由协议的进一步设计在于，所述步骤1)中对路段进行分块时，将单位块设定为宽为道路宽度、长为aR的矩形块，其中R表示车辆的无线通信传输距离，a为矩形块的长度系数。

所述车载自组织网络中基于遗传算法的QoS感知路由协议的进一步设计在于，所述步骤1)中，所述连通性模型为：设定两个相邻十字路口间同一方向上的任意两个连续车辆之间的距离为X，当X≤R时，车辆之间的链路处于连通状态，直接转发数据包；当X>R时，车辆之间的链路处于断开状态，无法直接转发数据包，若相反方向上处于两辆车之间的移动车辆可进行间接转发数据包，则判定路段上的连通性保持不变。

所述车载自组织网络中基于遗传算法的QoS感知路由协议的进一步设计在于，所述步骤1)中，所述延迟模型为：路段上部分链路连通时，在连通路段上的数据包的传输方向上，数据包所在当前节点会在其传输范围内的所有节点中选择距离自身最远的节点作为下一跳节点，进行贪婪转发，而断开路段上的数据包进行携带转发；路段上的链路全部连通时，数据包通过中继节点之间的贪婪算法进行转发。

所述车载自组织网络中基于遗传算法的QoS感知路由协议的进一步设计在于，所述步骤1)中当路段上的链路全部连通时，通过跳与跳之间的贪婪算法进行数据包的传输，则相邻十字路口i,j之间的传输延迟如式(1)：

D_nc＝H_nc·t_p (1)

其中，表示i,j之间的跳数，t_p表示一跳的传输时间，L表示路段长度；

两个相邻十字路口i,j之间的平均传输延迟如式(2)：

D(i,j)＝D_np·(1-P_c(i,j))+D_nc·P_c(i,j) (2)

其中，P_c(i,j)表示路段的连通概率；

当路段部分连通时，路段的传输延迟为：

其中，d_dp表示链路断开期间数据包传输的平均距离，d_cp表示路段连通期间数据包传输方向上的两个连续车辆之间的预期平均传输距离，v₁为车辆携带数据包传输的传输速度；

链路断开期间，数据包传输的平均距离如式(3)：

式中，E(n)为携带数据包传输时移动距离所对应的块的个数，为与所设定方向相反路段上的无法形成通路的概率，f_X(x)表示所设定方向的道路上的车辆的概率密度函数。

路段连通期间，数据包传输方向上的两个连续车辆之间的预期平均传输距离如式(4)：

d_cp＝d_cp1+d_cp2 (4)

式中，d_cp1为连通链路上的预期平均距离，d_cp2为车辆间链路断开的距离由所述设定方向相反的道路上的车辆修复成功后的平均传输距离。

所述车载自组织网络中基于遗传算法的QoS感知路由协议的进一步设计在于，1)设定两个十字路口I_i和I_j间以设定方向直线行驶的两个连续车辆V_e,V_e+1之间的距离x>R，则链路断开，通过与所述设定方向相反方向道路上的车辆(V_w,V_w+1)修复V_e,V_e+1之间的连通性，所设定的两个相邻十字路口之间的连通性概率如式(5)：

P_c(i,j)＝P_c1+P_c2 (5)

其中，P_c1表示设定方向的路段上至少一条链路断开的情况下的路段连通性概率，如式(6)；P_c2表示所述设定方向上的车辆之间的链路全部处于连通状态时的路段连通性概率，如式(7)：

所述车载自组织网络中基于遗传算法的QoS感知路由协议的进一步设计在于，所述步骤2)中所述路由协议中的车辆配备GPS与导航系统，根据交通状况与地理位置信息预测车辆的移动方向，动态选择下一跳十字路口。

所述车载自组织网络中基于遗传算法的QoS感知路由协议的进一步设计在于，所述遗传算法对所述所有可用路径进行路由优化具体包括如下步骤：

3-1)编码：根据网络路由的特点和遗传算法的编码原则，采用直接编码，即对于一条给定的从源点端点十字路口到目的节点端点十字路口的路径，该路径上的十字路口的编号即为染色体编码，一条编号序列就是一条染色体，即一条路径对应着一个个体；

3-2)设置初始群体：根据基于十字路口的路由协议的路由选择策略，探索到G条路由路径，作为初始群体，规模大小为G；

3-3)进行选择操作：根据适应度函数值，选取对应的适应度函数值最大的个体作为最优个体，构建适应度函数表示如式(8)：

S＝α·P_n+β·(1/D_nth) (8)

其中，P_n表示第n个个体的连通性概率；D_nth表示第n个个体(第n条路径)的平均传输延迟；α和β为加权系数，α,β∈[0,1]。

3-4)进行交叉操作，采用后向交叉交换两个个体中的子路径，在群体中随机选取两个染色体P1、P2作为父代个体，两条路径共同经过的十字路口作为备选的交叉位置，从备选的交叉位置中随机选择作为交叉位置，将交叉位置之后的部分进行交换，形成两个子代个体P1’、P2’；

3-5)变异：在群体中随机选择一个染色体P，在P中随机选择节点ni作为变异节点，在ni的邻居节点集中随机选择节点nj，产生从源点到nj和nj到目的节点的两条路径r1、r2，若r1、r2中存在重复的节点，则放弃此路径，不进行变异，否则连接两条路径形成新的染色体P’，进入下一代；

3-6)重复执行步骤3-3)至步骤3-5)，直到达到迭代次数为止，最终得到最优个体，优化路由路径。

所述车载自组织网络中基于遗传算法的QoS感知路由协议的进一步设计在于，所述步骤3-3)采用最佳策略选择和轮盘赌选择相结合的选择方法：在每对染色体进行交叉之前，先根据适应度值选择最佳个体，取代子代群体中适应度值最差的的个体，直接遗传到子代群体中，其余个体采用轮盘赌法。

本发明的有益效果为：

本发明的基于遗传算法的车载自组织网络路由协议，首先利用基于十字路口的路由协议探索可用路径，并且将道路进行分块研究QoS模型，同时两个相邻十字路口之间，利用贪婪携带-转发算法进行数据包的转发，最后利用遗传算法进行路径优化，寻找最佳路径。其中遗传算法是以目标函数作为搜索信息，根据目标函数变换的适应度函数选择和优化路径，具有并行性，由多个个体组成一个初始群体开始搜索，对群体进行选择、交叉、变异等遗传操作，产生新一代群体，然后继续搜索；同时遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一定的概率进行的，增加了其搜索过程的灵活性。另一方面，经仿真后，仿真结果显示与IBR协议和CAR协议相比，所提出的GABR协议延迟性能更优，数据包传输性能更好，通信性能更佳。

附图说明

图1为城市道路示例图。

图2为路段车辆的分布示意图。

图3为路段车辆的分布示意图(路段部分连通)。

图4为路段车辆的分布示意图(路段全部连通)。

图5为遗传算法的基本模块流程图。

图6为路由协议的主要流程图。

图7为路段平均延迟与传输距离的关系示意图。

图8为路段平均延迟与车辆数目的关系示意图。

图9为路段平均延迟与车辆速度的关系示意图。

图10为交叉操作示意图。

图11为变异操作示意图。

图12为平均延迟与传输距离的关系示意图。

图13为数据包传输比值与车辆数目的关系示意图。

具体实施方式

下面结合附图和具体实施方式对本申请作进一步详细的说明。

本实施例的车载自组织网络中基于遗传算法的QoS感知路由协议协议包括如下三个步骤，具体为：1)将道路进行分块，分析连通性模型和延迟模型，得到路段的平均延迟。2)根据基于十字路口的路由协议探索源点车辆与目的车辆之间的所有可用路径。3)通过以QoS为目标函数的遗传算法对所述所有可用路径进行路由优化，得到最佳路径。在城市环境下的道路模型可以简化为图1所示的城市道路示例，以下结合该示例进行具体说明。

图1中的城市道路设置有4个十字路口I₁～I₄，4条路段，每条路段的路况皆随机分布。

路段模型主要是根据城市环境下双向车道的多链路转发延迟以及链路连通性而建立，假设两个十字路口I_i,I_j之间的直线车道方向相反且I_i,I_j之间的路段长度为L，数据包传输方向是向东；同时路段上车辆的无线通信传输距离为R，车辆的数目服从泊松分布^[10]，向东的道路和向西的道路上车辆密度分别为λ₁,λ₂，车辆平均速度分别为v₁,v₂。QoS模型主要由连通性模型和延迟模型组成。同时为了准确分析QoS模型，将路段进行分块，每块的长、宽分别为aR和道路宽度，其中R表示车辆的无线通信传输距离，a为矩形块的长度系数，本实施例中a＝0.7。

连通性模型:在城市双向道路环境下，如图2所示，同一方向上的任意两个连续车辆之间的距离为X，当X≤R时，车辆之间的链路处于连通状态，直接转发数据包；当X>R时，车辆之间的链路处于断开状态，无法直接转发数据包，但相反方向上处于两辆车之间的移动车辆可以进行间接转发数据包，因此路段上的连通性保持不变。

假设K为随机变量，表示aR中的车辆数目，服从泊松分布，则K的概率质量函数(PMF)为：

P(K＝k)＝(aRλ)^k·e^-aRλ/k！ (1)

其中，λ表示路段上车辆密度。

由于任意两个连续车辆之间的距离满足指数分布^[11]，则在向东道路上，距离为X的两辆车之间的链路断开的概率如下：

其中，λ₁表示向东道路上的车辆密度。

根据上述连通性模型，如图2所示，可知向东道路上的两个连续车辆V_e,V_e+1之间的距离x>R，则链路断开，利用相反方向道路上的车辆(V_w,V_w+1)修复V_e,V_e+1之间的连通性，修复的概率表示如下：

其中，P(K＝0)＝e^-aRλ,λ＝λ₂，λ表示向西道路上的车辆密度。

设M随机变量，表示向东道路上断开链路的数目，若M个断开的链路可以修复，则路段I_ij处于连通状态，连通性的概率P_cM(M＝k)表示为：

其中，N表示向东道路上的车辆数目。

若向东道路上存在N-1个链路，其中M＝k个链路断开，则M的概率质量函数P_M(M＝k)服从二项分布，表示为：

由此可知，向东道路上至少一条链路断开的情况下(k≥1)，则路段的连通性概率表示为：

当向东道路上车辆之间的链路全部处于连通状态时，即所有块中至少有一辆车，此时路段的连通性概率表示为：

根据上述分析，十字路口I_i和I_j之间的连通性总概率为：

P_c(i,j)＝P_c1+P_c2 (8)

延迟模型:由于城市环境中交通灯的规则，车辆成簇移动，簇内的车辆相互连接，因此根据车辆簇群的规模大小，可以将车辆状况划分为以下两种不同的情况。

(1)路段部分连通状态:如图3所示，路段上部分链路连通，在连通路段上的数据包的传输方向上，数据包所在当前节点会在其传输范围内的所有节点中选择距离自身最远的节点作为下一跳节点，进行贪婪转发；而断开路段上的数据包进行携带转发。

(2)路段全部连通状态:如图4所示，路段上的链路全部连通，因此两个十字路口之间的数据包利用中继节点的贪婪算法进行转发。

根据上述模型可以得出两种情况的路段，接下来主要分析这两种路况的延迟。

当路段部分连通的情况下，如图3所示，路段部分连通，传输延迟D_np的表示如下：

其中，L表示路段长度，表示路段上的数据包的平均传输速度。

由于相反方向道路上的车辆，向东道路会出现链路连通与断开的交互时期，在链路断开时，车辆携带数据包进行传输，传输速度为v₁，当传输范围内出现邻居车辆时，将数据包进行转发；在链路连通时，直接将数据包转发给下一个邻居车辆，传输速度为v_1hop，表达式如下：

其中aR表示每块的长度，t_p表示一跳的传输时间^[13]。

根据交互更新过程定理^[14]，在链路断开期间，数据包的传输时间与总传输时间的比值为：

在链路连通期间，数据包的传输时间与总传输时间的比值为：

其中T_dp,T_cp分别表示链路断开和连通期间内的数据包的传输时间，d_dp,d_cp分别表示链路断开和连通期间内数据包的传输距离，将公式(10)、(11)和(12)代入，推导得到为：

将公式(13)代入公式(9)中，推导得出路段的传输延迟为：

链路断开期间，如图3所示，车辆V_k和V_k+1之间的距离x>R，且x对应的相反方向的道路上没有车辆，因此两者之间的链路断开，V_k则携带数据包进行传输，直到V_k的传输范围内出现可以进行数据包转发的邻居车辆为止。

车辆V_k和V_k+1之间链路断开，V_k携带数据包继续传输，直到向西道路上连续个块中每个块至少有一辆车，才能保证链路的连通，在此之前，V_k经过的块的个数表示如下^[14]：

其中，表示向西道路上每个块内至少有一辆车的概率。

V_k和V_k+1之间的链路断开(x＞R)，意味着两者之间的距离对应的相反方向道路上的块中至少有一个块内没有车辆，则V_k和V_k+1之间链路断开的概率为：

由于向东道路上车辆的概率密度函数为则链路断开概率为：

根据上述分析，链路断开期间数据包传输的平均距离为：

将公式(15)、(16)和(17)代入公式(18)中，可以推导出链路断开期间数据包传输的平均距离。

在链路连通期间，在车辆之间的链路连通时，数据包的传输速度为v_1hop，传输距离需要分情况讨论。

第一种情况，若向东道路上的连续车辆之间的距离不大于R，或者虽然距离大于R，但距离所对应的向西道路上的块内至少有一辆车可以进行修复，如图3所示，那么这两者之间是连通的，此时数据包传输方向上的两个连续车辆之间的预期平均传输距离为：

若有y个连续链路连通，那么传输距离为y·E(X|C)，因此连通链路上的预期平均距离为：

第二种情况，若车辆间链路断开的距离由向西道路上的车辆修复成功，则数据包仍以速度v_1hop进行传输，如图3所示，随着两端车辆的移动，V_k和V_k+1之间的距离块被连通情况2内的车辆占用，此时数据包可以进行跳与跳之间的转发，V_k和V_k+1之间的距离为平均传输距离，表达式如下：

最终路段部分连通状态下数据传输的平均距离为：

d_cp＝d_cp1+d_cp2 (22)

本文将公式(20)和(21)代入公式(22)中，得到路段部分连通下数据包传输的平均距离，根据公式(14)、(18)和(22)，推导得出路段延迟D_np。

当路段全部连通时，如图4所示，路段上的链路全部连通，因此利用跳与跳之间的贪婪算法进行数据包的传输，则相邻十字路口i,j之间的传输延迟为：

D_nc＝H_nc·t_p (23)

其中，表示i,j之间的跳数，t_p表示一跳的传输时间。

根据上述分析，两个相邻十字路口i,j之间的平均传输延迟为：

D(i,j)＝D_np·(1-P_c(i,j))+D_nc·P_c(i,j) (24)

其中，P_c(i,j)表示路段的连通概率。

图7-9分别是路段平均延迟与传输距离、车辆数目和车辆速度三者之间的关系。在图7中路段平均延迟是关于传输距离和车辆密度的函数，交通信息的参数设置如下，车辆速度v₁,v₂分别为10m/s和25m/s，路段长度L为2000m，车辆密度λ₁＝λ₂＝λ分别为0.01、0.02、0.03和0.04vehicles/m，由图可知：(1)车辆密度相同时，传输距离增大，数据包传输所需的延迟会减小；(2)传输距离一定时，车辆密度越大，传输延迟越小。在图8中路段平均延迟是关于车辆数目和路段长度的函数，传输距离R为200m，车辆速度v₁,v₂分别为10m/s和25m/s，路段长度L分别为1000、1500、2000和2500m，由图可知：(1)车辆数目一定时，路段长度减小，延迟会逐渐减小；(2)路段长度相同时，车辆数目越多，传输延迟会减少。在图9中路段平均延迟是关于车辆速度和车辆密度的函数，路段长度L为2000m，传输距离R为200m，车辆密度λ₁＝λ₂＝λ分别为0.01、0.015、0.02和0.025vehicles/m，由图可知：(1)车辆密度相同时，随着车辆速度的增加，延迟逐渐减少；(2)车辆速度一定时，车辆越密集，则延迟越小。上述曲线图详细显示了路段平均延迟与不同变量之间的变化趋势。

路由协议探索：如图6，本实施例的遗传算法的基础协议是基于十字路口的路由协议，此协议中的车辆配备GPS与导航系统，根据交通状况与地理位置信息预测车辆的移动方向，动态选择下一跳十字路口，同时，行驶在路段上的车辆利用携带转发策略进行数据包的传输。

遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,其本质是从一个随机的初始群体出发,依据优胜劣汰原则,通过选择,交叉,变异等遗传优化作用,产生更优的下一代群体，遗传算法基本处理流程参见图5。另一方面，遗传算法还保留有巨大搜索空间的多样性的特点。

基于路由探索的可用路径，根据下面五个步骤对遗传算法进行路径优化，不断重复迭代，寻找QoS最佳的路径。具体步骤如下：

1.编码：根据网络路由的特点和遗传算法的编码原则，本文采用直接编码，无需解码，即对于一条给定的从源点端点十字路口到目的节点端点十字路口的路径，该路径上的十字路口的编号即为染色体编码，一条编号序列就是一条染色体，即一条路径对应着一个个体。此种编码方式中染色体的长度不定，但编号数目不会超过十字路口的总数，因而有效地避免了循环路由的问题。

2.设置初始群体：本文根据基于十字路口的路由协议的路由选择策略，探索到G条路由路径，作为初始群体，规模大小为G。

3.进行选择操作：遗传算法中个体的优劣由适应度函数值决定，个体的适应度函数值越高，则说明个体越优秀，即对应的路由路径越优，适应度函数表示如下：

S＝α·P_n+β·(1/D_nth) (25)

其中，P_n表示第n个个体的连通性概率；D_nth表示第n个个体(第n条路径)的平均传输延迟；α和β为加权系数，α,β∈[0,1]。

本文采用最佳策略选择和轮盘赌选择相结合的选择方法，即在每对染色体进行交叉之前，先根据适应度值选择最佳个体，取代子代群体中适应度值最差的个体，直接遗传到子代群体中，其余个体都采用轮盘赌法进行选择，适应度值越高，被选择的概率越大。

4.进行交叉操作：交叉操作是交换两个个体中的子路径，本文采用后向交叉，如图10所示，在群体中随机选取两个染色体P1,P2作为父代个体，两条路径共同经过的十字路口(源点端点十字路口与目的节点端点十字路口除外)作为备选的交叉位置，从备选的交叉位置中随机选择作为交叉位置，将交叉位置之后的部分进行交换，形成两个子代个体P1’,P2’。

5.进行变异操作：如图11所示，群体中随机选择一个染色体P，在P中随机选择节点ni作为变异节点，在ni的邻居节点集中随机选择节点nj，产生从源点到nj和nj到目的节点的两条路径r1,r2，若r1,r2中存在重复的节点，则放弃此路径，不进行变异，否则连接两条路径形成新的染色体P’，进入下一代。

6.重复执行选择、交叉和变异操作，直到达到迭代次数为止，最终得到最优个体，优化路由路径。

本实施例还提供了利用MATLAB仿真软件对GABR的性能指标进行的仿真分析，并且与IBR、CAR协议进行性能参数的比较。仿真环境选取上述城市道路进行模拟，相关仿真参数如表1所示。

表1仿真参数设置

Tab.1 Settings of simulation parameters

如图12，为传输范围与平均延迟的曲线，由图可知GABR的平均延迟始终低于IBR和CAR，CAR协议是一种基于源点位置的路由协议，不能及时自适应地处理拓扑的变化，可能会导致数据包传输的缓慢；IBR协议是基于十字路口的路由协议，利用实时交通信息动态选择下一跳十字路口，但未考虑车辆密度，可能会导致传输延迟稍大；但所提出的GABR协议将路段进行分块，估计平均延迟时考虑路段连通性，再利用遗传算法进行路由优化，寻找出最佳路由。

如图13，为车辆数目与数据包传输比值的曲线，由图可知车辆越多，数据包丢失越少，同时针对不同的车辆数目，GABR协议的数据包传输能力较优，GABR协议实时获取交通信息，对路段进行分块，分析路段的连通性，动态地选择下一跳十字路口，利用遗传算法优化路径，有利于数据包传输成功；IBR协议主要考虑车辆数目与车辆速度，未考虑连通性，可能会导致数据包传输失败；CAR协议根据源点位置确定一条完整的路由路径，但对于不断变化的网络结构而言，固定的路径会导致大量数据包的丢失。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。

Claims (9)

1.一种车载自组织网络中基于遗传算法的QoS感知路由协议，其特征在于所述协议包括如下步骤：

1)将任意两个相邻十字路口之间的路段进行分块，分析连通性模型和延迟模型，得到路段的平均延迟；

2)根据基于十字路口的路由协议探索源点车辆与目的车辆之间的所有可用路径；

3)通过以QoS为目标函数的遗传算法对所述所有可用路径进行路由优化，得到最佳路径。

2.根据权利要求1所述的车载自组织网络中基于遗传算法的QoS感知路由协议，其特征在于所述步骤1)中对路段进行分块时，将单位块设定为宽为道路宽度、长为aR的矩形块，其中R表示车辆的无线通信传输距离，a为矩形块的长度系数。

3.根据权利要求1所述的车载自组织网络中基于遗传算法的QoS感知路由协议，其特征在于所述步骤1)中，所述连通性模型为：设定两个相邻十字路口间同一方向上的任意两个连续车辆之间的距离为X，当X≤R时，车辆之间的链路处于连通状态，直接转发数据包；当X>R时，车辆之间的链路处于断开状态，无法直接转发数据包，若相反方向上处于两辆车之间的移动车辆可进行间接转发数据包，则判定路段上的连通性保持不变。

4.根据权利要求3所述的车载自组织网络中基于遗传算法的QoS感知路由协议，其特征在于所述步骤1)中，所述延迟模型为：路段上部分链路连通时，在连通路段上的数据包的传输方向上，数据包所在当前节点会在其传输范围内的所有节点中选择距离自身最远的节点作为下一跳节点，进行贪婪转发，而断开路段上的数据包进行携带转发；路段上的链路全部连通时，数据包通过中继节点之间的贪婪算法进行转发。

5.根据权利要求4所述的车载自组织网络中基于遗传算法的QoS感知路由协议，其特征在于所述步骤1)中当路段上的链路全部连通时，通过跳与跳之间的贪婪算法进行数据包的传输，则相邻十字路口i,j之间的传输延迟如式(1)：

D_nc＝H_nc·t_p (1)

其中，表示i,j之间的跳数，t_p表示一跳的传输时间，L表示路段长度；

两个相邻十字路口i,j之间的平均传输延迟如式(2)：

D(i,j)＝D_np·(1-P_c(i,j))+D_nc·P_c(i,j) (2)

其中，P_c(i,j)表示路段的连通概率；

当路段部分连通时，路段的传输延迟为：

其中，d_dp表示链路断开期间数据包传输的平均距离，d_cp表示路段连通期间数据包传输方向上的两个连续车辆之间的预期平均传输距离，v₁为车辆携带数据包传输的传输速度；

链路断开期间，数据包传输的平均距离如式(3)：

$d_{dp}={\∫}_0^{\mathrm{\∞}}E\left(n\right)\·aR\·\frac{f_X\left(x\right)P\left(\stackrel{\‾}{C}\right|X=x)}{P\left(\stackrel{\‾}{C}\right)}dx---\left(3\right)$

式中，E(n)为携带数据包传输时移动距离所对应的块的个数，为与所设定方向相反路段上的无法形成通路的概率，f_X(x)表示所设定方向的道路上的车辆的概率密度函数。

路段连通期间，数据包传输方向上的两个连续车辆之间的预期平均传输距离如式(4)：

d_cp＝d_cp1+d_cp2 (4)

式中，d_cp1为连通链路上的预期平均距离，d_cp2为车辆间链路断开的距离由所述设定方向相反的道路上的车辆修复成功后的平均传输距离。

6.根据权利要求5所述的车载自组织网络中基于遗传算法的QoS感知路由协议，其特征在于1)设定两个相邻十字路口I_i和I_j间以设定方向直线行驶的两个连续车辆V_e,V_e+1之间的距离x>R，则链路断开，通过与所述设定方向相反方向道路上的车辆(V_w,V_w+1)修复V_e,V_e+1之间的连通性，所设定的两个相邻十字路口之间的连通性概率如式(5)：

P_c(i,j)＝P_c1+P_c2 (5)

其中，P_c1表示设定方向的路段上至少一条链路断开的情况下的路段连通性概率，如式(6)；P_c2表示所述设定方向上的车辆之间的链路全部处于连通状态时的路段连通性概率，如式(7)。

$P_{c1}=\underset{k=1}{\overset{N-1}{\Σ}}{P}_{c|M}(M=k)\·P_M(M=k)---\left(6\right)$

7.根据权利要求1所述的车载自组织网络中基于遗传算法的QoS感知路由协议，其特征在于所述步骤2)中所述路由协议中的车辆配备GPS与导航系统，根据交通状况与地理位置信息预测车辆的移动方向，动态选择下一跳十字路口。

8.根据权利要求1所述的车载自组织网络中基于遗传算法的QoS感知路由协议，其特征在于所述遗传算法对所述所有可用路径进行路由优化具体包括如下步骤：

3-1)编码：根据网络路由的特点和遗传算法的编码原则，采用直接编码，即对于一条给定的从源点端点十字路口到目的节点端点十字路口的路径，该路径上的十字路口的编号即为染色体编码，一条编号序列就是一条染色体，即一条路径对应着一个个体；

3-2)设置初始群体：根据基于十字路口的路由协议的路由选择策略，探索到G条路由路径，作为初始群体，规模大小为G；

3-3)进行选择操作：根据适应度函数值，选取对应的适应度函数值最大的个体作为最优个体，构建适应度函数表示如式(8)：

S＝α·P_n+β·(1/D_nth) (8)

其中，P_n表示第n个个体的连通性概率；D_nth表示第n个个体的平均传输延迟；α和β为加权系数，α,β∈[0,1]。

3-4)进行交叉操作，采用后向交叉交换两个个体中的子路径，在群体中随机选取两个染色体P1、P2作为父代个体，两条路径共同经过的十字路口作为备选的交叉位置，从备选的交叉位置中随机选择作为交叉位置，将交叉位置之后的部分进行交换，形成两个子代个体P1’、P2’；

3-5)变异：在群体中随机选择一个染色体P，在P中随机选择节点ni作为变异节点，在ni的邻居节点集中随机选择节点nj，产生从源点到nj和nj到目的节点的两条路径r1、r2，若r1、r2中存在重复的节点，则放弃此路径，不进行变异，否则连接两条路径形成新的染色体P’，进入下一代；

3-6)重复执行步骤3-3)至步骤3-5)，直到达到迭代次数为止，最终得到最优个体，优化路由路径。

9.根据权利要求8所述的车载自组织网络中基于遗传算法的QoS感知路由协议，其特征在于所述步骤3-3)采用最佳策略选择和轮盘赌选择相结合的选择方法：在每对染色体进行交叉之前，先根据适应度值选择最佳个体，取代子代群体中适应度值最差的个体，直接遗传到子代群体中，其余个体都采用轮盘赌法进行选择。