无线传感器网络LEACH协议的二进制粒子群改进算法*

曹欲晓，徐金宝，徐梦溪，彭焕峰

（南京工程学院 计算机工程学院，江苏 南京211167）

无线传感器网络LEACH协议的二进制粒子群改进算法*

曹欲晓，徐金宝，徐梦溪，彭焕峰

（南京工程学院 计算机工程学院，江苏 南京211167）

针对无线传感器网络LEACH协议分簇时，能量较低的节点可能会成为簇头，簇头在簇中的位置未必最优的问题，提出了一种基于二进制粒子群的LEACH协议优化算法。首先在成簇过程中使簇的个数最优，然后应用二进制粒子群算法在每个簇中选择最优簇头。仿真证明，二进制粒子群优化的LEACH协议较原始LEACH协议有效降低了总的能量消耗，延长了网络的生命期。

无线传感器网络；分簇；LEACH协议；二进制粒子群算法；粒子编码

0 引言

LEACH协议[1]是无线传感器网络（Wireless Sensor Network,WSN）经典的分层路由协议，能有效地延长网络生存时间。但是由于LEACH协议采用由节点生成随机数的方法选择簇头并成簇，使得每次成簇的数目相差较大，簇头在簇中的位置未必最优，且对簇头的剩余能量也未加考虑，因此LEACH协议还有可改进之处。

文献[2]在簇头选举时考虑了节点的能量因素，选择剩余能量大的节点作簇头，但未对簇的数目和簇头位置进行优化。文献[3]在选择簇头时，考虑了候选簇头及簇内节点的能量和距离因素，但对簇的数目和簇的大小未进行控制。文献[4]引入了簇门限数和合并极小簇的方法，对簇的规模和个数进行了优化，但对簇头在簇中的位置未作考虑。

针对LEACH协议的不足，本文基于LEACH提出了一种新的 BPSO-LEACH（Binary Particle Swarm Optimization LEACH）算法。BPSO-LEACH首先在分簇过程中控制簇的数量，使簇的个数最优以减小全网的能量消耗，然后对网络中的每一个簇应用二进制粒子群算法重新选择簇头，使簇内能量消耗之和最小且节点间能耗均衡。

1 LEACH协议的不足

由文献[1-4]可知，LEACH协议存在以下不足：

(1)每一轮分簇时，簇的数目可能差别较大。如果簇数太多，会有较多的簇头向基站传输数据，使全网的能耗过大；如果簇数太少，节点可能会离簇头较远，向簇头传输数据时会因消耗过多能量而导致较早死亡。

(2)选举簇头时，由随机数和阈值来决定一个节点是否成为簇头，没有考虑节点的剩余能量，使剩余能量较小的节点有可能成为簇头，导致簇头过早死亡。

(3)每一个簇中，簇头位置未必最优，使簇内节点能耗不均衡。

2 二进制粒子群优化算法

式中，w是惯性因子，c1是个体学习因子，c2是全局学习因子，r1和 r2是区间[0，1]上的随机数，PB是粒子的个体最优值，GB是粒子群最优值。

二进制粒子群优化算法 BPSO[6](Binary Particle Swarm Optimization)的位置矢量是二进制空间，粒子在每一维上的取值只能是0或1，速度矢量仍然位于实数空间。BPSO速度矢量的更新公式仍用式（2），位置矢量改用式（3）描述：

3 BPSO-LEACH算法

针对LEACH协议的不足，提出了以下改进方案。

(1)针对簇的个数不确定，根据 WSN的能量消耗模型，计算出使整个网络能耗最小的簇数，在分簇过程中控制簇的数量，使簇的个数最优。

(2)针对能量较小的节点可能成为簇头和簇头位置不是最优，在每个簇中遵循簇头节点能量较大、簇内成员节点能耗均衡的思想，应用BPSO算法重新选择簇头。

3.1 网络模型

(1)基站位于WSN外部，能量不受限制，计算能力不受限制。

(2)节点随机部署在一个正方形区域中，节点初始能量相等，部署后不再移动。

(3)基站知道 WSN内节点的地理位置和初始能量，基站能根据节点发送的数据量估算节点的剩余能量。

(4)成员节点可以根据到簇头的距离，调整自己的发射功率。

3.2 分簇数目的控制

在簇的形成阶段，每一个成为簇头的节点首先把自己成为簇头的信息报告给基站而不是向全网广播，此时的簇头称为候选簇头。如果向基站报告的候选簇头的个数超过 KBest，则基站从中随机挑选 KBest个作为候选簇头，其余的作为普通节点；如果候选簇头个数不足 KBest个，则基站线性增大阈值T(n)并告知全网节点，重新启动簇头选举，直到产生 KBest个候选簇头。候选簇头确定之后，按照LEACH中的成簇方法把整个网络分成KBest个簇。

3.3 应用BPSO算法确定最终簇头

从所有节点中选出 KBest个候选簇头并成簇后，候选簇头在簇中的位置很可能不是最优。下面应用BPSOLEACH算法选择每个簇最优的簇头。

3.3.1 粒子的编码

设簇中有M个节点，则粒子的搜索空间就是M维二进制空间。粒子i在进化的第k代的位置矢量是，粒子每一维矢量的取值只能是 0或 1。若=1，则表示第k次迭代时第k个粒子对应的分簇方案中把第j个节点作为簇头；若=0，则第j个节点作为簇中的成员。

3.3.2 适应值函数的设计

应用BPSO-LEACH算法选择簇头时，优化目标是使簇中所有节点的能耗之和最小且均衡。定义适应值函数如式（4）所示：

3.3.3 BPSO-LEACH的步骤

“三师”工作由学校马克思主义学院负责组织实施，为马克思主义学院的“一号工程”“一把手工程”。实施之前必先制定具体工作方案，经全体教师讨论，通过后再实施。每个月收集一次“三师”工作材料并及时通报，以督促进度，强化过程管理，防止弄虚作假。“三师”工作自2017年秋季展开后，经过一个学期的实践，发现存在以下问题：

对每一个簇分别应用BPSO-LEACH算法选择簇头。

(1)初始化一个规模为Q的粒子群，每个粒子的维数是 M（簇中节点个数），确定参数 c1、c2、w和迭代次数 k。

(2)初始化粒子的位置和速度。粒子的位置矢量由式（5）给出：

r(0，1)是区间[0，1]上的随机数，R是一个常数。粒子的速度矢量由式（6）给出：

其中：VMin和 VMax分别是粒子速度的最小值和最大值。

(5)根据式(2)和式(3)更新粒子的速度和位置矢量。

(6)重复步骤(3)～(5)，直到完成规定的迭代次数。

(7)对于最终全局最优值所对应的粒子，因其对应了若干种簇头选择方案（簇头选择方案总数等于值是1的矢量的维数之和）。对每一个候选簇头，应用式(4)求其适应值，取适应值最小的候选簇头作为最后的正式簇头。

4 仿真实验

应用MATLAB软件对LEACH和BPSO-LEACH进行仿真，各运行100次，取平均值进行比较。评价指标是：（1）网络生存时间，从仿真开始到网络中 70%的节点还存活所经历的轮数。（2）网络生存时间内节点的总能量消耗。

4.1 仿真环境和算法参数

仿真参数如表1所示。

表1 仿真参数

4.2 仿真结果

图1是LEACH和BPSO-LEACH的网络生存时间仿真结果。图中的横坐标表示分簇轮数，纵坐标表示存活节点数。从图1可以看出，LEACH在620轮左右即出现第一个死亡节点，而BPSO-LEACH在870轮左右出现第一个死亡节点。LEACH的存活节点还剩下70%时的轮数约为1 300轮，BPSO-LEACH约为1 930轮。LEACH分簇的节点在大约2 900轮后全部死亡，而BPSO-LEACH约为4 500轮。

图1 LEACH和BPSO-LEACH的生存时间

图2是LEACH和BPSO-LEACH总的能量消耗仿真结果。图中的横坐标表示分簇轮数，纵坐标表示网络中所有节点的剩余能量之和。由图2可以看出，在网络分簇的开始150轮，两种算法的能量消耗相差不大，随着分簇轮数的增加，BPSO-LEACH的能量消耗要明显小于LEACH。

图2 LEACH和BPSO-LEACH的能量消耗

5 结束语

本文首先在分簇过程中按最优簇数控制了簇的数量。初步分簇过程按照LEACH协议的簇头选举方法选出候选簇头，成簇后再应用二进制粒子群方法重新选择最终簇头。粒子的编码采用了簇头为1、节点为0的二进制编码方案，适应值函数的设计目标是簇中节点的能耗之和最小且能耗均衡。迭代结束后取最优粒子中适应值最小的候选簇头作为最终的簇头。仿真结果表明，BPSO-LEACH比LEACH可以节约30%的能量，延长约50%的网络生存期。

[1]HEINZELMAN W，CHANDRAKASAN A，BALAKRISHAM H. Energy-efficient communication protocol for wireless microsensor networks[C].Proceedings of the 33rd Annual Hawaii International Conf.on System Sciences.[S.l.]：IEEE Computer Society，2000：3005-3014.

[2]Chen Xuhui，Yang Zhiming，Cheng Huiyan.Unequal clustering mechanism of LEACH protocol for wireless sensor networks[C].2009 World Congress on Computer Science and Information Engineering(CSIE 2009)，Los Angeles，USA，March 2009

[3]HANDY M J，HAASE M，TIMMERMANN D.Low energy adaptive clustering hierachy with deterministic cluster-headselection[C].Proc.of the 4th IEEE Conf.on Mobile and Wireless Communication Networks.Stockolm：IEEE Communications Society，2002：368-372.

[4]吕涛，朱清新，张路桥.一种基于LEACH协议的算法[J].电子学报，2011，39（6）：1405-1409.

[5]KENNEDY J，EBERHART R C.Particle swarm optimization[C]. IEEE International Conference on Neural Networks，IV.Piscataway，NJ，USA：IEEE Service Center，1995：1942-1948.

[6]KENNEDY J，EBERHART R C.A discrete binary version of the particle swarm algorithm[C].The 1997 Conference on System，Cybernetics and Informatics.Piscataway，NJ USA： IEEE Press，1997：4104-4109.

[7]HESHAM A，Yang S H.Dynamic cluster head for lifetime efficiency in WSN[J].International Journal of Automation and Computing，2009，6(1)：48-54.

Improved binary particle swarm optimization algrothrim of LEACH protocol for wireless sensor network

Cao Yuxiao，Xu Jinbao，Xu Mengxi，Peng Huanfeng
(School of Computer Engineering,Nanjing Institute of Technology,Nanjing 211167，China)

This paper brings forth one kind of algrothrim based on binary particle swarm optimization(BPSO)which is used to sovle the problem described as follows.One problem is that node of wireless sensor network(WSN)with low energy probably could become cluster head.The other problem is that cluster head could have unreasonable position when WSN is divided into several clusters.Firstly，the number of clusters is managed to the best value.Secondly，BPSO is used to select the best node in each cluster as cluster head.Finally，it is proved by simulation experiment that LEACH protocol optimized by binary particle swarm can lower total energy consumption of WSN and prolong lifetime of WSN compared to LEACH protocol.

wireless sensor network；cluster；LEACH protocol；binary particle swarm optimization；particle code

TP393

A

0258-7998(2015)04-0091-03

10.16157/j.issn.0258-7998.2015.04.021

2014-11-02)

曹欲晓（1971-），男，硕士，讲师，主要研究方向：智能算法、无线传感器网络。

徐金宝（1970-），男，硕士，副教授，主要研究方向：智能算法、数据挖掘。

徐梦溪（1983-），女，博士研究生，讲师，主要研究方向：图像处理、模式识别。

江苏省高校自然科学研究面上项目（13KJB520009）