基于802.11DCF协作MAC的冲突分解算法

摘要：本文，针对MAC层中由于采用二进制指数退避算法而存在的小尺度时间上的不公平性现象和网络资源浪费的现象，改进了基于协作MAC系统的冲突分解算法。

关键词：算法；802.11

中图分类号：TN929.5 文献标识码：A文章编号：1007-9599 (2011)06-0000-03

Conflict Decomposition Algorithm ofMAC Based on 802.11DCF Collaboration

Liu Dingyu,Song Gaojun,Huang Xicheng

(Nanchang Hangkong University,Nanchang330068,China)

Abstract:In this paper,for the MAC layer due to the binary exponential backoff algorithm used to exist on a small scale the unfairness of the time phenomenon and the phenomenon of waste of network resources,improve the system based on cooperative MAC collision resolution algorithm.

Keywords:Algorithm;802.11

一、协作MAC系统

由于无线链路带宽受限，干扰和信号丢失会降低系统的吞吐量，同时由于移动终端大小和重量受限所以也不能采用传统意义上的MIMO。为了对抗阴影效应和衰落的影响，我们考虑协作的方案。因为在传统的无线局域网中低数据速率的站点对网络的吞吐量有反作用，所以采用多跳来减轻这种效果，即用高速据速率的站点帮助低数据速率的站点来进行传输。综合设计的复杂性和多跳在性能上比起两跳来说没有多少提高，故采用两跳的方案来进行分析。

协作通信[1-5]是利用信号的广播特性，通过中继转发信号并在接收端联合处理源信号和协作中继信号使得接收端获得空间分集增益的一种无线通信技术。

802.11采用多种速率调制模式[5-7]必然会导致公平性的问题，低数据速率的工作站必然比高数据速率的工作站占用更多的信道时间，这样不仅低数据速率的工作站业务质量下降，同时也会降低高数据速率工作站的带宽，从而降低了整个网络的吞吐量。当总的数据包到达速率足以使网络饱和时，系统吞吐量明显低于11Mbps，因为只有很少一部分站点能够传输11Mbps，同时由于的开销和碰撞也降低了吞吐量。随着站点个数的增加，对传统的系统802.11b来说由于碰撞的增加，吞吐量逐渐下降，但对于协作MAC系统来说由于低速率站点能够找到高速率的两跳路径的可能性增加，吞吐量也逐渐上升。随着站点个数的增加，对协作系统来说相对系统吞吐量有增加的趋势。

二、改进算法描述

针对二进制指数退避算法存在的问题，国际国内己经进行了大量的研究。其基本思想是当发送端发送数据的时候，数据包发生了冲突，说明此时信道繁忙，在发送端重发之前，先要随机退避一个时间段，以降低再次的冲突的可能性，这个随机的时间段由退避算法产生。当网络站点数不同时，相应的信道争夺程度也不同，对应的退避值选取也不同。

在传统的协作MAC中采用的策略是每个站点竞争窗口加倍然后再选择一个随机退避时隙重新竞争信道，本文提出了一种基于协作MAC的新的冲突分解算法。

改进算法：

1.当站点监听到物理信道空闲时间超过分布式协作模式帧间隔后，在发送数据前生成一个随机退避时间以推迟接入信道，如果其本身退避时间为非零值，则不需要选择随机退避时间。当退避计时器递减为零时，站点发送请求发送信号。

2.如果多个站点同时竞争信道时发生了碰撞则让新到达的站点在系统外等待，在参与碰撞的站点集合均成功传输结束后，再让新到达的站点传输，即发生碰撞的站点的传输优先级大于未发生碰撞的站点。

3.当传输发生碰撞的站点集合时，设置采用协作传输的站点具有比直传站点更高的优先级，优先传输协作站点的数据。

4.所有发生碰撞的站点集合均采用经典的树形分裂算法来进行冲突分解。

三、仿真实验与结论

本文采用蒙特卡洛方法进行仿真，站点随机分布在一个半径为100m的圆内，接入点（AP）在圆的中心点处。不同站点到AP的距离与传输速率之间的关系如表1所示：例如当站点距离接入点的距离大于67.1而小于74.7的时候，该站点的传输速率为2Mbps。当源站点STA1到中继站点STA2的传输速率为11Mbps，中继站点STA2到接入点AP的速率为5.5Mbps，源站点STA1可以以两跳速率分别为11Mbps，5.5Mbps的速率进行数据传输。假设系统处于饱和状态，即在每个站点处一直有数据包在等待传输，仿真时间为90秒，数据包的长度为1024字节，产生速率为100数据包/秒，且服从泊松分布，数据传输失败后最大重传次数为5。系统仿真参数如表2所示，其中Channel Rate表示信令传输的基本速率，Slot Time表示一个时隙的大小，Wmin，Wmax表示最小竞争窗口和最大竞争窗口的大小。Retry limit表示数据最大重传次数。

图1表示数据包的长度，可以看出随着数据包长度的增加系统的吞吐量呈现不断增长的趋势，系统的吞吐量随着站点数目的增加都能够趋近于稳定状态，当数据包的长度为512比特，1024比特，2048比特时，系统的吞吐量分别稳定于1.1Mbps，2.14Mbps，4.42Mbps。

图2结果表明，总体上看系统的吞吐量随着站点数的增加而增加并逐渐趋于平稳即达到平稳状态，采用新的冲突分解算法协作MAC系统与采用二进制指数退避算法的MAC协作系统相比并没有明显的变化，当站点个数为20时，系统吞吐量仅仅降低0.04Mbps，系统吞吐量下降仅为1.8%，而当站点个数更少时系统吞吐量下降越来越小，当站点个数小于10时，系统吞吐量基本没有变化。

如图3点数为20时，系统处于饱和状态下，在采用传统的二进制算法情况下，发送数据包最少的站点与发送数据包最多的站点的吞吐量之比仅为77%，而在采用新的冲突分解算法后，发送数据包最少的站点与发送数据包最多的站点的吞吐量之比提高到了90%以上，每个站点在仿真时间（90秒）内秒发送的数据包个数趋近相同。因此系统在小尺度时间上的公平性得到了很大的改善。造成这种现象的主要原因是由于采用新的冲突分解算法后在短时间内所有发生碰撞的站点都能够成功传输数据，而不会出现某个站点饿死的现象。

参考文献：

[1]IEEEStd802.11-1997 InformationTechnology-telecommunicationsAnd InformationexchangeBetweenSystems-LocalAndMetropolitanArea Networks-specificRequirements-part 11:Wireless Lan Medium Access Control(MAC)And Physical Layer(PHY)Specifications.18 November 1997 Page(s):iC445

[2]IEEE802.11a, SupplementtoIEEEStandardforInformationtechnology andTelecommunications and information exchange between systems-part11:Wireless LANMedium Access Control(MAC)and Physical Layer(PHY)speciation Higher-Speed PhysicalLayer Extension in the 5GHz Band,1999.

[3] IEEE802.11b,Supplement to IEEE Standard for Information technology and Telecommunications and information exchange between systems-part 11:Wireless LAN Medium Access Control(MAC)and Physical Layer(PHY)speciation Higher-Speed PhysicalLayer Extension in the 2.4GHz Band,1999

[4]IEEEstandard for information technology-telecommunications and information exchangebetween systems-local and metropolitan area networks-specific requirement.Part 11:wireless LAN medium access control(MAC)and Physical layer(PHY)specifications.Amendment 2:higher-speed physical lyaer(PHY)extension in the 2.4 GHz band,1999

[5]徐晓惠.无线接入网关键技术[博士学位论文].清华大学电子工程系,2006

[6]V.Bharghavan，“MACAW: A Media Access Protocol for WirelessLAN’s”，SIGCOMM’94,PP.212-225,London,England,Aug,1994

[7]A.Sendonaris,E.Erkip, and B. Aazhang, “Increasing uplink capacity via user cooperation diversity,” in Proc. IEEE Int. Symp. InformationTheory (ISIT), Cambridge, MA, Aug. 1998, p. 156

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文