中高速无线传感器网络[1]用于包括环境检测、视频多媒体等多种混合类型业务，网络负载通常很大，区域节点密度差异大，区域负载波动大。传统无线传感器网络的MAC协议竞争窗口滑动缓慢，对于负载波动大的业务会造成过渡时间长以及资源浪费等，不能满足数据复杂的中高速无线传感器网络[2]。目前出现了针对无线传感器网络MAC协议的多种有效的退避算法,典型退避算法有： (1)二进制指数退避算法BEB(Binary Exponential Backoff)[3] ,其特点是发生冲突时竞争窗口按二进制指数增长，发送成功时则降至最小值。其缺点是总是有利于最近发送成功的节点而公平性差， 且随着节点数增加而碰撞概率急剧增大， 造成网络性能迅速下降。(2)倍数增加线性递减退避算法MILD(Multiplicative Increase Linear Decrease)[4]，当网络节点数较多时，MILD由于竞争窗口变化较平滑，其吞吐率性能略优于BEB。但当网络有中等数目的节点时，则由于竞争窗口线性递减而显得缩小相对较慢，使节点竞争窗口值往往大于合理值。(3)CIMLD(Conic Increase Multiplicative Linear Decrease)算法[5]采用分段二次曲线计算倍乘退避因子来调节退避窗口，能够在不同区域中以不同速率解决信道冲突，但流封锁信道问题还没有完全解决。(4)PTTL(Preferentially Transmitting and Different Traffic Levels)退避算法[6]根据网络流量判定的级别来改变退避窗口大小，赋予转发节点一定的信道接入优势来提高前传效率而减少时延，但对网络流量变化适应性较弱。

    这些退避算法各具优势，但在负载波动变化急剧、数据复杂的中高速无线传感器网络环境中，网络性能则大幅下降。因此，本文在深入研究PTTL退避算法的基础上，提出一种密度预测与服务分级的MAC退避算法DPSC(Density Prediction and Service Classification)，以达到提高网络信道利用率与网络吞吐量的目的。
1 PTTL退避算法介绍与分析
    PTTL退避算法主要思想是：流量分级与转发优先。即节点通过侦听信道状态来判断当前网络流量级别，并对转发节点赋予较小竞争窗口而增大其信道接入概率。PTTL退避算法描述如下：
    (1)空闲状态，CW=max(CWmin,CW-i3)，其中i是连续侦听到空闲时隙数，CWmin是窗口最小值。
    (2)发送成功，CW=max(CWmin,CW-s2)，其中s是连续成功竞争信道并发送报文成功次数。
    (3)发送失败，竞争窗口CW为：
    CW=min(CWmax,CW*(C+1)),C≤CmaxCW=CWinit, C>Cmax　　
其中C是连续竞争信道失败次数，Cmax是最大退避次数，CWmax是窗口最大值。
    (4)节点是转发节点，则CW=CWmin。
    总的来说，PTTL退避算法简便易行，在网络负载较重的网络环境中性能良好。但PTTL退避算法并没有服务分级，即不同业务类型数据以相同的机会接入信道，造成关键数据延迟，不能反映实际需求。且节点是转发节点，则CW将无条件降低到CWmin，虽然这样能够在一定程度上提高转发能力并保证数据转发优先，但是当网络负载严重时，不区分服务类型的无条件降至最小值CWmin，会造成碰撞概率急剧增加，反而与尽快将数据发送出去的初衷相反。因此关键类型数据应该具有接入信道优先权，提高优先级数据的传输率，减少关键类型数据时延来满足应用实时性需求。
2 DPSC退避算法设计
    为了提高网络负载重且负载波动急剧的中高速无线传感器网络性能，基于PTTL退避算法提出密度预测与服务分级MAC退避算法DPSC。主要创新点如下：
    (1)网络节点数目进行加权递推平滑预测。节点密度与邻近节点数目是一一映射关系，即某节点的邻近节点越多，此节点区域的节点密度越大。假设网络自适应占空比p∈[0,1],即节点每周期处于活动状态概率为p。在每个估算周期i∈[1,n],利用竞争窗口来实现计算邻近节点，且计算节点数是指除开周期1~i-1中已计算的所有醒来邻近节点。在估算周期i中，询问节点发送询问包REQ。接收到询问包REQ且未有回答的醒来节点时,在M个时隙中随机选择一个时隙回复一个装载唯一身份ID的回复包ANS。询问节点在第i窗口成功收集分组Gi数目并记录ID。由伯利努试验二项分布可知占空比为p、实际邻近节点数目为N且发生k次的概率为:

  
3.1节点密度预测分析
    邻近节点数目的最大似然估算值N*与节点占空比p有关，占空比p的大小决定N*的估算精确度。当前网络邻居节点数Nc与平滑因子l、权重系数Cj相关，此处取l=5，C1=0.2，C2=0.4，C3=0.6，C4=0.8，C=1.0。其中相对误差e=|Nc-N|/N，Nc是当前邻近节点数目加权递推平滑预测值，N是当前邻近节点数目真实值。
    从图2可知，邻近节点数目越多，占空比p越大，则当前邻近节点数目加权递推平滑预测值与真实值相对误差e越小，即平滑预测值越接近真实值，估算精确度越高。同理，对于节点密度大的区域节点可以设置较低的占空比p进行估算而得到可靠的邻近节点数目估算值，且减少估算周期侦听所消耗的能量。

3.2 系统时延分析
    从图3可知，节点数目较少时各算法端到端时延基本相同，但节点数目较多时的时延相差甚远。DPSC算法时延增加速率最小，因为能够根据邻近节目数目动态地修改竞争窗口，减少碰撞概率与重发次数，从而减少端到端时延，能够适应不同节点数目的网络环境。
3.3 系统吞吐量分析
    从图4可知，随着节点密度增大吞吐量都有所下降，在节点数目小于10时吞吐量大致相同，之后出现大幅度差距。因为随着节点数目的增加,节点冲突概率将会增大，所以各种算法吞吐量都有所下降。其中DPSC算法下降速度最慢是由于邻近节点数目能自适应竞争窗口，从而有效地提高信道利用率，相对PTTL算法平均提高15%。其余三种算法都不太适应于高节点密度的网络环境，特别是BEB算法吞吐量下降最快。

3.4系统能耗分析
    从图5可知，各退避算法成功发送每比特数据的平均能耗随着系统网络节点数目的增加而增加。在邻近节点少的网络系统中，其他三种算法能耗低于DPSC算法，因为密度低而竞争信道的冲突少，数据发送成功率高，而DPSC算法却因节点估算预测的周期侦听耗能略高。但高密度时DPSC算法因为根据节点数目动态地改变竞争窗口而降低冲突概率，减少重传次数，所以平均能耗明显低于其他三种算法，相对于PTTL算法平均下降5%。

    本文退避算法DPSC通过二项分布概率模式对邻近节点数目进行最大似然估算并进行加权递推平滑预测，精准地估算出邻近节点数目，实现竞争窗口自适应节点密度的目的；根据服务分级思想，引入服务分级因子δ实现服务级别高的数据能优先发送；引入负载分级因子κ表示负载级别并赋予数据积压的节点优先发送权；引入多跳传发优先因子μ实现数据前传的连续性与减少时延，满足关键数据多跳传输实时性要求。DPSC退避算法与其他三种算法在节点低密度与低负载情况下网络性能差别不大，但在节点高密度与高负载情况下则表现出优越的网络性能。进一步的工作将采用无线传感器硬件平台CC2430对DPSC退避算法进行实际性能测试。
参考文献
[1] 王越超，程良伦.中高速传感器网络中基于服务区分的QoS路由算法研究[J].计算机应用与软件,2010(8):152-158.
[2] CHIA W C, CHEW L W, ANG L M, et al. Low memory image stitching and compression for WMSN using stripbased processing[J]. International journal of sensor network, 2012,11(1):22-32.
[3] PANTAZI A,ANTONAKOPOULOS T. Equilibrium point analysis of the binary exponential backoff algorithm[J].Computer Communications, 2001,24(18):1759-1768.
[4] Zhang Yi, PIUNOVSKIY A, AYESTA U,et al. Convergence of trajectories and optimal buffer sizing for MIMD congestion control[J]. Computer Communications, 2010,33(2):149-159.
[5] 奎晓燕，杜华坤. CIMLD:多跳Ad Hoc网络中一种自适应的MAC退避算法[J]. 小型微型计算机系统, 2009，30(4):679-682.
[6] 余庆春，谭狮. 一种基于转发优先及流量分级的无线传感器网络退避算法[J]. 计算机应用研究，2012,29(5):1846-1849.
[7] CAMILLO A,NATI M, PETRIOLI C,et al. IRIS:Integrated data gathering and interest dissemination system for wireless sensor networks [J]. Ad Hoc Networks, 2011, 11(2):654-671.