車載網(wǎng)VANETs(Vehicular Ad hoc Networks)是在行駛的車輛間構建的一種新型的移動無線自組織網(wǎng)絡，可以實現(xiàn)車輛間的多跳無線通信^[1],。由于車輛高速運動導致網(wǎng)絡拓撲變化快,，傳統(tǒng)的移動自組網(wǎng)路由協(xié)議已無法勝任車載網(wǎng)的路由計算。參考文獻[2-3]提出了演進圖模型,，將其應用于網(wǎng)絡拓撲變化較慢場景,，獲得網(wǎng)絡的動態(tài)拓撲特征，基于此計算無線自組網(wǎng)中的路由,。車載網(wǎng)雖然網(wǎng)絡拓撲變化快,，但是車輛沿著一定的道路行駛，使得車載網(wǎng)網(wǎng)絡拓撲的變化具有一定的可預測性,，因此參考文獻[4]提出了適用于車載網(wǎng)的基于演進圖的路由協(xié)議EG-RAODV(Evolving Graph-based Reliable Ad hoc on-demand Distance Vector Routing),通過定義鏈路可靠度和路由可靠度預測車載網(wǎng)中鏈路和路由在下一時刻互相連通的概率,，基于此計算車載網(wǎng)中的可靠路由,。但是參考文獻[4]在計算鏈路可靠度和路由可靠度時,局限于具有同向恒定速率的交通流場景所構建的演進圖模型，不能如實反映交通環(huán)境,，對于雙向可變速車流環(huán)境鏈路可靠度的計算不準確,，最終會導致車載網(wǎng)路由可靠度的降低?；诖?，本文提出基于增強型演進圖的路由算法，首先,，對于雙向可變速交通流等不同場景構建增強型演進圖,，如實反映交通環(huán)境，獲得車載網(wǎng)的動態(tài)變化信息,；再基于增強型演進圖,，應用參考文獻[4]的可靠度定義計算鏈路可靠度和路由可靠度；最后,，基于增強型演進圖和計算所得可靠度,，從源節(jié)點到目的節(jié)點計算一條最可靠的路由。

1 增強型演進圖建模

1.1演進圖

        在動態(tài)網(wǎng)絡中,，演進圖^[5]由一個t₀時刻給定的網(wǎng)絡拓撲圖及其計算預測的λ個索引序列的子圖構成的圖集,。每一個子圖表示對一定時間間隔內(nèi)計算預測得到網(wǎng)絡鏈路狀態(tài)圖。車輛和無線鏈路分別建模成圖中的節(jié)點和邊,。圖1所示為演進圖模型,。

        在圖1中，邊上的值代表鏈路存在的時間,?？梢哉f路徑A→D→C是不合格的，因為后面的鏈路D→C比前面的鏈路A→D存在時間短,。因此,，在演進圖論中路由中的鏈路生存時間必須成遞增序列。從圖中可以看出,，A→B→E→G是符合要求的路由,。

1.2 增強型演進圖

        在高速公路雙向可變速交通流中，假定每輛車配備全球定位系統(tǒng)GPS(Global Positioning System),，通過它可以獲得車輛位置和速度等信息,。t₀時刻相鄰車輛無線鏈路的持續(xù)連接時間T_p與無線傳輸距離H及其車輛的相對速度和位置有關。通過圖2四個車流場景圖可以計算出T_p的值,。

        圖2中,，L_ij代表車輛間的相對位置，V_i和V_j分別代表t₀時刻車輛速度大小,。

        對于EG-RAODV路由協(xié)議鏈路可靠度中的T_p值的計算只適用于圖2(a)場景1,，如果運用到圖2(b)場景2來計算T_p值,，勢必引起T_p值的減少，導致鏈路可靠度降低,，稱這種現(xiàn)象為短連接,，即鏈路連接時間的計算值比實際連接時間短；如果運用到圖2(c)場景3來計算T_p值,，勢必引起T_p值的增大,，導致鏈路可靠度虛增加，稱這種現(xiàn)象為虛連接,，即鏈路連接時間的計算值比實際連接時間長,；如果運用到圖2(d)場景4，則短連接和虛連接兩種現(xiàn)象可能同時存在,。

        假設源節(jié)點車輛在任何時刻都有全網(wǎng)的通信狀態(tài)圖,。對于不同時刻，無線鏈路的可靠度根據(jù)上文不同的場景來計算,，避免了短連接和虛連接現(xiàn)象的發(fā)生,，從而確保了鏈路可靠度的真實有效性,，以此構造出的演進圖即為本文所定義的增強型演進圖,。

        為了更好地理解增強型演進圖模型，在圖3中演示不同時刻t=0 s和t=5 s的增強型演進圖樣例,。圖中,，每個節(jié)點代表高速公路上的車輛，節(jié)點間的連線代表車輛間的通信鏈路,，每條連線上都有一個二元數(shù)組,，第一個元素代表當前時刻，第二個元素代表鏈路可靠度,。

        在圖3(a)t=0 s時,，每條鏈路的可靠度都大于0，代表鏈路都可用;當t=5 s時如圖3(b),，由于網(wǎng)絡拓撲改變,，出現(xiàn)邊{B,E}的可靠度值為0的情況，此時代表車輛B和E之間的鏈路斷開不能進行信息的直接傳遞,。

1.3可靠度

        可靠度包括鏈路可靠度和路由可靠度,。

　 鏈路可靠度是指兩輛車之間在時刻t₀存在一條直接相連的通信鏈路并保持連續(xù)通信一段時間的可能性大小^[4]。即：r(l)=P{連續(xù)可通信直到t₀+T_p|t₀時刻可通信}

        假設速度服從正態(tài)分布^[6],，則對于4種場景下鏈路可靠度的表達式為：

        在車載網(wǎng)絡當中,，從源節(jié)點車輛s_r到目的節(jié)點車輛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 基于增強型演進圖的車載網(wǎng)路由機制

        由于車載網(wǎng)通過無線鏈路連接網(wǎng)絡節(jié)點,，網(wǎng)絡拓撲不斷變化,，需要實時維護網(wǎng)絡拓撲與鏈路信息，為在車載網(wǎng)中計算路由提供依據(jù),，因此,，本文所提基于增強型演進圖的車載網(wǎng)路由機制包括基于增強型演進圖的車載網(wǎng)路由算法和路由發(fā)現(xiàn)與維護機制。

2.1基于增強型演進圖的車載網(wǎng)路由算法

        該算法維系一種可靠圖表, 該可靠圖表包含車載網(wǎng)當中車輛節(jié)點信息以及它們到其他車輛的最佳路由可靠度信息,。在算法的初始化中,，令源節(jié)點車輛s_r的路由可靠度R(s_r)=1，其他車輛的路徑可靠度為R(u)=§,。然后依據(jù)式(2)求得源節(jié)點到目的節(jié)點車輛的路由可靠度,，當當前車輛的所有鄰居節(jié)點車輛都被訪問完后，該車輛最終會被標記為已訪問并且確定了其路由可靠度,。其算法的偽代碼如下：

        已知：車載網(wǎng)的演進圖和源節(jié)點車輛s_r,。變量：未訪問車輛集合Q。

        求：可靠圖表,。該圖表包含從源節(jié)點車輛s_r到其他車輛的最可靠路由,。

        (1)設置路由可靠度值。令源節(jié)點車輛可靠度值R(s_r)=1,其他車輛可靠度值R(u)=§,。

        (2) 先令集合Q為空,，再將s_r加入到集合Q中。

        (3) 當集合Q不為空集,，執(zhí)行以下步驟：

              (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) 獲得源節(jié)點車輛的可靠圖表

        為了更好地了解基于增強型演進圖的路由算法,，可通過圖4來舉例說明。圖4代表某時刻基于增強型演進圖的路由算法樣例,。在樣例中,，源車輛sr為節(jié)點0，目的車輛為節(jié)點5，節(jié)點之間連線旁的數(shù)值為鏈路可靠度,，每一車輛都持有它的節(jié)點ID和它的路由可靠度,。基于增強型演進圖的路由算法發(fā)現(xiàn)源節(jié)點車輛s_r的鄰節(jié)點車輛1和2并分配了路由可靠度值,，如圖4(a),。繼而，節(jié)點1車輛很快發(fā)現(xiàn)目的節(jié)點車輛節(jié)點5,，并同樣地分配了路由最可靠度值0.09,，如圖4(b)。雖然已找到目的節(jié)點車輛5,，但算法不會停止而是試圖找到其他到達目的節(jié)點的路由,，最終找到一條通過車輛3、4,、6的路由并計算到路由可靠度值為0.13,如圖4(c),顯然0.13>0.09,，于是最終選擇傳輸路徑0→2→3→4→6→5作為最佳路由，如圖4(d),。

2.2路由發(fā)現(xiàn)與維護機制

        由上文所述,，當源節(jié)點獲得全網(wǎng)的增強型演進圖信息后，基于增強型演進圖的路由算法可找到目的節(jié)點的最可靠路由,。接著,，源節(jié)點車輛將沿著這條路徑發(fā)送路由請求包并在包中標記路徑中需要經(jīng)過的車輛節(jié)點，因此路由發(fā)現(xiàn)過程中不需要廣播路由請求信息,，節(jié)約了大量網(wǎng)絡資源,。需要注意的是,，即使中間節(jié)點車輛有最新的到達目的節(jié)點的路由,，它也不允許發(fā)送路由響應包，因為考慮到車載網(wǎng)絡拓撲動態(tài)變化性高,，中間節(jié)點到目的節(jié)點的路由信息很可能已經(jīng)過時,。只有當目的節(jié)點收到路由請求包時才發(fā)送路由響應包到源節(jié)點車輛。對于路由維護方面,，本路由方案使用與AODV（Ad hoc on-demand distance vector routing）相同的恢復策略,，即在某個中間車輛發(fā)生斷鏈時，該車輛將發(fā)送路由錯誤包來建立新的路由,。

3 仿真結果與分析

3.1仿真場景

        實驗采用基于離散事件的網(wǎng)絡模擬工具NS2,。對EG-RAODV和本文提出的基于增強型演進圖路由EEGR(Enhanced Evolving Graph-based Routing)協(xié)議在場景2、3和4情況下對數(shù)據(jù)包到達率,、路由請求率和端到端的延遲進行比較,。選擇雙向6車道長5 000 m的高速公路，每一方向各30輛車,，從里到外各車道的最高限速分別為120 km/h,、90 km/h和60 km/h,，無線通信距離為300 m。

3.2 仿真結果與分析

        本文令數(shù)據(jù)傳輸速率為恒定速率128 kb/s,，通過改變源節(jié)點車輛發(fā)送的分組包大小來比較EEGR和EG-RAODV路由協(xié)議在平均數(shù)據(jù)到達率,、平均路由請求率和平均端到端延遲的性能。

        圖5為場景2下的比較,。由于EG-RAODV路由協(xié)議中鏈路連接時間Tp的計算值比實際的短,，導致演進圖中鏈路可靠度的值減小，出現(xiàn)短連接現(xiàn)象,，而提出的EEGR使用了擴展的可靠度計算方法,避免了假連接的現(xiàn)象,，結果表現(xiàn)出更好的性能。需要注意的是隨著分組包的增大,，會引起分段的次數(shù)增多,一個分段的錯誤傳輸就會引起整個分組包的傳輸失敗,，繼而產(chǎn)生新的路由發(fā)現(xiàn)過程。因此隨著分組包增加,會出現(xiàn)分組到達率曲線遞減,、路由請求率曲線遞增和端到端時延曲線遞增的現(xiàn)象,。

        圖6為場景3下的比較，由于EG-RAODV路由協(xié)議中鏈路連接時間T_p的計算值比實際的要長,，導致演進圖中鏈路可靠度比真實值偏大,，出現(xiàn)虛連接現(xiàn)象，而本文提出的EEGR路由協(xié)議使用擴展了的可靠度計算方法,，避免了假連接的現(xiàn)象,，所以性能更好。 

        對于圖7場景4的情況,，由于EG-RAODV路由協(xié)議中會出現(xiàn)短連接或者虛連接現(xiàn)象,， 而本文提出的EEGR卻可以避免，正確反映動態(tài)網(wǎng)絡的可靠度特性,，所以結果優(yōu)勢更明顯,。

        演進圖能夠預測網(wǎng)絡拓撲的動態(tài)變化，能夠保證車載網(wǎng)在高度動態(tài)變化的網(wǎng)絡場景中計算具有可靠連接的路由,。本文提出基于增強型演進圖的車載網(wǎng)路由算法,，對實際路況進行建模，構造增強型演進圖,，基于增強型演進圖在車載網(wǎng)中,，由源節(jié)點到目的節(jié)點計算最可靠的路由， 保證所得路由的連通性,。通過仿真分析,，本文提出的路由算法能夠提高分組包的到達率、降低了路由請求率以及信息包的端到端時延。

參考文獻

[1] 常促宇,，向勇,，史美林．車載自組網(wǎng)的現(xiàn)狀與發(fā)展[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.