CN108811022A - 一种面向车辆网应用环境的动态高效路由方法 - Google Patents

Abstract

一种面向车辆网应用环境的动态高效路由方法。本方法研究了基于移动自组织网络(MANET)的传统路由协议在VANET中运行不佳的问题。由于VANET中的通信链路比MANET中的通信链路更加频繁，这种高度动态网络的路由可靠性更加需要关注，因而引入演化图论来对高速公路上的VANET通信图进行建模。扩展的演化图有助于捕捉车辆网络拓扑结构的演进特征，并预先确定可靠的路线。引入一种面向车辆网应用环境的动态高效路由协议，来促进路由过程中的服务质量(QoS)支持。与现有一些方法相比，本方法开发出来的寻求从源到目的地的VANET演化图中最可靠路由，明显优于其它相关协议，具有一定的实用价值。

Description

一种面向车辆网应用环境的动态高效路由方法

技术领域

本发明属于物联网领域，具体涉及一种面向车辆网应用环境的动态高效路由方法。

背景技术

随着通信技术的不断发展，作为一种特殊的Mobile Ad-hoc Networks(MANETs)网络，Vehicular Ad hoc Networks(VANETs)是智能交通系统设计中至关重要的一部分，许多研究机构已经开始致力于这方面的研究。在智能交通系统中，VANETs能够实现许多安全与非安全方面的应用。例如在安全方面有安全信息通知，道路障碍物警告以及事故避免等应用，而在非安全方面有车载娱乐，多媒体数据共享和远程通信服务等应用。路由协议作为VANETs中重要的组成部分，是实现智能交通至关重要的一部分。为了满足不同场景下，不同应用的需求，设计一个能够适应于不同的场景，而且有着高效可靠性低时延的路由协议成为了首要解决的问题。

与传统的MANETs节点相比，VANETs中车辆节点本身有着强大的运算以及存储能力，而且不需要考虑能量问题。但是其运动方向及运动速度受特定环境影响比较大，在不同的场景下其拓扑变化表现出不同的特点。例如，在高速场景中，由于车辆运动速度快，车辆节点密度小，网络拓扑变化相当剧烈，节点与节点之间的通信链路频繁断裂，使得节点间的通信极其不可靠，寻找出可靠的下一跳节点成为了首要解决的问题。

每天都有很多人死亡，还有更多的人在世界各地的交通事故中受伤。在车辆之间传播道路安全信息以预防事故和改善道路安全是车载自组织网络(VANET)发展的主要动机。VANET是一种有前途的技术，可以在道路上的车辆之间进行通信。它们是一种特殊形式的移动自组织网络提供车辆间通信。假设每个车辆都配备有无线通信设施以提供自组织网络连接。VANET通常是在没有基础设施的情况下运行的，网络中的每个车辆都可以发送，接收和中继消息到网络中的其他车辆。通过这种方式，车辆可以交换实时信息，司机可以了解道路交通状况和其他旅行相关信息。

发明内容

本发明的目的是解决VANETs满足不同应用环境下的需要的问题，提供一种面向车辆网应用环境的动态高效路由方法。本发明考虑了基于移动自组织网络(MANET)的传统路由协议在VANET中运行不佳的问题，因而引入演化图论来对高速公路上的VANET通信图进行建模。扩展的演化图有助于捕捉车辆网络拓扑结构的演进特征，并预先确定可靠的路线。通过实验仿真对比，本方法开发出来的寻求从源到目的地的VANET演化图中最可靠路由，明显优于其它相关协议，具有一定的实用价值。

本发明的面向车辆网应用环境的动态高效路由方法，主要包括如下关键步骤：

第1、车辆可靠性模型结构的构建：

第1.1、建立车辆交通流模型；

第1.2、建立链路可靠性模型；

第1.3、建立路由可靠性模型；

第2、面向VANET的演化图模型结构的构建：

第2.1、提出演化图理论模型；

第2.2、在演化图理论的基础上构建它的扩展版本VoEG模型；

第3、基于车辆网应用环境的动态高效路由协议的设计：

第3.1、寻找MRJ的新路由算法，为了寻找该算法，我们先预测一个算法模型；

第3.2、采用EG-Dijkstra算法来寻求预测算法的最优解；

第3.3、运用EG-Dijkstra算法来计算算法的复杂度；

第3.4、EG-RAODV中路由发现过程；

第3.5、车辆网的动态高效路由协议描述。

进一步的，步骤第1.1中建立了车辆交通流模型，即用宏观和微观这两种交通流模型来描述车辆交通流的时空传播，宏观方法将交通流描绘成连续流体的物理流动，同时描述了交通动态的宏观聚合量，微观方法则描述了每个单独车辆的运动，它模拟了每个车辆的加速，减速和车道变化等行为对周围交通的响应；

步骤第1.2中建立链路可靠性模型的方法如下，链路可靠性即定义为两个车辆之间的直接通信链路在特定时间段内保持连续可用的概率，给定在t处两个车辆之间的特定链路l的连续可用性的预测间隔T_p，则链路可靠性值r_t(l)为：

公式(1)中的积分可以使用高斯误差来导出函数Erf，因而得到：

其中Erf定义如下：

步骤第1.3中建立路由可靠性模型的方法如下：对于任意给定的路径，用k来表示它形成的链接的数量：l₁＝(s_r,n₁),l₂＝(n₁,n₂),...,l_k＝(n_k,d_e)，对于每一组链路l_w＝(w＝1,2,...,k)，我们用r_t(l_w)表示如公式(1)中定义的链路可靠性值，那么由R(P(s_r,d_e))表示的路线P的路线可靠性定义为：

其中l_w∈P(s_r,d_e) (4)

路线可靠性的定义为在该路线形成的路段的可靠性值的乘积，假设从源节点s_r到目的节点d_e有z个潜在的多条路由，并且如果M(s_r,d_e)＝{P₁,P₂,...,P_z}}是所有这些可能路线的集合，那么将根据以下标准在源节点处选择最佳路线：

进一步的，步骤第2.1中演化图论被提出作为动态网络的一个正式抽象，是给定图的λ子图的索引序列，其中给定索引处的子图对应于由索引号指示的时间间隔处的网络连通性，边缘被标记了相应的存在时间间隔，该演化图的行程是底层图中边缘时间标签递增的路线，设G(V,E)为给定图及其子图的有序序列，S_G＝G₁(V₁,E₁),G₂(V₂,E₂),G₃(V₃,E₃)...,G_λ(V_λ,E_λ)使得演化图定义为G＝G_λ(V_λ,E_λ)，其中G的顶点集为E_G＝UV_i，G的边集为E_G＝UE_i，假设给定索引i处的子图G_i(V_i,E_i)是时间间隔T＝[t_i-1,t_i]中网络的基础图，其中t₁＜...＜t_τ，时域T被纳入到模型中。我们定义一个旅程J＝(Ω,Ω_σ)，当且仅当Ω_σ是按照Ω,G和T，这意味着J允许在G从节点u到节点v的遍历；

步骤第2.2中我们提出了VoEG模型来解决VANET通信图的演变特性，并考虑车辆间通信链路的可靠性，将以下2元组(t,r_t(e))表示每个相关联的边，其中t表示当前时间，r_t(e)＝r_t(l)表示当前时间t的链路可靠性值，如公式(1)中定义；

在VoEG模型中，如果其可靠性值r_t(e)等于零，则两车之间的通信链路不可用，VoEG模型中链路的存在时间是连续的，并且取决于当前的车辆交通状态，在这种情况下，在搜索有效旅程时不需要检查链路的存在时间的顺序，令e＝{A,B}为VoEG中的链路，其中V_VoEG为顶点集合，E_VoEG为链路集合，设Trav(e)是一个函数，它决定了这个链路e是否可以被遍历。

在VoEG模型中引入旅程可靠性的新度量，新的旅程可靠性度量是基于公式(4)定义的，设k是在演化图G的u和v之间构成一个有效行程J(u,v)的边的个数，令r_t(e_w)为在时间t处边e_w的可靠度值，其中J＝(Ω,Ω_σ)。由R(J(u,v))表示的旅程可靠性定义如下：

其中e_w∈J(u,v) (7)

旅程的可靠性值等于所有形成的链路的可靠性值的乘积，其中

0≤R(J(u,v))≤1 (8)

假设从u到v有z个潜在的多次旅程，如果MJ(u,v)＝{J₁,J₂,...J_z}是所有这些可能旅程的集合，那么MRJ将根据目标车辆的以下标准来选择：

arg max_J∈MJ(u,v)R(J) (9)

从u到v的所有可能旅程中选择MRJ。

进一步的，步骤第3.1中预测的算法模型为：应用一个移动模型，假设车辆在公路上以相同的方向α₀，以恒定速度v₀行驶，每个车辆i被定义为具有以下参数：在t处当前的笛卡尔位置：x_i(t)和y_i(t)，当前速度v_i(t)＝v₀和运动方向α_i(t)＝α₀，通过下面的式子描述城市路段交通(CSM)模型的交通模型，

Δx_i,j＝v₀×Δt×cosα₀ (10)

Δy_i,j＝v₀×Δt×sinα₀ (11)

其中Δx_i,j和Δy_i,j是在Δt＝(t_j-t_i)期间的沿着x和y方向的行驶距离；

步骤第3.2所述采用EG-Dijkstra算法来寻求预测算法的最优解的方法如下，设定在两个不同的时刻采用简单的VoEG：t＝0s和t＝5s，其中源车辆s_r是节点0，目标车辆d_e是节点5；在t＝0s时，预测算法确定当前车辆的位置，然后，根据公式(1)来计算链接的可靠性值，EG-Dijkstra发现车辆并根据公式(5)～(7)分配MRJ值；然后，选择最大的可靠性值，并继续发现车辆，算法继续检查所有可能的旅程，算法继续发现车辆，并为每辆车分配MRJ值；最后，从不同的旅程再次到达目的车辆；

步骤第3.3所述运用EG-Dijkstra算法来计算算法的复杂度的方法如下，设顶点数为|V|并且边的数目是|E|，在EG-Dijkstra算法中，索引为3的while循环执行|V|倍，在步骤3.2中，我们提取Q中具有最高可靠性值的顶点，因此，每个顶点将被精确地添加到Q中一次，并从Q中删除一次，在最坏的情况下，步骤3.2中的这个任务取O(|V|)，但是，如果将Q作为堆实现，则具有最高可靠性值的车辆的计算复杂度将是O(log|V|)，RG阵列中的边缘松弛过程和更新可靠性值取O(E|+|V|)，EG-Dijkstra算法在高速公路上的VANET通信图中工作，即稀疏图，因此，可以得出EG-Dijkstra算法的总计算复杂度为O((|E|+|V|)log|V|)；

步骤第3.4所述EG-RAODV中路由发现过程的描述如下，EG-RAODV是在综合反应和主动基础上运作；在发送任何路由请求之前，即主动发现基于VoEG信息的到达目标车辆的路线；EG-RAODV不使用HELLO消息技术来检查链接的状态；在路由维护方面，EG-RAODV使用与AODV相同的机制，在发生链路中断时发出路由错误消息(RERR)，以启动新的路由发现过程；

步骤第3.5所述车辆网的动态高效路由协议描述如下：

算法1基于演化图EG-Dijkstra的步骤描述如下：

步骤1：在VoEG模型中找到最可靠的路线(MRJ)，并根据公式(7)和(9)中的旅程可靠性定义，提出演化图Dijkstra算法(EG-Dijkstra)来寻找MRJ；

步骤2：提出的EG-Dijkstra算法维护一个称为可靠图(RG)的数组，其中包含所有车辆及其相应的MRJ值，EG-Dijkstra通过初始化源车辆的旅程可靠性值RG(s_r)＝1和其他车辆的开始，然后从所有车辆中，找出基于公式(7)和(9)的旅程可靠性值，在考虑当前车辆的所有邻居时，将其标记为已访问，并将其行驶可靠性值标记为最终；

算法2EG-RAODV中路由发现过程的步骤描述如下：

步骤1：假定源车辆具有关于VoEG当前状态的信息，根据公式(1)计算在VoEG所有链路的可靠性的值，当源车辆在时间t有数据要发送时，它计算当前VoEG中每个链路的可靠性值，然后，EG-Dijkstra算法根据公式(7)找到从源车辆到目标车辆的MRJ；

步骤2：在这个阶段，找到源车辆到目的地的最可靠的有效旅程，它将创建一个路由请求消息(RREQ)，并将MRJ的跳数作为该RREQ的扩展，在EG-RAODV中，通过利用RREQ中的扩展信息，中间节点能够将路由请求转发到下一跳而不需要广播；

步骤3:在路线上的每辆车上，当接收到RREQ时，记录关于从哪个车辆听到的信息，然后，RREQ将根据分机的信息被转发到下一跳，中间车辆不允许向来源车辆发送路线回复消息(RREP)，在路由选择过程中，节点的移动性与高度动态化，因此，中间车辆的可靠值已经无效，当RREQ到达目标车辆时，RREP将被发送回源车辆以开始数据传输；

算法3EG-RAODV中路由维护过程的步骤描述如下：

步骤1：EG-RAODV采用节点周期性地广播HELLO报文，收到报文的节点知道发送者是其邻居，然后根据公式(4)计算链路可靠性，维护和其邻居的本地互连性，HELLO报文格式和RREP报文格式相同；

步骤2：如果在一定时间内，节点没有收到邻居的HELLO报文，并且路由表中存在以该邻居作为下一跳的路由表项，节点就会广播错误的路由消息RERR报文，需要进行路由维护；

步骤3：根据公式(5)找到源节点处选择最佳路线，链路层反馈是当转发数据报文时，如果在链路层收到下一跳节点路由信息里通知不可到达目的节点的报文，即下一跳没有通往目的节点的路由，则表明路由中断，根据中断节点离源节点和目的节点跳数的比较来选择进行本地恢复或广播RERR报文。

本发明的优点和积极效果是：

本发明主要设计了一种面向车辆网应用环境的动态高效路由方法，在该方法中，主要研究了基于移动自组织网络(MANET)的传统路由协议在VANET中运行不佳的问题。由于VANET中的通信链路比MANET中的通信链路更加频繁，这种高度动态网络的路由可靠性更加需要关注，因而引入演化图论来对高速公路上的VANET通信图进行建模。扩展的演化图有助于捕捉车辆网络拓扑结构的演进特征，并预先确定可靠的路线。引入一种面向车辆网应用环境的动态高效路由协议，来促进路由过程中的服务质量(QoS)支持。与现有一些方法相比，本方法开发出来的寻求从源到目的地的VANET演化图中最可靠路由，明显优于其它相关协议，具有一定的实用价值。

附图说明

图1是基本演化图模型；

图2是VoEG模型分别在t＝0s(a)和t＝5s(b)的图；

图3是数据传输速率和递交率的关系图；

图4是数据传输速率和平均路由请求的关系图；

图5是数据传输速率和平均链路故障数的关系图；

图6是数据传输速率和平均端到端时延的关系图；

图7是数据包和递交率的关系图；

图8是数据包和平均路由请求的关系图；

图9是数据包和平均链路故障数的关系图；

图10是数据包和平均端到端时延的关系图；

图11是本发明面向车辆网应用环境的动态高效路由方法的流程图。

【具体实施方式】

实施例1：

本实施例设计的方法是基于C++模拟库和框架可扩展模块化组件的OMNet++网络模拟器来构建我们的性能评估系统。性能评估的主要目标是确定高动态拓扑对路由过程性能的影响。除此之外，我们想要检查在不同的数据包大小和数据速率的情况下在高速公路场景中使用所提出的VoEG模型的好处。主要涉及的实施操作有OMNet++网络模拟器的构建，模拟场景的构建以及具体的算法计算过程。

参见附图11，本实施例面向车辆网应用环境的动态高效路由方法，主要包括如下关键步骤：

第1、车辆可靠性模型结构的构建：

第1.1、建立车辆交通流模型；

第1.2、建立链路可靠性模型；

第1.3、建立路由可靠性模型；

第2、面向VANET的演化图模型结构的构建：

第2.1、提出演化图理论模型；

第2.2、在演化图理论的基础上构建它的扩展版本VoEG模型；

第3、基于车辆网应用环境的动态高效路由协议的设计：

第3.1、寻找MRJ的新路由算法，为了寻找该算法，我们先预测一个算法模型；

第3.2、采用EG-Dijkstra算法来寻求预测算法的最优解；

第3.3、运用EG-Dijkstra算法来计算算法的复杂度；

第3.4、EG-RAODV中路由发现过程；

第3.5、车辆网的动态高效路由协议描述。

本发明步骤第1.1中建立了车辆交通流模型，即用宏观和微观这两种交通流模型来描述车辆交通流的时空传播。宏观方法将交通流描绘成连续流体的物理流动，同时描述了交通动态的宏观聚合量，如交通密度ρ(x,t)，交通流q(x,t)和平均速度v(x,t)，空间x和时间t对应于偏微分方程的函数。微观方法则描述了每个单独车辆的运动，它模拟了每个车辆的加速，减速和车道变化等行为对周围交通的响应。

步骤第1.2中建立链路可靠性模型的方法如下，链路可靠性即定义为两个车辆之间的直接通信链路在特定时间段内保持连续可用的概率。我们给定在t处两个车辆之间的特定链路l的连续可用性的预测间隔T_p，则链路可靠性值r_t(l)为：

公式(1)中的积分可以使用高斯误差来导出函数Erf。因而得到：

其中Erf定义如下：

步骤第1.3中建立路由可靠性模型的方法如下：在VANET中，源节点s_r与目的节点d_e之间可能存在多条潜在路线，其中每条路线是源节点与目的节点之间的一组链路。对于任意给定的路径，我们用k来表示它形成的链接的数量：l₁＝(s_r,n₁),l₂＝(n₁,n₂),...,l_k＝(n_k,d_e)。对于每一组链路l_w＝(w＝1,2,...,k)，我们用r_t(l_w)表示如公式(1)中定义的链路可靠性值，那么由R(P(s_r,d_e))表示的路线P的路线可靠性定义为：

其中l_w∈P(s_r,d_e)(4)

路线可靠性的定义为在该路线形成的路段的可靠性值的乘积。假设从源节点s_r到目的节点d_e有z个潜在的多条路由，并且如果M(s_r,d_e)＝{P₁,P₂,...,P_z}}是所有这些可能路线的集合，那么将根据以下标准在源节点处选择最佳路线：

如果有多条路线可用，那么我们选择最可靠的路线。

步骤第2.1中演化图论被提出作为动态网络的一个正式抽象，是给定图的λ子图的索引序列，其中给定索引处的子图对应于由索引号指示的时间间隔处的网络连通性，如附图1所示。

从附图1中可以看出，边缘被标记了相应的存在时间间隔，该演化图的行程是底层图中边缘时间标签递增的路线。设G(V,E)为给定图及其子图的有序序列，S_G＝G₁(V₁,E₁),G₂(V₂,E₂),G₃(V₃,E₃)...,G_λ(V_λ,E_λ)使得演化图定义为G＝G_λ(V_λ,E_λ)，其中G的顶点集为E_G＝UV_i，G的边集为E_G＝UE_i。假设给定索引i处的子图G_i(V_i,E_i)是时间间隔T＝[t_i-1,t_i]中网络的基础图，其中t₁＜...＜t_τ，时域T被纳入到模型中。我们定义一个旅程J＝(Ω,Ω_σ)，当且仅当Ω_σ是按照Ω,G和T，这意味着J允许在G从节点u到节点v的遍历。

目前的演变图论中，定义了三个旅程度量标准：最重要，最短，最快的旅程。引入它们分别查找最早的到达日期，最小跳数和最小延迟(时间跨度)路由。假设在演化图G中J＝(Ω,Ω_σ)是一个给定的行程，其中Ω＝e₁,e₂,e₃,...,e_k和Ω_σ＝σ₁,σ₂,σ₃,...,σ_k。

(1)跳数h(J)定义为h(J)＝|Ω|＝k。

(2)旅程a(J)的到达日期定义为遍历J中最后一个边的预定时间，加上它的遍历时间，即a(J)＝σ_k+ζ(e_k)。

(3)旅程时间t(J)定义为离开和到达之间的过去时间，即t(J)＝a(J)-σ₁。

步骤第2.2中我们提出了VoEG模型来解决VANET通信图的演变特性，并考虑车辆间通信链路的可靠性。附图2显示了在两个时刻：t＝0s和t＝5s高速公路上的VoEG模型。附图2中的每个节点都显示了高速公路上的车辆，与传统演化图中使用的每个边(链接)的相应存在时间间隔不同，我们将以下2元组(t,r_t(e))表示每个相关联的边，其中t表示当前时间，r_t(e)＝r_t(l)表示当前时间t的链路可靠性值，如公式(1)中定义。

在VoEG模型中，如果其可靠性值r_t(e)等于零，则两车之间的通信链路不可用。与传统的演化图不同，VoEG模型中链路的存在时间是连续的，并且取决于当前的车辆交通状态。在这种情况下，在搜索有效旅程时不需要检查链路的存在时间的顺序。令e＝{A,B}为VoEG中的链路，其中V_VoEG为顶点集合，E_VoEG为链路集合。设Trav(e)是一个函数，它决定了这个链路e是否可以被遍历。

我们在VoEG模型中引入了一种称为旅程可靠性的新度量，具体说明了VANET路由的动态。我们的目标是找到最可靠的旅程(MRJ)，而不是使用传统方法寻找最前沿，最短或最快旅程。MRJ在从源到目的地的所有可能旅程中具有最高的可靠性旅程。新的旅程可靠性度量是基于公式(4)定义的。设k是在演化图G的u和v之间构成一个有效行程J(u,v)的边的个数，令r_t(e_w)为在时间t处边e_w的可靠度值，其中J＝(Ω,Ω_σ)。由R(J(u,v))表示的旅程可靠性定义如下：

其中e_w∈J(u,v) (7)

旅程的可靠性值等于所有形成的链路的可靠性值的乘积，其中

0≤R(J(u,v))≤1 (8)

假设从u到v有z个潜在的多次旅程，如果MJ(u,v)＝{J₁,J₂,...J_z}是所有这些可能旅程的集合，那么MRJ将根据目标车辆的以下标准来选择：

arg max_J∈MJ(u,v)R(J) (9)

我们会从u到v的所有可能旅程中选择MRJ。

步骤第3.1中预测的算法模型为：为了预测时间t的车辆位置，我们需要应用一个移动模型，假设车辆在公路上以相同的方向α₀，以恒定速度v₀行驶。这种假设在具有交通流量的约束拓扑中是合理的，如城市街道和高速公路拓扑。基于这个假设，每个车辆i被定义为具有以下参数：在t处当前的笛卡尔位置：x_i(t)和y_i(t)，当前速度v_i(t)＝v₀和运动方向α_i(t)＝α₀，下面的式子描述了城市路段交通(CSM)模型的交通模型。

Δx_i,j＝v₀×Δt×cosα₀ (10)

Δy_i,j＝v₀×Δt×sinα₀ (11)

其中Δx_i,j和Δy_i,j是在Δt＝(t_j-t_i)期间的沿着x和y方向的行驶距离。

步骤第3.2中所述采用EG-Dijkstra算法来寻求预测算法的最优解的方法如下，附图2显示了EG-Dijkstra算法的一个简单例子在两个不同的时刻采用简单的VoEG：t＝0s和t＝5s。在这个例子中，源车辆s_r是节点0，目标车辆d_e是节点5。为了便于说明，我们在链路上不使用2元组符号，考虑到链路可靠性，每辆车都有自己的ID和RG(ID)值。

在t＝0s时，预测算法确定当前车辆的位置。然后，根据公式(1)来计算链接的可靠性值。EG-Dijkstra发现车辆1和4并根据公式(5)～(7)分配MRJ值。然后，选择最大的可靠性值，并继续发现车辆5，算法基于公式(9)分配0.12作为MRJ值。虽然车辆5是目的地，但算法不会在这个阶段停止，因为它必须检查所有可能的旅程。因而，算法继续发现车辆2,3和6，并为每辆车分配MRJ值。最后，从不同的旅程再次到达车辆5。因此，最终可靠性值将是0.13，并且在t＝0s时从车辆0到车辆5的MRJ是0→4→2→3→6→5。

步骤第3.3所述运用EG-Dijkstra算法来计算算法的复杂度的方法如下，设顶点数为|V|并且边的数目是|E|。在EG-Dijkstra算法中，索引为3的while循环执行|V|倍。在步骤3.2中，我们提取Q中具有最高可靠性值的顶点。因此，每个顶点将被精确地添加到Q中一次，并从Q中删除一次。在最坏的情况下，步骤3.2中的这个任务取O(|V|)。但是，如果将Q作为堆实现，则具有最高可靠性值的车辆的计算复杂度将是O(log|V|)。RG阵列中的边缘松弛过程和更新可靠性值取O(|E|+|V|)，EG-Dijkstra算法在高速公路上的VANET通信图中工作，即稀疏图。因此，可以得出EG-Dijkstra算法的总计算复杂度为O((|E|+|V|)log|V|)。

步骤第3.4所述EG-RAODV中路由发现过程的描述如下，EG-RAODV是在综合反应和主动基础上运作，它的反应性特征是按需求寻找路线。另一方面，在发送任何路由请求之前，即主动发现基于VoEG信息的到达目标车辆的路线。通过消除路由请求的广播，EG-RAODV显著地节省网络资源。除此之外，EG-RAODV不使用HELLO消息技术来检查链接的状态，因为整个VoEG在源车辆中被预先预测。在路由维护方面，EG-RAODV使用与AODV相同的机制，在发生链路中断时发出路由错误消息(RERR)，以启动新的路由发现过程。

步骤第3.5所述车辆网的动态高效路由协议描述如下：

算法1基于演化图EG-Dijkstra的步骤描述如下：

步骤1：在VoEG模型中找到最可靠的路线(MRJ)。正常的Dijkstra算法不能直接应用在这种情况下。我们要对其进行修改，并根据公式(7)和(9)中的旅程可靠性定义，提出演化图Dijkstra算法(EG-Dijkstra)来寻找MRJ。

步骤2：提出的EG-Dijkstra算法维护一个称为可靠图(RG)的数组，其中包含所有车辆及其相应的MRJ值。EG-Dijkstra通过初始化源车辆的旅程可靠性值RG(s_r)＝1和其他车辆的开始。然后从所有车辆中，找出基于公式(7)和(9)的旅程可靠性值。在考虑当前车辆的所有邻居时，将其标记为已访问，并将其行驶可靠性值标记为最终。

算法2 EG-RAODV中路由发现过程的步骤描述如下：

步骤1：假定源车辆具有关于VoEG当前状态的信息，根据公式(1)计算在VoEG所有链路的可靠性的值。当源车辆在时间t有数据要发送时，它计算当前VoEG中每个链路的可靠性值。然后，EG-Dijkstra算法根据公式(7)找到从源车辆到目标车辆的MRJ。

步骤2：在这个阶段，找到源车辆到目的地的最可靠的有效旅程。它将创建一个路由请求消息(RREQ)，并将MRJ的跳数作为该RREQ的扩展。请注意，RREQ中的这个扩展字段没有在传统的自组织路由协议中使用，而是留待将来使用。在EG-RAODV中，通过利用RREQ中的扩展信息，中间节点能够将路由请求转发到下一跳而不需要广播。

步骤3:在路线上的每辆车上，当接收到RREQ时，记录关于从哪个车辆听到的信息。然后，RREQ将根据分机的信息被转发到下一跳，中间车辆不允许向来源车辆发送路线回复消息(RREP)。在路由选择过程中，节点的移动性与高度动态化，因此，中间车辆的可靠值已经无效。当RREQ到达目标车辆时，RREP将被发送回源车辆以开始数据传输。

算法3EG-RAODV中路由维护过程的步骤描述如下：

步骤1：EG-RAODV采用节点周期性地广播HELLO报文，收到报文的节点知道发送者是其邻居，然后根据公式(4)计算链路可靠性，维护和其邻居的本地互连性，HELLO报文格式和RREP报文格式相同。

步骤2：如果在一定时间内，节点没有收到邻居的HELLO报文，并且路由表中存在以该邻居作为下一跳的路由表项，节点就会广播错误的路由消息RERR报文，需要进行路由维护。

步骤3：根据公式(5)找到源节点处选择最佳路线。链路层反馈是当转发数据报文时，如果在链路层收到下一跳节点路由信息里通知不可到达目的节点的报文，即下一跳没有通往目的节点的路由，则表明路由中断，根据中断节点离源节点和目的节点跳数的比较来选择进行本地恢复或广播RERR报文。

本实例中我们构建了一个模拟场景，使用一条5000米长的三车道公路车辆进行移动，车辆数量是30(交通密度低)，只考虑车辆运动的一个方向。当车辆到达高速公路的末端时，它们将从模拟区域出来。每条车道的平均车速分别为40、60和80公里/小时。将进行两个模拟实验。

1)实验A：我们将传输数据速率从32kb/s改为512kb/s。数据包的大小是1500字节。在这里，车辆的平均速度在三条车道中分别保持不变，分别为40、60和80公里/小时。

2)实验B：我们将数据包大小从500字节改为3000字节。传输数据速率是128kb/s。在这里，车辆的平均速度在三条车道中分别保持不变，分别为40、60和80公里/小时。

每个车道的车速都遵循正态分布。我们使用表1典型速度分布值来计算。

表1速度分布

本模拟实验将考虑四个性能指标，其分别是：

1.数据包的递交率(Packet Delivery Ratio，PDR)。数据包的递交率是指目的节点上所有成功接收到的数据包在源节点上由应用层生成的所有数据包的平均比例。

2.链路故障。链路故障是指路由过程中链路故障的平均数量。该度量显示了路由协议避免链路故障的效率。

3.路由请求比率。路由请求比率是指总传送的路由请求与在目的地车辆上成功接收到的总路由分组的比率。

4.平均端到端(E2E)延迟。平均端到端(E2E)延迟是指接收数据包的发送和接收时间之间的平均时间。

本实例的仿真实验结果如下：

1.不同数据速率对路由性能的影响

1)数据传输速率和递交率的关系

附图3为数据传输速率和递交率的关系。从图中可以看出，我们提出的EG-RAODV比PBR和AODV的数据包的递交率更高。还表明，EG-RAODV获得稳定的递交率性能，而PBR和AODV的递交率的性能随着数据传输速率的增加而降低，这种优势来源于EG-RAODV利用扩展演化图模型选择最可靠的路由。与PBR和AODV不同，在EG-RAODV中不需要路由请求广播，这节省了网络带宽资源并有助于提高数据传输率。

2)数据传输速率和平均路由请求的关系

附图4表明了数据传输速率和平均路由请求的关系。从图中可以看出，EG-RAODV的平均路由请求比率远小于PBR和AODV的平均路由请求比率。这是因为EG-RAODV主动发现使用VoEG的最可靠的路由，并基于所选择的路由来引导RREQ。另一方面，AODV和PBR继续广播RREQ，直到找到目标车辆。而PBR有最高的平均路由请求比率，因为它必须处理多个RREQ来找到到达目的地的最大预测路由生命周期的路由。

3)数据传输速率和平均链路故障数的关系

附图5为数据传输速率和平均链路故障数的关系。从图中可以看出，EG-RAODV协议的平均链路故障数低于AODV和PBR。PBR在链路故障方面优于AODV，因为它预测链路生存期，并在链路断裂之前创建新的备选路由。在所有不同的数据传输速率下，EG-RAODV表现最佳，特别是当数据速率增加时，因为生成的报文越多，AODV和PBR发生链路故障的次数越多。

4)数据传输速率和平均端到端时延的关系

附图6为数据传输速率和平均端到端时延的关系。从图中可以看出，EG-RAODV的另一个重要优势是，与AODV和PBR相比，它的平均端到端的延迟性能要低得多。EG-RAODV的最低延迟来自它使用主动方法来寻找新路由，由于它保存了整个VoEG的信息，EG-RAODV可以很容易地预测其他车辆的当前位置，并且在没有广播控制信息的情况下找到最可靠的路线。另一方面，AODV在三种方案中产生最高的延迟值，因为它使用纯粹的被动方法来寻找新的路由。PBR路由获得比AODV更低的延迟值，因为它会检查所有可能的路由来找到稳定的路由。

2.不同数据包大小对路由性能的影响

5)数据包和递交率的关系

附图7为数据包和递交率的关系。从图中可以看出，EG-RAODV总是在不同的数据包大小上达到最高和稳定的PDR性能。PBR比AODV再次执行得更好，因为它搜索到达目的地的所有可能路由，并选择具有最大预测路由生存时间的路由。

6)数据包和平均路由请求的关系

附图8表示了数据包和平均路由请求的关系。从图中可以看出，PBR的平均路由请求比率高于AODV和EG-RAODV。由于数据包的增加，碎片数量也会增加，而碎片引起更高的传送失败，为路由发现过程生成更多的路由请求。这就解释了为什么平均路由请求比率随着AODV和PBR的增加而增加。而EG-RAODV不受这个问题的影响，因为使用VoEG信息发现了最可靠的路线。

7)数据包和平均链路故障数的关系

附图9为数据包和平均链路故障数的关系。从图中可以看出，AODV中的平均链路故障数量是最高的，由于选择了最可靠的路由，EG-RAODV获得最低且稳定的链路故障数量。PBR采用了选择具有最大预测路线寿命的路线，因此，它的平均链路故障数比AODV要低。然而，PBR中的简单链路生存期预测算法无法找到最可靠的路由，因此导致比EG-RAODV更多的链路故障。

8)数据包和平均端到端时延的关系

附图10为数据包与平均端到端时延的关系。从图中可以看出，EG-RAODV的平均端到端的时延也比AODV和PBR低。EG-RAODV的延迟性能不受不同数据包大小的影响，EG-RAODV的数据包大小的延迟略有增加。

仿真结果表明，在所有测试的路由协议中，EG-RAODV达到最高的PDR。由于在路由发现过程中不需要广播技术，所以它获得最低的路由请求比率。由于它选择到目的地最可靠的路由，所以达到链路故障数最少，路由寿命最长，平均端到端延迟最小。

Claims (4)

1.一种面向车辆网应用环境的动态高效路由方法，其特征在于该方法主要包括如下步骤：

第1、车辆可靠性模型结构的构建：

第1.1、建立车辆交通流模型；

第1.2、建立链路可靠性模型；

第1.3、建立路由可靠性模型；

第2、面向VANET的演化图模型结构的构建：

第2.1、提出演化图理论模型；

第2.2、在演化图理论的基础上构建它的扩展版本VoEG模型；

第3、基于车辆网应用环境的动态高效路由协议的设计：

第3.1、寻找MRJ的新路由算法，为了寻找该算法，我们先预测一个算法模型；

第3.2、采用EG-Dijkstra算法来寻求预测算法的最优解；

第3.3、运用EG-Dijkstra算法来计算算法的复杂度；

第3.4、EG-RAODV中路由发现过程；

第3.5、车辆网的动态高效路由协议描述。

2.如权利要求1所述的面向车辆网应用环境的动态高效路由方法，其特征在于，步骤第1.1中建立了车辆交通流模型，即用宏观和微观这两种交通流模型来描述车辆交通流的时空传播，宏观方法将交通流描绘成连续流体的物理流动，同时描述了交通动态的宏观聚合量，微观方法则描述了每个单独车辆的运动，它模拟了每个车辆的加速，减速和车道变化等行为对周围交通的响应；

步骤第1.2中建立链路可靠性模型的方法如下，链路可靠性即定义为两个车辆之间的直接通信链路在特定时间段内保持连续可用的概率，给定在t处两个车辆之间的特定链路l的连续可用性的预测间隔T_p，则链路可靠性值r_t(l)为：

公式(1)中的积分可以使用高斯误差来导出函数Erf，因而得到：

其中Erf定义如下：

步骤第1.3中建立路由可靠性模型的方法如下：对于任意给定的路径，用k来表示它形成的链接的数量：l₁＝(s_r,n₁),l₂＝(n₁,n₂),...,l_k＝(n_k,d_e)，对于每一组链路l_w＝(w＝1,2,...,k)，我们用r_t(l_w)表示如公式(1)中定义的链路可靠性值，那么由R(P(s_r,d_e))表示的路线P的路线可靠性定义为：

其中l_w∈P(s_r,d_e) (4)

路线可靠性的定义为在该路线形成的路段的可靠性值的乘积，假设从源节点s_r到目的节点d_e有z个潜在的多条路由，并且如果M(s_r,d_e)＝{P₁,P₂,...,P_z}是所有这些可能路线的集合，那么将根据以下标准在源节点处选择最佳路线：

3.如权利要求1所述的面向车辆网应用环境的动态高效路由方法，其特征在于，步骤第2.1中演化图论被提出作为动态网络的一个正式抽象，是给定图的λ子图的索引序列，其中给定索引处的子图对应于由索引号指示的时间间隔处的网络连通性，边缘被标记了相应的存在时间间隔，该演化图的行程是底层图中边缘时间标签递增的路线，设G(V,E)为给定图及其子图的有序序列，S_G＝G₁(V₁,E₁),G₂(V₂,E₂),G₃(V₃,E₃)...,G_λ(V_λ,E_λ)使得演化图定义为G＝G_λ(V_λ,E_λ)，其中G的顶点集为E_G＝UV_i，G的边集为E_G＝UE_i，假设给定索引i处的子图G_i(V_i,E_i)是时间间隔T＝[t_i-1,t_i]中网络的基础图，其中t₁＜...＜t_τ，时域T被纳入到模型中。我们定义一个旅程J＝(Ω,Ω_σ)，当且仅当Ω_σ是按照Ω,G和T，这意味着J允许在G从节点u到节点v的遍历；

步骤第2.2中我们提出了VoEG模型来解决VANET通信图的演变特性，并考虑车辆间通信链路的可靠性，将以下2元组(t,r_t(e))表示每个相关联的边，其中t表示当前时间，r_t(e)＝r_t(l)表示当前时间t的链路可靠性值，如公式(1)中定义；

在VoEG模型中，如果其可靠性值r_t(e)等于零，则两车之间的通信链路不可用，VoEG模型中链路的存在时间是连续的，并且取决于当前的车辆交通状态，在这种情况下，在搜索有效旅程时不需要检查链路的存在时间的顺序，令e＝{A,B}为VoEG中的链路，其中V_VoEG为顶点集合，E_VoEG为链路集合，设Trav(e)是一个函数，它决定了这个链路e是否可以被遍历。

在VoEG模型中引入旅程可靠性的新度量，新的旅程可靠性度量是基于公式(4)定义的，设k是在演化图G的u和v之间构成一个有效行程J(u,v)的边的个数，令r_t(e_w)为在时间t处边e_w的可靠度值，其中J＝(Ω,Ω_σ)。由R(J(u,v))表示的旅程可靠性定义如下：

其中e_w∈J(u,v) (7)

旅程的可靠性值等于所有形成的链路的可靠性值的乘积，其中

0≤R(J(u,v))≤1 (8)

假设从u到v有z个潜在的多次旅程，如果MJ(u,v)＝{J₁,J₂,...J_z}是所有这些可能旅程的集合，那么MRJ将根据目标车辆的以下标准来选择：

arg max_J∈MJ(u,v)R(J) (9)

从u到v的所有可能旅程中选择MRJ。

4.如权利要求1所述的面向车辆网应用环境的动态高效路由方法，其特征在于，步骤第3.1中预测的算法模型为：应用一个移动模型，假设车辆在公路上以相同的方向α₀，以恒定速度v₀行驶，每个车辆i被定义为具有以下参数：在t处当前的笛卡尔位置：x_i(t)和y_i(t)，当前速度v_i(t)＝v₀和运动方向α_i(t)＝α₀，下面的式子描述了城市路段交通(CSM)模型的交通模型，

Δx_i,j＝v₀×Δt×cosα₀ (10)

Δy_i,j＝v₀×Δt×sinα₀ (11)

其中Δx_i,j和Δy_i,j是在Δt＝(t_j-t_i)期间的沿着x和y方向的行驶距离；

步骤第3.2所述采用EG-Dijkstra算法来寻求预测算法的最优解的方法如下，设定在两个不同的时刻采用简单的VoEG：t＝0s和t＝5s，其中源车辆s_r是节点0，目标车辆d_e是节点5；

在t＝0s时，预测算法确定当前车辆的位置，然后，根据公式(1)来计算链接的可靠性值，EG-Dijkstra发现车辆并根据公式(5)～(7)分配MRJ值；然后，选择最大的可靠性值，并继续发现车辆并继续检查所有可能的旅程，算法继续发现车辆，并为每辆车分配MRJ值；最后，从不同的旅程再次到达目的车辆；

步骤第3.3所述运用EG-Dijkstra算法来计算算法的复杂度的方法如下，设顶点数为|V|并且边的数目是|E|，在EG-Dijkstra算法中，索引为3的while循环执行|V|倍，在步骤3.2中，我们提取Q中具有最高可靠性值的顶点，因此，每个顶点将被精确地添加到Q中一次，并从Q中删除一次，在最坏的情况下，步骤3.2中的这个任务取O(|V|)，但是，如果将Q作为堆实现，则具有最高可靠性值的车辆的计算复杂度将是O(log|V|)，RG阵列中的边缘松弛过程和更新可靠性值取O(|E|+|V|)，EG-Dijkstra算法在高速公路上的VANET通信图中工作，即稀疏图，因此，可以得出EG-Dijkstra算法的总计算复杂度为O((|E|+|V|)log|V|)；

步骤第3.4所述EG-RAODV中路由发现过程的描述如下，EG-RAODV是在综合反应和主动基础上运作；在发送任何路由请求之前，即主动发现基于VoEG信息的到达目标车辆的路线；G-RAODV不使用HELLO消息技术来检查链接的状态；在路由维护方面，EG-RAODV使用与AODV相同的机制，在发生链路中断时发出路由错误消息(RERR)，以启动新的路由发现过程；

步骤第3.5所述车辆网的动态高效路由协议描述如下：

算法1基于演化图EG-Dijkstra的步骤描述如下：

步骤1：在VoEG模型中找到最可靠的路线(MRJ)，并根据公式(7)和(9)中的旅程可靠性定义，提出演化图Dijkstra算法(EG-Dijkstra)来寻找MRJ；

步骤2：提出的EG-Dijkstra算法维护一个称为可靠图(RG)的数组，其中包含所有车辆及其相应的MRJ值，EG-Dijkstra通过初始化源车辆的旅程可靠性值RG(s_r)＝1和其他车辆的开始，然后从所有车辆中，找出基于公式(7)和(9)的旅程可靠性值，在考虑当前车辆的所有邻居时，将其标记为已访问，并将其行驶可靠性值标记为最终；

算法2EG-RAODV中路由发现过程的步骤描述如下：

步骤1：假定源车辆具有关于VoEG当前状态的信息，根据公式(1)计算在VoEG所有链路的可靠性的值，当源车辆在时间t有数据要发送时，它计算当前VoEG中每个链路的可靠性值，然后，EG-Dijkstra算法根据公式(7)找到从源车辆到目标车辆的MRJ；

步骤2：在这个阶段，找到源车辆到目的地的最可靠的有效旅程，它将创建一个路由请求消息(RREQ)，并将MRJ的跳数作为该RREQ的扩展，在EG-RAODV中，通过利用RREQ中的扩展信息，中间节点能够将路由请求转发到下一跳而不需要广播；

步骤3:在路线上的每辆车上，当接收到RREQ时，记录关于从哪个车辆听到的信息，然后，RREQ将根据分机的信息被转发到下一跳，中间车辆不允许向来源车辆发送路线回复消息(RREP)，在路由选择过程中，节点的移动性与高度动态化，因此，中间车辆的可靠值已经无效，当RREQ到达目标车辆时，RREP将被发送回源车辆以开始数据传输；

算法3EG-RAODV中路由维护过程的步骤描述如下：

步骤1：EG-RAODV采用节点周期性地广播HELLO报文，收到报文的节点知道发送者是其邻居，然后根据公式(4)计算链路可靠性，维护和其邻居的本地互连性，HELLO报文格式和RREP报文格式相同；

步骤2：如果在一定时间内，节点没有收到邻居的HELLO报文，并且路由表中存在以该邻居作为下一跳的路由表项，节点就会广播错误的路由消息RERR报文，需要进行路由维护；

步骤3：根据公式(5)找到源节点处选择最佳路线，链路层反馈是当转发数据报文时，如果在链路层收到下一跳节点路由信息里通知不可到达目的节点的报文，即下一跳没有通往目的节点的路由，则表明路由中断，根据中断节点离源节点和目的节点跳数的比较来选择进行本地恢复或广播RERR报文。