基于混沌克隆遗传算法的无线传感器网络低能耗分簇方法

杨瑞，周杰

(石河子大学信息科学与技术学院，新疆 石河子 832003)

无线传感器网络通常由大量传感器节点组成，这些节点随机分布在监测区域内，多数无需基础设施支撑网络运行，并且自组织成簇[1-2]。随着嵌入式和无线通信技术的创新和进步，部分应用场景下的无线传感器网络节点体积已经越来越小。体积的减小使无线传感器网络的应用范围更加广阔，同时也降低了使用成本[3-4]。无线传感器的部署效率较高，同时拥有强大的环境适应能力，因而在国防和军事、智能家居、农业工程、环境监测等众多领域有着广泛的应用[5-6]。

在随机部署方式下，无线传感器网络的传感器节点经常由无人机随机抛洒至指定目标区域。这种随机部署方式虽然降低了部署成本，却无法保证传感器节点分布的合理性，从而导致部分区域出现覆盖空洞或者重叠覆盖的情况，进而导致监测效果不佳以及部分传感器节点能量的浪费[7]。因此，如何对网络进行有效分簇并在确保完成监测任务的同时降低网络能耗，是无线传感器网络研究中的一个重要问题。目前，已有部分专家学者提出许多低能耗分簇算法来优化无线传感器网络通信能耗[8-9]。

王磊[10]提出了一种粒子群算法(Particle Swarm Optimization, PSO)来优化无线传感器网络通信能耗，延长网络的生命周期。该算法虽能有效降低无线传感器网络的能耗，但收敛速度较慢，全局搜索能力较差。蒋华等[11]设计了一种基于改进灰狼优化算法的水下无线传感器网络分簇方案，该方案优化了网络的传输能量消耗，具有计算量小，便于实验的优点，能够有效降低传感器节点间传输数据的通信能耗，但容易陷入早熟收敛，难以通过优化获得较好的分簇结果。

为了解决无线传感器网络节点间数据传输能耗过大，生命周期较短的问题，本文提出了一种基于混沌克隆遗传算法(Chaotic Clonal Genetic Algorithm，CCGA)的无线传感器网络低能耗分簇方案，并建立了相应的目标函数。方案中设计了新的混沌算子和克隆算子，在降低网络通信能耗的同时有效解决了启发式算法收敛慢、运行时间过长等问题。在仿真中，对比了传感器节点数量分别为100、150、200、250时所提算法与常用的PSO和混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)的网络通信能耗。仿真结果表明相比于常用的PSO和SFLA，所提出的CCGA方案可以有效的降低无线传感器网络通信能耗，延长网络生存周期。

1 资料与方法

1.1 无线传感器网络低能耗分簇模型

在本节中，针对无线传感器网络中传感器节点通信能耗的约束，提出了一种低能耗分簇模型。本文研究的无线传感器网络结构如图1所示。

图1 无线传感器网络分簇结构

在无线传感器网络中，分簇即在监测的范围之内划分多个节点簇，每个节点簇内选择一个传感器节点作为簇头节点，并将簇内的其他节点作为感知节点[12-13]。在数据上行阶段，每个感知节点对目标进行感知，在完成感知任务后感知节点将数据上传至该节点簇内的簇头节点。簇头节点汇集簇内感知节点上传来的数据，再直接上传或多跳上传数据至网关节点。在任务下发阶段，感知节点执行的监测任务由网关节点发布到簇头节点，再由簇头节点下发至簇内的感知节点上。

无线传感器网络在发送和接收数据时会产生通信能耗，而通信能耗受到传感器节点间通信距离的影响[14-16]。由于通信能耗和数据传输距离直接相关，合理有效的分簇方式可以有效降低网络通信距离，进而降低网络能耗。由于节点电池能量有限，因此低能耗分簇对于无线传感器网络非常重要。

在无线传感器网络中，发送节点将p比特的数据的传输到接收节点所消耗的通信能耗为：costsend(p,d,i)=Eelec·p+εamp·p·di。其中，costsend(p,d,i)表示两个节点之间的距离为d时，源节点将p比特的数据发送到接收节点时需要的通信能耗。其中，Eelec表示电能参数，εamp表示功率放大参数，i为通信环境质量参数，i的值通常在2到4之间，通常根据通信环境的质量来确定i的取值。一般情况下，通信环境越好，i的值越小。

接收节点接收q比特的数据所需的通信能耗为：costreceived(q)=Eelec·q。其中，costreceived(q)代表接收节点接收q比特的数据时消耗的通信能耗。在本文的仿真实验中，假设q为3072 bit，εamp=100 pJ·bit-1·m-2，Eelec=50 nJ·bit-1，i=3。

1.2 遗传算法

遗传算法(Genetic Algorithm, GA)是一种适合解决复杂优化问题的智能算法，它模仿自然界中物种自然选择过程，具有强大的优化和搜索能力，可用于解决多目标优化问题[17]。遗传算法受达尔文进化论和优胜劣汰生存观念的启发，通过模拟基因随机重组和突变的过程向预定目标完成种群进化。然而，传统遗传算法易陷入早熟收敛，导致算法陷入进化停滞。

本文提出了一种新的CCGA无线传感器网络低能耗分簇方案。算法设计了相应的混沌算子以增强算法的全局搜索能力，并设计了新的克隆选择算子来避免算法陷入局部最优。混沌算子和克隆算子能够有效扩大算法的搜索范围，加快算法的收敛速度，进而完成能量高效分簇，从而有效降低无线传感器网络节点间数据传输所需通信能耗。通过CCGA优化无线传感器网络通信能耗主要步骤如下：

(1)利用混沌算子生成随机的染色体组，并完成CCGA染色体的初始化。

(2)选择优良的染色体作为亲本，以供交叉和变异算子使用。

(3)通过交叉和变异产生一个新种群。

(4)使用适应度函数评估新种群的优劣程度。

(5)使用克隆算子将产生的优秀染色体进行克隆扩增和高强度变异。

(6)使用适应度函数评估克隆算子的结果，淘汰劣等染色体并更新种群。

重复循环，直至达到最大迭代次数则输出最优染色体。

1.3 基于CCGA的无线传感器网络低能耗分簇方法

1.3.1 染色体编码

设计CCGA的第1步是找到合适的染色体编码方案。CCGA的效率部分取决于所采用的编码技术。由于二进制编码具有表示形式简单、表达能力强的特点，本文在低能耗分簇问题编码方案上选择二进制编码。当某向量上对应的二进制编码为数字“1”则表示该向量位置上的传感器节点为簇头节点，当二进制编码为数字“0”时，则表示该向量位置上为感知节点。若染色体的染色体编码为“0100110101”，编码的第2个数字是1，则表示第2个传感器节点是簇头节点。编码中的每个二进制数字为1个基因，例如该染色体中基因数为10，即每个基因代表1个传感器节点，无线传感器网络中传感器节点的数量为10。换句话说，染色体符号长度即为无线传感器网络中传感器节点的数量。

1.3.2 初始化种群

在本文中，将初始种群的大小设置为M，并且假定初始种群中有N个基因，即无线传感器网络中存在N个传感器节点，种群编码可由公式(1)表示：

(1)

式中，Bm表示为第m个染色体，bm,n表示在第m染色体中第n个传感器节点是否为簇头节点，若bm,n=1，表示该传感器节点为簇头节点，否则为感知节点。当无线传感器网络中簇头的数量固定为S，约束条件如公式(2)所示：

(2)

公式(2)约束了无线传感器网络中簇头节点的数量，并且将簇头节点的数量固定为S。例如，当无线传感器网络中的传感器节点的数量为100个时，如果将簇头比例定为10%，则簇头节点的数量为10，即S=10。

在CCGA中，初始化的质量对迭代优化速度会产生很大的影响。CCGA利用混沌序列Logistic映射来丰富初始化种群的多样性，从而加大算法的搜索范围便于找到更优解。混沌映射带来的随机性完全在解空间范围内，并且可以有效提升初始种群的质量，因此可以提升算法的收敛速度。Logistic映射数学如式(3)所示：

Za+1=μZa(1-Za),Za∈[0,1],μ∈(2,4]。

(3)

式中，μ为控制参量，μ的取值一般为4。

1.3.3 适应度计算

本文的目标是最大程度地降低无线传感器网络通信能耗，因此需要根据无线传感器网络的通信能耗评估每个染色体的适应度。对于CCGA中的染色体，其适应度值根据适应度函数计算得出。适应度值越低，染色体的质量越好。在本文中，通过公式(4)计算染色体的适应度值。

(4)

式中，Fit(Bm) 表示第m个染色体的适应度，Bm为第m个染色体，Fit(Bm)即第m个染色体的簇头选择结果所需要消耗的通信能耗，也就是第m种簇头的选择方法的适应度。i为通信环境质量参数，costsend,m,n(p,d,i)为在第m个染色体的方案中第n个传感器节点发送p比特数据到距离为d的传感器节点所需的能耗，而costreceived,m,n(q) 为在第m个染色体的方案中第n个传感器节点接收q比特数据所需的能耗。

1.3.4 选择

CCGA采用轮盘赌选择策略来选择父代染色体，选择程序采用最优染色体保存方法和轮盘赌技术。在轮盘赌中，具有更好的适应度值的染色体更有可能被选中。因此，可以在不同的轮次选择相同的染色体。CCGA根据基于适应度的方式确定被选的概率，进而进行父代的选择，然后将被选的父代染色体用于交叉算子。这样，在种群中适应度更优的染色体更容易被传给下一代。

为了确保具有较低通信能量消耗的染色体被选择的可能性更大，染色体的被选择概率与染色体的适应程度成反比，如公式(5)所示：

(5)

1.3.5 交叉

当完成选择算子后，被选择的染色体被直接转移给交叉算子。交叉算子的目的是搜寻具有更低能耗的染色体。交叉算子是将父代的染色体重新组合为两个新的染色体的启发式过程。算法对B1、B2两个染色体进行交叉运算的过程如下。首先通过逻辑与运算得到B′,B′是将两个染色体中对应位置的布尔代数进行对比，对应位置布尔代数相同则保持不变，不同则变为“0”。例如当B1=[010011001]、B2=[010010110]时，通过逻辑与运算后得到B′=[010010000]。

其次，再对两个染色体进行逻辑与运算得到B″,B″是将B1和B2中对应位置布尔代数相同的位置变成0，不同则变为1，则得到B″=[000001111]

最后，将B″中的“1”随机平均分配到B′中的相应位置，以获得两个由交叉产生的新染色体。如图4所示，B″中的数字“1”平均分配给B′，并且位置是随机的。因此，两个新获得的染色体Bnew1和Bnew2，其中一种的分配方案可以为Bnew1=[010011100]、Bnew2=[010010011]。

1.3.6 变异

在CCGA中，每条染色体上的每个基因都有突变的可能性。变异的主要目标是维持群体内的多样性。考虑到染色体中簇头的数量是恒定的，变异操作以一定概率将染色体中“ 1”的位置随机改变为“0”，并随机选择其中为“0”的位置成为“1”。在CCGA中，设置基因变异概率为0.05。例如B1=[010011001]，随机变异后可以得到B2=[010001011]。

2 结果与分析

在本节中，给出了在无线传感器网络中CCGA与常用的SFLA和PSO方案的仿真结果对比。通过进行仿真实验来验证本文所提出的CCGA低能耗分簇方法的性能。在配置为Intel Core i7-8550U，2.00 GHz，8GB RAM，Win10操作系统的电脑上利用MATLAB R2012a软件测试了该方案的性能。

在仿真中，设置监测范围为100 m×100 m的正方形区域，每个传感器的位置坐标在监测范围内随机生成。CCGA与常用的PSO以及SFLA方案的参数设置根据实验经验所得，其中CCGA和PSO两种方案的迭代次数与种群中染色体数的设置均一致，迭代次数设为100代，种群染色体个数为50。在CCGA中，变异概率和交叉概率分别设置为0.05和0.8。在PSO中，设置学习因子C1=C2=2。在SFLA中，全局迭代次数设置为100代，组内迭代次数设为20代，种群数量为6，子种群中青蛙的个数为5。

无线传感器网络的通信能量消耗由发送能耗和接收消耗组成。在实验中，为了考虑不同传感器节点数量和不同簇头比例对实验结果的影响，针对不同传感器节点数量进行了多次仿真实验。当簇头比例为10%，传感器节点数分别为100、150、200和250时，三种算法的通信能耗仿真结果如图2所示。

当簇头节点比例为10%时，在不同的传感器节点数量条件下，3种启发式算法得出的通信能耗均随算法迭代次数的增加而降低。这3种算法中，CCGA的通信能耗在迭代过程中始终低于常用的PSO与SFLA，且在代数增加时通信能耗下降速度较快。

当传感器节点数量为100时(图2A)，在经过100次的迭代后，CCGA的通信能耗低于常用的PSO和SFLA。CCGA低能耗分簇方案的通信能耗为0.028 10 J，而相同条件下PSO的通信能耗为0.028 18 J，SFLA的通信能耗为0.028 25 J。CCGA优化后的通信能耗比常用的PSO和SFLA分别降低了0.28%和0.53%。这表明了在优化无线传感器网络低能耗分簇中，CCGA搜索能力更强，收敛速度更快。

图2B、C、D分别对比了150、200和250个传感器节点的网络通信能耗，并且得到了类似的结果：当传感器节点为150时，CCGA、PSO和SFLA优化后的通信能耗分别达到0.041 90 J、0.042 01 J和0.042 05 J(图2B)，表明与常用的PSO和SFLA相比，CCGA低能耗分簇方案获得了更低的通信能耗，有效地避免了算法陷入进化停滞。传感器节点数为200，使用CCGA低能耗分簇方案后通信能耗下降到0.055 77 J，而常用的PSO和SFLA仅分别下降到0.055 90 J和0.055 96 J(图2C)。传感器节点为250，CCPEA、PSO和SFLA的通信能耗分别为0.069 61 J、0.069 76 J和0.069 82 J(图2D)。

A:100个传感器节点; B:150个传感器节点; C:200个传感器节点; D:250个传感器节点。图2 WSN通信能耗的对比

表1给出了当传感器节点分别为100、150、200、250时，所提出的CCGA方案相比常用的PSO与SFLA方案网络通信能耗降低的百分比。

表1 CCGA低能耗分簇方案相对PSO和SFLA方案通信能耗降低百分比

3 讨论与结论

3.1 讨论

针对无线传感器网络低能耗分簇问题，设计了系统模型，并给出了计算无线传感器网络通信能耗的适应度函数，提出了一种新的混沌克隆遗传算法。在仿真中随机生成传感器节点的初始位置，在不同传感器节点数量下对三种算法进行仿真实验，随着传感器节点数量的增加，网络的通信能耗变大。

(1)仿真结果表明，与常用的PSO和SFLA两种方案相比，所提CCGA算法的优势如下：随着迭代次数的增加，CCGA优化后的通信能耗更低。当传感器节点分别为100、150、200、250时，CCGA低能耗分簇方案获得的通信能耗均低于常用的PSO和SFLA方案。并且CCGA利用混沌算子生成随机初始种群，扩大了种群的搜索范围，有助于找到更好的解，最终实现了较低的能耗，有效地避免了算法的早熟收敛。

(2)目前常用的PSO和SFLA两种方案的劣势如下：寻优能力差，容易陷入过早收敛等缺点，如当传感器节点数量为250时，当迭代次数到达第20代时，PSO和SFLA的收敛速度显著降低，并且PSO所优化的网络能耗已接近其最优解。

综上所述，由于CCGA低能耗分簇方案实现的能耗更低，其在实际应用中价值更高。因为所提CCGA得到的解更具有稳定性，在不同传感器节点数量条件下均取得了更低的能耗，并且算法具有较强的鲁棒性，可以有效避免算法陷入早期停滞，因此该算法具有广阔的应用前景。通过将所提算法进行推广等措施，可以有效的在实际应用中降低无线传感器网络能耗。

本文所提CCGA方案在降低无线传感器网络通信能耗的同时避免了算法陷入早熟收敛。但是，对于CCGA参数的选择是基于现有研究的经验值范围，难以使算法的性能达到最优。由于参数的敏感性，参数数据的细微变化将影响算法的性能。下一步将对参数进行遍历搜索，从而对参数进行更细微的调整，使算法的性能达到最优。

3.2 结论

(1)本文提出了一种新的混沌克隆遗传算法(CCGA)，设计了新的目标函数，通过合理的低能耗分簇方案对无线传感器网络通信能耗进行了优化。

(2)CCGA中加入的混沌算子和克隆算子能够有效避免算法的早熟收敛和进化停滞问题，同时扩大了优化范围，提升了算法的运行效率。

(3)通过仿真实验与分析，对比了CCGA低能耗分簇方案相对于常用的PSO和SFLA低能耗分簇方案的网络通信能耗。实验结果表明，当簇头比例为10%时，不同传感器节点数量条件下CCGA的通信能耗均低于常用的PSO和SFLA。