（计算机系统结构专业论文）基于wsn定位技术的研究与实现.pdf

华东帅范人学硕上学位论文 基于w s n 定位技术的研究与实现 摘要 近年来，无线传感器网络以其低成本、低功耗、布设方便等特点，普遍应用 于军事、民用领域，诸如监控系统、导航系统、障碍规避系统等。这一类系统共 同要解决的问题是如何确定目标的位置，以及如何确定目标的运动方向或轨迹 等。因此，在无线传感器网络环境下实现一种有效、快速的定位算法已经成为当 今的一个研究热点。 本文首先介绍了无线传感器网络的结构及其软硬件架构；然后，分析研究了 目前通用的一些经典定位算法，比较了各种定位算法的优缺点及其应用背景；在 此基础上，分析研究了支撑定位算法的几种常用滤波算法；最后，结合r s s i 定 位算法和质心定位算法两种算法的特点，设计和实现了一个室内的基于z i g b e e 网络的定位系统：系统以z i g b e e 方式组网，节点通过集中式计算，在p c 机上采 用统计和三边测量方法，估算和描绘移动节点的坐标轨迹，通过数据实验，得到 了比较稳定的定位结果，完成了一个基于无线传感器网络的室内定位系统。 关键词： w s n 定位技术r s s ir a n g e b a s e d r a n g e f r e e 华东师范人学硕i 学位论文基十w s n 定位技术的研究与实现 a b s t r a c t i nr e c e n ty e a r s ，w i r e l e s ss e n s o rn e t w o r ki sw i d e l ya p p l i e di nb o t hm i l i t a r ya n d c i v i lf i e l d s ，s u c ha sm o n i t o r i n gs y s t e m ，n a v i g a t i n gs y s t e ma n do b s t a c l ea v o i d a n c e s y s t e m t h ew s nn o d e sa r ef e a t u r e da sl o wi np o w e ra n dc o s t ，a n dc o n v i e n e n tt o p l a c e i ns u c ha p p l i c a t i o n st h a tw s n i n v o l v e d ，t h em o s ti m p o r t a n ti sh o wt ol o c a l i z e a t a r g e t ，e s p e c i a l l yam o v i n go n e s oa p p l y i n ga ne f f i c i e n t ，f a s ta n de a s y t o - r e a l i s e l o c a l i z a t i o na l g o r i t h mi n t ow s ni sr e a l l yap o p u l a rt o p i c t h et h e s i sf h - s ti n t r o d u c e st l l ea r c h i t e c t u r eo fw s n ，a n dl o o k si n t oi t sh a r d w a r e a n ds o f t w a r e ；s e c o n d l y ，as e r i e so fc l a s s i c a ll o c a l i z a t i o na l g o r i t h m sa r er e s e a r c h e d a n dc o m p a r e db e t w e e n b a s e do nt h ea l g o r i t h m sm e n t i o n e d ，t h et h e s i sa l s oi n v o l v e s f i l t e r a l g o r i t h m sw h i c hs e r v i c e f o rl o c a l i z a t i o na l g o r i t h m i nt h ee n d ，c o m b i n i n g r s s i b a s e da l g o r i t h mw i t hm a s s c e n t e r - b a s e da l g o r i t h m ，aw s n - b a s e dl o c a l i z a t i o n s y s t e mi sd e s i g n e da n di m p l e n t e d k e y w o r d s ： w s nl o c a l i z a t i o nr s s i r a n g e b a s e d r a n g e f r e e “ 基于w s n 定位技术的研究7 j 实现 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果据我 所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研究成 果对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名：圭丝日期：2 婴乙型 学位论文授权使用声明 本人完全了解华东师范大学有关保留，使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅有权将学位论文的内容编入有关数据库进 行检索。有权将学位论文的标题和摘要汇编出版保密的学位论文在 怨密后适用本规定 学位论文作者签名：豢互娣 日期：竺! ：! ：兰! 汐千 缈攀警 师 乳 锄 期 牛东师范人学硕上学位论文基十w s n 定位技术的研究i 亍实现 1 1 论文研究的背景 第1 章绪论 w s n ( 无线传感器网络卜一般应用于监控、导航、障碍规避等系统，节点的位 置信息对于这类系统是至关重要的。因为在这类无线传感器网络应用中，通常需 要知道某些事件发生的具体位置，比如说森林火灾的现场位置、天然气管道泄漏 的具体地点等等；一般在这种监测系统中，会随机布放多个无线传感器节点，这 些节点以自组织的方式相互协调工作，确定某个移动或不移动节点的相对位置， 计算和估计该节点的绝对位置，完成定位的功能。定位信息除了可以报告事件发 生的地点之外，还具有以下一些用途诸如：目标跟踪、实时监视目标的行动路线、 预测目标的前进轨迹、协助路由和实时管理网络拓扑情况等等。因此，研究和实 现一种应用于无线传感器网络中的定位算法是很有现实意义的。 1 2 国内外研究现状 全球定位系统g p s 是目前应用最广泛的，也是最成熟的定位系统，它通过 卫星的授时和测距对用户节点进行定位，具有定位精度高、实时性好、抗干扰能 力强等优点，但是g p s 适用于无遮挡的室外环境，用户节点能耗高、体积大、 成本高、需要固定基础设施，并不适用于无线传感器网络。 现有的无线传感器网络下的定位算法分为两种：节点自身的定位和目标节点 的定位，其中后者是依赖于前者的。节点自身定位算法分为两大类，一种是基于 测距技术的定位算法，一种是无需测距的定位算法。基于测距技术的定位算法通 过测量节点间的距离或者角度信息，使用三边测量法、三角测量法或最大似然估 计法来计算节点位置，这一类算法包括r s s i ( 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 ) 定位、t o a ( t i m eo fa r r i v a l ) 定位、t d o a ( t i m ed i f f e r e n c eo na r r i v a l ) 定位和 a o a ( a n g l eo fa r r i v a l ) 定位。无需测距的定位算法有质心定位、凸规划定位、 d v - h o p ( d i s t a n c e v e c t o r h o p ) 定位、a m o r p h o u s 定位、m d s m a p 定位和 a p i t ( a p p r o x i m a t ep r rt e s t ) 定位。南加州大学的n i r u p a m ab u l u s u 等曾提出一种 基于网络连通性的室外定位算法，由少数关键节点定期向邻居节点广播一个信标 信号，其中包含自身i d 和位置信息；加卅i 大学伯克利分校的d o h e r t y 等曾提出 过凸规划模型定位算法；美国路特葛斯大学的d r a g o sn i c u l e s c u 等利用距离矢量 路由和g p s 定位思想也提出了。系列分布式定位算法。目标节点的定位大多数 华东师范人学硕l 学位论文 基于w s n 定位技术的研究j 实现 都是基于追踪( t r a c k i n g - b a s e d ) 的定位算法。目标追踪是1 9 5 5 年由w a x 首次提出， 2 0 世纪8 0 年代b a rs h a n l o m 和s i n g e r 为此作了进一步的研究和突破。 国外很多大学诸如美国加州大学伯克利分校、麻省理工学院、康奈尔大学、 加州大学洛杉矶分校都有对无线传感器网络定位技术的研究；国内一些高校如西 安电子科技大学、中国科技大学、哈尔滨工业大学也加入了这个领域。 1 3 本文的内容和组织结构 第一章绪论，介绍了论文研究的背景，国内外研究现状和论文的组织结构。 第二章从无线传感器网络的体系结构、网络节点组成、协议栈架构等几个 方面进行描述，介绍了无线传感器网络的特点和应用领域。 第三章节点自身定位算法和目标定位算法；并在此基础上讨论了适用于无 线传感器网络环境的定位算法。 第四章介绍了支撑各种定位算法的通用滤波算法和预测理论。 第五章设计和实现了一个基于无线传感器网络的室内定位系统。整个系统 在z i 【g b e e 网络环境中实现，结合质心定位算法和r s s i 算法的特点，实现了移动 节点在室内的定位。 第六章总结和展望。 华东师范人学坝 ：学位论文基于w s n 定位技术的研究0 实现 第2 章无线传感器网络 无线传感器网络与传统的无线网络相比，具有一些不同的特点： ( 1 ) 电源容量有限。无线传感器网络节点一般由电池供电，在使用过程中也 不能给电池充电或者更换电池。节能是无线传感器网络的设计前提。 ( 萄传感器节点受限于低成本、小体积和低功耗，硬件和软件资源非常有限。 ( 3 1 无中心，通常是一个对等式的网络。 ( 4 ) 自组织，无线传感器网络的布设和展开无需依赖任何预设的基础设施。 ( 5 ) 多跳路由。 ( 6 ) 动态拓扑。 f 7 ) 节点数量众多，分布密集。 2 1 无线传感器网络结构 图2 1 是一个无线传感器网络的系统结构图，它一般包括传感器节点( s e n s o r n o d e ) 、汇聚节点( s i n kn o d e ) 和管理节点。部署在监测区域的大量传感器节点以自 组织的方式构成网络，形成各种拓扑结构。传感器节点采集到的数据沿着其他传 感器节点逐跳进行传输，在传输过程中数据可能被多个节点处理，经过多跳后路 由到汇聚节点，最终通过互联网或者卫星到达管理节点。用户通过管理节点对传 感器网络进行配置和管理，发布监测任务以及采集监测数据。 q 汇聚节 用户任务餐理 越溅送域 图2 1 传感器网络体系统结构 传感器声点通常是一个微型的嵌入式系统，它的处理能力、存储能力和通信 能力相对较弱，通过携带能量有限的电池供电。每个传感器节点具备传统网络节 3 八 ：o；镣 毕东帅范人学硕卜学位论文基于w s n 定位技术的研究与实现 点的终端和路由器双重功能，除了进行本地信息收集和数据处理，还要对其他节 点转发来的数据进行存储、管理和融合等处理，同时，与其他节点协作完成一些 应用相关的特定任务。 汇聚节点的处理能力、存储能力和通信能力相对比较强，它连接传感器网络 和外部网络，实现两种协议栈之间的通信协议转换，同时发布管理节点的监测任 务，并把收集的数据转发n 夕i - 部网络。汇聚节点既可以是一个具有增强功能的传 感器节点，有足够的能量供给以及更多的内存和计算资源，也可以是没有监测功 能仅带有无线通信接口的特殊网关设备。 无线传感器网络相较于传统的网络，具备以下一些明显的特征，这些特征也 制约了无线传感器网络的应用领域和技术要素： 1 1 大规模 无线传感器网络的节点分布通常都是大规模部署的，在一个监测区域内，节 点的数目可能达到成千上万。大规模的特性体现在两个方面：一是指在地理区域 内部署了大量的传感器节点；一是指在面积不大的空间里面密集部署了大量的传 感器节点。 大规模地部署节点的优点在于：通过不同空间视角获得的信息具有更大的信 噪比；通过分布式处理大量的采集信息能够提高监测的精确度，降低对单个节点 传感器的精度要求；大量冗余节点的存在，使得系统具有很强的容错性能；大量 节点能够大量覆盖监测区域，减少盲区。 2 1 自组织性 无线传感器网络应用中，通常节点都是被放置在没有基础设施的地方，传感 器节点可能是通过飞机播散或者随意放置到人不可达的地方，因此节点之间的邻 居关系预先并不知道，这需要无线传感器网络中的节点具有自组织能力，能够自 行进行配置和管理，通过拓扑控制机制和网络协议自动形成转发监测数据的多跳 无线网络系统。 另外，无线传感器网络的节点部署的时问周期是比较长的，可能部分节点在 使用过程中能量耗尽或者因为环境因素造成了失效，也有可能网络中会加入新的 节点，以增加监测精度；这样无线传感器网络中的节点数目会动态地增加或者减 少，拓扑结构也会随之动态地改变。这就需要无线传感器网络的自组织性适应这 种拓扑变化。 3 1 动态性 无线传感器网络的拓扑结构会动态发生变化，导致变化的因素有：环境因素 或电能耗尽造成的传感器节点故障或者失效；环境变化造成的无线通信链路带宽 变化，甚至时断时通；传感器网络的节点的移动性；新节点的加入等等。这些酗 4 华东帅范大学硕十学位论文基十w s n 定位技术的研究与实现 素要求无线传感器网络能够适应动态的网络变化和具备重构功能。 4 ) 可靠性 由于无线传感器网络通常应用于恶劣环境或者人不可到达的区域，传感器节 点的工作环境可能会遭受太阳的暴晒、风吹雨淋，或者遭到无关人员的无意破坏。 因此，传感器节点需要具备坚固、不易损害以及适应各种恶劣环境条件的特性。 无线传感器网络的可靠性还需要体现在通信的保密性和安全性方面，因为通 常无线传感器网络的应用环境涉及到巨大数目的节点数，网络的维护性很难顾及 到，因此，无线传感器网络尤其需要具有鲁棒性和容错性。 5 1 应用相关性 不同的应用背景对无线传感器网络的硬件软件要求都会有很大的差别，因 此，无线传感器网络没有统一的通信协议平台，每一个具体的应用采用的无线传 感器网络技术也不尽相同。 国以数据为中心 目前盛行的互联网络是以地址为中心的：先有计算机终端系统，然后再互联 为网络，终端系统可以脱离网络而独立存在；。网络设备用网络中唯一的口地址 来标识，资源定位和信息传输都是依赖于终端、路由器、服务器等网络设备的口 地址。而无线传感器网络是任务型的网络，脱离无线传感器网络的传感器节点是 没有意义的。 无线传感器网络节点采用编号标识，根据采用的无线传感器网络协议来确定 是否需要分配全网唯一编号。由于传感器节点是随机部署，构成的传感器网络与 节点编号之问没有必然的联系，节点编号也不跟节点位置有必然的联系，在用户 使用无线传感器网络查询事件时，是直接将所关心的事件通告给网络，而不是通 告给某个固定编号的节点，然后网络获得所关心的事件信息后汇报给用户；这种 方式就是以数据本身为查询或传输线索，通常无线传感器网络就被称为以数据为 中心的网络。 5 华东帅范人学硕卜学位论文基十w s n 定位技术的研究与实现 2 2 无线传感器网络节点 图2 2 无线传感器网络节点体系结构 无线传感器网络有多个网络节点构成，每一个网络节点都会包括数据采集模 块、数据处理和控制模块、无线通信模块和供电模块。其中，数据采集模块由传 感器和a d c 组成，主要负责监测区域内信息的采集和数据转换；数据处理和控 制模块是无线传感器节点的核心模块，它控制整个节点的操作，存储和处理节点 采集的数据以及其他节点发来的数据；无线通信模块负责与其他节点进行无线通 信，交换控制消息和收发数据：供电模块则是节点的电源模块，一般采用电池供 电。 6 华东师范大学硕上学位论文 摹于w s n 定位技术的研究与实现 2 3 无线传感器网络协议栈 图2 - 3 无线传感器网络协议栈 如图2 3 所示，无线传感器网络采用与传统的有线网络的协议栈相似的分层 结构，它包括物理层、数据链路层、网络层、传输层和应用层。与有线网络不同 的地方在于，无线传感器网络协议栈还涉及到定位与跟踪管理、安全管理、时间 同步管理和电源管理等关键技术。这些关键技术也是研究无线传感器网络的热门 问题。下面分别针对无线传感器网络的每一层的功能，做一些详细的描述： 2 3 1 物理层 物理层主要提供简单但健壮的信号调制和无线收发技术，它其实包括 8 0 2 1 5 4 定义的物理层和具体硬件平台两个部分。无线收发技术可以使用射频 ( r f - r a d i of r e q u e n c y ) 和红外( 瓜i n f r a r e d ) 两种方式。由于红外方式的方向性比较受 限，无线传感器网络倾向于采用射频通信。 8 0 2 1 5 4 定义了通讯频带上的3 个免费的频段：2 4 g h z ( 全球) 、4 3 3 m h z ( 欧 洲) 和9 1 7 m h z ( 美国) 。由于是开放的频段，所以可能受其他外部系统的影响比较 显著，使用时一般会采取抗干扰( 其他无线设备的支持) 措施。 2 3 2 数据链路层 数据链路层用于建立可靠的点对点或者点对多点的通信链路，完成数据成 帧、帧检测、媒体访问控s 0 ( m a c ：m e d i u ma c c e s sc o n t r 0 1 ) 和差错控制的功能。其 中媒体访问控制的作用是避免点到点的通讯发乍冲突，m a c 协议不仅要完成组 牛东师范大学硕卜学位论文基于w s n 定位技术的研究与实现 建网络底层基础设施，实现多跳，并具备自组织特性的节点无线通讯的功能，还 要在节点通讯过程中实现平等高效的资源共享。 2 3 3 网络层 无线传感器网络的网络层主要负责路由生成与路由选择。尤其在无线传感器 网络这种自组织性网络中，为激活网络的连通性，节点必须建立有效的机制进行 组网和路由。当前采用的自组织性路由协议可以分成： a ) 表驱动型( p r e a c t i v ep r o t o c o l s ，先验式协议) 每个节点需要不断维护并更新路由表。典型的协议有距离矢量目标序列 等( d s d v ：d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o r ) 。 b ) 按需驱动型( r e a c t i v ep r o t o c o l s ，反应式协议) 节点在需要时才进行路由，源节点发起路由探测过程。典型的协议有动 态源路由( d s r ：d y n a m i c s o u r c e r o u t i n g ) 、按需距离矢量路由( a o d v a d h o c o nd e m a n dd i s t a n c ev e c t o rr o u t i n g ) 等等。 c ) 混合式的路由协议( h y b d dp r o t o c o l s ) 这是表驱动型路由和按需驱动型路由两种类型的结合。典型的协议有区 域性路由协议( z r p ：z o n er o u t i n gp r o t o c 0 1 ) 等等。 网络层的协议除了提供路由生成和选择的功能，还将q o s ( q u a l i t yo f s e r v i c e ) 放在首位，网络层的协议除了要有能力建立无线传感器网络，还需要适应无线传 感器网络的能量受限、计算能力受限以及存储能力受限等特征，通常会遵从以下 一些原则： a ) 优先考虑能量利用率 b ) 数据为中心 c ) 不影响传感器节点探测精度下的数据聚合 d 1 理想的节点定位和目标跟踪 2 3 a 传输层 传输层协议负责数据流的传输控制，是保证通信服务质量的重要部分。当无 线传感器删络需要接入外部网络时，该层是必需的：在这种情况下，工作在i s m 频段的设备可能会出现较高的数据包错误率，因而建立一套端对端的传输与拥塞 控制协议t 叮以更好地满足无线传感器网络的系统应用需求。 8 华东帅范大学碗十学位论文 基于w s n 定位技术的研究1 i 实现 在无线传感器网络的高层采用确认和重传机制，明显比底层复杂的错误处理 控制易于实现可靠的数据传输；此外，由于大量传感器节点的部署，各个传感器 节点通过在局部区域内结合信息进行冗余处理，减少和压缩数据量可以确保传输 数掘的高效性。 2 3 5 应用层 无线传感器网络的应用层包括一系列基于监测任务的应用层软件。因为无线 传感器网络主要应用于对事件的监测，而事件的监测往往需要多个节点上多种传 感器的协作。这种多种不同信息结合的过程称为数据融合，它具有四个显著的特 点： a ) 冗余处理：同一个信号可以被不同的传感器捕获，需要删除重复不必要 的信息； ”补充信息：一种传感器捕获一种特征，多种特征的结合将提供更全面的 信息； c ) 及时信息：多传感器并行采集与处理，可以获得更及时的信息； d ) 低成本信息：为获得准确信息而需要单个功能强大、高价的传感器和多 个多种廉价、功能较弱的传感器共同实现。 9 华东帅范大学硕卜学位论文 基十w s n 定位技术的研究与实现 第3 章定位算法分析 在传感器网络中，定位算法的机制就是依靠有限的已知位置节点，确定其他 未知位置的节点，并在传感器节点中建立起空间对应关系。通常将已知位置的节 点称为参考节点，它们预先被放置好，或者采用g p s 等方法得知其位置；而将 未知位置的节点称为未知节点，定位算法就是根据参考节点来确定未知节点的位 置。 基于无线传感器网络的定位问题一般分成两个层次，第一个层次是关于无线 传感器网络对自身传感器节点的定位问题，第二个层次则以第一个层次为基础， 是关于无线传感器网络对外部目标的跟踪定位。本章将对分别介绍和分析这两个 层次的定位问题。 3 1 节点自身定位 现有的无线传感器网络自身定位方法主要分为两大类：基于测距的方法 ( r a n g eb a s e d ) 和不基于测距的方：# 2 ；( r a n g ef r e e ) 。基于测距的定位机制需要两个节 点之间具有测量相互距离或者角度的能力；而不基于测距的定位机制则仅根据网 络的连通性信息获得位置信息。 3 1 1r a n g eb a s e d 方法 基于测距的定位机制中，定位通过以下两个主要阶段完成： a ) 节点之问获得相互间的距离信息或者角度信息。 b ) 节点利用相互问的距离信息采用某种定位算法计算自身位置。 基于测距得方法主要通过测量以下几种信号来确定节点之间的距离或者角 度：无线信号强度皿s s 0 、到达时间及时间差( t o a ) 、时间差( t d o a ) 和到达角 ( a o a ) 。 下面的章节将对这几种测距方法进行介绍和对比。 3 1 1 1 无线电信号强度测距法 无线电信号强度，又称r s s l ( r a d i os i g n a ls t r e n g t hi n d i c a t o r ) 1 直。已知发射功 率，接收节点通过接收功率，计算传播损耗，再通过理论或者经验的传播模型将 1 0 华东师范人学硕1 学位论文 基寸二w s n 定位技术的研究与实现 传播损耗转换为距离。在自由空日j 中，距发射d 处的天线接收到的信号强度由下 面的公式给出： 公式6 1 p r 似) = p t g t g r ) l 2 ( 4 s t ) 2 d 2 l 其中，p f 为发射功率；p r ( d ) p r ( d ) 为距离d 处的接收功率；衍、g ，分别是 发射天线和接收天线的增益；d 是距离( 单位：m ) ；l 是与传播无关的系统损耗因 子；九是波长( 单位：m ) 。该公式表明，在自由空间中，接收功率随着发射点与 接收点距离的平方衰减。通过测量接收信号的强度，利用这个公式即可计算收发 节点之间的大概距离。 一旦可以得到参考节点与未知节点之间的距离信息，就可以采用三边测量法 或者最大似然估计法计算出未知节点的位置。在三维空间中，三边测量法指的是 已知一个未知节点到三个以上参考节点的距离，就可以确定该点的坐标；三边测 量法在二维空间里可以用几何图形表示为：当得到未知节点到一个参考节点的距 离时，就可以确定，此未知节点在以此参考节点为圆心，以距离为半径的圆上； 如果得到未知节点到3 个参考节点的距离，则3 个圆的交点就是该未知节点的位 置。 上述的公式只是在理想的自由空间中传播的数学模型，实际应用中还存在诸 如反射，多径传播、非视距、天线增益等问题会影响传播损耗。环境的影响造成 了信号传播模型的复杂性。因此，无线电信号强度测距属于比较粗糙( 5 0 ) 的测 距技术。 3 11 2 到达时间测距法 到达时问差( t o a ：t i m eo f 山一v a l ) 测距方法通过信号传播时间来测量距离。 假定信号从参考节点到未知节点的传播时问为t ，信号的传播速度为c ，则参考 节点到未知节点的距离为t c 。这种方法需要接收信号的节点知道信号开始传输 的时刻，所以要求节点的时钟比较精确。 g p s 采用的就是t o a 测距法，它使用高贵高能耗的电子设备来精确同步卫 星时钟。 3 1 1 3 时间差测距法 时间差测距法( t d o a ：t i m ed i f f e r e n c e so f a 喇v a l ) 通过记录两种不同信号( 通 常为无线电信号和超声波信呼) 的到达时| 日j 的差异，根据已知两种信号的传播速 度，直接把时问差转换成距离。 华东师范大学硕f t 位论文基于w s n 定位技术的研究与实现 在二维平面中，双曲线表示为两个定点的距离之差为一个常数的所有点的集 合，而两个定点称作焦点。因此，t d o a 测距方法在二维平面上的几何意义为： 得到未知节点与两个参考节点的距离差，则未知节点的位置处于以两个参考节点 为焦点的双曲线方程上。通过测量得到未知节点所属的两个以上的双曲线方程 时，这些双曲线的交点即为未知节点的位置。 时间差测距法优于到达时间测距法，虽然它也需要较精确的计时功能，但是 由于它采用相对时间来确定节点位置，因而降低了对时间同步的要求。 3 1 1 4 到达角测距法 到达角测距法( a o a ：a n g l eo na 玎i v a l ) 通过阵列天线或者多个接收器结合来 得到相邻节点发送信号的方向，以构成一根从接收机到发射机的方位线。两根以 上的方位线即可确定未知节点的位置。 上述的几种基于测距的定位算法，都是以测量距离或者角度为前提，表3 - 1 从抗干扰能力、硬件实现复杂度和测距误差等方面列出了它们之间的差异，从表 中可以看出，除了r s s i 测距方法，其它三种测距方法具有一个共同的缺点，就 是传感器节点的造价比较高，采用这些测距方法的算法所要研究的重点大部分都 放在如何利用有限的电池资源、如何提高测量距离和角度的准确性方面。 表3 1 几种基于测距定位算法对比 抗干扰能力硬件实现测距误差 r s s i 受电磁干扰，可穿透障碍物不增加额外装置大 t o a 不易受干扰需要额外精确昂小 贵电子设备 t d o a不易受干扰需要额外精确电小 子设备 a o a 易受噪声影响需要额外硬件小 3 1 2r a n g ef r e e 方法 不基于测距的定位算法根据网络的连通性来确定位置，而不需要知道未知节 点到参考节点的距离或者角度，从成本和功耗上来说，它比基于测趴的定位算法 更具有优势。不基于测距的定位算法通常有如下几种：质心法、集i i j 凸优化法、 d v - h o p 法、无定形算f ：麦( a m o r p h o u s ) 、多维定标算法以及三角形内点近似定位算 法。 1 2 华东帅范人学硕l 学位论文基于w s n 定位技术的研究j 实现 3 121 质，b 定位 质心定位算法由南加州大学的n i r u p a m ab u l u s u 等学者提出，是一种基于网 络连通性的室外定位算法。 质心算法中，网络中位置已知的节点被称为信标节点( b e a c o n ) 。信标节点与 前面所说的参考节点相比，它在网络中所占的比例要更大一些，通信能力也强于 参考节点。未知节点首先接收信标节点的无线电信号，通过接收到的信标信号的 数量来确定是否处于该信标节点的覆盖范围内。即确定未知节点与信标节点的连 接关系( c m ) 是否超过一定的阈值。连接关系的计算公式如下所述： 公式6 2 c m 。一n 。q ，t ) n 。d q ，t ) x 1 0 0 其中，c m d 表示信标节点i 和未知节点j 的连接关系，( f ，f ) 表示未知节 点j 在t 时刻收到的信标节点i 发出的定位消息数量，。( f ，f ) 表示在t 时刻信标 节点i 广播的定位消息总数。当未知节点i 与多个信标节点完成这一过程之后， 就取这些信标节点覆盖范围的中心作为自身位置，如下图： 母 已知披燕带点 朱知带点实际位鳖 + 来细节点估计位置 图3 ，1 质心定位算法 质心定位算法最大的优点是计算量小，完全基于网络的连通性，实现方法简 单，缺点是需要比较多的信标节点，对信标节点的要求也比较高，整个系统的代 价会比较大。 3 1 2 2 集中凸优化定位 集中凸优化算法基于如下假设：如果两个节点可以有效的建立通信，节点之 间的距离必定小于节点的通信卜径。 如图3 2 所示，将节点表而、为凸边形的顶点，节点间的距离约束表示为凸边 华东师范犬学硕士学位论史 基于w s n 定位技术的研究j 实现 形的边。则节点的定位问题就可以转化为：网络中有n 个节点，其中m 个节点 坐标( x l ，y l ，x m ，y m ) 已知；把这些已知的点作为参考，算法的目标是 基于凸优化理论寻找满足节点间距离约束的n 。m 个节点的坐标 ( x m + l ，y m + l ，x i i ，y n ) 。凸优化定位算法采用集中计算的方式，所有节 点将与其邻接节点的连接关系以多跳方式发往中心计算机。该算法的定位准确度 易受到已知位置节点数目的影响。 位蒸已知带点 o饺豢未知节点 图3 2 集中凸优化定位 集中凸优化定位的优点是节点本身计算量小，也正因为这样，整个系统需要 中心计算机的支持，系统可扩展性较差，如果发生个别节点失效或者加入了新的 节点，中心计算机都需要重新计算所有节点的位置，会产生大量的通信开销。 3 1 2 3d v - h o p 定位 d v - h o p 算法由d r a g o sn i c u l e s c u 和b n a t h 等人提出，其原理与经典的距离 矢量路由算法很相似。 它的算法核心是：由参考节点向网络广播一个信标( b e a c o n ) ，该信标中包含 了此参考节点的位置信息以及一个初始值为1 的表示跳数( h o p ) 的参数；当此信 标在网络中以泛洪方式传播出去时，每转发一次跳数就要增加1 ；接收节点在它 收到关于某一个参考节点的所有信标中，保存最小跳数值的信标，丢弃其他较大 跳数值的同一参考节点的信标；通过这样的过程，网络中所有的节点都获得了到 每一个参考节点的最小跳数值。为了通过跳数值得到物理距离，系统需要估计网 络中平均每跳的距离。因为参考节点具有到网络内部其他参考节点的跳数值以及 这些参考节点的位置信息，所以参考节点就可以得到与其他参考节点的实际距 离。这样一来，一个参考节点可以得到网络的平均每跳距离，接下来再把它广播 到网络中，也称为校正值。位置未知的节点收到此校正值，即可估算自己到参考 节点的距离。只要一个位置未知的节点能够获得三个以上参考节点的估计距离， 就可以利用三边测蓬法估计其自身的位置。 1 4 华东帅范大学钡l 学位论文 萆于w s n 定位技术的研究j 实现 d v - h o p 算法与基于测距算法具有相似之处，就是都需要获得位置节点到参 考节点的距离，只是它是通过网络中拓扑结构信息而不是无线电信号的测量。 3 1 2 4a m o r p h o u s 定位 a m o r p h o u s 定位一般被称为无形计算定位，它建立在两个前提条件之下：一 是所有节点有效通信半径相同且已知；二是网络布设区内节点密度足够大或网络 连通性较高。 a m o r p h o u s 定位方法与d v - h o p 算法类似，而它获得的距离参考节点的跳数 被称为梯度值。未知节点收集邻居节点的梯度值，计算关于某一个参考节点的局 部梯度平均值。与d v - h o p 算法不同的是，a m o r p h o u s 算法假定预先知道网络的 密度，然后离线计算网络的平均每跳距离，然后获得三个或更多参考节点的梯度 值后，未知节点会计算与每个参考节点的距离，接着使用三边测量法和最大似然 估计法估算自身位置。 3 1 2 5m d s m 嗡- p 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 g ) ，该技术常 用于探索性数据分析或信息可视化。 m d s m a p 算法由3 个步骤组成： a ) 首先从全局角度生成网络拓扑连通图，并为图中每条边赋予距离值。 当节点具有测距能力时，该值就是测距结果。当仅拥有连通性信息 时，所有边赋值为1 。然后使用最短路径算法，如d i j k s t r a 或f l o y d 算法，生成节点间距矩阵： b ) 对节点间距矩阵应用m d s 技术，生成整个网络的2 维或3 维相对坐 标系统； c ) 当拥有足够的参考节点时( 2 维最少3 个，3 维最少4 个) ，将相对坐 标系统转化为绝对坐标系统。 3 1 2 6 三角形内点近似定位 三彳f j 形内点近似定位( a p i t a p p r o x i m a t ep o i n t i n t r i a n g u l a t i o n t e s t ) 算法中，一 毕东师范大学顾上学位论文基fw s n 定位技术的研究t j 实现 个未知节点从它所有能够与之通信的参考节点中选择三个节点，测试它自身在这 三个参考节点所组成的三角形内部还是外部；然后，再选择另外的三个参考节点 进行同样的测试，直到穷尽所有的组合或者达到所需要的精度。如果未知节点在 某三角形内部，称此三角形包含未知节点。最终，未知节点将包含自己的所有三 角形的相交区域的质心作为自己的估计位置。 a p i t 算法的最关键的步骤是测试未知节点是在三个参考节点组成的三角形 内部还是外部，这一测试的理论基础是三角形内点测试( p r r ) 。p i t 测试用来测试 一个节点是在其他3 个节点所组成的三角形内部还是三角形外部。如图3 3 所示， 如果存在一个方向，沿着这个方向，m 同时远离或者同时接近a 、b 、c 三个点， 那么m 位于a a b c 外；否则，m 则位于a b c 内。 玲、影 ，、 ， 、，、 ，愈、 一一一一一一一一一一一一 图3 3 三角形内点测试原理 静态网络中，m 点是固定的，不能朝着不同的方向移动，就不能执行p i t 测 试，所以此定位算法定义为a p i t 测试，即估算p i t ：如果节点m 的邻居节点中 没有同时远离或同时靠近三个参考节点a 、b 、c 的节点，那么m 就在a a b c 之内，否则，m 就在a a b c 之外。 这种方法是利用无线传感器网络中较高的节点密度来模拟节点移动，根据给 定方向上一个节点距离参考节点越远、接收信号强度越弱的无线传播特性来判断 距参考节点的远近。在无线传感器网络中，邻居节点间互相交换信息，仿效p i t 测试的节点移动。当节点m 比较靠近a b c 的一条边，或者m 周围的邻居节点 分布不均匀时，a p i t 的判断可能会发生错误，当未知节点密度较大时，a p i t 判 断发生错误的概率比较小。 华东帅范大学侦l 学位论文 基于w s n 定位技术的研究与实现 3 2 目标定位 节点的自身定位技术属于无线传感器网络的应用支撑技术，而目标定位则是 属于应用层次，并且建立在节点自身定位基础之上的。 目标定位，指的就是无线传感器网络对外部目标的跟踪定位。无线传感器网 络中对目标的跟踪定位实质上就是各个传感器节点之间协作跟踪的过程；目标定 位的技术关键在于如何共享数据信息、协作处理数据和管理参与跟踪的节点组； 它所关心的事件是哪些节点参与跟踪、何时唤醒参与跟踪的节点、跟踪信息的传 播方式和范围、如何传送跟踪数据给控制节点以及节点需要多少时间进行通信等 等。 根据跟踪对象的数量差别，无线传感器网络的目标跟踪定位分为单目标跟踪 和多目标跟踪；根据目标形状的差别，可以分为点目标跟踪和面目标跟踪；根据 传感器节点的运动方式，则分为静态目标的侦测和移动目标的跟踪。 目标跟踪定位的研究主要集中于单目标跟踪。单目标跟踪指的是传感器网络 中的多个节点协作跟踪一个目标；各个节点交换侦测数据，确定目标的位置和运 动轨迹，预测目标的运动方向，并且通过一定的唤醒机制使得目标运动方向上的 节点机是加入跟踪过程。本节将针对单目标跟踪，分别深入讨论单点目标跟踪和 单面目标跟踪。 3 2 1 目标定位过程 基于无线传感器网络的目标定位过程通常包括三个主要阶段：侦测、定位和 通告。 在侦测阶段，无线传感器网络中的传感器节点会定周期地查询传感器模块， 以侦测是否有目标出现；在侦测消息中，通常包括侦测节点的i d 、侦测节点自 身的位置信息以及该侦测节点到目标的距离。在定位阶段，则是通过多个传感器 节点相互协作，采用三角测量、双源检测等算法，确定目标的当前位置，根据节 点位置的历史数据预测和估计目标的运动轨迹。在通告阶段，节点将相互交换信 息，广播目标的预估轨迹，通知和启动轨迹附近的节点加入目标跟踪过程。 3 2 2 单点目标跟踪 对于单点的目标跟踪，本节将介绍三种基本的跟踪模型：双元跟踪模型、信 息协作模，哩以及传送树模型。 1 7 华东师范人学硕卜学位论文基十w s n 定位技术的研究与实现 3 2 2 1 双元检测协作跟踪 双元检测指的足传感器只有两种侦测状态：目标处于传感器侦测范围之内或 者范围之外。如图3 4 所示，其中圆心处为传感器节点，对于节点的侦测距离r ， 当目标距传感器节点的距离在( r - e ) 之内时总会被检测到；当目标距传感器节点 的距离在( r + e ) 之外时不会被检测到；当目标距传感器节点的距离在( r e ) 和( r + e ) 之间时以一定的概率被检测到。通常e 的取值为o 1 r 。 图3 - 4 双元检测传感器模型 双元检测不能检测到目标的距离，只能判断目标是否在侦测范围内。因此检 测到目标的节点只能确定包含目标的圆形区域，需要多个节点协作才能确定目标 的位置信息。当目标进入侦测区域之后，在节点足够密集的情况下，任何时刻都 有多个节点同时侦测到目标的位置区域。这些节点侦测范围的重叠区域是相对较 小的区域，目标就处于这个重叠区域内，以达到相对精确定位的目的。 由于目标运动的不确定性，要跟踪这些运动轨迹是比较复杂的。在不影响跟 踪结果的情况下，假设目标在节点的侦测范围内匀速运动，从而将目标的运动轨 迹近似为一条直线。由于单个传感器节点的侦测范围比较小，这样的假设会比较 接近目标的真实运动轨迹。通过大量节点的协作可以进一步提高跟踪精度。双元 跟踪的基本过程如下： ( 1 ) 节点侦测到目标进入侦测区域。唤醒自身的通信模块并向邻居节点广播 检测到目标的信息。信息中包含节点自身】d 以及自身位置信息。同时该 节点开始记录目标出现的持续时间。 ( 2 ) 如果节点检测到目标出现，同时接收到两个或两个以上节点发送的通告 消息，则节点计算目标位置。计算时采用目标在节点侦测范围内的持续 时间作为权重。 f 3 ) 当目标离开侦测区域时，节点向汇聚节点发送自己的位置信息以及目标 在自己侦测区域内的持续时间信息。汇聚节点根据已有历史数据和当前 获得的最新数据进行线性拟合，计算移动目标的运动轨迹。 牛东师范= 学碘l 学位论史摹f w s n 定位技术的研究1 j 实现 双元检测不能确定到目标的距离，但是可以确定目标在自己检测区域内的持 续时间。如下图所示，假设移动目标匀速运动，则目标在监测区域中的持续时问 越长，就表明它离节点越近，该节点的侦测数据也就越精确。因此检测到目标时 间k 的节点，它的数据应具有较大的权重。 图3 5 目标持续时问长度与计算全权重的关系 基于双元检测的协作跟踪适用于简单低廉的传感器节点，并通过大量密集部 署节点保证跟踪精度。基于双元检测的协作跟踪需要节点间的时间同步，并要求 节点知道自身的位置信息。 3 2 2 2 信息协作跟踪 对移动目标的侦测、分类、跟踪通常需要传感器节点进行协作。对节点跟踪 数据的融合能够有效地提高跟踪精度。通过选择合适的节点进行协作能降低节点 间的数据通信量，从而节省节点能量和通信带宽。协作跟踪的关键在于如何通过 节点问交换跟踪信息实现对目标运动轨迹较为精确的跟踪，同时尽量减少节点的 能量消耗。锝作跟踪的关键问题包括确定让哪些节点进行跟踪；需要获取哪些侦 测数据以及节点间必须交换哪些数据；需要综合考虑节点获得的跟踪信息的有效 性和精确度，以及节点完成跟踪任务需要的能量代价来决定哪些传感器节点应参 与跟踪过程以及跟踪节点间的西作方式。 信息协作跟