无线传感器网络能量高效分簇的一种改进方法

窦佩佩，曾玉琴，卢 毅，马洪亮，徐梦颖，周 杰

(石河子大学 信息科学与技术学院，新疆维吾尔自治区 石河子 832003)

无线传感器网络通常由大量廉价的微型传感器节点构成。无线传感器网络融合了无线通信技术、传感器技术、嵌入式计算技术等关键技术，网络中的传感器节点能够对外部环境中的对象进行监测并采集相关数据[1-2]。随着相关技术的飞速发展，无线传感器网络在军事、医学、农业、工业、环境监测等领域的应用变得更加广泛[3-7]，在防震、航空等特殊领域也表现出了相应价值[8-9]。随着5G技术的蓬勃发展，未来无线传感器网络在智能灌溉、智慧城市等领域将有广阔的发展空间[10-12]。

在无线传感器网络内，传感器节点的部署位置通常较为随机。由于大多数传感器节点体积较小且由电池供电，其能源总量受到限制，故降低网络能耗、提高能源利用率是无线传感器网络的一个重要研究方向。研究表明，采用分簇算法对网络中的传感器节点进行分簇能够有效地降低网络能耗。分簇算法将无线传感器网络内的传感器节点分成若干个节点簇，每一个节点簇中包含多个成员节点和一个簇头节点。簇头节点主要用于汇集数据处理结果和发放监测任务，成员节点主要用于监测。当上行传输数据时，成员节点首先将采集到的监测对象相关数据信息进行处理，然后把处理结果发送给所属簇的簇头节点；在下行传输数据时，各个成员节点接收来自所属簇中的簇头节点发放的监测任务。簇头节点和成员节点在数据传输的过程中会消耗较多能量，因此寻找合适的簇头节点是降低网络通信能耗的关键。

针对如何降低无线传感器网络能耗、延长网络寿命这一问题，文献[13]提出了一种基于模糊聚类和粒子群算法的簇头选择方法，利用模糊算法初始聚类，然后利用粒子群算法选择簇头节点。该算法能够有效地降低节点的死亡率，但当网络中节点的部署密度较大时，算法复杂度也随之增长，算法的搜索效率也跟着下降。文献[14]提出了一种灰狼优化算法，该算法能够有效降低网络能耗，但存在收敛速度不够理想的缺点。文献[15]提出了一种蚁群算法，该算法能够有效缩短收敛时间，但容易陷入局部最优。文献[16]提出了一种基于模糊逻辑的土狼优化聚类方法，先利用模糊逻辑算法获得初始分簇方案，再利用土狼优化算法进行优化；该算法有效延长了无线传感器网络寿命，但分簇方案中的簇头节点分布较为不均匀。文献[17]提出了一种改进的人工蜂群算法进行分簇，该算法能够合理地选出簇头节点，但算法易陷入进化停滞。

针对以上问题，笔者提出了一种基于克隆精英遗传算法的分簇方法，且将其和基于精英遗传算法的分簇方法、基于蛙跳算法的分簇方法进行了仿真比较。从仿真结果中可以看出，基于克隆精英遗传算法的分簇方法能够找到更加合适的簇头节点进行合理分簇，且网络能耗明显低于基于精英遗传算法的分簇方法和基于蛙跳算法的分簇方法。

1 无线传感器网络分簇模型

在监测范围内节点随机分布的无线传感器网络分簇结构如图1所示。在大多数无线传感器网络中，通信能耗占网络能耗总量的一半以上，故分簇时需要重点考虑如何降低发送和接收数据时的通信能耗。将大小为bbit的数据包发送到距离为d的接收节点时所消耗的能量为

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

Es(b，d)=bEelec+bεampdi。

(1)

接收节点接收大小为b的数据包所消耗的能量为

Er(b)=bEelec，

(2)

其中，Eelec表示电子能量参数，εamp表示功率放大参数。i的取值主要取决于所处的环境，周围的环境越差，i的值就越大。通常i的取值范围是[2，4]。

2 基于克隆精英遗传算法的无线传感器网络分簇方法

2.1 克隆精英遗传算法

遗传算法(Genetic Algorithm，GA)最早是由美国的 John Holland于20世纪70年代提出的。它是一种能够在全局中进行寻优搜索的算法，具有随机、迭代和进化等特点。但是它在对簇头节点方案进行选择、交叉和变异操作时，很有可能会破坏原本较好的簇头节点方案，使得新一代簇头节点方案网络能耗可能高于上一代簇头节点方案的网络能耗的情况。为了保证迭代过程中簇头节点方案不断优化，网络能耗越来越低，将克隆算子和精英算子引入遗传算法，以增加最佳总体解决方案的可能性。

2.2 算法流程

基于克隆精英遗传算法的无线传感器网络分簇方法的基本流程是：在拥有一定数量传感器节点的监测范围内，选择一定比例的节点当作簇头节点，接着将未被选择的节点列入距离其最近的簇头节点所在簇内，可以得到在当前的簇头节点方案下的网络通信能耗，然后利用克隆精英遗传算法优化当前的簇头节点方案，通过不断优化使得网络通信能耗越来越小。算法的具体步骤如下，

(1) 编码。克隆精英遗传算法的一个重要步骤就是编码，其将能量高效分簇问题转换为克隆精英遗传算法能够处理的问题。在选择、交叉和变异的过程中，编码的好坏对算法运行效率有着直接的影响。采用二进制向量的方式对节点进行编码，二进制向量中的每一位代表一个传感器节点，也就是代表一个基因位点。

(2) 初始化种群。在基于克隆精英遗传算法的分簇方法中，初始化种群时采用随机生成的方法。例如在一定的监测范围内有m个传感器节点，对这m个传感器节点进行长度为m的二进制编码。从这m个传感器节点中随机选择一定比例的节点作为簇头节点，并将二进制向量中簇头节点对应位置的值设为1，这样该向量就代表了一个个体。以同样的方法依次生成n个个体，这些个体就组成了初始种群，也就是初始的n个簇头节点方案。

(4) 选择。能量高效分簇是一个求解最小值的问题，在基于克隆精英遗传算法的分簇方法中，利用克隆算子对簇头节点方案进行选择。将簇头节点方案按照能耗从小到大进行排序，按照一定的比率克隆能耗较小的簇头节点方案，对克隆后的方案以较高的变异概率实施变异，从而组成新的种群。此时种群是由原种群中最优的几个簇头节点方案经过克隆和变异生成的，能量消耗小的分簇方案尽可能地保留了下来。

(5) 交叉。在使用克隆精英遗传算法解决无线传感器网络分簇问题的过程中，对簇头节点方案进行两两交叉，即随机选择一个交叉点将两个簇头节点方案中的相应基因位点进行交换。若两个簇头节点方案中有部分相同的基因位点，则可能出现交叉后两个方案没有任何变化的情况。为了避免这种情况的发生，先将两个方案中相同的基因位点剔除，然后对剔除相同基因位点后的两个方案进行交叉。交叉后，再将被剔除掉的相同基因位点重新加入到方案中，以保证方案中簇头节点数目和比例不变。种群中的所有个体都按顺序进行两两交叉，这样就通过交叉操作生成了新的种群。

(6) 变异。在解决无线传感器网络分簇问题的过程中，克隆精英遗传算法在变异过程中采用的是随机变异的方法。从种群中随机选择簇头节点方案，然后随机反转方案中的部分基因位点，并将新生成的个体当作新的簇头节点方案，这样就形成了新的种群。在变异时，由1翻转至0的基因位点和由0翻转至1的基因位点数量相同，因此变异操作过程中簇头节点数目和比例不变。

(7) 精英个体的保留和更新。在使用克隆精英遗传算法解决无线传感器网络分簇时，将上一代通信能耗最低的簇头节点方案与当前迭代过程中通信能耗最低的簇头节点方案进行对比。如果上一代最低通信能耗高于当前迭代过程中的最低通信能耗，那么就将本代精英个体更新为当前迭代过程中通信能耗最低的簇头节点方案，否则直接将上一代精英个体作为本代精英个体。

(8) 迭代结束。判断基于克隆精英遗传算法的分簇方法迭代过程是否结束时，如果达到设定的迭代次数时，就结束迭代并输出精英个体作为最优簇头节点方案；否则，重复选择交叉变异等操作过程。

3 仿真及结果分析

在无线传感器网络中，大部分传感器节点上行发送数据的通信能耗远大于其接收下行控制指令时的通信能耗，所以在此仿真实验中只考虑节点在上行发送数据时的通信能耗。实验在Windows 10系统、 酷睿i5处理器、 8 GB内存的PC机上，通过Matlab R2015b软件进行仿真。在仿真实验中，设置簇头节点的比率为10%，网络能耗利用式(1)计算。公式中的各个参数的取值为，数据包大小b的值取为1 KB，i的值取为3，Eelec的值取为50 nJ/bit，εamp的值取为100 pJ/(bit·m-2)。

在400 m×400 m的监测范围内随机部署传感器节点，利用基于克隆精英遗传算法的分簇方法、基于精英遗传算法的分簇方法和基于蛙跳算法的分簇方法对WSN的网络能耗进行优化。所提分簇方法中基因位点设为100个，变异概率设为0.1，过高的变异概率容易使算法陷入局部最优。基于精英遗传算法的分簇方法中基因位点设为100个，变异概率设为0.1。基于蛙跳算法的分簇方法中青蛙种群数设为20个，每个种群有5只青蛙，组内迭代数为10。

图2和图3是传感器节点数为100和200时，基于克隆精英遗传算法的分簇方法、基于精英遗传算法的分簇方法和基于蛙跳算法的分簇方法选出的簇头节点产生的能耗随迭代次数的变化。从图2中可以看到，基于克隆精英遗传算法的分簇方法的最低能耗约为1.475 8 J，基于精英遗传算法的分簇方法的最低能耗约为1.557 9 J，基于蛙跳算法的分簇方法的最低能耗约为1.643 2 J。基于克隆精英遗传算法的分簇方法优化结果比基于精英遗传算法的分簇方法的优化结果好约5.27%，比基于蛙跳算法的分簇方法优化结果好约10.19%。从图3中可以看到，基于克隆精英遗传算法的分簇方法的最低能耗约为1.102 2 J，基于精英遗传算法的分簇方法的最低能耗约为1.178 5 J，基于蛙跳算法的分簇方法的最低能耗约为1.517 1 J。基于克隆精英遗传算法的分簇方法优化结果比基于精英遗传算法的分簇方法的优化结果好约6.47%，比基于蛙跳算法的分簇方法优化结果好约27.35%。基于克隆精英遗传算法的分簇方法在降低网络能耗上的效果明显比另外两种分簇方法分簇方法好，对延长网络寿命有显著作用。

图2 能耗对比(传感器节点数为100)

图3 能耗对比(传感器节点数为200)

为了更加直观地看到3种分簇方法选出的簇头节点的分布情况，利用3种分簇方法对100个传感器节点进行分簇，结果如图4至图6所示。从图4至图6中可以看出，利用所提方法和基于精英遗传算法的分簇方法选出的分簇方案中，簇头节点分布较为均匀。而利用基于蛙跳算法的分簇方法选出的簇头节点分布较为不均匀，部分簇头节点之间的距离较近。图7为3种分簇方法对100个传感器节点进行分簇的成簇情况，一条数据表示一个簇中的成员节点数。在图7中可以看到，所提方法的分簇方案中每个簇内的成员节点数目较为平均，基于精英遗传算法的分簇方法的分簇方案中成员节点数目较不平均，而基于蛙跳的分簇方法中成员节点数目不一。综上所述，基于克隆精英遗传算法的分簇方法的分簇方案，簇头节点分布均匀，成员节点数目平均，比另外两种分簇方法的分簇方案更为合理。

图4 基于克隆精英遗传算法的分簇方法分簇结果

图5 基于精英遗传算法的分簇方法分簇结果

图6 基于蛙跳算法的分簇方法分簇结果

图7 3种分簇方法的分簇结果对比(100个节点)

表1为图2和图3中3种方法的运行时间对比。从表1中可以看出，基于蛙跳算法的分簇方法的运行时间最长，且随着网络节点密度的增加，运行时间也增加得更多。基于克隆精英遗传算法的分簇方法的运行时间比基于精英遗传算法的分簇方法的运行时间略小，但其最终优化的网络能耗低于基于精英遗传算法的分簇方法的，即基于克隆精英遗传算法的分簇方法在保证优化效果的同时，拥有较低的时间复杂度。

表1 运行时间对比 s

4 结束语

为了有效提高能源利用率、降低无线传感器网络能耗，笔者给出了一种基于克隆精英遗传算法的分簇方法，用来找出合适的簇头节点以降低无线传感器网络的通信能耗。将基于克隆精英遗传算法的分簇方法与基于精英遗传算法的分簇方法、基于蛙跳算法的分簇方法分别从不同节点数下能量消耗、簇头节点分布、簇内成员节点数目以及运行时间进行仿真比较。仿真结果显示，基于克隆精英遗传算法的分簇方法在优化网络能耗上的效果优于基于精英遗传算法的分簇方法和基于蛙跳算法的分簇方法，有效地延长了网络寿命，且分簇结果中簇头节点分布与簇内节点数较为合理，算法运行时间较短。