基于DCF退避机制的算法改进及其应用

张应征, 朱 燕



基于DCF退避机制的算法改进及其应用

张应征*1, 朱 燕2

(1. 湖南工程职业技术学院 信息工程系, 湖南 长沙, 410004; 2. 华中科技大学 计算机学院, 湖北 武汉, 430074)

无线局域网络技术中采用的基本接入方式是分布式控制DCF方法, 但它需要解决2个问题: 一是由多个节点同时发送数据帧而出现碰撞的情况; 二是随着网络总业务量的增多或出现突发状况时, 急剧增大的碰撞率情况. 为此, 采用改进的退避机制的算法, 以减少节点接入网络时冲突的方法, 提高MAC协议的整体性能, 并通过建立仿真子网模型予以应用测试. 结果表明, 这种方法提高了网络吞吐量, 解决了网络拥堵问题, 提高了通信效率.

退避算法; 无线网络; 仿真建模

无线局域网络技术起源于二战时美军研发的无线传输技术, 后经过科研人员对其封包式技术的改进,由IEEE802工作组在1997年6月发布的802.11协议成为无线局域网的第一代协议, 在1999年又发布了补充的802.11b协议, 随后又推出了802.11a、802.11g等, 最后形成一系列的802.11x协议, 成为无线局域网的标准[1]. 而802.11x系列协议标准的重点就是MAC(Media Access Control)层的协议, 其功能主要包括控制无线介质访问、提供有效的数据通信. 而作为IEEE 802.11 MAC层的DCF (Distributed Coordination Function)——分布式协调功能, 则用来提供异步的数据服务, 各个终端节点通过竞争的方式来使用信道, 主要包括载波监听机制、随机退避机制和帧间隔方法, 是一种无线网络中节点共享无线信道来进行传输数据的方式, 但这种方法需要解决多个节点同时发送数据帧而出现的碰撞情况.实践数据表明, 引入改进的二进制退避机制, 可使得数据帧发生碰撞几率显著减少, 具有提高通信效率的功能.

1 二进制指数退避算法

对IEEE 802.11 MAC层的DCF中的退避机制研究, 其核心是研究在DCF中采用的退避算法, 标准退避算法是二进制指数退避(Binary Exponential Backoff, BEB), 如下:

BEB算法在某些情况下解决了信道争用问题, 但是也存在2个缺点:

(a) 前一次成功发送的节点值立刻回到初始大小, 而其他不成功的节点值较大, 因此在某一小段时间内对于刚成功发送的节点再次竞争信道的概率大大增加, 从而造成不公平性现象, 并导致时延大范围抖动.

(b) 当网络节点数较多, 负载比较严重时, 节点每次成功发送后都将重置为min, 可能会引起更多的数据冲突, 不能正确反映当前信道竞争使用情况, 由于数据冲突和退避机制也要浪费时间, 从而造成系统的吞吐量急剧下降.

因此, 在BEB中节点的随机时间窗口设置就成为一个很重要的问题: 随机时间过小则冲突比较严重, 而过大则浪费严重.

2 退避算法的改进

BEB算法适合于负载比较轻的环境, 对于负载过重性能就会急剧下降, 为了能让节点更快地达到公平的竞争状态, 提高整个网络的性能, 在此基础上, 需要进行退避算法的改进[2]. 改进的退避算法描述如图1所示. 引入一个中间参数mid(min＜mid＜max), 作为区分节点竞争程度的阀值. 同时结合其他退避算法的取值, 考虑将初始竞争窗口设置min为2,max为1 024,min为32.

(a) 初始时网络负载较轻, 其竞争窗口≤mid时, 若发生冲突数据包发送失败, 则竞争窗口和BEB一样增长为原来的2倍; 若数据包发送成功, 竞争窗口线性减少, 在原窗口基础上减1, 避免竞争窗口下降过快引起更多的冲突.

(b) 当网络负载较多, 其竞争窗口＞mid时, 若数据包发送失败, 则竞争窗口值和BEB一样增长为原来的2倍; 当数据包发送成功后, 竞争窗口值不直接降到最小min, 而是在原窗口基础上除以4, 让竞争窗口快速降到mid附近, 防止过度空闲而使得信道利用率下降.

图1 改进的退避算法描述图

改进的退避算法如下:

3 仿真建模及分析

3.1 模型的建立

利用网络仿真软件对其进行建模, OPNET网络仿真软件是目前用于网络仿真开发和应用先进的平台之一, OPNET仿真模型划分为3层: 网络, 节点和进程层. 网络模型是最顶层模型, 由网络节点和通信链路组成, 可以反映网络拓扑结构的特点; 节点模型是由协议模型构造和连接起来, 可以反映设备的特性, 每1个模型对应1个或多个进程模型; 进程模型通过C语言编程的有限状态机来进行描述, 可以反映协议如何实现其具体功能. 建立1个无线子网模型, 包括1个AP和使用wlan_station_adv (Mobile Node)作为接入点的若干个无线移动站点[3].

(a) 为整个网络配置应用模块Application Config: 添加FTP、HTTP、Database. 为了提高仿真速度, Mix设置为50%, 业务流一半为精确发送, 一半为其他交易量. 业务交易间隔时间为exponential函数随机取样.

(b) Profile Config: 业务配置见图2, 描述1类用户群所涉及的应用. 业务开始时间(Start time)为100 s; 主询加载时间(duration)为仿真结束终止; 业务主询重复性(Repeatitions)为重复.

图2 业务主询问配置

(c) 配置服务器支持应用, 确定每台服务器具体支持的业务.

(d) 配置客户端业务主询, 因为是端对端的业务, 因此, 在客户端中同样需要设定业务主询, 其设置同业务主询配置一样.

3.2 节点模型

无线节点模型采用wlan_station_adv(mob)[4], 侧重分析无线网络的性能指标, 特别是MAC(Media Access Control)层协议, 其中source模块产生数据包. wlan_mac_intf模块为高层和MAC层的接口. wire_lan_mac模块完成各种MAC多址接入和传输, 实现无线介质访问控制协议的核心模块, 具体由进程模型来实现. sink模块处理接收的数据包, 释放内存. 同时进行平均时延和吞吐量方便的统计工作. wlan_port_tx0模块负责将数据帧发送到信道上. wlan_port_rx0模块用于检测信道状态, 获取数据帧传递给MAC模块来处理.

表1 仿真实验参数

3.3 仿真分析

利用建立好的模型, 对无线子网进行仿真分析. 设置移动节点的数目, 使用ON-OFF模式产生业务. 在不同的节点数目下分别采用BEB算法的基本DCF协议和改进的退避算法的基本DCF协议[5]. 分析和比较2者的吞吐量和传输时延性能. 仿真参数如表1所示, 程序中的cw等同于文中的.

4 改进的退避算法的关键代码

if( backoff_slots==BACKOFF_SLOTS_UNSET)

{ if(retry_count==0||wlan_flags->perform_cw==OPC_BOOLINT_ENABLED)

if(cw<=cw_mid)

{ max_backoff= max_backoff-1;

if(max_backoff

{ max_backoff= cw_min;

}

}

else

{ max_backoff= max_backoff/4;

}

}

}

else

{ max_backoff=2* max_backoff;

if(max_backoff>cw_max)

{

max_backoff= cw_max;

}

backoff_slots=floor(op_dist_uniform(max_backoff+1));

}

5 结果分析

根据对模型的数据测试应用, 得到结果, 图3和图4分别显示了在移动节点数分别为10、20、30、40、50、60、100的情况下, BEB算法和改进的算法在饱和数据量环境下的吞吐量和传输延时曲线, 对2种情况进行公平性比较, 见图5.

图3 吞吐量比较

图4 网络延时比较

图5 2种情况的公平性比较

从图3和图4可以看出, 改进的算法在吞吐量和网络延迟都要优于BEB算法. 当无线节点从10个增大到100个时, BEB算法中随着负载的增加吞吐量急剧下降, 吞吐量从4.2 Mb/s下降到2.5 Mb/s, 下降了40%; 改进后的退避算法从4.3 Mb/s下降到3.25 Mb/s, 性能下降了24.5%, 在一定程度上降低了冲突概率, 减少了数据的碰撞, 同时能有效地利用信道, 提高信道利用率. 从图5可以看出改进的算法其公平性也要优于BEB算法, 由于改进的算法其竞争窗口的变化依照不同的竞争阶段分别进行乘性和线性递减, 能以更加合理的概率接入信道, 提高了数据流之间的公平性. 因此改进后的算法比BEB算法具有更好的适应性.

6 结束语

文章通过引入二进制退避算法机制, 并对其进行改进, 应用到无线子网模型中, 显著减少了由多个节点同时发送数据帧造成的冲突, 具有重要的实际意义和参考价值.

[1] 陈伟, 张剑, 黄秋元. IEEE802.11标准MAC性能分析和一种改进方法[J]. 通信系统与网络技术, 2006, 4(3): 37—41.

[2] 王秀芳, 魏宇恒, 王洋. IEEE802.11 DCF退避机制的一种改进方法[J]. 长江大学学报: 自然科学版, 2008, 12(5): 67—70.

[3] 朱艳. 娄底职业技术学院无线校园网优化设计[D]. 武汉: 华中科技大学, 2010: 11.

[4] Papanikos I, Logothetis M. A study on dynamic load balance for IEEE 802.11b wireless LAN[A].Proc of COMCON[C].Los Angeles: CA:ETATS-UNIS, 2001: 83—89.

[5] 郭世泽. 无线局域网[M]. 北京: 人民邮电出版社, 2003: 65—68.

Improved algorithm based on DCF backoff mechanism and its application research

ZHANG Ying-zheng1, ZHU Yan2

(1. Department of Information Engineering, Hunan Engineering Polytechnic, Changsha 410004, China; 2. Computer College, Huazhong University of Science and Technology, Wuhan 430074, China)

Wireless local area network technology used in distributed control is the basic access method of DCF , but it need to solve the two problems: one is made of many nodes at the same time send data frames and appear the situation of the collision, Second is along with the increase of total volume or network emergencies, sharp increase of collision rate. Therefore, this article studies the backoff mechanism of improved algorithm, in order to reduce the conflict when the node access network, the method of improving the performance of the MAC protocol, and by establishing the simulation model of subnet and application, the results show that this method improve the network throughput, solve the network congestion problem, improve the efficiency of communication.

retreats algorithm; wireless network; simulation modeling

10.3969/j.issn.1672-6146.2013.01.012

TP 393.1

1672-6146(2013)01-0046-04

email: 406851863@qq.com.

2012-12-03

湖南工程职业技术学院( GCZY11KTZ12)

(责任编校:刘刚毅)