車載網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.