一种无线传感器网络非均匀分簇节点调度方法

摘要

本发明公开了一种无线传感器网络非均匀分簇节点调度方法，具体按照以下步骤实施：步骤1.非均匀分簇簇首的选举以及完成非均匀分簇；步骤2.在步骤1完成非均匀的分簇后，在簇内查找冗余节点，并关闭冗余节点使冗余节点进入休眠状态；步骤3.在完成步骤2冗余节点的调度休眠后，活动节点进入稳定工作状态；步骤4.在步骤3中活动节点工作完成之后，对簇内节点角色与状态进行调整；步骤5.在步骤4的节点角色与状态调整完之后，将循环执行步骤3、步骤4，直至所有节点能量消耗完。本发明一种无线传感器网络非均匀分簇节点调度方法，将非均匀分簇与冗余节点调度相结合，使得各节点的能量消耗比较均衡，有效的延长了网络的生命周期。

说明书

技术领域

本发明属于无线传感器网络技术领域，涉及一种无线传感器网络非均匀 分簇节点调度方法。

背景技术

无线传感器网络(Wireless Sensor Network，WSN)节点的能量、资源、 通信能力十分有限，如何利用节点能量设计高效的节点调度算法提高网络寿 命成为当前无线传感器网络研究的关键问题。

早在2000年，Heinzelman W提出了第一个针对WSN设计的低功耗自 适应分簇路由协议LEACH，该算法将网络的负载分配到每个节点上，从而 降低单个节点能量消耗，提高网络生存时间，但LEACH协议没有考虑簇首 分布不均以及节点剩余能量等问题。LEACH的改进协议很多，例如，采用 集中式的簇首产生算法，根据全局信息挑选簇首，有效控制簇首的数量和位 置，同时考虑剩余能量。LAECH协议及其改进算法虽然有效延长网络生命 周期，但存在簇间能量消耗不均衡的问题，离汇聚节点远的簇首仍然具有较 大的能耗。

针对簇间能量消耗不均衡等问题，国内外研究人员采用非均匀分簇策略 来平衡簇首的能量消耗。EECS方法为了均衡簇首能量消耗，普通节点在选 择簇首时不仅要考虑自身离簇首的距离，而且要考虑簇首到汇聚节点的距离， 从而构造出大小非均匀的簇。但EECS的能量平衡措施只能缓解簇首间的能 量消耗不均衡现象，无法从整体上实现节点间的能量平衡。而EEUC采用非 均匀分簇和簇间多跳路由有机结合的方式，利用非均匀的竞争半径，使得靠 近基站的簇的成员数目相对较小，从而簇首能够节约能量以供簇间数据转发 使用，达到均衡簇首能量消耗的目的，但EEUC只适合均匀分布的网络。在 原有方法的基础上，继承EEUC的非均匀分簇结构，采用基于时间驱动的 簇首选择机制且利用贪婪算法寻找簇首转发的中继节点。以上非均匀分簇算 法中，每一轮所有节点都要处于工作状态进行数据采集与传输，在节点分布 密集的无线传感器网络中，这样会造成大量信息冗余、无线信号干扰、能量 浪费等问题。

发明内容

本发明的目的是提供一种无线传感器网络非均匀分簇节点调度方法，解 决了现有技术中存在的无线传感器网络中节点能耗不均衡，网络的生命周期 短的问题。

本发明所采用的技术方案是，一种无线传感器网络非均匀分簇节点调度 方法，具体按照以下步骤实施：

步骤1、非均匀分簇簇首的选举以及完成非均匀分簇；

步骤2、在步骤1完成非均匀的分簇后，在簇内查找冗余节点，并关闭 冗余节点使冗余节点进入休眠状态；

步骤3、在完成步骤2冗余节点的调度休眠后，活动节点进入稳定工作 状态；

步骤4、在步骤3中活动节点工作完成之后，对簇内节点角色与状态进 行调整；

步骤5、在步骤4的节点角色与状态调整完之后，将循环执行步骤3、 步骤4，直至所有节点能量消耗完。

本发明的特点还在于，

步骤1簇首的具体选举方式及完成非均匀分簇为：距离汇聚节点近的簇 首消耗的能量较少，远离汇聚节点的簇首消耗的能量较多，因此越远离汇聚 节点形成的簇要越小，以平衡簇间较大的通信消耗；首轮所有节点参与簇首 的竞选，平衡所有节点的能耗；为了使越远离汇聚节点形成的簇越小，给每 个竞选簇首节点设置一个竞争半径R_compete，R_compete是节点距离汇聚点距 离与所在区域节点密度的函数；每个竞选簇首节点竞争半径N_i.R_compete的公 式为：

$\left(\begin{array}{c}{N}_i.R_{\mathrm{compete}}=(1-c\frac{d(N_i,\mathrm{BS})-d_{\min }}{d_{\max }-d_{\min }})(1-\rho )R_{\mathrm{set}}\\ \rho =(N_{\mathrm{nei}}\left(i\right)-1)/N_{\mathrm{all}}\end{array}\right)---\left(1\right)$

其中，其中d_max和d_min分别代表网络中的节点到汇聚点的最大距离和最 小距离；c是用于控制取值范围的参数，在0～1之间取值；ρ是节点所在区域 的密度因子；d(N_i，BS)是传感器节点到汇聚节点的距离；N_i是网络中任 一节点；i是网络区域中任意传感器节点的标号；R_set是预先设定最大竞争 半径；N_nei(i)是邻居节点数；N_all是整个网络中存活节点数。

在簇首竞选过程中，若候选簇首N_i宣布其竞选获胜，则在N_i的竞争半径 N_i.R_compete内的所有候选簇首均不能成为最终簇首，需要退出竞选过程，均 成为普通节点，同时这些节点加入最终簇首N_i，形成一个以N_i为簇首，N_i的 竞争半径内的其他候选簇首为簇内普通成员的一个簇。

步骤2的具体实施过程为：将簇内节点按能量从小到大排序，并将节点 的ID依次存储在名为clusterNodes的集合中，集合中每个元素都存在一个 index标记，在判断冗余节点时，簇首通过index+1的大小给簇内节点分配时 序，节点每次都从能量最小的节点开始判断是否为冗余节点，若为冗余节点， 则此节点立即进入睡眠状态，并发送一个休眠消息给其感知节点，避免了相 邻的两个节点同时休眠而出现的监测空洞现象，同时启动一个睡眠计时器 T_sleep保证在下一轮开始时处于活动状态。

步骤3的具体实施过程为：簇内节点采集监测区域内的信息，在自己传 输数据的时序内采用CSMA MAC协议向其簇首发送数据；簇首节点接收 来自簇内各个节点的信息，将其融合后以单跳方式发送给汇聚点。

步骤4的具体实施过程为：首先冗余节点睡眠计时器T_sleep到达，冗余 节点从睡眠状态转为工作状态；其次簇内的所有节点向上一轮簇首发送带有 自己ID和剩余能量的消息，簇首根据节点的剩余能量进行排序，更新 clusterNodes集合，选出能量最大的节点担任本轮簇首，向其它节点公布新 簇首的ID并向新簇首发送携带clusterNodes信息的消息；然后在各个簇内通 过判断冗余节点的方法判断节点是否为冗余节点；如果某个节点确定为冗余 节点，则立即将该节点转为睡眠状态，如果某个节点确定不是冗余节点，则 继续判断另一个节点，直到所有节点查找完毕。

判断冗余节点的判断方法为：节点检测监测半径R内是否存在4个或 4个以上的非簇首节点，这些节点称为N_i的感知节点，如果存在至少4个 感知节点按逆时针顺序相邻节点间的夹角同时满足60°～120°，则该节点冗 余，此时它的活动状态转为休眠状态。

本发明的有益效果是：本发明一种无线传感器网络非均匀分簇节点调度 方法将非均匀分簇与冗余节点调度相结合，使得每个节点的能量消耗比较均 衡，同时避免了大量的冗余节点同时工作造成资源浪费的问题，这样有效的 延长了网络的生命周期。

附图说明

图1是本发明一种无线传感器网络非均匀分簇节点调度方法中竞选簇首 节点的拓扑示意图；

图2是本发明一种无线传感器网络非均匀分簇节点调度方法中候选簇首 N与其他候选簇首的竞选示意图；

图3是本发明一种无线传感器网络非均匀分簇节点调度方法中感知节点 的分布图；

图4是本发明一种无线传感器网络非均匀分簇节点调度方法与两种现有 的经典方法的网络总能量的比较图；

图5是本发明一种无线传感器网络非均匀分簇节点调度方法与两种现有 的经典方法的网络存活时间的比较图。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细说明。

本发明一种无线传感器网络非均匀分簇节点调度方法，具体按照以下步 骤实施：

步骤1、非均匀分簇簇首的选举以及完成非均匀分簇，选举方式为：距 离汇聚节点近的簇首消耗的能量较少，远离汇聚节点的簇首消耗的能量较多， 因此越远离汇聚节点形成的簇要越小，以平衡簇间较大的通信消耗；首轮所 有节点参与簇首的竞选，平衡所有节点的能耗；为了使越远离汇聚节点形成 的簇越小，给每个竞选簇首节点设置一个竞争半径R_compete，R_compete是节 点距离汇聚点距离与所在区域节点密度的函数；每个竞选簇首节点竞争半径 N_i.R_compete的公式为：

$\left(\begin{array}{c}{N}_i.R_{\mathrm{compete}}=(1-c\frac{d(N_i,\mathrm{BS})-d_{\min }}{d_{\max }-d_{\min }})(1-\rho )R_{\mathrm{set}}\\ \rho =(N_{\mathrm{nei}}\left(i\right)-1)/N_{\mathrm{all}}\end{array}\right)---\left(1\right)$

其中，其中d_max和d_min分别代表网络中的节点到汇聚点的最大距离和最 小距离；c是用于控制取值范围的参数，在0～1之间取值；ρ是节点所在区域 的密度因子；d(N_i，BS)是传感器节点到汇聚节点的距离；N_i是网络中任 一节点；i是网络区域中任意传感器节点的标号；R_set是预先设定最大竞争 半径；N_nei(i)是邻居节点数；N_all是整个网络中存活节点数；

在簇首竞选过程中，若候选簇首N_i宣布其竞选获胜，则在N_i的竞争半径 N_i.R_compete内的所有候选簇首均不能成为最终簇首，需要退出竞选过程均成 为普通节点，同时这些节点加入最终簇首N_i，形成一个以N_i为簇首，N_i的竞 争半径内的其他候选簇首为簇内普通成员的一个簇；

步骤2、在步骤1完成非均匀的分簇后，在簇内查找冗余节点，并关闭 冗余节点使冗余节点进入休眠状态，具体为：将簇内节点按能量从小到大排 序，并将节点的ID依次存储在名为clusterNodes的集合中，集合中每个元素 都存在一个index标记，在判断冗余节点时，簇首通过index+1的大小给簇 内节点分配时序，节点每次都从能量最小的节点开始判断是否为冗余节点， 判断方法为：节点检测监测半径R内是否存在4个或4个以上的非簇首节 点，这些节点称为Ni的感知节点，如果存在至少4个感知节点按逆时针顺 序相邻节点间的夹角同时满足60°～120°，则该节点冗余，此时它的活动状 态转为休眠状态，并发送一个休眠消息给其感知节点，避免了相邻的两个节 点同时休眠而出现的监测空洞现象，同时启动一个睡眠计时器T_sleep保证在 下一轮开始时处于活动状态；

步骤3、在完成步骤2冗余节点的调度休眠后，活动节点进入稳定工作 状态，簇内节点采集监测区域内的信息，在自己传输数据的时序内采用 CSMA MAC协议向其簇首发送数据；簇首节点接收来自簇内各个节点的信 息，将其融合后以单跳方式发送给汇聚点；

步骤4、在步骤3中活动节点工作完成之后，对簇内节点角色与状态进 行调整，具体为：首先冗余节点睡眠计时器T_sleep到达，冗余节点从睡眠状 态转为工作状态；其次簇内的所有节点向上一轮簇首发送带有自己ID和剩 余能量的消息，簇首根据节点的剩余能量进行排序，更新clusterNodes集合， 选出能量最大的节点担任本轮簇首，向其它节点公布新簇首的ID并向新簇 首发送携带clusterNodes信息的消息；然后在各个簇内通过判断冗余节点的 方法判断节点是否为冗余节点；如果某个节点确定为冗余节点，则立即将该 节点转为睡眠状态，如果某个节点确定不是冗余节点，则继续判断另一个节 点，直到所有节点查找完毕。

步骤5、在步骤4的节点角色与状态调整完之后，将循环执行步骤3、 步骤4，直至所有节点能量消耗完。

实施例

步骤1、非均匀分簇簇首的选举以及完成非均匀分簇

在网络初始阶段，汇聚点以一定的功率向网络内广播一个信号，每个传 感器节点在接收到此信号后，根据接收信号的强度RSSI计算它到汇聚节点的 近似距离，并将这个距离记为d(N_i，BS)，N_i指网络中任一节点，i指网 络区域中任意传感器节点的标号。由于距离汇聚节点近的簇首消耗的能量较 少，远离汇聚节点的簇首消耗的能量较多，因此越远离汇聚节点形成的簇要 越小，以平衡簇间较大的通信消耗。本发明一种无线传感器网络非均匀分簇 节点调度方法在首轮采用所有节点参与簇首的竞选，平衡所有节点的能耗。 为了使越远离汇聚节点形成的簇越小，给每个竞选簇首节点设置一个竞争半 径R_compete，R_compete是节点距离汇聚点距离与所在区域节点密度的函数。 该函数主要功能是在节点密度相等的情况下，使远离汇聚点的节点具有较小 的竞争半径，从而生成较多的簇首，每个簇的范围就小，距离汇聚点较近的 节点具有较大的竞争半径，从而生成较少的簇首，每个簇的范围就大；在节 点与汇聚点距离相同的情况下，节点所在密度因子大，簇的竞争半径就小。 假定R_set是预先设定最大竞争半径，每个竞选簇首节点竞争半径N_i.R_compete如公式(1)所示：

$\left(\begin{array}{c}{N}_i.R_{\mathrm{compete}}=(1-c\frac{d(N_i,\mathrm{BS})-d_{\min }}{d_{\max }-d_{\min }})(1-\rho )R_{\mathrm{set}}\\ \rho =(N_{\mathrm{nei}}\left(i\right)-1)/N_{\mathrm{all}}\end{array}\right)---\left(1\right)$

其中，其中d_max和d_min分别代表网络中的节点到汇聚点的最大距离和最 小距离，c是用于控制取值范围的参数，在0～1之间取值，ρ是节点所在区域 的密度因子，它由节点采用布尔感知模型时检测到的邻居节点数N_nei(i)与 整个网络中存活节点数N_all的比重所确定的。由公式(1)可以看出，当两个 簇首节点密度相同时，距汇聚节点距离越远，簇半径越小，使簇内节省能量 用于簇首数据转发。当两个簇首到汇聚节点的距离相等时，节点所在区域密 度越大的竞争半径越小，达到平衡各簇负载的目的。

图1所示为一张竞选簇首节点的拓扑示意图，从左到右3个大小不同的 圆分别代表节点N₁，N₂，N₃的竞争区域。假设在节点N₁的竞争区域内，N₁竞 选获胜，则N₁成为簇首，在N₂的竞争区域内，N₂竞选成功，因为N₁在N₂的 竞选范围内，因此N₂代替N₁成为簇首。相同地，N₃竞选成功，N₃又代替N₂成 为簇首。此时，在3个节点的竞争范围内就只产生了一个簇首。为了避免上 述情况发生，定义候选簇首的竞争规则如下：

在竞选过程中，若候选簇首N_i宣布其竞选获胜，则在N_i的竞争半径 N_i.R_compete内的所有候选簇首均不能成为最终簇首，需要退出竞选过程。

图2为监测区域内任意一候选簇首N与其他候选簇首的竞选示意图，共有 (a)、(b)、(c)、(d)四种情况。由候选簇首的竞争规则可直接得出， N₂、N₃不能与N同时成为簇首。对于(c)所示情况，假设N竞选成功成为簇 首，若N₄也竞选成功，则根据候选簇首的竞争规则，候选簇首N₄竞选成功， 在N₄竞争半径内的所有候选簇首都不能成为最终簇首，则说明N不能成为簇 首，这与假设N竞选成功矛盾，因此由候选簇首的竞争规则可以得出当N竞 选成功时，N₄需退出竞选过程。对于(d)所示情况，N和N₅可以同时成为 簇首，两者互不影响。将图2中(a)、(b)、(c)3种情况中的候选簇首N₂、N₃、N₄规 定为候选簇首N的邻居节点，每个候选簇首都有其邻居节点集。公式(2)为 候选簇首N_i的邻居节点集合的定义：

N_i.NN_i＝{N_i|N_i∈{候选簇首}，且d(N_i,N_j)＜max(N_i.R_compete,N_j.R_compete)}   (2)

候选簇首向外广播一条包含自身ID，竞争半径R_compete以及自身能量E_n的消息，其他节点收到此消息后，通过公式(2)更新其邻居节点信息表。 每个候选簇首和其邻居节点比较剩余能量，剩余能量较大的候选簇首当选为 最终簇首，并立刻向其邻居节点发出自己是自己竞选成功成为簇首的消息， 收到此消息的邻居候选簇首退出竞争，成为普通节点，并从其他候选簇首的 邻居节点中移除。

在簇首竞选完成后，本发明一种无线传感器网络非均匀分簇节点调度方 法直接使最终簇首的邻居节点集成为自己的簇内成员，简化了传统的根据收 到簇首广播信息的强弱选择加入某个簇首的方法，避免了节点频繁的交互与 计算。簇形成后，簇首节点采用TDMA方式为簇中每个节点分配传输数据 的时间间隙最终完成整个网络的非均匀分簇。

步骤2、在簇内查找冗余节点

完成非均匀分簇后，在簇内查找冗余节点，并关闭冗余节点使其进入休 眠状态。在检测冗余节点时，为了更好地均衡节点的能耗，将簇内节点按能 量从小到大排序，并将节点的ID依次存储在名为clusterNodes的集合中，集 合中每个元素都存在一个index标记，在判断冗余节点时，簇首通过index+1 的大小给簇内节点分配时序，节点根据时序的大小在自己的时序内的进行判 断，即每次都从能量最小的节点开始判断。判断方法为：节点检测监测半径 R内是否存在4个或4个以上的非簇首节点，这些节点称为N_i的感知节点， 如果存在至少4个感知节点按逆时针顺序相邻节点间的夹角同时满足大于 60°小于120°，如图3所示的覆盖区域感知节点的分布图，则该节点冗余， 此时它的活动状态转为休眠状态，并发送一个休眠消息给其感知节点，避免 了相邻的两个节点同时休眠而出现的监测空洞现象，同时启动一个睡眠计时 器T_sleep保证在下一轮开始时处于活动状态。

步骤3、活动节点稳定工作

完成簇首的选举与冗余节点的调度休眠后，活动节点进入稳定工作阶段。 此阶段主要完成数据的采集和传输。在此阶段簇内普通节点的能量消耗主要 为发送数据消耗的能量，如公式(3)所示，其中，E_elec为电路消耗的能量， d为发送者与接收者的距离，当d<d₀时采用自由空间模型，发射功率呈d²衰减，当d>d₀或干扰较大时采用多路径衰减模型，发射功率呈d⁴衰减。ε_fs、 ε_mp分别为这两种模型中功率放大所消耗的能量比例系数。

$\left(\begin{array}{c}{E}_{\mathrm{Tx}}(l,d)=E_{\mathrm{Tx}-\mathrm{elec}}\left(l\right)+E_{\mathrm{Tx}-\mathrm{amp}}(l,d)\\ =\left(\begin{array}{c}{\mathrm{lE}}_{\mathrm{elec}}+{\mathrm{lϵ}}_{\mathrm{fs}}{d}^2,d<d_0\\ {\mathrm{lE}}_{\mathrm{elec}}+{\mathrm{lϵ}}_{\mathrm{mp}}{d}^4,d\ge d_0\end{array}\right)\end{array}\right)---\left(3\right)$

簇首消耗的能量如公式(4)所示。其中，S_i表示簇内处于工作状态的 普通节点数目。

E(CH_i)＝S_ikE_elec+(S_i+1)kE_DA+k(E_elec+ε_mpd⁴)   (4)

步骤4、簇内节点角色与状态的调整

首先冗余节点睡眠计时器T_sleep到达，冗余节点从睡眠状态转为工作状 态；其次簇内的所有节点向上一轮簇首发送带有自己ID和剩余能量的消息， 簇首根据节点的剩余能量进行排序，更新clusterNodes集合，选出能量最大 的节点担任本轮簇首，向其它节点公布新簇首的ID并向新簇首发送携带 clusterNodes信息的消息；然后在各个簇内通过判断冗余节点的方法判断节 点是否为冗余节点；如果某个节点确定为冗余节点，则立即将该节点转为睡 眠状态，如果某个节点确定不是冗余节点，则继续判断另一个节点，直到所 有节点查找完毕。

步骤5、步骤4的节点角色与状态调整完之后，循环执行步骤3、步骤4， 直至所有节点能量消耗完。

如图4所示，无线传感器网络仿真时间相同，本发明一种无线传感器网 络非均匀分簇节点调度方法对节点进行调度后的网络总能量远远大于其他 两种现有的经典方法的网络总能量。

如图5所示，无线传感器网络仿真时间相同，本发明一种无线传感器网 络非均匀分簇节点调度方法对节点进行调度后的存活节点数远远多于其他 两种现有的经典方法的节点存活数量。

本发明一种无线传感器网络非均匀分簇节点调度方法，将非均匀分簇与 冗余节点调度相结合，使得各节点的能量消耗比较均衡，且提高了能量利用 率，节约了网络总能量，有效的延长了网络的生命周期。