一種802.11e EDCA機制的優化算法

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

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

1 概述

IEEE 802.11工作組于2005年底推出的802.11協議的增強協議802.11e彌補了802.11協議不能夠對不同的業務提供不同服務質量(Quality of Service, QoS)的缺陷[1]。802.11e引入了混合協調功能(Hybrid Coordination Function, HCF)機制，該機制分為增強型分布式信道訪問(Enhanced Distributed Channel Access, EDCA)和混合協調功能控制信道訪問(Hybrid Coordination Function Controlled Channel Access,HCCA)2種信道訪問方式，分別是分布式協調功能(Distributed Coordination Function, DCF)和點協調功能(Point Coordinated Function, PCF)的改進和增強版[2]。EDCA機制將業務分為為8個優先級，分別映射到 4種接入類別AC(Access Category)中，這4種接入類別優先級從低到高分別是背景流(AC_BK)、盡力而為服務(AC_BE)、視頻(AC_VI)和音頻(AC_VO)，每種接入類別均有各自的EDCA參數，可以為不同的業務提供參數化的QoS保證[3]。

EDCA在保證高優先級業務QoS的同時，是通過犧牲低優先級業務QoS來實現的[4]。當網絡中站點數目增多時，高優先級業務的吞吐量表現穩定，而低優先級業務的吞吐量迅速下降，這樣就出現了信道資源分配嚴重不公平的現象[5]。

本文提出一種改進EDCA機制的算法。該算法將信道中一部分時隙合并起來構成合并時隙(Merge Time Slot,MTS)，在這些合并時隙中可以先后發送高優先級業務和低優先級業務，而單個時隙通常只發送低優先級業務，從而達到各種業務公平利用信道資源的目的。

2 合并時隙的結構

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

圖1 合并時隙的結構

將單個時隙提供給低優先級業務接入，即在單個時隙中若有高優先級業務和低優先級業務同時競爭信道，低優先級業務優先發送。同時，低優先級業務既可以在合并時隙中發包也可以在單個時隙中發包，這樣可以大大增加低優先級業務接入信道的概率。

當一個站點有包將要在合并時隙發送時發現信道已經被更高優先級的業務占用，此時，該站點就認為發包產生了沖突，將要發送的業務進入退避過程。在退避過程中，站點的倒計數器以5個單個時隙(包括一個合并時隙和一個單個時隙)為一個單位進行計數。

3 算法模型的建立

3.1 狀態模型

MTS-EDCA算法模型是建立在文獻[7-8]模型基礎之上的。為簡化仿真分析，設一個無線局域網中存在2種業務，分別為高優先級業務AC[3]和低優先級業務AC[0]，則一個合并時隙有 2個單個時隙構成，每個站點只有一種業務發送，且每個站點都處于飽和狀態，發送 2種業務的站點數目為1:1，都為n個。

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

其歸一化公式如下：

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

業務i在第 j個退避階數的競爭窗口Wi,j與Wi,0有如下關系：

在站點都處于飽和狀態下，當一個業務的競爭窗口減小到0時，這個業務開始發包，所以，高優先級業務AC[3]在MTS發包的概率可以表示為：

低優先級業務AC[0]有可能在MTS發包，也可能在單時隙(Single Time Slot, STS)發包，所以，AC[0]發包的概率為業務在合并時隙發包的概率與在單個時隙發包的概率和，可以表示為：

由于低優先級業務既可以在合并時隙發包也可以在單個時隙發包，因此大大提高了低優先級業務發包的概率，從而改善了信道資源分配嚴重不公平的現象。

當一個以上高優先級業務在一個合并時隙中發送或者已經有一個高優先級業務接入的情況下，如果又有多個低優先級業務接入時就會發生沖突，此時，業務發包時發生沖突的概率為：

在低優先級業務發包概率增大的同時發生沖突的概率也增大。站點檢測到信道忙的概率可以表示為信道至少有一個高優先級和低優先級業務在發包的概率：

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

3.2 吞吐量模型

吞吐量為每秒鐘傳送的有效比特數。設Ps1和Ps2分別表示AC[3]和AC[0]成功發送的概率[9]，可以表示為：

設Si為業務i的吞吐量，可以表示為：

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

3.3 媒體接入控制延時模型

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

令Di,j,k為業務i從狀態(i, j, k)(j為退避階數；k為退避計數器的值)到業務發送所經歷的延遲，與狀態(i, j,0)在延時狀態上存在如下關系[6]：

第 j次退避與第 j+1次退避存在如下關系：

當業務i達到狀態 bi,m+1,0時，達到業務的最大傳輸限制，包被丟棄，最大延時 Di,m+1,0可由下式給出：

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

4 仿真結果與分析

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

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

圖2 AC[3]吞吐量對比

圖3 AC[3]延時對比

圖4和圖5顯示了低優先級AC[0]吞吐量和延時在站點數目變化的仿真情況。當站點數目增多時，AC[0]在EDCA算法下的吞吐量隨著站點數目的增多而下降非常明顯，當站點數目達到50個時，吞吐量已經下降到了非常低的水平。而本文算法 AC[0]的吞吐量下降不太明顯，且較為穩定。AC[0]在本文算法下的延時隨著站點增加明顯高于 EDCA算法的時延，這是因為在本文算法中增加了低優先級接入信道概率，同時，也增加了低優先級業務發生碰撞延時的概率，所以本文算法提高低優先級業務吞吐量是以犧牲低優先級的時延為代價的。

圖4 AC[0]吞吐量對比

圖5 AC[0]延時對比

5 結束語

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

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

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

[3]徐小軍.基于WLAN的無線網絡設計與實現[J].科技創新導報, 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.