过滤发送阈值退避算法*

张长森, 陈鹏鹏, 胡宇鹏, 刘晓惠, 刘雪贞

(河南理工大学 计算机科学与技术学院,河南 焦作 454000)

过滤发送阈值退避算法*

张长森, 陈鹏鹏, 胡宇鹏, 刘晓惠, 刘雪贞

(河南理工大学 计算机科学与技术学院,河南 焦作 454000)

针对二进制回退机制存在的问题进行了分析，并提出了一种改进的回退算法。该算法通过引入过滤发送阈值的概念，动态地调整无线节点的等待时间，以实现网络吞吐量的最大化。在IEEE 802.11 DCF协议中以相同的物理层参数进行仿真。实验结果表明:与BEB算法、SD-DCF算法和MMS算法相比，改进算法在两种发送方式尤其是基本方式下，饱和吞吐量和分组平均接入时延均可获得不同程度的改善。

无线网络； MAC机制； IEEE 802.11 DCF; 退避算法

0 引 言

退避机制是无线网络MAC层协议中解决站点竞争信道资源发生碰撞的方法，目的是在多个站点争用同一信道时，保证接入的有效性，使得系统资源得到合理利用。包括IEEE802.11[1]和802.15.4标准在内的许多无线网络协议都采用二进制指数退避(binary exponential backoff,BEB)机制管理数据的重发。BEB算法为节点提供一种基于竞争窗口(contention window,CW)解决碰撞问题的方法。站点发送数据发生碰撞，CW的大小调整为原来的2倍；数据交互成功，CW置为最小。BEB算法因其原理简单且执行效率高等特点而备受研究者的青睐，多种针对BEB的扩展方法被提了出来[2～5]。Ni Qiang等人[6]提出了SD-DCF(slow CW decrease DCF)算法。SD-DCF在数据发送成功时，把CW的大小置为当前的1/2。Wang Chonggang等人[7]在文献[6]的基础上提出了GDCF(gentle DCF)。GDCF设定了连续传输成功次数计数器，计数器达到阈值时，CW大小减1/2。文献[8]提出的MMS(multi-channel MAC schemes based on 802.11)通过碰撞概率 管理退避计数器的递减频率，以达到动态调整无线站点等待时间的目的。

MMS保留了BEB的CW调整策略，实现简单，改善了信道带宽利用率，提高了网络吞吐量。但由于碰撞概率这一单一信息不能完全真实地反映当前网络状态，MMS算法并没有实现吞吐量最大化。本文在深入研究文献[8]的基础上，提出TFTB (transmission-filtered threshold back-off)算法。算法设置了一个和网络中竞争站点数量密切相关的阈值以控制节点竞争信道的激烈程度，并通过二维离散时间马尔科夫链建模分析了其理论最优值的设置。仿真实验表明，TFTB算法有效地改善了网络吞吐量和平均接入时延。

1 TFTB算法

1.1 算法描述

在动态分布式的网络环境中，动态竞争站点数量反映了网络当前的竞争状态，站点的竞争接入碰撞概率随着网络中竞争站点数量的增多而增大，当碰撞概率很大时,盲目地发送数据包会导致网络状况恶化。以符号r表示过滤发送阈值，并将探讨如何根据竞争节点数量选取r，才能实现网络吞吐量的最大化。TFTB算法描述如下：

if (reach the slot of transmission) ∥到达发送时隙

then {calculate r based on the information of competition stations } ∥根据竞争站点数确定r。

if (D≤r) ∥按照均匀分布在[0,1]中随机取一个值D和r进行比较

then {send frames or RTS packet } ∥发送数据帧

else {back off in current back-off stage} ∥D>r,不进行数据发送，在当前退避阶段重新退避

if (the node fails to access the channel)

then {CWnew=min(CWmax,CWold×2} ∥将CW更新为原来的2倍，直到达到最大。

else {CWnew=CWmin} ∥将CW设置为最小值。

在上述对TFTB算法的描述中容易发现，和BEB算法、S-DCF算法以及MMS算法不同的是TFTB算法在节点完成退避过程后并不直接发送数据,而是根据过滤发送阈值来确定是否发送数据。由均匀分布的性质可得，站点完成退避后，有r的概率进行数据发送，有1-r的概率不发送数据，在当前退避阶段重新退避。

1.2r的理论最优值

假定1 在网络中有n个站点竞争一个无线信道，信道条件是理想的，系统工作在饱和状态，即每个站的发送队列总是非空的。

假定2 某一个站点在某个时隙发送的数据帧发生冲突的概率pc为的常量，和数据帧经历过多少次冲突无关[9]。

由于TFTB算法保留了BEB的CW调整策略，以Wi表示节点各个退避阶段CW的大小，则Wi满足

(1)

式中 W=W0=CWmin表示CW的最小值，2mW=CWmax表示CW的最大值，i为退避阶段即数据帧经历的重传次数。 m为最大退避阶段。 其他参数定义如下：k为退避计数器的值;马尔科夫链的二维状态空间为：{(0,0),(0,1),(1,0)，…，(i,k)},i∈[0,m],k∈[0,Wi-1];P{i,k|i-1,k-1}表示从状态(i-1,k-1)转移到状态(i,k)的转移概率；bi,k表示站点处于退避阶段为i,退避计数器的值为k这一状态的稳态概率。τ表示某个随机选定的时隙，每个站点发送数据帧的概率。记q=r(1-pc)，可以得到TFTB算法的二维离散时间马尔科夫链模型，如图1所示。

图1 TFTB的马尔科夫链模型Fig 1 Markov link model for TFTB

由马尔科夫链模型可得到如下稳态方程

(2)

经过化简式(3)可以表示为

(3)

由于遍历状态空间中所有状态的稳态概率分布之和为1，得到

=1

(4)

联立式(2)、式(3)中后两个式子和式(4)可得

(5)

式中 pc=1-(1-τ)n-1。

由于r的过滤作用，结合式(3)中第一个式子可以将某个时隙站点的发送概率τ表示为

(6)

由文献[9]可得使S最大化τ的最优解

(7)

表1(a) r的最优值(10～50) Tab 1(a) Optimal value of r (10-50)

表1(b) r的最优值(60～100)Tab 1(b) Optimal value of r(60-100)

2 仿真结果与分析

为了评估TFTB算法的性能和理论分析的正确性，利用Matlab R2009a进行仿真实验。设置发送节点数量以10为步长从10变化到100，仿真时间为300 s。这10个网络场景中，网络中所有站点向同一个目的节点发送有效负载为1 000 B的数据流。其它仿真参数参照文献[1]中基于DSSS PHY的DCF协议，如表2所示。相同条件下，仿真还分析了BEB算法、SD-DCF算法和MMS算法。

表2 主要仿真参数Tab 2 Main simulation parameters

图2和图3描绘了网络饱和吞吐量随着竞争站点数的变化曲线。从图中可以看到：1)两种方式下，饱和吞吐量随竞争站点的增多呈现下降趋势，BEB算法的网络饱和吞吐量随竞争站点数的增加下降的最为明显，TFTB算法的饱和吞吐量随竞争站点数的增加，基本保持平稳，下降幅度很小。2)RTS/CTS方式下，竞争站点数为10时，TFTB算法的饱和吞吐量和其他三种算法比较并无明显优势。这是因为RTS/CTS模式下站点很少时，网络的拥塞程度很小，其他算法也能较好地适应网络状况。随着竞争节点增多，TFTB算法跟踪网络规模的变化把 设置为理论最优值，其饱和吞吐量逐渐高于其他三种算法。3)在基本方式下，TFTB算法的饱和吞吐量始终高于其他三种算法，随着竞争站点数量的增加，这种趋势越来越明显。竞争站点数目为100时，TFTB算法的网络饱和吞吐量比BEB算法提高约67.24 %，比SD-DCF算法提高约43.44 %，比MMS算法提高了约26.67 %。

分组的平均接入时延为数据帧进入MAC层缓存到完成发送所需时间。图4和图5分别给出两种发送方式下平均接入时延随着竞争站点数的变化曲线。从图中可以看出：1)两种方式下，随着竞争站点数量的增大不同算法的平均接入时延曲线均呈现上升趋势。对于不同竞争站点数目，TFTB算法的平均接入时延始终低于其他三种算法，随着站点数量的增加，它们之间的差距有扩大的趋势。2)在基本发送方式下，当竞争站点数量为100时，TFTB算法的接入时延不到BEB算法的1/2，这表明TFTB算法可以有效地提高站点接入信道的效率。

3 结束语

针对BEB机制存在的缺陷，本文提出了FTTB算法，根据网络规模设置相应的过滤发送阈值，动态地调整无线节点的等待时间。实验结果表明：FTTB算法的饱和吞吐量和平均接入时延与BEB算法相比均有明显的改善。其中基本发送方式下竞争站点数为10时，算法的饱和吞吐量比BEB算法提高了约67.24 % ，平均接入时延不到BEB算法的1/2。和其他BEB的增强算法相比FTTB算法的网络性能也有不同程度地改善。

图2 基本发送方式网络归一化饱和吞吐量Fig 2 Normalized system throughput of basic access scheme

图3 RTS/CTS方式网络归一化饱和吞吐量Fig 3 Normalized system throughput of RTS/CTS access scheme

图4 基本发送方式平均接入时延Fig 4 Average packet delay of basic access scheme

图5 RTS/CTS方式平均接入时延Fig 5 Average packet delay of RTS/CTS access scheme

[1] IEEE 802.11.Part 11:Wireless LAN medium access control(MAC) and physical Layer (PHY) specifications[S].2007,IEEE Std:New York.

[2] Sun Xianghua,Dai Lin.Backoff design for IEEE 802.11 DCF networks:Fundamental tradeoff and design criterion[J].IEEE/ACM Transactions on Networking,2015,23(1):300-316.

[3] 李运鹏,徐昌彪,刘 琳.无线传感器网络中一种竞争窗口自

适应MAC协议[J].传感器与微系统,2010,29(1):49-54.

[4] 刘云璐,蒲菊华,方维维,等.一种无线传感器网络MAC协议优化算法[J].计算机学报,2012,35(3):529-539.

[5] Liu Jainshing.Design and performance evaluation of a distributed transmission control protocol for wireless local area network[J].IEICE Trans on Communications,2006,89(6):1837-1845.

[6] Ni Qiang,Aad I,Turletti T,et al.Modeling and analysis of slow CW decrease IEEE 802.11 WLAN[C]∥14th PIMRC,Beijing:IEEE,2003:1717-1721.

[7] Wang Chonggang,Li Bo,Li Lemin.A new collision resolution mechanism to enhance the performance of IEEE 802.11 DCF[J].IEEE Transactions on Vehicular Technology,2004,53(4):1235-1246.

[8] 毛建兵,毛玉明,冷甦鹏,等.基于802.11的多信道MAC协议性能分析[J].计算机研究与发展,2009,46(10):1651-1659.

[9] Bianchi G.Performance analysis of the IEEE 802.11 distributed coordination function[J].IEEE Journal on Selected Areas in Communications,2000,18(3):535-547.

Back-off algorithm based on transmission-filtered threshold*

ZHANG Chang-sen, CHEN Peng-peng, HU Yu-peng, LIU Xiao-hui, LIU Xue-zhen

(College of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454000,China)

Analyze on existing problems of the binary back-off mechanism,and propose an improved back-off algorithm.By introducing the concept of the transmission-filtered threshold,the algorithm dynamically adjusts waiting time of wireless nodes，in order to achieve the maximum network throughput.In the IEEE 802.11 DCF protocol,the simulation experiments are carried out with the same physical layer parameters.Experimental results show that normalized network throughput and average packet access delay of improved algorithm can all be improved with varying degrees under two access modes and especially basic access mode,by contrast with BEB algorithm,SD-DCF algorithm and MMS algorithm.

wireless networks; MAC scheme; IEEE 802.11 DCF; back-off algorithm

10.13873/J.1000—9787(2016)07—0143—04

2015—10—19

国家自然科学基金资助项目(51174263)； 教育部博士点基金资助项目(20124116120004)；河南省基础与前沿技术研究项目(142300410144)

TP 393

A

1000—9787(2016)07—0143—04

张长森(1969-)，男，河南洛阳人，教授，博导，主研方向为无线传感器网络。