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

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

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

        對(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)致鏈路可靠度降低，稱(chēng)這種現(xiàn)象為短連接，即鏈路連接時(shí)間的計(jì)算值比實(shí)際連接時(shí)間短；如果運(yùn)用到圖2(c)場(chǎng)景3來(lái)計(jì)算T_p值，勢(shì)必引起T_p值的增大，導(dǎo)致鏈路可靠度虛增加，稱(chēng)這種現(xiàn)象為虛連接，即鏈路連接時(shí)間的計(jì)算值比實(shí)際連接時(shí)間長(zhǎng)；如果運(yùn)用到圖2(d)場(chǎng)景4，則短連接和虛連接兩種現(xiàn)象可能同時(shí)存在。

        假設(shè)源節(jié)點(diǎn)車(chē)輛在任何時(shí)刻都有全網(wǎng)的通信狀態(tài)圖。對(duì)于不同時(shí)刻，無(wú)線(xiàn)鏈路的可靠度根據(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)代表高速公路上的車(chē)輛，節(jié)點(diǎn)間的連線(xiàn)代表車(chē)輛間的通信鏈路，每條連線(xià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ù)涓淖儯霈F(xiàn)邊{B,E}的可靠度值為0的情況，此時(shí)代表車(chē)輛B和E之間的鏈路斷開(kāi)不能進(jìn)行信息的直接傳遞。

1.3可靠度

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

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

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

        在車(chē)載網(wǎng)絡(luò)當(dāng)中，從源節(jié)點(diǎn)車(chē)輛s_r到目的節(jié)點(diǎn)車(chē)輛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)圖的車(chē)載網(wǎng)路由機(jī)制

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

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

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

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

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

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

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

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

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

              (b) 將x標(biāo)記為已訪(fǎng)問(wèn);

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

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

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

        為了更好地了解基于增強(qiáng)型演進(jìn)圖的路由算法，可通過(guò)圖4來(lái)舉例說(shuō)明。圖4代表某時(shí)刻基于增強(qiáng)型演進(jìn)圖的路由算法樣例。在樣例中，源車(chē)輛sr為節(jié)點(diǎn)0，目的車(chē)輛為節(jié)點(diǎn)5，節(jié)點(diǎn)之間連線(xiàn)旁的數(shù)值為鏈路可靠度，每一車(chē)輛都持有它的節(jié)點(diǎn)ID和它的路由可靠度?；谠鰪?qiáng)型演進(jìn)圖的路由算法發(fā)現(xiàn)源節(jié)點(diǎn)車(chē)輛s_r的鄰節(jié)點(diǎn)車(chē)輛1和2并分配了路由可靠度值，如圖4(a)。繼而，節(jié)點(diǎn)1車(chē)輛很快發(fā)現(xiàn)目的節(jié)點(diǎn)車(chē)輛節(jié)點(diǎn)5，并同樣地分配了路由最可靠度值0.09，如圖4(b)。雖然已找到目的節(jié)點(diǎn)車(chē)輛5，但算法不會(huì)停止而是試圖找到其他到達(dá)目的節(jié)點(diǎn)的路由，最終找到一條通過(guò)車(chē)輛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)車(chē)輛將沿著這條路徑發(fā)送路由請(qǐng)求包并在包中標(biāo)記路徑中需要經(jīng)過(guò)的車(chē)輛節(jié)點(diǎn)，因此路由發(fā)現(xiàn)過(guò)程中不需要廣播路由請(qǐng)求信息，節(jié)約了大量網(wǎng)絡(luò)資源。需要注意的是，即使中間節(jié)點(diǎn)車(chē)輛有最新的到達(dá)目的節(jié)點(diǎn)的路由，它也不允許發(fā)送路由響應(yīng)包，因?yàn)榭紤]到車(chē)載網(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)車(chē)輛。對(duì)于路由維護(hù)方面，本路由方案使用與AODV（Ad hoc on-demand distance vector routing）相同的恢復(fù)策略，即在某個(gè)中間車(chē)輛發(fā)生斷鏈時(shí)，該車(chē)輛將發(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車(chē)道長(zhǎng)5 000 m的高速公路，每一方向各30輛車(chē)，從里到外各車(chē)道的最高限速分別為120 km/h、90 km/h和60 km/h，無(wú)線(xiàn)通信距離為300 m。

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

        本文令數(shù)據(jù)傳輸速率為恒定速率128 kb/s，通過(guò)改變?cè)垂?jié)點(diǎn)車(chē)輛發(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á)率曲線(xiàn)遞減、路由請(qǐng)求率曲線(xiàn)遞增和端到端時(shí)延曲線(xiàn)遞增的現(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)變化，能夠保證車(chē)載網(wǎng)在高度動(dòng)態(tài)變化的網(wǎng)絡(luò)場(chǎng)景中計(jì)算具有可靠連接的路由。本文提出基于增強(qiáng)型演進(jìn)圖的車(chē)載網(wǎng)路由算法，對(duì)實(shí)際路況進(jìn)行建模，構(gòu)造增強(qiáng)型演進(jìn)圖，基于增強(qiáng)型演進(jìn)圖在車(chē)載網(wǎng)中，由源節(jié)點(diǎn)到目的節(jié)點(diǎn)計(jì)算最可靠的路由， 保證所得路由的連通性。通過(guò)仿真分析，本文提出的路由算法能夠提高分組包的到達(dá)率、降低了路由請(qǐng)求率以及信息包的端到端時(shí)延。

參考文獻(xiàn)

[1] 常促宇，向勇，史美林．車(chē)載自組網(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.