VANETs城市場景下基于自適應時延的Geocast路由協議

李 明，曹建國

(1.長江重慶航道局，重慶 401147；2.華中科技大學 計算機科學與技術學院，湖北 武漢 430074)

VANETs城市場景下基于自適應時延的Geocast路由協議

李 明1，曹建國2

(1.長江重慶航道局，重慶 401147；2.華中科技大學 計算機科學與技術學院，湖北 武漢 430074)

基于廣播式的Geocast路由協議能夠在特定的地理區域內高效地發布數據。然而，廣播模式引起冗余重播，易導致廣播風暴問題。另外，由于城市場景下建筑物的影響，現有的多數廣播抑制方案難以應用于城市環境。為此，提出面向城市的基于自適應時延的Geocast路由協議UGAD。UGAD采用了基于自適應時延的廣播抑制方案，降低發生廣播風暴的概率。同時，考慮到交叉路口的地理優勢，給位于交叉路口的車輛“優惠”時延，使其具有優先轉發數據包權力，從而提高數據包到達率。此外，考慮到城市道路的復雜性，UAGD采用基于交叉路口轉發IF和貪婪轉發GF兩個模式，依據不同的道路情況選擇不同的轉發模式，從而降低冗余重播，并保持高的數據包到達率。最后，針對城市場景進行仿真，結果表明提出的UGAD具有高的數據包到達率，低的數據包重播率。

車載網；Geocast；廣播風暴；貪婪轉發；基于交叉路口轉發；時延

1 Geocast路由協議與DDT策略

車載網VANETs(Vehicular Ad Hoc Network)中，常需要向某個區域內的所有車輛發布數據[1]。因此，基于廣播的數據發布算法廣泛應用于VANETs。例如，地域性多播Geocast[2-4]協議。Geocast是一種基于地域位置的，向指定的目的區域內所有節點發布數據包的多播路由協議[5]。為此，Geocast路由協議被廣泛應用于車輛間交通信息、緊急事件以及商業廣播發布。如圖1所示，發生交通事故，第一個發現此事故的車輛(源節點)需要將此消息發布后續車輛，即后續車輛是消息的目的區域。

圖1 Geocast路由協議示意圖

在Geocast路由協議中，目的區域ZOR(Zone of Relevance)中所有節點是數據包的目的節點。依據數據包傳遞到ZOR方式的不同，Geocast路由協議可分為基于傳統泛洪的Geocast、定向泛洪的Geocast和非泛洪的Geocast[6]。

在基于傳統泛洪的Geocast路由協議中，接收到數據包后，節點先判斷是否位于目的區域ZOR中，若是則將數據包傳遞給上層應用，并同時繼續廣播該數據包，若不是則僅廣播該數據包。定向泛洪的Geocast路由協議[7]，是通過特定的轉發區域ZOF(Zone of Forwarding)轉發數據包，而不是像傳統泛洪那樣向四周廣播數據包。在非泛洪的Geocast路由協議中，源節點利用單播路由機制將數據包傳遞到ZOF中的某一個節點。該節點接收數據包之后，就在目的區域ZOR進行泛洪，致使ZOF中所有節點均收到該數據包。

在Geocast路由協議中，存在兩個區域內數據包傳遞問題：一是如何將數據包從轉發區域ZOF傳遞給目的區域ZOR；二是如何在目的區域ZOR節點將數據包發布給ZOR內所有節點。在第二區域(ZOR)內，主要采用泛洪機制發布數據包，以提高數據包到達率。針對第一區域(ZOF)，若采用泛洪機制將數據包傳遞至目標區域，可提高數據包到達率PRR(Packet Reachability Ratio)。PRR越高，表明數據包高效地傳遞了多個節點，但是，泛洪機制存在數據包冗余重播，易引起廣播風暴問題；若采用單播機制，盡管抑制了數據包冗余重播，但是降低了數據包傳遞到目的區域的效率，特別是在城市場景下，車輛間的通信受到高樓等建筑物的阻擋，僅采用單播機制難以保證高的數據包傳遞率。

為此，在Geocast路由協議中，一方面要抑制廣播風暴，另一方面要提高數據包到達率。抑制廣播風暴的目的在于避免網絡堵塞以及數據包碰撞。在移動自組織網絡MANET(Mobile Ad Hoc Network)，可將廣播算法分為4類[8]：泛洪式廣播、基于概率式廣播、區域廣播以及基于鄰居信息廣播。泛洪式廣播就是所有節點均轉播消息，這將引用過多的冗余(Redundancy)；基于概率式廣播是指消息的接收者依據概率參數決定是否轉播消息，但是這種方式依賴隨機參數，仍會引用冗余重播。區域廣播是指向某特定的范圍內轉播消息，如基于延時方案的區域廣播，其利用距離作為參數，并轉換成延時參量。離發送者越遠，具有越高的轉播優先權。基于鄰居信息廣播是指消息的接收者利用一跳或二跳鄰居節點信息去獲取網絡拓撲，并選擇下一跳的轉發節點。比如，在VANETs中，每個車輛周期地發送beacon包，其包含節點ID、位置、速度等信息。消息的接收者接收來自鄰居的beacon包，依據所有的beacon包的信息，選擇下一跳節點重播消息，而不是采取分布式重播決定。然而，由于車輛高速移動，周期地從beacon包獲取的鄰居節點信息與實時的鄰居信息總是存在差距，從beacon包獲取的信息總是滯后的。

文獻[9]提出了采用距離-推遲-時間算法DDT(Distance Defer Time)實現抑制廣播風暴。在DDT方案中，收到數據包的每個車輛依據離發送者的距離設置等待轉發該消息的時延。離發送者越遠，時延越短。若在等待轉發期間，收到數據包的復本(Duplicated packets)，車輛就取消息等待，也不轉發此消息。因為收到數據包的復本，就意味著已有車輛轉播了此消息。通過DDT抑制廣播風暴，緩解數據包冗余重播，如圖2所示。

圖2 DDT中數據包轉發過程

如圖2所示，車輛A、B、C收到來自S的數據包，它們依據在數據包傳播方向上距離S的長度設置等待轉發時間。由于車輛A在數據包傳播方向上離S最遠，因此A具有最短的等待時延，依次是B、C。圖中的1、2、3表示車輛A、B、C轉發的優先級。一旦A轉發了數據包，并且B、C收到來自A的數據包的復本，B、C就不再等待，也不再轉發該數據包。

DDT策略適用于直路模型(高速公路場景)。然而，在城市場景下，其性能急劇下降，這主要因為城市環境的建筑物阻礙了車輛間的通信，阻礙了車輛間的直接通信，這直接降低了車輛間信息交互的效率[10]，如圖3所示。

圖3 城市環境中障礙物的影響

如圖3所示，盡管A、C在車輛S的通信范圍，但是由于建筑物存在，使得S無法向A、C直接傳遞數據包。城市環境中的障礙物阻礙了一跳通信，使得DDT方案無法直接應用于城市環境。

為此，考慮城市場景的特點，提出面向城市場景的基于自適應時延的Geocast路由協議UGAD(Urban Geocast based on Adaptive Delay)。UGAD采用基于交叉路口、貪婪兩種轉發模式。在基于交叉路口轉發IF(Intersection based forwarding )模式中， 位于交叉路口的節點具有優先轉發數據包權，即短的等待轉發數據時間。IF模式利用交叉路口的地理優勢(不失一般性，交叉路口車輛多，轉發數據包容易)，提高數據包到達率。使用貪婪轉發GF (Greedy Forwarding) 模式，目的是降低冗余重播。UGAD利用發送節點與接收者、目標區域ZOR位置，計算角度，通過這個角度值對兩種模型進行切換。

2 UGAD方案

UGAD采用自適應時延機制，從而提高數據包到達率?？紤]到城市環境的特點，給位于交叉路口的車輛分配優先轉發權，提高了交叉路口廣播的機會。同時，UGAD使用兩個不同的轉發模式，依據不同的環境，選用不同的轉發模式，從而降低數據包冗余重播，同時保證數據包到達率。

2.1 基于交叉路口的機制

考慮到交叉路口特殊區域位置，不失一般性，交叉路口區域車輛較多，并且無障礙物，車輛間能夠直接通信，如圖4所示。處于交叉路口的車輛S，能夠向周圍車輛A、B、C直接發布數據包，不會出現圖3情況。為此，應充分利用交叉路口的地理優勢，使得位于交叉路口的車輛具有數據包優先轉發權。

圖4 交叉路口的轉發

此外，由于交叉路口車輛較多，為了提高數據包到達率，使位于交叉路口的車輛具有優先轉發權。

2.2 假設條件

UGAD假定每個車輛通過GPS系統知道交叉路口的位置以及自己的坐標位置。Geocast 的目的區域ZOR表示以p(x,y)為中心，r為半徑的圓。源節點發送數據包，其包含ZOR的信息，發送節點的位置信息。

此外，在UGAD內，定義轉發區域ZOF：比源節點S發離目的區域ZOR更近的區域。

在城市環境中，依據路邊建筑物的陰影衰弱可將道路拓撲分割為直線道路和交叉路口。具體而言，兩個交叉路口之間的直線道路區域為一個路段，如交叉路口Ii和Ij之間的直線道路區域rij。

2.3 數據包的處理過程

假定源節點S發送數據包M，節點i收到數據包M，并決定是否轉發數據包M。為此，首先節點i確認自己是否位于轉發區域ZOF內，如果在，節點i就有機會轉發數據包M，進而設置時延。如果不在，節點i就丟去數據包M，因為位于轉發區域ZOF外的節點不需要轉發數據包M。另外，節點i通過GPS確認自己的位置，同時從數據包M提取源節點S、目的區域ZOR的位置，從而保證節點i知道是否位于轉發區域ZOF內，具體過程如圖5所示。轉發區域ZOF的車輛，自行計算時延，一旦時延結束，就轉發數據包。若在等待期間，收到數據包的復本，車輛將中斷等待，并取消轉發數據包的安排。通過這種模式，抑制數據包冗余重播。

圖5 處理數據包的流程圖

2.4 時延的計算

為了滿足Geocast的性能要求，UGAD采用兩個不同的轉發模式，即貪婪轉發和基于交叉路口轉發。車輛依據不同的模式，計算時延。

1) 貪婪轉發GF模式

GF模式的目的在于最大化每一跳傳播增益，同時最小化冗余數據包問題。在GF模式中，節點i接收來自源節點j的數據包M，節點i依據式(1)計算時延。

(1)

2) 交叉路口轉發IF模式

IF模式的目的在于提高交叉路口數據包轉發的機會，從而增加數據到達率。在這種模式下，位于交叉路口的車輛具有“優惠”的時延，使得位于交叉路口的車輛比其他車輛具有優先轉發數據包的權力。在IF模式中，節點i接收來自源節點j的數據包M，節點i依據式(2)計算時延。

(2)

從式(2)可知，在IF模式下，位于交叉路口的車輛具有“優惠”的時延，離發送者越遠，退讓時間越短。通過IF模式，提高了數據包到達率。因此，當要求高數據包到達率，而不考慮冗余重播時，可采用IF模式。圖6顯示了IF模式的數據包轉發示例。

如圖6所示，源節點S發送數據包M，數據包從左向右傳輸，鄰居節點A、B、C、D、E、F均收到數據包M，其中F、C、B位于交叉路口，A、D、E位于非交叉路口。依據式(2)，F、C、B獲取優惠退讓時間，具有優先轉發數據包M的權力。同時，由于B離S最遠，其退讓時間最短，因此，B最先轉發數據包M。當收到來自B的數據包M的復本，A、C、D、E、F就取消等待。

2.5 轉發模式的選擇

轉發模式的選擇依賴于轉發節點至源節點的向量與轉發節點至目的區域的向量之間夾角。如果轉發節點有一維路徑(One-dimensional Path)到達目的區域ZOR，就啟用貪婪轉發GF模式，否則，就啟用交叉路口IF模式，使得位于交叉路口的車輛具有數據包的優先轉發權。可通過計算源節點與轉發節點的連線和轉發節點與目標區域連線的夾角，表示這兩種情況差異，如圖7所示。

圖7 兩個向量的夾角

一旦收到來自節點A的數據包，節點B從數據包提取A以及目的區域的中心點位置，并計算BA與BC的夾角θ的值，即

θ=arccos(BA·BC)

(3)

定義門限值α。通過cosθ與α進行比較，從而決定選用不同的轉發模式，并用格狀的道路拓撲表示城市場景。當接收到數據包，節點i確認位置。如果位于目的區域內，就選用IF模式。因為目的區域內，通過優先讓交叉路口車輛轉發數據包，可提高數據包的到達率；反之，就計算夾角θ，并將cosθ與α比較。如果小于α，就選擇IF模式，否則就采用貪婪轉發GF模式，算法流程圖如圖8所示。

3 性能仿真

3.1 仿真模型以及參數

圖8 轉發模式的選擇算法

圖9 仿真場景

參數值仿真平臺Scenargie16數據包大小500byte通信協議80211p調制制式OFDM(QPSK1/2)傳輸功率20dBm帶寬10MHz傳輸率60Mbit/s傳播模型ITU-RP1411

表2描述了車輛通信的參數，包括車輛移動模型、車輛密度以及速度等參數信息。

表2 車輛通信參數

3.2 性能參數

為了充分地評估提出的UGAD算法性能，將GAD與定向泛洪DF(Directed Flooding)、結合DDT的DF方案(DDT+DF)一起仿真，并進行比較。DF方案屬于Geocast路由協議，但是其沒有采取廣播抑制機制。而DDT+DF方案結合DF，并運用DDT機制抑制廣播。從下列兩個指標分析方案的性能：

2)數據包重播率(packet rebroadcast ratio)，數據包重播率越高，表明數據包冗余重播越嚴重，發生廣播風暴的概率越高。

3.3 仿真結果分析

1) GAD與DF、DF+DDT相比較

圖10顯示了在目標區域ZOR中3個方案的NVP-ZOF。NVP-ZOF的值越高，表明數據包傳遞率越高。

圖10 NVP-ZOF隨車輛密度的變化曲線

如圖10所示，與DF、DF+DDT相比，UGAD具有最高的NVP-ZOF，DF的NVP-ZOF最低。這主要是因為DF方案中的轉發區域內所有車輛都轉發數據包，引起數據包碰撞，降低了數據包傳遞率。而UGAD采用了基于退避時間的廣播抑制算法，同時，將位于交叉路口的車輛給予優先轉發權，提高數據包到達率。與DF相比，DF+DDT具有較好的NVP-ZOF性能，原因在于DF+DDT采用DDT的廣播抑制機制。DF、DF+DDT以及UGAD的數據包重播率如圖11所示。數據包重播率越高，發生廣播風暴概率越高。從圖11可知，DF方案存在很嚴重的風暴，這主要是因為DF沒有采用廣播抑制機制。而UGAD和DF+DDT通過廣播抑制機制將數據包重播率控于0.1之內，有效地解決了廣播風暴問題。

圖11 數據包重播率隨車輛密度的變化曲線

2)GAD比較

圖12描述了門限值a對UGAD的到NVP-ZOF的性能影響，在UGAD中，若a=1.0，那么位于交叉路口的車輛總是使用IF模式。從圖12可知，在低車輛密度情況下，即5～25 Vehicle/km，a為0.3、0.5、0.7、1.0下的NVP-ZOF沒有什么變化。然而當車輛密度大于30 Vehicle/km，a值越大，NVP-ZOF越大。不過，在a=0.7變為1.0時，NVP-ZOF變化不大。這也說明，沒有必要在所有的交叉路口重播數據包。如圖13所示，當門限值a較小時，比如0.3或0.5，UGAD具有非常低的數據包重播率，這主要是因為多數車輛采用了貪婪轉發GF模式。而與a=1.0相比，a=0.7的數據包重播率性能較好。

圖12 UGAD的NVP-ZOF隨車輛密度的變化曲線

4 總結

針對Geocast路由協議，提出面向城市場景的自適應時延的Geocast協議UGAD。UGAD的目的在于提高數據包到達率，同時減少冗余重播的數據包。為此，UGAD采用基于時延的交叉路口轉發IF以及貪婪轉發GF兩個模式，并依據源節點、數據包接收節點以及目標區域ZOR所在位置的不同，進行IF與GF模式的轉換，從而滿足不同的道路要求。在UGAD中，給位于交叉路口的車輛優先轉發數據包權限，提高數據包到達率。仿真結果表明，UGAD在目的區域內具有高的數據包到達率，同時保持低的冗余重播性能。

圖13 數據包重播率隨車輛密度的變化曲線

[1]CHEN W，GUHA R K，KWON T，et al. A survey and challenges in routing and data dissemination in vehicular ad-hoc networks[C]//Proc.IEEE ICVES 2008.[S.l.]：IEEE Press，2008： 328-333.

[2] MAIHOFER C. A survey of geocast routing protocols[J]. IEEE Communications Surveys and Tutorials， 2004，6(2)：32-42.

[3]于海寧，張宏莉.VANETs路由協議的研究進展[J].電子學報，2011，39(12)：2868-2880.

[4]彭沙嬰，林亞平，李超. 一種適用于稀疏無線網的定向Geocast路由協議[J].計算機工程與科學，2010，28(5)：8-13.

[5]Maihoer C.A survey of geocast routing protocols[J].IEEE Communications Surveys & Tutorials，2004，6(2)：32-42.

[6]李元振，廖建新，李彤紅，等.城市場景車載Ad Hoc網絡競爭轉發關鍵參數分析[J].電子學報，2011，38(5)：1154-1158.

[7]KO Y B，VAIDYA N H. Flooding-based geocasting protocols for mobile ad hoc networks[J]. Mobile Networks and Applications， 2012，7(6)：471-480.

[8]WILLIAMS B，CAMP T. Comparison of broadcasting techniques for mobile ad hoc networks[C]//Proc. ACM MobiHoc ’10. Switzerland：[s.n.]，2010：194-205.

[9]BACHIR A，BENSLIMANE A. A multicast protocol in ad hoc networks inter-vehicle geocast[C]//Proc. IEEE VTC 2003. [S.l.]：IEEE Press，2003：2456-2460.

[10]FLEURY M，QADRI N N，GHANBARI M. Improving propagation modeling in urban environments for vehicular ad hoc networks[J]. IEEE Trans. Intelligent Transportation Systems， 2011，12(3)：705-716.

[11]OHWADA Y，MAENO T，KANEDA S，et al. Realistic ITS simulation with scenargie simulator[C]//Proc. IPSJ DICOMO. Turku：[s.n.]，2008：233-234.

Adaptive Delay-based Geocast Protocol in Urban VANETs

LI Ming1, CAO Jianguo2

(1.ChangjiangChongqingWaterwayBureau,Chongqing401147,China; 2.SchooleofComputerScience&Technology，HuazhongUniversityofScienceandTechnology，Wuhan430074,China)

The broadcast-based geocast enables efficient data dissemination to vehicles within a given geographical region, but when dealing with broadcast, unnecessary retransmissions must be suppressed by controlling the packet forwarding to avoid the broadcast storm problem. However, most of existing broadcast suppression methods do not work in urban environments since buildings block the communication between two vehicles. In this paper, Urban Geocast based on Adaptive Delay (UGAD) protocol is proposed which adopts delay-based broadcast suppression scheme for urban environments. UGAD makes vehicles at intersections rebroadcast quickly by assigning them preferential delay values. Furthermore, vehicles use two different forwarding modes as parameters in order to fulfill the requirements of geocast. This develops the packet arrival ratio within a given geocast region, while reducing redundant rebroadcasts. Simulation results in an urban scenario show that UGAD achieves high packet arrival ratio as well as low packet rebroadcast ratio compared with existing methods.

VANETs; Geocast; broadcast storm; greedy forwarding; intersection forwarding; delay

?域內收數據包的車輛NVP-ZOF(Number of vehicles

the Packet within the Given ZOF)，NVP-ZOF越高，表明數據包到達率越高。

TP393

A

10.16280/j.videoe.2015.05.023

2014-07-11

【本文獻信息】李明，曹建國.VANETs城市場景下基于自適應時延的Geocast路由協議[J].電視技術,2015，39(5).

李 明(1981— )，碩士，工程師，主研智能交通，無線傳感器網絡；

曹建國(1985— )，博士研究生，主研集群與網格計算、分布式軟件性能評估、對等計算、語義網。

責任編輯：閆雯雯