車聯(lián)網(wǎng)中基于距離的多轉(zhuǎn)發(fā)者廣播協(xié)議

韓江洪,李 超,衛(wèi) 星,魏振春

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

進一步抑制轉(zhuǎn)發(fā),并使轉(zhuǎn)發(fā)節(jié)點盡力向源節(jié)點的覆蓋區(qū)域邊緣集中。在交通阻塞的節(jié)點密集場景下進一步減少參與轉(zhuǎn)發(fā)的節(jié)點數(shù)量,設(shè)計概率計算公式:

車聯(lián)網(wǎng)中基于距離的多轉(zhuǎn)發(fā)者廣播協(xié)議

韓江洪1,2,李 超1,衛(wèi) 星1,2,魏振春1,2

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

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

車載自組織網(wǎng)絡(luò);廣播協(xié)議;存儲轉(zhuǎn)發(fā);多轉(zhuǎn)發(fā);隱蔽站沖突;路由恢復(fù)

1 概述

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

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

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

2 DBMSB協(xié)議

2.1 DBMSB協(xié)議相關(guān)定義

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

圖1 節(jié)點信息分組格式

相關(guān)變量參數(shù)定義如下:

(1)節(jié)點ID:發(fā)送HELLO分組節(jié)點的ID號。

(2)節(jié)點坐標:節(jié)點坐標用(x,y)表示,x為經(jīng)度,y為緯度。

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

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

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

BDP分組攜帶廣播數(shù)據(jù)內(nèi)容和廣播控制信息,其格式如圖2所示。

圖2 廣播數(shù)據(jù)分組格式

相關(guān)變量參數(shù)定義如下:

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

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

(3)廣播發(fā)送節(jié)點 ID:該項為廣播轉(zhuǎn)發(fā)節(jié)點的ID。

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

(5)最優(yōu)轉(zhuǎn)發(fā)節(jié)點ID:該ID節(jié)點轉(zhuǎn)發(fā)優(yōu)先級最高,接收到上一跳轉(zhuǎn)發(fā)節(jié)點BDP分組后立即轉(zhuǎn)發(fā)。

(6)候選轉(zhuǎn)發(fā)節(jié)點1ID:該ID節(jié)點比最優(yōu)轉(zhuǎn)發(fā)節(jié)點多一個轉(zhuǎn)發(fā)延時,當最優(yōu)轉(zhuǎn)發(fā)節(jié)點未能轉(zhuǎn)發(fā)BDP分組時延時超時后將嘗試轉(zhuǎn)發(fā)BDP分組。

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

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

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

(10)廣播數(shù)據(jù):包含廣播消息實際內(nèi)容。

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

圖3 鏈路恢復(fù)應(yīng)答分組格式

相關(guān)變量參數(shù)定義:

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

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

2.2 協(xié)議設(shè)計思想

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

圖4 廣播域示意圖

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

2.3 廣播轉(zhuǎn)發(fā)節(jié)點以及轉(zhuǎn)發(fā)等待時延的選定

DBSMB協(xié)議由某跳轉(zhuǎn)發(fā)節(jié)點確定其下一跳最優(yōu)轉(zhuǎn)發(fā)節(jié)點和2個備選轉(zhuǎn)發(fā)節(jié)點,其過程如下:

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

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

為了使DBMSB協(xié)議在節(jié)點密度飽和的條件下

進一步抑制轉(zhuǎn)發(fā),并使轉(zhuǎn)發(fā)節(jié)點盡力向源節(jié)點的覆蓋區(qū)域邊緣集中。在交通阻塞的節(jié)點密集場景下進一步減少參與轉(zhuǎn)發(fā)的節(jié)點數(shù)量,設(shè)計概率計算公式:

其中,Pi表示節(jié)點i轉(zhuǎn)發(fā)概率;Lij表示從接收節(jié)點i到上一跳的發(fā)送節(jié)點j之間的距離;R表示節(jié)點的平均傳輸距離;n表示冪參數(shù)。

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

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

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

接收到廣播分組的節(jié)點其轉(zhuǎn)發(fā)等待延時由式(3)確定:

其中,waittime(i)為節(jié)點i轉(zhuǎn)發(fā)等待時延;Index(i)為廣播數(shù)據(jù)分組BDP中記錄的候選節(jié)點索引值;τ為信號傳播時延發(fā)送時延。

2.4 協(xié)議執(zhí)行過程

所有節(jié)點以t1為周期發(fā)送HELLO分組,所有接收到HELLO分組的節(jié)點更新節(jié)點信息表的數(shù)據(jù),下面分別說明協(xié)議在車輛密集和車輛稀疏2種情況下的轉(zhuǎn)發(fā)策略:

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

圖5 車輛完全連通分布

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

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

某備選轉(zhuǎn)發(fā)節(jié)點在waittime時間內(nèi)接收到對相同ID廣播信息則取消對該消息的轉(zhuǎn)發(fā)。

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

圖6 車輛鏈路斷開示意圖

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

分組轉(zhuǎn)發(fā)和路由恢復(fù)過程的偽代碼如下:

算法1分組轉(zhuǎn)發(fā)算法

算法2路由恢復(fù)算法

3 協(xié)議性能分析

如果BDP分組指定的最優(yōu)轉(zhuǎn)發(fā)節(jié)點未能成功轉(zhuǎn)發(fā)廣播消息,存在以下2種可能:

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

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

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

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

而B點成功轉(zhuǎn)發(fā)概率為:

相對于基于最大距離的轉(zhuǎn)發(fā)協(xié)議,由于原因(2)導(dǎo)致的發(fā)送失敗概率將降低

圖7 隱蔽站沖突示意圖

4 仿真與結(jié)果分析

4.1 仿真實驗

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

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

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

(2)轉(zhuǎn)發(fā)比率(Forwarding Ratio,FR):指廣播中參與轉(zhuǎn)發(fā)的節(jié)點占總節(jié)點數(shù)的比率。該性能反映廣播協(xié)議執(zhí)行效率,在成功轉(zhuǎn)發(fā)的前提下,轉(zhuǎn)發(fā)比越低轉(zhuǎn)發(fā)效率越高。

(3)負載(Load):指單位時間內(nèi)網(wǎng)絡(luò)的平均數(shù)據(jù)流量,完成一次廣播轉(zhuǎn)發(fā)產(chǎn)生的數(shù)據(jù)流量越少,其效率越高。

4.2 結(jié)果分析

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

圖8 平均端到端時延比較

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

圖9 轉(zhuǎn)發(fā)率比較

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

圖10 負載比較

5 結(jié)束語

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

[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廣播技術(shù)研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),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] 蔣建國,蘇兆品,張國富,等.多任務(wù)聯(lián)盟形成中的Agent行為策略研究[J].控制理論與應(yīng)用,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] 劉 業(yè),吳國新.基于802.11p/WAVE的車聯(lián)網(wǎng)連通性模型及其應(yīng)用研究[J].通信學(xué)報,2013,34(6): 85-91.

[10] 任 剛,劉曉慶,顧 程.基于起訖點的均衡交通分配改進算法[J].系統(tǒng)工程理論與實踐,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] 常促宇,向 勇,史美林.車載自組網(wǎng)的現(xiàn)狀與發(fā)展[J].通信學(xué)報,2007,28(11):116-126.

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

[14] 韓江洪,楊 帆,劉征宇,等.路基設(shè)備輔助下的高速公路車輛信息方向性傳輸協(xié)議[J].電信科學(xué),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

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

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

2014-02-19

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

中文引用格式:韓江洪,李 超,衛(wèi) 星,等.車聯(lián)網(wǎng)中基于距離的多轉(zhuǎn)發(fā)者廣播協(xié)議[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.