摘 要： 根据LEACH协议的特点和局限性对其进行了改进，提出了一种LEACH_EH（LEACH EAHANCE）算法。它使用K_MEANS算法对簇进行一次性分簇，之后结合节点到簇内质心距离与节点自身剩余能量选举出簇头。它将簇形成的顺序由先簇头后成簇变为先成簇后簇头，形成一次分簇多次选举簇头的模式。通过MATLAB进行仿真，实验结果表明，改进后的算法比原来的协议在节点能量均衡方面有了较大的提升，延长了网络生存周期。

　关键词：WSN路由协议；LEACH；K_MEANS算法；MATLAB仿真

　　当前，无线传感器由于技术的发展得到更加广泛的应用，针对无线传感器网络（WSN）[1]的研究也越来越多，无线传感器网络路由协议[2]成为了一个重点研究对象。按照时间先出现了Flooding算法、SPIN算法、SAR算法和定向扩散（Directed Diffusion）等平面路由算法，其后又研究出了LEACH算法、TEEN算法、HEED算法[3]及PEGASIS算法等层次路由算法。LEACH算法由于其不同于以往路由算法的指导思想成为以后层次路由算法设计时的参考标准，针对LEACH算法的自身局限性进行改进也成为了一个研究热点。参考文献[4]提出了一种休眠簇头的算法，它一次性选出所需要的工作簇头和休眠簇头，并且只分一次簇，减少了LEACH协议中多次选举簇头和分簇带来的能量耗损。参考文献[5]提出了LEACH-C算法，它提出各个节点把自身的剩余能量和位置信息发送给Sink节点，由Sink节点进行分簇。参考文献[6]在簇头选取中加入剩余能量，并且结合平面拓扑、层次拓扑和基于位置拓扑的优点形成混合型拓扑类型，修改LEACH协议中单轮成簇为双轮成簇。参考文献[7]提出了一种名为LEACH_SD（LELACH_Sensoring Denomina-tion）的协议，它提出了基于网络覆盖的路由生成思想。参考文献[8]基于节点的剩余能量和位置对LEACH协议进行了改进，将选簇过程分为临时簇头选择和正式簇头，把传感器节点的节点剩余能量值和几何平均位置作为选簇的重要因素，在此基础上选出区域内最佳簇头。参考文献[9]提出根据节点剩余能量进行筛选，剩余节点能量较低的暂时不进行采样，以此减少参加采样节点数量，其次对簇形成阶段不正常的节点进行放弃处理。以上改进方法在特定情况下都能够延长网络的生命周期。

　　本文结合LEACH协议的特点，提出改变原来LEACH协议先选择簇头后进行分簇的顺序，而是先进行均匀分簇，而后进行簇头选举的过程。

1 LEACH协议

　　1.1 算法介绍

　　LEACH算法是由MIT的Chandrakasan等人为无线传感器网络专门设计的低功耗自适应聚类路由算法（Low Energy Adaptive Clustering Hierachy）。它的基本思想是：将协议的运行过程分成一个个轮（round），每一轮由簇形成阶段和簇的稳定工作阶段组成[8]。在簇的形成阶段，每一个节点都会生成一个随机数，然后与一阈值T（n）进行比较，阈值T（n）计算式为：

　　T（n）=，n∈G0 ，n?埸G（1）

　　其中，P为期望的簇头节点的百分比，即每个节点成为簇头节点的概率；r为当前轮数；G是最近1/P轮为当选簇头的节点集合。

　　如果该节点的随机数小于阈值T（n），则该节点就当选为簇头节点，同时广播自己成为节点的控制帧，所有当选簇头的节点广播完控制帧后，未当选的普通节点根据收到的控制帧信号强度选择加入到相应的簇头，发送给该簇头加入控制帧。该过程结束后，簇头节点整理自己接收到的加入控制帧，采用TDMA的方式为相应的簇内节点分配发送时隙，簇就形成了。

　　在簇稳定工作阶段，簇内节点将收集到的数据在自己的时隙内发送给簇头节点，簇头节点将收集到簇内节点的数据进行处理、融合，然后将融合后的数据发送给Sink节点，由Sink节点再发送给远程数据处理中心进行处理。这个过程重复进行数次，之后，再进行簇的形成，以此往复，不断循环。

　　LEACH协议在簇形成阶段，每个节点都会轮流地成为簇头节点，前面几轮已经当选为簇头的节点，在后面的若干轮都无法再担任簇头，这就使得所有节点都能够作为簇头来分担作为簇头时能量消耗较大的问题。使得能量消耗能够均衡地分摊到各个节点，各个节点的能量消耗就能够更加一致，有效延长了网络的生存周期。

　　1.2 LEACH算法的不足

　　由于在簇头节点形成过程中，节点当选为簇头的概率是一样的。这样，可能会出现节点剩余能量较多的节点每次都在比较靠后的轮次当选簇头节点，而节点剩余能量较少的节点在比较靠前的轮次当选簇头，一些节点的能量消耗就会过大。同时，如果一轮中选举出的簇头节点距离不合适，势必会造成簇头节点内的簇内节点数目不均衡；或者是簇内节点到簇头节点的距离过大，或者是簇头节点过多或者过少。

　　上述几种情况都会加重个别簇头节点的负担，不利于均衡节点能耗。本文提出了一种基于K_MEANS算法的先分簇，再选举簇头的改进算法。该算法首先随机选取几个簇头，然后使用K_MEANS算法进行迭代，找出最优或者部分最优的分簇形式，接着根据节点剩余能量和距离该簇质心的距离选举出簇头，之后进入簇的稳定工作阶段。

　　LEACH算法是先选举簇头再形成簇，这种成簇过程带有很大的随机性，直接导致簇头距离不合适，各个簇内节点数目不均衡。改进算法则使用与之完全相反的方式生成簇。首先通过K_MEANS算法进行分簇，它通过几次迭代过程即可把拓扑区域内的节点尽可能地均分成不同的簇。各个簇内节点距离近，簇间较远。这样簇内节点到选举出的簇头节点的距离自然就大大缩短，之后，选择簇头节点，簇头节点的选择兼顾到了节点的剩余能量和到簇内质心的距离。能量较大同时到簇内质心的距离较小的节点优先当选为簇头节点，这样可以保证簇头节点在本轮数据传输完成之后属于能量与其他簇内节点剩余能量不至于有过大差距。改进算法之后同样进入到稳定的数据传输阶段。传输一段时间后，重新进行簇头的选择，如此循环下去。

　　2 LEACH_EH算法

　　2.1 K_MEANS算法

　　K-MEANS算法，也称为K-平均或K-均值算法，它是一种得到广泛使用的聚类算法。其主要思想是通过迭代过程把数据集划为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类类内紧凑，类间独立。

　　K_MEANS算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相识度越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。

　　本实验中K_MEANS算法先是随机的选取任意k个节点作为初始簇头，每个簇头代表一个簇。剩余的每个节点，根据其到各个簇头的距离加入到最近的簇头。各个簇进行质心计算，接着所有节点根据到k个质心的距离选择加入到最近的质心，之后进行新簇质心的计算。如果新的质心相对于原来的质心位置不变或者变化足够小，认为分簇已经收敛，分簇结束；否则继续迭代。

　　2.2 具体步骤

　　2.2.1 簇的形成

　　（1）从普通节点中选择出几个节点作为临时簇头（进行分簇用），簇头数目根据参考文献[9]中可知，最优簇头数为节点总数的3%~7%，这里选择5%。

　　（2）其他节点依据到各个临时簇头节点的距离选择加入距离最短的临时簇头，形成初始簇。

　　（3）计算各个簇质心坐标（按簇内节点坐标平均值计算），公式为：

　　xk=，yk=（2）

　　其中，k为质心编号，sk为编号k的质心拥有的节点数目。

　　（4）各个节点根据到各个质心的距离选择最近的质心加入其簇，若形成的各个簇已经收敛，跳到步骤（5）；否则跳到步骤（3），进行迭代计算。公式为：

　　其中，i为节点的编号，k为质心的编号。

　　（5）最终的分簇结果形成。

　　结果实验验证，该分簇方法能够在把随机生成的节点很好地分配在不同的簇内，图1为两组不同的实验场景生成的分簇结果，左边是生成的初始簇，右边是使用K_MEANS算法得出的簇。

　　2.2.2 簇头选举

　　分簇形成以后，接着进行簇的簇头选择。由于簇头节点的能量消耗较大，同时能量消耗与传输距离也有很大的关系。因此，对于每个节点产生一个判断值C（n）。其计算式为：

　　C（n）=?琢×+（1-?琢）×（4）

　　其中，E（n）表示节点的剩余能量，Eaver是节点n所属簇内节点剩余能量的均值，D（n）是节点n到簇质心的距离，使用欧式距离，Daver是簇内所有节点到该簇质心距离的均值，?琢是影响因子，用来权衡节点剩余能量与节点到簇质心的距离对簇头选举的影响。各个簇内C（n）值最大的节点当选为簇头节点，每一轮选择一次簇头。

　　2.2.3 数据传输

　　数据传输阶段与LEACH协议一样，簇内节点按照分配的时隙在相应时间内发送采集到的数据给簇头节点，簇内节点发送完成后，簇头节点对收到的数据进行数据融合，然后发送给Sink节点，这个过程进行数次，之后再进行簇头选举。

　　LEACH_ED算法的分簇和选举簇头流程图如图2所示。

　　3 实验仿真以及结果

　　本文采用的无线通信模型为一阶无线通信模型。根据这种模型，传感器节点传输k bit数据所消耗的能量为：

　　En（k，d）=k×Eelec+k×εamp×d2，d≤d0k×Eelec+k×famp×d4，d>d0（5）

　　节点接收k bit数据所消耗的能量为：

　　En（k）=k×Eelec（6）

　　其中，d0=，节点发送数据时根据距离选择不同的传输方式。当传输距离小于等于d0时，使用自由传输模式，能够有效地节省能耗；当传输距离大于d0时，使用多路径衰减模式进行数据传输。节点接收数据的能耗只与包的大小有关。

　　本文使用MATLAB进行仿真实验，设置节点数目为100个，拓扑的区域大小为100 m×100 m，Sink节点位于拓扑的中心（50，50）。节点完全随机地分布在区域内，节点位置固定。节点的初始能量为1 J，其他主要参数如表1所示。

　　定义当节点能耗小于0时节点死亡，死亡节点不再发送信息，也不再接收任何消息，与外界失去联系。

　　假定整个网络的绝对有效时间定义为从仿真开始到第一个节点死亡经历的时间，因为此时网络处于完全正常的工作状态下，各个传感器节点都能够发送采集到的数据给Sink节点。

　　相对有效时间定义为仿真开始到死亡节点为20%时经历的时间。此时，一部分节点已经死亡，但是，由于死亡的节点分布较为分散，仍然能够采集到死亡节点管辖区域的信息附近的其他节点，所以整个网络的信息采集仍然能够覆盖到全部区域的可能性还是比较大。

　　定义当节点死亡达到50%的时候，从开始到现在经历的时间为可信有效时间。此时，节点死亡过半，对于死亡节点所处的具体区域也不从得知，因为此时无法判断剩余活着的节点是否仍然能够覆盖全部区域。可信有效时间仅作为参考使用。

　　图3为本实验采用的实验场景。图4是LEACH-ED算法与LEACH算法的各轮次下剩余节点的存活数对比图。

　　图4中，LEACH算法的绝对有效时间为265轮，而LEACH_ED算法的绝对有效时间为350轮，绝对有效时间提高了32%。LEACH算法的相对有效时间大约为330轮，LEACH_ED算法的相对有效时间大约为370轮，相对有效时间提高了12%。LEACH算法的参考有效时间大致与新协议相同。从图4中还能发现，LEACH算法的绝对有效时间和相对有效时间的间距较大，大概经历了110轮，而改进后的LEACH_ED算法却只有20轮。这20轮中，节点大量死亡，死亡的频度远大于同期的LEACH协议。

　　是到各轮次时所有节点消耗的总能量图。改进后的协议每一轮所消耗的总能量与LEACH协议基本相同。但是结合图4可知，节点性能方面上却有很大的提高，原因在于改进后的协议主要是在均衡节点能耗上有较大性能提升。各个节点的能量损耗大致相同，所以节点的剩余能量也就基本一致。图4中的LEACH_ED协议从绝对有效时间到相对有效时间的间隔轮数较小，就是因为此时节点剩余能量都比较小同时大致相同，一个节点死亡同时表明其他节点的剩余能量也快耗尽，所以才会出现节点集中死亡的现象。

　　节点的剩余能量均衡程度可以用信息熵来表示。信息熵是一个数学上颇为抽象的概念，在这里不妨把信息熵理解成某种特定信息的出现概率（离散随机事件的出现概率）。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。信息熵也可以说是系统有序化程度的一个度量。信息熵可以用来衡量一模型中各种事件出现概率的均衡程度，信息熵越大，节点剩余能量越均衡，节点的能量消耗越平均。信息熵的计算式为：

　　H（x）=E[l（xi）]=E[log（2，1/p（xi））]=-p（xi）log（2，p（xi）（i=1，2，…，n）（7）

　　信息熵越大，表明模型中各个事件的概率越接近相同，当每个事件的概率均相同时，信息熵达到最大。

　　本实验中，p（xi）抽象为各轮次后节点剩余能量与总剩余能量的比值，即：

　　p（xi）=（8）

　　实验选取第50、100、150、200、250、300、350轮来比较两种协议不同轮次下的信息熵。图为对比图。

　　从图中可以看出LEACH_ED和LEACH在前4个轮次中信息熵都趋于相同，不过可以明显看出LEACH_ED协议在前4个轮次中信息熵要比LEACH协议略大；同时随着轮次的增加，LEACH_ED协议和LEACH协议的信息熵的差值越来越大。LEACH协议信息熵的变化趋势非常明显。这说明开始时新协议和LEACH协议剩余能量都较为平均；随着轮数的增加，LEACH协议中各节点的能耗就有所偏差，一些节点的剩余能耗明显要比其他的节点少。这导致LEACH协议中绝对有效时间时的轮次要比改进后协议的早大约85轮，相对有效时间早大约50轮，均衡节点能量消耗起到了至关重要的作用。

　　本文从LEACH协议的特点入手，分析了LEACH协议的优缺点。然后从均衡节点能耗上对LEACH协议进行了改进。改进后的LEACH_ED算法采用先分簇，再选举簇头节点，最后进行数据传输的顺序。使用聚类算法K_MEANS对节点进行一次性分簇，得到比较好的分簇效果，然后结合节点的剩余能量和到簇质心的位置选出簇头节点，之后进行数据传输。实验结果验证了改进算法的效果，在每轮总能耗与LEACH协议大致相同的情况下取得了很好的能耗均衡，且能在很长一段时间上保持同等的均衡效果。

　　参考文献

　　[1] AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al. Wireless sensor networks： a survey[J]. Computer networks， 2002，38（4）：393-422.

　　[2] YOUNIS O， FAHMY S. A hybrid， energy efficient， distributed clustering approach for ad-hoc sensor networks[J].IEEE Transactions On Mibile Computing， 2004，3（4）：660-669.

　　[3] AL-KARAKI J N， KAMAL A E. Routing techniques in wireless sensor networks： a survey[J]. Wireless Communications，IEEE，2004，11（6）：6-28.

　　[4] 兰慎，彭刚，李发飞.基于休眠簇头的LEACH算法研究[J].微型机与应用，2012，31（21）：65-70.

　　[5] Fan Xiangning， Song Yulin. Improvement on LEACH protocol of wireless sensor Network[C]. Internal Conference on Sensor Technologies and Applitcations，2007：260-264.

　　[6] 陈庆章，赵小敏，陈晓莹.提高无线传感器网络能效的双轮成簇协议设计[J].软件学报，2010，21（11）：2933-2943.

　　[7] Lu Jun， SUDA T. Coverage-aware self-scheduling in sensor networks[C]. 2003 IEEE 18th Annual Workshop on Computer Communications， 2003， CCW 2003，2003：117-123.

　　[8] 李年琼，黄宏光，李鹏.基于剩余能量和位置的LEACH改进算法[J].计算机工程.2012，38（24）：70-73.

　　[9] 王慧斌，俞弦，徐立中，等.无线传感器网路LEACH协议的改进[C].无线传感器网及网络信息处理技术-2006年通信与信号处理年会论文集，2006.

　　[10] HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. An application_specific protocol architecture for wireless microsensor network[J]. IEEE Transactions on Wireless Com-munication，2002，1（4）：660-670.

　　[11] 郭前岗，周德详，周西峰.LEACH路由协议最优簇头数计算方法[J].微型机与应用，2012，32（3）：61-66.