LEACH算法的改进分簇模型在无线传感器网络中的研究

牛潇，王忠庆

（中北大学，山西省 太原 030051）

0 引言

传感器网络具有异于MANET的独特性质，而传统MANET协议不适用于传感器网络，需要为传感器网络研究新的有效的路由算法。目前，在传感器网络的路由算法研究中，鉴于传感器网络中节点稠密分布、节点的能量、存储及数据处理能力十分有限的特性，一般采用基于分簇的方法来进行路由算法设计，以提高路由算法的性能。分簇算法作为路由协议的研究基础，对路由算法性能的优劣具有重要的影响。

1 LEACH算法及分析

LEACH算法是一种典型的层次路由算法。LEACH算法分别做了如下假设，主要设基站(BS)远离传感器网络节点并且是稳定的；传感器网络中的所有节点是同构的并且能量都受到限制；所有节点可以直接与基站通讯；节点都没有位置信息；簇头节点负责数据压缩汇聚以及与基站进行通讯；该算法主要通过随机选择簇首领，平均分担中继通信业务来实现节能。同时LEACH定义了“轮”(Round)的概念，针对每个节点n设定了一个阈值T(n)：

式(1)中p表示簇头节点占网络节点总数的百分比；r表示重新挑选簇头节点的轮数；G表示网络中最近1/p轮未当选簇头的节点的集合。并根据该阈值从侯选节点中挑选簇头，具体的步骤：

（1） 若传感器节点Ni∈G，则对于每个Ni独立运算(2.1)式，获得阈值T(n)。

（2） 若Ni不属于G，则根据(1)式，T(n)为零。

（3） Ni产生一个0~1之间的随机数RadomNum。

（4） 若T(n)＞RadomNum，则该节点当选为簇头，并广播当选消息。

（5） 其余节点选择加入某簇头所在的簇，形成稳定的拓扑结构。

（6） 稳定工作阶段。

（7） 每隔时间t，进行下一轮簇头选取，转Step1，重新选择簇头并成簇。

由以上步骤可知LEACH算法中的轮是指两次簇头选取之间的时间段，每一轮由初始化和稳定工作两个阶段组成。在初始化阶段，随机选择节点为簇首领，成为簇首领的节点向周围广播信息，其它节点根据接收到广播信息的强度来选择它所要加入的簇，并告知相应的簇首领，由于信息的强度和节点之间的距离是成正比的，因此，实际上各非簇头节点是选择距离自己地理距离最短的簇头所在的簇加入，并形成簇拓扑结构，如图1所示。

图1 成簇阶段图

无线传感器网络首先产生中心节点，其余节点加入距离自己最近的中心节点所在的簇，然后由中心节点直接和Sink节点进行通讯。在稳定工作阶段，节点持续采集监测数据，传送到簇头，由簇头对数据进行必要的融合处理之后，发送到终端节点。每轮工作周期结束后，重新选择簇头并重复前面的工作。

2 能量有效的分布式簇头选取算法

目前提出的很多路由算法都没有考虑传感器节点的实际分布情况。在上述的LEACH算法描述中，LEACH存在着以下的诸多问题。

(1)由于位于簇边缘位置的簇头通讯能耗远大于位于簇中心位置的簇头，因此将导致各簇头能耗不均衡，使某些簇头节点能量提前耗尽。

(2) LEACH没有考虑到传感器网络在进行部署的时候，节点分布密度对簇头能耗的影响。由此导致在传感器节点密集分布区域的簇头能耗巨大，而在传感器节点稀疏分布区域的簇头能耗较小，网络中各簇头的能耗极不均衡。

(3) 动态分簇引起网络拓扑结构频繁变换和大量广播通信，从而带来了额外的能量开销。

因此上述节点可能在某个局部分布非常的密集，而在其他的一些地方分布又非常稀疏。因此在这种情况下，简单的采用LEACH算法中的簇头选取机制，从而导致传感器网络生命周期的提前结束。首先提出了密度调节参数数学模型，然后将其与上一章提出的平均能耗调节参数结合起来，进而提出了能量有效的分布式簇头选取算法。

为了解决上面的问题，首先必须量化传感器网络的节点分布密度，为方便描述，做如下的假设：

(1) 传感器的通信半径R可以根据需求而改变，R0是基本通信半径，R≥ R0；

(2) Ni表示传感器网络中的第i个节点；

(3) 任意节点Ni坐标为（xNi, yNi）；

根据上面的假设，可知Dist(Ni，Nj)表示传感器网络中任意两点之间的直线距离，但是由于在分布式路由算法中节点的位置信息都无法获取，因此给出函数f(SignalIntension)，其中SignalIntension表示Ni节点接收到的，由Nj节点发出的信号的强度，这个值可以通过Ni节点的通讯模块获得，而f(SignalIntension)则表示接收信号的强度与收发信号的两节点之间距离的映射关系。对于任意节点Ni，若Dist(Ni，Nj)

根据以上分析提出一种能量有效的分布式簇头 选 取 算 法(EECHS，Energy Efficient Cluster Heads Selection)，该算法同时引入能量调节参数和密度调节参数，通过能量调节参数可以使得剩余能量越大且每轮平均工作能耗越小的节点有更多机会成为簇头。通过密度调节参数可以使得分布密度越大区域的节点有更多机会成为簇头。密度调节参数如下：

N(j)∈NeighborSet(i)。NeighborSet(i)是节点Ni的邻居节点集合。即Nodedensity(i)的值表示节点Ni的邻居节点的总数，也就是以N(i)为圆心，R0为半径的圆形区域的节点的个数。当Nodedensity(i)的值比较大时，意味着该节点所在区域节点分布的密度比较大。故，式(1)可修订为式(2)：

在式(3)中，Ecur表示节点当前的剩余能量，Eavg表示节点每轮的平均能耗。故，式(1)可修订为：

其中，rs为节点连续未当选为簇头的轮数，一旦节点当选簇头，则rs重置为0。

得出能量调节参数如式(6)：

故LEACH算法的式(5)可以改进为如式(7)所示：

显然，a=0，b=1时，式(7)将简化为式(9)：

即只在LEACH算法中进一步考虑剩余能量与工作能耗对网络生命周期的影响。

而当a=1，b=0时，式(9)将简化为式(10)：

即只在LEACH算法中进一步考虑节点分布密度对网络生命周期的影响。在稳定工作阶段，节点周期性的采集监测数据，并传送给簇首，进行必要的数据聚集和融合之后，将处理后的数据发送到Sink节点，这是一种减小通信数据流的有效工作模式。持续一段时间以后，整个网络进入下一轮工作周期，重新选择簇首。

LEACH可以在一定的程度上节省能量，与一般的协议相比，簇首的能量消耗非常高，各节点需要等概率地担任簇首才能使网络中所有节点比较均衡地消耗能量，有利于延长整个网络的生命周期，至少延长15%；其特点是分层和数据融合，分层有利于网络的扩展，数据融合能够减少通信量。但是它必须在每个簇首都可以和节点直接通信的基础上进行，因而有一定的局限性。

3 算法仿真实验

在输入要进行部署的传感器节点个数，区域大小，初始能量和调节参数等相关数据后，可以根据这些数据产生指定个数的节点，并且为每个节点随机分配一个坐标。通过仿真实验平台将生成节点分布的模拟图。因此采用EECHS算法在刚才模拟部署的传感器节点中选择簇头并成簇，实验平台将以直观的方式显示簇头选取的结果。最后实验平台还将记录每轮分簇过程中产生的簇头的坐标，并以列表的方式显示出来。具体的操作界面如图2所示。

图2 获取初始参数界面图

图2为仿真系统中获取部署节点参数数据的截图，取得相应的数据后即可对节点进行部署，其中能量调节参数和密度调节参数的取值范围为0~1之间。

图3为模拟100个节点部署的截图，其中每个小圈代表一个传感器节点。

图4为节点数为200个时，最后一轮分簇时选取的簇头截图，其中比较粗的小圈表示当选为簇头的节点，较细的圈表示普通节点。可通过选择左侧窗格中的分簇轮数来查看该轮产生的簇头节点的个数及各簇头的坐标，同时还可以查看总的分簇轮数，从而与采用LEACH算法时传感器网络的生命周期进行比较。

图3 节点部署模拟图

图4 簇头选取模拟图

4 实验结果

在实验过程中随机生成若干个点，代表随机分布的传感器，假定p=0.1，节点初始能量均为2000。当传感器节点个数固定为200，而部署区域大小分别取800×800，900×900，1000×1000，1100×1100，1200×1200时，得到的仿真实验结果如图5所示。

图5 部署区域大小变化时EECHS与LEACH算法实验对比图

在图5中，横坐标为正方形部署区域的边长，纵坐标为采用LEACH算法或EECHS算法时成簇的轮数(即网络的生命周期)。由图5可知，当节点数量不变，随部署区域面积的扩大，仅考虑节点的分布密度(a=0，b=1)、或仅考虑节点的剩余能量及其工作能耗(a=1，b=0)、或综合考虑节点的分布密度以及节点的剩余能量及其工作能耗(a=0.5，b=0.5)时，采用EECHS算法，传感器网络的生命周期均比采用LEACH算法时更长。特别的，当综合考虑节点的分布密度、节点的剩余能量及其工作能耗(a=0.5，b=0.5)时，传感器网络的生命周期延长了近150%。

若随机生成100，150，200……个点，而部署区域大小固定为1000×1000时，p=0.1，则仿真实验结果如图6所示。

图6 节点个数变化时EECHS与LEACH算法实验对比图

在图6中，横坐标为部署的节点个数，纵坐标为采用LEACH算法或EECHS算法时成簇的轮数(即网络的生命周期)。由图6知，当部署区域面积一定，随部署的节点数增加，仅考虑节点的分布密度(a=0，b=1)、或仅考虑节点的剩余能量及其工作能耗(a=1，b=0)、或综合考虑节点的分布密度以及节点的剩余能量及其工作能耗(a=0.5，b=0.5)时，采用EECHS算法，传感器网络的生命周期均比采用LEACH算法时更长。特别地，当综合考虑节点的分布密度、节点的剩余能量及其工作能耗(a=0.5，b=0.5)时，传感器网络的生命周期延长了近100%。

若随机生成100个点，而部署区域大小固定为1000 1000，p=0.1时，节点的初始能量分别取1000，1500，2000，2500，3000则仿真实验结果如图7所示。

在图7中，横坐标为节点的初始能量，纵坐标为采用LEACH算法或EECHS算法时成簇的轮数(即网络的生命周期)。由图7知，当部署区域面积及节点个数一定，随节点初始能量的增加，当仅考虑节点的分布密度(a=0，b=1)、或仅考虑节点的剩余能量及其工作能耗(a=1，b=0)、或综合考虑节点的分布密度以及节点的剩余能量及其工作能耗(a=0.5，b=0.5)时，采用EECHS算法，传感器网络的生命周期均比采用LEACH算法时更长。特别地，当综合考虑节点的分布密度、节点的剩余能量及其工作能耗(a=0.5，b=0.5)时，传感器网络的生命周期比采用LEACH算法时延长了近90%。

图7 初始能量变化时EECHS与LEACH算法实验对比图

[1] 史龙,王福豹,段渭军，等.无线传感器网络Range-Free 自身定位机制与算法[J].计算机工程与应用,2004,40（23）：127-130.

[2] B. Krishnamachari, D. Estrin, and S. Wicker. Modelling Data-Centric Routing in Wireless Sensor Networks[J]. In Proceedings of IEEE Infocom, 2002,102-111.

[3] 卢春枝.LU Chunzhi 无线传感器网络分簇路由协议分析[J].武汉理工大学学报:信息与管理工程版, 2008,30(1).

[4] 朱彬.廖俊国.罗芽松.使用部署知识的异构传感器网络有效成簇算法[J].计算机工程与应用,2009,45(13).

[5] 张新秀.张淼.张振川.无线传感器网络分簇路由改进算法及其性能[J].中国科技论文在线,2010,5(2).

[6] M. Chu, H. Haussecker,F. Zhao.Scalable informationdriven sensor querying and routing for ad hoc heterogeneous sensor networks[J].International Journal of High-Performance Computing Applications, 2002,16(3):348-356.

[7] 田艳霞,辛兵,吴克军.无线传感器网络的节能研究[J].兵工自动化，2006,25(3).

[8] 沈 波,张世永,钟亦平. 无线传感器网络分簇路由协议[J]. 软件学报, 2006,17(7): 1672-1681.