（计算机应用技术专业论文）基于遗传算法的无线传感器网络节点自身定位算法研究.pdf

摘要 无线传感器网络作为一种新兴技术，在工农业、城市管理、抢险救灾等许多领域都 有重要的科研价值和应用前景，是目前学术界研究的热点问题之一。其中，传感器节点 的定位问题是无线传感器网络中的一个基本和关键问题。 论文首先概述了无线传感器网络定位算法的研究现状。然后，介绍了定位算法的理 论基础，包括定位算法的基本原理、分类和性能评价。在此基础上，分四类对典型的定 位算法进行了讨论。由于定位问题本质上是一个最优化问题，论文重点对基于优化算法 一遗传算法( c a ，g e n e t i ca l g o r i t h m ) 、模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m ，s a ) 、 进化策略( e s ，e v o l u t i o ns t r a t e g i e s ) 和差分进化算法( d i f f e r e n t i a le v o l u t i o n ，d e ) 的四个定 位算法进行了介绍，详细叙述了每个算法的伪代码或步骤，对各自的优点与不足作了较 全面的总结。在分析其问题产生原因的基础上，给出了两个相应的解决方案。一是针对 以上四个定位算法的适应度函数会导致算法定位精度低且复杂度高的问题，适应度函数 中使用带有权值因子的距离未知节点最近的三个锚节点的信息。一方面，使用距离未知 节点最近的三个锚节点信息能减少算法复杂度且精度较高，另一方面，由于测距误差随 着节点间跳数的增大而增大，使用与未知节点到锚节点跳数成反比的权值因子能适当减 少测距误差的影响，因而可以提高定位精度：二是对c a 和s a 进行了深入分析，针对 g a 具有较强的全局搜索性能但容易产生“早熟收敛 现象而陷入局部最优解和s a 具 有摆脱局部最优解的能力但进化速度慢的问题，提出在c a 的选择策略中引入s a 的 m e t r o p o l i s 接受准则得到优化算法g s a ，这样可以改进种群的多样性，避免c a 陷入局 部最优解。最后，将g s a 应用于无线传感器网络的定位问题得到定位算法g s a l ( g e n e t i c a n ds i m u l a t e da n n e a l i n ga l g o r i t h ml o c a l i z a t i o n ) ，用m a t l a b 进行了仿真实验。实验结果 表明，g s a l 具有定位精度高、所需锚节点比率小、受测距误差影响小的特点。因此， g s a l 不仅具有一定的容错性，而且还能在一定程度上节约网络的部署成本。 关键词：无线传感器网络，集中式定位，遗传算法，模拟退火算法，性能评价 r e s e a r c ho ng ab a s e ds e l f - l o c a l i z a t i o na l g o r i t h m i nw i r e l e s ss e n s o rn e t w o r k s s u nm e i l i n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f z h ul i a n z h a n g ，z h a os h i j u i l a b s t r a c t w i r e l e s ss e n s o rn e t w o r k ( w s n ) ，w h i c hi san e wn e t w o r k - t e c h n o l o g y , c a nb ew i d e l y a p p l i e di na 面c u l t u r e ，i n d u s t r y , c i t ym a n a g e m e n t ，r e s c u ea n dr e l i e fw o r k n o w a d a y s ，i ti s b e c o m i n gah o tt o p i ci n w i r e l e s sc o m m u n i c a t i o nr e s e a r c h e s ，a m o n gw h i c ht h es e n s o r s e l f - l o c a l i z a t i o ni saf u n d a m e n t a la n dc r u c i a li s s u ef o rw s n a c c u r a t es e l f - l o c a l i z a t i o n c a p a b i l i t yi sh i g h l yd e s i r a b l ei nw i r e l e s ss e n s o rn e t w o r k f i r s t l y , t h et h e s i sg i v e sab r i e fi n t r o d u c t i o no ft h el o c a l i z a t i o na l g o r i t h r n si nw s n s e c o n d l y , t h et h e o r yo fl o c a l i z a t i o na l g o r i t h m s ，w h i c hi n c l u d e s t h eb a s i cp r i n c i p l e ， c l a s s i f i c a t i o na n dt h ep e r f o r m a n c ee v a l u a t i o no fl o c a l i z a t i o na l g o r i t h mi si n t r o d u c e d t h i s t h e s i ss t u d i e st h et y p i c a ll o c a l i z a t i o na l g o r i t h m si nf o u rc l a s s e s b e c a u s et h en o d el o c a l i z a t i o n i sa no p t i m i z a t i o np r o b l e mi nn a t u r e ，t h ef o u ro p t i m i z a t i o na l g o r i t h m b a s e dl o c a l i z a t i o n a l g o r i t h m s ，w h i c ha r eg e n e t i ca l g o r i t h mb a s e dl o c a l i z a t i o n ( g a l ) ，s i m u l a t e da n n e a l i n g b a s e dl o c a l i z a t i o n ( s a l ) ，e v o l u t i o n a r ys t r a t e g i e sb a s e dl o c a l i z a t i o n ( l e s s ) a n dd i f f e r e n t i a l e v o l u t i o nb a s e dl o c a l i z a t i o n ( r c d e ) a l ef o c u s e do n t h ep s e u d o - c o d eo rp r o c e d u r eo fe a c h l o c a l i z a t i o ns c h e m ei si n t r o d u c e da n da n a l y z e di nd e t a i l s t h ea d v a n t a g ea n dd e f e c to fe a c h l o c a l i z a t i o na l g o r i t h ma r ec o m p r e h e n s i v e l ys u m m a r i z e d t h e nt w or e l e v a n ts o l u t i o n sa r e p r e s e n t e db a s e do nt h ea n a l y s i so fd e f e c t s t h ef i r s to n ei sa d o p t i n g t h en e a r e s t3a n c h o r sw i t h r e s p e c tt oe a c hi n d i v i d u a lu n k n o w nn o d ei nl o c a l i z a t i o na l g o r i t h m ，w h i c hc a nr e d u c et h e a l g o r i t h mc o m p l e x i t ya n di m p r o v et h el o c a l i z a t i o np r e c i s i o n m e a n w h i l e ，t h e a n c h o r i n f o r m a t i o ni sa t t a c h e d 、析t l law e i g h tw h i c hi si n v e r s e l yp r o p o r t i o n a lt ot h eh o pc o u n t b e t w e e nu n k n o w nn o d ea n da n c h o rn o d e 。b e c a u s et h ed i s t a n c em e a s u r e m e n te r r o ri s b e c o m i n gl a r g e rw i t ht h ei n c r e a s i n go fh o pc o u n t t h ew e i g h tc a nr e d u c et h ei m p a c to f d i s t a n c em e a s u r e m e n te r r o r t h es e c o n do n ei si n t r o d u c i n gt h em e t r o p o l i ss e l e c t i o no fs a i n t og a ，w h i c hh e l p si m p r o v et h ed i v e r s i t yo fp o p u l a t i o na n da v o i dg ar u n n i n gi n t ol o c a l o p t i m u ms o l u t i o n t h ei m p r o v e do p t i m i z a t i o na p p r o a c hi sc a l l e dg s a f o rs h o r ta n di ti su s e d f o rl o c a l i z a t i o ni nw s n t h es i m u l a t i o nr e s u l t sr e v e a lt h a tg s a l ( g s al o c a l i z a t i o n ) i sa l l e f f e c t i v el o c a l i z a t i o na l g o r i t h mw h i c hu s e sf e w e ra n c h o r s ，n e e d ss m a l l e rt r a n s m i s s i o nr a n g e o fn o d e ，a n di si n s e n s i t i v et om e 龇e m e mn o i s ef a c t o r s og s a ln o to n l yh a sac e r t a i nf a u l t t o l e r a n c e ，b u tc a nr e d u c ed e p l o y m e n te x p e n s e s k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k s ，c e n t r a l i z e dl o c a l i z a t i o n ，g e n e t i ca l g o r i t h m ， s i m u l a t e da n n e a l i n ga l g o r i t h m ，p e r f o r m a n c ee v a l u a t i o n 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：j 越 日期： 叫年牛月 6 b 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：盗篓丛 指导教师签名：上l 篮j i 衅 1 7 ij 胡：工呷年尹月苫日 喻1 年牛月石日 中国石油大学( 华东) 硕士学位论文 第一章绪论 1 1 引言 随着通信技术、嵌入式计算技术、微电子技术和传感器技术的飞速发展和日益成熟， 价格低、体积小、功耗小，同时具有感知、计算和通信能力的微型传感器开始出现【i 】【2 】【3 1 。 由大量的这类传感器节点通过无线方式组成了无线传感器网络( w i r e l e s ss e n s o rn e t w o r k , w s n ) 。简单的说，w s n 由部署在监测区域内的具有有限通信和计算能力的大量传感器 节点以a dh o e 方式组成，这些节点通过无线通信方式组成一个多跳自组织网络，其目的 是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。w s n 具有远程监控、实时监测、能在恶劣或特殊环境下工作等许多优点，是目前i t 领域的一 个研究热点，它分别被美国商业周刊和m i t 技术评论杂志评为2 l 世纪最重要和 最有影响力的十大新兴技术之一【4 】。 1 2 无线传感器网络节点定位算法的研究背景及意义 作为一个全新的研究领域，w s n 在基础理论和工程技术两个层面向科技工作者提出 了大量的挑战性研究课题，其中w s n 的定位问题是当前的一个研究热点。w s n 的定位 问题可分为两类，一类是w s n 中节点自身的定位，另一类则是w s n 对外部目标的跟踪 定位。其中，节点的自身定位是对外部目标进行跟踪定位的基础【5 l ，? 并对各种应用有着 重要作用。课题主要研究前者，即着重于为w s n 节点的自身定位问题设计一种实用的解 决方案。 w s n 的工作区域很广，可以适用于人类无法接近的恶劣或特殊环境。节点通常被随 机布放在不同的环境中执行各种监测任务，并以自组织的方式相互协调工作。最常见的 是用飞机将传感器节点撒播在指定的监测区域中，而随机布放的节点在监测区域中的位 置是随机的、未知的。因此，实际应用中传感器节点需要在布放后进行自身定位。 传感器节点的定位可能有以下途径：第一，手工配置，即为每个节点手工输入其在 网络中的坐标值，但节点众多会导致耗时较多，因此该方法不可行。第二，为每个节点 配置一个g p s 接收器，节点通过接收多颗卫星的信号来确定自身的位置。g p s 具有定位 精度高、抗干扰能力强、实时性好等优点。但它体积大、价格高、能耗大，并且不能用 于室内，这些因素导致利用g p s 对低能耗的节点进行定位也不可行。 近年来，研究人员寻找到一种可行的对节点进行定位的方法，即针对节点的密集性 第一章绪论 以及其能量、计算、存储和通信能力的有限性等特点，采用一定的机制与算法估计节点 的位置。这一方面可以提高w s n 的性能，另一方面可以降低成本，有利于w s n 的大规 模应用。 1 3 国内外研究现状 随着w s n 技术的发展，w s n 的定位技术受到越来越多的关注。从1 9 9 2 年a t & t l a b o r a t o r i e sc a m b r i d g e 开发出室内定位系统a c t i v eb a d g e l 6 1 至今，研究者们一直致力于该 领域的研究。到目前为止，w s n 自身定位系统和算法的研究大致经过了两个主要阶段 7 1 。 第一阶段主要是基于基础设施的定位系统，代表性的研究成果包括a c t i v eb a d g e ， r a d a r ，a c t i v eb a t ，r a d i o c a m e r a ，a c t i v eo f f i c e ，e a s yl i v i n g ，s p o t o n ，h i b m lt r a c k e r ， p a r ct a b ，s m a r tf l o o r ，s m a r tr o o m s ，w h e r e n e t 等。文献【8 】【9 1 对这些系统作了比较详细 的描述。这些定位系统基于外部基础设施，因此对硬件的要求较高，实现定位的成本也 较高。 第二阶段主要是无需基础设施的定位技术，目前已成为w s n 领域的一个研究热点。 大多数定位算法中未知节点( 需要确定自身位置的节点) 都是利用少量锚节点( 位置已知 的节点，通过人工部署或g p s 系统来确定自身位置) 的位置信息以及到锚节点的距离信息 或与锚节点的连通性信息，按照某种定位机制来估算自身位置。根据定位所采用的方法， 将现有的定位算法大体分为四类：基于连通度的定位算法、基于距离的定位算法、混合 式定位算法和基于优化算法的定位算法。 1 基于连通度的定位算法 基于连通度的定位算法不需要测量节点间的实际距离，仅利用网络的连通性信息计 算节点的位置。由于不需测量节点间的实际距离，因此该类算法不受测距误差的影响。 该类算法中最典型的是2 0 0 0 年b u l u s un 提出的质心定位算法( c e n 们i d 算法) 【1 0 】，c e n t r o i d 算法简单，但其定位精度不高。2 0 0 1 年b u l u s un 改进t c e n t r o i d 算法，提出一种密度 自适应算法h e a p ，通过在锚节点密度低的区域增加锚节点的方法来提高定位精度。由 于距离未知节点越近的锚节点对未知节点位置的影响越大，2 0 0 6 年，陈维克提出加权质 心算法【1 2 1 ，利用加权因子体现各锚节点对估计位置的影响程度。 2 0 0 3 年h et 提土i a p i t t l 3 1 定位算法，该算法简单易行，通讯量和计算量较小，易于 扩展，但a p i t 测试对网络连通性的要求较高。2 0 0 3 年s h a n gy 提出m d s m a p 1 4 1 1 5 】【1 6 1 定 位算法，该算法适合于均匀网络，是较为精确的定位技术。但m d s m a p 要计算所有节 2 中国石油大学( 华东) 硕士学位论文 点间的最短路径，故通信和运算成本都较大，因此只适合短时应用的小规模网络。为解 决m d s m a p 算法仅适合于均匀网络的问题，s h a n gy 又提出了m d s m a p 的分布式版本 m d s m a p ( p ) ，该算法可以更好地适合于非均匀网络。 基于连通性的定位算法虽然定位精度不高，但它在成本、功耗、硬件限制等因素导 致某些应用无法使用测距技术的情况下是一种很好的选择，并且这类算法不受测距误差 的影响。实验证明，粗精度定位对于大多数应用已足够。例如，当定位误差小于节点无 线射程的4 0 时，定位误差对路由性能和目标追踪精确度的影响不大【1 3 。 2 基于距离的定位算法 基于距离的定位算法需要测量或估计节点间的实际距离，然后利用三边测量法、三 角测量法或多边测量法来计算节点位置。常用的测量节点间距离的方法有r s s i ( r e c e i v e d s i g n a ls t r e n g t hi n d i c a t o r ) 1 7 1 、a o a ( a n g l eo fa r r i v a l ) 1 引、t o a ( t i r n eo fa r r i v a l ) 1 9 】和 t d o a ( t i m ed i f f e r e n c eo fa r r i v a l ) t 2 0 1 。r s s i 技术根据无线信号在传播时的强度变化确定 两个节点间的距离。使用该技术虽然符合低功率、低成本的要求，但该技术可能会产生 4 - 5 0 的测距误差【2 l 】；使用a o a 技术不仅能确定节点的坐标，还能提供节点的方位信息， 但该技术易受外界环境的影响且需要额外硬件，在硬件尺寸和功耗上不适合大规模的 w s n ；t o a 技术利用信号传播时间测定源节点与接收节点间的距离，但该技术需要保持 节点间精确的时间同步，因此对传感器节点的硬件和功耗提出较高要求；t d o a 技术通 过比较两种传播速度不同的信号的到达时间差来确定两个节点间的距离。t d o a 技术的 测距误差小、精度高，但该技术对硬件的要求高，成本和能耗使得该技术对低能耗的传 感器网络提出了挑战。通过使用r s s i 、a o a 、t o a 或t d o a 技术测量节点间的距离来估 计未知节点位置的方法定位精度较高，但对节点的硬件提出很高的要求，定位过程中消 耗的能量也较多，因此不适合大规模w s n 的应用。目前常用的方法是利用跳段距离估计 节点间距离。普遍使用的是2 0 0 1 年n i c u l e s e ud 的a p s 算法圆】中使用的d v - h o p 或 d v - d i s t a n c e 方法。其中，d v - h o p 方法利用网络中平均每跳距离来估计节点之间的距离； 而d v - d i s t a n c e 方法使用r s s i 技术测量相邻节点间的距离，然后利用类似距离矢量路由 的方法传播并累计邻居节点间的距离，最终累计得到非邻居节点间的距离。d v - h o p 算 法中未知节点仅从最近的锚节点f 接收平均每跳距离h o p s i z e 。，其它锚节点的消息被忽 略，因此得到的消息不全面。2 0 0 6 年h u a n gq 【2 4 】提出w r e i 曲t e dd v - h o p 算法，即未知节点 不是仅接收最邻近锚节点f 的h o p s i z e j ，而是接收所有锚节点的h o p s i z e , 。为了体现最邻 3 第一章绪论 近锚节点的h o p s i z e , 影响最大，为每个h o p s i z e ，赋一权值，该权值是到锚节点跳数的倒 数。2 0 0 8 年c h e nh y 【2 5 1 对d v 二h o p 算法从两方面进行改进。第一，利用锚节点间的距离 修正d v - h o p 算法中的h o p s i z e j 。第二，利用双曲线方法【2 6 】求解未知节点的坐标，而不是 使用d v - h 0 p 中的三边或多边方法。l a n g e n d o e nk f 2 刀指出，d v h o p 适合于节点分布密集 且均匀的情况，在高度不规则网络中不适合。2 0 0 5 年w o n gs y 针对非均匀网络提出d h l 算法【2 钔，算法中引入节点局部密度的概念。d v h o p 定位算法中有两次洪泛过程，为了 减少通信量，2 0 0 7 年y a n gs w 提出【2 9 i h c r l 算法，该算法在定位过程中仅需一次洪泛过 程。实验表明。h c r l 算法不仅通信量小，而且定位精度较高。 目前，许多定位算法通过增加锚节点的方法来提高算法的定位精度，但增加锚节点 会使网络的硬件代价急剧增大。2 0 0 7 年l i up e i 蜘提出 3 0 】v a m ，a 算法，该算法的基本思 想是将定位精度较高的某些未知节点选为虚拟锚节点，然后利用这些虚拟锚节点和原来 的真实锚节点共同辅助其他的未知节点进行定位。v a n l a 算法可以在不增加实际硬件 代价的条件下提高算法的定位精度。 3 混合式定位算法 现有的大多数定位算法中，未知节点都使用相同的定位技术来估计自身位置。然而， 每种方法都有利弊，不存在适合任何情况的定位算法。近两年有学者提出混合式定位算 j 法。 2 0 0 6 年c h e n gk y 口1 1 将a p s 与p d m 3 2 1 结合得至u a p s + p d m 算法。2 0 0 7 年l u ik s t 3 3 1 将m d s 与p d m 结合得到m d s + p d m 算法。混合式定位算法的精度要高于单一使用某一种 定位算法的精度，但算法复杂度也会相应增大，不适合低功耗的传感器节点。 4 基于优化算法的定位算法 基于优化算法的定位算法的提出是源于定位问题的本质。定位问题本质上是一个基 于不同距离或路径测量值的优化问题，而且已被证明是一个n p 难解的问题【蚓。为了能 够在多项式时间内解决定位问题，现有的大部分工作致力于利用不同的启发式方法或数 学方法来提高定位估计的精度，但效果都不理想。目前遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、 模拟退火算法( s i m m u l a t e da n n e a l i n g ，s a ) 、进化策略( e v o l u t i o ns t r a t e g i e s ，e s ) 、差分进化 算法( d i f f e r e n t i a le v o l u t i o 玛d e ) 等优化算法已成功解决了许多复杂的优化问题。因此， 国内外学者初步提出利用这些优化算法来改善w s n 中节点定位算法的性能，这些算法的 4 中国石油大学( 华东) 硕士学位论文 求解过程本质上是最小化节点的定位误差函数。由于这类定位算法的定位精度高，且不 依赖于所采用的定位方法，因此课题将这类定位算法作为研究重点。 在国外，2 0 0 3 年d u c k e t tt 将同时定位和映射问题定义为全局优化问题，并利用g a 来解决 3 5 1 。2 0 0 5 年，k a n n a n a a 等提出基于s a 的定位算法s a l t 3 6 1 ，s a 的主要特征是可 以尽量避免陷入局部最优解，但s a l 的运行时间非常长，实时性很差，无法应用于拓扑 变化频繁的网络中。2 0 0 5 年，t e r w i l l i g e rm 等提出基于e s 的定位算法l e s s 3 7 ，l e s s 算 法的运行时间较短，但它对网络的连通度有较高要求。2 0 0 6 年，t a mv 和c h e n gk y 提 出利用m o a ( m i c r o g e n e t i c 舢g o r i 岫) 改进a p s 算法【3 8 】【3 9 4 0 i i 鬟j g a l 。由于不需要其他先 验假设或定位方面的知识，该方法通用性好，但该方法需要先利用a p s 进行粗略定位， 然后再利用m 雠行定位优化，这增加了网络的计算量。2 0 0 8 年，c h e h r ia ，f o r t i e rp 等提出基于d e 的定位算法r c d e 4 1 1 ，该算法复杂度较低，但在测距误差大、节点无线射 程r 较小或锚节点比率较低时，算法得到的定位精度较低。 在国内，2 0 0 6 年黄仑 4 2 j 提出了基于g a 的节点定位算法。通过优化初始种群、自适 应调整适应度的选择操作以及加入误差修正算子等方法克服简单遗传算法( s g a ) 局部搜 索能力不强的缺点，提高定位算法的性能。2 0 0 7 年刘利姣【4 3 】分析t s g a 的基本原理并将 其应用在w s n 的定位中。文中采用实数编码、轮盘赌算法和最优保存策略相结合的选择 算子、算术交叉算子等措施来改进s g a ，提高算法的定位精度。2 0 0 8 年，张清国【删提出 基于g a 的定位算法，使用基于下降的单顶点邻居变异操作( s i n g l e v e r t e x - n e i g h b o r h o o d m u t a t i o no p e r a t o r ) 和基于下降的算术交叉操作( d e s c e n d b a s e da r i t h m e t i cc r o s s o v e r o p e r a t o r ) 。以上提到的基于g a 的定位算法虽然取得了较好的性能，但由于没有从根本上 解决g a 存在的“早熟收敛缺陷，所以定位精度和效率不好。 1 4 论文研究内容及创新点 课题研究的主要内容是基于g a 的无线传感器网络定位算法。在研究定位算法基本 原理后，分四类对典型的定位算法进行了讨论。由于定位问题本质上是一个最优化问题， 重点研究了基于优化算法的定位算法g a l ，s a l ，l e s s 和r c d e ，并对各自的优点与 不足作了较全面的总结。在分析其问题产生原因的基础上，给出了两个相应的解决方案。 一是针对以上四个定位算法的适应度函数会导致算法定位精度低且复杂度高的问题，适 应度函数中采用了带有权值因子的距离未知节点最近的三个锚节点的信息。这是论文的 创新点之一。这一方面能减少算法复杂度且精度较高。另一方面，由于测距误差随着节 5 第一章绪论 点间跳数的增大而增大，使用与未知节点到锚节点跳数成反比的权值因子能适当减少测 距误差的影响，提高定位算法的精度。针对g a 具有较强的全局搜索性能但容易陷入局 部最优解而s a 局部优化能力强的问题，提出在g a 的选择策略中引入s a 的m e t r o p o l i s 接受准则，这样可以改进种群的多样性，避免g a 陷入局部最优解。这是论文的另一个 创新点。将改进后的g a 应用于无线传感器网络的定位问题得到定位算法g s a l ( g e n e t i c a n ds i m u l a t e da n n e a l i n ga l g o r i t h r nl o c a l i z a t i o n ) 。最后，仿真实验表明g s a l 具有定位精 度高、所需锚节点比率小、受测距误差影响小的特点，所以g s a l 不仅具有一定的容错 性，而且还能在一定程度上节约网络的部署代价。 1 5 论文组织结构 根据课题内容和所作的主要研究工作，论文的组织结构安排如下： 第一章主要介绍了w s n 定位算法的研究背景及意义、国内外研究现状，论文研究 内容及创新点，并对论文组织结构进行了说明。 第二章讨论了w s n 定位算法的理论基础，包括定位算法的基本原理、分类和性能评 价，为后续的研究工作提供基础。 第三章介绍了四类定位算法，其中重点介绍了基于优化算法的定位算法，为后续的 研究工作提供了重要借鉴。 第四章在详细介绍g a 和s a 的基本原理、主要步骤和流程的基础上，分析g a 和s a 各自的优缺点，采用在g a 的选择策略中引入s a 的m e t r o p o l i s 接受准则的方法改进g a 。 改进后的算法既具有g a 的全局性和并行性，又具有s a 的局部搜索能力，是一种性能 更好的优化算法。 第五章具体介绍基于g s a 的定位算法。本章首先介绍定位算法的数学模型，然 后给出了g s a 算法的具体实现。 第六章介绍了定位算法的仿真实验及分析。首先介绍仿真的网络环境，然后介绍课 题中使用的评价定位算法优劣的性能指标，最后将提出的定位算法与性能较好的两种基 于优化算法的定位算法进行了仿真比较和分析。 最后是总结与展望。该部分总结全文，并提出尚待解决的问题和以后的研究方向。 6 中国石油大学( 华东) 硕士学位论文 第二章定位算法的理论基础 传感器节点的自身定位就是在实际的物理网络中确定一个给定节点的物理位置，它 是许多w s n 应用的基础。由于人工部署节点和为每个节点配备g p s 的方法都不可行，通 常采用的确定节点位置的方法是设计定位算法。现有的大多数定位算法要求网络中有少 数的锚节点，然后利用这些锚节点的位置信息以及其它的距离或连通度信息估算未知节 点的位置。 2 1 定位算法的基本原理 1 基本概念描述 传感器网络中需要定位的节点称为未知节点；而通过人工部署或g p s 系统己知位 置，并帮助未知节点定位的节点称为锚节点。锚节点是绝大多数定位算法的基础【4 5 】。传 感器节点无线射程内的所有其他节点，称为该节点的邻居节点。两个节点之间间隔的跳 段总数，称为两个节点间的跳数。两个节点之间间隔的各跳段距离之和，称为两节点间 的跳段距离。 2 节点定位算法实施的两个步骤 大部分节点定位算法的实施包括两个阶段。第一阶段是测距阶段，测量或估计未知 节点相对于锚节点的距离；第二阶段是定位阶段，依据所获得的锚节点位置信息及测距 信息计算未知节点的位置。该阶段可以对得到的位置进行修正，以提高定位精度和减小 定位误差闱。节点定位算法的主要区别在定位阶段。 3 计算节点位置的数学方法 以二维空间的节点定位为例，当未知节点获得相对于3 个( 或3 个以上) 锚节点的距离 或者角度之后，可使用三边测量法、三角测量法或多边测量法计算自身位置。由于三角 测量法可转化为三边测量法，以下只介绍其他两种算法。 ( 1 ) 三边测量法 当一个节点到至少三个锚节点的估计距离已知时，可使用此方法。该方法将以三个 锚节点为中心的圆的交点作为未知节点的估计位置。如图2 1 所示： 7 第二章定位算法的理论基础 、 c ， ， 图2 1 三边测量法图示 f i 9 2 - 1 t r i l a t e r a t i o ni l l u s t r a t e d 已知三个锚节点a 、b 、c 的坐标分别为( x 1 ) y 。) ，( x 2 ，y 2 ) ，( x 3 ，y 3 ) ，它们到未知节点d 的距离分别为碣，畋，吃，假设未知节点d 的坐标为( 工，y ) 。 则存在下列公式： 厄i 再而= 盔 厄i 再而= 畋( 2 - 1 ) 瓜i 再而= 以 由式( 2 1 ) 可得到节点d 的坐标为： ；=1_22(x毛2一-xx33；2(y：l-y3，)，。二；二i2+y；一；2+刃d32一jd；2x3 2 ( y - y 22 y c 2 2 ， 【- y j )： ，) j 【- x ：一巧+ y ；一；+ 刃一彰j 卜叫 ( 2 ) 多边测量法 实际应用中节点间的测量距离存在误差，图2 1 所示的三个圆会出现无法交于一点 的情况。多边测量法是解决这一问题的常用方法，它也称为极大似然估计法，其原理如 图2 2 所示。 图2 2 多边测量法图示 f i 9 2 - 2m u l t i l a t e r a t i o ni l l u s t r a t e d 8 中国石油大学( 华东) 硕士学位论文 已知节点i ( i = 1 ，2 ，3 ，以) 的坐标为( ，片) ，它到未知节点d 的距离为嘎，设节点d 的 坐标为( x ，y ) ，那么有： f o 一而) 2 + ( y y 0 2 = 匝2 l ( x - x 0 2 + ( y - y 0 2 = 畋2 1 1 【g 一毛) 2 + ( 少一只) 2 = 吃2 从第一个方程开始分别减去最后一个方程，可得： f 五2 一矗2 2 ( x a - x d x + y 2 一2 - 2 ( y l 一只) y = 嘎2 一露2 lx 2 2 一2 2 ( x 2 一吒弦+ 奶2 一2 2 ( 儿- y ) y = 畦2 - d 2 ： 1 ； 【矗- 1 2 一而2 - z ( x - 1 一毛) x + 弘一1 2 一咒2 2 ( 一1 一只) y = 以一1 2 一破2 e 式为线性方程，可表示为：从：b ，其中 a = 2 g 一毛) 2 “一咒) 2 鸲一毛) 2 魄一) 一而) 2 一咒)，6 善要墨墨墨 b 耐心z 吨z ，x ： l y ( 2 - 3 ) ( 2 4 ) ( 2 - 5 ) 由于存在测距误差，合理的线性模型应该是似+ = b ，其中n 为万一1 维随机误差 向量。根据最小二乘原理，x 的值应当使模型误差n = 6 一似达到最小，即通过最小化 q ( x - - i l n l l 2 - - l i b 一似1 1 2 求x 的估计。对q ( x ) 关于x 求导并令其等于零，可以求得节点d 的坐标估计值为： j = 似r 么) 一1 a7 6( 2 6 ) 2 2 定位算法的分类 到目前为止，w s n 节点定位算法的分类还没有一个统一标准，除了前面所提到的分 类方法，定位算法还可分为集中式定位算法和分布式定位算法。 集中式定位算法是指在w s n 中由某个资源不受限的中心节点( 例如一台服务器) 负 责计算每个未知节点的位置，而其它节点只负责将定位所需的信息传送给该中心节点。 分布式定位算法是将计算量均衡的分布给每个未知节点，每个未知节点通过与邻居节点 的信息交换来估算自身位置。 o 第二章定位算法的理论基础 在集中式节点定位中，中心节点可以利用两种信息：一种是锚节点的位置信息，一 种是节点与邻居节点或非邻居节点间的距离信息。邻居节点间的距离可以通过专门的测 距技术( 如r s s i 、t o a 等) 得到；非邻居节点间的距离可以根据w s n 的多跳转发特性，通 过累计多跳路由上相邻节点的距离得到。集中式定位算法的优点是：节点一次性将所需 要的信息发送给中心节点，避免了分布式定位算法中相邻节点间大量的信息交换所带来 的通信开销：计算节点位置的任务由中心节点统一承担，其他节点节省了计算带来的开 销；由于中心节点的计算量和存储量几乎没有限制，因此该类算法可以根据需要进行多 次迭代，获得较精确的估计位置：集中式定位算法从全局角度统筹规划，在网络规模较 大、节点数目较多时，定位精度比传统的分布式算法要高。集中式定位算法的缺点是： 需要事先存在多跳路由，以便各个节点将信息发送到中心节点；通信开销不平衡，中心 节点附近的节点会因为转发信息的开销大而过早地消耗完电能，导致整个网络与中心节 点的信息交流中断；当个别节点失效或有新节点加入时，中心节点需要重新计算所有节 点的位置，这将会浪费前期所获得的节点位置信息，增加网络系统的能耗，缩短w s n 的生命期，因此不适合网络拓扑变化频繁的网络。 分布式定位算法对网络的拓扑变化具有很强的适应性，无须中心节点的支持；然而 对锚节点位置、锚节点密度以及邻节点数目等都有较高要求。 与分布式算法相比，集中式算法需要有中心节点的支持。目前仍有大量应用存在一 个功能较一般节点强大的中心节点，网络拓扑为静态，其中心节点附近的节点不管是否 采用集中式定位都面临着数据转发的压力。在这种情形下，集中式定位算法是一个较好 的选择。 2 3 定位算法的性能评价 w s n 定位算法的性能直接影响其可用性，如何评价其性能一直是个需要深入研究的 问题。目前还没有一个规范化和量化的评价标准。下面定性地讨论几个常用的评价标准， 作为后续定位算法性能考查的参考标准。 1 平均定位误差 未知节点f 的定位误差是算法估计出的节点位置魄，允) 与实际位置( 玉，咒) 之间 的距离。将所有未知节点的定位误差之和求平均值即得到网络中节点的平均定位 误差。为便于在不同的情形中进行比较与分析，论文中将平均定位误差进行规范化处理， 即除以每个节点的无线射程r 。因此，平均定位误差定义为： 1 0 中国石油大学( 华东) 硕士学位论文 e r r o r = 器荟n 厄i 再而 ( 2 - 7 ) 其中，是未知节点总数，( 薯，咒) 和( 毫，或) o = 1 ，2 ，m ) 分别是未知节点f 的实际 坐标和估计坐标，r 是节点的无线射程。 2 锚节点比率 锚节点比率是网络中锚节点个数占节点总数的比率。w s n 中锚节点的位置通常 通过两种手段来获得：人工布署或g p s 定位实现。人工部署锚节点的方式不仅受网络部 署环境的限制，还严重制约了网络和应用的可扩展性。使用g p s 定位，锚节点的费用会 比普通节点高两个数i - s t 4 刀。这意味着网络中即使仅有1 0 的节点是锚节点，整个网络 的价格也将增加1 0 倍。因此，锚节点比率也是评价定位系统和算法性能的重要指标之一。 3 网络连通度 网络中平均每个未知节点的邻居节点个数称为网络连通度【4 舯。判断节点彳i 是 否为节点4 的邻居节点方法：如果节点彳，到节点4 的测量距离小于节点的无线射 程r ，那么节点彳，就是节点4 的邻居节点。网络连通度增大不仅意味着网络部署费 用的增加，而且会因为节点间的通信冲突问题而造成有限带宽的阻塞。 4 容错性和自适应性 通常，定位系统和算法都需要比较理想的无线通信环境和可靠的节点设备。但在真 实的应用场合中常会有诸如以下的问题：外界环境中存在严重的多径传播、衰减、非视 距等问题；网络节点由于周围环境或自身原因( 如电池耗尽、物理损伤) 而出现失效的问 题；外界影响和硬件精度所