楊羽琦，章國安，吳敏

（南通大學電子信息學院，江蘇 南通 226019）

車載自組織網(wǎng)絡中基于十字路口的地理感知路由協(xié)議

楊羽琦，章國安，吳敏

（南通大學電子信息學院，江蘇 南通 226019）

為了解決城市道路多十字路口，對單個車輛節(jié)點運動感知不敏感所帶來的通信性能下降問題，提出一種車載自組織網(wǎng)絡中基于十字路口的地理感知路由（IGPR）協(xié)議，通過網(wǎng)絡網(wǎng)關選擇道路十字路口，形成骨干路由，在保證高連通概率的同時滿足時延和誤比特率要求。在雙向道路模型的基礎上分析獲得平均時延和平均跳數(shù)的數(shù)學計算式。仿真結果表明，IGPR協(xié)議與FRGR協(xié)議、VRR協(xié)議相比，傳輸時延小，跳數(shù)少，通信性能好。關鍵詞：車載自組織網(wǎng)絡；路由協(xié)議；平均時延；平均跳數(shù)

[3]提出一種保證高連通性的基于車輛密度的可變傳輸范圍路由 （variable transmission range routing protocol based on vehicle density，VRR），但由于城市環(huán)境多十字路口且車道方向變化頻繁，該協(xié)議在城市環(huán)境下表現(xiàn)不佳。為了解決城市環(huán)境下這些限制，本文提出了基于十字路口的地理感知路由 （intersection-based geographical perception routing，IGPR）協(xié)議，該協(xié)議通過在十字路口之間傳輸數(shù)據(jù)分組，降低路徑對單個節(jié)點運動靈敏度感知。十字路口的選擇基于最大化路徑連通概率即保證路由的穩(wěn)定性。

2 基于十字路口的地理感知路由

2.1 路段模型

本文所用的路段模型是城市環(huán)境下包括十字路口的雙向車道模型。本文假設車輛從全球定位系統(tǒng)（GPS）接收器[4]或其他感知位置服務獲得地理位置。車輛還可以使用車載的導航系統(tǒng)獲得區(qū)域數(shù)字地圖，以確定其相鄰道路十字路口的位置。

街道地圖被抽象成一個圖G(V，E)[5]。其中V表示有向圖頂點的集合，E表示邊的集合。對于任意兩個十字路口A和B，當有路段連通A和B時車輛可在該路段行駛。圖1為十字路口道路模型，其中有6個十字路口，3條主路段，每條路段的路況隨機分布。

圖1 十字路口道路模型

2.2 模型分析

如第2.1節(jié)所述，道路模型為G(V，E)，道路交叉口v∈V和路段e∈E相互連通。本文考慮一個雙向道路場景，任意兩個十字路口之間的直線車道上車輛運動方向相反。為了方便研究，現(xiàn)將長度為L的路段按照傳輸半徑R分成若干路段，即雙車道路段根據(jù)節(jié)點傳輸范圍劃分成間隙，如圖2所示。

圖2 雙車道路段

本地網(wǎng)關有本地網(wǎng)絡拓撲的最新信息，可以更新道路圖G的估計統(tǒng)計數(shù)據(jù)。路徑y(tǒng)由許多十字路口{v1,v2,…, vm}組成，這些十字路口由一系列路段{e1,e2,…,en}連通，其中，n=m-1。

2.2.1 連通概率pc

為了增加連通概率，可以利用城市環(huán)境雙向車道優(yōu)勢。這種情況下，假設車道1路段j上兩個連續(xù)的車輛Ni和Ni+1之間距離X＞R，表示該段是不連通的，Ni需向Ni+1發(fā)送數(shù)據(jù)分組，如果此時車道2上有車輛Ni,i+1在Ni的傳輸范圍內向相反方向運動，則可通過車道2上的車輛Ni,i+1將Ni連通到Ni+1。這意味著車道2上以Ni為中心的2R范圍內至少存在一個車輛節(jié)點，如圖3所示。

k1和k2分別表示車道1和車道2上間隔為R的長度內車輛數(shù)的隨機變量（如圖2所示）。假設車輛在兩個車道均勻分布，γ1和 γ2分別表示車道1和車道 2車輛節(jié)點的空間密度，長為R的區(qū)域中車輛數(shù)服從泊松分布：

圖3 雙車道車輛通信

車道1上Ni與Ni+1間出現(xiàn)通信斷路時，車道2上該路段2R范圍內至少能夠找到一個車輛節(jié)點，就可以解決車道1上該段的斷路，設k表示車道2上2R范圍內車輛數(shù)的隨機變量，則k是服從以下概率質量函數(shù)的泊松分布：

PnK表示該路段不連通的概率：

需要注意的是，車道1斷開的連通可能多于1個。設Q表示車道1上斷開的連通的個數(shù)的隨機變量，如果所有Q都是可以解決的，則路段j將被視為連通的。pc|Q是假設有Q個斷開連通的條件連通概率。pc|Q可以寫成：

其中，N表示車道1路段j車輛節(jié)點的數(shù)目，為獲得路段j連通概率，還需要知道Q的概率密度函數(shù)。如果兩個連續(xù)的車輛之間的距離大于R，連通就會斷開。設Pb是連通斷開的概率，由于任意兩個連續(xù)的車輛之間的距離為指數(shù)分布，因此：

一共有N-1條鏈路：

因此，路段j的總的連通概率為：

圖4顯示了長為5 000 m的雙車道上，不同的節(jié)點密度情況下，傳輸半徑與連通概率的關系曲線。當節(jié)點密度不變時，傳輸半徑越大，連通概率也越大。當傳輸半徑一定時，節(jié)點密度越大，連通概率越大。即接近連通概率1，節(jié)點密度低所需要的傳輸半徑大，節(jié)點密度高所需要的傳輸半徑小。

圖4 傳輸半徑與連通概率的關系曲線

2.2.2 誤比特率

路徑質量的另一種度量方式是誤比特率。由于無線通信信道衰落和噪聲的存在，兩個連續(xù)節(jié)點之間信息傳輸可能會發(fā)生錯誤，Pe表示傳輸信息發(fā)生的錯誤率。假設一個自由空間傳播路徑損失模型。每個鏈路上連續(xù)兩個節(jié)點之間的誤比特率為[6]：

其中，α1是一個常數(shù)，Pt為發(fā)射功率，Ptherm=α2Rb是熱噪聲功率，α2是常數(shù)，Rb是傳輸數(shù)據(jù)速率，2σf2是瑞利密度函數(shù)描述的信號包絡的均方值[7]。X是連續(xù)兩個車輛節(jié)點之間距離，當該距離大于傳輸范圍R時通信中斷，其概率密度函數(shù)（PDF）如下：

因此，連續(xù)兩個車輛之間的一個鏈路預期誤比特率可以計算為：

路段j的誤比特率Pej為：

圖5顯示了長為5 000 m的雙車道上，不同的節(jié)點密度情況下，傳輸半徑與誤比特率的關系曲線。當節(jié)點密度不變時，傳輸半徑越大，誤比特率也越大。當傳輸半徑一定時，節(jié)點密度越大，誤比特率越大。這是因為傳輸半徑越大，信道衰落和噪聲就越多，而節(jié)點密度越大，節(jié)點之間的干擾也越多，導致誤比特率增加。

圖5 傳輸半徑與誤比特率關系曲線

值得注意的是，不能毫無限制地增大傳輸范圍?？紤]圖4和圖5，可以看到，節(jié)點密度一定時，增加傳輸范圍可以提高連通率。但另一方面，隨著傳輸范圍的增加誤比特率也會增加。因此，應選擇合適的傳輸半徑來權衡連通概率和誤比特率。例如，當密度為0．004 veh/m時，600 m的傳輸范圍可以使連通概率接近1，如果此時再增加傳輸范圍，誤比特率也會增加。綜合判斷圖4和圖5中point1，當節(jié)點密度為0．004 veh/m時，最佳半徑大約為600 m。

3 基于十字路口的地理感知路由協(xié)議

3.1 IGPR路由協(xié)議

在IGPR協(xié)議中，源節(jié)點需知道將數(shù)據(jù)分組轉發(fā)到目的節(jié)點的路徑，這個信息是由網(wǎng)關提供的。此時網(wǎng)關充當位置服務器，具有本地網(wǎng)絡拓撲的一個實時視圖，其負責保存附近所有車輛的當前位置信息。這個過程可以通過基于區(qū)域位置服務管理協(xié)議 （regional location service management protocol，RLSMP）[4]完成。具體來說，每個車輛往前移動距離當前位置一個傳輸范圍時報告其位置信息給網(wǎng)關。此信息包含節(jié)點號、傳輸半徑R、節(jié)點的坐標位置X和Y、最后更新的時間、節(jié)點運動速度和方向。根據(jù)這些位置信息，網(wǎng)關在源節(jié)點和目的節(jié)點之間構建一條路由。不過，因為這些路由包括中間節(jié)點，由于中間節(jié)點的移動性，這些路由是不穩(wěn)定的。為了增加其穩(wěn)定性，IGPR建立了包含中間節(jié)點和道路十字路口的骨干路由。如圖1所示，源節(jié)點SN到目的節(jié)點DN的3個可行骨干路由：A-B-D-F、A-C-D-F和A-C-E-F。只有當網(wǎng)絡中節(jié)點密度顯著變化時，才需要重新計算骨干路由和傳輸半徑。

基于構建的骨干路由，網(wǎng)關將選擇有足夠車流量保證網(wǎng)絡連通性最佳的路段。選定路由將被發(fā)送到源節(jié)點并將存儲在數(shù)據(jù)分組報頭，以允許中間節(jié)點在十字路口之間轉發(fā)數(shù)據(jù)分組。轉發(fā)過程可以描述如下：當數(shù)據(jù)分組沿車道正常轉發(fā)時，它基于地理轉發(fā)算法選擇下一跳即下一個轉發(fā)節(jié)點選擇最接近于當前路段十字路口的節(jié)點。當數(shù)據(jù)分組已接近當前路段十字路口時，它會選擇最接近下一個十字路口的節(jié)點?！跋聜€十字路口”信息存儲在節(jié)點接收到的數(shù)據(jù)分組報頭中。

該協(xié)議的優(yōu)點是網(wǎng)關選擇最連通的骨干路由，因此，找到一個朝“下一個路口”的中間節(jié)點概率很高。IGPR協(xié)議流程如圖6所示。

3.2 IGPR時延性分析

骨干路由端至端時延D定義為從源節(jié)點發(fā)出去的數(shù)據(jù)分組到達目的節(jié)點所需的時間。從源節(jié)點到目的節(jié)點的路徑y(tǒng)包括道路的總路段n和各路段j所有的估計時延Dj，那么D可以表示為：

其中，時延Dj取決于路段j上移動節(jié)點數(shù)N和路段j相鄰節(jié)點Ni和Ni+1間數(shù)據(jù)分組傳輸所需要的時間。移動節(jié)點Ni和Ni+1間數(shù)據(jù)分組傳輸所需要的時間取決于Ni轉發(fā)分組的策略。如果Ni使用逐跳貪婪轉發(fā)，時延為處理和發(fā)送該數(shù)據(jù)分組所需時間，表示為tp，如果Ni采用的是攜帶與轉發(fā)策略，Ni攜帶數(shù)據(jù)分組轉發(fā)速度與 Ni的移動速度Si相同，該時延取決于Si和Ni到下一跳Ni+1之間的距離。為了估計時延D，考慮以下兩種情況。定義α=(L/R)。

情況1：如果路段長度L小于或等于傳輸范圍R，即α≤1。該段的數(shù)據(jù)分組轉發(fā)策略為逐跳轉發(fā)，時延為tp。為了方便處理，設tp是一個常數(shù)。因為無線干擾多發(fā)生在不同的信道，因此數(shù)據(jù)傳輸之間的干擾在該模型下可忽略，這種假設在許多文獻中都有使用[8，9]。注意，該分析模型應確保用不同信道，就可以反映VANET真實行為。

情況2：如果段長度L大于傳輸范圍R，即α＞1。設k12表示兩個車道間隔R內車輛的數(shù)目。同樣的，k12遵循以下概率密度函數(shù)的泊松分布：

計算該道路段時延，考慮節(jié)點轉發(fā)數(shù)據(jù)的策略。如果數(shù)據(jù)分組一跳一跳轉發(fā)，該鏈路上的時延就為第一種情況下的tp。如果數(shù)據(jù)分組是由車輛節(jié)點攜帶并轉發(fā)，路段上沒有任何轉發(fā)數(shù)據(jù)分組的車輛節(jié)點的概率用β表示。β估計為：

圖6 IGPR協(xié)議流程

其中，平均時延可以使用在路段j的節(jié)點的平均速度計算。路段j的平均時延為：

其中，S是路段j上節(jié)點的平均速度，N是路段上節(jié)點的數(shù)目：

3.3 IGPR跳數(shù)分析

對于骨干路由y，數(shù)據(jù)分組在路段j傳輸所需要的跳數(shù)由路段長度L和節(jié)點在該路段的傳輸半徑R決定。如果L＜R，即α≤1時，該路段數(shù)據(jù)分組的傳輸只需要單跳。如果L＞R，即α＞1時，數(shù)據(jù)分組可以多跳傳輸，也可以攜帶轉發(fā)。因此，路段j上平均跳數(shù)可表示為：

因此，由n個路段所形成的骨干路由y總跳數(shù)為：

4 性能仿真

本文用MATLAB仿真軟件對IGPR的性能指標進行仿真，并與基于十字路口的固定傳輸范圍地理感知路由（FRGR）[10]協(xié)議和基于車輛密度的可變傳輸范圍路由（VRR）[3]協(xié)議進行比較。仿真參數(shù)見表1。

表1 仿真參數(shù)設置

圖7顯示了IGPR協(xié)議、VRR協(xié)議和FRGR協(xié)議的節(jié)點密度與連通概率的關系曲線。3種協(xié)議的連通概率都隨著節(jié)點密度的增加而增加。當節(jié)點密度一定時，IGPR協(xié)議的連通概率最大，VRR協(xié)議連通概率最小。這是因為IGPR協(xié)議和FRGR協(xié)議考慮的是雙車道場景，車道2上節(jié)點可以幫助解決車道1上連接斷開的情況。而IGPR協(xié)議除了雙車道的優(yōu)勢，還可以通過改變傳輸范圍獲得更高連通率，可見IGPR協(xié)議的連通性能比其他兩個協(xié)議好。

圖7 節(jié)點密度與連通概率的關系曲線

圖8顯示了3種協(xié)議的車輛數(shù)與平均時延的關系曲線。IGPR和FRGR協(xié)議平均時延隨著車輛數(shù)的降低而增加，VRR協(xié)議平均時延基本保持不變，3種協(xié)議的時延受車輛數(shù)影響都較小。當車輛數(shù)一定時，IGPR協(xié)議的平均時延最小。這是因為IGPR協(xié)議和FRGR協(xié)議可以通過雙車道優(yōu)勢來降低數(shù)據(jù)分組攜帶轉發(fā)的次數(shù)，但FRGR協(xié)議因為傳輸范圍固定，有時候會出現(xiàn)找不到下一跳節(jié)點的情況，此時采用車輛攜帶轉發(fā)的方式轉發(fā)數(shù)據(jù)分組，最終導致時延比IGPR協(xié)議大，但是時延還是比單車道情況下的VRR協(xié)議小。

圖9顯示了3種協(xié)議的車輛速度與平均時延的關系曲線。IGPR和FRGR協(xié)議平均時延都隨著車輛速度的增加而降低，VRR協(xié)議平均時延基本保持不變。相同速度下，IGPR協(xié)議的平均時延最小，VRR協(xié)議平均時延最大。

圖8 車輛數(shù)與平均時延的關系曲線

圖9 車輛平均速度與平均時延的關系曲線

圖10顯示了3種協(xié)議的車輛數(shù)與平均跳數(shù)的關系曲線，平均跳數(shù)都隨著車輛數(shù)目的增加而增加。車輛數(shù)目相同時，VRR協(xié)議所需要的跳數(shù)最多，IGPR所需要的跳數(shù)最少。因為在車輛數(shù)一定時，IGPR協(xié)議自適應傳輸范圍，F(xiàn)RGR協(xié)議可以通過雙車道優(yōu)勢增加連通，即數(shù)據(jù)分組在兩個連續(xù)車輛間轉發(fā)多為1跳完成，而VRR還可能需要攜帶轉發(fā)。

5 結束語

本文提出了一種基于十字路口的地理感知路由協(xié)議，該協(xié)議通過網(wǎng)關對網(wǎng)絡中車輛節(jié)點的地理感知，選擇高連通率的骨干路由，并利用十字路口傳輸數(shù)據(jù)分組以降低路徑對單個節(jié)點運動靈敏度感知。通過理論分析獲得平均時延和平均跳數(shù)的數(shù)學計算式。仿真結果表明所提出來的IGPR協(xié)議與VRR協(xié)議、FRGR協(xié)議相比，降低了傳輸數(shù)據(jù)分組平均時延和平均跳數(shù)。

圖10 車輛數(shù)與平均跳數(shù)的關系曲線

參考文獻：

[1]SPAHO E,BAROLLI L,MINO G,et al.Performance evaluation of AODV,OLSR and DYMO protocols for vehicular networks using CAVENETV,DSDV and OLSR [C]//2010 IEEE International Conference on Network-Based Information Systems, Sept 14-16,2010,Gifu,Japan.New Jersey:IEEE Press,2010: 527-534.

[2]WANG M,ZHANG Y,LI C,etal.A survey on intersection-based routing protocols in city scenario of VANE[C]// 2014 IEEE International Conference on Connected Vehicles and Expo,Nov 3-7,2014,Vienna,Austria.New Jersey:IEEE Press,2014:821-826.

[3]蔡蓉,章國安,吳月波.車載網(wǎng)中基于車輛密度的可變傳輸范圍路由協(xié)議[J].電信科學,2015,31(3):1-7. CAI R,ZHANG G A,WU Y B.Variable transmission range routing protocol based on vehicledensity in VANET [J]. Telecommunications Science,2015,31(3):1-7.

[4]SALEET H,BASIR O,LANGAR R,etal.Region-based location service-management protocol for VANET [J].IEEE Transactions on Vehicular Technology,2010,59(2):917-931.

[5]LI G,BOUKHATEM L.An intersection-based delay sensitive routing for VANET using ACO algorithm[C]//IEEE International Conference on Computer Communication and Networks,Aug 4-7, Shanghai,China.New Jersey:IEEE Press,2014:1-8.

[6]CHENG H,YAO Y.Power adaptation for multihop networks with end-to-end BER requirements[J].IEEE Transactions on Vehicular Technology,2010,59(7):3445-3454.

[7]PANICHPAPIBOON S,PATTARA W.Connectivity requirements for self-organizing traffic information systems [J]. IEEE Transactions on Vehicular Technology,2008,57(6):3333-3340.

[8]MAK T K,LABERTEAUX K P.Multichannel medium access control for dedicated short-range communications[J].IEEE Transactions on Vehicular Technology,2009,58(1):349-366.

[9]SU H,ZHANG X.Clustering-based multichannel MAC protocols for QoS provisioning over vehicular Ad Hoc networks[J].IEEE Transactions on Vehicular Technology, 2007, 56 (6): 3309-3323.

[10]SALEET H,LANGAR R.Intersection-based geographical routing protocol for VANET:a proposal and analysis[J].IEEE Transactions on Vehicular Technology,2011,60(9):4560-4574.

Intersection-based geographical perception routing protocol in VANET

YANG Yuqi,ZHANG Guoan,WU Min
School of Electronics and Information,Nantong University,Nantong 226019,China

In order to solve the problem of the communication performance of degradation,which caused by multi-intersections in city environment and no sensitivity to individual node movements,an intersection-based geographical perception routing protocol in vehicular Ad Hoc network was proposed.The network gateways select road intersections to form the backbone of the route,ensuring a high probability of communication and meeting delay and bit error rate requirements.Mathematical formula of the average delay and the average number of hops were obtained on the basis of a two-way road model.Simulation results show that the transmission delay of IGPR is smaller,the number of hops of IGPR is less,and the communication performance of IGPR is better compared with the FRGR protocols and VRR protocols.

vehicular Ad Hoc network,routing protocol,average delay,average number of hops

TP393

A

10.11959/j.issn.1000-0801.2017014

1 引言

楊羽琦（1993-），女，南通大學電子信息學院碩士生，主要研究方向為車輛自組織網(wǎng)絡。

章國安（1965-），男，博士，南通大學電子信息學院教授、博士生導師，主要研究方向為無線通信網(wǎng)絡理論與技術。

吳敏（1992-），女，南通大學電子信息學院碩士生，主要研究方向為車輛自組織網(wǎng)絡。

2016-10-25；

2017-01-04

國家自然科學基金資助項目(No.61371113,No.61401241)

Foundation Items：The National Natural Science Foundation of China(No.61371113,No.61401241)

車載自組織網(wǎng)絡（vehicle Ad Hoc network，VANET）是一種無約束、自組織的特殊移動自組織網(wǎng)絡 （mobile Ad Hoc network，MANET），整個網(wǎng)絡以車輛為通信節(jié)點而不依賴于昂貴的網(wǎng)絡基礎設施，其與MANET不同點在于網(wǎng)絡規(guī)模大、節(jié)點分布不均勻、節(jié)點運動速度快等。VANET通信主要包括車輛與車輛之間的通信（vehicle-to-vehicle，V2V），車輛與基礎設施之間的通信（vehicle-to-infrastructure，V2I）和車輛與行人間的通信（vehicle-to-pedestrian，V2P）。隨著VANET的發(fā)展，近幾年其應用更加廣泛，如道路安全應用、查詢信息服務、集中控制交通信息系統(tǒng)服務、網(wǎng)絡娛樂服務、車內辦公服務等。

路由協(xié)議的研究在VANET中占重要位置，路由協(xié)議的分類根據(jù)不同的標準劃分也有不同。根據(jù)路由度量的不同，分為基于拓撲結構路由和基于地理位置信息路由；根據(jù)路由發(fā)現(xiàn)策略的不同，可分為主動路由和被動路由；根據(jù)路由協(xié)議工作原理不同，分為確定式路由和無狀態(tài)路由。基于拓撲的路由協(xié)議，如鏈路狀態(tài)路由（optimized link state routing，OLSR）[1]主要問題是路由不穩(wěn)定。事實上，傳統(tǒng)的以節(jié)點為中心的路由因VANET節(jié)點的高移動性，路由頻繁斷裂，路由修復開銷顯著增加，導致高傳輸時延。另一種方法是通過地理信息提供路由，使用目的節(jié)點和相鄰節(jié)點的位置信息轉發(fā)數(shù)據(jù)，盡管路徑更加穩(wěn)定，但由于城市環(huán)境比較復雜，地理轉發(fā)很多時候不能找到比當前節(jié)點更靠近目的節(jié)點的下一跳，在城市環(huán)境下表現(xiàn)不是很好[2]。