基于分区能耗均衡的自适应分簇算法

刘玮+冷震北

摘要：针对无线传感网络（WSN）中节点非均匀分布出现的能量空洞问题，提出了一种基于分区及剩余能耗和距离均衡的自适应分簇方法。在该方法中，按照一定的方法对网络按区域进行适度规模的分簇，并利用剩余能量和距离基站距离来选择簇首，最后由簇首将簇内信息汇到基战，最后通过仿真实验，结果显示该方法提高了网络的寿命，数据传输吞吐率得到了进一步的提升。

关键词：分簇； 簇首； 剩余能量

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2017）25-0200-03

无线传感器网络（wireless sensor network， WSN）是由大量的传感器节点以无线通信方式组成的一个多跳自组织网络，主要功能用于获取周围环境监控的数据，用于工业监控，现代农业，军事侦察，智能楼宇等多个场合。由于WSN中节点分散，节点体积比较小，携带能量有限，一般都是由有限能量的电池来供应。因此如何利用传感网节点有限的能量延长网络寿命，增大网络数据吞吐量一直是WSN目前急需解决的问题[1]。

一般情况下，传感器网络中的节点都是随机分布在待检测区域中的，网络节点之间自组织成网络，采用多跳的方式将采集到的数据发送到基站。当其中某个节点因为能耗殆尽失效或者其他原因不能工作时，即成为死亡节点。节点的死亡可能会影响数据的采集或者信息的传输通信，这会导致出现能量空洞的现象。

避免出现能量空洞，延长传感器网路生存周期一直是目前WSN继续解决的问题。解决无线网络中能量空洞问题最关键的方法是均衡网络节点能耗。因此对传感器网络路由协议进行研究，进行规模适度的分簇和合理地选择簇头是研究重点。

低功耗自适应集簇分层型算法（Low Energy Adaptive Clustering Hierarchy，LEACH）[2]是最早的分簇路由协议，后面的很多算法都是基于此算法进行改进和研究的。该协议通过随机选取簇首，平均分担能量负载，延长了网络的生命周期。但是该算法存在簇首分布随机，节点能量利用率不高的问题。文献[3]针对传统分层路由算法存在分簇不均匀，簇头选举不合理以及数据传输方式简单的问题，提出了基于K-means++的无线传感网改进分簇算法LEACH-KPP，该算法首先在成簇阶段采用K-means++算法实现均匀分簇，然后在簇头选举阶段改用簇头选举函数选取簇头，组后在数据融合传输阶段根据簇头与基站，簇头与簇头之间根据距离选择单跳和多跳混合的方式传输数据。文献[4]针对LEACH协议中簇头随机选取造成网络能耗过快的问题，提出了LEACH-E（LEACH Based on Energy）算法，该算法在簇头选取时引入了节点剩余能量以及网络的平均能量，使节点能量比网络平均能量高的节点优先充当簇头，该算法在普通节点的入簇包内携带节点的能量信息和能耗速度。通过簇头计算簇的平均能量，并将该信息转发给基站以计算获取网络平均能量，从而选举剩余能量较多地节点优先当选为簇头，降低剩余能量低的节点当选为簇头的概率。文献[5]中提出了对非均匀分簇路由协议的改进算法，通过在簇头竞争阶段设置阈值，计算非均匀分簇的竞争半径，改进簇头的选择策略和簇间路由选择。改进后的阈值综合考虑了节点的剩余能量，到汇聚节点的距离，以及邻居节点的个数和能量消耗速率，簇头选择更加合理，簇头的分布更加均匀，有效的控制了成簇的规模。文献[6]针对无线传感网中节点能耗不均的问题，提出了一种基于环的能耗均衡分簇路由算法，该算法对监测区域基于环进行分簇，在靠近基站的热区内划定数据汇聚区，汇聚区内节点不分簇，降低分簇及簇内的通信消耗，對汇聚区外其他环的簇个数进行优化以均衡消耗。提出新的最优路径选择策略，寻找整体最优路径，从而进一步降低能耗，延长网络生存周期。文献[7]提出了距离均衡的自组织分簇算法（DBSOCA），该算法通过簇内节点依据计算自身与基站的距离来竞选簇首，并确保基站与簇首及簇首间的传输能够保持一定的距离。通过平均传输距离来避免簇首因传输距离的不同而造成的能耗不均衡。文献[8]提出额基于动态簇半径的非均匀分簇算法（UCDCR），该算法在成簇组建阶段，对网络进行区域划分，不同区域的候选簇首通过簇竞争半径来构建大小不同的簇。使簇首随着网络的形态来改变簇竞争半径，从而为数据转发降低网络能耗，延长网络生命周期。以上算法通过不同的方法在一定程度上解决额簇头数目不明确，簇头分布不均衡的问题，使WSNs的生命周期得到了延长。为了进一步优化WSNs分簇，簇首选举，数据传输，克服LEACH算法的缺陷，本文提出了一种基于分区能耗均衡的自适应分簇路由算法。该算法从成簇，簇头选举，簇头的确立以及数据中继传输等三方面进行优化。

1 网络模型和能耗模型

1.1 网络模型

按照节点的功能，将节点分为三类： 基站，簇首，普通节点：

1） 基站固定于WSN监测区域的中心位置，能量无限；其余节点初始位置随机分布，能量有限且不能随机补充。

2） WSN的异构节点的初始能量和能量消耗速率不同，同构节点的初始能量和消耗速率相同，节点可以感知自身的能量剩余和计算能量消耗速率。

3） 所有节点在基站部署之后都是静止的。

4） 所有节点ID唯一，基站能够感知节点坐标。

5） 节点能调整通信功率，保证不同节点在通信范围内能够相互通信。

6） 网络按轮运行，节点定期上报检测数据。

1.2 能量消耗模型

此外，对网络中其他能量的消耗做如下假设：（1）节点感知环境信息的能量消耗为[Es]；（2）簇首消耗[EDA ]用于数据融合。

2 算法原理

本文提出的WSN分簇算法按轮依次进行，每一轮包括优化分簇，簇建立，数据传输三个阶段。算法流程图如下所示。endprint

2.1 自适应分簇

在传感器网络中，获得最优的簇首数或者适度规模分簇是有效均衡网络，延长网络生命周期的重要因素。基于自适应分簇方法是根据网络监控区域获得适度分簇的一个有效方法。

初始化时，根据网络监控的区域的大小，根据一定的原则将监控区域等分成M（M>=1）个子区域，每个子区域成为一簇。监测区域中心为能量无限大，位置固定的基站。周边区域子节点用不同颜色标注，节点颜色越深代表的该节点能量越大。自适性分簇算法的操作方法如下：

[Nr]为监控区域第r-1轮分区前存活的节点的数目；[Mr-1]为第r-1轮划分的子区域的总数目；[ω1]，[ω2]为划分权重系数。

若[Nm]>[Nmax] ，即节点的区域内密度过大，需要继续进一步将该区域继续细化；若[Nm]<[Nmin]，即 该区域内节点密度太小，会作为子区域自动加入周围的分簇区域。直到所有的分区的子节点数目满足[Nmin][≤][Nm][≤][Nmax]为止。通过对传感器网络进行自适应分区可以获得规模适度的分簇，使的网络成簇规模合理化[3]。

2.2 簇首的选取

传统的分簇方法LEACH在簇头选取时，未考虑节点剩余能量信息，会造成少量能量少的节点担任簇头。算法的思想为簇头选取时，每个节点随机生成一个0～1的随机数，如果节点生成的随机数小于[Tn]，则当选为该轮的簇头。传统的算法的公式为：

式中：n为监测区域节点中数， P为节点成为簇头的概率，r为节点随机生成的0-1的数字，G为当前轮的签1/p轮为担任过簇头的节点。

改进算法在簇头选举阶段综合考虑节点的剩余能量，节点与基站之间的距离以及与上一簇之间的距离避免较少的剩余能量或者与基站距离较远的基站担任簇头。改进的簇头算法尽量选择剩余能量多的节点，在能量相同的情况下选择距离基站近的节点作为簇头，且簇头尽量到周边节点的平均距离最短。这样避免了既保证簇首到基站之间传输耗费的能量最少，同时也保证簇内各成员节点到簇首的平均距离最短，最均匀。改进的簇头选举函数[Tn]可以修改为：

式中：Ei_rest为簇内的剩余能量，Eavg为簇内节点剩余能量的平均值，dB 为簇内节点距离基站的距离，ds_avg为簇内节点距离基站的平均距离，di 为 簇内节点距离上一轮簇头的距离，di_avg 为 簇内节点距离上一轮簇头的距离。加入[Ei_restEavg]可以选择剩余能量较多地节点优先被选中作为簇头，加入[1-dsds_avg]可以使距离较基站最近的节点优先被选中担任簇头，加入[1-didi_avg]可以选中簇内距离所有簇中距离其它节点平均距离最近的节点优先被选中簇头[3]。

成簇过程完成后，簇首已经获得了各个簇成员的信息。这些信息通过计算距离剩余能量，基站距离，和簇内其他成员平均距离等信息排列成一个选择表，这个选择表作为下一轮选择的的重要依据，并且被广播到簇内的各个成员。下一轮选择开始后，重新将数据信息提交给簇首，计算并产生新的分簇和簇首。

2.3 数据传输

在数据传输阶段，根据簇首与基站的距离远近可将传输分为单跳传输和多跳传输。数据传输的过程中，簇首对簇内数据进行融合后，将数据发送给基站。当簇首到基站的距离小于直接传输距离d0时，簇首直接与基站进行通信；当距离大于d0时，采用多跳方式将数据送到基站。多跳传输时，每个簇首可利用文献[8]中路由权重计算方法，选择适当的路径将数据转发到基站。

3 仿真验证与分析

3.1 仿真参数设置

实验的模拟场景设置如下：假设有100个静态节点随机部署在检测区域，对每个节点的位置进行标定。实验区域为一个100m*100m的平面正方形区域。各探测节点的坐标已知。其中基站位于方形检测区域的中心位置，能量无穷大，其余节点随机分布在监控区域内。

实验采用Matlab仿真，在实验过程中，如果某些节点的剩余能量低于初始能量的10%時即认为是失效节点，同时，假如网络中能够使用的节点不足10%时，网络已经失去了有效性，认为网络已经死亡，此时的吞吐量为最终的有效吞吐量。

3.2 网络能量的均衡性

根据图3可知，相比传统的LEACH算法，基于分区能耗均衡的分簇路由算法使的网络的负载均衡性更好，节点剩余能量下降速度更慢，从而有效地克服了网络空洞的现象。

3.3 网络的生命周期

由图4可看出，该基于分区能耗均衡的分簇路由算法由于均衡了每个节点的能耗，延长了网络周期。

图5显示由于算法在采用了单挑路由和多跳路由算法的基础上，通过计算路由权重选择合适的路径传输数据，明显提高了网络的吞吐率，说明网络的数据通信效率更高。

4 结束语

本文提出的基于分区能耗均衡的自适应分簇算法，通过均衡分区的自适应分簇，簇内基于剩余能量和通讯距离的簇首选举措施，可以延长WSN网络的生存周期和网络吞吐量。实验结果表明，在节点均衡分布的情况下，在一定范围里，该算法与传统的LEACH算法相比，具有明显的优势，下一步还需要进一步对算法的参数进行优化，如分区节点数目最大和最小阈值，参数w1，w2的取值等，从而进一步提高算法的效率。

参考文献：

[1] 王晓东.无线传感器网络节能算法研究[D].杭州：浙江大学控制科学与工程学院，2007.

[2] 肖玮，涂亚庆 基于等级的无线传感网自适应分簇算法[J].计算机应用，2017，37（6）.

[3] 余秀雅，刘东平，杨军 基于K-means++的无线传感网分簇算法研究[J].计算机应用研究，2017，34（1）.

[4] 韩广辉，张丽翠，基于LEACH协议的无线传感网能效的分簇算法[J].吉林大学学报，2017，35（1）.

[5] 王磊，谢弯弯 ，刘志中 ，齐俊艳 非均匀分簇路由协议改进算法[J].计算机科学，2017，44（2）.

[6] 孙超，彭力，唐波.基于环的能耗均衡分簇路由算法[J].计算机应用研究，2017，35（6）.

[7] 吴中华.距离均衡的自组之无线传感网络分簇算法[J].重庆师范大学学报，2017，34（1）.

[8] 熊炼，叶建光，刘晓彤. 基于动态簇半径的非均匀分簇算法[J].无线电通信技术，2017，43（1）.endprint