夏汉铸+刘辉元

摘 要： 针对无线Mesh网络的网络特性，分析无线Mesh网络中的EDCA算法，提出了一种基于公平的EDCA算法，详细讨论了该算法的具体实现过程及参数变化规则，通过仿真验证了该算法提高网络的公平性同时改善网络性能，还可以达到对不同业务流的业务区分。

关键词： 无线Mesh网络； 公平性； 增强分布式信道接入； 分布式协同功能

中图分类号： TN710?34； TP393 文献标识码： A 文章编号： 1004?373X（2014）07?0021?04

Research on fairness?based EDCA algorithm in wireless Mesh networks

XIA Han?zhu1， Liu Hui?yuan2

（1. Department of Information Engineering， Zhongshan Torch Polytechnic， Zhongshan 528436， China； 2. Chongqing School of Industry， Chongqing 400043， China）

Abstract： Aiming at the network characteristic of wireless Mesh networks （WMN）， the EDCA algorithm in WMN is analyzed， and a fairness?based EDCA algorithm is provided. The implementation process and the rule of parameter variation are discussed. Through simulation， the algorithm is proved to have the characteristic of improving the fairness of the network while perfecting the network performance. What′s more， it can also realize the differentiation of different service.

Keywords： wireless Mesh network； fairness； enhanced distributed channel access； distributed coordination function

0 引 言

随着网络技术的发展和应用，用户对网络的移动性和可靠性要求越来越高，基于IEEE 802.11系列标准的无线Mesh网络[1?2]近年来得到了快速、广泛的应用。在无线Mesh网络中，任何无线设备节点都可以同时作为接入点（AP）和路由器，网络中的每个节点都可以发送和接收信号，每个节点都可以与一个或者多个对等节点进行直接通信。但由于无线网络本身的特性和多种物理层传输技术的应用，合适的媒体接入控制MAC协议对无线Mesh网络至关重要。

在无线Mesh网络中应用的MAC协议[3?5]包括：CSMA/CA、DCF、PCF等，为了在MAC子层实现对不同业务流的QoS支持，IEEE 802.11e工作组在IEEE 802.11中DCF机制的基础上提出了增强分布式信道接入机制（Enhanced Distributed Channel Access，EDCA），使得无线Mesh网络可以更好地提供音频和视频业务的服务。

EDCA将不同的业务流分为4个不同的优先等级AC（Access Categories），每一个AC对应一个队列，通过设置仲裁帧间间隔（Arbitration Interframe Space，AIFS）、最小竞争窗口值CWmin、最大竞争窗口CWmax和传输机会TXOP（Transmission Opportunity）4个参数值实现不同业务流间的业务区分。文献[6?10]研究表明，由于无线网络状况的移动性和复杂性，EDCA算法中4个参数的静态设置并不能使无线网络的性能实现最优，特别在高负载或突发业务量较大的状况下，由于无线网络中有较高的冲突率，EDCA的网络性能急剧下降，无法满足网络用户的要求。也有相关研究通过CW的自适应调整机制及相关退避算法的改进，如Lamia Romdhani提出的AEDCF机制（Adaptive EDCF，AEDCF）；Younggoo Kwon提出的快速碰撞解决机制（Fast Collision Resolutio，FCR）等，使得EDCA算法更适合无线网络环境。但这些研究都没有考虑EDCA算法本身及参数AIFS、CWmin、CWmax和TXOP调整后对无线Mesh网络公平性（节点间和不同业务流间）带来的影响。

本文提出了一种基于公平的EDCA算法（Fairness?based EDCA，FEDCA）。FEDCA算法的基本思想是通过加权轮询的方式确定传输的数据接入类别和本次信道侦听的时间，通过公平因子的计算确定TXOP参数，以达到保证网络公平性的条件下提高网络性能和QoS保证的目的。并通过仿真结果验证该算法的可行性。

1 EDCA算法

EDCA是IEEE 802.11e工作组在IEEE 802.11协议中DCF机制基础上进行QoS支持提出的，其基本的接入信道方式与DCF保持一致，各移动节点以CSMA/CA方式通过竞争获得信道接入的机会。同时EDCA提供了不同类型业务数据传输的多种信道接入类别AC，可以实现不同业务的服务区分。

1.1 EDCA算法简介

为保证不同业务的不同QoS要求，EDCA算法定义了上层的8类业务类别（Traffic Category，TC）和本层的4类基于IEEE 802.1D的接入类别（Access Category，AC），8类TC分别映射至4类AC的队列中：AC_VO，AC_VI，AC_BE和AC_BK，分别代表语音（Voice）类，视频（Video）类，尽力而为（Best Effort）类和背景（Background）类的业务。为实现4个AC队列不同优先级的区别，定义了4个参数：仲裁帧间间隔AIFS、最小竞争窗口值CWmin、最大竞争窗口CWmax和传输机会TXOP。不同的AC通过不同的参数设置，控制其接入信道的过程，从而实现了不同业务类型的区分。

某一移动节点通过两个阶段实现一个AC队列内的数据发送。首先在一个节点内部争夺传输机会TXOP，获得传输机会的队列才有可能获得信道接入的机会。其次，获得信道接入机会的分组再在不同的节点间通过CSMA/CA方式获得信道接入机会才可以进行数据传输。EDCA算法完成数据传输第一阶段的任务：不同队列通过竞争获得传输机会。

IEEE 802.11e EDCA的基本访问机制如图1所示。

图1 IEEE 802.11e EDCA的基本访问机制

当因竞争信道发生冲突时，就进入退避过程。在此过程中，将退避计数器Backoff Timer置为[0，CW[AC]]范围内的任一整数值：Backoff_Timer（BT）=uniform[0，CW]×aSlotTime。CW[AC]的初始值设为CWmin[AC]。当发生碰撞时，CW[AC]的值就增加为（CW[AC]+1）×2-1，当CW[AC]增加到CWmax[AC]时，就维持CWmax[AC]的值不变，不再增加。当数据帧成功发送之后，将CW[AC]的值重置为CWmin[AC]，继续侦听信道。退避计时器每检测到一个空闲时隙，其值（BT）减1，最先减到零的数据帧占用信道，若节点内多个AC的退避计时器同时减到零，则较高优先级队列的数据帧将占用信道，其他数据帧又进入新一轮的退避过程。

1.2 EDCA算法分析

从图1中可以看出，较高优先级的AC通过设置较小的AIFS、CWmin和CWmax将优先获得无线信道的访问权，从而实现不同不同业务的业务区分。IEEE 802.11e标准中给出了一组EDCA参数建议值， 适合于大部分情况下的网络应用。但由于无线网络本身的移动性和可扩展性，在网络规模较大或网络流量动态变化时，标准中的建议值会对无线Mesh网络各移动节点及某一节点下的不同业务流造成不公平的现象，具体体现在以下几个方面：

（1） AIFS、AIFSN设置值导致节点间的不公平性。IEEE 802.11e标准中给出AIFS[AC]=aSIFSTime+AIFSN[AC]×aSlotTime。网络中所有移动节点AIFS、AIFSN值相同，这样有可能在网络中引起准同步现象（某一节点本次通过竞争获得信道使得下次竞争获得信道的概率增大）的出现，导致无线网络中其他节点多次竞争而无法获得信道的现象频繁出现，从而使得不同节点接入信道、共享资源的不公平，同时进一步降低网络链路的利用率，影响业务流的服务质量。

（2） AIFSN值的固定设置导致不同等级业务流间的不公平。由于高优先级的AIFSN值较小，在高优先级需传输的数据较多的情况下，低优先级的业务流在竞争信道时始终无法获得信道，必然导致低优先级业务的“饥饿”现象。

（3） CWmin和CWmax的设置。从EDCA的基本访问机制来看，CW[AC]的值成为影响AC队列发送数据和发送数据失败后重新竞争获得信道的关键因素。CWmin和CWmax值虽然实现了不同业务间的业务区分，但在网络高负载情况下，同样会导致低优先级业务的“饥饿”现象。

（4） TXOP的设置。TXOP反映了获得数据发送机会的队列最大发送数据帧数。如果采用IEEE 802.11e标准中的参考值，就会导致不公平的信道竞争机制在各业务流间更大的不公平。

（5） EDCA算法没有考虑节点的移动性及信道干扰导致误码对网络公平性的影响。

基于此，为提高无线网络的公平性、网络性能及不同业务流的QoS保证，FEDCA算法对EDCA算法中的AIFSN、CWmin、CWmax和TXOP四个参数依据公平性原则进行调整，以保证移动节点间和不同等级业务间的公平。

2 FEDCA算法实现

基于以上分析，本节详细讨论无线网络中FEDCA算法具体实现过程。

2.1 FEDCA算法的实现

为保证移动节点间和同一节点内的不同等级业务流的公平，FEDCA算法实现过程可以概括为：加权轮询调度、拥塞窗口CW动态调整、公平因子计算及TXOP调整。

（1） 加权轮询调度。FEDCA算法执行模型如图2所示。

图2 FEDCA算法执行模型

加权轮询调度的思想是为保证各等级业务间的公平性，给每一子队列分配一个权值，根据不同的权值来调度不同子队列中的数据，而不是采用EDCA算法中的最小退避窗口的队列获得数据发送的机会。其具体的实现过程为每一子队列AC分配一个对应的权值[W[AC]]（该权值表明该子队列可以连续发送数据的次数），按轮询的方式为每个子队列发送数据，如果某一子队列内的数据不够发送[Wi]次或为空，转到下一子队列准备发送数据，如此轮流执行。

（2） 拥塞窗口CW动态调整。为保证各移动节点间和同一移动节点内不同等级业务的公平性和提高系统的吞吐量，FECDA算法中所有业务等级的拥塞窗口CW都采用先指数退避在线性退避的方式，即对任意队列在CWCWmax，拥塞窗口维持CWmax不变。

（3） 公平因子计算及TXOP调整。在每一轮轮询数据转发完成后，为保证同一移动节点中不同等级业务流的公平，FEDCA算法通过对每一子队列的公平因子[F[AC]]计算，并与事先规定的公平因子[FD[AC]]比较，通过比较的结果确定下一轮调度的每一子队列大小TXOP[AC]=（TXOP[AC]+ΔTXOP[AC]），其具体变化关系如图3所示。

图3 公平因子F[AC]与ΔTXOP[AC]关系示意图

2.2 FEDCA算法讨论

从FEDCA算法实现过程来看：

（1） 公平性的度量。FEDCA算法采用比例公平作为衡量公平性的标准，也就是每一类业务占用的网络资源是成比例的，这样除了可实现各等级业务间的公平外还可提高系统的吞吐量。FEDCA算法对每一类业务分配一个公平因子[FD[AC]]（[FD[AC]<1，][iFDi=1]），用于表明该类业务在本移动节点共享资源中可使用的份额；

（2） 在加权轮询调度时给每一子队列分配的权值W[AC]与关系[FD[AC]：]

[FD[AC]=W[AC]W[AC]]

（3） FEDCA算法通过轮询的方式确定可以发送的队列数据，在发送成功后其拥塞窗口CW的变化方式与EDCA算法一致，发送失败后拥塞避免的过程也与EDCA算法一致，但其拥塞窗口的变化采用FEDCA算法描述中的方法，目的是维护节点内各等级业务的公平性。

（4） 每一业务等级的公平因子[FD[AC]]计算公式为：

[F[AC]=Total?Length[AC]Total?Length[AC]]

式中：Total?Length[AC]为本轮轮询调度中队列AC被调度的数据总长度；为保证每一队列能计算出该队列在本轮调度中的公平因子[FD[AC]，]对某一队列应维护一个计数器，用于统计该队列调度的数据长度Total?Length[AC]。

（5） ΔTXOP[AC]的计算公式为：

[ΔTXOP[AC]=F[AC]-F[AC]minF[AC]max-F[AC]min×2ΔTXOP[AC]max-ΔTXOP[AC]max]

如图3所示，为了体现不同业务间的区分[ΔTXOP[高]>ΔTXOP[低]；][F[高]max>F[低]max]；[F[高]min

3 仿真分析

为了验证FEDCA算法性能，通过网络仿真工具NS2实现该算法和EDCA算法的性能比较。仿真所采用的拓扑结构如图4所示，仿真时物理层采用802.11b，物理带宽设为11 Mb/s，4个移动节点分别发送VI、VO、BE和BK四种业务流，这4种业务流占总负载的比例为1[∶]1[∶]2[∶]4。分别对FEDCA、EDCA算法的吞吐量、端到端的延迟及等级业务流量VO、VI的变化情况进行了仿真，仿真结果如图5～图7所示。

从图5的仿真结果可以看出，同一等级的业务采用FEDCA算法业务量的变化幅度及变换频率比EDCA算法要小，而且不同等级的业务量比例基本保持不变，从而保证了移动节点内各业务间的公平性；从图6仿真结果可看出FEDCA算法能提高各类业务的吞吐量，从而提高了无线信道利用率；同时图7的仿真结果表明FEDCA算法能减少数据帧的平均转发延迟，从而提高了网络的QoS。

图4 无线网络仿真的拓扑结构图

图5 VO、VI吞吐量随时间变化图

图6 吞吐量与负载关系仿真图

图7 平均延迟与负载仿真图

4 结 论

本文提出的FEDCA算法能够根据网络的公平性要求，通过加权轮询的方式解决移动节点内的不同子队列竞争信道的问题，改变拥塞窗口的变化方式，提高系统的吞吐量和公平性，通过公平因子调整EDCA算法中的TXOP参数，最终实现提高无线Mesh网络的公平性和改善网络性能的目的。通过仿真分析可知，FEDCA算法保证了移动节点间和节点内不同业务的公平性，同时能够提高网络性能和实现对不同业务的区分。

参考文献

[1] AKYILDIZ I F， WANG X D， WANG W L. Wireless mesh networks： a survey [J]. Computer Networks， 2005， 47（4）： 445?487.

[2] CHENG R G， CHANG C J， SHIH C Y， et al. A new scheme to achieve weighted fairness for WLAN supporting multimedia service [J]. IEEE Transactions on Wireless Communications， 2006， 5（5）： 1095?1102.

[3] FU Z H， LUO F H， ZERFOS P， et al. The impact of multihop wireless channel on TCP performance [J]. IEEE Transactions on Mobile Computing， 2005， 4（2）： 209?221.

[4] BIANCHI G. Performance analysis of the IEEE 802.11 distributed coordination function [J]. IEEE Journey on Selected Areas in Communications， 2000， 18（3）： 535?547.

[5] AKYOL U， ANDREWS M， GUPTA P， et al. Joint scheduling and congestion control in mobile ad hoc networks [C]// Proceedings of the 2008 27th Conference on Computer Communications. Phoenix， AZ， the USA： IEEE， 2008： 619?627.

[6] KARENOS K， KALOGERAKI V， KRISHNAMURTHY S V. Cluster?based congestion control for sensor networks [J]. ACM Transactions on Sensor Network， 2008， 4（1）： 15?18.

[7] ABRANTES F， RICARDO M. A simulation study of xcp?b performance in wireless multi?hop networks [C]// Proceedings of the 3rd ACM Workshop on QoS and Security for Wireless and Mobile Networks. Chania， Crete Island， Greece： Q2SWinet， 2007： 23?30.

[8] LIN X， SHROFF N B. Joint rate control and scheduling in multihop wireless networks [C]// Proceedings of 2004 IEEE Conference on Decision and Control. Atlantis， Paradise Island， Bahamas： IEEE， 2004： 1484?1489.

[9] CHEN L， LOW S， DOYLE J. Joint congestion control and media access control design for ad hoc wireless networks [C]// Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Miami， FL， USA： INFOCOM， 2005： 2212?2222.

[10] YI Y， SHAKKOTTAI S. Hop?by?Hop congestion control over wireless multi?hop network [J]. IEEE/ACM Transactions on Networking， 2007， 47（5）： 445?467.

[5] AKYOL U， ANDREWS M， GUPTA P， et al. Joint scheduling and congestion control in mobile ad hoc networks [C]// Proceedings of the 2008 27th Conference on Computer Communications. Phoenix， AZ， the USA： IEEE， 2008： 619?627.

[6] KARENOS K， KALOGERAKI V， KRISHNAMURTHY S V. Cluster?based congestion control for sensor networks [J]. ACM Transactions on Sensor Network， 2008， 4（1）： 15?18.

[7] ABRANTES F， RICARDO M. A simulation study of xcp?b performance in wireless multi?hop networks [C]// Proceedings of the 3rd ACM Workshop on QoS and Security for Wireless and Mobile Networks. Chania， Crete Island， Greece： Q2SWinet， 2007： 23?30.

[8] LIN X， SHROFF N B. Joint rate control and scheduling in multihop wireless networks [C]// Proceedings of 2004 IEEE Conference on Decision and Control. Atlantis， Paradise Island， Bahamas： IEEE， 2004： 1484?1489.

[9] CHEN L， LOW S， DOYLE J. Joint congestion control and media access control design for ad hoc wireless networks [C]// Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Miami， FL， USA： INFOCOM， 2005： 2212?2222.

[10] YI Y， SHAKKOTTAI S. Hop?by?Hop congestion control over wireless multi?hop network [J]. IEEE/ACM Transactions on Networking， 2007， 47（5）： 445?467.

[5] AKYOL U， ANDREWS M， GUPTA P， et al. Joint scheduling and congestion control in mobile ad hoc networks [C]// Proceedings of the 2008 27th Conference on Computer Communications. Phoenix， AZ， the USA： IEEE， 2008： 619?627.

[6] KARENOS K， KALOGERAKI V， KRISHNAMURTHY S V. Cluster?based congestion control for sensor networks [J]. ACM Transactions on Sensor Network， 2008， 4（1）： 15?18.

[7] ABRANTES F， RICARDO M. A simulation study of xcp?b performance in wireless multi?hop networks [C]// Proceedings of the 3rd ACM Workshop on QoS and Security for Wireless and Mobile Networks. Chania， Crete Island， Greece： Q2SWinet， 2007： 23?30.

[8] LIN X， SHROFF N B. Joint rate control and scheduling in multihop wireless networks [C]// Proceedings of 2004 IEEE Conference on Decision and Control. Atlantis， Paradise Island， Bahamas： IEEE， 2004： 1484?1489.

[9] CHEN L， LOW S， DOYLE J. Joint congestion control and media access control design for ad hoc wireless networks [C]// Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Miami， FL， USA： INFOCOM， 2005： 2212?2222.

[10] YI Y， SHAKKOTTAI S. Hop?by?Hop congestion control over wireless multi?hop network [J]. IEEE/ACM Transactions on Networking， 2007， 47（5）： 445?467.