异构无线传感器网络的分簇算法

摘  要：針对LEACH算法缺乏对网络中能量异构性的考虑问题，为延长网络稳定周期，均衡节点能量消耗，提出一种改进的分簇算法。算法充分利用高级节点的能量优势，在簇头选举阶段，优先选举高级节点当选簇头，改善异构无线传感器网络中的簇头选举机制。仿真结果表明，改进后的算法均衡了网络能量消耗，延长了网络的稳定周期和一半节点死亡轮数。

关键词：异构;无线传感器网络;分簇;算法

中图分类号：TN929.5;TP212.9     文献标识码：A 文章编号：2096-4706（2020）15-0149-04

Abstract：LEACH lacks the consideration of energy heterogeneity in the network. In order to prolong the network stability period and balance the energy consumption of nodes，an improved clustering algorithm was proposed. The algorithm makes full use of the energy advantages of advanced nodes. In the cluster head election stage，it elects advanced nodes to be cluster head preferentially，which improves cluster head election mechanism in heterogeneous wireless sensor networks. The simulation results show that the improved algorithm balances energy consumption of network，prolongs stability period of network and also the death rounds of half nodes.

Keywords：heterogeneous;wireless sensor networks;cluster;algorithm

0  引  言

无线传感器网络（Wireless Sensor Networks，WSNs）是一门综合性的交叉学科，是物联网的重要组成部分[1]。无线传感器网络由大量的传感器节点组成。根据网络中节点是否相同，分为同构无线传感器网络和异构无线传感器网络[2]。无线传感器网络的异构性分为计算能力异构性、链路异构性、网络协议异构性、节点能量异构性[3]。当网络工作一段时间或部署新的节点后，各节点的能量不尽相同，因此，在大多数情况下，无线传感器网络普遍存在节点能量异构性。

在环境恶劣或危险的监测区域，基本是无人值守的，无线传感器网络节点一旦部署就无法补充能量或替换[4]。节点能量的受限性，使得如何更好地利用节点能量成为WSNs的首要设计目标。分簇路由算法能比平面路由算法更有效地利用能量，节省网络能耗[5]。

现有的经典分簇算法存在簇头能耗过高、选举机制不合理等问题，特别当网络中能量异构性强时，没有充分利用高级节点能量优势，使得网络出现能耗不均衡、稳定周期短等不良特性。针对以上问题，基于本校“无线传感器网络的节能分簇算法研究”项目，作者在LEACH（Low-Energy Adaptive Clustering Hierarchy）[6]算法基础上进行改进，提出一种适用于异构无线传感器网络的分簇算法。在前面轮数中，网络中能量异构性较强时，选择高级节点当选簇头;当能量异构性表现得不明显时，提高剩余能量高的节点当选簇头的几率，优化簇头选举机制，延长网络稳定周期。

1  相关研究

1.1  LEACH算法

LEACH算法是一个经典的分布式分簇路由算法。在LEACH算法中，工作周期按轮进行，每轮分为簇建立阶段和数据传输阶段[6]。在簇建立阶段，每个节点生成一个随机数，与设定的阈值作比较，决定自己是否成为簇头。在此阶段，整个网络划分为若干个分簇，每个分簇包含一个簇头节点和若干个簇内成员节点。簇内成员节点负责监测区域内的传感信息，发送至所在分簇的簇头节点。簇头节点融合各簇内成员节点的信息，发送至汇聚节点。簇内成员节点不直接与汇聚节点通信，而每轮中，簇头节点都与汇聚节点直接通信，因此簇头节点耗能较多。为了均衡簇头的能耗，LEACH算法采用随机选举簇头的方式，让所有节点以轮流的方式当选耗能较多的簇头节点。当序号n节点生成的随机数小于式（1）的阈值T（n）时，如果此节点在前面1/p轮中没有当选过簇头节点，则在此轮中当选为簇头节点。

簇头节点选举后，其余节点加入到最近的分簇中，簇头节点向其簇内节点发送TDMA调度表，簇内各节点根据TDMA调度表，向簇头节点发送数据。

1.2  异构分簇算法

针对LEACH算法假定节点初始能量相同，适用于同构无线传感器网络，国内外学者考虑节点能量异构性，提出了各种改进策略。文献[5]提出一种基于能量分布的非均匀分簇算法，簇头的选举中考虑节点剩余能量分布状况，采用非均匀的簇半径，形成大小非均匀的簇。文献[7]中考虑节点采集数据周期差异、初始能量的异构性和分布密度，结合模糊逻辑原理，采用竞争方式来选举最优簇头集合，成员节点采用类勾股定理的方法来选择加入分簇。文献[8]采用一种异构感知的分布式算法，针对异构无线传感器网络中不同能量级别的节点，根据能量来设置不同的簇头当选阈值，增大高级节点当选簇头的几率。文献[9]提出一种基于能量异构的多链路算法，根据高级节点能量和全网平均能量来确定簇头的阈值，采用层间多链路多跳传输和簇内单跳传输的方式。文献[10]提出一种多级异构的能量优化分簇算法，簇头的阈值函数中考虑节点位置和剩余能量，提高离汇聚节点近且剩余能量高的节点当选簇头几率。

為了均衡网络能量消耗，针对异构无线传感器网络中不同能量的节点，设置不同的当选簇头几率，才能有效利用网络中节点能量异构性，提高网络性能。

2  改进分簇算法

2.1  网络模型

根据异构无线传感器网络的特征，提出以下假设：

（1）网络是静态或近似静态的，节点随机部署后，位置不再变化。

（2）只有一个汇聚节点，位于网络上边界的中点处，能量充足，不受限制。

（3）节点可与汇聚节点通信，具有唯一的ID号，能感知自身的能量水平和位置信息。

（4）网络中有两种不同初始能量水平的节点，能量高的为高级节点，能量低的为普通节点，节点能量不可补充。

（5）无线信道具有对称性。

（6）所有节点的发射功率可控制。

2.2  能量消耗模型

本文采用无线电能量消耗模型，节点发送数据的能耗ETX与通信距离d、数据包大小L有关，如式（2）所示：

2.3  簇头选举与分簇

在簇头选举阶段，考虑普通节点和高级节点初始能量不一样，高级节点比普通节点高出能量倍数为α，为了充分利用网络中高级节点的能量优势，算法优先选举高级节点为簇头节点。

在前面轮数中，当轮数小于或等于轮数阈值r0时，高级节点比普通节点高出的能量较多，即网络中节点的能量异构性较强，选择高级节点为簇头节点，承担耗能较多通信任务;普通节点不当选簇头节点。

由于高级节点在前面轮数中当选了簇头，能量消耗比普通节点多。随着轮数增大，网络工作一段时间后，当轮数大于轮数阈值r0时，此时高级节点与普通节点的剩余能量差异缩小，即网络中节点的能量异构性减弱时，对两种节点设置不同的当选簇头几率。普通节点当选簇头几率pnrm为式（4），高级节点当选簇头几率padv为式（5）：

2.4  算法流程图

改进后算法流程图如图1所示。

3  仿真结果分析

3.1  仿真环境

为了验证算法的可用性和可靠性，本文采用MATLAB R2014a软件进行仿真分析。在M×M m2的正方形区域内，随机部署N个节点，其中，高级节点的比例为m，其能量为E0（1+α），其余为普通节点，其能量为E0，汇聚节点位于正方形区域上边界中点处，当M=100 m时，汇聚节点坐标为（50，100）。当M=100 m时，各节点分布如图2所示，其中，▲为汇聚节点，□为高级节点，○为普通节点。

仿真实验中采用的网络场景参数设置如表1所示。

3.2  仿真结果

改进后算法和LEACH算法的网络生存时间对比如图3所示。从网络开始运行到第一个节点死亡的时间间隔，称为网络稳定周期，在此时间内，所有节点存活，网络能稳定持续地监测环境信息和采集数据，网络处于稳定的工作阶段。从图中可知，LEACH算法的稳定周期624轮，改进后算法的稳定周期为772轮，对比LEACH算法，延长了23.72%。从网络开始运行到一半节点死亡的时间间隔内，出现部分节点死亡，但比例不高，网络仍能工作。图中LEACH算法一半节点死亡的轮数为732轮，改进后算法一半节点死亡的轮数为874轮，对比LEACH算法，延长了19.40%。改进后算法的稳定周期和一半节点死亡的轮数均比LEACH算法更优。

改进后算法和LEACH算法向汇聚节点发送数据量对比如图4所示。LEACH算法的传输量为11 037 L，改进后算法的传输量为23 704 L，约是LEACH算法的2.15倍。改进后的算法优先选举剩余能量较多的高级节点当选簇头节点，在前面轮数中，网络能量异构性较强，高级节点高出普通节点的能量较多，选举的簇头数量比LEACH算法较多，因此，改进后的算法向汇聚节点发送数据量较多。而LEACH算法不考虑节点能量异构性，把高级节点和普通节点视作一样的节点，具有相同的当选簇头几率。随着网络工作时间推移，在轮数为732轮以后，由于LEACH算法中出现过半节点死亡，网络剩余节点数量越来越少，LEACH算法向汇聚节点发送数据量明显减少。

4  结  论

本文在异构无线传感器网络环境下，基于LEACH算法，提出了一种改进的分簇算法。该算法考虑高级节点和普通节点的能量不同，通过优先选举高级节点当选簇头，充分利用节点的能量异构性，提高节点能量利用率。仿真结果表明，改进后的算法均衡了网络能量消耗，延长了网络的稳定周期和一半节点死亡轮数，网络性能更佳，算法可适用于能量异构网络。

参考文献：

[1] 马飒飒，张磊，夏明飞，等.无线传感器网络概论 [M].北京：人民邮电出版社，2015.

[2] 杨柳.基于分簇结构的无线传感器网络节能路由协议研究 [D].重庆：重庆大学，2016.

[3] 李继荣.异构无线传感器网络覆盖问题研究 [D].济南：山东大学，2010.

[4] 徐晶晶，张欣慧，许必宵，等.无线传感器网络分簇算法综述 [J].计算机科学，2017，44（2）：31-37.

[5] 张春花，刘方爱，申志远，等.一种新的异构无线传感器网络分簇算法 [J].传感器与微系统，2013，32（6）：143-146.

[6] HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

[7] 徐世武.异构无线传感网络最优簇首选择机制 [J].计算机系统应用，2016，25（1）：187-191.

[8] SMARAGDAKIS G，MATTA I，BESTAVROS A. SEP：a stable election protocol for clustered heterogeneous wireless sensor networks [C].In：Second International Workshop on Sensor and Actor Network Protocols and Applications，2004：223-233.

[9] 王卫星，黄虹，孙道宗，等.基于能量异构的WSN多链路算法 [J].华南理工大学学报（自然科学版），2015，43（9）：74-80.

[10] 胡中栋，伍华林.多级异构无线传感器网络能量优化分簇算法 [J].江西理工大学学报，2017，38（1）：73-78.

作者简介：伍敏君（1986—），女，汉族，广东中山人，讲师，硕士，研究方向：无线传感器网络技术、计算机应用技术。