面向城市VANETs的多跳警告廣播協(xié)議

王秀峰，王春萌，崔 剛

（哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，150001哈爾濱）

面向城市VANETs的多跳警告廣播協(xié)議

王秀峰，王春萌，崔 剛

（哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，150001哈爾濱）

為改善道路交叉口處信息向所有方向分發(fā)的可靠性以及降低信息分發(fā)時(shí)延，提出面向城市車(chē)載網(wǎng)絡(luò)多種交通密度、基于位置的多跳警告廣播協(xié)議MBW.本協(xié)議把無(wú)線信號(hào)一次發(fā)射覆蓋的道路分為東、南、西、北4個(gè)方向.道路交叉路口的中繼節(jié)點(diǎn)滿足兩個(gè)條件：首先，一個(gè)節(jié)點(diǎn)至少有兩個(gè)鄰居節(jié)點(diǎn)，該節(jié)點(diǎn)及鄰居的行駛方向都不同，并且與鄰居節(jié)點(diǎn)之間的距離都大于路寬；其次，ID號(hào)在交叉口的節(jié)點(diǎn)中最小，交叉路口處中繼節(jié)點(diǎn)優(yōu)先廣播信息不等待.道路上的中繼節(jié)點(diǎn)根據(jù)WT公式確定，WT值為零時(shí)轉(zhuǎn)發(fā)信息，并定義此節(jié)點(diǎn)為中繼節(jié)點(diǎn)，本協(xié)議支持信息在路上雙向傳輸.MBW協(xié)議的中繼節(jié)點(diǎn)選擇策略能夠減少中繼節(jié)點(diǎn)個(gè)數(shù)和信息分發(fā)冗余.仿真結(jié)果表明MBW協(xié)議和現(xiàn)存的VANETs廣播協(xié)議相比具有較好的高覆蓋率、低延遲、低轉(zhuǎn)發(fā)節(jié)點(diǎn)率和較低的網(wǎng)絡(luò)開(kāi)銷(xiāo).

車(chē)載網(wǎng)絡(luò)；基于位置的廣播；數(shù)據(jù)分發(fā)；多種交通密度

由于車(chē)載無(wú)線網(wǎng)絡(luò)VANETs（vehicular ad hoc networks）中多跳廣播經(jīng)常受到廣播風(fēng)暴的影響［1］，而移動(dòng)自組網(wǎng)MANETs（mobile ad hoc network）中減輕廣播風(fēng)暴方法不能直接用于VANETs［2-5］.目前研究學(xué)者針對(duì)VAENTs的特點(diǎn)提出幾種抑制廣播風(fēng)暴機(jī)制，例如，基于概率的廣播、基于計(jì)數(shù)的廣播、基于距離的廣播、鄰居知識(shí)廣播和基于位置的廣播［6］.在基于位置的機(jī)制中，距離最遠(yuǎn)的節(jié)點(diǎn)被選作中繼節(jié)點(diǎn)，每一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇是確定的和唯一的，因此基于位置的廣播冗余和延遲相對(duì)較低.當(dāng)前基于位置的城市VANETs廣播方法中，大多數(shù)假設(shè)車(chē)輛在直行的公路上行駛，而實(shí)際的城市場(chǎng)景有交叉路口和建筑物，交通密度是變化的.文獻(xiàn)［7-9］中提出面向感興趣區(qū)域ROI（region of interesting）信息分發(fā)，這種面向區(qū)域的信息分發(fā)考慮交叉口，但是網(wǎng)絡(luò)開(kāi)銷(xiāo)大，因此為限制信息冗余、降低網(wǎng)絡(luò)開(kāi)銷(xiāo)和鏈路時(shí)延，本文提出城市多跳警告廣播MBW（multi-hop broadcast for warning）協(xié)議.本協(xié)議充分考慮實(shí)際城市場(chǎng)景中道路交叉口處的交通信號(hào)和建筑物阻擋. MBW目的是通知從所有方向即將到來(lái)的汽車(chē)調(diào)整行車(chē)路線避免碰撞.本文以中繼節(jié)點(diǎn)為圓心建立直角坐標(biāo)系，把無(wú)線信號(hào)一次發(fā)射覆蓋的道路分為東、南、西和北4個(gè)方向.如果一個(gè)節(jié)點(diǎn)有兩個(gè)以上的鄰居節(jié)點(diǎn)，該節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的行駛方向都不同，并且ID號(hào)在交叉口的節(jié)點(diǎn)中最小，則該節(jié)點(diǎn)被定義為交叉口的中繼節(jié)點(diǎn).交叉口處的中繼節(jié)點(diǎn)優(yōu)先轉(zhuǎn)發(fā)信息不等待.道路上的中繼節(jié)點(diǎn)由WT公式?jīng)Q定，公式由接收節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率因子決定.WT結(jié)束時(shí)，中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)信息，該節(jié)點(diǎn)被選作中繼節(jié)點(diǎn).MBW支持?jǐn)?shù)據(jù)信息沿著道路雙向轉(zhuǎn)發(fā).

1 相關(guān)工作

廣播是VANETs信息分發(fā)的核心技術(shù).盲目的廣播會(huì)遭遇冗余重傳，尤其在密集型網(wǎng)絡(luò)中，目前已有很多基于位置的廣播方案，而相當(dāng)多的方法是針對(duì)直行公路的場(chǎng)景而不考慮交叉口信息分發(fā)設(shè)計(jì)［6，10-12］.

文獻(xiàn)［6］提出基于位置的多跳廣播PMB（position-based multi-hop broadcast）方法，降低信息重傳冗余并且改善信息傳輸?shù)膶?shí)時(shí)性.文獻(xiàn)［10］提出基于位置自適應(yīng)的廣播協(xié)議PAB（position-based adaptive broadcast），該協(xié)議考慮發(fā)送者和接收者之間的距離、汽車(chē)速度和角度.采用對(duì)向行駛的汽車(chē)作為中繼節(jié)點(diǎn)，并沒(méi)有給出信道占用多久.

文獻(xiàn)［11］提出基于相對(duì)位置的廣播協(xié)議RPB（the relative position based message dissemination），不采用基礎(chǔ)設(shè)施，減少硬件開(kāi)銷(xiāo).采用定向貪婪廣播路由方式轉(zhuǎn)發(fā)信息，由于采用ACK機(jī)制，網(wǎng)絡(luò)開(kāi)銷(xiāo)大.文獻(xiàn)［12］針對(duì)緊急事故提出一種基于位置的多跳廣播模型PMBP（a position based multi-hop broadcast protocol），PMBP每一跳選擇發(fā)送方向上距源節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)轉(zhuǎn)發(fā)信息，并且使用BRTS／BCTS握手機(jī)制.文獻(xiàn)［13-14］提出交叉口信息轉(zhuǎn)發(fā)的廣播機(jī)制，但是增加硬件開(kāi)銷(xiāo).

在城市廣播協(xié)議UMB（urban multi-hop broadcast protocol）中使用RTB／CTB廣播機(jī)制［13，15］，并且通過(guò)廣播節(jié)點(diǎn)和中繼節(jié)點(diǎn)之間的ACK機(jī)制增強(qiáng)廣播的可靠性，規(guī)定點(diǎn)對(duì)點(diǎn)通信只是在廣播節(jié)點(diǎn)和最遠(yuǎn)節(jié)點(diǎn)之間進(jìn)行，其它節(jié)點(diǎn)只接收信息，根據(jù)接收節(jié)點(diǎn)和廣播節(jié)點(diǎn)之間的距離設(shè)立信道占用時(shí)間.距離廣播節(jié)點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)占用信道時(shí)間較長(zhǎng)，所以距離較遠(yuǎn)的節(jié)點(diǎn)將被選作中繼節(jié)點(diǎn)，因此限制中繼節(jié)點(diǎn)的個(gè)數(shù)并且抑制信息重傳次數(shù)，減少?gòu)V播風(fēng)暴.在交通流密集型的道路上，通過(guò)RTB／CTB機(jī)制選擇中繼節(jié)點(diǎn)，該協(xié)議不容易收斂，增加網(wǎng)絡(luò)開(kāi)銷(xiāo)和降低網(wǎng)絡(luò)吞吐量.文獻(xiàn)［16］設(shè)置競(jìng)爭(zhēng)窗口，目的是在不同道路上不同的部分信息轉(zhuǎn)發(fā)不會(huì)重疊，確保較遠(yuǎn)的節(jié)點(diǎn)優(yōu)先和廣播節(jié)點(diǎn)握手.文獻(xiàn)［17］指出由于公路的每部分競(jìng)爭(zhēng)窗口重疊，不能保證距離廣播節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)被選作中繼節(jié)點(diǎn)，會(huì)遭遇更多碰撞.文獻(xiàn)［18］使用UMB中的RTB／CTB廣播握手機(jī)制選擇最遠(yuǎn)的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，貞間間隔IFS（interframe space）和距廣播節(jié)點(diǎn)之間的距離成反比，位置越遠(yuǎn)，IFS越短.

文獻(xiàn)［19］提出基于道路的廣播協(xié)議，根據(jù)汽車(chē)所在的道路，按照發(fā)送者和接收者之間的角度給汽車(chē)分組.并選擇每一跳具有最好視線的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，考慮道路交叉口及建筑物阻擋，提高傳輸?shù)目煽啃院陀行?AMB廣播協(xié)議擴(kuò)展UMB廣播協(xié)議并且改善網(wǎng)絡(luò)開(kāi)銷(xiāo)和轉(zhuǎn)發(fā)節(jié)點(diǎn)率［20］.BSM廣播協(xié)議中進(jìn)一步提高AMB協(xié)議的覆蓋率、網(wǎng)絡(luò)開(kāi)銷(xiāo)和轉(zhuǎn)發(fā)節(jié)點(diǎn)率［9］，但是BSM由于不一定能夠選擇到最遠(yuǎn)的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，會(huì)造成網(wǎng)絡(luò)開(kāi)銷(xiāo)大.

2 MBW協(xié)議的詳細(xì)設(shè)計(jì)

MBW廣播協(xié)議的主要目標(biāo)是在事故節(jié)點(diǎn)周?chē)M可能大的區(qū)域內(nèi)，以低延遲、低網(wǎng)絡(luò)開(kāi)銷(xiāo)和低轉(zhuǎn)發(fā)節(jié)點(diǎn)率在多種交通流密度環(huán)境中分發(fā)信息.MBW為了在每一跳中最大化接收警告信息的汽車(chē)數(shù)量，選擇中繼節(jié)點(diǎn)的機(jī)制是很重要的.本文分別給出在交叉口和在道路上兩種不同的選擇中繼節(jié)點(diǎn)方法.

本文為每一個(gè)中繼節(jié)點(diǎn)建立直角坐標(biāo)系，坐標(biāo)系原點(diǎn)為O，見(jiàn)圖1，兩條直線L1和L2把中繼節(jié)點(diǎn)一跳發(fā)射所覆蓋的范圍平均分成4份，每一份角度為．按照逆時(shí)針的方向，角度道路的東、西、南、北4個(gè)方向的定義為：

定義1 ?節(jié)點(diǎn)i，發(fā)送者和接收者之間的角度為φi，如果則節(jié)點(diǎn)i在道路東方．

定義2 ?節(jié)點(diǎn)i，發(fā)送者和接收者之間的角度為φi，如果則節(jié)點(diǎn)i在道路北方．

定義3 ?節(jié)點(diǎn)i，發(fā)送者和接收者之間的角度為φi，如果則節(jié)點(diǎn)i在道路南方．

定義4 ?節(jié)點(diǎn)i，發(fā)送者和接收者之間的角度為φi，如果則節(jié)點(diǎn)i在道路西方．

圖1 道路方向

本文采用MBW-ONE和MBW-TWO兩種方法分別實(shí)現(xiàn)MBW廣播協(xié)議.MBW-TWO采用周期性維護(hù)鄰居列表方法選擇交叉口的中繼節(jié)點(diǎn)，而MBW-ONE則采用緊急事故發(fā)生時(shí)創(chuàng)建鄰居列表及選擇交叉口中繼節(jié)點(diǎn)，MBW-ONE能夠有效地減少網(wǎng)絡(luò)開(kāi)銷(xiāo).二者均采用周期性hello信標(biāo)維護(hù)鄰居列表，hello包里面包含的信息：＜Hello，Position，Direction，Hop，SID，MID，VID＞，Hello代表hello包，Position標(biāo)志汽車(chē)的位置，Direction值為上一個(gè)中繼節(jié)點(diǎn)的方向（東、南、西、北），Hop值為hello包的跳數(shù)，SID代表源節(jié)點(diǎn)ID號(hào)，MID值是源節(jié)點(diǎn)信息ID號(hào)，VID域記錄汽車(chē)ID號(hào).當(dāng)一個(gè)節(jié)點(diǎn)收到hello包并且Hop值為0時(shí)則成對(duì)保存MID和SID. hello信標(biāo)為1 Hz.

MBW-ONE信息轉(zhuǎn)發(fā)策略：

源節(jié)點(diǎn)廣播hello信標(biāo)，其Hop值為0，收到這個(gè)信標(biāo)的節(jié)點(diǎn)廣播hello信標(biāo)并且1s內(nèi)只廣播一次，設(shè)置其Hop值為1，收到這個(gè)信標(biāo)的節(jié)點(diǎn)1s內(nèi)只發(fā)送一次應(yīng)答包，限制hello信標(biāo)和應(yīng)答包的次數(shù)能夠降低網(wǎng)絡(luò)開(kāi)銷(xiāo)，應(yīng)答包里包含Respond域和Position域，收到應(yīng)答包的節(jié)點(diǎn)計(jì)算自己和鄰居節(jié)點(diǎn)的距離，如果該節(jié)點(diǎn)在其東、西、南、北4個(gè)方向的鄰居節(jié)點(diǎn)中至少有兩個(gè)不同的方向有鄰居節(jié)點(diǎn)，該節(jié)點(diǎn)和鄰居節(jié)點(diǎn)的行駛方向不同，并且與它們的距離都大于路寬，則標(biāo)記自己在道路交叉口.并記錄自己VID為最小，否則不做任何事情.

1）一個(gè)Hop值為0的節(jié)點(diǎn)廣播hello包并等待tms后廣播數(shù)據(jù)包，如果交叉口的節(jié)點(diǎn)收到數(shù)據(jù)包，這些節(jié)點(diǎn)廣播Hop值為0的hello包，收到這個(gè)hello包的節(jié)點(diǎn)廣播hello信標(biāo)并標(biāo)記Hop值為1，那些收到這個(gè)hello信標(biāo)的節(jié)點(diǎn)廣播應(yīng)答包，然后帶有VID值最小的節(jié)點(diǎn)立即轉(zhuǎn)發(fā)數(shù)據(jù)包，因此這個(gè)節(jié)點(diǎn)被選作中繼節(jié).

2）如果路上所有的節(jié)點(diǎn)收到Hop值為0的hello信標(biāo)，收到數(shù)據(jù)包的節(jié)點(diǎn)計(jì)算WT后開(kāi)始等待，如果WT沒(méi)有結(jié)束，一個(gè)節(jié)點(diǎn)收到來(lái)自其它節(jié)點(diǎn)并且Hop值為0的hello包，則不廣播Hop值為0的hello包；如果一個(gè)節(jié)點(diǎn)在已經(jīng)發(fā)送Hop值為0的hello包之后收到來(lái)自其它節(jié)點(diǎn)Hop值為0的hello包，比較自己保存的SID、MID和hello包里的這兩個(gè)域值，如果自己的SID和MID和hello包里這兩個(gè)域值不同，表明沒(méi)有收到過(guò)該信息，則廣播Hop值為1的hello包而且1s內(nèi)只能發(fā)一次，然后收到這個(gè)hello信標(biāo)的節(jié)點(diǎn)1s內(nèi)只發(fā)一次應(yīng)答包，收到應(yīng)答包的節(jié)點(diǎn)更新交叉口標(biāo)記.如果一個(gè)節(jié)點(diǎn)收到一個(gè)hello包里的SID、MID值和自己保存的一樣，則比較VID值，如果自己的VID值比其它節(jié)點(diǎn)的VID值大并且Direction值是相同的，則取消轉(zhuǎn)發(fā)數(shù)據(jù).否則轉(zhuǎn)發(fā)數(shù)據(jù)信息.因此轉(zhuǎn)發(fā)節(jié)點(diǎn)被定義為道路上的中繼節(jié)點(diǎn).

3）在源節(jié)點(diǎn)廣播數(shù)據(jù)包之后，MID值加1.

MBW-TWO信息轉(zhuǎn)發(fā)策略：

1）當(dāng)一個(gè)節(jié)點(diǎn)收到Hop值為0的hello信標(biāo)，則更新鄰居列表，計(jì)算自己和鄰居節(jié)點(diǎn)的距離，如果至少有兩個(gè)鄰居節(jié)點(diǎn)和自己的距離大于路寬則標(biāo)記自己在交叉口，并且如果自己的VID值比收到的hello包里的VID小，則標(biāo)記VID最小值，否則不做任何事情.

2）事故發(fā)生時(shí)，源節(jié)點(diǎn)立即廣播數(shù)據(jù)信息，如果交叉口的節(jié)點(diǎn)收到信息，采用節(jié)點(diǎn)ID號(hào)最小的節(jié)點(diǎn)廣播信息，因此該節(jié)點(diǎn)也被選作中繼節(jié)點(diǎn).數(shù)據(jù)包包含信息：＜Data、Position、Direction、TS、SID、MID、Message＞.Data代表數(shù)據(jù)包，Position代表節(jié)點(diǎn)的位置，Direction是相對(duì)于上一個(gè)節(jié)點(diǎn)東、南、西、北4個(gè)方向，TS的值為發(fā)送數(shù)據(jù)包的時(shí)間，SID代表源節(jié)點(diǎn)的ID號(hào)，MID的值為信息的ID號(hào)，Message為告警信息.

3）當(dāng)路上的節(jié)點(diǎn)收到數(shù)據(jù)包，則計(jì)算WT并等待.如果WT沒(méi)有結(jié)束，節(jié)點(diǎn)收到來(lái)自其它節(jié)點(diǎn)的數(shù)據(jù)包并且它們方向域值相同，那么取消轉(zhuǎn)發(fā)信息，因此相對(duì)于源節(jié)點(diǎn)不同方向的節(jié)點(diǎn)還可以轉(zhuǎn)發(fā)信息.當(dāng)WT截止時(shí)，轉(zhuǎn)發(fā)數(shù)據(jù)包，因此，轉(zhuǎn)發(fā)節(jié)點(diǎn)被選作中繼節(jié)點(diǎn).

4）當(dāng)源節(jié)點(diǎn)廣播數(shù)據(jù)包之后，MID域值加1.

這兩個(gè)策略可以用來(lái)同時(shí)轉(zhuǎn)發(fā)不同的信息.

MBW廣播協(xié)議通過(guò)限制中繼節(jié)點(diǎn)的選擇，可減少信息重傳次數(shù).因此能夠減少信息冗余和競(jìng)爭(zhēng)，降低廣播風(fēng)暴的風(fēng)險(xiǎn).

3 WT公式的提出

為了限制重播信息的汽車(chē)數(shù)量，在基于位置廣播協(xié)議中，典型的WT計(jì)算方法是采用一些相關(guān)因素設(shè)計(jì)等待時(shí)間函數(shù)，比如廣播節(jié)點(diǎn)的無(wú)線通信半徑，發(fā)送者和接收者之間的距離，鄰居節(jié)點(diǎn)的數(shù)量和車(chē)速等.文獻(xiàn)［6］提出WT延遲為

式中：Ri和Rj是兩個(gè)節(jié)點(diǎn)的傳輸范圍，dij是節(jié)點(diǎn)i和j之間的距離．從式（1）中看不出明顯的WT和距離之間的關(guān)系，文獻(xiàn)［9］提出過(guò)類(lèi)似的WT函數(shù). BSM廣播協(xié)議提出WT為

式中：dsr是發(fā)送者和接收這之間的距離，nn是鄰居汽車(chē)的數(shù)量，很明顯這樣的表達(dá)式不是線性函數(shù)，文獻(xiàn)［8］提出HyDiAck廣播協(xié)議的WT為

式（4）、（5）表明等待時(shí)間TSij是Dij的線性函數(shù)，Dij是發(fā)送者和接收者之間的距離，NS是為每?jī)蓚€(gè)區(qū)間可提供的時(shí)隙數(shù)，文獻(xiàn)［7］提出UV-CAST協(xié)議給出WT為

式（6）表明τi是di，j的線性函數(shù)，τi為等待時(shí)延，di，j是發(fā)送節(jié)點(diǎn)和中繼節(jié)點(diǎn)之間的距離．基于上述思想可知距離發(fā)送者較遠(yuǎn)的節(jié)點(diǎn)有更大的轉(zhuǎn)發(fā)信息概率，因此基于發(fā)送者和接收者之間距離，本文提出節(jié)點(diǎn)轉(zhuǎn)發(fā)信息的概率表達(dá)式為

式中：Pi為接收者重播信息的概率，di為接收者距發(fā)送者之間的距離，r是無(wú)線通信半徑，如果一個(gè)節(jié)點(diǎn)有較高的轉(zhuǎn)發(fā)概率，那么在轉(zhuǎn)發(fā)信息之前等待的時(shí)間越短．因此，采用Pi概率因子分別建立指數(shù)和線性的WT為

在本研究中WTmax為100ms，如果WTmax太高，時(shí)延將會(huì)增加.如果太低，許多汽車(chē)在收到信息之前會(huì)重播信息.圖2給出式（8）、（9）計(jì)算等待時(shí)延的比較，當(dāng)接收節(jié)點(diǎn)距離發(fā)送節(jié)點(diǎn)越遠(yuǎn)，則等待時(shí)間WT越小，尤其當(dāng)距離＞200m時(shí)，線性的WT函數(shù)和指數(shù)的WT函數(shù)計(jì)算的WT值幾乎相等，但是當(dāng)距離＜200 m時(shí)，則指數(shù)的WT函數(shù)計(jì)算的WT值比線性的小，WT值越小，信息轉(zhuǎn)發(fā)的越早，為信息盡快轉(zhuǎn)發(fā)，本文采用指數(shù)的WT公式.

圖2 指數(shù)和線性的WT曲線

式（8）是計(jì)算路上WT的計(jì)算方法，但是對(duì)于交叉口的中繼節(jié)點(diǎn)，本文規(guī)定收到信息則立即轉(zhuǎn)發(fā)不等待，其它在交叉口的節(jié)點(diǎn)收到信息時(shí)候取消轉(zhuǎn)發(fā).因此，本文把道路上轉(zhuǎn)發(fā)信息計(jì)算WT的方法和道路交叉口轉(zhuǎn)發(fā)信息不等待時(shí)延的方法合并成一個(gè)公式為

4 信息分發(fā)的實(shí)現(xiàn)

為實(shí)現(xiàn)數(shù)據(jù)信息分發(fā)，本文使用信息貼標(biāo)簽技術(shù)［21］.當(dāng)信息發(fā)送時(shí)，象貼標(biāo)簽一樣被貼上源節(jié)點(diǎn)的ID號(hào)、信息的ID號(hào)和汽車(chē)ID號(hào)，在本研究中，信息分發(fā)采用MBW-ONE和MBW-TWO策略實(shí)現(xiàn)，信息分發(fā)的過(guò)程遵循以下兩個(gè)流程圖，見(jiàn)圖3、4.

5 廣播協(xié)議性能分析

5.1 模擬場(chǎng)景和參數(shù)的設(shè)置

為分析MBW廣播協(xié)議的性能，本文采用NS2模擬器進(jìn)行模擬.所有的協(xié)議都是在低、中、高交通密度條件下模擬的，汽車(chē)的密度范圍從0.8～4千輛／h，速度從0～60 km／h變化.本文采用2.25 km2網(wǎng)格道路拓?fù)浣Y(jié)構(gòu)實(shí)現(xiàn)MBW廣播協(xié)議的模擬，每條道路有3車(chē)道雙向交通流.汽車(chē)行駛遵循交叉口的交通燈信號(hào).交通信號(hào)包括紅燈、綠燈和黃燈，在模擬過(guò)程中，直行綠燈和紅燈分別為30、70 s，黃燈3 s；左轉(zhuǎn)綠燈為20 s，左轉(zhuǎn)紅燈80 s，左轉(zhuǎn)黃燈為3 s；整個(gè)交通信號(hào)周期為103 s.本文設(shè)置交叉口及障礙物.為了模擬真實(shí)的汽車(chē)移動(dòng)，采用VISSIM模擬器定義的移動(dòng)性模型.在某一條道路的中間位置的汽車(chē)負(fù)責(zé)產(chǎn)生警告信息.

圖3 MBW-ONE流程

圖4 MBW-TWO流程

IEEE802.11p標(biāo)準(zhǔn)里Veins 2.0網(wǎng)絡(luò)模型已經(jīng)定義鏈路層和物理層［22］，為廣播協(xié)議設(shè)置3 Mbps的位速率，信息包的大小為512字節(jié)，hello信標(biāo)包的大小25字節(jié)并且每1秒發(fā)送一次，應(yīng)答包為9個(gè)字節(jié)，模擬時(shí)間為500 s.使用下面4個(gè)特性來(lái)分析MBW的可靠性、高效性和可擴(kuò)展性.覆蓋率是指在模擬區(qū)域內(nèi)收到數(shù)據(jù)包汽車(chē)數(shù)量的百分?jǐn)?shù).高覆蓋率意味著MBW廣播協(xié)議選擇中繼節(jié)點(diǎn)和數(shù)據(jù)傳輸是可靠的，并且協(xié)議對(duì)于不同的交通密度具有較高的容忍性.時(shí)延是指一個(gè)數(shù)據(jù)包從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所用的時(shí)間.這個(gè)特性測(cè)量數(shù)據(jù)傳輸?shù)母咝?網(wǎng)絡(luò)開(kāi)銷(xiāo)等于模擬期間每個(gè)汽車(chē)接收到的數(shù)據(jù)包的數(shù)量.這個(gè)特性用來(lái)測(cè)量網(wǎng)絡(luò)的可擴(kuò)展性.轉(zhuǎn)發(fā)節(jié)點(diǎn)率是指網(wǎng)絡(luò)中重播來(lái)自源節(jié)點(diǎn)信息的汽車(chē)的比例.

5.2 模擬結(jié)果

圖5中給出多種交通流密度下幾個(gè)協(xié)議的覆蓋率，MBW和BSM協(xié)議的覆蓋率隨著交通密度的增加而增加.這是合理的，因?yàn)殡S著交通密度的變大，網(wǎng)絡(luò)連接性較好，因此數(shù)據(jù)包的接收率將會(huì)增加.MBW的覆蓋率在不同的交通密度條件下比BSM的高.特別是，當(dāng)交通流密度大約1.2千輛／h的時(shí)候，覆蓋率達(dá)到了100%，這是因?yàn)镸BW維護(hù)兩跳鄰居信息，采用汽車(chē)行駛的道路方向（東，南，西，北）、節(jié)點(diǎn)和鄰居節(jié)點(diǎn)之間的距離來(lái)識(shí)別交叉口，交叉口的識(shí)別率高，交叉口的中繼節(jié)點(diǎn)選擇準(zhǔn)確率高，減少信息在交叉口的冗余和碰撞，在路上可選擇到最遠(yuǎn)的中繼節(jié)點(diǎn)，減少信息的碰撞機(jī)會(huì)，增強(qiáng)信息可靠傳輸，所以覆蓋率比BSM的高.BSM協(xié)議的覆蓋率低是因?yàn)闆](méi)有交叉口識(shí)別機(jī)制，交叉口容易錯(cuò)過(guò)向所有方向轉(zhuǎn)發(fā)，而且選擇鄰居數(shù)量多的節(jié)點(diǎn)作中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)，所以中繼節(jié)點(diǎn)不一定是最遠(yuǎn)的，會(huì)造成信息冗余碰撞.這從式（3）可看得出來(lái).它的覆蓋率只有在密集型交通流中高，BSM的覆蓋率沒(méi)有達(dá)到100%.

圖5 覆蓋率

圖6 給出BSM和MBW鏈路時(shí)延比較.當(dāng)節(jié)點(diǎn)密度增加的時(shí)候，幾個(gè)協(xié)議的鏈路時(shí)延變短，因?yàn)楣?jié)點(diǎn)增多，網(wǎng)絡(luò)的連接性比較好，所以鏈路時(shí)延變短. MBW-TWO鏈路時(shí)延比BSM和MBW-ONE都低，理由是MBW-TWO在模擬期間一直維護(hù)兩跳鄰居信息，所以使用最短的時(shí)間發(fā)現(xiàn)交叉口的中繼節(jié)點(diǎn)并且迅速把信息轉(zhuǎn)發(fā)到其它節(jié)點(diǎn).本文規(guī)定交叉口的中繼節(jié)點(diǎn)直接轉(zhuǎn)發(fā)信息不等待，所以減少信息的轉(zhuǎn)發(fā)時(shí)間.MBW-ONE的鏈路時(shí)延比其它兩個(gè)高，這是因?yàn)镸BW-ONE只有在事故發(fā)生時(shí)才維護(hù)鄰居列表，所以在選擇中繼節(jié)點(diǎn)時(shí)浪費(fèi)時(shí)間.

圖6 時(shí)延

BSM廣播協(xié)議在二者中間，因?yàn)锽SM在模擬期間一直維護(hù)鄰居列表，它的時(shí)延函數(shù)選擇鄰居數(shù)量多的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，但不一定能夠選擇到最遠(yuǎn)的中繼節(jié)點(diǎn)，所以時(shí)延較大.

圖7給出幾個(gè)協(xié)議的轉(zhuǎn)發(fā)節(jié)點(diǎn)率.轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)量少，則信息冗余和競(jìng)爭(zhēng)減少，因此廣播風(fēng)暴的風(fēng)險(xiǎn)相應(yīng)地降低.MBW-ONE具有最低的轉(zhuǎn)發(fā)節(jié)點(diǎn)率并且曲線平滑.MBW-ONE的轉(zhuǎn)發(fā)節(jié)點(diǎn)率大約12%左右.BSM位于MBW-ONE和MBW-TWO之間.BSM的轉(zhuǎn)發(fā)節(jié)點(diǎn)率大約15%.MBW-ONE的轉(zhuǎn)發(fā)節(jié)點(diǎn)率比BSM低3%.MBW-TWO的轉(zhuǎn)發(fā)節(jié)點(diǎn)率輕微地增加.當(dāng)交通密度大約2.8、4.0千輛／h，BSM的轉(zhuǎn)發(fā)節(jié)點(diǎn)率突然增加到30%，理由是當(dāng)交通密度高的時(shí)候，BSM選擇的中繼節(jié)點(diǎn)不一定是最遠(yuǎn)的節(jié)點(diǎn)，結(jié)果導(dǎo)致轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)增加.本文提出的MBW轉(zhuǎn)發(fā)節(jié)點(diǎn)率低，這表明MBW選擇中繼節(jié)點(diǎn)的方法是正確的，所以降低轉(zhuǎn)發(fā)節(jié)點(diǎn)率.

圖7 轉(zhuǎn)發(fā)節(jié)點(diǎn)率

圖8 給出交通密度變化的所有協(xié)議的網(wǎng)絡(luò)開(kāi)銷(xiāo)，盡管不同的交通密度，MBW的網(wǎng)絡(luò)開(kāi)銷(xiāo)比BSM的低.因此MBW展示較好的網(wǎng)絡(luò)開(kāi)銷(xiāo)性能.MBWONE的網(wǎng)絡(luò)開(kāi)銷(xiāo)比MBW-TWO的網(wǎng)絡(luò)開(kāi)銷(xiāo)平均低5%，比BSM的網(wǎng)絡(luò)開(kāi)銷(xiāo)平均低20%，MBW-TWO的網(wǎng)絡(luò)開(kāi)銷(xiāo)比BSM平均低10%.因此MBW的可擴(kuò)展性在高的交通密度下比BSM的好，這樣的結(jié)果是因?yàn)镸BW有效地限制中繼節(jié)點(diǎn)的數(shù)量，因此，當(dāng)交通密度變大的時(shí)候，重播的信息數(shù)量減少，信息冗余降低.

圖8 網(wǎng)絡(luò)開(kāi)銷(xiāo)

6 結(jié) 語(yǔ)

本文提出一個(gè)新的基于位置的MBW廣播協(xié)議，是一個(gè)多種交通流密度下面向城市場(chǎng)景的警告信息分發(fā)協(xié)議.MBW把無(wú)線信號(hào)一次覆蓋道路的范圍分為東、南、西、北4個(gè)方向.維護(hù)兩跳鄰居信息，節(jié)點(diǎn)根據(jù)其至少兩個(gè)不同的方向的鄰居節(jié)點(diǎn)和自己之間的距離是否大于路寬來(lái)判斷自己是否在道路的交叉口，如果在交叉口有多個(gè)節(jié)點(diǎn)，則采用ID號(hào)最小的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，并且交叉口的中繼節(jié)點(diǎn)賦予優(yōu)先轉(zhuǎn)發(fā)的權(quán)限.支持?jǐn)?shù)據(jù)沿著道路雙向分發(fā). MBW協(xié)議在不同的交通密度條件下的覆蓋率優(yōu)于BSM的覆蓋率，實(shí)現(xiàn)低網(wǎng)絡(luò)開(kāi)銷(xiāo)、信息傳播的低時(shí)延、低轉(zhuǎn)發(fā)節(jié)點(diǎn)率.

總之，MBW廣播協(xié)議適合解決多種交通流密度環(huán)境下的安全信息廣播應(yīng)用，并且具有低網(wǎng)絡(luò)開(kāi)銷(xiāo)、低延遲和高覆蓋率.

［1］LIFan，WANG Yu.Routing in vehicular ad hoc network：a survey［J］.IEEE Vehicular Technology Magazine，2007，2（2）：12-22.

［2］NIS Y，TSENG Y C，CHEN Y S，et al.The broadcast storm problem in a mobile ad hoc network［C］／／Proceedings of the 5th Annual ACM／IEEE International Conference on Mobile Computing and Networking.Seattl：IEEE，1999：151-162.

［3］TSENG YC，NIS Y，SHIH E Y.Adaptive approaches to relieving broadcast storms in a wirelessmultihop mobile ad hoc network［J］.IEEE Transactions on Computers，2003，52（5）：545-557.

［4］HU Chunyu，HONG Yifei，HOU J.On mitigating the broadcast storm problem with directional antennas［C］／／IEEE International Conference on communications.Seattle：IEEE，2003：104-110.

［5］QAYYUM A，VIENNOT L，LAOUITI A.Multipoint relaying for flooding broadcastmessages in mobile wireless networks［C］／／Proceedings of the 35th Annual Hawaii International Conference on System Sciences.Big Island Hawaii：IEEE，2002：3866-3875.

［6］WU Xuewen，SONG Shiming，WANG Huibin.A novel position-based multi-hop broadcast protocol for vehicular Ad Hoc networks［J］.Journal of Networks，2011，6（1）：112-120.

［7］VIRIYASITAVAT W，TONGUZ O K，BAI Fan，et al.Uvcast：an urban vehicular broadcast protocol.Communications Magazine［J］.2011，49（11）：116-124.

［8］MAIA G，VILLAS L A，BOUKERCHE A，et al.Data dissemination in urban vehicular ad hoc networks with diverse traffic conditions［C］／／2013 IEEE Symposium on Computers and Communications.Split：IEEE，2013：000 459-000 464.

［9］NAJAFZADEH S，ITHNIN N，RAZAK S A，et al.Bsm：broadcasting of safetymessage in vehicular ad hoc networks［J］.Arabian Journal for Science and Engineering，2014，39（2）：777-782.

［10］YANG Y T，CHOU LD.Position-based adaptive broadcast for inter-vehicle communications［C］／／IEEE International Conference on CommunicationsWorkshops.BeiJing：IEEE，2008：410-414.

［11］LIU Congyi，CHIGAN C X.Rpb-md：a novel robust message dissemination method for vanets［C］／／IEEE Global Telecommunications Conference.New Orleans：LA：IEEE，2008：1-6.

［12］BI Yuanguo，ZHAO Hai，SHEN Xuemin，A directional broadcast protocol for emergency message exchange in intervehicle communications［C］／／IEEE International Conference on Communications.Dresden：IEEE，2009：1-5.

［13］KORKMAZ G，EKICI E，?ZGNüER F，et al.Urban multi-hop broadcast protocol for inter-vehicle communication systems［C］／／Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Networks. Philadelphia：ACM，2004：76-85.

［14］Li Da，HUANG Hongyu，LIXu，et al.A distance-based directional broadcast protocol for urban vehicular ad hoc network［C］／／International Conference on Wireless Communications.Networking and Mobile Computing. Shanghai：IEEE，2007：1520-1523.

［15］KORKMAZG，EKICIE，?ZGüNER F.Black-burstbased multihop broadcast protocols for vehicular networks［J］. IEEE Transactions on Vehicular Technology，2007，56（5）：3159-3167.

［16］CHIASSERINI C F，GAETA R，GARETTO M，et al. Efficient broadcasting of safety messages in multihop vehicular networks［C］／／20th International Parallel and Distributed Processing Symposium.Rhodes Island：IEEE，2006：8-14.

［17］FASOLO E，ZANELLA A，ZORZI M，An effective broadcast scheme for alertmessage propagation in vehicular ad hoc networks［C］／／2006 IEEE International Conference on Communications.Istanbul：IEEE，2006，9：3960-3965.

［18］TAHA M M I，HASAN Y M Y.Vanet-dsrc protocol for reliable broadcasting of life safety messages［C］／／2007 IEEE International Symposium on Signal Processing and Information Technology.Cairo：IEEE，2007：104-109.

［19］TUNG L C，GERLA M.An efficient road-based directional broadcastprotocol for urban vanets［C］／／2010 IEEEVehicular Networking Conference.Jersey City：IEEE，2010：9-16.

［20］KORKMAZ G，EKICIE，?ZGüNER F.An efficient fully adhoc multi-hop broadcast protocol for intervehicular communication systems［C］／／2006 IEEE International Conference on Communications.Istanbul：IEEE，2006，1：423-428.

［21］LITTLE T D C，AGARWAL A.An information propagation scheme for vanets［C］／／2005 IEEE Intelligent Transportation Systems Proceedings.Vienna：IEEE，2005：155-160.

［22］JIANG D，DELGROSSI L.Ieee 802.11p：Towards an international standard for wireless access in vehicular environments［C］／／2008 IEEE Vehicular Technology Conference.Calgary：IEEE，2008：2036-2040.

（編輯苗秀芝）

M ulti-hop broadcast protocol for warning for urban vanets

WANG Xiufeng，WANG Chunmeng，CUIGang
（School of Computer，Harbin Institute of Technology，150001 Harbin，China）

To improve dissemination toward all directions and decrease duration thatmessage is forwarded，in this paper，themulti-hop broadcast forwarning protocol in urban VANETs is proposed.The roadswhich wireless signal cover every time areclassified into four directions：east，south，west and north.Relay node at the intersection is decided by following rules：first，it has at least two neighbor nodeswhosedirections are different to the relay node，and the distances between relay nodeand the neighbors are more than the width of road.Second，its ID is the smallest among the nodes at the intersection.Relay nodes at intersections prioritize to forward messages without waiting.Relay nodes on the road are selected according to waiting-time equation and message is rebroadcasted if waiting time ends.MBW supports thatmessage is propagated in both directions along the road.Due to relay node selection strategy，the number of relay nodes andmessage retransmissions is decreased.Simulation results show that MBW offers better coverage，lower delay，lower forwarding nodes ratio and lower overhead compared to exiting broadcasting protocols in VANETs.

VANETs；position-based broadcast；data dissemination；diverse traffic density

TP393

：A

：0367-6234（2015）11-0034-07

10.11918／j.issn.0367-6234.2015.11.006

2015-01-23.

國(guó)家自然科學(xué)基金（61272130）.

王秀峰（1979—），女，教授，博士研究生；崔 剛（1947—），男，教授，博士生導(dǎo)師.

王秀峰，wxf＠hit.edu.cn.