一种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.