陶志勇，袁永财

1.辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105

2.辽宁工程技术大学 研究生学院，辽宁 葫芦岛 125105

1 引言

无线传感器网络（WSN）是一种特殊的无线多跳分布式网络，它不需要固定的网络支持，具有快速组网、抗毁灭性强等特点[1]。同时由于WSN自身特性，网络中节点资源的使用是受到限制的，尤其是电池的使用。因此，如何降低WSN网络中节点的能耗成为当前研究WSN的热点之一。

介质访问控制协议（MAC）决定了无线信道的使用方式，并在节点之间分配有限的无线通信资源[2]。MAC协议处于无线传感器网络协议的底层部分，直接影响着网络的吞吐量、能效、节点公平性等网络重要性能，特别是MAC协议中的退避算法直接影响节点间碰撞概率、节点公平性与能量效率等关键性能。

目前退避算法使用比较广泛的是由IEEE 802.11DCF[3]标准定义的二进制指数退避算法（BEB）[4]，但BEB算法并不完善，自提出以来，很多学者从不同的方面对其进行了改进。如文献[5-7]从退避协议的稳定性对BEB进行改进；文献[8]则关注网络中节点的公平性等。文献[9]通过引入竞争窗口复位值Lx来选择退避窗口大小，其核心思想是：若当前竞争窗口比Lx大则在发送成功时退避窗口变为Lx，再次发送成功竞争窗口才变为最小值，这样经过两步窗口复位缓解了竞争窗口震荡[9]的问题。但是文献[9]没有给出在网络流量快速增加时该如何调整竞争窗口的方法。文献[10]通过在发送数据前开启一个观测窗口来计算时隙利用率S_U，S_U随网络负载增大而增大。在数据发送成功后，竞争窗口根据时隙利用率和数据重传次数来改变，而不是盲目的将竞争窗口变为最小，从而维护了网络中节点接入信道的公平性，也提高了网络的吞吐量。但是文献[10]在数据发送失败时窗口的增大是通过乘以一个固定的系数来实现的，不能满足网络中流量动态变化的需求。本文在BEB的基础上，结合文献[9-10]两种改进算法提出了周期性采样的两步指数退避算法PTEB。

2 PTEB算法

根据IEEE 802.11DCF标准的规定，BEB算法具体描述为：若节点通信成功，将竞争窗口降为最小值。若节点通信失败，则将竞争窗口CW[11]值扩大到原来的2倍，一直到最大值。当此节点的CW值增大到CWmax时，再请求信道要求重传时CW的值应一直保持为CWmax，直到此节点发送成功或者达到了帧传输的最大重传次数后CW被置为CWmin为止。

IEEE 802.11DCF标准还规定了节点接入信道的方式，当节点有数据要发送时，首先需要侦听信道，如果侦听到信道连续空闲时隙超过DIFS，则节点就进入了退避状态，如果侦听信道连续空闲时隙没有超过DIFS则一直侦听直到超过DIFS为止。节点进入退避状态后，通过BEB算法计算CW值。计算CW的值是为了给节点选取退避时间。根据公式（1）计算具体的退避时间[12]：

BackoffTime=Random(0，CW)×aSlotTime（1）其中，aSlotTime是一个时隙长度，由物理层决定。例如DSSS（直接序列扩频）时隙固定为20 μs。Random(0，CW)是在[0，CW]范围内均匀分布的随机整数，CW是BEB算法中计算出的结果。初始值为CWmin，最大值为CWmax。退避时间值保存在退避计数器内，当退避计数器的值减为零时，节点才可以开始发送数据。若在退避过程中节点检测到信道变为忙，则结束退避过程，并重新开始侦听信道。

PTEB算法在标准BEB算法的基础上进行了改进，二者的不同之处主要有以下几点：

（1）引入采样周期概念。

（2）定义了两个网络参数，分别是信道竞争能力参数和网络拥挤参数，用来衡量当前采样周期内网络的状况。

（3）CW的改变不再是按照二进制指数的形式增长，而是按照上面定义的两个网络参数进行增大或减小。

（4）节点分两个阶段对CW进行调整：第一阶段为节点发送数据后；第二阶段为节点刚进入退避阶段时。

2.1 采样周期

为了了解当前网络工作的实时状况，把时间分割成连续的相同大小的时间段，这样的一个时间段称为采样周期。一个采样周期的长度至少能够满足节点完成一次数据传输所需的时间，即：

采样周期≥DIFS+CWmax+最大数据长度

同时采样周期也不可无限制的增大，因为在下文中可以知道，在采样周期内要对一些参数进行计数，在实际情况中，存储该数值的变量的范围是有限制的，所以采样周期的最大值不能超过该变量的范围。

采样周期的取值在其允许的范围内，值越大越好，因为频繁的对网络状况进行采样会增加数据的计算时间，从而导致网络延时的增加。

2.2 信道竞争能力参数

BEB算法中竞争窗口只是根据数据发送的成功还是失败来进行调整，本文出于对节点公平性的考虑，引入了节点信道竞争能力参数Qc如公式（2）所示；同时还引入了Qc的阈值：QCH、QCL，分别表示Qc的上限和下限。

当一个采样周期开始时，Ncs初值等于0，节点每成功竞争到信道一次，Ncs的值就加1，表示在此时刻之前，当前采样周期内节点成功竞争到信道的次数；Nsum初值等于0，节点每参与竞争信道一次，Nsum的值就加1，表示在此时刻之前，当前采样周期内节点参与竞争信道的总次数。

由于在一个采样周期的开始，Ncs、Nsum均为0，此时的Qc无法计算，所以规定在采样周期开始时Qc的初始值为0。但是这样会导致相邻的两个采样周期中Qc值的突变，因此对公式（2）作如下修正：

其中，α+β=1。Qc(T-1)是前一个采样周期结束时的Qc值，Qc(T)表示本次采样周期的Qc值，α、β分别是Qc(T-1)和Qc(T)所占的权重，α为Qc(T-1)与Qc(T)的相关系数的绝对值，由相关系数的定义可知α的取值在[0，1]之间。

2.3 网络拥挤参数

如果节点知道当前网络的繁忙程度，那么就可以使节点以此为依据对CW做出相应的调整，而不是根据发送的成功或失败来盲目的增大或减小CW。本文以Qb来表示网络的繁忙程度，同时引入阈值QBG来表示网络可以容忍拥挤的一个限度。

当一个采样周期开始时，Nsf初值等于0，节点每发送失败一次，Nsf的值就加1，表示在此时刻之前，当前采样周期内节点数据发送失败的次数；Nsum与公式（2）相同。

与Qc一样，Qb也需要进行修正：

其中α+β=1。下文中的Qc和Qb均为修正后的值，为了表达清晰，仍使用Qc和Qb来表示。

2.4 CW的计算

CW的初始值[13]设为CWmin，之后CW的值会根据PTEB算法进行调整。CW计算分为两个阶段：

第一个阶段是在节点发送数据后，

其中CWpre是前一次竞争窗口的值，[X]表示对X做取整运算。

第二阶段是在节点侦听到信道连续空闲时间超过DIFS时，节点根据当前的Qc、Qb计算CW。

3 PTEB算法分析

PTEB算法首先将时间划分为连续的采样周期，在每一个采样周期内，各个节点都有属于自己的网络参数Qc和Qb。

当节点在一个采样周期内有数据要发送时，与BEB算法一样，要先侦听信道的状态，直到进入退避状态。当节点进入到了退避状态后，节点根据公式（5）计算此时的CW，然后进行退避。退避结束后，节点发送数据，发送数据后按照公式（4）再次计算CW值，此时如果还有数据要发送，节点重新侦听信道，并重复以上的过程。

3.1 公平性分析

网络中节点的公平性指的就是节点接入信道的机会的均等性，而CW则关系到节点接入信道的能力，CW值越大接入信道的概率就越低，竞争能力就越差；相反，节点的竞争能力就越强。

节点的公平性影响着网络的吞吐率以及数据传输的实时性，因此维护WSN中节点的公平性也是一项重要的任务。

维护网络中节点的公平性问题其实就是平衡节点接入信道能力的问题。如果节点接入信道能力过强，可以通过增大CW来减小其竞争力；相反的，可以通过减小CW来增大节点接入信道的能力。

从公式（5）中可以看出，当节点接入信道能力小于规定的下限并且网络负荷较轻时，这说明Qc＜QCL是因为本节点的竞争信道能力较其他节点弱，所以用Qc乘以当前的CW来减小竞争窗口的值，从而使本节点竞争信道能力变强。

而当节点接入信道能力大于规定的上限时，无论当前网络负载是重还是轻，都应该增大CW。这是因为当网络负载较轻时，本节点拥有较大的Qc就说明其他节点的竞争信道能力比本节点小的多，所以用1+Qc乘以当前的CW来增大竞争窗口的值，从而使本节点竞争信道能力变弱；相反，当网络负载较重时，为了避免数据碰撞的加剧，也应该增大CW。

而在节点接入信道能力适中且网络负载较轻时，不对CW进行调整。

经过上面的分析可知，CW在经过公式（5）的调整后，在不加剧节点间数据碰撞的前提下，网络的公平性得到了改善。

3.2 窗口自适应性分析

网络中的流量是动态变化的，希望竞争窗口能够根据网络流量的变化而自动的调整，从而减小数据的碰撞，增大网络的吞吐率。

数据发送失败后，当Qb＜QBG时，说明网络负载较轻，如果CW变为原来的2倍，会使网络中空闲的时隙变多，降低了网络的吞吐量。而当网络负载很重时，即Qb＞QBG，窗口还是变为原来的2倍，这样窗口的变化速度又相对过慢，会使网络中数据碰撞次数慢慢增多。

公式（4）中，数据发送失败后CW变为原来倍。当Qb/QBG＜1时说明网络负载较轻，根据指数增长的规律，此时的值在（1，2）之间，且增长速度比较缓慢；当Qb/QBG＞1时说明网络负载较重，根据指数增长规律，此时的值在(2，+∝)之间，且增长速度比较迅速。这样改进后，在网络负载轻时节点接入信道的速度会变快，网络中空闲时隙会减少；在网络负载较重时数据碰撞次数会减少，由碰撞而引起的能量消耗也会减少。

4 仿真分析

本文使用Matlab进行仿真测试。物理信道使用的是文献[14]中多址接入信道模型，以CSMA/CA作为信道的接入方式。由于本文只是研究碰撞算法，并没有将完整的MAC层加以实现，只是对IEEE 802.11协议的MAC层进行裁减，使用了简化后的MAC层。每个节点数据包到达的时间服从参数λ为100 aSlotTime的泊松分布。

仿真环境参数设定如表1所示。

表1 仿真环境参数

4.1 仿真参数

通过以下3个性能指标来评估PTEB算法的性能。

（1）归一化吞吐率throughput

定义为整个网络单位时间内成功交互的数据比特数同物理信道数据速率的比值，即：

（2）网络中节点公平因数G

网络中节点的竞争窗口大小可以间接反映网络中的公平性，如公式（7）所示，用竞争窗口的标准差来表示公平因数G：

（3）平均碰撞次数Coll_Num_Avrg

其中Coll_Numi为节点i一个周期内的碰撞次数。

4.2 归一化吞吐率比较

本文对BEB、PTEB、MILD（乘性增加线性减小算法）3种退避机制在不同节点数目情况下的吞吐率进行对比，如图1所示。

图1 归一化吞吐率比较

从图1可以看出，当节点数量较少时，3种算法的吞吐率相差不大，MILD的吞吐率要略高于BEE，BEB的吞吐率略高于PTEB；而当节点数量超过某一值时，PTEB算法的吞吐率相对于BEB和MILD算法的吞吐率总是处于较高的水平上，随着节点数量的继续增多，网络中空闲时隙越来越少，数据碰撞会越来越严重，3种算法的吞吐率也会逐渐下降并逐渐接近。

4.3 节点公平因数的比较

不同算法下的公平因数随节点数量的变化曲线，如图2所示。

图2 网络公平因数比较

从图2可以看出当节点数量较小时，PTEB算法的公平性要低于其他两种算法；而当节点数量大于某一值时，PTEB算法的公平性要远远优于其他两种算法。

4.4 平均碰撞次数比较

不同算法下的数据平均碰撞次数随节点数量的变化曲线，如图3所示。

图3 平均碰撞次数比较

从图3可以看出，PTEB算法下的平均碰撞次数总是小于其他两种算法中的平均碰撞次数，随着节点数量的增多三者的平均碰撞次数也逐渐趋于相等。

5 结束语

本文通过理论分析和实验仿真，证明了PTEB算法能够根据网络流浪的动态变化来调整竞争窗口CW的大小，并且在节点数量不是很小的时候（大于20），其在减少数据碰撞，增加网络吞吐率，维持节点公平性等方面要优于BEB与MILD算法。

[1]古连华，程良伦.Au-MAC：一种自适应的无线传感器网络MAC协议[J].自动化学报，2010，36（1）：54-59.

[2]唐震洲，胡倩.基于数据重排序的无线传感器网络低延时节能MAC协议[J].传感技术学报，2010，23（7）：1037-1043.

[3]IEEE Std 802.11.Part 11 Wireless LAN Medium Access Control（MAC）and Physical Layer（PHY）specifications[S].New York：IEEE Press，2007.

[4]Pantazi A，Antonakopoulos T.E-quilibrium point analysis of the binary exponential backoff algorithm[J].Computer Communications，2001，24（18）：1759-1768.

[5]Zhang Y，Piunovskiy A，Ayesta U，et al.Converge-nce of trajectories and optimal buffer sizing for MIMD congestion control[J].Computer Communications，2010，33（2）：149-159.

[6]Wang C，Li B，Li L.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.

[7]姚为锡，蔡保国，缪学宁.竞争窗口线性变化的分级冲突解析算法[J].计算机工程与应用，2013，49（22）：72-76.

[8]唐勇，周满元.Ad hoc网络中MAC不公平性的研究与改进[J].计算机工程，2010，36（22）：100-102.

[9]彭静，朱艺华.IEEE802.11无线局域网二进制指数退避算法改进与分析[J].计算机工程与科学，2012，34（12）：39-44.

[10]张强，付敬奇.一种IEEE 802.11接入机制的新退避算法[J].传感技术学报，2008，21（12）：2073-2077.

[11]王二飞.无线传感器网络MAC层CSMA/CA机制的研究[D].北京：北京邮电大学，2012.

[12]陈忠真.IEEE802.11 DCF算法的研究[D].西安：西安电子科技大学，2012.

[13]王叶群，黄国策.一种时效性约束的二进制指数退避算法[J].计算机科学，2012，39（4）：56-59.

[14]刘学勇.详解MATLAB/SIMULINK通信系统建模与仿真[M].北京：电子工业出版社，2011.