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

摘要 节点自定位技术是无线传感器网络的主要支撑技术之一。在大多数无线传感器 网络应用中，确定传感器节点的物理位置是最基本的要求。目前现有的无线传感器 网络节点自定位算法普遍存在定位性能受环境和锚节点配置影响大、算法复杂度 高、能耗大等问题。随着无线传感器网络技术的不断进步成熟，其应用将会越来越 广泛，节点定位技术研究对于无线传感器网络具有重要的理论意义和应用价值。 本文旨在对无线传感器网络节点自定位技术进行相关的讨论和研究。 ( 1 ) 针对e u c l i d e a n 算法中定位精度及覆盖率受锚节点密度影响较大的问题， 提出了一种改进的分布式节点自定位算法。该算法将初始定位精度较高的节点升级 为锚节点，未知节点根据更新的锚节点位置信息循环求精，并通过估计坐标值的方 差来控制循环求精过程中的循环次数。仿真实验显示，改进定位算法在锚节点密度 较低情况下能有效提高定位精度和覆盖率，明显降低了对锚节点密度的依赖程度。 ( 2 ) 将基于支持向量机( s v m ) 理论应用于传感器节点自定位中，提出了一种 基于s v m 分类区域的距离无关的定位算法，首先s v m 通过对训练数据的学习构造一 个二叉决策树分类器，然后该分类器将未知节点的位置确定在某一分类区域中，最 后取这一区域的中心作为节点的估计位置。该算法仅仅需要网络连通性信息( 即跳 数) ，降低了网络成本和通信负荷。仿真表明该算法在保证一定的定位精度下，有 效减轻了覆盖漏洞和边缘问题。 最后。对论文的工作进行了总结，对未来的研究工作进行了展望。 关键词：无线传感器网络；自定位；循环求精；分类区域 a b s t r a c t n o d es e l f - l o c a l i z a t i o nt e c h n o l o g yi so n eo ft h em a i ns u p p o r t i n gt e c h n o l o g i sf o r w i r e l e s ss e n s o rn e t w o r k i nm o s ta p p l i c a t i o n s ，d e t e r m i n i n gt h ep h y s i c a lp o s i t i o n so f s e n s o rn o d e si st h eb a s i cr e q u i r e m e n t s a tp r e s e n t , t h ee x i s t i n gn o d es e l f - l o c a l i z a t i o n a l g o r i t h mh a sg r e a t l yi m p a c t e db yc i r c u m s t a n c e sa n da n c h o rd e p l o y i n g , h i g ha l g o r i t h m c o m p l e x i t ya n dh i 曲p o w e rc o n s u m p t i o np r o b l e ma n ds oo n i t i so b v i o u s l yt h a tt h e t e c h n o l o g yo fw i r e l e s ss e n s o rn e t w o r kw i l lg o a h e a dv e r yq u i c k l ya n di t sa p p l i c a t i o n s w i l lb ew i d e ra n dw i d e ri nt h ec o m i n gf u t u r e 1 1 1 er e s e a r c ha sd e s c r i b e di nt h i s d i s s e r t a t i o ni so fs i g n i f i c a n c ei nb o 也t h e o r e t i c a la n da p p l i c a t i o na r e a s t h i st h e s i si sf o rt h ep u r p o s eo fm a k i n gs o m er e l a t e dd i s c u s s i o n sa n dr e s e a r c ho f s e l f - l o c a l i z a t i o nt e c h n o l o g yb a s e do nw i r e l e s ss e n s o rn e t w o r k ( 1 ) t oa d d r e s st h ep r o b l e mt h a ta n c h o rr a t i oh a v eas t r o n gi m p a c to nl o c a l i z a t i o n e r r o ra n dc o v e r a g ei ne u c l i d e a na l g o r i t h m , t i l i sp a p e rp r o p o s e sai m p r o v e dd i s t r i b u t e d l o c a l i z a t i o na l g o r i t h m t 1 1 i sm e t h o du s e sh i g hl o c a l i z a t i o na c c u r a c yn o d e sa sn e wa n c h o r n o d e s a c c o r d i n gt ot h ei n f o r m a t i o n , o t h e rn o d e sr a i s et h el o c a l i z a t i o na c c u r a c yb y i t e r a t i v er e f i n e m e n t s a n di tc o n t r o l st h ee k e d a t i o nt i m e sw i t ht h ev a r i a n c eo f c o o r d i n a t e s s i m u l a t i o nr e s u l t ss h o wt h a t , c o m p a r e dw i t he u c l i d e a na l g o r i t h m , i m p r o v e d l o c a l i z a t i o na l g o r i t h mc a ne n h a n c et h el o c a l i z a t i o na c c u r a c ye f f i c i e n t l yw h e nt h ea n c h o r r a t i oi sl o w e r i ti so b v i o u st h a tt h ei n f l u e n c eo fa n c h o rr a t i oo nt h el o c a l i z a t i o na c c u r a c y a n dc o v e r a g ei sl e s s ( 2 ) w r ea p p l yt h es u p p o r tv e c t o rm a c h i n e ( s v m ) t h e o r yt o t h es e n s o rn o d e s e l f - l o c a l i z a t i o na l g o r i t h m t h e nar a n g e - f r e el o c a l i z a t i o na l g o r i t h mb a s e do ns v m c l a s s i f i c a t i o nr e g i o n si sp r o p o s e d f i r s t , s v mc o n s t r u c t e dab i n a r yd e c i s i o nt r e ec l a s s i f i e r v i al e a r n i n go ft r a i n i n gd a t a t h e nt h ec l a s s i f i e rd e t e r m i n e dt h ec e r t a i nc l a s s i f i c a t i o n r e g i o nw h e r e t h eu n k n o w nn o d e sl o c a t e di n f i n a l l y , w e 墩t h er e g i o n sc e n t e rp o 血a s t h ee s t i m a t e dp o s i t i o no ft h eu n k n o w i ln o d e 1 1 妃p r o p o s e da l g o r i t h mr e q u i r e dm e r e c o n n e c t i v i t yi n f o r m a t i o n ( i e ，h o pc o u n t so n l y ) ，s oa st or e d u c et h en e t w o r kc o s ta n d c o m m u n i c a t i o nl o a d s 1 1 ks i m u l a t i o nr e s u l t ss h o wt h a tt h i sa l g o r i t h ma l l e v i a t e st h e c o v e r a g eh o l e sa n db o r d e rp r o b l e ms i g n i f i c a n t l yw h i l ec c 羽t a j nl o c a t i o na c c u r a c yw a s a s s u r e d i nt h ee n d , i ti st h ec o n c l u s i o no f t h et h e s i sa n dt h ep r o s p e c tf o rt h ef i l t u r er e s e a r c h k e yw o r d s ：w i 托l e s ss e n s o rn e t w o r k ；s e l f - l o c a l i z a t i o n ；r e r a t i v er e f i n e m e n t s ； c l a s s i f i c a t i o nr e g i o n s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：王竹碚 日期：功睁9 年石月矿日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 、 作者签名：王磅珞 导师签名：苏瓶 日期：枷 年6 月萝日日期：枷吖年占月缪e l 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库一中全文发布，并可按。章程 中的 规定享受相关权益。回壶途塞埕銮蜃溢卮；旦坐生；旦= 玺；旦三生蕉盔! 作者签名：王节砖 导师签名去1 价 日期：卫p 力年6 月苫日日期：z 口岬年月君日 硕士学位论文 m a s t e r st h e s i s 1 1 研究背景及意义 第一章绪论 目前，由于微电子机械系统( m e m s ) 、集成电路( i c ) 设计、射频( 1 强) 等 技术的飞速发展，导致了一种集合处理、存储、无线通信和感应功能的低功耗设备 的出现。这种微型电池供电的设备，被称为无线传感器节点，它们通常随机散布在 人类不能涉足的区域中，测量感兴趣的物理、化学、地质或生物参数，以监测物理 环境。 无线传感器网络节点通常自组织成a d - h o c 网络形式，通过基于根的收集树从 整个网络收集和共享信息，图1 1 是一个无线传感器网络的例子，节点之间以无线 通信方式交换信息，数据经过多跳被转发到基站，这些数据直接或远程登录传递给 终端用户，从而实现了“普适计算”的理念i l 】。 图1 1 无线传感器网络示意图 无线传感器网络节点自身定位技术在传感器网络应用中扮演着基础地位的角 色，也是传感器网络重要的支撑技术之一，图1 2 显示定位技术在无线传感器网络 协议栈中比较特殊的位置，它既要依靠数据传输信道，同时又要为上层的各个网络 协议提供信息服务，比如基于地理位置的路由协议通过应用节点的位置信息可以提 高路由效率，减少网络能量消耗。因此，传感器节点自定位算法的研究对无线传感 器网络的应用和发展都具有重要的意义。 硕士学位论文 m a s t e r st h e s i s 图i - 2 无线传感器网络协议栈 首先，大多数需要感知信息的传感器网络应用都离不开传感器节点的自身位置 1 2 l 。比如无线传感器网络用来监测森林火灾的应用，当基站收到传感器节点感知到 温度变化的数据后，最重要的是要知道火灾发生的具体的地理位置，传感器节点自 身位置信息可以回答温度上升的地方在哪里。还有其他一些应用，比如跟踪有特殊 需要或配有医疗保健设施的人，找到战场上的士兵和坦克，分析动物行为的自然栖 息地等。 定位技术还能为w s n 的其他服务提供有益的支持，优化网络在其它方面的应 用。如传感器网络的地理路由协谢”】，针对目标节点，根据一些节点的准确的位置 信息可确定一条高效的路由路径，以免数据在网络中洪泛传播，对网络动态性有很 好的适应能力，减小了数据延时和网络能量消耗。新的大规模w s n 的基于定位技 术的多跳路由、数据挖掘、数据融合也需要可靠的定位技术，定位技术还可以为网 络提供命名空间，实现均衡网络负荷等【5 】。在不增加成本的前提下，每个传感器节 点嵌入定位系统为w s n 的应用打开了一个新的领域。 传统的定位方法不能很好的直接应用到传感器网络中。现有的定位系统，如全 球定位系统( g l o b a lp o s i t i o ns y s t e m ，简称g p s ) ，一个卫星无线电导航系统，嵌入到 每个传感器节点是不切实际的，不符合节点资源有限、小体积、低成本的要求。另 外，g p s 因需要与卫星视距通信决定了不能正常工作在内室环境，而传感器网络通 常是工作无人涉足的室外环境。因为受外部因素，如风力、动物或人类的作用，传 感器节点的位置是动态变化的，即使用手持设备也是行不通的。因此，无线传感器 网络定位技术要求不需要任何额外的硬件、较低的计算和通信复杂度。 如何设计出适合传感器网络自身特点的，简单精确、能量高效、分布式可扩展 的节点定位算法，已成为近年来国内外学术界研究讨论的热点。 2 硕士学位论文 m a s t e r st h e $ 1 s 1 2 国内外研究现状 定位技术作为传感器网络应用的支撑技术之一，同样引起了各国研究学者的关 注。研究人员从不同的学科，如嵌入式技术、信号处理、计算机科学与系统工程等 进行深入研讨，已有一些解决方案被提出，部分成果已在实际工程系统中使用。 这些传感器网络自定位算法和系统的研究大致经历了两个阶段：第一阶段主要 偏重于紧密耦合型和基于基础设施的定位系统，其中比较有代表性的定位系统有 a c t i v eb a d g e 系统【6 1 ，a c t i v eo f f i c e 系统 t i ，r a d a r 系统i s ，s p o t o n l 9 1 等。 a t & tc a m b r i d g e 的a c t i v eb a d g e 系统是最早的室内定位系统，它是为大楼内 定位以房间为单位而设计的便携式定位系统，一些红外线传感器节点通过以太网连 接而组成网络，分布在建筑物内。a c t i v eo f f i c e 系统使用了超声波测距技术，优化 了b a d g e 系统，提供了比b a d g e 更精确的定位功能。但是，a c t i v e0 伍c e 系统同样 存在着布置代价和总体成本高、可扩展性差的缺点。r a d a r 系统是微软研究小组 基于i e e e8 0 2 1 1 无线网络技术设计的一种基于射频的室内定位系统。在r a d a r 系统中采用了情景分析技术。虽然r a d a r 系统在试验环境中表现出良好的特性， 但是该技术受到现实环境中的障碍物、温度、传播模式等条件的制约，往往不容易 实现。 第二阶段主要关注对于松散耦合型和无需基础设施的定位系统和算法，也是目 前研究的热点，代表性的研究成果包括c r i c k e t 系统【l 们，a h l o s 系统【l ， s p a ( s e l f - p o s i t i o n i n ga l g 耐也l n ) 相对定位算法【1 2 】，a p s ( a d - h o cp o s i t i o n i n gs y s t e m ) 【b 1 4 1 ，通用型定位算法( g e n e r i cl o c a l i z e da l g o r i t h m ) t ”j 等。 为了弥补紧密耦合定位系统的不足，麻省理工学院的o x y g e n 项目开发了最早 的松散耦合定位系统c r i c k e t 系统。它也是基于分布在建筑物天花板上的锚节点， 定期发送射频信号，而目标也携带信号收发器，从而来确定目标在建筑物内的具体 房间位置。a h l o s 系统采用了一种迭代多边定位的思路，普通节点一旦估计出自身 位置，那么这些节点就像锚节点一样，也可以在多边定位法中充当锚节点来使用。 该算法对锚节点密度要求高，而且迭代过程中存在误差累积，不适用于大规模的传 感器网络。 目前，国内对传感器网络定位技术的研究才刚刚起步，王永才等人在m i c a 2 系 统上，研究利用电磁波与声波传播时间差t d o a 测距技术实现测距，然后通过几何 关系实现传感器节点自身定位。王福豹【1 7 l 基于对近几年有代表性的系统和算法的原 理和特点的分析，介绍了它们的分类和性能评价标准，并提出了未来的研方向。孙 硕士学位论文 ，幢a s t e r st h e s i s 学斌等人【18 】利用监测目标邻居节点间的消息，跟踪目标的行动踪迹，属于w s n 中 的目标定位算法。 虽然有些定位系统和算法在某种程度上解决一些实际问题，但是，在现有的解 决方案中，大多数算法不能同时考虑功耗、成本、复杂度和容错能力。一些技术和 算法通常仅针对某类应用，对于不同的环境要求等提出的各种定位解决方案，在相 对理想化的条件下能达到令人满意的效果，尤其是我国在定位领域内的研究还不 多，真正能够应用到实际中的还比较少。因此，该领域还有很大的发展空间，有待 我们进一步的去探索，以使无线传感器网络能够为人类的实际生活带来更好的服 务。 1 3 论文研究内容 在传感器网络中，节点自身定位是一个至关重要的问题，因为很多无线传感器 网络的具体应用都要以传感器节点的位置信息为前提，是大多数应用的基础，因此 无线传感器网络节点自身定位问题的研究极具理论意义和应用价值。 本文详细的对现有的无线传感器网络自身定位系统和算法进行了归纳和总结， 期望能为后续的研究提供有益的参考。传感器网络节点定位通常会受到锚节点成本 高数量有限而无法高密均匀分布的限制( 称为锚节点稀疏问题) 。本文在对现有的 e u c l i d e a n 定位算法研究的基础上，针对e u c l i d e a n 算法中定位精度及覆盖率受锚节 点密度影响较大的问题，提出了一种改进的分布式节点自定位算法。该算法将初始 定位精度较高的节点升级为锚节点，这些升级的锚节点和其它初始配置的锚节点视 为一样，未知节点根据更新的锚节点位置信息循环求精，并通过估计坐标值的方差 来控制循环求精过程中的循环次数。 另外，我们以支持向量机( s v m ) 理论为基础，建立基于s v m 的定位模型， 定位过程中只通过未知节点距锚节点的跳数信息，而不需要测距信息，建立分类二 叉树，将未知节点的位置确定在一定范围内，降低了网络部署条件对定位性能的影 响，有效减轻了因网络部署条件产生的覆盖漏洞和边缘问题。 1 4 论文章节结构 本论文的工作是围绕w s n 节点自定位算法这一崭新课题进行的，论文的章节 结构安排如下： 第一章主要介绍了无线传感器网络节点自定位技术的研究背景及意义、国内外 的研究现状，简述了本文的研究内容； 4 硕士学位论文 h i a s t e r st h e s i s 第二章集中讨论了无线传感器网络定位过程中所需的数学原理和技术，以及定 位的特点，自定位系统和算法的分类情况，在此基础上，对以前的和最近的几种典 型的定位算法进行了分析和总结，最后给出了常用的节点定位算法性能评价标准。 在第三章中，我们重点讨论了锚节点密度对定位性能的影响，提出了一种锚节 点稀疏的传感器网络节点自定位算法，并对其进行了仿真验证，对性能进行了评估。 本文第四章，我们详细介绍了支持向量机( s v m ) 原理，在此基础上建立了传感 器网络节点自定位算法，并将该算法与经典的d v - h o p 定位算法进行了仿真比较。 第五章是总结与展望，对本论文的研究工作进行总结，对于其中存在的不足， 在展望今后进一步的研究工作中提出一些建议。 5 硕士学位论文 m a s t e r st h e s i s 第二章无线传感器网络节点自定位技术 传感器节点定位是无线传感器网络布置完成后面临的主要问题之一。传感器节 点分为锚节点和未知节点，锚节点已知自身的位置，是未知节点定位的参考点。所 谓定位就是指一组未知节点，通过估计至邻居锚节点的距离或邻居锚节点的数目， 利用节点间交换的信息，确定每个未知节点位置的机制。 2 1 传感器节点定位技术简介 2 1 1 节点间距离或角度的测量方法 目前节点定位的定位过程包括三种形式：第一种是，未知节点首先需要获得到 多个( 至少三个) 锚节点的距离，或者与邻近的锚节点的相对角度信息，然后使用 某种数学计算方法计算出自身的物理位置坐标。第二种是，根据网络的连通性，比 如网络连通度、节点连通度或未知节点距离锚节点的跳数等信息实现节点的自身定 位。第三种是场景分析，比如通过分析照片推断出位置并定位，这种方式需要事先 对系统进行专i 了的配置，且可以离线测量，但分析图片的过程要求很大的计算量， 并不适合无线传感器网络。 在无线传感器网络中，通常用的有l 峪s i ，t o a ，t d o a 和a o a 等技术来测量 节点间距离或角度。 ( 1 ) 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 ，接收信号强度指示) ：一个节点在 接收一条信息时可测量接收信号的功率，通过功率和距离的关系可转化为节点间的 距离。已知发射功率，在接收节点测量接收功率，路径损失系数为f ，接收 方可使用信号传播模型将传播损耗转化为距离d ，如式( 2 1 ) ，根据实际定位过程 中使用的是理论或经验的信号传播模型不同，公式会有所变化。 p矿 = c 等d = d 挚 ( 2 1 ) ” y1 研 该技术主要使用r f ( 射频) 信号，实现简单，不需要额外的硬件和数据交换， 符合低成本、低功率的要求，已经被广泛采用。不足之处是现实环境中的多径传播、 天线增益、非视距、反射等问题都会引起接收端产生严重的测量误差，因此精度较 低，r s s i 产生的测量误差可达到5 0 。 ( 2 ) t o a ( t u n eo fa r r i v a l ，到达时间) ：该技术通过测量信号( 通常是超声波 6 硕士学位论文 m a s t e r st h e s i s u v 或射频信号r f ) 的传播时间来测量距离。如图2 1 所示，假设发送方和接收方 都知道信号传输的开始时间t o ，接收节点接收到信号时间为r j ，则信号传播时间为 n t o ，超声波的传播速度为1 ，则锚节点到未知节点的距离为d = ( t t t o ) x v 发射点 距离 接收点 图2 1t o a 示意图 t o a 要求节点有非常精确的时钟，以获得可以接受的估计精度。在无线传感器 网络中，节点间的距离较小，采用t o a 测距难度较大，同时节点硬件尺寸、价格 和功耗的限制也决定了t o a 技术很难应用于松散耦合定位系统。 ( 3 ) t d o a ( t t m ed i f f e r e n e eo na r r i v a l ，到达时间差) ：为了避免外在的同步要 求，t d o a 利用了内部的同步，这个同步就是信号传输开始的瞬间。发射节点通常 同时发射无线电波信号和超声波信号两种不同传播速度的无线信号，如图2 2 所示， 由于无线电波以光速传播，比超声波的传播速度快的多，因而可以忽略无线电波的 传播时间，所以接收节点根据两种信号到达的时间差以及信号传播速度，计算两个 节点之间的距离：d = ( t 2 o ) v 2 发射点 距离d 接收点 图2 - 2 t d o a 示意图 7 ， f 硕士学位论文 m a s t e r s 下h e s i s 天线阵列来得到相邻锚节点发送信号的到达方向，从而构成一根从接收节点到发射 节点的方位线，两根方位线的交点即为未知节点的位置。 发射点1发射点3 发射点2 图2 3a o a 示意图 该测量方法的硬件系统设备复杂，测量精度也受外界环境影响，需要两节点之 间存在视距( l o s ) 传输。 以上四种测距技术都有一定的优点和不足之处，综合成本和测量精确度考虑， 其中的r s s i 和t d o a 两种方法最为常用，可见于以下的定位系统和算法。 2 1 2 节点位置计算方法 在传感器节点自定位系统和算法中，当未知节点估计出到邻近锚节点的距离或 角度，并满足节点计算条件，就可以计算出未知节点自身的位置。目前已知的结合 距离或角度的节点定位计算方法包括：三边测量法，最大似然估计法，三角测量法。 ( 1 ) 三边测量法：测边是无线传感器网络定位中应用最为广泛的方法，假设 在二维空间中，当已知一个未知节点到三个锚节点的估计距离，则可使用此方法。 这个简单的方法是利用以三个锚节点为中心的圆交点作为未知节点的位置。如图 2 4 所示： 图2 - 4 三边测量法示意图 图中已知彳、雪、c 三个锚节点坐标分别为瓴，乃) 、瓴，躬) 、瓴，乃) ，他们到 3 硕士学位论文 l a s t e r st h e s i s 未知节点的距离分别为d t ，卢1 ，2 ，3 ，假设未知节点坐标为 ，力。根据毕达哥拉 斯( p y t h a g o r a s ) 定理，下列方程组成立： 侄 而) 2 + c y x 2 ) 2 + 0 ， 乜) 2 + o x l = 1 2 ( x t - x , 。j 翌刿q 嚣：要二搿二羽 亿3 ， 分别为瓴，y 。) 、0 2 ，y 2 ) 、纯，乃) ，( t ，儿) 。他们到未知节点d 的距离分别 i o 一) 2 + o - y 0 2 = 砰 ； ( 2 4 ) l ( x - - x 。) 2 + ( ) ，二y 。) 2 = 露 l 砰一t 一2 “一冷+ 订一z 一2 ( m 一只) y = 砰一刃 i( 2 5 ) 【矗一一2 ( x 纠一矗) x 2 一z - 2 0 , 。q - y 。) y = 船一西 彳仨篡甜x 协- l 纛2 2 2 篡22 2 2 0 , 2 l - 2 ( 确一)州一儿) j l 叫 1 矗一+ y q z + 刃一既i 即选择一个伍y ) 使得i l 魃一6 1 1 2 最小，等价于最小化均方误差，得到： 9 幻2 砰霹霹 = = = r 小p 一 一 硕士学位论文 m a s t e r st h e s i s 2 - - ( a r 么) 一1 a r b 。 a 2 a 1 图2 5 最大似然估计定位示意图 ( 3 ) 三角测量法：也称为信号到达角度( a o a ) 定位法或方位测量定位法。 这里的角度是锚节点和位置未知节点的连线与参考线形成的角度( 正比方向为o 。) ，利用方向性天线或天线阵列来获得角度值，从而实现定位。假设在二维平面 中，通过三个或更多a o a 角度测量值，即可计算出未知节点的估计坐标。如图2 。6 所示： 图2 - 6 三角测量法示意图 已知彳、曰、c 三个节点的坐标分别为( 而，y 1 ) 、( x 2 , y 2 ) 、0 3 ，y 3 ) ，节点彳、丑、 c 到节点d 的角度分别为么 a d b ，二a d c ，b d c ，假设节点d 的坐标为似力。 对于节点彳、c 和_ a d c ，确定圆心为o l ( x 。l ，y 。1 ) ，半径为，j 的圆，a = 一a 0 1 c ， 则： ( x o l - x 1 ) 2 + 帆一乃) 2 = 2 ( z 们一工2 ) 2 + 0 ，o i y 2 ) 2 - 4 ( 2 7 ) ( x - x 3 ) 2 + ( y 一乃) 2 = 2 1 1 2 2 1 2 c o s 口 由式( 2 7 ) 能够确定圆心仍点的坐标和半径力。同理彳、b 、一a d b 和曰、c 、 z b d c 分别确定相应的圆心仍k 2 ，儿2 ) ，半径心，圆心0 3 ( x 0 3 ，y 0 3 ) ，半径乃。最 后利用三边测量法，由点d ( x ，力，o t ( x o i ，y 。) ，仍o 。：，y 。2 ) ，d 3 瓴，y 0 3 ) 确定节点 d 的坐标。 1 0 2 2 自定位系统和算法的分类 ( 1 ) 绝对定位与相对定位【2 1 1 。绝对定位的定位结果是一个绝对坐标值，并且 可以嵌入到某些参考体系中。而相对定位中通常是以某些节点为参考点建立的一个 相对坐标系统，节点间的相对位置是正确的，但这个相对坐标与绝对坐标之间没有 关系。绝对定位对所有目标都是有效的，受节点移动性影响较小，有更广泛的应用 领域。但研究发现网，一些基于相对定位的地理位置的路由，也能够实现部分路由 协议，而且相对定位能够区分网络内的任何节点，不需要锚节点。典型的相对定位 算法和系统有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 ) 1 2 1 ，l p s o o c a lp o s i t i o n i n gs y s t e m ) 【1 9 】，当 网络配置的不同时，m d s m a p 定位算法1 2 0 】可以分别实现两种定位。 ( 2 ) 分布式计算与集中式计算。根据定位计算模式来分，即是由每个节点自 身完成还是把数据报告给中心基站，由基站计算并发布给各个节点。分布式计算是 指每个节点都要参与定位计算，换句话说，所有节点自行计算自身位置；在集中式 计算模式中，所有测距信息都要集中到某个基站，在那里进行节点定位计算，并把 结果返回给每个节点。 集中式计算的优点是它从全局的角度统筹规划，计算量和存储量几乎没有限 制，从而可以获得精确度较高的位置估算。它的缺点是因所有数据都要在中心节点 进行处理，其附近的节点会因转发数据而有过大的通信开销，则会过早地消耗完电 能，另外，各个节点可能不愿意把自身位置暴露给中心基站。集中式定位算法包括 m d s m a p 2 0 ，凸规划口1 1 等，n h o pm u l t i l a t e r a f i o np r i m i t i v e t z z l 定位算法可以根据 应用需求采用两种不同的计算模式。 ( 3 ) 紧密耦合与松散耦合。在紧密耦合定位系统中，锚节点需要事先由人工 部署在特定的地方，而且还要通过有线的方式与中心控制器相连接；但是，在松散 耦合型定位系统中，传感器节点通过无线方式通信，不存在中心控制器，所以所有 节点采用分布式协作方式实现定位。 紧密耦合型是无线传感器网络定位发展过程中的第一阶段定位系统的特征，比 较适用于室内环境，它的优点是具有较低的延时和较高的精确性，在这种定位环境 中，对于高要求的时间同步相对比较容易达到，但由于这种部署方式的限制，系统 的可扩展性严重受到影响，因而无法应用于人类无法涉足的室外恶劣环境中。作为 传感器节点自定位发展的第二阶段的特征松散耦合型，这种解决方案的提出， 弥补了紧密耦合的不足，无线传感器网络以a d h o e 方式部署，具有很大的灵活性， 节点间可在自己的通信范围内与其它节点进行数据交换，进而实现定位，但这是以 硕士学位论丈 m a s t e r 。st h e s i s 牺牲定位的精确性为代价的。 ( 4 ) 基于测距技术( r a n g e b a s e d ) 的定位与无须测距技术( r a n g e f r e e ) 的定 位。在r a n g e b a s e d 定位过程中需要位置未知的节点到锚节点的距离信息或者角度， 而这些信息必须通过测量设备或测量技术测量所得，在获得距离或角度信息后，便 可使用前面所述的未知节点位置计算方法来估算节点自身位置坐标；在r a n g e - f l e a 定位过程中，一种情况是无需距离和角度信息，仅通过网络连通性估算未知节点的 坐标；另一种情况是所需的距离和角度信息仅根据节点间的估计距离或跳数来估算 得出，不需要测距设备的支持而实现节点定位。 r a n g e b a s e d 定位机制虽然有比较好的定位精度，但传感器节点通常需要额外的 硬件设备，增加了网络成本和能量消耗，并不适用于低功耗、低成本的大规模传感 器网络应用领域。实际的应用经验说明，粗精度定位已能够满足大多数应用要求( 当 定位误差小于传感器节点无线通信半径的4 0 时，定位误差对基于地理位置的路由 协议的性能和目标追踪精确度的影响不是很大t 2 9 1 ) 。 ( 5 ) 基于锚节点与无需锚节点。基于锚节点算法是通过占有很小比例的锚节 点来实现定位的，这些锚节点通常是通过人工部署或自带g p s 设备而知道自身位 置，然后他们向其邻居节点广播自身位置信息，目的是让未知节点充分利用这些信 息估计自身位置。基于锚节点算法通常会产生一个绝对定位系统，但节点定位精度 深受锚节点数目多少以及锚节点在网络中分布的影响，另外，这种算法还存在网络 扩展性的问题。无需锚节点算法不需要节点位置的任何假设，在这种情况下，建立 了一组参考节点的相对坐标系统，而不是绝对坐标系统，但在坐标信息充分时，这 个相对坐标系统可以转化为绝对坐标系统。无需锚节点算法的缺点是当参考节点位 置发生变化时，其它所有节点的坐标均需重新计算。 2 3 典型的自定位算法 2 3 1 凸规划定位算法 凸规划算法【2 1 1 是一种集中式的无需测距技术的定位算法，如果一个节点在另一 节点的通信半径内，那么他们之间便存在凸约束，这些约束条件就限定了未知节点 的位置范围。如图2 _ 4 所示，图中阴影部分表示未知节点可能存在的区域，阴影部 分所在的矩形区域是由节点和锚节点之间的通信性得到的，然后以矩形的质心作为 未知节点的估计位置。 1 2 硕士学位论文 m a s t e r st h e s i s 图2 _ 4 凸规划算法示意图 凸规划算法完全基于基于网络连通性，计算比较简单、容易实现，但有一个很 严重的问题是凸约束优化完全由一个中心节点计算，能量消耗过大，因此，不适合 许多a d h o e 节点装置。文献【3 0 】对凸规划算法进行了相关的改进，提出了将一个节 点不在另一节点的通信射程内，即它们之间不能直接通信，也可以作为节点位置约 束的思想来提高定位精度。 2 3 2a p s 定位算法 d r a g o sn i c u l e s c u 等人提出了一系列分布式定位算法，合称为a p s ( a dh o e p o s i t i o n i n gs y s t e m ) 1 3 , 1 4 】，又称为距离向量算法。a p s 定位算法属于基于锚节点算法， 利用距离矢量路由思想，一个锚节点通过一些传播方法向网络洪泛广播自身位置信 息，并由锚节点计算出平均每跳距离长度，然后广播至网络中，每个节点既可收到 距离一些锚节点的最少跳数，跳数可以转化为到锚节点的距离，从而计算出自身位 置坐标。本文只讨论其中的四种算法。 ( 1 ) d v - h o p 定位算法 d v - h o p ( d i s t a n c ev e c t o r - h o p ) 距离向量跳段算法，是a p s 系列算法中最基本 的机制，并首次采用了典型的距离矢量交换协议，使网络中所有未知节点获得与锚 节点相隔的跳数和距离。每个节点都包含一个表 咒蚝 ，) ，并和它的邻居节点交换 更新信息，一旦一个锚节点获得与其它锚节点的距离，则估算网络平均每跳距离 一，。i ! 。： ( 而一) 2 + 一乃) 2 ，盔h 槲。= 兰_ ，节一，其中( x i , v i ) t x t 纠v l 、( 颤彩) 是锚节点f 、j 4 喇叠a 蛐= 弋f ；- 一，哭中 、l 习刃，定馏1 尽l 、 l h j j 的坐标，j ! ，是f 与，之间的跳数，然后将其作为一个校正值以可控洪泛法广播至网 络中。当任一未知节点接收到校正值之后，根据已知到锚节点的跳数可计算出与这 个锚节点的距离。当未知节点获得与3 个或更多锚节点的距离时，则利用三边测量 法或极大似然估计法定位。 1 3 硕士学位论文 m a s t e r st h e s i s 如图2 5 所示，通过上述的第一阶段和第二阶段，可知锚节点z 2 与锚节点三j 之间的跳数是2 ，距离是4 0 m ，与锚节点3 之间的跳数5 ，距离是7 5 m 。则2 可 以估算平均每跳距离( 4 0 + 7 5 ) ( 2 + 5 ) = 1 6 4 2 。同理，三移三3 也分别可估算出平均每 跳距离，假设a 从距自己最近的锚节点三2 获得校正值，则它与不在同一直线的三1 、 2 、五3 三个锚节点之间的距离分别为3 x 1 6 4 2 ，2 x 1 6 4 2 ，3 x 1 6 4 2 ，然后使用三边 测量法估算节点么的位置。 图2 5d v - h o p 定位算法示意图 d v - h o p 算法传播机制的优点是实现简单，并且不需要要测距设备，不受测距 误差的影响。其缺点是只能在各向同性的均匀网络中，锚节点估算的平均每条距离 才比较合理，否则，校正值是存在一定的误差的。 ( 2 ) d v - d i s t a n c e 定位算法 d w i s t a l c a g ( d i s t a n c ev e c t o r - d i s t a n c e ) 距离向量距离算法与d v - h o p 类似，但 未知节点问的距离不再是通过跳数来获得，而是相邻节点使用r s s i ( 接收信号强度 指示) 测量节点间的距离。作为一个度量值，距离矢量算法使用累计每跳的距离， 一方面，比粗粒度算法d v - h o p 定位精度要高，因为不是所有的每跳距离都是一样 的，但另一方面i 这种算法对测距误差比较敏感。 在各向同性的密集网络中，d v - d i s t a n c e 算法的性能表现良好，在不均匀网络中， 将与各个锚节点的距离简单的累加起来作为与锚节点的直线距离，存在一定的误 差。 ( 3 ) e u c l i d e 锄定位算法 e u c l i d e a n 定位算法中使用的是与锚节点真实的欧几里德距离，每个节点拥有 r s s i 测距能力，所以这种方法最接近全球定位系统的性质。任一节点a 需要至少 两个邻居节点b 、c 才能估算与相隔两跳的锚节点工的距离。如图2 6 所示，a 通 过r s s i 技术测得距节点晚c 在的距离a b 。a c 以及b c 的距离也已知。对于四 边形a b c l ，所有边长和一条对角线b c 已知，根据三角形的性质可以计算出a l 的长度，即未知节点a 与锚节点l 的欧几里德距离。使用这种方法，当未知节点获 1 4 得与3 个或更多锚节点之间的距离后可实现自身定位。 图2 6e u c l i d e a n 算法示意图 由于在e u c l i d e a n 算法中节点只根据局部拓扑( 两跳通信范围) 实现自身定位， 所以在各向异性的网络中依然可以提供较好的准确性，在定位性能和通信成本方面 也更有优势，但受节点密度和锚节点密度的影响。 ( 4 ) d v - c o o r d i n a t e 定位算法 这个方法要求在d v 传播启动前一定的处理阶段已完成，首先，如果一个节点 获取了类似e u c l i d e a n 算法中的两跳信息，那么这个节点就可以建立一个以自身为 原点的局部坐标系统，下一个处理步骤是登记邻居节点，并将他们的坐标转化到自 己的坐标系统中，在d v 传播阶段，取代传播实际的欧几里德距离，而传播在发送 节点坐标系统里指定的两个锚节点坐标，节点在收到多个锚节点坐标信息后将自己 的坐标全局化。 d v - c , o o r d i n a t e 算法与e u c l i d e a n 算法一