車載網(wǎng)絡(luò)中基于混合地理路由協(xié)議

黃智聰

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

關(guān)鍵詞： 車載網(wǎng)絡(luò)； 地理路由； 發(fā)送節(jié)點；接收節(jié)點； 轉(zhuǎn)發(fā)節(jié)點； 傳遞率

中圖分類號： 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 引 言

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

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

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

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

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

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

1 約束條件

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

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

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

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

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

2 SRHGR協(xié)議

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

2.1 候選轉(zhuǎn)發(fā)集

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

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

如果集[ψi]內(nèi)只有一個節(jié)點，即[ψi=1]時，就選用該節(jié)點作為轉(zhuǎn)發(fā)消息的節(jié)點；若[ψi>1]，說明有多個可選節(jié)點，因此，需要計算這些可選節(jié)點的權(quán)重，并據(jù)此設(shè)置轉(zhuǎn)發(fā)時延。

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

2.2 權(quán) 重

節(jié)點權(quán)重反映鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包是否合適。在SRHGR協(xié)議中，利用距離因子和相對速度因子估計節(jié)點權(quán)重?？紤]距離因子的目的在于增加每跳距離，而相對速度因子是指當前節(jié)點和候選轉(zhuǎn)發(fā)節(jié)點間的相對速度?？紤]相對速度因子是為了避免行駛速度過快，而不在當前節(jié)點的一跳通信范圍內(nèi)。

2.3 基于權(quán)重的轉(zhuǎn)發(fā)時延

一旦成功接收了數(shù)據(jù)包，節(jié)點就參與競爭轉(zhuǎn)發(fā)。利用節(jié)點權(quán)重，設(shè)置不同的時延，進而實現(xiàn)分散化協(xié)調(diào)轉(zhuǎn)發(fā)。

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

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

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

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

2.4 數(shù)據(jù)包轉(zhuǎn)發(fā)流程

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

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

3 性能分析

3.1 仿真平臺

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

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

3.2 仿真結(jié)果

3.2.1 數(shù)據(jù)包接收率

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

3.2.2 端到端傳輸時延

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

4 結(jié) 語

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

參考文獻

[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.