黃智聰

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

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

中圖分類號(hào)： TN915.04?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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é)點(diǎn)通信范圍，為車輛間的信息交互提供了平臺(tái)。然而，由于網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化、無(wú)線鏈路的不穩(wěn)定性，發(fā)現(xiàn)和維護(hù)穩(wěn)定轉(zhuǎn)發(fā)路徑仍是一項(xiàng)挑戰(zhàn)工作[2?3]。

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

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

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

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

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

1 約束條件

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

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

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

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

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

2 SRHGR協(xié)議

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

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

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

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

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

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

2.2 權(quán) 重

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

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

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

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

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

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

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

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

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

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

3 性能分析

3.1 仿真平臺(tái)

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

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

3.2 仿真結(jié)果

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

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

3.2.2 端到端傳輸時(shí)延

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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