基于动态概率休眠调度机制的WSNs 拓扑控制算法*

韩瑞艳，高 飞，李伯宇，刘小雨

(云南民族大学 电气信息工程学院，云南 昆明650500)

0 引 言

无线传感器网络(WSNs)拓扑控制是WSNs 建网和通信的基础，其控制方法主要采用节点功率控制和层次型拓扑控制两大类［1］。前者为传感器节点选择合适的发射功率，而后者采用基于休眠调度的拓扑控制机制，是一种较为经典的方法，全连通群的休眠调度算法［2］，基于梯度的微传感器休眠调度路由协议(gradient－based micro sensor routing protocol with sleep scheduling，GMSRP－SLE)［3］算法，分簇的地理拓扑控制(geographical topology control，GTC)［4］算法以 及 分 组 调 度 协 议(group－based scheduling protocol，GSP)［5］等算法都属于此类方法，均可有效减少网络总体能量消耗，并延长网络的生命周期。上述算法在网络节点密度较大时，所构造的簇的数量较多，簇头间信息交互量大，会造成能量不必要的开销。而且，当采用非均匀分簇和随机休眠调度机制时，节点易出现休眠不均匀的现象，从而不能合理均衡地利用节点的能量，网络的连通性也因此受到影响。

为了有效恢复休眠节点引起的连通受损的局部拓扑结构，在保障网络连通性的基础上延长网络的生命周期，本文提出一种融合了随机调度(randomized scheduling，RS)［6］算法和层次型低能耗自适应分簇(low－energy adaptive clustering hierarchy，LEACH)算法［7］的动态概率休眠调度机制的拓扑控制(dynamic probability sleep－scheduling based topology control，DPSS—TC)算法。

1 算法设计

1.1 设计思想

本文采用让成员节点以一定的概率进入休眠的休眠调度机制来均衡节点的能量消耗。算法的设计思想如图1 所示。其中，n0为簇头所属簇内的成员节点数量，n'为可执行休眠调度的成员节点数量的阈值，p 为休眠概率的取值范围;节点的工作状态用标识符S.state 表示如下

遍历节点的初始状态，即S.state=1。簇头根据所属簇内的成员节点数量n0自适应地设定休眠概率p，执行随机休眠调度，并有效恢复连通受损的局部拓扑。

1.2 DPSS—TC 算法的实现步骤

1.2.1 分簇并获取邻居信息

执行LEACH 算法后，簇内的每个成员节点向簇头分别发送报文{ID，Er，Dt}，包括节点信息ID、节点当前剩余能量信息Er、成员节点与簇头的距离Dt。簇头统计成员节点的数量n0，而且，每个节点将获得其所有1 跳邻居完整的信息和自己所处位置到簇头节点的通信跳数r。

1.2.2 休眠调度

为了实现簇内的连通，簇头需根据簇内的成员节点数量n0动态地设置休眠概率p，以确保簇内有一定量的活跃节点。执行休眠调度后，为避免某些簇内的成员节点全休眠，因此，执行休眠调度后的成员节点中应至少存在n(n∈N+)个活跃节点

其中，标识符S.flag=1 表示簇内成员节点不执行休眠调度;S.flag=0 表示簇内成员节点执行休眠调度。当S.flag=0时，簇头根据n0动态地设置休眠概率p，并向簇内的成员节点发送携带p 的hello—2 报文。

由于休眠节点易造成部分通信链路中断，簇头无法进一步判断簇内的连通性能。因此，节点在休眠之前，需增加一个预处理过程，即各个成员节点向自己所属簇内的簇头发送hello—3 报文，报文中携带自身的状态信息，节点发送报文hello—3 之后，节点才能进入到相应的休眠状态或活跃状态。

1.2.3 连通性的恢复

由于休眠节点会导致网络的部分拓扑结构变化，因此，需要对连通失效的拓扑部分进行恢复，以便网络保持良好的通信状态。连通性判据如下

其中，标识符S.connectivity=1 表示簇内的连通性良好，S.connectivity=0 表示簇内的连通性有待进一步判决;r.active 表示活跃节点分布在与所属簇头相距的r 跳。若S.connectivity，则根据中断链路是否存在休眠节点的情况，采取如下调度措施:1)若两个不连通的活跃节点间存在休眠节点，需强制性唤醒休眠节点;2)若不存在休眠节点，则提高相应活跃节点的发射功率。

直至簇内相邻两跳内的活跃节点间正常通信，节点在该轮次的剩余时间内保持当前状态，网络转入稳定的数据通信阶段，节点周期性地执行该算法。

2 算法的仿真分析

2.1 节点休眠概率的设定

由于节点执行休眠判决时，每个节点独立地以概率方式判断该轮次中自身的状态，每个节点做一次贝努利实验。那么簇内存在n0个成员节点时，需做n0次贝努利实验。

簇内的节点个数设为nt，休眠概率设为p，则节点的活跃概率为q=1－p;簇头需保持在活跃状态，故休眠调度的节点个数为n0=nt－1。簇内存在n(n=0，1，2，…，n0)个活跃节点的概率设为p(n)，则

簇内n0个成员节点中至少存在k(k=1，2，3，…，n0)个活跃节点的概率设为q(k)，则

由k≤n0可知(k－1)＜n0，由于，显然0≤，故q(k)的取值范围为(0，1］。为了提高运算的精确性，将式(2)所得结果小数点后的第四位四舍五入，若取值为1，即q(k)的概率值为1，说明该次实验为必然事件。

从上述分析可知，由式(2)可知n0与p 的关系，将“执行休眠调度后的成员节点中存在至少n 个活跃节点”设为事件A。分析n=3 时，事件A 必然发生时所需p 的取值范围，如表1 所示。

经计算可知，p(A)={n|n0≤n}=Φ;从表中数据可知，p(A)={n|n0∈［4，6］，p=0.1}=Φ。因此，p(A)={n|n0＜n'}=Φ。因此，当n0＜n'时，则说明簇内成员节点较为稀少，为保证监测的有效性和可靠性，节点均保持在活跃状态;当n0≥n'时，簇内成员节点执行休眠调度。

表1 休眠概率p 的取值范围Tab 1 Value range of dormant probability

2.2 性能分析

本文采用Matlab 对算法进行仿真分析，其中，LEACH算法部分的仿真参数值一般为固定值，这些参数的具体设置如表2 所示。其他仿真参数值设置如下:在200 m×200 m的监测区域内，随机撒布s(100≤s≤200)个传感器节点，Sink 节点位于(0，0)m 处;节点的能量均等且具有相同的通信半径，其初始能量E0为0.5 J;节点在活跃状态下单位时间能耗为10 μJ/s，在休眠状态下的单位时间能耗为100 nJ/s，节点失效的能量阈值为10 μJ，节点提高发射功率时单位时间能耗为1 nJ/s。此外，不考虑分簇后每一轮次成员节点进行报文信息交互时的能量消耗。

表2 LEACH 算法部分仿真参数Tab 2 Partial simulation parameters of LEACH algorithm

若n 的取值过大，某些簇内的成员节点经休眠调度后依然全处在活跃状态，不能最大化节约节点的能量消耗。因此，n 的仿真参数取值为n∈［3，9］，n 与阈值n'的取值关系如表3 所示。

表3 满足n 时n'的最小值Tab 3 The minimum value of n'to meet n

本文将网络生命周期定义为网络中所有节点全部进入死亡状态时网络持续的有效工作时间，分析 取不同参数值时对网络生命周期的影响，如图2 所示。

图2 n 的取值对网络生命周期的影响Fig 2 Influences of value of n on network lifetime

从图2 可知，当n 一定时，网络的存活轮次随节点数量的增加而增加;当节点数量一定时，n 的取值对网络的存活时间影响不大，本文取n=3。比较DPSS—TC 算法和LEACH 算法对网络生命周期的影响，如图3 所示。

图3 网络生命周期的分析Fig 3 Analysis on network lifetime

通过仿真实验可知，网络的生命周期与网络中节点的数量为近似线性比例关系。由于DPSS—TC 算法可进一步均衡节点的能量消耗，其在节能效果上优于LEACH 算法，并且在保障网络连通的基础上有效地延长了网络的生命周期。

3 结 论

拓扑控制作为WSNs 的一种关键节能技术，通常在保持网络重要特性如连通和覆盖的前提下改变、简化或优化网络的拓扑来节省能量。仿真实验表明:DPSS—TC 算法不仅能保证网络的连通性，而且有效延长了网络的存活周期。

［1］ Akyildiz I F，Su W，Sankarasubramaniam Y，et al.A survey on sensor networks［J］.Communications Magazine，IEEE，2002，40(8):102－114.

［2］ 董 蕾，于宏毅，张 霞.一种无线传感器网络全连通群的休眠调度算法［J］.电子与信息学报，2007，29(5):1220－1223.

［3］ Gao D，Zheng T，Zhang S，et al.Improved gradient－based micro sensor routing protocol with node sleep scheduling in wireless sensor networks［C］∥2010 IEEE 72nd Vehicular Technology Conference，VTC 2010 Fall，IEEE，2010:1－5.

［4］ Zebbane B，Chenait M，Badache N.Towards an energy－efficient algorithm based sleep－scheduling for wireless sensor networks［C］∥2012 The 5th International Conference on New Technologies，Mobility and Security(NTMS)，IEEE，2012:1－4.

［5］ Zebbane B，Chenait M，Badache N.Enhancing the sensor network lifetime by topology control and sleep－scheduling［C］∥2013 International Conference on Smart Communications in Network Technologies(SaCoNeT)，IEEE，2013:1－5.

［6］ 丁雷雷，高 飞，韩瑞艳.基于节点休眠机制的无线传感器网络覆盖控制算法［J］.云南民族大学学报:自然科学版，2015，24(3):230－234.

［7］ Xu Y，Heidemann J，Estrin D.Adaptive energy－conserving routing for multihop Ad Hoc networks［R］.Los Angeles:USC，2000.

［8］ Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application－specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.