（计算机应用技术专业论文）无线传感器网络节点相对定位算法研究.pdf

摘要 无线传感器网络在军事国防、环境监测、抢险救灾和危险区域的远程控制等 诸多领域具有广泛的应用前景。网络节点或监测目标的定位是其中众多应用的一 个关键条件。而且无线传感器网络的某些路由机制、覆盖信息、负载均衡和拓扑 控制等都依赖于网络中传感器节点的位置信息。因此，定位在无线传感器网络的 应用、运行和管理等方面有着重要作用；针对无线传感器网络节点自身定位技术 的研究具有重要的理论与实际意义。 无线传感器网络中的定位问题包括节点自身定位和外部目标定位两部分，其 中后者依赖于前者。本文研究的用于无线传感器网络节点自身定位的相对定位算 法一一聚类s p a 算法( s c a l a b l ea n dd i s t r i b u t e dg p sf r e ep o s i t i o n i n gf o rs e n s o r n e t w o r k s ) ，是该研究领域内一种经典的相对定位算法。它首次提出以节点聚类方 式在无锚节点和无须预先配置网络基础设施的条件下，构建覆盖无线传感器网络 的相对坐标系来进行节点定位，并具有良好的扩展性能。但其不足在于定位过程 逋信开销过大，进而对节点能耗、网络通信负载和定位时耗都造成不良影响。 本文提出相应的改进方法一一局部坐标系构建过程中辅助节点对的优化选择 方法和全局坐标系构盎过程中局部坐标系的优化合并策略，可在不影响原算法定 位覆盖率的前提下，有效降低它在构建本地局部坐标系和合并构建网络全局坐标 系这两个主要过程中的通信开销。最后在j s i m 网络仿真平台上进行仿真实验， 对比算法在改进前后的定位覆盖率、定位误差率和通信丌销值，结果说明改进方 案可行，改进后的算法更具有实用性。 关键字：无线传感器网络；定位算法；节点自身定位；相对定位 无线传感器网络节点相对定位算法研究 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 sh a v eg r e a tp r o s p e c ti nt h ea p p l i c a t i o n so fm i l i t a r y a f f a i r s ，c i r c u m s t a n c e o b s e r v a t i o n ，d i s a s t e rr e l i e fo p e r a t i o n ，d a n g e r o u s a r e a d o m i n a t i o n ，e t c o n eo ft h ek e yq u a l i f i c a t i o n sf o rt h e s ea p p l i c a t i o n si sl o c a l i z a t i o no f t h et a r g e t sn e e d i n gm o n i t o r i n ga n dt h en e t w o r kn o d e a n ds o m er o u t i n gs c h e m e ， i n f o r m a t i o no fn e t w o r kc o v e r a g e ，l o a db a l a n c e ，t o p o l o g yc o n t r o l ，a n ds oo na l s o d e p e n do nt h el o c a t i o ni n f o r m a t i o no ft h en o d e si nn e t w o r k s a l lt h e s ei n d i c a t et h a t l o c a l i z a t i o ni saf u n d a m e n t a la n dc r i t i c a li s s u ef o rt h ea p p l i c a t i o n ，o p e r a t i o na n d m a n a g e m e n to fw i r e l e s ss e n s o rn e t w o r k s ，ra n dt h es t u d yf o rs e l f - p o s i t i o n i n go f w i r e l e s ss e n s o rn e t w o r k sp o s s e s s e sg r e a ts i g n i f i c a n c ei nt h et h e o r ya n dp r a c t i c e ，w i l l b e c o m ea ni m p o r t a n tp a r ti nt h er e s e a r c ha r e a t h el o c a l i z a t i o no fw i r e l e s ss e n s o rn e t w o r k sc a nb eg e n e r a l i z e di nt w op a r t st h a t a r ei nc o r r e l a t i o n ，t h e ya r el o c a l i z a t i o no ft h en o d e si nt h en e t w o r k sa n dt h a to ft h e t a r g e t sn e e d i n gm o n i t o r i n g ，t h el a t e rr e l i e so nt h ef i r s t t h er e l a t i v el o c a l i z a t i o n a l g o r i t h m 一一c l u s t e r i n g b a s e ds p aa l g o r i t h m ( s c a l a b l ea n dd i s t r i b u t e dg p sf r e e p o s i t i o n i n gf o rs e n s o rd e t w o r k s ) ，i sac l a s s i c a la l g o r i t h mt h a tw a sp r e s e n t e df o rt h e l o c a l i z a t i o no fn o d e si nw i r e l e s ss e n s o rn e t w o r k sw i t hn ob e a c o nn o d e sa n da d v a n c e c o n f i g u r a t e d i n f r a s t r u c t u r e i ti sw e l ls c a l a b l e b u tt h ed i s a d v a n t a g e sa r eh e a v y c o m m u n i c a t i o nc o s ta n d c o r r e s p o n d i n g i n f l u e n c eo n e n e g yc o s t ，n e t w o r k c o m m u n i c a t i o nl o a da n dp o s i t i o n i n gt i m e t w oa m e l i o r a t i o nm e t h o d sw e r ep r e s e n t e di nt h i sp a p e r - - o p t i m i z e ds c h e m e s f o rt h ec h o i c eo fa s s i s t a n tn o d e si nt h ec o n s t r u c t i o no ft h el o c a lc o o r d i n a t e s y s t e m ( l c s ) a n df o rt h ec o m b i n a t i o no fl c s si nt h ec o n s t r u c t i o no fn e t w o r k c o o r d i n a t es y s t e m 烈c s ) i tc a r le f f e c t i v e l yr e d u c et h ec o m m u n i c a t i o nc o s ti nt h e c o n s t r u c t i o nc o u r s e so fl c sa n dn c sw i t hn oi n f l u e n c eo nt h el o c a l i z a t i o nc o v e r a g e t h es i m u l a t i o nb a s e do nj - s i ms h o w e dt h ei m p r o v e da l g o r i t h me x h i b i t sl o w e rr a t eo f l o c a l i z a t i o ne r r o ra n dc o m m u n i c a t i o nc o s t c o m p a r i n gw i t ht h eo r i g i n a l ，a n dt h e l o c a l i z a t i o nc o v e r a g er e m a i n st h es a m e i t sp r o v e dt h a tt h ep r e s e n t e da m e l i o r a t i o n s c h e m e sa r ef e a s i b l ea n dt h ei m p r o v e da l g o r i t h mi sm o r ea p p l i c a b l e 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 s ；l o c a l i z a t i o na l g o r i t h m ；s e l f p o s i t i o n i n g a l g o r i t h m ；r e l a t i v el o c a l i z a t i o n ； i l 硕士学位论文 插图索引 图1 1 论文结构图3 图2 1 无线传感器的体系结构5 图2 2w s n 的典型体系结构5 图2 3 传感器网络协议栈6 图2 4w s n 中的锚节点和无线传感器节点9 固2 。5 三边测量法示意图1 0 图2 6 三角测量法示意图1 0 图2 7 极大似然估计法示意图11 图3 1s p a 算法节点的局部坐标计算过程l7 图3 2s p a 算法l r g 的选择1 8 图3 3s p a 算法节点坐标重新计算过程1 8 图3 4 聚类s p a 算法中局部坐标系合并计算示意图1 9 图3 5 算法中扫，g ) 的作用1 9 图3 6 算法中0 ，q ) 的作用1 9 图3 7 全局坐标系的构建过程2 l 图3 8 两种合并方式示意图2 2 图3 9 某w s n 网络拓扑2 2 图4 1j - s i m 体系结构图2 7 图4 2a c a 实体与i c 芯片的类比2 8 图4 3 组件与端口的关系2 8 图4 4 网络规模为栉2 + 2 时的仿真前后的内存消耗量变化3 1 图4 5 框架定义的典型w s n 模块结构图3 1 图4 6s e n s o rn o d e 组件图一3 3 图4 7s i n kn o d e 组件图3 3 图4 8 t a r g e tn o d e 组件图3 3 图4 9w s n 仿真拓扑图3 4 图4 1 0 仿真界面图3 4 图5 d 仿真w s n 拓扑示意图4 4 f f 无线传感器网络节点相对定位算法研究 附表索引 表5 1 仿真实验p c 配置3 5 表5 2 仿真实验网络拓扑参数4 5 表5 3 网络覆盖率4 5 表5 4 定位误差率4 6 表5 5 定位通信量4 7 1 v 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：节仁雾 日期：p 辟；月；。日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“4 ”) 作者签名：衔、要日期：w 耐年；月岁。日 导师签镑以 慨翮年；月如日 硕士学位论文 i i 项目来源 第一章绪论 本课题来源于“中国网上教育平台试点工程”高等教育网上教育系统子项 目，编号t 计高技 2 0 0 0 2 0 3 4 号。 1 2 研究课题的目的与意义 无线传感器潮络 1 4 ( w i r e l e s ss e n s o rn e t w o r k s ，简称w s n ) 是一种全新的信息 获取和处理技术，能够通过所部署的大量无线传感器节点相互协作实时地监测、 感知、采集和处理各种环境或监测对象的信息，这些信息通过无线方式传送到数 据处理中心或基地站。w s n 中的很多特定应用都依赖于传感器节点或者目标物体 的地理位置信息，比如在战场对军事目标位置的判定和森林火灾方位的确定。如 果不能明确被感知信息的地理位置，则所采集的数据是没有意义的。此外，w s n 的网络运行和管理也需要节点位置信息的辅助，比如基于地理信息的路由、资源 的有效配置、计算网络覆盖范围、网络的负载均衡等诸多方面。w s n 中定位问题 的研究正是基于上述广泛的网络管理和应用背景。 w s n 节点的自身定位可以单纯地使用o p s ( o l o b a lp o s i t i o n i n gs y s t e m ) 方式。 这需要为w s n 中的每个传感器节点配置g p s 信号接收器来实现精确定位。但是， 网络规模大、传感器节点成本受限、网络使用区域不在室外以及传感器节点功耗 等诸多因索限制了单纯的g p s 定位方式在w s n 中的使用。目前已经有一些系统 和算法可以较好地解决w s n 的节点自身定位问题。根据定位效果，可以将它们 分为绝对定位和相对定位两类【5 j 。文献【6 】指出，在一定条件下，绝对定位结果可 以转换为相对定位结果。对绝对定位和相对定位的研究发现，前者相对于后者在 定位精度、规模、容错性、自适应性等方面都具有较好的表现，但同时，绝对定 位算法也依赖于网络的基础设施或者依赖于具有g p s 等特殊定位方式的锚节点， 并对网络部署有特定要求，从而可能受限于传感器成本和网络应用环境等原因无 法适用于某些实际应用。相比之下，相对定位算法有着更好的适用性，它不要求 在w s n 中配置中心节点或者锚节点，仅仅要求每个节点具备测距功能即可。 虽然相对定位算法有更好的适用性，但是在性能上还存在着不足，一个比较 突出的问题就是通信开销过大。这势必增加定位过程的时耗，加剧网络中节点的 无线传感器网络节点相对定位算法研究 能耗，加重网络通信负载。本文的主要目的就是分析改进聚类s p a 定位算法，降 低其定位过程的通信开销和定位误差，从而减少定位时耗和对节点的能耗，并提 高定位准确度。 1 3 研究内容 目前，w s n 定位算法有多种分类方法。按计算方式可分为集中式或分布式； 按定位效果可分为绝对式和相对式：按定位手段可分为基于测距技术和非测距， 等等。每一类定位算法都有其自身的特点和适用范围，没有哪一种是绝对最优的 7 , s l 。 本文主要研究w s 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 ) 【9 j ，聚类s p a ( s c a l a b l ea n dd i s t r i b u t e dg p sf r e e p o s i t i o n i n gf o rs e n s o rn e t w o r k s ) 1 0 】和l p s ( 1 0 c a lp o s i t i o n i n gs y s t e m ) 1 1 j 等相对定位算 法的基础上，针对聚类s p a 在局部坐标系构建过程和全局坐标系构建过程中存在 的通信开销过大的问题，提出了局部坐标系构建过程中辅助节点对的优化选择方 法和全局坐标系构建过程中新的局部坐标系合并策略。通过这两个方面的改进来 降低原定位算法存在的定位通信开销和定位误差过大的问题，提高了算法的性能。 本文的另一个研究内容是分析现有的w s n 仿真研究方法。分析、比较了现 有的一些主要w s n 仿真平台：重点介绍了j - s i m l l 2 , 1 3 1 网络仿真平台的内部架构、 仿真设计步骤和仿真机制，研究了j - s i m 用于w s n 仿真的一般方法和步骤。 1 4 本文主要工作 本文的主要工作包括以下几个方面： 介绍w s n 的特点和基本概念；分析w s n 定位算法的研究现状、应用情况和 发展前景；分析比较了几种主要的w s n 模拟仿真平台。 分析聚类s p a 算法的主要思想，针对原算法通信开销过大的缺陷，提出了局 部坐标系构建过程中辅助节点对的优化选择方法和全局坐标系构建过程中局 部坐标系的优化合并策略。 介绍j - s i m 网络建模与仿真平台的内部架构、仿真设计步骤和仿真机制；研究 j - s i m 用于w s n 建模与仿真的一般方法和步骤。 通过扩展j - s i m 的w s n 模块，和构建仿真网络拓扑，在j - s i m 平台上对聚类 s p a 和改进算法进行仿真实验，对仿真结果进行统计和性能分析。 硕士学位论文 1 5 论文结构 本文的结构如图1 1 所示： 绪论 l 相关研究综述 l 基于聚类s p a 算法的改进 l i 基于j s i m 的无线传感器网络建模与仿真 l i 对聚类s p a 和改进算法的仿真实现和分析 l 结论 图1 1 论文结构图 无线传感器网络节点相对定付算法研究 第二章相关研究综述 2 1 无线传感器网络 近十几年来，随着微电机系统、无线通信和数字电子等技术的快速发展使 得具有数据采集、计算处理和无线通信能力的低成本、低功耗、微型传感器的研 制和生产得以成为现实。w s n 就是由大量微型传感器节点以a dh o e 方式组成 的无线网络，其目的是通过所部署的大量无线传感器节点相互协作地感知、采集 和处理网络覆盖范围内的各种监测对象的信息，这些信息再通过无线方式传送到 数据处理中心或基地站。传感器、感知对象和观察者构成了w s n 的三个要素【“】。 w s n 被认为是2 i 世纪最重要的技术之一，它将对人类的生产和生活产生深 远的影响。如果说因特网构成了逻辑上的信息世界，改变了人与人之间的沟通方 式，那么，w s n 就是将逻辑上的信息世界与客观上的物理世界融合在一起，改变 了人类与自然界的交互方式【”】。作为一种全新的信息获取和处理技术，它在军事 国防、环境监测、抢险救灾、危险区域的远程控制等许多领域都具有广泛的应用 前景。 w s n 与传统的无线网络有着不同的设计目标和技术要求，即使是a dh o e 网 络的协议和算法也未必适合其特点和应用条件。它的特殊性和广阔的应用前景给 研究人员提出了大量有挑战性的研究课题。 2 1 1 无线传感器的体系结构 在不同的应用中，传感器节点的结构不尽相同，但一般都由传感单元、数据 处理单元、数据收发单元、电源单元等功能模块组成。传感单元由各类传感器及 数模转换设备组成，传感器的类型是由被监测物理信号的形式决定的；数据处理通 常选用低功耗嵌入式微控制器；数据传输单元主要由相应的通信协议( 主要是 m a c 协议) 及低功耗、短距离的无线通信模块组成。因为需要进行较复杂的任务 调度与管理，系统还需要个微型化的实时操作系统，加州大学伯克利分校为此专 门开发了t i n y o s i j ，另外还有u c o s - i i 等。电源是影响节点寿命的关键因素。图 2 1 描述了无线传感器节点的一般组成。除此之外，根据具体应用的需要，可能还 会有定位系统、电源再生单元和移动单元等。 会有定位系统、电源再生单元和移动单元等。 硕士学位论文 圈2 1 无线传感器的体系结构【1 ) 2 1 2 无线传惑器网络的体系结构 堡墨叁生墅_ 一个典型的传感器网络由传感器节点( s e n s o rn o d e ) 、汇聚节点( s i n kn o d e ) 、 i n t e r n e t 或通信卫星、任务管理节点等部分构成。传感器节点任意散落在被监测 区域内，这一过程是通过飞行器撒播、人工埋置和火箭弹射等方式完成的。节点 再以自组织形式构成网络。每个节点都可以收集数据，并通过“多跳”路由方式把数 据传送到汇聚节点。它也可以用同样的方式将信息发送给各节点。汇聚节点直接 与i n t e r a c t 或通信卫星相连，通过i n t e r n e t 或通信卫星实现任务管理节点( 即观察者) 与传感器之间的通信。用户通过管理节点对传感器网络进行配置和管理，发布监 测任务以及收集监测数据。图2 2 描述了w s n 的基本体系结构，但是针对特定的应 用环境，网络的结构可以有所不同。 用户 圜 图2 2w s n 的典型体系结构【1 】 2 1 3 无线传感器网络的协议层次 根据网络的体系结构和具体应用范围的不同，w s n 的协议层次也不完全相 无线传感器网络节点相对定位算法研究 同，并且到目前为止，还没有形成w s n 的标准协议栈。最典型的情况是自下而 上包含物理层、数据链路层、网络层、传输层、应用层；另外，协议栈还包括能 量管理平台、移动管理平台和任务管理平台。如图2 3 ( a ) 所示： 匣 二 垂 ( a )( b ) 图2 3 传感器网络协议栈1 5 】 物理层：负责提供简单而健壮的信号调制和无线收发技术。 数据链路层：数据链路层负责介质访问控制( m a c ) 和差错控制。 网络层：网络层协议负责路由发现和维护，是w s n 的重要协议层，也是目前 研究的热点之一。 传输层：传输层负责将传感器网络的数据提供给外部网络，比如因特网。 应用层：包括一系列基于监测任务的应用软件。 能量管理平台：管理传感器节点如何使用能源，在各个协议层都需要考虑节 省能量。 移动管理平台；监测并注册传感器节点的移动，维护到汇聚节点的路由，使 传感器节点能动态跟踪其邻居的位置。 任务管理平台：在一个给定的区域内平衡和调度监测任务。 图2 3 ( b ) 是在上一种协议栈的基础上经过改进得到的另一种协议栈模型。 2 1 4 无线传感器网络的相关应用 w s n 作为一种全新的信息获取和处理技术，特别适用于完成大规模、复杂的 监测和追踪任务。其广泛的应用前景体现在许多领域。 军事应用：w s n 具有可快速部署、可自组织、隐蔽性强和高容错性等特点， 因此非常适合在军事上应用。无线传感器节点可以被大量投放到敌方控制区或者 冲突区，实现对敌军兵力和武器装备的监控、战场的实时监视、孜方军事目标的 定位、战场评估、核攻击和生物化学攻击的监测和搜索等功能。 生态环境研究 1 7 , 1 8 】：w s n 在生态环境方面可用于观测农作物灌溉和生长情 6 硕士学位论文 _ _ _ - _ 1 11 1 i _ _ _ - _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - _ 况、土壤和空气成分、野生动物的生存状况和大面积的地表监测，准确及时预报 森林火灾、山洪爆发和泥石流等灾害。 医疗护理：可以在病人身上安装用于检测身体机能的微型传感器节点，他们 可对病人的心率和血压等生理指标进行远程实时检测【l9 1 ，并将信息汇总传送给医 生，进行及时处理，为远程医疗创造条件；利用w s n 长期收集被观察者的人体生 理数据，对了解人体健康状况和研制新药品都很有帮助。 空间探索：可以借助航天器向外星球表面大量撒播无线传感器节点，建立大 规模的w s n 来感知收集外星球表面的环境数据，然后通过卫星信道传输给外太空 轨道上的航天器或探测卫星。由于w s n 具有很好的抗毁性和自组织性，如果能很 好的解决能量供给闯题，则可以作为一种长期、可靠的外星球环境探测方式。美 国宇航局喷气推进实验室研制了s e n s o rw e b s 2 0 】，用于将来对火星的科学探测。 除了上述列出的一些应用领域，w s n 还将广泛用于工业控制、智能交通、智 能农业和智能建筑等。总之，w s n 的应用将深入人类社会生产和生活的各个领域， 将成为影响人类未来生存状态的一项重大科技创新。 2 1 5 无线传感器网络拘研究现状 传感器网络的挑战性也为研究人员提供了广阔的研究空间。美国军方最先开 始这一领域的研究，并且投入巨大。目前，军事部门、民用领域和学术界都在对 其开展深入而广泛的研究。 在军事领域，美国陆军提出的“智能传感器网络通信计划”、“无人值守地 面传感器群”项目，美国海军确立的“传感器组网系统”项目、“协同作战能力” 研究等。 在民用领域，美国交通部1 9 9 5 年提出“国家智能交通系统项目规划”，i n t e l 公司2 0 0 2 年发布“基于微型传感器网络韵新型计算发展规划”等。 在学术界，美国的多个著名高校和研究机构都在从事w s n 的理论和应用方面 的研究，并且处于领先地位。比如，加州大学伯克利分校研制的传感器系统“智 能尘埃”( s m a r t d u s t ) ，其体积只有一立方毫米，可以悬浮在空中；并研制了传感 器操作系统t i n y o s 1 6 1 和感知数据库系统t i n y d b 2 1 1 。加州大学洛杉矶分校研制了 w i n 8 无线集成网络传感器( w i r e l e s si n t e g r a t e dn e t w o r ks e n s o r s ) 。麻省理工学院致 力于基于知识的信号处理技术。哈佛大学研究传感器网络中通讯i 的理论基础。 在国内，中科院上海微系统研究所、沈阳自动化所、软件研究所、计算所、 电子所、自动化所和合肥智能技术研究所等科研机构，哈尔滨工业大学、清华大 学、北京邮电大学、西北工业大学、天津大学和国防科技大学等脘校在国内较早 开展了这一领域的研究，并已经取得一些初步成果。 无线传感器网络节点相对定位算法研究 2 2 无线传感器网络定位算法的研究现状 定位，简单的说就是确定目标的位置信息。在w s n 中，位置信息对传感器网 络的监测活动至关重要，事件发生的位置或获取信息的节点位置是传感器节点监 测消息中所包含的重要信息。 w s n 中定位算法的研究有着重要的意义，这主要体现在两个方面： 1 、w s n 中的很多特定应用都依赖于传感器节点或者目标物体的地理位置信 息，不知道传感器位置而感知的数据是没有意义的。比如在战场中对敌方军事目 标的定位可以有利于集中火力进行打击；在智能交通应用中，可以监测特定车辆 的位置和运动情况；在目标跟踪应用中，实时监视目标的行动路线，预测目标的 前进轨迹等等。 2 、w s n 的网络运行和管理也需要节点位置信息的辅助。例如基于地理信息 的路由、资源的有效配置、对外部目标的定位和追踪、计算网络覆盖范围2 2 1 、控 制网络的负载均衡等。 根据w s n 的特点，其定位算法必须具备以下特点： 1 、自组织性：传感器节点随机分布，不能依靠全局的基础设施协助定位。 2 、健壮性：传感器节点的硬件配置低、能量少、可靠性差，测量距离时会产 生误差，算法必须具备良好的健壮性。 3 、能量有效性：尽可能地减少定位算法中计算的复杂性、减少节点间的通信 开销，以尽量长的延长网络中的生存周期。通信开销时传感器网络的主要能量开 销。 2 2 1 定位算法的相关概念 在w s n 节点自身定位算法的研究中，根据节点是否已知自身的位置信息，把 传感器节点分类为锚节点( b e a c o nn o d e ) 和未知节点( u n k n o w nn o d e ) 。锚节点通过人 工部署或配置g p s 定位设备等手段获得自身的精确位置信息，它们在w s n 中所占 的比例比较小，其部署目的就是协助未知节点进行定位。而分布在w s n 中的未知 节点则是依靠锚节点提供的辅助信息，按照一定的算法来计算得到自身的估计位 置。锚节点和未知节点在w s n 中的部署关系如图2 4 所示。 硕士学位论文 o 图2 4w s n 中的锚节点和无线传感器节点 其他的相关概念【。知包括： 邻居节点( n e i g h b o r n o d e ) ：指传感器节点通信半径内的所有其他节点。 跳数( h o pc o u n t ) ：指两个节点之间间隔的跳段总数。 跳段距离( h o p d i s t a n c e ) ：指两个节点之间间隔的各跳距离之和。 基础设施( i n f r a s t r u c t u r e ) ：指协助传感器节点定位的已知自身位置的固定设 施。 到达时间( 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 v i a l ，t d o a ) ：指两种不同传播速度的信 号从一个节点传播到另一个节点所需要的时间之差。 接受信号强度指数( 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 ) 指节点接收到 的无线信号的强度大小。 到达角度( a n g l eo f a r r i v a l ，a o a ) ：指节点接受到的信号相对于自身轴线的 角度。 视线关系( 1 i n eo f s i g h t ，l o s ) ：指两个节点之间没有障碍物间隔，能够之间 无线通信。 非视线关系( n ol i n eo fs i g h t ，n l o s ) ：指两个节点之问存在障碍物。 2 2 2 节点二维坐标计算方法 传感器节点定位过程中，未知节点在获得对于邻近锚节点的距离或邻近锚节 点与未知节点之间的相对角度后，通常使用以下三种方法计算自己的估计位置。 1 ) 三边测量法( t r 订a t e r a t i o n ) f 1 5 , 2 3 1 三边测量法原理如图2 5 所示，已知a 、b 、c 三个节点的坐标分别为( 勋，弘) ， ，y b ) ，x c ，y o ) ，以及它们到未知节点d 的距离分别为函，d b ，正，假设节点d 的 坐标为( x ，y ) 。 那么存在下列方程组： 9 无线传感器网络节点相对定位算法研究 ，j 一一、 、 j f ， ， _ ， 图2 5 三边测量法示意图f 1 5 】图2 6 三角测薰法示意图【1 5 】 g 一勘) 2 + ( ，一p ) 2 = 如 瓜j 矿砑：击 瓜j 矿面i 了：反 由上式可得节点d 的坐标为： m 2 一珏) l y j2 【2 一n ) ( 2 1 ) 2 ) - _ - - 角测量法( t r i a n g u i a t i 仰) i i l 5 , 2 3 1 三角测量法原理如图2 6 所示，已知a ，b ，c - - 个节点的坐标分别为k ，弦) ， ，y b ) ，k ，弘) ，节点d 相对于节点a ，b ，c 的角度分别是：z a d b ，z a d c ，么 b d c ，假定节点d 的坐标为( y ) 。 对于节点a ，c 和a d c ，如果弧段a c 在a b c 内，那么能够唯一确定一个 圆，设圆心为d l l ，y 0 1 ) ，半径为九，那么口= _ , 4 0 l c = ( 2 石一2 - , 4 d c ) ，并且存在 下列方程组： 妊再习面i 了：， 振；习可面i 可：九( 2 2 ) ( 蟊一溉) 2 + 挑一弦) 2 = 2 r l2 2 r , 2c o s o f 由上式能够确定圆心d - 的坐标和半径r 1 。同理对a ，b ，a d b 和b ，c ，z b d c 分别确定相应的圆心d 2 如2 ，y 0 2 ) 、半径r 2 、圆心d 3 3 ，y 0 3 ) 、半径，3 。 最后利用三边测量法，由点d 0 ，y ) ，o ，( 妒- ，y 0 2 ) ，o z ：，弦：) 和o ，( 加，弘，) 确定d 点坐标。 3 ) 极大似然估计法( 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 ”】 极大似然估计法原理如图2 7 所示，已知l ，2 ，3 等n 个节点的坐标分别是 0 一，印) ，g ：，y 2 ) ，g ，”) ，p ) ，它们到节点d 的距离分别是d - ，凼，砒， 1 0 1ll，j 2 2 西西 一 一 2 2 正面+ + 2 2 弘弦 一 一 弦p + + 托 鼽 一 一 2 2 勋 勘 。l 一 川u 弦弦 一 一 如曲 2 2 硕士学位论文 函，假设节点d 的坐标为g ，力。 l 5 i g 一x ) 2 + 幻一y ) 2 - - d 1 2 ； ( 2 3 ) i 一x ) 2 + 幻一) ，) 2 = 晶2 i x l 2 一舶2 2 g 1 一x ) x + y 1 2 一p 2 2 ( y l 一 砂= d 1 2 一而2 ；( 2 4 ) l 赫一1 2 一知2 2 ( 轴一i 一抽b + p 1 2 一弦2 2 幻一l p 抄= 痈一1 2 函2 爿= 蓑：二，l ：二二， ，6 ；x 1 2 - x h 2 + y 1 2 - - y n l 2 二2 + - 凶d ：1 2 一磊一。：1 ，x = r i 肛k 叫。一p ) j 一! 埘j 一2 j 使用标准的最小均方差估计方法可得节点d 的坐标：j ：“r a ) - 1 4 r b 。 w s n 自身定位系统和算法的性能直接影响其可用性。目前定位算法性能评价 的模型化和量化还是个热点问题。不过已经有研究人员提出了某些可行的评价指 标。文献【7 】中给予了总结。 定位精度：这是定位技术的首要指标，只有满足一定定位精度的定位系统才 有实用价值。一般用误差值与节点无线射程的比例表示。 定位规模：不同的定位系统的有效定位规模是不同的；并且，在一定时间内， 不同定位系统能够定位的目标数量也是不同的。 无线传感器网络节点相对定位算法研究 锚节点密度：某些依赖锚节点进行定位的系统和算法，其性能会随着锚节点 的密度发生很大变化。一般锚节点的密度越大，定位效果越好，但定位的成本也 就越大。 节点密度：因为节点密度会影响w s n 的网络连通度，在连通度大的网络中， 节点可以获得更多的定位辅助信息。某些算法只有在节点部署密集的情况下才能 有好的定位性能，相反，对于稀疏的w s n 网络，其定位性能会有很大下降。 容错性和自适应性：通常定位系统和算法都需要比较理想的无线通信环境和 可靠的网络节点设备。但在真实应用场合中常会有诸如以下的问题：外界环境中 存在严重的多径传播、衰减、非视距( n o n 1 i n e o f s i g h t ，简称n l o s ) 、通信盲点等 问题；网络节点由于周围环境或自身原因( 如电池耗尽、物理损伤) 而出现失效的 问题；外界影响和节点硬件精度限制造成距离或角度测量误差增大的问题。因此， 定位系统和算法的软、硬件必须具有很强的容错性和自适应性，能够通过自动调 整或重构纠正错误、适应环境、减小各种误差的影响，以提高定位精度。但这也 相应地提高了定位系统和算法的复杂度，要耗费更大的定位代价。 功耗：功耗是对w s n 的设计和实现影响最大的因素之一。由于传感器节点 电池能量有限，因此在保证定位精度的前提下，与功耗密切相关的定位所需的计算 量、通信开销、存储开销、时间复杂性是一组关键性指标。 代价：定位系统或算法的代价可从几个不同方面来评价时间代价包括一个系 统的安装时间、配置时间、定位所需时间。空间代价包括一个定位系统或算法所 需的基础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一种定位系 统或算法的基础设施、节点设备的总费用。 以上七个评价指标在一定程度上给研究人员提供了一个评价、设计和实现定 位系统和算法的具体准则和要求。但是，它们是相互关联的，在使用时必须根据 具体情况做出权衡，以选择和设计适于具体应用的定位系统和算法。 2 2 4 定位算法的分类 w s n 定位算法的分类方法有多种，以下是几种常见的分类方法： 1 ) 基于测距的( r a n g e b a s e d ) 定位和无需测距( r a n g e - f r e e ) 的定位【2 4 】 基于测距的定位通过测量节点间点到点的距离或角度信息，并使用三边测量 法、三角测量法或最大似然估计法定位法计算节点位置；而无需测距的定位则仅 仅依靠网络连通性等信息进行定位。前者通常使用的测距技术有r s s i 2 5 1 、t o a 2 们、 a o a 【2 ”、t d o a 2 8 】。为了采用基于测距的定位算法，就必须在传感器节点上额外 配备测距装置，这在一定程度上增加了节点的成本和功耗，并且由于目前的测距 技术误差比较大，这直接影响了节点定位的精度，一般的做法是通过多次测量和 硕士学位论文 循环定位求精【2 9 1 来减小测距误差对定位韵影响，但这一过程又需要额外的计算量 和通信量。基于测距的定位算法与无需测距的定位算法相比虽然有着成本较高、 能耗较高、计算量和通信量较大的不足，但是前者的定位精度一般都要比后者高。 可以相信，随着技术进步，更精确、能耗更小的测距技术韵出现，以及对定位精 度的更高要求，基于测距的定位算法将获得更好的发展空间。 目前对于两种定位方式的研究都出了很多成果，例如基于测距的定位系统和 算法有c r i c k e t 定位系统f 3 御、s p a ( s e i f p o s i t i o n i n ga l g o r i t h m ) 相对定位算法i 叭、 t w o p h a s ep o s i t i o n i n g 定位算法【2 9 1 、n - h o pm u l t i l a t e r a t i o np r i m i t i v e 定位算法f 3 1 】和 t p s 定位算法【3 2 】等；无需测距的定位算法有a p s 算法集f 3 3 ，3 4 l 中的d v h o p 定位算 法、m d s m a p 算法t 3 5 和c o n v e xp o s i t i o n e s t i m a t i o n 定位算法1 3 6 i 等。 2 ) 绝对定位和相对定位p 绝对定位必须让所有的特定位节点使用共同的参照系，其定位结果是一个全 局性的标准坐标位置，比如用经度和纬度表示出来。对同一地理位置的节点进行 多次绝对定位，其定位结果将是一样的，而采用相对定位，结果则可能不同。相 对定位可以让每个定位节点使用不同的参照系，通常是以网络中的部分节点为参 考，建立整个网络的相对坐标系统。文献【5 】指出，在一定条件下，绝对定位结果 可以转换为相对定位结果。 相比而言，绝对定位可为阚络提供唯一的命名空间，受节点移动性影响较小， 有更广泛的应用领域，但在相对定位的基础上也能够实现部分路由协议，尤其是基 于地理位置的路由( g e o - r o u t i n g ) 0 7 1 。通常为了实现绝对定位，需要在网络内部署 一定比例的锚节点或中心节点，而相对定位不需要锚节点和中心节点。总之，绝 对定位算法依赖于网络的基础设施或具有g p s 等特殊定位方式的锚节点，并对网 络部署有特定要求，从而可能受限于传感器成本和网络应用环境等原因无法适用 于某些实际应用。典型的绝对定位算法有n h o pu l t i l