（计算机应用技术专业论文）基于跳数比率的无线传感器网络节点定位技术研究.pdf

中文摘要 节点定位技术是无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ，w s n ) 的主要支 撑技术之一，即根据少数己知位置的节点，按某种定位机制确定自身位置。w s n 中的传感器节点在存储、计算和电池供电等方面的能力有较大的限制，因此在保证 一定定位精度的前提下，研究具有较低的计算复杂度和较低的节点间通信开销的定 位算法，从而减低功耗、延长网络生存时间，对于w s n 的实际大规模应用具有重 要的理论意义和应用价值。 本文首先对w s n 节点定位技术的基本原理、计算方法以及性能评价指标等方 面进行研究总结，分析了现有各类定位算法的基本思想、应用背景及性能。重点对 适用于较大网络规模的d v - h o p 算法进行研究，深入分析了该算法的特点，针对其 通信负载大、节点较少时定位误差大等缺点，提出了一种改进算法。该算法采用网 格型网络拓扑结构，通过设置不同通信范围的主副两级锚节点进行辅助定位，将整 个定位过程分为粗略位置约束和精确计算两阶段：( 1 ) 根据节点接收的信号强度， 利用其与节点间欧氏距离的线性反比关系来缩小定位范围，限制第二阶段中节点通 信的区域，同时为最后的定位结果设置过滤条件；( 2 ) 在缩小的区域内进行一次网 络泛洪来统计节点间最i j , 髟l 数，用跳数比率( h o p c o u n t r a t i o ) 构造a p o l l o n i u s c i r c l e ，最终利用三边测量法和最大似然估计法进行节点定位。 改进后的算法在c r o s s b o w 的m o t e w o r k s2 0f 平台上、使用i r i s 节点对其网 络通信负载、定位精度、边缘稳定性等指标进行了实际对比测试和验证。结果表明， 改进后的定位算法在不增加硬件开销的基础上，与传统的d v - h o p 算法相比，实现 了网络通信负载的大幅降低，定位精度较高且边缘稳定性较好，同时在一定程度上 降低了系统计算复杂度，达到了预期要求。 关键词：无线传感器网络；节点定位；d v - h o p 算法；跳数比率；a p o l l o n i u sc i r c l e a b s t r a c t t h el o c a l i z a t i o no fs e n s o rn o d ei so n eo fs i g n i f i c a n tt e c h n o l o g i e si n w i r e l e s ss e n s o rn e t w o r k s ( w s n ) ，i tb a s e so naf e wp o s i t i o nk n o w nn o d e s t h e nc a l c u l a t es e l f - l o c a t i o nt h r o u g has p e c i a l1 0 c a t i o nm e c h a n i s m b e c a u s e o fc o n s t r a i n ti ns t o r a g e ，c o m p u t a t i o na n db a t t e r yp o w e r , e t c s ot h er e s e a r c h o fal o c a t i o na l g o r i t h m ，w h i c hs a t i s f ya a p p r o p r i a t ea c c u r a c yr e q u i r e m e n t ， h a sl o wc a l c u l a t ec o m p l e x i t ya n dt r a f f i cl o a d ，s ot h a ti tc a nd e c r e a s ep o w e r c o n s u m p t i o na n dp r o l o n gn e t w o r kl i f e t i m e ，i se s s e n t i a lt ow s na p p l i c a t i o n i nb o t ht 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 a tf i r s t ，w ei n t r o d u c et h eb a s i c p r i n c i p l e s ，c a l c u l a t em e t h o d sa n d p e r f o r m a n c ee v a l u a t i o nc r i t e r i o no fn o d el o c a t i o na l g o r i t h m ，a n a l y s e st h e b a s i ci d e a s ，a p p l i c a t i o nb a c k g r o u n d sa n dp e r f o r m a n c eo fv a r i o u se x i s t i n g a l g o r i t h m s e s p e c i a l l y , w ed i dm u c hr e s e a r c ho nd v - h o pa l g o r i t h m ，t h a t a d a p t st ol a r g es c a l en e t w o r k ，a n a l y s e da n dd i s c u s s e di t sc h a r a c t e r i s t i c s d e e p l y c o n s i d e r i n gt h o s ed r a w b a c k so fd v - h o p ，s u c ha sh i g ht r a f f i cl o a d a n d p o s i t i o ne r r o r , w ed e s i g n e d a n a l g o r i t h m w h i c hd o e ss o m e i m p r o v e m e n t so nd v - h o p i tu s e st h eg r i dn e t w o r ks t r u c t u r e ，d e f i n e s t w o g r a d ea n c h o r sw h i c hh a v es e p a r a t ec o m m u n i c a t i o nr a n g et oa s s i s t p o s i t i n g ，t h ew h o l ep r o c e s si sd i v i d e di n t ot w os t a g e st h a tar o u g hl o c a t i o n b i n da n da c c u r a t ec a l c u l a t i o n ：( 1 ) a c c o r d i n gt ot h el i n e a ri n v e r s er e l a t i o n s h i p b e t w e e ns i g n a ls t r e n g t hn o d er e c e i v e da n dt h ee u c l i d e a nd i s t a n c eo ft w o n o d e s ，w ec a nn a r r o wt h es c o p eo fp o s i t i o na n ds e tt h ef i l t e rf o rt h ef i n a l r e s u l t ( 2 ) i nt h en a r r o w e rs c o p e ，w es t a t i s t i ct h el e a s th o pc o u n tb e t w e e n t w on o d e st h r o u g hn e t w o r kb r o a d c a s t ，a n dc o n s t r u c ta p o l l o n i u sc i r c l eb y h o pc o u n tr a t i o ，a tt h ee n d ，w eu s et r i l a t e r a t i o na n dm a xl i k e l i h o o d e s t i m a t i o nt oc a l c u l a t et h e1 0 c a t i o n t h i si m p r o v e da l g o r i t h mi sr e a l i z e do nm o t e w o r k s2 0fa n di r i s n o d e sw h i c ha r ep r o d u c t e db yc r o s s b o wc o m p a n y , w et e s t e da n dc o m p a r e d t h er e s u l t so ft r a f f i c l o a d ，p o s i t i o n i n ga c c u r a c ya n de d g es t a b i l i t y t h e i i i e x p e r i m e n ts h o w st h a t ，c o m p a r e st od v - h o p ，t h i sa l g o r i t h ma c h i e v e s a o b v i o u sr e d u c t i o ni nn e t w o r kl o a d ，ah i g hp o s i t i o n i n ga c c u r a c ya n dab e t t e r e d g es t a b i l i t y m e a n w h i l e ，i td e c r e a s e st h ec a l c u l a t i o nc o m p l e x i t ys l i g h t l y , g e t st h eg o a le x p e c t e d k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k ；n o d el o c a l i z a t i o n ；d v - h o p ；h o p c o u n tr a t i o ；a p o l l o n i u sc i r c l e i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：2 盥璺日期：丝亟：! 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名： 圣! 鞋 日期： 二z ：二： 导师签名：垒墨坐丛 日期：! ! ：三：竺 第一章绪论 第一章绪论 作为近年来的研究热点之一，无线传感器网络相关的研究成果不断涌现，确定 事件发生的位置或获取消息的节点的位置是传感器网络最墓本的功能之一，对传感 器网络应用的有效性起着关键的作用。本章首先介绍了本文研究的背景，然后介绍 了节点自定位问题的一些背景知识及国内外研究现状，最后介绍了本文的主要工作 及安排。 1 1 研究背景及意义 无线传感器网络( w n s ，w i r e l e s ss e n s o rn e t w o r k ) 是由部署在监测区域内大量 的廉价微型传感器节点组成，通过无线通信方式形成一个多跳的自组织的网络，它 是由微机电系统( m e m ，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 ) 和无线通信技术结合集成而出的一种新型信息获取和处理模式，被广泛应 用在军事、农业、工业等领域，通过多个传感器间协作地感知、收集和处理网络覆 盖范围内被感知对象的信息，最后将被认定为有价值的信息发送给观察者。 对于w s n 的研究，起步于2 0 世纪9 0 年代末期，最早是由美国国防部高级研 究计划局发起的主要做为军事应用。相比于传统的信息获取方式，w s n 具有自组 织、廉价、功耗低、部署迅速、较好的可扩展性等优点，很适用于特殊时刻和特殊 环境下迅速搭建信息基础设施，故其拥有相当广阔的应用前景。 做为无线传感器网络主要支撑技术之一的节点定位技术，即根据少数己知位置 的节点，按某种定位机制计算确定自身的位置，其对传感器网络的监测活动至关重 要。在w s n 中，获取信息的节点的位置或事件发生的位置是传感器节点监测过程 中的重要信息，没有位置信息的监测消息往往并没有多大的实际意义。另外，除了 用来报告事件发生的地点，定位信息还能帮助实现：协助路由、目标跟踪、预测运 动轨迹、报告网络的覆盖质量、协助维护网络的负载均衡等功能。因此，确定获取 消息的节点位置或事件发生的位置是w s n 最基本的功能之一，直接影响到传感器 网络应用的有效性。 同时节点的定位问题也是w s n 的一个技术难点，最初人们想到的是使用全球 定位系统( g p s ) 来实现，但考虑到无线传感器网络在价格、体积、功耗等方面较大 的局限性，使用g p s 是不适合实际应用的。因此，需要设计新型的节点定位机制。 另一方面，传感器节点自身能力的限制也要求定位技术尽可能地降低计算复杂度和 节点间的通信开销，以降低功耗，延长整个网络生存时间。 1 基丁跳数比率的无线传感器网络节点定位技术研究 总之，研究一种适用于较大网络规模的、精度较高且通信功耗较低和计算简 单的分布式定位算法，对于w s n 的大规模实际应用具有重要的理论意义和应用价 值。 1 2 无线传感器网络节点定位技术研究现状 从人们开始节点定位系统的研究至今，w s n 自身定位系统和算法的研究大致 可以划分为两个阶段。第一阶段主要偏重于紧密耦合型和基于基础设施 ( i n f r a s t r u c t u r e b a s e d ) 类的定位技术，代表性的研究成果有a c t i v eb a d g e 、r a d a r 、 r a d i oc a m e r a 、a c t i v eo f f i c e 、s p o t o n 、s m a r tf l o o r 、s m a r tr o o m s 、3 d i d 等【u 】， 文献 4 9 1 【5 0 l 中对这些系统做了比较详细的描述。而在第二阶段中，松散耦合 型和无需基础设施( i n f r a s t r u c t u r e f r e e ) 定位技术则成为关注和研究的重点，并己成 为当前w s n 主要的研究领域，例如c r i c k e t 、相对定位算法s p a 、a p s 一系列分布 式定位算法等都是已有的研究成果。 c r i c k e d l 2 】是最早的室内定位系统，由m i t 为了弥补松散藕合定位算法的不足 而开发的，它和南加州大学的n i r u p a m a b u l u s u 的质心算法【1 3 】虽然都完全基于网络 连通性，实现起来非常简单，但却都要求未知节点必须与锚节点直接相邻，因而需 要较高的锚节点密度。同样，维吉尼亚大学t i a nh e 的a p i t h 】算法尽管巧妙地利用 了p i t ( p o i n ti nt r i a n g l e ) 原理，在无需测距的条件下实现网络定位，但也需要非常高 的锚节点密度，几乎无法应用于实际场合【1 5 】。 瑞士洛桑联邦工业大学的s r d j a n c a p k u n 等人提出了一种称为s p a 的相对定位 算法，其针对无基础设施的移动无线网络，但由于所有节点都需要进行坐标建立和 变换计算，节点数量与通信开销几乎呈指数比。针对其缺点，一种基于聚类的定位 算法由美国仁斯利尔理工学院的r a j a g o p a l l y e n g a r 等人提出了，大大降低了通信开 销。但是这两种算法均没有采取措施来抑制测距误差，故定位精度都较差i l 5 1 。 美国路特葛斯大学的d r a g o s n i c u l e s c u 等人提出了一系列分布式定位算法，该 系列算法是建立在距离矢量路由和g p s 定位原理基础之上的，由6 种定位算法组 成：d v - h o p 、d v - d i s t a n c e 、e u c l i d e a n 、d v - c o o r d i n a t e 、d v - b e a r i n g 和d v - r a d i a l ， 合称为a p s l l 6 1 。 加州大学伯克利分校的c h r i s s a v a r e s e 等人，将定位算法划分成初始和循环求精 两个阶段，进而提出了c o o p e r a t i v e r a n g i n g 和t w o p h a s e p o s i t i o n i n g 【1 1 】两种循环求精 定位算法，目的是减缓测距误差对定位的限制。后者对初始定位结果进行加权循环 2 第一章绪论 求精，对测距误差的抑制更加的有效。而a n d r e a s s a w i d e s 在2 0 0 2 年又采用分布式 卡尔曼滤波技术循环求精的算法：n h o pm u l t i t a t e r a t i o np r i m i t i v e 。而以上的循环算 法都无法预知循环的次数，这使算法的不确定性增加了。 另外，具有代表性的集中式定位算法包括：加州大学伯克利分校d o h e r t y 的凸 规划f 2 1 】和密苏里哥伦比亚大学y i s h a n g 的多维定标算法m d s m a p ) r 2 2 1 ，然而集中 式计算方式很大的缺点就是中心节点承担了太大的通信和计算任务，那些中心节点 附近的节点电能会很快被耗尽，从而缩短网络寿命。 己开发出的基于a d - h o c 的w s n 定位系统包括：k a l l i l lw h i t e h o u s e 提出的 c f l j a m 3 r i 2 4 定位系统，该系统建立在m i c a 平台之上，并使用超声波测距和信号强度 ( r s s ) 定位，但对环境依赖过大。另一个是j e f f r e yh i t o w e r 等人设计的s p o t o n 定 位系统，它使用类似于c a l a m a r i 的定位技术1 1 5 】1 5 。 与国外比较而言，国内传感器网络定位方面的研究成果相对较少，但近年来， 国内的不少研究机构和高等院校也纷纷从w s n 定位的理论和应用等方面开始了积 极的研究。0 6 年由科学家倪明选等担任的国家9 7 3 项目 云 无线传感器网络节点定位技术中网络的通信负载和定位精度是两个重要的衡 量标准，在满足算法应用环境所要求定位精度的前提下，减少网络的通信、计算复 杂度是本章即将介绍的节点自身定位算法的一个重点。本章首先介绍了无线传感器 网络中节点无线信号衰减模型，来作为定位算法的第一阶段理论基础；然后详细说 明了d v - h o p 算法原理，深入讨论分析其信负载较大，产生定位误差的原因，并在 算法第二阶段中基于d v - h o p 原理进行改进，最终实现定位。 3 1 无线信号传播模型 无线信号传播模型主要依据的是信号传播损耗与传输距离的正比线性关系，目 前主要应用于利用信号衰减推测距离的r s s i 技术中。接收节点先计算出信号的传 播损耗，然后根据信号传播理论或经验模型公式推测节点间距，由间距最后计算节 点位置。目前，很多定位算法都是利用r s s i 技术进行测距实现的，但是本算法中， 我们仅仅引入信号强度( r s s ) ，将其作为一种定位辅助手段，用于定位第一阶段中 节点位置范围的约束及控制算法中的节点每一跳的通信距离。 3 1 1 信号传播理论模型 理想状态下，没有多路的衰减和屏蔽，锚节点和未知接点之间的r s s 测量值就 是它们之间的精确的距离。如果锚节点按照r s s 值的递减排成一个序列，那么这个 序列反映的就是锚节点与未知节点之间的距离是递增的。对于这个顺序排列的锚节 点的第i 个点：r i r i 专d i c ； ，h，h p 那么 ( 坩一一p = 而( b - a ) c ( 3 1 ) 又。b 0 ，c o ，b a c。式3 1 的值恒大于零， 即( ) ( 口一一c ) 结论：对于小于1 的分数，在分子分母同减去一个较小的正实数之后，该分数 数值较以前减小。 p 咣+ 删“圳慨 细，自峨们珊岿“ 足够大时，在以上假设的情景下，网络锚点比例接近与2 8 5 。 3 2 2 网络节点运行时序 锚点最本质的功能就是向网络广播自身的位置信息及算法相关的必要信息，在 本文算法中两级锚点广播数据包存在一定的时序。 在定位的第一阶段，主锚点首先广播信息包，信息包中包含：信号强度、锚点 位置、从属于该主锚点的四个副锚点i d 号等，未知节点比较接收到的不同主锚点 基于跳数比率的无线传感器网络节点定位技术研究 信号强度，随着算法的运行，动态更新保存信号强度最大的前三个主锚点信息包， 根据3 1 1 节介绍的无线信号理论模型，我们不难推断出信号强度最大的主锚点距 离未知节点最近，从而也就确定未知节点所在的g r i d 以及该g r i d 相关四个顶点的副 锚点，至此定位的第一阶段结束。未知节点根据存储的主锚点信号强度来判断自身 是否处于特殊位置，如果是则可以直接确定位置，算法提前结束。否则进入定位第 二阶段。 在定位的第二阶段，副锚点广播信息包，信息包中包含：锚点位置、副锚点自 身i d 号、初始跳数( h o pc o u n t ) 值1 ，在某嘶d 内部的未知节点，根据前阶段确 定的自身所属g n a 的四个顶点副锚点，它们只接收并转发这四个副锚点发出的数据 包，如果接收到的数据包是新的( 即首次接收到该副锚点信息包或者是新接到的数 据包跳数较原来的小) ，那么就保存并h o pc o u n t + l ，然后以广播的方式转发该数据 包，如此进行直到所有的未知节点趋于稳定，不再更新自身存储的这些副锚点信息， 至此网络的通信过程结束，进而展开定位计算。未知节点根据在第一阶段得到所在 鲥d 主锚点信息从而确定初步定位的范围，在第二阶段中又存储g n a 相关四个副锚 点的h o pc o u n t ，每个未知节点利用两个副锚点的跳数比率来代替d v - h o p 中所采用 的两锚点的距离比率，符合一定跳数比率的锚点组可以构成一个a p o l l o n i u sc i r c l e ( 特性详见3 5 3 节) ，不少于三个a p o l l o n i u sc i r c l e 便可以利用2 3 2 节中介绍的三 边测量法或者极大似然估计法最终计算出位置。对于同未知节点，存在不同跳数 比率的a p o l l o n i u sc i r c l e 组，从而计算出若干个位黄结果。此时再结合第一阶段所 得的定位范围约束，剔除不合理的位置结果，从而最终定位该未知节点。同理类推， 在保证网络一定连通度的情况下，网络内的每个未知节点都可以实现自身定位。 3 3 算法整体描述 如上节3 ，2 2 所述，整个算法是按照预先规定的逻辑顺序井然有序的来运行的， 可以归纳描述为如下： ( 1 ) 网络主副两级锚节点及未知节点的内容初始化。 ( 2 ) 主副两级锚点的定时器t i m e r l 和t i m e r 2 开始计时，当定时器t i m e r l 计 时结束后，主锚点向网络周期广播包含自身信息的数据包，之后，主锚点进入睡眠 状态，未知节点接收并储存被断定是有效的数据包信息，定位第一阶段结束。未知 节点根据自身存储的主锚点信号强度来判断其是否在特殊位置，如果在特殊位置， 则可以直接确定节点位置，并转向第( 5 ) 步执行。否则进入第( 3 ) 步。 第三章基于r s s 和跳数比率的r a n g e f r e e 分阶段。1 7 点自身定位算法 ( 3 ) t i m e r 2 计时结束后，副锚点向网络周期广播包含自身信息的数据包，之 后，副锚点进入睡眠状态，算法所有锚点网络通信过程结束。未知节点接收并储存 被断定是有效的数据包信息。 ( 4 ) 未知节点根据存储的主、副锚点相关信息，利用跳数比率构造a p o l l o n i u s c i r c l e ，根据同一跳数比率构造的a p o l l o n i u sc i r c l e 的圆心坐标和半径建立线性方程 组，采用三边测量法或最大似然估计法，计算节点位置。结合第一阶段确定的位置 约束条件，对若干定位结果进行过滤并求平均值，最终实现定位。 ( 5 ) 未知节点将最终的位置，广播到基站节点，算法结束。 3 4 定位第一阶段：基于r s s 的位置范围约束 参照图3 1 ，在定位的第一阶段主锚点n i ( i 矿) 广播数据包，未知节点读取数 据包的信号强度( s t r e n g t h ) ，这里认为覆盖区域内信道衰落具有一致性，则存在节点 接收到信号的r s s 与距离信号源的欧氏距离( e u c l i dd i s t a n c e ) 存在线性反比关系，依 照这个规则初步缩小其位置范围。针对上图3 1 的一个鲥d 来讨论，如果节点m 接收到 来f i n 0 、n 3 、n 1 的数据包，其q b r s s 0 _ r s s 3 ，r s s 3 r s s l ，那么m 到这些主锚点的e u c l i d d i s t a n c e 大小关系为i m - n 3 1 _ l m - n o i ，i m - n 1 i i m n 3 i 【5 4 】。同理，根据接收到的r s s ，其他 未知节点可以轻松得到与其他鲥d 主锚点的距离远近关系。 具体到图3 1 来讲，m 接收正锚点信号r s s 强弱顺序依次为n o 、n 3 、n 1 ，这样m 就 处于n o 所在的网格内，结合其他较弱的两个主锚点，可以把未知节点缩小在更加小的 范围内即a n l n 0 1 ，为最后的定位结果提供约束条件，过滤掉不合理的结果，尤其是 在g r i d p 勺部未知节点数目稀少网络连通度很小的情况下，第一阶段的定位约束范围保 证了定位误差不至于很大甚至不能定位。 3 5 定位第二阶段：基于d v - h o p 和跳数比率的节点自身定位算法 3 5 1 传统的d v - h o p 定位算法 n i c u l e s c 等人提出了d v - h o p 定位算法，基本思想是将待定位节点到参考节点 之间的距离用网络平均每跳距离与定位节点到参考节点之间跳数的乘积来表示，然 后使用三边测量法计算得到节点位置信息。虽然待定位节点通信范围内的参考节点 数量不多，但是采用上述方法可以获得通信范围外多个参考节点的估计距离，利用 大量的冗余信息实现节点定位。该算法只需较少的锚点，计算开销适中，不需要进 行节点之间的距离测量，是个可扩展的算法，节点不需要任何附加硬件支持，是无 线传感器网络节点定位的一个理想方案，其缺点是仅在各向同性的密集网络中，校 2 3 基于跳数比率的无线传感器网络节点定位技术研究 正值才能合理地估算平均每跳距离，对于网络拓扑不规则的网络定位精度迅速下 降。 图3 - 2d v - h o p 算法买例图 f i g 3 2e x a m p l e o fd v h o p 如图3 2 ，通过锚点的信号广播和中间节点的转发，己知了锚节点l l 与l 2 ，l 3 之间的 距离和跳数，l 2 计算得到校正值( 即平均每跳距离) ( 4 0 + 7 5 ) ( 2 + 5 ) = 1 6 4 2 ，在图3 - 2 中， 假设a 从l 2 获得校正值，则它与3 个锚节点之间的距离分别为l i ：3 1 6 4 2 ，l 2 ：2 x 1 6 4 2 ， l 3 ：3 x 1 6 4 2 ，然后使用三边测量法确定节点a 的位置。 d v - h o p 算法e h - - 个阶段组成，总体流程图如下图3 3 所示： 图3 - 3d v - h o p 算法实现流程图 f i g 3 3p r o c e s sc h a r to fd v h o p 网络初始化主要包括一些初始参数的设置，以及传感器节点的构造。 第一阶段，首先使用典型的距离矢量交换协议，使网络中所有节点获得距锚节 2 4 第二章基于r s s 和跳数比率的r a n g e f r e e 分阶段节点自身定伊算法 点的跳数( d i s t a n c ei nh o p s ) 。为了获得到节点间的跳数，锚节点向所有邻居节点广播 一个包含其位置信息的数据包，接收到该数据包的节点确认来自该锚点的这个数据 包跳数最小后，将跳数加一继续转发，这样每一个节点即可得到距锚节点的最小跳 数。第二阶段，在获得其他锚节点位置和相隔跳距之后，锚节点根据以下式3 2 计 算网络平均每跳距离， ( 一工，) 2 + ( 少，- y ，) 2 h o p s i z 红l 瓦_ 2 其中，( x i ，y i ) 、( x j ，y j ) 是信标节点i 、j 的坐标，坞i 是信标节点i 与j ( - ，) 之间的跳段 数。然后锚点将平均每跳距离作为一个校正值( c o r r e c t i o n ) 采用可控洪泛法广播至网 络中，每个节点仅接受获得的第1 个校正值，而不再理会后来者，这样就确保了绝 大多数节点从最近的锚节点接收校正值。当接收到校正值之后，节点根据跳数计算 与锚节点之间的距离。第三阶段，当未知节点获得与3 个或更多锚节点的距离时， 就可以执行三边测量定位算法( 2 3 2 节有详细介绍) 计算出自己的位置。在大型网 络中，还可通过为数据包设置一个跳数上阈值来减少网络通信量。 接下来对d v - h o p 算法做一下简要分析，为了描述一个网络环境，我们需要定 义如下特征量： 锚点数量1 1 ； 未知节点数量m ； 网络所存在空间的维数( 2 d 或3 - d ) ； 在给定的传输能耗和比特错误率下，每个节点的平均无线传播范围r ； d v - h o p 算法通信开销：这里对定位算法的讨论中所有邻居节点间的通信都是 以广播而非直接的单播形式实现的。因此，通信代价实质就是节点发送的广播包数 且 里。 一开始每个锚节点都发送广播包，称做跳数包，每个锚节点的跳数包包含相应 自身位置的坐标，跳数值h = l 。每个收到这些跳数包的节点都要检查包的信息是否 满足保存转发的条件( 即收到的跳数包来自一个新节点或者收到的跳数值小于之前 保存的跳数值) ，这样就大量减少了算法产生通信量降低了能耗，如果节点将存储 该信息并再次广播转发，将跳数h 变为h + l 。这一过程将一直重复，直到没有节点 能够产生它的邻居节点都未接收过的消息，便自然停止。整个网络中每个节点只发 送未发送的或者是跳数更小的数据包，在d v - h o p 第一阶段每个锚点节点平均转发 2 5 基于跳数比率的无线传感器网络节点定位技术研究 ( n 1 ) 个数据包，每个未知节点平均发送1 1 个数据包，通信量为 f n + m 玎+ 行( ，7 1 ) 1 ： ：+ 阼聊；第二阶段中每个锚点广播自身计算的每跳距离，由于 未知节点只接受并转发第一个校正值，而丢弃所有后来者，锚点只是广播校正值却 不转发其他锚点的校正值，通信量为聆+ 形。 计算开销：算法的计算开销包括距离计算和最小二乘算法。未知节点使用1 1 个 锚点进行位置估计，每个节点执行1 1 个乘法运算以计算r 1 个距离，在计算距离的基 础上，节点执行最小二乘运算来估计位置。每一次最小二乘运算实际包含两个过程， 数据必须首先被线性化，然后应用传统最d , - - 乘法公式，假设一个包含n 个锚点的 d 维空间场景，线性化包括形成矩阵c 和b ( 详见2 3 2 节) ，生成c 需要d x ( n - 1 ) 次减法，生成b 需要( n 1 ) x ( 2 d + 1 ) 次的加法和( n 1 ) 2 ( d + 1 ) 次的乘法。一旦数 据被线性化了，我们就使用最小二乘法的解法来计算位置估值，整个运算过程的计 算复杂度与其矩阵的大小成比例。对于一个矩阵c 月仰q ) d ，最小二乘法的计算复杂 度是o ( ( 玎一1 ) d z + d ，3 ) 。我们将之松散地转化为用数目相当的计算次数( f l o p s ) 表示。 把这些表达式结合在一起，对于每个锚节点，每个节点都将执行一次乘法( 求距 离) 和一次最4 , - - 乘法计算( 求位置) 。因此，每个节点在整个建立阶段的算法的过程 中将运行的计算次数f l o p s 平均为： 挖+ d 扣一1 ) + ( 行一1 ) ( 2 d + 1 ) + 2 ( 拧一1 ) ( d + 1 ) + d 2 ( ，2 一1 ) + ? = 疗+ 印一1 ) ( d 2 + 5 d + 3 ) + ? z 这里应该注意：由上述线性化和最小二乘法计算统计的f l o p s 所得到的估计代价要 高于实际的代价，这是由于在锚节点数量很大的网络中，节点不需要使用所有的n 个锚节点来进行定位计算，在这里是为了方便讨论简单，故将n 个锚点都参加计算。 在以后的3 5 4 节讨论中也在此假设上展开。 假设d v - h o p 算法是在二维空间中的，故d = 2 ，则该算法的基本性能如表3 - 1 ： 表3 - 1d v - h o p 算法性能分析 t a b 3 - 1p e r f o r m a n c ea na n a l y s i so fd v - h o p 3 5 2d v - h o p 算法存在的问题 由于节点硬件等原因，使得网络中的节点存在以下一些复杂情况：( 1 ) 同等发射 功率，同样的距离下，不同的节点产生的结果不同，有的可以很快地互相通信，而 第二章基于r s s 和跳数比率的r a n g e f r e e 分阶段节点自身定位算法 有的获取彼此信息的反应时间很长，或者根本不能通信。( 2 ) 同一个节点对儿，其中 有一个节点能获取另一个节点的信息，但另外一个节点却获取不到该节点任何信 息。( 3 ) 同一对儿节点，在同一位置，不同的时间段产生的结果都会不一样。( 4 ) 由于 节点内部通信频率不停的变动，使得相距较远的两个节点，以一个较小的概率在某 一时刻能通信。节点之间是以一定的概率连通的，当两个节点因为相距较远以一个 很小的概率互相通信时，若简单地认为该对节点之间的跳数为1 ，这样的判断方式， 势必会带来较大的定位误差。另外，即使没有其他因素的影响，简单地使用跳数指 示距离是不可靠的，同样的跳数获取的距离值之间相差很大。 d v - h o p 算法对跳数信息过于依赖，当锚节点因为以上种种原因，接收到不合 理的跳数值之后，会很大程度上影响锚节点计算出的平均每跳距离值；非锚节点的 情形就更复杂：会接收到不合理的跳数值和平均每跳距离值，不论是何种情况，造 成的定位误差将是巨大的。 d v - h o p 算法中锚点需要进行两次网络数据包泛洪，网络通信负载较大，在定 位的第二阶段，未知节点只是采用了第一个接收到的每跳校验值，但是为了保证每 个未知节点能够得到该校验值必须转发，这样造成较大的通信浪费。 由于整个网络几乎是完全连通的，网络内不良节点( 不能确定位置的节点) ，除 了不可达节点之外，还存在其他三种类型请参考文献【5 5 】，d v - h o p 算法无法判断 出不良节点，网络中所有的可达节点都会收到每个参考节点的位置信息，一个节点 收到了平均每跳距离和3 个以上参考节点的跳数就可以执行三边测量法计算自己的 位置，这样也就降低了定位精度。 下面，为了尽量弥补上述一些不足，提出一个改进的定位算法，整个定位算法 分成初步定位以缩小定位范围和精确计算定位两部分，特别是在网络节点密度低的 情况下保证了一定的定位精度。将原来的节点统计整个网络距锚点的最小跳数缩小 到每个萌d 内部来完成，各个鲥d 之间相互独立，增强了定位算法的健壮性和稳定 性。并且锚节点只需向网络泛洪一次( 统计跳数) 而不用再次估算和泛洪每跳平均 距离，大大降低了网络通信负载。 3 5 3 数学模型a p o l l o n i u sc i r c l e a p o l l o n i u s ( 约公元前2 6 2 公元前19 0 年) 是古希腊亚历山大时期的三位重要数 学家之一( 另两位是e u c l i d 和a r c h i m e d e s ) ，他最重要的数学成就是在前人的基础 上创立了相当完美的圆锥曲线理论。 a p o l l o n i u s 定理：设一动点到两定点的距离之比为两不等已知线段之比，则该 2 7 基丁跳数比率的无线传感器网络：节点定位技术研究 点的轨迹是一个圆，这个轨迹圆叫做a p o l l o n i u s 圆，其直径在这两个定点所在的直 线上。事实上，当这个距离比值为l 时，这些点的轨迹就是两个定点组成的线段的 垂直平分线。如下图3 _ 4 所示： 图3 - 4 a p o l l o n i u sc i r c l e - # 例图 f i g 3 - 4e x a m p l eo fa p o l l o n i u sc i r c l e p 是a p o l l o n i u sc i r c l e 上的一点，它到点a 、b 的距离比是常数1 1 1 ；n ，而直径的两端 点i 、e 分别是线段a b 内部和外部的点，通过如下的式3 3 可以计算它们的坐标。 xi = 丛挚x e = 百m x b - n x a y ，= 警y=1mrb丁-nrae( 3 3 )，聊+ 玎 上 肌一玎( 3 - j ) 由此也可以计算得到圆心的坐标和半径： 五：i m 2 x b - 丁n 2 x ak ：等笋尸= 业雾 这样，符合某个距离之比的两个定点，就能够确定一个a p o l l o n i u sc i r c l e ，那 么满足某一跳数比率的一组a p o l l o n i u sc i r c l e ( 至少三个) 就可以确定一个点的坐 标，如下图3 5 所示。 a 图3 - 5 三个相同跳数比率的a p o l l o n i u sc i r c l e 微p 、p 点 f i g 3 5t h r e ea p o l l o n i u sc i r c l e sw i t hs a m eh o pc o u n tr a t i o ng e tpa n dp p o i n t s 上图中a 、b 、c 是三个固定的点，圆c a b 、o a c 、o a c 都是满足某一距离之比并 分别由( a 、b ) ，( a 、c ) ，( b 、c ) 三组固定点所形成的a p o l l o n i u sc i r c l e 。一般情况 下，利用2 。3 2 节中介绍的三边测量法计算j 这_ - - + a p o l l o n i u sc i r c l e 就能够确定个公 2 8二o 第二章基t - r s s 和跳数比率的r a n g e f r e e 分阶段节点自身定位算法 共交点，但是这里注意：存在少数特殊情况，并不像通常三点测量定位法，三个不 同的a p o l l o n i u sc i r c l e 不一定能唯一确定一个点位置，例如上图3 5 所示，这三个不同 的a p o l l o n i u sc i r c l e 之间存在p 并c l p 两个交点，这样就需四个对锚点组合构成的四个 a p o l l o n i u sc i r c l e 相交，然后利用极大似然估计法来计算确定唯一p 点的坐标。如下图 3 - 6 所示： 图3 - 6 四个相同跳数比率的a p o i l o n i u sc i r c l e 确定p 点 f i g 3 6f o u ra p o l l o n i u sc i r c l e sw i t hs a m eh o pc o u n tr a t i o ng e tpp o i n t 将a p o l l o n i u sc i r c l e 的这些数学特性具体应用到本文的算法中时，图3 6 中的固定 点a 、b 、c 、d 即网络区域中的副锚点( 注意：这里并不包括主锚点，因为主锚点只 是在算法的第一阶段工作，目的是为了初步确定未知节点在哪一个g r i d p 勺，再加之主 锚点本身的通信距离较远相应的发射功率功耗也较大，因此主锚点不再在定位的第 二阶段工作，这样也可以相应的延长网络寿命) ，点之间的距离由跳数代替，若干跳 数比率相同的a p o l l o n i u sc i r c l e 确定的公共交点即网络区域中的未知节点。 3 5 4 基于d v - h o p 和跳数比率定位算法 该部分是本文定位算法的重点，也是本算法的第二阶段。这个阶段中，每个g r i d 所属的四个副锚点广播包含自身信息的数据包，而g r i d 内的未知节点只保存到达这四