車聯網中基于距離的多轉發者廣播協議

韓江洪,李 超,衛 星,魏振春

(1.合肥工業大學計算機與信息學院,合肥230009;2.安全關鍵工業測控技術教育部工程研究中心,合肥230009)

進一步抑制轉發,并使轉發節點盡力向源節點的覆蓋區域邊緣集中。在交通阻塞的節點密集場景下進一步減少參與轉發的節點數量,設計概率計算公式:

車聯網中基于距離的多轉發者廣播協議

韓江洪1,2,李 超1,衛 星1,2,魏振春1,2

(1.合肥工業大學計算機與信息學院,合肥230009;2.安全關鍵工業測控技術教育部工程研究中心,合肥230009)

為實現安全信息在車載自組織網絡中快速、有效的傳播,提出一種基于距離的多轉發者廣播協議。將上一跳轉發節點信號邊緣處的節點作為最優轉發節點,以增加單次轉發覆蓋新節點的數量。選擇信號覆蓋范圍中點處節點和次接近信號覆蓋范圍邊緣處節點作為備選轉發節點,以降低因隱蔽站或車輛脫離信號覆蓋范圍導致轉發失敗的概率,并通過反向車輛存儲轉發廣播分組恢復路由。仿真結果表明,該協議能夠適應多種車輛密度的車載自組織網絡,滿足不同交通流密度情況下緊急信息的分發要求,降低車輛間通信的平均端到端延時和轉發率,提高轉發效率,并且負載上升緩慢,能有效抑制廣播風暴。

車載自組織網絡;廣播協議;存儲轉發;多轉發;隱蔽站沖突;路由恢復

1 概述

高速公路環境車速快、封閉性強的特點使高速公路事故多發、救援困難。依靠多跳Ad-hoc網絡廣播前方道路信息將有效減少交通事故和交通阻塞。由于車載自組織網絡(Vehicular Ad-hoc Network, VANET)節點移動快,鏈路存活時間短,傳統的移動網絡廣播協議在車載自組織網絡應用中存在諸多問題,適用于車載自組織網絡的廣播協議已經成為VANET研究熱點問題。

在VANET中,最簡單的信息分發方式是泛洪式廣播,任何接收到新信息的節點都向其鄰居節點轉發,隨著網絡節點數量的增加,其效率會急速下降,在車流密度大的區域冗余會造成嚴重的碰撞,形成廣播風暴,消耗有限的信道資源。針對泛洪式廣播協議的不足,已有許多研究者提出一系列改進協議。文獻[1]通過可變的自適應幀長,實現對競爭節點的定量傳輸,與傳統協議相比,可以提升網絡的健壯性,減少傳輸時間,但同時也增加了分組丟失率,未實現對已接收信息進行反饋,效率較低。文獻[2]通過貪心選擇具有最大額度的節點作為廣播轉發節點以減少信息轉發次數。文獻[3-5]通過計算接收節點與源節點距離和最大傳輸半徑的比值得出一個轉發延時,離廣播節點較遠的節點有較短的等待時隙以達到減小冗余轉發的目的,但在網絡稀疏時若干等待時隙中不存在轉發節點,轉發延時較大。文獻[6-7]研究了稀疏網絡的廣播消息傳播問題,提出了一種存儲-攜帶-廣播的策略,一定程度上解決了在道路車輛較少情況下廣播信息不可達問題。文獻[8]通過增設路基設備,解決稀疏網絡不連通以及信息傳播時延高問題。文獻[9-10]分析了某特定路段上任意兩車之間的聯通概率問題,設計了一種車聯網報文格式,應用連通性模型中的相關參數解析式給出了廣播消息報文的TTL字段的初始值設定方案,從而有效控制廣播報文的泛濫。文獻[11-12]論述了車聯網以及常見的車聯網路由協議及其比較。文獻[13]通過選取最佳中繼節點來最大限度提高車聯網的端到端吞吐量。

由于節點密集和節點稀疏在高速公路上都有可能存在,在節點密集區域需要抑制廣播分組,而在節點稀疏區域需要進行存儲轉發以提高廣播消息送達成功率。因此,本文提出一種基于距離的多轉發者廣播協議(DBMSB),主要用于高速公路無基站環境下車輛安全消息的分發,該方法結合高速公路環境下車輛分布特性,由上一跳轉發節點確定多個下一跳轉發節點,在某次轉發不成功時利用備選轉發節點減少轉發失敗而引起的時延,并利用反向車輛解決鏈路斷開信息不可達問題。

2 DBMSB協議

2.1 DBMSB協議相關定義

DBMSB協議約定待研究的VANET節點都安裝有GPS和相同的全向天線[14],其通信半徑為R。道路上的每個節點維持2個1跳范圍內節點信息表、同向節點信息表(Node towards the Same Direction,NSD)和反向節點信息表(Node towards the Opposite Direction,NOD),NSD表和NOD表包含節點信息類型相同,其節點信息由周期性交換HELLO分組更新,其格式如圖1所示。

圖1 節點信息分組格式

相關變量參數定義如下:

(1)節點ID:發送HELLO分組節點的ID號。

(2)節點坐標:節點坐標用(x,y)表示,x為經度,y為緯度。

(3)節點速度:用矢量表示節點速度,vx和vy分別表示節點在x軸和y軸方向速度分量。

(4)HELLO分組發送時間:節點發送HELLO分組的時間戳,用以估算表中節點當前位置。

DBMSB定義了2種分組HELLO分組和BDP分組,其中,HELLO分組為節點信息交換分組,各節點周期性交換HELLO更新節點信息表,其數據類型和節點信息表相同。BDP分組為廣播數據分組。

BDP分組攜帶廣播數據內容和廣播控制信息,其格式如圖2所示。

圖2 廣播數據分組格式

相關變量參數定義如下:

(1)類型:用以標識數據分組類型,節點對不同的數據分組將采用不同的處理方式。

(2)廣播分組ID:用以唯一標識廣播分組。

(3)廣播發送節點 ID:該項為廣播轉發節點的ID。

(4)生存距離:每條廣播消息有其影響區域,由應用層指定,每次轉發時后將減去轉發節點與上一跳轉發節點距離,當生存距離為0時說明已經超出消息影響區域,丟棄BDP分組。

(5)最優轉發節點ID:該ID節點轉發優先級最高,接收到上一跳轉發節點BDP分組后立即轉發。

(6)候選轉發節點1ID:該ID節點比最優轉發節點多一個轉發延時,當最優轉發節點未能轉發BDP分組時延時超時后將嘗試轉發BDP分組。

(7)候選轉發節點2ID:該ID節點比候選轉發節點1多一個轉發延時,當候選轉發節點1未能轉發BDP分組時延時超時后將嘗試轉發BDP分組。

(8)傳播道路標志位:用以限定BDP分組傳播道路,取值為0,1,進行取反操作后則表示允許在相反車道中轉發。

(9)暫存節點ID:與其值相同的節點可以暫時保存BDP分組。

(10)廣播數據:包含廣播消息實際內容。

LRSP分組為鏈路恢復應答分組用于在路由恢復中確認BDP分組正確接收,其格式如圖3所示。

圖3 鏈路恢復應答分組格式

相關變量參數定義:

(1)廣播包ID:該ID為反向車輛暫存廣播包的ID。

(2)發送者ID:用以標識LRSP分組發送者。

2.2 協議設計思想

由于高速公路道路寬度小于節點信號覆蓋半徑,某輛車接收到廣播消息則與其并行行駛的車輛也能接收到廣播消息。如圖4所示,為了便于表述,規定由東往西行駛車輛為正向行駛車輛,由西往東行駛車輛為反向車輛。

圖4 廣播域示意圖

當某位置發生事故時,正駛向事故地點一定距離內的車輛將受事故影響,需要通過廣播提前告知這些車輛前方路況信息,而反向車道車輛和正向車輛正在駛離事故地點的車輛不受事故影響,因此,在廣播消息轉發具有方向性和區域限制性。為了減少廣播轉發次數,每次轉發所覆蓋的新節點需盡可能多,本協議從車輛節點地理位置分布出發,選擇距離廣播上游節點地理位置最遠且在上游廣播節點信號覆蓋范圍內節點作為下一跳轉發節點,由于廣播節點信號邊緣處節點可能無法正確接收廣播消息,選擇2個備選轉發節點,當最優轉發節點未能成功轉發廣播消息時,備選轉發節點將替代最優轉發節點轉發廣播消息。考慮到同向行駛的車輛存在稀疏的情況,廣播消息在到達某一節點后無法找到下一跳轉發者時將借助于反向車輛存儲轉發廣播消息恢復路由。

2.3 廣播轉發節點以及轉發等待時延的選定

DBSMB協議由某跳轉發節點確定其下一跳最優轉發節點和2個備選轉發節點,其過程如下:

根據節點信息表中節點位置坐標、速度向量和HELLO發送時間利用式(1)計算出當前各節點實際坐標。

其中,xcurr(i)和ycurr(i)為節點i當前坐標估算值;xprev(i)和yprev(i)為節點i在節點信息表中的坐標;vx(i)和vy(i)分別為節點i速度在坐標軸x軸方向和y軸方向速度分量;tcurr為當前進行計算時系統時間;tsnd(i)為HELLO分組發送時間。

為了使DBMSB協議在節點密度飽和的條件下

進一步抑制轉發,并使轉發節點盡力向源節點的覆蓋區域邊緣集中。在交通阻塞的節點密集場景下進一步減少參與轉發的節點數量,設計概率計算公式:

其中,Pi表示節點i轉發概率;Lij表示從接收節點i到上一跳的發送節點j之間的距離;R表示節點的平均傳輸距離;n表示冪參數。

當n=0時,此方法等同于泛洪;當n≥1時,轉發節點數會進一步減少,而且轉發節點會繼續向傳輸的邊緣集中,n越大,轉發節點的數量就越少且向上一跳節點覆蓋區域邊緣集中的趨勢就越明顯,冪參數值可根據具體情況進行調節。由式(2)可以看出,接收節點與發送節點間的距離越遠,其轉發概率越大,而且這種趨勢會隨冪參數n值的增加而增大。

當Pi＞1/2時,則選擇節點i為下一跳節點,否則按照上述方式重新查找、計算。

當前節點位置信息可以計算出廣播轉發節點到其他節點距離,選擇廣播傳播方向距離當前廣播節點最大的節點為最優轉發節點,其Index=0,距離次大的節點為備選廣播節點1,其Index=1,最優轉發節點和當前廣播節點連線中點位置的節點為備選廣播節點2,其Index=2,上一跳轉發節點Index=3。

接收到廣播分組的節點其轉發等待延時由式(3)確定:

其中,waittime(i)為節點i轉發等待時延;Index(i)為廣播數據分組BDP中記錄的候選節點索引值;τ為信號傳播時延發送時延。

2.4 協議執行過程

所有節點以t1為周期發送HELLO分組,所有接收到HELLO分組的節點更新節點信息表的數據,下面分別說明協議在車輛密集和車輛稀疏2種情況下的轉發策略:

(1)廣播傳播方向相鄰車輛均在通信范圍內,如圖5所示。

圖5 車輛完全連通分布

V1為當前將要進行轉發節點。節點V1遍歷NSD表,利用2.3節所述方法計算出1個最優轉發節點和2個備選轉發節點,更新BDP分組廣播控制信息部分,監聽信道t1時間,如果信道空閑則進行轉發。如果NSD表中不存在等待廣播消息的節點則按照策略(2)進行路由恢復。當節點V1轉發BDP分組后,各節點進行如下操作:

V1監聽信道waittime時間,如果接收到相同ID的BDP分組且其上一跳轉發節點ID與自身相同則取消重傳,否則使用二進制指數退避算法重傳BDP分組。非轉發節點監聽信道,如果接收到BDP分組,則提取允許轉發ID信息,如果與本節點ID相同,則該節點成為新的轉發節點等待waittime時間后進行轉發。

某備選轉發節點在waittime時間內接收到對相同ID廣播信息則取消對該消息的轉發。

(2)廣播傳播方向存在兩節點間距離超過節點最大通信半徑R導致將車輛節點分割成2個不連通的區域,如圖6所示。

圖6 車輛鏈路斷開示意圖

當節點V3進行轉發時在NSD表中無法找到合適的下一跳轉發節點時,則遍歷NOD表,利用式(1)計算出NOD表中各節點當前位置,選擇正在駛向節點V3且距離V3最遠的節點作為消息攜帶節點,如圖中Vw,V3更新BDP分組廣播控制部分信息,將允許轉發節點修改為Vw,將傳播車道標志位取反,偵聽信道t1時間,如果信道空閑則進行轉發。Vw接收到BDP分組后發送LRSP分組,表明已有反向車輛成功攜帶BDP分組,V3接收到LRSP分組后取消重傳。Vw檢查NOD表,如果存在正向行駛車輛,其在廣播傳播方向并且位置比上一跳轉發節點更遠則更新BDP分組,進行轉發,正向車輛接收到BDP分組后回復LRSP分組,鏈路恢復完成。

分組轉發和路由恢復過程的偽代碼如下:

算法1分組轉發算法

算法2路由恢復算法

3 協議性能分析

如果BDP分組指定的最優轉發節點未能成功轉發廣播消息,存在以下2種可能:

(1)在BDP分組發送時最優轉發節點已經離開當前廣播節點信號覆蓋范圍。由于備選轉發節點1和最優轉發節點距離相近,近似認為通過備選轉發節點1轉發時上一跳轉發覆蓋節點數和通過最優轉發節點轉發覆蓋節點數相同,假定最優轉發節點和備選轉發節點脫離上游廣播節點信號覆蓋范圍概率相同,則由于原因(1)導致的轉發失敗概率將降低3/4。

(2)由于隱蔽站信號碰撞。越接近上一跳廣播節點的節點,其進行轉發時受到隱蔽站的影響越小,但是選擇靠近上一跳轉發節點的節點作為新的轉發節點單次轉發覆蓋的新節點數比較少,為了平衡降低隱蔽站沖突和增大單次轉發覆蓋新節點數,將上一跳轉發節點信號半徑中點處的節點作為一個備選轉發節點。為簡化證明,在這里說明車流量密度最大情況下成功轉發的概率。

假定場景為單車道,車輛處于一種最密集的狀態,每R范圍存在N個節點等距離分布,每個節點以概率p隨機發送數據分組,某節點發送數據時,其通信范圍內的節點能偵聽到數據發送而取消發送數據,上一跳通信半徑中點處的節點其能否成功轉發只受隱蔽站影響。

如圖7所示,節點A為上一跳轉發節點,節點C為A通信范圍邊緣節點,節點B為A-C中點處節點,則影響C的隱蔽站有個,C點成功轉發概率為:

而B點成功轉發概率為:

相對于基于最大距離的轉發協議,由于原因(2)導致的發送失敗概率將降低

圖7 隱蔽站沖突示意圖

4 仿真與結果分析

4.1 仿真實驗

如上文所述,DBSMB協議能適應節點密集和節點稀疏的網絡,在節點密集區域能抑制廣播風暴,減少轉發次數,在節點稀疏區域能夠盡可能送達廣播消息。本文使用NS2對該協議在不同密度下的性能進行檢驗。其中目標廣播區域為一條長5 km,寬50 m的雙向4車道長直公路,取節點數為100,200, 300,400,500,1 000,1 500,2 000,2 500,3 000是根據文獻[8]所述交通阻塞狀態下每車道每公里有133輛車確定。仿真MAC層采用802.11p協議,單跳最遠通信半徑為500 m,傳輸速率為1 Mb/s,每個節點的運動速度在80 m/s～120 m/s隨機選擇,節點隨機分布于廣播區域內并且每個節點以0.01概率隨機發送數據。

仿真實驗將從以下3個方面對比本協議與簡單泛洪廣播協議和SCB協議的性能。

(1)平均端到端時延(Average End to End Delay,AEED):指從包生成到其下一跳節點成功轉發所經歷的時間平均值,其中反向車輛成功暫存廣播數據包視為成功轉發,其時間由轉發延時waittime和二進制指數退避算法確定。

(2)轉發比率(Forwarding Ratio,FR):指廣播中參與轉發的節點占總節點數的比率。該性能反映廣播協議執行效率,在成功轉發的前提下,轉發比越低轉發效率越高。

(3)負載(Load):指單位時間內網絡的平均數據流量,完成一次廣播轉發產生的數據流量越少,其效率越高。

4.2 結果分析

端到端時延是衡量協議通信實時性的一個主要性能指標,能夠反應通信協議的實際應用效果。圖8對比了簡單泛洪廣播協議、SCB協議和本協議平均端到端時延,在節點數較少時簡單泛洪廣播協議時延比 DBMSB協議和 SCB協議大,由第 3節原因(1)導致的轉發失敗使得SCB協議的平均端到端時延略大于本協議,在節點較為密集時由第3節原因(2)導致的發送失敗使得簡單泛洪廣播協議和SCB廣播協議時延較大。DBMSB協議的時延在不同的密度下變化較小,其主要時延由轉發不成功造成重傳、進行轉發節點選擇時的詢問、聲明等待過程的時間構成,由于有效避免了“廣播風暴”引起的沖突,其在競爭信道時用于退避重傳的時間很少,因此其時延受密度增長的影響不大。適用于交通密度不斷變化的VANET廣播場景。

圖8 平均端到端時延比較

圖9對比了簡單泛洪廣播協議、SCB協議和本協議轉發率。在能夠滿足覆蓋率要求的前提下,參與轉發的節點越少,即轉發比率越小,則協議的執行效率越高。泛洪協議的每個節點都參與轉發,所以其轉發比率接近100%。SCB協議并非每個節點都參與轉發,因而轉發比率并不高。DBMSB協議進行廣播時其參與轉發的節點個數在各個密度度條件下變化不大,在每一跳中其轉發節點一般為離上一跳節點距離遠的節點,所以,參與轉發的節點數量由傳輸距離和廣播目標范圍決定,由于密度增大,在特定范圍內的節點數增加,因此其轉發比率隨密度增加而遞減。在節點密度較大時由于DBSMB協議采用多候選轉發節點機制,其性能相對于簡單泛洪廣播協議和SCB協議有所提升。

圖9 轉發率比較

圖10對比了簡單泛洪廣播協議、SCB協議和本協議負載。泛洪協議的特點決定了其負載會隨節點的增加而增大,泛洪協議的負載與網絡密度成正比,在特定的廣播區域內,密度大時其網絡負載也大,因為在泛洪廣播中每個收到廣播數據的節點都要進行轉發,而通信節點過多產生的沖突與競爭會引發更多的重傳。SCB協議的網絡負載上升不大,只有泛洪協議的20%左右。DBMSB協議的負載在各種車輛密度也都遠低于泛洪協議,且比SCB協議的網絡負載要小,其負載隨密度增長緩慢,僅為泛洪通信在同密度下負載的 10%左右,其原因在于采用DBMSB協議進行數據廣播能夠有效避免大量轉發時產生的沖突。從圖中可以看出DBSMB協議轉發數據分組時占用網絡資源較少。隨著節點密度增大,其負載上升較為平穩,能抑制廣播風暴。

圖10 負載比較

5 結束語

本文提出一種基于距離的多轉發節點廣播協議,在進行廣播數據轉發時選擇多個轉發節點以減少轉發失敗情況下的等待延時,并且通過反向車輛存儲轉發廣播分組,解決正向車道鏈路斷開使信息不可達問題。仿真結果表明,該協議能滿足不同交通流密度情況下緊急信息的分發要求,降低分組投遞的平均端到端延時和分組轉發次數。下一步將研究不同交通流密度情況下多轉發節點的選擇方法,以提高分組投遞成功率。

[1] Sou S,Tonguz O K.A-ADHOC:An Adaptive Real-time Distributed MAC ProtocolforVehicularAd Hoc Networks[J].Mobile Networks&Applications,2011, 16(5):576-585.

[2] 周連科.基于交通流密度的 VANET廣播技術研究[D].哈爾濱:哈爾濱工業大學,2011.

[3] Fan C W,Su K C,Wu H M,et.al.An Effective Multihop Broadcast Control Mechanism for Emergency Alert Message in VANET[C]//Proceedings of the 12th International Conference on ITS Telecommunications. Taipei,China:[s.n.],2012:791-795.

[4] Slavik M,Mahgoub I,Alwakeel M M.Analysis and Evaluation of Distance-to-mean Broadcast Method for VANET[J].Journal of King Saud University:Computer and Information Sciences,2014,10(26):153-160.

[5] Song Fang,Tao Luo.A Novel Two-timer-based BroadcastRouting Algorithm for Vehicular Ad-hoc Networks[C]//Proceedings of GreenCom’13,iThings/ CPSCom’13,IEEE International Conference on and IEEE Cyber,Physical and Social Computing.Beijing, China:IEEE Press,2013:1518-1522.

[6] Sou S I,Lee Y.SCB:Store-Carry-Broadcast Scheme for MessageDisseminationinSparseVANET[C]// Proceedings of Vehicular Technology Conference. Yokohama,Japan:[s.n.],2012:1-5.

[7] 蔣建國,蘇兆品,張國富,等.多任務聯盟形成中的Agent行為策略研究[J].控制理論與應用,2008, 25(5):853-856.

[8] Sou S I,Tonguz O K.Enhancing VANET Connectivity Through Roadside Unitson Highways[J].IEEE Transactions on Vehicular Technology,2011,60(8): 3586-3602.

[9] 劉 業,吳國新.基于802.11p/WAVE的車聯網連通性模型及其應用研究[J].通信學報,2013,34(6): 85-91.

[10] 任 剛,劉曉慶,顧 程.基于起訖點的均衡交通分配改進算法[J].系統工程理論與實踐,2012,32(10): 2315-2322.

[11] Williams B,Tracy C.Comparison ofBroadcasting Techniques forMobileAd HocNetworks[C]// Proceedings of MOBIHOC’02.Lausance,Switzerland: ACM Press,2002:194-205.

[12] 常促宇,向 勇,史美林.車載自組網的現狀與發展[J].通信學報,2007,28(11):116-126.

[13] 趙 海,彭海霞,朱 劍,等.基于組確認機制的車聯網中最佳中繼節點的選擇[J].東北大學學報:自然科學版,2013,34(1):35-39.

[14] 韓江洪,楊 帆,劉征宇,等.路基設備輔助下的高速公路車輛信息方向性傳輸協議[J].電信科學,2013,(1): 57-62.

編輯 金胡考

Multi Senders Broadcast Protocol Based on Distance in Internet of Vehicles

HAN Jianghong1,2,LI Chao1,WEI Xing1,2,WEI Zhenchun1,2
(1.School of Computer and Information,Hefei University of Technology,Hefei 230009,China; 2.Engineering Research Center of Safety Critical Industry Measure and Control Technology of Ministry of Education,Hefei 230009,China)

In order to make safety messages broadcast fast and efficiently in Vehicular Ad-hoc Network(VANET),this paper proposes a multi senders broadcast protocol based on distance(DMSBM).In order to cover the most new nodes, DBMSB protocol selects the signal coverage bounder node of pre-node as the best forwarding node,and selects the midpoint node of the signal coverage and the secondary node close to the edge point as alternative forwarding node to avoid forwarding failure rate caused by hidden stations and nodes out of the signal coverage.It also uses the reverse vehicle to store and forward broadcast packet to restore routing.Simulation results show that this protocol can adapt to VANET with a variety of vehicle density,and it can also meet the distribution of emergency information under various traffic densities.It can reduce the average end to end delay and enhance the forwarding efficiency.Routing load rises slowly in this protocol,which can effectively inhibit broadcasting storm.

Vehicular Ad-hoc Network(VANET);broadcast protocol;store and forward;multiple forward;confliction of hidden station;routing restoration

1000-3428(2015)01-0006-06

A

TP393

10.3969/j.issn.1000-3428.2015.01.002

國家自然科學基金資助面上項目(61370088);高等學校博士學科點專項科研基金資助項目(20100111110004);安徽省自然科學基金資助項目(1208085QF113)。

韓江洪(1954-),男,教授、博士生導師,主研方向:分布式控制,車聯網;李 超,碩士研究生;衛 星,講師;魏振春,副教授。

2014-02-19

2014-03-26 E-mail:lchao1990@126.com

中文引用格式:韓江洪,李 超,衛 星,等.車聯網中基于距離的多轉發者廣播協議[J].計算機工程,2015,41(1):6-11.

英文引用格式:Han Jianghong,Li Chao,Wei Xing,et al.Multi Senders Broadcast Protocol Based on Distance in Internet of Vehicles[J].Computer Engineering,2015,41(1):6-11.