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

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

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

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

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

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

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

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

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

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

1.3可靠度

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

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

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

        在車載網(wǎng)絡(luò)當(dāng)中,，從源節(jié)點(diǎn)車輛s_r到目的節(jié)點(diǎn)車輛d_e可能存在多條傳輸路由,每條路由又由不同鏈路組成。對(duì)于任一條由k條鏈路組成的路徑P,，可以這樣表示k：l₁=(s_r,n₁),，l₂=(n₁,n₂)，…,，l_k=(n_k,d_e),，對(duì)于每條鏈路l_w(w=1,2,…,k)用r_t(l_w)表示鏈路可靠度值，對(duì)于路由P的可靠度定義為路由中各鏈路可靠度值的乘積,，即

2 基于增強(qiáng)型演進(jìn)圖的車載網(wǎng)路由機(jī)制

        由于車載網(wǎng)通過(guò)無(wú)線鏈路連接網(wǎng)絡(luò)節(jié)點(diǎn),，網(wǎng)絡(luò)拓?fù)洳粩嘧兓枰獙?shí)時(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)車輛都被訪問(wèn)完后,，該車輛最終會(huì)被標(biāo)記為已訪問(wèn)并且確定了其路由可靠度,。其算法的偽代碼如下：

        已知：車載網(wǎng)的演進(jìn)圖和源節(jié)點(diǎn)車輛s_r。變量：未訪問(wèn)車輛集合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)記為已訪問(wèn);

              (c) 對(duì)于車輛x的每一個(gè)鄰居車輛v,，如果車輛v沒(méi)被標(biāo)記為已訪問(wèn)且它們之間的鏈路可靠度不為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)圖的路由算法,，可通過(guò)圖4來(lái)舉例說(shuō)明。圖4代表某時(shí)刻基于增強(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,，但算法不會(huì)停止而是試圖找到其他到達(dá)目的節(jié)點(diǎn)的路由，最終找到一條通過(guò)車輛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ā)送路由請(qǐng)求包并在包中標(biāo)記路徑中需要經(jīng)過(guò)的車輛節(jié)點(diǎn)，因此路由發(fā)現(xiàn)過(guò)程中不需要廣播路由請(qǐng)求信息,，節(jié)約了大量網(wǎng)絡(luò)資源,。需要注意的是，即使中間節(jié)點(diǎn)車輛有最新的到達(dá)目的節(jié)點(diǎn)的路由,，它也不允許發(fā)送路由響應(yīng)包,，因?yàn)榭紤]到車載網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化性高，中間節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由信息很可能已經(jīng)過(guò)時(shí),。只有當(dāng)目的節(jié)點(diǎn)收到路由請(qǐng)求包時(shí)才發(fā)送路由響應(yīng)包到源節(jié)點(diǎn)車輛,。對(duì)于路由維護(hù)方面，本路由方案使用與AODV（Ad hoc on-demand distance vector routing）相同的恢復(fù)策略,，即在某個(gè)中間車輛發(fā)生斷鏈時(shí),，該車輛將發(fā)送路由錯(cuò)誤包來(lái)建立新的路由。

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

3.1仿真場(chǎng)景

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

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

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

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

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

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

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

參考文獻(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.