0 引言

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

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

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

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

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

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

其中D_max為節點傳輸的最大范圍，D_ij為節點i與節點j間的歐式距離。CW_base為競爭窗口值，可通過CW_base優化網絡密度。SNR_i為節點i的SNR值，單位為dB。SNR_thresh表示為了保證可靠傳輸而設置的最小SNR門限值。k為常數，以確保式(1)為正整數(Positive Integers)^[14-15]。

    每個節點計算CW_max，并在[0，CW_max]區間內隨機選擇一個時隙，再等待該時隙到來，并準備重播緊急消息Mes。時隙最先到來的節點將成來轉發節點，并重播該緊急消息Mes。一旦接收到已重播的緊急消息RE_Mes，其他節點就終止重播緊急消息的活動。

    注意到，離節點j越遠的節點具有更低的CW_max，相應地，從統計上看，節點具有短的等待時間，因此，這些節點被選為轉發節點的概率更大。此外，來自轉發節點Forwarder的Re_Mes作為回復節點j的確認消息ACK。

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

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

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

2 系統仿真及數據分析

2.1 仿真參數

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

2.2 仿真數值分析

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

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

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

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

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

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

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

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

    圖4描繪了吞吐量隨數據包大小的變化曲線。從圖4可知，提出的算法的吞吐量是SB算法的兩倍。在SB協議中，大量的網絡資源被消耗于RTB/CTB/ACK數據包的交互環節，而提出的算法避開了這些環節，從而大幅度地提高了吞吐量。

    由圖4可知，隨著數據包尺寸的增加，吞吐量呈增加趨勢。這個數據結果反映一個事實：競爭節點在重播前所耗的時間與數據包大小沒有關系，而對于大的數據包而言，每次傳輸的數據量大，進而提升了吞吐量。

3 總結

    在VANET環境下，針對緊急消息的傳播問題展開分析，提出一個新型的廣播算法。源節點廣播緊急消息Mes，接收節點利用信噪比SNR和GPS坐標信息計算最大競爭窗口CW_max，并從[0，CW_max]區間內隨機選擇一個時隙用于轉發消息Mes。當時隙到來并沒有收到其他節點廣播的消息Re_Mes，則成為轉發節點，并重播緊急消息。若源節點收到消息Re_Mes，表明緊急消息已成功傳遞到下一個節點，源節點無需再廣播。通過這種方式摒棄了RTB/CTB握手機制，也免去ACK的過程，提高消息的傳輸速度，降低了時延。若出現傳輸碰撞，節點再從[0，CW_max]隨機選擇時隙，重復上述過程。由于CW_max反映了節點的實時信息，發生碰撞的概率極小。仿真結果表明，與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 broad-casting in VANETs using SNR with ACK decoupling[C].IEEE ICC 2014-Ad-hoc and Sensor Networking Symposium，2014：574-579.

[3] 常促宇，向勇，史美林.車載自組網的現狀與發展[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，FERRARI 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