基于自適應信標交換的方向廣播協議

吳學文，顧 欣

（河海大學 計算機與信息學院，江蘇 南京211100）

0 引 言

VANET 通過車輛節點配備的傳感器系統進行信息的采集、傳輸和交換，實現緊急情況預警、協同駕駛、分布式交通信息的收集與分發等交通安全類應用，以提高行車安全性和交通效率。其中，緊急情況預警對信息傳輸的實時性和可靠性要求極高。協同駕駛、分布式交通信息收集與分發則要求廣泛性、高效性與安全性。舒適類應用中的信息傳輸往往對傳輸可靠性、帶寬、延遲等要求較高。因此，VANET 的信息傳輸對服務質量QoS要求各異，如何針對VANET 的基本特征和不同應用設計高效的、可靠的廣播協議成為目前VANET 的研究重點。本文旨在針對現有十字路口廣播協議存在的不足，提出一種性能更優越的廣播協議。

1 相關工作

現有的VANET 廣播協議按照中繼方式又可分為基于概率的廣播協議、基于位置的廣播協議、基于MAC 層的廣播協議和基于鄰居消息的廣播協議。其中，多數協議是為高速公路等直線道路場景設計，只有少部分協議考慮十字路口處多路段的信息廣播。

1.1 現有VANET廣播協議分析

1.1.1 基于概率的廣播協議

基于概率的廣播協議中的節點接收到廣播分組后，立即或等待一定時隙后以概率P 轉發分組，P 為1時就退化為簡單洪泛。文獻 ［1］提出加權式p－堅持、時隙式1－堅持、時隙式p－堅持3種基于概率的廣播協議。K.A.Hafeez等提出一種基于網絡拓撲的p－堅持廣播協議［2］（network topology p－persistence scheme，NTPP）：若接收節點為候選廣播節點，則在延時等待后轉發分組；否則在延時等待后以概率p轉發分組。

1.1.2 基于位置的廣播協議

基于位置的廣播協議在傳輸范圍內選擇相對遠的節點轉發分組，可在較大程度上減少中繼節點數目冗余。該類協議的中繼節點選擇策略主要有：距離閾值法、計數法、概率法、時間片法。前3種策略的共同特點是中繼節點不唯一，因而不能最大程度減少中繼節點的數目和分組冗余。基于位置的廣播協議多為時間片法或其改進，完全采用分布式思想，選擇的中繼節點是確定且唯一的。目前，很多基于位置的廣播協議被提出，時間片策略也被普遍采用，典型的基于位置的廣播協議有EDB［3］、S1－PB、TRAB［4］、LDMB［5］等。

1.1.3 基于MAC層的廣播協議

針對基于IEEE802.11的MAC 協議不支持可靠廣播的問題，許多基于MAC 層的廣播協議被提出，如Gokhan K等提出一種適用于城市道路場景的多跳廣播［6］（urban multi－hop broadcast，UMB）協議，通過RTB／CTB 握手機制 （request to broadcast／clear to broadcast）選擇最遠節點作為廣播中繼節點，并通過ACK 分組確認提高可靠性。UMB的可靠性和資源利用率高，但基于握手機制的中繼選擇策略使得信道競爭與沖突問題較為突出，不適合高密度的VANET。文獻 ［7］提出的基于跨層的多跳廣播協議PMBP （position based multi－hop broadcast），基 于BRTS／BCTS握手機制選擇中繼節點，并采用IEEE 802.11e支持不同優先級分組的廣播。

1.1.4 基于鄰居消息的廣播協議

基于鄰居消息的廣播協議中，節點根據來自鄰居節點的周期性的Hello或Beacon消息維護和更新鄰居列表，在得知網絡拓撲的基礎上選擇最佳中繼節點。這種協議的中繼方式主要有：距離法、拓撲分層法、連通域集合法。其中連通域集合法是節點通過鄰居列表信息計算自身是否處于連通區域集合 （connected dominating set，CDS）中，處于CDS內的節點相對處于CDS外的節點具有更短的延時等待時間，從而最先接入信道成為廣播中繼節點。典型的基于 鄰 居 消 息 的 協 議 有 ERD［8］、StreetCAST［9］、DBAMAC［10］、DV－CAST［11］、AckPBSM［12］等。

1.2 考慮十字路口的廣播協議分析

上述廣播協議多為高速公路等直線路段場景設計，未考慮十字路口處廣播傳輸的方向性，因而將其用于城市道路是不可取的。現有的考慮十字路口的廣播協議主要有UMB、EDB、DP－IB［13］、StreetCAST、RB－FI、AckPBSM、ERD 等。對于十字路口轉發方式，UMB、EDB、DP－IB、StreetCAST 均在十字路口安裝轉發器，該集中式方法實現簡單、可靠性和信道利用率比較高，缺點是給每個路口配備轉發器增加了成本。RB－FI、AckPBSM、ERD 則采用完全分布式策略，分別在十字路口的各路段上，并從中選擇合適的中繼節點。本文主要討論分布式策略。

RB－FI通過計算轉播節點速度矢量與轉播節點到接收節點的位移矢量間夾角的正弦值，分別將轉播節點后方和前方節點分為三類 （sinα＞0、sinα＝0、sinα＜0），表示處于不同路段上，采用基于位置的時間片法分別選擇中繼節點。RB－FI默認相同道路上的車輛節點處于同一條直線上，但在實際場景中往往存在偏差 （尤其是多車道場景），容易造成分類錯誤，從而影響協議性能。AckPBSM 基于連通域集合法，無需根據車輛節點的位置、速度等信息了解車輛是否處于十字路口。ERD 在十字路口處根據 “line－ofsight”原則選擇各路段上最合適中繼節點，但由于缺乏重播機制，容易造成稀疏路段上的廣播中斷。UV－CAST 結合類似傳染轉發策略提高廣播可靠性，核心思想是：處于十字路口的中繼節點在完成分組轉播后，選擇其傳輸范圍邊界處 的 節 點 成 為SCF （store－carry－forward）節 點；SCF發現有未收到該分組的節點進入其傳輸范圍時就轉播分組，旨在保證所有方向上的不同路段的節點都能收到廣播分組。相對于以上幾種選擇各路段上最遠節點的廣播協議，UVCAST 能保證廣播覆蓋率，但額外的SCF 節點轉播分組，造成分組冗余和碰撞。

2 基于自適應信標交換的方向廣播協議DB－IA

基于鄰居消息的廣播協議根據包含位置、速度等信息的信標掌握網絡拓撲，在此基礎上選擇最合適的節點作為中繼節點，實現簡單且冗余抑制率高。因此，本文采用基于鄰居消息的中繼策略，針對現有考慮十字路口的廣播協議存在的不足，提出一種同時適用于高速公路和城市道路場景的基于自適應信標交換的方向廣播協議 （directional broadcast considering intersection via adaptive beaconing，DB－IA）。DB－IA 采用自適應信標交換機制動態調整信標分組廣播周期，減小分組沖突和網絡開銷，提高資源利用率。在可靠性方面，DB－IA 通過中繼節點間單播ACK 分組進行廣播分組確認，并結合雙向傳輸和存儲－轉發策略緩解廣播中斷問題。為避免十字路口多中繼節點同時轉播分組造成的沖突，DB－IA 通過優化退避方式控制轉播隊列，使分組轉播快速、有序地完成，提高廣播的實時性。

2.1 中繼節點選擇策略

DB－IA 中的節點根據周期性的包含ID、路段、位置、速率等信息的信標分組完成鄰居列表的建立或更新。信標分組和鄰居列表的格式如圖1所示。

圖1 信標分組和鄰居列表格式

各字段含義如下：ID：節點標識符；R＿ID：路段標識符；Loc：節點位置；Vel：節點速率；Vel－R：鄰居節點相對當前節點的運動趨勢 （靠近／遠離）；Loc－R：鄰居節點與當前節點的位置關系 （前方／后方）；Dis：鄰居節點與當前節點的距離。

對于緊急告警信息，同向車道上緊隨EMSN 的車輛處境最危險，應當優先被警告；對于交通疏導信息，同向車道上的節點進入擁堵區域的概率比較大，應當快速被告知。因此，DB－IA 優先選擇相距最遠的同向車輛節點轉發分組，旨在滿足交通安全需求的同時減少中繼節個數。當同向車道存在網絡空洞時則采用反向中繼策略，即暫時選擇反向車道上的節點作為下一中繼節點，而后在條件允許的情況下返回同向中繼策略。因此，所有車輛節點可分為同向中繼節點、反向中繼節點和非中繼節點三類。

節點接收到廣播分組后，判斷自己是否為上層中繼節點 （pre－relay node，PRN）選擇的中繼節點，若是則進行下一中繼節點的選擇。首先，根據鄰居列表中感興趣區域的鄰居節點的路段標識符R＿ID判斷場景：若R＿ID相同，說明為直路場景；若R＿ID不同，說明為十字路口場景，每個路段分別選擇一個中繼節點。同向中繼節點的感興趣區域為其后方，而反向中繼節點的感興趣區域為其前方。

直路或每個路段的中繼選擇策略基本相同，描述如下：若當前節點為同向中繼節點，則選擇后方鄰居節點中距離最遠且靠近的節點為同向中繼節點，如無靠近的節點則選擇距離最遠且遠離的節點為反向中繼節點；若當前節點為反向中繼節點，則選擇前方鄰居節點中最遠且靠近的節點為同向中繼節點，若無靠近的節點則選擇距離最遠且遠離的節點為反向中繼節點。

如圖2 所示，假設節點A 為緊急消息源節點 （emergency message source node，EMSN），A 根 據 鄰 居 節 點 的R－ID判斷后方為直線道路場景，則選擇后方最遠且靠近的節點B為同向中繼節點；B 判斷其后方為十字路口場景，在路段2、3根據最遠且靠近原則分別選擇D 和G 為同向中繼節點。對于路段1，因為無靠近的節點則根據雙向中繼原則選擇最遠且遠離的節點C為反向中繼節點。對于節點D，在判斷后方為直線道路場景后發現后方傳輸范圍內無靠近的節點，即發生同向傳輸空洞，所以選擇節點E為反向中繼節點。E選擇其前方且靠近的節點為同向中繼節點。告警信息分組按照以上規則被傳輸到遠處路段上，直到分組過期。

2.2 自適應信標交換機制

信標交換主要實現鄰居節點發現和位置等信息交互，是DB－IA進行中繼節點選擇的重要基礎和依據，其廣播方式和周期對DB－IA協議性能存在較大的影響。在節點密度相對低的場景下，較小頻率的信標交換延長鄰居發現時間，某一時刻使用的鄰居節點信息并不是最實時的，影響協議的可靠性。在節點密度相對高的場景下，若保持較大頻率的信標交

圖2 DB－IA 中繼節點選擇

換，雖能獲得較為實時的鄰居信息，但過多占用了告警信息廣播帶寬，產生沖突的概率較大，降低協議的實時性。因此，為使DB－IA能適應不同節點密度場景，本文提出一種自適應信標交換機制來取代傳統的固定周期的信標交換策略。

自適應信標交換機制主要依據車輛節點密度、距離、移動性等因素，動態調整信標交換周期I，涉及的主要參數包括：密度度量D，距離度量d、移動性度量M 等。I 的計算方法如下所示

其中，Di＝n，n表示鄰居節點的總個數，Dmax是一個預設值，表示節點能夠承受的最大鄰居節點數，dij為節點i到鄰居節點j的距離 （m），R 為車輛節點傳輸范圍，vi和vj分別為節點i及其鄰居節點的移動速率 （m／s）；w 為權重因子，可根據場景或應用的不同，調節各參數對I 計算的影響程度，此處w1＝w2＝0.25，w3＝0.5，I 的值始終處于區間 ［Imin，Imax］內，Imin和Imax分別為I 的下限和上限，其值由網絡負載承受能力和可靠性要求來決定?？紤]以下幾種情形：①D 較大，表明局部節點密度較大；②d 較大，表明節點距離較遠，節點靠近其鄰居節點的傳輸范圍邊界，因而離開其傳輸范圍的概率較大；③M 較大，即節點i的相對移動速度較快，可能快速從一鄰居節點的傳輸范圍移動到另一鄰居節點的傳輸范圍。根據式 （1）可知：情形①下，應在保證鄰居發現精度的基礎上適量減小I值，避免頻繁的信標交換造成信息碰撞；情形②③，應增大I，來緩減稀疏網絡或移動性的影響，保證鄰居發現的實時性和精度。

2.3 可靠性保障

2.3.1 ACK 機制

由于DB－IA 在每個路段只選擇一個中繼節點，這些中繼節點能否可靠地接收到告警分組至關重要，DB－IA 通過在相鄰中繼節點間的ACK 分組來保證廣播的可靠性。每個中繼節點在轉播分組后開啟重播定時器 （ReBroadcast timer，RBT），生成ACK 分組并準備發送至PRN；檢查其鄰居列表，若PRN 在其中，則單播ACK 分組給PRN；否則，廣播該ACK 分組。接收ACK 廣播分組的鄰居節點，若發現目標節點在其鄰居列表中，則競爭ACK 信使節點。競爭勝出的節點單播該ACK 分組給目標節點；否則，丟棄該ACK 分組，不作處理。若該中繼節點在其RBT 溢出之前未收到所有來自下層中繼節點的ACK 分組，則進行告警分組重播。

ACK 信使節點競爭過程如下：發送ACK 報文的最大等待時間TAck－max被分為NAck個等長時間片，每個時間片的長度LAck為

每個競爭ACK 信使節點的中間節點首先從 ［0，NAck－1－1］中隨機選擇一個時間片idx，再從 ［0.0，LAck］中隨機選擇一個片內偏移offset，則最終的延時等待時間TAck如下所示

經過兩次隨機選擇，各中間節點的等待時間被較大程度地離散化，有效降低了多個中間節點同時轉發ACK 報文的概率。

2.3.2 網絡空洞修復機制

當因網絡空洞造成廣播中斷時，中繼節點重復啟動重播定時器，不斷周期性的重播分組，直到有車輛進入其信號覆蓋范圍內或者消息過期。圖3展現了網絡空洞的修復過程：時刻1，中繼節點A需要轉播分組，而其傳輸范圍內無車輛節點，即產生網絡空洞；時刻2，節點B進入A 的信號覆蓋范圍內，成為反向中繼節點，而其傳輸范圍內也無其它節點，因此繼續周期性重播過程；時刻3，節點C進入B的信號覆蓋范圍，成為同向廣播節點，網絡空洞修復成功；若分組未過期，則繼續進行分組的定向廣播。網絡空洞修復時間相對較長，對信息傳輸時延的影響較大，卻又不可避免。

圖3 網絡空洞修復過程

2.4 十字路口多中繼節點快速轉播機制

在十字路口場景中，各路段的中繼節點接收到廣播分組的時刻比較靠近，并可能同時嘗試轉播分組競爭信道。為減少隨機退避策略帶來的沖突和碰撞，DB－IA 通過合理設置退避時間來控制分組轉播隊列，使得十字路口的廣播中繼快速、有序完成，減少時延。

如圖4所示，節點B和C偵聽到節點A 的轉播，而后節點B開始延時退避和轉播，后續節點C 重復這個過程。DB－IA 加入網絡分配矢量NAV，其值設置足夠大，以保證列表上的中繼節點能不受干擾地完成各路段上的分組轉播。

圖4 十字路口多中繼節點轉播機制

3 協議仿真與性能評估

本文以NS－2作為網絡仿真平臺，利用VanetMobiSim交通流仿真器限制車輛運動的區域及軌跡，以廣播覆蓋率（REachability，RE）、廣 播 冗 余 抑 制 率 （saved ReBroadcast，SRB）、分組碰撞次數 （number of collision，NoC）、端到端時延 （latency）為網絡性能評估指標，分別對RBFI、ERD、UV－CAST 和本文提出的DB－IA 進行仿真實驗和性能比較。

以上評估指標定義如式 （8）～式 （10）所示，其中NRNt和NRNr分別是源節點后方車輛節點數和源節點后方接收到廣播分組的車輛節點數，NBNf是信道競爭后成為中繼節點的車輛節點數，TSr是源節點后方某節點首次接收到廣播分組的時間戳，TSs是源節點產生告警信息的時間戳

3.1 實驗環境與場景

本文利用VanetMobiSim 為車輛自組網設計了車輛移動的場景，設置的參數包括仿真區域，仿真區域被劃分塊數，其中運動的車輛數，車輛移動的速度范圍，以及包含紅綠燈的岔路口個數。具體參數設置見表1。

表1 VanetMobiSim 的仿真參數設置

仿真實驗在Otcl仿真配置腳本中設置相關實驗參數，見表2。其中，RB－FI處于 ［0，RAD＿TMAX］區間上，RAD＿TMAX 設置為100ms。Street－CAST 和ERD 的信標交換周期設置為0.25 ms，而DB－IA 則根據密度、速度等參 數 計 算 信 標 交 換 周 期。Street－CAST、RB－FI、ERD、UV－CAST 的MAC 協 議 均 采 用IEEE802.11DCF，而DBIA 則采用提出的改進思想。

3.2 結果與分析

本文在不同告警信息產生時刻，對6種交通場景進行仿真，最后統計獲得其平均值作為實驗結果，如圖5～圖8所示。

（1）4種協議的RE隨車輛節點密度呈遞增趨勢，且在高密度場景下都能達到100%。ERD 因缺乏分組確認機制來修復稀疏路段的廣播中斷，RE 性能較差，原因在于：UV－CAST 協議指定SCF 節點緩存分組，并轉發給進入其傳輸范圍內且未收到該分組的鄰居節點，以確保所有路段的車輛節點都能接收到廣播分組；DB－IA 通過在中繼節點間單播ACK 分組進行廣播分組確認；RB－FI雖采用存儲－轉發策略，但節點分類錯誤使得實際情況中某些路段上不存中繼節點，從而影響RE性能。

表2 NS－2仿真實驗參數設置

圖5 不同車輛節點密度場景下的RE

圖6 不同車輛密度場景下的SRB

圖7 不同車輛密度場景下的NoC

圖8 不同車輛密度場景下的平均Latency

（2）DB－IA 和ERD 的冗余抑制效果接近且相對較好，RB－FI次 之，UV－CAST 相 對 最 差。ERD 和DB－IA 都 是 在得知網絡拓撲的基礎上，直接在每個路段上選擇最遠且唯一的中繼節點，從而較大程度上減少了中繼節點的數目和廣播跳數。RB－FI由于分類錯誤問題，某一路段可能存在兩個或以上節點轉播分組，廣播冗余抑制的效果不佳。在稀疏場景中，UV－CAST 中每個十字路口選擇的SCF 節點增加了轉播節點的個數，所以SRB性能相對RB－FI低。隨著節點密度的增加，UV－CAST 的SCF 節點轉播分組需求降低，而RB－FI的分類錯誤程度加劇，兩中協議的SRB性能的差距逐漸減小。

（3）4種協議的NoC都是車輛節點密度的遞增函數。當節點密度增大時，ERD的中繼節點數目不受影響，但信標分組數量激增；ERD的分組碰撞比較嚴重。RB－FI中，節點分類錯誤增加了中繼節點的個數，而節點密度的增加使得距離相近的鄰居節點競爭信道，導致分組碰撞加劇。DB－IA 的NoC最小，原因在于：與ERD 相似，中繼節點數目基本不受節點密度變化的影響；自適應信標交換機制在節點密度增大時適度減少分組交換頻率，從而減少信標分組的數量；針對十字路口各路段上的中繼節點同時轉播分組可能造成的碰撞，DB－IA通過設置遞增的退避時間來控制轉播順序，使得轉播快速、有序完成，很大程度上減少分組碰撞的概率。

（4）平均Latency曲線呈現兩邊高、中間低的形態，表明節點密度過低或過高都會降低廣播的實時性。無論在稀疏場景或稠密場景中，DB－IA 的實時性最好。

當ρ＞10時，DB－IA 的中繼節點個數幾乎不受密度增加的影響；改進的退避方式避免十字路口多中繼節點的分組碰撞，有效減少信道接入時延；自適應信標交換機制減小信標的廣播周期，減少信標分組與廣播分組的碰撞。ERD 中激增的信標分組，UV－CAST 中多中繼節點的信道競爭，RB－FI中節點路段分類錯誤，使得它們的平均Latency比DB－IA 大。

當ρ≤10時，ERD 由于沒有確認和重播機制修復網絡空洞，廣播中斷帶來的時延較大。DB－IA 結合存儲－轉發和雙向傳輸策解決網絡空洞問題，修復時間相對短。RB－FI和UV－CAST 分別采用存儲－轉發和SCF節點轉發策略修復網絡空洞，但耗時相對DB－IA 長，平均Latency稍大。

當ρ處于 （5，10］區間時，DB－IA 和ERD 的平均Latency小于RB－FI和UV－CAST，原因在于：DB－IA 和ERD在每個路段上選擇唯一的中繼節點，平均Latency隨著中繼節點數目較少而減少；RB－FI和UV－CAST 的廣播冗余效果不如前兩種協議，平均Latency有所增加。

4 結束語

本文在研究現有VANET 廣播協議的基礎上，針對十字路口廣播協議存在的不足，提出了一種同時適用于高速公路和城市道路兩種場景的方向廣播協議DB－IA。根據周期性的信標交換獲得網絡拓撲信息，在各路段上選擇最遠的節點作為中繼節點，減少了廣播跳數。采用自適應信標交換機制取代傳統的固定周期的信標交換，減少了分組沖突和網絡開銷。通過ACK 分組確認機制，提高廣播可靠性。通過給每個中繼節點設置遞增的退避時間，提高廣播實時性和可靠性。仿真結果表明，DB－IA 具有相對優越的性能，適合交通安全類信息傳輸。

［1］Wistipongphan N，Tonguz OK，Parikh JS，et al.Broadcast storm mitigation techniques in vehicular ad hoc networks［J］.Wireless Communications.IEEE，2007，14 （6）：84－94.

［2］Hafeez KA，Zhao Lian，Liao Zaiyi，et al.A new broadcast protocol for vehicular ad hoc networks safety applications［C］／／Global Telecommunications Conference.IEEE，2010：1－5.

［3］Li Da，Huang Hongyu，Li Xu，et al.A distance－based directional broadcast protocol for urban vehicular ad hoc network ［C］／／Proc of the International Conference on Wireless Communications，Networking and Mobile Computing，2007：1520－1523.

［4］Wu Xuewen，Yan Wei，Song Shiming，et al.A transmission range adaptive broadcast algorithm for vehicular ad hoc networks［C］／／Proc of the Second International Conference on Networks Security Wireless Communication and Trusted Computing，2010：28－32.

［5］Yang Qiong，Shen Lianfeng.A multi－hop broadcast scheme for propagation of emergency messages in VANET ［C］／／Proc of 12th IEEE International Conference on Communication Technology，2010：1072－1075.

［6］Korkmaz G，Ekici E，Ozguner F.Black－burst－based multihop broadcast protocols for vehicular networks［J］.IEEE Transactions on Vehicular Technology，2007，56 （5）：3159－3167.

［7］BI Yuanguo，ZHAO Hai，SHEN Xuemin.A directional broadcast protocol for emergency message exchange in inter－vehicle communications［C］／／IEEE International Conference on Communications，2009：1－5.

［8］Tung Lung－Chih，Gerla M.An efficient road－based directional broadcast protocol for urban VANETs ［C］／／Proc of IEEE Vehicular Networking Conference，2010：9－16.

［9］Yi Chih－Wei，Chuang Yi－Ta，Yeh Hou－Heng，et al.Streetcast：An urban broadcast protocol for vehicular ad hoc networks［C］／／Proc of the IEEE 71st Vehicular Technology Conference，2010：1－5.

［10］Bononi L，Di Felice M.A cross layered MAC and clustering scheme for efficient broadcast in VANETs［C］／／Proc of the IEEE International Conference of Mobile Ad Hoc and Sensor Systems，2007：7－12.

［11］Tonguz O，Wisitpongphan N，Bai F，et al.Broadcasting in VANET ［J］.Mobile Networking for Vehicular Environments.IEEE，2007：7－12.

［12］Ros FJ，Ruiz PM，Stojemnovic I.Reliable and efficient broadcasting in vehicular ad hoc networks［C］／／Proc of Vehicular Technology Conference.IEEE，2009：1－5.

［13］Zhao Jing，Zhang Yang，Cao Guohong.Data pouring and buffering on the road：A new data dissemination paradigm for vehicular ad hoc networks［J］.IEEE Transactions of Vehicular Technology，2007，56 （6）：3266－3277.