VANET中基于碰撞概率和過期概率的自適應(yīng)退避算法研究*

劉委婉，陳志佳，劉南杰，仲 浩，趙海濤

（1.南京郵電大學(xué)通信與信息工程學(xué)院 南京210003；2.南京郵電大學(xué)網(wǎng)絡(luò)基因工程研究所 南京210003；3.國網(wǎng)上海市電力公司信息通信公司 上海200122；4.江蘇有線數(shù)據(jù)網(wǎng)絡(luò)有限公司 南京210003）

1 引言

車載自組織網(wǎng)絡(luò)[1]（vehicular Ad Hoc network，VANET）(以下簡稱車載網(wǎng)）作為智能交通系統(tǒng)的基本組成部分，是指在交通道路上車輛之間、車輛與固定接入點(diǎn)之間相互通信組成的移動Ad Hoc網(wǎng)絡(luò)。提供車輛與車輛（vehicle-tovehicle，V2V）、車輛與基礎(chǔ)設(shè)施（vehicle-to-infrastructure，V2I）之間的相互通信，用于傳遞輔助駕駛或避免事故的實(shí)時信息或提供娛樂信息、Internet接入等數(shù)據(jù)服務(wù)，為實(shí)現(xiàn)安全便捷駕駛提供了強(qiáng)大的通信支持，在事故預(yù)警、保障交通安全以及優(yōu)化交通流量等方面發(fā)揮了重要作用。

IEEE 802.11p[2]協(xié)議是WAVE（wireless access in vehicular environment）協(xié)議棧的底層協(xié)議，它是IEEE 802協(xié)議族的新成員，專門用于支持車載網(wǎng)下的應(yīng)用。目前IEEE 802.11p協(xié)議仍然處于草案階段。IEEE 802.11p將信道分為7個子信道，每個子信道是10 MHz，在5.9 GHz的頻譜之上，如圖1所示。每個子信道擁有27 Mbit/s的帶寬，保護(hù)間隔是IEEE 802.11a的兩倍，信號傳輸?shù)姆秶軌蜓由斓? km。IEEE 802.11p的物理層采用的是IEEE 802.11a傳輸技術(shù)。MAC層采用兩種訪問機(jī)制：基本接入?yún)f(xié)議是基于IEEE 802.11的DCF（distributed coordination function,分布式協(xié)調(diào)功能）機(jī)制，該機(jī)制不區(qū)分消息的優(yōu)先級，節(jié)點(diǎn)應(yīng)該在指定的時間間隔內(nèi)，利用載波偵聽機(jī)制判斷信道是否空閑，通過退避減少消息間的碰撞；擴(kuò)展層接入?yún)f(xié)議是基于IEEE 802.11e的EDCA機(jī)制[3]，通過EDCA（enhanced distributed channel access）機(jī)制，IEEE 802.11p可以將不同的數(shù)據(jù)流按優(yōu)先級分成不同的接入類別，這樣可以保證車載應(yīng)用的服務(wù)質(zhì)量。EDCA定義了4個不同的接入類別，分別對應(yīng)于MAC層的4個傳輸隊列。由于本文研究的是車輛間傳輸?shù)男艠?biāo)信息，該消息不需要區(qū)分消息優(yōu)先級類別，因此本文重點(diǎn)研究DCF接入機(jī)制。

信標(biāo)消息又叫做合作性提醒消息（cooperative awareness message，CAM），與分布式緊急消息通知（decentralized emergency notification，DEN）的不同之處在于，它不需要任何的觸發(fā)機(jī)制，每隔一定的時間都會向周圍的車輛廣播一次自身的行駛速度、方向、位置等信息，并且它的生命周期是有限的。因此，在車載網(wǎng)中需要采取有效的退避機(jī)制來保證信標(biāo)消息能夠?qū)崟r準(zhǔn)確地傳遞給周邊車輛。本文針對車載網(wǎng)中信標(biāo)消息的特性，根據(jù)分組丟失中過期消息數(shù)與預(yù)先設(shè)定門限值的相對大小提出一種新的退避算法CEB（collision-expiration back-off）。

2 相關(guān)工作

IEEE 802.11 DCF的核心是帶沖突檢測的載波偵聽多址接入（CSMA/CA）協(xié)議及隨機(jī)退避機(jī)制。DCF接入機(jī)制為：當(dāng)某個站點(diǎn)需要傳輸數(shù)據(jù)分組時，它首先偵聽信道直到檢測到信道的空閑時長達(dá)到DIFS為止。在這DIFS媒體空閑時間之后，節(jié)點(diǎn)開始在[0,CWmin-1]隨機(jī)選擇時間進(jìn)行退避，當(dāng)退避計數(shù)器為0時節(jié)點(diǎn)開始傳輸數(shù)據(jù)分組[4]。DCF采取二進(jìn)制指數(shù)退避（binary exponential back-off，BEB）算法[5]來選擇退避時間。在該算法中，節(jié)點(diǎn)在每次碰撞后會將競爭窗口（contention window，CW）值增大一倍，直到CW達(dá)到最大競爭窗口（maximum contention window，CWmax）值為止，當(dāng)節(jié)點(diǎn)成功傳輸一個信號時，就將當(dāng)前的CW值恢復(fù)為CWmin。Li J等人在參考文獻(xiàn)[6]中指出，IEEE 802.11 DCF在處理大量競爭節(jié)點(diǎn)尤其是隱藏節(jié)點(diǎn)存在的網(wǎng)絡(luò)時，性能很差；Stanica R等人在參考文獻(xiàn)[7]中對BEB算法進(jìn)行了改進(jìn)，根據(jù)信標(biāo)消息過期的特性提出了RBEB算法。在RBEB算法中，最小競爭窗口的初始值設(shè)置得相對較大，每當(dāng)有消息過期時就將競爭窗口值減半，直到達(dá)到IEEE 802.11p規(guī)定的最小值為止。一旦成功傳輸一個信標(biāo)消息，最小競爭窗口值就恢復(fù)為初始值。但是該算法主要存在以下幾個缺點(diǎn)。

·退避初始時將最小競爭窗口值設(shè)置得過大會增加信標(biāo)消息的時延。

·每當(dāng)有消息過期時就將競爭窗口值減半，競爭窗口值變化幅度過大，不能很好地反映當(dāng)前網(wǎng)絡(luò)信道的競爭情況。

圖1 IEEE 802.11p頻譜段和信道分配

·沒有考慮消息碰撞概率對網(wǎng)絡(luò)性能的影響。魏李琦等人在參考文獻(xiàn)[8]中指出車輛間的相對速度對于信道接入的公平性有重要影響，并提出基于相對速度的退避算法，該算法相對于BEB算法具有一定程度的改進(jìn)。

縱觀近年來車載網(wǎng)中信標(biāo)消息接入機(jī)制的研究工作，關(guān)于碰撞概率和過期概率對于信標(biāo)消息性能的影響并沒有給予足夠的重視，尤其是在V2V通信模式下聯(lián)合考慮碰撞消息和過期消息對最小競爭窗口進(jìn)行調(diào)整的問題。本文在RBEB算法的基礎(chǔ)上，根據(jù)其算法的不足并結(jié)合參考文獻(xiàn)[8]中的研究方法，提出一種新的基于碰撞消息概率和過期消息概率的退避算法CEB。

本文的貢獻(xiàn)如下。

·建立馬爾可夫鏈模型推出信標(biāo)消息中碰撞概率與過期概率隨最小競爭窗口的變化關(guān)系。

·結(jié)合碰撞概率和過期概率與最小競爭窗口的關(guān)系提出一種新的退避算法CEB。

·通過NS2和VanetMobiSim聯(lián)合仿真，就廣播接收率和平均到達(dá)時延的性能，將CEB算法與BEB算法及參考文獻(xiàn)[7]中提出的RBEB算法進(jìn)行了比較。

3 信標(biāo)消息性能建模

為了能夠更好地理解信標(biāo)消息的特性（考慮信標(biāo)消息具有有限的生命時長），通過建立如圖2所示的馬爾可夫鏈模型進(jìn)行分析。

馬爾可夫狀態(tài)轉(zhuǎn)移概率為：

W0為最小競爭窗口值。在退避階段，節(jié)點(diǎn)會從[0,W0-1]隨機(jī)選擇值進(jìn)行退避。

（1）單獨(dú)考慮某一時刻(t=i)的退避過程，一階馬爾可夫鏈的平穩(wěn)概率為：

其中：

解式（2）得：

設(shè)τ為節(jié)點(diǎn)在該時刻進(jìn)行信息傳輸?shù)母怕剩瑒t：

不考慮信道存在誤碼的情況，有：

其中，Pc為消息產(chǎn)生碰撞的概率，Ps為消息成功傳輸?shù)母怕?，Pb為信道繁忙的概率：

（9）

（2）考慮多個時刻時，由參考文獻(xiàn)[7]知：

其中，Pe為信標(biāo)消息過期的概率，表 示t=i時 退 避值為1的概率。根據(jù)式（9）和式（10）可知，當(dāng)增大競爭窗口W0時，消息的碰撞概率Pc會減小，而消息的過期概率Pe會增加。

綜上所述，可以得出如下結(jié)論：當(dāng)競爭窗口在一個較小范圍時，消息的碰撞概率大于消息的過期概率，而碰撞概率會隨著競爭窗口的增大而減小，因此為了增加廣播的接收率應(yīng)該增加最小競爭窗口的值；當(dāng)競爭窗口處于較大值范圍時，消息的過期概率占據(jù)主要成分，而消息的過期概率會隨著最小競爭窗口的增大而增大，所以為了增加廣播的接收率，此時應(yīng)該減小最小競爭窗口的值；當(dāng)消息的碰撞概率與過期概率達(dá)到均衡時，廣播接收率能夠達(dá)到最大值。因此最優(yōu)的競爭窗口應(yīng)該能夠保證消息的碰撞概率和過期概率之間的均衡。

圖2 信標(biāo)消息的馬爾可夫鏈（當(dāng)t=T時消息過期）

4 基于碰撞率和過期率的退避算法

為了解決V2V通信模式下信標(biāo)消息廣播接收率過低的問題，針對車載網(wǎng)中信標(biāo)消息的特性，提出一種基于碰撞消息概率和過期消息概率的退避算法CEB。由于無法統(tǒng)計分組丟失中的碰撞消息數(shù)，在本文中采取一種折中的方法：每個車輛節(jié)點(diǎn)根據(jù)本節(jié)點(diǎn)統(tǒng)計的過期消息數(shù)目與預(yù)先設(shè)定的過期消息數(shù)門限的比值動態(tài)調(diào)整最小競爭窗口值，以達(dá)到提高車載網(wǎng)中廣播接收率的目的。

CEB算法是基于信標(biāo)消息過期概率、碰撞概率與最小競爭窗口的關(guān)系這一思想而提出的，它的實(shí)現(xiàn)也十分簡單方便。每個節(jié)點(diǎn)只需要在MAC幀頭增加一個區(qū)域用于統(tǒng)計過期消息數(shù)，并設(shè)定一個合理的過期消息數(shù)門限m0（m0為經(jīng)過多次仿真后取得的合理值）。節(jié)點(diǎn)根據(jù)區(qū)域里的值與m0的大小關(guān)系進(jìn)行最小競爭窗口調(diào)整。在本文中認(rèn)為當(dāng)過期消息數(shù)小于m0時，網(wǎng)絡(luò)中的分組丟失主要由消息的碰撞導(dǎo)致，此時根據(jù)前面的分析，為了提高廣播的接收率應(yīng)該增加最小窗口的值；當(dāng)過期消息數(shù)大于m0時，認(rèn)為網(wǎng)絡(luò)中的分組丟失主要由消息過期導(dǎo)致，此時應(yīng)該減小最小競爭窗口的值；當(dāng)過期消息數(shù)為m0時，最小競爭窗口的值保持不變。在統(tǒng)計區(qū)域內(nèi)的過期消息數(shù)時，需要將時間分成周期性的觀察間 隔（observation interval，OI），每過一個OI就統(tǒng)計當(dāng)前的過期消息數(shù)目并將當(dāng)前區(qū)域內(nèi)的值清空。在本文中將OI的值設(shè)定為一個信標(biāo)消息周期。

CEB算法具體的偽代碼如下，其中mi表示當(dāng)前OI內(nèi)某個特定車輛節(jié)點(diǎn)的過期消息數(shù)目，CWinit為IEEE 802.11p協(xié)議規(guī)定的最小競爭窗口值。

算法1 CEB算法偽代碼

if（在OI內(nèi)）//統(tǒng)計OI內(nèi)信標(biāo)消息過期數(shù)目，包括收到的和在節(jié)點(diǎn)隊列里因過期而丟棄的

{

mi=0;

if(過期消息被丟棄)then

mi+=1;//統(tǒng)計當(dāng)前節(jié)點(diǎn)過期消息數(shù)

end if

d=mi/m0;

mi=0;//在OI結(jié)尾清空區(qū)域內(nèi)的值

}end if

CW=CWinit;//將IEEE 802.11p協(xié)議規(guī)定的最小競爭窗口值賦給當(dāng)前的最小競爭窗口

CW=CW/d;//根據(jù)d調(diào)整最小競爭窗口的值。

if(CW≤3)

CW=3;//如果最小競爭窗口值小于或等于3，取IEEE 802.11p規(guī)定的最小競爭窗口值的最小值3

end if

if(CW≥15)

CW=15;//如果最小競爭窗口值大于或等于15，取IEEE 802.11p規(guī)定的最小競爭窗口值的最大值15

end if

end if

5 CEB性能仿真

為了驗證CEB算法對車載網(wǎng)中信標(biāo)消息性能的影響，本文采取VanetMobiSim1.1和NS2.35進(jìn)行聯(lián)合仿真。車載網(wǎng)絡(luò)移動性模擬器VanetMobiSim[9]能夠方便地定義車輛的真實(shí)移動模型和具體移動參數(shù)。它所具有的IDM_IM模型和IDM_LC模型均考慮了真實(shí)的交通規(guī)則和場景，考慮了車輛之間的相互作用，能得到更真實(shí)的車輛移動性仿真軌跡。NS2[10]是UC Berkeley大學(xué)開發(fā)的一個離散事件仿真器，是進(jìn)行網(wǎng)絡(luò)研究主流仿真軟件之一，它的仿真過程如 圖3所 示[11]。

圖3 NS2仿真流程

在仿真平臺中，本文對直線型的高速公路進(jìn)行模擬，每個方向兩個車道共4個車道，采用IDM_LC模型。每條道路的長度為2 000 m，車輛數(shù)為10～80，廣播的通信范圍設(shè)置為300 m。具體的仿真參數(shù)見表1。

表1 仿真參數(shù)設(shè)置

圖4表示改變車輛節(jié)點(diǎn)總數(shù)時，信標(biāo)消息的廣播接收率在BEB、RBEB和CEB算法下的變化趨勢。通過對比可以發(fā)現(xiàn)，在車載網(wǎng)環(huán)境下利用CEB算法，廣播接收率的性能相比于BEB算法和RBEB算法有明顯的提高。觀察曲線可知，隨著節(jié)點(diǎn)數(shù)的增加，CEB算法的優(yōu)勢越趨明顯。這是因為CEB算法綜合考慮了信標(biāo)消息的碰撞概率和過期概率，相比于RBEB算法中只考慮信標(biāo)消息的過期概率和BEB算法只考慮信標(biāo)消息的碰撞概率來說，更能夠根據(jù)當(dāng)前的信道情況進(jìn)行最小競爭窗口的調(diào)整，使得當(dāng)前的競爭窗口值能夠最大化反映當(dāng)前網(wǎng)絡(luò)中信道的競爭情況。

圖4 廣播接收率變化

分析單個廣播接收率的曲線可以發(fā)現(xiàn)，信標(biāo)消息的廣播接收率與周圍競爭節(jié)點(diǎn)數(shù)是密切相關(guān)的。當(dāng)周圍鄰居節(jié)點(diǎn)數(shù)目較少時，信標(biāo)消息的信道訪問競爭程度輕，此外，隱藏終端的影響也較小，因此此時的廣播接收率較大；而當(dāng)周圍的鄰居節(jié)點(diǎn)數(shù)目增多時，競爭信道的節(jié)點(diǎn)增多，傳輸沖突概率增加，因此廣播接收率有所下降。

圖5 廣播平均到達(dá)時延變化

圖5 表示改變車輛節(jié)點(diǎn)總數(shù)時，信標(biāo)消息的平均到達(dá)時延在BEB、RBEB和CEB算法下的變化趨勢。通過對比可以發(fā)現(xiàn)，CEB算法在提高廣播接收率的同時也帶來了信標(biāo)平均到達(dá)時延性能的提升。這是因為相對于BEB和RBEB算法中最小競爭窗口以指數(shù)冪變化來說，CEB算法的最小競爭窗口是線性變化的，能夠較好地反映當(dāng)前網(wǎng)絡(luò)中信道的競爭情況。

6 結(jié)束語

車載網(wǎng)是由車輛節(jié)點(diǎn)組成的移動Ad Hoc網(wǎng)絡(luò)，具有網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化、信道不穩(wěn)定等特點(diǎn)。IEEE 802.11p協(xié)議中MAC層的DCF機(jī)制在高動態(tài)拓?fù)渥兓能囕d網(wǎng)中性能并不是很好，尤其是針對車載網(wǎng)中的廣播消息，由于沒有反饋機(jī)制，傳統(tǒng)的BEB算法并不能應(yīng)用在車載網(wǎng)中。本文針對車載網(wǎng)中信標(biāo)消息的特性，提出基于碰撞概率和過期概率的最小競爭窗口調(diào)整算法CEB，通過優(yōu)化退避機(jī)制來降低信標(biāo)消息傳送過程中信道競爭程度，提高了信標(biāo)消息的廣播接收率，降低了平均到達(dá)時延。

1 Preparation for Driving Implementation and Evaluation of C-2-X Communication Technology,Detailed Description of Selected Use-Cases and Corresponding Technical Requirements.Pre-Drive C2X Deliverable D4.1,2008

2 IEEE P802.11pTM/D5.0.Draft Standard for Information Technology—Telecommunications and Information Exchange between Systems-Local and Metropolitan Area Networks—Specific Requirements—Part11:Wireless LAN Medium Access Control(MAC)and Physical Layer(PHY)Specifications Amendment 7:Wireless Access in Vehicular Environments,2011

3 Rawat D B,Popescu D C,Yan G,et al.Enhancing VANET performance by joint adaptation of transmission power and contention window size.IEEE Transactions on Parallel and Distributed Systems,2011,22(9):1528～1535

4 Ma X,Chen X,Refai H H.Unsaturated performance of IEEE 802.11 broadcast service in vehicle-to-vehicle networks.Proceedings of Vehicular Technology Conference 2007,Baltimore,USA,2007:1957～1961

5 于倩.基于Ad Hoc網(wǎng)絡(luò)退避算法的研究.燕山大學(xué)碩士學(xué)位論文,2012

6 Li J,Blake C,Couto D D,et al,Capacity of Ad Hoc wireless networks.Proceedings of the ACM Annual International Conference on Mobile Computing and Networking(MOBICOM 2001),Rome,Italy,2001

7 Stanica R,Chaput E,Beylot A L.Enhancements of IEEE 802.11p protocol for access control on a VANET control channel.Proceedings of IEEE International Conference on Communications,ICC 2011,Kyoto,Japan,2011:1～5

8 魏李琦,肖曉強(qiáng),陳穎文等.基于相對速度的IEEE 802.11p車載網(wǎng)絡(luò)自適應(yīng)退避算法.計算機(jī)應(yīng)用研究,2011(10)

9 VanetMobiSim.http://vanet.eurecom.fr/,2013

10 Network Simulator 2(ns2).http://nsnam.isi.edu/nsnam/index.php/Main Page,2013

11 熊棟宇,陳前斌,唐倫等.車載安全應(yīng)用廣播性能分析.計算機(jī)應(yīng)用研究，2010(4)