基于混沌优化萤火虫算法的WSN分簇算法*

孙爱晶，郑世鹏

(西安邮电大学通信与信息工程学院，陕西 西安 710121)

无线传感器网络(wireless sensor network，WSN)中是由大量低成本、能量有限的无线传感器节点组成的自组织多跳网络，对于复杂的环境很难给节点补充能量，所以为了尽可能的延长网络的生存时间，节能是无线传感器网络中很重要的一个问题[1－2]。高效合理的网络拓扑结构能够大幅提高网络的利用效率并延长其生命周期，优化网络的整体能耗效率、延长网络寿命是WSN中一项重要的研究内容[3－4]。

经典的低功耗自适应集簇分层型(low-energy adaptive clustering hierarchy，LEACH)[5]协议根据提出的概率公式随机选取簇首，节点随机生成一个随机数，并和阈值做比较，如果小于该阈值，则节该点被选为簇头，节点根据簇首的位置就近入簇，簇头对采集的数据进行融合后以单跳方式传输到基站，该策略不能保证簇首数目及簇首位置的合理分布，选取簇头也没有考虑节点的剩余能量。研究者针对LEACH协议的缺点提出的多种改进型协议。其中较为经典的如李成法等人提出的EEUC算法[6]，该算法中候选簇头的选取方式和LEACH协议选取簇头的方式类似，在候选簇头中引入了竞争半径决定最终簇首，使用非均匀成簇的策略，缩小基站周围簇首的成簇半径，减小了簇头收集簇内数据时的负载，有效的缓解了以多跳方式向基站传输数据时产生的“热区”问题；文献[6]在LEACH协议的基础上提出了LEACH-improved算法，在选取簇首时考虑了多个影响因子，避免了能量较小的节点当选为簇首，但因子间的权重值难以确定，实际应用困难，且易形成极大簇造成节点间的负载不平衡；针对WSN节点能耗不均的问题，文献[8]引入蚁群算法确定路由，通过信息素浓度选出路由节点优化路径质量；文献[9]针对簇首位置和传输路径选取不合理加剧节点能耗、缩短网络寿命的问题，采用改进粒子群算法对网络分簇，并设计了一种最小生成树的多跳路由，有效延长了网络的生存周期。还有一些研究者引入聚类算法对网络进行分簇，Bakaraniya等[10]基于K-means算法提出了K-LEACH算法，初始阶段利用K-means进行聚类，簇头的选举没有考虑节点的剩余能量；直接使用传统K-means和FCM算法进行聚类容易产生局部最优解和收敛速度慢的问题，文献[11]使用遗传算法(GA)优化模糊C均值聚类从而提出了GAFCMCR算法，该算法将GA应用到FCM算法的优化计算中，由GA得到初始聚类中心，再使用标准的FCM算法聚类，然后通过评价函数，在每个簇内竞选出最终簇首，该算法成簇效果较好，具有较好的能量均衡性。但在簇头轮换阶段，判断更换簇头的条件里参数λ选取困难，文中只提到λ取值太大或者太小都会增加网络的能量消耗，并没有验证所选取值是否最优，也没有给出选取最佳值的方法。

本文针对簇首分布不合理，节点负载不均衡，簇首轮换能耗大的问题，综合上述算法的优缺点提出了一种基于混沌优化萤火虫算法的WSN分簇算法。算法首先利用混沌理论优化的萤火虫算法，根据节点的位置分布设计目标函数对节点进行聚类，使簇首在整个检测区域内的分布更合理；然后引入双簇首规则均衡簇头负载，避免某些簇头负载过大较早死亡，并在数据传输阶段使用最短路径Bellman-Ford算法[12－13]确定数据多跳传输链路。另外，在簇首轮换阶段，充分考虑整个网络的剩余能量，由主簇首选出簇内当前剩余能量最高的两个节点充当下一轮的簇头。本文将从以上叙述的几个方面对算法进行仿真和分析。

1 系统模型

1.1 网络模型

本文所采用的网络模型如图1所示，由N个随机部署在M×M监测区域的传感器节点和一个能量不受限的汇聚节点(Sink)组成，关于该模型做出以下假设:①所有节点随机抛洒布设后位置都是固定不变的，汇聚节点位于检测区域中心位置；②节点可以通过接收的信号强度计算与Sink节点和其他节点的距离；③节点可以感知自身位置以及其他节点位置，根据距离控制发射功率和某一特定的节点通信；④每个成员节点周期性的检测数据并发送给相应的簇首；⑤每个节点属性相同，都具备一定的存储、计算、查询和数据融合能力。

图1 网络模型

1.2 能量模型

传感器节点传输数据所消耗的能量远大于节点用于计算所消耗的能量[14]，根据一阶无线电模型，在多径衰落信道，能耗和传输距离d的四次方成正比，所以本文从优化簇首的分布与簇结构的角度来减少采集数据时传播所消耗的能量，并采用LEACH协议中的一阶无线通信能耗模型，则传输距离为d时传感器节点发送lbit数据所消耗的能量ETx(l，d)可以表示为式(1):

式中，ε代表发射放大器的放大倍数；l代表传感器节点所发送或接收消息的比特数；Eelec代表发射或接收电路处理单位比特所消耗的能量；d0＝，为传输距离阈值，其中εfs为自由信道的能耗参数，εmp为多径衰落信道的能耗参数，当传输距离d＜d0时为自由信道，传感器节点发送或接收数据时消耗的能量与距离的平方成正比；当d≥d0为多径衰落信道，与距离的四次方成正比。

传感器节点接收lbit数据消耗的能量ERx如式(2):

2 理论分析

2.1 萤火虫算法

萤火虫算法(Firefly Algorithm，FA)[15]是由剑桥学者Yang模拟自然界中萤火虫的发光与移动特性提出的一种基于群体搜索的随机优化算法。其仿生原理是:利用萤火虫的发光特性使个体之间相互吸引，荧光度较弱的萤火虫向较强的萤火虫移动，从而实现位置优化。

Algorithm 1 Firefly Algorithm

FA算法主要遵循以下三个原则:①所有的萤火虫不区分性别，个体之间可以相互吸引；②吸引度β和亮度I成正比，因此对于任意两个萤火虫，亮度低的将向亮度高的个体移动，并且吸引度和亮度都随着距离的增加而减小。如果萤火虫的周围找不到更亮的个体，该萤火虫将做随机移动。③萤火虫的亮度由目标函数的值决定。

定义1萤火虫的相对荧光亮度为:

式中，I0为萤火虫的最大荧光亮度，即自身(r＝0处)荧光亮度，与目标函数值相关，目标函数值越优自身亮度越高；γ为光强吸收系数，可设置为常数；rij为萤火虫i和j之间的距离。

定义2萤火虫的吸引度β为:

式中，β0为最大吸引度，即光源(r＝0处)的吸引度。萤火虫个体的吸引度β随着个体间距离的增加而降低，其值的大小决定低亮度萤火虫个体向高亮度萤火虫个体移动的距离。

定义3萤火虫i被萤火虫j吸引进行移动的位置由式(5)更新:

式中，xi、xj代表任意两只萤火虫i和j在空间所处的位置；(xj－xi)为它们的笛卡尔距离；α∈[0，1]，为步长因子；rand是随机数，服从标准均匀分布；α×(rand－1/2)为随机扰动，避免算法陷入早熟。通过多次移动后，所有的个体都聚集到亮度最高的萤火虫位置，从而实现寻优。

下面为FA的伪代码描述:

2.2 混沌优化

FA对初值敏感，寻优能力主要靠个体间的相互作用，缺乏变异机制，易陷入局部最优且难以摆脱。混沌是非线性系统所特有的一种非周期运动现象，其行为复杂且类似随机，但存在精致的内在规律性，具有内随机性、初值敏感性和遍历性等特点[16]。混沌优化就是利用混沌运动的他特性来提高随机优化算法的效率[17－18]。文献[19]中的已经证明立方映射产生的序列具有较好的均匀性，本文将采用立方映射来初始化种群，文献[20]给出了利用立方映射产生混沌序列的优化过程所包括的两个关键步骤如下:①将混沌空间映射到优化问题的解空间；②利用混沌动态特性实现对解空间的搜索。

本文采用文献[21]提出的一种将混沌空间映射到优化问题解空间的算法:

①对于D维空间的M个萤火虫个体，首先随机产生一个D维向量，该向量作为第一个萤火虫个体，表示为Y＝(y1，y2，…，yd)，其中yi∈[－1，1]，1≤i≤d。

②然后将Y的每一维利用式(6)进行M－1次迭代，生成其余的M－1个萤火虫个体。

③将产生的混沌变量按式(7)映射到解的搜索空间:

Ud和Ld分别表示搜索空间的第d维的上下限，yid是利用式(6)产生的第i个萤火虫的第d维，xid即为第i个萤火虫在搜索空间的第d维的坐标。

2.3 CACOFA算法

根据本文选取的网络模型规模大小，CACOFA算法先随机产生一个40维向量作为第一个萤火虫个体，然后使用式(6)对该向量的每一维进行迭代19次，得到20个萤火虫个体，最后通过式(7)将20个萤火虫个体映射到解空间的20个解。把最终得到的20个解作为FA算法的初始解，通过对网络节点进行聚类得到最优解，由基站向全网广播聚类结果，节点收到数据包后解析出来自己所在的聚类及簇内成员，并创建一个链表存储在内存中；采集数据时，普通节点通过查询当前轮所属的簇头并向其发送数据，同时节点在发送的数据帧中加入自己的标号和当前的剩余能量信息。基站收到簇内所有存活节点的数据后会根据能量信息判断是否需要更换簇头，轮换簇头的阈值条件是簇头节点的平均剩余能量小于普通节点的平均剩余能量。更换簇头时，基站直接查询第一次的聚类结果中选出当前剩余能量最大的节点作为簇头重新进行广播，而不需要重新聚类，这样不仅能均衡簇头节点的负载，同时还降低了运行算法重新聚类带来的网络延迟。算法流程如图2所示:

图2 算法流程

如果簇头分布不合理，那么在数据采集阶段，会带来很大的网络开销，为了使簇头分布的更合理，本算法通过综合考虑簇首数量和簇结构的紧凑性设计适应度函数来优化簇头的分布。本文希望簇结构是比较紧凑的，且较均匀的分布在整个网络，适应度函数F如式(8):

其中分子部分代表所有普通节点到基站的距离的和；分母的第一部分是普通节点到其对应的簇头的距离和，第二部分是簇头到基站的距离和。当簇头均匀的分布在网络中，且节点距离簇头的距离越小，则对应的适应度函数值越大。

2.4 复杂度分析

混沌优化过程中只需要对表示萤火虫向量的维数进行遍历，复杂度可表示为O(M×D)。本文设置萤火虫算法迭代次数为200，适应度函数的计算时间复杂度为O(f)，标准萤火虫算法迭代过程的复杂度为O(M2)，则优化后的萤火虫算法的计算时间复杂度为O(M×D＋200×M2×f)，可简略表示为O(M2)。综上，使用混沌理论优化萤火虫算法与原算法复杂度数量级相同。

2.5 簇间路由

簇头负责簇内所有数据的收集与融合，会消耗比普通节点更多的能量，如果继续使用簇头进行路由，会加剧节点间能耗的不平衡性，造成个别节点过早死亡；同时根据本文采用的簇头轮换条件，簇头能耗过快将导致轮换过于频繁，会增加额外的能量消耗，故本文引入双簇首机制，添加副簇首负责传送数据来均衡主簇头的能耗，减少簇头轮换的次数。本文采用经典LEACH协议中的时分多址通信机制，簇头为每个成员节点划分一个时隙，普通节点在固定的时隙内以单跳的方式向主簇头传输数据。主簇头节点对采集的数据进行融合处理后发送给副簇头并在副簇头间以多跳的方式传输到基站。本文采用最短路径算法中的Bellman-Ford算法确定多跳路径，该算法是一种用于搜索最短路径的图搜索算法[22－23]。为避免单独搜集各个节点的剩余能量会增加额外的能量开销，本文采用文献[9]的数据帧方式，各节点完成数据采集和处理后，将自身剩余能量作为数据添加在数据包中一起路由到基站。

3 仿真与分析

本文使用MATLAB 2016a为仿真工具在相同参数条件下对LEACH算法、EEUC算法、GAFCMCR算法和本文CACOFA算法进行了多项性能对比分析，实验参数设置如表1所示:

表1 仿真参数

图3仿真了LEACH算法、EEUC算法、GAFCMCR算法和本文CACOFA算法的分簇效果，LEACH算法采用概率来选择簇头，从子图(a)可以看出簇头分布和成簇效果都不理想；EEUC采用竞争半径策略来均衡节点负载，如子图(b)，越靠近基站的成簇半径越小，虽然有效的避免了“热区”内的节点较早死亡，但整个网络的生存时间依然较短；GAFCMRA采用遗传算法优化FCM聚类算法来进行网络分簇，虽然有效的延长了网络的生存时间，但从子图(c)可以看出，簇结构存在极大极小簇；而本文提出的CACOFA算法，如子图(d)，簇头分布均匀，且簇结构的大小均匀；靠近基站的节点直接与基站成簇。

图3 算法分簇效果对比图

本文使用簇头包含普通节点的数量表示簇头的负载，多次运行各个算法统计数据如表2。EEUC算法与其他三种算法的思想不同，它是通过非均匀分簇的思想来均衡整个网络的能耗，故此处不通过簇头负载参与比较。通过数据可以看出LEACH算法存在极大簇与极小簇，方差最大；GAFCMRA算法存在极大簇，且方差较大；本文CACOFA算法不存在极大簇或极小簇，簇头负载的方差为3.76，分簇效果最好。

表2 算法的簇头负载

表3给出了各个算法仿真时出现第一个死亡节点的轮数，使用CACOFA算法的网络出现第一个死亡节点的轮数是1 021，比LEACH算法、EEUC算法、GAFCMRA算法分别提高了127%、99%、39%。

表3 出现第一个死亡节点的轮数

图4从死亡节点个数与轮数之间的关系的角度对比了各算法的生命周期，仿真结果表明本文算法CACOFA的生命周期均大于LEACH算法、EEUC算法、GAFCMRA算法；在大约700轮的时候，LEACH算法的节点已经全部死亡；900轮的时候，EEUC算法和GAFCMRA算法的存活节点只剩下总节点个数的约五分之一，而CACOFA算法还没出现第一个死亡节点，表明CACOFA算法可以有效延长网络的生存时间。另外，CACOFA算法的节点从开始死亡到全部死亡经历的时间比较短，只用了150轮左右，说明网络内所有节点的能耗是比较均衡的，验证了算法在均衡簇头负载方面的有效性。

图4 存活节点的个数与轮数的关系

图5和图6分别仿真了网络总剩余能量和运行轮数的关系、普通节点采集数据包与轮数的关系。当运行相同轮数时，CACOFA算法的网络总剩余能量始终最多，而且采集的数据包大于其他三种算法，说明该算法有效的降低了每轮节点传输数据的能耗，使每轮的节点能量开销比LEACH算法、EEUC算法、GAFCMRA算法都要小，从而延长了网络的生命周期。从图6可以看出，CACOFA算法采集的数据包均大于其他三种算法。在大约750轮之前，CACOFA算法采集的数据包个数与其他算法略有浮动，但总体差别不大，在750轮之后，采用其他三种算法的网络均已死亡，CACOFA算法依然可以正常采集数据，进一步验证了CACOFA算法延长网络生命周期的有效性。

图5 网络总剩余能量和轮数的关系

图6 数据包与轮数的关系

4 结论

本文从无线传感器网络的特点出发，为了尽可能的延长网络的寿命，在分簇的思想上从均衡节点负载，降低每轮网络运行所需能耗的角度考虑，提出了基于混沌优化萤火虫算法的WSN分簇算法。在成簇阶段，目标函数充分考虑距离因素，通过混沌优化的萤火虫算法对网络节点进行聚类；在簇头轮换阶段，从聚类结果中选取剩余能量最高的节点作为簇头；在数据传输阶段，采用簇内单跳、簇间多跳的方式进行传输。仿真结果表明，本文提出的CACOFA算法能够有效均衡节点负载，延长网络的生存周期。

在数据路由阶段，本文采用了现有的最短经典路径算法进行仿真，但最短路径只能减小单条链路上的能耗，并不能保证链路上的能耗均衡。下一步工作可通过优化路由算法进一步均衡整个网络的能耗，延长网络的生命周期。