0 引言

    車(chē)聯(lián)網(wǎng)VANETs(Vehicle Ad Hoc Networks)已成為研究熱點(diǎn)，車(chē)聯(lián)網(wǎng)的實(shí)施有利于提高行駛安全性^[1-2]。車(chē)輛的快速移動(dòng)及車(chē)輛分布的不均勻性，給VANETs路由協(xié)議設(shè)計(jì)提出了挑戰(zhàn)。相比于基于拓?fù)渎酚桑?a class="innerlink" href="http://ihrv.cn/tags/地理信息路由" title="地理信息路由" target="_blank">地理信息路由更適合應(yīng)用于拓?fù)鋭?dòng)態(tài)變化的車(chē)聯(lián)網(wǎng)中，能更好地適應(yīng)拓?fù)浣Y(jié)構(gòu)變化，具有簡(jiǎn)單高效、低負(fù)載等特點(diǎn)。因此受到更廣泛的關(guān)注^[3-6]。

    地理信息路由常采用貪婪轉(zhuǎn)發(fā)策略，其是從鄰居節(jié)點(diǎn)中選擇離目的節(jié)點(diǎn)最近的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。該策略復(fù)雜度低、易實(shí)現(xiàn)，適用于動(dòng)態(tài)變化的網(wǎng)絡(luò)^[7]。然而，真實(shí)環(huán)境中，僅利用鄰居節(jié)點(diǎn)和目的節(jié)點(diǎn)位置信息決策路由的地理信息路由并不具有良好的路由性能。因?yàn)椋S著源節(jié)點(diǎn)與下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)間距離的增加，信號(hào)衰減和數(shù)據(jù)包丟失率也隨之增加^[8-9]，這就降低了數(shù)據(jù)包傳輸成功率，并增加了路由開(kāi)銷。

    在2000年，B.Karp等人提出基于地理信息路由協(xié)議GPSR（Greedy Perimeter Stateless Routing）^[10]。GPSR協(xié)議實(shí)施貪婪轉(zhuǎn)發(fā)策略，通過(guò)距離值選擇下一跳節(jié)點(diǎn)，離目標(biāo)節(jié)點(diǎn)最近節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。然而，僅采用簡(jiǎn)單的貪婪轉(zhuǎn)發(fā)策略，很容易陷入局部最小化，即路由空洞。

    文獻(xiàn)[11]提出了基于GPSR的改進(jìn)協(xié)議GPCR。當(dāng)遭遇局部最小化(空洞)時(shí)，采用邊界轉(zhuǎn)發(fā)，數(shù)據(jù)包攜帶節(jié)點(diǎn)引用右手規(guī)則進(jìn)行尋找下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。此外，文獻(xiàn)[7]提出一種基于感知空洞形狀的分段貪婪路由EMCG(Easy Modeling Greedy Routing)協(xié)議。EMGR協(xié)議采用了空洞邊界探測(cè)包，通過(guò)這些探測(cè)包收集位于邊界節(jié)點(diǎn)的信息，并依據(jù)這些信息，獲取空洞形狀，最后依據(jù)形狀，尋找最合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)。然而，該協(xié)議需要耗盡過(guò)多資源收集邊界節(jié)點(diǎn)信息。

    文獻(xiàn)[12]提出了基于在線導(dǎo)航系統(tǒng)的RBVT-R協(xié)議。通過(guò)一系列高網(wǎng)絡(luò)連接率的十字路口建立源節(jié)點(diǎn)與目的節(jié)點(diǎn)間的路徑。然而，由于路由決策過(guò)程中需要使用實(shí)時(shí)的交通信息，致使節(jié)點(diǎn)能夠感知城市地圖，增加了復(fù)雜度，提高了RBVT-R路由對(duì)網(wǎng)絡(luò)條件的適應(yīng)能力。

    上述的路由協(xié)議均在強(qiáng)調(diào)如何提高數(shù)據(jù)包轉(zhuǎn)發(fā)率問(wèn)題，但是這些路由協(xié)議并沒(méi)有考慮到城市環(huán)境下，長(zhǎng)距離傳輸數(shù)據(jù)包的成功與否受多方面因素影響。特別是，這些協(xié)議均沒(méi)有考慮節(jié)點(diǎn)間的移動(dòng)的相對(duì)方向以及鏈路質(zhì)量。為此，本文提出面向VANETs城市場(chǎng)景下一種優(yōu)化的地理信息路由協(xié)議，記為IGR(Improved geographical)。IGR協(xié)議在選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，不再使用貪婪轉(zhuǎn)發(fā)策略，而是結(jié)合節(jié)點(diǎn)的位置、無(wú)線鏈路質(zhì)量以及節(jié)點(diǎn)的移動(dòng)方向這三方面信息，并將這些信息融合成競(jìng)爭(zhēng)資本，最后，依據(jù)競(jìng)爭(zhēng)資本選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。仿真結(jié)果表明，提出的IGR協(xié)議能夠有效地提高數(shù)據(jù)包傳遞率、縮短了端到端傳輸時(shí)延，減少了平均跳數(shù)。

1 IGR協(xié)議

    在動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)中，僅基于單一指標(biāo)選擇從源節(jié)點(diǎn)至目的節(jié)點(diǎn)的路由可能是次優(yōu)解。眾多的因素影響了車(chē)輛間無(wú)線鏈路，如車(chē)輛行駛方向、距離以及鏈路質(zhì)量。當(dāng)數(shù)據(jù)包攜帶車(chē)輛需要尋找下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，該車(chē)輛應(yīng)該依據(jù)鄰近車(chē)輛離目的節(jié)點(diǎn)的距離、行駛的相對(duì)方向以及鏈路質(zhì)量等信息決策路由，進(jìn)而選擇最優(yōu)的數(shù)據(jù)包轉(zhuǎn)發(fā)節(jié)點(diǎn)。為此，提出的IGR協(xié)議將距離、行駛相對(duì)方向以及鏈路質(zhì)量三項(xiàng)信息融合成一個(gè)競(jìng)爭(zhēng)資本函數(shù)，源節(jié)點(diǎn)就通過(guò)競(jìng)爭(zhēng)資本函數(shù)擇優(yōu)選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

1.1 臨近率

    數(shù)據(jù)包攜帶車(chē)輛計(jì)算鄰居車(chē)輛的臨近率AR(Approaching the destination Ratio)，其反映了鄰居車(chē)輛離目的節(jié)點(diǎn)距離的遠(yuǎn)近。假定車(chē)輛i的臨近率AR_i定義如式(1)所示。

其中D_s表示源車(chē)輛離目的車(chē)輛的距離、D_i表示車(chē)輛i離目的車(chē)輛的距離。從式(1)可知，臨近率AR反映了距離信息。AR越大，車(chē)輛離目的車(chē)輛越近，具有成為下一跳數(shù)據(jù)包轉(zhuǎn)發(fā)節(jié)點(diǎn)的優(yōu)先權(quán)越大。

1.2 相對(duì)方向

    不失一般性，可認(rèn)為兩車(chē)輛之間要么以相同方向行駛，要么以相反方向行駛，并且車(chē)輛行駛方向受限于街道和十字路口。由于車(chē)輛行駛方向的兩極性，相比于反方向車(chē)輛間的路由，處于同方向行駛的車(chē)輛間的路由更趨于穩(wěn)定^[13]。

    因此，將車(chē)輛行駛方向納入選擇下一跳數(shù)據(jù)包轉(zhuǎn)發(fā)的指標(biāo)，將同方向的行駛車(chē)輛給予更高的轉(zhuǎn)發(fā)優(yōu)先權(quán)。需要指明的是，同方向不是指兩車(chē)輛方向夾角為0°，而方向夾角小于預(yù)設(shè)的值，就認(rèn)為兩車(chē)輛同向。下面計(jì)算方向夾角。

    如圖1所示，設(shè)定節(jié)點(diǎn)i在t₁時(shí)刻的位置為(x₁，y₁)，在t₂時(shí)刻它移動(dòng)到了位置(x₂，y₂)。擁有數(shù)據(jù)包的節(jié)點(diǎn)C的位置是(x_C，y_C)，目標(biāo)節(jié)點(diǎn)d的位置為(x_d，y_d)。在這種情況下，鄰居節(jié)點(diǎn)i的移動(dòng)速度，數(shù)據(jù)包轉(zhuǎn)發(fā)方向v_i與節(jié)點(diǎn)移動(dòng)方向之間的切角φ_i由式(2)和式(3)計(jì)算得到。 

    除了考慮方向因素之處，在數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程中還需考慮無(wú)線信道質(zhì)量。

1.3 Beacon接收率

    假定車(chē)輛i，其一跳鄰居車(chē)輛集為N_i，則車(chē)輛i的Beacon接收率BRR(Beacon Reception Rate)：

1.4 競(jìng)爭(zhēng)資本函數(shù)

    引用文獻(xiàn)[14-15]提出的評(píng)價(jià)函數(shù)，將臨近率、方向和beacon接收率折算成一個(gè)指標(biāo)。由于在本文提出的IGR協(xié)議中，只考慮了3個(gè)路由指標(biāo)，因此，車(chē)輛的競(jìng)爭(zhēng)資本表達(dá)式為：

    其中，Γ為評(píng)價(jià)函數(shù)，SP_max表示評(píng)價(jià)函數(shù)最大時(shí)的選擇概率，β為變量，其標(biāo)識(shí)了路由指標(biāo)的最大值α₁、α₂、α₃為三個(gè)指標(biāo)的權(quán)值系統(tǒng)。

    當(dāng)式(7)的導(dǎo)數(shù)等于零時(shí)，Γ_i達(dá)到最大。因此，β為：

    式(7)中各項(xiàng)分別取最大值時(shí)，可計(jì)算β值。AR_max值可依據(jù)車(chē)輛無(wú)線通信范圍以及仿真進(jìn)行估計(jì)，可得AR_max=10，而方向最大值DR_max=1。beacon接收率BRR在0～1間取值，因此BRR_max=1。SP_max為概率，SP_max=1。  

2 性能分析

2.1 仿真模型

    利用MATLAB軟件以及NS2建立仿真平臺(tái)，對(duì)提出的IGR協(xié)議進(jìn)行仿真，并與GPCR和RBVT-R協(xié)議進(jìn)行比較。主要考查數(shù)據(jù)包傳遞率PDR(Packet Delivery Ratio)、端到端傳輸時(shí)延EED(End to end delay)以及跳數(shù)HC(Hop Count)三方面的路由性能。

    仿真區(qū)域選取上海市大小為3 968 m×1 251 m的矩形區(qū)域，含有370條道路、124個(gè)十字路口。在仿真過(guò)程中，利用STRAW(STreet RAndom Way)建立車(chē)輛隨機(jī)移動(dòng)模型。

    在仿真區(qū)域內(nèi)，車(chē)輛數(shù)從100～350變化。每個(gè)車(chē)輛產(chǎn)生beacon包的周期為0.5 s，產(chǎn)生的數(shù)據(jù)包大小為512 B。詳細(xì)的仿真參數(shù)如表1所示。

2.2 仿真結(jié)果及分析

    本次實(shí)驗(yàn)?zāi)康脑谟诳疾榻煌芏葘?duì)IGR協(xié)議的性能影響。通過(guò)實(shí)驗(yàn)，能夠觀察三個(gè)協(xié)議應(yīng)對(duì)交通密度的性能。實(shí)驗(yàn)中，車(chē)輛的速度設(shè)為50 km/h，數(shù)據(jù)包源車(chē)輛數(shù)為15個(gè)，密度數(shù)從100～350變化。仿真結(jié)果如圖2所示。

    從圖2可知，GPCR協(xié)議的PDR性能最差，特別是在低密度區(qū)域。這主要是因?yàn)镚PCR利用貪婪轉(zhuǎn)發(fā)策略去選擇下一跳數(shù)據(jù)包轉(zhuǎn)發(fā)車(chē)輛，即選擇離目的車(chē)輛最短路徑的車(chē)輛作為下一跳轉(zhuǎn)發(fā)車(chē)輛。由于車(chē)輛的快速移動(dòng)，車(chē)輛間的鏈路是非常脆弱的，這就導(dǎo)致轉(zhuǎn)發(fā)至目的車(chē)輛的數(shù)據(jù)包非常少。然而，隨著車(chē)輛密度的增加，GPCR協(xié)議向目的節(jié)點(diǎn)成功轉(zhuǎn)發(fā)的數(shù)據(jù)包也隨之增加。此外，RBVT-R協(xié)議在車(chē)輛數(shù)增加時(shí)具有更好的性能，這是由于車(chē)輛數(shù)增加，網(wǎng)絡(luò)連接概率隨之提高，促進(jìn)了更多的數(shù)據(jù)包轉(zhuǎn)發(fā)。相比于GPCR、RBVT-R，提出的IGR協(xié)議具有較好的性能，因?yàn)镮GR協(xié)議從鏈路質(zhì)量、方向以及距離三方面信息選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

    3個(gè)協(xié)議的數(shù)據(jù)包平均傳輸時(shí)延隨節(jié)點(diǎn)密度變化曲線如圖3所示。從圖3可知，提出的IGR協(xié)議的EED最小。原因在于IGR協(xié)議向目的節(jié)點(diǎn)傳輸數(shù)據(jù)包時(shí)選擇了最優(yōu)鏈路的路徑，降低了因鏈路不穩(wěn)定而引起的數(shù)據(jù)包丟失概率。然而，隨著車(chē)輛密度的增加，時(shí)延也隨之增加。由于車(chē)輛密度的增加，使得IGR協(xié)議需要消耗更多時(shí)間去決策下一跳數(shù)據(jù)包轉(zhuǎn)發(fā)節(jié)點(diǎn)。此外，從圖3可知，RBVT-R協(xié)議的EED隨車(chē)輛密度增加而呈下降趨勢(shì)，原因在于已建立的路由在較長(zhǎng)時(shí)間內(nèi)仍保持穩(wěn)定，避免了頻繁建立路由，進(jìn)而縮短了傳輸時(shí)延。

    圖4描述了傳輸?shù)钠骄鴶?shù)隨車(chē)輛密度的變化曲線。與GPCR協(xié)議相比，提出的IGR協(xié)議在向目的節(jié)點(diǎn)傳輸數(shù)據(jù)包時(shí)，需要更多的跳數(shù)，傳輸路徑更長(zhǎng)。IGR協(xié)議在數(shù)據(jù)包傳遞率和平均時(shí)延方面優(yōu)于GPCR協(xié)議。

3 總結(jié)

    為了滿足VANET城市場(chǎng)景下路由協(xié)議的性能要求，提出了一種地理信息路由的優(yōu)化協(xié)議。提出的IGR協(xié)議在數(shù)據(jù)包轉(zhuǎn)發(fā)過(guò)程中，不再考慮傳統(tǒng)地理信息路由協(xié)議的基于地理位置貪婪轉(zhuǎn)發(fā)策略，而是利用源車(chē)輛離候選車(chē)輛間的相對(duì)移動(dòng)方向、候選車(chē)輛離目的車(chē)輛間的距離以及beacon接收率三方面信息選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。仿真數(shù)據(jù)證實(shí)了IGR協(xié)議在降低數(shù)據(jù)包傳輸時(shí)延，提高數(shù)據(jù)包傳輸率方面的優(yōu)越性。

參考文獻(xiàn)

[1] MISRA S，Venkata Krishna，SARITHA V.LACAV：an energyefficient channel assignment mechanism for vehicular ad hoc networks[J].J.Supercomput.，2012，62(3)：1241-1262.

[2] AKYIDIZ I F，MELODIA T，CHOWDHURY K R.A survey on wireless multimedia sensor networks[J].Comput.Netw.，2007，51(4)：921-960.

[3] CHEN Y，LIN Y.Dir：diagonal-intersection-based routing protocol for vehicular adhoc networks[J].Telecommunication systems，2010，3(5)：1-18.

[4] CHENG P，LEE K，GERLA M.Geodtn+nav：geographic dtn routing with navigator prediction for urban vehicular environments[J].Mobile Networks and Applications，2010，15(1)：61-82.

[5] DJAHEL S，GHAMRI-DOUDANE Y.Arobust congestion control scheme for fast and reliable dissemination of safety messages in vanets[C].In Proceeding of the 2012 IEEE conference wireless communications and networking，2012：2264-2269.

[6] GHAFOOR K，BAKAR K.A novel delay and reliability aware inter vehicle routing protocol[J].Network Protocols and Algorithms，2014，2(2)：66-88.

[7] 范敏，謝思佳.基于空洞模型的地理位置路由改進(jìn)算法研究[J].傳感技術(shù)學(xué)報(bào)，2012，25(11)：1556-1561.

[8] LEE K，LEE U，GERLA M.To-go：topology-assist geoopportunistic routing in urban vehicular grids[C].In Proceedings of the 2009 IEEE international conference on wireless on-demand network systems and services，Snowbird，2013：11-18.

[9] YAN G，OLARIU S.A probabilistic analysis of link duration in vehicular ad hoc networks[J].IEEE Transactions on Intelligent Transportation Systems，2012，12(4)：1227-1236.

[10] Ghafoor K Z，Mohammed M A.Routing protocols in vehicular ad hoc networks: Survey and research challenges[J].Network Protocols and Algorithms，2013，5(4)：39-83.

[11] LOCHERT C，MAUVE M，HARTENSTEIN H.Geographic routing in city scenarios[J].Mobile Computing and Communications Review，2015，9(1)：69-72.

[12] NZOUONTA J，RAJGURE N.Vanet routing on city roads using real-time vehicular traffic information[J].IEEE Transactions on Vehicular Technology，2009，58(7)：3609-3626.

[13] 徐會(huì)彬.關(guān)于VANETs關(guān)鍵理論技術(shù)研究[D].博士學(xué)位論文，2014.

[14] SADIQ A，ABU BAKAR K.A fuzzy logic approach for reducing  andover latency in wireless networks[J].Network Protocols and  lgorithms，2011，2(4)：61-87.

[15] KAYHAN Z G，JAIME L，ALI S S.Improved geographical routing in vehicular Ad Hoc networks[J].Wireless Pers ommun，2015，80：785-804.