盧進(jìn)軍，龍英艷，潘宏利

1.陜西理工學(xué)院物理與電信工程學(xué)院，陜西漢中723000

2.陜西理工學(xué)院教育科學(xué)學(xué)院，陜西漢中723000

1 引言

每天，有許多人死于交通事故，為此，車(chē)載網(wǎng)VANETs（Vehicular Ad hoc Networks）的研究得到廣泛關(guān)注。通過(guò)VANETs分發(fā)道路安全消息，預(yù)防交通事故。因此，VANETs也被認(rèn)為是應(yīng)用于道路車(chē)輛通信的最有前途的技術(shù)之一[1]。VANETs是移動(dòng)自組網(wǎng)MANETs（M obile Ad hoc Networks）一種特殊形式，能實(shí)現(xiàn)車(chē)輛間的通信。在網(wǎng)絡(luò)中的每個(gè)車(chē)輛，能收、發(fā)以及向其他車(chē)輛轉(zhuǎn)發(fā)消息。通過(guò)這種方式車(chē)輛能交互實(shí)時(shí)的交通信息，有利于用戶安全駕駛。與MANETs不同，VANETs具有獨(dú)特的特性，如高的傳輸功率，高的計(jì)算能力，節(jié)點(diǎn)的高速移動(dòng)、移動(dòng)預(yù)測(cè)性以及網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化等[2]。這些特性給部署VANETs提出挑戰(zhàn)，尤其是，節(jié)點(diǎn)的高速移動(dòng)和拓?fù)鋭?dòng)態(tài)變化[3-4]。

在VANETs中，將車(chē)輛看成頂點(diǎn)（vertices），車(chē)輛間通信鏈路看成邊（edge），并引用圖論（graph theory）以理解VANETs的拓?fù)涮匦?。文獻(xiàn)[5-6]針對(duì)可預(yù)測(cè)的移動(dòng)模型，提出采用演化圖形獲取動(dòng)態(tài)網(wǎng)絡(luò)的移動(dòng)信息。這一成果在MANETs以及延時(shí)容忍網(wǎng)絡(luò)（delay-tolerant networks）[7]顯示了不錯(cuò)的性能，然而，演化圖論不能直接應(yīng)用于VANE Ts。

為此，本文以高速公路的車(chē)輛為分析對(duì)象，并假定車(chē)輛以勻速行駛，對(duì)演化圖論進(jìn)行改進(jìn)，并利用改進(jìn)后的圖論形成VANETs通信圖，在此基礎(chǔ)上，提出基于演化圖論的可靠的VANETs路由協(xié)議。

2 相關(guān)研究

文獻(xiàn)[8-9]分析了VANETs中的路由可靠性。對(duì)于VANETs，Taleb等[10]提出了基于車(chē)輛行駛方向的路由方案。該方案利用車(chē)輛方向信息預(yù)測(cè)鏈路壽命，在鏈路斷裂前進(jìn)行切換新的鏈路。根據(jù)車(chē)輛移動(dòng)方向組群，并從同一個(gè)群構(gòu)建鏈路。如果車(chē)輛改變了行駛方向，就意味著由該車(chē)輛建立的鏈路有可能斷裂。

文獻(xiàn)[11]提出速度輔助路由協(xié)議。該協(xié)議利用轉(zhuǎn)發(fā)節(jié)點(diǎn)與目的節(jié)點(diǎn)的相對(duì)速度信息決策數(shù)據(jù)包的轉(zhuǎn)發(fā)路徑。通過(guò)目的節(jié)點(diǎn)的位置以及速度預(yù)測(cè)目的節(jié)點(diǎn)下一時(shí)刻的位置，并據(jù)此明確數(shù)據(jù)包的轉(zhuǎn)區(qū)域。

文獻(xiàn)[12]利用了高速公路車(chē)輛移動(dòng)模型的可預(yù)測(cè)性，提出基于預(yù)測(cè)路由PBR（Prediction-Based Routing）方案。PBR預(yù)測(cè)路由壽命，并預(yù)先切換即使斷裂的路由。通過(guò)車(chē)輛的通信范圍、位置以及速度計(jì)算鏈路的壽命，PBR選用壽命最長(zhǎng)的鏈路組建路由。

文獻(xiàn)[13]提出基于移動(dòng)預(yù)測(cè)路由協(xié)議MOPR（Movement Prediction-based Routing）。MOPR預(yù)測(cè)車(chē)輛下一時(shí)刻的位置從而發(fā)現(xiàn)穩(wěn)定的路由，當(dāng)源節(jié)點(diǎn)與目節(jié)點(diǎn)間存在多條通路時(shí)，MOPR就從中選取最穩(wěn)定的路由傳輸數(shù)據(jù)。

此外，一些研究在MANETs和VANETs引用演化圖論分析動(dòng)態(tài)網(wǎng)絡(luò)的特性。文獻(xiàn)[14]利用演化圖論模型評(píng)估MANETs的最小的路由開(kāi)銷(xiāo)，并利用網(wǎng)絡(luò)仿真軟件NS2實(shí)現(xiàn)演化圖論；文獻(xiàn)[15]著重分析了VANETs通信圖形的統(tǒng)計(jì)特性，并針對(duì)網(wǎng)絡(luò)動(dòng)態(tài)特性進(jìn)行了全面的分析。

3 車(chē)輛可靠性模型

在高速公路上，車(chē)輛常以高速行駛，這為建立可靠路由方案增添了不少困難。路由的性能受多個(gè)因素影響，例如，車(chē)輛的移動(dòng)模型以及車(chē)輛分布均是影響路由的因素[16]。為了能建立準(zhǔn)確的車(chē)輛可靠性模型，首先應(yīng)確定移動(dòng)模型以及車(chē)輛分布特性。車(chē)輛分布的確定有利于預(yù)測(cè)車(chē)輛間通信的持續(xù)時(shí)間。

3.1 車(chē)輛分布

有兩個(gè)主要方法描述車(chē)輛流量的時(shí)空傳播[17]，分別為宏觀、微觀流量模型。宏觀的流量模型利用聚合的宏觀量描述車(chē)輛流量，如交通密度p(x，t)，交通流量q(x，t)以及平均速度v(x，t)。x表示空間位置，t表示時(shí)間。利用以下等式[18]將這些參數(shù)關(guān)聯(lián)一起。

其中，dm表示車(chē)輛間平均距離；ρveh表示交通密度；lm表示車(chē)輛的平均長(zhǎng)度；vm表示車(chē)輛平均速度；τm表示車(chē)輛間通信的平均用時(shí)；qm表示平均交通流量。微觀流量模型是將車(chē)輛作為獨(dú)立的個(gè)體描述，主要有加速度、減速度以及換道回應(yīng)周邊流量等參數(shù)。眾所周知，宏觀流量模型可描述一般的交通流量狀態(tài)也可表示個(gè)體車(chē)輛[19]。因此，本文選用宏觀流量模型。接下來(lái)，從宏觀的角度，利用車(chē)輛速度的分布建立鏈路可靠性模型。

3.2 鏈路可靠性模型

定義鏈路可靠性表示車(chē)輛間鏈路在一段時(shí)間持續(xù)可用的概率。兩車(chē)輛在時(shí)間t，建立了鏈路l。在時(shí)段Tp，鏈路的可靠性可表示為r(l)：

為了計(jì)算鏈路可靠性，首先應(yīng)分析車(chē)輛速度分布。假定車(chē)輛速度服從正態(tài)分布[20]，基于這個(gè)假設(shè)，對(duì)于車(chē)輛?，其速度的概率密度函數(shù)記為g(?)。相應(yīng)地，G(?)表示概率分布函數(shù)。

其中，μ、σ2分別表示速度的均值、方差[21]。車(chē)輛間距離d可通過(guò)車(chē)輛的相對(duì)速度進(jìn)行計(jì)算。假定車(chē)輛的通信范圍為R。因此，通信可持續(xù)時(shí)間T的概率密度函數(shù)f(T)可表示為：

其中，Δv表示車(chē)輛相對(duì)速度；μΔv、σ2Δv分別是相對(duì)速度Δv的均值、方差。

在時(shí)間t，車(chē)輛i、j形成鏈路l，鏈路的壽命Tp可表示為：

其中，Li，j表示車(chē)輛i、j間的歐式距離。

3.3 路由可靠性定義

在VANETs中，源節(jié)點(diǎn)s與目的節(jié)點(diǎn)d可能存在多條路由ω。每條路由由一系列的鏈路組成。不失一般性，對(duì)于某特定的路由P，假定它由k條鏈路組成：l1=(s，n1)，l2=(n1，n2)，…，lk=(nk，d)。根據(jù)式（8），每條鏈路lm(m=1，2，…，k)的鏈路可靠值可表示為r(lm)。因此，路由P的路由可靠值Re(P(s，d))：

假定源節(jié)點(diǎn)s與目的節(jié)點(diǎn)d存在ω條路由。用M(s，d)={P1，P2，…，Pω}為源節(jié)點(diǎn)s與目的節(jié)點(diǎn)d路由集。在路由決策時(shí)，應(yīng)選取最可靠的路由作為數(shù)據(jù)轉(zhuǎn)發(fā)的通道，即按照式（10）選擇路由：

4 面向VANETs演化圖論模型

當(dāng)前的演化圖論（Evolving Graph Theory）不能直接應(yīng)用于VANETs，因?yàn)楫?dāng)前演化圖論模型并沒(méi)有考慮通信鏈路的可靠值。為了滿足VANETs的要求，對(duì)當(dāng)前的演化圖論進(jìn)行擴(kuò)展。擴(kuò)展后的演化圖論模型EEGM（Extended Evolving Graph model）結(jié)合了實(shí)時(shí)交通流量信息，并融入通信鏈路的可靠性信息。

對(duì)于一個(gè)特定的圖G(V，E)，其子圖記為SG=G1(V1，E1)，G2(V2，E2)，…，Gλ(Vλ，Eλ)。因此，。將演化的圖論記為G～=(SG，G)，其中，VG～、EG～分別表示G～點(diǎn)、邊的集合。

當(dāng)前的演化圖論有三個(gè)擇選通路的規(guī)則[14]：最初的（foremost），最先到達(dá)；最短的（shortest），最小跳數(shù)；最快的（fastest），最小傳輸時(shí)延。

擴(kuò)展后的演化圖論模型EEGM：

提出的EEGM強(qiáng)調(diào)了VANETs的通信圖，并考慮通信鏈路的可靠值。如圖1顯示了兩個(gè)時(shí)刻的面向高速公路的EEGM的樣例。圖中的節(jié)點(diǎn)表示高速公路上的行駛的車(chē)輛。與演化圖論不同的時(shí)，EEGM對(duì)每條邊用(t，r(e))標(biāo)識(shí)，其中t表示當(dāng)前時(shí)間，r(e)=r(l)表示鏈路可靠性，由式（8）計(jì)算。

在EEGM中，如果r(e)=0，表示此通信鏈路無(wú)效。設(shè)Trav(e)為決策鏈路e是否能遍歷的函數(shù)，如式（11）所示：

圖1（a）顯示了在t=0時(shí)每條鏈路的可靠性值，從圖中可知，所有的鏈路都是有效的，Trav(e)=True。圖1（b）顯示了在t=5時(shí)每條鏈路的可靠值。從圖（a）演化到（b），鏈路的可靠值發(fā)生了變化。注意到{B，E}和{F，G}不再有效，因?yàn)樵趖=5時(shí)，r({B，E})=r({F，G})=0。

圖1 在t=0，t=5時(shí)的EEGM模型

此外，引用新的指標(biāo)命為通路的可靠值（Journey Reliability）。通過(guò)該指標(biāo)選擇轉(zhuǎn)發(fā)數(shù)據(jù)的通路。在數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)，選取最可靠的通路（M ost Reliable Journey，MRJ），而不是最初的，最短、最快的通路。

假定有k條邊組成一個(gè)有效的從節(jié)點(diǎn)i到節(jié)點(diǎn)j的通路J()i，j。在時(shí)間t，邊ew的可靠值表示為rt(ew)，w=1，2，…，k。因此，通路的可靠值Re(J(i，j))如式（12）所示：

假定這有n條從節(jié)點(diǎn)i到節(jié)點(diǎn)j的通路，n條通路的集合表示為MJ(i，j)={J1，J2，…，Jn}。因此，可通過(guò)式（13）選取最可靠的通路MRJ：

5 移動(dòng)模型

本文研究的VANETs場(chǎng)景為高速公路。假設(shè)車(chē)輛以勻速沿單一方向行駛。根據(jù)文獻(xiàn)[11]的分析，這個(gè)假設(shè)是合理的?；谶@個(gè)假設(shè)，每個(gè)車(chē)輛i設(shè)置以下參數(shù)：在時(shí)間t笛卡兒位置坐標(biāo)xi(t)和yi(t)；速度vi(t)=v0；移動(dòng)方向ai(t)=a0。

6 提出的EG-RAODV

為了實(shí)現(xiàn)VANETs數(shù)據(jù)傳輸?shù)目煽啃?，結(jié)合EEGM的特性，提出新的路由協(xié)議。該路由協(xié)議利用EEGM的模型，從路由的可靠值的角度選擇從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最佳路由。提出基于EEGM選擇最可靠的MRJ的方案，并將此方案運(yùn)用到按需式距離矢量路由協(xié)議AODV（Ad hoc On-demand Distance Vector）[22]，提出的路由協(xié)議記為EG-RAODV。

6.1 EG-Dijkstra算法

在EEGM模型中尋找最可靠的路由，等價(jià)于尋找MRJ。常用的Dijkstra算法[23]不能直接應(yīng)用于本文，為此，將其修改，并提出基于演化圖論的Dijkstra算法（EG-Dijkstra）。基于式（11）和（13），利用EG-Dijkstra算法尋找MRJ。

EG-Dijkstra利用可靠圖數(shù)組RG（Reliable Graph）保存所有車(chē)輛以及它們相應(yīng)的MRJ值。在算法的初始階段，源節(jié)點(diǎn)s為RG(s)=1，其他節(jié)點(diǎn)的RG()i=?。圖2顯示了EG-Dijkstra算法的示例。

假設(shè)源節(jié)點(diǎn)為圖2中標(biāo)識(shí)的節(jié)點(diǎn)0，目的節(jié)點(diǎn)為節(jié)點(diǎn)5，且RG(0)=1。根據(jù)式（8）計(jì)算每條鏈路可靠值r(l)。如節(jié)點(diǎn)0與節(jié)點(diǎn)1間鏈路可靠值為r(l0)=0.43，l0=(0，1)。根據(jù)EG-Dijkstra算法，利用r(l0)與RG(0)相乘，得到下一節(jié)點(diǎn)的RG值。如節(jié)點(diǎn)0的RG(1)=r(l0)×RG(0)=1×0.43=0.43。節(jié)點(diǎn)5的RG(5)=r(l1)×RG(1)=0.43×0.21≈0.09，如圖2的（ii）所示。

圖2 EG-Dijkstra算法的示例

盡管節(jié)點(diǎn)5是目的節(jié)點(diǎn)，但是EG-Dijkstra算法運(yùn)行到圖2的（ii）并不停止，其需計(jì)算所有通路的可靠值，并從中選擇最可靠的值，作為數(shù)據(jù)的路由。從圖2可知，有兩條通路到達(dá)目的節(jié)點(diǎn)：第一條0→1→5；第二條0→4→2→3→6→5。第一條通路可靠值為0.09；第二條為0.13，如圖2的（iv）所示。這表明第二通路比第一條通路更可靠，為此，選用第二通路作為數(shù)據(jù)傳輸?shù)耐ǖ馈?/p>

6.2 EG-RAODV路由特性

假定源節(jié)點(diǎn)知曉當(dāng)前EEGM的狀態(tài)信息。源節(jié)點(diǎn)在時(shí)間t需傳輸數(shù)據(jù)，源節(jié)點(diǎn)先計(jì)算EEGM模型中的每條鏈路的可靠值，并利用EG-Dijkstra算法尋找最可靠的通路MRJ。在獲取最可靠的MRJ后，源節(jié)點(diǎn)產(chǎn)生路由請(qǐng)求消息RREQ（Routing Request message），并將MRJ的跳數(shù)加入RREQ中，即擴(kuò)展RREQ，存儲(chǔ)MRJ的信息。依據(jù)MRJ的信息，中間節(jié)點(diǎn)轉(zhuǎn)發(fā)路由請(qǐng)求，無(wú)需廣播。

沿途MRJ的車(chē)輛收到RREQ，中間節(jié)點(diǎn)不需要向目的節(jié)點(diǎn)發(fā)送路由請(qǐng)求回復(fù)消息RREP（Routing Reply message）。只有RREQ到達(dá)目的節(jié)點(diǎn)，才回復(fù)RREP消息。

據(jù)上述分析可知，EG-RAODV方案無(wú)需廣播路由請(qǐng)求，這極大節(jié)省了網(wǎng)絡(luò)資源。此外，EG-RAODV并沒(méi)有使用hello消息去確認(rèn)鏈路的狀態(tài)，減少了網(wǎng)絡(luò)負(fù)擔(dān)。在路由維護(hù)過(guò)程階段，EG-RAODV使用了與AODV相同的機(jī)制。當(dāng)鏈路斷裂時(shí)，發(fā)送路由錯(cuò)誤消息RERR（Routing Error message），從而實(shí)現(xiàn)維護(hù)路由并發(fā)現(xiàn)新路由的功能。

7 仿真分析

仿真的目的在于評(píng)估提出的路由協(xié)議的性能。采用OMNet++進(jìn)行仿真，每一個(gè)仿真實(shí)驗(yàn)進(jìn)行50次，取平均值作為仿真的最終數(shù)據(jù)。將仿真結(jié)果與AODV以及PBR進(jìn)行比較。

7.1 仿真環(huán)境

仿真區(qū)域?yàn)? 000m的三車(chē)道高速公路。30輛車(chē)（低密度交通流量）分布于仿真區(qū)域。車(chē)輛僅單方向行駛，到達(dá)高速公路末端，就退出仿真區(qū)域。三個(gè)車(chē)道的平均速度分別為40 km/h、60 km/h、80 km/h。針對(duì)兩個(gè)實(shí)驗(yàn)場(chǎng)景進(jìn)行仿真：

（1）實(shí)驗(yàn)A數(shù)據(jù)傳輸速率從32～512 Kb/s變化；數(shù)據(jù)包的大小為1 500 Byte。三個(gè)車(chē)道的車(chē)輛平均速度仍為40 km/h、60 km/h、80 km/h。

（2）實(shí)驗(yàn)B數(shù)據(jù)包的大小從500 Byte至3 000 Byte變化；數(shù)據(jù)傳輸速率為128 Kb/s。三車(chē)道的車(chē)輛平均速度仍為40 km/h、60 km/h、80 km/h。

7.2 性能指標(biāo)

在仿真過(guò)程中，利用以下性能指標(biāo)評(píng)估網(wǎng)絡(luò)性能。

（1）分組傳輸率PDR（Packet Delivery Ratio）：目的節(jié)點(diǎn)成功接受到的數(shù)據(jù)包數(shù)目與在應(yīng)用層的源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包數(shù)目之比；

（2）平均鏈路斷裂數(shù)（Average Number of Link Failures）：在路由階段，鏈路斷裂的平均數(shù)目；

（3）路由請(qǐng)求消息率（Routing requests ratio）：路由請(qǐng)求消息占總的路由消息百分比；

（4）平均端到端傳輸時(shí)延E2E（Average End to End delay）：接受到的數(shù)據(jù)包發(fā)送與接收的時(shí)間差。

7.3 仿真結(jié)果

（1）數(shù)據(jù)傳輸速率的變化對(duì)路由性能的影響

圖3顯示分組傳輸率隨數(shù)據(jù)傳輸速率的變化曲線。從圖3可知，與PBR、AODV相比，提出的EG-RAODV具有最高的分組傳輸率。此外，EG-RAODV隨數(shù)據(jù)傳輸率的變化相對(duì)較穩(wěn)定，而PBR和AODV的下降較快。這主要是因?yàn)镋G-RAODV采用EEGM模型，提高了路由的穩(wěn)定性；同時(shí)EG-RAODV無(wú)需廣播RREQ，節(jié)省了網(wǎng)絡(luò)資源，為分組傳輸率提供了更多帶寬。

圖3 實(shí)驗(yàn)A：分組傳輸率隨數(shù)據(jù)傳輸速率變化

圖4顯示了路由請(qǐng)求消息率隨數(shù)據(jù)傳輸速率的變化情況。與PBR和AODV相比，EG-RAODV的路由請(qǐng)求消息率最小。這主要是因?yàn)镻BR和AODV需一直廣播RREQs直到目的節(jié)點(diǎn)，而EG-RAODV只需依據(jù)MRJ進(jìn)行傳輸，無(wú)需廣播，大大減少了發(fā)送RREQs的數(shù)量。

圖4 實(shí)驗(yàn)A：路由請(qǐng)求消息率隨數(shù)據(jù)傳輸速率變化

圖5顯示EG-RAODV、PDR以及AODV的平均鏈路斷裂數(shù)隨數(shù)據(jù)傳輸速率的變化情況。從圖可知，EG-RAODV具有最低的平均鏈路斷裂數(shù)。AODV最高，這是由于AODV采用最短路徑原則選擇路由，未考慮鏈路可靠性。PDR之所以優(yōu)于AODA是因?yàn)镻DR采取鏈路壽命預(yù)測(cè)機(jī)制，在鏈路斷裂前，選用了新的路由。此外，從圖5知，數(shù)據(jù)傳輸速率越高，EG-RAODV的優(yōu)勢(shì)越明顯。

圖5 實(shí)驗(yàn)A：平均鏈路斷裂數(shù)隨數(shù)據(jù)傳輸速率的變化

提出的EG-RAODV的另一個(gè)優(yōu)勢(shì)體現(xiàn)于平均端到端傳輸時(shí)延，如圖6所示。EG-RAODV具有最低的端到端傳輸時(shí)延。這主要是因?yàn)镋G-RAODV具有整個(gè)EEGM的信息，很容易預(yù)測(cè)其他節(jié)點(diǎn)的位置，并能找出最可靠的路由。由于AODV僅采用原始的反應(yīng)式路由方法建立路由，AODV的端到端傳輸時(shí)延最大。

圖6 實(shí)驗(yàn)A：平均端到端傳輸時(shí)延隨數(shù)據(jù)傳輸速率的變化

（2）數(shù)據(jù)包大小的變化對(duì)路由性能的影響

如圖7所示，EG-RAODV隨數(shù)據(jù)包大小的變化呈現(xiàn)最高的分組傳輸率，并且穩(wěn)定。注意大尺寸的數(shù)據(jù)包可能是分散傳輸?shù)?。在分組傳輸過(guò)程中，任何傳輸分散數(shù)據(jù)包鏈路的斷裂都可能導(dǎo)致整個(gè)數(shù)據(jù)包分組傳輸失敗，如果失敗，需要重新開(kāi)始新的路由發(fā)現(xiàn)工作。從圖可知，EG-RAODV的性能優(yōu)于AODV，這主要是因?yàn)镋G-RAODV搜尋了所有到達(dá)目的節(jié)點(diǎn)的通路，并從中選取最可靠的路徑作為數(shù)據(jù)的傳輸通路。

圖8顯示三個(gè)協(xié)議的平均路由請(qǐng)求消息率的變化情況。PBR路由協(xié)議的平均路由請(qǐng)求消息率高于AODV和EG-RAODV。隨著數(shù)據(jù)包尺寸的增大，數(shù)據(jù)包分散的數(shù)量也隨之增加。這將引起更多的分組傳輸失敗，從而導(dǎo)致更多的路由請(qǐng)求消息，以建立新的路由。這也正是PBR的平均路由請(qǐng)求消息高于AODV、EG-RAODV的原因。幸運(yùn)的是，EG-RAODV并不受此影響，原因就在于EG-RAODV利用EEGM模型建立最可靠的路由。

圖7 實(shí)驗(yàn)B：分組傳輸率隨數(shù)據(jù)包大小的變化

圖8 實(shí)驗(yàn)B：分組傳輸率隨路由請(qǐng)求消息率的變化

圖9 實(shí)驗(yàn)B：平均鏈路斷裂數(shù)隨數(shù)據(jù)包大小的變化

圖10 實(shí)驗(yàn)B：平均端到端傳輸時(shí)延隨數(shù)據(jù)包大小的變化

圖9顯示三個(gè)協(xié)議的平均鏈路斷裂數(shù)的變化情況。從圖可知，AODV具有最高的鏈路斷裂數(shù)，這也恰好解釋了AODV具有最低的分組傳輸率，如圖7所示。由于EG-RAODV選擇最可靠的路由，EG-RAODV的路由持續(xù)時(shí)間長(zhǎng)，鏈路斷裂數(shù)目少。由于PBR采用鏈路預(yù)測(cè)機(jī)制，PBR的平均鏈路斷裂數(shù)低于AODV。然而，由于PBR只是采取了簡(jiǎn)單的預(yù)測(cè)鏈路壽命機(jī)制，無(wú)法建立最可靠的路由，PBR的平均鏈路斷裂數(shù)高于EG-RAODV。

在實(shí)驗(yàn)B中，與PBR和AODV相比，EG-RAODV方案具有最低的平均端到端時(shí)延，如圖10所示。隨著數(shù)據(jù)包大小的變化，EG-RAODV變化相對(duì)穩(wěn)定，幾乎不受影響。PBR以及AODV隨著數(shù)據(jù)包尺寸的增加，端到端時(shí)延也隨之增長(zhǎng)，這是因?yàn)閿?shù)據(jù)包尺寸的增大引起分散的數(shù)據(jù)包增加，任何一個(gè)分散數(shù)據(jù)包傳輸?shù)氖?，就意味?shù)據(jù)包的傳輸失敗。

8 結(jié)論

針對(duì)VANETs的路由問(wèn)題，本文展開(kāi)了分析。首先擴(kuò)展了演化圖論，并提出了EEGM的模型。同時(shí)，結(jié)合Dijkstra算法，提出EG-Dijkstra算法，并將此算法引入EEGM，用以尋找最可靠的通路MRJ。最后，從可靠性出發(fā)，提出EG-RAODV路由協(xié)議。針對(duì)高速公路場(chǎng)景進(jìn)行仿真，并與PBR、AODV進(jìn)行比較。結(jié)果表明提出的EG-RAODV在路由請(qǐng)求消息率、平均端到端傳輸時(shí)延、鏈路斷裂數(shù)以及分組傳輸率方面均比PBR、AODV高。這主要是因?yàn)镋G-RAODV通過(guò)EEGM模型，計(jì)算所有通路的可靠值，并從中選用最可靠的數(shù)據(jù)通路作為數(shù)據(jù)的路由；同時(shí)，EG-RAODV中轉(zhuǎn)發(fā)節(jié)點(diǎn)不廣播RREQ，只是定向傳播，節(jié)省了更多網(wǎng)絡(luò)資源。

[1]Nekovee M.Sensor networks on the road：the promises and challenges of vehicular Ad hoc networks and vehicular grids[C]//Proceedings of Workshop Ubiquitous Comput e-Res，Edinburgh，UK，2005.

[2]Moustafa H，Zhang Y.Vehicular networks techniques，standards and applications[M].New York，NY，USA：Taylor&Francis，2009：7-11.

[3]Abdalla G M T，Abu-Rgheff M A，Senouci S M.Current trends in vehicular Ad hoc networks[C]//Proc of IEEE G lobal Inf Infrastruct Symp，Marrakech，Morocco，2007：1-9.

[4]Blum J J，Eskandarian A，Hoffman L J.Challenges of intervehicle Ad hoc networks[J].IEEE Trans on Intell Transp Syst，2004，5（4）：347-351.

[5]Mao G，Anderson B D O.Graph theoretic models and tools for the analysis of dynamic wireless multihop networks[C]//Proc of IEEE Wireless Commun Netw Conf，2009：1-6.

[6]Monteiro J，Goldman A，F(xiàn)erreira A.Performance evaluation of dynam ic networks using an evolving graph combina-torial model[C]//Proc of IEEE Int Conf WiMob Comput，Netw Commun，2006：173-180.

[7]Ferreira A.Building a reference combinatorial model for MANETs[J].IEEE Netw Mag，2004，18（5）：24-29.

[8]Jiang S，He D，Rao J.A prediction-based link availability estimation for mobile Ad hoc networks[C]//Proc of IEEE INFOCOM，2001：1745-1752.

[9]Thilagavathe V，Duraiswamy K.Prediction based reliability estimation in MANETs with Weibull nodes[J].Eur J Sci Res，2011，64（2）：325-329.

[10]Taleb T，Ochi M，Jamalipour A，et al.An efficient vehicleheading based routing protocol for VANET networks[C]//Proc of IEEE Wireless Commun Netw Conf，2006：2199-2204.

[11]Feng K T，Hsu C H，Lu T E.Velocity-assisted predictive mobility and location-aware routing protocols for mobile Ad hoc networks[J].IEEE Trans on Veh Technol，2008，57（1）：448-464.

[12]Namboodiri V，Gao L.Prediction-based routing for vehicular ad hoc networks[J].IEEE Trans on Veh Technol，2007，56（4）：2332-2345.

[13]Menouar H，Lenardi M，F(xiàn)ilali F.A movement predictionbased routing protocol for vehicle-to-vehicle communications[C]//Proc of 1st Int V 2V Commun Workshop，San Diego，CA，USA，2005：1-7.

[14]M onteiro J.The use of evolving graph combinatorial model in routing protocols for dynamic networks[C]//Proc of XV Concurso Latinoamericano de Tesis de Maestrìa，2008：1-17.

[15]Pallis G，Katsaros D，Dikaiakos M D，et al.On the structure and evolution of vehicular networks[C]//Proc of the 17th IEEE/ACM Annu Meeting Int Symp MASCOTS，2009：1-10.

[16]Ng S C，Zhang W，Zhang Y，et al.Analysis of access and connectivity probabilities in vehicular relay networks[J].IEEE Journal on Selected Areas in Communications（JSAC），2011，29（1）：140-150.

[17]Olariu S，Weigle M C.Vehicular networks from theory to practice[M].New York，NY，USA：Taylor&Francis，2009：344-346.

[18]Rudack M，Meincke M，Jobmann K，et al.On the dynamics of Ad hoc networks for Inter Vehicle Communication（IVC）[C]//Proceedings of the ICWN，Las Vegas，NV，USA，2002.

[19]Kerner B S.Introduction to modern traffic flow theory and control[M].Berlin，Germany：Springer-Verlag，2009.

[20]Niu Z，Yao W，Ni Q，et al.Link reliability model for vehicle Ad hoc networks[C]//Proc of London Commun Symp，London，UK，2006：1-4.

[21]Rudack M，Meincke M，Jobmann K，et al.On traffic dynamical aspects of Inter Vehicle Communications（IVC）[C]//Proc of the IEEE Veh Technol Conf，2003：3368-3372.

[22]Perkins C E，Royer E M.Ad-hoc on-demand distance vector routing[C]//Proc of the 2nd IEEEWMCSA，1999：90-100.

[23]Cormen T H，Leiserson C E，Ronald L R.Introduction to algorithms[M].Cambridge，MA，USA：M IT Press，1990.