一種802.11e EDCA機(jī)制的優(yōu)化算法

王 鷺，蔣 陽，郎保才，韓飛飛

(重慶大學(xué)通信工程學(xué)院，重慶 400044)

1 概述

IEEE 802.11工作組于2005年底推出的802.11協(xié)議的增強(qiáng)協(xié)議802.11e彌補(bǔ)了802.11協(xié)議不能夠?qū)Σ煌臉I(yè)務(wù)提供不同服務(wù)質(zhì)量(Quality of Service, QoS)的缺陷[1]。802.11e引入了混合協(xié)調(diào)功能(Hybrid Coordination Function, HCF)機(jī)制，該機(jī)制分為增強(qiáng)型分布式信道訪問(Enhanced Distributed Channel Access, EDCA)和混合協(xié)調(diào)功能控制信道訪問(Hybrid Coordination Function Controlled Channel Access,HCCA)2種信道訪問方式，分別是分布式協(xié)調(diào)功能(Distributed Coordination Function, DCF)和點(diǎn)協(xié)調(diào)功能(Point Coordinated Function, PCF)的改進(jìn)和增強(qiáng)版[2]。EDCA機(jī)制將業(yè)務(wù)分為為8個(gè)優(yōu)先級(jí)，分別映射到 4種接入類別AC(Access Category)中，這4種接入類別優(yōu)先級(jí)從低到高分別是背景流(AC_BK)、盡力而為服務(wù)(AC_BE)、視頻(AC_VI)和音頻(AC_VO)，每種接入類別均有各自的EDCA參數(shù)，可以為不同的業(yè)務(wù)提供參數(shù)化的QoS保證[3]。

EDCA在保證高優(yōu)先級(jí)業(yè)務(wù)QoS的同時(shí)，是通過犧牲低優(yōu)先級(jí)業(yè)務(wù)QoS來實(shí)現(xiàn)的[4]。當(dāng)網(wǎng)絡(luò)中站點(diǎn)數(shù)目增多時(shí)，高優(yōu)先級(jí)業(yè)務(wù)的吞吐量表現(xiàn)穩(wěn)定，而低優(yōu)先級(jí)業(yè)務(wù)的吞吐量迅速下降，這樣就出現(xiàn)了信道資源分配嚴(yán)重不公平的現(xiàn)象[5]。

本文提出一種改進(jìn)EDCA機(jī)制的算法。該算法將信道中一部分時(shí)隙合并起來構(gòu)成合并時(shí)隙(Merge Time Slot,MTS)，在這些合并時(shí)隙中可以先后發(fā)送高優(yōu)先級(jí)業(yè)務(wù)和低優(yōu)先級(jí)業(yè)務(wù)，而單個(gè)時(shí)隙通常只發(fā)送低優(yōu)先級(jí)業(yè)務(wù)，從而達(dá)到各種業(yè)務(wù)公平利用信道資源的目的。

2 合并時(shí)隙的結(jié)構(gòu)

本文算法首先將信道中的部分時(shí)隙合并起來構(gòu)成合并時(shí)隙，每個(gè)合并時(shí)隙都是由幾個(gè)單個(gè)時(shí)隙組成的，在每個(gè)合并時(shí)隙中，單個(gè)時(shí)隙的個(gè)數(shù)是由當(dāng)前網(wǎng)絡(luò)中存在的接入類別數(shù)量決定的。這樣信道中同時(shí)存在合并時(shí)隙和單個(gè)時(shí)隙，且合并時(shí)隙與單個(gè)時(shí)隙所占信道比例為 1:1。IEEE 802.11e定義了 4種接入類別分別是[6]AC_VO、AC_VI、AC_BE、AC_BK。若在一個(gè)無線網(wǎng)絡(luò)中存在4種接入類別的業(yè)務(wù)，則一個(gè)合并時(shí)隙中存在 4個(gè)單個(gè)時(shí)隙，在合并時(shí)隙中每個(gè)時(shí)隙都對(duì)應(yīng)一個(gè)特定的AC接入，在4個(gè)單個(gè)時(shí)隙的合并時(shí)隙中，AC_VO的業(yè)務(wù)在第1個(gè)時(shí)隙發(fā)包，AC_VI的業(yè)務(wù)在第 2個(gè)時(shí)隙發(fā)包，以此類推。合并時(shí)隙的結(jié)構(gòu)如圖1所示。

圖1 合并時(shí)隙的結(jié)構(gòu)

將單個(gè)時(shí)隙提供給低優(yōu)先級(jí)業(yè)務(wù)接入，即在單個(gè)時(shí)隙中若有高優(yōu)先級(jí)業(yè)務(wù)和低優(yōu)先級(jí)業(yè)務(wù)同時(shí)競爭信道，低優(yōu)先級(jí)業(yè)務(wù)優(yōu)先發(fā)送。同時(shí)，低優(yōu)先級(jí)業(yè)務(wù)既可以在合并時(shí)隙中發(fā)包也可以在單個(gè)時(shí)隙中發(fā)包，這樣可以大大增加低優(yōu)先級(jí)業(yè)務(wù)接入信道的概率。

當(dāng)一個(gè)站點(diǎn)有包將要在合并時(shí)隙發(fā)送時(shí)發(fā)現(xiàn)信道已經(jīng)被更高優(yōu)先級(jí)的業(yè)務(wù)占用，此時(shí)，該站點(diǎn)就認(rèn)為發(fā)包產(chǎn)生了沖突，將要發(fā)送的業(yè)務(wù)進(jìn)入退避過程。在退避過程中，站點(diǎn)的倒計(jì)數(shù)器以5個(gè)單個(gè)時(shí)隙(包括一個(gè)合并時(shí)隙和一個(gè)單個(gè)時(shí)隙)為一個(gè)單位進(jìn)行計(jì)數(shù)。

3 算法模型的建立

3.1 狀態(tài)模型

MTS-EDCA算法模型是建立在文獻(xiàn)[7-8]模型基礎(chǔ)之上的。為簡化仿真分析，設(shè)一個(gè)無線局域網(wǎng)中存在2種業(yè)務(wù)，分別為高優(yōu)先級(jí)業(yè)務(wù)AC[3]和低優(yōu)先級(jí)業(yè)務(wù)AC[0]，則一個(gè)合并時(shí)隙有 2個(gè)單個(gè)時(shí)隙構(gòu)成，每個(gè)站點(diǎn)只有一種業(yè)務(wù)發(fā)送，且每個(gè)站點(diǎn)都處于飽和狀態(tài)，發(fā)送 2種業(yè)務(wù)的站點(diǎn)數(shù)目為1:1，都為n個(gè)。

Pt1和Pt2分別表示AC[3]和AC[0]發(fā)包的概率；pc1和pc2分別表示AC[3]和AC[0]發(fā)包時(shí)發(fā)生沖突的概率；Pb為業(yè)務(wù)檢測到信道忙的概率；m表示業(yè)務(wù)的最大重傳次數(shù)；b( i, t)表示業(yè)務(wù)i在退避時(shí)的退避計(jì)數(shù)值；s( i, t)表示業(yè)務(wù)i在退避是的退避階數(shù)。隨機(jī)過程{s( i, t), b( i, t) }構(gòu)成了二維馬爾科夫過程。

其歸一化公式如下：

由式(1)～式(3)可得初始狀態(tài)bi,0,0：

業(yè)務(wù)i在第 j個(gè)退避階數(shù)的競爭窗口Wi,j與Wi,0有如下關(guān)系：

在站點(diǎn)都處于飽和狀態(tài)下，當(dāng)一個(gè)業(yè)務(wù)的競爭窗口減小到0時(shí)，這個(gè)業(yè)務(wù)開始發(fā)包，所以，高優(yōu)先級(jí)業(yè)務(wù)AC[3]在MTS發(fā)包的概率可以表示為：

低優(yōu)先級(jí)業(yè)務(wù)AC[0]有可能在MTS發(fā)包，也可能在單時(shí)隙(Single Time Slot, STS)發(fā)包，所以，AC[0]發(fā)包的概率為業(yè)務(wù)在合并時(shí)隙發(fā)包的概率與在單個(gè)時(shí)隙發(fā)包的概率和，可以表示為：

由于低優(yōu)先級(jí)業(yè)務(wù)既可以在合并時(shí)隙發(fā)包也可以在單個(gè)時(shí)隙發(fā)包，因此大大提高了低優(yōu)先級(jí)業(yè)務(wù)發(fā)包的概率，從而改善了信道資源分配嚴(yán)重不公平的現(xiàn)象。

當(dāng)一個(gè)以上高優(yōu)先級(jí)業(yè)務(wù)在一個(gè)合并時(shí)隙中發(fā)送或者已經(jīng)有一個(gè)高優(yōu)先級(jí)業(yè)務(wù)接入的情況下，如果又有多個(gè)低優(yōu)先級(jí)業(yè)務(wù)接入時(shí)就會(huì)發(fā)生沖突，此時(shí)，業(yè)務(wù)發(fā)包時(shí)發(fā)生沖突的概率為：

在低優(yōu)先級(jí)業(yè)務(wù)發(fā)包概率增大的同時(shí)發(fā)生沖突的概率也增大。站點(diǎn)檢測到信道忙的概率可以表示為信道至少有一個(gè)高優(yōu)先級(jí)和低優(yōu)先級(jí)業(yè)務(wù)在發(fā)包的概率：

從式(6)～式(10)可逐一求解 pt1、pt2、pc1、pc2、pb的值，作為下面計(jì)算的參數(shù)。

3.2 吞吐量模型

吞吐量為每秒鐘傳送的有效比特?cái)?shù)。設(shè)Ps1和Ps2分別表示AC[3]和AC[0]成功發(fā)送的概率[9]，可以表示為：

設(shè)Si為業(yè)務(wù)i的吞吐量，可以表示為：

其中，E( L)為成功傳送一次所傳送的有效載荷；TH為傳送包頭所用的時(shí)間，包頭包括 MAC包頭和 PHY頭部；TACK、TL和TL′分別是傳送 ACK包的時(shí)間、一個(gè)平均大小載荷的傳輸時(shí)間和在沖突中傳送最大載荷所耗費(fèi)的時(shí)間；Tsi為成功傳輸一次E( L)所占用信道的時(shí)間，包括傳送包頭的時(shí)間、傳送應(yīng)答幀的時(shí)間、傳輸一個(gè)平均大小載荷的時(shí)間，以及SIFS和AIFS的時(shí)間；AIFS的值根據(jù)不同優(yōu)先級(jí)而不同；Tci為站點(diǎn)發(fā)包時(shí)發(fā)生沖突所消耗的時(shí)間。

3.3 媒體接入控制延時(shí)模型

在飽和狀態(tài)下，媒體接入控制(Medium Access Control,MAC)延遲主要包括介質(zhì)訪問延遲和傳輸延遲，其中，介質(zhì)訪問延遲主要有退避時(shí)間和發(fā)生沖突后的等待時(shí)間[10]；傳輸延遲是指一個(gè)包從隊(duì)列前端準(zhǔn)備發(fā)送到最后成功發(fā)送所經(jīng)歷的時(shí)間。

令Di,j,k為業(yè)務(wù)i從狀態(tài)(i, j, k)(j為退避階數(shù)；k為退避計(jì)數(shù)器的值)到業(yè)務(wù)發(fā)送所經(jīng)歷的延遲，與狀態(tài)(i, j,0)在延時(shí)狀態(tài)上存在如下關(guān)系[6]：

第 j次退避與第 j+1次退避存在如下關(guān)系：

當(dāng)業(yè)務(wù)i達(dá)到狀態(tài) bi,m+1,0時(shí)，達(dá)到業(yè)務(wù)的最大傳輸限制，包被丟棄，最大延時(shí) Di,m+1,0可由下式給出：

在得到最大延時(shí)的值后，通過迭代的方法帶入式(18)和式(19)即可求出所有狀態(tài)延時(shí)的值。業(yè)務(wù)i總的延時(shí)由下式表示：

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

本文算法以IEEE 802.11b作為物理層，通信采用基本接入方式[11]進(jìn)行仿真。為了簡化，在仿真網(wǎng)絡(luò)中只配置了2種優(yōu)先級(jí)的業(yè)務(wù)，即AC[3]和AC[0]，并且假設(shè)在一個(gè)無線網(wǎng)絡(luò)中每個(gè)站點(diǎn)只有一種業(yè)務(wù)發(fā)送，且隨時(shí)都有業(yè)務(wù)發(fā)送，即站點(diǎn)處于飽和狀態(tài)，在這個(gè)無線網(wǎng)絡(luò)中發(fā)送 AC[0]的站點(diǎn)數(shù)目與發(fā)送 AC[3]的站點(diǎn)數(shù)目相同。設(shè)置時(shí)隙長度為 20 μs，最短幀間間隔 SIFI為 10 μs，AC[0]與 AC[3]的仲裁幀間系數(shù) AIFSN的值分別為 3和 2，數(shù)據(jù)包大小為1000 Byte，物理層頭部大小為192 bit，MAC層頭部大小為272 bit，數(shù)據(jù)率為11 Mb/s[12]。

AC[3]的吞吐量對(duì)比和延時(shí)對(duì)比如圖2、圖3所示。從圖2可以看出，當(dāng)站點(diǎn)數(shù)目較少時(shí)，本文算法跟EDCA算法的吞吐量相近，但是隨著站點(diǎn)數(shù)目的增加，本文算法的吞吐量明顯高于EDCA算法的吞吐量。從圖3可以看出，本文算法相比于EDCA算法在站點(diǎn)數(shù)目增多的情況下不會(huì)導(dǎo)致太多額外延時(shí)。

圖2 AC[3]吞吐量對(duì)比

圖3 AC[3]延時(shí)對(duì)比

圖4和圖5顯示了低優(yōu)先級(jí)AC[0]吞吐量和延時(shí)在站點(diǎn)數(shù)目變化的仿真情況。當(dāng)站點(diǎn)數(shù)目增多時(shí)，AC[0]在EDCA算法下的吞吐量隨著站點(diǎn)數(shù)目的增多而下降非常明顯，當(dāng)站點(diǎn)數(shù)目達(dá)到50個(gè)時(shí)，吞吐量已經(jīng)下降到了非常低的水平。而本文算法 AC[0]的吞吐量下降不太明顯，且較為穩(wěn)定。AC[0]在本文算法下的延時(shí)隨著站點(diǎn)增加明顯高于 EDCA算法的時(shí)延，這是因?yàn)樵诒疚乃惴ㄖ性黾恿说蛢?yōu)先級(jí)接入信道概率，同時(shí)，也增加了低優(yōu)先級(jí)業(yè)務(wù)發(fā)生碰撞延時(shí)的概率，所以本文算法提高低優(yōu)先級(jí)業(yè)務(wù)吞吐量是以犧牲低優(yōu)先級(jí)的時(shí)延為代價(jià)的。

圖4 AC[0]吞吐量對(duì)比

圖5 AC[0]延時(shí)對(duì)比

5 結(jié)束語

本文提出一種802.11e EDCA機(jī)制的改進(jìn)算法。通過對(duì)信道中時(shí)隙的調(diào)整，提高了業(yè)務(wù)的吞吐量，并且改善了信道資源分配不合理情況。仿真結(jié)果表明了該算法的有效性。今后將以業(yè)務(wù)的傳輸時(shí)延為主要研究方向，在保證傳輸業(yè)務(wù)吞吐量的前提下使傳輸延時(shí)降至最低。

[1]湯鵬杰, 唐風(fēng)仙.基于EDCA的WLAN QoS性能分析與仿真[J].微型機(jī)與應(yīng)用, 2012, 21(3): 23-25.

[2]龐 玲.無線局域網(wǎng)絡(luò)模型建立于性能分析[J].電子設(shè)計(jì)工程, 2012, 19(2): 42-44.

[3]徐小軍.基于WLAN的無線網(wǎng)絡(luò)設(shè)計(jì)與實(shí)現(xiàn)[J].科技創(chuàng)新導(dǎo)報(bào), 2012, 32(7): 50-52.

[4]IEEE.Std.802.11eTM-2005 Part 11: Wireless LAN Medium Access Control and Physical Layer Specifications Amendment 8:Medium Access Control Quality of Service Enhancements[S].2005.

[5]Bianchi G.IEEE 802.11 Saturation Throughput Analysis[J].IEEE Communications Letters, 1998, 2(12): 318-320.

[6]Choi S, Prado J D, Shankarand S S.IEEE 802.11e Contentionbased Channel Access(EDCF) Performance Evaluation[C]//Proc.of IEEE International Conference on Communications.[S.l.]: IEEE Press, 2003.

[7]Xiao Yang, Li Haizhon, Choi S.Protection and Guarantee for Voice and Video Traffic in IEEE 802.11e Wireless LANs[C]//Proc.of IEEE INFOCOM’04.[S.l.]: IEEE Press,2004.

[8]Bianchi G.Performance Analysis of the IEEE 802.11 Distributed Coordination Function[J].IEEE Journal on Selected Areas in Communications, 2000, 18(3): 535-547.

[9]Kong Zhenning.Performance Analysis of IEEE 802.11e Contention-based Channel Access[J].IEEE Journal on Selected Areas in Communications, 2004, 22(10): 2095-2106.

[10]Xiao Yang.Performance Analysis of IEEE 802.11e EDCF Under Saturation Condition[C]//Proc.of IEEE International Conference on Communications.[S.l.]: IEEE Press, 2004.

[11]Bianchi G.Performance Analysis of the IEEE 802.11 Distributed Coordination Function[J].IEEE Journal on Selected Areas in Communications, 2000, 18(3): 535-547.

[12]Abuzanat T T.FQ-EDCA: An Extension of EDCA to Improve Fairness in Ad-hoc Wireless Network[C]//Proc.of the 39th International Conference on Computers & Industrial Engineering.[S.l.]: IEEE Press, 2009.