0 引言

    隨著專用短程通信DSRC(Dedicated Short-Range Communications)標(biāo)準(zhǔn)的成熟，車載自組織網(wǎng)絡(luò)VANETs(Vehicle Ad hoc Networks)成為研究的焦點(diǎn)。VANETs網(wǎng)絡(luò)通過車間通信V2V(Vehicle-to-Vehicle)實(shí)現(xiàn)消息的傳遞。車輛間傳遞的消息分為兩類：緊急消息(Emergency Message)和非緊急消息。當(dāng)前方車輛發(fā)現(xiàn)交通事故、路面有障礙物等緊急情況，需向周圍車輛發(fā)布這一情況，即緊急消息，提醒周圍車輛采取必要的措施^[1-3]。

    由于緊急消息對(duì)時(shí)間相當(dāng)敏感，必須快速、可靠地傳輸，否則就失去意義。目前，常采用廣播機(jī)制傳遞緊急消息，如城市多跳廣播^[3]，是一個(gè)有效傳遞緊急消息的方案。當(dāng)出現(xiàn)緊急情況，源節(jié)點(diǎn)(第一個(gè)發(fā)現(xiàn)該緊急情況的車輛)向鄰居節(jié)點(diǎn)廣播消息，接收節(jié)點(diǎn)再重播，直到所有相關(guān)的節(jié)點(diǎn)均收到此消息。然而，這種簡單的廣播策略，會(huì)引發(fā)信道擁擠，導(dǎo)致廣播風(fēng)暴。

    為此，研究者提出基于地理信息的廣播算法^[4-9]。G.Korkmaz^[4]提出基于城市多跳廣播協(xié)議UMB(Urban Multi-Hop Broadcast Protocol)。利用GPS信息和請(qǐng)求廣播RTB(Request to Broadcast)數(shù)據(jù)包機(jī)制，將傳輸范圍分幾段，每段的節(jié)點(diǎn)知道自己所在的段區(qū)域，位于最遠(yuǎn)段的節(jié)點(diǎn)具有成為轉(zhuǎn)發(fā)清除廣播CTB(Clear to Broadcast)數(shù)據(jù)包的優(yōu)先權(quán)。然而，當(dāng)最遠(yuǎn)段內(nèi)的節(jié)點(diǎn)數(shù)不止一個(gè)時(shí)，就出現(xiàn)碰撞。為了避免碰撞，發(fā)送者需通過近的段再將廣播RTB數(shù)據(jù)包。接收節(jié)點(diǎn)利用RTB內(nèi)的信息，產(chǎn)生一個(gè)干擾信號(hào)Jamming Signal去占用信道。當(dāng)信道內(nèi)無其他節(jié)點(diǎn)的Jamming Signal就發(fā)送CTB數(shù)據(jù)包。此過程一直進(jìn)行，直到成功選舉轉(zhuǎn)發(fā)節(jié)點(diǎn)。可見，UWB協(xié)議中的碰撞避免機(jī)制是一個(gè)重復(fù)迭代過程，效率低，并且VANETs的動(dòng)態(tài)拓?fù)渲率雇掏铝肯陆?。為了改進(jìn)UWB協(xié)議，文獻(xiàn)[7]采用智能廣播SB(Smart Broadcast)以消除復(fù)雜的碰撞避免機(jī)制，極大地提高了時(shí)延性能。然而，智能廣播仍采用了RTB/CTB交互和ACK機(jī)制，未能避免因RTB/CTB交互和ACK (Acknowledgements)所引用的開銷。除了基于地理位置信息的廣播算法外，利用節(jié)點(diǎn)的信噪比SNR(Signal to Noise Ratio)去選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)^[10-13]也是可行方案之一。

    為此，本文提出一種廣播緊急消息的新型算法。該算法以縮短緊急消息傳播時(shí)延、提高傳輸速度為目的，利用信噪比SNR和節(jié)點(diǎn)的位置信息計(jì)算最大競(jìng)爭(zhēng)窗口，并從中選擇轉(zhuǎn)發(fā)緊急消息時(shí)隙，摒棄了RTB/CTB握手機(jī)制，降低了ACK的使用頻率。

1 基于SNR/GPS的伴隨ACK decoupling的廣播

    提出的廣播算法避免了廣播前的握手過程。源發(fā)送節(jié)點(diǎn)Sender(緊急消息的初始傳播者，假定是節(jié)點(diǎn)j)利用標(biāo)準(zhǔn)的802.11 CSMA/CA技術(shù)接入媒介，并廣播緊急消息Mes。發(fā)送節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)N_j計(jì)算相應(yīng)的SNR值，以及歐式距離D。接收節(jié)點(diǎn)(假定為節(jié)點(diǎn)i，i∈N_j)利用這些值計(jì)算最大競(jìng)爭(zhēng)窗口尺寸CW_max：

其中D_max為節(jié)點(diǎn)傳輸?shù)淖畲蠓秶?，D_ij為節(jié)點(diǎn)i與節(jié)點(diǎn)j間的歐式距離。CW_base為競(jìng)爭(zhēng)窗口值，可通過CW_base優(yōu)化網(wǎng)絡(luò)密度。SNR_i為節(jié)點(diǎn)i的SNR值，單位為dB。SNR_thresh表示為了保證可靠傳輸而設(shè)置的最小SNR門限值。k為常數(shù)，以確保式(1)為正整數(shù)(Positive Integers)^[14-15]。

    每個(gè)節(jié)點(diǎn)計(jì)算CW_max，并在[0，CW_max]區(qū)間內(nèi)隨機(jī)選擇一個(gè)時(shí)隙，再等待該時(shí)隙到來，并準(zhǔn)備重播緊急消息Mes。時(shí)隙最先到來的節(jié)點(diǎn)將成來轉(zhuǎn)發(fā)節(jié)點(diǎn)，并重播該緊急消息Mes。一旦接收到已重播的緊急消息RE_Mes，其他節(jié)點(diǎn)就終止重播緊急消息的活動(dòng)。

    注意到，離節(jié)點(diǎn)j越遠(yuǎn)的節(jié)點(diǎn)具有更低的CW_max，相應(yīng)地，從統(tǒng)計(jì)上看，節(jié)點(diǎn)具有短的等待時(shí)間，因此，這些節(jié)點(diǎn)被選為轉(zhuǎn)發(fā)節(jié)點(diǎn)的概率更大。此外，來自轉(zhuǎn)發(fā)節(jié)點(diǎn)Forwarder的Re_Mes作為回復(fù)節(jié)點(diǎn)j的確認(rèn)消息ACK。

    本文提出的廣播算法的兩個(gè)關(guān)鍵點(diǎn)：摒棄RTB/CTB環(huán)節(jié)縮短信道接入時(shí)延、消除ACK環(huán)節(jié)提高消息傳播效率。緊急消息能夠在各時(shí)域內(nèi)隨機(jī)分布，發(fā)生碰撞的概率較小。一旦發(fā)生了碰撞，可再從CW_max中隨機(jī)選擇時(shí)隙，直到不發(fā)生碰撞。

    算法流程如圖1所示。從圖1可知，提出的廣播算法降低了對(duì)ACK依賴。若Sender能夠收到Forwarder重播的消息Re_Mes，便可將其作為ACK消息，降低了ACK的使用，稱為ACK decoupling；反之，就需要節(jié)點(diǎn)向Sender發(fā)送ACK，稱為ACK recovery。接下來，從ACK decoupling、ACK recovery方面分析提出的廣播性能，并與SB進(jìn)行比較。

    在提出的算法中，通過結(jié)合SNR和GPS坐標(biāo)，降低ACK依賴性。收到數(shù)據(jù)包的節(jié)點(diǎn)依據(jù)式(1)計(jì)算CW_max，并從中隨機(jī)地選擇時(shí)隙。當(dāng)時(shí)隙到來時(shí)，候選轉(zhuǎn)發(fā)節(jié)點(diǎn)試著重播消息。若在傳遞重播消息時(shí)發(fā)生碰撞，提出的方案與SB的處理方式不同，并且選取轉(zhuǎn)發(fā)節(jié)點(diǎn)所用的方案也不一樣，目的在于降低ACK dependency。在SB中，節(jié)點(diǎn)隨機(jī)選擇時(shí)隙，并競(jìng)爭(zhēng)成為轉(zhuǎn)發(fā)節(jié)點(diǎn)Forwarder，然后，F(xiàn)orwarder向發(fā)送節(jié)點(diǎn)回復(fù)ACK。如果不能成功傳遞ACK，就重復(fù)該過程。與SB不同，提出的方案使用SNR和GPS信息，致使發(fā)送者一直實(shí)時(shí)地監(jiān)聽來自轉(zhuǎn)發(fā)節(jié)點(diǎn)的廣播消息，消除了ACK過程。   

2 系統(tǒng)仿真及數(shù)據(jù)分析

2.1 仿真參數(shù)

    采用N3-3仿真軟件進(jìn)行仿真，并考慮瑞利衰落模型。考慮4車道(雙向)道路，長為4 km。節(jié)點(diǎn)通信范圍為300 m、時(shí)隙Time Slot為20 μs、SIFS為10 μs，每次實(shí)驗(yàn)運(yùn)行時(shí)間為100 s，具體的仿真參數(shù)如表1所示。

2.2 仿真數(shù)值分析

    (1)對(duì)提出的算法的平均每跳時(shí)延的影響

    圖2描繪了在不同的CW_base環(huán)境下，提出的算法每跳平均時(shí)延隨節(jié)點(diǎn)密度的變化曲線。因?yàn)楣?jié)點(diǎn)密度越低，位于300 m通信范圍內(nèi)的節(jié)點(diǎn)數(shù)目越小，相應(yīng)地，發(fā)送者Sender可能需等待最長時(shí)限(大于CW_base)后，才能重播緊急消息。然而，當(dāng)節(jié)點(diǎn)密度大于40 nodes/km，時(shí)延略有增加。這主要是因?yàn)?，?dāng)節(jié)點(diǎn)密度增加一定程度，更多的節(jié)點(diǎn)參與了競(jìng)爭(zhēng)重播消息，提高了碰撞概率，增加了時(shí)延。

圖2  提出算法的平均每跳時(shí)延隨節(jié)點(diǎn)密度的變化情況

    此外，低的CW_base(如CW_base=2)具有更低的平均時(shí)延。原因很簡單，低的CW_base導(dǎo)致CW_max更低，這就意味著轉(zhuǎn)發(fā)節(jié)點(diǎn)Forwarders只需等待較短的時(shí)間，便可重播消息。

    下面將提出的算法與SB算法從每跳的平均時(shí)延、吞吐量方面進(jìn)行對(duì)比分析。

    (2)節(jié)點(diǎn)密度對(duì)每跳平均時(shí)延的影響

    由圖3可知，與SB相比，提出的算法的平均每跳時(shí)延降低了約SB算法在整個(gè)節(jié)點(diǎn)密度區(qū)間，平均時(shí)延約1.75 ms，而提出的算法的平均每跳時(shí)延約為0.6 ms。兩個(gè)主要的原因：首先，SB算法嚴(yán)重依賴于RTB/CTB握手機(jī)制，需等待較長干擾信號(hào)(Jamming Signal)才重播消息，而提出的算法在重播消息前，沒有RTB/CTB環(huán)節(jié)。其次，SB算法利用ACK解決碰撞問題，而提出的算法是采用SNR和坐標(biāo)信息去處理，摒棄了ACK環(huán)節(jié)。

    (3)數(shù)據(jù)包大小對(duì)吞吐量的影響

    圖4描繪了吞吐量隨數(shù)據(jù)包大小的變化曲線。從圖4可知，提出的算法的吞吐量是SB算法的兩倍。在SB協(xié)議中，大量的網(wǎng)絡(luò)資源被消耗于RTB/CTB/ACK數(shù)據(jù)包的交互環(huán)節(jié)，而提出的算法避開了這些環(huán)節(jié)，從而大幅度地提高了吞吐量。

    由圖4可知，隨著數(shù)據(jù)包尺寸的增加，吞吐量呈增加趨勢(shì)。這個(gè)數(shù)據(jù)結(jié)果反映一個(gè)事實(shí)：競(jìng)爭(zhēng)節(jié)點(diǎn)在重播前所耗的時(shí)間與數(shù)據(jù)包大小沒有關(guān)系，而對(duì)于大的數(shù)據(jù)包而言，每次傳輸?shù)臄?shù)據(jù)量大，進(jìn)而提升了吞吐量。

3 總結(jié)

    在VANET環(huán)境下，針對(duì)緊急消息的傳播問題展開分析，提出一個(gè)新型的廣播算法。源節(jié)點(diǎn)廣播緊急消息Mes，接收節(jié)點(diǎn)利用信噪比SNR和GPS坐標(biāo)信息計(jì)算最大競(jìng)爭(zhēng)窗口CW_max，并從[0，CW_max]區(qū)間內(nèi)隨機(jī)選擇一個(gè)時(shí)隙用于轉(zhuǎn)發(fā)消息Mes。當(dāng)時(shí)隙到來并沒有收到其他節(jié)點(diǎn)廣播的消息Re_Mes，則成為轉(zhuǎn)發(fā)節(jié)點(diǎn)，并重播緊急消息。若源節(jié)點(diǎn)收到消息Re_Mes，表明緊急消息已成功傳遞到下一個(gè)節(jié)點(diǎn)，源節(jié)點(diǎn)無需再廣播。通過這種方式摒棄了RTB/CTB握手機(jī)制，也免去ACK的過程，提高消息的傳輸速度，降低了時(shí)延。若出現(xiàn)傳輸碰撞，節(jié)點(diǎn)再從[0，CW_max]隨機(jī)選擇時(shí)隙，重復(fù)上述過程。由于CW_max反映了節(jié)點(diǎn)的實(shí)時(shí)信息，發(fā)生碰撞的概率極小。仿真結(jié)果表明，與SB相比，提出的算法的平均時(shí)延降低了約，吞吐量提高了兩倍。

參考文獻(xiàn)

[1] KENNEY J B.Dedicated short-range communications(DSRC) standards in the united states[C].Proceedings of the IEEE，2011，99(7)：1162-1182.

[2] RAZVAN C，HAMZA A，HUANG F.Fast and reliable broad-casting in VANETs using SNR with ACK decoupling[C].IEEE ICC 2014-Ad-hoc and Sensor Networking Symposium，2014：574-579.

[3] 常促宇，向勇，史美林.車載自組網(wǎng)的現(xiàn)狀與發(fā)展[J].通信學(xué)報(bào)，2007，11(5)：116-127.

[4] KORKMAZ G，EKICI E，OZGLINER F.Urban multi-hop broadcast protocol for inter-vehicle communication systems[C].Proceedings of the 1st ACM International Workshop on Vehicular Ad hoc Networks, VANET′04，New York，USA，2004：76-85.

[5] 夏梓峻，劉春鳳，趙增華，等.基于鏈路預(yù)測(cè)的VANET路由算法[J].計(jì)算機(jī)工程，2012，38(4)：110-114.

[6] PANICHPAPIBOON S，F(xiàn)ERRARI G，TONGUZ O K.Connectivity of ad hoc wireless networks：An alternative to graph-theoretic approaches[J].Wirel.Netw.，2010，16(3)：793-811.

[7] FASOLO E，ZANELLA A，ZORZI M.An effective broadcast scheme for alert message propagation in vehicular Ad hoc Networks[C].Communications，2006.ICC′06.IEEE International Conference on，2006(9)：3960-3965.

[8] Bai Songnan，Huang Zequn，Kwak Dongyong，et al.Vehicular multi-hop broadcasting protocol for safety message dissemination in VANETs[J].Vehicular Technology Conference Fall(VTC 2009-Fall)，2009 IEEE 70th，2009，1(5)：20-23.

[9] Li Ming，Lou Wenjing，Zeng Kai.Oppcast：opportunistic broadcast of warning messages in VANETs with unreliable links[C].Mobile Adhoc and Sensor Systems, 2009.MASS′09.IEEE 6th International Conference on，2009：534-543.

[10] MI R P，DONGWON K S.A simple SNR based linear back-off to propagate multi-hop emergency messages on the distributed VANETs[C].Communications in Computer and Information Science，2012：34-41.

[11] KESTING A，TREIBER M，HELBING D.Connectivity statistics of storeand-forward intervehicle communication[J].IEEE Trans.Intell.Transp.Syst.，2010，11(1)：172-181.

[12] PASCOE M C，GOMEZ J，RANGEL V，et al.Route duration modeling for mobile ad-hoc networks[J].Wireless Netw.，2010，16(3)：743-757.

[13] Jang Chulhee，Lee Jae-Hong.Path selection algorithms for multi-hop VANETs[C].Vehicular Technology Conference Fall(VTC 2010Fall)，2010：1-6.

[14] Yan Gongjun，Olariu Stephan.A probabilistic analysis of link duration in vehicular ad hoc networks[J].IEEE Transactions on intelligent transportation system，2011，12(4)：1227-1237.

[15] KHAN F，CHANG Y，COPELAND P S.Handshaking vs.instant broadcast in VANET safety message routing[C].Proceedings of IEEE PIMRC′II，2011：709-714