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

唐雨龍，傅 明

（長沙理工大學計算機與通信工程學院，長沙 410004）

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

唐雨龍，傅 明

（長沙理工大學計算機與通信工程學院，長沙 410004）

在車輛節(jié)點高速移動的專用短程通信（DSRC）網(wǎng)絡(luò)中易出現(xiàn)拓撲結(jié)構(gòu)頻繁變化和信道訪問不公平等現(xiàn)象。針對該問題，在媒體訪問控制層中，提出一種考慮信道生存時間的 DSRC退避算法。該算法利用車輛節(jié)點間位置及速度的相互關(guān)系動態(tài)調(diào)整節(jié)點的競爭窗口，實現(xiàn)信道的有序競爭。實驗結(jié)果表明，與傳統(tǒng)的二進制指數(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)成，具有實時性強、區(qū)域分割等特點［1］。DSRC已經(jīng)廣泛運用在不停車收費、車輛行駛安全、信息服務(wù)等領(lǐng)域，并且在車輛識別、駕駛員識別、路網(wǎng)與車輛之間信息交互等方面具備很大優(yōu)勢［2］。

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

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

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

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

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

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

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

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

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

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

圖1 V2I模式示意圖

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

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

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

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

圖2 V2V模式示意圖

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

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

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

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

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

LTBA算法的競爭窗口計算公式如下：

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

算法的基本流程為：

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

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

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

（4）計算生存時間ti；

（5）計算競爭窗口Cwi；

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

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

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

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

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

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

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

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

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

圖3 丟包率對比

圖4 端到端平均時延對比

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

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

圖6 吞吐量比較

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

6 結(jié)束語

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

［1］ 張令文，劉 留，和雨佳，等.全球車載通信DSRC標準發(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］.通信學報，2010，31（11）：107-116.

［11］ 魏李琦，肖曉強，陳穎文，等.基于相對速度的802.11p車載網(wǎng)絡(luò)自適應(yīng)退避算法［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］.計算機工程，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

國家自然科學基金資助項目（61303043）。

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

2014-10-29

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