（计算机应用技术专业论文）基于直方图分布估计算法的无线传感器网络定位技术.pdf

基于直方图分布估计算法的无线传感器网络定位技术 摘要 论文题目：基于直方图分布估计算法的无线传感器网络定位技术 专业：计算机应用技术 硕士生：刘伟莉 指导教师：张军教授 摘要 节点定位问题是无线传感器网络( 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 定位技术研究 领域的新热点。 分布估计算法( e s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m , e d a ) 是一种结合了统计 学习理论和遗传算法原理的新型智能优化算法，它通过对概率模型的更新和采样 操作来实现种群的进化。与其他智能优化算法相比，e d a 的最大不同是用概率 模型来捕捉问题空间的可行区域，这种更具有统计意义的进化方式使其在求解高 维复杂的问题时能获得较优秀稳定的性能。w s n 定位问题不但维数高( 即待定 位的节点多) ，而且应用环境复杂( 受噪音的影响大) ，因此采用e d a 来求解 w s n 定位问题是一个很有意义的尝试。本文根据现实应用的高精度和高鲁棒性 要求，提出了一种基于直方图分布估计算法( h i s t o g r a mb a s e de s t i m a t e d d i s t r i b u t i o n a l g o r i t h m , h e d a ) 的无线传感器网络定位技术，其核心是带自适应局 部优化的直方图分布估计算法( h e d a l ) 。h e d a l 设定每个个体由对所有未知 节点的估计坐标组成，算法流程主要包括初始化、模型采样、模型更新和自适应 局部优化四个过程。第一步的初始化过程首先将整个监测区域均匀离散化成若干 个小区域，然后根据已知的测量距离近似估计出每个未知节点分布在各小区域的 基于直方图分布估计算法的无线传感器网络定位技术 摘要 概率，并为每个未知节点构建一个对应的直方图模型来描述其分布在各小区域的 概率。第二步的采样过程是在已建立的直方图模型上，通过逐一采样所有未知节 点的估计位置来生成一个新个体，进而产生新一代的种群。第三步的模型更新过 程则先在当前种群选择部分优秀个体，然后统计已选个体中每个未知节点落入各 小区域的频率，并以此更新相应的直方图模型。第四步的自适应局部优化过程为 局部优化解的质量，在当前最优个体的一定半径范围内进行重复探索，并根据每 代的优化效果来自适应调整探索半径的缩放。后面三个过程按序循环进行，从而 实现了种群的迭代进化。 仿真实验设计了多种不同场景下的测试案例，并将h e d a l 与b i s w a s 提出 的半定规划( s e m i d e f i n i t ep r o g r a m m i n g ，s d p ) 算法进行比较。实验结果表明， h e d a l 在测距误差较大的环境中依然能够获取比s d p 算法有更高精度的定位 结果，从而验证了本文所提出算法的有效性。我们还对h e d a l 算法的主要参 数对其性能的影响进行分析，实验结果验证了h e d a l 的鲁棒性。 关键词：无线传感器网络、节点定位、直方图、分布估计算法、测距误差 n w i r e l e s ss e n s o rn e t w o r kl o c a l i z a t i o nt e c h n i q u eb a s e d0 1 1h i s t o g r a me s t i m a t e dd i s t r i b u t i o na l g o r i t h ma b s t r a c t t i t l e ：w t r e l e s ss e n s o rn e t w o r kl o c a l i z a t i o nt e c h n i q u eb a s e do n h i s t o g r a me s t i m a t e dd i s t r i b u t i o na l g o r i t h m m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n i q u e n a m e ：w 色i l il i u s u p e r v i s o r ：p r o f j u nz h a n g a b s t r a c t n o d el o c a l i z a t i o ni st h ef o u n d a t i o no ft h ew i r e l e s ss e n s o rn e t w o r k ( w s n ) a p p l i c a t i o n s t r a d i t i o n a l l o c a l i z a t i o n a l g o r i t h m s c a l lb e m a i n l y c l a s s i f i e di n t o r a n g e f r e e a n d r a n g e - b a s e d m e t h o d s t h e r a n g e - f le e m e t h o d sh a v el o w e r r e q u i r e m e n t st ot h eh a r dw a r e sa n dt h el o w e rl o c a l i z a t i o na c c u r a c y m e a n w h i l e ，t h e r a n g e b a s e dm e t h o d sh a v eh i g h e rl o c a l i z a t i o na c c u r a c y , b u ts u f f e rf r o mh i g h e r s e n s i t i v i t yt ot h ed i s t a n c em e a s u r e m e n te r r o r s a st h ed i v e r s i f i c a t i o na n dt h e c o m p l i c a t i o n o fa p p l i c a t i o ne n v i r o n m e n t sd e v e l o p ，t o om a n yc o n s t r a i n t sb r i n g g r o w i n gc h a l l e n g e st ot h et r a d i t i o n a ll o c a l i z a t i o nt e c h n i q u e s h e n c e ，r e s e a r c h e r sh a v e i n t r o d u c e dv a r i o u si n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ，s u c ha st h eg e n e t i ca l g o r i t h m ( g a ) a n dt h es i m u l a t e da n n e a l i n g ( s a ) ，i n t ot h el o c a l i z a t i o nt e c h n i q u e s s u c h i n t e l l i g e n to p t i m i z a t i o nb a s e dl o c a l i z a t i o na l g o r i t h m su s u a l l yh a v eas i m p l ea n d g e n e r a la l g o r i t h mf r a m e w o r k w 乱hs a t i s f y i n gl o c a l i z a t i o nr e s u l t s ，t h e yh a v ea l r e a d y b e c o m eah o ts p o ti nt h er e s e a r c hf i e l do fw s nl o c a l i z a t i o nt e c h n i q u e s t h ee s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m ( e d a ) i san e wb r a n c ho ft h ei n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s i ti sa l s oac o m b i n a t i o no ft h es t a t i s t i c a ll e a r n i n gt h e o r ya n d t h eg a p r i n c i p l e ，w h i c hi m p l e m e n t st h ee v o l u t i o nt h r o u g ht h eu p d a t ea n ds a m p l i n g o p e r a t i o n so nt h ep r o b a b i l i s t i cm o d e l c o m p a r e dw i t ho t h e ri n t e l l i g e n to p t i m i z a t i o n a l g o r i t h m s ，t h ed i s t i n c tf e a t u r eo ft h ee d ai st h a tt h ep r o m i s i n ga r e a si nt h es e a r c h s p a c ea r ec a p t u r e db yap r o b a b i l i s t i cm o d e l t h i ss t a t i s t i c a l l ys o u n dm a n n e re n s u r e s a ne x c e l l e n ta n dr o b u s tp e r f o r m a n c eo ft h ee d af o rs o l v i n gt h eh i g h l yd i m e n s i o n a l a n dc o m p l e xp r o b l e m s s i n c et h ew s nl o c a l i z a t i o np r o b l e mn o to n l yh a sah i g h 1 1 1 w i r e l e s ss e n s o rn e t w o r kl o c a l i z a t i o nt e c h n i q u eb a s e do nh i s t o g r a me s t i m a t e dd i s t r i b u t i o na l g o r i t h ma b s t r a c t d i m e n s i o n ( i e ，t h el a r g en u m b e ro fu n k n o w l ln o d e s ) ，b u ta l s oh a sc o m p l e x a p p l i c a t i o ne n v i r o n m e n t s ( i ，e t h ep o s s i b l ei n f l u e n c eo fn o i s e s ) ，i ti sam e a n i n g f u lt r y t ou s et h ee d af o rt h ew s nl o c a l i z a t i o np r o b l e m a c c o r d i n gt ot h ea p p l i c a t i o n r e q u i r e m e n t s ，t h i sp a p e rp r o p o s e saw s nl o c a l i z a t i o nt e c h n i q u eb a s e do nt h e h i s t o g r a m - b a s e de s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m ( h e d a ) f o rh i g h l ya c c u r a t ea n d h i g h l yr o b u s tl o c a l i z a t i o nr e s u l t s t h ec o r eo ft h i sn o v e lt e c h n i q u ei sah e d a b a s e d l o c a l i z a t i o na l g o r i t h mw i t ha na d a p t i v el o c a lo p t i m i z a t i o n ( h e d a l ) t h eh e d a li s m a i n l yc o m p r i s e do ft h e f o u r f o l l o w i n gp r o c e s s e s t h e f i r s t p r o c e s s i st h e i n i t i a l i z a t i o n ，w h i c hf l r s t l yd i s c r e t i s i z e st h ew h o l em o n i t o r i n ga r e aa v e r a g e l yi n t o s e v e r a ls m a l lg r i d s ，a n dt h e ne s t i m a t e st h ep r o b a b i l i t yo fe a c hu n k n o w nn o d ei n c l u d e d i ne v e r yg r i db yu s i n ga l lk n o w nd i s t a n c e s t h er e s u k i n gp r o b a b i l i t i e so fe a c h u n k n o w nn o d ea r em o d e l e db yar e l a t i v eh i s t o g r a mi nt h i sp a p e r t h es e c o n dp r o c e s s i st h es a m p l i n go p e r a t i o n , w h i c hg e n e r a t e so f f s p r i n gb ys a m p l i n gf r o mt h eh i s t o g r a m s t h et h i r dp r o c e s si st ou p d a t et h eh i s t o g r a m sb ya n a l y z i n gt h ec u r r e n tp o p u l a t i o n f i r s t l y , ac e r t a i nn u m b e ro fb e s ti n d i v i d u a l si nt h ec u r r e n tp o p u l a t i o na r es e l e c t e d t h e nt h es t a t i s t i c f r e q u e n c yo fe a c hu n k n o w nn o d ei n c l u d e d i ne v e r y g r i d i s c a l c u l a t e da c c o r d i n gt ot h e s es e l e c t e di n d i v i d u a l s f i n a l l y , a i m i n ga tf i n d i n gh i g h l y a c c u r a t es o l u t i o n , a na d a p t i v el o c a lo p e r a t i o ni su s e dt oe x p l o r et h eb e s t s o - f a r i n d i v i d u a li ne v e r yg e n e r a t i o n t h el a s tt h r e ep r o c e s s e sc y c l ei no r d e rt oi m p l e m e n t t h ei t e r a t i v ee v o l u t i o no ft h ep o p u l a t i o n s t i m u l a t e d e x p e r i m e n t sc o m p a r e t h eh e d a lw i t hb i s w a s se x c e l l e n t s e m i d e f i n i t ep r o g r a m m i n g ( s d p ) l o c a l i z a t i o na l g o r i t h mi nv a r i o u ss c e n e s e x p e r i m e n t a lr e s u l t ss h o wt h a t t h ep r o p o s e dh e d a lc a ng i v em o r ea c c u r a t e s o l u t i o n sp e r f o r m a n c ei nt h ee n v i r o n m e n t sw i t hn o i s yd i s t a n c e t h ep a r a m e t e r a n a l y s i sh a sa l s od e m o n s t r a t e dt h er o b u s t n e s so f t h eh e d a l 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 , n o d el o c a l i z a t i o n , h i s t o g r a m , e s t i m a t e d d i s t r i b u t i o n a l g o r i t h m ，d i s t a n c em e a s u r e m e n te r r o r i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：型堡弱 日 期：至迓q 箜笪且2 堕一 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：寥l 伟萄 日期：2 d 口年月2f t 谚争日琶、乌姒 名 。 签 币l 辨鬻 基于直方图分布估计算法的无线传感器网络定位技术 引言 引言 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k , w s n ) 是由大量具有特定功能的 传感器节点通过自组织的无线通信方式，相互传递信息，协同完成特定功能的智 能专用网络【1 】。传统的计算机处理模式主要为人机交互，而无线传感器网络的 诞生将打破这种模式，使之扩展为人、计算机与物理世界三者之间的交互【2 】。 无线传感器网络通过传感器感知和收集物理世界的信息，并通过与人和计算机的 交互对物理世界做出反馈。交互模式的扩展极大地提高了人类认识世界和改造世 界的能力，对与之相关的众多应用领域也将产生深远的影响。虽然无线传感器网 络的诞生只是近十年的事情，但它已经成功地应用于环境科学 2 】、交通管理【3 】、 医疗卫生【4 】、军事反恐、空间探测和灾害监测等领域【5 】。鉴于无线传感器网络 技术的重要作用，当今世界各国都投入了大量的人力和财力对该领域进行研究。 可以说，无线传感器网络技术目前正处于飞速发展的时期，而无线传感器网络的 广泛应用，也必将对人们的社会生活和产业变革带来极大的影响，对社会的发展 产生巨大的推动作用。 定位技术是无线传感器网络应用的基础，具有重要的理论价值和实用价值。 无线传感器网络的许多应用，如交通管理、空间探测和灾害监测等，必须以定位 技术提供相应节点的位置信息为前提。无线传感器网络的定位问题可以分为节点 自身的定位( n o d e sl o c a l i z a t i o n ) 和外部目标的定位( s o u r c el o c a l i z a t i o n ) ，其 中前者是后者的基础。节点自身定位问题即是依据少量的知道自身精确位置的锚 点( a n c h o rn o d e ) ，确立网络中其它所有未知节点( u n k n o w nn o d e ) 位置的问 题，而目标定位则是在无线传感器网络中确定若干特定目标的位置的过程，一般 在进行目标定位之前先要完成网络节点自身的定位，然后再通过相似的原理估计 出目标的位置。一个简单的确定无线传感器网络自身节点位置的方法是给每个传 感器配置一个全球定位系统( g l o b a lp o s i t i o ns y s t e m , g p s ) 定位部件，直接通过卫 星实现定位。然而，无线传感器网络通常都具有庞大数量的传感器节点，给每个 传感器配置一个g p s 定位部件代价过于昂贵【6 】。因此，目前的无线传感器网络 基于直方图分布估计算法的无线传惑器网络定位技术 引言 通常只有极少的部分节点知道自身的位置，再通过分析节点之间的距离关系或网 络连接关系估计出各个节点的具体位置。随着无线传感器网络应用环境的多样化 和复杂化，对其定位技术的要求也呈现出多样化的趋势。结合实际的应用环境， 对无线传感器网络丌展定位技术的研究成为了当前国际上备受关注的热点研究 领域之一。 近年来，国内外的学者们相继提出了许多新的定位技术。按照定位过程是否 需要节点测量距离，当前的定位算法可大致分为距离相关( r a n g e b a s e d ) 和距 离无关( r a n g e f r e e ) 两类【7 】。距离相关算法需要首先利用测量手段获取节点间 点到点的距离或角度信息，然后再通过各种几何方法求出节点的位置，常用的测 量手段有r s s i 8 、t o a 9 、t d o a 1 0 和a o a ii 等。距离无关算法则无需每 个节点都去测量距离或角度信息，而是采用间接的方法。如：可以通过少数几个 已知位置的节点，以及相关的连接信息估计出所有节点的位置。经典的距离无关 类定位算法有质心法【1 2 】、d v - h o p 1 3 和a m o r p h o u s 算法 1 4 】等。 随着无线传感器网络应用环境的多样化和复杂化，过多的限制条件使得传统 定位技术面临越来越大的挑战。在这种情况下，基于智能优化算法的定位技术开 始发挥作用。近年来陆续有学者提出了基于智能优化算法的定位技术，如遗传算 法【1 5 】和模拟退火算法 1 6 1 等。这些智能优化定位算法的结构简单通用，而且常 常能够求解出令人满意的定位结果，已成为当前无线传感器网络定位研究领域的 个重要的课题。 分布估计算法( e s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m , e d a ) 又称为基于概率模 型的遗传算法( p r o b a b i l i s t i cm o d e lb u i l d i n gg e n e t i ca l g o r i t h m ，p m b g a ) ，是二十 世纪九十年代初提出的一种新型智能优化算法 1 7 】【1 8 】。它结合了统计学习的理 论和遗传算法的原理，通过迭代更新概率模型，并从概率模型中采样来实现对种 群的进化。传统的进化算法通常采用具体的个体操作，如交叉、变异或是差分组 合等显式方式，实现对个体的演变；而分布估计算法则采用构建种群的概率模型 和对模型采样生成新种群的隐式方式来实现个体的演变。这种全新的进化模式赋 予了分布估计算法独特的性能。大量的理论研究和现实应用表明，分布估计算法 在求解高维复杂的问题时具有优秀的性能。而无线传感器网络的定位问题不但维 数高( 即待定位的节点多) ，而且应用环境复杂( 即受噪音的影响大) ，因此采用 2 基于直方图分布估计算法的无线传感器网络定位技术引言 分布估计算法来求解无线传感器网络的定位问题是一个很有意义的尝试。基于 此，本文设计了一种基于直方图分布估计算法( h i s t o g r a me s t i m a t i o no f d i s t r i b u t i o na l g o r i t h m , h e d a ) 的无线传感器网络定位技术，其核心是带自适应局 部优化的直方图分布估计算法( h e d a l ) 。 本文首先介绍了无线传感器网络定位的应用场景，并跟踪了该领域的研究现 状；然后综述了分布估计算法的基本原理及其最新研究进展；接着结合实际情况， 设计出性能优秀的h e d a l 来求解无线传感器网络定位问题。本文重点研究了 无线传感器网络定位问题的适应度函数设计、概率模型的更新与采样、用于提高 结果定位精度的自适应局部优化操作。为了验证h e d a l 的有效性，本文结合 实际应用设计了大量的测试案例，并与b i s w a s 提出的优秀s d p 定位算法进行比 较，同时对算法的重要参数进行了分析。具体地说，论文的主要成果和创新点有 如下几点： ( 1 ) 提出一种基于直方图分布估计算法的无线传感器网络定位技术。大量 的研究和实践证明，分布估计算法在求解高维复杂的优化问题时具有 优越性。而大规模的无线传感器网络定位问题恰恰是一个高维的连续 优化问题。针对这一点，本文设计了引入自适应局部优化过程的直方 图分布估计算法h e d a l ，用于求解无线传感器网络定位。 ( 2 ) 提出一种有效的非可行区域排除方法。在求解无线传感器网络定位问 题前，我们通常可以获取传感器之间的带噪音的距离矩阵。虽然是带 有噪音的距离，但其中包含的丰富信息量可以被有效地利用起来，缩 小搜索空间。本文利用传感器的通信半径和距离信息，提出了排除节 点非可行方格的方法，并将传感器节点可能的位置以概率的形式限制 在一定的区域中，而不是整个区域，这大大提高了算法的搜索效率。 ( 3 ) 设计出一种带噪音环境定位问题的适应度评估函数。由于节点之间的 距离信息带有噪音，如何设计有效的适应度评估函数，使之准确评估 节点位置与真实节点位置之间的差异是一个难点。本文巧妙地利用了 传感器的通信半径，从正反两方面综合考虑，提出了h e d l 的适应 度评估函数。 ( 4 ) 设计出丰富的结合实际应用的测试案例，对算法的性能进行验证；同 基于直方图分布估计算法的无线传感器网络定位技术引言 时与公认的优秀s d p 定位算法进行分析和比较，验证本文所提出的算 法的有效性。最后，本文对算法的主要参数设置以及参数对算法性能 的影响特性进行了实验和分析，验证了h e d a l 的鲁棒性。 论文的各章内容组织如下： 第1 章对无线传感器网络的节点定位技术进行了概述。介绍了无线传感器网 络定位问题的经典应用以及基本定位原理，并综述了近年来该领域的研究现状。 第2 章对分布估计算法进行了概述。着重介绍分布估计算法的基本原理、算 法特点及最新的研究进展。 第3 章设计了一种用于求解w s n 定位问题的h e d a f l 。着重介绍了模型定 义和非可行区域的判定、适应度评估函数的设计、概率模型的更新与采样技术、 自适应局部优化操作等。 第4 章结合实际应用，设计了丰富的测试案例来验证所提出的算法的有效 性，并与当前较优秀的s d p 定位算法进行比较和分析，最后对算法的重要参数 进行了分析。 第5 章对全文进行总结，讨论了本文所提出算法的特点及优缺点，并对将来 的工作做了展望。 最后是本文的参考文献。 4 基于直方图分布估计算法的无线传感器网络定位技术第l 章无线传感器网络定位技术概述 第1 章无线传感器网络定位技术概述 传感器节点的自身定位是无线传感器网络的基础支撑技术之- - 1 9 ，对w s n 的理论方法和应用研究都有重要意义【2 0 】。设计良好的定位算法需要综合考虑定 位精度、应用场景、能量消耗等多方面的因素，但其中的定位精度常被作为主要 的衡量指标【2 l 】。 1 1 应用场景 在实际应用中，传感器节点的位置信息对无线传感器网络来说是至为关键的 【2 2 。下面列举了无线传感器网络定位技术的一些常见应用： 第一，环境监测，无线传感器网络通过感知环境中包括温度、湿度、亮度和 压力等各种不同的物理特性，来监测特殊事件的发生【2 3 】。之后为进一步采取措 施，无线传感器网络便需要利用其内各节点的位置信息，来确定事件发生的具体 位置，如战场上敌方车辆运动的区域，森林火灾的现场位置，天然气管道泄漏的 具体地点等【2 4 】。 第二，目标跟踪【2 5 】【2 6 】，无线传感器网络为实时监视快速移动目标的行动 并预测其前进路线，也必须借助节点定位技术【2 7 】或预先知道的节点位置信息 2 8 】 来实现。 第三，协助路由，无线传感器网络利用已有的定位信息构建多点传送树或直 接优化多点传送路线【2 9 】，能避免信息在整个网络的扩散，发挥协助路由的作用。 第四，网络管理，无线传感器网络的节点位置信息可用于构建网络拓扑 【3 0 ，也能用于实时统计网络覆盖情况【3 1 】，以便对节点密度低的区域采取必要 的措施。 由于网络特点、成本代价、环境复杂度等多方面的不同，许多已有的定位系 统及其算法并不能直接适用于求解w s n 定位问题。例如，目前最成熟的全球定 基于直方图分布估计算法的无线传感器网络定位技术第l 章无线传感器网络定位技术概述 位系统g p s ( g l o b a lp o s i t i o ns y s t e m ) ，虽然定位精度高、实时性好、抗干扰能力 强，但通常需要用户节点能耗高体积大并有固定的基础设施，因此难于在低成本 自组织的无线传感器网络中广泛使m 2 4 。又如，在机器人领域中，虽然机器人 节点的移动等特性与传感器节点相似 3 2 】，但是机器人通常还携带精确的测距设 备 3 3 】，使得机器人定位算法也不适用于无线传感器网络。 因此如何针对复杂的、动态变化的无线传感器网络应用环境，设计出一种简 单通用且有效稳定的定位算法，就成为了当今无线传感器网络研究领域中的一个 热点问题。 1 2 定位原理 无线传感器网络的节点定位问题，常假设在一定范围的监测区域内分布着大 量的传感器节点，其中包含小部分位置已知的锚点和大部分待定位的未知节点， 任意传感器节点与在其通信半径( c o m m u n i c a t i o nr a d i u s ) 内的所有节点相邻， 求解目标是通过收集、分析网络中除锚点坐标外的定位数据，计算出所有未知节 点的位置。定位数据的形式可以是相邻节点的测量距离、相邻节点的测量角度、 节点间的连通性、节点间的连通跳数等。通常认为基于前两种测量数据的定位算 法属于距离相关类；而基于后两种定位数据的算法属于距离无关类。 由于距离无关算法仅需要节点间的连通性就可计算未知节点的位置，所以与 距离相关算法相比能降低计算复杂度、对节点硬件的要求和对测距误差的敏感 度，但通常只能实现粗粒度的定位精度。从高效稳定的设计要求出发，本文主要 关注距离相关算法的研究。下面将首先对大多定位技术中使用的测量手段和几何 方法进行介绍。 1 2 1 测量手段 无线传感器网络定位中常用的测量手段有接收信号强度指示( r e c e i v e ds i g n a l s t r e n g t hi n d i c a t o r , r s s i ) ，到达时间( t i m eo fa r r i v a l ，t o a ) ，到达时间差( t i m e d i f f e r e n c eo f a r r i v a l ，t d o a ) 和到达角度( a n g l eo f a r r i v a l ，a o a ) 等。 6 基于直方图分布估计算法的无线传感器网络定位技术第l 章无线传感器网络定位技术概述 ( 1 ) r s s i 8 在节点间以已知功率发射无线信号，并通过测量接收功率来将 信号的传播损耗转化为距离。它利用了传感器节点本身具有的无线通信能力，因 而是一种低功率的廉价测距技术。但因为无线信号的传播容易受反射、多径传播、 非视距等多种环境因素的影响，所以r s s i 是一种较粗糙的测距技术。 ( 2 ) t o a 9 i 通过测量信号在两节点间的传播时间来测量它们的距离，典型 应用是g p s 定位系统。该技术虽然往往能取得不错的定位精度，但同时也需要 昂贵、高能耗的特殊设备来精确时钟同步，因此对无线传感器网络应用而言几乎 是不可行的。 ( 3 ) t d o a 1 0 l j l 臣过在两个节点间同时发射两种不同传播速度的信号( 如超 声波和r f 等) ，然后将两种信号的到达时间差转化为距离。该技术的测距精度 较r s s i 高，目l ； 被广泛应用在无线传感器网络应用定位中；但由于受超声波传 播距离有限和易受非视距因素影响等的约束，t d o a 的应用常要求较高的网络密 度和较少障碍的监测环境。 ( 4 ) a o a 1 l 】通过节点接收到的信号相对于自身轴线的角度来进行定位， 需要在节点上安装一个天线阵列或多个接收器来实现。该技术除可用于定位外， 还能提供节点的方向信息；但也受噪声和非视距等因素影响，且需要额外的硬件 支持。 由于成本等优势，r s s i 和t d o a 在目前的无线传感器网络中应用最为广泛， 但它们都可能产生较大的测距误差，因此设计一种简单通用且受测距误差影响小 的定位算法具有现实意义。 1 2 2 几何方法 传统定位技术中常用的包括三边测量( t r i l a t e r a t i o n ) 、三角测量( t r i a n g u l a t i o n ) 和极大似然估计( m a x i m u ml i k e l i h o o de s t i m a t i o n , m l e ) 等方法 2 4 1 。 ( 1 ) 三边测量法利用待定位节点与周围三个不共线点间的测量距离来获得 所求坐标。如图1 1 所示，设灰点d 阮力为待定位节点，它与周围不共线的三个 锚点a ( x l ，y o 、b ( x 2 ，见) 、c ( x 3 ， ) 的距离分别为函、蟊、磊。 7 基于直方图分布估计算法的无线传感器网络定位技术第l 章无线传感器网络定位技术概述 a0 l ，y 1 ) b 阮，y 2 ) 图1 1 三边测量法 由欧式距离定义我们可获得如下关系： c ，y 3 ) o 一薯) 2 + ( j ，一咒) 2 = 彳 ( x 一屯) 2 + ( y - y 2 ) 2 = 以 ( 1 1 ) ( x - x 3 ) 2 + ( j ，一乃) 2 = 霹 由上式我们不难求得d 的坐标为： 袭二嚣瑟二珂瞄2 ：要二要：凄二列2 ，2 ( 奶一乃) j 【巧一+ 尤一订+ 彰一矸j ( 2 ) 三角测量法利用待定位节点与周围三个不共线点间的测量角度来获得 所求坐标。如图1 2 所示，设灰点d ( x ，力为待定位节点，它与周围不共线的三个 锚点a ( x l ，y o 、b ( x 2 ，妮) 、c ( x 3 ，y 3 ) 的角度分别为a l 、n 2 、a 3 。 图1 2 三角测量法 c ( x 3 ，y 3 ) 基于直方图分布估计算法的无线传感器网络定位技术 第l 章无线传感器网络定位技术概述 对于三角形a b d ，设其外接圆的圆心为o l o l ，y l ) ，半径为厂l ，则有 _ _ a o , b = 2 ，r - a , l ，且有 ( 毫一毛) 2 + ( 一一一) 2 = 2 ( i 一屯) 2 + ( 一儿) 2 = 2 ( 1 3 ) ( 而一而) 2 + ( m 一儿) 2 = 2 2 2 r , 2c o s z a q b 由式( 1 3 ) 便可求得d 1 0 i ，y l ) 和，i ，同理也可求得对于三角形b c d 和三 角形a c d 的两个外接圆的圆心及半径，最后利用三边测量法，便可由三个圆心 和半径获得d 的坐标。 ( 3 ) 极大似然估计法利用待定位节点与三个以上不共线点间的测量距离来 获得所求坐标。如图l - 3 所示，设狄点d ( x ，力为待定位节点，它与周围不共线的 刀o 3 ) 个已知点a ig l ，y 1 ) ，a 2 ，y 9 ，a 3 ( x 3 ，y 3 ) ，a 开的距离分别为凶，d 2 ， 西，磊。 图1 3 极人似然估计法 由欧式距离定义我们可获得如下关系： a 。b n ，y 0 o 一而) 2 + ( j ，一m ) 2 = 砰 o 一而) 2 + o 一此) 2 - ( x 一为) 2 + ( y 一乃) 2 = ( 1 4 ) ( x 一) 2 + ( 夕一只) 2 = 刃 将前面( 胛1 ) 个式子分别减去最后一个式子可得到： 9 基于直方图分布估计算法的无线传感器网络定位技术 第l 章无线传感器网络定位技术概述 若令 2 ( 五一毛弦+ 2 ( 朋一只) y = 爵一砰+ 彳一+ 订一z 2 ( x 2 - x , , ) x + 2 ( y 2 - y d y = 刃一彰+ 一+ 以一露 2 ( 墨- x ) x + 2 ( y 3 一只) y = 刃一彰+ 一+ 必一露 ( 1 5 ) ； 2 ( 矗一i 一毛弦+ 2 ( 虼一l 一此) y = 刃一。+ 矗。一+ 正。一z a = 2 ( x l 一毛) 2 ( 一l 一矗) 2 ( y l 一儿) 2 ( 以一l 一只) x = 嘲 扣( d 2 - u t + x t ，瓮习 x = ( 4 r 4 ) 爿7 1 b 1 3 研究现状 ( 1 6 ) ( 1 7 ) ( 1 8 ) ( 1 9 ) 1 3 1 算法分类 基于定位问题在w s n 应用中的重要定位，国内外学者已经提出了许多求解 算法，大体可进行如下几种分类： 1 ) 距离相关定位和距离无关定位 两类算法的不同在于是否需要通过测量手段来较精确地获得两节点间的定 位数据。其中，距离相关算法将相邻节点间的测量距离或角度作为定位信息，而 距离无关算法则仅需要节点间的连通性就可计算未知节点的位置。在相同条件 下，距离相关算法因拥有测距信息的支持，一般比距离无关算法有更高的定位精 度，但可能受测距误差的影响；而距离无关算法则能降低对节点硬件的要求，但 1 0 基于直方图分布估计算法的无线传感器网络定位技术第l 章无线传感器网络定位技术概述 通常只能实现粗粒度的定位精度。 m d s m a p ( m u l t i d i m e n s i o n a ls c a l i n gm a p ) 算法 3 4 1 1 3 5 n - 7 看作是一种距离 相关算法，其主要实现过程为：( 1 ) 生成全局的网络拓扑连通图，并使用d i j k s t r a 或f l o y d 等最短路径算法，生成节点间距矩阵；( 2 ) 对节点间距矩阵应用m d s 技术，生成整个网络的相对坐标系统：( 3 ) 当拥有足够的信标节点时，将相对坐 标系统转化为绝对坐标系统。该算法的优点在于：既可基于节点间的测量距离也 可基于节点间的连通性，还可用于锚点稀疏的网络和非凸区域的定位。但对于一 个较大型的无线传感器网络，m d s m a p 算法需要耗费很大的存储空间和很大的 计算复杂度，同时所需的通信复杂度也不容忽视。 质心( c e n t r o i d ) 算法 9 1 2 1 是一种仅基于网络连通性的距离无关算法，其 基本思想是：未知节点以其所有相邻锚点所组成的多边形的几何质心为自身的估 计位置。该算法的优点在于仅基于网络的连通性，算法简单易实现；但其定位精 度较低，且受锚点的密度和分布的影响较大。 2 ) 集中式定位与分布式定位 两种方式的区别在于对基础设施的依赖程度不同。其中，集中式的定位算法 通常要求有一个特殊的中心节点支持，该中心节点具备较高的计算能力和存储能 力，可通过收集所有传感器节点间的位置信息，来集中计算w s n 中所有未知节 点的坐标；而分布式的定位