WLAN中非完全合作博弈策略的MAC协议

裴菁华

（湖北工业大学计算机学院，湖北 武汉430068）

IEEE802.11协议是无线局域网的实施标准，该标准为无线网络提供了两种媒体接入控制机制：分布式协调功能（DCF）方式和点协调功能（PCF）方式，DCF使用CSMA／CA（载波侦听多点接入／冲突避免）协议，DCF对所有类型的数据流都只提供统一的尽力而为的服务，一个站点检测到无线媒介空闲的时候才开始发送信号；PCF定义一种轮询协议，但是，DCF或者PCF都不支持任何形式的数据优先次序［1］.由于语音和多媒体在无线网络中的应用，IEEE 802.11MAC层不区分数据优先级的标准需要增加服务质量（QoS）条款.在802.11e中采用EDCA增强型分布式信道访问是基于DCF进行改进的接入方式，采用优先级分类，将业务分为4个AC（access category），指的是 Voice、Video、Best effort、Back ground的访问类别，通过区分优先级的方式，采用8个优先级来实现不同业务流的QOS的保障.但是，研究表明，当系统处于高竞争的状态下，高优先级业务会耗尽低优先级业务的资源，使低优先级数据流出现“饥饿”现象，引发公平性问题［2］.

笔者针对802.lle无线局域网中的不公平现象，将微观经济学的思想用于网络性能优化中，通过基于非完全合作博弈论的站点间信道竞争机制保证各站点获取信道访问权.仿真表明，该方法能够实现按优先级、延时以及碰撞率成比例的权重来接入信道，在保证了高优先级QoS需求的前提下，提高低优先级的吞吐量，降低时延，保证公平的信道访问机率.

1 纳什均衡

设参与信道竞争的站点为i和j，任意站点k（k＝i，j）在同一竞争时刻具有两种策略：S（发送），W（等待），任意两站点的博弈策略如图1所示.

图1 站点间的竞争策略

当节点发送分组成功时获得效用函数us，等待则获得效用函数uw，当两个站点同时发送数据流时，获得效用函数任意站点的效用值满足

假设各站点具有相同的效用值 （uc，uw，us），站点的发送概率

那么，任意站点i的效用平均值

每个用户的效用函数若要达到最大化效用函数的值，其一阶必要条件是将集合ui对τ进行微分［3］：

那么，可求得任意站点i（i1，…，n）的最优发送策略

纳什均衡表明该策略集合是所有参与者的最优战略的组合，记为其中是第i个参与者在均衡情况下的最优策略.它是i的所有可能的战略中使用户效用ui最大化的战略.ui表示所有参与人的策略组合的函数，i的最优策略通常依赖于其他参与者的战略选择.这里用τ－i＝（τ1，…，τi－1，τi＋1，…，τn）表示除了一个确定的参与者i之外的其他参与者的集合，表示由除QSTAi外的剩余所有参与者的策略组合的向量.τ＊是给定τ－i情况下第i个参与者的最优策略［4］，即

而均衡则意味着对所有站点i∈（1，2…n）均成立，所有站点最优策略的组合就是参加本次博弈的纳什均衡，两站点竞争的纳什均衡组合为

2 非完全合作博弈模型

非完全合作博弈相比合作博弈和非合作博弈而言有所不同［5］.首先，非合作博弈，WLAN中该方式充分考虑了用户节点之间互相竞争的特征，即节点自私地希望最优化自己的性能参数，从而使网络处于无序的竞争状态，虽然使用区别优先级的方式，但是在高竞争的情况下，低优先级的业务却无法保障，导致整个系统性能的降低；其次，完全合作博弈的方式并不符合实际情况中节点自私性的特点.而非完全合作博弈的方式更适合用于优化网络中的分组碰撞解决协议CSMA／CA的方式，使节点保持既竞争又合作的状态，在保障自己质量的前提下尽量保障其它的业务的质量，这样才能够得到网络整体性能都有所提升的策略，节点之间虽然没有明确的合作协议，但是却能够达到一种合作的效果［6］.

网络中各站点间竞争信道的过程主要分为两个阶段，即初始发送分组阶段和分组发生碰撞的阶段，在第一阶段的时候各站点竞争信道，在第二阶段分组发生碰撞后的各站点启动退避策略，依据这两个阶段将非完全合作博弈的机制分为两个过程：

2.1 分组初始发送策略

首先，根据各站点的优先级赋初始权值，假设站点i根据当前发送分组的权重Wi，按下式设置其初始退避时间参数 （Backoff Interval），L表示站点i发送的分组的平均长度，站点的退避时间间隔BI是时隙长度aslottime的整数倍.

2.1.1 竞争策略 站点之间的竞争针对不同优先级、延时以及碰撞率来设置权值实现，站点i的权重参数用Wi表示.站点i在博弈中具有非协作、自私特性，由式［1］可知，权重参数与退避时间成反比，Wi值越小，优先级越低，退避时间越长，站点占用信道的可能性越小，Wi值越大，优先级越高，退避时间越短，站点占用信道的可能性越大.

2.1.2 合作策略 各站点之间的合作主要由相同优先级之间和不同优先级之间的合作来实现.在实现相同优先级的业务之间，为了实现其合作性，引入了均值为1的参数s，该参数的取值范围是从0.9～1.1之间的随机变量.以避免由于相同权重站点同时发送数据流，导致信道内发生碰撞而产生恶性竞争；在不同优先级之间，为了实现其合作性，引入了参数Scalling＿Factor此参数可以根据当前信道竞争状态的动态进行调整.权重参数Wi体现了高优先级数据流相对于低优先级数据流竞争的特性，高优先级数据流与低优先级数据流之间合作的特点则通过参数Scalling＿Factor来实现：

高负载的情况下，信道竞争激烈时，为避免无序的恶性竞争导致系统性能降低，各优先级站点都要利用公式（2）增大其Scalling＿Factor参数值，延长退避时间；反之，低负载的情况下，当信道较为空闲时，各站点可以利用公式（3）减小Scalling＿Factor参数值，自利的减少退避时间，获得较高的系统吞吐量.

2.2 分组碰撞解决策略

上述的纳什均衡竞争策略虽然能够降低不同优先级站点之间的初始退避时间的可能性，但是冲突还是不能完全避免，当系统中有多个站点同时发送分组，而退避间隔在同一时刻结束，那么各站点就会再次同时发送分组，从而产生碰撞［7］.信道竞争状况与信道的竞争站点的博弈状态有关，在EDCA的服务中区分Acess Category的优先级，博弈状态不仅要考虑信道的竞争站点数，更要考虑站点携带数据流的优先级等因素.因此，这里站点的博弈状态参数包括碰撞次数 Collision［P］，参数 Collision＿Counter用来记录站点当前分组发生碰撞的次数.每次发生碰撞后，站点i按以下步骤更新其退避间隔BI和博弈状态参数：

步骤1 碰撞计数器初始值为0，发生碰撞后增加1.

步骤2 更新当前权值，由下式计算各站点的权重，每行依次表示业务优先级、延时以及碰撞次数在权值中的比例：

步骤3 根据下式更新当前退避间隔，这样就可以把业务的优先级、延时以及碰撞率等结合起来调整退避级数：

在上述对于各站点发生碰撞之后的解决策略的思想是：碰撞计时器初始值为0，站点i分组每发生一次碰撞，碰撞计数器增加1，然后根据公式更新站点i的权值，最后根据权值采用二进制退避方法来调整退避间隔BI的值［8］.

3 仿真及分析

为了简化分析，设站点内的各队列处于饱和状态，即始终都有分组待发送，每个站点只有同种类型的数据流发送，信道理想，不考虑隐藏终端和捕获效应.通过和标准的IEEE802.11eEDCA进行比较，对G－EDCA基于数据流不同的优先级，采用优先级、延时以及碰撞次数以不同的比例对不同业务设置不同的权重，并对其进行仿真及分析.本文中物理层采用IEEE802.11b的物理层参数如表1，使用802.11e协议的默认站点竞争参数见表2.

表1 802.11b物理层参数

表2 EDCA机制仿真参数

3.1 吞吐量仿真及分析

25个节点随机分布在500m×500m的场景下，仿真时间为80s.图2所示，在低负载的情况下，高优先级的业务（AC3，AC2）吞吐量呈上升趋势，随着竞争站点的增加，网络负载增大，信道竞争变得激烈，AC3，AC2逐渐下降并趋于稳定；低优先级的业务（AC1，AC0）的吞吐量却随着网络负载的增大而迅速下降，表明EDCA机制在高负载的情况下，低优先级的业务会被高优先级的业务耗尽，产生不公平.

图2 EDCA吞吐量

图3 所示，采用非完全合作博弈论竞争与合作相结合的G－DECA方法，高优先级的业务随着负载增加而上升，在竞争逐渐激烈的情况下，吞吐量相较EDCA有所降低，却并不至于影响其QOS，低优先级的业务吞吐量降低明显减慢，保障了低优先级业务的性能.

图3 图G－EDCA吐吞量

3.2 延时仿真及分析

18个节点分布在500m×1 000m的场景下，如图4所示，仿真时间为450s.从2个QSTA开始，每隔50s增加一个节点发送数据流.

图4 网络拓扑

图5 表示随着仿真时间的增加，网络中端到端的延时的变化状况.在整个过程中随着时间的增加，EDCA平均延时逐渐在增加，在60s的时候，延迟突然增大，这是因为，高优先级的业务耗尽了低优先级的业务资源，低优先级的业务出现了延迟，GEDCA可以在高竞争的情况下，提高低优先级业务的权重，保证数据流的发送，所以G－EDCA延时比较稳定.

图5 延时对比

4 结论

本文提出了一种竞争合作相结合的EDCA协议.它将EDCA与非完全合作博理论相结合，采用竞争合作的方式，在高度竞争时，各站点保证高优先级业务的前提下，增加低优先级业务的权重，给低优先级的业务更好的服务，从而保证了网络QOS.

从NS2仿真实验可以看出，与IEEE 802.11eEDCA相比，G－EDCA能够有效地提高网络的吞吐量，降低了端到端的延迟.但是，本文没有对每个QSTA发送不同类型的数据流做研究，在今后的工作中，还需要对G－EDCA做情况更加复杂的研究与验证，设计更加完善的实验模型与仿真.

［1］IEEE.Wireless LAN Medium Access Control（MAC）and Physical Layer （PHY）specifications：Medium Access Control（MAC）Quality of Service（QoS）Enhancements［S］.IEEE Standard 802.11e，2005.

［2］周立衡，章国安，邱恭安.IEEE 802.11eEDCA 竞争窗口算法的研究［J］.SCIENCE ＆ TECHNOLOGY INFORMATION.2010，（25）：19.

［3］GBianehi.Performance analysis of the IEEE802.11 distributed coordination function［J］.IEEE Journal of Selected Areas in Telceommunications.2000.3，18（3）：535－547.

［4］李明欣，陈山枝，谢东亮.异构无线网络中基于非合作博弈论的资源分配和 接入控制［J］.Journal of software.2010.8：2 037－2 049.

［5］熊启滨，胡放之.合作与非完全合作博弈理论研究综述［J］.Journal of China Three Gorges University，Humanities＆Sciences，2009，5（3）：80－83.

［6］姚 欣，曹 敏，戴琼海.无线网络的QoS控制的博弈论［J］.电信快报，2001（7）：9－10.

［7］Jia Hu，Geyong Min，Weijia Jia.Admission control in the IEEE 802.11eWLANs based on analytical modelling and game theory［J］.IEEE Communications Society，2009，（19）：379－384.

［8］LI Yishan，LI Yuhong，LI Tao.A game－theoretic resource allocation algorithm based on utility in IEEE 802.11e［J］.IEEE computer society.2011（131）：283－288.