（计算机应用技术专业论文）无线传感器网络中分布式定位算法的研究与实现.pdf

北京邮电大学硕士研究生学位论文 致谢 图表目录 图二1 三角定位的几何解释。 图3 11 e r i 渔矾算法的伪代码 图3 2t e 融认玳算法 图3 3a b c 和i e 砌h 锄算法。 2 1 2 2 图3 4 普通节点上运行算法的伪代码。2 4 图3 5 矩形约束区域2 8 图3 6 弱连接节点。 图3 7 定位算法中用到的消息包及相应数据格式3 1 图3 8 觚c h o r o 算法实现3 2 图3 - 9n c w 锄c h o r o 算法实现3 2 图3 1 0 吼k n o w n 0 算法实现3 3 图3 1 1u p d a t e _ n e i g h b o r o 算法实现3 3 图3 1 2h o p _ b a s c dt r i 柚g u l a t i o n o 算法实现3 4 图3 一1 3d 吡i r i 姐g l i l a t i o n o 算法实现3 5 图3 1 4 n da n c h o r o 算法实现3 6 图3 1 5 n d _ p o s i t i o n o 算法实现3 6 图5 1 建立算法后位置估值的平均误差。4 5 图5 - 2 求精算法后位置估值的平均误差4 5 图5 3 定位节点的比率4 6 图5 _ 4 测距值敏感度4 7 图5 5 凸网络结构4 9 表4 1 建立阶段和求精阶段算法的能耗表达4 l 表4 2 简化的建立阶段和求精阶段算法的能耗表达4 1 北京邮电大学硕士研究生学位论文 独仓q 性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 扭怪日期：2 盟 ：至：墨f 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 翅怪日期：2 鲤f ：羔：翌! 导师签名：垒乞堕毖日期： 兰竺2 ：型： 北京邮电大学硕士研究生学位论文 无线传感器网络中分布式定位算法的研究与实现 摘要 许多无线传感器网络的协议和应用都需要知道网络中节点的地 理位置。节点随机部署的传感器网络具有与a d 咱o c 网络类似的特点， 其分布式和高自由度的网络环境对定位算法提出了很高的要求。由于 能量，代价，或视野条件等因素，我们不可能为网络中的每个节点装 配g p s 设备。在这种情况下，如何依靠少量配有自定位设备的节点来 确定全网中每个节点的位置就显得尤为重要。 无线传感器网络中定位有两个主要的挑战：锚节点稀疏和测距误 差问题。利用冗余和超解方程组可减少测距值的误差对位置估值的影 响，而通过节点间协作和在网络内反复传播信息的分布式算法则可以 有效地解决锚节点稀疏问题。但是并没有一种方法能够同时解决这两 个问题。为此，本文提出了一种分步定位算法：在算法建立阶段，通 过计算到锚节点的扩展距离可以获得节点的初始位置估值；在求精阶 段，利用相邻节点的位置信息来修正和约束位置估值，使之不断逼近 真实值。同时，为了克服单纯求精算法的弊端，引入了信赖度量值和 弱连接节点，进一步改善了求精过程。 论文主要分析对比了两种典型的分布式算法，为了保证算法的稳 定性，选择了基于跳数的d v 咱o p 算法作为建立阶段算法的基础，然 后详细阐述了整个分步( 建立和求精) 算法的设计和具体实现过程， 并从计算复杂度、能耗和时延等方面深入分析了分步算法的代价，并 通过仿真测试验证了算法优异的稳定性和加入求精阶段后对精确度 的提高。最后，文章进一步权衡了几种算法的利弊，讨论存在的问题， 并指出将来可能的工作方向。 关键词：无线传感器网络；定位算法；分步算法；求精算法 北京邮电大学硕士研究生学位论文 d i s t r i b u t e dp o s m o n i n g a l g o r r i i h m sf o r 、7 l r e l e s ss e n s o rn e i i w o r k m a n yw i r e l e s ss e n s o rn e m o r kp r o t o c o l sa n d 印p l i c a t i o n sa s s u m et h e 王【1 1 0 w l e 电eo fg e o g r a p h i cl o c a t i o no fn o d e s t h ea b s o l u t el o c a t i o no f e a c h n e 细o r k e dn o d ei s 狮a s s u m e df a c tb ym o s ts c n s o r m o r k sw h i c h 啪 t h p r e s c n ti h es e n s e di n f o h n a t i o no nag e 0 伊印h i c a lm 印f i i l d i n g l o c a t i o nf o ra l ln o d e si nan e 咐o r kw h e t eo i l l val i m i t e df r a c t i o no fn o d e s h a v es e l fl o c a t i o nc a p a b i l 畸i si m p o n a l l ts i i l c ci ti sn o tp r a c t i c a lt oe q u i p e a c hn o d ew i mg p sd u et op o w e r ，c o s t ，f o mf a c t o ro fl i n eo fs i g l l t c o n d i t i o n w i r e l e s ss e n s o rn e t w o r k s ，w h e r et h en o d e sa r cf a n d o m l y d 印l o y e d ，r e s e m b l ea i la d h o cn e t 、) l ，o r ke n v i r o n m e n tw i mh i g hd e g r e e so f f r e e d o ma n dd i s t m u t e dc o m p o s i t i o n ，a i i dm u sp o s es i 萨i f i c a i l lc h a l l e n g e s o np o s i t i o n i n ga l g 耐t h m s t 1 l e r ea r ct w om a j o rc l a s s e so fp r o b l e m st h a tm a k ep o s i t i o n i n g w i m i i la nw i r e l e s ss e n s o rn e t w o r kc h a l l e n g i n g ：t h er a n g ee r r o fp r o b l e m ， a n dt h es p a f s ea n c h o rn o d ep r o b l e m w bc a na i l s w e fm er a n g ee h o r p m b l e mw i t hr e d u n d a n c ya n do v e 卜d e t e n n i n e ds y s t e m so fe q u a t i o n s t h e d i s t r i b u t e da l g o r i t h m ，w h i c hw o r i ( st h r o u 曲c o l l a b o r a t i o n sb e t 、) l ，e e nn o d e s 锄di t e r a t i v ed e l i v e 巧o fm e s s a g ea c r o s st h en e t 、7 l ，o r k ，p r o v i d e sac l e a n s o l u t i o nt ot h es p a r s ea n c h o rn o d ep r o b k m n ed i f e i c l l l t y ，h o w e v e r ，i s t h a tn e i t h e rs o l u t i o nw o r k si nm ep r e s e n c c0 fb o t hp r o b l e m s ，b e c 卸s c r e d u n d a n c yc a l l sf o rh i g hd e n s i t y t ba n s w e rt h eo r m o g o n a l i t yo ft h e s e 4 北京邮电大学硕士研究生学位论文 t w os 印盯a t e 弛d n n i c t i n gs o l u d o n s ，at w o - s t a g ea 1 9 0 r i t l l mi sp r o p o s c d a tt h es t a n i n gp h 舔e ，w ec o m p u t em ee x t e n d e dr 蛐g c st ot h e 锄c h o rn o d e 髂t 0d e r i v et h ei n i t i a l 髓t i m a t c dp o s i t i o n ；a tt h em f i n e m e n tp h 雒e ，t h c 0 0 n s t r a i n t s 咖o db yt h e 拙t a l l c e st 0 也cd i 删( o - h o p ) 舱i g t l b o 瑙o f an o d ew mf o f c et h en e wp o s i t i o nt o w a f d sm ct n i ep o s i t i o na f t e ra m m l b e ro fr c 细e m e n ti t c r a t i o n s t bo v e r o o m et h e 确，oi m p o r t 孤t l i l n i t a t i o n so ft h ep u mr e 缅e m e n ta 1 9 0 r i t h 王n ，w ei n t r o d u c ct h ec o n c c p to f 鲫i f i d c em e t r i 娼姐di l l c 0 衄e c t e dn o d c s 幻i m p r o v et h e 北矗n e m e n t p r o c e s s f i r s t ，t h ep a p e ra n a l y s e sa n dc o r n p a r c s 鲥ot y p i c a l d i s t d b u t e d a l g o r i t h 脚t o s u r et h ec 0 鹪i s t e n c yo ft h ca l g o d t h 瞄，w ed e v e l o p e da h o p - b a s e dd i s t f i b u t e dp o s i t i o n i n gm e t h o df o rt h es t a n i n gp h a s eb a s e do n t h ea l g o r i t h md v - h o p t h e nt h ep 印e rc x p l a i r l si nd e t a nt t 圮d e s i 弘a n d i m p l e m e n t a t i o no ft h ew h o l et 、】l r o - p h a s ea l g o r i t h m f u n h e r t h ep a p e ra l a n a l y z e st h ec o s tf b ri m p l e m e n t i n gt h ea l g o r i t h mi nt e m so fc o m p u t a t i o n ， p o w e l a n dt i m e e x p e r i m e n t a t i o ni st h e np e d o 姗e d t 0 v e r 晦t h e c o n s i s t c ya n de n l l a n c e da o a r a c ) ro f t h ea l g o r i t i l l l 娼a 舭ri n t r o d u c i n gt t l e r e 矗n e m e n tp h a i nt h ee n d ，、cw i l ld i s c l i 鼹t h ea l g o r i t h m s am o r e q u a l i t a t i v el e v e l ，l o o i 【i n g a tt h et r a d e o f eb e t w e e nv a r i o u sa l g o r i 岫n s ， p o s s i b l e u r 。c so fe 啪r 绷da r e 勰f b ri m p r o v e m e n ta n d 觚r eg r o w t h k e yw o r d s ：砌r c l e s ss e n s o rn e 咖f k s ；p 0 s i t i o n i n ga 1 9 0 r i t i l m ； 锕o p h a s ea l g 耐t l l l n ；r e 6 n e m e n ta l g o r i m m 北京邮电大学硕士研究生学位论文 第一章绪论 1 1 无线传感器网络中定位问题的介绍与分析 无线通信和传感器技术的蓬勃兴起正带来一个全新的计算时代：泛在计算 唧。具备有计算和通信能力的节点集结起一个多方多面的网络，把智能散布到各 种环境下的大片地理区圳”。通过自身的感知、远距离运作，全网范围内数据通 信、以及协作的信息处理和计算，传感器网络的应用项目使许多特别服务成为可 能。智能环境【1 0 】、多样的娱乐应用、以及在自动化和机器人领域其他可能性都是 这一类服务的实例p 】。 无线传感器网络具有分布式的特点，可以非常灵活的获得网络环境中的信 息。这使得无线传感器网络在军事应用、环境科学、医疗健康、空间探索等领域 都具有技术优势i l j 。它可用于监视其部署范围内的一系列环境特征，例如光、温 度、声音等等。这些监测数据大部分有着共同的特点，就是只有在知晓采集它们 的时间和地点的情况下才是有用的【“。因此大部分的传感器数据都带有位置和时 间信息。然而获取位置数据对于无线传感器网络来说是一个很大的挑战。 无线传感器网络对于节点的组成、节点的相对位置、以及网络的运行环境等 尽可能地不做约束。高自由度催生出一大批可能自争开放场景，这对算法的健壮性 提出了很高的要求。要在网络中配置定位系统，并通过锚定于某个三维的全局位 置系统来获取位置信息，需要两个前提。第一，在一个定位算法中所考虑到的所 有节点必须包含在同一个连通的网络中。第二，在这个网络中必须存在至少四个 ( 在三维空间中) 锚节点。这里所说的连通网络指的是到网络中的每个节点都存 在一条可行的路由，并且锚节点事先知晓自己参照某个全局位置系统的位置。 传感器网络的a d h o c 特性导致其缺乏固有的网络架构。除了极少数的情况， 所有的节点都被认为是平等的，使之很难通过依靠集中的计算瞄】来解决全网范围 内的问题，例如定位。在一个非常大规模的由低存储量和低带宽的节点构成的网 络中，即使以多跳的方式将整个网络的拓扑传送给服务器，基站( 服务器) 周围 的节点也承受着过大的负荷。分割的网络区域使集中式定位无法进行，而不断改 变的拓扑也会增加集中式算法的难度。因此，我们将考虑通过多跳路由在网络内 反复地传播信息地分布式算法。这些定位算法依靠测距值来估算相邻节点间的距 离。 8 北京邮电大学硕士研究生学位论文 有几种技术可以用于获得这些测量值，包括到达时间( 1 d a ) 、到达角度 ( a q a ) 、和信号强度( r s s i ) 1 3 】。本文中的算法并不关心使用哪种技术，除了 不同的方法在精确度、复杂度、代价和能量要求方面有着不同的权衡。某些方法 测得的量值会带有相当于测距值5 0 的误差，如果不做处理会导致位置信息完 全无用。这就是在无线传感器网络中定位的两个主要挑战之一，在这篇论文中将 被定义为测距误差问题。 在三维空间中为了独一无二的确定未知目标的位置，至少需要四个位置已知 的参考节点，这就产生了定位算法的第二个主要挑战锚节点稀疏问题。参考节点 太少产生模糊性导致方程组不可解。回忆一下前面说到的前提，在算法开始的时 候只有锚节点带有位置信息，并且这些锚节点随机分布在一个任意范围的网络 中。考虑到无线电发送的有效传播距离，网络中的任一随机选择的节点很难能够 同足够多的参考节点直接通信来推算自身的位置估值。 对应于两类主要的困难，定位算法可以分成两个阶段：建立阶段和求精阶段。 在建立阶段，通过节点间的协作将锚节点的位黄信息传播到全网，这样解决了锚 节点稀疏问题，允许所有的节点都能获得初始位置估值。这些初始值并不期望很 精确，但作为粗略的估值却相当有用。在求精阶段利用建立阶段的结果来提高这 些位置估值的精确度。这时需要解决测距误差问题。 这些算法的最终目标是将可靠的位置估值提供给系统中其他需要使用这些 位置信息的部分，例如应用或路由算法【4 】【5 】【6 】。使用这些定位算法的应用程序 自然希望得到性能稳定的位置估值，因此定位系统应该支持那些提供较为恒定的 适度误差的算法，而不是牺牲恒定性来换取偶时的低误差。同样值得关心的是算 法的代价，以时间和能耗为指标。在这些方面，不同的应用有着不同的需求，因 此一个健壮的定位系统应该包含参数来按需分配任务的优先级，完成任务可用的 总时间，以及与特定算法相关的在时间、精确度、和能量方面的权衡。 这其中的某些应用要求系统必须易于构架且能维持很长的一段时间。例如， 极受关注的智能办公环境就布置有无线传感器网络，能够实时监控并根据温度、 气流、光线和其他因素调节办公环境。为了使之可行，网络必须具有自组织性来 容许合理地简易安装，尽可能地没有层次结构来防止个别节点的无效，还必须低 能耗来满足频繁服务的需要。当然还有其他的要求，而所有的这一系列变数和限 制都影响了定位系统的开发。 9 北京邮电大学硕士研究生学位论文 2 主要工作介绍 正如前面所说，在无线传感器网络中定位有两个主要挑战：测距值误差和锚 节点稀疏问题。针对这两类主要的问题，我们将提出一种分步定位算法。算法分 为建立阶段和求精阶段。在建立阶段，我们依靠节点问的协作和在全网内传播位 置信息来获得到锚节点的扩展距离，以此解决锚节点的稀疏问题。这个阶段将得 到初始位置估值。这个值将作为求精阶段的输入，通过一系列的循环求精将不断 逼近于真实值。求精阶段的主要目的就是通过相邻节点的位置和距离信息来修正 并约束位置估值，以此在网络中抵消测距值带来的误差。主要工作概括如下： 1 ) 介绍了定位算法的基本原理和技术，着重阐述了三角定位的实现。 2 ) 介绍并比较了两种典型的分布式算法：t e r r a 斟和d v - h o p ，为了获得 性能稳定的定位算法，选择基于跳数的d v h o p 作为建立阶段算法的基 础，得到建立阶段的算法h 叩一s t a n 。 3 ) 利用邻居节点的位置信息对前一阶段的位置估值进行求精。为了克服单 纯求精算法的弊端，引入信赖度量值和弱连接节点，优化了求精过程， 进一步提高了算法的性能。 4 ) 详细阐述了算法的整个实现过程，包括建立和求精阶段。介绍了消息包 格式，节点类的实现及其对各种消息的处理过程。 5 ) 深入分析了算法实现的代价，包括计算复杂度，能量代价和时间代价， 并给出各个量的参数化表示。这部分讨论的目的是为了不同应用的具体 需求提供参考指标。 6 ) 对算法进行仿真测试，并分析相关结果。主要比较了将建立阶段算法作 为一个完整的算法，和引入求精阶段之后算法的不同性能。在此基础上， 我们更为定性地权衡了几种算法的利弊，并讨论了在特殊场景下定位系 统存在的问题。 有两类节点将贯穿全文的讨论：普通节点( 或说节点d e ) ，及锚节点( a n c h o f n o d 曲。这两种节点间的区别在于是否带有特殊硬件或预编译的数据来确定一个 全局的参考坐标。普通的节点没有配备这样的能力，而锚节点一开始就知道自己 在某个全局坐标系统中的位置。通过引入g p s 接收器，或硬件编程并固定网络 1 0 北京邮电大学硕士研究生学位论文 中一小部分的节点都可以在网络中部署适量的锚节点。这些锚节点非常有效地将 网络锚定于一个可以为网络外的实体所辨识的参考系统。但我们同时必须注意 到，赋予一个节点事先确定的位置信息意味着增加成本，同时节点的灵活性降低， 因此我们期望锚节点的数量能尽可能的少。另外需要指出的是普通节点在得到位 置估值之前常常被称为未知节点。 位置估值的误差大小将会是本文关注的重点。具体数字将表示为百分比的误 差，归一化为r ( r 表示节点广播半径) ，是节点的真实位置与估算位置之间距离 大小的度量。真实位置是节点在全局坐标系中的绝对物理位置，而估算位置则是 该节点感知到的位置值，或者说是通过定位算法对节点的真实位置所能作出的最 佳猜测。因此2 5 的位置误差意味着由一个由全知的观察者所看的位置和由算 法推导出的节点位置间有着o 2 5 r 个单位的几何距离。 1 3 本文的章节安排 本文的论述围绕无线传感器网络中对节点定位的几种算法展开，在分析了它 们的利弊之后提出了一种改进了的两步定位算法。我们假设已有其他的子系统能 够提供测距值，作为这些算法的输入数据，并且这些距离值都将带有与之相关的 随机误差分布。文中讨论的算法使用这些测距值来推算网络中每个节点的位置 值，然后把得到的坐标提供给系统的其余部分。我们并不关心得到测距值所需克 服的种种挑战和困难，也不具体了解从定位系统输出的坐标值的目的用途。这些 问题我们将从抽象概念层面的高度上浅涉辄止，因为我们的重点是在得到测距值 后，获得位置估值的过程。 第二章将介绍无线传感器网络中定位问题研究的背景，基本理论和技术，这 是接下来所有讨论的基础。这章将涉及一般性的三角定位理论，测距技术，和其 他相关的工作。第三章将阐述能够满足传感器网络要求的一种两步定位算法及它 的具体实现。算法是在现有定位算法基础上提出的，目的是针对影响定位的两个 主要问题提供解决方法。第四章将从计算复杂度，能耗和时间等方面对第三章中 介绍的算法进行详细地分析和讨论。第五章将给出算法的仿真结果及相应的分 析。对应直观的数据结果，这一章将更为定性地分析算法的性能，权衡算法的优 缺点，探讨可能的误差源，并提出将来可能的改进工作。最后，第六章将总结这 篇论文。 1 l 北京邮电大学硕士研究生学位论文 第二章定位算法综述 2 1 定位算法的几何解释 位置的整体概念从根本上是取决于一个预定义的参考框架。换句话说，所有 的位置都是相对的。同样地，若不知坐标系统而将一组坐标值分配给某个目标是 不具实际意义的。在本文的讨论中，一个全局的坐标系统的概念是理所当然的存 在的。同时，我们假设存在某个全局坐标系统，而锚节点以之为参考。当然，这 一坐标系统的具体细节与我们将要进行的讨论无甚关系。事实上，这些细节是与 特定的应用相关的。而算法的唯一日标是在已知的全局坐标系统里确定一个节点 的位置。这一过程通过三角定位( 砸粕g i l l a t i 曲) 完成。 t 打a i l g i l l a t i o n 是一种在坐标系统内定位目标的方法，也是这里讨论的算法的 基础。用最通用的解释来说，仃i 锄g l l l a t i 是利用节点间点与点之间的边来定位 的几何技术。在一个二维空间中，与能构成三角形的三个参考点都相关的目标的 位置是可以独一无二地确定的。这些节点间的联结表示为测得的距离和角度。本 文中的算法只考虑到节点间的距离，是三角定位一种具体的实现。通过一个简洁 的例子我们可以直观的理解这种算法。如图2 - 1 所示： 图2 1 ：三角定位的几何解释 图l 显示的是一个二维的空间，其中m 节点的位置未知，它的周围有三个 参考节点a 1 ，a 2 和a 3 。三个参考节点知晓自身的位置。旦m 确定了它到a 1 的距离值r ，m 便可推得它位于以a 1 为圆心，r 为半径的园周上的某点。类似地， 北京邮电大学硕士研究生学位论文 知道了m 和第二个参考节点a 2 间的距离，我们可以作出另一个圆与第一个圆正 好相交于两点。最后，m 与a 3 的关系将为我们引入第三个圆，而理论上这三个 圆将恰好交于一点：m 点所在的位置。当然，这一方法可以很容易扩展到三维空 间的情况，这时我们只需再加入第四个参考节点。我们可以想象一开始第一个参 考节点将确定一个球面。这一球面很快就因第二个参考节点的引入而简化为一个 平面上的圆周，情况又成为了我们己熟悉的二维空间。 2 2 测距技术的介绍 现在的定位算法通常是依赖某种形式的原始度量值。几种较为常见的可用于 得到这些度量值的方法包括到达时间( t o a ) ，到达角度( a o a ) ，和信号强度 ( r s s i ) 。 t o a 依据的是无线电波的传播速率和信号从一个节点传到另一个节点所花 费的时间。结合这两个值，1 b a 系统就可以计算出发送方和接受方之间的距离。 1 o a 有着很高的精度，但要求相对快速的处理能力解决细粒度测量中的时差问 题。对于较短的距离，这个问题就更为突出了。因此对于在无线传感器网络中定 位，t o a 技术并不是一个好选择。 t o a 可以和声波测量相结合来得到只相当于传送半径几个百分值的精度。但 声波信号依赖于温度和角度，需要不受阻挡的视线和额外的硬件配置。这就加大 了定位的开销且不易安放。 不用前面测量距离的技术，a o a 利用天线阵列来测量信号到达的角度。角 度可以和距离估值以及其他的角度量值结合来得到位置。a o a 技术的一个主要 缺陷是所需的硬件。安装和维护天线阵列的代价是很昂贵的，这使得a o a 并不 适用于低成本的应用。 r s s i 测量的是无线电信号从发送端到接受端的衰减。无线信号的强度随着 距离呈指数衰减，接受端可通过测量这衰减率来估算到发送端的距离。不过经验 证明r s s l 会产生很不精确的距离估值。本文中我们假设就是这一方法来为定位 算法提供距离估值。尽管如此，具体的测距技术的选择与文中所论述的定位算法 并没有关系。算法只关心与每种特定的定位技术相关的期望误差分布。 北京邮电大学硕士研究生学位论文 2 3 三角定位的原理 三角定位( 仃i 柚g u l a 嘶n ) 过程起始于一个预测的位置估值，这个值在后面会不 断被校正来逼近真实位置。假设是估测的位置，是真实的位置值，而到信 标节点i 的相应距离分别为：ni 一，ll + 毛和磊叫一乇l + t 。到每个信标 节点的距离为：n 一“一毛) 2 + 饥一咒) 2 。距离的校正值p 使用泰勒展式来 线性近似。如果五是a 的单位向量，五一“一毛) i 一无i 且r 一吒一，= f ，那么校 正值近似为：a p a n 一五r + p 。对每个信标节点都做上述近似，我们得 到线性方程组，其中的未知数是位置校正值廿= 【缸母】： p l p 2 p 3 p 。 k p j 1 ，h ，2 v ，3 ， ： 3h j 。 在每次循环后，校正值缸和每都将应用于当前的位置估值。解线性方程组 可以使用任何的最小二乘解法。下面讨论的算法是以j 姐b c u t e l 【1 习的工作为依据 的。b e u t c l 利用最小二乘法来从许多组的参考节点和相关距离中得出位置估值， 并权衡了多余的参考组( 三组就可以求得唯一解) 的影响来提高误差存在情况下 的位置估值的精确度。 使用n 个参考节点和与之相关的测距值来进行三角定位第一步就是构建如 下的方程组： ( 石l 一“：) 2 + 2 一“z ) 2 + ( 舶一“x ) 2 + ( y l 一蜥) 2 + ( _ ) ，2 一“y ) 2 + 0 。一蜥) 2 + 0 1 一“：) 2 ( z 2 一“：) 2 ( 翻一“：) 2 r 1 2 r 2 2 2 式( 2 - 1 ) 在上面的数据结构中，( ) 【i ，z i ) 是第i 个参考节点的三维坐标，( u x ， u y ，u z ) 是未知节点的坐标，而r i 是位置节点和参考节点问的测距。通过线性 变换，将方程组中的每一行与最后一行相减，再做一些算术移项，我们得到下面 1 4 北京邮电大学硕士研究生学位论文 的关系： 其中： 彳- 一2 + 6 0 l 一舶) 0 2 一赫) 似一i 一赫) 么“一6 ( ) ，i 一弘) ( ) ，2 一弦) ( 弘1 一弘) 圈 o l 一厶) g 2 一厶) ( 翻。l 一厶) ，1 2 一 2 一工1 2 + 赫2 一) ，1 2 + y 2 一z 1 2 + 厶2 r 1 2 一h 2 一x 2 2 + h 2 一y 2 2 + 弘2 一z 2 2 + 厶2 h 1 2 一 2 一赫一1 2 + 赫2 一弘一1 2 + 弘2 一妇一1 2 + 磊2 上面的方程组可以通过传统的最小二乘法【1 3 】来求解。解为： 式( 2 2 ) h 一口) - 1 爿b 式( 2 - 3 ) 正如在上一节所讨论的，二维空间中的三角定位可以通过三个或三个以上的 参考节点来完成。在没有任何误差的情况下，三个参考节点将提供一个完美的位 置解，无需再有额外的参考节点来进行改进。然而，当参考节点的位置值或距离 信息存在误差时，求得的解也会带有意思一定程度的误差。通过增加额外的参考 节点可以减少误差。 还有别的情况同样会带来误差，例如糟糕的几何布局或节点簇集。这里所说 的簇集指的是相对于某个未知节点的参考节点的拓朴。当参考节点均匀地分布于 以未知节点的周围，且到未知节点的距离相似，这种情况下我们能得到最好的结 果。而不好的拓扑例子包括一组参考节点排列成一条直线，或是组里的节点包含 一些相距很远或很近的参考点。 最后还必须说明的是如果两个参考节点离得很近，而系统的计算单位又不是 无限趋近于精确，那么这两个节点的位置信息就会被认为是重复的。因此，当参 北京邮电大学硕士研究生学位论文 考节点的数目不够多时，上述的数据结构在进行求解计算时会导致奇点的产生。 在反复的算法中，经过一段时问的计算，误差累积到一定程度将影响到本应足够 的参考节点，使之严重失衡。这时，就产生了奇点，导致方程不可解。 2 4 相关工作的介绍 近来由h i g h t o w e r 和b 0 r r i e n o 川进行的调查和分类工作让我们总体了解了定 位系统研究现状。然而，在无线传感器网络中对传感器节点进行定位的系统却没 怎么被论述，这是因为测距误差和锚节点稀疏问题很难解决。 一种完全避免测距误差问题的方法是只利用节点间的连接度来推算位置。在 b u l u s ue ta 1 的g p s k s s 系统【1 4 l 中，已知位置的信标节点构成网格；每个位置 待定的节点将自身位置设置为它所连接的信标节点构成图形的质心。定位精度大 约是信标节点间距离的三分之一，这意味着在实际应用中需要很高的信标节点密 度。加州大学伯克利分校的d o h c n y 等人将节点问点到点的通信连接视为节点位 置的几何约束，把整个网络模型化为一个凸集，从而将节点定位问题转化为凸约 束优化问题【1 5 j 。定位精度取决于锚节点所占的比率。例如，在锚节点比率为1 0 的情况下，定位精度与无线信号传播范围在同一个数量级上。而现在提出的一 个凸约束定位的严重缺陷在于算法中的计算集中到一个单独的节点上完成。这会 导致个别节点快速耗尽能量，或节点失效而导致整个算法瘫痪。这点其实也是所 有集中式定位算法的只要缺点。 而由美国路特葛斯大学( r u t g e r su n i v e r s i t y ) 的d m g o sn j c u l e s c i i 等人利用距 离矢量路由( d i s t 柚c ev e d o f 咖t i n g ) 和g p s 定位的原理提出的“d v h o p ”算法 【1 6 】1 1 7 】则是完全a d h o c 的分布式定位算法。对于密集网络，可获得相当于无线信 号传播距离三分之一的定位精度。一开始，锚节点在全网洪泛自己的位置信息。 每个位置未知的节点记录至少三个锚节点的位罨和到它们的最少跳数。当一个锚 节点得到另一个锚节点的位置后，就可以计算它们之间的距离。将距离除以它们 相距的跳数得到每跳平均距离后，将其在全网洪泛。每个需要定位的节点利用这 个每跳均值将距锚节点的跳数转化为距离，当得到三个以上锚节点的距离后便利 用三角定位计算自身的位置。d v h o p 在密集且规则的网络拓扑下工作得很好， 但对于稀疏或不规则网络，定位精度只能达到无线信号的最大传播范围。d v h o p 是本文后面论述的算法的基础，不同的是d v h o p 被认为是一个完整的算 法，而我们将对其的结果提出进一步的求精算法。 1 6 北京邮电大学硕士研究生学位论文 当误差较小时，利用节点间的测距值我们可以获得更为精确的位置信息。当 锚节点的比例很高时，可以使用加州大学洛杉矶分校的a n d 北鹤s a w i d e s 等人开 发的“i t e m t ! i v e 舢l t i l a t c m t i o n 定位算法【堋。至少与三个锚节点连接的节点计算完 自己的位置后就可以上升为锚节点，在进入下一次循环时，帮助其他的未知节点 定位。近来又提出了一系列几乎不需要锚节点的方法【1 9 】【刎【2 1 】吲，这些方法十分 相似，原理如下。节点测算出到它邻居节点的距离，并广播其值。这样，每个节 点都能知道到邻居的距离以及一些邻居之间的距离。如此建立起带有相对位置的 部分局部地图。相邻的局部地图通过调整坐标系统结合起来。而锚节点的已知位 置可以用来获得带有绝对坐标的地图。当网络中有着三个或更多的锚节点时，一 张单独的带有节点绝对位置的地图就产生了。这种方式的定位算法并不很健壮， 因为当结合多个地图时，误差会累积。 1 7 北京邮电大学硕士研究生学位论文 第三章基于跳数的分步定位算法的设计和实现 3 1 分步定位算法的思想 正如本文中的第一章所说的，在无线传感器网络中定位有两类主要的挑战： 测距误差问题和锚节点稀疏问题。利用冗余和超过未知数个数的方程组可以处理 测距误差问题。下面将要介绍的另两种算法( 1 e r r a 小和d v h 叩) 将针对锚 节点稀疏提供直接有效的解决方法。困难在于没有一种方法可以同时解决这两个 问题。 b c u t c l 提出的冗余方法出色地利用来自多余参考节点的额外信息来均衡在 测算距离值时产生的误差。他发现，求解时使用的节点从3 个增加到1 0 个，位 置估值的误差将降为原来的1 4 。不过b c u t e l 的算法假设被定位的节点由许多位 置已知的参考节点所包围。事实上，这类研究所关心的a d h o c 网络面临着锚节 点稀疏问题。这一问题特别强调节点周围并不环绕着其他的位置己知节点。因此， 纯粹的冗余方法是行不通的。 同样地，当给出完全没有误差的测距值时，r e r ra 玳( 或d v 二h o p ) 可解决锚 节点稀疏问题。但当测距值有误差时，它们就无法正常工作了。t e r r a 烈可以 将少数锚节点的信息传播到整个网络，使所有的节点都能获得精确的位置估值。 但它是一个循环算法，快速地重用着信息。因此，任何原始测距值上的误差都会 被重复地累加，并猛增到很大的部分使推算出的最终值完全无用。正如前面提到 的，所有获得原始数据的方法在实际操作中都会带有一些误差。这就是本文中所 论述的距离误差问题，它否定了单纯的t e r r a 玳算法的有效性。 为了结合这两种单独且矛盾的解法，本文提出了一种两步算法，算法分为建 立阶段和求精阶段。在建立阶段，节点以d v h o p 算法为基础，将克服位置信 息稀疏的困难，并得到初始位置估值。我们认为这些初始的位置值很粗糙( 有很 大的误差) ，但作为求精阶段的起始值还是可以信赖的。求精阶段采用这些初始 的位置估值并循环计算提高其精度，在一定时间后得到更精确的解。 3 2 建立阶段的算法h o p - s 协r t 的设计 建立阶段的目的是解决锚节点稀疏问题，忽略在测距值上的误差。这很难做 北京邮电大学硕士研究生学位论文 好，所幸事实上，建立阶段只是负责给出节点位置的粗略估值，以此来得到网络 拓朴的最初近似。这一阶段的算法在两个层面上牺牲精确度来换取一致性。第一， 它选择产生一组有着一致的误差程度的位置估值，而不是一组同时有着非常精确 或非常糟糕值的位置。第二，这一阶段的算法关心其在不同实验和场景下的一致 性。建立算法应该在几乎所有的场景和实验中都能产生大致位于相同级别上的误 差。 这一节我们将研究两种不同的算法：r r a 矾和d v i i o p 。尽管1 1 r r a 被证明结果一致性很差而不予采用，研究它还是很有启发的，尤其是以便为了与 d v h 叩对比。两种算法和它们的结果都将在下面论述。 3 2 1 建立算法一：1 1 弧j 认矾 t e r ra 全称叫做t r i 孤g i i l a t i v i ae x 劬d c dr 孤g ea n dr e d u n d 柚t a 豁0 c i a t e do fi n t e 珊e d i a t cn o d e s 它是a b c 算法【2 l j 的扩展，提供更好的位置估 值。t e r r a 相较于a b c 并未提供足够的改善，因为从r i e 砌认m 得出的位置 值一致性太差。不管怎样，这一节将简要地介绍t e r ra 玳，因为它为我们提供 了获得扩展距离( e x t c n d c dm g e ) 的基本思想和方法，也就是如何估算出自身节 点和它的通信半径以外节点问的距离。这将为下一节要介绍的d v - h o p 提供参考 依据。 a b c 算法使网络位置未知的节点参考相互间的位置来协作定位，但并不考 虑全局的参考系统。换句话说，a b c 可以用于建立一张拓朴正确的地图，而这 张地图参考的坐标系统只能为这一网络中的节点所辨识。相对于任何的全局坐标 系统，这一坐标系统将有着完全随机的轴向。虽然我们可以通过旋转坐标系来解 决坐标轴的取向问题，t e r r a 则是运行于a b c 之上，并通过协作距离修正 ( c 0 0 p e r 砌v cm g i n g ) 方法来将全局定位的挑战转化为许多分布式的局部优化问 题。这种方法正体现了分布式定位的思想，它巧妙地避开了全局资源和全局通信 的需要并能得到误差更小的最终位置估值。 起始，a b c 算法假设n o 位于点( o ，o 0 ) 。第一个与n o 建立通信的节点被认 为是位于( 1 0 1 ，0 ，o ) ，其中r 0 1 是n 0 和n l 之间的距离估值( r s s d 。下一个节点n 2 的位置，便可以由这两个假设很容易地计算出来： ，0 1 2 + ，0 22 + r 1 2 2 x 2 墨一 2 ，0 1 北京邮电大学硕士研究生学位论文 y ：= 石：万 接下来的n 3 节点，基本上采用同n 2 相同的方式计算出来： 从这个节点开始，求解更多节点位置的系统方程组就不再是不足解的了。每 个新节点的位置都可以通过标准算法求得。在理想的条件下，这种算法将生成拓 朴正确，且相对与全局坐标系有着随机轴向的地图。 ，0 1 2 + ，2 + ，1 3 2 ：r 3 = 2 ，们 r 2 一，2 3 2 + x 2 2 + v 2 2 2 x 2 x 3 y 32 i 万一 z ，j 丁j 了 1 1 弧r 气矾利用a b c 算法将每个节点包含到几张独立的地图中；每个锚节 点对应一张地图。当某个节点被数量足够多的地图所包含时，它便能确定自身相 对于全局坐标系统的位置。 网络中的每个锚节点发起a b c 算法，产生a 组独立的坐标系统。每个坐标 系统都锚定于各自对应的锚节点。单从其中的一个锚节点来看，它进行的a