（计算机应用技术专业论文）距离无关无线传感器网络三维定位研究.pdf

摘要 摘要 无线传感器网络是一种由大量具有无线通信功能的传感器构成的动态、分 布式、自组织网络，其目的是通过协作的方式感知、采集和处理网络覆盖区域中 感知对象的信息，并发送给观察者。传感器网络可以使人们在任何时间、地点和 任何环境条件下获取大量详实而可靠的信息。它不仅可以应用于国防军事、国家 安全、环境监测、交通管理、医疗卫生、制造业、反恐以及抗灾等领域，还可以 广泛应用于各种消费电子产品以及其它嵌入式系统中，对人们的生活和工作方式 产生革命性的影响。而无线传感器网络节点定位是传感器网络中的一项重要的基 础技术。 目前无线传感器网络的定位研究一般都局限于二维平面，三维空间下的研究 十分有限，而在实际应用中，由于地形限制( 如在山区，丘陵，海洋的复杂地形) 或者环境限制( 如位于建筑物的不同楼层或在空中不同高度) ，使得无线传感器 往往在空间上成立体分布，而不是平面分布，所以仅仅在平面上对传感器网络节 点进行二维定位是远远不够的，需要把定位研究拓展到三维空间中去。 本文的研究工作主要围绕三维定位算法展开。三维定位算法较之二维定位算 法在测距和定位计算中，误差更大，因此如何有效控制定位误差是三维定位算法 的难点之一。本文在传统d v h o p 定位算法的基础之上，提出了距离无关三维定 位算法，该算法的主要特点是为未知节点选择了对自身而言最佳的网络平均每跳 距离，最大限度地降低了定位误差，提高了定位算法的精度。 当网络中信标节点过少或信标节点分布不均匀时，未知节点由于无法获得足 够多的信标节点参与定位计算，而无法实现定位。本文针对这种情况提出了基于 聚类的三维定位算法，该算法首先把网络划分为多个簇集，然后对簇内节点实现 相对定位，最后把各簇合并，建立统一的全局坐标系。当网络中有足够的信标节 点时，可进行三维坐标转换，对未知节点进行绝对定位。 关键字：无线传感器网络距离无关三维定位基于聚类的三维定位算法 a b s t r a c t 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 sas o r to fd y n a m i c ，d i s t r i b u t e d ，s e l f - o r g a n i z e d n e t w o r km a d eu po fl o t so ff u n c t i o n a ls e n s o r sw i t hw i r e l e s sc o m m u n i c a t i o na b i l i t i e s t h e ys e n s e ，c o l l e c ta n dp r o c e s st h ei n f o r m a t i o no fc o v e ra r e ao fw s n ，a n dp u b l i s h t h er e s u l t st ot h eo b s e r v e r w s nc o u l db r i n gag r e a td e a lo fr e l i a b l ei n f o r m a t i o n a n y t i m e ，a n y w h e r ea n di na n yc o n d i t i o n w s nc o u l db ea p p l i e dt on a t i o n a ld e f e n s e ， n a t i o n a l s e c u r i t y , e n v i r o n m e n t a lm o n i t o r i n g ，仃a m cc o n t r o l ，m e d i c a lt r e a t m e n t ， m a n u f a c t u r i n g a n t i t e r r o r i s t sa sw e l la sa n t i d i s a s t e r i tc o u l da l s ob ea p p l i e dt oa l l k i n d so fe l e c t r o n i cp r o d u c t sa n de m b e d d e ds y s t e m s i nc o n c l u s i o n w s nb r i n g s p e o p l em a n yr e v o l u t i o n a r ye f f e c t st op e o p l e sl i f ea n dw o r k l o c a l i z a t i o nt e c h n o l o g y i saf o u n d a t i o no fw i r e l e s ss e n s o rn e t w o r kt e c h n i q u e s a tp r e s e n t t h er e s e a r c ho ns e n s o rn e t w o r k1 0 c a l i z a t i o n c o m m o n l yo n t w o d i m e n s i o n a l ，s e l d o mo nt h r e e d i m e n s i o n a l ，b u ti np r a c t i c a la p p l i c a t i o n ，b e c a u s e l i m i tt ot e r r a i n ( s u c ha sm o u n t a i na r e a ，h i l l ，a n do c e a n ) o re n v i r o n m e n t ( s u c ha s d i f f e r e n t1 e v e lo fb u i l d i n go rd i f f e r e n th e i g h ti na i r ) ，t h ew i r e l e s ss e n s o rs o m e t i m e s d i s t r i b u t ei nt h r e e d i m e n s i o n a l ，n o to np l a n e ，s oo n l yl o c a l i z a t i o ni nt w o d i m e n s i o n a l i sn o te n o u g h a n de x p a n d i n gt h er e s e a r c ht ot h r e e d i m e n s i o n a li sn e e d e d t h i sp a p e rr e s e a r c h e so nt h r e e d i m e n s i o n a ll o c a l i z a t i o n t 1 1 r e e d i m e n s i o n a l l o c a l i z a t i o nh a sm o r ee r r o r si nr a n g ea n dl o c a l i z a t i o nc o m p u t et h a nt w o d i m e n s i o n a l l o c a l i z a t i o n s oh o wt oc o n t r o ll o c a l i z a t i o ne r r o ri so n eo f d i f f i c u l t y o f t h r e e d i m e n s i o n a la l g o r i t h m t h i sp a p e ra d v a n c er a n g f r e et h r e e d i m e n s i o n a l l o c a l i z a t i o na l g o r i t h mb a s e do nt r a d i t i o n a ld v - h o pa l g o r i t h m t h em a i nt r a i to ft h i s a l g o r i t h mi sc h o s et h eb e s ta v e r a g en e t w o r kh o pd i s t a n c e f u r t h e s tr e d u c e1 0 c a l i z a t i o n e r r o r ：i m p r o v et h ep r e c i s i o no fl o c a l i z a t i o na l g o r i t h m 晒i l et h en e t w o r kh a sl i t t l ea n c h o rn o d eo ra n c h o rn o d ed i s t r i b u t eo d d s 。t h e u n k n o w nn o d ec a n tl o c a l i z a t i o nd u et on oe n o u g ha n c h o rn o d e t h i sp a p e ra d v a n c e c l u s t e r i n g b a s e dt h r e e d i m e n s i o n a l1 0 c a l i z a t i o na l g o r i t h ma g a i n s tt h i ss i t u a t i o n t h i s a l g o r i t h md i v i d et h en e t w o r ki n t om a n yc l u s t e r s ，u n k n o w nn o d er e l a t i v el o c a l i z a t i o n 。 t h e ni n c o r p o r a t en e i g h b o i r h o o dc l u s t e r s b u i l dg l o b a lr e f e r e n c ef r a m e w h e nn e t w o r k h a se n o u g ha n c h o rn o d e s 。i tc a nm a k et h r e e d i m e n s i o n a lc o o r d i n a t et r a n s f o r i l l ，a n d g i v eu n k n o w nn o d ea b s o l u t el o c a l i z a t i o n 。 k e y w o r d ：w i r e l e s s s e n s o r n e t w o r k ，r a n g e f r e e t h r e e d i m e n s i o n a ll o c a l i z a t i o n ， c l u s t e r i n g - b a s e dt h r e e - d i m e n s i o n a ll o c a l i z a t i o na l g o r i t h m l i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：噬孟壹塑 签字日期：盈翌乏! 三f 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 留公开口保密( 年) 作善签名：越鱼盈 签字日期：4 掣 导师签名： 签字日期：z 生塑：亟! f 第1 章绪论 1 1 课题的目的和意义 第1 章绪论 无线传感器网络【l 】是- t 中由大量具有无线通信功能传感器构成的动态、分布 式、自组织网络，其目的是通过协作的方式感知、采集和处理网络覆盖区域中感 知对象的信息，并发送给观察者。传感器网络可以使人们在任何时间、地点和任 何环境条件下获取大量详实而可靠的信息。它不仅可以应用于国防军事、国家安 全、环境监测、交通管理、医疗卫生、制造业、反恐以及抗灾等领域，还可以广 泛应用于各种消费电子产品以及其它嵌入式系统中，从而对人们的生活和工作方 式产生革命性的影响。 无线传感器网络节点定位是传感器网络研究中的一项重要的基础性研究内 容。从技术角度而言，确定传感器的位置对于有效地协调网络中各项分布式功能 至关重要；同时，由于传感器网络中的节点往往缺乏全局唯一标识，因此，一些 传感器网络路由协议往往依靠传感器节点的位置信息对数据进行选路。从应用角 度而言，传感器感知到的数据往往需要与其位置信息紧密结合才具有实际意义。 比如当传感器网络应用于战场侦查时，传感器不仅需要确定目标的类型、特性， 还要确定其准确的位置；在应用于环境监测时，不仅需要测定各种被监测指标的 数据，还需要确定这些数据在地理上或空间上的分布状况。因此，研究无线传感 器网络节点定位非常重要。 定位信息除用来报告事件发生的地点外，还具有下列用途：目标跟踪、实时 监视目标的行动路线、预测目标的前进轨迹、协助路由，如直接利用节点位置信 息进行数据传递的地理路由协议，避免信息在整个网络中的扩散，并可以实现定 向的信息查询；进行网络管理，利用传感器节点传回的位置信息构建网络拓扑图， 并实时统计网络覆盖情况，对节点密度低的区域及时采取必要的措施等等。因此， 在传感器网络中，传感器节点的精确定位对各种应用有着重要的作用。 目前无线传感器网络二维定位研究趋于成熟，相关研究成果比较丰富，但是 三维定位却很少有人研究，而在实际的应用中，由于地形限制( 如在山区，丘陵， 海洋的复杂地形) 或者环境限制( 如位于建筑物内不同楼层或在空中不同高度) ， 使得无线传感器往往在空间上成立体分布，而不是平面分布，所以仅仅在平面上 对传感器进行二维定位是远远不够的。 三维传感器网络是由部署在三维物理空间中，执行一定感知任务的传感器节 第1 章绪论 点组成的无线网络系统。现在已经有很多三维传感器网络应用的例子，如智能尘 埃网络，使各节点悬浮在大气中来探测空间不同位置的气压、气温；冰河监测l z j ， 网络节点被埋在冰床下不同深度，测量温度、压力、方向等数据；放置在鸟类巢 穴【3 】周围的传感器节点，观测温度、压力、湿度等环境数据。随着实际应用的进 一步发展，理论研究显得越来越重要，所以现在提出传感器网络三维定位算法的 研究是顺应现实发展需要的，同时也是一项十分紧迫的工作。 1 2 国际国内研究状况和进展 在国内，无线传感器网络正在引起越来越多研究者的兴趣，国家自然科学基 金也开始资助这方面的研究。从目前已知的相关文献来看，国内的很多研究工作 是对传感器网络的综述或者是在特定领域的应用研究，也有一些文献是对传感器 网络的数据管理、体系结构、低能耗、安全等问题的研究。只有相对较少的文献 对定位问题进行了研究，已知的有电子科技大学的研究者提出了一种基于移动信 标( 已知位置) 的分布式概率定位算法，并和几种分布式定位算法进行了比较， 同时这些研究的绝大多数都是针对二维平面的定位，有关三维定位方面的研究的 文献极少，目前已知的有武汉大学的研究者提出的一种基于球壳交集的传感器网 络三维定位算法【4 】，是a p i t ( a p p r o x i m a t ep o i n ti nt r i a n g u l a t i o n ，三角形定位算法) 定位算法在三维的扩展。 国际上，美国自然科学基金委员会2 0 0 3 年制定了传感器网络研究计划，支 持相关基础理论研究。美国国防部和各军事部门都对传感器网络给予了高度重 视，把传感器网络作为一个重要研究领域，并设立了一系列的军事传感器网络研 究项目( c 4 k i s r 计划、s m a r ts e n s o rw e b 、无人值守地面传感器群等) 。美国英 特尔公司、微软公司等信息业巨头也开始了传感器网络方面的研究工作。日本、 德国、英国、意大利等科技发达国家也纷纷展开了该领域的研究工作。 从相关文献上看，目前的大多数无线传感器网络节点定位研究集中在二维定 位方面【5 6 l f f l ，现有的典型定位系统如a c t i v eb a d g e 8 1 、a c t i v eb a t 9 、c r i c k e t 1 0 1 、 a p s 以及t e r m i n o d e 1 l 】等都是局限于二维平面上的传感器定位系统。c r i c k e t 系统 是m i t 开发的室内超声波无线射频定位系统，可将节点定位到4 x 4 平方英尺的 面积内。它虽然实现了节点的分布式定位，具有较好的扩展性。但它是依赖于固 定在天花板或墙壁上的参考点发出超声波和无线射频对节点进行定位的，是一种 典型的二维定位系统，只能确定节点在平面上的坐标。目前已知的三维定位系统 有b a ts y s t e m 1 2 j ，它是a c t i v eb a d g e 的后继发展，是一种基于测距的定位技术。 该系统使用超声波信号的t o a t l 3 】【1 4 1 ( 信号到达时间，t i m eo f a r r i v a l ) 实现三维空间 第1 章绪论 定位，使用多边定位方法提高精度。b a t 系统的定位精度最高达到3 c m 。 随着无线传感器网络应用的不断深入，二维定位技术显然已经不能满足现实 发展的需要，因此在二维定位技术的基础之上，研究三维定位技术，并将其与实 际应用紧密结合，是当前无线传感器网络中亟待研究的课题，也是未来这一领域 的核心问题之一。 1 3 论文各部分的主要内容 第一章主要阐述了本文研究的目的、意义以及国内外相关研究的现状。第二 章主要介绍传感器网络的一些基本概论和无线传感器网络节点定位的常用距离 测量方法和三维坐标计算方法。第三章主要介绍传感器网络定位算法的常用分类 标准，算法性能的评价指标，然后介绍了一些经典的传感器网络定位算法。第四 章主要介绍距离无关三维定位算法和基于簇集的三维定位算法的主要思想和内 容。第五章介绍了用于算法三维仿真的平台，仿真的原理和仿真工具的体系结构， 并对距离无关三维定位算法进行了仿真实现。第六章对全文做了总结，并对无线 传感器网络节点三维定位的进一步研究工作进行了展望。 第2 章无线传感器网络定位的基本原理 第2 章无线传感器网络定位的基本原理 本章主要介绍无线传感器网络定位的一般原理，以便我们能够更好地理解无 线传感器网络节点定位的相关内容。主要内容包括传感器网络的的体系结构，定 位相关的基本概念、测距手段和三维坐标计算方法。 2 1 无线传感器网络体系结构 无线传感器网络由电源、感知部件、嵌入式处理器、存储器、通信部件和 软件几部分构成。电源为传感器提供正常工作所必需的能量，通常为微型电池。 感知部件用于感知、获取外界信息，并将其转换为数字信号。处理部件负责协调 节点各部分的工作，如对感知部件获取的信息进行必要的处理、保存、控制感知 部件和电源的工作模式等。通信部件负责与其它传感器或观察者的通信。软件则 为无线传感器网络提供必要的软件支持，如嵌入式操作系统、嵌入式数据库等。 用户 图2 1 无线传感器网络系统结构 图2 1 给出了一个典型的无线传感器网络体系结构。网络由传感器节点 ( s e n s o rn o d e ) 、汇聚节点( s i n k ) 、i n t e r n e t 或通信卫星、任务管理节点等部 分构成。大量的传感器节点随机散布在传感器区域( s e n s o rf i e l d ) 内部或者附 近，通过自组织方式构成网络。传感器节点监测的数据沿着其它传感器节点逐跳 第2 章无线传感器网络定位的基本原理 地进行传输，在传输过程中监测数据可能被多个节点处理，经过多跳后路由到汇 聚节点，最后通过互联网或卫星到达管理节点。用户通过管理节点对无线传感器 网络进行配置和管理，发布监测任务以及收集监测数据。 图2 2 无线传感器网络抽象结构 图2 2 在一个比较抽象的级别上讨论传感器网络的功能结构，其中共分为 五层：( 1 ) 物理层，提供简单但健壮的信号调制和无线收发技术；( 2 ) 数据链路 层，负责数据成帧，帧监测，媒体访问和差错控制；( 3 ) 网络层，主要负责路由 生成与路由选择；( 4 ) 传输层，负责数据流的传输控制，是保证通信服务质量的 重要部分；( 5 ) 应用层，包括一系列基于监测任务的应用层软件。 能量管理平台管理传感器节点如何使用能源，在各个协议层都需要考虑节 省能量；移动管理平台监测并注册传感器节点的移动，维护到汇聚节点的路由， 使得传感器节点能够动态跟踪其邻居的位置；任务管理平台在一个给定的区域内 平衡和调度监测任务。 2 2 无线传感器网络定位的基本概念 在无线传感器网络节点定位技术中，根据节点是否已知自身的位置，把传 感器节点分为信标节点( 或锚节点) 和未知节点。信标节点在网络节点中所占比 例往往比较小，它们一般通过携带g p s 定位设备等手段获得自身的精确位置。 信标节点是未知节点进行定位的参考点。传感器网络中，除了信标节点外，其它 节点都是未知节点，未知节点可以通过一些定位算法，利用信标节点的位置信息 来确定自身的位置。 无线传感器网络定位算法可分为三个阶段：测距阶段，定位计算阶段和修 正求精阶段。通常一般的定位算法只由前两个阶段组成，对于精度要求较高的情 第2 章无线传感器网络定位的基本原理 况，可以添加修正求精阶段。本章主要介绍三维情况下的测距和定位计算方法。 无线传感器网络的基本术语： 邻居节点( n e i g h b o rn o d e s ) ：传感器节点通信半径内的所有其他节点，称为该节 点的邻居节点。 跳数( h o pc o u n t ) ：两个节点之间间隔的跳段总数，称为两个节点之间的跳数； 跳段距离( h o pd i s t a n c e ) ：两个节点之间间隔的各跳段距离之和，称为两节点之 间的跳段距离。 连通( e o n n e c t i b l e ) ：是指节点间可以进行通信，称节点互为连通。 连通度( c o n n e c t i v i t y ) ：一个节点拥有的邻居节点数目，称为该节点的连通度。 信标节点密度( b e a c o nd e n s i t y ) ：传感器网络中信标节点数目与所有节点数目的 比值，称为该网络的信标节点密度。 到达时间( t i m eo f a r r i v a l ，t o a ) ：信号从一个节点传播到另一个节点所需要的时 间，称为信号的到达时间。 视线关系( 1 i n eo f s i g h t ，l o s ) ：两个节点间没有障碍物间隔，能够直接通信，称 为两个节点间存在视线关系。 非视线关系( n l o s ，n ol o s ) ：两个节点之问存在障碍物。 2 3 距离测量方法 测距是定位算法的基础，测距技术的优劣直接影响到算法的定位误差，通常 可分为两类：通过测量与参考节点的距离或角度进行定位的方法属于基于测距 ( r a n g e - b a s e d ) 的定位方法；而不通过测量距离、仅依据相对位置关系或网络连通 性来进行定位的方法则称之为无需测距( r a n g e f l e e ) 的定位方法。 在基于测距的定位方法中，网络中每个未知节点都需要测量其与各参考节点 之间的距离( 或角度) 。考虑到传感器节点的特点，测距手段不应增加额外硬件， 并需要保证一定的精度。常用的测距技术有：t o a ，t d o a ，a o a ，r s s i 等。 t o a t l 5 ( t i m eo f a r r i v a l ) ：己知信号传播速度，通过测量信号在两节点间的 传播时间得到距离。使用无线电信号t o a 技术最基本的定位系统是g p s ，由于微 小的时间测量误差会带来巨大的测距误差，g p s 系统中对于时钟及时间同步的要 求非常高，g p s 卫星上装有价值昂贵、精确度达到n s 级的原子钟，g p s 接收机则 采用精度略差的石英钟，并通过不断地与卫星进行时间同步来减少误差。若使用 超声波作为信号源则可在一定程度上解决这一问题，然而超声波传播距离非常有 限，同时易受干扰，需要增加声学发射机与接收机，并且两者需要处于直线可视 第2 章无线传感器网络定位的基本原理 范围内，易受非视距传播( n o n l i n e o f - s i g h t ，nl o s ) 的影响。因传感器网络节点 在尺寸、成本、功耗上的限制，上述采用无线电或超声波信号的t o a 测距方法均 不适用于传感器网络节点。 t d o a i i 叫( t i m ed i f f e r e n c eo na r r i v a l ) ：通过记录两种不同信号在两节点中 的传播时间差，基于信号传播速度，由传播时间差计算得到距离。已经有一些定 位算法采用t d o a i 贝i j 距方法【1 7 】【1 8 】，通常使用无线射频信号和超声波信号。发射节 点同时发出两种信号，若射频信号传播速度为1 ，。，超声波信号传播速度为1 ，接 收节点收到两信号的时间差为，则计算得出两节点间d = a t d 。一1 ，：) v ，1 ，：。与 上述t o a 方法相比，t d o a 不需要时间同步，对时间精度的要求较低，然而同样 受到超声波传播中的n l o s 限制，只能适用与节点部署较为密集、障碍物较少的 情况。 r s s i 1 9 ( 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 ，并计算传播过程中的损耗，使用理论或 经验的信号传播衰减模型将传播损耗转换为距离。信号衰减模型可用公式表示如 下： 特懈，- 1 0 n 1 0 9 - 鬻象罢 亿， 其中，p ( d ) 、e ( d o ) 分别表示在距离基站d 、d o 处的信号强度，p ( d ) 是接 收节点实际测量到的r s s i ，尸( d o ) 一般可以用距天线巩处的路径衰减来代替， 其典型值为p ( 1 ) - - 3 0 d b ：刀称同层衰减指数，表示路径长度和路径损耗之间的 比例因子，依赖与建筑物的结构和使用的材料，典型值为：办公楼”= 3 2 5 ，一 般建筑物刀= 2 7 6 ；n w 表示节点和基站之间墙壁个数，c 表示信号穿过墙壁的 阈值；w a f 表示路径损耗附加值，是信号穿过障碍物的衰减因子，依赖于障碍 物的结构和使用的材料。 由于传感器节点具备通信能力，通信控制芯片通常会提供测量r s s i 的方法， 在信标节点广播自身坐标的同时可以完成r s s i 的测量，因此是一种低功率、低 代价的测距技术，r a d a r ，s p o t o n 等许多项目【2 0 】【2 1 】f 2 2 】【2 3 】中使用了该技术。其误 差主要来源与信号实际传播过程中环境影响造成的信号衰减与理论或经验模型 不符，从而带来了实际建模的复杂性，如信号反射、多径干扰、n l o s 、天线增 益等。因此，基于r s s i 的测距应视为一种粗糙的测距技术，有可能产生较大的 测距误差，一般用于对误差要求不高的场合。 a o a t 2 4 ( a n g l eo f a r r i v a l ) ：该方法将距离的测量转换为角度的测量，未知 节点通过天线阵列或其它特殊接收设备感知信标节点信号到达方向，计算两节点 之间的相对方位角，最后通过三角测量法计算未知节点坐标。其缺点是受外界环 第2 章无线传感器网络定位的基本原理 境的影响，如噪声、n l o s 问题等都会对测量结果产生不同影响。另外还需要额 外的硬件，在硬件尺寸和功耗上可能无法用于传感器节点。 距离无关的测距技术主要通过网络中的信标节点来计算网络中跳段的平均 距离( 网络平均每跳距离) ，未知节点从信标节点发送的消息中获取网络平均每 跳距离，然后乘以距离信标节点的跳数即可获得与该信标节点估算距离，从而完 成测距工作。 2 4 三维坐标计算方法 未知节点测得与信标节点之间的距离以后，使用一定的坐标计算方法就可以 确定自己的坐标。在二维情况下常用的坐标计算方法有三边测量法、三角测量法、 极大似然估计法等。在三维情况下，对三边测量法进行扩展可以得到四边测量法， 而极大似然估计法则可以直接在三维下使用。 2 4 1 四边测量法 在二维坐标平面进行节点定位有三边测量法，与此类似，在三维空间内确定 一个未知节点的坐标至少需要知道四个信标节点的位置信息和未知节点到它们 的距离，因此可以称这种定位方式为四边测量法。在此假设m ( x ，y ，z ) 为未知节 点，另外己知四个信标节点的坐标分别为：纸( ，y o ，g ) 、m 。( 而，y 。，乙) 、 m 2 2 ，y 2 ，z 2 ) 、m 3 ( 屯，y 3 ，z 3 ) ，其中点m 与其它四点的空间距离分别为： d ，= 瓜二丁石j f 丽 ( f = o 123 )( 2 2 ) 融鞋兰墨 一z ；+ d j d ： 一z ；+ d ；一d ； 一z ；+ 诉一刃 ( 2 3 ) 2 4 2 极大似然估计法 在实际坐标求解时，一般采用极大似然估计法1 2 5 】【2 6 1 ，它是四边测量法的变 形，如图2 3 所示。即有n ( n 4 ) 个信标节点m ( x 1y ，毛) ，鸩( x ：，y 2 ，z 2 ) ， 式记忆忆 捡圬瑶圬蛳埘埘埘点露 算0、“：，。_ 第2 章无线传感器网络定位的基本原理 m 。o 。，y 。，z 。) 到未知节点m ( x ，y ，z ) 的距离分别为d ，d ：，- ，以，则满足： ( 2 4 ) 采用极大似然估计法求解，从第一个方程开始到第n - 1 个方程，分别减去第 1 1 个方程，可得： x ；- - x ：一2 x ( x l x n ) + y i ! 一y ： 一2 y ( y l y 。) + z i ! 一z j ：一2 z ( z l z 。) = d ? 一西 x ；一一2 x ( x 2 一x n ) + j ，；一一- 2 y ( y ：一y 。) + z ；一z ：- 2 z c z 2 一z 。) = d ；一d ： x i i x ：- 2 x ( x 一l x n ) + y 三l - y ：- 2 y ( y 。一l - y 。) + z 。2 一l z ：- 2 z ( z 。一l z n ) = 谚i l 一 用线性方程表示为：a x = b ，其中： b = ) x = 囝 图2 3 多边测量法的极大似然估计 使用标准的最小均方差估计法可以得到节点m 的坐标为： j = ( 么r 彳) 一1 a r b 9 - ( 2 5 ) 砰霹 露 = = = r r 小办 一 一 一 0 0 0 + + + r p ；p 儿儿 儿 一 一 一 + + + 卜r p 崩庇 如 一 一 一 0 ) ) n 乙乙 吁 一 一； 一 毛龟 。 比孙 犯 、-、， ， 砒 一，一，； 一 姗咖 肌 ) ) j 一，一，： 一 墨吃 * 孙孙 砸 2 2 2 a 砰彰 “ 一 一 2 2 ”2 n a 群爵 旧 + + 2 z z 一 一 一 0 2 l 2 2 2 肛 + + ；+ 2 打2 打 2 疗 ”只 少 一 一 一 少 & 玑 + 十 2”2n + x x 2 一 一 懂 2 2 2 一 z x d 第2 章无线传感器网络定位的基本原理 此方法在测距存在一定误差的情况下仍能达到相当高的定位精度，然而其缺 点在于需要进行较多的浮点运算，其计算开销带来的能量消耗对传感器网络节点 来说不容忽视。 2 5 本章小结 三维情况下的距离测量和二维情况下一样，既可以用硬件进行测距，如 t o a 、t d o a 、r s s i 等，也可以用矢量路由的测距方法，如d v - h o p 算法中对网 络平均每跳距离的测量。至于定位计算部分，二维情况下的三边测量法到三维空 间则变成了四边测量法，而三维情况下极大似然估计法中的聆应该大于4 。总的 来说，在测距和定位计算部分，二维和三维有很多的相似性，很多二维情况下使 用的方法可以直接扩展到三维情况下使用。 第3 章无线传感器网络定位算法综述 第3 章无线传感器网络定位算法综述 无线传感器网络中的定位算法有很多，根据不同的分类标准可以划分为几大 类。本章首先介绍传感器网络中定位算法的划分标准，接着介绍无线传感器网络 中定位算法性能的评价标准，最后介绍几种经典的定位算法，通常这些算法都在 二维情况下使用，但是经过扩展以后，可以很好的在三维情况下运用。 3 1 无线传感器网络定位算法的分类 在无线传感器网络中，定位算法通常按以下标准进行分类： ( 1 ) 基于距离的定位算法和距离无关的定位算法 根据定位过程中是否测量实际节点间的距离，把定位算法分为：基于距离的 ( r a n g e b a s e d ) 定位算法和距离无关的( r a n g e f r e e ) 定位算法。前者需要测量相邻节 点间的绝对距离或者方位，并利用节点间的实际距离来计算未知节点的位置。该 方法定位精度比较高，但对节点的硬件也提出了很高的要求；后者无需测量节点 间的绝对距离或方位，而是利用节点间的估计距离来计算未知节点的位置，降低 了对节点的硬件要求，使得节点成本更适合于大规模传感器网络，但定位误差相 应的有所增加。 ( 2 ) 绝对定位和相对定位算法 、 绝对定位与物理定位类似，定位结果是一个标准的坐标位置，如经纬度。而 相对定位通常是以网络中部分节点为参考，建立整个网络的相对坐标系统。绝对 定位有广泛的应用领域，但相对定位也有自己的应用场合。尤其是基于地理位置 的路由，只需相对定位即可。典型的相对定位算法和系统有s p a ( s e l f - p o s i t i o n i n g a l g o r i t h m ) t 2 7 1 ，l p s ( l o e a lp o s i t i o n i n gs y s t e m ) t 2 引，s p o t o n t 2 9 】等，m d s m a p 定位 算法可以根据网络配置的不同分别实现两种定位。 实现绝对定位需要有部分已知位置的参考节点，又叫信标节点，这类节点一 般由人工部署在指定地点或者通过卫星定位系统获取绝对位置。其余的节点则利 用信标节点的位置作参考实现绝对定位。 ( 3 ) 集中式定位算法和分布式定位算法 根据定位过程是否需要集中式定位计算，把定位算法分为：集中式 ( c e n t r a l i z e dc o m p u t a t i o n ) 定位算法和分布式( d i s t r i b u t e dc o m p u t a t i o n ) 定位算 法。集中式定位是把所需信息传递到某个中心节点，进行节点的定位计算；分布 第3 章无线传感器网络定位算法综述 式定位依赖节点间的信息交换和协调，计算节点位置的工作在各个节点上完成。 ( 4 ) 紧密耦合t i g h t l yc o u p l e d 与松散耦合l o o s e l yc o u p l e d 所谓紧密耦合定位系统是指信标节点不仅被仔细地部署在固定的位置，并且 通过有线媒介连接到中心控制器，而松散耦合型定位系统的信标节点采用无中心 控制器的分布式协调方式。 典型的紧密耦合定位系统包括a t & t 的a c t i v eb a d g e i s 、p i n p o i n t 公司的 3 d i d l 3 0 1 、乔治亚理工学院的s m a r tf l o o r l 3 1 】等。它们的共同特点是适用于室内环 境，具有较高的精确性和实时性，时间同步和信标节点间的协调问题容易解决。 但这种部署策略限制了系统的可扩展性，代价大，无法应用于布线工作不可行的 室外环境。 松散耦合型定位算法如a h l o s ，a p i t ，它们以牺牲紧密耦合系统的精确性 而获得了部署的灵活性，依赖信标节点和未知节点间的协调和信息交换实现定 位。在这种类型的系统中，因为网络以a dh o e 方式部署，信标节点间没有直接 的协调，所以节点间会竞争信道并相互干扰。针对这个问题，剑桥的m i k eh a z a s 等提出使用宽带扩频技术( 如d s s s 、d s c d m a ) 来解决多路访问和带内噪声 干扰问题 3 2 】【3 3 】。 ( 5 ) 递增式定位算法和并发式定位算法 根据节点定位的先后次序不同，把定位算法分为：递增式( i n c r e m e m a l ) 定 位算法和并发式的( c o n c u r r e n t ) 定位算法【3 4 1 。递增式定位算法通常从信标节点 开始，信标节点附近的节点首先开始定位，依次向外延伸，各节点逐次进行定位， 这类算法的主要缺点是定位过程中传播、累积测量误差；并发式定位算法中所有 未知节点同时进行位置计算。 ( 6 ) 粗粒度与细粒度 依据定位所需信息的粒度可将定位算法或系统分为两类：根据信号强度或时 间等来度量与信标节点距离的称为细粒度定位技术；根据与信标节点的接近度来 度量的称为粗粒度定位技术。其中细粒度又可分为基于距离和基于方向性测量两 类。粗粒度定位的原理是利用某种物理现象来感应是否有目标接近一个已知的位 置，如质心、a c t i v eb a d g e 、x e r o r 的p a r c t a b 3 5 j 系统等。 ( 7 ) 基于信标节点的定位算法和无信标节点的定位算法 根据定位过程中是否使用信标节点，把定位算法分为：基于信标节点 ( b e a c o n - b a s e d ) 的定位算法和无信标节点的( b e a c o n f r e e ) 定位算法。前者在 定位过程中以信标节点作为定位中的参考节点，各节点定位后产生整体绝对坐标 系统：后者只关心节点间的相对位置，在定位过程中无需信标节点的参与，各节 点以自身作为参考点，将邻居节点纳入自己定义的坐标系中，相邻的坐标系依次 第3 章无线传感器网络定位算法综述 转换合并，最后产生整体相对坐标系统。 3 2 定位算法的性能评价指标 无线传感器网络定位算法的性能直接影响其可用性，如何评价它们是一个需 要深入研究的问题。下面定性地讨论几个常用的评价定位系统和算法的标准。 定位精度：定位技术首要的评价指标就是定位精度，一般用误差值与节点无 线射程的比例来表示，例如定位精度为3 0 表示定位误差相与节点的无线射程 的比值是0 3 。也有部分定位系统将网络部署区域划分为网格，其定位结果的精 度也就是网格的大小，如微软的r a d a r 。 规模：不同定位系统或算法也可以在园区内、建筑物内、一层建筑物或仅一 个房间内实现定位。另外，给定一定数量的基础设施或在一段时间内，一种技术 可以定位多少目标也是一个重要的评价指标。例如，r a d a r 系统仅能在即拿著 我的一层内实现目标定位，而a c t i v eo f f i c e 定位系统则可以每2 0 0 m s 定位一个节 点。 覆盖率：覆盖率是指可实现定位的未知节点与未知节点总数的比例。尽管密 集部署是无线传感器网络的特点之一，但总会有一些不可达或连通度极低的未知 节点存在，除这些节点，实现尽可能多的未知节点的精确定位也是自身定位算法 和系统追求的目标之一。 容错性和自适应性：通常定位系统和算法都需要比较理想的无线通信环境和 可靠的网络节点设备。但在真实应用场景这常会出现以下问题：外界环境中存在 严重的多径传播、衰减、非视距、通信盲点等问题；网络节点由于周围环境或自 身原因( 电池耗尽、物理损伤) 而出现失效问题；外界影响和节点硬件精度限制 造成节点间点到点的距离或角度测量误差增大的问题。由于环境、能耗和其他原 因，物理地维护或替换传感器节点或使用其他高精度的测量手段常常是十分困难 或不可行的。因此，定位算法和系统的软硬件必须具有很强的容错性和自适应性， 能够通过自动调整或重构纠正错误、适应环境、减小各种误差的影响，提高定位 精度。 节点密度：在无线传感器网络中，节点密度增大不仅意味着网络部署费用的 增加，而且会因为节点间的通信冲突问题带来有限带宽的阻塞。节点密度通常以 网络的平均连通度来表示。许多定位算法的精度受节点密度的影响，如d v - h o p 、 a m o r p h o u s 等算法仅可在节点密集部署情况下合理估算节点位置。 信标节点密度：信标节点定位通常依赖人工部署或g p s 实现。人工部署信 标节点的方式不仅受网络部署环境的限制，还严重制约网络和定位算法的可扩展 第3 章无线传感器网络定位算法综述 性。而使用g p s 定位，信标节点的费用会比普通节点高两个数量级，这意味着 即使仅有1 0 的节点是信标节点，整个网络的价格将增加十倍。因此信标节点 密度也是评价定位系统和算法性能的重要指标之一。 功耗：功耗是对w s n 的设计和实现影响最大的因素之一。由于传感器节点 电池能量有限，因此在保证定位精度前提下，与功耗密切相关的定位所需的计算 量、通信开销、存储开销、时间复杂性是一组关键性指标。 代价：定位算法或系统的代价可以从几个不同方面来评价。时间代价包括一 个系统的安装时间、配置时间、定位所需时间。空间代价包括一个定位算法或系 统所需的基础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一种定 位算法或系统的基础