張韌志，韓 棟

(黃淮學院 信息工程學院，河南 駐馬店463000)

車聯(lián)網(wǎng)VANETs中一種分發(fā)緊急消息的廣播方案*

張韌志，韓 棟

(黃淮學院 信息工程學院，河南 駐馬店463000)

車載網(wǎng)VANETs中的車間通信V2V能夠?qū)崿F(xiàn)車間緊急消息的傳遞。然而，傳統(tǒng)的廣播算法采用RTB和CTB握手機制，同時在傳遞消息后，還需確認ACK環(huán)節(jié)，降低了緊急消息傳遞速度、增加了傳輸時延。為此，提出了一種廣播緊急消息的新型算法。該算法利用數(shù)據(jù)包的信噪比SNR和節(jié)點位置坐標信息計算最大競爭窗口，再在最大競爭窗口內(nèi)隨機選擇一個時隙用于轉(zhuǎn)發(fā)緊急消息，避免了RTB/CTB握手機制。當源節(jié)點收到重播的緊急消息，表明緊急消息已成功傳到下一節(jié)點，將其作為抑制源節(jié)點再廣播緊急消息指標，避免了ACK確認環(huán)節(jié)，從而提高了緊急消息的傳播效率和速度，降低了傳輸時延。

車載網(wǎng)；廣播；RTB；CTB；ACK；緊急消息；競爭窗口

0 引言

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

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

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

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

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

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

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

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

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

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

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

圖1 算法流程圖

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

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

2.1 仿真參數(shù)

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

2.2 仿真數(shù)值分析

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

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

表1 仿真參數(shù)

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

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

下面將提出的算法與SB算法從每跳的平均時延、吞吐量方面進行對比分析。

(2)節(jié)點密度對每跳平均時延的影響

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

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

圖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ù)據(jù)結(jié)果反映一個事實：競爭節(jié)點在重播前所耗的時間與數(shù)據(jù)包大小沒有關(guān)系，而對于大的數(shù)據(jù)包而言，每次傳輸?shù)臄?shù)據(jù)量大，進而提升了吞吐量。

圖3 提出的算法和SB算法的平均每跳的時延性能比較

圖4 提出的算法和SB算法的吞吐量性能比較

3 總結(jié)

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

[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 broadcasting 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].通信學報，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]夏梓峻，劉春鳳，趙增華，等.基于鏈路預測的 VANET路由算法[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，RANGELV，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.

A new broadcasting emergency message algorithm in VANETs

Zhang Renzhi，Han Dong
(Huanghuai University，Zhumadian 463000，China)

In Vehicle Ad hoc Networks，Vehicle-to-Vehicle communication is able to transmit emergency message.However，traditional broadcasting algorithm introduces the Request to Broadcast and clear to Broadcast handshake mechanism.Meantime，after broadcasting message，it need acknowledge process，which reduces the transmission speed of emergency message，increase the transmission delay.Therefore，a new broadcasting emergency message algorithm is proposed.It uses Signal-to-Noise Ratio and location information to compute the contention window sizes，and randomly choose a time slot from the contention window sizes to transmit the emergency message.It avoids the RTB/CTB handshake mechanism.When the source node received the rebroadcasted emergency message，it means that emergency message has been successfully transmit，which inhibition of source node to broadcast an urgent message indicators，and avoid the ACK，so as to improve the transmission efficiency and speed，reduce the transmission delay.

VANETs；broadcast；Request to Broadcast；Clear to Broadcast；acknowledge；emergency message；contention window

TN915.5

A

10.16157/j.issn.0258-7998.2015.07.028

張韌志，韓棟.車聯(lián)網(wǎng)VANETs中一種分發(fā)緊急消息的廣播方案[J].電子技術(shù)應(yīng)用，2015，41(7)：100-102，106.

英文引用格式：Zhang Renzhi，Han Dong.A new broadcasting emergency message algorithm in VANETs[J].Application of Electronic Technique，2015，41(7)：100-102，106.

2015-01-14)

張韌志（1980-），男，講師，主要研究方向：計算機網(wǎng)絡(luò)、數(shù)據(jù)庫。

河南省重點科技攻關(guān)項目研究基金(142102210335)，河南省教育廳重點科技攻關(guān)項目(14B520036)

韓棟（1979-），男，博士，講師，主要研究方向：計算機網(wǎng)絡(luò)。