基于演化圖論的可靠的VANETs路由協(xié)議

盧進軍，龍英艷，潘宏利

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

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

1 引言

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

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

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

2 相關(guān)研究

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

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

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

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

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

3 車輛可靠性模型

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

3.1 車輛分布

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

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

3.2 鏈路可靠性模型

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

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

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

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

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

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

3.3 路由可靠性定義

在VANETs中，源節(jié)點s與目的節(jié)點d可能存在多條路由ω。每條路由由一系列的鏈路組成。不失一般性，對于某特定的路由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é)點s與目的節(jié)點d存在ω條路由。用M(s，d)={P1，P2，…，Pω}為源節(jié)點s與目的節(jié)點d路由集。在路由決策時，應(yīng)選取最可靠的路由作為數(shù)據(jù)轉(zhuǎn)發(fā)的通道，即按照式（10）選擇路由：

4 面向VANETs演化圖論模型

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

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

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

擴展后的演化圖論模型EEGM：

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

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

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

圖1 在t=0，t=5時的EEGM模型

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

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

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

5 移動模型

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

6 提出的EG-RAODV

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

6.1 EG-Dijkstra算法

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

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

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

圖2 EG-Dijkstra算法的示例

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

6.2 EG-RAODV路由特性

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

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

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

7 仿真分析

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

7.1 仿真環(huán)境

仿真區(qū)域為5 000m的三車道高速公路。30輛車（低密度交通流量）分布于仿真區(qū)域。車輛僅單方向行駛，到達高速公路末端，就退出仿真區(qū)域。三個車道的平均速度分別為40 km/h、60 km/h、80 km/h。針對兩個實驗場景進行仿真：

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

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

7.2 性能指標(biāo)

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

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

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

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

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

7.3 仿真結(jié)果

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

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

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

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

圖4 實驗A：路由請求消息率隨數(shù)據(jù)傳輸速率變化

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

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

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

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

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

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

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

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

圖8 實驗B：分組傳輸率隨路由請求消息率的變化

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

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

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

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

8 結(jié)論

針對VANETs的路由問題，本文展開了分析。首先擴展了演化圖論，并提出了EEGM的模型。同時，結(jié)合Dijkstra算法，提出EG-Dijkstra算法，并將此算法引入EEGM，用以尋找最可靠的通路MRJ。最后，從可靠性出發(fā)，提出EG-RAODV路由協(xié)議。針對高速公路場景進行仿真，并與PBR、AODV進行比較。結(jié)果表明提出的EG-RAODV在路由請求消息率、平均端到端傳輸時延、鏈路斷裂數(shù)以及分組傳輸率方面均比PBR、AODV高。這主要是因為EG-RAODV通過EEGM模型，計算所有通路的可靠值，并從中選用最可靠的數(shù)據(jù)通路作為數(shù)據(jù)的路由；同時，EG-RAODV中轉(zhuǎn)發(fā)節(jié)點不廣播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.