基于能量和距离的WSN自适应分簇算法

孙增友，周　池

(东北电力大学 信息工程学院，吉林 吉林 132012)



基于能量和距离的WSN自适应分簇算法

孙增友，周池

(东北电力大学 信息工程学院，吉林 吉林 132012)

摘要：无线传感器网络中节点的能量有限且难以补充，为了提高网络节点的能量利用率，延长网络生命周期。在LEACH算法分簇结构的不足的基础上，提出一种自适应的最优簇首数计算方式，综合考虑传感器节点的能量及距离，对阈值公式T(n)进行改进。经仿真实验分析，本文提出的算法较LEACH算法节点存活率更高，网络生命周期显著延长。

关键词：无线传感器网络；LEACH；分簇

为了最大化的延长无线传感器网络(Wireless Sensor Network ，WSN)的生命周期，学者们设计了多种层次路由协议以充分利用网络中各节点的能量[1-2]。

经典LEACH 算法将网络中的节点分为多个簇，簇内节点以相同的概率随机地被选为簇首，在一定程度上，这种算法能防止某个节点损耗过高，均衡了网络整体能耗。但该算法不能保证每轮的分簇数量达到最佳。同时，由于簇首的选择未考虑节点的能量和地理位置信息，簇首可能会集中分布于监测区域的某一处，造成个别簇首覆盖的监测区域面积较大，负担的成员节点数量较多，能量消耗较大而过早死亡。文献[3]提出了一种新型的自适应最佳分簇算法，选取能量较大的节点作为簇首，从而保护剩余能量少的节点，该算法在一定程度上提升了网络性能，但是算法未考虑节点位置，小范围区域内可能当选大量簇首，使簇首分布不均匀，易形成网络空洞。因此，本文在考虑网络中各节点的能量和位置的基础上，通过阈值T(n)的重新定义对LEACH协议的簇首选择过程进行优化，实现网络整体功耗的降低，从而提高网络生命周期[3]。

1WSN系统模型和能量模型

1.1WSN系统模型

本文考虑簇首节点通过单跳转发的方式与基站直接通信，采用文献[3]的系统模型，用一个无向加权图G表示其网络拓扑结构G={V，E}，V为传感器网络中所有节点的集合V={v1v2…vi…vn}。

1.2能耗模型

本文采用文献[4]的能耗模型，当发送和接收lbit数据时，能耗公式如下：

(1)

(2)

Etotal=Etx+Erx，

(3)

其中，d为源节点到目的节点的距离；n为信道衰减指数，取值范围为[2,5]；εfs为单位放大功率；εmp为多径衰落模型的单位放大功率；Eelec为发送或接收单位bit数据的能耗[4]。

2分簇路由算法

2.1确定最佳簇首数

(4)

(5)

因此，可计算一个簇的总能耗为：

(6)

推出整个网络能耗为：

(7)

为了使网络总能耗最小，则

(8)

(9)

dto-CH节点与簇头的距离，为

(10)

则式(8)即：

(11)

得

(12)

由式(12)可知，最优簇首数由网络规模和网络节点数决定。然而，在实际的网络运行过程中，随着网络中节点能量的耗尽，存活节点数在不断减少，节点数目也在不断变化，因此本文用当前节点数代替网络初始节点数，提出自适应最优簇首数计算公式，即：

(13)

通过能量消耗与节点位置求得的最优簇头数目，结合了网络节点数的动态变化过程，与leach原有的随机簇首数相比，更有助于降低无线传感器网络的整体能耗。

2.2簇首选取

LEACH算法进行簇首选取时，每轮开始时节点产生一个[0，1]的随机数，如果这个数小于阈值T(n)，节点当选簇首[6]

(14)

但是，LEACH算法在选取簇首时未考虑节点能量及节点间距离等因素，一些能量较低的节点也有可能被选为簇首，容易导致该类节点负载过重而过早死亡[7-8]。文献[2]提出的AOCH算法，把剩余能量最多的节点选为簇首，却没有考虑其到基站的距离。因此，本文在进行簇首选择时，综合考虑节点的剩余能量和节点与基站的距离关系，构造了一个调节函数f，使剩余能量较多且距离基站较近的节点优先竞争簇头。

f=f1×f2，

(15)

(16)

(17)

(18)

改进后的T(n)除了考虑当前节点的剩余能量外，还考虑了节点与基站之间的距离，尽可能的选择与基站距离较近的节点作为簇首。在单跳路由网络中，即降低了传输延迟，也减少了簇首的发送能耗，不至于使其能耗开销过大。为了更进一步约束被选节点的能量，我们定义簇首还需满足下式[9-10]：

(19)

3实验与性能分析

3.1实验环境与参数设定

本实验是在Matlab环境下进行仿真，100个网络节点随机均匀分布在100×100的方形监测区域内，基站位于监测区域外，坐标为(50，150)，如图1。仿真参数设定如表1。

图1　网络节点分布

图2　LEACH与本文算法簇首数量图

3.2结果分析

我们首先选取了50轮内LEACH和本文算法的簇首数量进行比较，如图2所示，本文算法簇首数波动范围较小，与LEACH算法相比，簇首数量更稳定。因此，保证了网络成簇数量的均衡性，避免分簇数量过多或过少而引起的能量波动及能量分布不均匀现象。

图3a为网络节点存活数比较图。随着网络运行，节点能量不断消耗，网络节点数不断减少。由图可知，LEACH算法在运行至500轮左右时最先开始出现第一个死亡节点，文献[2]提出的AOCH算法推迟了第一个节点死亡时间，而本文提出的算法在运行至650轮左右时才出现，节点死亡时间明显延迟。当运行到800轮时，LEACH算法的网络节点几乎全部死亡，而本文所采用的算法仍有12%左右的节点存活，节点存活时间明显增加，有效的延长了网络生命周期。

为了进一步对本文算法的效果进行验证，图3b对网络总能耗进行了仿真分析，如图可知，随着轮数的增长，网络能耗逐渐增加，从0-1200轮的时间中，任意轮的LEACH能耗最快，在800轮左右时，由于节点数量几乎全部死亡，能量耗尽。AOCH算法考虑了节点剩余能耗，在一定程度上减少了网络总体能耗，但是由于未考虑节点位置，因此较本文提出的算法耗能快。

图3　a节点存活数，b总能量消耗

4结论

本文改进了LEACH算法分簇时未考虑能量和节点位置信息的缺点，综合考虑网络监测区域的面积和节点数等因素，通过自适应调整的方式确定最优簇首数。在选举簇首时，考虑存活节点的剩余能量和位置信息，通过函数f对簇首选择阈值T(n)进行调整。经仿真验证，本文提出的新算法能有效提高节点存活率，延长网络生命周期。

参考文献

[1]李建坡，钟鑫鑫，徐纯.无线传感器网络动态节点定位算法综述[J].东北电力大学学报，2015，35(1)：52-58.

[2]李建坡，钟鑫鑫，徐纯.无线传感器网络静态节点定位算法综述[J].东北电力大学学报，2015，35(2)：73-82.

[3]过文亮，施惠昌，周一飞.一种新型的自适应最佳簇首分簇算法[J].微计算机信息，2009，25(2):183-184+201.

[4]Pratyay Kuila ，Prasanta KJana，Energy efficient clustering and routing algorithms for wireless sensor networks:Particle swarm optimization approach[J].Engineering Applications of Artificial Intelligence，2014 (33):127-140.

[5]廖鹰，齐欢，王晓红等.基于距离和分布的无线传感器网络分簇算法[J].华中科技大学学报(自然科学版)，2012，6(40):29-33.

[6]赵小敏，毛科技，王正莉等.基于能量和距离的分簇式WSN路由协议设计[J].解放军理工大学学报(自然科学版)，2012，8(13):394-397.

[7]王林，赵绍英.无线传感器网络LEACH路由协议的研究与改进[J].计算机工程与应用，2012，48(2):80-82.

[8]潘霞，于宏毅，张霞.一种基于LEACH的能耗均衡分君算法[J].电路与系统学报，2012，17(1)：75-80.

[9]张磊，陈曙.一个新的基于能量和距离的传感器网络协议[J].计算机应用，2008，5(28):1117-1119.

[10] 胡君，王雷，林亚平.传感器网络中一种基于节点平均能耗的分布式簇头选取算法[J].计算机应用，2007，27(12)：2979-2981.

Adaptive Clustering Algorithm in WSN Based on Energy and Distance

SUN Zeng-you，ZHOU Chi

(School of Information Engineering，Northeast Dianli University，Jilin Jilin 132012)

Abstract：The energy of nodes in wireless sensor networks is limited and it is difficult to add.In order to improve the energy utilization of the nodes，and prolonging the lifetime of the network..This paper for the shorts of cluster structure in LEACH algorithm，proposed a calculation of an adaptive optimal number of cluster heads，considering the sensor node energy and the distance for clustering.The threshold formula T(n) was improved.Through simulation experiments，the proposed algorithm is more than the LEACH algorithm in node survival rate，the lifetime of the network is significantly prolonged.

Key words：Wireless Sensor Network；LEACH；Cluster

中图分类号：TP212.9

文献标识码：A

文章编号：1005-2992(2016)01-0082-05

作者简介：孙增友(1963-)，男，吉林省吉林市人，东北电力大学信息工程学院高级工程师，硕士生导师，主要研究方向：无线通信、电力系统通信.

收稿日期：2015-06-05