基于IEEE 802.11p的車載自組網(wǎng)MAC層接入算法RLBSA

何 晉，陳思洋，朱西平，3（.成都信息工程大學教務處 成都 605；.成都信息工程大學信息安全工程學院 成都 605；3.電子科技大學通信抗干擾國家級重點實驗室 成都 673）

基于IEEE 802.11p的車載自組網(wǎng)MAC層接入算法RLBSA

何 晉1，陳思洋2，朱西平2，3
（1.成都信息工程大學教務處 成都 610225；2.成都信息工程大學信息安全工程學院 成都 610225；3.電子科技大學通信抗干擾國家級重點實驗室 成都 611731）

基于多業(yè)務的p-persistent模型提出實時偵聽的自適應算法（RLBSA）。該算法針對VANET4種優(yōu)先級設置提出利用計算信道沖突/空閑比來優(yōu)化信道的利用率，即當信道空閑較多時，節(jié)點根據(jù)自適應策略增加發(fā)送概率；而信道沖突較多時，則降低發(fā)送概率。該算法解決了在多種優(yōu)先級業(yè)務并存的條件下需要對各個優(yōu)先級發(fā)送節(jié)點數(shù)量進行估計的問題，且可以根據(jù)網(wǎng)絡負載自適應調(diào)整刷新發(fā)送概率的時長，克服了需要預先根據(jù)網(wǎng)絡密度設置偵聽周期長度的弊端。仿真結(jié)果表明該算法可以很好解決當網(wǎng)絡中存在大量高優(yōu)先級數(shù)據(jù)時AC3業(yè)務的沖突問題，同時低優(yōu)先級數(shù)據(jù)也能保證其訪問信道的機會。

公平性；p-堅持模型；吞吐量；車載自組網(wǎng)

IEEE 802.11p協(xié)議作為美國IEEE正式頒布的VANET協(xié)議，其MAC層性能對車載自組網(wǎng)的實際部署有著重要的影響。IEEE 802.11p協(xié)議采用的EDCA（enhanced distributed coordination access）機制雖然能夠很好地區(qū)分支持不同優(yōu)先級業(yè)務的QoS，但在某些通信條件下也存在諸多限制。如文獻［1-2］指出EDCA的核心DCF（distributed coordination function）機制的廣播性能較差，當節(jié)點密度較大時，極易產(chǎn)生包碰撞。文獻［3］則指出EDCA中高優(yōu)先級數(shù)據(jù)將搶占大部分帶寬，而低優(yōu)先級數(shù)據(jù)則可能面臨被餓死的困境，提出了QATC（QoS-supporting adaptive transmission control）算法。針對DCF以及EDCA的弊端，研究人員亦作出不少研究。如文獻［4］提出了p-persistent模型，將窗口退避模型轉(zhuǎn)化為發(fā)送概率模型，以發(fā)送概率優(yōu)化為目的，提高網(wǎng)絡整體吞吐量。文獻［5］則針對IEEE 802.11e中的EDCA機制提出了多業(yè)務的p-persistent模型。目前，大多數(shù)基于p-persistent模型的算法都需要對節(jié)點數(shù)量進行估計，而數(shù)學估計方法過于繁瑣，不利于提高算法效率［3］。

本文針對DCF、EDCA機制以及基于二者算法的弊端，提出了RLSBA算法，該算法基于多業(yè)務的p-persistent模型，通過實時偵聽信道狀態(tài)，計算沖突/空閑比與發(fā)送概率，在提高系統(tǒng)吞吐量的同時降低節(jié)點間的碰撞概率，保障不同優(yōu)先級業(yè)務下的公平性。

1 p-persistent模型

1.1 單業(yè)務p-persistent模型

為了解決二進制退避算法帶來的諸多弊端與限制，文獻［4］提出了一種新的基于競爭窗口概念模型，稱之為p-persistent模型。該模型的核心思想是：一個節(jié)點以服從幾何分布的概率p進行數(shù)據(jù)發(fā)送，以（1?p）概率進行退避。其中p服從：

式中，E［B］表示平均退避時間，可進一步寫成：

式中，E［CW］為競爭窗口，因此聯(lián)立式（1）和式（2）可以得到p的表達式為：

為了評估信道在不同網(wǎng)絡吞吐量下的負載情況，文獻［4］進一步提出虛擬傳輸時間（virtualtransmissiontime，VT）概念，將其定義為連續(xù)兩個成功傳送的數(shù)據(jù)包間隔，如圖1所示。

圖1 虛擬傳輸時間劃分示意圖

從圖1可以看出，一個虛擬傳輸時間內(nèi)包括了空閑時間、沖突時間以及一次成功傳輸時間，而吞吐量可以表示為：

式中，E［L］與E［VT］分別為一次成功傳輸?shù)臄?shù)據(jù)長度以及平均虛擬傳輸時間。式（4）表明當數(shù)據(jù)長度L固定時，要使吞吐量最大化，就必須使平均虛擬傳輸時間最小。根據(jù)圖1可以有如下定義［4］：

式中，E［NC］表示平均碰撞次數(shù)，進一步有［6］：

式中，TC與TS表示一次沖突及一次成功傳輸所需時間；后3項分別表示IEEE 802.11中的SIFS、ACK以及DIFS時間。根據(jù)p-persistent模型，上述所有變量均可以由發(fā)送概率p表示，且可以得到E［VT］關(guān)于p的表達式，因此最大化Thr的問題轉(zhuǎn)化為了求合適的p值，使得E［VT］最小化。

1.2 多業(yè)務p-persistent模型

假設某個網(wǎng)絡中存在K類優(yōu)先級數(shù)據(jù)，網(wǎng)絡中的各個節(jié)點只選擇一種優(yōu)先級業(yè)務進行發(fā)送，并且第i個優(yōu)先級數(shù)據(jù)的發(fā)送節(jié)點數(shù)量為Ni［7］，則式（4）可以進一步表示為：

式中，P（i）表示優(yōu)先級為i的業(yè)務被成功發(fā)送概率。則E［NC］及E［idle］可分別表示為：

式中，δ表示一個時隙時間，即aSlotTime。根據(jù)文獻［7-10］，考慮將不同優(yōu)先級的業(yè)務按比重進行帶寬分配，以實現(xiàn)對不同業(yè)務流QoS的區(qū)分化支持。設i與j優(yōu)先級的帶寬分配比重為ri，j，聯(lián)立式（7）可得［8］：

因此，在有多個優(yōu)先級業(yè)務的網(wǎng)絡中求取系統(tǒng)的最大吞吐量即可轉(zhuǎn)化為以下兩個問題的求解：

1）求取p值以滿足式（10）給出的帶寬分配比重。

2）求取p值以滿足式（4）給出的系統(tǒng)總吞吐量并使其最大化。

上述問題的核心與單業(yè)務的p-persistent模型一致，即求各個業(yè)務的最優(yōu)傳輸概率p。盡管有諸多文獻給出了多種p值計算方法，但是絕大多數(shù)方法都是基于知道通信范圍內(nèi)發(fā)送不同優(yōu)先級業(yè)務的節(jié)點密度N為前提，并且當利用非線性方程組求解時也無法獲得唯一解。另有文獻的算法設計雖然回避了N值估計，但是各個節(jié)點的發(fā)送概率會產(chǎn)生相互依賴，且算法復雜，成本開銷較大。

2 RLSBA算法

2.1 RLBSA理論分析

在VANET中同時存在多個優(yōu)先級業(yè)務且節(jié)點數(shù)量不一，綜上可知，RLBSA的核心任務是求得發(fā)送各個優(yōu)先級業(yè)務節(jié)點的發(fā)送概率p，使得E［VT］能夠最小化，進一步最大化系統(tǒng)吞吐量。1.1節(jié)表明，當節(jié)點數(shù)量固定后E［VT］是一個關(guān)于p的函數(shù)，而通過該函數(shù)對p求導來獲取E［VT］極值的方法過于復雜，并且由于VANET拓撲變化頻繁而劇烈，對于某些參數(shù)的實時性要求很高，因此，基于上述方法并不能有效地解決p值求取問題。而文獻［6］回避了直接利用E［VT］函數(shù)求解發(fā)送概率，而使用一個虛擬傳輸時間段里面的平均數(shù)據(jù)沖突占用時長與平均空閑時長提出了一個近似優(yōu)化解：

式中，idletotal與colltotal兩個參數(shù)分別為一個虛擬傳輸時間段內(nèi)總的空閑時間長度與總的沖突時間長度。結(jié)合圖1得到：

文獻［11］通過數(shù)學證明了該近似優(yōu)化條件的有效性，即通過式（12）求得的發(fā)送概率p等同于使用E［VT］函數(shù)求解發(fā)送概率，即當p滿足式（12）時，網(wǎng)絡有最佳信道利用率且系統(tǒng)有最大吞吐量。

文獻［12-14］在多優(yōu)先級業(yè)務如采用EDCA機制的網(wǎng)絡中也將該近似優(yōu)化條件進行了擴展，并指出該近似優(yōu)化條件的實際意義在于：當節(jié)點的發(fā)送概率過大，會造成信道的嚴重沖突，數(shù)據(jù)碰撞概率大大提高，導致信道帶寬被無效使用；而如果節(jié)點的發(fā)送概率過小，又會導致信道利用率偏低，造成頻帶較大程度的浪費，因此當一段時間內(nèi)信道總的沖突時間等于總空閑時間的時候，信道利用率達到一種平衡狀態(tài)。

2.2 發(fā)送概率自適應調(diào)整策略

根據(jù)式（11）和式（12），將η=E［colltotal］/E［idlecoll］是否等于1作為判斷條件調(diào)整發(fā)送概率p是整個RLSBA算法的核心，但是在具體實施過程中還需要考慮怎樣調(diào)整p使其能快速適應網(wǎng)絡的變化，進而能夠有效地使得信道的沖突空閑比快速趨近1。因此，文獻［3］提出了一種調(diào)整策略，即：

式中，p′為調(diào)整后的發(fā)送概率。前提是需要預先人為設置偵聽周期，當達到一個周期后執(zhí)行該算法。該方法的弊端在于對于不同節(jié)點密度的網(wǎng)絡適應性較差，無法根據(jù)通信密度自動調(diào)節(jié)發(fā)送概率調(diào)整周期。因此本文提出通過設置碰撞次數(shù)上限來調(diào)整發(fā)送概率刷新周期，即當網(wǎng)絡中碰撞次數(shù)達到設定上限后，節(jié)點計算這段時間內(nèi)的沖突空閑比，再根據(jù)式（13）計算新的發(fā)送概率。在此基礎上設置一個最晚調(diào)整周期，以免在網(wǎng)絡過于稀疏，碰撞次數(shù)很難達到門限值時強制對其進行一次p值刷新。通過統(tǒng)計IEEE 802.11p原始MAC算法1s內(nèi)包碰撞次數(shù)，碰撞次數(shù)上限設置為100以內(nèi)較妥，而強制刷新周期可以據(jù)此設為1～2s。考慮當VANET的通信密度較大，即車輛節(jié)點以及分組發(fā)送頻率都較高時，碰撞次數(shù)很快就能達到門限值，因此在這種情況下車輛節(jié)點能夠很快進行自適應調(diào)整；而當網(wǎng)絡不太繁忙時，分組的碰撞次數(shù)上升較緩，因此調(diào)整速率也會隨之降低，以節(jié)約系統(tǒng)開銷成本；當網(wǎng)絡負載過輕時，車輛節(jié)點將按照最晚調(diào)整周期進行一次強制性發(fā)送概率調(diào)整。

2.3 算法描述

用idle（k）表示當網(wǎng)絡碰撞次數(shù)達到上限時該時間段內(nèi)信道空閑以及沖突的時間總長。一般情況下，為了避免idle（k）以及coll（k）的抖動跳變，算法利用加權(quán)平均對上述兩個變量進行處理［3］：

式中，a表示平滑因子。當a過大時，系統(tǒng)的歷史信息保留較多，車輛節(jié)點對于發(fā)送概率的調(diào)整不能真實反映現(xiàn)有的網(wǎng)絡狀況；而a過小時，p可能會出現(xiàn)較大的抖動，使得平滑效果變差，根據(jù)相關(guān)研究表明，當a取0.8時系統(tǒng)有較好的表現(xiàn)。當一個偵聽時間段結(jié)束后，計算：

獲得信道的空閑/沖突比值后，節(jié)點根據(jù)式（13）進行發(fā)送概率調(diào)整。在實際的應用當中，不能保證在經(jīng)過多次調(diào)整后η能達到絕對的1。為了避免這樣重復的計算浪費，應該將調(diào)整目標設立為以1為中心的區(qū)間，即［1?φ，1+φ］。當經(jīng)過調(diào)整后的η若能屬于［1?φ，1+φ］，則不進行后續(xù)調(diào)整而保持現(xiàn)有概率繼續(xù)執(zhí)行發(fā)送任務。根據(jù)相關(guān)數(shù)值分析，當φ取0.05，即當η屬于［0.95，1.05］時系統(tǒng)誤差屬于可接受范圍。假設系統(tǒng)經(jīng)過調(diào)整后的發(fā)送概率為p′k+1，則此時不再使用IEEE 802.11中的二進制退避機制，而是直接根據(jù)式（3）進行調(diào)整。經(jīng)過變形后有：

在實際的應用中，有不同的優(yōu)先級業(yè)務，因此存在差異化的初始發(fā)送概率p的賦值。設r為參考優(yōu)先級，則各優(yōu)先級初始化p值可由式（3）中給出的方法得到：

設當前發(fā)送業(yè)務優(yōu)先級為i，當網(wǎng)絡碰撞次數(shù)達到上限或者超過2s仍未達到上限時依次處理：

1）E［idle（k）］=aE［idle（k?1）］+（1?a）idle（k）；

2）E［coll（k）］=aE［coll（k?1）］+（1?a）coll（k）；

4）判斷η，如果η∈［1?φ，1+φ］，則保持pi；否則對業(yè)務i，i∈［1，K］計算：

3 算法仿真與性能仿真

本仿真場景為邊長900m的雙向四車道，節(jié)點參數(shù)設置如表1所示。

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

圖2 各優(yōu)先級業(yè)務帶寬分配對比

該場景設置節(jié)點數(shù)量為80，吞吐量比值如圖2所示。各個優(yōu)先級業(yè)務的吞吐量基本按照預設的比值在理論值附近波動，尤其是采用RLBSA后可以明顯看出即使在通信負荷較重時，高優(yōu)先級業(yè)務在享有大多數(shù)信道訪問機會的同時低優(yōu)先級業(yè)務的吞吐量也能夠得到保證，從而解決了IEEE 802.11p中低優(yōu)先級業(yè)務常被餓死的情況。

圖3 網(wǎng)絡吞吐量隨節(jié)點密度變化對比

圖3展示了當節(jié)點密度較小時，采用改進算法的網(wǎng)絡吞吐量與采用IEEE 802.11p的網(wǎng)絡吞吐量非常接近，但隨著節(jié)點密度增加，RLBSA算法明顯地降低了業(yè)務吞吐量對于節(jié)點密度的敏感性，而與之相對的IEEE 802.11p協(xié)議則產(chǎn)生了大幅的下降。因此RLBSA算法可以有效優(yōu)化在高節(jié)點密度下網(wǎng)絡的吞吐量指標。

圖4的仿真場景采用AC3單業(yè)務流作為分析條件；圖5則采用混合優(yōu)先級業(yè)務。兩張對比圖分析了RLSBA以及IEEE 802.11p機制下節(jié)點沖突次數(shù)情況的對比。

圖4 沖突次數(shù)對比

從圖4看出，當仿真開始時，由于發(fā)送概率未及時調(diào)整，因此與IEEE 802.11p算法接近，但是隨著仿真的繼續(xù)，發(fā)送概率p被不斷優(yōu)化調(diào)整，在第4s過后，采用RLBSA算法的AC3業(yè)務流沖突次數(shù)開始顯著小于IEEE 802.11p協(xié)議且逐漸趨穩(wěn)。表明了即使在城市環(huán)境下當VANET存在飽和AC3數(shù)據(jù)業(yè)務時，也能很好地控制數(shù)據(jù)沖突概率，使得網(wǎng)絡的整體性能得到保證。

圖5 不同節(jié)點密度對沖突概率的影響

圖5則表明隨著節(jié)點密度的增加，采用RLBSA算法的沖突概率呈緩慢上升趨勢，在節(jié)點密度最大處其沖突概率為0.15左右，而采用IEEE 802.11p協(xié)議的車輛節(jié)點的沖突概率明顯高出RLBSA算法，在最大節(jié)點密度處的沖突概率高出RLBSA算法近4倍。由此可以看出，RLBSA算法可以隨著網(wǎng)絡情況的變化及時作出自適應調(diào)整，并將網(wǎng)絡沖突概率限制在較小的范圍內(nèi)。

4 結(jié)束語

IEEE 802.11p雖然能夠支持對于QoS的區(qū)分化服務，并能在一定程度上保證其有效性，但是其采用的EDCA機制以及EDCA的核心二進制退避算法卻導致了當網(wǎng)絡負載較高時存在的兩個較為突出的缺陷：在網(wǎng)絡中存在大量高優(yōu)先級數(shù)據(jù)時其數(shù)據(jù)的沖突概率將大大增加，而低優(yōu)先級數(shù)據(jù)卻面臨被餓死的情況。本文基于p-persistent模型以及QATC算法提出了適用于IEEE 802.11p的RLBSA算法并優(yōu)化了發(fā)送概率p的自適應調(diào)整策略。RLBSA算法可以根據(jù)不同優(yōu)先級業(yè)務預設帶寬的分配比例進行相關(guān)業(yè)務流的發(fā)送，在保證高優(yōu)先級業(yè)務的QoS的同時保證低優(yōu)先級的數(shù)據(jù)也能按照較為穩(wěn)定的概率獲得信道接入機會，提高業(yè)務間的公平性。下一步將針對不同應用場景下發(fā)送概率自適應調(diào)整的優(yōu)化值繼續(xù)深入研究，對碰撞次數(shù)上限、最晚調(diào)整周期等技術(shù)參數(shù)的選擇開展實驗，提高業(yè)務間的公平性和系統(tǒng)的吞吐量，提高算法的可用性，實現(xiàn)對業(yè)務的精細化管理。

［1］CHEN Xian-bo，REFAI H H，MA Xiao-min.Saturation performance of IEEE 802.11 broadcast scheme in ad hoc wireless LANs［C］//VTC 2007-Fall：Proceedings of IEEE 66th Vehicular Technology Conference.New York：Institute of Electrical and Electronics Engineers Inc，2007.

［2］袁濤.基于IEEE 802.11p的車載自組網(wǎng)MAC層關(guān)鍵技術(shù)研究［D］.南京：南京郵電大學，2013.

YUAN Tao.Research on key technologies of medium access control in vehicular ad hoc networks based on IEEE 802.11p［D］.Nanjing：Nanjing University of Posts and Telecommunications，2013.

［3］毛建兵.無線局域網(wǎng)絡隨機信道接入控制機制研究［D］.成都：電子科技大學，2010.

MAO Jian-bing.Researchs on random medium access control schemes in wireless local area networks［D］.Chengdu：University of Electronic Science and Technology of China，2010.

［4］FREDERICO C，MARCO C，ENRICO G.Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit［J］.IEEE/ACM Transactions on Networking，2000，8（6）：785-799.

［5］XIAO Y.Performance analysis of priority schemes for IEEE802.11 and IEEE802.11e wireless LANs［J］.IEEE Trans on Wireless Communication，2005，4（4）：1506-1515.

［6］IEEE Std.802.11：Wireless LAN Medium Access Control（MAC）and Physical Layer（PHY）Specifications［S］//IEEE Computer Society.New York：IEEE，2007.

［7］LONG Ke-ping，LI Yun，ZHAO Wei-liang，et al.p-RWBO：a novel low-collision and QoS-supported MAC for wirelessad hoc networks［J］.Science in China Series F：Information Sciences，2008，51（9）：1193-1203.

［8］GE Ye，HOU J C，CHOI S.An analytic study of tuning systems parameters in IEEE 802.11e enhanced distributed channel access［J］.Computer Networks，2007，51（8）：1955-1980.

［9］ZHONG Fan.Throughput and QoS optimization for EDCA-based IEEE 802.11 WLANs［J］.Wireless Personal Communications，2007，43（4）：1279-1290.

［10］LI Bo，ROBERTO B，F(xiàn)ANG Yong.Achieving optimal performance by using the IEEE 802.11 MAC protocol with service differentiation enhancements［J］.IEEE Transactions on Vehicular Technology，2007，56（3）：1374-1387.

［11］RAFFAELE B，MARCO C，ENRICO G.Optimal capacity of p-persistent CSMA protocols［J］.IEEE Communications Letters，2003，7（3）：139-141.

［12］HU R Q，ZHA Wei，QIAN Yi，et al.An adaptive p-persistent 802.11 MAC scheme to achieve maximum channel throughput and QoS provisioning［C］//WCNC 2006：Proceedings of IEEE WCNC 2006.New York：IEEE，2006.

［13］ZHA Wei，HU R Q，QIAN Yi，et al.An adaptive MAC scheme to achieve high channel throughput and QoS differentiation in a heterogeneous WLAN［C］//ACM International Conference Proceeding Series：Proceedings of the 3rd International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks.New York：ACM，2006.

［14］白翔，毛玉明，冷甦鵬，等.QoS區(qū)分的自適應p-persistent MAC算法對信道利用率的動態(tài)優(yōu)化［J］.軟件學報，2009，20（3）：608-619.

BAI Xiang，MAO Yu-ming，LENG Su-peng，et al.QoS differentiation based adaptive p-persistent MAC scheme for dynamic optimization of the channel utilization［J］.Journal of Software，2009，20（3）：608-619.

編輯 稅 紅

RLBSA Algorithm for VANET MAC Layer Based on IEEE 802.11p

HE Jin1，CHEN Si-yang2，and ZHU Xi-ping2，3
（1.Teaching Affairs Office，Chengdu University of Information Technology Chengdu 610225；2.Information Security Engineering College，Chengdu University of Information Technology Chengdu 610225；3.National Key Laboratory of Science and Technology on Communications，University of Electronic Science and Technology of China Chengdu 611731）

A real-time listening based self-adaptive algorithm（RLBSA）is proposed in this paper to enhance the channel utilization rate according to the collision/idle ratio computed for four priorities of vehicular ad-hoc network（VANET）.The nodes increase the transmission probability when the channel is relatively idle and decrease when channel is relatively busy.RLBSA has no need to know the number of nodes which can hardly be acquired by using mathematical method.Moreover，RLBSA can regulate the adjustment period of transmission probability according to the network load other than the fixed period which needs to be previously set.The simulation shows that RLBSA can successfully handle the collision problem of high priority data and the starvation of low priority data in the scenario with high node density.

fairness；p-persistent model；throughput；VANET

TP301

A

10.3969/j.issn.1001-0548.2015.05.006

2014-09-01；

2015-06?25

國家自然科學基金（61071100）；四川省科技支撐計劃（2013GZ0028）；四川省教育廳科技計劃重點項目（15ZA0182）

何晉（1978-），男，副教授，主要從事無線網(wǎng)絡與通信、模式識別與智能系統(tǒng)等方面的研究.