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 二进制粒子群优化算法

　　设粒子在D维空间中寻优，每个粒子有一个位置可用式（1）和式（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 分簇数目的控制

　　设WSN中有N个节点，随机分布在L×L的区域，共分成K个簇，dHB是簇头到基站的欧氏距离，?着fs和?着mp是节点的无线通信能量消耗系数。由文献[7]可知：当网络分成K个簇时，总的能量消耗最小，此时的K称为KBest。

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

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

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

　　3.3.1 粒子的编码

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

　　3.3.2 适应值函数的设计

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

　　式中：d是簇中第i个节点到候选簇头距离的平方，var(diH)是簇中第i个节点到候选簇头距离的方差， eH是候选簇头的能量，?琢>0，?茁>0，?酌>0，?琢+?茁+?酌=1。在WSN生命期的不同轮中，可以使簇头的选举倾向于能耗最小或是能耗最为均衡。

　　3.3.3 BPSO-LEACH的步骤

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

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

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

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

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

　　(3)计算粒子的适应值。对于每一个粒子，如果X=1，表示第k次迭代时第i个粒子表示的分簇方案中第j个节点作为簇头，其他节点作为成员，利用式（4）计算粒子的适应值。

　　(4)计算每个粒子的个体最优值和整个种群的全局最优值。迭代过程中，使适应值函数取得最小值的粒子的位置矢量是个体最优值，在所有的个体最优值中求出全局最优值。

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

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

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

4 仿真实验

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

　　4.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轮。

　　图2是LEACH和BPSO-LEACH总的能量消耗仿真结果。图中的横坐标表示分簇轮数，纵坐标表示网络中所有节点的剩余能量之和。由图2可以看出，在网络分簇的开始150轮，两种算法的能量消耗相差不大，随着分簇轮数的增加，BPSO-LEACH的能量消耗要明显小于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 cluste-ring mechanism of LEACH protocol for wireless sensor networks[C].2009 World Congress on Computer Science andInformation Engineering(CSIE 2009)，Los Angeles，USA，March 2009

　　[3] HANDY M J，HAASE M，TIMMERMANN D.Low energy adaptive clustering hierachy with deterministic cluster-head selection[C].Proc.of the 4th IEEE Conf.on Mobile and Wireless Communication Networks.Stockolm：IEEE Communi-cations 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.Pis-cataway，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 onSystem，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.