（通信与信息系统专业论文）一种新的基于波的干涉的传感器节点定位算法.pdf

山东大学硕士学位论文 w s n t o a t d o a r s s i 氏q 入 g p s s p a a h l o s a p s a p l l r n l o s h i r i 鹏 符号说明 w i r e l e s ss e n s o rn e 佩，o r k s t i m eo fa r r i v a l t i m ed i 行醯e 1 1 c eo fa r r i v a l r e c e i v e ds i 印a ls 慨g mh l d i c a t o r a n g l e0 f 加1 r i v a l i n t 硎 酾l c eo fw a v 髓 g 1 0 b a lp o s i 怕n i n gs y s t 锄 s e l f 印s i t i o i l i i l g 越g 嘶t h i n a d - h o cl o c a l i c a t i o ns y s t e m a dh o cp o s i t i o i l i n gs y s t e m 蛔x i n l a t ep o i i l t i n t 五a n g u l a t i o nt e s t n o n l i n c - o f s i g h t h i g h - 胁o l 砸0 nr 0 b u s th a l i z a t i o n 无线传感器网络 到达时间 到达时间差 接收信号强度指 示器 到达角度 波的干涉 全球定位系统 自定位算法 a d _ h o c 定位系统 a d h o c 定位系统 近似的p i t 测试法 非视距 高精度定位算法 5 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：翌整：薹一 日期：兰堕生! 旦至! 旦 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名珊麟聊签名：磁溘日期： 硼彦每年片寻d 目 山东大学硕士学位论文 摘要 无线传感器网络( w s n ) 作为未来新兴技术之一，它的发展和广泛应用，将对 人们的社会生活和产业变革带来极大的影响。它相对于移动通信网、无线局域 网、蓝牙网络、a dh o c 网络等常见的无线网络具有很多新的特点，有很多的研究 热点。 无线传感器网络由大量靠无线和多跳方式通信的智能传感器节点构成，这些 节点一般被密集布设在特定的没有固定基础设施的监控区域。由于传感器节点在 布设时采取随机投放的方式，网络中大多数节点位置不能事先确定。但对于很多 应用，没有位置信息的监测消息是毫无意义的。因此，在传感器网络中，传感器 节点的精确定位是各种应用的前提和基础。在大规模无线传感器网络环境下，节 点资源( 能量、处理能力、存储量) 有限，可靠性差，通信距离短，给传感器网络 的自身定位带来了很大的挑战。本文的研究工作就是围绕着无线传感器网络自身 定位这一课题进行的。 本文首先对无线传感器网络自身定位问题进行综述，介绍自身定位的基本概 念、基本方法，给出传感器网络自身定位算法的评价指标、分类方法，分析评价 了几个自身定位典型算法。 接着在对基于距离的定位算法进行深入研究的基础上，提出了一种新的未知 节点角度测量方法。该方法以波的干涉基本理论为基础，将对未知节点的角度测 量转化为较易实现的频率测量。简单地说，就是在信标节点发出变频干涉波，则 干涉场中相对于信标节点角度不同的点所经历的合成波强度的变化频率是不同 的；即角度小时合成波强度的变化频率也小，随着角度的增大，合成波强度的变 化频率也增大。根据这一现象，各未知节点通过检测自身位置处合成波强度的变 化频率，就可以确定自身相对于信标节点的角度。 最后，在上面所提出的新的节点角度测量法的基础上，对传感器网络节点的 定位算法做了进一步的探讨和实验。 山东大学硕士学位论文 经实验证明，本文提出的传感器网络节点角度测量方法简单易用，与a o a 相 比，对节点硬件没有过高要求，且定位精度较高，是一种适用于无线传感器网络 的新的节点定位方法。 2 关键字：角度测量；干涉波；强度颇率；无线传感器网络 山东大学硕士学位论文 a b s t r a c t w i r e l e s ss e n s o rn 咖o r k s ( w s n s ) w i l lb eo n eo fm o s ti m p o r t a n tn e w t e c l l n o l o g i e s i nt h em t u r e i t sd e v e l o p m e i l t 硼de x t e n s i v e 印p l i c a t i o i l sw i l ls u r e l yb r i n g 伊e a ti m p a c t o nb l l i i l 柚l i f cs t y l ea n da l s os 纸ft 0i i l d u 嘶a lr c i l 0 v a t i o n a n dc o m p 枨遍w i t l lf i a i i l i l i a r w i r e l e s sn e l m ，o t k ss u c ha sm o b i l ec o m m u l l i c a t i o nn e “v o r k 、w i r e l e s sl o c a la r e a n 咖。呔、b l l l e 觚) t bn e t w o r k 、a dh o cn e m o r ke t c ，w s nh a sa1 0 tn e wp r o p e n i e s a i l dm 觚yr e s e a r c hh o t s l 砷t s a 、i r e l e s ss 锄ri l c 撕o r k ( w s n ) c o i l s i s t so fas e to fs e n s o r st h a tc o m m 疵c a t e w i t he a c ho t l l e ri na na dh o cm 锄e r 1 1 1m i sk i n do fn c t w o r l ( ，s 饥s o rn o d e 8a r ed 印l o y c d r a n d o i i l l y 锄dd 饥s e l yi nt h e 邪隐t 0b em o n i 删t h ep r e c i s ep o s i t i o i l so f t l l es 伽岱 m a y1 1 0 tb eh o w n i i la d v a i l c e ；b u tt op 赋e s si i l f o 衄新o n ，i ti si m p o r t a n tt oh o w 慨 t l l ed a t ac o m 鼯缸眦s o ，d e t 印n i i 血1 9m ep o s i t i o 璐o fs e i l s o r si sak e yp r o b l e mi nm 觚y a p p l i c a t i o 璐1 kn o d 骼a 他t ) i p i c a l l yh i g l l l y 碱；o l h 争c o i l s t r a i l l e d r o c 岱s o r m e n l o 锄dp o w e r ) ，a r ep r o n et of 砸l u i e h a v el 砌t e dc o m m u i l i c a t i o n r a n g e t h e s e c h 锄c t e r i s t i c sp r e s tg r e a td i 伍c l l l tt 0l a 唱e s c a l es e n s o rn e t 啪f k s 1 0 c a l 讫a t i o n t c c l l i l i q u c s t h i s 也懿i s 舭u s 懿o ns e l f l o c a l 娩a t i o np r o b l e m i nw i r e l c s ss e 芏l s 0 rn e t w o f k s f i r s tt h e 也器i sr e v i e w so ft 1 1 e1 0 c a l i z a 缸o np r o b l e mi nw i r e l e s ss e i l s o rn e t w 诎s ， i n 眦髂t l l e 缸1 d a m 锄t a lp 血c i p l 鼯o fs c l k a l 娩撕o nt i 。c h i l i q u e s ，d i s c 吣s 鹤t h e e 、r a lu a _ t i o nc r i t 舐o no f 也ep e m 脚1 a n c e 锄d 也et a ) 【o n 伽哕o f 丽r e l e s ss e i l s o rn e 眺 l c l o c a l 刎o na l g o r i t h m s ，m s c u s s c st ：h c p r i n c i p l 骼卸dc h a r a c t e r i s t i c s o fs o m e r 印r e s 既她廿v e1 0 c a l i z 舭n 印p r o a c h 骼 i 协恤m 岱i sp r o p o s 髓an 铡m e t h o do fa n g i l l a t i o no f 幽w nn o d c s b 砌o n t h et l l 。0 巧o fi n t e l f e 阚1 c e0 fw a v e s ，l i sm i 甜l o dt r a n s f - o 肌st 1 1 e 锄班em ea s _ u r 锄e n tt 0 t h ee a s i e r 鱼m q u e n c ym s 哪e m e n t h ls i i n p l y ，t h eb e a c o nn o d es c i l d si n _ t c l f 的l c eo f w a v 懿a n dc h 锄g 岱t h e 心e q 嘞c y ，i 1 1m i sp r c h c 器蹈，c h a n g i i l gf b q u e n c yo ft l l ec o m p o s e d w a v 嚣i n t e n s i t ) ，i nd i 舒：r e n td i r e c t i o n st 0 廿l eb e a c o nn o d ei sd i f f 打e n t ，i e ，也ec h a n 垂n g 蜀n e q u c yo fm ec o i n p o s 。dw a v 嚣i 够i s 锄a l l 、j l ，! h 铋t l l ea n 舀ei ss m a l l ，觚dg o 铝 u pw i t t l 觚百e a c c o r d 吨t 0t l l i s 劬旭l l i l ：b 1 0 w nn o d e sc 觚m e 趿鹏t h e 孤酉et 0m e b e a c o nn o d e 。 3 山东大学硕士学位论文 f i n a l l y ，b 嬲e d0 nm en e wm e a s u r 锄e mo ft i l e 锄g l eo fs m s o rn o d 岱，也ep a p e r d i s c u s s e s 舭u tt l l ep o s i t i o n i n ga l g r i t h m 觚dd o e st h ce x p 洫e n t m s wm 删o f a i l g u l a t i o no fu i 】妇o 、ns e i l s 0 rn o d c s i ss i m p l ea n de a s yt 0u s e ， c o m p a r e dt 0a o 八h 弱l o w e rr e q u e s tt 0m eh 锄d w a r eo fs e l 】l s o rn o d e s 孤dh a sh i g h e r p r e c i s i o n t 1 1 i s 锄g l em e a s l l r 啪e n ti sn e w 锄d s u i t a b l ef o rt h ew i r e l e s s ss e i l s o rn e t w o r k s k e y w o r d s ：a n g km e a s u m e n t ；i n t e r f e r e n c ew a v e s ；i n t 蛆s i 锣；f r e q u e n c y ；w s n 4 山东大学硕士学位论文 第一章绪论 1 1 引言 无线传感器网络( w s n ) 是由大量无处不在的，具有通信与计算能力的微小传感 器节点密集分布在无人值守的监控区域而构成的能够根据环境自主完成指定任务的 。智能”自治测控网络系统。如果说因特网改变了人与人之间交流、沟通的方式，那 么，w s n 则将逻辑上的信息世界与真实物理世界融合在一起，将改变人与自然交互 的方式。为此，无线传感器网络被认为是2 l 世纪最重要的技术之一，2 0 0 3 年2 月 份的美国技术评论杂志评出对世界产生深远影响的十大新兴技术，无线传感器 网络被列为第一，未来科学家预言无线传感器将引发新的信息革命，一些专家认为 传感器网络、仿生人体器官等是全球未来的四大高技术产业，它们将掀起新的产业 浪潮，这预示着未来到处是以电池为电源的无线传感器网络，这些传感器可监控环 境、机器甚至人类自己。 传感器技术本身不断地在发展、深化和交叉，从原先的单一的敏感元件发展到 混合集成传感器、智能传感器、无线传感器网络等，真正朝着无所不在的信息获取 技术方向迈进。无线传感器网络是一种独立出现的网络，它的基本组成单位是无线 传感器节点，这些节点集成了传感器、微处理器、无线接口和电源管理四个主要模 块。传感器、微机电系统( 姬 l s ) 集成电路、以及低功耗无线通信等技术的飞速发 展，使得低成本、低功耗、多功能的微型无线传感器网络的大规模应用成为可能， 这些微型无线传感器是集成的光机电一体化系统，具有无线通信、数据收集和处 理、协同工作等功能。它们共同组成了传感器网络，导致了一种全新的信息获取和 处理模式，微型传感器节点可以随机或者特定地布置在工作环境中，通过无线通信 实现自组织，获取周围环境的信息，形成分布自治系统，相互协同完成特定的任 务。 信息的获取是实现信息化的前提获取物理环境信息的一种重要工具就是传感 器。传感器等信息获取技术和传送技术的进步，为传感器网络的发展和应用奠定了 基础。近年来，随着无线技术、旺m s 技术的发展，传感器网络技术取得了巨大的 6 山东大学硕士学位论文 进步。无线传感器网络由于其快速展开、抗毁性强、监测精度高、覆盖区域大等特 点而产生了广阔的应用前景，由此成为当前信息领域的研究热点。 w s n 巨大的学术价值和广阔的应用前景中，已经引起了许多国家军事界、产业 界和学术界的高度重视。从2 0 世纪九十年代开始，美国d a r p a 先后启动 t w i n s ( w l e 鼹硼锷嘣。dn e t 、0 收s 锄s o r s ) 【1 1 、u j 6 心旧s ( i i l i c 玲a i d a 曲v em 出- d o m a i n p o w 昏a w 嘴s 渊) 、s e i l s i t ( s 吼s o rh 怕咖a 幻nt e c h n o l o g y ) 圈等项目，出巨资在众 多大学和研究机构展开传感器网络的基础研究，它们涵盖了w s n 设计、节点设计、 通信协议、信息处理等各个方面，极大地推动了w s n 技术的发展。 1 2 无线传感器网络概述 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ，简称w s n ) 【3 】是当前在国际上备 受关注的、涉及多学科高度交叉、知识高度集成的前沿热点研究领域。它综合了传 感器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息处理技术等， 能够通过各类集成化的微型传感器协作地实时监测、感知和采集各种环境或监测对 象的信息，这些信息通过无线方式被发送，并以自组多跳的网络方式传送到用户终 端，从而实现物理世界、计算世界以及人类社会三元世界的连通。 w s n 以最少的成本和最大的灵活性，连接任何有通信需求的终端设备，采集数 据，发送指令。作为无线自组双向通信网络，传感网络能以最大的灵活性自动完成 不规则分布的各种传感器与控制节点的组网，同时具有一定的移动能力和动态调整 能力。 w s n 可应用于布线和电源供给困难的区域，人员不能到达的区域( 如受到污 染、环境不能被破坏或敌对区域) 和一些临时场合( 如发生自然灾害时，固定通 信网络被破坏) 等。它不需要固定网络支持，具有快速展开，抗毁性强等特点， 可广泛应用于军事、工业、交通、环保等领域，被认为是2 l 世纪最重要的技术 之一，它将会对人类未来的生活方式产生深远影响。 w s n 节点既是信息的采集和发出者，也充当信息的路由者，采集的数据通过 多跳路由到达网关，再由网关与外部通信。 1 2 1 无线传感器网络结构 7 山东大学硕士学位论文 无线传感器网络典型的体系结构如图l l 所示【3 】，节点具有传感、信号处理 和无线通信功能，它们既是信息包的发起者，也是信息包的转发者。通过网络自 组织和多条路由，将数据向网关发送。网关( 也称为s i n kn o d e ) 是一个特殊的 节点，它可以使用多种方式与外部网络通信，如i n t e r n e t 、卫星或移动通信网络 等等，大规模的应用可能使用多个网关，也可以利用无人机飞越网络上空，通过 网关采集数据。节点由于受到体积、价格和电源供给等因素的限制，通信距离较 短，只能与自己通信范围内的邻居交换数据，要访问通信范围以外的节点，必须 使用多跳路由。为了保证网络内大多数节点都可以与网关建立无线链路，节点的 分布要相当的密集。 监控中心j 用户 圃 图l l 无线传感器网络体系结构图 1 2 2 无线传感器网络的特点 无线传感器网络具有很多鲜明的特剧3 】： ( 1 ) 通信能力有限，通信覆盖范围较窄。 ( 2 ) 电源能量有限。电源能量约束是阻碍传感器网络应用的严重问题，在 传感器网络设计过程中，任何技术和协议的使用都要以节能为前提，最大化网络 的生命周期。 山东大学硕士学位论文 ( 3 ) 无中心。无线传感器网络中所有节点地位平等，是对等式网络，节点 可以随时加入或离开网络，任何节点的故障不会影响整个网络的运行，具有很强 的抗毁性。 ( 4 ) 自组织。网络的布设和展开无需依赖于任何预设的网络设施，节点通 过分层协议和分布式算法协调各自的行为，节点开机后就可以快速、自动地组成 一个独立地网络。 ( 5 ) 多跳路由。网络中节点通信距离有限，一般在几百米范围内，节点只 能与它的邻居直接通信。如果希望与其射频覆盖范围之外的节点进行通信，则需 要通过中间节点进行路由固定网络的多跳路由使用网关和路由器来实现，而无 线传感器网络中的多跳路由是由普通网络节点完成的，没有专门的路由设备。这 样每个节点既可以是信息的发起者，也是信息的转发者。 ( 6 ) 硬件资源有限。节点计算能力、程序空间和内存空间普遍的比计算机 功能要弱很多，因此在节点操作系统设计中，协议层次不能太复杂。 ( 7 ) 节点数量众多，分布密集。为了对一个区域执行监测任务，往往有成 千上万传感器节点空投到该区域，传感器节点分布非常密集，利用节点之间高度 连接来保证系统的容错性和抗毁性。 1 2 3 无线传感器网络协议栈与功能模块 随着传感器网络的深入研究，研究人员提出了多个传感器节点上的协议栈。 早期的协议栈【l 】包括物理层、数据链路层、网络层、传输层和应用层，与互联网 协议栈的五层协议相对应，如图l 一2 所示。另外，协议栈还包括能量管理平 台、移动管理平台和任务管理平台。这些管理平台使得传感器节点能够按照能源 高效的方式协同工作，在节点移动的传感器网络中转发数据，并支持多任务和资 源共享。各层协议和平台的功能如下： 物理层提供简单但健壮的信号调制和无线收发技术； 数据链路层负责数据成帧、帧检测、媒体访问和差错控制； 网络层主要负责路由生成与路由选择； 传输层负责数据流的传输控制，是保证通信服务质量的重要部分； 应用层包括一系列基于监测任务的应用层软件； 9 山东大学硕士学位论文 能量管理平台管理传感器节点如何使用能源， 能量； 移动管理平台检测并注册传感器节点的移动， 传感器节点能够动态跟踪其邻居的位置； 在各个协议层都需要考虑节省 维护到汇聚节点的路由，使得 任务管理平台在一个给定的区域内平衡和调度检测任务。 图l 一2 无线传感器网络协议栈 传感器节点由传感器模块、处理器模块、无线通信模块和能量供应模块四部 分组成，如图1 3 所示。传感器模块负责监测区域内信息的采集和数据转换； 处理器模块负责控制整个传感器节点的操作，存储和处理本身采集的数据以及其 他节点发来的数据：无线通信模块负责与其他节点进行无线通信，交换控制消息 和收发采集数据；能量供应模块为传感器节点提供运行所需的能量，通常采用微 型电池。前三个模块为传感器节点的能量消耗模块，各模块能量消耗情况如图1 4 所示，可见处理器和传感器模块的功耗很低，绝大部分能量消耗在无线通信 模块上。无线通信模块分为四种状态：发送，接收，空闲和睡眠，发送状态消耗 的能量最多，接收和空闲状态次之，而在睡眠状态则关闭通信模块。所以为使网 络高效使用能量，可以考虑使节点减少不必要的转发和接收，不需要通信时尽快 进入睡眠状态。为使网络通信不会中断，协调好节点相互间的转发、接收的工作 时间是很重要的。 l o 山东大学硕士学位论文 嵌入式软件 0 | 存储器l t 传感器i- ia d 转换器l一微处理器i- 1 无线收发器 ；数据采藁覆瑛i 上 i 其它外设i 匡觋篓篓i ji i 二数据处垂馘j 下 电源 图l 一3 传感器节点体系结构 1 2 4 无线传感器网络的支撑技术 由于w s n 特殊的应用需求和应用场合，不同于传统的有线、无线网络，很多 现有的技术并不完全适合，这给w s n 的设计提出了很大的挑战，很多关键技术需 要进一步研究和实现。目前，w s n 的关键技术主要集中在以下几个方面： 定位技术在w s n 的一些应用中，如战场侦察、地震洪水现场监控等，都需 要知道传感器节点的位置信息，从而确定信息来源的准确位置。全球定位系统 ( g p s ) 己经在很多领域中应用，但它成本高，且对使用环境有一定限制，在水 下、室内等不能直接使用，w s n 需要更加合适的定位技术。定位技术是本论文的 主要研究内容，将在后续章节中重点阐述。 数据融合技术所谓数据融合( d a t aa g g r e g a t i o n ) ，是对大量节点感知获 取的随机的、不确定的、不完整的含有噪声甚至是错误的数据或信息当中，进行 滤波等信息处理，计算出可靠的、精确的完整信息的处理过程。数据融合技术是 w s n 减少数据冗余，提高通信效率和能量效率的一种有效方式。到目前为止，人 们已经提出了不少数据融合的方法，其中波束生成( b e 锄f o 珈i n g ) 算法是w s n 中 应用较多的方法。但是这类算法计算量比较集中，执行该任务节点的能量消耗非 常大，这对于能量受限的传感器节点来说是非常不利的。综合考虑能量效率是 w s n 数据融合技术未来的发展方向。 路由技术对于w s n 来说，提高能量效率、延长网络寿命是其路由算法设计 山东大学硕士学位论文 中首先要考虑的因素。在过去的几年里，已经有大量的研究专门为w s n 设计了很 多路由协议【4 】，如信息协商传感器协议( s e n s o rp r o t o c o l sf o ri n f o 瑚a t i o nv i a n e g o t i a t i o n ，s p i n ) 、定向扩散( d i r e c t e dd i f f u s i o n ) 、低能量自适应分层簇结 构( l o w e n e r g y a d a p t i v ec l u s t e r b a s e dh i e r a r c h y ，l e a c h ) ，高效育邑量收集 算法( p o w e r e f f i c i e n t g a t h e r i n g i ns e n s o ri n f o r m a t i o n s y s t e m s ， p e g a s i s ) 【5 1 、敏感门限高效能耗传感器网络协议( t h r e s h o l d s e n s i t i v ee n e r g y e f f i c i e n tp r o t o c 0 1 s ，t e e n ) 【6 】等。以上路由协议在节省能量方面的丰要方法 是：( 1 ) 采用数据融合和资源协商机制，减少冗余数据的发送。( 2 ) 各节点轮流承 担数据处理和发送业务，平均消耗网络能量来延长网络寿命。这些路由协议都很 好地提高了网络的能量效率，但是它们在如何增强移动性、安全性和q o s 等方面 还需要进一步研究。 网络协议由于无线传感器网络节点的计算能力、存储能力、通信能力以及 携带的能量都十分有限。每个节点只能获取局部网络的拓扑信息，其上运行的网 络协议也不能太复杂。同时，传感器拓扑结构动态变化，网络资源也在不断变 化，这些都对网络协议提出了更高的要求。无线传感器网络协议负责使各个独立 的节点形成一个多跳的数据传输网络，目前研究的重点是网络层协议和数据链路 层协议。 网络拓扑控制对于自组织的传感器网络而言，网络拓扑控制具有重要意 义。通过拓扑控制自动生成的良好的网络拓扑结构，能够提高路由协议和m a c 协 议的效率，可为数据融合、时间同步和目标定位等很多方面奠定基础，有利于节 省节点的能量来延长网络的生存期。 时钟同步时钟同步是需要协同工作的传感器网络系统的一个关键机制。在 分布式系统中，不同的节点都有自己的本地时钟。由于不同节点的晶体振荡器频 率存在偏差，以及温度变化和电磁波干扰等，即使在某个时刻所有节点都达到时 间同步，它们的时间也会逐渐出现偏差。能量、价格和体积等方面的约束，使得 网络时间协议n t p ( n e t w o r kt i m ep r o t o c 0 1 ) 、g p s 等现有时间同步机制不适用于 传感器网络，需要修改或重新设计时间同步机制来满足传感器网络的要求。 安全技术任务型的w s n 在很多情况下都需要保证其任务执行的机密性和数 据传输的安全性，它需要一套有效的安全机制，包括物理层的高效加密算法、数 山东大学硕士学位论文 据链路层抗d o s 攻击的安全姒c 协议、网络层的安全路由协议及应用层的密钥管理 和安全组播方案等。s p i n s ( s e c u r i t yp r o t o c o l sf o rs e n s o rn e t w o r k ) 【7 】安全体 系是目前所提出的安全机制中比较实用的w s n 安全机制。它在数据机密性、完整 性、可认证等方面都作了充分的考虑。在密钥管理方面，预配置密钥方式是w s n 比较常用的一种方式，比较有代表性的算法有随机密钥对模型和基于多项式的密 钥对模型等。 无线通信技术无线传感器网络需要低功耗短距离的无线通信技术。 i e e e 8 0 2 1 5 4 标准是针对无线个人网络的无线通信标准，把低功耗、低成本作为 设计的主要目标，旨在为个人或者家庭范围内不同设备之间低速联网提供统一标 准。该标准较适用于无线传感器网络。 此外，介质访问控制协议、容错技术、应用层技术等都是w s n 目前研究的技 术热点。 1 3 无线传感器网络定位算法概述 无线传感器网络由大量靠无线、多跳方式通信的智能传感器节点构成，这些 节点一般被密集布设在特定的没有固定基础设施的监控区域 & 1 0 1 ，其目的是协作 地感知、采集和处理网络覆盖的地理区域中感知对象的信息，并发布给观察者。 由于传感器节点在布设时采取随机投放的方式，网络中大多数节点位置不能事先 确定。但对于很多应用，如目标跟踪，实时监视目标的行动路线，预测目标的行 动轨迹等，不知道传感器位置而感知的数据是没有意义的【l l 1 2 1 。另外，无线传感 器网络的定位还可以为其他一些应用提供位置信息：分布式事件记录；基于位置 的路由协议，如直接利用节点位置信息进行数据传递的地理路由协议，避免信息 在整个网络中的扩散，并可以实现定向的信息查询；为网络提供命名空间【1 3 以5 】； 实现网络的负载均衡【1 6 1 7 】；进行网络管理，利用传感器节点传回的位置信息构建 网络拓扑图【1 8 】，并实时统计网络覆盖情况【1 9 洲，对节点密度低的区域及时采取必 要的措施，等等。 因此，传感器节点自身的位置信息是其它大多数研究与应用的前提，定位问 题己成为无线传感器网络领域重要的研究课题，是无线传感器网络技术研究的基 础【2 l 】。 山东大学硕士学位论文 全球定位系统g p s 是目前应用得最广泛最成熟得定位系统，通过卫星的实时 授时和测距对用户节点进行定位，具有定位精度高、实时性好、抗干扰能力强等 优点，但是g p s 定位适应于无遮挡得室外环境，用户节点通常能耗高体积大，成 本也比较高，需要固定的基础设施等，这使得它不适用于低成本自组织的传感器 网络【2 2 粕】。在机器人领域中，机器人节点的移动性和自组织等特性，使其定位技 术与传感器网络的定位技术具有一定的相似性，但是机器人节点通常携带充足的 能量供应和精确的测距设备，系统中机器人节点的数量很少，所以这些机器人定 位算法也不适用于传感器网络。人工部署传感器节点也受到成本等问题的限制。 因此，必须采用其它方法实现传感器网络自身定位。 传感器节点的定位是w s n 系统布设完成后面临的首要问题，它可表述为：依靠 有限的位置己知节点，在传感器节点间建立起一定的空间关系，确定布设区中其 它节点的位置【2 5 1 。 由于传感器节点能量有限、可靠性差、节点规模大且随机布放、无线模块的 通信距离有限，对定位算法和定位技术提出了很高的要求。传感器网络的定位算 法通常需要具备以下特点： 1 ) 自组织性：传感器网络的节点随机分布，不能依靠全局的基础设施协助定 位。 2 ) 健壮性：传感器节点的硬件配置低、能量少、可靠性差，测量距离时会产 生误差，算法必须具有较好的容错性。 3 ) 能量高效：尽可能地减少算法中计算的复杂性，减少节点间的通信开销， 以尽量延长网络的生存周期。通信开销是传感器网络的主要能量开销。 4 ) 分布式计算：每个节点计算自身位置，不能将所有信息传送到某个节点进 行集中式计算。 针对不同的w s n 应用，节点定位难度不尽相同。对于军事应用，节点布设有 可能采取空投的方式，导致节点位置随机性非常高，系统可用的外部支持也很少： 而在另外一些场合，节点布设可能相对容易，系统也可能有较多的外部支持。 在传感器网络节点定位技术中，传感器节点可以分为两类：信标节点和未知 节点。信标节点在网络中所占比例很小，可以通过携带g p s 系统或者预先在指定 位置部署等手段获得自身的精确位置。信标节点在定位技术中作为参考点，以确 1 4 山东大学硕士学位论文 定未知节点的实际位置。未知节点通过定位技术，根据信标节点的位置信息来确 定自身位置。 4 波的干涉理论概述 1 4 1 波的干涉的基本理论及其应用领域 两列波在传播时相遇，将保持各自的特性( 频率、波长、振动方向等) 独立 传播下去，这称为波的独立传播原理【2 6 】。正因为波的传播具有独立性，当两列波 在空间某点相遇时，在该点每列波引起的振动，并不因其他波的存在而发生改 变。因此该点的振动就是每列波在该点引起振动的合成，这就是波的叠加原理。 波的叠加原理强调几列波相遇时所引起的总的综合效应。 一般地说，振动方向、频率、振幅、相位均不相同的几列波在空间相遇时， 其合成波是很复杂的。而振动方向相同、频率相同、相位差恒定的两个波源发出 的两列波在空间相遇时，形成的空间各点的合振动各具有一定振幅，这些不同振 幅的振动在空间的分布不随时间变化，这种现象称为波的干涉，这样的两列波称 为相干波，相应的波源称为相干波源。 在应用领域，以干涉原理为基础的干涉测量技术为人们提供了精密测量和检 验的手段。如激光干涉仪，可以用来测量表面的平面度，机械部件的圆度，曲率 半径等；利用雷达干涉技术监测区域地表形变；合成孔径雷达干涉测量是新出现 的卫星成像技术，可以得出地面位移场完整的密集合成孔径雷达干涉图像，用于 地震研究、火山活动监测以及冰川和冰流运动的研究。 1 4 2 波的干涉理论在本文中的应用 本文将波的干涉理论应用于传感器节点定位中的角度测量。角度测量是节点 定位的基础。信标节点发出两列干涉波，就会在其周围形成干涉场。匀速提高发 射波的频率，则干涉场中各点处合成波的强度会发生变化，而且相对于信标节点 不同的角度合成波强度的变化频率也是不同的。根据合成波强度的变化频率，各 未知节点就可以测出自身所在的相对位置。 山东大学硕士学位论文 1 5 本文结构安排 本文首先对无线传感器网络进行的综述，然后对已有的定位算法进行了介绍 和分析，接着提出了一种新的基于波的干涉的未知节点角度测量方法，并在这种 新的角度测量方法的基础上，设计了定位算法，进行了仿真实验。 本文共分为五章。第一章阐述了课题的研究背景、意义、理论依据和研究方 向，第二章对现有的定位算法进行了分析和讨论，并提出了本文的观点。第三章 对提出的新的基于波的干涉的未知节点角度测量法的基本原理，实现方法进行了 详细的阐述，并建立模型进行了仿真实验。第四章在上一章节点角度测量的基础 上，对未知节点进行了定位。第五章总结了本文的工作和创新特点，指出了进一 步研究方向。 1 6 山东大学硕士学位论文 第二章无线传感器网络节点定位技术 在无线传感网络中，位置信息对监测活动至关重要，在很多应用中，检测到 事件之后所关心的首要问题就是事件发生的位置。例如，交通拥塞发生的地点， 城市中车辆运动的区域，军事目标的位置等。对于这些问题，传感器节点必须首 先知道自身的地理位置信息，这是进一步采取措施和做出决策的基础。 节点位置信息除了用来报告事件发生的地点外，还具有下列用途：目标跟 踪，实时监视目标的行动路线，预测目标的前进轨迹；协助路由，如直接利用节 点位置信息进行数据传递的地理路由协议，避免信息在整个网络中的扩散，并可 以实现定向的信息查询；进行网络管理，利用传感器节点传回的位置信息构建网 络拓扑图，并实时统计网络覆盖情况，对节点密度低的区域及时采取必要措施， 实现网络的负载均衡等。确定传感器节点的位置是传感网络最基本功能之一，对 传感网络的有效性起着关键作用，也是本文重点研究的问题。 传感网络节点的能量有限、可靠性差、节点规模大且随机布放、无线模块的 通信距离有限，对定位算法和定位技术提出了很高的要求【2 7 】。因此，传感网络的 定位算法通常要求具备自组织性好、健壮性强、能量高效和分布式计算等特点。 目前的算法大都在能耗、成本和精度上作了折衷考虑。由于各种情况差别很大， 没有普遍适合于各种应用的定位算法，因此要针对不同的应用，通过综合考虑节 点的规模、成本及系统对定位精度的要求来选择最适合的定位算法。 2 1 节点定位技术的基本概念 传感器网络中每个节点在某个空间坐标系中确定自己空间位置的过程称为节点 定位【2 酊。由无线传感器网络的特点知，给每个传感器节点配备一个g p s 接收器或事 先为每个节点指定位置信息是不现实的，因此我们只能使一小部分节点装配定位装 置或事先给这些节点指定位置坐标，这些通过某种手段知道自身位置的少数节点称 为信标节点( b e a c o nn o d e ) 或锚节点( a n c h o rn o d e ) 。在传感器网络中除了知道自己 位置信息的参考节点外就是需要通过某种算法计算出自己位置信息的节点，称这些 节点为未知节点( u n k n o w nn o d e ) 。 1 7 山东大学硕士学位论文 信标节点在网络节点中所占的比例很小，可以通过携带g p s 定位设备等手段获 得自身的精确位置，是未知节点定位的参考。信标节点通过向未知节点广播自己的 位置信息，为未知节点确定位置提供信息。 无线传感器网络节点定位问题可表述为：依靠有限的位置已知节点即信标节 点，确定布设区中其它未知节点的位置，在传感器节点间建立起一定的空间关系 的过程。 2 节点定位技术分类 无线传感器网络节点定位算法的分类方法很多，目前提出的定位算法通常有以 下几种分类： ( 1 ) 基于距离的定位算法和距离无关的定位算法 根据定位过程中是否测量实际节点间的距离，把定位算法分为：基于距离的 ( r a n g e - b a s e d ) 定位算法和距离无关的( r a n g e f r e e ) 定位算法嘲。前者需要测量相 邻节点间的绝对距离或方位，并利用节点间的实际距离来计算未知节点的位置；后 者无需测量节点间的绝对距离或方位，而是利用节点的连通性和多跳路由信息交换 等方法来估计节点间距离或角度，并完成位置估计。基于距离的定位算法总体上能 取得较好的定位精度，但在硬件成本和功耗上受到一些限制。在硬件和功耗限制较 为苛刻时，非基于距离的定位算法是一种低成本、高效率的取代方法。室内定位系 统c r i c k e t 【3 0 】、a h l o s ( a 扣h o cl o c a l i z a t i o ns y s t 鲫) 算法【3 1 1 、基于a o a 的a p s 算法 ( a dh o cp o s i t i o n i n gs y s t 鲫) 【3 2 】、i 砌a r 算法【3 3 1 、l c b 算法( l o c a l i z a b l e c o l l a b o r a t i v eb o d y ) 瞰1 和d p e ( d i r e c t e dp o s i t i o ne s t i m a t i o n ) 【3 习算法等都是基 于距离的定位算法。 距离无关的定位算法在计算未知位置节点的实际位置时，不需要两节点之间 的实际距离或者角度，因而降低了对节点的硬件要求，同时满足了传感器网络应 用的实际需求。目前提出的距离无关的定位算法有质心算法，d v h o p 定位，基于 概率统计模型的定位【3 6 ，3 7 】【2 8 】等等。 ( 2 ) 递增式的定位算法和并发式的定位算法 根据节点定位的先后次序不同，把定位算法分为：递增式的( i n c r 明e n t a l ) 定 位算法和并发式的( c o n c u r r e n t ) 定位算法【3 8 】。递增式的定位算法通常从信标节点开 山东大学硕士学位论文 始，信标节点附近的节点首先开始定位，依次向外延伸，各节点逐次进行定位，这 类算法的丰要缺点是定位过程中累积和传播测量误差；并发式的定位算法中所有的 节点同时进行位置计算。有些并发式的算法采用迭代优化的方式来减小误差。并发 式定位算法能更好地避免局部最小和误差累积。 ( 3 ) 基于信标节点的定位算法和无信标节点的定位算法 根据定位过程中是否使用一定比例的信标节点，把定位算法分为：基于信标节 点的( b e a c o n - b a s e d ) 定位算法和无信标节点的( b e a c o n f r e e ) 定位算法【3 9 加】。前者 在定位过程中，以信标节点作为定位中的参考点，各节点定位后产生整体绝对坐标 系统；后者只关心节点间的相对位置，在定位过程中无需信标节点，各节点先以自 身作为参考点，将邻近的节点纳入自己定义的坐标系中，相邻的坐标系统依次转换 合并，最后产生整体相对坐标系统。基于信标节点的定位算法很多，例如质心算 法、d v h o p 、a h l o s 、l c b 和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 nt e s t ) 等 等；而a b c ( a s s u m p ti o n b a s e d c o o r d i n a t e s ) 【4 1 】和a f l ( a n c h o r - f r e e l o c a li z a t i o n ) 【3 8 】是典型的非基于信标节点的定位算法。 ( 4 ) 集中式计算与分布式计算 集中式计算( 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 叩u t a t i o n ) 是指依赖节点间的信息交换和协调，由节点自行计 算的定位方式。集中式计算的优点在于从全局角度统筹规划，计算量和存储量几 乎没有限制，可以获得相对精确的位置估算。它的缺点包括与中心节点位置较近 的节点会因为通信开销大而过早地消耗完电能，导致整个网络与中心节点信息交 流的中断，无法实时定位等【2 3 】。集中式定位算法包括凸规划( c o n v e x o p t i m i z a t i o n ) 粕s m a p 等n - h o pm u l t i l a t e r a t i o np r i m i t