-1-
基于量子遗传算法边坡检测无线传感网络优化
王焱 1，孙雁鸣 1，佟维妍 2
1辽宁工程技术大学电控学院，辽宁兴城 （125105）
2 沈阳工业大学工程学院，辽宁辽阳 （111003）
摘 要：将无线传感网络技术结合到露天矿边坡检测系统中，当露天矿边坡出现异常时，及
时将信息传递给监测人员，避免出现不必要的损失。将量子遗传算法应用于边坡检测无线传
感网络的多目标优化设计中，设计了边坡检测网络的组网策略，制定了适当的编码机制，并
结合多方面重要参数，建立了适应度函数。仿真结果表明：基于量子遗传算法的网络设计优
化了能量管理，使网络生命周期达到最长。
关键词：量子遗传算法；适应度函数；无线传感网络
中图分类号: TP
1 引言
露天矿的有效与合理开采深度随着露天开采的延伸而不断增加，边坡暴露的高度、面积
以及维持时间而不断增加。露天矿边坡的稳定直接关系到采矿人员与采矿设备的安全,要确
保露天矿边坡的安全就必须对其进行监测。随着露天矿开挖边坡逐渐增高、开采范围越来越
大,其监测的难度也不断加大、监测精度要求越来越高。如何适应露天采矿对边坡稳定的要
求,更好地确保露天矿边坡安全,探讨优质、高效、高精度的监测方法和技术具有重要的现实
意义。
将无线传感网络应用于露天矿边坡检测的问题，已被众多研究人员所关注。随着科技的
发展，检测的手段也趋于多样化，大致可分为：简易观测法、设站观测法、仪表观测法、远
程监测法[1-2]。为了保证监测的连续性与准确性，采用边坡布置检测网络，进行远程监测已
成为研究的重点。
本文将无线传感网络技术应用于露天矿边坡检测系统。根据露天矿边坡的特殊环境，研
制了无线传感网络的组网模式。与有线网络相比一个最难解决的问题是无线传感网络的能源
受到极大的限制。给网络中的传感器节点更换电池是困难的，因此优化网络的关键任务是延
长网络的寿命。本文采用量子遗传算法等现代全局寻优工具，在保证网络连通，满足最大信
息检测情况下，优化网络的能量管理，使网络的能量消耗达到最少，使网络的生命周期达到
最大。
2 无线传感网络组网策略
网络中节点有四种工作模式，簇头模式，休眠模式，高功率发射模式及低功率发射模式。
确保网络的连通性，设计采用单跳簇结构通讯方式组建无线传感网络。簇头节点处理的信息
比一般节点多很多，而且传递信号的距离较普通节点远，消耗的能量也会比普通节点多，因
此，必须避免节点多次以簇头形式通信。高功率发射节点和低功率发射节点传递的信息的距
离不同，因此高功率节点消耗的能量较低功率节点多。在不影响检测的情况下，不同周期部
分节点以休眠模式工作，这样更加节省能量的损耗[3]。
3 量子遗传算法方法论
遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概
率搜索方法。但传统遗传算法存在着收敛慢，随机性低等缺点。因此将量子计算方法与传统
-2-
的遗传算法相结合，使寻优的效率更高、速度更快。量子遗传算法以量子计算的一些概念和
理论为基础,用量子比特编码来表示染色体,用量子门作用和量子门更新来完成进化搜索。
编码机制
本设计采用单量子比特编码，用一对复数定义一个量子比特位。这样，一条染色体就可
以用如下形式的单量子比特来进行编码。
1 2
1 2
1 2
......
( , ...... )
......
k
k
k
Q q q q
α α α
β β β
⎛ ⎞= = ⎜ ⎟⎝ ⎠
(1)
其中 k 为染色体基因个数，每个基因由一个量子比特位（qk=[αk βk]T）组成。其中 α和
β 分别是|0>和|1>的概率振幅。每个量子比特位为量子比特的叠加态，并不是一个确定的状
态。单从染色体 Q 出发是不能得到确定的编码的。因此需对量子比特编码的每一个基因（概
率振幅）进行一次测量，以获得一组确定编码（|0>或|1>）。传感器节点可能运行在四种模
式，编码如下：休眠节点（|0>|0>），低功率发射节点（|0>|1>），高功率发射节点(|1>|0>)，
簇头节点（|1>|1>）。
量子旋转门
在量子理论中，各个状态间的转移是通过量子门变换矩阵实现的。量子遗传算法在状态
转移过程中加入最优个体的信息来产生旋转门，加快算法收敛。在 0、1 编码的问题中，我
们可以设计下面这种量子旋转算子来加速进化求优：
cos( ) sin( )
WhirlGate( )=
sin( ) cos( )
i i
i
i i
θ θθ θ θ
−⎛ ⎞⎜ ⎟⎝ ⎠
(2)
( , )i i ifθ θ α β= Δ ×
其中 f(αi βi)和 Δθ分别代表旋转的方向和角度，Δθ的选择必须合理，如果 Δθ的取值过
大,算法搜索的网格就很大,容易出现早熟现象,算法易于收敛于局部极值点，反之，如果 Δθ
的取值过小，则搜索速度太慢甚至会处于停滞状态。传统的量子算法在 Δθ值的选择上是采
用固定值的选择方法，一般将 Δθ选择在 π到 π之间。经过反复的实验，发现将 Δθ
作为一个变量会更好的加速全局的寻优。将 Δθ定义为一个与进化代数有关的变量。
Δθ=π×step，式中 step 为可变步长。在 Δθ∈[π π]前提下，选取 1 与最大代数
为起点与终点，再在起点与终点之间合理的选取一个点，通过这三个点做三次样条插值得出
一个函数，通过所求取的函数计算出所有代数所对应的函数值，作为每代的旋转角。通过 Δθ
的变化有效的调整了整个寻优的过程。
函数 f(αi βi)的作用是使算法朝着最优解得方向搜索。具体选择策略如表 1。本文 αi、βi
在第一象限。
表 1 量子旋转门调整策略
Table 1 Quantum whirl gate adjusting strategy
xi bi f（x）>f(b) Δθ ( , )i if α β
0 0 假 0 0
0 0 真 0 0
0 1 假 Δθi +1
0 1 真 Δθi -1
1 0 假 Δθi -1
-3-
1 0 真 Δθi +1
1 1 假 0 0
1 1 真 0 0
其中 xi为当前染色体的第 i 位，bi为当前的最优染色体的第 i 位，f(x)为适应度函数。Δθi
为旋转角度的大小。f(αi βi)为旋转角度的方向，保证算法的收敛。
量子交叉
交叉是指对两个父代个体的部分结构进行重组而生成新个体的操作，通常采用的交叉操
作如单点交叉、多点交叉、均匀交叉、算术交叉等，它们都是限制在两个个体之间。当交叉
的两个个体相同时，它们都不再奏效。本文利用量子的相干特性构造一种新的交叉操作——
全干扰交叉来完成量子遗传算法交叉过程。
适应度函数
经过对无线传感网络模型的构造，找出其中较为重要的三套参数来构成适应度函数，由
多目标函数混合成单个目标函数，各种参数结合到一起形成一个适应度函数。其中部分部分
参数构造参照了文献[4]，下面对各个参数进行介绍。
休眠参数
（1） 休眠节点误差（DSE）
休眠节点误差（DSE） 是用来限制网络中的休眠节点的数量，一个网络休眠节点过多，
就算是很节能，也不能看作是一个好的优化，当网络休眠节点数目超过总结点数 50%时，
此系统视为瘫痪。休眠节点比例在本次应用中被假设为总节点数的 10%。
e if e 0
0
nd nd
DSE n
else
⎧ >⎪= ⎨⎪⎩
(3)
式中：ndom 休眠节点数量；n 节点的总数；nde=ndom-n*
连通性参数
（1） 节点覆盖率（FC）
节点覆盖率（FC）评估整个网络节点工作情况，限制工作节点与非工作节点的比例，
所以 FC 可以取到正值与或负值，在计算适应度的时候可以平衡工作节点与非工作节点的数
量。
nch nhs nls nout ndomFC
n
+ + − −= (4)
（2） 簇中节点个数误差（SCE）
根据簇头的物理特性，每个簇头能够处理的数据和与簇中节点通信的能力是有一定极限
的，这里假设一个簇最多可以有 10 个节点。
⎪⎪⎩
⎪⎪⎨
⎧
≤
>=
∑
=
00
01
nfull
nfull
nfull
n
SCE
nfull
i
i
(5)
-4-
中国科技论文在线
（3） 超限节点误差（SORE）
超限节点误差(SORE)，确保每个节点能与它的簇头通讯。这取决于节点的信号通信能
力。网络中高功率发射节点能覆盖半径为 2 2 个单位长度的圆形区域，低功率发射节点能
覆盖半径为 2 个单位长度的圆形区域。
noutSORE
n nodm
= − (6)
能量参数
（1） 网络总体能量的消耗（OE）
运行能量消耗参数(OE)，指节点在一些特定的运行阶段消耗的能量，它主要取决于传感
器节点的运行模式。簇头节点、高功率发射节点、低功率发射节点消耗能量的比例是20：2：
1，休眠节点为零。这些比例是用来简化分析的，不代表节点在这些运行模式下准确真实的
能量关系。这里能量总体的消耗是我们优化的重点，总体的能量消耗越慢，整个网络工作的
时间也就越长。
20 2nch nhs nlsOE
n n n
= + +
(7)
（2）通讯能量损耗（CE）
指正常运行模式下的节点与簇头通讯的能量消耗。
1 1
inc
k
ji
i j
CE dμ
= =
= ∑∑
(8)
（3） 电池惩罚值（BCP）
网络中不同的节点不同的工作状态消耗的能量是不相同的，为了使网络工作能够达到最
长，因此不希望相同节点一直工作在高消耗的状态下，因此加入 BCP 来影响节点下一周期
工作状态，从而使网络工作时间最长。
[ ] [ ]
[ ]
1
1 1
ngrid
t t
i t
i i
BCP PF
BC=
⎛ ⎞= −⎜ ⎟⎜ ⎟⎝ ⎠∑ (9)
[ ] [ ] [ ]1 1t t t
i i iBC BC BRR
− −= −
在起始的第一代时，由于所有节点都未工作，即当Cyc=1时，不加入电池的惩罚值。因
此，网络的适应度函数最终形式表示如下：
f=1/（a1×DSE+a2×FCa3×SCE+a4×+SORE+a6×CE+a7×BCP） （10）
适应度函数是权重函数，参数的重要性是通过设置适当的加权系数ai:i＝１,2,3…,7来确
定的，经过反复的仿真对权重值进行缩小、放大最终得到：
表 2 权重系数
Table 2 Weight coefficient
a1 a2 a3 a4 a5 a6 a7
900 -50 100 9000 100 1
-5-
中国科技论文在线
4 遗传算法实验
0 50 100 150 200 250 300
1
2
x 10
-3
Generation
F
itn
es
s
AVERAGEFITNESSVALUE
FITNESSVALUE
0 50 100 150 200 250 300
3
4
5
6
Generation
O
pe
ra
tio
na
l E
ne
rg
y
图（a）最优个体与平均适应度函数值图 （b）运行能量损耗参数
(a) The best individual and the average value of fitness function (b) Operation energy loss parameter
0 50 100 150 200 250 300
200
220
240
260
280
300
320
Generation
C
om
m
un
ic
at
io
n
E
ne
rg
y
0 50 100 150 200 250 300
10
15
20
25
30
35
40
45
50
55
Generation
N
um
be
r
nch
nls
nhs
图（c）通讯能量损耗参数图 （d）各节点工作状态
(c) Communication energy loss parameter (d) Each node working condition
图 1 十五个周期网络参数的进化平均进程
Figure 1 the evolution of average process of 15-cycle network parameters
在遗传算法运算300代后，最好的遗传算法的进化过程如图1（a）所示，图中绘制了每
代中最佳个体的适应度曲线和整个种群的平均适应度曲线在15个周期的平均值。从种群的平
均适应度的大体增长可以看出：尽管由于交换算子和旋转算子，曲线存在许多波动，但是总
体上体现出遗传算法对种群的优化。
图 1（b）为系统所消耗的能量的进化过程，可以看出曲线有明显的下降的趋势，最终
趋于平稳。
图 1（c）为系统高功率发射节点与低功率发射节点通信时所消耗的能量，从图中可以
看出，在 120 代时达到一个峰值，之后平稳的下降，因为高、低功率节点与簇头节点比起来
耗能不大，所以并不是主要能量消耗的部分，但是由于一个网络中其工作的数目较多，也必
须对此进行限制，根据我们的实验结果，在该模型下对适应度函数权重进行调整，这一指标
达到 300 以下时为较理想状态。
图 1（d）为在 300 代中节点工作情况的数目统计曲线，可以看出最终簇头节点的数目
保持在 10 个左右。
表 2 列出了量子遗传算法与传统遗传算法单周期的数据，可以通过表格直观的看出量子
遗传算法较传统遗传算法的优势。（GA1,GA2 为传统遗传算法，GA3 为量子遗传算法）
-6-
中国科技论文在线
表2 网络设计的参数值比较
Table 2 Comparison of network design parameters
GA1 GA2 GA3
Generation 1000 500 300
DSE（休眠节点误差） 0 0
FC(节点覆盖率)
OE（运行能量）
CE（通讯能量） 230 323 203
Active（活跃节点） 90 89 90
CH（簇头节点） 14 14 13
HSR（高信号范围节点） 22 29 18
LSR（低信号范围节点） 54 47 59
CH/ Active
HSR/ Active
LSR/ Active
Fitness(适应度值)
通过表 2，可以看出量子遗传算法寻优的效率远远高于传统的遗传算法，量子遗传算法
300 代可以达到传统遗传算法 1000 代的所达到的效果，同时也可以看出传统遗传算法寻优
缓慢。
实验显示，在初始随机群落中节点受到通讯条件的限制，在进化刚开始时，算法总是试
着找到至少满足通讯约束和面向应用的约束状态。随后，能源消耗问题及“成簇”问题的参数
被最优化，尽可能使运行能量消耗最小，簇头节点较少，低功率发射节点的增加等等。
0 10 20 30 40 50 60 70 80 90 100
0
1
NumberOfPeople
B
at
te
ry
C
ap
ac
ity
0 5 10 15
0
Cycle
P
er
ce
nt
ag
e
O
f B
at
te
ry
C
ap
ac
ity
battery<95
battery<90
battery<85
图（a）15 个周期各节点电量剩余图 （b）15 个周期电量低于 95%、90%、85%统计
(a) Remaining power of each node in 15 cycles (b) Statistics of power were lower than 95%, 90%, 85%
respectively in 15 cycles
-7-
中国科技论文在线
0 5 10 15
0
10
20
30
40
50
60
70
80
90
Cycle
N
um
be
r
O
f S
en
so
r
notused
useonce
usetwice
use3times
use4times
图（c）15 个周期节点作为簇头模式工作次数统计
(c) Statistics of the frequency that nodes working in the cluster head mode in 15 cycles
图 2 十五个周期网络参数的进化
Figure 2 Evolution of network parameters in 15-cycle
图 2（a）为 15 个周期 100 个节点电量消耗的情况，通过图 3（a）可以看出 100 个节点
的电量消耗比较平均没有节点有过多的能量消耗，因为是在 15 个周期，所以依然存在稍有
不平均的情况。
图 2（b）为节点能量损耗小于 95%、小于 90%、小于 85%的节点在 15 个周期占系统节
点总数的百分比，明显可以看出，消耗能量大的节点的增长速度明显小于能量消耗小的节点
的增长速度，可以证明整个系统的能量消耗是平均的。
图 2（c）为 15 个周期中节点做簇头模式工作次数统计，可以看出未做过簇头的节点逐
步在减少，而以簇头模式工作 1-4 次的节点数目在增多，以簇头模式工作次数多的节点增长
的速度明显小于以簇头模式工作次数少的节点，从而可以保证能量的消耗平均。
5 总结
本文采用量子遗传算法等现代全局寻优工具，根据我们设计的无线传感网络的组网模
式，进行了编码机制的设计，适应度函数的建立，控制参数的调整等重要工作。网格中的节
点运行于不同的模式，量子遗传算法决定了哪些节点应该作为簇头，哪些节点运行于高信号
或低信号模式，哪些节点处于休眠模式。在最优过程中，休眠误差参数，网络连通参数、能
量参数都被考虑进去，使网络达到综合最优设计。通过量子遗传算法在网络自适应设计中的
应用，优化了网络的能量管理，使网络的生命周期达到最长。
仿真实验结果验证了量子遗传算法的优越性，通过算法的寻优，最终保证了无线传感网
络中节点耗电的平均化，同时也使整个网络耗能趋于最低，最终实现了检测网络生命周期达
到最长。
参考文献
[1] 罗志强.边坡工程监测技术分析[J].公路，2002，第五期：45~48.
[2] 胡厚田.边坡地质灾害的预测预报[M].西南交通大学出版社，.
[3] S. Bandyopadhyay, . Coyle, An energy efficient hierarchical clustering algorithm for wireless sensor
networks, in: IEEE INFOCOM 2003, San Francisco, CA, April 2003.
[4] Konstantinos P. Ferentinos, Theodore A. Tsiligiridis, “Adaptive design optimization of wireless sensor
networks using genetic algorithms”, Computer Networks 51 (2007) 1031–1051.
[5] 周明，孙树栋.遗传算法原理及应用[M].国防工业出版社，1999.
[6] Amol P. Bhondekar*, Member, IAENG, Renu Vig, Madan Lal Singla, C Ghanshyam, Pawan Kapur, “Genetic
Algorithm Based Node Placement Methodology For Wireless Sensor Networks”, Proceedings of the International
-8-
中国科技论文在线
MultiConference of Engineers and Computer Scientists 2009 Vol I IMECS 2009, March 18 - 20, 2009, Hong
Kong.
The optimization of Wireless Sensor Networks in the slope
detection base on quantum genetic algorithms
WangYan1, SunYan-ming1, Tong Wei-yan2
1 Institute of Electrical & control Engineering, Liaoning Technical University, Liaoning Huludao,
(125105)
2 Shenyang University of Technology, Engineering College, Liaoning Liaoyang
(111003)
Abstract
The Wireless Sensor Networks (WSN) technology is employed in the open-pit mine slope detection
system. When the open-pit mine slope is found abnormal, the WSN transmit data to the monitors
timely in case of the unnecessary losses. Quantum genetic algorithm (QGA) is used in the
multi-objective optimization problem of slope detection with WSN. It's for designing networking
strategy of slope detection system. Appropriate encoding mechanism is worked out. Combining with
various important parameters, the fitness function is established. Simulation results show: Energy
management is optimized with the WSN base on QGA and guarantee maximum life span of the
network.
Keywords: genetic algorithms; fitness function; Wireless Sensor Networks
