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

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

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

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

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

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

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

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

1 概述

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

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

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

2 DBMSB協(xié)議

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

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

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

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

(1)節(jié)點(diǎn)ID:發(fā)送HELLO分組節(jié)點(diǎn)的ID號(hào)。

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

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

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

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

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

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

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

(1)類型:用以標(biāo)識(shí)數(shù)據(jù)分組類型,節(jié)點(diǎn)對(duì)不同的數(shù)據(jù)分組將采用不同的處理方式。

(2)廣播分組ID:用以唯一標(biāo)識(shí)廣播分組。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 廣播域示意圖

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

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

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

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

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

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

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

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

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

當(dāng)Pi＞1/2時(shí),則選擇節(jié)點(diǎn)i為下一跳節(jié)點(diǎn),否則按照上述方式重新查找、計(jì)算。

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

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

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

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

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

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

圖5 車輛完全連通分布

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

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

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

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

圖6 車輛鏈路斷開示意圖

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

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

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

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

3 協(xié)議性能分析

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

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

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

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

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

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

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

圖7 隱蔽站沖突示意圖

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

4.1 仿真實(shí)驗(yàn)

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

仿真實(shí)驗(yàn)將從以下3個(gè)方面對(duì)比本協(xié)議與簡(jiǎn)單泛洪廣播協(xié)議和SCB協(xié)議的性能。

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

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

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

4.2 結(jié)果分析

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

圖8 平均端到端時(shí)延比較

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

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

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

圖10 負(fù)載比較

5 結(jié)束語(yǔ)

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

[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] 蔣建國(guó),蘇兆品,張國(guó)富,等.多任務(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è),吳國(guó)新.基于802.11p/WAVE的車聯(lián)網(wǎng)連通性模型及其應(yīng)用研究[J].通信學(xué)報(bào),2013,34(6): 85-91.

[10] 任 剛,劉曉慶,顧 程.基于起訖點(diǎn)的均衡交通分配改進(jìn)算法[J].系統(tǒng)工程理論與實(shí)踐,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é)報(bào),2007,28(11):116-126.

[13] 趙 海,彭海霞,朱 劍,等.基于組確認(rèn)機(jī)制的車聯(lián)網(wǎng)中最佳中繼節(jié)點(diǎn)的選擇[J].東北大學(xué)學(xué)報(bào):自然科學(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

國(guó)家自然科學(xué)基金資助面上項(xiàng)目(61370088);高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20100111110004);安徽省自然科學(xué)基金資助項(xiàng)目(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].計(jì)算機(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.