（计算机软件与理论专业论文）无线传感器网络中定位算法的研究.pdf

无线传感器网络中定位算法的研究 摘要 微机电系统、片上系统和无线通信技术的进步孕育了无线传感器网络。 网络中的节点具有体积小，价格低并且具有传感和计算能力等特点，由于 这些特性，它们可应用于各种不同的区域，但同时又由于环境的复杂性， 也会给研究者提出很大的挑战，而传感器网络中的节点定位问题因为与实 际的很多应用直接相关而尤为受到关注。 本文介绍了一种基于分簇的多跳相对定位算法一一m r l a c 算法。 m r l a c 算法是一种不基于锚节点的分布式定位算法，其基本思想是将整 个网络分成很多个拥有头节点的簇，然后再建立局部坐标系并且在每个簇 内对节点进行局部定位，最后通过合并所有簇的方法对节点进行全局定 位。 仿真结果表明，m r l a c 算法在低功耗运行的同时，其定位精度相对 同类算法更高。 关键字：无线传感器网络、定位算法、 ar e s e a r c ho fl o c a l i z a t i o na l g o r i t h m i nw i r e l e s ss e n s o r n e t w o r k s a b s t r a c t a d v a n c e si nm 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 ) ，s o c ( s y s t e m o nc h i p ) a n dw i r e l e s sc o m m u n i c a t i o n sh a v em a d ew s n ( w i r e l e s ss e n s o r n e t w o r k ) p o s s i b l e t h e s en o d e sw h i c ha r ev e r ys m a l l ，s m a r t ，a n dc h e a p s e n s i n ga n dc o m p u t i n gd e v i c e sw i l lb ea p p l i e di nm a n yd i f f e r e n ta r e a si n f u t u r e t h e yp r e s e n tm a n yc h a l l e n g e sb e c a u s et h e ya r ec l o s e l yc o u p l e dt ot h e p h y s i c a lw o r l d ，a n dn o d el o c a l i z a t i o nh a sb e e nat o p i co fa c t i v er e s e a r c hi n r e c e n ty e a r sb e c a u s el o c a l i z a t i o ni se s s e n t i a lo fm a n ya p p l i c a t i o n s i nt h i sd i s s e r t a t i o n ，w ep r e s e n tm r l a c ，am u l t i h o pr 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 b a s e dc l u s t e r , w h i c hi sad i s t r i b u t e da n c h o r - f r e ei o c a l i z a t i o n a l g o r i t h m m r l a ci sa c h i e v e db yd i v i d i n gt h en e t w o r ki n t om a n ym u l t i - h o p c l u s t e r se a c hw i t hi t so w nc l u s t e rh e a dn o d e e a c hc l u s t e rh e a di sr e s p o n s i b l e f o rb u i l d i n gal o c a lr e l a t i v em a pc o r r e s p o n d i n gt oi t sc l u s t e r t oo b t a i nt h e g l o b a lr e l a t i v et o p o l o g yo ft h en e t w o r k ，t h ec l u s t e r sc o l l a b o r a t i v e l yc o m b i n e t h e i rl o c a lm a p s s i m u l a t i o nr e s u l t ss h o wt h a tm r l a ci sa b l et oa c h i e v ea c c u r a c yb e t t e r t h a nt h ec u r r e n ta d h o cl o c a l i z a t i o na l g o r i t h m s ，i nl o w - p o w e ro p e r a t i o na tt h e s a m et i m e 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 ，c l u s t e r 圈2 1 三边测量法。 图表清单 图2 2 原子多边测量技术 图2 3 协作多边测量技术 图3 1 簇的形成 图3 2 建立簇内坐标系 图3 3 簇坐标系的变换 图3 4 簇头节点的算法流程图 。1 0 。2 l 图3 5 非簇头节点的算法流程图 图3 6 基于两个参考节点的估算 。2 7 2 8 图3 7 第三个参考节点的作用3 0 图3 8 两个参考节点产生的误差3 0 图3 9 第三个参考节点产生的误差。 图3 1 0 三角形形状的决定因素。 图3 1 1 构造局部坐标系 图3 1 2 测距误差对定位的影响 图3 1 3 两点定位法 图3 1 4 簇对的相交与重叠 图3 1 5 簇间连通图 图3 1 6 坐标系的转换 3 l 3 2 3 3 3 5 3 6 3 8 图4 in s 2 体系结构4 3 图4 2n s 2 的w s n 仿真流程4 3 图4 3p 对c 的影响( k = 2 ) 4 6 图4 4p 对c 的影响( d = 7 ) 4 6 图4 5d 对c 的影响( p = 1 5 ) 4 7 图4 6k 对c 的影响( p = 1 5 ) 4 7 图4 7 4 r l a c 算法与m d s - m a p ( p ) 算法定位精度的对比 4 8 表格清单 表2 i 各种现有算法的比较1 7 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究_ i 作及取得的研究成果据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得金胆王些太堂 或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 签字日期；年月 日 学位论文版权使用授权书 本学位论文作者完全了解金篷王丝盍堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权盒照 王些盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：年月 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 黜锄c 中 蝴吲啊年细日 电话： 邮编： 致谢 业精于勤，下笔五万言；时光荏苒，三年弹指间。在此篇毕业论文完 成之际，回首过往，感慨良多三年的研究生生涯留下的虽不是笔浓墨 重彩，却也让我久久不能释怀如果用一颗二十六岁的心去感慨人生的无 常和爱的伟大，确有些为赋新词强说愁的味道，我能做的，也只能用这一 小段篇幅去感谢那些曾经给过我帮助和关爱的人。 最要感谢的人是我的导师周健副教授。几年中，周老师无论在学业上 还是在生活上，对我的帮助和关心都是贯穿始终的。在学业方面，周老师 严谨的治学态度和孜孜不倦的探求精神对我是一种无声的鞭策，在具体的 问题上，他总是能用一种交流的方式给我最信服的答案。尤其在毕业论文 期间，周老师从论文的选题、开题到最后的开发和写作，都给了我很多宝 贵的参考意见，并利用不多的休息时间对我的论文进行了审阅和修改。在 生活上，周老师严于律己，宽以待入，他风趣幽默的谈吐和张驰有度的个 性都给我很大的影响，这些也将会是我今后生活中的财富。 老师的帮助和关心让我感激不尽，而父母的爱却难以付诸支字片语。 父爱是厚重的，当我成功对，父亲的理智提醒我戒骄戒躁，失落时，父亲 的坚毅帮助我重拾信心。他是我的骄傲，他的身影在我的心中是一座没有 颜色的大山，让我清醒，给我依靠。母爱是无形的，那些叮咛和暖语早已 成为我生命的一部份，它们或许并不精彩，却给我的心一个恬静温馨的去 处，而母亲永远在那里等我，帮我洗去身上的尘土，让我停泊。 需要感谢的人还有很多，然而论文的结尾和电影不同，不用列出一串 冗长的感谢名单，在此，我向曾经帮助过我的兄弟和朋友们一并表示诚挚 的谢意。 1 1 研究背景 第一章绪论 当计算机的运算速度突飞猛进，使数据处理能力和计算能力迅速提高后； 当存储器的容量无线增长，使海量存储终于得以实现时：当网络的带宽一再提 升，传输数据已变得轻而易举时，人们却发现，与这些技术的发展不协调的是 信息的采集和获取手段已大大落后了于是，融合了传感器技术、信息处理技 术和网络通信技术的无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ) 技术应运而 生了。 随着传感器技术、嵌入式计算技术、通信技术和半导体与微机电系统制造 技术的飞速发展，具有感知、计算存储和通信能力的微型传感器开始出现在军 事、工业、农业和宇航各个领域【l 】。无线传感器网络是集传感器执行器、控制 器和通信装置于一体，集传感能力，计算能力，通信能力于一身的资源受限( 计 算、存储和能源) 的嵌入式设备。由这些微型传感器构成的无线传感器网络能 够实时监测、感知和采集网络分布区域内的各种监测对象信息，并对这些信息 进行处理，传送给需要这些信息的用户 无线传感器网络是一种无基础设施的无线网络。该技术被认为是2 l 世纪最 重要的技术之一，它将会对人类未来的生活方式产生巨大影响。麻省理工学院 的技术评论杂志评出了对人类未来生活产生深远影响的十大新兴技术，无 线传感器网络即位于这十种新技术之首。 1 1 1 国内外研究现状 根据研究侧重点的不同，我们认为可以把无线传感器网络从2 0 世纪9 0 年 代开始到现在的发展历程划分为三个阶段。第一阶段主要致力于小型化、低功 耗、低成本的传感器节点的开发和研制，出现了众多的传感器节点；第二阶段 则对无线传感器网络作为通信网络的特性研究，特别是通信协议的设计和实现。 这个阶段，研究学者们设计提出了许多的通信协议，特别是数据链路层的m a c 协议和网络层的路由协议。第三阶段，侧重于对无线传感器网络的群体智能行 为的研究。目前的研究正处于第二、第三阶段 第一阶段的研究主要来自美国军方和自然基金委的资助一些项目 1 9 7 8 年由美国国防部高级研究计划署( d a r p a ) 在宾西法尼亚州匹兹堡的 卡内基一梅隆大学( c a r n e g i e - m e l l o nu n i v e r s i t yi np i t t s b u r g h ，p e n n s y l v a n i a ) 主 办的分布式传感器网络研讨会，由于军事防御系统的需要，提出对传感器网络 的通信与计算之间的权衡展开研究这些军事需求引起美国军方的高度重视， 并从2 0 世纪9 0 年代开始了一系列的项目研究f 2 】。 1 9 9 3 年开始的无线集成网络传感器( 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 。 w i n s ) 项目，由美国加州大学洛杉矶分校( u n i v e r s i t yo fc a l i f o r n i aa tl o s a n g e l e s 。u c l a ) 和罗克维尔自动化中心共同开发。该项目涵盖了无线传感器网 络设计的各个方面，包括m e m s 传感器、通信芯片的电路级设计、信号处理体 系，组网通信协议设计和传感检测的基础理论研究。 1 9 9 6 年开始的由m i t ( m a s s a c h u s e t t si n s t i t u t eo f t e c h n o l o g y ) 承担的u a m p s ( m i c r o a d a p t i v e m u l t i d o m a i n p o w e r a w a r es e n s o r s ) 项目致力于开发一个完整 的面向低功耗需求的无线传感器网络系统。u a m p s 的研究，产生了无线传感器 网络中一个重要的协议，即低能耗白适应集群分层协议( l e a c h ) 。 1 9 9 8 年开始的致力于研究大规模分布式军事传感系统的无线专用网络的 s e n s l t ( s e n s o ri n f c i r m a t i o nt e c h n o l o g y ) 项目，该项目一共由2 9 个子项目组成， 由包括u cb e r k e l e y 、u c l a 、m i t 、哈佛在内的2 5 个研究机构共同承担。s e n s i t 项目的首要任务是为网络化微传感器开发所有需要的软件。 u cb e r k e l e y 的j a nm r a b a e y 于1 9 9 9 年开始了p i c o r a d i o 项目，研究自约 束的中等规模的具有低成本、低功耗节点的无线专用网络。p i c o r a d i o 的物理层 采用直接序列扩频技术，m a c 结合采用扩频技术和c s m a 机制。 s m a r td u s t 项目开始于1 9 9 9 年，并于2 0 0 1 年完成，研制出体积不超过一立 方毫米、使用太阳能电池供电、具有光通信能力、可悬浮在空中的自治传感器 节点一一“智能尘埃”( s m a r td u s t ) ，用于在战场上抛撤数千个微小的无线传 感器，监控敌人的活动情况而不让敌方察觉，把重要的情报发送给中央司令部。 s e a w e b 项目旨在建立用于海洋学的水声网( u n d e r w a t e ra c o u s t i c n e t w o r k s ) 水声网的低功耗、低数据吞吐量、大覆盖范围、高数据时延容忍等 特性都与无线传感器网络相似。 无线传感器网络发展的第一阶段，开发出了许多传感器节点和研究平台， 代表性的节点有u c l a 和r o c k w e l l 自动化中心研制的w i n s 节点，m i t 研制 的u a m p s 节点，u cb e r k e l e y 的s m a r td u s t 节点和u cb e r k e l e y 的m o t e s 节点 等。在这些平台中，m o t e s 硬件平台及其配套的t i n y o s 操作系统应用最为广泛， 为全球4 0 0 多家研究机构所采用。 第一阶段也对无线传感器网络的通信协议进行了一些研究和设计，主要是 将a d h o c 网络中的相关协议( 比如8 0 2 1 l 等) 进行改进，增加对能耗有效性的 支持而在无线传感器网络发展的第二阶段，开始对无线传感器网络作为通信 网络进行了大量的通信协议设计和开发，出现了许许多多的m a c 协议和路由 协议此外，第二阶段也开始对无线传感器网络的信息处理、数据查询、部署 覆盖等应用和中问件的相关问题进行越来越深入的研究，包括与其它技术进行 结合研究等。在这一阶段，除了美国各大高校和科研机构外，法国、英国、日 本、意大利等其它各国的一些大学和研究机构也纷纷开展了该领域的研究工作。 2 0 0 0 年起国际上开始出现有关无线传感器网络研究结果的报道2 0 0 3 年开始， 有关无线传感器网络的国际会议和杂志大量涌现。 国内的研究起步较早的有中科院沈阳自动化所、中科院软件所、清华大学、 浙江大学、华中科技大学、哈尔滨工业大学、西北工业大学、黑龙江大学等。 中国国家自然科学基金于2 0 0 3 年开始对无线传感器网络的研究进行了资助，并 于2 0 0 4 年将其列为重点项目立项，而2 0 0 5 年又有两项相关项目列为重点项目 立项 无线传感器网络发展的第三阶段，着重对网络的群体智能行为和实际应用 的研究。目前，这方面的研究相对较少，大量的问题还没有涉及到。 1 1 2 应用前景 无线传感器网络所具有的众多类型的传感器，可探测包括地震、电磁、温 度、湿度、噪声、光强度、压力、土壤成分、移动物体的大小、速度和方向等 周边环境中多种多样的现象。基于m e m s 的微传感技术和无线联网技术为无线 传感器网络赋予了广阔的应用前景。这些潜在的应用领域可以归纳为：军事、 航空、反恐、防爆、救灾、环境、医疗、保健、家居、工业、商业等领域。 ( 1 ) 军事应用 无线传感器网络是网络中心战体系中面向武器装备的网络系统，是c 4 1 s r ( c o m m a n d ，c o n t r o l ，c o m m u n i c a t i o n s ，c o m p u t i n g ，i n t e l l i g e n c e ，s u r v e i l l a n c e ， r e c o n n a i s s a n c ea n dt a r g e t i n g ) 的重要组成部分。自组织和高容错性的特征使无 线传感器网络非常适用于恶劣的战场环境中，进行我军兵力、装备和物资的监 控，冲突区的监视，敌方地形和布防的侦察，目标定位攻击，损失评估，核、 生物和化学攻击的探测等 ( 2 ) 空间探索 探索外部星球一直是人类梦寐以求的理想，借助于航天器布撒的传感器网 络节点实现对星球表面长时间的监测，应该是一种经济可行的方案。美国国家 航空和宇宙航行局( n a t i o n a la e r o n a u t i c sa n ds p a c ea d m i n i s t r a t i o n ，n a s a ) 的 j p l ( j e t p r o p u l s i o n l a b o r a t o r y ) 实验室研制的s e n s o r w e b s 就是为将来的火星探测 进行技术准备的，已在佛罗里达宇航中心周围的环境监测项目中进行测试和完 善。 ( 3 ) 反恐应用 美国的9 1 1 恐怖袭击造成了难以估量的巨大损失，而目前世界各地的恐怖 袭击也大有愈演愈烈之势采用具有各种生化检测传感能力的传感器节点，在 重要场所进行部署，配备迅速的应变反应机制，有可能将各种恐怖活动和恐怖 袭击扼杀在摇篮之中，防忠于未然，或尽可能将损失降低到最少。 ( 4 ) 防爆应用 矿产、天然气等开采、加工场所，由于其易爆易燃的特性，加上各种安全 设旄陈旧、人为和自然等因素，极易发生爆炸、坍塌等事故，造成生命和财产 损失巨大，社会影响恶劣。在这些易爆场所，部署具有敏感气体浓度传感能力 的节点，通过无线通信白组织成网络，并把检测的数据传送给监控中心，一旦 发现情况异常，立即采取有效措施，防止事故的发生。 ( 5 ) 灾难救援 在发生了地震、水灾、强热带风暴或遭受其他灾难打击后，固定的通信网 络设施( 如有线通信网络、蜂窝移动通信网络的基站等网络设施、卫星通信地 球站以及微波中继站等) 可能被全部摧毁或无法正常工作，对于抢险救灾来说， 这时就需要无线传感器网络这种不依赖任何固定网络设施、能快速布设的自组 织网络技术。边远或偏僻野外地区、植被不能破坏的自然保护区，无法采用固 定或预设的网络设施进行通信，也可以采用无线传感器网络来进行信号采集与 处理。 ( 6 ) 环境科学 随着人们对于环境的日益关注，环境科学所涉及的范围越来越广泛。通过 传统方式采集原始数据是一件困难的工作传感器网络为野外随机性的研究数 据获取提供了方便，比如，跟踪候鸟和昆虫的迁移，研究环境变化对农作物的 影响，监测海洋、大气和土壤的成分等。此外，也可用于对森林火灾的监控。 ( 7 ) 医疗保健 如果在住院病人身上安装特殊用途的传感器节点，如心率和血压监测设备， 利用传感器网络，医生就可以随时了解被监护病人的病情，进行及时处理。还 可以利用传感器网络长时间地收集人的生理数据，这些数据在研制新药品的过 程中是非常有用的，而安装在被监测对象身上的微型传感器也不会给人的正常 生活带来太多的不便此外，在药物管理等诸多方面，它也有新颖而独特的应 用。总之，传感器网络为未来的远程医疗提供了更加方便、快捷的技术实现手 段。 ( 8 ) 智能家居 嵌入家具和家电中的传感器与执行机构组成的无线传感器执行器网络与 i n t e r n e t 连接在一起将会为人们提供更加舒适、方便和具有人性化的智能家居环 境。包括家庭自动化( 嵌入到智能吸尘器，智能微波炉，电冰箱等，实现遥控、 自动操作和基于i n t e r n e t ，手机网络等的远程监控) 和智能家居环境( 如根据亮度 需求自动调节灯光，根据家具脏的程度自动进行除尘等) 。 ( 9 ) 工业自动化 像机器人控制，工业自动化，设备故障监测故障诊断，工厂自动化生产线， 恶劣环境生产过程监控，仓库管理，如沃尔马公司使用的射频识别条型码芯片 ( r f i d ) 等。大型设备的监控：在一些大型设备中，需要对一些关键部件的技 术参数进行监控，以掌握设备的运行情况在不便于安装有线传感器的情况下， 无线传感器网络就可以作为一个重要的通信手段。 ( 1 0 ) 商业应用 自组织、微型化和对外部世界的感知能力是无线传感器网络的三大特点， 这些特点决定了无线传感器网络在商业领域应该也会很多的应用比如，城市 车辆监测和跟踪、智能办公大楼、汽车防盗、交互式博物馆、交互式玩具等众 多领域，无线传感器网络都将会孕育出全新的设计和应用模式。 无线传感器网络于传统的无线网络相比有着不同的设计目标，后者在高度 移动的环境中通过优化路由和资源管理策略最大化带宽的利用率，同时为用户 提供一定的服务质量保证。而在无线传感器网络中，除了少数节点需要移动以 外，大部分节点都是静止的p l 。因为它们通常运行在人无法接近的恶劣甚至危 险的远程环境中，能源无法更换，设计有效的策略延长网络的生命周期成为无 线传感器网络的核心问题。这些独特的要求和制约因素为无线传感器网络的研 究提出了新的技术问题。 无线传感器网络处于新技术的最前沿，目前尚存在这许多值得探讨的热点 课题，国内外学者正在进行深入研究。不同的研究人员对无线传感器网络的许 多问题都有不同观点 1 2 定位问题 作为一种全新的技术，无线传感器网络为科技工作者提出了许多具有挑战 性的研究课题，而定位就是其中之一定位是大多数应用，特别是军事应用的 基础。无线传感器网络中的定位机制与算法包括两部分：节点自身定位和外部 目标定位，前者是后者的基础1 4 j 。 对于大多数应用，不知道传感器位置而感知的数据是没有意义的【5 1 传感 器节点必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件”， 实现对外部目标的定位和追踪 4 1 。另一方面，了解传感器节点位置信息还可以 提高路由效率，为网络提供命名空间f 6 ，7 - 射，向部署者报告网络的覆盖质量【9 1 0 l ， 实现网络的负载均衡l l l t1 2 1 和网络拓扑的自配置i 3 1 无线传感器网络节点的微型化和有限的电池供电能力使其在节点硬件的选 择上受到很大限制，低功耗是其最主要的设计目标而人工部署和为所有网络 节点安装g p s 接收器都会受到成本、功耗、扩展性等问题的限制，甚至在某些 场合可能根本无法实现。因此必须针对其密集性，节点的计算、存储和通信等 能力都有限的特点设计有效的低功耗定位算法 定位研究在国内才刚刚起步，国外已有了一定的研究和发展。从a t & t l 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 eb a d g e 1 4 1 至今， 研究者们一直在致力于开发能够自定位的系统和算法。事实上，经过这些年的 努力，许多技术都能够解决无线传感器网络的自身定位问题，但每一种系统和 算法都是用来解决不同的问题或支持不同的应用，它们在用于定位的物理现象， 传感器设备的组成，能量需求，基础设施和时空的复杂性等许多方面不同，第 二章中将对这些系统和算法进行详细的介绍和对比因此，该领域还有待更多 的人提出更好的方法，以求解决好定位问题，从而使传感器网络真正在实际生 活中得到广泛应用。 1 3 论文的组织与内容 作为无线传感器网络应用的支撑技术之一，节点的自定位问题的研究极具 研究价值，也能带来不少有价值的商业应用。本文在分析对比现有的无线传感 器网络定位算法的基础上，提出了一种新型的可扩展的自定位算法，在研究算 法自身的同时，也期望着能为无线传感器网络的定位算法开辟一条的思路。 本论文的研究内容安摔如下： 第一章主要介绍了课题的研究背景和研究意义，并由此引出了定位算法这 一具体的研究内容。 第二章首先介绍了无线传感器网络中节点自定位的基本原理与机制；然后 选取了几种算法进行了对比分析，这些算法代表着不同的定位思想，也象征着 定位算法研究的不同阶段；最后横向评价了各种算法的优缺点，进而提出了评 价定位算法的几个重要的性能指标。 第三章提出了一种基于分簇的多跳相对定位算法一一m r l a c 算法，并对 其整体模型和各个模块分别进行了深入的讨论。首先，文章将用一节的篇幅对 算法各个模块之间的关系和运行的流程进行概括分析；然后，文章将从分簇、 局部定位和全局定位三个方面，分三节对各个步骤进行详细分析，并给出其实 现细节。 第四章主要讨论了怎样在n s 2 仿真器上实现m r l a c 算法，并对仿真结果 进行了综合分析。为了能在n s 2 上仿真本算法，首先要配置n s 2 仿真器，文中 介绍了配置的过程，而后给出了算法仿真的过程结果显示，m r l a c 算法能 够在低功耗运行的同时保证较高的定位精度，并且其定位精度比其它定位算法 更高，在节点平均连通度较低的情况下，提高的尤为显著。 第五章总结全文，概括了m r l a c 算法中的优缺点，并展望了算法可扩展 的部分以及未来的研究方向。 第二章无线传感器网络中定位算法综述 在大多数情况下，在传感器网络中，节点是被配置在事先完全没有预设好 位置的环境中的这些传感器是采用自组织的方式来配置的，完全取决于节点 自身在这样一个大的坐标系内来识别它们自身，也就是在实际的物理网络中决 定一个给定节点的位置问题，这个问题也就是本文讨论的定位问题 节点的准确定位是无线传感器网络应用的重要条件。由于其工作区域或者 是人类不适合进入的区域，或者是敌对区域，传感器节点需要通过飞行器抛撤 于工作区域，节点的位置都是随机的。而节点所采集到的数据必须结合其在测 量坐标系内的位置信息才有意义，没有位置信息的数据几乎没有任何利用价值。 无线传感器网络要在这些特殊的区域应用，首先必须要解决的问题是以最小的 通信开销和硬件代价实现节点定位。 获得节点位置的一个直接想法是使用全球定位系统( g p s ) 来实现，但是 在无线传感器网络中使用g p s 来获得所有节点的位置受到价格、体积、功耗等 因素的限制，存在着一些困难。因此目前主要的研究工作是利用少量已知位置 的节点( 采用g p s 定位或者预先放置的参照节点) ，来获得其它节点的位置信 息。 节点定位的精确性则依赖于两个相邻的参考点之间的距离以及它们的传输 信息的范围。而定位的方法对己知其位置的参考点及待定位的节点之间的通信 形式关系尤为密切 本章将先介绍无线传感器网络中节点白定位的基本原理和机制，而后对现 有的一些典型的定位算法进行对比分析，最后提出了一些在评价定位算法性能 时所用的重要的指标。 2 1 定位原理与定位机制 关于定位技术，一般都会马上提到的一种解决方案就是g p s ，既全球定位 系统。然而，实际上在传感器网络应用中，有很多具体的因素都限制了g p s 在 其中的应用。比如说，g p s 只能在户外进行工作；另外g p s 的接收器一般都很 昂贵，这一点也不适用于传感器网络中小而价格低廉的传感器节点；还有就是它 对环境的要求上也受到了限制，如一些障碍物如浓雾等的影响；而且在很多传 感器应用中，是g p s 的盲区，不可能用其来定位因此，传感器节点需要有其 他的方法来给它们自身定位并将它们自身组织成为一个坐标系，而不是依赖于 现有的一些设施。 目前，很多研究工作者都在从事这方面的研究，也提出了很多关于定位问 题的解决方案。在本章中，我们将就这些来进行讨论 因为在大部分的定位技术方案中，都采用了三角形测量技术、及多边测量 技 术( t r i l a t e r a t i o n m u l t i l a t e r a t i o n ) ，在此我们将首先对该技术进行介绍 2 1 1 三边测量技术 三边测量技术的理论依据是在二维空问中，知道了一个节点到三个以上参 考点的距离，就可以确定该点的坐标【”i 图2 1 三边测量法 三边测量技术是建立在几何学的基础上，它可通过与一些己知点的相关距 离信息来给自己定位。图2 i 中三个参考节点a 、b 、c 的坐标分别为( x i ，y 1 ) 、 ( x 2 ，y 2 ) 、( x 3 ，y 3 ) ，未知节点s 的坐标为( x ，y ) ，并且与三个参考点的距离分 别为d l 、d 2 、d 3 ，显然有下式： l k z l l l 2 = d 2 其中i i x 一工，| | 表示任意两点的距离对于这样的一个非线性方程组，可以很容易的 采用线性化的方法求解出s 的估计位置。 当传感器网络中节点之间的连接很多时，大多数节点都可以直接或者间接 获得三个以上参考点的距离信息。这样可以利用冗余节点的信息获得更高的定 位精度，有下式； i 协酽- 6 l m 酽一2 善，1 x = 西 取其中一个锚节点善口，有下式： l 恤2 + 恤d i r 一2 x d 工= d ， 上两式相减有： 一2 ( 新一x o ) r x = ( 函2 一d 0 2 ) 一( 忙，1 1 2 i 防d 2 ) 令a i = 2 ( x ，一x d ) ，b i = ( 砰一d 铲) 一( i k ，2 1 k d l l 2 ) ，可得： a x = b 其中彳= 0 j ，d 2 ，。) t ，b = ( 6 ，b 2 ，“) 7 。根据最小二乘估计，当1 1 4 x 一6 2 取最小值时，可以得出x 的估算值： ，= 似1 彳) 。a 1 b 三角形测量技术中，除了三边测量技术以外，还有三角测量技术，即利用 节点问的角度信息，其原理基本相同。这种二维情况下的测量技术，可以很容 易的推广到三维情况，但需要利用到球的相关知识。在三维情况下，定位一个 未知节点需要四个参照节点，也就是说需要四个球的半径才能最终定位。 2 1 2 多边测量技术 多边测量技术是一项尽最大可能估计节点位置的技术，目前研究比较成熟。 下面简略介绍原子多边测量技术和协作多边测量技术。 a 图2 2 原子多边测量技术 c 图2 2 中，未知节点s 通过三个以上的参考节点来进行定位。该技术是利 用原子多边测量技术为基础在自组织网络中对节点进行定位。它是以完全分布 式的方式来为尽可能多的节点进行定位。在传感器网络布置好以后，参考节点 便向其邻居节点广播它们的位置信息，而那些位置未知的节点便测量与参考节 点问的相关距离等信息，并通过参考的位置信息进行定位。一旦一个未知节点 确定了它自身位置信息后，它便成为参考节点并向其邻居节点同样广播相关信 息，以便对其他节点进行定位。该过程不断重复进行，直到能够通过相关信息 利用多边测量技术来对尚未定位的节点进行定位该过程便是叠代多边测量技 术，它是建立在原子多边测量技术基础之上的，能够对网络中任意节点定位 同时，它也能够对一个有中心节点或是在基于群的网络中对群的集合进行定位。 但该方法的一个缺点是由于在节点定位过程中利用了一些的未知节点在定 位后也作为参考节点来帮助其他节点定位，从而容易引起累积误差。但一般在 具体应用该方法时，都会采用相关措施来减小此类误差。 b 图2 3 协作多边测量技术 c 而在参考节点任意分布的自组织网络中，一些节点很可能出现这样一些情 况，如节点不能找到三个参考节点，可能找到一个，或是两个。此时就无法用 原子多边测量方法来进行定位。在这种情况下，我们就可以用协作式技术来定 位此时，如果有足够的信息以形成一个稳定的且只有唯一一个或一组解的方 程，那么一个或多个节点的定位问题就可通过解一组二次方程来解决，如图2 。3 中所示即为一个最基本的协作式多边测量技术应用的拓扑结构。其中节点s 和 节点t 为未知节点，而节点a 、b 、c 、d 为参考节点，s 和t 分别有三个邻居 节点，但只有两个参考节点，那么我们就可以构造二次方程来解决节点s 和t 的定位问题。 2 2 现有定位算法的分析 从目前定位算法的研究情况看，总的来说大致经过了两个阶段第一阶段 主要偏重于基于基础设施的定位技术，代表性的研究成果有a c t i v eb a d g e d 4 、 a c t i v eb a t 7 1 、r a d a r l l 6 l 等，这类算法的共同特点是适用于室内环境，具有较 高的精确性和实时性，时间同步和锚节点阃的协调问题容易解决。但这种部署 策略限制了系统的可扩展性，代价很大，无法应用于布线工作不可行的室外环 境，背离了无线传感器网络的特点和优势，因此已经渐渐淡出人们的视野。 第二阶段的研究主要针对与无基础设施的定位技术，由于它符合无线传感 器网络的特点，并且应用的范围更广，目前已经成为了该领域一个不小的热点。 下面根据算法是否基于锚节点和测距的特征，概括性的介绍其中一些具有代表 性的定位算法。 2 2 1c r i c k e t 系统 c r i c k e t 是第一个不基于基础设施的定位算法d 7 1 它由散布在建筑物内的 位置固定的锚节点和需要定位的人或物携带的未知节点组成，是一种基于锚节 点和测距的定位算法。锚节点随机地同时发射r f 和超声波信号，r f 信号中包 括该锚节点的位置未知节点使用t d o a 技术测量与锚节点的距离，当可获得 三个或以上锚节点距离时使用三边测量法提供物理定位，精度为4 x 4 英尺“： 否则就以房间为单位提供符号定位。 2 2 2 质心定位算法 质心算法是南加州大学的n i r u p a m ab u l u s u 等提出的一种仅基于网络连通 性的室外定位算法l i 引。该算法是一种基于锚节点而不测距的算法，其核心思想 是：锚节点每隔一段时间，向邻居节点广播一个信标信号，信号中包含自身i d 和位置信息。当未知节点接收到来自不同锚节点的信标信号数量超过某一个预 设门限或接收一定时间后，该节点就确定自身位置为这些锚节点所组成的多边 形的质心仿真显示，大约有9 0 未知节点定位精度小于锚节点问距的1 3 。 显然，该算法仅能实现粗粒度定位，需要较高的锚节点密度；但它非常简单，完 全基于网络连通性，无需锚节点和未知节点间协调。 2 2 3 凸规划定位算法 加州大学伯克利分校的d o h e r t y 等将节点阃点到点的通信连接视为节点位 置的几何约束，把整个网络模型化为一个凸集，从而将节点定位问题转化为凸 约束优化问题，然后使用半定规划和线性规划方法得到一个全局优化的解决方 案，确定节点位置i i ”。同时也给出了一种计算未知节点有可能存在的矩形空间 的方法。即根据未知节点与锚节点间的通信连接和节点无线射程，计算出未知 节点可能存在的区域，并得到相应矩形区域，然后以矩形的质心作为未知节点 的位置。 凸规划是一种集中式定位算法，并且基于锚节点测距，在锚节点比例为 1 0 条件下，定位精度大约为1 0 0 。为了高效工作，锚节点需要被部署在网 络的边缘，否则外围节点的位置估算会向网络中心偏移 2 2 4a p i t 定位算法 a p i t 算法1 2 川是一种基于锚节点而无须测距的定位算法，其理论基础是 p e r f e c t p o i n t - i n - t r i a n g u l a t i o n t e s tt h e o r y ( p i t ) ：假如存在一个方向，沿着 这个方向m 点会同时远离或接近a 、b 、c 那么m 位于a a b c 外，否则，m 位于a b c 内。为了在静态网络中执行p i t 测试，定义了a p i t 测试 ( a p p r o x i m a t ep i tt e s t ) ：假如节点m 的邻居节点没有同时远离或者靠近三个 锚节点a 、b 、c ，那么m 就在a a b c 内，否则，m 在a b c 外它利用w s n 较高的节点密度来模拟节点移动和在给定方向上，一个节点距锚节点越远，接 收信号强度越弱的无线传播特性来判断与锚节点的远近。 在a p i t 算法中，一个目标节点任选三个相邻锚节点，测试自己是否位于 它们所组成的三角形中使用不同锚节点组合重复测试直到穷尽所有组合或达 到所需定位精度最后计算包含目标节点的所有三角形的交集质心，并以这一 点作为目标节点位置。 仿真结果显示，a p i t 测试错误概率相对较小( 最坏情况下1 4 ) ，平均定位 误差小于4 0 但因未知节点必须与锚节点直接通信的需求，该算法的要求较 高的锚节点密度。 2 2 5a p s 系列算法 美国路特葛斯大学( 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 等利用距离矢量 路由和g p s 定位的思想提出了一系列分布式定位算法，合称为a p s 算法1 2 1 ，2 2 1 ， 包括了d r - h o p 、d v - d i s l a n c e 、e u c | i d e a n 等算法。a p s 系列算法均是基于锚节 点的定位算法，其中后两者需要测距，而前者无须测距。 d v - h o p 算法由三个阶段组成。首先使用典型的距离矢量交换协议，使网络 中所有节点获得距锚节点的跳数。第二阶段，在获得其他锚节点位置和相隔跳 距后，锚节点计算网络平均每跳距离，然后将其作为一个校正值广播至网络中。 校正值采用可控洪泛法在网络中传播，这意味着一个节点仅接受获得的第一个 校正值，而丢弃所有后来者，这个策略确保了绝大多数节点从最近的锚节点接 收校正值。在大型网络中，可通过为数据包设置一个t t l 域来减少通信量。当 接收到校正值后，节点根据跳数计算与锚节点距离。当未知节点获得与三个或 更多锚节点的距离，则在第三阶段执行三边测量定位。 d v - h o p 算法在网络平均连通度为l o ，锚节点比例为1 0 的各向同性网络 中平均定位误差大约为3 3 其缺点是仅在各向同性的密集网络中，校正值才 可以合理地估算平均每跳距离。 d v - d i s t a n c e 算法与d v - h o p 类似，所不同的是相邻节点使用r s s i 测量节 点闻点到点距离，然后利用类似距离矢量路由的方法传播与锚节点的累计距离。 未知节点获得与三个或更多锚节点的距离后使用三边测量定位。d v - d i s t a n c e 算 法也仅适用于各向同性的密集网络。仿真显示，该算法定位精度为2 0 ( 网络 平均连通度为9 ，锚节点比例l o ，测距误差小于l o ) ；但随着测距误差的增 大，定位误差也急剧增大。 e u c l i d e a n 定位算法中假设节点拥有使用r s s i 测量节点间距离的能力，它 给出了计算锚节点与相隔两跳的未知节点距离的方法。该算法以锚节点首先广 播出一个包含自身i d 和位置的信标信号开始，并将该信号的订l 域设置为2 。 即该信标仅能传送两跳当一个未知节点可从两个已知相互距离和与锚节点距 离的节点处接收到该信号，它就可以计算出自身与该锚节点的距离当未知节 点获得与三个或更多锚节点距离后定位自身。 2 2 6h o p t e r r a i n 算法 为了减小测距误差对定位的影响，加州大学伯克利分校的c h r i ss a v a r e s e 等提出了基于循环求精定位算法一一t e r r a i n 算法和h o p t e r r a i n 算法， 它们都属于基于锚节点和测距的定位算法 算法分为启始和循环求精两个阶段。启始阶段着重于获得节点位置的粗略 估算在循环求精阶段中，每一次循环开始时节点广播它的位置估算，并根据 从邻居节点接收的位置信息和节点间测距结果，重新执行三边测量计算自身位 置，直至位置更新的变化可按受时循环停止。 t e r r a i n 算法【2 2 l 首先在所有锚节点上根据节点间测距结果使用a b c 算法 建立局部坐标系统，然后将结果( 以这个锚节点为原点的局部网络拓扑) 传播 到整个网络未知节点根据它获得的网络拓扑确定它