一种基于自适应竞争窗口的无线传感器网络拥塞缓解策略

方晨 刘昊 时龙兴

(东南大学国家专用集成电路系统工程技术研究中心，南京 210096)

无线传感器网络在商业和军事上具有广泛的应用，如环境监测、工业传感、战场情报等［1-2］.该网络通常由树形汇聚的数据流组成，而并非独立的点对点数据传输.随着周期性、离散、突发的事件发生，无线传感器网络表现出独特的汇聚特性，即数据包产生并迅速向一个或多个汇聚节点移动［3］.

在传统的Ad hoc无线网络中，节点需要保持工作状态以侦听可能到达的数据包，其中空闲侦听浪费了大量的能量.而在无线传感器网络中，路由及媒体访问控制层(media access control，MAC)的能效是无线传感器网络通信协议一个基本的设计要点［4-5］.近年来的研究发现，在无线传感器网络协议设计中，首选的节能方法是使节点周期性睡眠以节省能耗［6-11］.

数据包汇聚特性和周期性睡眠带来了很多负面效应.例如，在汇聚的网络中，数据包经过多跳接力向汇聚节点集中，导致离汇聚节点越近数据密度越大；在周期睡眠的MAC协议中，数据包经过多跳传输，大幅增加了数据包传递延迟；传感器节点同步唤醒，增加了碰撞的概率.当网络载荷增加时，这些负面效应加剧了网络拥塞，导致网络中数据包延迟及丢失.尽管传感器节点可以采用上层拥塞缓解协议进行拥塞控制［12-14］，但是离开MAC层的帮助，它们不能对网络拥塞进行快速反应，以避免由于缓存溢出导致数据包的丢失.

针对上述问题，本文提出了一种适用于大多数传感器网络MAC协议的拥塞减轻策略，即自适应竞争窗口策略(adaptivecontentionwindow，ACW).该策略包括拥塞探测和拥塞减轻2个部分，原理是使缓存较多数据包的节点获得较高的成功竞争信道的概率，进行数据包的发送，以缓解网络拥塞引起的数据包丢失问题.

1 ACW策略设计

1.1 拥塞

在一个典型的传感器网络中，传感器节点探测到事件发生，产生数据包；随后，数据包被节点以接力方式向汇聚节点传输(见图1).图中，节点0，1，2为子节点，节点3为父节点，节点4为爷节点.假设对于节点i，数据包的到达率和发送率分别为λi和 μi，则在时间 t内，在子节点(i=0，1，2)聚集的数据包数目为(λi－μi)t，而父节点在t时间内聚集的数据包数目为 (+λ3)t.可以预见，子节点数目增加时，父节点会聚集更多的数据包.同时，子节点和父节点均需竞争媒体访问信道.图1中，子节点和父节点共享通信信道，且其信道竞争能力相同.随着子节点数目的增加，父节点成功竞争信道的概率下降，不能有效地将子节点传输来的数据包传递至爷节点，父节点缓存越来越多的数据包，直至其缓存溢出，网络发生严重拥塞，整个网络性能下降.因此，若父节点能够探测拥塞并提升自身竞争信道能力，尽快将数据包传递至爷节点，则可以达到缓解拥塞的目的.

1.2 拥塞探测

目前，拥塞探测方法主要有2种:① 基于队列长度的拥塞探测方法；② 基于信道采样的拥塞探测方法.前者的性能弱于后者［12］.在基于队列长度的拥塞探测方法中，节点监测发送队列的缓存空置比率，当缓存空置比率低于某个阈值时，节点判断网络发生了拥塞.在基于信道采样的拥塞探测方法中，有数据包需要发送前，需要对传感器节点进行信道采样，再根据信道繁忙状态，计算利用率因子，如果其高于某阈值，则节点判断网络发生了拥塞；然而，信道采样属于空闲侦听，会浪费能量［13］.无线传感器网络需要节省能量，以使节点工作时间更长，故在ACW策略中，采用第1种方法进行拥塞探测.

1.3 拥塞缓解

节点探测到拥塞后，开始调用自适应竞争窗口算法，使缓存较多数据包的节点获得较高的进行数据包发送的概率.自适应竞争窗口算法将当前周期节点的随机竞争窗口尺寸Wran∈(1，Wm)与其缓存队列长度l∈(1，lm)进行反比例映射，其中Wm表示当前周期中可选取竞争窗口尺寸的最大值，lm表示节点最大队列长度，由节点缓存空间决定.

该竞争窗口自适应过程是一个闭环反馈控制过程，流程图见图2.节点监测发送队列的长度，发现缓存空置比率上升时，预测本节点会聚集更多的数据包，故缩小竞争窗口尺寸，提高成功竞争信道、进行数据包发送的概率；反之，则增大竞争窗口的尺寸.

图2 自适应竞争窗口调整

当前周期节点随机选择的竞争窗口尺寸Wc为

式中，α=l/lm表示缓存的占用比率.

此外，当网络严重拥塞时，相邻节点缓存队列长度均较长，各节点经过映射计算得出的Wran较小，导致随机选择竞争窗口的范围缩小，相邻节点竞争信道时碰撞概率上升.因此，设Wlit为随机选择竞争窗口范围的下限，若经过映射计算得出的Wran小于 Wlit，则 Wran=Wlit，以减小竞争窗口选择范围缩小后引起的碰撞概率.

实际应用中，不同节点的缓存大小及竞争窗口的初始值不尽相同，但ACW策略采用的反比例映射算法可使其具有较广泛的适用性.

前人关于 IEEE 802.11可变竞争窗口的研究［4-5］并不适用于低占空比工作周期的无线传感器网络［15］.因此，本文从无线传感器网络自身的特性及存在的问题出发，展开研究.

2 仿真环境

将ACW策略在仿真软件NS-2 V2.29中实现，并采用NOAH路由协议.仿真中，每个节点都加载载荷，载荷为固定比特率数据流，所有数据包大小为50 B.假设中继节点不改变数据包的长度，且节点对数据的处理可以在射频收发转换时间内完成，故数据处理不会引入新的延迟.不同类型数据包的传输延迟见表1.

表1 传输延时表

簇状树形网络拓扑简单实用，在众多无线传感器网络应用中被大量采用［16-17］.因此，本文采用一个8节点的树形网络进行仿真评估，其网络拓扑图见图3.为了证明ACW策略的有效性，在SMAC协议［6］上加载ACW策略，并与原协议进行性能对比.节点参数设置见表2.

图3 树形拓扑

表2 节点参数设置表

3 结果分析

3.1 ACW策略效果

采用SMAC协议时，节点1～节点7的缓存队列长度与仿真时间的变化关系见图4.由图可知，离汇聚节点较近的节点1～节点3的队列在仿真过程中长期处于饱和状态，其余各节点的缓存队列在仿真开始后迅速进入饱和状态，且队列被逐渐排空.该仿真过程持续1200 s.仿真中，外围节点将数据包推送至离汇聚节点较近的节点，而离汇聚节点较近的节点来不及排空缓存的数据包，发生缓存溢出，导致节点1～节点3处大量数据包被丢弃.

图4 SMAC各节点队列长度变化曲线

采用ACW策略后，节点1～节点7的缓存队列长度与仿真时间的变化关系见图5.由图可知，离汇聚节点较近的节点1～节点3的队列于仿真开始时便迅速进入饱和状态，随后各节点的缓存队列被逐渐排空，仿真持续1800 s.其原因在于，当网络发生拥塞时，ACW策略提高了节点1～节点3成功竞争信道的概率，同时，迫使外围缓存数据包较少节点的竞争信道成功率大幅降低，延缓了外围节点向节点1～节点3推送数据包的速度，缩短了缓存队列的长度，外围节点逐渐恢复竞争信道能力，从而继续进行数据包的传递.ACW策略极大地避免了由于拥塞导致的数据包丢失.

图5 ACW各节点队列长度变化曲线

由此可知，ACW策略的效果主要体现在2个方面:①帮助缓存队列较长的节点提高竞争信道能力，获得较高的数据包发送概率，以减轻拥塞，减少数据包的丢失；②在缓存队列较短的节点处，缓存数据包.当拥塞发生时，网络中的数据包在网络的外围节点进行缓存，避免了数据包的迅速汇聚.

3.2 数据包传递率及能耗评估

数据包传递率是指成功到达汇聚节点的数据包数目与产生于所有源节点的数据包总数目的比值.源节点数据包的产生间隔时间与数据包传递率之间的关系见图6.由图可知，随着源节点向网络中注入数据包的频率增加，ACW策略大幅提高了SMAC协议的数据包传递率.当数据包的产生间隔时间小于10 s时，ACW策略使数据包传递率提高了25%～30%.

图6 数据包传递率与源节点数据包产生时间间隔的关系

平均能耗是指仿真过程中各节点耗能的平均值.由图7可知，由于SMAC协议采用周期性睡眠策略，其平均能耗较低.ACW策略大幅提高数据包传递率的同时，相对于SMAC协议，其能耗略微增加.增加的能耗源于对更多数据包的传输.

图7 平均能耗与源节点数据包产生时间间隔的关系

4 结论

1)设计了一种自适应竞争窗口调整算法.将缓存较多数据包的节点赋予较高的成功竞争信道概率，从而提高了数据包的传递率.当拥塞发生时，数据包在网络外围被节点缓存，避免了数据包的迅速汇聚.本质上，通过平衡网络中载荷分布，大幅减少了网络中数据包的丢失.

2)在仿真软件NS-2 V2.29中进行了ACW 策略设计及仿真.结果表明，该策略提高了数据包的传递率，缓解了无线传感器网络拥塞所带来的副作用.

References)

［1］Yick J，Mukherjee B，Ghosal D.Wireless sensor network survey［J］.Computer Networks，2008，52(12):2292-2330.

［2］Potdar V，Sharif A，Chang E.Wireless sensor networks:a survey［C］//Proceedings of 2009 Advanced Information Networking and Applications Workshops.Bradford，England，2009:636-641.

［3］Wan C Y，Eisenman S B，Campbell A T，et al.Overload traffic management for sensor networks［J］.ACM Transactions on Sensor Networks，2007，3(4):18-22.

［4］Pries R，Menth S，Staehle D，et al.Dynamic contention window adaptation(DCWA)in IEEE 802.11e wireless local area networks［C］//Proceedings of 2008 International Conference on Communications and Electronics.Hoi An，Vietnam，2008:92-97.

［5］Lv J，Zhang X M，Han X J，et al.A novel adaptively dynamic tuning of the contention window(CW)for distributed coordination function in IEEE 802.11 ad hoc networks［C］//Proceedings of 2007 International Conference on Convergence Information Technology.Gyeongju，Korea，2007:290-294.

［6］Ye W，Heidemann J，Estrin D.An energy-efficient MAC protocol for wireless sensor networks［C］//Proceedings of 2002 IEEE INFOCOM.New York，USA，2002:1567-1576.

［7］Ringwald M，Romer K.BitMAC:a deterministic，collision-free，and robust MAC protocol for sensor networks［C］//Proceedings of the 2nd European Workshop on Wireless Sensor Networks.Istanbul，Turkey，2005:57-69.

［8］Yu F，Wu T，Biswas S.Toward in-band self-organization in energy-efficient MAC protocols for sensor networks［J］.IEEE Transactions on Mobile Computing，2008，7(2):156-170.

［9］Liu S，Fan K，Sinha P.CMAC:an energy-efficient MAC layer protocol using convergent packet forwarding for wireless sensor networks［J］.ACM Transactions on Sensor Networks，2009，5(4):1-34.

［10］Hurni P，Braun T.MaxMAC:a maximally traffic-adaptive MAC protocol for wireless sensor networks［C］//Proceedings of 2010 European Conference on Wireless Sensor Networks.Coimbra，Portugal，2010:289-305.

［11］Fang C，Liu H，Qian L.LC-MAC:an efficient mac protocol for the long-chain wireless sensor networks［C］//Proceedings of 2011 International Conference on Communications and Mobile Computing.Qingdao，China，2011:495-500.

［12］Hull B，Jamieson K，Balakrishnan H.Mitigating congestion in wireless sensor networks［C］//Proceedings of 2004 International Conference on Embedded Networked Sensor Systems.Baltimore，Maryland，USA，2004:134-147.

［13］Wan C Y，Eisenman S B，Campbell A T.Coda:congestion detection and avoidance in sensor networks［C］//Proceedings of 2003 International Conference on Embedded Networked Sensor Systems.Los Angeles，CA，USA，2003:266-279.

［14］Zhai H，Fang U.Distributed flow control and medium access in multihop ad hoc networks［J］.IEEE Transactions on Mobile Computing，2006，5(11):1503-1514.

［15］Intanagonwiwat C，Govindan R，Estrin D.Directed diffusion:a scalable and robust communication paradigm for sensor networks［C］//Proceedings of 2000 International Conference on Mobile Computing and Networking.Boston，USA，2000:56-67.

［16］Jonhnstone I，Nicholson J，Shehzad B，et al.Experiences from a wireless sensor network deployment in a petroleum environment［C］//Proceedings of 2007 International Conference on Wireless Communications and Mobile Computing.New York，USA，2007:382-387.

［17］Wan Y D，Li L，He J.Anshan:wireless sensor networks for equipment fault diagnosis in the process industry［C］//Proceedings of 2008 Sensor，Mesh and Ad Hoc Communications and Networks.San Francisco，CA，USA，2008:314-322.