用于VANET緊急消息傳輸的改進二元分割廣播協議

程黛月，章國安，葉 翔

（南通大學電子信息學院 南通 226019）

1 引言

近些年來，VANET（車輛自組織網絡）中的緊急消息傳輸在智能交通系統（intelligent transportation system，ITS）里引起了重要關注。車輛自組織網絡主要通過廣播的方式傳播緊急消息。這樣的廣播方式主要依賴于被許可的專用短程通信，如IEEE 802.11p和IEEE P1609.4標準[1,2]。然而，由于車輛自組織網絡節點的高速移動、節點密度頻繁變化、網絡拓撲結構不穩定以及信道資源有限等特點，使得快速可靠地廣播緊急消息成為極大的挑戰[3]。而近期的研究表明，最初的IEEE 802.11p的MAC子層標準并不適用于VANET中對緊急消息的及時廣播。

目前在VANET中廣播協議方面的研究主要有以下幾種。

[4]提出RTB/CTB握手方案，解決隱藏終端問題。然而，其性能分析結果顯示，它具有較高的通信時延。

·參考文獻[5]針對參考文獻[4]存在的問題，提出了智能廣播（SB）協議，該協議具有較短的通信時延，然而它對網絡變化的適應性較差。

·參考文獻[6]提出了機會廣播（OB-VAN）協議，目的是滿足安全應用所需的嚴格時間約束和較高的投遞率。然而當多個節點選取同一個退避值時，會發生嚴重的沖突。

·參考文獻[7]提出了BPAB（binary partition assisted broadcast）協議，目的是減少并穩定廣播時延。從性能分析結果中看出，BPAB協議相比于其他協議，如SB協議，在平均消息傳播速度方面具有更好的性能表現。但是在協議初始階段，該機制并未賦予緊急消息最高優先級，從而在協議初始階段消耗更多時間。

本文針對參考文獻[7]的不足，提出了一種改進的二元分割廣播協議（MBPAB協議），該協議能夠更大地降低廣播時延，提高消息傳播速度。

2 系統模型

系統模型如圖1所示，這場景為高速公路。在該場景中，假設沒有路邊單元等基礎設施用于通信支持。

圖1 系統模型

圖1 中，車輛在高速公路中移動，它們之間通過IEEE 802.11p網絡通信接口直接通信。在這個模型中，來自所有方向的車輛都可以加入緊急消息的傳播。有效地利用反向交通，能夠在傳播方向上有效地延伸傳播距離。這種通信一般用于節點對等網絡。

3 協議描述

本文針對BPAB協議，提出了一些改進方法，主要是在緊急消息接入信道前加入mini-DIFS[7]來減小競爭時間。mini-DIFS能夠為緊急消息提供快速的信道接入。二元分割主要減小競爭抖動以及在每一跳中選擇合適的轉發節點（離消息源節點最遠的節點）。因此它實現了較快的平均傳播速度。此外，類似于IEEE 802.11p標準下的請求廣播/清除廣播（RTB/CTB）握手機制也被運用到協議中，用來解決多跳無線網絡中的隱藏終端的問題。最后，在沖突解決和數據傳輸階段，發生碰撞的消息被重新發送。改進的二元分割的全部過程如圖2所示。每個階段細節如下所示。

（1）本協議使用mini-DIFS，其基本思想是將DIFS劃分為多個時隙，有緊急消息的節點隨機選擇幾個時隙（而不需要再等待整個DIFS），判斷信道是否閑忙。DIFS的時隙劃分如圖3所示，這里DIFS的時隙劃分為w個。圖4表示用于判斷信道狀態等待的一個隨機時間。

微時隙的長度l以及微時隙的數量w的計算式如下：

圖2 改進的二元分割過程

圖3 DIFS劃分

圖4 等待時間

其中，δ是在傳輸范圍R內的最大信道傳播時延。Tswitch是收發器在發送和接收模式之間的轉換所需要的時間。TDIFS和TSIFS分別對應于DIFS和SIFS的標準持續時間。一旦通信信道進入閑置狀態，為賦予緊急消息優先權，嘗試廣播緊急消息的車輛將從（0，w]中隨機選取第i個微時隙。等待時間Tw最終被計算成：

mini-DIFS階段結束后，發送端發送一個RTB數據分組，等待來自下一跳轉發節點響應的CTB數據分組。利用RTB/CTB機制解決隱藏終端和廣播風暴問題[8]。在發送節點傳輸范圍內，接收到RTB消息的所有車輛同時廣播出一個黑脈沖消息BA，即干擾信號。一旦發送端接收到BA，便判斷出消息傳播方向區域內至少有一個候選轉發節點。這種情況下，將進入二元分割進程。否則，發送節點會判定，傳播方向內沒有候選轉發節點。那么發送節點會等待一定時間，然后重新開始mini-DIFS過程。

（2）收到發送節點的RTB分組后，所有潛在的轉發節點同時廣播黑脈沖BA，告知發送節點存在潛在轉發節點。下一步就是選取離發送節點最遠的可能的轉發節點，再以每跳最大通信范圍向下一跳轉發緊急消息，這可以通過二元分割機制實現。

（3）碰撞處理機制：最后一輪二元分割過程結束后，可能發生CTB碰撞。這種情況下，所選區域內，退避時間未結束的車輛將繼續進行倒計時，因此，它們最終也會成為一個轉發節點。

超時階段（由最大競爭窗口時間Cw和廣播CTB數據分組的時間（Ttimeout=maxcw+TCTB）組成）結束后，若發送節點未能收到CTB，它將僅需圖2（b）所示的一半的時隙通過廣播黑脈沖來重啟該進程。一旦探測到半個時隙的黑脈沖，在所選區域的候選節點通過選擇新的Cw值相互重新競爭。該進程在設定的閾值內重復執行，直到CTB被成功發送。否則，若重新競爭次數超出預先設定的閾值，候選節點競爭進程將被終止。

4 協議性能參數

4.1 單跳時延Td

單跳時延指的是緊急消息被收到至轉發給中繼節點的時間。如圖2（a）所示，即：

其中，TI表示初始化時間，TP表示分割時間，TC表示競爭時間，TB表示消息傳播時間。

（1）初始時間TI

初始時間是指緊急消息被收到至RTB數據分組成功傳播的時間。因此，它由mini-DIFS時間Tm以及RTB數據分組廣播時間TRTB組成，如下：

在mini-DIFS進程的競爭階段時間內，會經歷下面3種情況之一。

·空閑：沒有車輛廣播RTB，并且信道在整個mini-DIFS時隙中都處于空閑狀態。

·成功：只有一個車輛廣播RTB，廣播成功。

·碰撞：同時有多輛車廣播RTB，發生碰撞。

3種情況下的平均初始時間的持續時間分別為：

其中，Tm_idle是信道處于空閑狀態的時間。Tm_suc是成功傳播RTB時間。Tm_col表示平均碰撞時間，由TRTB和mini-DIFS階段間的平均競爭時間Tm_cont組成。

設w為mini-DIFS的時隙數。因此，一個節點在給定時隙內初始化一次廣播的概率為pm=1/w。因為緊急消息事件發生概率非常小，并且獨立于其他事件，無記憶進程和數據分組之間的獨立模型適用于這種情況。因此，假設緊急消息的是以到達率為λm（本文默認為5緊急分組/s）的泊松隨機過程到達的。根據泊松隨機過程，空閑、成功以及碰撞情況下的概率如下：

每種情況獨立發生，在成功發送RTB前發送失敗的次數是以期望值為fm的幾何分布，期望值計算如下：

假設在一個mini-DIFS階段，空閑和碰撞情況都表示通信失敗。因此，失敗的mini-DIFS時隙的持續時間期望值Tm_fail為：

因此，在mini-DIFS階段所需的平均時間Tm為：

將式（14）代入式（5），可得初始時間為：

（2）分割時間TP

分割時間是在分割機制中消耗的時間：

其中，n是任何多進制分割機制的基礎值，本文n值取2；N是分割迭代次數。TSlotTime是時隙的持續時間。

（3）競爭時間TC

假定單位區域內的車輛數是一個隨機的變量，該變量服從均值為λ的泊松分布。因此在任意具有N次迭代的n元分割機制的每個區域的車輛數將是一個均值為μ=λ/nN的泊松隨機變量。

與mini-DIFS階段相似，競爭階段也會經歷下面3種情況之一。

·空閑：沒有車輛廣播CTB，信道在整個時隙里保持空閑。

·成功：只有一個車輛廣播CTB，CTB傳播成功。

·碰撞：同時有多個車輛廣播CTB，發生碰撞。每種情況下消耗的時間分別為：

其中，Tc_idle等同于TSlotTime。Tc_suc由CTB的傳播時間TCTB、SIFS階段的時間TSIFS以及數據傳播持續時間TData組成。Tc_col由TCTB和DIFS階段的TDIFS組成。

每一次Cw的選擇的概率為p=1/Cw，這里的Cw是指每次分割可獲得的競爭窗口的個數。因此，3種情況下的概率分別為：

由于在成功傳播CTB前的競爭次數等于源節點廣播的黑脈沖的次數，競爭時間可計算為：

成功傳播CTB之前的失敗嘗試次數是以期望值為f的幾何分布，Tc_fail是失敗時隙的預期持續時間。每個參數的計算如下：

（4）廣播傳輸時間TB

TB用來表示廣播傳輸時間，它由CTB成功發送時間TCTB、SIFS時間TSIFS以及數據傳輸時間TData組成，計算如下：

將式（15）、式（16）、式（23）以及式（26）代入式（4）中，單跳時延可計算為：

4.2 平均單跳廣播進展β

平均單跳廣播進展指每一跳信息廣播的平均距離。協議將通信范圍劃分為2N個區域。若假設，最終的中繼節點在相應區域中的某處，那么在第i（i=1,2,…,2N）個區域消息進度（用Mi表示）可表示為：

當某路段存在節點且比這個路段更遠的路段為空白的，那么這個路段即被選定。則空白和非空白區域的概率分別為：

若在區域j（j>i）不存在轉發節點，那么區域i將成為選中的區域。因此：

那么，平均單跳廣播進展β可表示為：

4.3 消息傳播速度ν

消息傳播速度定義為每秒廣播緊急消息的平均距離，即單跳廣播進展除以通信時延的值。

5 仿真分析

本文采用單跳時延、單跳消息進展和消息傳播速度3個性能指標來評估協議的性能。仿真條件假設如下：

·車輛在高速公路上是隨機分布的，所有車輛都相對運動，具有固定的網絡拓撲結構；

·Cw為競爭窗口大小，本文選取其值為4，N為其迭代次數，本文取值為3；

·單位區域內的車輛數是一個均值為λ的泊松分布的隨機變量；

·通信范圍近似為單位區域的長方形；

·忽略車輛節點的移動性對廣播性能的影響；

·源節點發送的緊急消息能被其通信范圍內的所有節點接收。

本文考慮一個1 500 m長的高速公路環境，車輛位置的分布服從泊松過程，每輛車上都安裝了無線通信設備，具體參數值見表1。

表1 性能仿真參數

圖5 單跳時延隨車輛密度變化曲線

MBPAB協議和BPAB協議以及SB協議的單跳時延隨車輛密度變化的曲線如圖5所示。從圖5中可以看出，SB協議在車輛密度較低的情況下，單跳時延較低，但是當車輛密度大于25輛/單位區域時，其單跳時延快速增長，并不適用于車輛密度較高時緊急消息的傳播。當車輛密度從5增大到40的過程中，BPAB和MBPAB的單跳時延見表2。

表2 BPAB與MBPAB單跳時延

從表2可看出，當車輛密不斷增加時，BPAB和MBPAB協議的單跳時延緩慢增加，同時，MBPAB協議的時延比BPAB協 議 的 時 延 低14.7μs，MBPAB協 議 引 入 了mini-DIFS，使緊急消息擁有最高優先級接入信道，從而為消息的傳播爭取更多有效時間，使緊急消息能夠有效地廣播出去。

圖6比較了3種協議的單跳廣播進展隨著車輛密度的變化曲線。從圖6中可以看出，SB協議隨著車輛密度的增大，單跳廣播進展在車輛密度達到15輛/單位區域后，呈下降趨勢，說明該協議在車輛網絡發生異常情況下（如交通事故場景中），容易導致網絡擁塞，不能將消息可靠地廣播出去。MBPAB協議與原BPAB協議的單跳廣播進展曲線是一致的，隨著車輛密度的上升，其單跳廣播進展緩慢增長，并且當車輛密度增大時，單跳廣播進展能達到最大傳播范圍的94%，說明MBPAB協議能保證消息傳播的可靠性。

圖7比較了3種協議的消息傳播速度隨車輛密度變化的性能曲線。從圖7中可以看出，車輛密度低于15輛/單位區域時，SB協議消息傳播速度高于2 000 m/s，其性能優于MBPAB協議；當車輛密度高于15輛/單位區域時，SB協議消息傳播速度呈逐漸下降趨勢，說明該協議適用于車輛密度稀疏的網絡，而在高車輛密度網絡下，協議性能變差。從MBPAB和BPAB協議的消息傳播速度曲線比較中，發現MBPAB協議由于采用了mini-DIFS，平均傳輸速度相較于原協議提升了大概75 m/s。這種提升是因為mini-DIFS機制賦予緊急消息較高的優先權，降低了接入時延，提高了消息傳播速度，從而改善協議的性能。

圖6 平均單跳廣播進展隨車輛密度變化曲線

圖7 消息傳播速度隨車輛密度變化曲線

6 結束語

本文提出了一種改進的二元分割廣播協議，賦予緊急消息最高的優先級接入信道，通過分析推導獲得單跳時延、平均單跳廣播進程以及消息傳播速度的計算式。仿真結果表明，MBPAB協議與BPAB、SB協議相比，降低了單跳廣播時延并且提高了消息傳播速度，增強了廣播協議的有效性和可靠性。

參考文獻

1 IEEE Std.P802.11-REVmc/D3.0.IEEE Draft Standard for Information Technology-Telecommunications and Information Exchange between Systems Local and Metropolitan Area Networks-Specific Requirements Part 11:Wireless LAN Medium Access Control（MAC）and Physical Layer（PHY）Specifications,Jun 2014

2 IEEE Std.1609.4-2010.IEEE Standard for Wireless Access in VehicularEnvironments（WAVE）-Multi-ChannelOperation,Feb2011

3 張恩展,鄺育軍.路口2-D VANET中緊急信息單跳廣播的可靠性分析.電信科學,2014,30（3）:80～86 Zhang E Z,Kuang Y J.Reliability analysis of emergency message broadcast at an intersection in 2-D VANET.Telecommunications Science,2014,30(3):80～86

4 Korkmaz G,魻zgüner F,Ekici E,et al.Urban multi-hop broadcast protocol for inter-vehicle communication systems.Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Networks（VANET’04）,Philadelphia,PA,USA,2004:76～85

5 Fasolo E,Zanella A,Zorzi M.An effective broadcast scheme for al ert message propagation in vehicular Ad Hoc networks.Proceedings of 2006 IEEE International Conference on Communications,Glasgow,Scotland,UK,2006:3960～3965

6 Bachir A,Benslimane A.A multicast protocol in Ad Hoc networks inter-vehicle geocast.Proceedings of the 57th IEEE Vehicular Technology Conference,Jeju,Korea,2003:2456～2460

7 Sahoo J,Wu E H K,Sahu P K,et al.Binary-partition-assisted MAC-layer broadcast for emergency message dissemination in VANETs.IEEE Transactions on Intelligent Transportation Systems,2011（3）:757～770

8 Hafeez K A,Zhao L,Mark J W,et al.Distributed multichannel and mobility-aware cluster-based MAC protocol for vehicular Ad Hoc networks.IEEE Transactions on Vehicular Technology,2013(8):3886～3902

9 Wisitpongphan N,Tonguz O K,Parikh J S,et al.Broadcast storm mitigation techniques in vehicular Ad Hoc networks.IEEE Wireless Communications,2007,14（6）:84～94