基于改进量子遗传算法的WSNs 多路径路由研究

张 兢，王 猛，杨 超

(重庆理工大学电子信息与自动化学院，重庆 400054)

0 引言

无线传感器网络(wireless sensor networks，WSNs)是由大量的具有数据感知、信息处理和通信能力的传感节点组成，与传统网络相比，WSNs节点体积小、规模大，携带的电池能量十分有限。如何最大限度节约网络能量消耗，延长网络的生命周期成为 WSNs研究重点［1］。

在WSNs中，单路径路由协议往往会造成网络能量消耗不均，某个节点或某个区域中节点失效会导致链路断开形成路由空洞，而多路径路由协议通过在源节点与目的节点之间建立多条路径，可以提高传输可靠性和实现负载均衡［2－4］。

WSNs路径搜索问题属于NP问题，量子遗传算法(quantum genetic algorithms，QGA)作为一种概率搜索优化算法，很适于解决高度复杂的非线性问题，与遗传算法(genetic algorithm，GA)相比，其具有收敛速度更快、稳定性更高和更好的全局最优解［5］。鉴于QGA算法强大的搜索能力，本文将改进的QGA算法引入WSNs节能路由算法研究中，通过对指导种群进化的染色体组选取、量子编码、量子旋转门调整策略、适应度函数的选择等方面进行改进，降低网络能量消耗，提高网络的生存时间，并通过实验仿真验证了算法的有效性。

1 多条较优染色体组的设计

QGA算法是20世纪90年代，由Narayanan A和Moore M等将量子理论引入GA算法而提出的，QGA算法对GA算法的编码方式和演化过程进行了改进，算法的收敛速度大大加快。在QGA算法中，每次迭代只选一条最优染色体来指导群体的进化，每条染色体进化时，都以它为演化目标进行旋转操作，那些带有合理信息的其他染色体由于暂时的适应度不高而被淘汰，算法很容易收敛到局部最优解［5－6］。QGA 的信息传播结构如图1所示。

图1 QGA的信息传播结构图Fig.1 Information transmissionmodel of QGA

针对量子遗传算法的不足，可选用多条较优染色体来指导种群的进化，这样既保证了染色体的多样性，算法也不易收敛到局部解。多条较优染色体组的信息传播结构如图2所示。

多条较优染色体组是由适应度函数来评判产生的。对染色体进行评估、测量后，选取适应度最高的m条染色体作为多个较优染色体组成员，每次评估完染色体后，再次选取m个染色体与多个较优染色体组中的m个染色体比较，从中选取最优的m个染色体进行保留，以此保证染色体的多样性。m值的确定与问题解的空间有关，若解空间的局部最优节点多，幅度变化较大，m值要适当增大;反之，则m值要适当减小。

图2 多条较优染色体组的信息传播结构图Fig.2 Information transmission model ofmore excellent chromosomes group

2 改进的量子遗传算法

2.1 球面坐标角度的量子编码

标准的量子遗传算法采用量子比特的编码方式，一个量子比特的状态可为“0”或“1”，也可为2个量子态的叠加态［7］。其状态可表示为|φ〉=α|0〉+β|1〉，α 和 β 满足归一化条件|α|2+|β|2=1。由平面坐标系 α =cosθ，β =sinθ，可得编码方案为

(1)式中:θij=2π × rand，rand 为［0，1］的随机数;i=1，2，3，…，m，m 为种群规模;j=1，2，3，…，n，n 为量子位数［8］。

在(1)式的编码方式下，量子染色体的长度会随着WSNs规模的不断扩大而增加，算法的计算复杂度也随之增加，降低了算法的效率和搜索空间。因此，将问题的解空间映射到半径为1的三维球面坐标系中，量子位的3个坐标可看作3个并列的基因，这意味着每个染色体同时出现3条并列的基因链，相当于搜索解的空间提高了3倍。量子比特球坐标概率幅示意图如图3所示。

设球面上任意一点P的坐标为(xi，yi，zi)，对应原始解空间中某条染色体的一个基因位，由球面坐

标系可知

(2)式中:φ∈［0，2π］;θ∈［0，π］。则由量子比特编码可得，在球面坐标下，P的量子比特的状态为:|P〉=［sinθcosφ，sinθsinφ，cosθ］T。

图3 量子比特球坐标概率幅示意图Fig.3 Amplitude of quantum bit spherical coordinate rate

2.2 动态量子旋转门调整策略

量子遗传算法中，旋转门是最终实现演化操作的执行机构，通常采用的量子旋转门如下

(6)式中:(αi，βi)T和(α'i，β'i)T分别代表染色体第i个量子比特旋转门更新前后的概率幅;θi为旋转角，它的正负决定着算法的收敛方向，它的大小决定算法收敛的速度和效率。若旋转角的幅度过大，易使算法陷入局部最优，若太小，则算法的收敛速度和效率降低，因此，旋转角的选择对算法尤为重要［9－10］。

本文按(7)式对旋转角θi进行自适应动态调整

(7)式中:k1，k2∈(0.001π，0.05π);fmax为种群中最大的适应度值;faverage为每代群体的平均适应度值;f为进行量子更新的个体的适应度值。

当进行量子更新个体的适应度值低于平均适应度值，表示该个体不是优良个体，对其旋转角要采用较大的值，反之，要根据适应度值取相应的旋转角。

2.3 适应度函数

选择一个合理的适应度函数，对路由算法至关重要，在此，基于簇的网络结构模型，以路由能量消耗作为优化目标，构造适应度函数。

传感器节点发送n bit数据所消耗的能量主要分为两部分，即:信号发射电路所消耗的能量和信号放大电路所消耗的能量，可表示为

(8)式和(9)式中:ETe(n)是发送电路所耗能量;ERe(n)是接收电路所耗能量;ξamp是放大倍数;di，j是节点i和节点j之间的信号传输的欧式距离;λ为一常量，在自由空间衰减模型中，λ =2，ξamp=10 pJ/bit·m－2，在两径传输衰减模型中，λ =4，ξamp=1.3 ×10－3pJ/bit·m－4。通信模型的选取与发射器和接收器之间的距离有关。若发射器与接收器距离小于阈值d0，则采用自由空间衰减模型，反之，采用两径传输衰减模型［11］。

因此，在长度为 di，j的信道中，传输 n bit的消息，路径传输过程所消耗的总能量为

(11)式中:Emax为能量消耗最大的路径上所耗能量;Emin为能量消耗最小的路径所耗能量;E(x)为路径x的能量消耗。

2.4 算法流程

1 )生成初始量子个体种群;

2 )对初始量子个体种群进行k次测量，获得k个确定个体;

3 )对k个个体进行适应度评估，取其中最优适应度的个体，作为下一次进化目标;

4 )验证最佳路由条件，确定所得最优个体是否满足，若是，则输出相应的传输路径，算法结束，否则进行第5)步;

5 )保留部分优势个体，再一次进行测量，并进行适应度评估，获得适应度值;

6 )将适应度值与目标值进行比较，根据动态量子旋转门调整策略，对种群进行适应度调整，得到下一代个体;

7 )执行选择、交叉、变异操作;

8 )若获得的新个体适应度大于当前个体的目标值，则将新个体作为种群下一代进化的目标，否则，保持当前目标不变;

9 )遗传代数加1，并返回第4)步。

3 仿真实验与分析

为了验证改进的量子遗传算法(Improved－QGA)在WSNs路由选择中的有效性，在100 m×100 m的范围内随机分布100个无线传感器节点。将基于Improved－QGA算法与基于GA、QGA算法的多路径路由从网络总体能量消耗、网络存活节点数目两个方面进行比较，仿真参数设置如表1所示。

表1 仿真参数设置Tab.1 Set of simulation parameters

图4是3种算法的网络总体能量消耗仿真比较。从图4中可以看出，在算法运行150轮之前，3种算法在网络总体能量消耗方面差距不大，但随着算法运行轮数的增加，Improved－QGA算法在能量消耗上明显优于GA和QGA算法。当网络能量耗尽时，Improved－QGA算法运行了大约470轮，而GA与QGA算法只运行了400轮和430轮。由此可见，Improved－QGA算法更能节省网络的能量损耗。

图4 网络总体能量消耗仿真对比图Fig.4 Simulation comparison of Energy consumption

图5是网络节点存活数目仿真对比图。如图5所示，Improved－QGA算法大约运行200轮时才开始出现死亡节点，而GA和QGA算法出现死亡节点时大约运行150轮和170轮。在死亡节点个数占50%时，Improved－QGA算法运行了约430轮，GA和QGA算法运行约370轮和400轮。当节点全部死亡时，改进的量子遗传算法运行了约470轮，GA，QGA却只运行了400轮和430轮。由此可以看出，Improved－QGA算法明显延长了网络的生存时间。

图5 网络节点存活数目仿真对比图Fig.5 Simulation comparison of living node numbers

4 结束语

本文将改进的量子遗传算法引入到无线传感器网络多路径路由优化中，根据无线传感器网络的特点，提出了一种有效的多路径路由选择策略，通过对

指导种群进化的染色体组选取、量子编码、量子旋转门调整策略、适应度函数的选择等方面进行改进，以无线传感器网络总体能量消耗和网络节点存活数目为性能指标进行了实验仿真。仿真验证表明，采用基于改进的量子遗传算法的多路径路由能有效地减少网络能量消耗，延长网络节点的生存周期。

［1］蔡绍滨.无线传感器网络关键技术的研究与应用［M］.哈尔滨:哈尔滨工业大学出版社，2011:15－18.

CAIShaobin.The research and application of key technology for wireless sensor network［M］.Harbin:Harbin institute of technology press，2011:15－18.

［2］周集良，李彩霞，曹奇英.基于遗传算法的WSNS多路径路由优化［J］.计算机应用，2009，29(2):521－524.

ZHOU Jiliang，LICaixia，CAO Qiying.Multi－path routing optimization forwireless sensor networks based on genetic algorithm［J］.Journal of computer application，2009，29(2):521－524.

［3］ASLAM M，JAVAID N，RAHIM A，et al.Survey of extended LEACH－based clustering routing protocols for wireless sensor networks［C］//High Performance Computing and Communication＆2012 IEEE 9thInternational Conference on Embedded Software and Systems(HPCCICESS).USA:IEEE Press，2012:1232－1238.

［4］杨靖，秦宁宁，徐迈.传感器网络中基于簇的多路径路由协议［J］.南京理工大学学报，2012，1(36):49－54.

YANG Jing，QIN Ningning，XUMai.Cluster－based multipath routing protocol for wireless sensor networks［J］.Journal of Nanjing university of science and technology，2012，1(36):49－54.

［5］唐义龙，潘伟，李念强.基于量子遗传算法的无线传感器网络路由研究［J］.传感器与微系统，2011，12(30):68－70.

TANG Yilong，PAN Wei，LI Nianqiang.Research on wireless sensor networks routing based on quantum genetic algorithm［J］.Transducer and microsystem technologies，2011，12(30):68－70.

［6］钱晓华，王俊平.基于量子遗传算法的无线传感器网络路由［J］.辽宁大学学报，2010，2(37):113－116.

QIAN Xiaohua，WANG Junping.Research on wireless sensor networks routing based on quantum genetic algorithm［J］.Journal of Liaoning university，2010，2(37):113－116.

［7］王宝伟，王洪国.求解路由选择问题的改进量子遗传算法［J］.计算机工程与应用，2008，44(23):114－117.

WANG Baowei，WANG Hongguo.Improved quantum genetic algorithm for routing problem［J］.Computer engineering and applications，2008，44(23):114－117.

［8］钱国红，黄德才.基于3D角度编码的量子遗传算法［J］.计算机科学，2012，8(39):242－245.

QIAN Guohong，HUANG Decai.Quantum genetic algorithm based on angle coding 3D［J］.Computer Science，2012，8(39):242－245.

［9］王宝伟，王洪国.角度编码量子遗传算法［J］.计算机工程与科学，2009，3(31):75－79.

WANG Baowei，WANG Hongguo.An angle－coding chromosome quantum genetic algorithm［J］.Computer Engineering ＆ Science，2009，3(31):75－79.

［10］GHOLAMHOSSEIN Ekbatanifard，REZA Monsefi.A fast multi－objective genetic algorithm based approach for energy efficient QoS－routing in two－tiered wirelessmultimedia sensor networks［J］.Modern Applied Science，2010，4(6):101－112.

［11］GERGELY Treplan，LONG TranThanh，JANOS Levendovszky.Energy efficient reliable cooperative multipath routing in wireless sensor networks［J］.World Academy of Science，Engineering ＆ Technology，2010，6(68):1366－1371.

(编辑:田海江)