一种基于能量和区域密度的LEACH算法的改进

章成学，王 霄，杨 靖，张静静

（贵州大学 电气工程学院，贵阳550025）

0 引 言

无线传感器网络（Wireless Sensor Network，简称WSN）是应用于环境监测、工业监控和交通监控等诸多重要应用领域中，最新兴、最有前途和最领先的技术之一［1］。网络中的节点采集环境数据，通过单跳或者多跳的方式传输给基站。由于其节点能量较少，电池更换不便，节点的能耗对于WSN特别重要。如何更高效地利用有限的节点能量来延长网络的生存周期，是一个重要的设计目标。

分簇算法常常被用来优化WSN的能耗，低功率自适应集簇分层（LEACH）算法是现有比较经典的分簇路由算法之一，但是其会因为随机分簇而导致簇首能量消耗较大，从而导致部分节点过早死亡。有文献在研究了LEACH-C算法后，提出LEACH-m算法。通过引入剩余能量、节点覆盖率和半径内节点通信代价来选举簇首节点［2］；有文献提出了LEACH-ED算法，引入剩余能量因素和邻居节点数量因素来优化选举阈值，虽然延长了网络的生命周期，但是该算法未考虑稳定阶段的传输问题，也未引入节点与汇聚节点的距离因素［3］；有文献考虑了节点的剩余能量、节点到汇聚节点的距离和每轮运行结束后节点的剩余能量情况，优化了簇首节点的选取方法，提出了MEC-LEACH（Minimum Energy Consumption based LEACH）算法［4］。但是该算法在簇首节点的选举并未考虑网络结构和节点部署情况，可能出现在节点密集区域选择的簇首个数较少，稀疏区域选择的簇首个数较多的情况，造成部分节点能耗加剧，从而降低网络生存周期。

本文在以上研究基础上，对LEACH算法进行改进，改进的算法考虑了网络中的平均剩余能量，节点到汇聚节点的距离与网络不同区域节点密度3种情况，根据稳定传输的能量消耗求出最佳簇首个数，引入区域密度来调节不同疏密程度下的簇首个数，利用剩余能量和到汇聚节点距离的加权值来优化选举阈值，从而改善网络性能。

1 无线传感器网络和能量模型

1.1 无线传感器模型

无线传感器网络由不同功能的节点构成［5］。对于单跳网络，由终端节点和汇聚节点构成。而对于多跳网络，由终端、路由器、协调器，3种功能节点构成。在多跳网络中，传感器节点部署在一个目标区域中，传感器节点测得的信息（如温度、湿度、光照、压力、速度等）通过多跳的方式，经路由节点传送到汇聚节点［6］。节点部署在偏远地区，由于不便更换电池，为了延长网络的生存周期，如何尽可能保持节点的能耗均衡就是所有路由算法所追求的。

WSN网络模型的假设：

（1）WSN是由n个传感器节点和一个基站组成，节点随机分布在区域A＝M×M空间中；

（2）每个节点的结构相同，即有效感知范围，存储空间和通信的范围相同；

（.3）汇聚节点（s i nk节点）具有无限的能量和存储空间；

（4）每个节点始终都有自己的采集休眠周期，在各自指定的时间发送信息；

（5）所有节点和基站在部署后就不再移动；

（6）传感器节点在部署后都知晓部署位置。

其节点网络拓扑图如图1所示。

图1 节点网络拓扑图Fig.1 Node network topology

1.2 无线传感器网络的能耗模型

无线传感器网络的能耗主要来自2个方面，一个是节点接收数据的能耗，另一个是节点发送数据的能耗［7］。发送端发送Lbit数据的能耗公式（1）如下：

其中，E elec为发送电路的能耗，其取决于数字编码、调制、滤波和信号扩展等因素［8］；εfs和εamp分别为自由空间能耗和多径衰落能耗中的功率放大系数是划分空间模型的阈值。若节点间的距离d＜d0，则采用自由空间模型，若d＞d0则采用多径衰落模型。

节点接收Lbit消息的能耗如公式（2）所示：

簇首节点处理簇内成员发送过来的信息的能耗如公式（3）所示：

其中，E da为单位数据消息聚合处理器耗能大小。

2 LEACH算法的改进

2.1 LEACH算法介绍

LEACH算法是采用“轮”的思想进行操作的，每一轮分为分簇阶段和簇内成员数据稳定传输阶段［9］。在第一阶段通过让各个节点在［0，1］中生成一个随机数，若产生的随机数小于计算出的阈值T（n），则该节点当选为簇首节点，并广播成为簇首节点的消息，其它节点根据消息的RSSI来判断加入到哪一个簇，并发送加入到簇的消息请求到该簇首节点，簇首节点建立簇内成员表。分簇完成后，系统就会开始节点数据的传输，在开始此阶段前普通节点使用时分多址（TDMA）协议来进行数据的传输，簇首节点会将簇内成员的信息进行处理和发送给sink节点。每一轮都重复这个过程。在簇头的形成阶段，网络的阈值T（n）的表达式为式（4）［10］：

其中：p为预期的簇首节点占网络中节点的比例，r为网络现阶段运行的轮次；G为候选节点的集合，其为在1／p轮内没有当选簇首的传感器节点集合。在后续的传输阶段，节点根据划分好的时隙传输数据给各自的簇首节点，簇首节点融合数据后发送给si nk节点。

2.2 LEACH算法的不足

由于算法采用轮的思想，用产生随机数的方法使得所有的传感器节点成为簇首的概率都相等，但是随机产生的簇首可能自身的剩余能量较低，在担任簇首的周期内加剧剩余能量的消耗，加速节点的死亡。远离汇聚节点的节点和靠近汇聚节点的节点具有相同的概率当选簇首，这也会导致远离汇聚节点的节点过早的死亡。

2.3 改进的LEACH算法

本文在LEACH算法的基础上进行改进，首先利用在稳定传输阶段的网络能耗来求出此时的最佳簇首数，在稳定传输的阶段，网络的能耗主要有簇首数据收集，普通节点的采集，簇首节点将收集的数据融合后发送s i nk节点的能耗。所以可以得到公式（5）：

其中，n为现轮节点存活的数量，d toB S为上一轮簇首到s i nk节点的平均距离，其改进的p的公式（7）为：

其中，E re（i）为节点的剩余能量；E ave为节点的平均能耗，将节点部署的区域根据d0划分为q＝个相同面积的区域；ρre（i）为节点所在区域的密度；ρ为整个区域的节点密度。当某区域的密度小于某一阈值时，该节点不参与选取簇首节点，加入到离自身最近的簇。

针对LEACH没有考虑簇首节点剩余能量和簇首节点与s i nk节点的距离，本文构建一个阈值调节因子f来改进原来的阈值表达式，其具体公式（8）如下：

其中，d a vgnt os i nk为节点到s i nk节点的平均距离，d nt o si nk为该节点到si nk节点的距离。λ1和λ2的和为1，节点剩余能量较多时f越大，节点离s i nk节点较近时f也越大。f越大，所求的阈值也越大，节点有更大的概率当选簇首节点。改进的阈值表达式（9）为：

其簇的半径为公式（10）：

其中，节点在加入簇的算法流程，如图2所示。

在下一轮选举开始前，若有节点死亡，分2种情况进行处理，若死亡的节点是普通节点，即簇首节点在正常传输阶段没有收到该节点的数据，簇首节点进行查询。广播该节点死亡，并将该节点的信息删除。若死亡的是簇首节点，则簇内的普通节点在该节点的TDMA片段没有收到簇首节点的确定帧，则向s i nk节点发送簇首节点死亡的消息包，s i nk节点给簇内普通节点发送选举消息，簇内成员选出簇首节点。这种部分选举避免每次节点死亡后进行全局节点选举而增加的能量消耗。

S i nk节点记录每一轮簇首节点在此轮消耗的能量，若此轮消耗的能量小于上一轮消耗的能量，则下一轮不进行分簇，保持该簇首继续进行下一轮传输，直至略过的轮数大于r y u轮时，继续上述分簇过程。这样避免了该网络分配了最优簇首，因为频繁的分簇选出劣质的簇首节点，降低网络生命周期。

3 仿真结果分析

3.1 仿真环境和仿真参数的设定

为了验证本文改进算法的有效性，本文采用Matlab仿真平台对本文算法与MEC-LEACH算法进行了仿真对比。假设网络节点死亡个数超过80%后，导致网络失去大部分功能。在实验环境中，将100个节点随机的分布在范围为（0，0）和（100，100）内，一个汇聚节点（x m，y m）位于（50，125），λ1和λ2分别为0.6和0.4。具体的参数配置，见表1。

表1 实验参数Tab.1 Experimental parameter

3.2 结果分析

本文考虑各个算法的网络生命周期，网络中节点剩余能量，网络的总传输数据量几个方面，将改进算法与LEACH算法、MEC-LEACH算法进行比较。

网络节点死亡个数随时间（轮数）增大的变化状态如图3所示。LEACH算法首次出现死亡节点的周期为第632轮，MEC-LEACH算法首次出现死亡节点的周期为第911轮，而本文算法首次出现死亡节点的周期为第942轮。假定网络中节点死亡数量达到80%后，整个网络死亡。本文算法的网络生存周期大约为986轮，LEACH算法和MEC-LEACH算法的网络生存周期分别为921轮和936轮。这主要是因为LEACH算法随机产生不均匀簇，导致部分节点因为能量消耗较大而过早的死亡。MECLEACH算法由于考虑了剩余能量和与汇聚节点的距离，相比LEACH算法，网络的能量消耗比较均衡，但是没有考虑不同区域内的节点密度对簇首个数的影响。本文算法考虑到上述的3种因素，使网络生存周期相比MEC-LEACH算法有一定的提高。由于LEACH算法造成网络中节点消耗能量不均衡，使得部分节点率先死亡，其它节点可能保留较多的能量，因此在节点首次死亡后，后续节点是陆续逐个死亡，呈现较缓的上升曲线。MEC-LEACH算法和本文的算法由于在节点首次死亡前，网络能量消耗较为均衡，所以在节点首次死亡后，由于剩余的节点自身能量并不是很高，后续就出现了大量的节点死亡，呈现较陡的上升曲线。

图3 3种算法网络节点生存周期比较Fig.3 Comparison of network node life cycles of the three algorithms

网络系统总的能量消耗是衡量网络系统好坏的一个重要指标。3种不同算法的网络剩余能量的比较如图4所示，可以看出本算法在运行过程中较前2种算法有较高的剩余能量，这是因为本文算法动态调整簇首节点，使网络簇首数始终处于网络能量消耗较优的个数。并且考虑节点剩余能量，与汇聚节点距离以及节点密度等，动态调整选举阈值，使合适的节点当选簇首，减小网络能量消耗延长网络生存周期。

图4 网络剩余能量Fig.4 Residual energy of the network

网络中节点最小剩余能量，如图5所示。LEACH算法运行的网络中，每周期节点的剩余能量最小的值比另外2种算法低，这是因为在分簇时未考虑节点剩余能量，所以剩余能量较低的节点有几率继续当选簇首节点，加快其能量消耗。因为簇首节点随机选举，每轮周期节点消耗的能量不均衡。所以图5中LEACH算法的曲线波动较为明显。MECLEACH算法和本文算法都考虑了节点剩余能量，网络中节点的能耗比较均匀，因此网络中节点最小剩余能量相差不大。在节点首次死亡后，由于剩余的节点自身能量并不是很高，后续出现大量的节点死亡。

图5 网络中节点最小剩余能量Fig.5 Minimum residual energy of nodes in the network

LEACH算法中汇聚节点接收了大约87 155个数据包，MEC-LEACH算法中的汇聚节点接收了大约89 860个数据包，本文算法中的汇聚节点接收了大约96 870个数据包。

4 结束语

本文在LEACH算法的基础上，针对随机分簇和簇首能耗不均的问题，通过最小网络能耗来得到最优的簇首个数。在簇首节点选取上，考虑节点的剩余能量，与汇聚节点间的距离和节点所在区域密度，使剩余能量较高，距离汇聚节点较近，所在区域节点密度较大的节点更容易成为簇首节点。仿真实验表明，相比与LEACH算法和其它改进LEACH算法，本文的改进算法可以更有效的延长网络生存周期，降低和均衡网络能耗，提高网络汇聚节点接收的数据量，提高网络性能。