基于K-means聚类的WSN能耗均衡路由算法

张海燕，刘 虹

(北京林业大学信息学院，北京100083)

无线传感器网络(Wireless Sensor Network，WSN)是由众多具有通信和计算能力的传感器节点，以多跳通信、自组织方式形成的网络［1］。节点间协同工作，实时监测、感知和采集网络分布区域内监测对象的信息，并通过一跳或多跳的方式将这些感兴趣的数据路由至汇聚节点。

目前无线传感器网络已经成为研究热点之一，随着对无线传感器网络的深入研究和广泛应用，它将深入到人类生活的各个领域(如军事、工业生产、环境监测、医疗监护等)。由于传感器节点的电源能量、计算能力和通信能力都非常有限，所以节能路由协议的设计，对无线传感器网络来说非常重要［2］。如何高效使用节点的能量，均衡整个网络的能耗，延长整个网络的生命周期是无线传感器网络研究的重点。研究表明，与平面路由协议相比，分层路由协议能有效将整个网络的能量负载平均分配到每个传感器节点中，从而达到降低网络能源消耗、提高网络整体生存时间的目的，其中 LEACH［3］(Low Energy Adaptive Clustering Hierarchy)是经典的分层路由协议。

LEACH协议虽然有很多优点，但其自身还存在一些问题，因此对LEACH协议的改进已成为一个研究的重点与热点。文献［4］中提出一种能量均衡自适应分簇算法，在簇头的选举过程中考虑到了节点的剩余能量，然而，该算法还存在簇头分布不均匀、所有簇头直接与基站通信、远离基站的簇头能量损耗快的问题。文献［5］提出一种基于PSO的无线传感器网络双簇头分簇算法，该算法利用主簇头完成数据的收集与融合，用副簇头进行数据传输，达到了平衡能量负载的目的，但该算法也存在簇头分布不均匀的问题。本文根据K-means算法及无线传感器网络分簇路由算法的特点，提出了一种新的基于K-means聚类的WSN能耗均衡路由算法(KBECRA)，将K-means算法应用于WSN分簇路由中，在簇内则根据不同的适应值选择主簇头和副簇头。KBECRA算法使得簇结构更加均匀，同时避免了簇头分布过于集中，或分散在边缘地区，从而避免簇头节点能量消耗过快加速簇的死亡。在簇内选择主副簇头分工合作，可将能耗分散开，从而延缓簇的死亡时间。KBECRA算法较好地平衡了网络的能量负载，达到了延长网络生存周期的目的。

1 LEACH协议研究

1.1 LEACH协议概述

LEACH协议是无线传感器网络最早提出的分簇路由协议。LEACH协议的基本思想是通过随机循环的选举过程生成簇头节点，并基于接收信号的强度来形成簇，以簇头节点作为路由器负责将簇内节点采集到的信息传输到基站节点;定期轮换簇头节点以保证每个节点公平负担网络能耗、提高网络整体生存时间［6］。

LEACH协议的工作过程是周期性的，它采用了“轮”的概念，每轮分为簇的建立阶段和稳定数据传输阶段。

在簇的建立阶段，每个节点生成一个0－1之间的随机数，并计算阈值，如果所生成的随机数小于阈值，则这个节点被选为簇头。簇头节点选定后，向网络中广播自己是簇头的消息，收到簇头广播的非簇头节点根据信号的强度，选择信号最大的簇头节点加入，并发送请求加入的数据包。簇形成后，簇头创造TDMA时序并通知簇内成员节点。

LEACH算法中阈值的计算公式为:

其中，p表示期望的簇头节点占网络节点总数的百分比;r表示当前轮数;G表示网络中最近1/p轮未当选簇头的节点集合。

在稳定数据传输阶段，簇内的成员节点按照TDMA时序，在自己的时间槽内，将采集的数据发送给簇头。簇头节点将收到的数据进行融合处理，然后将融合后的数据直接发送给基站。

1.2 能量模型

在LEACH协议中，使用的能量模型是第一顺序无线电能量模型(First Order Radio Model)［7］。传感器节点发送k-bit字节所消耗的能量为:

传感器节点接收k-bit字节所消耗的能量为:

其中，Emp是传输功效，Eelec是发送电路和接收电路消耗的能量，由于实际相差很小，将二者简化为相等。β是由无线电信道决定的常量，d是信号传输距离。当传输距离小于预先定义的一个阈值时，采用自由空间信道模型，令β=2;当传输距离大于这个预先定义的阈值时，使用多路衰减信道模型，令β=4。

1.3 LEACH协议分析

LEACH协议拥有很多优良的性质，其中最主要的优点有:①LEACH协议采用层次结构，路径的选择和路由信息的存储都变得非常简单，节点不需要存储大量的路由信息，大大减少了路由控制信息的数量;②簇头的选择采用自适应随机选取机制，使各个节点成为簇头的机会均等，进一步使得整个网络的负载相对比较均衡;③LEACH协议中簇的自组织形成使得整个网络具有良好的扩展性。

虽然LEACH协议拥有很多优点，但其本身还存在一些问题，如:①LEACH协议在簇头的选择时没有考虑到节点的能量，每次选出的簇头节点不一定是最合适的节点;②LEACH协议中簇头节点既负责接收簇内成员节点的数据，又负责数据的融合，以及将数据传输给基站，所以簇头节点的开销较大;③LEACH协议无法保证簇头节点在空间上均匀分布，簇头节点可能集中在某一个小区域内或者分布在边缘，造成成员节点与簇头节点进行数据传输时消耗过多能量;④簇头与基站之间采用单跳通信，根据能量消耗模型，当距离较大时则能量消耗很大;⑤LEACH协议假设所有节点都能与基站进行直接通信，这使得LEACH协议不能应用于较大区域。

2 基于K-means聚类的WSN能耗均衡路由算法

本文针对LEACH协议存在的在簇头的选择时没有考虑到节点的能量、簇头节点的能耗较大、簇头节点可能集中在某一个小区域内或者分布在边缘、造成成员节点与簇头节点进行数据传输时消耗过多能量等缺点，对其进行改进，从而提出KBECRA算法。新算法在LEACH算法的基础上，将K-means聚类算法利用到分簇中，在簇内则根据不同的适应值选择主簇头和副簇头。其中，主簇头负责收集并融合簇内节点的数据，然后将融合后的数据发送给副簇头，副簇头将从主簇头接收到的数据发送给基站。这样可以在一定程度上将簇头的能耗分散开，做到能耗均衡从而延长网络的生命周期。

2.1 网络模型

本文采用文献［3］和［8，10］的传感器网络模型，此模型具有以下特点:①基站位置固定，在传感器网络区域之外;基站的计算资源和能量不受限制，能覆盖整个网络;②节点能量有限，初始能量水平相同;节点位置固定或移动范围和速度很小;③节点能控制传输功率，具有全局唯一的表示ID;④节点以固定速率监测环境，定期上报监测数据。

2.2 能量模型

新算法采用与经典LEACH协议一样的能量模型，即第一顺序无线电能量模型。

2.3 算法思想

基于K-means［11］聚类的WSN能耗均衡路由算法是在LEACH协议的基础上提出的，同样存在周期性轮，每轮分为两部分:簇的建立阶段和稳定数据传输阶段。

2.3.1 簇建立阶段

在簇的建立阶段，节点首先将自己的位置信息和能量信息发送给基站，之后基站利用K-means算法，将区域内所有节点进行聚类分析。利用 K-means算法进行聚类分析的工作过程如下:①首先从m个节点中任选k个节点作为初始聚类中心;②对于其他非聚类中心，则根据与这些聚类中心的相似度，分别将它们分配给与其最相似的聚类中心;③计算每个聚类中所有节点的均值;④不断重复①至③步骤直到标准测度函数开始收敛为止，最终每个聚类代表一个簇。

分簇工作的流程图如图1所示。

由于经典LEACH协议中簇首节点是根据随机数产生的，没有考虑节点的剩余能量和位置信息，存在一定的局限性，而且簇首节点的能效开销较大，可能造成网络的过早死亡。KBECRA算法针对上述缺陷进行了改进，提出在簇内首先根据阈值选择出辅助簇头，再根据不同的适应值选择主簇头和副簇头。辅助簇头负责告知簇内节点主、副簇头的id号，主簇头将接收到的数据进行融合处理，并传输给副簇头，副簇头负责与基站进行数据传输。其中选择主簇头的适应值一方面考虑了节点与簇内其他节点之间的距离，因为传输距离与能量的消耗密切相关，另一方面考虑了节点的剩余能量，因为主簇头在接收其他节点发送的数据时要消耗能量。在选择副簇头时则考虑的是节点的能量和节点与基站之间的距离。

图1 分簇阶段的流程图

基于以上描述，参考参考文献［5］和［12］，提出在选择主、副簇头时的适应函数f1和f2如下:

其中，g1表示节点ni的能量;g2表示簇内节点到主簇头节点平均距离的倒数;m表示簇内节点的个数;CH表示主簇头;d(ni，CH)表示节点ni到主簇头节点的距离;g3表示副簇头节点到基站距离的倒数;BS表示基站;d(ni，BS)表示节点ni到基站节点的距离。g1的定义是为了选择的主副簇头具有较多的能量，g2的定义是为了使主簇头到簇内节点之间的平均距离最小，g3的定义则是为了使副簇头到基站节点的距离最小。通过α和β可以调节g1和g2两个因素在适应值函数f1中所占的比重，通过ε和δ可以调节g1和g3两个因素在适应值函数f2中所占的比重。

辅助簇头将主簇头和副簇头节点的信息发布给簇内所有节点，并为所有节点分配TDMA时隙。

2.3.2 稳定数据传输阶段

在稳定数据传输阶段，簇内的成员节点按照TDMA时序，在自己的时间槽内，将数据发送给主簇头。主簇头将收到的数据进行融合处理，然后将融合后的数据发送给副簇头。副簇头主要负责将数据转发给基站。

3 仿真与结果分析

本文采用MATLAB对LEACH协议，以及对KBECRA算法进行仿真。根据网络以及能量模型，设定仿真参数如下:200个传感器节点随机分布在200 m×200 m的网络中，基站位于(200，250)。传感器节点的初始能量为0.5 J，Eelec=50 nJ/bit，Efs=10 pJ/bit/m2，Emp=0.001 3 pJ/bit/m4，EDA=5 nJ/bit，数据包的长度为 4 000 bit，控制包长度为100 bit。α=0.4，β=0.6，ε=0.4，δ=0.6。仿真结果分别如图2～图4所示。

图2为两种算法在某一轮的成簇结构图。其中图2(a)为KBECRA算法的簇结构图和主副簇头分布图，图2(b)为LEACH算法的簇结构图和簇头分布图，使用不同的颜色和形状表示不同的簇，(a)中*代表主簇头，向右三角形代表副簇头，(b)中*代表簇头。由图2可得，LEACH协议分簇不均匀，有的簇节点过多，这会加剧该簇内簇头节点的死亡;同时LEACH协议中簇头可能集中于某一区域或边缘地区。而KBECRA算法比LEACH协议分簇均匀，簇头分布也更加均匀，避免了簇头集中在某一区域或边缘地区的情况。

图2 两种算法的簇结构图

图3所示是存活节点图，反映了随着时间关系网络中存活节点的个数。由图3可以看出，LEACH协议在第271轮开始出现节点死亡，KBECRA在第513轮出现节点死亡;LEACH协议在第650轮有50%的节点死亡，KBECRA算法在第807轮有50%的节点死亡;LEACH协议在第820轮有90%的节点死亡，KBECRA算法在第1100轮有90%的节点死亡。

图3 网络中剩余的存活节点数

表1对两种算法的第1个节点死亡时间，一半节点死亡时间，以及90%节点死亡时间进行了统计。从表1中可以看出，KBECRA算法第1个节点的死亡时间是LEACH算法的1.89倍，一半节点死亡时间是LEACH算法的1.24倍，90%节点的死亡时间是LEACH协议的1.34倍。这表明KBECRA算法使能量消耗更加均匀地分布在所有节点中，避免了单个节点因能量消耗过大而过早死亡，可延长网络的生命周期。

表1 两种算法的节点生存时间统计

图4是网络的总能耗图，它反映了在两种不同算法下，网络的总能量消耗随时间的变化关系。由图4可得，网络中200个节点的总能量为100 J，LEACH在第271轮开始出现节点死亡，消耗的总能量是 47.42 J，KBECRA 算法消耗的是 36.15 J;LEACH在第650轮时出现50%节点死亡，消耗的总能量是 92.61 J，KBECRA算法消耗的是 78 J;LEACH在第768轮时出现80%节点死亡，消耗的总能量是98.47 J，KBECRA 算法消耗的是87.5 J。

图4 网络的总能量消耗

表2是两种算法的能耗统计表。由表2可以看出，在第271轮KBECRA算法的能耗比LEACH算法的能耗减少了11.27 J，减少的百分比是23.8%;在第650轮KBECRA算法的能耗比LEACH算法的能耗减少了14.6 J，减少的百分比是 15.8%;在第 768 轮 KBECRA算法的能耗比LEACH算法的能耗减少了10.97 J，减少的百分比是11.2%。通过以上数据表明，与经典LEACH协议相比，本文采用的算法有效减少了网络的总体能量消耗，网络性能得到了很大的提高。

表2 两种算法的能耗统计

与LEACH协议相比，KBECRA可以延长网络生命周期，减少网络总能耗，是因为该算法将K-means聚类算法利用到分簇中，使得分簇更加均匀，避免了簇头分布不均匀或集中分布在某一区域的情况，进而减少了簇内节点与簇头进行数据传输时的能耗，同时避免了簇头节点的能耗过高。在簇内则采用了主、副簇头的通信方式，这种方式在一定程度上将簇头的能耗分散开，可以做到能耗均衡，从而延长网络的生命周期。

4 结论

本文提出基于K-means聚类的WSN能耗均衡路由算法KBECRA，算法通过K-means聚类算法进行分簇，在簇内则根据不同的适应值选择主副簇头，较好地平衡了网络的能量负载，从而达到了延长网络生命周期的效果。通过仿真实验证明它具有较好的性能，但是本文主要着眼于能耗均衡和延长网络生命周期，今后工作的重点是研究算法的延迟以及安全方面，设计具有安全性的能量均衡路由协议。

［1］ 王殊，阎毓杰，胡富平，等.无线传感器网络的理论及应用［M］.北京:北京航空航天大学出版社，2007.

［2］ 何延杰，李腊元，邢明彦.WSN中一种能量均衡的分簇路由协议的设计［J］.传感技术学报，2009，22(10):1513－1514.

［3］ Heinzelman W R.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proceedings of the 33rd Hawaii International Conference On System Sciences.［S.1.］:IEEE Computer Society，2000.

［4］ 杜玉红，张晓敏，蔡成闻.无线传感器网络能耗均衡自适应分簇算法［J］.传感技术学报，2007，20(7):1616－1619.

［5］ 韩冬雪，张瑞华，刘丹华.基于PSO的无线传感器网络双簇头分簇算法［J］.计算机工程，2010，36(10):100－102.

［6］ 乐世成，王培康.无线传感器网络中的节能路由算法［J］.计算机工程，2008，34(7):113－114，117.

［7］ 祝华君.基于LEACH的无线传感器网络路由协议研究［D］.武汉:武汉理工大学，2009.

［8］ KuIik J，Heinzelman W R，Balakrishnan H.Negotiation-Based Protocols for Disseminating Information in Wireless Sensor Networks［J］.Wireless Net-works，2002，8:169－85.

［9］ Intanagonwiwat C，Govindan R，Estrin D.Directed Diffusion.A Scalable and Robust Communication Paradigm for Sensor Networks［C］//Proc.6th Annual Int’I.Conf.Mobile Com.and Net，Aug.2000，56－67.

［10］ Lindsey S，Raghavendra C，Sivalingam K M.Data Gathering Algorithms in Sensor Networks using Energy Metrics［J］.IEEE Trans.Parallel and Distribute.Sys，Sept.2002，13(9):924－35.

［11］ Wei Peng，David J Edwards.K-Means Like Minimum Mean Distance Algorithm for Wireless Sensor Networks［C］//2010 2nd International Conference on Computer Engineering and Technology.2010 IEEE:120－124.

［12］ Abdul Latiff N M，Tsimenidis C C，Sharif B S.Energy-Aware Clustering for Wireless Sensor Networks Using Particle Swarm Optimization［C］//The 18th Annual IEEE International Symposium on Personal，Indoor and Mobile Radio Communications.2007.