唐雨龍，傅 明

（長沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，長沙 410004）

考慮生存時間的DSRC自適應(yīng)退避算法

唐雨龍，傅 明

（長沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，長沙 410004）

在車輛節(jié)點(diǎn)高速移動的專用短程通信（DSRC）網(wǎng)絡(luò)中易出現(xiàn)拓?fù)浣Y(jié)構(gòu)頻繁變化和信道訪問不公平等現(xiàn)象。針對該問題，在媒體訪問控制層中，提出一種考慮信道生存時間的 DSRC退避算法。該算法利用車輛節(jié)點(diǎn)間位置及速度的相互關(guān)系動態(tài)調(diào)整節(jié)點(diǎn)的競爭窗口，實(shí)現(xiàn)信道的有序競爭。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的二進(jìn)制指數(shù)退避算法相比，該算法在改善信道訪問公平性及優(yōu)化網(wǎng)絡(luò)性能方面有較好的表現(xiàn)。

專用短程通信；車載網(wǎng)絡(luò)；IEEE802.11p協(xié)議；信道訪問公平性；退避算法

DO I：10.3969/j.issn.1000-3428.2015.10.023

1 概述

專用短程通信（Dedicate Short Range Communication，DSRC）是一種專門用于車載網(wǎng)絡(luò)通信的新興技術(shù)，也是未來智能交通系統(tǒng)（Intelligent Transport System，ITS）發(fā)展的關(guān)鍵技術(shù)。DSRC主要由車載設(shè)備（On-board Unit，OBU）、路側(cè)設(shè)備（Road-side Unit，RSU）構(gòu)成，具有實(shí)時性強(qiáng)、區(qū)域分割等特點(diǎn)［1］。DSRC已經(jīng)廣泛運(yùn)用在不停車收費(fèi)、車輛行駛安全、信息服務(wù)等領(lǐng)域，并且在車輛識別、駕駛員識別、路網(wǎng)與車輛之間信息交互等方面具備很大優(yōu)勢［2］。

車載通信包括車-車（Vehicle to Vehicle，V2V）、車-路（Vehicle to Infrastructure，V2I）2種方式，廣義上的車-路通信是包含這2種類型的通信。在車-路通信中，DSRC中的車輛節(jié)點(diǎn)并不是固定或者完全隨機(jī)地運(yùn)動，而是具有方向性、一定的規(guī)律性、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)快速變化等特點(diǎn)，這就為網(wǎng)絡(luò)設(shè)計(jì)帶來了較多的考慮因素和困難。

IEEE 802.11p協(xié)議是DSRC在MAC層和物理層的關(guān)鍵技術(shù)，該協(xié)議在IEEE 802.11標(biāo)準(zhǔn)的基礎(chǔ)上對連接建立的速度、切換頻率作出了優(yōu)化和增強(qiáng)，使其能適應(yīng)車-車、車-路的通信環(huán)境，滿足在高速移動環(huán)境下的通信需求，符合智能交通系統(tǒng)的應(yīng)用的標(biāo)準(zhǔn)［3］。IEEE 802.11p協(xié)議在MAC層采用的是分布式協(xié)調(diào)功能（Distribution Coordinate Function，DCF）訪問機(jī)制，該機(jī)制的核心就是二進(jìn)制指數(shù)退避（Binary Exponential Backoff，BEB）算法。BEB算法

雖實(shí)現(xiàn)簡單，且已廣泛應(yīng)用，但其存在的問題也比較明顯，在不同的通信場景下，BEB算法都不能有效保證節(jié)點(diǎn)公平地訪問信道。該問題在節(jié)點(diǎn)高速移動、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁變化、鏈路穩(wěn)定性較差的DSRC網(wǎng)絡(luò)中更為突出，從而容易導(dǎo)致丟包率增加，通信不公平等問題。為此，本文提出一種考慮生存時間的DSRC自適應(yīng)退避算法。

2 相關(guān)研究工作

許多因素對MAC協(xié)議的工作性能有重要影響，如節(jié)點(diǎn)數(shù)量、數(shù)據(jù)傳輸方式和類型、退避機(jī)制、節(jié)點(diǎn)的信號范圍等。而在DSRC網(wǎng)絡(luò)中，節(jié)點(diǎn)的移動特性如速度、方向、位置等也是不可忽視的方面，因此，用于DSRC的MAC協(xié)議應(yīng)當(dāng)針對網(wǎng)絡(luò)節(jié)點(diǎn)的特征而提供有效的服務(wù)。目前，關(guān)于優(yōu)化和改進(jìn)傳統(tǒng)退避算法的研究有很多，但針對車-路通信中節(jié)點(diǎn)的移動特性而言，還有進(jìn)一步研究的空間。

分析IEEE 802.11p協(xié)議的特點(diǎn)［4］可以發(fā)現(xiàn)，在DSRC網(wǎng)絡(luò)中競爭窗口值的大小關(guān)系到能否滿足節(jié)點(diǎn)的數(shù)據(jù)傳輸需求，經(jīng)過優(yōu)化退避機(jī)制的M AC層協(xié)議對于提高網(wǎng)絡(luò)吞吐量、公平性以及降低網(wǎng)絡(luò)負(fù)載等方面有重要影響。IEEE 802.11p協(xié)議通過載波偵聽多路訪問（Carrier Sense Multiple Access，CSMA）的方式，控制各節(jié)點(diǎn)的信道訪問。在網(wǎng)絡(luò)負(fù)載較高、信道較忙的情況下，該協(xié)議采用的BEB算法有可能導(dǎo)致某些節(jié)點(diǎn)長時間得不到信道的訪問機(jī)會。

文獻(xiàn)［2］通過模擬仿真指出，在采用IEEE 802.11p協(xié)議的網(wǎng)絡(luò)中，在節(jié)點(diǎn)密度高，移動速度快的場景下，傳輸時延、丟包率等性能會嚴(yán)重下降；文獻(xiàn)［5］通過仿真分析說明了車輛節(jié)點(diǎn)移動速度對MAC層信道訪問有顯著影響，指出了該協(xié)議在性能上的不足，即在數(shù)據(jù)傳輸量較大時，無法保證對時延敏感的信息進(jìn)行及時傳輸；文獻(xiàn)［6］提出了一種結(jié)合時分多址的機(jī)制，在該機(jī)制中，根據(jù)交通密度動態(tài)改變控制信道（Control Channel，CCH）和服務(wù)信道（Service Channel，SCH）的間隔，以期優(yōu)化資源分配利用減少沖突，但該機(jī)制缺陷在于其前提是每個節(jié)點(diǎn)需要知道當(dāng)前的網(wǎng)絡(luò)中的車輛密度；文獻(xiàn)［7］提出一種優(yōu)化資源分配來改進(jìn)信道訪問公平性的方法，然而該方法是著重解決能量效率問題并不適用于車載網(wǎng)絡(luò)；文獻(xiàn)［8］對IEEE 802.11p協(xié)議的控制信道進(jìn)行了分析和改進(jìn)，但只在節(jié)點(diǎn)內(nèi)部優(yōu)化了其優(yōu)先級機(jī)制，并沒有考慮到節(jié)點(diǎn)之間的競爭；文獻(xiàn)［9］指出在V 2I模式下，同一個RSU范圍內(nèi)不同速度不同數(shù)據(jù)率的車輛會影響其他車輛的通信，并提出了一種基于速度的按比例分配資源的優(yōu)化方法，但未考慮車輛所處位置造成的差異性；文獻(xiàn)［10］提出根據(jù)服務(wù)優(yōu)先級別不同而選擇不同的退避算法，實(shí)現(xiàn)多優(yōu)先級業(yè)務(wù)區(qū)分服務(wù)，然而當(dāng)無線網(wǎng)絡(luò)中沒有高優(yōu)先級業(yè)務(wù)時，低優(yōu)先級業(yè)務(wù)仍需等待較長的退避時間，造成了信道資源的浪費(fèi)；文獻(xiàn)［11］提出了一種基于相對速度的自適應(yīng)退避算法，對IEEE 802.11p協(xié)議做了針對性的優(yōu)化，但該算法在應(yīng)用中還存在一些問題，今后將對此進(jìn)行分析，并提出新的機(jī)制。

綜上所述，當(dāng)前關(guān)于退避算法的研究工作雖然很多。但針對DSRC網(wǎng)絡(luò)中節(jié)點(diǎn)的移動特征而作出相應(yīng)改進(jìn)的成果還比較少，因此，IEEE802.11p協(xié)議在這一點(diǎn)上還有進(jìn)一步優(yōu)化和改進(jìn)的需要。

3 信道生存時間及其訪問公平性問題

文獻(xiàn)［12］描述了因車載通信中不同節(jié)點(diǎn)的速度差異而導(dǎo)致的公平性問題，而這個問題在DSRC所采用的IEEE802.11p協(xié)議中仍然沒有解決。以V 2I模式為例，如圖1所示，車輛節(jié)點(diǎn)A，B同時進(jìn)入RSU的信號范圍內(nèi)（虛線圓圈所示），其中，節(jié)點(diǎn)A的速度V1大于節(jié)點(diǎn)B的速度V2，顯然，車輛A將先于車輛B駛出RSU的通信范圍，這就意味著車輛A與RSU可用的通信時間（即生存時間）少于 B，按照傳統(tǒng)的退避機(jī)制，A，B節(jié)點(diǎn)若擁有與其移動性無關(guān)的信道訪問概率，那么在同樣距離內(nèi)節(jié)點(diǎn)A所擁有與RSU通信的生存時間小于節(jié)點(diǎn)B，即節(jié)點(diǎn)A獲得信道使用的總次數(shù)將低于節(jié)點(diǎn) B，這種差距在相對速度較大的時候尤其明顯。這就是速度差異而導(dǎo)致的節(jié)點(diǎn)信道訪問不公平性，而這種不公平性在V2V模式下同樣存在。

圖1 V2I模式示意圖

由前文的分析可知，擁有較少生存時間的節(jié)點(diǎn)應(yīng)當(dāng)具有較大的信道訪問機(jī)會，反之亦然。因此，用于車載網(wǎng)絡(luò)的MAC層協(xié)議應(yīng)當(dāng)考慮節(jié)點(diǎn)不同的移動特征來提供有區(qū)別的信道訪問服務(wù)。本文算法正是為解決這個問題而提出的。

4 基于車輛相互關(guān)系的退避算法

文獻(xiàn)［11］在V 2V模式下提出了基于相對速度

的自適應(yīng)退避算法（Relative Speed-based Selfadaptive Backoff Algorithm，RSBA），旨在優(yōu)化和改進(jìn)車輛節(jié)點(diǎn)的速度差異而產(chǎn)生的信道訪問不公平的現(xiàn)象。但是該算法還存在一些問題：考慮這樣一種很容易出現(xiàn)的情況，如圖2所示，節(jié)點(diǎn)A，B，C均為行駛中的車輛，A與B在C的通信范圍內(nèi)，Vc＜Va＜Vb，但是A將先于B駛出C的通信范圍，若僅參考相對速度，那么節(jié)點(diǎn)A獲得信道訪問的概率就會低于節(jié)點(diǎn) B，這也是不公平的。此外，該算法只適用于V2V模式，并且只記錄同向車道上節(jié)點(diǎn)數(shù)據(jù)，從而無法解決雙向車道之間的信道競爭公平性問題。

圖2 V2V模式示意圖

BEB算法是DCF中的基本退避算法，第i+1次發(fā)送數(shù)據(jù)時用公式表示為：

其中，Cw是競爭窗口；Cwmin是最小競爭窗口；Cwmax是最大競爭窗口。當(dāng)節(jié)點(diǎn)發(fā)送數(shù)據(jù)成功時，競爭窗口Cw值置為最小值Cwmin，發(fā)生沖突時，則以指數(shù)增加的方式，直到達(dá)到最大值 Cwmax。前面的分析已經(jīng)指出，BEB算法不能很好保證信道訪問的公平性，尤其是針對移動場景。

為優(yōu)化和改進(jìn)DSRC環(huán)境中的信道訪問公平性問題，在分析了車輛節(jié)點(diǎn)的移動特性后，提出一種同時適用于V2V和V2I這2種模式的退避算法（Life Time Backoff Algorithm，LTBA）。

LTBA算法是基于車輛當(dāng)前行駛速度和下一跳節(jié)點(diǎn)的距離直接影響通信的生存時間這一思想而提出的，生存時間越少則應(yīng)當(dāng)擁有更高的優(yōu)先權(quán)。算法中每個節(jié)點(diǎn)根據(jù)自身的當(dāng)前速度和下一跳節(jié)點(diǎn)的距離及速度，計(jì)算在該信號范圍內(nèi)的生存時間，以此調(diào)整競爭窗口值，改進(jìn)傳統(tǒng)退避算法從而達(dá)到提高公平性和優(yōu)化網(wǎng)絡(luò)性能的目的。節(jié)點(diǎn)通信采用無線自組網(wǎng)的形式進(jìn)行數(shù)據(jù)傳輸，根據(jù)生存時間，動態(tài)調(diào)整競爭窗口以區(qū)分信道接入的優(yōu)先級。各車輛節(jié)點(diǎn)通過車載設(shè)備（如GPS終端等）獲取自身速度和位置等參數(shù)，并周期廣播該信息，動態(tài)維護(hù)一跳鄰居節(jié)點(diǎn)的信息表。

算法的基本思想是：節(jié)點(diǎn)第 i+1次競爭窗口的值與第 i次是否成功無關(guān)。設(shè)通信設(shè)備的信號的傳輸距離為 L，則車輛節(jié)點(diǎn)的當(dāng)前生存時間為ti=（L±D）/ΔV，其中，ΔV表示節(jié)點(diǎn)與下一跳通信節(jié)點(diǎn)的相對速度；D為2個節(jié)點(diǎn)的距離；正負(fù)號表示前后的位置。生存時間的大小能夠直接反映出各個車輛節(jié)點(diǎn)在該信號范圍內(nèi)所擁有的通信時間，從而以此為依據(jù)調(diào)整各節(jié)點(diǎn)的信道接入的優(yōu)先級。該算法避免了采用RSBA算法［11］而可能產(chǎn)生的問題，并且能同時適用于V2I和V 2V 2種模式下的通信。

LTBA算法的競爭窗口計(jì)算公式如下：

其中，α是影響因子，用于調(diào)整生存時間對競爭窗口的影響程度，其取值與實(shí)驗(yàn)參數(shù)及相鄰節(jié)點(diǎn)運(yùn)動情況有關(guān)，當(dāng)相鄰節(jié)點(diǎn)同方向移動時 0＜α＜1，反之α≥1。

算法的基本流程為：

（1）準(zhǔn)備發(fā)送數(shù)據(jù)；

（2）獲取自身的位置及速度；

（3）查找鄰居表中下一跳節(jié)點(diǎn)的速度和位置；

（4）計(jì)算生存時間ti；

（5）計(jì)算競爭窗口Cwi；

（6）選擇并等待退避時間結(jié)束；

（7）發(fā)送數(shù)據(jù)；

（8）若發(fā)生沖突，回到步驟（2），發(fā)送成功則繼續(xù)步驟（9）；

（9）若還有數(shù)據(jù)發(fā)送，回到步驟（2），否則結(jié)束。

5 仿真結(jié)果與分析

采用NS2作為仿真平臺比較和評價(jià)BEB，RSBA和本文提出的LTBA算法的性能。NS2是一個源代碼公開、免費(fèi)的網(wǎng)絡(luò)模擬軟件，包含的模塊涉及到網(wǎng)絡(luò)的各個層面。節(jié)點(diǎn)的運(yùn)動模型由VANETMobisim產(chǎn)生，該軟件是CanuMobiSim的一個擴(kuò)展，也是一種廣泛應(yīng)用的移動模型軟件，并且支持車輛駕駛的超車、減速等實(shí)際行為特征。CanuMobiSim是基于JAVA語言開發(fā)的移動網(wǎng)絡(luò)仿真軟件，可以產(chǎn)生不同格式的運(yùn)動文件，而且能夠支持各種網(wǎng)絡(luò)仿真平臺，如NS2，GloMoSim等。

模擬場景為5 km長的雙向四車道高速公路，每個車道寬為5 m，車輛最小速度為60 km/h，最大速度為120 km/h，車輛節(jié)點(diǎn)均設(shè)置相同的MAC層參數(shù)，所有節(jié)點(diǎn)通信距離為250 m，每個數(shù)據(jù)包的大小為1 KB，仿真時間100 s。在仿真開始之后，車輛節(jié)

點(diǎn)即開始隨機(jī)產(chǎn)生并發(fā)送消息。在不同節(jié)點(diǎn)數(shù)量的情況下，對IEEE 802.11p協(xié)議默認(rèn)的BEB算法、RSBA算法、本文算法進(jìn)行了比較。

圖3、圖4比較了3種算法的丟包率和端到端平均時延，LTBA相比另外2種算法在節(jié)點(diǎn)數(shù)量增加時，丟包率明顯減少，且平均時延也有所降低，即鏈路穩(wěn)定情況有較好的改善。在車輛節(jié)點(diǎn)較少時，網(wǎng)絡(luò)丟包率較低、時延變化緩慢是因?yàn)樾诺栏偁庉^少，隱藏終端的問題也不明顯。隨著節(jié)點(diǎn)數(shù)增加，信道訪問的競爭開始增多導(dǎo)致丟包率增加、時延增大。而當(dāng)節(jié)點(diǎn)增加到適當(dāng)區(qū)間時，丟包率變化比較穩(wěn)定，這是因?yàn)楣?jié)點(diǎn)的適當(dāng)增加，數(shù)據(jù)傳輸更容易找到下一跳節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)數(shù)目較多時，由于范圍內(nèi)信道訪問競爭激烈，由沖突導(dǎo)致丟包的概率也就會相應(yīng)增加。

圖3 丟包率對比

圖4 端到端平均時延對比

圖5 公平性指數(shù)比較

圖6比較了3種算法中平均吞吐量隨節(jié)點(diǎn)數(shù)變化的情況，可以看出，由于公平性的改進(jìn)，丟包率減少，網(wǎng)絡(luò)的性能有較好改善。

圖6 吞吐量比較

以上實(shí)驗(yàn)結(jié)果表明，考慮生存時間的退避算法LTBA能較好地提高DSRC中節(jié)點(diǎn)訪問信道的公平性，減少節(jié)點(diǎn)的信道訪問沖突，降低網(wǎng)絡(luò)丟包率，提高吞吐量和鏈路穩(wěn)定度。

6 結(jié)束語

DSRC網(wǎng)絡(luò)中的節(jié)點(diǎn)大部分是高速移動的，這就意味著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)會頻繁變化，導(dǎo)致鏈路不穩(wěn)定、通信不公平等問題，因此，優(yōu)化和改進(jìn) V2V，V2I中協(xié)議的性能成為近年來備受關(guān)注的研究熱點(diǎn)。本文分析了DSRC網(wǎng)絡(luò)的特點(diǎn)和傳統(tǒng)退避機(jī)制的不足，提出一種考慮生存時間的退避算法。該算法通過計(jì)算與下一跳節(jié)點(diǎn)的可用通信時間來分配信道訪問的優(yōu)先級進(jìn)而降低信道競爭程度，并兼容V2I和V 2V 2種通信模式。仿真結(jié)果表明，該算法能達(dá)到優(yōu)化網(wǎng)絡(luò)性能的目的，具有較好的易實(shí)現(xiàn)性和擴(kuò)展性。下一步工作將綜合考慮更多與移動性相關(guān)的參數(shù)，進(jìn)一步探討和研究該算法在真實(shí)環(huán)境中的應(yīng)用。

［1］ 張令文，劉 留，和雨佳，等.全球車載通信DSRC標(biāo)準(zhǔn)發(fā)展及應(yīng)用［J］.公路交通科技，2011，28（S1）：71-76，85.

［2］ Hafeez K A，Zhao Lian，Bobby M，et al.Performance Analysis and Enhancement of the DSRC for VANET’s Safety Applications［J］.IEEE Transactions on Vehicular Technology，2013，62（7）：3069-3083.

［3］ Chiu Kuan-Lin，Lin Chih-Che，Gupta S D，et al.A Traffic Speed Enforcement System for High Speed Environment Based on Dedicated Short-range Communications（DSRC）Technology［C］//Proceedings of International IEEE Conference on Intelligent Transportation System s.Washington D.C.，USA：IEEE Press，2013：1292-1297.

［4］ Fernandez JA，Borries K，Lin Cheng，et al.Performance of the 802.11p Physical Layer in Vehicle-to-vehicle Environments［J］.IEEE Transactions on Vehicular Technology，2012，61（1）：3-14.

［5］ Alasmary W，Zhuang Weihua.The Mobility Impact in IEEE 802.11p Infrastructureless Vehicular Networks［C］// Proceedings of the 72nd IEEE Vehicular Technology Conference.Washington D.C.，USA：IEEE Press，2010：1-5.

［6］ Guo Jinjie，Huo Yiding，Hu Chang，et al.An Adaptive and Reliable MAC Mechanism for IEEE 1609.4 and 802.11p VANETs［C］//Proceedings of the 15th International Symposium on Wireless Personal Multimedia Communications.Washington D.C.，USA：IEEE Press， 2012：55-59.

［7］ Garcia-Saavedra A，Serrano P，Banchs A，et al.Energyefficient Fair Channel Access for IEEE 802.11 WLANs［C］//Proceedings of IEEE International Symposium on World of Wireless，Mobile and Multimedia Networks.Washington D.C.，USA：IEEE Press，2011：20-24.

［8］ Yao Yuan，Rao Lei，Liu Xue.Performance and Reliability Analysis of IEEE 802.11p Safety Communication in a Highway Environment［J］.IEEE Transactions on Vehicular Technology，2013，62（9）：4198-4212.

［9］ Harigovindan V P，Babu A V，Lillykutty J.Proportional Fair Resource Allocation in Vehicle-to-infrastructure Networks for Drive-thru Internet Applications［J］.Computer Communications，2014，40（1）：33-50.

［10］ 李瑞芳，羅 娟，李仁發(fā).適于無線多媒體傳感器的MAC層退避算法［J］.通信學(xué)報(bào)，2010，31（11）：107-116.

［11］ 魏李琦，肖曉強(qiáng)，陳穎文，等.基于相對速度的802.11p車載網(wǎng)絡(luò)自適應(yīng)退避算法［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（10）：3878-3880.

［12］ Harigovindan V P，Babu A V.Ensuring Fair Access in IEEE 802.11p-based Vehicle-to-infrastructure Networks［EB/OL］.（2010-11-21）.http：//www.academ ia. edu/10659761/Ensuring-fair-access-in-IEEE-802.11pbased-vehicle-to-infrastructure-networks.

編輯 劉

冰

Adaptive Backoff Algorithm for DSRC Considering Survival Tim e

TANG Yulong，F(xiàn)U Ming
（College of Computer and Communication Engineering，Changsha University of Science&Technology，Changsha 410004，China）

In Dedicated Short Range Communication（DSRC）network，it has the phenomenon that the topology changes frequently and channel access has unfairness.Am ing at the problem，a backoff algorithm for DSRC considering survival time is proposed in the media access control layer.This algorithm adjusts the congestion window of nodes by the relationships of position and velocity of vehicles，and makes the com petition of channel access reasonable.Experimental results show that compared with the traditional binary index Backoff algorithm，this algorithm has better performance in channel access fairness and network optimization.

Dedicate Short Range Communication（DSRC）；vehicular network；IEEE 802.11p protocol；channel access fairness；backoff algorithm

唐雨龍，傅 明.考慮生存時間的DSRC自適應(yīng)退避算法［J］.計(jì)算機(jī)工程，2015，41（10）：121-125.

英文引用格式：Tang Yulong，F(xiàn)u Ming.Adaptive Backoff Algorithm for DSRC Considering Survival Time［J］.Computer Engineering，2015，41（10）：121-125.

1000-3428（2015）10-0121-05

A

TP391

國家自然科學(xué)基金資助項(xiàng)目（61303043）。

唐雨龍（1988-），男，碩士研究生，主研方向：無線傳感器網(wǎng)絡(luò)，物聯(lián)網(wǎng)；傅 明，教授、博士。

2014-10-29

2014-12-02E-m ail：281422477@qq.com