車載通信中增強型多跳廣播算法研究*

趙海濤 ，朱洪波 ，2，劉南杰 ，蔡耿雄

（1.南京郵電大學(xué)通信與信息工程學(xué)院 南京 210003；2.南京郵電大學(xué)物聯(lián)網(wǎng)技術(shù)與應(yīng)用協(xié)同創(chuàng)新中心 南京210003）

1 引言

根據(jù)世界衛(wèi)生組織(World Health Organization,WHO)2013年的全球道路安全現(xiàn)狀報告，全球每天有將近3 400人死于交通事故，每年因交通事故受傷或殘疾的人數(shù)近千萬[1]。數(shù)據(jù)表明大多數(shù)交通事故是由于司機錯誤判斷而引起的，因為他們不能預(yù)料到前方道路的危險狀況。除此之外，天氣以及視線遮擋都有可能進一步降低司機對前方道路的了解。

幸運的是，隨著世界各國專家和研究人員對車輛通信不斷的研究和探討[2～7]，這個問題有望得到解決。除此之外，VANET(vehicular Ad Hoc network)已成為近10年來智能交通的研究熱點之一。因為VANET在解決車輛與道路安全、交通效率以及司機與乘客的便利性和舒適性上有極大的潛力。目前對VANET的研究主要集中在架構(gòu)的設(shè)計和實施上，研究工作包括路由、廣播、服務(wù)質(zhì)量、安全性等[8]。而本文的研究工作主要集中在VANET的多跳廣播協(xié)議。

由于VANET固有的特性，如車輛快速移動、節(jié)點分布不均勻、網(wǎng)絡(luò)拓撲頻繁變化等因素，多跳廣播存在許多挑戰(zhàn)和亟待解決的問題。在車輛密集的情況下，存在多輛車同時廣播數(shù)據(jù)分組，從而導(dǎo)致競爭和沖突。而當車輛稀疏時，又容易造成網(wǎng)絡(luò)分割問題，即廣播車輛一跳范圍內(nèi)沒有車輛可以作為中繼節(jié)點向更遠的區(qū)域轉(zhuǎn)發(fā)數(shù)據(jù)分組。同時，大量隱藏/暴露節(jié)點的存在也會影響廣播信息分發(fā)的可靠性。

2 相關(guān)研究

在Ad Hoc網(wǎng)絡(luò)中，當消息目的地在車輛一跳范圍之外時，多跳是唯一的可行方法。最簡單的多跳協(xié)議是洪泛廣播，接收到廣播消息的車輛需要立即向其鄰居車輛轉(zhuǎn)發(fā)該消息。在車輛稀疏的環(huán)境中，洪泛廣播是一種有效的消息分發(fā)方式。然而，隨著車輛數(shù)的增加，由于競爭和沖突，消息的交付率會大幅下降，即所謂的“廣播風(fēng)暴”問題[9]。

廣播抑制技術(shù)是一種常用的解決廣播風(fēng)暴問題的手段。Wisitpongphan等提出3種輕量級的廣播抑制技術(shù)：加權(quán)p-持續(xù)、時隙1-持續(xù)以及時隙p-持續(xù)[10]。其中時隙p-持續(xù)廣播結(jié)合了加權(quán)p-持續(xù)廣播和時隙1-持續(xù)廣播的優(yōu)點。車輛接收到數(shù)據(jù)分組之后，根據(jù)廣播節(jié)點和自身的距離計算出分配的等待時間。若在等待時間結(jié)束之前還沒有收到數(shù)據(jù)分組的副本，則以概率p轉(zhuǎn)發(fā)數(shù)據(jù)分組，否則丟棄數(shù)據(jù)分組。

然而，時隙p-持續(xù)廣播存在兩個主要的問題。在稀疏網(wǎng)絡(luò)中，分配的時隙可能不存在任何車輛，從而增加了不必要的等待時間（空白等待時間）。而對于密集網(wǎng)絡(luò)，同一時隙存在大量車輛，因此也會引起頻繁的競爭和沖突。Bae等提出一種基于鄰居信息的廣播機制（NIBS）解決上述的問題[11]。廣播節(jié)點根據(jù)鄰居表計算出在自己之后的車輛數(shù)目，并將其包含在廣播信息分組中。接收節(jié)點根據(jù)自己的鄰居表算出與廣播節(jié)點之間的車輛數(shù)目，用接收到的數(shù)據(jù)分組中的車輛數(shù)目減去計算出的車輛數(shù)目，即可得出自己是距離廣播節(jié)點第n遠的車輛。經(jīng)過（n-1）×τ（其中τ為等待時隙）的等待時間后，若車輛還沒有收到廣播數(shù)據(jù)分組的副本，則廣播該數(shù)據(jù)分組；否則丟棄該數(shù)據(jù)分組。NIBS解決了空白等待時間的問題，降低了端到端時延。然而，NIBS沒有解決稀疏網(wǎng)絡(luò)中的網(wǎng)絡(luò)分割問題，并且在密集網(wǎng)絡(luò)中競爭與沖突問題依然存在。

Li等提出一種基于距離的廣播協(xié)議——高效方向廣播(EDB)[12]。EDB使用定向天線，規(guī)定與行駛方向相反的最遠接收節(jié)點負責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)分組，并且在十字路口中安裝定向中繼器，用于協(xié)助向各個路段轉(zhuǎn)發(fā)數(shù)據(jù)分組。節(jié)點接收到數(shù)據(jù)分組后等待一段時間，此等待時間與發(fā)送者和接收者之間的距離成反比。若接收節(jié)點在等待時間后還沒有接收到廣播數(shù)據(jù)分組的副本，則轉(zhuǎn)發(fā)此數(shù)據(jù)分組；否則丟棄數(shù)據(jù)分組。Chou等在EDB的基礎(chǔ)上，提出了基于位置的定向廣播(LDB)協(xié)議[13]。LDB對節(jié)點等待時間進行改進，考慮了車輛位置、行駛方向和速度等因素。雖然LDB比EDB有更好的端到端時延，且考慮了雙向的高速公路場景，但與EDB一樣，依然沒有解決網(wǎng)絡(luò)分割問題。

基于以上的相關(guān)研究，本文提出一種基于鄰居信息的增強型多跳廣播協(xié)議（enhanced neighbor information-based broadcast protocol,ENIMBP），ENIMBP解決了高速公路場景下的網(wǎng)絡(luò)分割問題，在稀疏網(wǎng)絡(luò)中能顯著地降低端到端時延，并且能夠適應(yīng)不同的車輛密度場景。

3 基于鄰居信息的增強型多跳廣播協(xié)議

3.1 系統(tǒng)模型

目前大多數(shù)高速公路都是雙向的，選擇反向行駛的車輛作為轉(zhuǎn)發(fā)節(jié)點除了可以解決稀疏網(wǎng)絡(luò)中的網(wǎng)絡(luò)分割問題之外，還可以適應(yīng)不同的場景[14]。假設(shè)每輛車都能通過定位系統(tǒng)獲取自己的精確位置、速度和行駛方向。每輛車都有相同的處理器和計算能力，且無線信號的傳輸速度接近光速。除此之外，ENIMBP要求車輛維護自己的鄰居表，因此需要周期性地發(fā)送Hello分組進行信息交互。

定義1 中繼區(qū)域和忽略區(qū)域

ENIMBP采用全向天線，并將車輛i的廣播范圍分成兩個區(qū)域：位于廣播車輛后面的區(qū)域，定義為中繼區(qū)域Ri；位于廣播車輛前面的區(qū)域，定義為忽略區(qū)域Ii,如圖1所示。ENIMBP規(guī)定，車輛i的鄰居表中只有位于中繼區(qū)域Ri的車輛才負責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)分組，而位于忽略區(qū)域Ii的車輛則丟棄數(shù)據(jù)分組。

圖1 廣播范圍劃分

定義2 轉(zhuǎn)發(fā)等待時間WTi

ENIMBP采用基于接收者的廣播抑制技術(shù)，即由接收者根據(jù)自己的信息決定何時進行廣播。定義車輛i的轉(zhuǎn)發(fā)等待時間為WTi，在等待WTi時間后，若還沒有收到任何數(shù)據(jù)分組，則進行廣播。WTi的計算會在第3.2節(jié)進行闡述。

3.2 中繼節(jié)點選擇

3.2.1 數(shù)據(jù)分組格式

當車輛探測到緊急情況時，會生成并廣播數(shù)據(jù)分組。車輛根據(jù)鄰居表可以計算出位于中繼區(qū)域內(nèi)的節(jié)點數(shù)目N。數(shù)據(jù)分組格式如圖2所示。

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

其中，VID表示廣播車輛ID；Position表示廣播車輛的位置；Velocity表示車輛的速度矢量，包括大小和方向；N為位于廣播節(jié)點中繼區(qū)域內(nèi)的車輛數(shù)目；MID表示消息ID；Message描述詳細的道路事件。

3.2.2 計算WTi

廣播車輛的鄰居節(jié)點收到廣播數(shù)據(jù)分組后，根據(jù)廣播數(shù)據(jù)分組和各自的位置、速度信息計算相應(yīng)的轉(zhuǎn)發(fā)等待時間。假設(shè)廣播車輛i的速度大小為vi，歸一化的單位向量為；接收車輛j的速度大小為vj，歸一化的單位向量為。廣播車輛i的中繼區(qū)域內(nèi)的車輛數(shù)目為Ni，接收車輛j根據(jù)自己的鄰居表計算出自身與廣播車輛i之間的車輛數(shù)nj,i（不包含廣播車輛）。在沒有并行車輛的情況下，根據(jù)式（1）就可以區(qū)分出不同車輛的轉(zhuǎn)發(fā)等待時間。式（1）可以計算出接收車輛j是距離廣播車輛i第Ni-nj,i遠的車輛，其中，C1為單位等待時間，即最遠接收車輛等待C1，次遠接收車輛等待2C1，以此類推。

然而，在許多實際場景中，往往會出現(xiàn)多輛車并行的情況，也就是說最遠接收車輛有可能有多輛。因此，ENIMBP對式（1）進行改進，考慮了節(jié)點速度和方向等因素，得出接收車輛j的轉(zhuǎn)發(fā)等待時間為：

從式（2）可以看出，在距離相同的情況下，與廣播車輛反向的接收車輛轉(zhuǎn)發(fā)等待時間會比與廣播車輛同向的接收車輛的小，因此會優(yōu)先轉(zhuǎn)發(fā)數(shù)據(jù)分組。在距離相同且廣播車輛與接收車輛同向的情況下，則速度小的車輛優(yōu)先轉(zhuǎn)發(fā)數(shù)據(jù)分組，因為速度小的接收車輛與廣播車輛的相對距離較大；而在距離相同且廣播車輛與接收車輛反向的情況下，則速度大的車輛優(yōu)先轉(zhuǎn)發(fā)數(shù)據(jù)分組，因為速度大的接收車輛與廣播車輛的相對距離較大。適當選擇C1與 C2，可以有效地區(qū)分接收車輛的轉(zhuǎn)發(fā)優(yōu)先級。

3.3 廣播流程

NIBS只考慮了單向的公路場景，因此當存在稀疏網(wǎng)絡(luò)中的網(wǎng)絡(luò)分割問題時，會導(dǎo)致廣播中斷。然而，現(xiàn)實中的高速公路大多數(shù)都是雙向的，因此，這里針對雙向的高速公路，提出一種切實可行的轉(zhuǎn)發(fā)算法。

為了解決隱藏/暴露節(jié)點問題，在廣播車輛中繼區(qū)域內(nèi)沒有任何車輛時，廣播車輛會廣播一個僅包含事件ID的取消數(shù)據(jù)分組，通知忽略區(qū)域內(nèi)的車輛放棄廣播。

如圖3（a）所示，在車輛A處發(fā)生了意外，由車輛A產(chǎn)生廣播數(shù)據(jù)分組，并按以下流程完成信息的傳播。

步驟1 廣播車輛根據(jù)鄰居表計算出位于自己中繼區(qū)域內(nèi)的車輛數(shù)目N，若N=0，則進入步驟2，否則，進入步驟3。

步驟2 若中繼區(qū)域內(nèi)的車輛數(shù)目N=0，則廣播車輛不會廣播數(shù)據(jù)分組。與此同時，該車輛不斷地更新鄰居表，每次更新鄰居表都會檢測是否有車輛位于自己的中繼區(qū)域。當中繼區(qū)域出現(xiàn)車輛時，則進入步驟3；否則，繼續(xù)存儲攜帶。

步驟3 若中繼區(qū)域內(nèi)的車輛數(shù)目N>0，廣播車輛以自己的ID、位置以及中繼區(qū)域車輛數(shù)目更新廣播數(shù)據(jù)分組中相應(yīng)的信息，并廣播數(shù)據(jù)分組，進入步驟4。值得注意的是，為了避免因鏈路中斷而導(dǎo)致的分組丟失，廣播節(jié)點會一直周期性地進行廣播，直到收到廣播數(shù)據(jù)分組副本或者取消數(shù)據(jù)分組為止。

步驟4 接收車輛首先根據(jù)數(shù)據(jù)分組中的廣播節(jié)點位置和自己的位置判斷自己處于廣播節(jié)點的哪個區(qū)域。若處于忽略區(qū)域，則不做任何處理，直接丟棄數(shù)據(jù)分組；若處于中繼區(qū)域，則根據(jù)數(shù)據(jù)分組的事件信息對駕駛員做出相應(yīng)的提醒，并進入步驟5。

步驟5 接收車輛根據(jù)接收的數(shù)據(jù)和式（2）計算自己的等待時間，并根據(jù)自己的鄰居表判斷中繼區(qū)域中是否有車輛。若有，則轉(zhuǎn)到步驟3，若沒有，則進入步驟6。

步驟6 當接收車輛中繼區(qū)域沒有車輛時，接收節(jié)點廣播取消數(shù)據(jù)分組，即讓位于忽略區(qū)域的車輛放棄不必要的廣播（因為此時沒有車輛比本接收車輛距離廣播車輛更遠）。接收到此取消數(shù)據(jù)分組的車輛將放棄廣播。

圖3 ENIMBP廣播過程

對于圖3所示的車輛分布，車輛A為源點，它產(chǎn)生數(shù)據(jù)分組。由于中繼區(qū)域中有車輛B、C、D，所以車輛A廣播該數(shù)據(jù)分組。車輛E位于A的忽略區(qū)域中，故直接丟棄數(shù)據(jù)分組。根據(jù)式（2），車輛B為第一個廣播節(jié)點，但由于B的中繼區(qū)域不存在任何車輛，故廣播取消數(shù)據(jù)分組，車輛A、C、D接收到取消數(shù)據(jù)分組請求后放棄后續(xù)的廣播。經(jīng)過一段時間后，車輛C將進入B的中繼區(qū)域 （車輛A與車輛B相向而行），此時B更新數(shù)據(jù)分組中的相應(yīng)數(shù)據(jù)，并廣播該數(shù)據(jù)分組。

根據(jù)上述的步驟，基于鄰居信息的增強型多跳廣播協(xié)議的流程如圖4所示。

圖4 ENIMBP廣播流程

4 仿真與性能評估

為了對改進算法進行性能評估，本文使用網(wǎng)絡(luò)仿真軟件NS2對算法進行仿真，并與已提出的NIBS和時隙p-持續(xù)(p=0.5)方案進行比較。

4.1 仿真環(huán)境

仿真場景為雙向的高速公路場景，每個方向3個車道，車道寬4 m，道路總長5 km。利用車載網(wǎng)絡(luò)移動模擬器VanetMobiSim[15]模擬車輛的移動，假設(shè)車輛隨機分布，并產(chǎn)生車輛移動跟蹤文件。網(wǎng)絡(luò)仿真軟件選用NS-2.34[16]，該版本集成了IEEE 802.11p/WAVE[17～19]模塊，因此很適合用于VANET的仿真。仿真參數(shù)見表1。

表1 仿真參數(shù)

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

4.2.1 端到端時延

圖5 端到端時延

圖5是 NIBS、時隙 p-持續(xù)（p=0.5）和 ENIMBP 3種方案的端到端時延隨著車輛密度的變化情況。從圖5中可以看出，在任何車輛密度場景下，ENIMBP的端到端時延都優(yōu)于NIBS和時隙p-持續(xù)方案。在車輛密度極低的情況下，網(wǎng)絡(luò)分割問題的存在導(dǎo)致NIBS和時隙p-持續(xù)方案的端到端時延劇增；而隨著車輛密度的不斷增大，相同距離的車輛也隨之增多，從而NIBS和時隙p-持續(xù)方案都有所增加。然而，ENIMBP利用反向車輛很好地解決了車輛密度低時的網(wǎng)絡(luò)分割問題；同時轉(zhuǎn)發(fā)等待時間引入了車輛速度和方向等因素，在相同距離的車輛不斷增多的情況下，依然能夠很好地區(qū)分車輛間的轉(zhuǎn)發(fā)等待時間。

4.2.2 分組到達率

圖6是 NIBS、時隙 p-持續(xù)(p=0.5)和 ENIMBP 3種方案的分組到達率隨著車輛密度變化的情況。從圖6中可以看出，在車輛密度極低的情況下，由于網(wǎng)絡(luò)分割問題的存在，NIBS和時隙p-持續(xù)方案的分組到達率都很低；隨著車輛密度的增大，NIBS和時隙p-持續(xù)方案的分組到達率顯著提高，但當車輛密度增大到一定程度時，相同距離的車輛增多，分組到達率又有所下降。而ENIMBP解決了網(wǎng)絡(luò)分割問題，并引入車輛速度和方向，在何種車輛密度場景下，都能保證高的分組到達率。

圖6 分組到達率

5 結(jié)束語

本文提出了一種高速公路場景下基于鄰居信息的增強型多跳廣播協(xié)議——ENIMBP，通過利用車輛的鄰居信息同時結(jié)合車輛的位置、行駛速度和方向來確定轉(zhuǎn)發(fā)等待時間，以選擇最優(yōu)的轉(zhuǎn)發(fā)車輛。根據(jù)車輛的位置，ENIMBP可以初步確定與廣播車輛距離不同的車輛的轉(zhuǎn)發(fā)等待時間。而在與廣播車輛距離相同的情況下，ENIMBP則利用車輛速度和方向來區(qū)分轉(zhuǎn)發(fā)等待時間。仿真結(jié)果表明，與NIBS和時隙p-持續(xù)方案相比，在車輛密度較小的情況下，ENIMBP利用鄰居信息和反向車輛的存儲—轉(zhuǎn)發(fā)機制，可以保證較低的端到端時延和較高的分組到達率；而在車輛密度較大的情況下，由于額外引進了車輛速度和位置來計算轉(zhuǎn)發(fā)等待時間，ENIMBP能更好地區(qū)分相同距離車輛的等待轉(zhuǎn)發(fā)時間，從而降低了沖突和競爭，提高了分組到達率。

然而，ENIMBP依然存在很多不足的地方。鄰居信息需要及時地更新和維護，在車輛密度低的情況下，廣播算法需要頻繁地廣播取消數(shù)據(jù)分組，從而增加了網(wǎng)絡(luò)負載。ENIMBP只考慮了高速公路場景，而并不適用于城市道路環(huán)境。下一步的工作將圍繞這些問題進一步深入研究，不斷完善本文提出的廣播算法。

1 World Health Organization.Global Status Report on Road Safety 2013,2013

2 Tsugawa S,Kato S,Tokuda K,et al.A cooperative driving system with automated vehicles and inter-vehicle communications in Demo 2000.IEEE Intelligent Transportation Systems,2001(3)

3 Car 2 car.http://www.car-to-car.org,2012

4 Festag A,Fubler H,Hartenstein H,et al.FleetNet:bringing car-to-car communication into real world.Proceedings of 11th World Congress on Intelligent Transportation Systems(ITS’04),Maceiò,Alagoas,Brazil,2004

5 Reichardt D,Miglietta M,Morsink P.CarTALK 2000:safe and comfortable driving based upon inter-vehicle-communication.IEEE Intelligent Vehicle Symposium,2002(12)

6 CVIS.http://www.cvisproject.org,2012

7 Jiang D,Delgrossi L.IEEE 802.11p:towards an international standard for wireless access in vehicular environments.Proceedings of IEEEVehicularTechnologyConference,Baltimore,MD,USA,2008

8 Zeadally S,Hunt R,Chen Y.S,et al.Vehicular Ad Hoc networks(VANETS):status,results,and challenges.Telecommunication Systems,2012(4)

9 Tseng Y C,Ni S Y,Chen Y S,et al.The broadcast storm problem in a mobile Ad Hoc network.Wireless Networks,2002,8(2～3)

10 Wisitpongphan N,Tonguz O K,Parikh J S,et al.Broadcast storm mitigation techniques in vehicular Ad Hoc networks.IEEE Wireless Communications,2007(6)

11 Bea J S,Kum D.W,Nam J.C,et al.Neighbor informationbased broadcast scheme for VANET.Proceedings of 18th Asia-Pacific Conference on Communications,Penang,Malaysia,2012

12 Li D,Huang H,Li X,et al.A distance-based directional broadcast protocol for urban vehicular Ad Hoc network.Proceedings of the 3rd IEEE International Conference on Wireless Communications,Networking and Mobile Computing(WiCOM 2007),Shanghai,China,2007

13 Chou L D,Yang Y T.Location-based directional broadcast for inter-vehicle communications.Proceedings of IEEE Vehicular Technology Conference,Ottawa,Canada,2010

14 Nadeem T,Shankar P,Iftode L.A comparative study of data dissemination models for vanes.Proceedings of 3rd Annual International Conference on Mobile and Ubiquitous Systems(MOBIQUITOUS),San Jose,CA,USA,2006

15 VanetMobiSim.http://vanet.eurecom.fr/

16 Network Simulator 2(NS2).http://nsnam.isi.edu/nsnam/index.php/Main_Page

17 Eichler S.Performance evaluation of the IEEE 802.11p WAVE communication standard. Proceedings of IEEE Vehicular Technology Conference(VTC-2007),Baltimore,USA,2007

18 Stanica R,Chaput E,Beylot A L.Properties of the MAC layer in safety vehicular Ad Hoc networks.IEEE Communications Magazine,2012(5)

19 Ghandour A J,Difelice M,Artail H,et al.Dissemination of safety messages in IEEE 802.11p/WAVE vehicular network:analytical study and protocol enhancements.Pervasive and Mobile Computing,2013(3)