一种基于动态虚簇头的WSN拥塞控制改进算法
2015-10-19胡平霞
胡平霞
摘要：针对多跳分簇层次结构WSN模型中簇头出现的拥塞问题，该文提出了一种基于动态虚簇头的拥塞控制改进算法，采用平均队列长度和拥塞度两个参数检测拥塞，通过簇内和簇外采取不同的机制解除和缓解拥塞，仿真实验结果表明该算法在丢包率、网络吞吐量、数据传输时延上都有较好的性能。
关键词：WSN；分簇结构；动态虚簇头；拥塞控制
中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2015）20-0168-04
Congestion Control Algorithm Based on Dynamic Virtual Cluster Head
HU Ping-xia
（Journal of Hunan Environment-Biological Polytechnic， Hengyang 421001， China）
Abstract： Aiming at the congestion problem of cluster head in the WSN model of multi-hop clustering hierarchy， this paper presents an improved Congestion Control algorithm based on Dynamic Virtual Cluster head（CCDVC） to release network congestion. The occurrence of congestion is detected by the average queue length and the congestion degree， different algorithms are taken between inner-cluster and extra-cluster to eliminate congestion and release congestion， the simulation results show that the proposed algorithm performance better in packet loss rate， network throughput and data transmission delay.
Key words： WSN； clustering structure； dynamic virtual cluster head； congestion control
1 引言
无线传感器网络（Wireless Sensor Network， WSN）是由部署在监测区域内大量低成本且具有传感、数据处理和通信能力的传感器节点 （sensor nodes）、基站（Sink）以及任务管理用户通过自组织方式形成的网络[1]。随着物联网技术、无线网络技术发展的日新月异，WSN广泛应用于当今社会各个领域，高密度、大规模的应用使WSN无法承受负载所产生的拥塞问题已经成为WSN应用的束缚。基于分簇结构的WSN由于采用了合理、有效的分层路由协议在WSN应用中突显出优势，这也成为该领域研究热点之一。
目前国内外研究人员提出针对 WSN 的拥塞控制算法集中在CODA[2]、 ESRT[3]、Fusion[4]、 Siphon[5]等，其中STCP[6]（Sensor Transmission Control Protocol）和 COMUT[7]（Congestion control for Multi-class Traffic）是基于分簇结构的典型算法。
文献[6]STCP算法以一定概率在节点发送的数据包包头中设置拥塞比特，Sink节点在收到包含拥塞比特的数据包时通告数据源节点减小发送速率或变更发送路径，使网络拥塞得到缓和或解除。文献[7]的COMUT 算法各节点向簇头周期性地报告估计到的本地流量，簇头结点在此基础得到本地流量的估算值，当该值大于设定好的门限值时，表示网络已经发生了拥塞。本簇簇头与其它簇簇头以周期性广播进行联系，以AIMD 的策略对源节点速率进行调整。这两种算法都是基于流量控制的，虽然在一定程度上解除了网络拥塞，但在WSN实时应用环境中造成实时数据发送不及时或丢失造成损失，网络吞吐量不稳定，数据传输的时延也会增大。
2 WSN分簇结构模型
分簇结构是基于分层的WSN拓扑结构，相对节点地位平等的平面结构，分簇结构中节点地位不平等。在分簇结构中节点被分簇，并定义簇头节点[（Cluster Head，CH）]和成员节点[（ClusterMember，CM）]，。通常一个簇包括一个簇头结点和多个普通结点为，由簇头节点完成本簇内部普通节点的管理和簇内数据的采集，同时还需完成簇间数据转发和整体路由更新和维护。成员结点仅负责完成自身数据收集和路由维护。
由于WSN分簇结构比平面结构在应用上具有显著的优势，在高密度、大规模的WSN应用中已经占据了重要的位置。但簇头结点负责本簇和簇间的数据转发，负荷加重容易产生拥塞，给WSN带来网络拥塞的问题。针对簇头结点出现的拥塞问题，本文提出了一种基于动态虚簇头的拥塞控制改进算法CCBDC（Congestion Control Algorithm Based on Dynamic Virtual Cluster Heads）。
WSN分簇结构网络模型中，以一个无向图[G=（V，E）]来表示节点和链路，其中[V={vi}，i∈L={1，2，…，n}]为WSN节点集合， [E={eij=（i，j）}]为WSN节点通信链路集合，如果[eij=1]，则表示节点i与j互为邻接节点，两节点间存在边。见图1，本文使用的网络模型为两层结构，成员结点CM将数据发送到簇头结点CH需经过[k（1≤k≤4）]跳。
图1 两层分簇结构网络模型图
针对上述网络模型做如下假设：
（1）应用环境假设：WSN是密度的静态网络，节点是静止的（部署后不移动），符合大多数应用要求；
（2）Sink节点假设：Sink节点唯一且位置固定于整个WSN区域外的某一处；
（3）簇及节点假设：簇间相对独立，簇内节点唯一且以[ID（n）]标记；节点能量用完进入死亡状态，不补充能量，簇头节点为（CH）储备更多能量；无辅助定位设施获知位置信息，算法所需信息从相邻节点获取。
3 WSN拥塞检测方法
精准、及时的拥塞检测是拥塞控制的关键之一，合理的拥塞检测应结合多个因素进行判断。基于分簇结构的WSN拥塞大多数发生在簇头结点（CH），导致其发生拥塞有以下两个方面的可能：（1）簇内原因：本簇内发生多个节点频繁发送数据给簇节点的情况；（2）簇外原因：簇外多个簇头节点同时给本簇头发送需转发的数据的情况。因此拥塞检测首要明确引起簇头拥塞的原因才能进行信息反馈。结合以上分析本文采用平均队列长度和拥塞度两个参数来判断网络状态，并结合簇内数据包个数和簇外数据包个数间的比值还确定拥塞原因。
3.1平均队列长度
为实现拥塞控制，引入平均队列长度。在每个簇头缓存中由以下公式计算平均队
列长度：
[Qave=（1-wq）×Q′ave+wq×q] （1）
[Q′ave]是上一时间点已计算的平均队列长度；[wq]是权值；[q]是采样测量时的平均长度。
3.2 拥塞度[C（n）]
节点存储分组会对节点数据处理产生压力，影响其处理分组的能力。节点拥塞度定义如下：
[C（n）=TsTa] （2）
[Ta=（1-p）×Ta+p×（t-t′）] （3）
[Ts=（1-p）×Ts+p×ts] （4）
使用节点MAC层接收数据包的平均时间和转发数据包的平均时间之比来衡量拥塞度，其中[t]为本次数据包的到达时间，[t′]为上一数据包的到达时间，[Ts]为到达节点MAC层的两个相邻数据包的平均时间间隔；[Ta]表示数据包在本节点的平均处理时间；[ts]为刚刚发出的数据包的传输时间；p是通过经验设定的常量（SenTCP[9]算法中设定为[0.1]，在本文通过反复实验设定为0.2实验效果最佳）。拥塞度[C（n）≤1]说明节点n状态正常，反之则表示节点趋于拥塞。
3.3 拥塞检测
从拥塞检测的精准性和节点耗能代价两方面考虑，利用三个阈值[α1]、[α2] 和[α3]将节点缓存队列分成四个区：0区、1区、2区和3区，分别表示安全区、恢复区、避免区、拥塞区，如图2所示。
图2 节点缓存队列示意图
结合平均队列长度[Qave]通过三个参数[r1]、[r2] 和[r3]将节点缓存分成以下四种状态，分别表示安全状态，恢复状态，拥塞避免状态、拥塞状态，如表1所示：
表1 网络状态表
[[Qave]值大小＼&节点缓存状态＼&[Qave]<[r1]＼&安全状态＼&[r1]<[Qave]<[r2]＼&恢复状态＼&[r2]<[Qave]<[r3]＼&拥塞避免状态＼&[Qave]>[r3]＼&拥塞状态＼&]
处于安全状态表示网络运行平稳，无需进行拥塞检测；处于恢复状态表示节点负荷大有可能进入拥塞，考虑WSN突发性因素结合拥塞度[C（n）]进行如下分析：
[C（n）≤1]不做任何处理，由节点自身调节恢复到安全状态，[C（n）>1]，认为节点进入准拥塞状态，需采用拥塞避免机制；在拥塞避免状态直接启动拥塞避免机制；在拥塞状态表示拥塞避免已经无效，节点采取一定策略进行丢包或降低发送速率以解除拥塞。
在安全状态以外的节点采用数据包采样方法在周期时间T内计算簇外数据包及簇间数据包数，并根据二者的比值分析引发拥塞的原因，见式（5）。通过e的值分析拥塞产生的原因，本文通过反复实验分析如下：当[0
[e=MN] （5）
式中M为来自簇内CM节点的数据包总数，N指来自簇间CH节点的数据包总数。
3.4 最短路径树[（SPT）]定义和说明
最短路径树[（Shortest path tree，SPT）]是树状拓扑结构最合适用于WSN的一种，通过找到最短路径即到目标节点转发跳数最少的路径，在网络环境相当的情况下其具有较低的数据传输时延。本文[SPT]符号及相关说明如下：
表2 最短路径树（SPT）符号和说明
[名称＼&符号＼&说明＼&跳数＼&h（n）＼&普通节点n到簇首节点的最小跳数＼&邻接点跳数＼&hn（m）＼&普通节点n的邻接节点m到簇首节点的最小跳数＼&度数＼&d（n）＼&普通节点n与其邻接节点相连接的边数＼&邻接点度数＼&dn（m）＼&普通节点n的邻接节点m的度数＼&邻接点集＼&N（n）＼&普通节点n的邻接节点集＼&父节点集＼&F（n）＼&普通节点n的父节点集：[F（n）=uu∈V?u∈N（n）?h（u）=h（u）-1]＼&子树节点个数＼&t（n）＼&以普通节点n为根的子树中节点个数＼&]
每个传感器节点都有一个唯一的ID号，根据节点的度数d（n）以及ID号的大小可以对G=（V，E）中任意节点n的父节点集F（n）构造一个全序集（F（n），[?]），公式（6）如下：
[m?n=ID（m） 4 基于CCBDC算法的WSN拥塞控制算法 本算法的主要思想是在通过在簇内的寻找动态虚拟簇头结点为本簇内的簇头节点分流。通过簇内拥塞分析和检测使用最短路径树算法寻找动态VCH，形成以此节点为根的子树，重新计算树成员节点的路由，树成员节点通过此路由发送数据到VCH；簇间通过动态虚拟簇头分流来缓解网络拥塞。根据分析，簇头节点最容易发生拥塞，在本算法中，簇头节点周期性的运行着此算法，VCH根据网络情况动态变化。周期内算法步骤伪代码表示如下： （1）开始 （2）拥塞检测 （3）是否发生拥塞，是转入下一步，否转入结束 （4）簇内产生拥塞，转入一下步，否则是转入（9） （5）通过最短路径算法寻找VCH （6）重定向路由 （7）拥塞缓解 （8）是否发生簇间拥塞，是转入（10），否转入结束 （9）通过能量算法寻找VCH （10）构造多元路径 （11）拥塞缓解 （12）销毁多元路径 （13）结束 算法开始进入拥塞检测，产生拥塞，根据拥塞检测算法判断，若是簇内拥塞，通过最短路径算法寻找VCH，并重新计算路由更新节点路由，拥塞缓解后要判断是簇间是否有拥塞发生，是则进行簇间控制，否则本轮拥塞处理结束，网络进入平稳状态；如果拥塞不是簇内原因引起，进入簇间控制，通过能量状态来寻找VCH并进行簇间拥塞处理。若没有检测到拥塞返回开始，等待下一个周期的检测。 5 算法实验仿真与结果分析 5.1仿真平台及参数设置 根据研究内容及特点，本文选择NS2网络仿真平台，网络环境及参数设置见表 表3 仿真实验参数 [仿真参数＼&数值＼&仿真参数＼&数值＼&Mac层协议＼&IEEE802.11＼&链路带宽（bps）＼&1M＼&节点频率＼&914MHz＼&发送功率＼&550mW＼&接收功率＼&395mW＼&监听功率＼&360mW＼&节点最大传输距离＼&15m＼&部署范围＼&100m *100m＼&节点数目＼&1000＼&簇首数目＼&25＼&缓存区容量B＼&200个数据包＼&数据包大小＼&100bytes＼&α1、α2、α3＼&0.7、0.85、0.95＼&仿真时间＼&60s＼&] 本文从网络吞吐量、数据传输时延及丢包率三个方面对算法在NS2网络仿真平台上进行了仿真，并对STCP和COMUT算法作对比实验。 5.2 仿真结果与分析 在仿真实验结束后，通过调用自动生成的[Trace]文件得到实验中的反映状态的数据和实验结果数据。借助专业绘图软件[Origin]根据[Trace]文件中的数据形成数据图表对各项性能指标进行分析。 （1）网络吞吐量仿真实验及结果分析 在本实验中，通过10个源节节点不断给Sink节点发送数据，仿真时间设置为60秒，网络吞吐量即为统计Sink节点收到的数据包个数，通过修改速率重复实验，实验结果如图3所示： 图3 三种算法在不同速率下的网络吞吐量 从实验结果数据图中可以得到三种算法在不同的发送速率下网络吞吐量的情况对比，当节点发送速率小于时，吞吐量相差不大且随着发送速率增大而以线性形式增长。当发送速率大于0.6packet/s时，CCBDC算法的吞吐量明显大于COMUT、STCP算法两算法的吞吐量，通过分析后两种算法采取降低速率的方法缓解拥塞，而CCBDC算法采用了精准有效的簇间或簇内的拥塞避免机制，吞吐量随速率的增加略有增加并趋于平稳。 （2）丢包率仿真实验及结果分析 在此实验中，通过设置普通节点的数据包发送速率，统计各节点到达包的个数、应达包个数为节点发送速率、节点数目、仿真时间三者的乘积，应达包和到达包之差得到丢包个数，其中丢包率按下公式计算： [丢包率=丢包书目节点总发包数] （7） 图4 三种算法在不同速率下的丢包率 实验结果如图4所示，从实验结果数据图中可以得到当数据包发送速率高于0.6packet/s时，CCBDC算法在丢包率这下指标上明显强于COMUT算法和STCP算法，难过分析后两种算法通过降低速率来避免丢包，CCBDC算法是采用调整网络结构措施来避免拥塞造成丢包，因此在本次实验中CCBDC算法性能强于COMUT算法和STCP算法。 （3）数据传输时延仿真实验及结果分析 本次实验通过远距离（距离Sink节点）普通节点分别在不同速率下向目标Sink节点传送数据包，计算数据包从源节点发送到Sink节点接收时间，修改速率反复实验，得到平均传输时延，实验结果如结果如图5所示： 图5 三种算法的数据传输时延 从实验结果数据图中可以得到三种算法的传输时延因发送速率的增加而加大，发送速率在0.6packet/s以下时，在种算法性能相当；当发送速率在0.6packet/s和 0.65packet/s之间时，由于此网络状态下，CCBDC正在寻找虚拟簇头节点以及构造多元路径增加了开销，因此 CCBDC算法的传输时延会略大于其他两种算法；当发送速率在0.65packet/s以上时，CCBDC算法虚拟簇头已经生成，拥塞缓解或减轻，因此CCBDC算法在速率0.65packet/s以上时在传输时延上明显优于COMUT算法和STCP算法。
6总结
本文在基于分簇结构的WSN基础上，提出一种基于动态虚簇头的拥塞控制算法处理网络拥塞问题。采用平均队列长度和拥塞度两个参数来判断网络状态，并结合簇内数据包个数和簇外数据包个数间的比值还确定拥塞原因。通过构造多元路径解决簇间拥塞及在簇内寻找虚簇头解决簇内拥塞。通过仿真实验平台，与COMUT算法、STCP算法进行对比性实验并分析实验结果，本算法在网络吞吐量、数据传输时延及丢包率三个方面有所改善，但是由于实验都是在仿真平台完成，对比实际应用环境的复杂性，存在着一定的局限性，如何将算法应用于实际应用环境中这是以后努力的方向。
参考文献：
[1] 任丰原， 黄海宁， 林 闯. 无线传感器网络[J]. 软件学报， 2003，14（7）：1284-1291.
[2] Wan C Y， Eiseman S B， Cambell A T. CODA： CongestionDetection and Avoidance in Sensor Networks[C].Proc. of the1st ACM Conference on Embedded Networked Sensor Systems.Los Angeles， USA： [s. n.]， 2003.
[3] Sankarasubramaniam Y， Akan O B， Akyidiz I F. ESRT： Event-tosink Reliable Transport in Wireless Sensor Networks[C].Proc. Of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing. Annapolis， USA： [s. n.]， 2003.
[4] Hull B， Jamieson K， Balakrishnan H. Mitigating Congestion in Wireless Sensor Networks[C].Proc. of the 2nd ACM Conf. on Embedded Networked Sensor Systems. Baltimore， USA： [s. n.]，2004.
[5] Wan C Y， Eisenman S B， Campbell A T， et al. Siphon： Overload Traffic Management Using Multi-radio Virtual Sinks[C].Proc. Of the 13th ACM Conf. on Embedded Networked Sensor Systems.·New York， USA： [s. n.]， 2005.
[6] Iyer Y G， Gandham S， Venkatesan S. STCP： A Generic Transport Layer Protocol for Wireless Sensor Networks[C].Proc. of the 14th International Conference on Computer Communication. San Diego， USA： [s. n.]， 2005.
[7] Karenos K， Kalogerak V， Krishnamurthy S V. Cluster-based Congestion Control for Supporting Multiple Classes of Traffic in Sensor Networks[C].Proc. of the 2nd IEEE Workshop on Embedded Networked Sensors. Washington D. C.， USA： [s. n.]， 2005.
[8]刘永帅，无线传感器网络拥塞控制的研究[D].燕山大学，2011.
[9]Wang C， Sohraby K，Li B.SenTCP：A Hop-by-Hop Congestion Control Protocol for Wireless Sensor Network[C].Proceedings of the 24th IEEE Conference on Computer Communications.USA：IEEE Computer Society， 2005.
[10]Charalambos Sergiou ， Vasos Vassiliou， Aristodemos Paphitis.Hierarchical Tree Alternative Path （HTAP） algorithm for congestion control in wireless sensor networks[C]. Ad Hoc Networks 2013 （11）： 257-272.
