第9期
田浩杉：基于量子遗传的蒙特卡洛节点定位算法
125
DOI ;10. 13873/J. 10009787(2017)090125-04
基于量子遗传的蒙特卡洛节点定位算法
浩杉
（兰州交通大学电子与信息工程学院，甘肃兰州730070）
摘要：针对无线传感器网络（WSNs）节点定位的间题，提出了一种量子遗传算法与蒙特-卡洛相结合的定位算法（QCA-MCL）。将QCA应用于MCL中的采样过滤阶段，通过合理的编码方案、译码方案以及量子旋转门对采样区域中随机产生的量子染色体进行操作，提高了样本寻优效率和定位精度，并加快了算法的收敛速度。仿真结果表明：与蒙特-卡洛定位算法相比，提出的QGA-MCL算法能够减少约10.2%的定位误差，同时，算法的收效速度也得到了显著提升。
关键调：无线传感器网络；量子遗传算法；蒙特-卡洛定位算法
中图分类号：TP393
文献标识码：A
文章编号：1000-9787(2017)09-0125-04
Monte Carlo node localization algorithm based on
quantumgenetic
TIAN Hao-shan
(School of Electronic and Information Engineering,Lanzhou Jiao Tong University ,Lanzhou 730070 , China) Abstract: A new node localization algorithm is proposed for wireless sensor networks( WSNs) , which combines quantum genetic algorithm with the Monte Carlo localization( QGA-MCL) . QGA is applied to the sampling filtering stage in MCL. Operate the quantum chromosomes which is random generated in sampling area by reasonable encoding scheme, decoding scheme and quantum rotating gate, Simulation results demonstrate that compared with Monte Carlo localization algorithm, the proposed QCA-MCL algorithm can reduce positioning error about 10. 2 % , and meanwhile, the convergence speed of algorithm is improved significantly
Key words: wireless sensor networks ( WSNs ); quantum genetic algorithm ( QGA) ; Monte Carlo localization(MCL) algorithm
0引言
早在2004年，蒙特一卡洛定位（Monte-Carlolocalization， MCL)算法便由机器人定位中引入到了移动无线传感器网络[-s]（wirelesssensornetworks，WSNs）中进行节点定位，虽然MCL定位算法抛开了节点移动性的干扰，基至节点移动速度越大定位精度越高，但采样成功率很低，并且容易出现粒子退化的间题"]。近年来，很多学者对其进行了改进，文献[8]提出了蒙特-卡洛盒子定位（Monte-Carlolocation boxed，MCB）算法，通过锚箱（anchorbox）和采样箱（sample box)缩小采样区域，从而提高了采样效率。但当观测模型分布在错箱的比重很小时，采样的成功率仍然很低9.18)。文献[11提出了动态静态网络节点定位（mobileandstatic sensornetworklocalization，MSL），算法利用邻居节点中定位精度较高的节点来辅助定位，但其计算过程非常复杂，通信耗能也比较大。文献[12]将DV-Hop引人到了MCL定位
收稿日期：201609-09
中，提出了多跳蒙特-卡洛定位（multi-hop-basedMonte-Carlo localization，MMCL)算法，充分利用了错锚节点的信息，在低错节点密度的网络中表现出了良好的定位性能。上述算法从不同角度对MCL算法进行了改进，但在网络拓扑变化比较频繁的高速移动网络环境下，上述算法的稳定性和网络生存性则存在一定的性能缺陷。
本文在MCL定位算法的基础上引入了一种通过量子遗传的方法来提高寻优效率，即QGA-MCL算法，算法通过新的寻优手段将MCL的样本采集及过滤阶段优化，提高了收敏速度和定位精度。
MCL基本原理
在WSNs监测区域内随机部署P个目标节点和M个错节点。目标节点具有以下特征：节点随机运动；每个节点运动模型独立；节点具有相同的属性。下面将重点关注个目标节点，通过MCL算法来预测该节点位置。算法主要通过预测和过滤2个阶段实现。