（信息与通信工程专业论文）基于rssi的无线传感器网络定位技术研究及应用.pdf

基于r s s i 的无线传感器网络定位技术研究及应用 摘要 微机电系统、无线通信和数字电子技术的进步孕育了无线传感器网络技术 ( w i r e l e s ss e n s o rn e t w o r k ，w s n ) ，无线传感器网络将改变我们与客观世界的交 互方式。定位技术作为无线传感器网络的一项重要应用，已经得到了广大科研人 员长时间的广泛关注。本文在现有的定位技术基础上，主要研究基于接收信号强 度( r e c e i v e ds i g n a ls t r e n g t hi n d i c a t o r ，r s s i ) 的无线传感器网络定位技术。 首先，本文分析了当前无线传感器网络定位技术的应用概况，指出了当前定 位技术的优缺点所在。 然后，本文考虑到基于非度量多维标度( n o n m e t r i cm u l t i d i m e n s i o n a l s c a l i n g ，n m d s ) 的定位算法彻s r s s i 中存在r s s i 值随机误差大的缺点， 引入了极大似然估计( 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 ) 的思想，利用多 次测量求平均的方式来有效地降低r s s i 值的测量误差，由此提出了 n m d s m l e - r s s i 算法，提出了算法的网络通信模型并分析了其应用背景。 接下来，本文利用m a t l a b 仿真工具对n m d s m l e r s s i 算法进行了仿真 实验，实验结果表明，n m d s m l e r s s i 算法最适合应用于室内环境，应用于矿 井隧道环境时，由于应用环境狭长的特点，定位结果会有一定的扭曲现象。 此外，针对矿井隧道这一应用环境的特点以及r s s i 在实际应用中所表现出 来的易跳变的特性，本文基于加权的思想，利用r s s i 值对锚节点( 即位置已知 的节点) 的坐标进行加权，根据多个锚节点的平均加权坐标得出待定位节点位置 信息，从而提出了一种加权质心( w e i g h t e dc e n t r o i d ，w c ) 的定位算法 r s s i w c 。本文利用德州仪器z i g b e e 协议栈( t e x a si n s t r u m e n t sz i g b e es t a c k ， t iz s t a c k ) 以及实验室开发的c c 2 4 3 0 节点和s e n s o r - v i e w 图形界面在类似于矿 井隧道的环境中做了相关的实物实验，取得了良好的定位性能。 关键词：无线传感器网络；定位；接收信号强度指示；矿井隧道 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 ) i sg r o w i n gw i t h t h e d e v e l o p m e n t o f m e m s ( m i c r o e l e c t r o m e c h a n i s ms y s t e m ) ，w i r e l e s s c o m m u n i c a t i o n a n d d i g i t a l t e c h n o l o g y w s nw i l lc h a n g ei n t e r a c t i v em o d eb e t w e e nh u m a na n dt h eo b j e c t iv e w o r l d a sa ni m p o r t a n ta p p l i c a t i o ni nw s n ，l o c a l i z a t i o nt e c h n o l o g yi sc o n c e r n e db y r e s e a r c h e r sf o ral o n gt i m e b a s e do nc u r r e n tl o c a l i z a t i o nt e c h n o l o g i e s ，t h em a i nt a s k s o ft h i sp a p e ra r er e s e a r c ho fl o c a l i z a t i o nt e c h n o l o g i e su s i n gr e c e i v e ds i g n a ls t r e n g t h i n d i c a t o r ( r s s i ) i nw s n f i r s t t h i sp a p e ra n a l y s e st h es i t u a t i o no fc u r r e n ti o c a l i z a t i o nt e c h n o l o g i e si n w s n , a n d i n d i c a t e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e m t h e n , b e c a u s et h er a n d o me r r o ro fr s s ii nn m d s r s s i ，w h i c hb a s e do n n o n m e t r i cm u l t i d i m e n s i o n a ls c a l i n g ( n m d s ) ，i sg r e a t ，s om a x i m u ml i k e l i h o o d e s t i m a t i o ni si n t r o d u c e d e r r o ri se f f e c t i v e l yr e d u c e dt h r o u g hc a l c u l a t i n ga v e r a g e v a l u ea f t e rs e v e r a lm e a s u r e s t h i sp a p e rp r o p o s e sn m d s m l e - r s s ia l g o r i t h m , a n d n e t w o r kc o m m u n i c a t i o nm o d e lf o ri t t h ea p p l i c a t i o nb a c k g r o u n di sa n a l y z e d a n dt h e n t h i sp a p e rs i m u l a t e sn m d s m l e r s s lw i t hm a t l a bt ov e r i f yi t s p e r f o r m a n c e s t h er e s u l t si n d i c a t et h a tn m d s m l e r s s ii sb e t t e rf o ra p p l i c a t i o no f i n d o o re n v i r o n m e n t l o c a l i z a t i o nr e s u l t sh a v ec e r t a i nd i s t o r t i o np h e n o m e n o nw h e n n m d s 几e r s s ii se m p l o y e di nm i n et u n n e le n v i r o n m e n t ，w h i c hi sl o n ga n d n a l t o w i na d d i t i o n , r s s iv a l u ei se a s yt oj u m pi np r a c t i c a l a i m e da tm i n et u n n e l a p p l i c a t i o ne n v i r o n m e n t ，t h i sp a p e rw e i g h t s t h ec o o r d i n a t eo fa n c h o r ( p o s i t i o nk n o w n ) n o d ew i t hr s s ib e t w e e na n c h o ra n dp o s i t i o n u n k n o w nn o d e ，t h e nc a l c u l a t e st h e c o o r d i n a t eo fp o s i t i o n u n k n o w nn o d eb ya v e r a g ew e i g h t e dc o o r d i n a t e so fs e v e r a l a n c h o r s t h i sp a p e rp r o p o s e sar s s i - w e i g h t e dc e n t r o i dl o c a l i z a t i o na l g o r i t h m t h i s p a p e rd oe x p e r i m e n t si nam i n et u n n e l l i k e de n v i r o n m e n tw i t ht e x a si n s t r u m e n t s z s t a c kp r o t o c o l ，c c 2 4 3 0n o d e sd e v e l o p e di no u rl a b o r a t o r ya n dt h ep cs o f t w a r e s e n s o r - v i e w t h er e s u l to fl o c a l i z a t i o np e r f o r m a n c ei sg o o d 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 ；l o c a l i z a t i o n ；r e c e i v e ds i g n a l s t r e n g t h i n d i c a t o r ；m i n e t u n n e l 1 i i 基于r s s i 的无线传感器网络定位技术研究及应用 插图索引 图1 1 典型的无线传感器网络结构2 图2 1 凸规划算法示意9 图2 2a p i t 定位示意图1 0 图2 3d v - h o p 定位算法示意图1 l 图2 4 最大似然估计定位示意图1 2 图3 1 随机网络分布图一2 0 图3 2 网格网络分布图2 0 图4 1 网络拓扑图2 7 图4 2 室外环境下，n m d s m l e r s s i 算法定位误差3 0 图4 3 室内环境下，n m d s m l e r s s i 算法定位误差3 l 图4 4 矿井隧道条件下，n m d s m l e r s s i 算法定位误差3 l 图4 5 室外环境下，三种定位算法性能比较3 2 图4 6 矿井隧道环境下，三种定位算法性能比较3 2 图5 1c c 2 4 3 0 节点3 5 图5 2z i g b e e 网络示意图3 5 图5 3 防空洞内部图一3 7 图5 4 防空洞内部图3 8 图5 5 防空洞内部图3 8 图5 6s e n s o r - v i e w 平台样式3 9 图5 7 防空洞环境示意图一4 0 图5 8 定位结果显示图4 3 图5 9 定位结果显示图4 4 图5 1 0 定位结果显示图4 4 图5 1 l 定位结果显示图4 5 v i 硕士学位论文 附表索引 表4 1 邻居表格式2 8 表4 2 发向汇聚节点的消息包格式2 8 表4 3 不同环境下的u w b 信道模型2 9 表5 1 锚节点消息包格式4 0 表5 2 待定位节点发送的消息包格式4 l 表5 3 汇聚节点上传到p c 的数据包格式4 l 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：鬻铭 j 日期：乒卯年多月易日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囹。 ( 请在以上相应方框内打“、”) 作者签名：静毵 作者签名：静勖 导师签名：多锄欺 v 日期：弛7 年么月e t 日期：渺7 年步月日 1 1 课题来源 第1 章绪论 本课题来源于国家自然科学基金：一类复杂环境下的无线传感器网络定位算 法研究( 基金号：6 0 6 7 3 0 6 1 ) 和湖南省自然科学基金：矿井无线传感器网络移动 节点定位与动态轨迹跟踪研究( 基金号：0 6 j j 5 0 1 1 1 ) 1 2 研究意义 无线传感器网络的节点定位技术是无线传感器网络应用的基本技术也是关 键技术之一。我们在应用无线传感器网络进行环境监测从而获取相关信息的过程 中，往往需要知道所获得数据的来源【。例如在森林防火的应用场景中，我们可 以从传感器网络获取到温度异常的信息，但更重要的是要获知究竟是哪个地方的 温度异常，这样才能让用户准确的知道发生火情的具体位置，从而才能迅速有效 地展开灭火救援等相关工作；又比如在军事战场探测的应用中，部署在战场上的 无线传感器网络只获取“发生了什么敌情 这一信息是不够的，只有在获取到“在 什么地方发生了什么敌情这样包含位置信息的消息时才能让我军做好相应的部 署。因此，定位技术是无线传感器网络的一项重要技术也是一项必需的技术。 无线传感器网络是应用相关的网络技术，在不同的应用背景下，包括定位技 术在内的各项关键技术都会有很大的不同。本文在室内、室外尤其是矿井隧道等 不同的应用背景下对无线传感器网络定位技术做了相关的研究。本文通过提出一 种引入极大似然估计的算法一一n m d s m l e r s s i 以及应用于矿井隧道的无线 传感器网络移动节点定位算法- - m r s s i w c ，并进行了相关的仿真和实物实验， 为改善面向不同应用背景的无线传感器网络定位技术以及定位技术的实际应用 提供重要的参考和借鉴意义。 1 3 研究背景 随着微电子技术和无线通信技术的飞速发展和不断成熟，具有感知能力、计 算能力和通信能力的无线传感器网络孕育而生。自从2 0 世纪9 0 年代国际上开始 对无线传感器网络的研究以来，其相关技术得到了飞速的发展。无线传感器网络 综合了传感器技术、嵌入式计算技术、分布式信息处理技术和通信技术，能够以 协作的方式实时地监测、感知和采集网络区域内的各种对象的信息，并进行处理。 这些信息通过自组织的多跳无线网络传送到用户终端，从而实现物理世界、计算 世界以及人类社会三元世界的连通。 基于r s s i 的无线传感器嘲络定位技术研究及应用 无线传感器网络由部署在监测区域内的大量廉价微型的无线传感器节点组 成，节点之间通过无线通信的方式构成一个具有协作感知和处理相关信息能力的 自组织网络1 2 】。如图1 1 所示，整个无线传感器网络系统往往由无线传感器节点、 汇聚节点、i n t e r n e t 和用户组成p 】。其中，汇聚节点的处理能力、存储能力和通 信能力一般都比普通的无线传感器节点要强，它负责连接无线传感器网络和 i n t e r n e t 等外部网络，实现两种协议栈之间的通信协议转换，同时发布管理节点 的监测任务，并把收集的数据转发到外部网络上。汇聚节点既可以是特殊的增强 型的无线传感器节点，也可以是没有监测功能仅带有无线通信接口的网关设备。 监测区域 图2 1 典型的无线传感器网络结构 无线传感器网络具有十分广阔的应用前景，在军事国防、城市管理、生物医 疗、抢险救灾、环境监测、防恐反恐等许多重要领域都有潜在的实用价值，已经 引起了学术界和工业界的高度重视，被认为是对2 1 世纪产生重大影响力的技术 之一。麻省理工学院的技术评论杂志( t e c h n o l o g yr e v i e w ) 评出了对人类 未来生活产生深远影响的十大新兴技术，无线传感器网络位于这十种新技术之首 【4 】 o 在现有的无线定位技术中，全球定位系统( g l o b a lp o s i t i o ns y s t e m ，g p s ) 是目前应用的最广泛的定位技术【5 】。g p s 定位利用卫星进行测距，具有定位精度 高、时延低以及抗干扰能力强等优点。但g p s 定位系统应用到传感器网络有如 下几个方面的限制： l 、成本限制 无线传感器网络技术本身是一项低成本的技术，有人甚至提出，在传感器网 络发展成熟时，每个无线传感器节点的成本将不超过1 美圆。而昂贵的g p s 卫 星设备显然不符合这一要求。因此，g p s 定位系统全面地应用于传感器网络不 太现实，顶多只能在少数的几个无线传感器节点上装备，但也要控制成本。 2 、能耗限制 2 硕十学位论文 无线传感器节点往往携带能量有限电源，因此对能耗的要求比较高。而g p s 定位设备往往能耗比较大，因此，在无线传感器节点上装备g p s 定位设备会降 低节点寿命。 3 、设施限制 无线传感器网络往往是一次性部署，整个网络的寿命也是整个应用的寿命周 期。而g p s 定位系统需要长期使用的固定设施，如信号塔等。很显然，建造专 门的固定设施这一点无线传感器网络很难做到。 4 、应用限制 g p s 定位系统只适用于无遮挡的室外环境，而无线传感器网络的部署环境 根据应用的不同具有多样化和复杂化的特点。如部署在茂密的森林中，半封闭的 矿井隧道中以及室内环境等等。因此，g p s 定位系统很难满足无线传感器网络 多样化的应用环境需要。 综上所述，g p s 定位技术应用于无线传感器网络有着无法克服的缺陷，想 要在节点为数众多的无线传感器网络中全面地应用g p s 技术不仅功能上有限 制，而且在应用上也满足不了要求。 另外，在传感器网络中，无线传感器节点能量有限、通信距离有限、数目众 多而且容易“死亡，因此，对无线传感器网络的定位技术提出了很高的要求， 主要有以下几个方面【l 】： 1 、自组织性 无线传感器网络的节点随机分布，缺乏全局的基础设施来协助定位，因此， 需要定位技术具有自组织性，能根据网络自身的信息来进行定位。 2 、健壮性 无线传感器节点具有硬件配置低、能量有限、部署环境恶劣等特点，因此， 定位技术需要有较好的容错性和鲁棒性。 3 、节能 通信开销是无线传感器网络主要的能量开销。定位技术应该尽可能地降低节 点间的通信开销，从而尽可能地延长网络寿命。 基于以上所述，如何根据无线传感器网络的应用环境和功能要求，设计出高 效实用的定位技术和算法便成了相关技术人员需要主要解决的问题。 无线传感器网络节点间接收信号强度指示( r s s i ) 1 6 1 是解决节点定位问题 的一种重要的方法，其主要的应用优势有以下几个方面： 1 、应用方便。r s s i 是节点间互相通信时所接收到对方的信号强度大小，在 无线传感器节点间能正常通信时该值往往能直接从硬件提取，无需其他设备。这 对降低网络成本和复杂性具有重要意义。 基于r s s i 的无线传感器嘲络定位技术研究及应用 2 、对称性。r s s i 值往往具有对称性，因此，测定两个节点间的r s s i 值只 需进行一个消息包的收发即可完成而不需要消息包的来回来完成。这对于降低定 位算法的复杂度或对定位精度要求不是很高的应用场景有重要意义。 3 、距离单调性。r s s i 值与节点间的距离值成单调性关系，随着距离的增大 而变小。因此，r s s i 能同时满足基于测距和基于非测距定位算法的要求。 另一方面，尽管r s s i 值在应用上具有一些相对于其他技术的不可替代的优 点，但其也存在着固有的不足之处，如： 1 、随环境变化的差异大。r s s i 值在不同的应用场景和不同的天气条件下会 表现出较大的差异性。本文通过对不同的应用条件分别进行分析来解决这一问 题，对r s s i 在不同场合下的应用区别对待。 2 、r s s i 值不太稳定。在实际应用中( 如第五章) ，r s s i 值可能不会有理想 条件下那么稳定，这会对定位的结果产生一定影响。本文通过多次求平均( 引入 极大似然估计) 或者不将r s s i 值转换成距离等方式来降低r s s i 值不稳定对定 位结果的影响。 综上所述，利用r s s i 值来进行定位相对于其他的定位方式有着不可比拟的 优势，本文也将在这样的背景下展开相关的研究。 1 4 研究内容 本文在无线传感器网络节点之间接收信号强度指示的基础上，分别应用了测 距和非测距两种方式，提出了一种具有广泛应用前景的无线传感器网络定位算法 和特定应用背景( 矿井隧道) 下的无线传感器网络移动节点定位算法。主要的研 究内容包括以下几个方面： 1 、本文对现有的无线传感器网络定位算法的评价体系和分类体系进行总结， 对一些典型的定位算法进行分析，总结已有的成果。 2 、本文在n m d s r s s i ( c ) 7 1 算法的基础上引入距离的极大似然估计，改进 原算法，提出了n m d s m l e r s s i 定位算法，并将该算法应用于超宽带 ( u l t r a w i d e b a n d ，u w b ) 1 8 】传感器网络。本文给出算法应用的网络通信模型， 并对不同应用环境和部署条件下的算法应用效果进行m a t l a b 仿真实验，对结 果进行比对和分析。 3 、本文在矿井隧道这一特定的应用背景下，基于r s s i 值，设计一种简单 高效的无线传感器网络移动节点定位算法一一r s s i 加权质心( r s s i w e i g h t e d c e n t r o i d ，r s s i w c ) 定位算法。 4 、本文利用实验室开发的硬件平台和图形显示工具，以及t iz s t a c k 协议 栈一j ，对r s s i w c 定位算法进行实物实验，并分析实验结果。 4 硕：学位论文 1 5 本文章节安排 全文共分5 章，各章内容安排如下： 第1 章概述无线传感器网络相关技术、选题背景以及本文的主要工作。 第2 章介绍无线传感器网络定位技术相关概述，主要介绍了定位技术的评价 指标、分类方法以及一些典型的定位算法。 第3 章介绍了多维标度技术( m u l t i d i m e n s i o n a ls c a l i n g ，m d s ) 和m a t l a b 等相关的知识和实验工具。 第4 章介绍了超宽带的相关定义，并在此基础上分析了u w b 信道模型和距 离的极大似然估计。利用非度量多维标度方法，提出了一种引入极大似然估计的 u w b 传感器网络定位算法。并通过相关的仿真实验对该算法在各种应用环境中 的结果进行了比对和分析。 第5 章根据实验室开发和应用的一系列软硬件平台：c c 2 4 3 0 节点、t i z s t a c k 协议栈和s e n s o r v i e w 工具等。提出了一种应用于矿井隧道环境中的移 动传感器节点定位算法。然后根据在防空洞环境中的实物实验，对实验结果进行 了分析。 最后总结全文，并对下一步研究工作做出展望。 基于r s s i 的无线传感器嘲络定位技术研究及应用 第2 章相关研究 在救灾抢险、环境探测、森林防火、军事目标跟踪等相当多的无线传感器网 络应用场景中，不知道无线传感器节点的位置而感知的数据是没有意义的。无线 传感器节点必须明确自己的位置才能详细说明“在什么地方出现了什么情况 ， 以此来实现更准确的信息收集和对目标的定位。 另一方面，了解无线传感器节点的位置信息还可以提高路由效率【l0 1 ，特别 是某些基于地理位置的路由机制，还可以为网络提供命名空间【1 1 1 ，向观察者报 告网络的覆盖质量【1 2 】，实现网络的负载均衡以及网络拓扑的自配置【1 3 1 等。 由此可见，定位问题是无线传感器网络应用中的一个首要的、基本的问题， 因此也长时间地得到了研究人员广泛的关注。而由于无线传感器网络的应用背景 比较广泛，再加上其本身的通信能力，计算能力以及能耗等方面的限制，一直都 没有一个通用的定位系统及算法提出。现有的一些定位系统和算法大都只是针对 某种特定的应用，在某些方面性能的提高总是以牺牲另外一些方面的性能为代 价。 2 1 定位技术的评价指标 无线传感器网络定位系统及算法的性能直接影响其可用性。相关研究人员如 何评价它们是一个需要深入研究的问题，而无线传感器网络是一个基于应用的网 络，在不同的应用背景下对定位系统及算法的评价会有不同的指标，但总体来说， 可从以下几个方面来做出评价1 1 4 l ： 1 、定位精度。定位精度是绝大多数定位技术的首要评价指标，一般用误差 值与节点一跳的无线通信距离的比例来表示，如定位精度为1 0 ，则表示定位 误差相当于节点一跳的无线通信距离的10 。很显然，定位系统和算法肯定是 越精确越好，也就是说定位精度值越小越好。 2 、适用的规模。不同的定位算法可能适用于不同的网络规模，有的系统和 算法可能只适合于一栋建筑物内或者是很小的一片区域内的网络定位，而对于大 型的网络这类算法往往显的很吃力甚至无法完成定位。一般来说，定位算法的适 用规模越大越好，但由于复杂度以及能耗等方面的限制，定位算法适用的网络规 模往往存在一定的限制。 3 、锚节点个数。锚节点即位置已知的参考节点，其往往通过人工部署或者 装备g p s 等装置来进行定位，但这会大大提高网络的复杂度和成本，而锚节点 越多往往会使得定位结果越精确。因此，如何在保证足够的定位精度的前提下尽 6 硕上学位论文 可能少的部署锚节点甚至是不部署锚节点，是每个算法研究人员在研究定位算法 的过程中都需要充分考虑的问题。 4 、节点密度。在无线传感器网络中，节点密度越大，网络的成本也就越高， 并且节点密度过大还会增大相互间通信的干扰，影响通信的质量。网络的节点密 度通常以网络的平均连通度来表示。一般来说，在一定网络规模的条件下，网络 的节点密度越低，对定位算法的要求就越高。有些定位算法需要在节点密集部署 的条件下才能取得良好的定位效果。 5 、容错性和自适应性。一般来说，定位系统和算法都需要比较理想的无线 通信环境和可靠的网络节点设备，但在真实应用场合中常会存在诸多的问题，比 如：外界环境中存在严重的多径传播、衰减、非视距、通信盲点等；网络节点由 于电池耗尽、物理损伤等自身问题而失效；外界影响和节点硬件精度限制造成节 点间点到点的距离或角度测量误差增大。由于环境、能耗和其他原因，物理地维 护或替换无线传感器节点或使用其他高精度的测量手段常常是十分困难或不可 行的。因此，定位系统和算法的软、硬件必须具有很强的容错性和自适应性，能 够通过自动调整或重构纠正错误、适应环境、减小各种误差的影响，以提高定位 精度。 6 、功耗。功耗是对无线传感器网络的设计和实现影响最大的因素之一。由 于无线传感器节点电池能量有限，因此在保证定位精度的前提下，与功耗密切相 关的定位所需的计算量、通信开销、存储开销、时间复杂性是一组关键性指标。 7 、代价。定位系统或算法的代价可从几个不同方面来评价。时间代价包括 一个系统的安装时问、配置时间、定位所需时间。空间代价包括一个定位系统或 算法所需的基础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一种 定位系统或算法的基础设施、节点设备的总费用。 上述7 个性能指标不仅是评价无线传感器网络自身定位系统和算法的标准， 也是其设计和实现的优化目标。为了实现这些目标的优化，有大量的研究工作需 要完成。同时，这些性能指标是相互关联的，必须根据应用的具体需求做出权衡， 以选择和设计合适的定位技术。 2 2 定位技术的分类 由于无线传感器节点本身能量和计算能力有限，再加上其部署区域复杂以及 自组织性等特点，现在还没有一种针对无线传感器网络的通用的定位算法。实际 上，已有许多系统和算法能够解决无线传感器网络的定位问题。但是，每种系统 和算法都用来解决不同的问题和面向不同的应用，而他们在网络规模，能耗要求， 精度要求以及容错性等方面都各有优缺点【l4 1 。 7 基于r s s i 的无线传感器网络定位技术研究及应用 而各种定位系统和算法可根据是否需要测距、是否需要锚节点、节点是否移 动、集中式还是分布式计算等不同的参考方面来进行分类。 1 、按是否需要测距可分为基于测距( r a n g e b a s e d ) 和无需测距( r a n g e f r e e ) 定位算法。前者需要测量节点间的绝对距离和方位，并利用节点间的实际距离来 计算未知节点的位置；后者无需测量节点间的绝对距离和方位，而是利用节点间 的估计距离计算节点位置。 在基于距离的定位中，测量节点间距离或方位时采用的方法主要有：基于到 达时间( t o a ) 、基于到达时间差( t d o a ) 、基于到达角度( a o a ) 以及基于接 收信号强度指示( r s s i ) 等。而m i k l o sm a r o t i 等人提出了利用两个无线信号的 干涉信号来测距的机制【15 】，为节点间的测距提供了一个新的思路。计算节点位 置的方法有三边测量法( 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 u l t i l a t e r a t i o n ) 等。 在无需测距的定位机制中，因为无需测量节点间的绝对距离和方位，这样就 降低了对节点硬件的要求，但是定位误差也相应地有所增加。这一类的定位算法 主要有质心算法，距离向量跳段( d v - h o p ) i l6 】算法，经典的多维标度 ( m d s m a p ) u7 】算法等。而m d s m a p 还能应用于基于测距的情况，从而获得 更为精确的定位。 2 、按是否需要锚节点来辅助定位可分为基于锚节点( a n c h o r b a s e d ) 和无 锚节点( a n c h o r f r e e ) 的定位算法。前者需要在网络中部署一定数量的位置已 知的节点作为参考，待定位节点通过测量与锚节点之间的距离和方位等信息来进 行定位：而无锚节点的定位算法无需锚节点的帮助，其利用节点间的相互连通信 息来达到定位的目的。由于锚节点是位置已知的节点，因此，锚节点需要装备 g p s 等定位装置，并且一般的定位算法都需要网络配备一定比例的锚节点，且 越多越好，这样就增加了网络的成本和硬件复杂度。而无锚节点的定位很好的避 免了这个问题，但是在降低成本和复杂度的同时，却加大了定位误差，并且无锚 节点定位算法实现的都是相对定位，除非引进锚节点，否则不能得到节点的绝对 位置坐标。 哥伦比亚大学的s h a n gy i 等人提出的m d s m a p 定位算法【1 。7 1 、h u s e y i n a k c a n 等人利用节点间的相对移动信息来确定节点上一时刻的位置【l8 】以及 g i a n n ig i o r g e t t i 等人最近提出了用自组织映射( s o m ) 技术来进行定位【l9 】的想 法。这些都是比较典型的无锚节点定位算法。 3 、按节点是否移动可以分为针对动态网络和静态网络的定位算法，而根据 锚节点( 也可无) 和待定位节点两种不同“身份的节点移动与否，又可以细分 为锚节点移动待定位节点移动、锚节点静止待定位节点移动、锚节点移动待定位 节点静止和锚节点静止待定位节点静止等四种。 8 硕，i 二学位论文 现今的许多定位算法都是针对静态网络或者是半移动网络的，而针对锚节点 和待定位节点都移动的网络的定位算法比较少，h ul 等人提出了基于序列蒙特 卡罗的非测距无线传感器网络定位算法【2 们，网络的锚节点和待定位节点可以无 控制移动，取得了较好的定位精度；而m i h a i ll s i c h i t i u 等人提出了一种针对于 单个锚节点移动情况的定位算法【2 1 1 。 4 、按节点位置的计算是集中计算还是分布计算可以分为集中式的和分布式 的定位算法。集中式计算是把定位信息传送给某个中心节点，并在那里进行节点 定位计算。分布式计算是把整个网络分成多个区域，在每个区域里分别进行定位 计算，然后合并成全局定位。集中式定位算法的优点在于从全局的角度统筹规划， 可以获得相对精确的位置估算，但是其计算复杂度和时间复杂度太高，而且部分 节点的通信开销和能耗过大过快，容易造成网络拓扑变化。针对这些，现今的定 位算法大多采用分布式计算方式，一般来说是以牺牲小部分定位精度为代价，从 而达到降低能耗的目的。 典型的集中式定位算法有m d s m a p 17 1 、凸规划【2 2 1 、s p a 算法【2 3 】等。 而s h a n gy i 等人针对经典m d s m a p 的缺点提出了m d s m a p 的改进算法 m d s - m a p ( p ) ( r ) 2 4 , 2 5 ，而美国仁斯利尔理工学院的r a j a g o p a li y e n g a r 等人 提出了一种基于聚类( c l u s t e r i n g b a s e d ) 的s p a 定位算法【26 。，这些都是典型的分 布式定位算法。 2 3 典型的定位算法 1 、t 5 舭j ( c o n v e xp o s i t i o ne s t i m a t e ) 定位算法【2 2 】 o 锚节点 待定位节点 图2 1 凸规划算法示意 加州大学伯克利分校的d o h e r t y 等人将节点间点到点的通信连接视为节点 位置的几何约束，把整个网络模型化为一个凸集，从而将节点定位问题转化为凸 9 基于r s s i 的无线传感器网络定位技术研究及应用 约束优化问题，然后使用半定规划和线性规划方法得到一个全局优化的解决方 案，确定节点位置。同时也给出了一种计算未知节点有可能存在的矩形区域的方 法。如图2 1 所示，根据未知节点与锚节点之间的通信连接和节点无线射程，计 算出未知节点可能存在的区域( 图中阴影部分) ，并得到相应矩形区域，然后以矩 形的质心作为未知节点的位置。 凸规划是一种集中式定位算法，在锚节点比例为1 0 的条件下，定位精度 大约为1 0 0 。为了高效工作，锚节点必须部署在网络边缘，否则节点的位置估 算会向网络中心偏移。 2 、a p i t ( a p p r o x i m a t ep i n t i n t r i a n g u l a t i o nt e s t ) 定位算法【z 7j a p i t 定位算法【2 7 】首先确定多个包含未知节点的三角形区域，这些三角形区 域的交集是一个多边形，它确定了更小的包含未知节点的区域，然后计算这个多 边形区域的质心，并将质心作为未知节点的位置，如图2 2 所示。 图2 2a p i t 定位示意图 其优点是在无线信号传播模式不规则和无线传感器节点随机部署的情况下， a p i t 算法的定位精度高，性能稳定，但缺点是a p i t 算法对网络的连通性提出 了较高的要求，存在固有的无法定位的节点。 3 、a p s ( a d h o ep o s i t i o n i n gs y s t e m ) 定位算法【1 6 , 2 8 1 美国路特葛斯大学( r u t g e r su n i v e r s i t y ) 的d r a g o sn i c u l e s c u 等人利用距离 矢量路由( d i s t a n c ev e c t o rr o u t i n g ) 和g p s 定位的原理提出了一系列分布式定位 算法。合称为a p s 。它包括6 种定位算法：d v - h o p ，d v - d i s t a n c e ，e u c l i d e a n ， d v c o o r d i n a t e ，d v - b e a r i n g 和d v r a d i a l 。 1 0 硕十学位论文 d v - h o p 算法由3 个阶段组成。首先使用典型的距离矢量交换协议，使网络 中所有节点获得其与锚节点之间的跳数( d i s t a n c ei nh o p s ) 。第2 阶段，在获得 其他锚节点位置和相隔跳数之后，锚节点计算网络平均每跳距离，然后将其作为 一个校正值( c o r r e c t i o n ) 广播至网络中。校正值采用可控洪泛法在网络中传播， 这意味着一个节点仅接受获得的第1 个校正值，而丢弃所有后来者，这个策略确 保了绝大多数节点可从最近的锚节点接收校正值。在大型网络中，可通过为数据 包设置一个t t l 域来减少通信量。当接收到校正值之后，节点根据跳数计算与 锚节点之间的距离。当未知节点获得与3 个或更多锚节点的距离时，则在第3 阶 段执行三边测量定位。 如图2 3 所示，已知锚节点l 1 与l 2 ，l 3 之间的距离和跳数。l 2 计算得到 校正值( f l o 平均每跳距离) ( 4 0 + 7 5 ) ( 2 + 5 ) = 1 6 4 2 。在上例中，假设a 从l 2 获得校 正值，则它与3 个锚节点之间的距离分别为l 1 - 3x1 6 4 2 ，l 2 - 2 x1 6 4 2 ，l 3 - 3 1 6 4 2 。然后使用三边测量法确定节点a 的位置。 图2 3d v - h o p 定位算法示意图 实验结果显示在网络平均连通度为1 0 ，信标节点比例为1 0 的各向同性网 络中定位精度约为3 3 。其优点是测距误差对它无影响，缺点是仅在各向同性 的密集网络中，校正值才能合理地估算平均每跳距离。 d v - d i s t a n c e 算法与d v o h o p 类似，所不同的是相邻节点使用r s s i 测量节点 间点到点距离，然后利用类似于距离矢量路由的方法传播与信标节点的累计距 离。当未知节点获得与三个或更多信标节点的距离后使用三边测量定位。其优点 是测距比d v - h o p 要精细，缺点是同样也仅适用各向同性的密集网络中、定位误 差随测距误差增大而增大。实验结果显示在网络平均连通度为9 ，信标节点比例 为l o ，测距误差小于1 0 。定位精度为2 0 。 基于r s s i 的无线传感器网络定位技术研究及应用 4 、a h l o s 定位算法【2 9 】 加州大学洛杉矶分校的a n d r e a ss a v v i d e s 等人设计了一种称为“m e d u s a ”的无 线传感器节点试验平台( 配备有射程3 m 的超声波收发器，可使用t d o a 技术以 2 c m 的精度测量距离) ，并在该平台上开发了a h l o s 和n h o pm u l t i l a t e r a t i o n p r i m i t i v e 定位算法。 a h l o s 算法中定义了3 种定位方式一一原子式、协作式和重复式最大似然 估计定位( a t o m ，c o l l a b o r a t i v e 和i t e r a t i v em u l t i l a t e r a t i o n ) 。其中a t o m m u l t i l a t e r a t i o n 就是传统的最大似然估计定位。 a ) o 待定位节点 锚节点 图2 4 最大似然估计定位示意图 如图2 4 a ) 所示c o l l a b o r a t i v em u l t i l a t e r a t i o n 是指假如个节点可以获得足够 多的信息来形成一个由多个方程式组成并拥有唯一解的超限制条件 ( o v e r d e t e r m i n e d ) 或限制条件完整( w e l l d e t e r m i n e d ) 的系统，那么就可以同时定 位跨越多跳的一组节点。 图2 4 b ) 就展示了c o l l a b o r a t i v em u l t i l a t e r a t i o n 的一个二维拓扑示例，未知节 点2 和4 都有3 个邻居节点，且1 ，3 ，5 和6 都是锚