基于QEA优化的WSNs簇间路由策略*

余成波，赵西超，杨 佳，田引黎，晏绍奎，代琪怡

（重庆理工大学远程测试与控制技术研究所，重庆 400054）

0 引言

无线传感器网络（wireless sensor networks，WSNs）由于节点能量有限且无法补充，因此，如何高效率地利用传感器节点的能量是WSNs中一个重要问题。传统的单跳通信容易造成节点过早死亡，出现“局部空洞”，缩短网络生存周期等问题;多跳通信方式可减少通信距离，增强网络的稳定性并提高节点能量利用效率，延长网络生存周期，还能满足网络扩展性的需要［1］。但在多跳方式下，距离基站较近的簇头节点由于承担的转发任务较重，容易产生“热点”问题。因此，合理选择跳数和跳选簇头，可以均衡簇头节点能量，避免“热点”问题，延长网络生存周期。

量子进化算法（quantum evolutionary algorithm，QEA）［2］是由量子理论和进化算法（EA）不断融合而发展出来的一种新型优化算法，它基于量子计算的概念和理论，采用量子比特编码染色体，使一个染色体可以表示多个状态的信息;同时利用量子门更新完成进化搜索，因此，具有种群规模小、收敛速度快、全局搜索能力强，具有自适应性等优势，从而引起了国内外的广泛关注。

1996年，Narayanan A最早将量子理论引入到进化算法领域，提出了量子衍生型遗传算法［3］。2000年，Han K H提出遗传量子算法［4］，该算法首次用量子态矢量来编码染色体，利用量子门旋转更新染色体，通过对背包问题的优化，证明比常规遗传算法有更好的优化效果。针对遗传量子算法的不足，Han K H在2002年提出了QEA［5］。

本文在研究了QEA实际应用地基础上，结合WSNs的特点，提出一种基于QEA优化的簇间路由策略，用于均衡簇头节点能耗。在众多均衡簇头节点能耗协议中，能量高效的非均匀分簇（energy-efficient uneven clustering，EEUC）［6］是一个非均匀分簇和簇间多跳路由有机结合的路由协议，使靠近基站的簇的成员数目较小，来达到均衡簇头节点能耗的目的。分布式能量均衡的非均匀分簇（distributed energy-balanced unequal clustering，DEBUC）［7］协议是一种能量高效均衡的非均匀分簇路由协议，有效地节约单个节点能量，延长了网络生存周期。仿真实验表明，相比与以上2种协议，该优化策略可以有效均衡簇间能耗，延长网络的寿命。

1 WSNs能量均衡分簇路由策略

1.1 簇的形成

1.1.1 簇头选取数量确定

设有N个节点均匀分布，分布的区域设为M×M;要生成q个簇头，簇头最优数量采用文献中的方法确定［8］

式中qm为最优簇头节点数量，dt-BS为簇头区域到基站的距离。εam，εamp为不同信道下信号放大的能量损失率（参考1.2节能耗模型）。由式（1）可知，最佳簇头的数量与区域面积、初始节点个数、以及到基站的距离有关。

1.1.2 簇头节点的形成与轮换策略

每个候选簇头节点设置一个竞争半径Rc，用于控制簇头在网络中的分布，使距离基站较近的簇头节点数量较多同时其竞争半径较小［10］

式中dmax和dmin为节点到基站的最大和最小距离，d（Ci）为簇头节点Ci与基站的距离，c为位于0～1之间的常数为预先定义的最大竞争半径。根据公式（2）可知，候选簇头的竞争范围为（1-c）～之间变化。最后形成离基站较近的簇结构较小，并且随着距离的增加数量相应减少［9］。同时，簇头节点采用分布式竞争算法，若候选簇头成功竞选为簇头，则在其半径内所有簇头均不能成为最终簇头，退出竞争过程。簇头节点选举过程中，点处于休眠状态，以减少能耗。

簇头轮换策略在参考LEACH协议的基础上，做了一定的改进［10］。门限T（n）定义为

式中p为网络中簇头节点占总结点数目的百分比，r为当前的轮数;G为在前1/p轮中没有担当过簇头节点的节点集合;mod是求模运算符号。Ecut为节点当前能量，Eint为节点初始能量，可以看出:节点剩余能量较大的节点成为簇头的可能性更大，从而更有利于节点之间的能量均衡［7］。

1.2 能耗模型

能耗模型如图1所示。

图1 节点能耗模型Fig 1 Node energy consumption model

节点能耗主要分为3个方面:数据接收能耗、数据融合能耗和数据发送能耗。由于数据融合能耗较小，可忽略不计。在保证合理信噪比的条件下，建立如下能耗模型。无线通信模块发送和接收kbit数据时能耗分别为ET和ER。Eelec为射频能耗系数，d表示源节点和目标节点之间的距离，节点发送kbit数据的能耗为［8］。

选择2种信道模型进行:一种是自由空间，发射功率以d2衰减，能量损失率为εam;第二种是多路衰减，发射功率以d2衰减，能量损失率为εamp。

节点发送kbit数据时的能耗为

节点在数据通信时总能耗为数据发送和数据接收之和

1.3 QEA优化簇间路由策略的算法描述与流程

优化策略如图2所示。

QEA可以很好地求解函数优化问题，根据以上分析，把该算法用于优化于簇间路由［11］，能均衡簇头节点的能耗。优化步骤如图3所示［12］。

图2 QEA优化簇间路由策略Fig 2 QEA optimal inter-cluster routing strategy

图3 QEA优化流程图Fig 3 Flow chart of QEA optimization

图4 染色体编码示意图Fig 4 Sketch map of chromosome encoding

节点目标函数如下:

网络能量均值函数

能量方差函数

图5 簇间路由路径示意图Fig 5 Schematic diagram of inter-cluter routing path

2 数据仿真与分析

根据图2、图3的流程，结合1.1，1.2节的具体步骤，得出最优簇头节点数量为20个，根据最大竞争半径为R0c，结合分簇算法把簇头节点分成4层，并根据距离基站的远近确定每层簇头节点数量为4，4，5，7，从而染色体长度为:4×4+4×5+5×7=71。

图6对比了4种协议的网络总能耗随仿真时间（轮）的变化曲线，较小的坡度表明较慢的能量消耗速度和较长的生存周期。QEA优化的簇间路由策略的坡度小于EEUC和DEBUC，说明该策略在一定程度上均衡了簇头节点间的能耗。图7给出3种协议能量方差随仿真时间（轮）的变化曲线，该优化策略的簇头节点剩余的能量方差一直很低，表明其能有效地均衡网络簇头节点的能耗。

图6 网络簇头节点能耗变化曲线Fig 6 Energy consumption change curve of network cluster head node

图7 网络簇头节点剩余能量方差变化曲线Fig 7 Residual energy variance change curve of network cluster head node

3 结束语

针对WSNs中不均匀分簇，多跳通信方式存在的“热点”问题，本文提出一种基于QEA优化的WSNs能量均衡的分簇路由策略，该策略在簇头轮换、分簇机制、簇头数量确定都做了一定改进，并根据QEA的特点优化了簇间路由协议。仿真实验表明:该策略提高了网络能量的利用率，有效均衡了簇头节点间的数据转发能耗，一定程度上避免了“热点”问题，延长了网络生存周期。

［1］薛晓亮，齐荣宾，钱 峰.基于能量均衡的WSN多跳非均匀分簇路由算法［J］.华东理工大学学报，2011（3）:352-358.

［2］范胜辉.量子进化算法及其应用研究［D］.南京:南京航空航天大学，2010:2-23.

［3］Narayanan A，Moore M.Quantum-inspired genetic algorithms［C］//Proceedings of the 1996 IEEE International Conference on Evolutionary Computation，ICEC'96，Nogaya:JSME，1996:61-66.

［4］Han K H，Kim J H.Genetic quantumalgorithm and its application to combinatorial optimization problem［C］//Proceedings of the 2000 Int'l Congress on Evolutionary Computation（ICEC），California，2000:1345-1360.

［5］Han K H，Kim J H.Quantum-inspired evolution aryalgorithm for a class of combinatorial optimization［J］.IEEE Trans on Evolutionary Computation，2002（6）:580-593.

［6］Ye M，Li C F，Chen G H，et al.An energy efficient clustering scheme in wireless sensor networks［C］//Proceedings of the 24th IEEE International Performance，Computingand Communications Conference，Phoenix，AZ:IEEE Computer Society，2005:535-540.

［7］蒋畅江，石为人，唐贤伦，等.能量均衡的无线传感器网络非均匀分簇路由协议［J］.软件学报，2012，23（5）:1222-1232.

［8］熊 飞.无线传感网络分簇路由的研究［D］.重庆:重庆理工大学，2012:12-40.

［9］丁 岳，丁 勇，赵国安，等.多约束条件下能耗均衡的WSN路由算法的研究［J］.计算机应用与软件，2012，29（5）:244-247.

［10］王艳丽，杨 顺.基于能量均衡的无线传感器网络算法的改进［J］.微计算机控制，2010（24）:117-119.

［11］邓长春.基于量子进化算法的路由选择［J］.计算机工程应用，2010，46（23）:103-105.

［12］史 峰，王 辉，郁 磊，等.Matlab智能算法30个案例分析［M］.北京:北京航空航天大学出版社，2011:78-87.