刘志坤，刘 忠，李朝旭

(海军工程大学电子工程学院，武汉 430033)

无线传感器网络(WSN)作为一种新型的信息采集、传输、处理系统，在军事和民用领域得到了广泛的应用［1－2］。WSN的一个显著特征是节点能量有限，通常难以进行能量补充。因此，如何节约节点的能量消耗，延长网络的存活周期，就成为WSN领域研究的一个热点问题。分簇路由协议是解决该问题的一种有效方法。它将WSN划分为若干个簇组织，从而可以有效地管理网络数据，提高网络效能，延长网络存活时间。

LEACH(Low-Energy Adaptive Clustering Hierarchy)是最早提出的分簇协议［3］，它以等概率对簇首进行周期随机选择，将整个网络的负载均匀分布到每个传感器节点，从而达到降低网络能耗，延长网络寿命的目的。该算法最大的缺陷是忽略了节点能量的因素，造成网络能量消耗的不均衡，导致局部节点过早死亡。此后的研究者大都注意到了这一缺陷，并作了改进。文献［4］在簇头选择的过程中引入节点的剩余能量，使剩余能量较多的节点当选为簇头的可能性增加，降低了组簇失败的可能性。文献［5］中的LEACH-C算法，进一步要求当选簇头节点的能量高于网络节点的平均剩余能量。文献［6］提出了DF-LEACH算法，考虑到距离基站较远的簇头通信能耗较大这一因素，避免了距离基站较远的簇头节点较早死亡。文献［7］给出的算法将所有节点分为固定的簇，簇内节点根据所处簇的半径自适应地进行簇头选择。簇头选举是一个NP难解问题，智能优化算法解这类问题具有独特的优势。文献［5］中的LEACH-C算法在基站采用模拟退火算法(Simulated Annealing Algorithm)完成分簇;文献［8］给出了一种基于蚁群优化的分簇算法，但是只适用于小规模网络;文献［9］采用粒子群优化(PSO)分簇算法，提出了均匀分簇(每个簇的节点数量及候选簇头数量相等)的思想，但是该算法不适用于网络节点分布不均匀的情况;文献［10］提出了一种基于最优簇数的分簇策略，采用PSO进行分簇优化，但是没有考虑簇头到基站距离这一因素。

根据最优化理论领域的NFL(No Free Lunch Theorem)定理［11］，没有一种算法对任何问题都能做到解最优。因此，需要针对某一实际问题，融合不同算法的各自优势，构造出适应该问题的新算法。本文正是根据这一思路，将混沌理论引入PSO算法，有效避免了PSO算法易陷入局部最优解的缺陷，提出了一种应用混沌粒子群优化的分簇协议，新协议对剩余能量、簇头距汇聚节点距离以及簇范围的选择作了综合考虑，延长了网络生存周期。

1 系统模型

1.1 网络模型

本文采用分簇层次网络拓扑结构，如图1所示。

图1 网络拓扑结构图

网络由簇成员节点(Cluster member node)，簇头节点(Cluster head node)和汇聚节点(Sink node)组成。分簇算法将网络节点分为多个簇，每个簇包含一个簇头节点和多个簇成员节点，簇成员节点将采集到的数据传送到簇头节点，簇头节点除了自身采集数据外，还要接收其成员节点发送来的数据，并对这些数据进行融合，而后将处理的结果发送至汇聚节点。汇聚节点具有足够的能量，其处理能力、存储能力和通信能力较强，起到连接无线传感器网络与外部网络的作用。除汇聚节点外，对网络节点模型的具体要求如下:

(1)节点属于同构节点，具有相同的初始能量、信息处理能力、探测半径和通信半径，并且通信半径远大于探测半径;

(2)发射功率在允许范围内可调;

(3)节点的位置固定，其自身的位置信息已知，可以通过GPS设备或者节点自定位算法获得，本文不讨论WSN节点自定位问题;

(4)汇聚节点唯一且位置固定，各网络节点距离汇聚节点的距离已知，可以通过节点与汇聚节点的信息交换获取。

1.2 能耗模型

节点的能量消耗主要来自数据收发和处理，与之相比，侦听和休眠状态消耗的能量微不足道。因此，本文仅考虑数据收发和处理的能耗。为了便于与LEACH算法进行仿真比较，采用与文献［3］相同的无线通信模型，网络节点发送kbit数据传输dm距离消耗的能量ETx为

节点接收kbit数据所需要的能量ERx为

节点处理kbit数据所需的能量Eda-fus为

其中，Eelec是发送电路和接收电路的能量消耗;Eda是处理数据的能量消耗;εfs和εmp分别是自由空间模型和多径衰减模型中功率放大器的能量消耗，d0是传输距离门限，决定了衰减模式。

2 混沌粒子群算法

PSO算法是一种基于种群搜索策略的全局优化算法［12］，它在搜索空间中初始化一群随机粒子，每个粒子代表解空间内的一个随机解，粒子在搜索空间内飞行，根据其自身经验和整个群体的经验动态调整自己的速度，通过迭代找到最优解，每个粒子根据如下的公式来更新自己的速度和位置:

其中，vk是粒子的速度向量;xk是当前粒子的位置;pbestk表示粒子本身所找到的最优解的位置;gbestk表示整个种群目前找到的最优解的位置;c0表示惯性权重，当它取较大值时，有利于跳出局部极值，当它取较小值时，有利于算法收敛，一般取介于(0，1)之间的随机数，c1、c2表示加速常数，其值低时允许粒子在目标区域外徘徊，高的值则导致粒子突然冲向或超过目标区域，一般取(0，2)之间的随机数。

粒子群算法很容易陷入局部最优解［13］，为了解决该问题，将混沌理论引入PSO算法，完成算法改进。混沌是存在于非线性系统中的一种貌似随机的运动形式，是确定性系统内在随机性的表现，它具有随机性，遍历性和规律性三个特点［14］。混沌的这些特征，十分有利于PSO的优化和改进:随机性有利于算法获得大范围搜索能力，遍历性使得最终解有能力逼近最优解，规律性可以保证算法使用固定的迭代方程，从而便于编程计算。改进后的算法思路是:首先初始化种群，设定好参数。而后计算每个粒子的适应度，选出个体极值和全局极值，利用式(4)、式(5)开始迭代寻优过程。运算到预先设定的次数后，启动混沌搜索，对当前最优解gbest施加混沌扰动，获得新的最优解g'best，计算其适应值fitness'并与gbest的适应值 fitness进行比较，如果 fitness'＜fitness(即加入混沌扰动后的最优解优于当前最优解)，则选取g'best作为新的全局最优解继续迭代计算。

以往的研究通常使用logistic映射产生混沌扰动，但是根据文献［15］的结论，Tent映射的遍历均匀性优于logistic映射，可以获得更高的搜索寻优效率，因此本文采用Tent映射作为混沌扰动产生器，它的表达式如下:

产生混沌点列的过程如下:

步骤1设粒子的n维位置向量为xi=(xi1，xi2，…，xin)，根据式(7)将其映射到［0，1］区间上

其中，［ak，bk］是第k维变量xik的定义域。

步骤2由式(6)迭代产生混沌序列

步骤3由式(8)将混沌序列中的点映射回原空间，得到xi经过Tent映射后的混沌点列:

3 分簇协议描述

3.1 分簇原则

本文的分簇协议主要遵循以下原则:

(1)簇头节点的剩余能量较多 这点是经典的LEACH分簇协议没有考虑到的。因为簇头节点要担负更多的管理和通信任务，消耗的能量也相应的更多，如果当选的簇头节点能量不足，会造成簇组织的维持时间缩短，造成任务无法完成。

(2)簇头节点与汇聚节点的距离相对较近 簇头节点根据簇成员节点汇报的信息进行初步的处理后，要将结果发送给汇聚节点，如果簇头距离汇聚节点过远，信号的发送将消耗大量的能量，簇头会很快死亡。

(3)簇头节点激活的范围要适当 所谓适当，就是指簇的规模不能太大，这会造成簇边界成员与簇头的通信距离过远，此外，过多的成员节点与簇头信息交互有可能造成不必要的数据冲突;簇的规模又不能太小，这会造成簇的工作范围减小，激活节点的数目不够，满足不了任务要求。因此，需要通过强制手段限定簇范围，达到确保簇具有局部性的目的。

前两条原则，本文通过混沌粒子群算法中适应度的合理设置来满足，第(3)条原则，则通过对接收指示信号强度设定阀值获得，将给出一种簇范围确定方法。

3.2 基于CPSO的分簇算法(CPSOCH)

在设计时权衡节点剩余能量及节点与汇聚节点的距离两个因素。适应度的计算公式为:

其中，α1、α2是影响因素的权重，满足 α1+α2=1;qi是网络中第i个节点的剩余能量，qk是第k个当选簇头节点的剩余能量，f1是能量评价因子，等于网络中所有节点能量之和除以所有当选簇头节点的能量之和;li是第个节点距离汇聚节点的距离，lk是第k个当选簇头节点距离汇聚节点的距离;f2是距离评价因子，等于网络中所有节点到汇聚节点的距离之和除以所有当选簇头节点到汇聚节点的距离之和。这对应了之前对簇头选择的要求:节点的剩余能量越多，距离汇聚节点越近，越有可能当选为簇头。通过调节α1、α2达到调节各方面因素权重的目的。

首轮选举时，假设网络刚部署完毕，各节点剩余能量几乎相同，因此仍采用LEACH算法的簇头选举方式。确定最优簇数K，根据文献［5］的结论

其中，N、Efs、Eelec、εmp的意义如前文所述，l是簇头到汇聚节点的距离，D网络区域的边长，计算时通常取监测区域的中心或者所有节点平均坐标到汇聚节点的距离。

从第二轮选举开始，各节点剩余能量不同，此时汇聚节点采用本文基于CPSO的选举方法确定簇头。

基于CPSO的簇头选举算法具体步骤如下:

步骤1初始化M个粒子，每个粒子代表一种分簇可能，包含K个簇头候选节点;

步骤2通过式(9)～式(11)计算每个粒子的适应值，记录个体最优解和种群最优解;

步骤3通过式(4)、式(5)更新粒子的速度和位置;

步骤4搜索一定次数后通过式(6)～式(8)产生混沌扰动，计算扰动后每个粒子的适应值，记录个体最优解和种群最优解;

步骤5重复步骤2、3、4直到达到预定的循环次数，输出结果。

步骤6发布簇头信息。

确定簇头节点后，它要选择适当数目的成员节点参与任务，以往的选择方法往往无法保证簇的局部性，不利于节省能量。因此，本文根据接收指示信号强度阀值的方法来确定簇成员。簇头应用CSMA(Carrier-sense Multiple Access)MAC层协议向非簇头节点广播当选消息(ADV，Advertisement Message)，消息发送能量强度相同。如果节点接收到的ADV信号强度大于事先设定的阀值S0，则向该簇头发送请求加入消息Join-REQ，申请成为该簇头的成员节点。如果某节点同时收到多个能量大于S0的ADV消息，它将选择ADV强度最大的簇头。因为信号能量越强，说明节点距离该簇头的距离越近，可以有效地节省通信消耗。阀值S0的设定可根据网络具体执行任务的不同要求设定。

4 算法仿真及性能评估

为了对本文提出的分簇算法性能进行评估，在相同条件下对本文算法和LEACH算法进行仿真比较。实验中取200 m×200 m的区域，区域顶点的坐标分别为(0，0)、(200，0)、(200，200)，(0，200)。随机部署的节点的数为200个，汇聚节点的位置为(100，300)，根据式(12)可算出，簇头数量K的值取6。根据文献［3］，q0取 2J，Eelec取 50 nJ/bit，εfs取 10 pJ/bit/m2，εmp取 0.001 3 pJ/bit/m4，d0取 75 m，Eda取5 pJ/bit，数据包取2 000 bit。CPSO的参数设置为:初始化粒子数为 20，c0、c1、c2及最大速度vmax是在规定范围内通过多次实验确定的经验值，其中，c0取0.729 8，c1、c2取为 1.496 2，vmax=5，最大迭代次数设为1 000次，运算600次之后加入混沌搜索。对于影响因素权重α1、α2设置的考虑是:首先，节点必须拥有足够多的能量，这是其顺利运行的前提，如果能量不足，即使距离汇聚节点较近，也不应该被选为簇头;其次，如果距离权重α2取值过大，必然会导致当选簇头的范围集中在距离汇聚节点较近的小范围内，不利于目标跟踪等任务的完成。结合实验分析，本文将 α1、α2分别取为0.7、0.3。

选用网络生命周期和能耗两个技术指标来评价算法的性能［4］。其中生命周期的评估用3个时间来描述:第1个节点的死亡时间(First Node Die，FND)，一半节点死亡时间(Half of Nodes Die，HND)，最后一个(全部)节点死亡时间(Last Node Die，LND)。能耗用从网络启动到所有节点能量耗尽所用的时间来表示。仿真结果取10次运行的平均值。

从图2可以看出，较之LEACH协议，新协议的FND，HND，LND 的时间分别延长了 115.82%，34.53%，38.65%，明显延长了网络的生命周期。特别是极大地延缓了第一个死亡节点的出现时刻，说明新协议较好了均衡了网络能量消耗，避免了个别节点的快速死亡。

图2 网络生命周期对比

从图3可以看出，LEACH协议运行了533轮后能量全部消耗完毕，而CPSOCH协议则在运行了739轮后才消耗完所有的能量。LEACH的曲线斜率变化较大，说明在不同时间内存在簇头选择不合理造成能量消耗较大的情况，而CPSOCH曲线斜率相对平稳，说明簇头选择相对更合理。可见在能耗方面CPSOCH协议也优于LEACH协议。

图3 能耗对比

5 结论

本文提出了一种WSN分簇协议，利用了智能算法在处理NP难解问题上的优越性，将结合了混沌理论和粒子群算法的混沌粒子群算法应用于分簇问题的优化，在簇头选择时考虑到了节点能量和汇聚节点距离等因素，在成员节点划分时，给出了一种基于信号能量阀值的簇范围划分方法，从而达到了节省能量，延长网络生存寿命的目的。下一步的工作应针对不同应用场景(目标跟踪、环境监测等)，对该算法的具体应用进行研究。

［1］李建中，高宏.无线传感器网络的研究进展［J］.计算机研究与发展，2008，45(1):1－15.

［2］孟凡勇，熊庆旭.基于应用任务的无线传感器网络MAC协议［J］.传感技术学报，2010，23(1):98－103.

［3］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proc.of the 33rd Annual Hawaii International Conf.on System Younis Sciences.Maui:IEEE Computer Society，2000:3005－3014.

［4］Handy M J，Haase M，Timmerrnann M D.Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection［C］//Proc.of the 4th IEEE Conf.on Mobile and Wireless Communications Networks.Stockholm:IEEE Communications Society，2002:368－372.

［5］Heinzelman W，Chandrakasan A，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans on Wireless Communications，2002，1(4):660－670.

［6］陈磊，赵宝华.低能耗自适应分簇的面向数据融合的路由协议［J］.北京邮电大学学报，2009，32(5):71－74.

［7］胡星华，骆坚，谭珊珊.固定簇的LEACH半径自适应簇头改进算法［J］.传感技术学报，2011，24(1):79－82.

［8］张荣博，曹建福.利用蚁群优化的非均匀分簇无线传感器网络路由算法［J］.西安交通大学学报，2010，44(6):33－38.

［9］Tillett J，Rao R，Sahin F.Cluster-Head Identification in ad-hoc Sensor Networks Using Particle Swarm Optimization［C］//Proc.of IEEE International Conf.on Personal Wireless Communications.New Delhi，India，，2002:201－205.

［10］郭剑，孙力娟，王汝传.基于最佳簇数的无线传感器网络粒子群分簇协议［J］.南京邮电大学学报(自然科学版)，2010，30(2):36－40.

［11］Wolpert D H，Macready W G.No Free Lunch Theorems for Optimization［J］.IEEE Trans.on Evolutionary Computation，1997，1(1):67－82.

［12］Kennedy J，Eberhart R.Particle Swarm Optimization［C］//Proc.of IEEE International Conf.on Neural Networks，Perth，1995:1942－1948.

［13］Zhang C S，Sun J G.An Alternate Two Phases Particle Swarm Optimization Algorithm for Flow Shop Scheduling Problem［J］.Expert System with Applications，2009，36(3):5162－5167.

［14］Tavazoei M S，Haeri M.An Optimization Algorithm Based on Chaotic Behavior and Fractal Nature［J］.Journal of Computational and Applied Mathematics，2007，206(2):1070－1081.

［15］单良，强浩，李军.基于Tent影射的混沌优化算法［J］.控制与决策，2005，20(2):179－182.