黃家瑋，鐘少華，劉聯(lián)海，王建新

（中南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410083）

車載自組網(wǎng)中基于車輛密度的多跳廣播協(xié)議

黃家瑋，鐘少華，劉聯(lián)海，王建新

（中南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410083）

在車載自組網(wǎng)中，介質(zhì)訪問控制協(xié)議（MAC）的轉(zhuǎn)發(fā)效率直接影響了數(shù)據(jù)消息的多跳廣播傳輸性能?，F(xiàn)有方法通常在每跳覆蓋范圍內(nèi)選擇最遠(yuǎn)節(jié)點(diǎn)來承擔(dān)轉(zhuǎn)發(fā)任務(wù)，通過降低轉(zhuǎn)發(fā)次數(shù)實(shí)現(xiàn)快速多跳廣播覆蓋。然而，通過仿真實(shí)驗(yàn)和模型分析，當(dāng)車輛密度變大時(shí)，現(xiàn)有方法導(dǎo)致信道競(jìng)爭(zhēng)的接入延時(shí)劇增。因此，提出了一種基于IEEE 802.11p協(xié)議的多跳廣播協(xié)議VDF，根據(jù)車輛密度自適應(yīng)地選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。事故預(yù)警和在線游戲2種典型應(yīng)用仿真實(shí)驗(yàn)結(jié)果表明VDF降低了全網(wǎng)廣播消息的覆蓋延時(shí)，同時(shí)取得了信道沖突程度和多跳覆蓋速度的合理折中。

無線車載自組織網(wǎng)絡(luò)；介質(zhì)訪問控制協(xié)議；廣播；IEEE 802.11p

1 引言

近年來，隨著無線通信、計(jì)算機(jī)網(wǎng)絡(luò)等技術(shù)應(yīng)用于智能交通系統(tǒng)（ITS,intelligent transport system）中，車載自組網(wǎng)（VANET，vehicular ad-hoc networks）正逐漸成為車載通信的主流技術(shù)，通過車輛—基站和車輛—車輛之間通信，提供了各種輔助車輛行駛的網(wǎng)絡(luò)服務(wù)[1]。但VANET中車輛節(jié)點(diǎn)移動(dòng)速度快、鏈路壽命短、網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化快等因素直接影響了網(wǎng)絡(luò)傳輸效率。實(shí)驗(yàn)表明，在VANET 中數(shù)據(jù)分組的成功傳輸率不超過50%，傳輸延遲大而且延時(shí)抖動(dòng)劇烈[2]。同時(shí)，由于車輛節(jié)點(diǎn)通常呈現(xiàn)“桶狀”的密集聚集，常用的泛洪廣播路由協(xié)議會(huì)帶來嚴(yán)重的信道擁塞和沖突分組丟失。

因此，保證VANET網(wǎng)絡(luò)應(yīng)用數(shù)據(jù)信息低延時(shí)、高可靠的傳播是一件具有挑戰(zhàn)性的工作。例如，在典型的事故預(yù)警應(yīng)用中，當(dāng)探測(cè)事故發(fā)生時(shí)，車輛將立即采取多跳廣播的方式向其他車輛發(fā)送事故預(yù)警消息[3]。如果后續(xù)車輛沒有及時(shí)收到預(yù)警消息，就可能會(huì)發(fā)生追尾甚至連環(huán)相撞事故。從事故發(fā)生到后續(xù)車輛收到警告消息的延時(shí)越短，車輛避險(xiǎn)概率就越高。

學(xué)術(shù)界和工業(yè)界對(duì)車載自組網(wǎng)的介質(zhì)訪問控制協(xié)議進(jìn)行了廣泛的研究。其中，IEEE 802.11p協(xié)議[4]成為了VANET 的介質(zhì)訪問控制協(xié)議通信的主流協(xié)議。作為IEEE 802.11協(xié)議簇中的一員，IEEE 802.11p協(xié)議沿用了基于二進(jìn)制指數(shù)退避的載波監(jiān)聽多址接入（沖突避免）技術(shù)實(shí)現(xiàn)在共享無線傳輸介質(zhì)上的信道接入。其主要流程是：需要發(fā)送數(shù)據(jù)的節(jié)點(diǎn)監(jiān)聽信道來判斷信道狀態(tài)，如果信道空閑，則發(fā)送數(shù)據(jù)；如果信道忙碌，則在信道空閑后，等待隨機(jī)退避時(shí)間后重新競(jìng)爭(zhēng)信道的使用權(quán)。

IEEE 802.11p協(xié)議雖然提供了隨機(jī)公平的信道接入方法，但各節(jié)點(diǎn)隨機(jī)接入信道的方式并不能在多跳傳輸場(chǎng)景下提供低延時(shí)保證。而且為了降低信道開銷，IEEE 802.11p協(xié)議也沒有使用RTS/CTS信道預(yù)約機(jī)制來避免各節(jié)點(diǎn)同時(shí)發(fā)送造成數(shù)據(jù)碰撞。為了解決多跳傳輸中的延時(shí)和可靠性問題，很多學(xué)者提出了各種基于IEEE 802.11p協(xié)議的多跳廣播傳輸協(xié)議。這些協(xié)議大部分使用GPS設(shè)備獲取地理位置信息，以最小化連通支配集為設(shè)計(jì)目標(biāo)，選擇當(dāng)前節(jié)點(diǎn)傳輸范圍內(nèi)最遠(yuǎn)的節(jié)點(diǎn)來承擔(dān)轉(zhuǎn)發(fā)任務(wù)，這樣不但降低了轉(zhuǎn)發(fā)次數(shù)，而且避免了多個(gè)節(jié)點(diǎn)同時(shí)轉(zhuǎn)發(fā)而引發(fā)的數(shù)據(jù)碰撞。

本文通過仿真實(shí)驗(yàn)和模型分析證明了在不同車輛密度場(chǎng)景中，選擇不合理的中繼節(jié)點(diǎn)進(jìn)行多跳廣播消息轉(zhuǎn)發(fā)會(huì)導(dǎo)致信道接入延時(shí)劇增，從而提高消息的總傳輸延時(shí)。因此，本文提出了一種基于IEEE 802.11p的多跳廣播協(xié)議VDF（vehicle density based forwarding），根據(jù)車輛密度自適應(yīng)地選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，在信道接入延時(shí)和轉(zhuǎn)發(fā)跳數(shù)之間取得了較好的均衡。

2 相關(guān)工作

在IEEE 802.11p協(xié)議的多跳傳輸中，每一個(gè)收到消息的節(jié)點(diǎn)都會(huì)轉(zhuǎn)發(fā)該消息。由于相同消息會(huì)被重復(fù)廣播，這不但浪費(fèi)了有限的無線信道帶寬，而且造成頻繁的數(shù)據(jù)碰撞和過高的信道接入延時(shí)。為了解決這個(gè)問題，目前，提出了多種基于IEEE 802.11p協(xié)議的快速多跳廣播協(xié)議，具體可以分為基于延時(shí)和基于概率的2類協(xié)議。

基于延時(shí)的多跳廣播協(xié)議的基本思路是給最遠(yuǎn)的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)分配最短的廣播等待延時(shí)。文獻(xiàn)[5]提出了一種基于IEEE 802.11p協(xié)議的多跳廣播協(xié)議UMB，根據(jù)車輛節(jié)點(diǎn)距發(fā)送方的不同距離給節(jié)點(diǎn)分配不同的廣播延時(shí)，距發(fā)送方越遠(yuǎn)的節(jié)點(diǎn)所分配的廣播延時(shí)越短。因此，廣播延時(shí)最短的車輛節(jié)點(diǎn)最先廣播收到的消息，而其他收到同樣消息的節(jié)點(diǎn)不再?gòu)V播該消息，避免數(shù)據(jù)碰撞，并提高效率。

另一種基于延時(shí)的Rec協(xié)議[6]也使用了地理位置信息來選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。在Rec協(xié)議中，選取距離沒收到消息的鄰居節(jié)點(diǎn)質(zhì)心最近的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。該節(jié)點(diǎn)收到消息后立即轉(zhuǎn)發(fā)，因此能減少延時(shí)和不必要的重傳次數(shù)。但由于車輛的高移動(dòng)性，Rec協(xié)議很難得到周圍節(jié)點(diǎn)的實(shí)時(shí)位置信息。

為了避免錯(cuò)誤的估計(jì)傳輸范圍，JIVCA[7]使用周期性的Hello分組來實(shí)時(shí)獲取鄰居節(jié)點(diǎn)的位置信息。根據(jù)鄰居節(jié)點(diǎn)的位置信息，JIVCA實(shí)時(shí)更新各節(jié)點(diǎn)的當(dāng)前估計(jì)傳輸范圍。與其他基于延時(shí)的協(xié)議不同的是，JIVCA通過調(diào)節(jié)MAC層競(jìng)爭(zhēng)窗口值來選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。距離發(fā)送方越遠(yuǎn)節(jié)點(diǎn)的競(jìng)爭(zhēng)窗口值越小，具有越大的可能性成為轉(zhuǎn)發(fā)節(jié)點(diǎn)。

基于概率的多跳廣播協(xié)議為每一個(gè)車輛節(jié)點(diǎn)設(shè)定不同的廣播轉(zhuǎn)發(fā)概率[8～10]。文獻(xiàn)[8]提出了一種加權(quán)的p-堅(jiān)持MAC協(xié)議，收到消息的節(jié)點(diǎn)根據(jù)自己距離發(fā)送方的距離計(jì)算廣播的概率。隨著距離的增加，廣播所收到消息的概率增大。因此，距離發(fā)送方最遠(yuǎn)的節(jié)點(diǎn)最有可能首先廣播消息，從而降低信道中的廣播消息數(shù)量和信道競(jìng)爭(zhēng)程度。

3 問題分析

為了加快廣播消息的傳播速度，基于延時(shí)和基于概率的廣播協(xié)議都為距離發(fā)送節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)賦予最高的轉(zhuǎn)發(fā)優(yōu)先級(jí)。這樣，方法實(shí)現(xiàn)了轉(zhuǎn)發(fā)中繼數(shù)量的最小化，但同時(shí)卻忽略了轉(zhuǎn)發(fā)中繼節(jié)點(diǎn)面臨的信道競(jìng)爭(zhēng)問題：轉(zhuǎn)發(fā)節(jié)點(diǎn)雖然在發(fā)送節(jié)點(diǎn)傳輸覆蓋范圍內(nèi)具有最高的轉(zhuǎn)發(fā)優(yōu)先級(jí)，能避免傳輸范圍內(nèi)的信道沖突，但這卻無法避免與傳輸范圍外的隱藏節(jié)點(diǎn)沖突。而當(dāng)車輛節(jié)點(diǎn)密度增加時(shí)，這種由隱藏節(jié)點(diǎn)引起的競(jìng)爭(zhēng)延時(shí)會(huì)不斷加劇，造成端到端的廣播傳輸性能下降。本節(jié)首先描述VANET多跳廣播的典型場(chǎng)景，然后利用仿真實(shí)驗(yàn)來分析車輛節(jié)點(diǎn)密度對(duì)多跳廣播傳輸性能的影響。

車載無線網(wǎng)絡(luò)多跳廣播的典型場(chǎng)景設(shè)定為如圖1所示的多車道公路。由于車輛節(jié)點(diǎn)的傳輸半徑范圍R遠(yuǎn)大于道路寬度，因此，場(chǎng)景可簡(jiǎn)化為道路長(zhǎng)度為L(zhǎng)的直線網(wǎng)絡(luò)拓?fù)洹Ｆ渲?，車輛密度為α，發(fā)送方S和轉(zhuǎn)發(fā)節(jié)點(diǎn)F的距離為d。F轉(zhuǎn)發(fā)S所發(fā)送消息的同時(shí)，在發(fā)送方S的傳輸范圍R內(nèi)沒有其他車輛與F競(jìng)爭(zhēng)信道。

用NS2[11]仿真搭建如圖1所示的實(shí)驗(yàn)拓?fù)鋱?chǎng)景，所有車輛節(jié)點(diǎn)均勻分布在5 km長(zhǎng)的4車道直線道路上，以恒定速度同向行駛。各節(jié)點(diǎn)使用IEEE 802.11p作為MAC層協(xié)議，以10個(gè)/秒的速率發(fā)送消息分組。消息分組大小為1 000 byte，這在傳輸速率為1 Mbit/s的無線信道中需要占用32個(gè)時(shí)隙。表1描述了仿真和分析中的道路交通參數(shù)和MAC層協(xié)議設(shè)置。車輛密度分別為每公里每車道25、100和175 輛，以模擬測(cè)試車輛密度稀疏和稠密的不同道路場(chǎng)景中轉(zhuǎn)發(fā)的性能。同時(shí)，測(cè)試中選擇距離發(fā)送節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)中繼節(jié)點(diǎn)。由于傳輸半徑遠(yuǎn)大于道路寬度，本文將實(shí)驗(yàn)拓?fù)鋸?車道簡(jiǎn)化為1車道的直線道路，那么車輛密度所對(duì)應(yīng)的α參數(shù)值分別為0.1、0.4和0.7輛/米。

圖1 車載無線網(wǎng)絡(luò)多跳廣播的典型場(chǎng)景

表1 實(shí)驗(yàn)場(chǎng)景參數(shù)設(shè)置

實(shí)驗(yàn)中測(cè)試道路最前端的車輛節(jié)點(diǎn)向最后端車輛節(jié)點(diǎn)發(fā)送消息分組的傳輸延時(shí)和廣播次數(shù)。圖2所示為在不同車輛密度下該消息分組端到端延時(shí)的累積分布函數(shù)。當(dāng)車輛密度很小時(shí)（α=0.1輛/米），傳輸延時(shí)主要分布在0.15 s以下。而當(dāng)密度變大時(shí)，延時(shí)值不斷提升，其中，α=0.7輛/米時(shí)，延時(shí)主要分布在0.45 s左右。

為了進(jìn)一步分析延時(shí)隨著密度上升而提高的原因，本文統(tǒng)計(jì)了端到端傳輸消息中各轉(zhuǎn)發(fā)節(jié)點(diǎn)的廣播次數(shù)。其中，總廣播次數(shù)包括了各轉(zhuǎn)發(fā)節(jié)點(diǎn)的正常中繼發(fā)送次數(shù)和由于信道沖突而造成的發(fā)送失敗次數(shù)。圖3顯示，隨著密度的變大，信道沖突的發(fā)送失敗次數(shù)不斷提高。雖然正常中繼發(fā)送次數(shù)不變，總的廣播次數(shù)仍然提升約55%。

圖2 端到端消息延時(shí)的累計(jì)分布函數(shù)

圖3 端到端消息發(fā)送次數(shù)

4 理論建模和協(xié)議設(shè)計(jì)

從第3節(jié)的分析可知，如果選擇距離發(fā)送節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)中繼節(jié)點(diǎn)，在節(jié)點(diǎn)密度變大時(shí)信道的沖突會(huì)使傳輸延時(shí)不斷提高，降低傳輸性能。針對(duì)該問題，本節(jié)首先利用數(shù)學(xué)建模和仿真實(shí)驗(yàn)來分析轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇位置和多跳廣播延時(shí)的關(guān)系，進(jìn)而得到最佳轉(zhuǎn)發(fā)節(jié)點(diǎn)的選取方法，最后提出了基于車輛密度的多跳廣播協(xié)議。

4.1 建模分析

為了分析轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇位置和多跳廣播延時(shí)的關(guān)系，本文提出p-堅(jiān)持CSMA/CA模型用以分析IEEE 802.11p的信道競(jìng)爭(zhēng)機(jī)制。該模型從發(fā)送概率p的幾何分布中隨機(jī)取樣，以刻畫無線節(jié)點(diǎn)的隨機(jī)退避機(jī)制，能較好地分析IEEE 802.11協(xié)議簇的傳輸性能[12,13]。

圖4展示了一次消息發(fā)送的典型流程，其中包括了成功發(fā)送（successful）時(shí)隙，以及每次成功發(fā)送之前可能產(chǎn)生的信道碰撞（collision）時(shí)隙和信道空閑（idle）時(shí)隙。其中，由多個(gè)車輛節(jié)點(diǎn)在相同時(shí)隙發(fā)送消息將產(chǎn)生信道碰撞。而發(fā)生信道碰撞后，依據(jù)IEEE 802.11p的退避算法，各節(jié)點(diǎn)將隨機(jī)等待一段時(shí)間，從而形成了信道空閑時(shí)隙。

圖4 消息發(fā)送的過程

由圖1可知，距離d內(nèi)共有αd個(gè)節(jié)點(diǎn)。轉(zhuǎn)發(fā)節(jié)點(diǎn)F進(jìn)行消息轉(zhuǎn)發(fā)時(shí)，可能有αd–1個(gè)隱藏節(jié)點(diǎn)與之發(fā)生信道消息碰撞。使用式(1)和式(2)計(jì)算轉(zhuǎn)發(fā)節(jié)點(diǎn)F成功傳輸概率Ps和碰撞概率Pc。

其中，在初始狀態(tài)下，依據(jù)最小競(jìng)爭(zhēng)窗口值CWmin計(jì)算得到各節(jié)點(diǎn)的平均隨機(jī)退避時(shí)間為，那么各節(jié)點(diǎn)發(fā)送概率p為

根據(jù)式(1)和式(2)，可以計(jì)算得到轉(zhuǎn)發(fā)節(jié)點(diǎn)F所經(jīng)歷碰撞次數(shù)Nc的期望值E[Nc]為

每次信道碰撞時(shí)間Tc包括消息發(fā)送時(shí)間σm和DIFS等待時(shí)間σD。其中，m、D和σ分別為消息發(fā)送占用時(shí)隙數(shù)、DIFS等待時(shí)隙數(shù)和時(shí)隙長(zhǎng)度。由式(4)計(jì)算得到在每次成功發(fā)送前的總信道碰撞時(shí)間Tcol為

如圖2所示，信道碰撞僅發(fā)生在2個(gè)空閑片段之間，所以計(jì)算空閑片段數(shù)量的期望值E[Ni]為

依據(jù)發(fā)送概率p和競(jìng)爭(zhēng)節(jié)點(diǎn)數(shù)目αd可以確定每個(gè)空閑片段的等待時(shí)隙數(shù)，計(jì)算其期望值E[Ti]為

在一次成功發(fā)送前的總信道空閑時(shí)間Tidle為

而一次成功發(fā)送消息數(shù)據(jù)的時(shí)間Ttrans為

一次轉(zhuǎn)發(fā)消息數(shù)據(jù)的總傳輸時(shí)間Thop包括信道碰撞時(shí)間Tcol、信道空閑時(shí)間Tidle和成功發(fā)送時(shí)間Ttrans，由式（5）、式（8）和式（9）得到。

假設(shè)消息從道路最前方車輛節(jié)點(diǎn)通過多跳廣播轉(zhuǎn)發(fā)到最后方車輛節(jié)點(diǎn)，一共需要次廣播轉(zhuǎn)發(fā)，可以得到端到端的多跳廣播延時(shí)T為

定義相鄰2個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)之間的距離為單跳轉(zhuǎn)發(fā)距離d。d的值越大，下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)距離當(dāng)前轉(zhuǎn)發(fā)點(diǎn)越遠(yuǎn)。圖5顯示了d從0 m變化到290 m時(shí)，端到端的多跳廣播延時(shí)的變化情況。從理論計(jì)算和NS2仿真結(jié)果看出，端到端的延時(shí)T的變化趨勢(shì)和車輛密度α直接相關(guān)。當(dāng)車輛密度小時(shí)（α=0.1輛/米），選擇較近的節(jié)點(diǎn)來轉(zhuǎn)發(fā)廣播消息會(huì)導(dǎo)致過多的轉(zhuǎn)發(fā)次數(shù)和較大的廣播延時(shí)。因此，端到端的廣播延時(shí)T隨著距離d的增大而減小。但是當(dāng)車輛密度變大后，選擇最遠(yuǎn)的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)將經(jīng)歷過多的信道碰撞，從而加大端到端延時(shí)。如圖5所示，當(dāng)α為0.7輛/米時(shí)，選擇較近或較遠(yuǎn)的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)都會(huì)增加端到端的廣播延時(shí)。

4.2 協(xié)議設(shè)計(jì)

由4.1節(jié)的分析可以知道多跳廣播延時(shí)是單跳距離d的凸性函數(shù)，即在不同的車輛密度下，有且僅有一個(gè)最優(yōu)單跳距離dopt使多跳廣播延時(shí)最小化。為了得到盡可能小的多跳延時(shí)，單跳距離選取的原則是通過得到信道沖突和覆蓋速度的合理折中以實(shí)現(xiàn)多跳延時(shí)的最小化。這實(shí)際上是一個(gè)凸優(yōu)化問題，可描述為求延時(shí)T(d)的最小值T(dopt)。

圖5 端到端的多跳廣播延時(shí)的變化情況

其中，T(d)描述了多跳廣播延時(shí)與單跳距離大小的函數(shù)關(guān)系，R是傳輸半徑范圍。為了保證端到端的傳輸延時(shí)最小，可以依據(jù)一階導(dǎo)數(shù)T′(d)=0來求解得到最優(yōu)距離dopt的值，如式(13)所示。

其中，lambertw函數(shù)為乘積對(duì)數(shù)函數(shù)[14]。為了實(shí)現(xiàn)該目標(biāo)，本文設(shè)計(jì)了根據(jù)車輛密度自適應(yīng)地選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)以調(diào)節(jié)單跳轉(zhuǎn)發(fā)距離的VDF協(xié)議。VDF根據(jù)車輛密度計(jì)算當(dāng)前節(jié)點(diǎn)距轉(zhuǎn)發(fā)節(jié)點(diǎn)的最優(yōu)距離dopt，選出合適的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)F，以實(shí)現(xiàn)網(wǎng)絡(luò)延時(shí)的最小化。

首先，在IEEE 802.11p協(xié)議中，各車輛節(jié)點(diǎn)會(huì)周期性發(fā)送“心跳”信標(biāo)（beacon）分組向周圍鄰居節(jié)點(diǎn)廣播自己的ID號(hào)和位置信息。VDF利用了beacon分組來與周圍節(jié)點(diǎn)共享實(shí)時(shí)的節(jié)點(diǎn)位置信息，同時(shí)在beacon分組中設(shè)置“轉(zhuǎn)發(fā)節(jié)點(diǎn)標(biāo)識(shí)位”（缺省值為0），用以區(qū)分beacon分組是否由當(dāng)前轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)送。各節(jié)點(diǎn)依據(jù)收到的beacon分組信息更新其鄰居節(jié)點(diǎn)列表neighbour_list，統(tǒng)計(jì)其鄰居節(jié)點(diǎn)個(gè)數(shù)，計(jì)算出車輛密度α，同時(shí)，依據(jù)GPS信息和轉(zhuǎn)發(fā)節(jié)點(diǎn)的beacon分組計(jì)算自己距離轉(zhuǎn)發(fā)節(jié)點(diǎn)的距離df。得到車輛密度后，依式(13)得到最優(yōu)單跳轉(zhuǎn)發(fā)距離dopt。

各節(jié)點(diǎn)收到消息數(shù)據(jù)分組后，先判斷所收到的是否為新分組，如果是，則計(jì)算等待時(shí)隙CW，同時(shí)計(jì)時(shí)器開始計(jì)時(shí)，當(dāng)計(jì)時(shí)器超時(shí)后將發(fā)送該消息數(shù)據(jù)分組。其中，為了與IEEE802.11p協(xié)議兼容，VDF采用了分布式的控制策略，各節(jié)點(diǎn)依據(jù)自己距離轉(zhuǎn)發(fā)節(jié)點(diǎn)的距離df來計(jì)算其競(jìng)爭(zhēng)窗口CW值

其中，傳輸半徑R、最大競(jìng)爭(zhēng)窗口CWmax和最小競(jìng)爭(zhēng)窗口CWmin的值如表1所示。從式（14）可見，各節(jié)點(diǎn)分配了不同等待廣播時(shí)隙，距發(fā)送方的距離df與最優(yōu)距離dopt最接近的節(jié)點(diǎn)獲得最小的競(jìng)爭(zhēng)窗口CW值，也就具有最大概率成為中繼節(jié)點(diǎn)來首先轉(zhuǎn)發(fā)廣播消息。當(dāng)某個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)廣播消息后，則成為新的轉(zhuǎn)發(fā)節(jié)點(diǎn)，并在其后所發(fā)送的beacon分組中將“轉(zhuǎn)發(fā)節(jié)點(diǎn)標(biāo)識(shí)位”設(shè)置為1，向其鄰居節(jié)點(diǎn)通告該節(jié)點(diǎn)已經(jīng)成為轉(zhuǎn)發(fā)節(jié)點(diǎn)。

如果節(jié)點(diǎn)所收到的消息數(shù)據(jù)分組不是新分組，這表明其他節(jié)點(diǎn)已經(jīng)承擔(dān)了中繼任務(wù)并轉(zhuǎn)發(fā)該消息。因此，當(dāng)前節(jié)點(diǎn)不再轉(zhuǎn)發(fā)該消息，計(jì)時(shí)器停止計(jì)時(shí)。

VDF協(xié)議的核心代碼如下。

5 仿真與實(shí)驗(yàn)

本節(jié)通過NS2仿真實(shí)驗(yàn)對(duì)Rec、IEEE 802.11p和VDF進(jìn)行性能評(píng)估，其中，IEEE 802.11p協(xié)議采取缺省的隨機(jī)退避機(jī)制。實(shí)驗(yàn)性能評(píng)價(jià)指標(biāo)包括廣播延時(shí)和廣播次數(shù)。1）廣播延時(shí)定義為消息從第一個(gè)發(fā)送方到最后一個(gè)接收方的傳輸延時(shí)。作為網(wǎng)絡(luò)傳輸?shù)年P(guān)鍵性能指標(biāo)，廣播延時(shí)越小，數(shù)據(jù)消息的傳播速度越快，越能滿足安全預(yù)警等應(yīng)用的快速傳輸要求。2）廣播次數(shù)包括消息成功廣播次數(shù)和因?yàn)樾诺琅鲎捕〉膹V播次數(shù)。從第3節(jié)的分析可以知道，傳輸范圍越大，導(dǎo)致信道碰撞概率和廣播失敗次數(shù)增加，但傳輸范圍越小則意味著每次廣播覆蓋的范圍越小，需要更多數(shù)量的中繼傳輸。因此，只有選擇合適的中繼轉(zhuǎn)發(fā)節(jié)點(diǎn)，才能得到最佳的傳輸范圍以避免過多的失敗廣播或中繼廣播。

實(shí)驗(yàn)拓?fù)浣Y(jié)構(gòu)采用如圖1所示的5 km 4車道公路場(chǎng)景。所有車輛節(jié)點(diǎn)均衡分布在道路上，并以10 beacon/s的速率發(fā)送100 byte的beacon消息來聲明各自的ID和位置信息。同時(shí)，為了模擬智能交通系統(tǒng)中其他應(yīng)用所產(chǎn)生的背景流量，設(shè)定所有車輛節(jié)點(diǎn)以10 packet/s的速度發(fā)送1.5 KB大小的數(shù)據(jù)分組給它們的鄰居節(jié)點(diǎn)，其他的網(wǎng)絡(luò)參數(shù)設(shè)置如表1所示。實(shí)驗(yàn)中每組測(cè)試重復(fù)10次，并根據(jù)置信區(qū)間為95%來統(tǒng)計(jì)平均結(jié)果。

在實(shí)驗(yàn)中，模擬了2種典型的應(yīng)用服務(wù)。1) 事故預(yù)警：當(dāng)交通事故發(fā)生時(shí)，事故車輛利用多跳廣播向后面所有車輛發(fā)送事故預(yù)警消息。測(cè)試可以分為單源和多源場(chǎng)景，在單源的場(chǎng)景中只有隊(duì)首車輛節(jié)點(diǎn)是事故預(yù)警消息源，而多源場(chǎng)景中會(huì)隨機(jī)選擇一定數(shù)量的車輛節(jié)點(diǎn)為消息源。2) 在線游戲：各用戶通過周期性的多跳廣播來將數(shù)據(jù)發(fā)送到其他所有用戶。由于游戲數(shù)據(jù)的傳播速度直接影響著用戶體驗(yàn)，通過改變數(shù)據(jù)發(fā)送間隔以在不同信道負(fù)載下來測(cè)試協(xié)議的延時(shí)性能。最后，本文模擬了一個(gè)高速公路多車追尾連鎖事故的場(chǎng)景，用以分析在交通事故發(fā)生時(shí)不同協(xié)議的避險(xiǎn)效果。

5.1 單源場(chǎng)景下事故預(yù)警應(yīng)用的性能比較

本實(shí)驗(yàn)測(cè)試在單源場(chǎng)景下，當(dāng)車輛節(jié)點(diǎn)分別采用IEEE 802.11p、Rec和VDF協(xié)議進(jìn)行多跳廣播事故預(yù)警時(shí)的廣播延時(shí)和廣播次數(shù)。實(shí)驗(yàn)中選擇道路上最前車輛節(jié)點(diǎn)作為預(yù)警消息的發(fā)送源，以0.05 s作為發(fā)送間隔周期性發(fā)送2 KB大小的預(yù)警消息分組。首先，測(cè)試不同網(wǎng)絡(luò)負(fù)載下的協(xié)議性能。為了控制網(wǎng)絡(luò)負(fù)載，逐漸增加道路上車輛節(jié)點(diǎn)的數(shù)量，車輛密度從50輛/千米增加到250輛/千米。

如圖6(a)的結(jié)果所示，當(dāng)車輛密度為50輛/千米時(shí)，VDF和Rec取得了相近的延時(shí)性能，而IEEE 802.11p的延時(shí)相對(duì)較高。這是因?yàn)檐囕v密度較小時(shí)，IEEE 802.11p由于不考慮車輛密度因素，隨機(jī)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，單跳的平均轉(zhuǎn)發(fā)距離較小，預(yù)警消息的傳輸速度最低。隨著車輛密度的提高，信道沖突的增加導(dǎo)致了3種協(xié)議的多跳廣播傳輸延時(shí)都在變大。但Rec的延時(shí)增長(zhǎng)速度明顯高于其他2種協(xié)議。當(dāng)車輛密度為250輛/千米時(shí)，Rec的延時(shí)分別比VDF和IEEE 802.11p高約34%和15%。這是由于Rec雖然通過選擇傳輸范圍內(nèi)最遠(yuǎn)的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)提高了消息覆蓋范圍，但同時(shí)也造成了過高的無線信道的競(jìng)爭(zhēng)退避延時(shí)。VDF協(xié)議根據(jù)接收節(jié)點(diǎn)接收范圍內(nèi)車輛密度決定下一次傳輸范圍，降低了沖突退避延時(shí)和重傳概率，延時(shí)性能最好。

圖6 單源場(chǎng)景下改變車輛密度的事故預(yù)警消息傳輸性能

從圖6(b)可以看出，由于IEEE 802.11p隨機(jī)選擇轉(zhuǎn)發(fā)中繼節(jié)點(diǎn)，需要更多次的中繼廣播，造成其廣播數(shù)量最高。相對(duì)于IEEE 802.11p，Rec減少了中繼廣播，其廣播次數(shù)降低了約20%。當(dāng)密度變大時(shí)，VDF減小了單跳轉(zhuǎn)發(fā)距離，從而降低了信道沖突概率和重傳次數(shù)，獲得了最低的總廣播次數(shù)。

實(shí)際上，車輛移動(dòng)的差異性會(huì)導(dǎo)致網(wǎng)絡(luò)拓?fù)浜蛙囕v密度不斷變化。接下來測(cè)試在不同車輛速度差異度下的協(xié)議性能。其中，所有車輛初始以125輛/千米的密度均勻分布在道路上。實(shí)驗(yàn)開始后車輛開始移動(dòng)，平均速度為50 km/h，各車速率服從均勻分布，其最大速度差異度從10%增加至50%。

如圖7(a)所示，在不同的車速差異度下，VDF始終獲得了最小的多跳廣播傳輸延時(shí)。圖7(b)中，Rec和VDF的廣播次數(shù)相似，相對(duì)IEEE 802.11p降低了約20%。以上結(jié)果說明在動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)渲校词管囕v密度不斷變化，VDF協(xié)議仍然體現(xiàn)了較好的健壯性和可靠性。

圖7 單源場(chǎng)景下改變車速差異度的事故預(yù)警消息傳輸性能

5.2 多源場(chǎng)景下事故預(yù)警應(yīng)用的性能比較

交通事故發(fā)生時(shí)，除了單事故源的情況，也有可能多個(gè)車輛節(jié)點(diǎn)同時(shí)預(yù)警并發(fā)送交通預(yù)警消息。此時(shí)多個(gè)并發(fā)廣播的交通預(yù)警消息之間也會(huì)發(fā)生信道碰撞。因此，本實(shí)驗(yàn)在固定車輛密度的情況下考察多源場(chǎng)景下的預(yù)警消息廣播性能。實(shí)驗(yàn)中預(yù)警消息發(fā)送的車輛節(jié)點(diǎn)隨機(jī)選擇，并且數(shù)量從當(dāng)前道路車輛總數(shù)的5%逐步增加到25%。預(yù)警消息的發(fā)送間隔時(shí)間和分組大小分別設(shè)定為0.05 s和2 KB，車輛密度固定為125輛/千米。

從圖8(a)可以看出，3種協(xié)議的傳輸延時(shí)都隨著發(fā)送節(jié)點(diǎn)數(shù)量的增加而增長(zhǎng)。而且由于多個(gè)車輛節(jié)點(diǎn)并發(fā)廣播加劇信道沖突，多源場(chǎng)景下的多跳廣播延時(shí)都要高于對(duì)應(yīng)的單源場(chǎng)景。在3種協(xié)議中，隨著源節(jié)點(diǎn)的數(shù)量增多，由于其最遠(yuǎn)節(jié)點(diǎn)轉(zhuǎn)發(fā)的策略，Rec的延時(shí)增長(zhǎng)速度最快。而相對(duì)于其他方法，因?yàn)檫x擇較近的節(jié)點(diǎn)作為承擔(dān)轉(zhuǎn)發(fā)任務(wù)，降低了信道沖突的概率，VDF的延時(shí)性能最佳。其中，當(dāng)源節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)為25%時(shí)，VDF的延時(shí)相對(duì)Rec和IEEE 802.11p分別降低了約29%和19%。

如圖8(b)所示，在多源場(chǎng)景下各協(xié)議的廣播次數(shù)比單源場(chǎng)景都有增高，而IEEE 802.11p的廣播次數(shù)仍然是最高的。與單源場(chǎng)景類似，由于VDF避免了過多的重傳廣播，其總廣播次數(shù)在源節(jié)點(diǎn)數(shù)據(jù)量較多時(shí)比Rec還要小，取得了最好的性能。

圖8 多源場(chǎng)景下的事故預(yù)警消息傳輸性能

5.3 在線游戲應(yīng)用的性能比較

在線游戲是車載無線網(wǎng)中的一種典型娛樂應(yīng)用，各節(jié)點(diǎn)通過廣播通信將游戲數(shù)據(jù)發(fā)送給其他游戲參與節(jié)點(diǎn)，數(shù)據(jù)的實(shí)時(shí)傳輸性能直接決定用戶體驗(yàn)。同時(shí)，相對(duì)事故預(yù)警應(yīng)用僅需要傳輸預(yù)警消息，在線游戲應(yīng)用需要所有用戶實(shí)時(shí)并發(fā)傳輸大量數(shù)據(jù)，所以保證傳輸可靠性就變得十分重要。本實(shí)驗(yàn)通過調(diào)節(jié)數(shù)據(jù)發(fā)送的間隔來測(cè)試傳輸延時(shí)和成功接收率。實(shí)驗(yàn)設(shè)定4車道下，車輛密度為每公里每車道24輛（α=100輛/千米），隨機(jī)選擇50輛車作為游戲用戶，各用戶周期性發(fā)送2 000 byte的數(shù)據(jù)分組給其他用戶。分組發(fā)送間隔依次設(shè)置為10 ms、50 ms和100 ms。

從圖9(a)可以看出，當(dāng)分組發(fā)送間隔為10 ms時(shí)，由于較高的數(shù)據(jù)發(fā)送速率，各協(xié)議的延時(shí)都大于3.5 s。當(dāng)分組發(fā)送間隔為50 ms或100 ms時(shí)，3個(gè)協(xié)議的延時(shí)都降到0.8 s以下。注意到50 ms和100 ms的分組發(fā)送間隔下延時(shí)相差并不大，其原因在于發(fā)送速率還不夠高，競(jìng)爭(zhēng)還未造成信道飽和。圖9(b)比較了各協(xié)議的節(jié)點(diǎn)傳輸成功概率。隨著分組發(fā)送間隔變大，由于信道沖突率降低，各協(xié)議的傳輸成功概率都不斷提高。相對(duì)其他協(xié)議，在不同發(fā)送間隔下，VDF對(duì)不同信道競(jìng)爭(zhēng)狀態(tài)都顯示較好的適應(yīng)性，以較小覆蓋范圍轉(zhuǎn)發(fā)廣播消息，取得最低延時(shí)和最高可靠性。

圖9 在線游戲應(yīng)用的傳輸性能

5.4 高速公路多車追尾連鎖事故的避險(xiǎn)性能比較

本實(shí)驗(yàn)測(cè)試車輛隊(duì)列發(fā)生追尾事故時(shí)，各廣播協(xié)議的避險(xiǎn)效果。實(shí)驗(yàn)考察車輛密度為每公里每車道40輛的4車道高速公路行駛場(chǎng)景。其中，選擇30輛車組成車輛行駛速度為120 km/h的同向行駛車隊(duì)，車間距離為25 m。當(dāng)隊(duì)首車輛發(fā)生事故時(shí)，會(huì)以0.05 s的周期發(fā)送2 KB大小的預(yù)警消息分組，同時(shí)以8 m/s2的加速度來降低行駛速度。如果前后兩車車距小于4 m時(shí)，則認(rèn)為發(fā)生了追尾事故，此時(shí)兩車都會(huì)以8 m/s2的加速度來降速直至停車。同時(shí)假設(shè)當(dāng)發(fā)生以下2種情況時(shí)，駕駛員能剎車降速以避險(xiǎn)：1) 當(dāng)前車相鄰的前方兩車發(fā)生了事故；2)收到了前方任一車輛轉(zhuǎn)發(fā)的事故預(yù)警消息。當(dāng)駕駛員剎車后，車輛將以8 m/s2的加速度降速。設(shè)定駕駛員的反應(yīng)時(shí)間在0.75～1.5 s均衡分布。

實(shí)驗(yàn)考察Rec和VDF 2個(gè)協(xié)議的避險(xiǎn)性能指標(biāo)：1) 前后兩車停車或追尾時(shí)的相對(duì)速度，如果相對(duì)速度大于0，則說明兩車發(fā)生追尾事故，而且相對(duì)速度越大，事故危害越大；2) 前后兩車停車后的車距，如果車距小于4 m，則說明兩車最終還是發(fā)生追尾事故。

圖10對(duì)比了Rec和VDF協(xié)議下前后兩車停車或追尾時(shí)的相對(duì)速度。0～3號(hào)車間的相對(duì)速度都大于0，這說明當(dāng)隊(duì)首車輛（0號(hào)車）發(fā)生事故時(shí)，由于車速過快，其后1～3號(hào)車都發(fā)生了追尾。其余的車輛則依據(jù)所接收的事故預(yù)警信息來降速避險(xiǎn)。圖10(a)和圖10(b)中結(jié)果對(duì)比顯示出相對(duì)于Rec協(xié)議，VDF協(xié)議降低了多跳廣播延時(shí)，從而保證更多車輛節(jié)點(diǎn)有效避險(xiǎn)。

圖10 前后兩車相對(duì)速度

圖11顯示了Rec和VDF協(xié)議下前后兩車停車后的車距?？梢钥闯?，由于存在駕駛員反應(yīng)時(shí)間的差異性，各車間的車距各不相同。對(duì)比圖11(a)和圖11(b)，VDF協(xié)議下更多車輛的前后車距大于4 m，這說明VDF取得了更好的多跳廣播預(yù)警避險(xiǎn)性能。

圖11 前后兩車車距

6 結(jié)束語

本文提出了一種車載無線網(wǎng)絡(luò)中基于車輛密度的多跳廣播協(xié)議，這種協(xié)議沒有選擇最遠(yuǎn)的可達(dá)節(jié)點(diǎn)來進(jìn)行中繼轉(zhuǎn)發(fā)，而是根據(jù)車輛密度自適應(yīng)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，從而緩解信道競(jìng)爭(zhēng)，有效地降低了多跳廣播延時(shí)和廣播次數(shù)。NS2仿真實(shí)驗(yàn)表明，相對(duì)Rec和IEEE 802.11p協(xié)議，VDF在事故預(yù)警和在線游戲2種典型車載無線應(yīng)用中都取得較好的性能。為了避免車輛節(jié)點(diǎn)高移動(dòng)性的影響，未來擬研究車載無線網(wǎng)中基于移動(dòng)預(yù)測(cè)的轉(zhuǎn)發(fā)節(jié)點(diǎn)優(yōu)選方法，并在真實(shí)網(wǎng)絡(luò)進(jìn)一步測(cè)試協(xié)議的性能。

[1]PANICHPAPIBOON S,PATTARAATIKOM W.A review of information dissemination protocols for vehicular ad hoc networks [J].IEEE Communications Surveys and Tutorials,2012,14 (3):784-798.

[2]ZHANG J,MA X,WU T.Performance modeling and analysis of emergency message propagation in vehicular ad hoc networks [J].Wireless Communications and Mobile Computing,2014,14(3):366-379.

[3]XIANG Q,CHEN X,KONG L.et al.Data preference matters:a new perspective of safety data dissemination in vehicular ad hoc networks[C]// In Proceedings of INFOCOM,2015.

[4]IEEE 802.11p/D10.0,Part11:wireless LAN medium access control (MAC) and the physical layer (PHY) specifications:amendment 7:wireless access in vehicular environment,draft 7.0 [S].2010.

[5]KORKMAZ G,EKICI E,OZGUNER F,et al.Urban multihop broadcast protocol for inter-vehicle communication systems [C]// ACM Intl Workshop on Vehicular Ad Hoc Networks.2004:76-85.

[6]LIU J,YANG Z,STOJMENOVIC I.Receiver consensus:on-time warning delivery for vehicular ad-hoc networks [C]// In Proceedings of ICDCS,2012:386-395.

[7]PALAZZI C,ROCCETTI M,FERRETTI S.An inter vehicular communication architecture for safety and entertainment [J].IEEE Transactions on Intelligent Transportation Systems,2010,11(1):90-99.

[8]ZHOU L,ZHANG Y,SONG K,et al.Distributed media services in P2P-based vehicular networks[J].IEEE Transactions on Vehicular Technology,2011,60(2):692-703.

[9]WEGENER A,HELLBRUCK H,FISCHER S.et al.AutoCast:an adaptive data dissemination protocol for traffic information systems [C]// In Proceedings of VTC,2007:1947-1951.

[10]SLAVIK M,MAHGOUB I.Stochastic broadcast for VANET [C]// In Proceedings of CCNC,2010:1-5.

[11]The network simulator [EB/OL].http://www.isi.edu/nsnam/ns/

[12]CALI F.CONTI M,GREGORI E.Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit [J].IEEE/ACM Transactions on Networking,2000,8(6):785-799.

[13]DENG D J,KE C H,CHEN H H.Contention window optimization for IEEE 802.11 DCF access control [J].IEEE Transactions Wireless Communication.2008,7(12):5129-5135.

[14]CHATZIGEORGIOU I.Bounds on the Lambert function and their application to the outage analysis of user cooperation[J].IEEE Communications Letters,2013,17 (8):1505-1508.

黃家瑋（1976-），男，湖南長(zhǎng)沙人，博士，中南大學(xué)副教授，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)算法和協(xié)議。

鐘少華（1989-），男，湖南長(zhǎng)沙人，中南大學(xué)碩士生，主要研究方向?yàn)檐囕d無線網(wǎng)絡(luò)的MAC協(xié)議。

劉聯(lián)海（1978-），男，福建廈門人，中南大學(xué)講師、博士生，主要研究方向?yàn)闊o線網(wǎng)絡(luò)協(xié)議設(shè)計(jì)。

王建新（1969-），男，湖南邵陽人，博士，中南大學(xué)教授，主要研究方向?yàn)榫W(wǎng)絡(luò)理論優(yōu)化。

Vehicle density based multihop broadcast protocol in VANET

HUANG Jia-wei,ZHONG Shao-hua,LIU Lian-hai,WANG Jian-xin
(School of Information Science and Engineering,Central South University,Changsha 410083,China)

In vehicular ad hoc networks (VANET),the medium access control (MAC) protocol was of crucial importance to provide time-critical multihop broadcast.Contemporary multihop broadcast protocols in VANET usually choose the farthest node in broadcast range as the forwarder to reduce the number of forwarding hops.However,it was demonstrated that the farthest forwarder may experience long contention delay in case of high vehicle density.An IEEE 802.11p-based multihop broadcast protocol vehicle density based forwarding (VDF) was proposed,which adaptively chose the forwarder according to the vehicle density.The evaluation results in safety warning and online game applications show that,VDF could shorten broadcast delay by achieving the proper trade-off between the contention delay and coverage speed.

VANET,MAC,broadcast,IEEE 802.11p

The National Natural Science Foundation of China (No.61103204,No.61572530,No.61402541,No.61462007,No.61402542)

TP393

A

10.11959/j.issn.1000-436x.2016233

2015-10-26；

2016-11-30

資助項(xiàng)目（No.61103204,No.61572530,No.61402541,No.61462007,No.61402542）