WSN中一种平衡节点能耗的分簇算法研究①

杨彩霞，　高　丽，　路　畅（兰州交通大学电子与信息工程学院，甘肃 兰州 730070）

WSN中一种平衡节点能耗的分簇算法研究①

杨彩霞，高丽，路畅
（兰州交通大学电子与信息工程学院，甘肃 兰州 730070）

针对无线传感器网络（WSN）中能量消耗和节点死亡过高的问题，在分析LEACH-C集中式分簇算法的基础上，提出了一种基于量子行为粒子群优化的WSN分簇算法.考虑到模拟退火算法在执行算法过程中的复杂性，利用具有全局搜索能力和收敛速度快等特点的量子行为粒子群优化算法，代替模拟退火算法对LEACH-C分簇算法中簇头的选取进行优化.通过MATLAB仿真分析，改进后的算法有效延长了传感器节点的生命，平衡了各节点的能量，提高了WSN的整体性能.

无线传感器网络；LEACH-C；分簇算法；量子行为粒子群优化算法；节点死亡

0　引言

LEACH-C分簇算法［1］是 Heinzelman继LEACH算法之后于2002年提出的集中式分簇路由算法.文献［2］对LEACH-C算法改进，提出了一种LEACH-m算法，针对过度依赖基站的问题，引入副簇头，并且降低簇头的能耗，提高簇的生存能力.文献［3］对LEACH-C算法中簇头选取使用的模拟退火算法进行了改进，文献［4］引用SUSAN算子对LEACH-C算法进行了改进.文献［5］利用固定和非固定相结合的方式，进行分簇，提出了LEACH-C分簇算法.本文在LEACH-C的基础上，提出了一种基于量子行为粒子群的LEACH-C分簇算法.

1　基于量子行为粒子群的LEACHC分簇算法

1.1LEACH-C分簇算法

在LEACH-C算法每个周期的开始时间，基站用来接收所有节点的位置信息和剩余能量值，并且在收？到节点的信息后，计算所有节点的平均能量值，备选节点是能量大于平均能量值的节点.然后使用模拟退火算法从备选节点中找出簇头集，选出簇头节点，最后把这个簇头集合广播给网络中的所有节点.如果一个节点收到的簇头集合中包含有自己的信息，那么这个节点就作为其中的一个簇头；否则，节点直接与相应的簇头建立联系，并等候相应的时分复用（TDMA）时隙的到来，最后向簇头传输数据，在这个过程中，簇头完成了TDMA中时隙的分配.

1.2量子行为粒子群优化算法

量子行为粒子群优化算法［6］（Quantum-behaved Particle Swarm Optimization，QPSO）是Sun J等人在粒子群优化算法的基础上，结合量子理论，提出的一种具有全局搜索特点的算法.相对于粒子群优化算法（PSO），QPSO算法的进化方程简单，不需要粒子的速度信息，并且收敛速度快，控制参数少，运算比较方便.QPSO算法中，束缚状态的粒子通过概率密度函数描述，能够根据一定概率出现在整个可行搜索空间的任何一个位置，也可能出现在一个远离局部吸引子的位置上，因此可以有效增加群体多样性，从而达到全局搜索.此外，QPSO算法的另一个亮点是引入平均最佳位置，粒子之间能够在迭代进化过程中互相等待，粒子之间的协作能力和全局搜索能力得到了提高.

在量子力学中，粒子的状态用波函数φ（X，t）描述，它是坐标和时间的复函数.其中X（x，y，z）为粒子在三维空间中的位置向量.波函数的物理意义是：波函数模的平方是粒子在t时刻出现在空间某一点X的概率密度.即：

把概率密度函数归一化可以得到：

引入平均最好位置mbest，定义为全部粒子个体最优位置的平均，即

其中pbest为粒子个体最优.（3）式被叫做量子行为粒子群优化算法.

1.3无线网络能量消耗模型

对于改进的分簇算法，给出在二维区域内的的无线网络模型：（1）基站位置固定；（2）每个传感器节点初始能量相同或相近，并且都拥有唯一的ID标志；（3）所有节点部署后不再移动，节点之间等效通信；（4）所有节点都有定位能力.

能量模型采用和文献［5］中相同的能量模型.若传输mbit的信息经过距离d，此时发送端的能量消耗为：

如果数据的传输距离小于阈值d0时，功率放大消耗采用自由空间模型，如果数据的传输距离大于等于d0时，采用多路径衰减模型.其中Eelec，表示发射电路所要消耗的能量；εfs，εmp分别表示自由空间模型和多路径衰减模型中的信号衰减因子；d0表示发送方和接收方之间的通信距离.

1.4 基于量子行为粒子群优化的LEACH-C分簇算法

量子行为粒子群优化算法（QPSO）作为一种随机优化算法，在搜索能力，收敛速度以及解的精度等方面都体现了较好的性能.在LEACH-C算法中，簇头相比簇内节点来说，本身消耗了更多能量；根据簇头距基站的距离来说，簇头距基站的距离决定了通信能耗的大小；分析考虑到分簇的重要性，本论文拟结合QPSO算法，对簇头选取进行优化.

传统的LEACH-C分簇算法中，簇头的选择使用模拟退火算法.在模拟退火算法中，随机产生一个初始解，并且算法执行过程中的随机扰动都在一定程度上使得算法执行的效率比较低，并且消耗了更多的时间，影响了网络的整体性能.而且理想的退火算法需要温度值非常缓慢地连续下降，这个过程一般不容易做到，这也是模拟退火算法在执行算法时效率不高的原因之一.模拟退火算法在选举簇头的过程中，尽管减小了整个WSN网络的传输代价，但是增加了节点的能量.因此，本文在原来算法的基础上，针对簇头的选取，根据QPSO算法的步骤，提出了一种改进的算法.

在改进的算法的簇的建立阶段，首先基站获得各节点的位置信息，然后根据QPSO算法选取簇头，选取簇头的主要步骤如下：

步骤1首先对节点进行初始化.设传感器节点均匀分布在一定的区域内，对于在这个区域内给定的粒子群，随机产生服从均匀分布的粒子的向量，计算粒子群的个体最好位置，也就是计算该区域节点的个体最好位置.节点的的个体最好位置的计算依然采用Sun J等人提出的下列公式：

步骤2计算每个节点的适应度函数值，并将适应度函数最优的节点设置为全局最优.

步骤3根据（3）式更新节点的平均最优位置.

步骤4通过（1）式更新节点的位置.

步骤5将节点的当前适应度函数值和个体最优pbest适应度函数值进行对比，若是前者优于后者，则取代为个体最优pbest.

步骤6和步骤5类似，将节点的当前适应度函数值和全局最优gbset适应度函数值进行比较，如果前者优于后者，则取代为全局最优gbest.全局最优采用以下公式计算［8］：

步骤7如果没有达到终止条件，重复步骤2 到6，直至满足要求，全局最优节点则为当选簇头，得到簇头集合.

最后，基站把这个簇头集合广播给网络中的所有节点.节点进行判断，自己的信息是否与簇头集合中包含的信息一致，完成数据的稳定传输.

2　仿真分析

算法的仿真在MATLAB上进行.为了验证算法的正确性，将改进的算法和LEACH-C算法以及LEACH算法进行比较.首先设定基站的坐标为（50，50），位置是固定不变的，仿真场景设置为200m*200m的区域，并且在区域内均匀分布100个传感器节点，算法可执行的最大时间轮数是5000轮.具体的仿真环境参数如表1所示.仿真实验通过对节点的存活个数，以及网络能量消耗进行评价.

表1　仿真环境参数

图1　节点存活个数对比图

图1是在传感器节点存活个数和时间运行轮数之间的关系图.取时间运行100轮的结果图进行分析，从图中可以看出，LEACH算法和LEACH-C算法的第一个死亡节点在算法运行开始阶段就出现了，改进的算法的节点死亡时间比LEACH算法和LEACH-C算法提前了.从程序运行结束来看，LEACH算法和LEACH-C算法在大约40轮和60轮之间节点全部死亡，而改进的算法在大约68轮左右节点全部死亡.改进后的算法相对于原算法，明显提高了传感器节点的存活时间.

图2　网络能量消耗对比图

图2是网络能量消耗对比图.横坐标设置为时间运行轮数，纵坐标为节点的能量消耗，单位为焦耳.从图中可以看出，改进后的算法相比LEACH算法和LEACH-C算法，能量消耗曲线呈平缓变化，有效延长了传感器网络的寿命.

3　结束语

本文在分析了LEACH-C算法的基础上，结合量子行为粒子群优化算法对LEACH-C分簇算法中簇头的选取进行了优化，并在MATLAB上进行了仿真分析.从仿真结果可以看出，改进后的算法有效延长了节点的死亡时间，使传感器节点的存活率更高，并且进一步减少了算法中存在的能量损耗，提高了传感器网络的整体性能.但改进的算法还是适用于规模小的网络，具有一定的局限性，如果将算法应用于实际环境中，考虑的因素会更多，这都是下一步要进行的研究方向.

［1］Heinzelman W R，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［C］.MITUSA：IEEE Transactions on Wireless Communications，2002：660-670.

［2］何传波.无线传感器网络关键技术的研究［D］.武汉：武汉理工大学，2014.

［3］ 牛伟伟，高铁杠.LEACH-C协议中模拟退火算法的改进［J］.计算机工程与设计，2011，32（6）：1869-1872.

［4］ 唐启涛，刘蓉，张燕等.基于SUSAN算子的LEACH-C路由算法［J］.微计算机信息，2012，10：200.

［5］蒋华，刘伟强，王鑫.无线传感器网络中Leach-c路由协议的研究与改进［J］.微电子学与计算机，2014，12（31）：43-47.

［6］孙俊，方伟，吴小俊，须文波.量子行为粒子群优化：原理及其应用［M］.北京：清华大学出版社，2011：1-50.

［7］盛歆漪，孙俊，周頔，等.自学习的量子粒子群优化算法改进［J］.计算机工程与应用，2014，50（20）：24-29.

［8］Sun J，Wu X，Palade V，et al.Convergence analysis and improvements of quantum-behaved particle swarm optimization ［J］.Information Sciences，2012，193：81-103.

Research on the Clustering Algorithm of a Balanced Energy Consumption of Nodes for WSN

YANG Cai-xia， GAO Li， LU Chang
（School of Electronic&information Engineering，Lanzhou Jiaotong University，Lanzhou 730070，China）

Aiming at the problem that the energy consumption and node death are too high for wireless sensor networks（WSN），on the basis of analyzing the LEACH-C centralized clustering algorithm，the paper proposed a WSN clustering algorithm based on quantum-behaved particle swarm optimization.The complexity of simulated annealing algorithm in the implementation of the algorithm was taken into account.A quantum behaved particle swarm optimization algorithm with global searching ability and fast convergence rate，and replaced the simulated annealing algorithm was used to optimize the selection of cluster head in LEACH-C clustering algorithm.Through MATLAB simulation analysis，the improved algorithm can effectively prolong the life of sensor nodes，balance the energy of each node，and improve the overall performance of WSN.

WSN；LEACH-C；Clustering Algorithm；QPSO；Node death

TP393

A

1008-1402（2015）06-0925-04

2015-10-26

国家自然科学基金（61261029）.

杨彩霞（1989-），女，甘肃武威人，硕士研究生，主要研究方向为无线传感器网络，通讯作者：高丽（1974-），女，副教授，研究生导师，主要研究方向为智能信息处理理论及应用技术.