（通信与信息系统专业论文）基于aoa和tdoa的无线传感器网络三维定位算法的优化.pdf

山东大学硕士学位论文 摘要 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ，简称w s n ) 是由大量具有特定功能的 传感器节点通过自组织的无线通讯方式，相互传递信息，协同地完成特定功能的 智能专用网络，它综合了传感器技术、嵌入式计算技术、现代网络、无线通信技 术和分布式信息处理技术等，能够通过各类集成化的微型传感器协作地实时监 测、感知和采集各种环境或监测对象的信息，完成连续的监测、目标发现、位置 识别等任务，这些信息通过无线方式被发送，并以自组多跳的网络方式传送到用 户终端，从而实现物理世界、计算世界以及人类社会的连通。无线传感器网络是 目前i t 领域的一个研究热点，而且传感器网络是一个新兴技术，国内与国际水 平的差距并不很大，及时开展这项对人类未来生活影响深远的前沿科技的研究， 对整个国家的社会、经济将有重大的战略意义。 位置信息是传感器节点采集数据中不可缺少的部分，没有位置信息的监测消 息通常毫无意义。因此，定位技术是传感器网络的一项支撑技术，是传感器网络 进行目标监测、跟踪、识别等众多应用的前提，也是传感器网络研究中的热点问 题之一。 本文首先介绍了一种基于a o a 的无线传感器网络三维联合定位算法，该算法 是在典型的a o a 算法基础上做了改良，在信标节点附近安装两对性能参数完全相 同的、互相垂直的、间距为2 r 的超声波发射机，当其中一对发射机存在不能测量 的死角时使用另一对进行角度测量，解决了原算法的死角问题。再引入了基于到 达时间差( t d o a ) 的距离测量方法，提出了针对三维空白j 定位的联合定位算法， 分析证明，本算法复杂度较低，算法精度较高，能够有效地估计三维空间中传感 器节点的位置。 在对该定位算法的分析研究中发现，原文缺少对两个主要参数超声波发射机 r 和超声波频率变化范围厂，的研究。本文在仿真软件m a t l a b 上针对r 和厂建立一 个完整的实验模型，分别详细分析r 和厂的取值对测量结果的影响。实验结果表 明，在满足死角条件下，r 和厂的任何取值下该算法都能够精确的实现传感器节 点的空间定位，验证了算法的j 下确性。同时我们还发现不同的r 和厂取值与测量 误差确实存在一定的关系，经分析该误差影响主要来自于两个方面：原算法公式 山东大学硕十学位论文 2 推导中的误差与待测节点干涉波强度周期测量的精确度。因此我们从这两方面着 手，利用公式推导和估算，得出了一个关于误差值计算公式。最后经过仿真实 验，验证了该公式的j 下确性，并给出了一组定位算法的最佳参数值。 本文还探讨了使用电磁波取代超声波在本算法中应用的可能性。电磁波相比 超声波在生活中更加常见，它具有更宽的频率范围、不需介质就能传播、不像超 声波容易受到环境、气温等外部因素的干扰等优点，在很多环境中对比超声波具 有一定的优势。 关键词：无线传感器网络；节点定位；测量误差；电磁波 山东大学硕士学位论文 a bs 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 ) r e f e r st ot h es e l f - o r g a n i z i n gn e t w o r k ，w h i c hi s c o m p o s e do fm a n ym i c r o - s e n s o rn o d e sd e p l o y e di ns p e c i a lf u n c t i o nb yw i r e l e s s c o m m u n i c a t i o n ，c o l l a b o r a t i v e l ya i m i n g t o p e r c e i v e 、c o l l e c ta n dd i s p o s e t h e i n f o r m a t i o nf r o mt h ep e r c e i v e do b j e c ti nt h en e t w o r ko v e r l a ya r e aa n dt h e ns e n dt ot h e o b s e r v e r c o m b i n i n gt h es e n s o rt e c h n o l o g y 、e m b e d d e dc o m p u t i n gt e c h n o l o g y 、 m o d e mn e t w o r k 、w i r e l e s sc o m m u n i c a t i o nt e c h n o l o g ya n dd i s t r i b u t e di n f o r m a t i o n p r o c e s s i n gt e c h n o l o g y ，w s nc a nb ea p p l i e dt or e a l t i m em o n i t o r i n ga n de n v i r o n m e n t a l i n f o r m a t i o nc o l l e c t i n gi no r d e rt oc o m p l e t et h em i s s i o ns u c ha sc o n t i n u o u sm o n i t o r i n g ， t a r g e td i s c o v e r ya n dp o s i t i o nr e c o g n i t i o nw i t l lk i n d so fi n t e g r a t e dm i n i a t u r es e n s o r s t h e s ei n f o r m a t i o ni ss e n tt h r o u g hw i r e l e s st r a n s m i s s i o n , a n da c h i e v et h eu s e rt e r m i n a l s i ns e l f - o r g a n i z i n gm u l t i p l eh o p sn e t w o r km o d e , s oa st oa c h i e v et h ep h y s i c a lw o r l d ， c o m p u t i n gw o r l da n dh u m a ns o c i e t yc o n n e c t i v i t y a tp r e s e n lw s ni sa h o tr e s e a r c h a r e a si ni tf i e l d a san e wt e c h n o l o g y ，i tc a n n o tb ew i t h o u te q u a l i t yw i t hb o t l l i n t c m a t i o n a la n dd o m e s t i c w es h o u l db e g i nt h ew s nr e s e a r c hi nt i m et ob es u r et o d e f e n dt h eb e n e f i mo fo u rs o c i e t ya n de c o n o m y l o c a l i z a t i o n t e c h n o l o g y i sa n i n d i s p e n s a b l ep a r t o fd a t a a c q u i r i n g w i t h o u t l o c a l i z a t i o ni n f o r m a t i o n ，t h em o n i t o ri n f o r m a t i o ni sw o r t h l e s s t h e r e f o r e ，l o c a l i z a t i o n t e c h n o l o g yi sas u p p o rt e c h n o l o g yo f s e n s o rn e t w o r k ，ap r e m i s ef o rw s nt oc a r r yo u t t a r g e ti d e n t i f i c a t i o n 、m o n i t o r i n g 、t r a c k i n ga n dm a n yo t h e ra p p l i c a t i o n s ，a n da l s oah o t i s s u e si nt h es t u d yo fs e n s o rn e t w o r k t h i sp a p e rf i r s ti n t r o d u c e sac o m b i n e dl o c a l i z a t i o na l g o r i t h mb a s e do nw a v e i n t e r f e r e n c ea n g l em e a s u r e m e n t ( a o a ) w i t ha l li m p r o v c da l g o r i t h m ，i nw h i c ht w o p a i r so fu l t r a s o n i ct r a n s m i t t e r sa r ei n s t a l l e do nt h eb e a c o nn o d e s t h ep a r a m e t e r so f u l t r a s o n i ct r a n s m i t t e r sa r et h es a m e ，a n dt h ep e r p e n d i c u l a rb i s e c t o r so ft h et w op a i r so f u l t r a s o n i ct r a n s m i t t e r sa r ep e r p e n d i c u l a r , a n dt h ed i s t a n c eb e t w e e nap a i ro fu l t r a s o n i c t r a n s m i t t e r si s2 r i ft h ea n g l ec o u l d n tb em e a s u r e db yo n ep a i r ，t h eo t h e rp a i rb e g i n st o w o r k m a t h e m a t i c a la n a l y s i sa n ds i m u l m i o nr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h m c o m p l e t e l ys o l v e dt h eb l i n ds p o to f t h ep r i m a lo n e 山东大学硕十学位论文 t h r o u g ht h et i m ed i f f e r e n c eo fa r r i v a l ( t d o a ) ，t h ep a p e rp r o p o s e sac o m b i n e d l o c a l i z a t i o na l g o r i t h m w i t hh i g h e ra c c u r a c yt h i sa l g o r i t h mc a l le f f e c t i v e l ye s t i m a t et h e l o c a t i o no ft h es e n s o rn o d e si nt h r e e d i m e n s i o n s i nt h el o c a l i z a t i o na l g o r i t h ma n a l y s i sr e s e a r c h , w ef i n dt h a tt h eo r i g i n a lp a p e rt a k e s n oa c c o u n to ft w om a i np a r a m e t e r so f u l t r a s o n i ct r a n s m i t t e rra n dt h er a n g eo fu l t r a s o n i c f r e q u e n c yc h a n g ef b a s e do nt h es i m u l a t i o ns o f t w a r em a t l a bw ee s t a b l i s h e d a c o m p l e t ee x p e r i m e n t a lm o d e lf o rra n df ，r e s p e c t i v e l yc a r r i e do na nd e t a i l e da n a l y s i s f o rt h ei n f l u e n c eo fv a l u eo nt h em e a s u r e m e n tr e s u l t s t h ee x p e r i m e n tr e s u l t sa l s o d e m o ns t r a t e dt h a ti nn ob l i n ds p o tc o n d i t i o n s ，t h ea l g o r i t h me f f e c t i v e l ye s t i m a t e st h e l o c a t i o no ft h es e n s o rn o d e si nt h r e e d i m e n s i o n sw i t h o u tt h ev a l u eo fra n df ，t h e c o r r e c t n e s so ft h i sa l g o r i t h mw a sv e r i f i e d f u r t h e m o r e ，w ef o u n dt h a tt h em e a s u r e m e n t e r r o rw a sc l o s e l yr e l a t e dt ot h e d i f f e r e n tv a l u eo fra n df t h r o u g ha n a l y z i n gt h e m e a s u r e m e n te r r o r , i n f l u e n c em a i n l yc o m e sf r o mt w oa s p e c t s ：t h ec a l c u l a t i o ne r r o ro f o r i g i n a la l g o r i t h ma n dt h ep r e c i s i o no fn o d ei n t e r f e r e n c ew a v ep e r i o d i cm e a s u r e m e n t f r o mt h et w oa s p e c t s ，w eo b t a i n e dac a l c u l a t i n gf o r m u l ao fe r r o rb yf o r m u l a sa n d e s t i m a t i o n f i n a l l y ，t h es i m u l a t i o nv a l i d a t e dt h ec o r r e c t n e s so f t h i sf o r m u l a , a n dw eg o t ag r o u po fl o c a l i z a t i o na l g o r i t h mt h eo p t i m u mv a l u e t h ep a p e ra l s od i s c u s s e st h ep o s s i b i l i t yo fu s i n ge l e c t r o m a g n e t i cw a v et or e p l a c e u l t r a s o u n dw a v ei nt h i sa l g o r i t h m e l e c t r o m a g n e t i cw a v ei sp o p u l a rt h a nu l t r a s o n i ci n o u rl i f e ，i th a sam o r ew i d ef r e q u e n c yr a n g e ，s p r e a d i n gw i t h o u tm e d i u m i ti sn o ts o v u l n e r a b l eb ye n v i r o n m e n t a l ，t e m p e r a t u r e ，e t ea su l t r a s o n i c ，a n dh a sc e r t a i na d v a n t a g e s i nm a n ye n v i r o n m e n t k 呵w o r d s ：w s n ；n o d e sl o c a t i o n ；m e a s u r e m e n te r r o r ；e l e c t r o m a g n e t i cw a v e 4 山东大学硕士学位论文 w s n m e m s r s s i g p s s p a a h l o s a p s a p i t h i r i 乃c u w b a o a t o a t d o a f f t 符号说明 w i r e l e s ss e n s o rn e t w o r k s m i c r oe l e c t r om e c h a n i s ms y s t e m 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 g l o b a lp o s i t i o n i n gs y s t e m s e l f - p o s i t i o n i n ga l g o r i t h m a d - h o el o c a l i c a t i o ns y s t e m a dh o ep o s i t i o n i n gs y s t e m 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 nt e s t h i 曲一r e s o l u t i o nr o b u s tl o c a l i z a t i o n u l t r a - w i d e b a n d a n g l eo f a r r i v a l t i m eo f a r r i v a l t i m ed i f f e r e n e eo fa r r i v a i f a s tf o u r i e rt r a n s f o l r i h 无线传感器网络 微电子机械系统 接收信号强度指示器 全球定位系统 自定位算法 a d - h o c 定位系统 自适应定位系统 近似的p i t 测试法 高精度定位算法 超宽带技术 到达角度 到达时间 到达时间差 快速傅晕叶变换 5 山东大学硕+ 学位论文 1 1 研究背景 第一章绪论 无线传感器网络是由随机部署或抛洒在特定区域的大量廉价传感器节点通过 无线通信方式快速形成的一个多跳、自组织的网络。这些密集分布的节点具有传 感、数据处理和无线通信等能力，能够协作地感知、采集和向基站报告网络覆盖 区域内的监测对象的信息【l 】。与传统的信息获取方式相比，无线传感器网络具有 自组织、功耗小、廉价和快速部署、可扩展性强、能在恶劣和特殊的环境下正常 工作等优点。基于无线传感器网络的这些优点，非常适合在较恶劣的环境中快速 构建信息传输通道，因此具有广阔的应用前景，如环境监测、交通管理、医疗卫 生、制造业等领域【l 】1 2 。无线传感器网络可以使人们在任何时间、地点和任何环 境条件下获取大量详实而可靠的信息，因此，无线传感器网络是一种全新的研究 技术，是信息感知和采集的一场革命【3 1 。 无线传感器网络作为一门由多学科高度交叉的新兴学科，在当前国际上备受 关注。美国商业周刊和m i t 技术评论在预测未来技术发展的报告中，分别将无线 传感器网络列为2 1 世纪最有影响力的2 l 项技术和改变世界的1 0 大技术之一 1 4 1 5 1 。美国自然科学基金委员会、美国国防部和各军事部门都对传感器网络给予 了高度重视。加州大学、麻省理工学院、哈佛大学等各大院校都已经在无线传感 器网络的研究工作中先后建立了几个实验平台，并取得了重大进展。日本、英 国、意大利、巴西等国家也对传感器网络表现出了极大的兴趣，纷纷设立或启动 相应的行动计划1 6 j 。 在国内，一些科研单位和大学也掀起了无线传感网络的研究热潮。中科院、 清华大学、哈尔滨工业大学、西安电子科技大学等单位已经初步开展了在传感器 及传感器网络方面的研究工作l ? l 。但是从总体上来讲，在研究问题的深度和投入 的科研力量上，国内的研究水平相对发达国家如美国还有一定的差距，国内关于 传感器网络的研究还处于刚刚起步的阶段。因此及时开展对无线传感器网络的研 究，对于维护国土安全，对整个国家的社会、经济都有着重大的战略意义。 6 山东大学硕士学位论文 1 2 无线传感器网络概述 无线传感器网络涉及传感器技术、网络通信技术、无线传输技术、嵌入式技 术、分布式信息处理技术、软件程序技术等，是多学科高度交叉、新兴前沿的一 个热点研究领域。其应用已经由初期的军事国防领域扩展到环境监测、交通管 理、医疗健康、社会服务、抢险抗灾、空间探索等诸多领域。在未来，人们将通 过分散于四周的传感器网络直接感知客观世界，使其在任何时间、任何地点、任 何环境下都能够获取大量翔实可靠的信息，从而极大的扩张网络的功能和人类认 识世界的能力1 2 11 5 。 1 2 1 无线传感器网络体系结构 典型的无线传感器网络结构如图1 1 所示l l l l 8 1 1 9 l ，传感器节点通过飞机喷洒或 人工布置等方式随机散布于整个被监控区域，通过自组织的方式构成无线网络。 传感器节点在探测到信息后，经过初步处理以多跳中继的方式将其传送给汇聚节 点，然后经因特网或卫星等传输途径最终到达用户所在的监控管理中心。终端用 户也可以通过管理中心对无线传感器网络进行管理和配置、发布监测任务或收集 回传数据，实施监控和操纵。 传黪器节点 图1 1 无线传感器网络模型 传感器节点除了要进行本地信息的收集和数据处理，还要对其它节点传输来 的数据信息进行存储、管理和融合。因而每一个传感器节点都具有信息采集和路 由的双重功能，通常是一个微型的嵌入式系统，兼具处理能力、通信能力和存储 能力等功能，通过携带的电池来提供能量。 7 山东人学硕士学位论文 汇集节点的处理能力、通信能力和存储能力相比传感器节点要更强，它负责 连接无线传感器网络与i n t e r a c t 等外部网络，实现了两种协议栈之间的通信协议 转换，同时也发布管理节点的监测任务，并将收集到的数据转发到外部网络上。 汇集节点可以是一个具有增强功能的节点，有足够的能量供给和更多的计算资源 和内存，也可以是仅带有无线通信接口而没有监测功能的网关设备i 。 网关设备在无线传感器网络中非常重要。无线传感器网络的协议栈如图1 2 所示【l 】【】，包括和互联网协议栈相对应的五层模型和能量、移动与任务管理平 台。各层协议功能如下： 8 图1 2w s n 网络协议栈 1 ) 物理层负责信号的调制和数据的收发，所采用的传输介质主要是无线 电、红外线和光波等； 2 ) 数据链路层负责数据成帧、帧监测、媒体访问控制和差错控制； 3 ) 网络层负责路由的生成和路由选择，通常，大多数节点无法直接与网关 直接通信，需要通过中间节点以多跳路由的方式将数据传送至汇聚节 点； 4 ) 传输层负责数据流的传输控制，在网络层基础上提供可靠的、端到端的 传输质量保证； 5 ) 应用层主要解决应用共性问题，包括一系列基于监测任务的软件。 各管理平台作用如下： 6 ) 能源管理平台管理节点如何使用自身附带的能源，在各个层次都需要考 虑如果高效的利用能源； 7 ) 移动管理平台用来探测和注册节点的移动： 山东大学硕士学位论文 8 ) 任务管理平台平衡和调度特殊区域分配的任务。 三个平台互相配合工作，使得传感器节点能够高效的协同工作，并支持多任 务和资源共享。 1 2 2 无线传感器网络的特征 无线传感器网络是集成了数据采集、数据处理通信的网络系统，并以自组织 方式组网，与目前常见的无线网络，包括移动通信网、无线局域网、蓝牙网络和 a dh o c 网络等相比，w s n 除了具有移动性、自组织等特征外，还有其他鲜明的 特点1 6 】u i i n - 2 0 1 网络规模大，节点分布广 传感器节点的通信和感知半径较小，感知半径从几米到几十米，通信半径一 般从几十米到两三百米，而且基于节能因素传感器节点大部分时间处于睡眠状 态。所以为了保证监控区域的覆盖网络的连通度，更为了获得精确信息，在监测 区域通常要部署大量传感器节点，传感器节点的数量可能上万，甚至更多。 2 自组织组网模式 在无线传感器网络中，节点的位置不可能预先精确设定，节点之间的相邻关 系也不可能预先知道，所以要求传感器节点具有自组织能力，能够自动进行配置 和管理，通过拓扑控制机制和网络协议自动形成转发监测数据的多跳无线传感器 网络系统。单个节点可以随时加入或离开网络，具有很强的抗毁性。网络的布设 和展开无需依赖于任何固定的网络基点，开机后通过各种协议和分布式算法协调 各自的行为，可以快速的形成自组网络。 3 以数据为中心 传感器网络是以数据为中心的网络，观察者感兴趣的是传感器采集的数据， 而不是传感器本身。以数据为中心的特点，要求传感器网络的设计必须以数据感 知、管理和处理为中心，把数据库技术和网络技术紧密结合，实现一个以数据为 中心的网络系统。 4 网络动态性强 无线传感器网络的拓扑结构不够稳定，随时可能会因为下列因素而变化： 节点由于电能耗尽或者损坏而失效。环境影响，例如电磁干扰而造成通信链路 9 l i i 东大学硕十学位论文 受影响，甚至于通信中断。新的节点的加入或者汇聚节点的移动导致网络拓扑 改变。传感器节点间歇睡眠的工作方式引起网络的拓扑变化。 5 可靠性高 无线传感器网络经常部署在恶劣环境或人类不宜达到的区域，而且传感器数 量大、分布广，使得无线传感器网络的维护十分困难甚至不可维护。无线传感器 网络的安全性和通信保密性也很重要，要防范监测数据被盗和获取伪造的监测信 息。因此，就要求传感器网络的硬件必须具有高强壮性和容错性。 6 与应用紧密相关 无线传感器网络用来感知客观的物理世界，不同的应用背景有着不同的网络 需求。因此其硬件平台、软件系统和网络协议各有不同，没有统一的通信协议平 台。针对每一个具体应用来研究无线传感器网络技术，是无线传感器网络设计不 同于传统网络的一个显著特征。 1 2 3 无线传感器网络的关键技术 无线传感器网络作为当今信息领域新的研究热点，涉及多学科交叉的研究领 域，涉及到非常多的关键技术8 - 1 2 】： 1 拓扑控制 拓扑控制是无线传感器网络研究的核心技术之一。无线传感器网络拓扑控制 指的是在满足网络覆盖度和连通度的前提下，通过功率控制和骨干网节点进行选 择，剔除节点间不必要的无线通信链路，生成一个高效的数据转发的网络拓扑结 构。通过拓扑控制自动生成良好的网络拓扑结构，可以有效的提高通信协议的效 率，可以为上层的数据融合、目标定位、时间同步等许多应用奠定基础，有利于 整个网络的负载平衡，从而节省节点的能量来延长整个网络的生命周期。 2 网络协议 由于传感器节点自身携带的能量、计算能力、存储能力以及通信能力都十分 有限，且节点数目众多，构建路由时只能获取局部拓扑，网络拓扑的动态变化， 网络资源的变化，都对网络协议提出了更高的要求。因此无线传感器网络协议既 需要维持有效的数据传输链路，又要减少数据通信量、讲究能量效率，还要具有 一定的鲁棒性，往往需要根据应用类型或应用目标环境特征定制。 1 0 山东大学硕士学位论文 3 时间同步 时间同步是需要协同工作的传感器网络系统的一个关键机制。由于传感器节 点受到成本、能量和体积的限制，传统的网络时间协议已不适用于传感器网络， 使得无线传感器网络的时间同步遇到了很多新的挑战，研究适合传感器网络的时 间同步方法得到国内外传感器网络研究领域的广泛关注。传感器网络的时间同步 可以采用两种方法：一、给每个节点配备g p s 模块得到精确的时间，这样节点就 可以和标准时间一致，达到同步；二、利用网络通信，交换时间信息，使得全网 保持一个统一的时间，达到同步。 4 网络安全 无线传感器网络作为任务型的网络，不仅要进行数据采集，而且要进行数据 传输和融合、任务协同等工作。尤其在某些应用中( 如战场监测、国家安全 等) ，安全问题更是显得尤为重要。如何提高传输过程的机密性、数据产生的可 靠性以及数据融合的高效性，都是无线传感器网络安全的研究重点。为了保证任 务的机密布置和任务执行结果的安全传递和融合，传感器网络安全路由技术方面 研究主要从两个方面入手：一是采用消息加密、身份认证、路由信息广播认证、 入侵检测、信任管理等机制来保证信息传输；二是利用传感器节点的冗余性，提 供多条路径的完整性和认证。 5 数据融合 数据融合，就是对节点获取的大量随机、不确定、不完整、含有噪声( 甚至 是错误) 的数据，进行滤波等处理，得到可靠、精确、完整数据信息的过程。由 于传感器网络对目标的观察存在数据冗余，若不对这些冗余数据进行处理就传送 给观察者，将会带来巨大的网络流量，从而导致快速能量消耗；另一方面，这种 流量通常都是不均衡分布的，越靠近观察者的节点越容易由于能量的快速消耗而 失效。因此各节点在收集数据的过程中，必须进行数据融合，在数据融合的同时 也滤除了部分噪声，提高了信息的准确度。 6 嵌入式操作系统 传感器节点具有监测、计算、存储等功能，同时节点还有体积小，成本低的 限制，携带的硬件资源非常有限，因此需要配合操作系统来满足传感器网络的特 殊需要，高效地利用其有限的内存、处理器和通信模块。美国加州大学伯克利分 山东大学硕十学位论文 校针对无线传感器网络研发了t i n y o s 操作系统，在随后的研究中得到比较广泛 的应用，但仍然存在不足之处。 7 定位技术 节点定位技术是无线传感网络的主要支撑技术之一。位置信息是传感器节点 采集数据中不可缺少的部分，确定事件发生的位置或数据采集的节点位置，是无 线传感器网络基本功能之一，没有位置信息的监测消息是毫无意义的。由于传感 器节点存在资源有限、部署随机、通信易受干扰等特点，定位机制必须满足自组 织、健壮性、能量高效、分布式计算等要求。定位技术的基本原理有三边测量 法、三角测量法、极大似然估计法。 1 3 无线传感器网络定位技术 在无线传感器网络中，监测节点的位置信息是非常重要的，没有位置信息的 监测将大大降低监测消息的使用价值，传感器节点必须首先知道自身的地理位置 信息。因此，获取监测节点的位置信息成为无线传感器网络最基本的功能之一。 传感器节点通常是通过随机的方式布置在各种环境中来执行监测任务，因此 节点无法事先知道自身的位置，这就要求了无线传感器网络必须能够在节点部署 后进行实时定位。传感器节点自身定位就是根据少数已知位置的节点，按照某种 定位算法或机制确定自身的位置。传感器网络节点的能量有限、节点规模大且随 机布放、无线通信距离有限，对定位技术提出了很高的要求n 町。因此，传感器网 络的定位算法通常要求具备自组织性好、健壮性强、能量高效和分布式计算等特 点。 1 3 1 定位的基本原理 传感器网络中每个节点在某个空间坐标系中确定自己的空间位置的过程称为节 点定位。由于无线传感器网络节点数目众多、能量有限、成本低等特点，在每个传 感器节点配备一个g p s 接收器或事先为每个节点指定位置信息是不可行的，因此我 们只能使一小部分节点装配定位装置或事先给这些节点指定位置坐标，这些通过某 种手段知道自身位置的少数节点称为信标节点( b e a c o nn o d e ) 或锚节点( a n c h o r n o d e ) 。由于受到成本及能耗的限制，锚节点在网络节点中所占的比例很小。在传 感器网络中除了已知位置信息的信标节点外就是需要通过某种方法来计算其位置信 1 2 山东大学硕士学位论文 息的节点，这些节点称之为未知节点( u n k n o w nn o d e ) 。信标节点在网络节点中所占 的比例很小，可以通过携带g p s 定位设备或提前决定等手段获得自身的精确位 置，是未知节点定位的参考。信标节点通过向未知节点广播自己的位置信息，为未 知节点确定位置提供信息n 伽n 射。 无线传感器网络节点定位问题可表述为：依靠有限的位置已知节点即信标节 点，确定布设区中其它未知节点的位置，在传感器节点问建立起一定的空间关系 的过程。 1 3 2 定位方法的分类 在传感器网络中，定位算法通常有以下几种分类： ( 1 ) 基于测距技术的定位和无须测距技术的定位 根据定位过程中是否测量实际节点问的距离，把定位算法分为基于测距技术的 定位和无须测距技术的定位算法。基于测距技术的定位通过测量节点间点到点的距 离或角度等信息，使用三边测量( t r il a t e r a t i o n ) 、三角测量( t r i a n g u l a t i o n ) 或 最大似然估计( m u l t i l a t e r a t i o n ) 定位算法计算节点位置；无须测距技术的定位则 无须距离和角度信息，仅根据网络连通性等信息即可实现。质心算法汹1 、 a m o r p h o u s 胁1 、d v - h o p 算法嘲、a p i t 算法捌、凸规划算法和m d s - m a p 算法嘶1 是现 有的6 种无须测距技术的定位算法。基于测距技术的定位常用的测距技术则有 r s s i 嘲刎，t o a 别，t d o a 和a o a 别刘等等。 ( 2 ) 绝对定位与相对定位【3 3 3 】 绝对定位就是让所有的待定位节点使用共同的参照系，其定位结果是一个全局 性的标准坐标位置，比如经度和纬度，对同一地理位置的节点进行多次绝对定位， 其定位结果将是一样的。相对定位是以网络中部分节点为参考，建立整个网络的 相对坐标系统来进行定位。相对定位可以让每个定位节点使用不同的参照系，通 常是以网络中的部分节点为参考，建立整个网络的相对坐标系统。相比而言，绝对 定位可为网络提供唯一的命名空间，受节点移动性影响较小，有更广泛的应用领 域。而且大多数定位系统和算法都可以实现绝对定位服务。 ( 3 ) 物理定位与符号定位1 1 3 山东大学硕十学位论文 定位系统可提供两种类型的定位结果：物理位置和符号位置。例如，某个节点 的经纬度，就是这个物体在地球的物理位置；而该节点在某个建筑物的某个房间 里，则是符号位置。物理定位和符号定位是可以相互转换的。与物理定位相比，符 号定位更适于某些特定的应用场合，例如，在安装有无线烟火传感器网络的智能建 筑物中，管理者更关心某个房间或区域是否有火警信号，而不是火警发生地的经纬 度。 ( 4 ) 集中式计算与分布式计算 集中式计算是指把所需信息传送到某个中心节点( 例如，一台服务器) ，并在那 里进行节点定位计算的方式；分布式计算是指依赖节点间的信息交换和协调，由节 点自行计算的定位方式。集中式计算的优点在于从全局角度统筹规划，对计算量和 存储量几乎没有限制，可以获得相对精确的位置估算。它的缺点包括与中心节点位 置较近的节点会因为通信开销大而过早地消耗完电能，导致整个网络与中心节点信 息交流的中断，无法实时定位等。集中式定位算法包括凸规划( c o n v e x o p t i m i z a t i o n ) ，m d s - m a p 等，分布式定位算法包括a h l o s ，a f l ，a p s ，a p i t 等。 现实中可根据应用需求采用两种不同的计算模式。 ( 5 ) 基于信标节点的定位和无信标节点的定位 这种分类方式类似于绝对定位与相对定位的分类。绝对定位与相对定位是从定 位效果上来进行分类，而基于信标节点的定位与无信标节点的定位是从定位手段上 来进行分类。基于信标节点的定位算法在定位过程中使用了信标节点，并以它作为 定位中的参考点，各节点定位后产生整体绝对坐标系统；无信标节点的定位算法不 用部署信标节点，它依靠节点间的相对位置，以网络中的某些节点作为参考点，形 成局部坐标系，相邻的局部坐标系再依次转换合并，最后产生整体相对坐标系统。 基于信标节点的定位算法很多，例如质心算法、d y - h o p 、a h l o s 、l c b 和a p i t 等 等；而a b c ( a s s u m p t i o nb a s e dc o o r d i n a t e s ) 1 3 s 和a f l ( a n c h o r - f r e el o c a l i z a t i o n ) l u l 是典型的非基于信标节点的定位算法。 1 3 3 定位算法性畿评价指标 无线传感器网络自身定位算法的性能指标直接影响其可用性，如何评价它们 是一个需要深入研究的问题m 儿驯。下面讨论几个常用的评价标准： 1 4 山东大学硕士学位论文 1 定位精度 这是定位算法最主要的性能指标，它一般用未知节点的估计位置和真实位置 的距离偏差和节点通信半径的百分比表示，例如某算法的定位精度为3 0 ，它表 示未知节点的估计位置和真实位置之间的距离约为通信半径的3 0 。也有部分定 位系统将二维网络部署区域划分为网格，其定位结果的精度也就是网格的大小， 如m i c r o s o f t 的r a d a r 系统系统。 2 锚节点密度 锚节点是指在网络一部署完毕，便可以知道自己位置的那些传感器节点。锚 节点定位通常依靠人工部署或g p s 实现。由于经常应用在环境恶劣的区域，人工 部署锚节点的方式并不现实，而且还严重制约网络和应用的可扩展性。使用g p s 定位，锚节点的费用会比普通节点高两个数量级，这意味着即使仅有1 0 的节点 是锚节点，整个网络的价格将增加十倍。因此锚节点密度也是评价定位系统和算 法性能的重要指标之一。 3 节点密度 节点密度即一个节点平均有几个邻居节点，通常以网络的平均连通度来表 示。在无线传感器网络中，节点密度增大不仅意味着网络部署费用的增加，而且 通信冲突更加频繁，带来有限带宽的阻塞。许多定位算法的精度受节点密度的影 响，如d v - h o p 算法陋儿纠仅可在节点密集部署情况下合理估算节点位置。 4 覆盖率 覆盖率值的是成功实现定位的未知节点与未知节点总数的比例。无论如何部 署，总会有一些不可达或连通度极低的未知节点存在，实现尽可能多的未知节点 的精确定位也是自身定位算法和系统的追求目标之一。 5 容错性和自适应性 传感器网络在真实应用中经常会遇到诸如以下问题：外界环境中存在严重的 多径传播、衰减、通信盲点等问题；网络节点由于周围环境或自身原因( 如电池 耗尽、物理损伤) 而出现失效的问题；外界影响和节点硬件精度限制造成节点间 点到点的距离或角度测量误差增大的问题。由于环境、能耗和其他原因，物理的 维护或替换传感器节点或使用其他高精度的测量手段常常是十分困难或不可行 的。因此，定位系统和算法的软、硬件必须具有很强的容错性和自适应性，能够 1 5 山东大学硕十学f ) = 论文 通过自动调整或重构纠正错误、适应环境、减小各种误差的影响，提高定位精 度。 6 功耗 无线传感器网络中，每个传感器节点的能量是十分有限的，而且应用环境常 常十分恶劣，更换电池几乎是不现实的，因此功耗问题是对无线传感器网络的设 计和实现影响最大的因素之一。 7 代价 定位系统或算法的代价可从几个不同方面来评价。时间代价包括一个系统的 安装时间、配置时间、定位所需时间。空间代价包括一个定位系统或算法所需的 基础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一种定位系统或 算法的基础设施、节点设备的总费用。 上述8 个性能指标不仅是评价w s n 自身定位系统和算法的标准，也是其设计和 实现的优化目标。为了达到这些目标的优化，需要进行大量的研究工作。同时这 些性能指标是相互关联，难以同时顾及的，必须根据具体需求做出权衡，选择和 设计合适的定位技术。 1 4 本文的研究内容 本文研究的内容和目标包括：对无线传感器网络中现有的节点定位算法进行 分类及归纳总结，深入研究一种基于a o a 的无线传感器网络三维联合定位算法， 对其存在的一些问题提出解决方案，并在此基础上进行如下改良：构建仿真模 型，研究r 值、超声波频率的变化频带等参数对测量结果的影响，并寻找最佳的 参数值；结合仿真数据，分析测量误差产生的原因，并导出关于误差的公式算 法；最后探索研究是否可用电磁波取代超声波，如可能，并比较分析其性能。 论文的各章节内容安排如下： 第一章绪论。主要介绍课题的研究背景，概述无线传感器网络以及典型的定 位系统和算法，最后介绍了论文的主要工作。 第二章深入研究一种基于a o a 的无线传感器网络三维联合定位算法。 第三章创建仿真模型，分别深入研究r 值、超声波频率的变化频带对三维联 合算法测量结果的影响，并分析其测量误差产生的原因。 1 6 山东大学硕士学位论文 第四章基于对r 值、超声波频率的变化频带的仿真分析，导出一个关于误差 的公式算法，并通过仿真实验给出最佳的参数值。 第五章探索是否可用电磁波取代超