生命周期最大化的无线水质监测网络路由优化研究

申庆祥　张宇华

摘 要：针对区域集中分布的无线水质监测网络，汇聚节点附近的监测节点容易形成数据传输“热点”而过早死亡，造成能量空洞的问题，将改进的量子遗传算法应用于无线水质监测网络的路由优化。通过建立系统的能耗模型，提出相应的量子编码方式和考虑监测节点剩余能量的适应度函数，设计了水质监测网络优化的量子遗传算法，优化了无线水质监测网络数据的传输路径，避免能量空洞现象过早出现。仿真结果表明该方法能够快速获得监测节点到汇聚节点的最佳路径，显著延长了水质监测网络的生命周期。

关键词：无线水质监测网络；能量空洞；网络生命周期；量子遗传算法；路由优化

中图分类号：TP212.9 文献标识码：A

Abstract：In the centralized distribution wireless water quality monitoring network，the monitoring nodes near the sink nodes are easy to form a hot spot of data transmission and come to an untimely end，which causes the energy hole problem.This study adopts the improved quantum genetic algorithm in the route optimization of the wireless water quality monitoring system.With the establishment of the system energy consumption model，the paper proposes a corresponding quantum coding method and the fitness function with the residual energy of monitoring nodes.The water quality monitoring network is optimized to avoid the premature energy hole through the quantum genetic algorithm.The simulation results show that the best route from monitoring nodes to the sink nodes can be quickly obtained through this method，which significantly prolongs the lifetime of the wireless water quality monitoring network.

Keywords：wireless water quality monitoring network；energy hole；network lifetime；quantum genetic algorithm；route optimization

1 引言（Introduction）

基于无线传感器网络的水质监测系统具有监测区域广、容错性能强、可扩展性能好、可远程实时监测和无须复杂布线等特点。由于无线传感器网络的能量消耗绝大部分在无线通信上，许多学者通过对WSN网络的数据传输路径进行优化，从而减少监测节点的网络通信能耗，延长节点的生命周期。WSN网络路径优化问题是NP-hard问题，一些学者采用遗传算法[1]、蚁群算法[2]、粒子群算法[3]和量子遗传算法[4-7]进行优化求解。量子遗传算法的全局优化和高效搜索能力，更适合WSN网络的路径优化。文献[7]采用群体灾变策略，避免量子遗传算法收敛到局部最优解，提高了算法求解成功率。但是该论文采用的量子编码方式在网络规模较大时，极大地增加了算法复杂度，而且以最小能耗为优化目标，并未考虑能量空洞现象对网络生命周期的影响。

在水质监测系统中汇聚节点附近的监测节点容易形成数据传输“热点”，导致这些节点过早死亡，造成“能量空洞”现象[8]，影响网络的生命周期。本文通过建立无线水质监测网络模型和数据传输能耗模型，综合考虑网络的数据传输能耗和节点的剩余能量，优化量子编码方式，改进了文献[7]的量子遗传算法，优化数据传输路径，避免能量空洞现象过早出现，延长网络的生命周期。

2 基于WSN的水质监测系统网络模型（Wireless

water quality monitoring network model）

2.1 WSN网络模型

本文的無线水质监测网络如图1所示，平面区域内部署若干水质监测节点进行水质信息的采集，各个监测节点通过多跳路由形式将采集到的信息传输至汇聚节点，汇聚节点将监测节点采集到的信息通过互联网或其他网络传输至监测中心。

为了便于研究，本文将每一个节点进行编码：1，2，…，n。将网络抽象成一个无向赋权图：。其中，V表示系统节点的集合，E表示节点间通信可达链路集，如式（1）和式（2）所示：

2.2 WSN能耗模型

典型的传感器节点中消耗能量的模块包括传感采集模块、微处理器模块和无线通信模块。文献[9]的实验表明，传感器节点各部分能量消耗的情况如图2所示。

从图2可以看出无线传感器网络绝大部分能量消耗在通信模块。无线通信模块有四种工作状态：发送、接收、空闲、睡眠。其中睡眠状态的能量消耗最少，发送状态的能量消耗最大，合理减少不必要的转发和接收是减少系统能量消耗的关键。传感器节点到发送数据的能耗模型如式（5）所示：

3 水质监测网络路径的优化（Path optimization forendprint

wireless water quality monitoring network）

3.1 量子遗传算法

量子遗传算法充分发挥了量子算法的加速作用，将量子算法和遗传算法进行融合，弥补了传统遗传算法的不足。使用量子的态矢量编码染色体，一条染色体表达为多个态的叠加，从而增加了种群多样性，能够在较小的种群规模下求得最优解。用量子逻辑门实现染色体的更新操作，使当前最优个体的信息能够很容易的引导变异，使得种群以较大的概率向较好的模式进化，从而实现对目标的优化求解。本文应用量子遗传算法研究无线水质监测网络通信的路径优化。主要由量子编码、种群初始化、量子观测、适应度评价、量子门操作等步骤来完成。

3.2 编码

在量子遗传算法中，量子比特是量子计算机中最小的信息单位。一个量子比特可以处于态、态，以及和之间的任意叠加态。因此个量子位可以同时表示个状态，使得量子遗传算法比经典遗传算法具有更多的多样性特征。

对于无线传感器网络的数据传输路径寻优问题，可以采用多种量子编码方式。文献[5]—文献[7]中第代第个量子染色体的编码方式如式（7）所示。

这种编码方式量子染色体的长度会随着无线传感器网络规模的扩大而大大增加，极大地增加算法的计算复杂度，使算法的计算效率急剧下降。

文献[4]采用检测最大范围内可行节点的数目值确定染色体编码方式，这种编码方式需要检测生成的路径是否能够到达汇聚节点和是否存在环路等问题，使得算法的复杂度增加。

3.3 译码

译码的过程是把一个量子个体对应成某个监测节点至汇聚节点数据传输路径。对于一个量子个体译码过程为：首先，令，。选取监测节点作为起始点，从节点的邻居节点中随机挑选一个节点，然后产生一个0到1之间的随机数，若，则为下一个路径节点且令，：若，则重新选择。为避免编码路径出现环路，在一条编码路径中当一个路径节点被选中以后，标记该路径节点，只有未被标记的节点才有可能作为下一个路径节点。从节点的邻居节点中除去已经被选择的节点，在节点的剩余邻居节点中随机挑选一个节点，然后产生一个0到1之间的随机数，若，则为下一个路径节点且令，；若，则重新选择。重复这样选择下一个路径节点，直到所选节点为汇聚节点时停止，这样就可以求得一个矩阵A和一个向量B，向量B对应的就是一个编码的路径，矩阵A对应的就是进行旋转门操作时所需要的个体。

3.4 量子旋转门操作

量子门作为进化操作的执行机构，可以根据具体的问题进行选择。常用的量子门有旋转门、异或门、受控异或门和Hadamard变换门等。本文选择量子旋转门对种群进行更新。旋转门的调整操作如公式（11）所示：

参考基因位的值指目前所求得的最好个体中各个基因位的值。用当代种群中的其他个体与此个体相比较，在相对应的基因位朝目前最好个体的方向转化。对于旋转角度本文取值为，旋转角度的正负表示向正或负方向旋转。

3.5 适应度函数设计

量子遗传算法需要用适应度值表示个体的优劣。对于水质监测系统的网络路径优化，设计适应度函数时应考虑水质监测系统节点的剩余能量、节点间能耗、路径长度等。

3.6 程序流程图

本文程序的流程如图3所示，先对无线水质监测网络的进行初始化操作，包括：节点ID编码、获得各监测节点的邻居节点集合和剩余能量。然后生成若干初始化种群，对种群个体进行一次测量，以获得一组监测节点至sink节点的路径解，根据每个解的适应度值确定当代个体中的最优路径。根据当代最优个体，利用量子旋转门对种群中的个体进行调整，随着迭代次数地增加，使种群的解逐渐向最优解收敛，最终获得监测节点至sink节点最优数据传输路径。本文初始化种群个数选择10个。

4 仿真结果与分析（Simulation results and analysis）

4.1 路径优化结果

为了测试本文量子遗传算法的路径优化性能，选取如图4所示的随机生成的一个20节点的水质监测网络作为本文实验对象。图4中对每个节点进行编号，连线表示所连接的监测点可以直接通信，连线上的数字表示传输数据的能量消耗，初始情况下各监测节点所含能量相同。实验在Intel i3-2348M 2.30GHz CPU、Windows10操作系统、4G内存、Matlab R2015b语言编程环境下进行测试。

为验证了本文算法的优越性，对求解WSN网络路径优化的常规遗传算法[1]、差分进化算法[10]、粒子群算法[3]、文献[7]采用的量子遗传算法和本文的改进的量子遗传算法进行对比分析。为了减少实验随机性对算法性能评估的影响，每种方法做100次实验，取100次实验的平均值作为计算结果。分别考察以下指标：

（1）最优解：每种算法100次实验中所求解的无线传感器路径数据传输消耗能量的最小值。

（2）平均值：每种算法100次实验中所求解的无线传感器路径数据传输消耗能量的平均值。

（3）运行代数：每种算法求得最优解时平均运行代数。

（4）成功率：每种算法100次试验中得到最优解的百分比。

从表2三种算法性能对比表可以看出，本文的量子遗传算法与常规遗传算法、粒子群算法、差分进化算法和文献[7]的量子遗传算法相比，本文量子遗传算法的成功率高，且能在较少的代数内找到最优解。说明本文的量子遗传算法对于无线传感器网络的数据传输路径优化是有效的，且减少了算法运行代数，提高了搜索最优路径的成功率。

4.2 生存周期优化结果

将本文的量子遗传算法与文献[7]量子遗传算法和单跳路由算法进行网络生存周期仿真比较。实验的仿真环境为：在的区域内随机抛洒50个传感器监测节点和1个汇聚节点，令汇聚节点位于处。每個节点的初始能量为，通信半径，节点每次发送数据的长度为，监测节点发送每字节数据的能耗，两种模型下监测节点信号放大器处理每字节数据的能耗、endprint

。本文网络的生存周期定义为网络运行的轮数，当有一半节点能量耗尽时即认为网络死亡。实验仿真结果如图5所示。

由图5可以看出，单跳路由算法在起始阶段一些节点很快死亡，网络在200轮左右已有半数节点死亡。单跳路由算法是监测节点与汇聚节点直接通信，因此与汇聚节点相距较远的监测节点的数据传输过程耗能较大使节点能量过早耗尽，与汇聚节点相距较近的节点数据传输过程耗能较小能维持很长的生存时间。文献（20）的量子遗传算法未考虑监测节点的剩余能耗，在运行450轮左右时网络死亡。本文改进的量子遗传算法在运行600轮左右网络死亡，显著延长的系统的生命周期。

5 结论（Conclusion）

本文针对无线水质监测系统中监测节点的能量空洞现象造成网络过早死亡的问题。从网络路径优化的角度，采用量子遗传算法进行数据传输路径的优化，解决水质监测节点的过早死亡问题，主要表现在：

（1）优化了无线水质监测网络的数据传输路径，采用改进量子遗传算法，提高路径搜寻的成功率，避免收敛到局部最优解；且能够在较少的代数内找到最优路径，路径优化成功率高。

（2）充分考虑各节点的传输能耗和剩余能量等因素，选择最合适的通信路径，避免能量空洞现象过早出现，有效延长了网络生存周期。

参考文献（References）

[1] 雷霖，李伟峰，王厚军.基于遗传算法的无线传感器网络路径优化[J].电子科技大学学报，2009，38（2）：227-230.

[2] 童孟军，关华丞.基于蚁群算法的能量均衡多路径路由算法的研究[J].传感技术学报，2013，26（3）：425-434.

[3] Zhu X，Zhang Y.Wireless sensor network path optimization based on particle swarm algorithm[J].Computer Engineering，2010，3（4）：534-537.

[4] 唐义龙，等.基于量子遗传算法的无线传感器网络路由研究[J].传感器与微系统，2011，30（12）：68-70.

[5] 钱晓华，王俊平.基于量子遗传算法的无线传感器网络路由[J].辽宁大学学报（自然科学版），2010，37（2）：113-115.

[6] 邹少军.基于量子遗传算法的无线传感器网络路径优化[J].计算机测量与控制，2010，18（3）：723-726.

[7] 夏俊，等.基于量子遺传算法的无线传感网络路由优化[J].同济大学学报（自然科学版），2015，43（7）：1097-1103.

[8] Sharma R.Energy Holes Avoiding Techniques in Sensor Networks：A survey[J].2015，20（4）：204-208.

[9] Estrin D，Srivastava M，Sayeed A.Tutorial on Wireless Sensor Networks[J].Technologies Protocols & Applications，

2002，13（4）：317-328（12）.

[10] Xu Yulong，Wang Xiaopeng，Zhang Han.Comparative study on the optimal path problem of wireless sensor networks[C].2016 IEEE International Conference on Mechatronics and Automation，2016：2234-2239.

作者简介：

申庆祥（1990-），男，硕士生.研究领域：无线传感器网络，物联网技术.

张宇华（1975-），男，博士，副教授.研究领域：无线传感器网络，能源管理与节能治理.endprint