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

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

（1.南京郵電大學通信與信息工程學院 南京210003；2.南京郵電大學網絡基因工程研究所 南京210003；3.國網上海市電力公司信息通信公司 上海200122；4.江蘇有線數據網絡有限公司 南京210003）

1 引言

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

IEEE 802.11p[2]協議是WAVE（wireless access in vehicular environment）協議棧的底層協議，它是IEEE 802協議族的新成員，專門用于支持車載網下的應用。目前IEEE 802.11p協議仍然處于草案階段。IEEE 802.11p將信道分為7個子信道，每個子信道是10 MHz，在5.9 GHz的頻譜之上，如圖1所示。每個子信道擁有27 Mbit/s的帶寬，保護間隔是IEEE 802.11a的兩倍，信號傳輸的范圍能夠延伸到1 km。IEEE 802.11p的物理層采用的是IEEE 802.11a傳輸技術。MAC層采用兩種訪問機制：基本接入協議是基于IEEE 802.11的DCF（distributed coordination function,分布式協調功能）機制，該機制不區分消息的優先級，節點應該在指定的時間間隔內，利用載波偵聽機制判斷信道是否空閑，通過退避減少消息間的碰撞；擴展層接入協議是基于IEEE 802.11e的EDCA機制[3]，通過EDCA（enhanced distributed channel access）機制，IEEE 802.11p可以將不同的數據流按優先級分成不同的接入類別，這樣可以保證車載應用的服務質量。EDCA定義了4個不同的接入類別，分別對應于MAC層的4個傳輸隊列。由于本文研究的是車輛間傳輸的信標信息，該消息不需要區分消息優先級類別，因此本文重點研究DCF接入機制。

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

2 相關工作

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

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

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

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

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

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

本文的貢獻如下。

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

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

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

3 信標消息性能建模

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

馬爾可夫狀態轉移概率為：

W0為最小競爭窗口值。在退避階段，節點會從[0,W0-1]隨機選擇值進行退避。

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

其中：

解式（2）得：

設τ為節點在該時刻進行信息傳輸的概率，則：

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

其中，Pc為消息產生碰撞的概率，Ps為消息成功傳輸的概率，Pb為信道繁忙的概率：

（9）

（2）考慮多個時刻時，由參考文獻[7]知：

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

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

圖2 信標消息的馬爾可夫鏈（當t=T時消息過期）

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

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

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

CEB算法具體的偽代碼如下，其中mi表示當前OI內某個特定車輛節點的過期消息數目，CWinit為IEEE 802.11p協議規定的最小競爭窗口值。

算法1 CEB算法偽代碼

if（在OI內）//統計OI內信標消息過期數目，包括收到的和在節點隊列里因過期而丟棄的

{

mi=0;

if(過期消息被丟棄)then

mi+=1;//統計當前節點過期消息數

end if

d=mi/m0;

mi=0;//在OI結尾清空區域內的值

}end if

CW=CWinit;//將IEEE 802.11p協議規定的最小競爭窗口值賦給當前的最小競爭窗口

CW=CW/d;//根據d調整最小競爭窗口的值。

if(CW≤3)

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

end if

if(CW≥15)

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

end if

end if

5 CEB性能仿真

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

圖3 NS2仿真流程

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

表1 仿真參數設置

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

圖4 廣播接收率變化

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

圖5 廣播平均到達時延變化

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

6 結束語

車載網是由車輛節點組成的移動Ad Hoc網絡，具有網絡拓撲動態變化、信道不穩定等特點。IEEE 802.11p協議中MAC層的DCF機制在高動態拓撲變化的車載網中性能并不是很好，尤其是針對車載網中的廣播消息，由于沒有反饋機制，傳統的BEB算法并不能應用在車載網中。本文針對車載網中信標消息的特性，提出基于碰撞概率和過期概率的最小競爭窗口調整算法CEB，通過優化退避機制來降低信標消息傳送過程中信道競爭程度，提高了信標消息的廣播接收率，降低了平均到達時延。

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網絡退避算法的研究.燕山大學碩士學位論文,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 魏李琦,肖曉強,陳穎文等.基于相對速度的IEEE 802.11p車載網絡自適應退避算法.計算機應用研究,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 熊棟宇,陳前斌,唐倫等.車載安全應用廣播性能分析.計算機應用研究，2010(4)