无线网络预约退避算法的实现和分析

吕 超， 陈向东

（西南交通大学 信息科学与技术学院，四川 成都 610031）

0 引言

目前，国内外学者从CSMA/CA退避算法方面提出了大量改进措施, 以提高IEEE802.11[1]无线局域网的性能。从这些方法中的预约退避算法着手分析，通过对NS2 网络仿真软件的IEEE802.11无线局域网仿真模块进行修改和扩展,实现和改进了预约退避算法的仿真模块,并通过大量仿真实验,对IEEE802.11无线局域网标准CSMA/CA二进制退避算法和预约退避算法的吞吐量和平均时延等方面进行了详细分析和比较。

1 MAC层退避算法

在IEEE 802.11标准中定义了两种无线介质访问控制方法，它们是：分布协调功能（DCF）和点协调功能（PCF）。DCF是 IEEE802.11最基本的媒体访问方法，其核心是CSMA/CA。IEEE802.11DCF分布式协调功能的介绍已经有很多，例如参考文献[2-4]。

基于802.11DCF的基本工作框架, 目前已提出了多种改进的退避算法, 可使MAC 协议在吞吐率、时延、公平性、稳定性等因素的一个或几个方面得到性能提升。目前主有要改进 CW更新规则类、检测网络状况动态调整参数类、动态调整接入优先级类、多阶退避类、多接入优先级类和预约发送时隙类[5]。下面主要介绍预约发送时隙类。

1.1 预约发送时隙退避算法（EBA）

目前提出的EBA( Early Backoff Announcement)[6]算法中，节点在竞争到信道后，立即计算出本节点在发送完毕后在下一次退避过程中将要使用的退避时间(如果本次发送成功)，并在发送的控制或数据报文中将此信息捎带出去，预约发送时隙。其他节点若成功收到此报文，就能预知发送节点下一次发送将要使用的时隙，如果和自己的相同，则换一个。以达到降低节点之间的碰撞。EBA的主要思想[6]如图 1所示。

EBA在MAC层标头的尾部加上一个新的3字节的预发送域。并把该标头用于发送 DATA帧时使用，并假设所有节点能量无限，能实时检测到信道情况和其他节点发送的时隙占用情况。当其他节点在收到不是发给自己的 DATA帧时能读出源节点的下次退避使用的时隙，如果和自己退避结束时刻的时隙相同，则向前向后搜索1个未预约的空闲时隙作为自己退避结束时的发送时隙。

图1 标准802.11与EBA退避时间的产生过程

在 EBA中，每个节点都有自己的预约窗口（RW，Reservation Window）[6]以记录自己和邻居节点的预约发送时隙以及占用情况。在预约窗口中记录 3个分量 Iempty、Ireserved和 Itx。Iempty表示还未被任何站点预约的时隙点，Ireserved表示已经被其他站点预约的发送时隙点，Itx表示该节点选择的下一发送时隙点。Backoff=Itxslotnumber。

1.2 改进的预约退避算法

根据EBA把预约的下次退避时间寄存在MAC层的标头中和仅在传送 DATA帧时发送的思想，简化退避记时用预约窗口的要求，减少按时隙数来区分退避时间和发送时间的麻烦，体现预约退避算法的直接想法，介绍一种简化的改进预约退避算法。即 MAC帧格式采用和 EBA相关的方法，只是MAC帧尾加一个2字节的预发送域来储存发送节点的下次退避时间。其他节点将该值来与自身退避计数器值相比较,如果相同则再次随机选取一个退避时间，从而减少节点间的碰撞。这也即是在实现方法的上的改进。

2 改进的预约退避算法在NS2上实现

NS2，即Network Simulator Version 2,是面向对象的、离散事件驱动的网络环境模拟器，主要用于解决网络研究方面的问题。NS2 提供了在无线或者有线网络上的路由、多播等多种协议的模拟，它能客观的验证网络协议的正确性和进行相关的性能测试，实现绝大多数常见的网络协议以及链路层的模型，直观的评价网络协议的性能和运行情况[7]。

在NS2中, IEEE802.11无线局域网的仿真由Mac802_11类实现。Mac802_11类定义了 IEEE802.11无线局域网标准DCF机制的所有操作方法。并详细描述对 NS2 2.31 版本中的Mac802_11类的修改和扩展, 以实现对改进预约退避算法的仿真。NS2的 IEEE820.11部分主要是由程序 mac-802_11.h、mac-802_11.cc、mac-timers.h、mac- timers.cc 等实现。而对改进预约退避算法的仿真也就是基于在这四个程序的基础上做了改进。现对源代码的主要修改做如下介绍：

（1）添加属性

（2）添加操作

①在发送数据帧前把下次将采用的退避时间写入MAC帧标头中，随数据帧一起发送给其他邻居节点包括目的节点。根据NS2中 MAC层 DCF的数据传送流程，信道竞争接入主要由check_pktTx()函数实现。所以把这流程添加到check_pktTx()函数中。基于篇幅仅给出具体改进的程序如下：

②邻居节点在收到源节点发送的数据帧时提取出帧标头中退避时间域的值，并与自身的退避时间做比较，如果一样，则更新。

③在mac-timers.h文件中添加backofftimer（）类中的子函数：void checkrtime(int cw, u_int16_t newrtime);在mac-timers.cc文件中添加checkrtime（）子函数的具体内容。并对backofftimer（）类中的子函数start（）函数做相应修改。

3 仿真与性能分析

3.1 仿真场景与参数设置

仿真场景设置为无线模式,一个中心节点只负责接收数据,四周100～200 m半径内随机分布4～16个节点，所有节点固定不动，所有的节点都处在其余所有节点的通信范围之内，也就是说网络中任意2个节点之间都能直接进行通信。这样网络中不存在隐藏节点，不用考虑路由问题。RTS门限取3000（即不使用RTS/CTS），传输层采用UDP协议，应用层采用 CBR数据流，包长为 1000 Bytes。数据传输速率为11 Mb，控制帧传输速率为1 Mb。仿真场景由NSG2生成，具体方法参见参考文献[8]。

3.2 性能分析

吞吐量分析：由图2可看出，可看出在6节点前，因为网络容量还未饱和，碰撞不激烈，随节点增多，吞吐量也增大；但在6节点后，无论是802.11DCF还是改进的预约退避算法的吞吐量都随节点的增加而减少，这也说明随着节点的增多，碰撞越来越激烈，吞吐量下降，但预约退避算法的下降速度显然要比802.11DCF平缓些，节点越多预约退避算法的优势越明显。

图2 平均吞吐量随节点数变化

时延、包投递率分析：由图3和图4所示。无论802.11DCF还是改进的预约退避算法，平均延时都随节点的增加而增大，包投递率都随节点的增加而减少。反映了随节点数增加，碰撞发生概率的增加。但改进的预约退避算法要比802.11DCF的平均延时还要小，包投递率要高，特别随着节点数增多，优势体现越明显。

图3 平均延时随节点数变化

图4 包投递率随节点数变化

4 结语

从NS2的MAC802_11类出发，分析和改进了预约退避算法，以简单的方式实现EBA的功能，并通过NS2仿真得以实现。在仿真结果中可以看出,简化的改进预约退避算法在单跳网络中性能也较好, 也能对IEEE802.11无线局域网的网络吞吐量、平均时延和包投递率有一定的提高，尤其是对吞吐量的改善。

[1]张勇,郭达.无线网状网原理与技术[M].北京:电子工业出版社，2004：20-25.

[2]孙戈.段距离无线通信及组网技术[M].西安:西安电子科技大学出版社,2008:18-23.

[3]金艳华,宋军.基于 NS2 的 IEEE802.11MAC 仿真模块分析[J].电视技术,2009,33(S2):196-199.

[4]徐春莹.WLAN上的多媒体业务质量研究[J].通信技术,2007,40(11):162-163.

[5]黎宁,韩露.无线自组织网络退避算法综述[J].计算机应用,2005,25(06):1244-1247

[6]CHOI J, YOO J, CHOI S.EBA: An Enhancement of the IEEE 802.11 DCF via Distributed Reservation. IEEE Transactions on Mobile Computing[J].2005,4(04):378-390.

[7]卢聘,王翀.基于 NS2 的轮询组网协议模拟[J].通信技术,2010,43(05):130-131.

[8]柯志亨,程容祥,邓德隽.NS2仿真实验—多媒体和无线网络通信[M].北京：电子工业出版社,2009:82-103.