基于演化圖論的可靠的VANETs路由協議

盧進軍，龍英艷，潘宏利

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

2.陜西理工學院教育科學學院，陜西漢中723000

1 引言

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

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

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

2 相關研究

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

文獻[11]提出速度輔助路由協議。該協議利用轉發節點與目的節點的相對速度信息決策數據包的轉發路徑。通過目的節點的位置以及速度預測目的節點下一時刻的位置，并據此明確數據包的轉區域。

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

文獻[13]提出基于移動預測路由協議MOPR（Movement Prediction-based Routing）。MOPR預測車輛下一時刻的位置從而發現穩定的路由，當源節點與目節點間存在多條通路時，MOPR就從中選取最穩定的路由傳輸數據。

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

3 車輛可靠性模型

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

3.1 車輛分布

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

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

3.2 鏈路可靠性模型

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

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

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

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

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

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

3.3 路由可靠性定義

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

假定源節點s與目的節點d存在ω條路由。用M(s，d)={P1，P2，…，Pω}為源節點s與目的節點d路由集。在路由決策時，應選取最可靠的路由作為數據轉發的通道，即按照式（10）選擇路由：

4 面向VANETs演化圖論模型

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

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

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

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

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

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

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

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

此外，引用新的指標命為通路的可靠值（Journey Reliability）。通過該指標選擇轉發數據的通路。在數據轉發時，選取最可靠的通路（M ost Reliable Journey，MRJ），而不是最初的，最短、最快的通路。

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

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

5 移動模型

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

6 提出的EG-RAODV

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

6.1 EG-Dijkstra算法

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

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

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

圖2 EG-Dijkstra算法的示例

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

6.2 EG-RAODV路由特性

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

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

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

7 仿真分析

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

7.1 仿真環境

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

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

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

7.2 性能指標

在仿真過程中，利用以下性能指標評估網絡性能。

（1）分組傳輸率PDR（Packet Delivery Ratio）：目的節點成功接受到的數據包數目與在應用層的源節點發送的數據包數目之比；

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

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

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

7.3 仿真結果

（1）數據傳輸速率的變化對路由性能的影響

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

圖3 實驗A：分組傳輸率隨數據傳輸速率變化

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

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

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

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

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

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

（2）數據包大小的變化對路由性能的影響

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

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

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

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

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

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

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

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

8 結論

針對VANETs的路由問題，本文展開了分析。首先擴展了演化圖論，并提出了EEGM的模型。同時，結合Dijkstra算法，提出EG-Dijkstra算法，并將此算法引入EEGM，用以尋找最可靠的通路MRJ。最后，從可靠性出發，提出EG-RAODV路由協議。針對高速公路場景進行仿真，并與PBR、AODV進行比較。結果表明提出的EG-RAODV在路由請求消息率、平均端到端傳輸時延、鏈路斷裂數以及分組傳輸率方面均比PBR、AODV高。這主要是因為EG-RAODV通過EEGM模型，計算所有通路的可靠值，并從中選用最可靠的數據通路作為數據的路由；同時，EG-RAODV中轉發節點不廣播RREQ，只是定向傳播，節省了更多網絡資源。

[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，Ferreira 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，Filali 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.