一种基于遗传算法的无线传感器网络节点定位技术研究.docx
《一种基于遗传算法的无线传感器网络节点定位技术研究.docx》由会员分享，可在线阅读，更多相关《一种基于遗传算法的无线传感器网络节点定位技术研究.docx（13页珍藏版）》请在冰点文库上搜索。
一种基于遗传算法的无线传感器网络节点定位技术研究
井冈山大学学报（自然科学版
文章编号：
1674-8085（201104-0071-05
一种基于遗传算法的无线传感器网络节点
定位技术研究
*
廖萍，孔翠香
（井冈山大学电子与信息工程学院,江西，吉安343009
摘要：
本文分析了基于误差的最小二乘估计定位原理，提出一种基于遗传算法的无线传感器网络节点定位技术。
建立所有节点的定位误差之和最小的数学模型，利用遗传算法求解模型的最优解，从而得到未知节点的最优的估计位置。
实验仿真结果表明该算法对未知节点的定位精度高，条件简单，适合各种规模的无线传感网络节点的定位。
关键词：
无线传感器网络；定位；遗传算法；锚节点
中图分类号：
TP393.02文献标识码：
ADOI:
10.3969/j.issn.1674-8085.2011.04.018
STUDYONALOCALIZATIONTECHNOLOGYOFWIRELESSSENSOR
NETWORKBASEDONGENETICALGORITHM
*
LIAOPing，KONGCui-xiang
（SchoolofElectronicandInformationEngineering,JinggangshanUniversity,Ji’an,Jiangxi343009,China
Abstract:
WeanalyzetheshortcomingsoftheleastsquaresestimationlocalizationalgorithminWirelessSensor
Network.AnovellocalizationTechnologybasedongeneticalgorithmforWirelessSensorNetworkisproposed.Themathematicalmodelwasbuiltwiththesmallesterrorforallofnodes,andthegeneticalgorithmwasusedtogettheoptimalsolutionofthemodel.Finally,wecangettheoptimalestimatepositionoftheunknownnodes.TheresultsofthesimulationshowthatthelocalizationaccuracyofthealgorithmisefficientforthenodesoftheWirelessSensorNetwork,anditsconditionissimplesothatsuitableforallsizesofwirelesssensornetworks.Keywords:
wirelesssensornetwork;localization;geneticalgorithm;anchornode
0引言
无线传感器网络是由部署在检测区域，具有通信与计算能力的传感器节点组成的自组织分布式网络系统，其作用是协作式的感知、采集和处理网络监测区域内的信息并发送给检测者[1]。
传感器节点采集或感知的数据不知道具体的位置信息是毫无意义的[2]
，因此传感器节点定位技术是无线传感器网络应用中的关键技术之一
[3-4]
。
虽然采用GPS定位系统可以精确得到每个节点
的位置，但高昂的成本使GPS定位不能广泛应用于传感器节点的定位。
现有的无线传感网络定位算法大多依据少量位置已知的锚节点来估计整个网络中未知节点的位置。
常见的无线传感器网络定位算法可分为基于测距[5]的定位算法以及与距离无关的
定位算法。
基于测距的定位算法（如RSSI[6-10]、TOA和TDOA）在定位过程中需要测量节点间的距离或角度信息，该定位算法对节点的硬件要求较高并受测量环境的影响较大。
而无需测距的定位算法在定位过程中无需测量节点间的距离或角度信息，而是
第32卷第4期Vol.32No.4井冈山大学学报（自然科学版
2011年7月July2011JournalofJinggangshanUniversity（NaturalScience71
收稿日期：
2011-04-18；修改日期：
2011-06-10
基金项目：
吉安市重点科技计划项目（吉市科技字[2009]40号
作者简介：
*廖萍（1980-，男，湖南衡阳人，讲师，主要从事计算机应用、计算机网络、无线传感器网络等研究（Email:
jxjgsliaoping@;
孔翠香（1978-，女，陕西渭南人，讲师，硕士，主要从事无线传感器网络、Adhoc网络等研究（Email:
liuyun8888@.
井冈山大学学报（自然科学版
72
采用节点间的估算距离来实现节点的定位，如
RadhikaNagpal等提出Amorphous]
11[定位算法，以
及DvHop算法，这类定位算法硬件成本低、功耗小、
但定位精度较差。
以上定位算法均具有自身的特点，但它们的定位精度都不够理想，且在定位最后阶段均采用最小二乘估计定位算法估算未知节点的位置。
1基于误差的最小二乘估计定位原理
大多数定位算法对未知节点的计算是通过获知三个或三个以上锚节点间的距离，运用最小二乘法估计法估计出未知节点的位置。
最小二乘估计的定位原理可描述为：
当已知k锚节点的位置
（11yx，…，,（kkyx以及它们距离待测节点
（yx之间的距离为1r，…，kr时，可得方程组
222
111222
（（（（k
kkxxyyrxxyyr⎧−+−=⎪
⎨⎪−+−=⎩
（1）
该方程组为非线性方程组，不便于求解，用
（1）式中的前1k−个方程减去第k个方程后，可以得到
AxB=形式的线性方程组，其中
11112（2（2（2（
nnnnnnxxyyAxxyy−−−−⎡⎤
⎢⎥=⎢
⎥⎢⎥−−⎦
⎣
（2）222222
111222222111kkkkkkkkkxxyyrrBxxyyrr−−−⎡−+−+−⎤
⎢⎥=⎢⎥⎢⎥−+−+−⎦
⎣
（3）用最小二乘法估计求未知节点的位置（,xy，但是由于最小二乘法用前1k−个方程减去第k个方程的思路求解，解的精确程度受最后一个方程误差的限制，如果最后一个方程误差较大的话，即使前1k−个方程误差很小，定位结果的误差也会较大。
由此引入误差项，用前1k−个方程减去第k个方程得
1112222221111
11222222111
2（2（_2（2（kkkkkkkkkkkk
kkkkkkxxxyyyeexxyyrrxxxyyyeexxyyrr−−−−−−−+−+−=
⎧⎪−++−⎪⎪
⎨
⎪−+−+−=
⎪⎪−+−+−⎩即：
（iAxeeB+−=
式中（iee−项为误差项，其为1k−维随机误差向量，根据最小二乘原理求解方程使
2
1
k
iieeBAx=−=−∑取值达到最小来求x的估计
值，对上式关于x求导并令其等于0，可以求解出未知节点的最小二乘位置估计
^
1（TTXAAAB−=（4）
该算法依据节点的测距信息进行定位，测距误差的存在可能引起较高的定位误差。
本文从最小二乘估计法出发，引入遗传算法来完成传感器节点定位。
2基于遗传算法的无线传感网络节
点定位
遗传算法是一种借鉴自然界生物的遗传和进化过程而形成的自适应全局随机搜索与优化算法。
它将问题的所有可能解组成一个种群，将每一个可能解视为种群的个体，从选定的初始种群（解）出发，在整个种群空间内随机搜索，按照一定的适应度函数评估每一个体，循环使用选择、交叉、变异三种遗传算子，使问题的解不断进化，直至搜索到最优解。
文献[12]在第1阶段利用采样方法对节点初始位置进行初步估计，在第2阶段采用遗传算法对节点初始位置进行求精；文献[13]用遗传算法优化定位参数；文献[14]用遗传算法对无线传感网络节点定位及求取其路径；本文提出一种新的无线传感网络节点定位算法。
遗传算法完成节点定位的基本步骤如下：
（1个体的编码
编码是把问题的可行解从解空间转换到遗传算法所能处理的搜索空间的转换方法。
目的是为了随机产生一组侯选变量，可以采用多种形式编码（如二进制编码、符号编码与符点数编码），通常采用二进制形式，即用0，1字符串构成一定长度的基因链，表示个体变量，从遗传算法解空间转换问题空间称为解码。
本文对个体的编码采用二进制编码。
二进制编
井冈山大学学报（自然科学版
73
码中我们将每个个体的基因值用1,0（区间均匀分布的随机数来表示，个体位置的纵坐标与横坐标的编码长度均为10位。
（2种群的初始化
假设网络中共有K个未知节点，坐标可表示为
11（,,,（,jjxyxy，（1,2,3,,jK=，第j个未知节点的坐标用向量jX表示，其中N个节点为锚节点，位置11（,,,（,iiabab，（1,2,3,,iN=。
第i个锚节点的坐标用向量jA表示，jX可以与3个锚节点可以通信，设这三个锚节点坐标分别为（,iiab，
（1,2,3i=中的任意三个锚节点，随机产生100M=个个体lM（1,2,3,,100l=作为初始种群，每个个体的位置（,llmc（1,2,3,,100l=。
（3遗传定位算法的适应度函数设置在遗传算法中的适应度函数设为
:
（,min（K
jjjfxy==
（1,2,3,,jK=，（1,2,3,,iN=中的任意三个，其中（,jjxy是第j个未知节点的坐标，（,iiab是第
i个锚节点的坐标，
id是第i个未知节点与锚节点的距离。
这样就将节点定位问题转化为模型优化问题，即上式的最优解即是未知节点的估计位置。
（4选择算子的选取
选择也称为复制，根据变量集中每个个体变量的适应度值或一定概率值对群体中的个体进行选择和淘汰，其目的是为了避免基因缺失、提高计算效率和全局收敛性，产生最优的群体。
因此遗传算法中的优良个性可以一直繁殖下去。
选择算子采用基于适应度的赌轮选择法。
其基本思想是:
每个个体被选中的概率与其适应度大小成正比，设群体大小为100M=，个体i的适应度为（fi，那么个体i被选中的概率pix可表示为：
1
（
（
ixM
ifipfi==
∑，计算所有个体的适应度值，并对它
们按照从大到小的顺序进行排序。
具体的选择方法是依据每个个体的适应度值进行选择：
即适应度值高的个体被遗传至下一代群体中的概率大；适应度
值较低的个体被遗传至下一代群体中概率较小。
（5交叉率的选取
交叉（也叫重组）是在通过较大概率从群体中选择出来的两个不同的个体变量之间互换部分代码（交叉运算或基因重组）。
遗传算法中交叉概率
pc的选择是影响遗传算法性能的关键，pc越大，新个体产生的速度越快，而pc过大时，遗传算法被破快的可能性也越大，使得具有高适应度的个体结构很快被破坏，但如果pc过小，会使搜索过程缓慢或者停滞不前，因此需要不停的反复实验来确定合适的pc来找到问题的最佳解，我们选择个体以概率
0.6cp=进行交叉，也就是选择出来新的个体里面的概率为cp需要进行基因重组，经过重新组合产生下一代新个体，在交叉重组的过程中要尽量避免基因代码差异较小的个体进行交叉，防止“近亲结合”，产生不良个体。
假设交叉前两个选择出来的两个较优个体的编码分别为：
交叉前个体A的编码：
01001011001101010交叉前个体B的编码：
10011010011001101从第16开始到第20位的基因值进行基因重组，那么产生新的个体'A和'B，交叉后它们的编码分别为：
交叉后新的下一代个体'A的编码：
010*********
交叉后新的下一代个体'B的编码：
10011010011101010
（6变异
变异则是从产生新一代的'A和'B个体集合中选择很小一部分的个体（假设变异概率0.01mp=，将个体的基因代码的某一位或者某几位值做改变（变异运算），将个体'A第7位与第12位的基因值进行基因变异，新的个体'A变异前后后它的编码分别为'A与''A，
在二进制编码中的实现方法一般是将基因链中的某些位取反而实现。
变异前个体'A的编码：
01001011001001101变异后形成新的下一代个体''A的编码：
010*********
进行变异的目的是防止某些个体处于不变的状态而失去一些较有用的基因，来参加变异的个体
井冈山大学学报（自然科学版
74
的概率应该很小，我们取pm。
（7这样循环迭代，直到迭代次数达到预定次数，或者群体的解达到最优时，停止迭代。
4仿真实验及算法性能分析
4.1环境及参数设置
为了更好、更准确的评价遗传算法定位优化的优越性，在Matlab7.0环境下进行仿真，遗传算法的参数取值为:
种群规模的初始值为100，交叉概率设置为6.0=cp，变异概率设置为01.0=mp，最大迭代次数设为100，编码长度为10。
从最优值的变化以及定位误差几个方面来观察遗传算法的定位性能。
4.2仿真与结果分析
注：
◇表示锚节点的位置，○表示未知节点的估计位置，*表示未知节点的实际位置
图1遗传算法的定位结果
Fig.1ThelocalizationresultoftheGeneticAlgorithm
从图1可以看出，遗传定位算法的定位误差较小，定位性能很好。
从图2可以看出，每个未知节点的最优值随迭代次数的增加而快速衰减，在迭代次数为30之后最优值几乎衰减为零，故迭代次数选择30即满足定位误差要求。
图2五个未知节点的最优值收敛图
Fig.2Theconvergencefigureofoptimalvalueforfive
unknownnodes
图3五个未知节点的定位误差收敛图
Fig.3Theconvergencefigureoflocalizationerrorforfive
unknownnodes
从图3可以看出每个未知节点的定位误差随迭代次数的增加而快速衰减，在迭代次数为10之后，定位误差趋于稳定，且定位误差的值收敛于10%之下，表明遗传算法的定位误差很小，定位精度很高，能够满足无线传感器节点的定位要求。
5结束语
本文以最小二乘估计法为基础，阐述了一种基于遗传算法的无线传感网络改进定位算法的设计方案，建立了所有节点的定位误差之和最小的数学模型，利用遗传算法求解模型的最优解，从而得到未知节点的最优的估计位置。
实验仿真结果验证了算法的有效性，表明该算法对未知节点的定位精度高，因此本算法具有较好的实用性，适合各种无线
井冈山大学学报（自然科学版
75
传感网络节点的定位。
参考文献：
[1]彭爱平,郭晓松.基于二次栅格扫描的无线传感网络定
位算法[J].传感技术学报,2009,22（11:
1650-1654.
[2]RabacyJJ,AmmerMJ,daSilvaJrJL,etal．Picorodio
SupportsAdHocUltra-lowPowerWirelessNetworking[J].Computer,2000,33（7:
42-48.
[3]KIMS,KOJG,YOONJ,etal．Multiple-objective
metricforplacingmultiplebasestationsinwirelesssensornetworks[A].Procofthe2rdInternationalSymposiumonWirelessPervasiveComputing.Piscataway,USA,2007:
627-631.
[4]李建中,高宏.无线传感器网络的研究进展[J].计算机研
究与发展,2008,45（1:
1-15.
[5]吕睿,阳宪惠.减少无线传感器网络节点定位误差的方
法[J]．清华大学学报,2008，48（S2：
1839-1843.
[6]XLi，HCShi，YShang．AsortedRSSIquantization
basedalgorithmforsensornetworklocalization．The11thInt’lConferenceonParallelandDistributedSystems,Japan,2005.
[7]LUTHYKA,EGRANTD,HENDERSONTC.
LeveragingRSSIforroboticrepairofdisconnectedwirelesssensornetworks[A].Proceedingsof2007IEEEInternationalConferenceonRoboticsandAutomation.
Rome,Italy,2007:
10-14.
[8]BENKICK,MALAJNERM,PLANINSICP,etal.Using
RSSIvaluefordistanceestimationinwirelesssensornetworksbasedonZigBee[A].Proceedingsof15thInternationalConferenceonSystems,SignalsandImageProcessing.Bratislava,Slovakia,2008,303-306.
[9]SHENX,WANGZ,JIANGP,etal.Connectivityand
RSSIbasedlocalizationschemeforwirelesssensornetworks[J].LectureNotesinComputerScience,2005,3645（2:
578-587.
[10]刘学平.无线传感网络RSSI定位算法的研究与应用[D].
西安:
西北大学,2009.
[11]NagpalR,ShrobeH,BachrachJ.Organizingaglobal
coordinatesystemfromlocalinformationanad-hocsensornetwork[C]//2ndInt’lWorkshoponInformationProcessinginSensorNetworks（IPSN’03）,PaloAlto，2003.
[12]章磊,段莉莉．基于遗传算法的WSN节点定位技术[J].
计算机工程,2010,5:
85-87.
[13]王越,张宁.基于遗传算法的无线传感网络定位参数优
化[J].计算机应用与软件,2010,7（27:
91-93.
[14]单曦靓,孙艳.基于遗传算法的WSN移动信标节点定位
及路径求取[J].计算机工程与应用,2010,4（30:
95-97.
升级会员 