車(chē)聯(lián)網(wǎng)中基于拓?fù)涓兄姆植际綇V播路由研究

馬金忠 王文杰 田彥山?

摘 要：針對(duì)車(chē)聯(lián)網(wǎng)基于距離等待轉(zhuǎn)發(fā)的廣播路由存在“慢反應(yīng)”和“局部廣播風(fēng)暴”的問(wèn)題，研究了基于MAC的廣播路由和基于概率的廣播路由，提出了一種發(fā)送節(jié)點(diǎn)依靠beacon消息以自組織方式感知局部拓?fù)湫畔?，并將抽象出的鄰居?jié)點(diǎn)的數(shù)量和分布等特征信息嵌入到廣播報(bào)文中，接收節(jié)點(diǎn)基于概率廣播路由動(dòng)態(tài)分配轉(zhuǎn)發(fā)優(yōu)先級(jí)的分布式廣播路由協(xié)議。該協(xié)議無(wú)需路邊單元的協(xié)助，節(jié)點(diǎn)以自適應(yīng)方式分布轉(zhuǎn)發(fā)安全消息，網(wǎng)絡(luò)開(kāi)銷(xiāo)較小。仿真結(jié)果表明，所設(shè)計(jì)的廣播協(xié)議具有更低的時(shí)延和更少的冗余，能更好地適應(yīng)車(chē)聯(lián)網(wǎng)拓?fù)涞膭?dòng)態(tài)變化。

關(guān)鍵詞：廣播協(xié)議;轉(zhuǎn)發(fā)策略;局部信息感知;車(chē)聯(lián)網(wǎng);TSBP協(xié)議;拓?fù)?/p>

中圖分類(lèi)號(hào)：TP393.04 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2019）05-00-06

0 引 言

車(chē)聯(lián)網(wǎng)的安全應(yīng)用在減少交通事故、提高道路交通效率、保證國(guó)民經(jīng)濟(jì)發(fā)展、保障人民生命財(cái)產(chǎn)安全方面起到舉足輕重的作用，安全消息快速分發(fā)到事故后方數(shù)千米區(qū)域內(nèi)，使得駛向事故位置的車(chē)輛能夠避免連環(huán)碰撞，保障車(chē)輛安全行駛[1]。由于車(chē)載設(shè)備的通信距離有限，通常通過(guò)多跳廣播來(lái)實(shí)現(xiàn)安全消息快速、可靠地分發(fā)，而多跳廣播的核心是中繼轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇?，F(xiàn)有的多跳廣播策略按照中繼節(jié)點(diǎn)的確定方式主要分為兩類(lèi)：一類(lèi)是基于發(fā)送端指定中繼（Sender-based）的多跳轉(zhuǎn)發(fā)策略;另一類(lèi)是基于接收端分布式中繼（Receiver-based）的多跳轉(zhuǎn)發(fā)策略。Sender-based策略的優(yōu)點(diǎn)是能夠?qū)崿F(xiàn)安全消息的快速分發(fā)，且車(chē)流密度的變化對(duì)網(wǎng)絡(luò)冗余影響較小，其缺點(diǎn)是在車(chē)輛拓?fù)淇焖僮兓木W(wǎng)絡(luò)中傳輸可靠性下降，這是因?yàn)樵摬呗缘某晒σ蕾囉诰珳?zhǔn)的鄰居信息，在車(chē)輛拓?fù)淇焖僮兓木W(wǎng)絡(luò)中信道衰落和干擾嚴(yán)重，導(dǎo)致發(fā)送端指定的中繼節(jié)點(diǎn)接收?qǐng)?bào)文失敗，從而造成廣播中斷。Receiver-based策略的優(yōu)點(diǎn)是能最大限度覆蓋安全消息的廣播范圍，原因在于這類(lèi)轉(zhuǎn)發(fā)策略規(guī)定地理上最遠(yuǎn)的候選接收節(jié)點(diǎn)優(yōu)先轉(zhuǎn)發(fā);這類(lèi)策略的另一優(yōu)點(diǎn)是節(jié)點(diǎn)在正確接收?qǐng)?bào)文后以分布式方式協(xié)作轉(zhuǎn)發(fā)，以保證多跳轉(zhuǎn)發(fā)的連續(xù)性。基于上述優(yōu)點(diǎn)，Receiver-based策略受到了研究者的廣泛關(guān)注，但該類(lèi)策略中候選節(jié)點(diǎn)并非對(duì)發(fā)送節(jié)點(diǎn)的所有候選鄰居節(jié)點(diǎn)全部徹知，當(dāng)車(chē)輛處于密集網(wǎng)絡(luò)中時(shí)會(huì)發(fā)生“局部廣播風(fēng)暴”，而當(dāng)車(chē)輛處于稀疏網(wǎng)絡(luò)中時(shí)會(huì)產(chǎn)生“慢反應(yīng)”的問(wèn)題。

針對(duì)Receiver-based策略存在的問(wèn)題，本文在前人研究成果的基礎(chǔ)上，對(duì)車(chē)聯(lián)網(wǎng)局部拓?fù)湫畔⒏兄夹g(shù)進(jìn)行了研究，提出了基于拓?fù)涓兄姆植际綇V播路由協(xié)議（Topology Sensing Broadcast Protocol，TSBP）。TSBP不依賴路邊單元，是完全自組織的路由協(xié)議，發(fā)送節(jié)點(diǎn)將TSBP包頭添加到beacon消息中感知其局部拓?fù)湫畔?，這些信息能夠協(xié)助接收節(jié)點(diǎn)統(tǒng)一分配轉(zhuǎn)發(fā)概率和轉(zhuǎn)發(fā)時(shí)延。這種獲取車(chē)聯(lián)網(wǎng)內(nèi)車(chē)輛分布狀況用于中繼決策的方法，網(wǎng)絡(luò)開(kāi)銷(xiāo)代價(jià)較小，能夠適應(yīng)車(chē)聯(lián)網(wǎng)中車(chē)輛拓?fù)淇焖僮兓沫h(huán)境，如城市道路和高速道路，應(yīng)用前景較為廣闊。

1 問(wèn)題與挑戰(zhàn)

由于Receiver-based中繼轉(zhuǎn)發(fā)策略合理利用了空間信道的廣播特性，適合安全消息的定向擴(kuò)散，因而是研究者最為關(guān)注的一類(lèi)安全消息廣播策略。而接收端分布式轉(zhuǎn)發(fā)的廣播協(xié)議中最常見(jiàn)的是基于距離的優(yōu)先級(jí)調(diào)度機(jī)制，其轉(zhuǎn)發(fā)等待時(shí)延Dwait的經(jīng)典公式見(jiàn)式（1）：

式中：R表示車(chē)載設(shè)備最大通信距離;d表示收發(fā)節(jié)點(diǎn)間的距離;Dmax表示接收節(jié)點(diǎn)最大等待時(shí)延。由式（1）可知，接收節(jié)點(diǎn)與上一跳發(fā)送節(jié)點(diǎn)距離越遠(yuǎn)，其等待時(shí)延越小，意味著其轉(zhuǎn)發(fā)優(yōu)先級(jí)越高，這種機(jī)制使等待時(shí)延大的節(jié)點(diǎn)的轉(zhuǎn)發(fā)受到了抑制，從而減少了網(wǎng)絡(luò)冗余。另外，在每一跳中都是與發(fā)送節(jié)點(diǎn)距離最遠(yuǎn)的節(jié)點(diǎn)優(yōu)先轉(zhuǎn)發(fā)，這樣能夠使安全消息快速覆蓋事故車(chē)輛之后的風(fēng)險(xiǎn)區(qū)域。由于相鄰車(chē)輛并發(fā)數(shù)據(jù)會(huì)加劇碰撞，加之信道衰落等影響可能導(dǎo)致廣播中斷，針對(duì)這種情況，Omar H A[2]等人提出了改進(jìn)算法—時(shí)隙1堅(jiān)持算法（Slotted-1）。Slotted-1算法在廣播方向上把風(fēng)險(xiǎn)區(qū)域劃分為許多小段（segment），每個(gè)小段內(nèi)的車(chē)輛節(jié)點(diǎn)轉(zhuǎn)發(fā)優(yōu)先級(jí)相同，與事故車(chē)輛距離越遠(yuǎn)的小段內(nèi)的車(chē)輛轉(zhuǎn)發(fā)優(yōu)先級(jí)越高，其轉(zhuǎn)發(fā)等待時(shí)延Dwait見(jiàn)公式（2）：

式中：σ為一跳最小時(shí)延;Ns為一跳通信范圍內(nèi)劃分的segment數(shù)，其余參數(shù)與式（1）相同。在該算法中某節(jié)點(diǎn)接收到上一跳節(jié)點(diǎn)廣播的報(bào)文后，首先等待一個(gè)靜態(tài)時(shí)延Dintend，在這段時(shí)間內(nèi)該節(jié)點(diǎn)接收來(lái)自低優(yōu)先級(jí)節(jié)點(diǎn)廣播的副本。當(dāng)靜態(tài)時(shí)延等待計(jì)時(shí)器超時(shí)后，該節(jié)點(diǎn)確定了離自己最近的節(jié)點(diǎn)，用它們之間的距離代入公式（2）計(jì)算Dwait。對(duì)于接收節(jié)點(diǎn)而言，距離自己最近的節(jié)點(diǎn)實(shí)際上就是距離上一跳發(fā)送節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)，這一過(guò)程意味著讓距離事故車(chē)輛最遠(yuǎn)的segment內(nèi)的節(jié)點(diǎn)具有最小的等待時(shí)延（如圖1所示的節(jié)點(diǎn)E和F），在減少冗余的同時(shí)最大限度覆蓋了地理范圍。Slotted-1優(yōu)先級(jí)調(diào)度示意如圖1所示。

然而這類(lèi)基于等待的廣播路由性能易受固定參數(shù)Dintend和Ns的影響。圖2所示為稀疏網(wǎng)絡(luò)，該網(wǎng)絡(luò)中車(chē)輛分布不均勻，雖然高優(yōu)先級(jí)segment內(nèi)沒(méi)有車(chē)輛，但是位于低優(yōu)先級(jí)segment內(nèi)的車(chē)輛節(jié)點(diǎn)也不能立即轉(zhuǎn)發(fā)消息，必須在靜態(tài)時(shí)延等待計(jì)時(shí)器超時(shí)后才能轉(zhuǎn)發(fā)，延緩了消息的廣播，此即“慢反應(yīng)”問(wèn)題。又如圖3所示為密集的網(wǎng)絡(luò)，處于同一segment內(nèi)的車(chē)輛節(jié)點(diǎn)較為聚集，因?yàn)樗鼈兙哂邢嗤霓D(zhuǎn)發(fā)優(yōu)先級(jí)，所以會(huì)同時(shí)轉(zhuǎn)發(fā)數(shù)據(jù)，這種數(shù)據(jù)并發(fā)會(huì)加劇信道競(jìng)爭(zhēng)。如此一來(lái)，會(huì)導(dǎo)致兩個(gè)問(wèn)題：一是會(huì)使消息接入信道的時(shí)延增加，降低廣播有效性;二是會(huì)產(chǎn)生大量無(wú)效副本，使廣播碰撞概率增加，導(dǎo)致廣播可靠性降低，此即“局部廣播風(fēng)暴”問(wèn)題。

在城市和高速道路中，VANET具有車(chē)流密度高度動(dòng)態(tài)變化、車(chē)輛移動(dòng)速度快、信道干擾和衰落嚴(yán)重的特性，對(duì)快速、可靠地廣播安全消息提出了嚴(yán)峻挑戰(zhàn)，“慢反應(yīng)”和“局部廣播風(fēng)暴”等問(wèn)題廣泛存在于Receiver-based分布式轉(zhuǎn)發(fā)協(xié)議中，不利于“與生命相關(guān)”的安全消息的快速擴(kuò)散，其廣播性能亟需優(yōu)化。

2 相關(guān)工作

為了實(shí)現(xiàn)安全消息的快速、可靠擴(kuò)散，研究者提出了許多性能優(yōu)良的廣播協(xié)議，其中Receiver-based分布式等待競(jìng)爭(zhēng)轉(zhuǎn)發(fā)策略得到了廣泛關(guān)注，針對(duì)分布式轉(zhuǎn)發(fā)策略中廣泛存在的“慢反應(yīng)”和“局部廣播風(fēng)暴”問(wèn)題，涌現(xiàn)出許多優(yōu)化方案，其中較常見(jiàn)的包括基于MAC的廣播路由和基于概率的廣播路由。

VANET中廣泛存在的隱藏終端問(wèn)題為克服隱藏終端對(duì)通信的影響。研究者基于MAC層進(jìn)行了轉(zhuǎn)發(fā)路由的優(yōu)化，如Ekici提出UMB算法[3]，該算法將單播路由中的RTS/CTS握手機(jī)制引入消息廣播過(guò)程中，可有效減少隱藏終端的影響，提高廣播的可靠性。然而頻繁的握手必然會(huì)引入額外的控制時(shí)延，不利于安全消息的快速擴(kuò)散。對(duì)此，研究人員分別從車(chē)流密度[4]、多信道[5]、應(yīng)用場(chǎng)景[6]、優(yōu)先級(jí)配置[7]等方面對(duì)控制時(shí)延進(jìn)行了優(yōu)化。為了避免引入額外的控制時(shí)延，Yi C W[8]等通過(guò)給用戶分配不同的最小競(jìng)爭(zhēng)窗（CWmin）來(lái)區(qū)分其轉(zhuǎn)發(fā)優(yōu)先級(jí)，一般是與發(fā)送節(jié)點(diǎn)距離越遠(yuǎn)的接收節(jié)點(diǎn)具有更小的CWmin值，在競(jìng)爭(zhēng)中優(yōu)先轉(zhuǎn)發(fā)。為了控制冗余，TDC Little等規(guī)定只在某一個(gè)窄帶內(nèi)的節(jié)點(diǎn)參與競(jìng)爭(zhēng)轉(zhuǎn)發(fā)[9]，相似的優(yōu)化方案也出現(xiàn)在文獻(xiàn)[10-11]中。雖然基于競(jìng)爭(zhēng)窗的轉(zhuǎn)發(fā)策略可避免引入控制開(kāi)銷(xiāo)和時(shí)延，但由于接入機(jī)制的隨機(jī)性，最遠(yuǎn)的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)可能會(huì)競(jìng)爭(zhēng)失敗，導(dǎo)致覆蓋相同的范圍需要更多次中繼，由此降低了轉(zhuǎn)發(fā)效率。另外，在密集網(wǎng)絡(luò)中，眾多候選節(jié)點(diǎn)競(jìng)爭(zhēng)共享信道也會(huì)讓接入時(shí)延劇增，降低廣播路由算法的有效性和拓展性。

在基于等待的廣播策略中，廣播方向上所有的節(jié)點(diǎn)都可參與轉(zhuǎn)發(fā)，這一機(jī)制導(dǎo)致同優(yōu)先級(jí)的節(jié)點(diǎn)并發(fā)數(shù)據(jù)造成無(wú)效網(wǎng)絡(luò)冗余。為控制無(wú)效網(wǎng)絡(luò)冗余，N Wisitpongphan等人率先提出了基于概率的廣播策略[12]，這類(lèi)策略通過(guò)給每個(gè)車(chē)輛節(jié)點(diǎn)分配不同轉(zhuǎn)發(fā)概率的方式允許一部分節(jié)點(diǎn)參與轉(zhuǎn)發(fā)權(quán)的競(jìng)爭(zhēng)，轉(zhuǎn)發(fā)概率越高的節(jié)點(diǎn)，其成為實(shí)際中繼轉(zhuǎn)發(fā)節(jié)點(diǎn)的機(jī)會(huì)就越大，因此基于概率的廣播策略最關(guān)鍵的問(wèn)題是節(jié)點(diǎn)轉(zhuǎn)發(fā)概率的分配。加權(quán)p堅(jiān)持算法（Weighted-p）和時(shí)隙p堅(jiān)持算法（Slottedp）是基于概率的廣播策略中比較有代表性的算法。在Weighted-p算法中，車(chē)輛節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率與收發(fā)雙方的距離成正比，即與上一跳節(jié)點(diǎn)距離越遠(yuǎn)的節(jié)點(diǎn)，其轉(zhuǎn)發(fā)概率越高，從而實(shí)現(xiàn)最大的地理范圍覆蓋;Slottedp算法是在最遠(yuǎn)距離優(yōu)先轉(zhuǎn)發(fā)的基礎(chǔ)上，首先讓節(jié)點(diǎn)等待一定的時(shí)延，等待時(shí)延結(jié)束后以概率P轉(zhuǎn)發(fā)。Oh S[13]等通過(guò)觀測(cè)車(chē)輛節(jié)點(diǎn)的競(jìng)爭(zhēng)水平動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率，以降低網(wǎng)絡(luò)中的競(jìng)爭(zhēng)和冗余。還有研究者綜合考慮距離和車(chē)流密度[14-15]等分配車(chē)輛節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率，其策略是距離上一跳節(jié)點(diǎn)越遠(yuǎn)的節(jié)點(diǎn)或處于稀疏網(wǎng)絡(luò)中的節(jié)點(diǎn)具有更高的轉(zhuǎn)發(fā)概率?；诟怕实膹V播策略的優(yōu)點(diǎn)是有效降低了相鄰節(jié)點(diǎn)并發(fā)數(shù)據(jù)的可能性，一定程度上降低了競(jìng)爭(zhēng)和碰撞，從而減少網(wǎng)絡(luò)冗余。其缺點(diǎn)是廣播效率降低，這是因?yàn)樽顑?yōu)候選節(jié)點(diǎn)成為實(shí)際轉(zhuǎn)發(fā)節(jié)點(diǎn)具有一定的概率，如果地理上最遠(yuǎn)的鄰居不是實(shí)際參與中繼轉(zhuǎn)發(fā)的節(jié)點(diǎn)，廣播的一跳范圍就被縮小了。

3 廣播協(xié)議設(shè)計(jì)

如前所述，在基于距離等待的廣播策略中因Dintend和Ns的固定配置導(dǎo)致了“慢反應(yīng)”和“局部廣播風(fēng)暴”問(wèn)題的產(chǎn)生，而基于概率的廣播策略具有抑制冗余的優(yōu)勢(shì)，為避免前者的劣勢(shì)，發(fā)揮后者的優(yōu)勢(shì)，發(fā)送節(jié)點(diǎn)可利用車(chē)聯(lián)網(wǎng)中已有的beacon消息感知局部拓?fù)湫畔?，從而協(xié)助接收節(jié)點(diǎn)統(tǒng)一分配轉(zhuǎn)發(fā)時(shí)延并動(dòng)態(tài)分配轉(zhuǎn)發(fā)概率。根據(jù)以上思路，本文提出了一種基于局部拓?fù)涓兄目焖購(gòu)V播路由協(xié)議TSBP，該協(xié)議無(wú)需路邊單元協(xié)助，在完全自組織的方式下，能夠適應(yīng)車(chē)聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)的快速變化和車(chē)流密度的動(dòng)態(tài)變化。

3.1 拓?fù)涓兄夹g(shù)

beacon（DSRC中定義為BSM消息）是VANET中廣泛使用的基本安全應(yīng)用。運(yùn)動(dòng)中每一個(gè)車(chē)輛節(jié)點(diǎn)通過(guò)beacon消息以一定的周期廣播其基本狀態(tài)，當(dāng)其一跳鄰居收到beacon消息后便更新鄰居列表。鄰居列表表達(dá)的是每輛車(chē)對(duì)其局部拓?fù)涞恼J(rèn)知，主要包括鄰居的ID、位置、速度大小和方向、時(shí)間戳等信息。每輛車(chē)感知到鄰居信息后，維護(hù)一張包含鄰居的ID和位置的候選鄰居拓?fù)鋱D。發(fā)送節(jié)點(diǎn)通過(guò)廣播自己的候選鄰居拓?fù)鋱D，使所有接收節(jié)點(diǎn)都知道發(fā)送節(jié)點(diǎn)的候選鄰居分布情況，從而避免“慢反應(yīng)”和“局部廣播風(fēng)暴”問(wèn)題。但這種方式會(huì)產(chǎn)生大量網(wǎng)絡(luò)負(fù)載，增加網(wǎng)絡(luò)傳輸時(shí)延。為減少網(wǎng)絡(luò)負(fù)載，我們提出了一種發(fā)送節(jié)點(diǎn)F在廣播報(bào)文中嵌入用于接收節(jié)點(diǎn)中繼決策的有效鄰居數(shù)NeF、有效通信距離dmax、車(chē)流密度指示器TIF等特征信息的低負(fù)載解決方案，數(shù)據(jù)幀如圖4所示。

TSBP包頭由三部分組成：第一部分是安全消息基本信息，包括消息傳播的方向Direction，消息的類(lèi)型typep，消息初始產(chǎn)生的地點(diǎn)（xp，yp）和時(shí)間tp，上一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)F廣播消息的地點(diǎn)（xF，yF）和時(shí)間tF;第二部分是廣播路由需要使用的安全路由信息NeF，dmax和TIF;第三部分為擴(kuò)展域。

TSBP協(xié)議中beacon消息的安全傳輸是成敗的關(guān)鍵之一，很多能夠保證beacon消息較可靠傳輸?shù)姆桨副惶岢?，其中比較常見(jiàn)的方案是在一個(gè)廣播周期內(nèi)多次重播beacon消息，這一方法能使beacon消息的收包率達(dá)到90%以上[16]。

3.2 候選中繼優(yōu)先級(jí)調(diào)度算法

上一跳車(chē)輛節(jié)點(diǎn)Vj統(tǒng)計(jì)其感知信息，包含有效通信距離dmax、有效鄰居數(shù)Nej等，并嵌入到安全消息報(bào)文頭部，然后廣播，其一跳鄰居Vi收到廣播報(bào)文后轉(zhuǎn)發(fā)等待時(shí)延TWi，見(jiàn)式（3）：

從公式（3）可以看出，考慮dmax后，在最遠(yuǎn)segment內(nèi)的車(chē)輛以最高優(yōu)先級(jí)轉(zhuǎn)發(fā)，它們無(wú)需等待一個(gè)隨機(jī)時(shí)間來(lái)接收網(wǎng)絡(luò)內(nèi)的其他副本，即轉(zhuǎn)發(fā)等待時(shí)延為0，從而避免了轉(zhuǎn)發(fā)誤判;考慮Nej后，TSBP協(xié)議能根據(jù)候選鄰居的分布情況以及車(chē)流密度動(dòng)態(tài)調(diào)整通信范圍內(nèi)的segment數(shù)量，處于不同segment內(nèi)的候選節(jié)點(diǎn)的轉(zhuǎn)發(fā)優(yōu)先級(jí)也得以區(qū)分。

為了控制無(wú)效網(wǎng)絡(luò)冗余，在獲取了車(chē)流密度指示器TI的估值后，TSBP協(xié)議給所有候選節(jié)點(diǎn)分配了一個(gè)轉(zhuǎn)發(fā)概率PTI，如式（4）：

為盡可能減少網(wǎng)絡(luò)副本，降低無(wú)效網(wǎng)絡(luò)冗余，在公式（4）中規(guī)定1≥P1>P2>P3>0，即車(chē)輛處于越是密集的網(wǎng)絡(luò)，其轉(zhuǎn)發(fā)概率越低。

此外，在VANET中，隨著地域和時(shí)間的變化，車(chē)輛節(jié)點(diǎn)的分布也在高度動(dòng)態(tài)變化中，根據(jù)車(chē)輛節(jié)點(diǎn)位置的不同，其轉(zhuǎn)發(fā)優(yōu)先級(jí)也應(yīng)有一定的區(qū)分，與上一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)距離越遠(yuǎn)的接收節(jié)點(diǎn)其轉(zhuǎn)發(fā)概率越大。本文采用公式（5）給不同位置的車(chē)輛節(jié)點(diǎn)分配不同的轉(zhuǎn)發(fā)概率，以減少低優(yōu)先級(jí)車(chē)輛節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)產(chǎn)生的無(wú)效網(wǎng)絡(luò)冗余。

有效通信距離的計(jì)算受鄰居列表準(zhǔn)確性的直接影響，當(dāng)收發(fā)節(jié)點(diǎn)之間的距離比有效通信距離大時(shí)，本文將其等待時(shí)延設(shè)置為0，即該節(jié)點(diǎn)轉(zhuǎn)發(fā)優(yōu)先級(jí)最高，此時(shí)轉(zhuǎn)發(fā)概率只由PTI控制，這樣設(shè)計(jì)的好處首先是每一跳的轉(zhuǎn)發(fā)都覆蓋了最大的地理范圍，有利于消息快速傳播;其次在一定程度上能適應(yīng)整個(gè)網(wǎng)絡(luò)拓?fù)涞能?chē)流密度變化。

3.3 TSBP工作流程

根據(jù)前述內(nèi)容，TSBP協(xié)議的流程如圖5所示。

網(wǎng)絡(luò)中每輛車(chē)首先利用車(chē)載設(shè)備獲取方向、速度、經(jīng)緯度、時(shí)間戳等基本狀態(tài)信息，并將這些信息封裝在beacon消息中定期向鄰居節(jié)點(diǎn)廣播。當(dāng)鄰居車(chē)輛收到beacon消息后，會(huì)根據(jù)基本狀態(tài)信息立即更新其鄰居列表。根據(jù)該鄰居列表，節(jié)點(diǎn)的網(wǎng)絡(luò)層感知拓?fù)湫畔?，分析特征信息—有效鄰居?shù)、有效通信距離、車(chē)流密度指示器，進(jìn)行分布式中繼決策，之后把這些信息嵌入到報(bào)文頭部并廣播。每個(gè)鄰居節(jié)點(diǎn)接收到數(shù)據(jù)包后，立即分析上一跳發(fā)送節(jié)點(diǎn)的拓?fù)湫畔ⅲ缓蟾鶕?jù)自己與發(fā)送節(jié)點(diǎn)之間的距離，分配候選中繼節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率和轉(zhuǎn)發(fā)時(shí)延。距離上一跳越遠(yuǎn)的節(jié)點(diǎn)，分配的等待時(shí)延越少，可優(yōu)先轉(zhuǎn)發(fā)。如果某些車(chē)輛節(jié)點(diǎn)未通過(guò)概率測(cè)試，那么他們不能參與等待競(jìng)爭(zhēng)轉(zhuǎn)發(fā)的過(guò)程。若有節(jié)點(diǎn)在計(jì)時(shí)器到期之前接收到確認(rèn)幀（ACK）或廣播副本則取消等待。其他候選節(jié)點(diǎn)轉(zhuǎn)發(fā)報(bào)文時(shí)，重復(fù)上述過(guò)程，更新廣播報(bào)文中的拓?fù)湫畔?，?zhí)行逐跳轉(zhuǎn)發(fā)，直到整個(gè)風(fēng)險(xiǎn)區(qū)域的車(chē)輛都獲得安全消息。另外，TSBP協(xié)議在網(wǎng)絡(luò)層還引入了重傳機(jī)制，以盡可能地減少?gòu)V播副本，同時(shí)保障安全消息的連續(xù)分發(fā)。只有包含消息源節(jié)點(diǎn)在內(nèi)的上一跳節(jié)點(diǎn)在最大等待時(shí)間內(nèi)沒(méi)有收到ACK或任何轉(zhuǎn)發(fā)的副本時(shí)，才開(kāi)啟重傳過(guò)程，此時(shí)安全消息被重新廣播，如果收到ACK或副本，則取消重傳過(guò)程。

4 仿真與分析

為了分析TSBP的廣播性能，本文使用實(shí)驗(yàn)室仿真軟件工具NS2+SUMO來(lái)模擬實(shí)際車(chē)輛的運(yùn)動(dòng)和通信環(huán)境。

4.1 仿真場(chǎng)景設(shè)置

在SUMO軟件中設(shè)定一條寬度為40 m，長(zhǎng)度為3 000 m的雙向六車(chē)道直行道路，讓20～100輛車(chē)先后隨機(jī)進(jìn)入該道路，并滿足車(chē)輛拓?fù)涞倪B通性。車(chē)輛移動(dòng)符合karuosi智能跟車(chē)方式，車(chē)輛時(shí)速取值在30～100 km之間，當(dāng)車(chē)輛到達(dá)道路盡頭時(shí)掉頭反向運(yùn)動(dòng)以保證道路上一定的車(chē)流密度。處于網(wǎng)絡(luò)中的車(chē)輛的理論通信半徑設(shè)定為300 m，每輛車(chē)隨機(jī)生成多跳廣播消息，每秒生成一個(gè)報(bào)文，并且以0.5的概率發(fā)送。其他主要仿真參數(shù)見(jiàn)表1所列，配置好參數(shù)后使用NS2[17]進(jìn)行仿真。

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

為了驗(yàn)證TSBP的廣播性能，本文選擇了具有代表性的泛洪廣播算法（Mflood）、最遠(yuǎn)節(jié)點(diǎn)轉(zhuǎn)發(fā)算法（FARTHEST）、時(shí)隙1堅(jiān)持算法（Slotted-1）、時(shí)隙p堅(jiān)持算法（Slottedp）等典型廣播算法與TSBP進(jìn)行對(duì)比分析。

對(duì)比的算法性能指標(biāo)主要包括報(bào)文投遞率（Packet Delivery Ratio，PDR）、端到端時(shí)延（End-to-End Delay，E2ED）、一跳平均時(shí)延（One Hop Delay，OHD）、廣播冗余（Broadcast Redundancy，BR）、轉(zhuǎn)發(fā)效率（Forwarding Efficiency，F(xiàn)E）。報(bào)文投遞率PDR與車(chē)流密度的關(guān)系曲線如圖6所示。

如圖6所示，隨著車(chē)流密度的增加，廣播協(xié)議的報(bào)文投遞率遞增，原因是有更多的車(chē)輛節(jié)點(diǎn)參與轉(zhuǎn)發(fā)。當(dāng)增加到100車(chē)/3 km的密集網(wǎng)絡(luò)時(shí)，由于報(bào)文碰撞的增加將導(dǎo)致投遞率遞減。Slottedp和TSBP通過(guò)引入轉(zhuǎn)發(fā)概率在一定程度上減少了碰撞，因而在高密度時(shí)投遞率優(yōu)于Slotted-1，但是在低密度時(shí)，轉(zhuǎn)發(fā)存在一定的概率性，因而投遞率略低，雖然TSBP通過(guò)感知車(chē)流密度來(lái)動(dòng)態(tài)調(diào)整轉(zhuǎn)發(fā)概率，在一定程度上提高了投遞率，卻依然低于Slotted-1，原因是車(chē)聯(lián)網(wǎng)拓?fù)涓叨葎?dòng)態(tài)變化，因而自適應(yīng)算法性能有待進(jìn)一步優(yōu)化。由于FARTHEST規(guī)定節(jié)點(diǎn)在收到報(bào)文后按照距離分配等待時(shí)延，相比Slotted-1少了一個(gè)靜態(tài)等待時(shí)延用來(lái)消除多個(gè)副本的轉(zhuǎn)發(fā)，因而廣播會(huì)因?yàn)轭l繁的碰撞而中斷，F(xiàn)ARTHEST的投遞率在幾類(lèi)廣播協(xié)議中更低。

廣播協(xié)議的時(shí)延隨車(chē)流密度的變化曲線如圖7、圖8所示。為了減少上一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)并發(fā)數(shù)據(jù)導(dǎo)致廣播中斷，Slotted-1和Slottedp在節(jié)點(diǎn)轉(zhuǎn)發(fā)前分配靜態(tài)等待時(shí)延，每一跳轉(zhuǎn)發(fā)都引入了額外的等待時(shí)延，因而轉(zhuǎn)發(fā)時(shí)延較高，尤其在低密度網(wǎng)絡(luò)中，“慢反應(yīng)”現(xiàn)象更明顯。Mflood，F(xiàn)ARTHEST和TSBP規(guī)定節(jié)點(diǎn)收到報(bào)文后無(wú)需靜態(tài)等待，按照優(yōu)先級(jí)轉(zhuǎn)發(fā)，在高密度時(shí)競(jìng)爭(zhēng)加劇，廣播時(shí)延遞增。TSBP通過(guò)發(fā)送節(jié)點(diǎn)感知鄰居的分布和數(shù)量計(jì)算有效通信距離，來(lái)替代固定值計(jì)算等待時(shí)延，適應(yīng)了拓?fù)涞膭?dòng)態(tài)變化特性，減少了實(shí)際參與競(jìng)爭(zhēng)轉(zhuǎn)發(fā)的冗余節(jié)點(diǎn)數(shù)，等待時(shí)延和轉(zhuǎn)發(fā)跳數(shù)都得以優(yōu)化。由以上分析可知，與其他幾種典型的廣播協(xié)議相比，本文提出的TSBP算法能有效緩解稀疏網(wǎng)絡(luò)中的“慢反應(yīng)”問(wèn)題造成的影響，優(yōu)化了廣播協(xié)議的時(shí)延性能。

圖9顯示了廣播協(xié)議的冗余量隨車(chē)流密度的變化情況，圖中顯示隨著車(chē)流密度的增加，網(wǎng)絡(luò)的連通性逐漸變好，實(shí)際參與報(bào)文轉(zhuǎn)發(fā)的節(jié)點(diǎn)也隨之增加，網(wǎng)絡(luò)中增加了大量無(wú)效副本，廣播冗余增加。同時(shí)無(wú)效冗余導(dǎo)致無(wú)效轉(zhuǎn)發(fā)次數(shù)大量增加，因而轉(zhuǎn)發(fā)效率遞減，如圖10所示。從圖10可以看出，轉(zhuǎn)發(fā)效率惡化的速度隨著碰撞的加劇而增加，“局部廣播風(fēng)暴”在高密度時(shí)凸顯，使得廣播性能惡化。FARTHEST通過(guò)收發(fā)節(jié)點(diǎn)之間的距離配置轉(zhuǎn)發(fā)優(yōu)先級(jí)，抑制了一部分節(jié)點(diǎn)的轉(zhuǎn)發(fā)，較Mflood冗余性能在更大程度上得以優(yōu)化。Slotted-1則通過(guò)把一跳通信范圍劃分成優(yōu)先級(jí)不同的區(qū)域，使得低優(yōu)先級(jí)區(qū)域內(nèi)的冗余量進(jìn)一步減少，從而提升其轉(zhuǎn)發(fā)效率。由于Slotted-1，Slottedp通過(guò)引入概率機(jī)制進(jìn)一步減少了冗余，所以在幾類(lèi)算法中冗余性能最優(yōu)。但是Slottedp協(xié)議中概率配置是固定的，這導(dǎo)致其不能適應(yīng)網(wǎng)絡(luò)的密度變化，在低密度網(wǎng)絡(luò)中報(bào)文投遞率較低，所以其廣播效率隨著車(chē)流密度的增加先增后減。TSBP通過(guò)計(jì)算有效鄰居數(shù)來(lái)動(dòng)態(tài)配置劃分的路段數(shù)，通過(guò)計(jì)算收發(fā)節(jié)點(diǎn)之間的距離以及局部車(chē)流密度指示器來(lái)分配轉(zhuǎn)發(fā)概率，較大程度上抑制了無(wú)效副本的產(chǎn)生，在密集網(wǎng)絡(luò)中依然保持較少的冗余和較高的轉(zhuǎn)發(fā)效率，較大程度上緩解了密集網(wǎng)絡(luò)下的“局部廣播風(fēng)暴”問(wèn)題。由于針對(duì)拓?fù)涞母兄腔谥芷谛缘腷eacon消息建立的鄰居列表，因而廣播性能受信道衰落和干擾影響較大，尤其在低密度條件下，網(wǎng)絡(luò)拓?fù)涞淖兓ち遥従痈兄臏?zhǔn)確性有待進(jìn)一步提高。

5 結(jié) 語(yǔ)

基于接收節(jié)點(diǎn)競(jìng)爭(zhēng)轉(zhuǎn)發(fā)的策略被廣泛應(yīng)用于車(chē)聯(lián)網(wǎng)中安全緊急消息的多跳轉(zhuǎn)發(fā)，然而，這種策略在密集網(wǎng)絡(luò)和稀疏網(wǎng)絡(luò)中分別存在“局部廣播風(fēng)暴”和“慢反應(yīng)”問(wèn)題，對(duì)此，本文將基于接收節(jié)點(diǎn)競(jìng)爭(zhēng)轉(zhuǎn)發(fā)的策略與基于概率廣播的協(xié)議，發(fā)揮基于概率廣播協(xié)議在降低無(wú)效網(wǎng)絡(luò)冗余方面的優(yōu)勢(shì)，提出了一種基于車(chē)聯(lián)網(wǎng)局部拓?fù)涓兄姆植际綇V播路由協(xié)議TSBP。仿真結(jié)果表明：相對(duì)于經(jīng)典的廣播協(xié)議，TSBP在保障廣播可靠性的同時(shí)，時(shí)延和冗余性能更優(yōu)。由于TSBP性能受鄰居拓?fù)湫畔⒏兄夹g(shù)的影響較大，下一步研究的方向是跨物理層、MAC層和應(yīng)用層優(yōu)化協(xié)議，進(jìn)一步提高協(xié)議對(duì)車(chē)流密度和拓?fù)渥兓倪m應(yīng)性。

參 考 文 獻(xiàn)

[1]劉輝元，董春陽(yáng)，黃瓊.基于VANETs下的決策樹(shù)多副本機(jī)會(huì)路由協(xié)議[J].重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，28（6）：769-776.

[2] OMAR H A，ZHUANG W，ABDRABOU A，et al. Performance evaluation of VeMAC supporting safety applications in vehicular networks[J].IEEE transactions on emerging topics in computing，2013，1（1）：69-83.

[3] G?KHAN K，EKICI E. Urban multi-hop broadcast protocol for inter-vehicle communication systems[C]// Proc. ACM Workshop on Vehicular Ad Hoc Networks. 2004：76-85.

[4] IBRAHIM K，WEIGLE M C，ABUELELA M. p-IVG： Probabilistic Inter-Vehicle Geocast for Dense Vehicular Networks[C]// Vehicular Technology Conference，Vtc Spring 2009. IEEE，2009：1-5.

[5] AKKHARA P，SEKIYA Y，WAKAHARA Y. Efficient alarm messaging by multi-channel cut-through rebroadcasting based on inter-vehicle communication[J].Iaeng International journal of computer science，2009，36（2）.

[6] VIRIYASITAVAT W，BAI F，TONGUZ O K. UV-CAST： An urban vehicular broadcast protocol[J].IEEE communications magazine，2011，49（11）：116-124.

[7] LI M，LOU W，ZENG K. OppCast： Opportunistic broadcast ofwarning messages in VANETs with unreliable links[C]// IEEE，International Conference on Mobile Adhoc and Sensor Systems. IEEE，2009：534-543.

[8] YI C W，CHUANG Y T，YEH H H，et al. Streetcast： An Urban Broadcast Protocol for Vehicular Ad-Hoc Networks[C]// Vehicular Technology Conference. IEEE，2010：1-5.

[9] A J. An information propagation scheme for VANETs[C]// Intelligent Transportation Systems，2005. Proceedings. IEEE，2005：155-160.

[10] CHEN R，JIN W L，REGAN A. Broadcasting safety information in vehicular networks： issues and approaches[J]. Network IEEE，2010，24（1）：20-25.

[11] ZHU，LINA，ZHAO，et al. Hello scheme for vehicular ad hoc networks： analysis and design[J]. Eurasip journal on wireless communications & networking，2013（1）：1-11.

[12] WISITPONGPHAN N，TONGUZ O K，PARIKH J S，et al. Broadcast storm mitigation techniques in vehicular ad hoc networks[J].Wireless communications IEEE，2007，14（6）：84-94.

[13] OH S，KANG J，GRUTESER M. Location-Based Flooding Techniques for Vehicular Emergency Messaging[C]// Third International Conference on Mobile and Ubiquitous Systems： Networking & Services，IEEE，2006：1-9.

[14] HAFEEZ K A，ZHAO L，LIAO Z，et al. A New Broadcast Protocol for Vehicular Ad Hoc Networks Safety Applications[C]// Global Telecommunications Conference. IEEE，2011：1-5.

[15] FARNOUD F，VALAEE S. Reliable Broadcast of Safety Messages in Vehicular Ad Hoc Networks[C]// INFOCOM. IEEE，2009：226-234.

[16] XU Q，MAK T，KO J，et al. Medium access control protocol design for vehicle-vehicle safety messages[J].Vehicular technology IEEE transactions on，2007，56（2）：499-518.

[17] NS2，the network simulator[EB/OL]. http：//www.isi.edu/nsnam/ns.