車載網(wǎng)VANETs(Vehicular Ad hoc Networks)是在行駛的車輛間構(gòu)建的一種新型的移動無線自組織網(wǎng)絡(luò)，可以實(shí)現(xiàn)車輛間的多跳無線通信^[1]。由于車輛高速運(yùn)動導(dǎo)致網(wǎng)絡(luò)拓?fù)渥兓?，傳統(tǒng)的移動自組網(wǎng)路由協(xié)議已無法勝任車載網(wǎng)的路由計(jì)算。參考文獻(xiàn)[2-3]提出了演進(jìn)圖模型，將其應(yīng)用于網(wǎng)絡(luò)拓?fù)渥兓^慢場景，獲得網(wǎng)絡(luò)的動態(tài)拓?fù)涮卣鳎诖擞?jì)算無線自組網(wǎng)中的路由。車載網(wǎng)雖然網(wǎng)絡(luò)拓?fù)渥兓?，但是車輛沿著一定的道路行駛，使得車載網(wǎng)網(wǎng)絡(luò)拓?fù)涞淖兓哂幸欢ǖ目深A(yù)測性，因此參考文獻(xiàn)[4]提出了適用于車載網(wǎng)的基于演進(jìn)圖的路由協(xié)議EG-RAODV(Evolving Graph-based Reliable Ad hoc on-demand Distance Vector Routing),通過定義鏈路可靠度和路由可靠度預(yù)測車載網(wǎng)中鏈路和路由在下一時刻互相連通的概率，基于此計(jì)算車載網(wǎng)中的可靠路由。但是參考文獻(xiàn)[4]在計(jì)算鏈路可靠度和路由可靠度時,局限于具有同向恒定速率的交通流場景所構(gòu)建的演進(jìn)圖模型，不能如實(shí)反映交通環(huán)境，對于雙向可變速車流環(huán)境鏈路可靠度的計(jì)算不準(zhǔn)確，最終會導(dǎo)致車載網(wǎng)路由可靠度的降低?；诖耍疚奶岢龌?a class="innerlink" href="http://ihrv.cn/tags/增強(qiáng)型演進(jìn)圖" title="增強(qiáng)型演進(jìn)圖" target="_blank">增強(qiáng)型演進(jìn)圖的路由算法，首先，對于雙向可變速交通流等不同場景構(gòu)建增強(qiáng)型演進(jìn)圖，如實(shí)反映交通環(huán)境，獲得車載網(wǎng)的動態(tài)變化信息；再基于增強(qiáng)型演進(jìn)圖，應(yīng)用參考文獻(xiàn)[4]的可靠度定義計(jì)算鏈路可靠度和路由可靠度；最后，基于增強(qiáng)型演進(jìn)圖和計(jì)算所得可靠度，從源節(jié)點(diǎn)到目的節(jié)點(diǎn)計(jì)算一條最可靠的路由。

1 增強(qiáng)型演進(jìn)圖建模

1.1演進(jìn)圖

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

        在圖1中，邊上的值代表鏈路存在的時間?？梢哉f路徑A→D→C是不合格的，因?yàn)楹竺娴逆溌稤→C比前面的鏈路A→D存在時間短。因此，在演進(jìn)圖論中路由中的鏈路生存時間必須成遞增序列。從圖中可以看出，A→B→E→G是符合要求的路由。

1.2 增強(qiáng)型演進(jìn)圖

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

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

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

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

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

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

1.3可靠度

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

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

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

        在車載網(wǎng)絡(luò)當(dāng)中，從源節(jié)點(diǎn)車輛s_r到目的節(jié)點(diǎn)車輛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 基于增強(qiáng)型演進(jìn)圖的車載網(wǎng)路由機(jī)制

        由于車載網(wǎng)通過無線鏈路連接網(wǎng)絡(luò)節(jié)點(diǎn)，網(wǎng)絡(luò)拓?fù)洳粩嘧兓枰獙?shí)時維護(hù)網(wǎng)絡(luò)拓?fù)渑c鏈路信息，為在車載網(wǎng)中計(jì)算路由提供依據(jù)，因此，本文所提基于增強(qiáng)型演進(jìn)圖的車載網(wǎng)路由機(jī)制包括基于增強(qiáng)型演進(jìn)圖的車載網(wǎng)路由算法和路由發(fā)現(xiàn)與維護(hù)機(jī)制。

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

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

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

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

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

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

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

              (a) 在Q中找到可靠度最高的車輛x;

              (b) 將x標(biāo)記為已訪問;

              (c) 對于車輛x的每一個鄰居車輛v，如果車輛v沒被標(biāo)記為已訪問且它們之間的鏈路可靠度不為0，可求得車輛v的路由可靠度R(v)=R(x)×r_t(e),其中r_t(e)為車輛v與車輛x之間的鏈路可靠度值；將v加入到集合Q中；

              (d) 將x從集合Q中移除，返回到(c)。

        (4) 獲得源節(jié)點(diǎn)車輛的可靠圖表

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

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

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

3 仿真結(jié)果與分析

3.1仿真場景

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

3.2 仿真結(jié)果與分析

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

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

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

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

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

參考文獻(xiàn)

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