车载网VANETs(Vehicular Ad hoc Networks)是在行驶的车辆间构建的一种新型的移动无线自组织网络，可以实现车辆间的多跳无线通信^[1]。由于车辆高速运动导致网络拓扑变化快，传统的移动自组网路由协议已无法胜任车载网的路由计算。参考文献[2-3]提出了演进图模型，将其应用于网络拓扑变化较慢场景，获得网络的动态拓扑特征，基于此计算无线自组网中的路由。车载网虽然网络拓扑变化快，但是车辆沿着一定的道路行驶，使得车载网网络拓扑的变化具有一定的可预测性，因此参考文献[4]提出了适用于车载网的基于演进图的路由协议EG-RAODV(Evolving Graph-based Reliable Ad hoc on-demand Distance Vector Routing),通过定义链路可靠度和路由可靠度预测车载网中链路和路由在下一时刻互相连通的概率，基于此计算车载网中的可靠路由。但是参考文献[4]在计算链路可靠度和路由可靠度时,局限于具有同向恒定速率的交通流场景所构建的演进图模型，不能如实反映交通环境，对于双向可变速车流环境链路可靠度的计算不准确，最终会导致车载网路由可靠度的降低。基于此，本文提出基于增强型演进图的路由算法，首先，对于双向可变速交通流等不同场景构建增强型演进图，如实反映交通环境，获得车载网的动态变化信息；再基于增强型演进图，应用参考文献[4]的可靠度定义计算链路可靠度和路由可靠度；最后，基于增强型演进图和计算所得可靠度，从源节点到目的节点计算一条最可靠的路由。

1 增强型演进图建模

1.1演进图

        在动态网络中，演进图^[5]由一个t₀时刻给定的网络拓扑图及其计算预测的λ个索引序列的子图构成的图集。每一个子图表示对一定时间间隔内计算预测得到网络链路状态图。车辆和无线链路分别建模成图中的节点和边。图1所示为演进图模型。

        在图1中，边上的值代表链路存在的时间。可以说路径A→D→C是不合格的，因为后面的链路D→C比前面的链路A→D存在时间短。因此，在演进图论中路由中的链路生存时间必须成递增序列。从图中可以看出，A→B→E→G是符合要求的路由。

1.2 增强型演进图

        在高速公路双向可变速交通流中，假定每辆车配备全球定位系统GPS(Global Positioning System)，通过它可以获得车辆位置和速度等信息。t₀时刻相邻车辆无线链路的持续连接时间T_p与无线传输距离H及其车辆的相对速度和位置有关。通过图2四个车流场景图可以计算出T_p的值。

        图2中，L_ij代表车辆间的相对位置，V_i和V_j分别代表t₀时刻车辆速度大小。

        对于EG-RAODV路由协议链路可靠度中的T_p值的计算只适用于图2(a)场景1，如果运用到图2(b)场景2来计算T_p值，势必引起T_p值的减少，导致链路可靠度降低，称这种现象为短连接，即链路连接时间的计算值比实际连接时间短；如果运用到图2(c)场景3来计算T_p值，势必引起T_p值的增大，导致链路可靠度虚增加，称这种现象为虚连接，即链路连接时间的计算值比实际连接时间长；如果运用到图2(d)场景4，则短连接和虚连接两种现象可能同时存在。

        假设源节点车辆在任何时刻都有全网的通信状态图。对于不同时刻，无线链路的可靠度根据上文不同的场景来计算，避免了短连接和虚连接现象的发生，从而确保了链路可靠度的真实有效性，以此构造出的演进图即为本文所定义的增强型演进图。

        为了更好地理解增强型演进图模型，在图3中演示不同时刻t=0 s和t=5 s的增强型演进图样例。图中，每个节点代表高速公路上的车辆，节点间的连线代表车辆间的通信链路，每条连线上都有一个二元数组，第一个元素代表当前时刻，第二个元素代表链路可靠度。

        在图3(a)t=0 s时，每条链路的可靠度都大于0，代表链路都可用;当t=5 s时如图3(b)，由于网络拓扑改变，出现边{B,E}的可靠度值为0的情况，此时代表车辆B和E之间的链路断开不能进行信息的直接传递。

1.3可靠度

        可靠度包括链路可靠度和路由可靠度。

　 链路可靠度是指两辆车之间在时刻t₀存在一条直接相连的通信链路并保持连续通信一段时间的可能性大小^[4]。即：r(l)=P{连续可通信直到t₀+T_p|t₀时刻可通信}

        假设速度服从正态分布^[6]，则对于4种场景下链路可靠度的表达式为：

        在车载网络当中，从源节点车辆s_r到目的节点车辆d_e可能存在多条传输路由,每条路由又由不同链路组成。对于任一条由k条链路组成的路径P，可以这样表示k：l₁=(s_r,n₁)，l₂=(n₁,n₂)，…，l_k=(n_k,d_e)，对于每条链路l_w(w=1,2,…,k)用r_t(l_w)表示链路可靠度值，对于路由P的可靠度定义为路由中各链路可靠度值的乘积，即

2 基于增强型演进图的车载网路由机制

        由于车载网通过无线链路连接网络节点，网络拓扑不断变化，需要实时维护网络拓扑与链路信息，为在车载网中计算路由提供依据，因此，本文所提基于增强型演进图的车载网路由机制包括基于增强型演进图的车载网路由算法和路由发现与维护机制。

2.1基于增强型演进图的车载网路由算法

        该算法维系一种可靠图表, 该可靠图表包含车载网当中车辆节点信息以及它们到其他车辆的最佳路由可靠度信息。在算法的初始化中，令源节点车辆s_r的路由可靠度R(s_r)=1，其他车辆的路径可靠度为R(u)=§。然后依据式(2)求得源节点到目的节点车辆的路由可靠度，当当前车辆的所有邻居节点车辆都被访问完后，该车辆最终会被标记为已访问并且确定了其路由可靠度。其算法的伪代码如下：

        已知：车载网的演进图和源节点车辆s_r。变量：未访问车辆集合Q。

        求：可靠图表。该图表包含从源节点车辆s_r到其他车辆的最可靠路由。

        (1)设置路由可靠度值。令源节点车辆可靠度值R(s_r)=1,其他车辆可靠度值R(u)=§。

        (2) 先令集合Q为空，再将s_r加入到集合Q中。

        (3) 当集合Q不为空集，执行以下步骤：

              (a) 在Q中找到可靠度最高的车辆x;

              (b) 将x标记为已访问;

              (c) 对于车辆x的每一个邻居车辆v，如果车辆v没被标记为已访问且它们之间的链路可靠度不为0，可求得车辆v的路由可靠度R(v)=R(x)×r_t(e),其中r_t(e)为车辆v与车辆x之间的链路可靠度值；将v加入到集合Q中；

              (d) 将x从集合Q中移除，返回到(c)。

        (4) 获得源节点车辆的可靠图表

        为了更好地了解基于增强型演进图的路由算法，可通过图4来举例说明。图4代表某时刻基于增强型演进图的路由算法样例。在样例中，源车辆sr为节点0，目的车辆为节点5，节点之间连线旁的数值为链路可靠度，每一车辆都持有它的节点ID和它的路由可靠度。基于增强型演进图的路由算法发现源节点车辆s_r的邻节点车辆1和2并分配了路由可靠度值，如图4(a)。继而，节点1车辆很快发现目的节点车辆节点5，并同样地分配了路由最可靠度值0.09，如图4(b)。虽然已找到目的节点车辆5，但算法不会停止而是试图找到其他到达目的节点的路由，最终找到一条通过车辆3、4、6的路由并计算到路由可靠度值为0.13,如图4(c),显然0.13>0.09，于是最终选择传输路径0→2→3→4→6→5作为最佳路由，如图4(d)。

2.2路由发现与维护机制

        由上文所述，当源节点获得全网的增强型演进图信息后，基于增强型演进图的路由算法可找到目的节点的最可靠路由。接着，源节点车辆将沿着这条路径发送路由请求包并在包中标记路径中需要经过的车辆节点，因此路由发现过程中不需要广播路由请求信息，节约了大量网络资源。需要注意的是，即使中间节点车辆有最新的到达目的节点的路由，它也不允许发送路由响应包，因为考虑到车载网络拓扑动态变化性高，中间节点到目的节点的路由信息很可能已经过时。只有当目的节点收到路由请求包时才发送路由响应包到源节点车辆。对于路由维护方面，本路由方案使用与AODV（Ad hoc on-demand distance vector routing）相同的恢复策略，即在某个中间车辆发生断链时，该车辆将发送路由错误包来建立新的路由。

3 仿真结果与分析

3.1仿真场景

        实验采用基于离散事件的网络模拟工具NS2。对EG-RAODV和本文提出的基于增强型演进图路由EEGR(Enhanced Evolving Graph-based Routing)协议在场景2、3和4情况下对数据包到达率、路由请求率和端到端的延迟进行比较。选择双向6车道长5 000 m的高速公路，每一方向各30辆车，从里到外各车道的最高限速分别为120 km/h、90 km/h和60 km/h，无线通信距离为300 m。

3.2 仿真结果与分析

        本文令数据传输速率为恒定速率128 kb/s，通过改变源节点车辆发送的分组包大小来比较EEGR和EG-RAODV路由协议在平均数据到达率、平均路由请求率和平均端到端延迟的性能。

        图5为场景2下的比较。由于EG-RAODV路由协议中链路连接时间Tp的计算值比实际的短，导致演进图中链路可靠度的值减小，出现短连接现象，而提出的EEGR使用了扩展的可靠度计算方法,避免了假连接的现象，结果表现出更好的性能。需要注意的是随着分组包的增大，会引起分段的次数增多,一个分段的错误传输就会引起整个分组包的传输失败，继而产生新的路由发现过程。因此随着分组包增加,会出现分组到达率曲线递减、路由请求率曲线递增和端到端时延曲线递增的现象。

        图6为场景3下的比较，由于EG-RAODV路由协议中链路连接时间T_p的计算值比实际的要长，导致演进图中链路可靠度比真实值偏大，出现虚连接现象，而本文提出的EEGR路由协议使用扩展了的可靠度计算方法，避免了假连接的现象，所以性能更好。 

        对于图7场景4的情况，由于EG-RAODV路由协议中会出现短连接或者虚连接现象， 而本文提出的EEGR却可以避免，正确反映动态网络的可靠度特性，所以结果优势更明显。

        演进图能够预测网络拓扑的动态变化，能够保证车载网在高度动态变化的网络场景中计算具有可靠连接的路由。本文提出基于增强型演进图的车载网路由算法，对实际路况进行建模，构造增强型演进图，基于增强型演进图在车载网中，由源节点到目的节点计算最可靠的路由， 保证所得路由的连通性。通过仿真分析，本文提出的路由算法能够提高分组包的到达率、降低了路由请求率以及信息包的端到端时延。

参考文献

[1] 常促宇，向勇，史美林．车载自组网的现状与发展[J]．通信学报，2007,28(11)：116-126. 

[2] MAO G, ANDERSON B D O. Graph theoretic models and tools for the analysis of dynamic wireless multihop networks[C].in Proceedings of IEEE Wireless Communications and Networking Conference, 2009. 

[3] MONTEIRO J, GOLDMAN A, FERREIRA A. Performance evaluation of dynamic networks using an evolving graph combinatorial model[C].in Proceedings of IEEE international conference on Wireless and Mobile computing, Networking and communications(WiMob), 2006.

[4] EIZA M H, NI Q. An evolving graph-based reliable routing scheme for VANETs[J]. IEEE Transactions on Vehicular Technology, 2013,62(4):1493-1504.    

[5] FERREIRA A. On models and algorithms for dynamic communication networks[C]. The Case for Evolving Graphs.in Proceedings of 4e rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL’2002), 2002.

[6] NIU Z, YAO W, NI Q, et al.  Link reliability model for vehicle Ad Hoc networks[C]. in London Communications Symposium, 2006.