（通信与信息系统专业论文）无线传感器网络定位系统的开发.pdf

00 二：。；! jjl i iy$111lj8lliil4lllllll7lll15lllll9lllll at h e s i sf o rt h ed ! 铲优o fm a s t e ri nt e l e c o m m u n i c a t i o n sa n di n f o r m a t i o n s y s t e m s t h e e x p l o i t a t i o no f l o c a l i z a t i o ns y s t e m b a s e do nw i r e l e s ss e n s o rn e t w o r k s b yq ul i a n g s u p e r v i s o r ：w a n gj i n k u a n n o r t h e a s t e r nu n i v e r s i t y j a n u a r y2 0 0 8 l i 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 二e 恧o 1z 学位论文作者签名： 、翔、o 日期：铂口7 ，d 3 0 2 , 学位论文版权使用授权书 本学位论文作者i 指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： i j ，1；t 【 l l 摘要 摘要 信技术、微机电系统技术、传感技术和计算技术的发展，已经开发 多功能的自组织无线传感器节点。在这样情况下，相应的无线传感 而生，并有望逐渐得到越来越大规模的应用。 节点定位技术是无线传感器网络的主要支撑技术之一，节点自身的正确定位是提供 监测事件位置信息的前提。只有在节点自身正确定位之后，才能确定传感器节点监测到 的事件的具体位置。对于无线传感器网络的发展与应用而言，实用化的节点定位技术研 究对于传感器网络技术性能提高和实用性保证有重要的理论意义和应用价值。 本文围绕着项目组实际承担的国家“9 8 5 工程第二期重点实验平台的建设，对无 线传感器网络室内定位技术展开了研究。本文主要研究内容如下： 第三章着重介绍了r a n g e - f r e e 定位机制中具有代表性的算法的原理和特 点，并对其分析比较；然后，论述了基于超声波的r a n g e b a s e d 的t d o a 定位方法。 第四章重点介绍现有的几种室内定位系统，并进行了分析比较。 第五章具体论述了国家9 8 5 工程第二期重点实验平台的设计与实施。 最后，利用基于超声波的t d o a 技术实现了基于无线传感器网络的室内定位实验平 台的建设，室内定位精度达到5 c m 。该成果为无线传感器网络中的其它课题，如路由协 议、时间同步管理等的研究提供了前提理论基础。对无线传感器网络其它研究工作的开 展具有重要意义。 关键词：无线传感器网络；定位；r s s i ：；室内定位系统 i i l ， s e l f - l o c a l i z a t i o no fs e n s o rn o d e si st h ep r o m o t i o no fm o n i t o r i n ge v e n t sn o r m a l l y t h e r ea r e s t i l ll o t so fs h o r t c o m i n g si nt h i st e c h n o l o g ys u c ha sg r e a ti m p a c t e db yc i r c u m s t a n c e s ，h i g l l a l g o r i t h mc o m p l e x i t ya n dh u g ee n e r g y - c o s t s ，u n s u i t a b l ef o rm o b i l es e n s o rn e t w o r k s w ec a n c o n c l u d ea l lo ft h e mi no n ew o r d ：u n p r a c t i c a l t h i st h e s i sf o c u s e so nt h ed i s c u s s i o no ft h ep r a c t i c a ll o c a l i z a t i o nt e c h n o l o g i e so ft h e a p p l i c a t i o nt ot h ee x p e r i m e n t a lf l a tb a s e do nt h ew i r e l e s ss e n s o rn e t w o r k s ，w h i c hi si m b u r s e d b yt h e “9 8 5 ”n a t i o n a lp r o j e c t t h em a j o ra n a l y s e sa n df i n d i n g sa r ea sf o l l o w s ： i nc h a p t e r3 t h e r ei sae m p h a s i z e di n t r o d u c eo nr e p r e s e n t a t i v ea l g o r i t h m so f t h er a n g e - f r e el o c a l i z a t i o n i n gm o d e ，w h i c hh a v eb e e nc o m p a r e da n da n a l y z e d t h e n ，l o c a l i z a t i o n i n gm o d eb a s e do nt d o a m o d ew i t haa s s i s t a n tm e t h o do f t h eu l t r a s o n i ca r ed i s c u s s e d i n c h a p t e r4 t h e r ei sad i s c u s s i o no ni n s i d el o c a l i z a t i o ns y s t e m sb a s e do n w i r e l e s ss e n s o rn e t w o r k s i n c h a p t e r5 t h e r ei sac o n c r e t e l yd i s c u s s i o no nt h ed e s i g na n di m p l e m e n to f t h ee x p e r i m e n t a lf l a tb a s e do nt h ew i r e l e s ss e n s o rn e t w o r k s ，w h i c hi si m b u r s e d b yt h e9 8 5n a t i o n a lp r o j e c t i nt h ee n d ，t h ei n d o o rl o c a l i z a t i o ns y s t e mb a s e do nt h ew s ni sa c c o m p l i s h e dw i t ht h e i i i l 东北大学硕士学位论文a b s t r a c _ r t d o a t e c h n o l o g yb a s e do nt h eu l t r a s o n i c t h ea c c u r a c yo ft h es y s t e ma r r i v ea tt h e5 c m t h e a c c o m p l i s h m e n tp r o v i d e st h ep r e c o n d i t i o nf o ro t h e rr e s e a r c h e so np r o b l e m si nt h ew s n t h e r ei st h ei m p o r t a n ts i g n i f i c a t i o nt ot h en e x ts t e po ft h er e s e a r c hi nt h ew s n ，f o re x a m p l e t h er o o t i n gp r o t o c o l 、t h em a n a g e m e n to ft i m es y n c h r o n i z a t i o n ，a n ds oo n k e y w o r d s ：w i r e l e s ss e n s o rn e t w o r k s ；l o c a l i z a t i o n ；r s s i ；i n s i d el o c a l i z a t i o ns y s t e m ，弋j 。； 目录 目录 i i i 1 1 1 1 i v r 第1 章绪论1 1 1 研究背景与现状1 1 2 无线传感器网络节点定位技术概述4 1 2 1 节点定位的重要意义4 1 2 2 节点定位概念及基本术语5 1 2 3 节点定位技术的研究现状和技术难题6 1 3 本文的主要工作。8 第2 章无线传感器网络定位技术1 1 2 1 无线传感器网络定位算法分类。1 1 2 1 1 基于测距和非测距定位算法1 1 2 1 2 集中式与分布式定位算法1 1 2 1 3 紧耦合与松耦合定位算法1 2 2 1 4 绝对与相对定位算法1 2 2 2 无线传感器网络定位基本原理1 3 2 2 1 节点间距离或角度的测量方法。1 3 2 2 2 节点定位的计算方式1 4 2 3 定位算法的性能评价标准1 8 2 4 现有定位算法1 9 2 4 1 质心算法1 9 2 4 2 凸规划算法2 0 2 4 3s p a 算法。2 0 2 4 4a p s 算法2 1 2 4 5a p i t 算法2 3 v 东北大学硕士学位论文目录 2 4 6m d s m a p 算法。2 4 2 5 现有定位算法的比较2 6 第三章基于r s s i 的无线传感器网络定位技术2 9 3 1 无线信号传播模型2 9 3 1 1 信号传播经验模型2 9 3 1 2 信号传播理论模型。3 0 3 2 基于r s s i 的无线传感器网络定位系统概述。3 1 3 2 1 现有定位系统简介3 2 3 2 2s p o t o n 定位系统3 3 3 2 3c a l a m a r i 定位系统3 5 3 3d 、结：；8 第4 章基于无线传感器网络的室内定位平台的实现环境。3 9 4 1 硬件环境3 9 4 2t i n v o s 系统与n e s c 语言4 1 4 3t o s s i m 仿真软件和g d b 调试工具。4 4 4 4d 、结4 5 第5 章基于无线传感器网络的室内定位平台4 7 5 1 定位实验平台概述4 7 5 1 1 信标与目标节点系统。4 8 5 1 2p c 演示系统5 1 5 2 实验验证5 2 5 3 小结5 2 第6 章结论。5 3 参考文献5 5 硕士期间参与工程项目5 9 致谢6 1 个人简历6 3 第一章绪论 现状 第1 章绪论 ( w s nw i r e l e s ss e n s o rn e t w o r k s ) 【1 】1 2 】【3 1 作为近年来新兴的研究热 7 点，它正处于蓬勃发展的上升期，方兴未艾。近两年，无线传感器网络相关的研究成 果不断涌现，但这些研究成果基本还处于起步阶段，离实际应用的要求还差的很远。 而位置信息对于无线传感器网络而言无疑是最基本、最重要的信息要求，对无线传感 器网络应用起着最关键的作用。本文系统地研究了无线传感器网络节点定位问题【4 j ， 特别是室内实用化的节点精确定位技术。通过基于无线传感器网络的室内定位实验平 台的建设，以达到提高节点定位技术和算法的实用性和有效性的目的。本章首先介绍 了研究背景、然后介绍了无线传感器网络节点定位问题的一些背景知识和国内外研究 现状，最后介绍了本文的主要内容和论文组织。 几年来，美国商业周刊、 技术评论等杂志中多次发表文章指出，传感器网 络是全球未来的四大高技术产业之一，并将掀起新的产业浪潮。无线传感- 器r ( w i r e l e s s s e n s o rn e t w o r k s ) 是下一代“无处不在计算”的关键技术。 无线传感器网络是一种独立出现的网络，微型传感器节点可以随机或特定地布置 在工作环境中，通过无线通信实现自组织，最后获取周围环境的信息，形成分布式自 治系统，相互协同完成特定的任务，它导致出现了一种全新的信息获取和处理模式。 传感器等信息获取技术的进步，为传感器网络的发展和应用奠定了基础。近年来，随 着无线技术、微机电系统技术、片上系统技术和计算技术的巨大发展和进步，孕育出 一种新型的信息获取和处理模式，那就是无线传感器网络的出现。 无线传感器网络典型的工作方式如下：使用飞行器将大量传感器节点抛洒在目标 区域，节点通过自组织快速形成一个无线网络。随机分布的集成有传感器、数据处理 单元和通信模块的微型节点借助于配置的形式多样的传感器测量所在周边环境中的 热、光、声纳、电磁波和地震波等信号，从而探测温度、湿度、噪声、光强、压力、 空气成分和移动物体的大小、速度和方向等众多我们感兴的环境特征。在网络中，节 1 东北大学硕士学位论文第一章绪论 点既是信息的采集和发出者，也充当信息的路由者，采集的数据通过多跳路由到达网 关。网关是一个特殊的节点，可通过i n t e r n e t 、移动通信网络、卫星等与监控中心通信， 也可利用无人飞机掠过网络上空，通过网关采集数据。与传统的信息获取方式相比， 无线传感器网络有自组织、功耗低、成本低和部署迅速、可扩展性强等优点。无线传 感器网络一般是一个对等的、自组织、多跳路由的、动态的网络。无线传感器网络与 传统的无线网络( 如w l a n 和蜂窝移动电话网络) 有着不同的设计目标，后者在高度 移动的环境中通过优化路由和资源管理策略达到最大化带宽的利用率，同时为用户提 供一定的服务质量保证。目前完成的进一步研究表明：无线传感器网络与传统无线网 络有着明显不同的技术要求，前者以数据为中心，后者以传输为目的。 图1 1 无线传感器网络体系结构 f i g u r e1 1f r a m e w o r ko fw i r e l e s ss e n s o rn e t w o r k s 无线传感器网络由许许多多个功能相同或不同的无线传感器节点组成。每一个传 感器节点由传感单元s e n s i n gu n i t ( 传感器、a d 转换器) 、计算单元p r o c e s s i n gu n i t ( 微控制处理器、存储器) 、通信单元t r a n s c e i v e r ( 无线收发器) 和能量单元p o w e ru n i t ( 电池、能量转换器) 等组成，如图1 2 所示。除此之外，还可附加所需的其它功能 模块。 2 一章绪论 图1 2 无线传感器节点功能结构图 f ig u r e1 2f u n c ti o n a la r c h it e c t u r eo fas e n s o rn o d e 由于无线传感器网络的巨大应用价值，它已经引起了世界许多国家的军事部门、 工业界和学术界的极大关注。其最早是由美国国防部高级研究计划局为军事应用而发 起的，并在1 9 9 8 年9 月被h o u s es c i e n c ec o m m i t t e e 评价为美国的重大科技突破。1 9 9 9 年8 月1 5 日，在美国西雅图召开第五届a c m i e e e 移动计算与网络国际学术会议年 会( m o b i c o m 9 9 ) 上，加里福尼亚大学洛杉矶分校计算机科学系的d e b o r a he s t r i n 教授等发表了具有里程碑意义的研究论文：n e x tc e n t u r yc h a l l e n g e s ：s c a l a b l e c o o r d i n a t i o ni ns e n s o rn e t w o r k s 5 1 ，从此拉开了传感器网络研究的序幕。随后的两年内， 在顶级的国际学术会议上，有关传感器网络的高水平学术论文陆续出现。2 0 0 2 年8 月， 佐治亚理工学院的i a ne a k y i l d i z 教授等在i e e ec o m m u n i c a t i o n sm a g a z i n e 上发表了题 为“a s u r v e yo ns e n s o rn e t w o r k s 的综述性学术论文，再次激发了学术界对传感器网 络研究性趣。随后，于2 0 0 2 年到2 0 0 3 年间，美国自然科学基金委员会开始以巨资扶 助传感器网络研究项目，美国加州大学伯克利分校、麻省理工学院、加州大学洛杉矶 分校、斯坦福大学、康奈尔大学等高校从2 0 0 3 年开始了传感器网络基础理论和关键技 术的研究。加州大学伯克利分校研制的传感器系统m i c a 、m i c a 2 、m i c a 2 d o t 已被广泛 的用于低能无线传感器网络的研究和开发，麻省理工学院致力于信号处理技术、哈佛 大学研究传感器网络中通信的理论基础等。在欧洲和日本，大量类似的项目也得到了 政府的大力资助，如欧盟的e y e s 计划和s e w i n g 系统等。由于政府的资助和商业需 求的驱动，国外各大公司( 如i n t e l 、i b m 和m i c r o s o f t 等) 都投入到各类无线传感器 3 东北大学硕士学位论文第一章绪论 网络研发计划中。 在国内对传感器网络的研究起步较晚，近两年才受到广泛关注。国内的很多高校 也掀起了对无线传感器网络的研究热潮。清华大学、东北大学、中国科学院沈阳自动 化所、中国科学技术大学、浙江大学等高校已经初步开展了在无线传感器网络方面的 研究工作。在线项目资助方面，在国家“十五”科技攻关项目把传感器网络列为重大 研究项目。国家自然科学基金委员会和8 6 3 计划均把传感器网络的相关研究项目作为 重点资助对象。2 0 0 5 年和2 0 0 6 年的国家发改委专项项目以及2 0 0 6 年国家9 7 3 基础研 究计划的引导下，国内对无线传感器网络的研究热情也空前高涨。2 0 0 6 年2 月由国务 院制定的国家中长期科学和技术发展规划纲要中，明确将“传感器网络及智能信 息处理 列入重点研究领域及优先主题。但从总体上来讲，在研究问题的深度和投入 的科研力量上，国内的水平与美国还有相当的差距。 传感器网络以应用为目标，而相应理论成果大多存在着与实际应用相脱节的问题， 尤其缺少对整个系统的创新性研究，拥有自主知识产权的内容更是微乎其微。无线传 感器网络是一个复杂且庞大的系统工程，涉及到的研究工作和需要解决的问题很多， 例如节点定位方法、路由与拥塞控制、节点集成及能量利用与节约、节能的通信协议、 拓扑控制、数据管理、网络安全等。其中节点定位技术首先被列入传感器网络的关键 技术和需要重点解决的问题。 1 2 无线传感器网络节点定位技术概述 作为一种全新的技术，无线传感器网络中的节点定位技术是众多无线传感器网络 关键技术的前提和基础。无线传感器网络中的定位机制与算法包括两部分：节点自身 定位和外部目标定位，前者是后者的基础。 1 2 1 节点定位的重要意义 节点定位是传感器网络的关键技术之一。首先，节点所采集到的数据必须与测量 坐标系内的位置结合，没有位置信息的数据几乎没有利用价值。比如说一个被监控目 标的地点或者窃贼闯入室内的位置对监控系统具有重要意义；其次，传感器网络的一些 系统功能，比如网络拓扑控制等，需要位置信息；最后，位置信息对传感器网络中的 服务性应用非常重要，比如智能小区内的非危重病人的健康状况监护，节点位置信息 可以使医生和病人知道距离最近的医疗设备和医护人员的位置。更为重要的是，随着 4 ， 东北大学硕士学位论文 第一章绪论 传感器网络技术的不断进步，很自然地会出现更多基于位置信息的协议和应用。正是 基于上述原因，传感器网络的定位技术已经成为一个非常重要的研究方向。 对于大多数应用，不知道传感器位置而感知的数据是没有意义的。传感器节点必 须明确自身位置才能详细说明“在什么位置或区域发生了特定事件 ，实现对外部目标 的定位和追踪。另一方面，了解传感器节点位置信息还可提高路由效益，为网络提供 命名空间，向部署者报告网络的覆盖质量，实现网络的负载均衡和网络拓扑的自配置。 1 2 2 节点定位概念及基本术语 节点定位问题即根据少数已知位置的节点，按照某种定位机制确定自身的位置。 只有在节点自身正确定位之后，才能确定传感器节点监测到的事件的具体位置，这需 要监测到该事件的多个传感器节点之间相互协作，并利用他们自身的定位机制确定事 件发生的位置。在传感器网络中，传感器节点自身的正确定位是提供监测事件位置信 息的前提。在传感器网络节点定位技术中，根据节点是否己知自身位置，把传感器节 点分为信标节点( b e a c o nn o d e ) 和未知节点( u n k n o w nn o d e ) 。信标节点在网络节点中所占 的比例很小，一般系统中5 到1 0 为信标节点。信标节点可以通过g p s 、人工配置 等手段获得自身的精确位置。信标节点是未知节点的参考点。 未知节点。信标节点 图1 3 无线传感器网络中的信标节点与位置节点 f ig u r e1 3b e a c o nn o d e sa n du n k n o w nn o d e so fs e n s o rn e t w o r k s 一般来说，节点定位需要借助被定位节点与位置已知的参考节点间某种形式的通 信，如无线电或声波通信等。传感器节点定位过程中，未知节点在获得对于邻近锚节 点的距离，或获得邻近的锚节点和未知节点之间的相对角度后，通常使用三边测量法， 5 东北大学硕士学位论文第一章绪论 三角测量法或极大似然估计法来计算自己的位置。三边计算的理论依据是在三维空间 中，知道了一个节点到三个以上参考点的距离，就可以确定该点的坐标。目前，很多 系统依赖于测量射频信号来获得节点之间的距离，如测量射频信号强度、到达的角度、 到达的时间等等。 节点定位中用到的基本术语有： 邻居节点( n e i g h b o rn o d e s ) ：传感器节点通信半径内的所有其他节点，称为该节点的 邻居节点； 跳数( h o pc o u n t ) ：两个节点之前间隔的跳段总数，称为两个节点之间的跳数； 接收信号强度指示( 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 ) ：节点接收到的无线 信号的强度值，称为接收信号强度指示； 视线关系( l i n eo fs i g h t ，l o s ) ；两个节点间无任何障碍物间隔而能直接通信，称 为两节点间为视线关系； 非视线关系( n ol o s ，n l o s ) ：两个节点间有障碍物而不能直接通信，称为两节 点间为非视线关系； 到达角度( a n g l eo f a r r i v a l ，a o a 6 1 ) ：节点接受到的信号相对于自身轴线的角度， 称为新还要相对接收节点的到达角度； 到达时间( t i m eo f a r r i v a l ，t o a ) ：信号从一个节点到达另一个节点需要的时间， 称为信号到达时间； 到达时间差( t i m ed i f f e r e n c eo f a r r i v a l ，t d o a l 7 1 ) ：两种不同传播速度的信号从一 个节点到另一个节点所需要的时间之差，称为信号的到达时间差。 1 2 3 节点定位技术的研究现状和技术难题 从a t & tl a b o r a t o r i e sc a m b r i d g e 于1 9 9 2 年开发出最早的室内定位系统a c t i v e b a d g e 至今，定位系统和算法的研究大致经过了两个阶段。第一阶段主要偏重于紧密 耦合型和基于基础设施的定位系统；而松散型定位系统的节点采用无中心控制器的分 布式无线协调方式，代表性的研究成果包括r a d a r 、a c t i v eb a t 、s p o to n 、a c t i v eo f f i c e 等。2 0 0 0 年以后对于松散耦合型和无需基础设施的定位技术的关注和研究可认为是定 位算法和系统研究的第二阶段，目前已经成为w s n 领域的一个热点。 为了弥补紧密耦合定位系统的不足，m l t 开发了最早的松散耦合型室内定位系统 c r i c k e t 。南加州大学的n i r u p a m ab u l u s u 的质心算法虽然都非常简单，完全基于网络 6 住论文第一章绪论 锚节点和未知节点间协调，但要求未知节点必须与锚节点直接相邻，因 锚节点密度。同样，维吉尼亚大学t i a nh e 的a p i t l 8 ( a p p r o x i m a t ep i tt e s t ) 地利用了p i t 原理( p e r f e c tp o i n t i n t r i a n g u l a t i o nt e s tt h e o r y ) 在无需测距 网络定位，但也需要非常高的锚节点密度，几乎无法应用于实际场合。 工业大学s r d j a nc a p k u n 的s p a ( s e l f - p o s i t i o n i n ga l g o r i t h m ) 算法提出了在 件下实现整个网络的相对定位的方案，但是其通信开销几乎与节点数量 对s p a 的缺点，美国仁斯利尔理工学院的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 ) 的相对定位算法，显著减小了通信开销。但是这两种算法没 有对测距误差采取任何抑制措施，所以定位精度都较差。美国路特葛斯大学的d r a g o s n i c u l e s c u 利用距离矢量路由和g p s 定位的思想于2 0 0 1 年和2 0 0 3 年提出了一系列分 布式定位算法一合称为a p s l 9 j ( 1 0 j 【1 1 l ( a dh o cp o s i t i o ns y s t e m ) ，它共包括了6 种定位算 法：d r - 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 o b e a r i n g 和d r - r a d i a l 。这一 系列算法都各有弊端。为了降低锚节点密度，加州大学洛杉矶分校的a n d r e a ss a v v i d e s ， 在2 0 0 1 年提出了a h l o s 算法【1 2 1 ，原子式和协作式最大似然估计( a t o ma n dc o l l a b o r a t i v e m u l t i l a t e r a t i o n ) 定位满足条件的节点，并将己定位的未知节点升级为锚节点，多次循环 直至实现整个的网络定位。为了减小测距误差的影响，c h r i ss a v a r e s e 在2 0 0 1 年提出 的c o o p e r a t i v er a n g i n g 算法中采用循环求精过程对初始定位结果进行求精；并在2 0 0 2 年的o p h a s ep o s i t i o n i n g 算法中提出了对初始定位结果进行加权循环求精的思想， 对测距误差的影响有一定的抑制。而现有这些循环算法的共同缺点就是循环次数无法 预知，增加了算法的不确定性。 还有一些集中式定位算法，如加州大学伯克利分校d o h e r t y 的凸规划【1 3 1 【1 4 l 和密苏 里哥伦比亚大学y is h a n g 提出的多维定标算法( m d s m a p l l 5 1 ) 。但采用集中式计算方 式，最大的缺点在于将整个网络的连通性信息传送到执行定位计算的某个中心节点会 过早耗尽靠近中心节点的那些节点的电能，从而造成网络通信的中断。 目前，由于这些定位算法都有它的局限性和使用范围，考虑现有实验环境的限制 和约束，使用紧密藕合型和基于基础设施的定位系统，是行不通的。集中式定位算法 由于对单个节点的要求过高，也不适合于现有的应用环境。分布式定位算法是个很好 的选择，主要有b o u n d i n gb o x 、d v o h o p 、e u c l i d e a n 、r o b u s tp o s i t i o n 等算法。 总体来说，现行的定位技术存在一下技术难题： 缺乏更加有效精确的测距方法； 7 东北大学硕士学位论文第一章绪论 减少节点定位带来的通信开销； 大规模无线传感器网络中的误差累积问题； 传感器节点有能量限制，需要研究在算法复杂度与能量消耗之间的合理折衷，即 定位精度与能力消耗间的衡量； 目前的研究只是局限于静态网络，移动节点的跟踪与定位也是需要深入研究的问 题。 总之，无线传感器网络定位算法的研究从总体上说尚处于一个起步的阶段，已有 t 的研究工作正在为该领域提出越来越多的承待解决的问题。现有的几乎所有算法均不 能很好地满足应用要求。 1 3 本文的主要工作 本论文以国家“9 8 5 工程第二期重点实验平台建设为依托，以传感器网络定位方 法与实现为主要研究对象，以提高定位算法的精度和实用性为主要目的来展开。 本文主要工作如下： 深入研究基于无线传感器网络的各种定位算法，并进行分析比较。对其中适合室 内定位的t d o a 技术和适应性良好的基于r s s i 的定位算法进行了重点研究与阐述。 在工程实现上，通过深入研究三种现有系统，即c r i c k e t 、s p o t o n 、c a l a m a r i 系统， 我们提出自主设计的基于无线传感器网络的室内定位实验平台设计和实施方案。最后， 主要实现了基于t d o a 技术的无线传感器网络室内定位方案。 论文的组织： 本论文主要研究传感器网络的定位算法及室内定位系统的实现，围绕定位算法展 开，在第一章介绍了本文的研究背景和主要工作。第二章描述了无线传感器网络定位 问题的基本理论和模型。第三章主要具体地研究：基于r s s i 的无线传感器网络定位 算法和基于t d o a 技术的定位方法。第四章研究y - - 种现有基于无线传感器网络的定 ， 位系统以及自主设计的基于t d o a 技术的无线传感器网络室内定位系统。第五章阐述 了基于t d o a 技术建设的无线传感器网络实验平台的具体细节。第六章对本问作出总 结，并提出承待解决的问题。 章节结构如下： 第一章：绪论； 第二章：无线传感器网络定位算法的基本理论和模型； 8 文第一章绪论 r s s i 校验的无线传感器网络定位算法； 传感器网络室内定位系统； 无线传感器网络室内定位实验平台的实现； 总结与展望。 9 东北大学硕士学位论文 第一章绪论 1 0 ， 学位论文 一 一 1 第二章无线传感器网络定位技术 第2 章无线传感器网络定位技术 传感器网络定位算法分类 现有的无线传感器网络定位算法在满足一些前提条件下，基本能达到在某个特定区 域随机部署的应用要求。但是对于真正的实际应用而言，要满足的条件限制都是很严格 的。因此，该领域还有待提出更好的方法来更好的解决节点定位问题，使传感器网络能 真正在实际生活中得到广泛应用。本章描述了无线传感器网络定位技术中的关键问题， 作为后续章节讨论的基础，其中包括定位算法的分类、定位算法的基本原理和模型等； 并进行分析比较。 对于无线传感器网络定位算法以及定位系统来说，并没有一个国际统一认可的分类 标准。下面本文提出的这些分类方法，不一定适用于每一种定位算法和定位系统，但能 在一定程度上描述不同定位技术的特点和特性。 2 1 1 基于测距和非测距定位算法 根据定位过程中是否测量实际节点间的距离，我们把定位算法分为：基于测距的 ( r a n g e - - b a s e d ) 定位算法和非测距的( r a n g e - - f r e e ) 定位算法n 引。前者需要测量相邻节 点间的绝对距离或方位，并利用节点间的实际距离来计算未知节点的位置：后者无需测 量节点的绝对距离或方位，而是利用节点间的估计距离计算节点位置。 这种分类方法是目前最主要的无线传感器网络定位算法分类方法。在下面章节里面 还有进一步的深入介绍和算法间的分析比较。 2 1 2 集中式与分布式定位算法 、1 集中式( 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 ) 计算是 指依赖节点间的信息交换和协调，节点自行计算的定位方式。 1 1 东北大学硕士学位论文 第二章无线传感器网络定位技术 集中式计算的优点在于从全局角度统筹规划，计算量和存储量几乎没有限制，可获 得相对精确的位置估算。它的缺点包括与中心节点位置较近的节点会因为通信量大而过 早消耗完电能，导致整个网络与中心节点信息交流的中断，无法实时定位等。集中式定 位算法包括凸规划、m d s - m a p 、n - h o p m u l t i l a t e r a t i o np r i m i t i v e 定位算法可根据应用 需求采用两种不同的计算模式。 2 1 3 紧耦合与松耦合定位算法 。， 所谓紧藕合( t i g h t l yc o u p l e d ) 定位系统指锚节点不仅被仔细地部署在固定的位置， 并且通过有线媒介连接到中心控制器：而松耦合( 1 0 0 s e l yc o u p l e d ) 定位系统的锚节点采 1 用无中心控制器的分布式无线协调方式。 典型的紧藕合定位系统包括a t & t 的a c t i v eb a d g e n 7 1 、p i n p o i n t 公司的3 d - i d 、乔 治亚理工学院的s m a r tf l o o r 等。它们的共同特点是适用于室内环境，具有较高的精确 性和实时性，时间同步和锚节点间的协调问题容易解决。但这种部署策略限制了系统的 可扩展性，代价大，无法应用于布线工作不可行的室外环境。 最近提出的许多定位系统和算法如a h l o s 、a p i t 等都属于松耦合解决方案。它们以 牺牲紧耦合系统的精确性而获得了部署的灵活性，依赖锚节点和未知节点间的协调和信 息交换实现定位。在松散耦合系统中，因为网络以a dh o c 方式部署，锚节点间没有直 接的协调，所以节点间会竞争信道并相互干扰。针对这个问题，剑桥的m i k eh a z a s 等 提出使用宽带扩频技术( 如d s s s 、d s c d m a ) 来解决多路访问和带内噪声干扰问题。 2 1 4 绝对与相对定位算法 绝对定位与物理定位类似，定位结果是一个标准的绝对的坐标位置，如经纬度。而 相对定位通常是以网络中部分节点为参考，建立整个网络的相对坐标系统。绝对定位可 为网络提供唯一的命名空间，受节点移动性影响较小，有更广泛的应用领域。但研究发 现，在相对定位的基础上也能够实现部分路由协议，尤其是基于地理位置的路由( g e o r o u t i n g ) ，而且相对定位不需要锚节点。大多数定位系统和算法都可以实现绝对定位服 务，典型的相对定位算法和系统有s p a ( s e l f - - p o s i t i o n i n ga l g o r i t h m ) 、l p s n 8 1 ( 1 0 c a l p o s i t i o n i n gs y s t e m ) 、s p o t o n ，而m d s m a p 定位算法可以根据网络配置的不同分别实 现这两种定位。 总之，对于无线传感器网络而言，它的特性是以数据为中心的一种分布式、自组织、 1 2 东北大学硕士学位论文 第二章无线传感器网络定位技术 低功耗、地成本的传感器网络。显而易见，对于面对可实际应用的无线传感器网络定位 算法来说，非测距( r a n g e - f r e e ) 、分布式、松耦合的定位算法才是更符合无线传感器 网络特性的定位技术。 2 2 无线传感器网络定位基本原理 2 2 1 节点间距离或角度的测量方法 在无线传感器网络定位中，常用的节点间的距离或角度的测量技术有t o a ( t i m eo f a r r i v a l ) 、t d o a ( t i m ed i f f e r e n c eo fa r r i v a l ) 、r s s i ( r 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 ) 和a o a ( a n g l eo fa r r i v a l ) 。 t o a ：该技术通过测量信号传播时间来测量距离。使用t o a 技术最基本的定 位系统是g p s ，g p s 系统需要昂贵、高能耗的电子设备来精确同步卫星时钟。 因w s n 节点硬件尺寸、价格和功耗限制，g p s 和其他t o a 技术对无线传感器 网络而言几乎是不可行的。 叠 t d o a ：测距技术被广泛应