車載網絡中基于混合地理路由協議

黃智聰

摘 要： 車載網絡（VANETs）中的多跳轉發仍是一項挑戰工作。現存的路由協議以高數據包傳遞率或以低時延為目的。為此，提出基于發送和接收節點的混合地理路由協議（SRHGR）。SRHGR協議結合了基于發送節點和接收節點轉發節點的選擇特性，首先利用Beacon包建立一跳鄰居集，再通過距離建立候選轉發節點，然后利用節點距離因子和相對速度因子計算節點的權重，最后依據權重設置節點轉發消息的時延，進而選擇最優的轉發節點。仿真結果表明，提出的SRHGR協議既降低了傳輸時延，又提高了數據包傳遞率。

關鍵詞： 車載網絡； 地理路由； 發送節點；接收節點； 轉發節點； 傳遞率

中圖分類號： TN915.04?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2018）17?0145?04

Abstract： The multi?hop forwarding remains a challenging task in vehicle Ad Hoc networks （VANETs）. The available routing protocol either focus on the high packet transmission ratio or low latency. Therefore， a sender?receiver based hybrid geographic routing （SRHGR） protocol is proposed in this paper， in which the selection feature of sending node， receiving node and forwarding node is combined. The beacon packet is used in SRHGR protocol to construct one?hop neighbor set， and then the candidate forwarding node is established according to the node distance. The node distance factor and relative speed factor are adopted to calculate the weight of the node. The delay of node forwarding message is set according to its weight， so as to select the optimal forwarding node. The simulation results show that the proposed SRHGR protocol can reduce the transmission delay， and also improve the data packet transmission ratio.

Keywords： vehicle Ad Hoc network； geographic routing； sending node； receiving node； forwarding node； transmission rate

0 引 言

作為智能交通系統（Intelligent Transportation System，ITS）的最有前景技術，車載網絡（Vehicular Ad Hoc Networks，VANETs）[1]的相關研究受到廣泛關注。VANETs中網絡層的多跳協議增加了節點通信范圍，為車輛間的信息交互提供了平臺。然而，由于網絡拓撲的動態變化、無線鏈路的不穩定性，發現和維護穩定轉發路徑仍是一項挑戰工作[2?3]。

對于VANETs的多跳通信[4]，地理路由協議得到廣泛應用。地理路由協議無需維護全局網絡拓撲信息，降低了開銷。此外，全球定位系統GPS的日益普及也為地理路由協議的使用提供了平臺。目前，依據選擇下一跳策略的不同，地理路由協議可分為基于發送節點和基于接收節點兩類[5]。

在基于發送節點的地理路由協議中，源節點是從其一跳鄰居節點中選擇下一跳轉發節點。多數的選擇指標是依據常規狀態信息的交互，如周期的Beacon包。通常是利用無線媒介的單播傳輸（Unicast Transmission），將數據包傳輸至下一跳轉發節點。一般地，基于發送節點的地理路由協議具有低的時延，但是它通常遭受無線信道的高誤碼率，路由可靠性差。

基于接收節點協議也稱為機會路由協議，它通過廣播模式將數據包轉發至所有鄰居節點。一旦接收了數據包，節點就判斷自己是否可成為候選轉發節點。隨后，所有候選轉發節點就利用基于時延等待函數競爭轉發數據包。即在數據包被轉發前，節點引入時延。在等待時延過程中，一旦監聽到該數據包已被轉發，就取消等待，放棄對轉發數據包的競爭，并丟棄數據包。

基于接收節點協議利用所有鄰居節點競爭產生轉發節點，提高了路由可靠性。這類協議只要有一個節點能接收到該數據包，就能完成數據包的傳遞工作。因此，這類協議更適合高密度網絡。然而，由于基于接收節點協議在每一跳都引入了等待時延，增加了端到端傳輸時延。因此，此類協議的關鍵在于如何設置合適的時延函數，縮短總體的端到端傳輸時延。

本文提出發送和接收節點的混合地理路由協議（Sender?Receiver based Hybrid Geographic Routing，SRHGR）。該SRHGR協議既利用基于發送節點協議的低時延特性，又結合機會路由協議的可靠性。先利用節點位置信息產生候選轉發節點集，再利用節點位置、相對速度因子計算候選轉發節點集內所有節點權重，并依據權重排序，最后設置每個節點的轉發時延。仿真結果表明，提出的SRHGR協議提高了數據包傳遞率，并降低了端到端傳輸時延。

1 約束條件

本文提出的SRHGR協議基于以下約束條件：

1） 車輛通信范圍為[R]，下文車輛與節點概念相同；

2） 每個車輛備有GPS系統，能夠獲取自己的位置坐標以及道路地圖信息；

3） 車輛周期地廣播Beacon消息，其包含節點的位置和速度信息；

4） 歐氏距離（Euclidean distance）[D]。車輛[i]，[j]的位置分別為[xi，yi]，[xj，yj]。它們之間的歐氏距離為[Dij]：

2 SRHGR協議

提出的SRHGR協議結合基于發送節點選擇候選轉發節點策略和分散化協調策略。首先利用Beacon包的交互，建立一跳鄰居集[N]，再依據距離信息建立候選轉發集[ψ]。然后計算集[ψ]內節點的轉發權重[λ]，并依據權重[λ]對集[ψ]節點排序。最后引入基于時延轉發理念，計算集[ψ]內節點的時延。SRHGR協議框圖如圖1所示。

2.1 候選轉發集

首先，所有節點周期地廣播Beacon包，當節點收到來自其他鄰居節點的Beacon包，說明此節點在自己的一跳通信范圍內，據此，將此節點納入為自己一跳鄰居集[N]。

圖2描述了建立[N]的過程。節點[A，C，D，F]各自建立[N]集。如節點[B]的一跳鄰居集[NB=A，C，D，F]。由于節點[E]產生的Beacon包不能到達[B]，所以節點[B]的[N]集中并不包括節點[E]。同樣，節點[E]的[N]集中也不包含節點[B]。各個節點交互各自的[N]集，致使每個節點建立完備的[N]集。

如果集[ψi]內只有一個節點，即[ψi=1]時，就選用該節點作為轉發消息的節點；若[ψi>1]，說明有多個可選節點，因此，需要計算這些可選節點的權重，并據此設置轉發時延。

當然，肯定也會出現[ψi=0]的情況。若[ψi=0]，說明一跳鄰居集內沒有節點比自己離目的節點更近。在這種情況下，需利用其他的一跳鄰居節點[k∈Ni，k?ψi]采取攜帶存儲轉發策略。

2.2 權 重

節點權重反映鄰居節點轉發數據包是否合適。在SRHGR協議中，利用距離因子和相對速度因子估計節點權重。考慮距離因子的目的在于增加每跳距離，而相對速度因子是指當前節點和候選轉發節點間的相對速度。考慮相對速度因子是為了避免行駛速度過快，而不在當前節點的一跳通信范圍內。

2.3 基于權重的轉發時延

一旦成功接收了數據包，節點就參與競爭轉發。利用節點權重，設置不同的時延，進而實現分散化協調轉發。

首先，依據各節點的權重，對集[ψi]內節點進行從小到大排序。即權重越小，排序位置越靠前。權重[ω]最大的節點在集[ψi]內的位置[pc]就是第一個，即[pc=0]。具體而言，節點[j∈ψi]在集[ψi]內的排序位置為[pj]，則它所需要等待的時延[Tj]為：

式中[tf]為集[ψi]內兩個連續節點的等待時延差。該值應足夠大，進而使節點有足夠的信道接入時間，降低碰撞概率。然而，若[tf]過大，會增加時延。為此，引用機會路由方法。候選轉發節點一旦接收了數據包，就設置自己的等待時延，并等待。在等待的同時，監聽周圍節點是否已轉發了數據包，如果已有其他節點轉發數據包，則停止等待，放棄轉發數據包，否則，待時延結束后，立即轉發數據包。

從上述分析可知，式（7）所計算的等待時延只考慮集[ψi]節點。換而言之，若[ψi]內沒有節點（[ψi=0]），則沒有轉發節點。再或者集[ψi]內有節點，但它們并沒有收到數據包。考慮到這兩種情況，并提高傳輸數據包的可靠性，利用一跳鄰居集內的其他節點轉發數據包。

具體而言，對于在一跳鄰居集[Ni]內，而不在集[ψi]內的節點[k∈Ni，k?ψi]。它所需要等待的轉發時延為[Tk，CBF]：

2.4 數據包轉發流程

首先，節點周期地交互Beacon包。當節點需要轉發數據包（源節點[i]）時就先利用所收到的Beacon包建立一跳鄰居集[Ni]和轉發節點集[ψi]，然后再轉發數據包，并將轉發節點集[ψi]嵌入數據包的首部。源節點轉發的數據包格式如圖3所示。

一旦接收到數據包，節點就判斷自己是否在集[ψi]。若是，則查看自己在集[ψi]的位置，并依據式（7）設置等待時延。若不是，則依據式（8）設置轉發時延。各節點在等待自己的時延過程中，監聽其他鄰居節點是否已轉發數據包，若發現已有其他節點轉發數據包，則停止轉發，并丟棄數據包。否則，待等待時延完畢，就立即轉發數據包。整個數據包的轉發流程等待如圖4所示。

3 性能分析

3.1 仿真平臺

為了更好地評估SRHGR協議的性能，利用NS2.34建立仿真平臺。選擇4 km長單方向3車道的雙向高速公路作為仿真模型。車輛行駛速度范圍為80～130 km/h。車輛數為270。對于每個數據包，隨機選擇一對節點作為源節點和目的節點。具體的仿真參數如表1所示。

為了更好地分析SRHGR協議的性能，選擇典型的貪婪轉發路由（記為Greedy）和CBF進行同步仿真，并與SRHGR路由進行比較。

3.2 仿真結果

3.2.1 數據包接收率

數據包接收率隨節點數的變化曲線如圖5所示。從圖5可知，Greedy路由的數據包接收率最低，特別是在低密度區域，數據包接收率極低。例如，當節點數小于150時，數據包接收率低于0.5。原因在于：Greedy路由在選擇下一跳轉發節點時，只考慮了距離。而CBF路由的數據包接收率較高，高于Greedy路由。與Greedy和CBF相比，SRHGR路由的數據包接收率最高，遠高于Greedy路由，略高于CBF路由。原因在于：SRHGR路由從所有一跳鄰居節點中擇優選擇下一跳轉發節點，提高了數據包接收率。

3.2.2 端到端傳輸時延

端到端傳輸時延隨節點數的變化曲線如圖6所示。從圖6可知，SRHGR協議在節點數變化期間，具有低的端到端傳輸時延。而CBF的傳輸時延較高，這主要是因為CBF在每一跳選擇轉發節點，都引入了等待時延，最終增加了端到端傳輸時延。相比于CBF路由，Greedy路由的端到端傳輸時延較低。原因在于：Greedy路由總是選擇離目的節點最近的節點作為下一跳轉發節點，降低了傳輸跳數。

4 結 語

本文針對車聯網的數據包傳輸問題，提出基于發送和接收節點的混合地理路由SRHGR。SRHGR協議結合基于發送節點路由的低時延和接收節點的高可靠性。利用節點距離和相對速度估計每個候選轉發節點的權重，并據此設置轉發時延。仿真結果表明，提出的SRHGR協議有效地提高了數據包傳遞率，并降低了端到端傳輸時延。

參考文獻

[1] YASER P， NEDA N， KRISHNAN H. Stable and fair power control in vehicle safety networks [J]. IEEE trasactions on vehicular technology， 2016， 65（3）： 1662?1675.

[2] RAYNER P， SERGIO. Experimenting broadcast storm mitigation techniques in FANETs [C]// 2016 the 49th Hawaii International Conference on System Science. Koloa： IEEE Computer Society， 2016： 5868?5877.

[3] PRATAP K， ERIC H. BAHG： back?bone?assisted hop greedy routing for VANET′s city environments [J]. IEEE transactions on intelligent transportation systems， 2013， 14（1）： 199?213.

[4] LEE K C， LEE U， GERLA M. Survey of routing protocols in vehicular ad hoc networks [J]. Advances in vehicular Ad Hoc networks： developments and challenges， 2012（21）： 149?151.

[5] TOMATIS A， MENOUAR H， ROSCHER K. Forwarding in VANETs： Geonetworking [EB/OL]. [2015?01?23]. https：//link.springer.com/chapter/10.1007%2F978?3?319?15497?8_8.

[6] FUBLER H， WIDMER J， KASEMANN M. Contention?based forwarding for mobile Ad Hoc networks [J]. Ad Hoc networks， 2003， 1（4）： 351?369.

[7] HEISSENBUTTEL M， BRAUN T， HEISSENB M. BLR： beacon?less routing algorithm for mobile Ad Hoc networks [J]. Computer communications， 2004， 27（11）： 1076?1086.

[8] ROSCHER K， MAIERBACHER G. Reliable message forwar?ding in VANETs for delay?sensitive applications [C]// 2016 International Symposium on Wireless Communication Systems. Poznan： IEEE， 2016： 199?203.

[9] ZHAO Z L， ROSARIO D， BRAUN T， et al. Topology and link quality?aware geographical opportunistic routing in wireless Ad?Hoc networks [EB/OL]. [2014?05?26]. https：//www.researchgate.net/profile/Denis_Rosario/publication/256081798_Topology_and_Link_Quality?aware_Geographical_Opportunistic_Rou?ting_in_Wireless_Ad?hoc_Networks/links/00b7d5217c14b121? eb000000/Topology?and?Link?Quality?aware?Geographical?Opportunistic?Routing?in?Wireless?Ad?hoc?Networks.pdf.

[10] ARANITI G， CAMPOLO C， CONDOLUCI M， et al. LTE for vehicular networking： a survey [J]. IEEE communication magazine， 2013， 51（5）： 148?157.

[11] REHMAN O， MOHAMED O K， HADJ B. An adaptive relay nodes selection scheme for multi?hop broadcast in VANETs [J]. Computer communications， 2016， 87（6）： 76?90.