一种改进退避算法及其在无线子网仿真中的应用研究

论文导读：进制指数退避算法。无线网络是计算机网络发展的一个重要部分。仿真建模及分析。仿真建模，一种改进退避算法及其在无线子网仿真中的应用研究。
关键词：退避算法，无线网络，仿真建模
 

1 引言

无线网络是计算机网络发展的一个重要部分，存在巨大的市场潜能，大多数单位都建立了自己的无线局域网，采用的是分布式控制DCF方法，但这种方法需要解决多个节点同时发送数据帧而出现的碰撞情况，文章引入二进制退避机制，并予以改进，改进后的算法经过应用，显著减少了数据帧发生碰撞的情况，具有重要的实际意义。博士论文，仿真建模。

2二进制指数退避算法

在IEEE802.11DCF中采用的标准退避算法是二进制指数退避(Binary Exponential Backoff，BEB)。博士论文，仿真建模。如公式1-1所示。

F1=Min（2CW，CWmax）（公式1-1）

F2=CWmin

BEB算法在某些方法解决了信道争用问题，但是也存在的两个缺点：

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

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

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

3改进的退避算法

从上面可以得出BEB算法适合于负载比较轻的环境，负载过重性能急剧下降。为了能让节点更快的达到公平的竞争状态，提高整个网络的性能。在此基础上，提出改进的退避算法，如图3-1所示：引入一个中间参数CWmid（ CWmin<CWmid<CWmax），作为区分节点竞争程度的阀值。同时结合其他退避算法的取值，考虑将初始竞争窗口设置为CWmin为2，CWmax为1024，CWmin为32。

1、初始时网络负载较轻，其竞争窗口CW<=CWmid时，若发生冲突数据包发送失败，则竞争窗口和BEB一样增长为原来的2倍CW=2CW；若数据包发送成功，竞争窗口CW线性减少，在原窗口基础上减1，避免竞争窗口下降过快引起更多的冲突。

（2）当网络负载较多，其竞争窗口CW>CWmid时，若数据包发送失败，则竞争窗口CW值和BEB一样增长为原来的2倍；当数据包发送成功后，竞争窗口CW值不直接降到最小CWmin，而是在原窗口基础上除以4，让竞争窗口快速降到CWmid附近，防止过度空闲而使得信道利用率下降。博士论文，仿真建模。

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

改进的退避算法如公式3-2所示：

（CW>CWmid）

F1=Min（2CW， CWmax） （公式3-2）

F2=CW/4

（CW<=CWmid）

F1=Min（2CW， CWmax）

F2=CW-1

4OPNET仿真建模及分析

4.1模型的建立

利用网络仿真软件对其进行建模。OPNET网络仿真软件是目前用于网络仿真开发和应用先进的平台之一， OPNET仿真模型划分为三层：网络，节点和进程层。网络模型是最顶层模型，由网络节点和通信链路组成，可以反映网络拓扑结构的特点；节点模型是由协议模型构造和连接起来，可以反映设备的特性，每一个模型对应一个或多个进程模型；进程模型通过C语言编程的有限状态机来进行描述，可以反映协议如何实现其具体功能。

建立一个无线子网模型，包括一个AP和使用wlan_station_adv （Mobile Node）作为接入点的若干个无线移动站点。

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

（2）Profile Config：业务配置如图4-1所示，描述一类用户群所涉及的应用。业务开始时间（Start time）为100s；主询加载时间（duration）为仿真结束终止；业务主询重复性（Repeatitions）为重复。

图4-1 业务主询问配置

（3）配置服务器支持应用，确定每台服务器具体支持的业务。

（4）配置客户端业务主询，因为是端对端的业务，因此，在客户端中同样需要设定业务主询。博士论文，仿真建模。设置同业务主询配置一样。

4.2 节点模型

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

4.3仿真分析

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

表4-1 仿真实验参数

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

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<cw_min）

{ 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));

/*生成随机退避*/

}

6结束语

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

参考文献
[1]陈伟，张剑，黄秋元.IEEE802.11标准MAC性能分析和一种改进方法.通信系统与网络技术.2006（2）
[2]王秀芳，魏宇恒，王洋.IEEE802．11 DCF退避机制的一种改进方法.长江大学学报（自然科学版）.2008，12（5）
[3]Papanikos I，Logothetis M.A study on dynamic loadbalance for IEEE 802.11b wireless LAN//Proc of Comcon.Los Angeles，CA.2000
[4]牛伟，郭世泽.无线局域网.人民邮电出版社.2003