基于概率的車載網自適應廣播協議

熊 鵬

(上海電機學院 電子信息學院，上海 201306)

車載自組網(Vehicular Ad-hoc Networks, VANET )的發展不僅對眾多商業發展和娛樂推廣起著巨大的推動作用，也是現代智能交通系統(Intelligent Transportation System, ITS) 的重要組成部分，對提高交通安全狀況更是不可或缺的。據文獻[1]報道,若司機能多出額外0.5 s的報警時間，高速上車輛追尾事故將能降低近60%。因此，通過為VANET設計和構建新協議來向那些行駛在車輛稀疏或視線受限區域的車輛發布告警信息具有非常重要的積極意義。

專用短距通行(Dedicated Short Range Communication, DSRC)技術作為近年新出現的技來術，完全能夠滿足了VANET對安全或非安全領域的需求；它同時也被認為是車輛間實現無線訪問(Wireless Access in Vehicular Environment, WAVE)[2]或IEEE802.11p協議[3]的最好技術和方案。借助于DSRC技術，VANET中車輛間通信可以通過兩種方式來實現：車輛與車輛間的通信 (V2V) 和車輛與路邊設施間的通信(V2R)[2,4-5]。前者借助車載本身搭載的通信單元(OBU)，車輛向行駛在路上的某特定車輛發送信息；后者車輛則只與安裝在路邊的固定設施(RSU)進行信息交互。不管是V2V還是V2R，廣播通信都已成為多數VANET實際應用中車輛間信息發布的基礎性方案。例如，某個特定RSU可以針對路上的特定區域廣播交通事故信息。對應區域車輛一旦收到相關信息，則可以進一步向與其相鄰的車輛廣播該信息，同樣的行為在該區域所有車輛間不斷重復進行,直至該區域所有車輛都收到該信息，進而能做出規避事故區域的選擇，從而能夠避免事故區域的交通擁堵狀況，提高整個道路車輛通行效率。原始意義上的廣播通信通常由泛洪算法實現。泛洪是一種節點全網廣播信息，以保證網絡中所有節點都能收到相應信息的算法。這種算法在節點有限的中小網絡中運行效果不錯，通行效率也較高。但同樣的算法照搬到大型可擴展網絡中，節點的廣播、重播通信將會造成大量冗余廣播信息，以及因共享無線信道而導致的節點相互傳送信息時的信道爭用帶來的數據沖突，都將使得泛洪算法的性能急劇降低。這就是著名的廣播風暴問題(Broadcast-Storm Problem, BSP)[6]。近年來，針對BSP涌現出了不少解決方案，它們可歸納為4類[7]：① 基于概率的；② 基于泛洪的；③ 基于區域的(又可進一步劃分為基于位置和基于距離的)；④ 基于鄰居關系的。這些方案同時也在移動自組網中出現并得到廣泛研究[8-12]。BSP同樣也困擾著VANET中節點進行的信息廣播通信。針對VANET中的BSP，在綜合分析和參考已有技術方案的情況下，從信息的可達性和降低信息重播數量兩方面著手，提出了新的基于概率的自適應加權廣播協議(Adaptive and Weighted Broadcast Protocol，AWBP)。模擬試驗顯示方案在沒有顯著增加額外開銷的情況下，能夠解決或較大程度地緩解大型網絡中廣播通信引起的BSP。

1 相關工作

文獻[13]基于概率和計時器在單、雙車道高速路的設定場景下，提出了3個廣播通信方案: 時隙1-堅持、時隙p-堅持和加權時隙p-堅持；并分別從分組傳送延遲、丟包率和系統開銷3個方面分析了它們的性能。時隙1-堅持中，網絡中的節點一旦收到相關廣播信息，則以概率1向其他節點廣播接收到的信息(即一定重播)。時隙-堅持，其要求所有節點以預先選定的概率p重新廣播接收到的信息。這里，概率p通常為0.5，該值通常能實現網絡的最大效能。雖然，時隙p-堅持能通過使用多個不同的p值來提升網絡性能[8,10]，但其仍然存在著大量廣播被重傳的現象。對于加權p-堅持(WPP)[13]，其節點重播接收到信息的概率必須等于發送節點和接收節點信號范圍間的比值。WPP在網絡節點(車輛)數量不足的區域效率非常低；而對高密度節點(車輛)區域，節點也必須選擇一個適當的廣播概率才行。此外，上述3個方案在廣播收到(或新)的信息前，節點都必須緩存信息一段時間。文獻[14]針對BSP和隱藏節點問題及可靠的多跳廣播需求提出了一個專用于車載網的城區多跳廣播協議(Urban Multi-hop Broadcast,UMB)。該協議雖然實現了高密度節點區域高流量負荷環境下的網絡信息交付的高成功率，但該協議需要中繼器、支持黑場信號等的硬件成本和額外能量消耗。作為UMB協議的擴展，文獻[15]給出了一個完全自組織網絡多跳廣播協議(Adhoc Multihop Broadcast,AMB)。該協議使用了一個定向廣播方案來向距離自己最遠的節點指派重播功能，專門設計的十字路口廣播方案被用來處理十字路口的信息重播，從而避免了UMB中交叉路口廣播信息時對中繼器的需求。

文獻[12]中的廣播方案，試圖通過限定緊急信息的廣播方向在源節點周邊減緩BSP。然而該方案沒有對由廣播造成的影響進行量化性分析，也沒有提供具體的方式、方法或手段來評估該方案的具體性能和效果。文獻[12]中的方案基于源節點和目的節點的位置、方向和移動速度提出了一個新的廣播方案。通過忽略源、目的節點信號沒有覆蓋到的節點進行的重播，使得該方案能把BSP的影響降到最低。 事實上，前面提到的絕大多數基于概率的廣播方案都會造成網絡中大量冗余廣播信息的出現，而這些信息正是導致BSP產生的根源。在充分吸納現有廣播協議優點的情況下，本文基于WPP協議提出了一個新的基于概率的AWBP。模擬試驗表明：新協議能夠避免WPP協議性能嚴重依賴網絡環境的不足，在數據可達率和降低節點廣播數量等多個指標數據上均有良好的性能。

2 基于概率AWBP

新協議以WPP協議為基礎 ，以低重傳概率實現網絡信息高可達性為目標，嘗試著提出了一個新的基于概率的AWBP，并對它的性能做了全面分析， 試驗結果顯示AWBP完全能夠以較低的額外開銷實現預先設定的各項目標。

2.1 相關概念

通過對現有研究的分析和總結，能夠發現，車載網的廣播協議的性能可集中體現于2個參數：信息可達率RE(Reachability)和重播保存率SR(Saved Rebroadcast)。一個好的車載網廣播協議應該具備在信息可達性和重播保存率間達成平衡的能力。

定義1信息可達率RE。假設網絡中的節點總數為N，節點Vr收到的信息數量為r，則信息可達率為

RE=r/N

(1)

該參數反映了收到信息的車輛與網絡中車輛總數之間的比值。

定義2重播保存率SR。假設節點Vs發送了s個信息，如果節點Vr收到的信息數量為r，則重播保存率為

SR=1-s/r

(2)

該參數主要反映協議降低廣播重播信息的能力。

2.2 基于概率的AWPB

WPP協議中，車輛一旦收到一個數據分組，就按概率Pij進行重播并定義

Pij=Dij/R

(3)

式中:Dij為節點i和j間的距離；R為網絡中信息平均傳輸的范圍。

WPP規定：如果節點收到來自多個不同節點的相同信息，則該節點在重播該信息前必須等待一段隨機時間，從而能夠以盡量低的概率來重播信息。顯然，那些與源節點有相同距離的節點將具有相同的重播概率。這也是WPP協議在高密度節點網絡中更容易出現BSP的原因。對于一個擁有少量節點的稀疏網絡，當接收到信息的節點恰好為源節點的近距離節點時，該節點的重播概率將非常低，從而又將導致信息在全網節點間的低可達性。顯然，應該對WPP中的轉發概率進行重新設計。

圖1顯示的兩種場景。假設S以250 m的半徑廣播信息。其中，S與C,E,F,G和H間的距離D分別為5 m、100 m、100 m、125 m和125 m。根據式(1)，相應節點的轉發概率分別為0.02，0.4，0.4，0.5和0.5。通過試驗可觀察到，來自C的重播將會消亡，無法到達節點A和B。而來自E，F，G和H的重播又將產生過多的重播冗余數據出現。

圖1 WPP協議的缺陷

因此，提出的AWBP協議中，設計了一個通用的概率方法，其動態地調整每輛車的重新轉發概率，并且考慮每個車輛的局部密度，具體算法邏輯步驟如下。

Begin

{

Step1節點Vr收到新信息msg

Step2計算源節點Vs與Vr間的距離d

Step3計算Vs鄰居節點的數量Nn

Step4計算網絡中平均鄰居結點數量Navg

Step5Ifd≤r/2 THEN //r為傳輸范圍

IfNn≥NavgTHEN

Vr位于一個密集結點的網絡區域中

Vr靠近源節點Vs,并且廣播半徑小

Vr以低概率P=Plow對接收到的信息進行

Go to Step7

Else

Vr位于一個稀疏結點的網絡區域中

Vr靠近源節點Vs,但廣播半徑小

Vr以低概率P=Plow對接收到的信息進行

重播: Go to Step7

Step6Ifd>r/2 THEN

IfNn

Vr位于一個稀疏結點的網絡區域中

Vr無離源節點Vs,度且廣播半徑大

Vr以低概率P=Plow對接收到的信息進行

重播: Go to Step7

Else

Vr位于一個密集結點的網絡區域中

Vr靠近源節點Vs,并且廣播半徑小

Vr以低概率P=Plow對接收到的信息進行

重播: Go to Step7

Step7If (Random::uniform(0.0, 1.0)<=P)

Forward(msg)

Else

Free(msg)

}

End

上述算法中,步驟7是利用區域(0.0,1.0)中的均勻隨機數來進一步降低網絡中可能出現的重播冗余。

為了評估網絡的局部密度，AWBP通過使用“HELLO”分組來獲取節點的鄰域信息，以便為網絡中的每個節點構造其1跳鄰居列表。

對一給定拓撲場景的網絡，假設網絡中節點總數為N，任意節點Vi在某一特定時刻的鄰居節點數量為Xi，則該網絡的鄰居節點平均數為

(4)

根據文獻[6]中的方法，網絡中每個節點每秒周期性地向四周廣播“HELLO”分組以獲取該節點的鄰居數量(Xi)，該值與網絡平均鄰居節點數(Navg)間的比值作為判斷節點所處網絡區域的疏密標準。每個節點就能對接收到的信息獨立作出重播與否決策。限于資源和時間，本協議的最佳網絡節點平均鄰居數量Navg通過大量的模擬試驗來獲取。表1顯示了在不同路況和節點總數的情況下，相對應的最佳平均網絡鄰居節點的數量。

表1 不同路況和節點數量下對應的平均鄰居節點數

AWPB依據網絡平均節點數把道路劃分為節點密集區和節點稀疏區2個邏輯區域。不同的邏輯區域中的不同節點都將有自己特定的信息重播概率。

對于高密度區，節點的信息轉發概率可由式(3)調整為

(5)

相應的低密度區節點轉發概率可調整為

(6)

在某些情況下，P值可能小于零或大于1。 小于零則意味著高密度區中,節點非常靠近發送節點。 這種情況下,通過編碼可以將P值調整為零。大于1則意味著稀疏區域中的節點距離發送節點非常遠。 同理,這時P的值將被調整為1。

表2顯示了不同P值的可能情況。每個接收到信息的節點首先應該緩存該信息，同時初始化自己的計時器以等延時TWAIT_TIME的到來。若在最大延時Tmax期間，節點不止一次的收到相同信息，則依據式(5)來計算信息重播概率。否則，信息重播概率由式(6)決定。信息重播延遲則可通過下式(7)來確定：

式中：T0為節點密度與信息發送、接收節點間距離的關系。

表2 不同距離鄰居節點對應的轉發

這里需要特別指出的是：AWBP采用文獻[16]的方案，Tmax的值均勻的分布于[0，2] ms之間。這就意味著：鄰居越多的節點，其延遲重播信息的時間越長；反之，鄰居越少的節點則能更快的重播信息。

3 性能分析

實驗采用和曼哈頓城市模型(Manhattan Grid Model)在NS-2 2.34相同的模擬實驗平臺[17]執行。通過不同場景和關鍵參數的多個模擬實驗來獲取包括信息可達率和重播保存率在內的AWPB的多項性能指標。實驗區域大小設為2 km×2 km，每次實驗時間定為15 min，具體參數如表3。

整個區域被劃分為兩橫兩縱，擁有4個十字路口的車輛通行環境。在每個十字路口，車輛可以某個確定的概率選擇向左或右轉。這時車輛轉彎的概率設定為0.5。每條道路擁有兩個車道，車輛在兩邊均可移動。車輛發送信號的有效距離為250 m，這也是DSRC[18]的推薦距離。網絡密度通過改變公路上的車輛數量來實現網絡中節點密度從低到高變化。為了更真實地模仿城市道路通行狀況，則以不同車速的實驗來模擬現實道路交通環境。例如，車速可分別設定為60 km/h的城市道路最高限速或30 km/h擁擠時的車速。為了更好地反映AWPB的性能，實驗對AWPB，WPP和簡單泛洪協議(SF)三者同時展開模擬，并對它們的實驗數據進行比較。結果顯示,重播的概率對網絡中冗余信息的數量存在著重要的影響。

表3 模擬實驗的參數設置

實驗分別從車輛密度和車速兩方面考察對信息的可達性和重播保存率2個重要指標[19-20]的影響。

3.1 車輛密度對廣播協議性能的影響

為了摸擬現實交通中車輛密度隨時間變化的場景，第1個試驗，每公里的車輛數從10輛逐漸增加到100輛。車速則從最低的20 km/h提高到60 km/h。結果如圖2和圖3所示。

圖2 3個協議的SR與車輛密度的關系

圖2和圖3顯示了車輛密度不同時，對三者的重播保存率和信息可達率帶來的影響。圖2反映了車輛密度與AWBP,WPP和SF 3個廣播協議的重播保存率的關系。當車輛密度為100輛/km時，AWBP,WPP和SF分別對應著73%，39%和0保存率；而當車輛密度降到10輛/km時，它們相應的保存率也降低到31%，15%和0。顯然，AWPB性能明顯優于WPP和SF兩者。此外，相對WPP和SF，AWPB的車輛密度應用范圍也更大。

圖3 3個協議的RE與車輛密度的關系

3.2 車速對廣播協議性能的影響

第2個實驗的車輛密度定為70輛/km，車速介于30～80 km/h，以便觀察車速對RE和SR的影響。

圖4反映的是車速與AWBP,WPP和SF 3個廣播協議SR的關系。從圖4可看出，隨著車速從30 km/h增加到80 km/h，WPP的SR從20%提升到40%，而AWPB卻把自己的SR從40%提升到了78%左右。這里，SF的SR近似于零，這是因為每輛車都重播它們的信息而導致的。顯然，AWBP相較于WPP和SF,SR提高了50%～100%，有著明顯的性能優勢。

圖4 3個協議的SR與車速的關系

圖5反映的是車速與AWBP,WPP和SF 3個廣播協議的信息可達率RE的關系。從圖5可以看出，隨著車速的提升，三者都有較好的表現，尤其SF表現最好，其信息可達率RE幾乎近于100%。但與WPP比,AWBP的表現又要更好些，當車速達到或超過某個值時，其RE有著和SF同樣的優異表現。

圖5 3個協議的RE與車速的關系

4 結 語

提出一個新的基于概率的AWPB，目的是為了緩解車載網廣播信息時所引起的BSP。模擬實驗結果顯示，AWBP能極大地減少網絡中的泛洪數據量(比SF減少了60%以上，比WPP也減少了25%以上)。顯然，AWPB的性能比很多已有的類似工作在緩解BSP上有著更好地表現。希望對VANET設計者在開發具有指定的覆蓋和連接度的基于應用的車載網絡時具有實際意義。

參考文獻

[1] AMBAK K, ATIQ R, ISMAIL R, Intelligent transport system for motorcycle safety and issues[J].European Journal of Scientific Research, 2009,28(4): 600-611.

[2] MORGAN Y L.Managing DSRC and WAVE standards operations in a V2V Scenario[J]. International Journal of Vehicular Technology, 2010(2):1-18.

[3] Network Working Group. Ad hoc on demand distance vector (AODV) routing protocol. RFC 3561. [EB/OL]. (2003-07-01) [2018-03-23]. https://tools.ietf.org/html/rfc3561

[4] ARMSTRONG L. Dedicated short range communications (DSRC) Home. [EB/OL][2018-03-23].http://www.leearmstrong.com/DSRC/DSRCHomeset.htm.

[5] IEEE standards association. IEEE Std 802.11eTM. [EB/OL]. (2005-05-03)[2018-03-23]. http:// http://standards.ieee.org/findstds/standard/802.11e-2005.html

[6] NI S Y, TSENG Y C, CHEN Y S,et al. The broadcast storm problem in a mobile ad hoc network [J]. The 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, 1999,8(2-3): 151-162.

[7] WILLIAMS B, CAMP T.Comparison of broadcasting techniques for mobile ad-hoc networks[C]//The 3th Acm International Symposium on Mobile Ad Hoc Networking and Computing. Lausanne: ACM SIGMOBILE, 2002: 194-205.

[8] SASSON Y, CAVIN D,SCHIPER A. Probabilistic broadcast for flooding in wireless mobile ad hoc networks[J]. Wireless Communications and Networking, 2002(2): 1124-1130.

[9] FUKUHARA T, WARABINO T, OHSEKI T,et al. Broadcast methods for inter-vehicle communications system[J]. Wireless Communications and Networking Conference, 2005(4): 2252-2257.

[10] YASSEIN M M B,KHAOUA M O,MACKENZIE L M,et al. Performance evaluation of adjusted probabilistic broadcasting in MANETs[EB/OL]. [2018-03-23].https://www.computer.org/csdl/proceedings/dasc/2006/2539/00/25390245-abs.html.

[11] YASSEIN M B, AL-DUBAI A, KHAOUA M O, et al. New adaptive counter based broadcast using neighborhood information in MANETS.[C]//The 23rd IEEE International Symposium on Parallel and Distributed Processing. Rome: IEEE, 2009:1-7.

[12] YANG Y, CHOU L. Position-based adaptive broadcast for inter-vehicle communications[EB/OL].[2018-03-23].https://www.mendeley.com/research-papers/positionbased-adaptive-broadcast-intervehicle-communications/.

[13] SLAVIK M, MAHGOUB I. Stochastic broadcast for VANET[C]// The 7th IEEE Conference on Consumer Communications and Networking Conference. Las Vegas:IEEE,2010: 205-209.

[14] KORKMAZ G, EKICI E, ?ZGüNER F,et ai.Urban multihop broadcast protocol for inter-vehicle communication systems[J]. ACM International Workshop on Vehicular Ad-hoc Networks. 2004:76-85.

[15] KORKMAZ G, EKICI E, OZGUNE F.An Efficient fully ad-hoc multi-hop broadcast protocol for inter-vehicular communication systems[J]. IEEE International Conference on Communications, 2006(1):423-428.

[16] BACHIR A,BENSLIMANTE A. A multicast protocol in ad hoc networks inter-vehicle geocast.[C]//The 57thIEEE Semiannual Vehicular Technology Conference. Jeju Island: IEEE, 2003:2456-2460.

[17] Information Sciences Institute. NS-2 simulation experiment platform. [EB/OL]. (2016-10-18)[2018-03-23]. http://ftp.isi.edu/nsnam/dist/.

[18] OMAR H A, ZHUANG W, LI L.VeMAC: A TDMA-based MAC protocol for reliable broadcast in VANETs[J]. IEEE Educational Activities Department , 2013,12(9): 1724-1736.

[19] AL-KUBATI G, AL-DUBAI A, MACKENZIE L，et al. Efficient road topology based broadcast protocol for VANETs.[C]//The IEEE Wireless Communications and Networking Conference. Istanbul: IEEE,2014:2710-2715.

[20] ELBATT T, YEUNG G, HABERMASS.Performance evaluation of safety applications over DSRC vehicular ad hoc networks.[C]//Proceedings of the First International Worshop on Vehicular Ad Hoc Networks. Philadelphia: ACM SIGMOBILE,2004:1-9.