車載自組織網絡中基于十字路口的地理感知路由協議

楊羽琦，章國安，吳敏

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

車載自組織網絡中基于十字路口的地理感知路由協議

楊羽琦，章國安，吳敏

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

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

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

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

2.1 路段模型

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

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

圖1 十字路口道路模型

2.2 模型分析

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

圖2 雙車道路段

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

2.2.1 連通概率pc

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

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

圖3 雙車道車輛通信

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

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

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

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

一共有N-1條鏈路：

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

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

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

2.2.2 誤比特率

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

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

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

路段j的誤比特率Pej為：

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

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

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

3 基于十字路口的地理感知路由協議

3.1 IGPR路由協議

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

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

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

3.2 IGPR時延性分析

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

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

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

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

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

圖6 IGPR協議流程

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

其中，S是路段j上節點的平均速度，N是路段上節點的數目：

3.3 IGPR跳數分析

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

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

4 性能仿真

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

表1 仿真參數設置

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

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

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

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

圖8 車輛數與平均時延的關系曲線

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

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

5 結束語

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

圖10 車輛數與平均跳數的關系曲線

參考文獻：

[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]蔡蓉,章國安,吳月波.車載網中基于車輛密度的可變傳輸范圍路由協議[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-），女，南通大學電子信息學院碩士生，主要研究方向為車輛自組織網絡。

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

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

2016-10-25；

2017-01-04

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

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

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

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