（微电子学与固体电子学专业论文）基于omnet仿真的无线传感器网络定位算法研究.pdf

基于o m n e t + + 仿真的无线传感器网络定位算法研究 摘要 无线传感器网络作为一种新的信息获取和处理技术，能够实时监测、感知 和采集各种环境或监测对象的信息，其应用领域非常广泛。在无线传感器网络 中节点的位置信息对传感器网络的监测活动至关重要，获取网络节点的位置信 息是无线传感器网络在众多领域应用的基础。 目前很多算法在低密度网络下节点的定位精度较低，比较容易受到网络拓 扑结构变化的影响，并且在对节点定位的过程中对节点的能量消耗过大。结合 以上节点定位的不足，本文在d v - h o p 算法的基础上提出了基于选择信标节点 的d v h o p 算法，算法采用选择信标节点的方式，利用节点的权重比例来计算 平均跳距，同时采用将选择的信标节点分成若干个组的策略，利用三边测量法 分别计算出未知节点的位置，并将计算出的结果进行平均。 为了降低网络的通信开销，提高网络稳定性，本文又提出了一种基于节点 密度的定位算法，根据k 。s 公式估算每跳间距，利用选择信标节点和加权平均 的思想减少算法的误差。基于节点密度的算法只进行一次泛洪广播，很大程度 上减少了网络的通信开销。 利用o m n e t + + 仿真工具分别对上述两种算法进行仿真测试。分析结果表 明：选择信标节点的d v - h o p 算法和基于节点密度的算法，降低了节点定位误 差，减少了网络的能耗，提高了网络的整体稳定性。 关键词：o m n e t + +无线传感器网络d v - h o p 定位算法节点密度 r e s e a r c ho nl o c a l i z a t i o na l g o r i t h m sf b rw i r e l e s ss e n s o r n e t w o r ku s e do m n e t + + s i m u l a t o r a b s t r a c t a san e wt e c h n o l o g yo fa c c e s s i n ga n dp r o c e s s i n gi n f o r m a t i o n ，w i r e l e s ss e n s o r n e t w o r k sc a nb eu s e dt os e n s ea n dc o l l e c tt h ei n f 6 r m a t i o no fv a r i o u se n v i r o n m e n t a n dm o n i t o ro b je c ti nt h er e a lt i m e ，a n di t sr a n g eo fa p p l i c a t i o ni sv e r yb o a r d t h e l o c a t i o ni n f o r m a t i o no fn o d e si nw i r e l e s ss e n s o rn e t w o r k si sp r i m ei m p o r t a n tt ot h e m o n i t o r i n ga c t i v i t i e s o ft h es e n s o rn e t w o r k ，a n da c c e s s i n gt ot h en e t w o r kn o d e l o c a t i o ni n f o r m a t i o ni st h eb a s i so fm a n ya p p l i c a 【t i o n s a tp r e s e n tm a n g ya 1 9 0 r i t h m s ，t h en o d ep o s i t i o n i n ga c c u r a c yi s l o w e ri n l o w d e n s i t yn e t w o r k ， w h i c hi sa f 诧c t e de a s i l yb yt h ec h a n g eo ft h en e t w o r k t e c h n o l o g y ，i na d d i t i o n ，i tc a u s eg r e a te n e r g yc o ：【l s u m p t i o ni nt h en o d ep o s i t i o n i n g c o n s i d e r i n gt h el a c ko fa b o v ew a y si nn o d ep o s i t i o n i n g ，o nt h eb a s i so fd v - h o p a l g o r i t h m ，t h ed 、乙h o pa l g o r i t h mb a s e do nt h e ：；e l e c tb e a c o nn o d e si sp r o p o s e di n t h i sp a p e r ，t h i sa l g o r i t h ma d o p tt h em o d eo fs e l e c t i n gt h eb e a c o nn o d e s ，u s i n gt h e p r o p o r t i o no fn o d ew e i g h t st oc a l c u l a t et h ea v e r a g eju m pd i s t a n c e ，w h i l eu s i n ga s t r a t e g yi nw h i c hw ed i v i d e dt h es e l e c t e db e a c o n sn o d ei n t oan u m b e ro fg r o u p s ， a n di ta l s ou s et h em e t h o do ft r i l a t e r a t i o nt oc a l c u l a t et h el o c a t i o no fu n k n o w nn o d e f i n a l l y ，a v e r a g et h ec a l c u l a t e dr e s u l t s i no r d e rt or e d u c et h ee x p e n s e so ft h en e t 、o r kc o m m u n i c a t i o na n di m p r o v e t h es t a b i l i t yo ft h en e t w o r k ，t h ea l g o r i t h mb a s e do nn o d ed e n s i t yi sp r o p o s e di nt h i s p a p e r a c c o r d i n gt ot h ek sf i o m u l ae s t i m a t e dt h ep e r - h o ps p a c i n g ，u s i n gt h ei d e a o fs e l e c t i n gb e a c o nn o d e sa n dw e i g h t e da v e r a g et or e d u c et h ee r r o ro ft h ea l g o r i t h m t h i sa l g o r i t h m o n l yc a r r i e do u tan o o d i n gb r o a d c a s t ，s u b s t a n t i a l l yr e d u c et h e e x p e n s eo fn e t w o r kc o m m u n i c a t i o n u s i n go m n e t + + s i m u l a t i o np l a t f o r mt o s i m u l a t et h et w oa l g o r i t h m s t h e r e s u l t so fs i m u l a t i o ns h o w st h a t ：t h e s et w oa l g o r i t h m sr e d u c et h ea c c u r a c yo f n o d e p o s i t i o n i n ga n dt h ee n e r g yc o n s u n l p t i o no f t h en e t w o r k ，i m p r o v et h es t 2 l b i l i t yo ft h e n e t w o r k k e y w o r d s ：0 m n e t + + ；w s n ；d v - h o pp o s i t i o n i n ga l g o r i t h m ；n o d ed e n s i t y 致谢 在毕业之际，回顾在合肥工业大学的研究生期间的学习与生活，由衷感谢 我的导师刘士兴副教授对我学业的悉心指导和工作生活方面的关心，在这三年 时间里，他为我们提供了很多学习和锻炼的机会，他的关心和指导使我在学业 上取得了很大的进步。刘老师广博的学识、严谨的治学作风、诲人不倦的教育 情怀使我深受影响和激励，在此特向刘士兴老师表示真诚的感谢与崇高的敬意。 感谢电子科学与应用物理学院的各位老师和领导，他们为我们的学习、科 研提供了优良的环境，在此我对他们的教育与关心深表谢意。 我也要感谢我实验室的所有同学，我们互相帮助，共同学习，让我研究生 期间的生活充满热情和快乐。 最后，我要谢谢我敬爱的父母和家人，谢谢他们多年来给予我的无私关爱 与奉献，使我充满前进的动力和精神支柱。 作者：孟召晶 2 0 1 2 年4 月2 6 日 插图清单 图1 1 无线传感器网络架构1 图2 1 声波测距原理7 图2 2t d o a 定位原理8 图2 3a o a 定位原理1 图2 4 质心定位算法9 图2 5a p i t 算法10 图2 6p i t 原理1 1 图2 7 三边测量法原理1 1 图2 8 三角测量法原理1 2 图3 1o m n e t + + 的模块l7 图3 2 仿真编译过程2 1 图4 1 网络拓扑结构2 4 图4 2 节点信息传播方式2 5 图4 3 选择信标节点的算法示意2 7 图4 4 均匀分布的拓扑结构3 0 图4 5 随机分布的拓扑结构3 0 图4 6 建立网络拓扑3l 图4 7 节点均匀分布下的定位比例3 2 图4 8 节点均匀分布下的定位误差3 2 图4 9 节点非均匀分布下的定位比例3 3 图4 1 0 节点非均匀分布下的定位误差3 4 图5 1 跳距与邻居节点的关系3 5 图5 2 节点邻居节点数目与每跳平均距离的关系3 7 图5 3 节点密度算法4 1 图5 - 4 均匀分布下节点密度算法的定位比例4 3 图5 5 非均匀分布下节点密度算法的定位比例4 4 图5 6 节点均匀分布下的定位误差4 5 图5 7 节点非均匀分布下的定位误差一4 5 图5 8 算法的通信开销4 6 表格清单 表2 一lr a n g e - b a s e d 定位算法对比1 3 表2 - 2r a n g e f r e e 定位算法对比1 4 表3 1 仿真系统对比2 3 表5 1 邻居节点个数目与每跳平均距离的对应表3 7 第一章绪论 1 1 课题的研究背景及意义 近年来，随着微电子技术制造工艺的提升，使得传感器节点的制造技术也 在飞速发展，从而出现了许多体积更小、功能更多的传感器节点，这些节点不 仅能采集环境中的信息，还能对采集的信息进行简单的处理，并通过无线通信 的方式将信息发送出去。 无线传感器网络由传感器节点、汇聚节点、网关和用户终端等组成。如图 1 一l 所示，传感器节点用于探测目标区域信息，是一个具有采集、处理和发送 功能的微系统，有些节点除了收集和处理本地信息外，还要完成对其他节点的 定位【lj 。无线传感器网络的作用就是通过网络中的节点对目标环境和对象信息 进行实时采集和监测，并且将信息通过无线多跳网络传递给用户终端【2 1 。无线 传感器网络( w i r e l e s ss e n s o rn e t w o r k ，w s n ) 的研究包括了对传感器技术、无 线通信技术和节点定位技术等众多方面的研究【3 】。在这众多的研究领域当中对 网络中节点定位技术的研究又是其他研究领域的基础。 图l - l 无线传感器网络架构 目前无线传感器网络的应用己经扩展到很多方面，包括环境监测、智能家 居、工业控制以及国防建设等。但是在这些应用领域中大部分是以获知系统内 各传感器节点位置为前提的，因此在w s n 的诸多应用中，不知道传感器位置 而感知的数据是没有意义的【3 j 。但是在大多数的应用领域中网络的规模都较大， 网络中的节点都很多，这些节点随机分布在探测区域，因此其位置不能被事先 确定，而无线传感器网络的大量应用都需要获知网络中节点的地理位置信息， 所以获知信息来源的准确位置已经成为无线传感器网络技术所研究的一个重要 方向。 全球定位系统( g p s ) 是通过卫星实时的对目标进行定位。该技术的定位 精度很高，而且能够完成对移动目标的精确定位。但其在定位过程中目标的能 耗会很高，而且它还需要对目标加入额外的硬件才能完成定位，这样就导致了 目标的体积很大，成本较高，因此其不适用需要大规模部署的传感器网络节点 的定位。而人工部署对于大规模的传感器网络更是不可能实现，所以现阶段通 过定位算法对传感器网络节点进行定位才是主流。 1 2 节点定位技术的现状 近年来随着w s n 应用的发展，国内外的研究者们都对节点的定位技术做 了大量的研究。继a t & tl a b o r a t o r i e sc a m b r i d g e 提出了一种室内定位系统 a c t i v eb a d g e 后，又相继出现几种比较典型的定位系统如m i c r o s o f ：【sr a d a r 【4 1 ， a c t i v eb a d g e 【5 1 ，s p o t o n 【6 1 ，a h l o s 【”，c r i c k e t 【8 1 等。n i c u l e s c u 和n a t h 提出了 d v h o p 定位算法。目前国内对无线传感器网络定位算法的研究也有很多：孙 利民1 9 j 等人对已有的定位算法进行了详细的介绍，并对各种算法进行了分类。 王福豹l l l j 等人从测量距离算法和确定位置算法介绍了定位原理，并指出传感器 网络定位算法的研究方向。李方敏【眨】等人提出了一种分布式定位算法，该算法 无需测距设备支持就能完成节点的定位。孙学斌【1 3 】等人提出了一种移动目标定 位算法，用来获得监测区域内移动节点的坐标。 但是在己出现的这些定位算法中，没有一种算法能在拥有较高的定位精度 和定位比例的同时，又能很好地保证网络的稳定性。基于测距技术的定位算法， 虽然能够获得较高的定位精度，但定位算法通常需要一定的硬件设备来支持， 从而造成节点的能耗和成本很高，而且这类算法很容易受到环境中各种干扰的 影响，以至于节点的定位精度很不稳定。基于非测距的定位算法，不需要添加 额外的硬件，能有效降低传感器的成本和功耗，并且随着非测距定位算法的发 展，其定位精度已经能够满足很多应用对定位精度的要求。因此，目前基于非 测距的定位算法有更广泛的应用空间。 1 3 课题研究内容及论文结构 d v h o p 算法1 1 4 儿 j 是一种基于非测距技术的定位算法，其在对节点进行定 位的过程中表现出了良好的定位性能，能满足一般情况下网络对节点定位精度 的要求，但该算法也存在一些方面的不足：定位精度受网络拓扑结构的影响比 较大；定位过程中能耗较高等。为了降低节点分布的随机性对定位精度造成的 影响，减小节点的定位误差，本文在d v h o p 算法的基础上引入选择信标节点 的策略，提出了一种选择信标节点的d v h o p 算法，该算法能降低节点分布的 随机性对定位结果造成的影响，提高节点的定位精度。利用o m n e t + + 仿真平 台对所提出的算法进行仿真验证，得到网络节点定位的各项性能指标，通过分 析算法的性能指标参数，验证算法在节点的定位精度和网络能耗上的优越性。 为了降低节点能耗，保证网络的长期稳定性，在选择信标节点的d v - h o p 算法的基础上本文又提出一种基于节点密度的算法，并对该算法的后期计算进 行了优化。该算法是根据未知节点周围邻居节点的数目来估算每跳平均距离 2 u 引。利用o m n e t + + 仿真平台对算法进行模拟仿真，并对仿真结果进行分析， 从而验证基于节点密度的算法在降低节点的能耗和提高网络的整体稳定性上的 优势。 本文章节安排如下： 第一章：绪论。给出了课题的研究背景及所研究课题的意义；分析了国内 外定位技术的研究现状；指出了论文的主要研究方向和内容。 第二章：节点定位技术。概括性的介绍了定位技术及其分类；给出了一些 当前较典型的定位算法，并分析了各算法的优缺点；指出了本文的研究方向： 基于非测距的分布式节点定位算法。 第三章：o m n e t + + 仿真平台。详细介绍了o m n e t + + 仿真平台的组成结构、 语法以及仿真过程，并通过与其它仿真软件的进行对比，体现o m n e t + + 平台 在无线传感器网络仿真中的优越性。 第四章：选择信标节点的d v h o p 算法。提出了选择信标节点的d v h o p 算法，并通过仿真平台的仿真分析，验证了选择信标节点的d v h o p 算法的定 位性能。 第五章：基于节点密度的定位算法。本章针对选择信标节点的d v h o p 算 法能耗较大的缺点，提出了基于节点密度的定位算法。通过仿真分析，验证该 算法的定位性能。 第六章：总结与展望。 第二章节点定位技术 2 1 节点定位技术简介 在众多的对无线传感器网络的研究中，最终都要落实到对网络中节点的研 究。根据在网络中所起到的作用不同，可以把传感器节点分为信标节点( b e a c o n n o d e ) 和未知节点( u n k n o w nn o d e ) 。研究传感器节点定位的主要目的就是要 确定这些未知节点的坐标。在传感器网络中，信标节点的坐标信息是已知的， 但在节点总数中占据很小的比例，节点定位技术的主要工作就是利用这些已知 的节点去获得那些未知节点的位置坐标。目前较实用的技术就是通过定位算法 来确定这些未知节点的坐标。使用定位算法确定未知节点的坐标一般情况下需 要分为两步：第一步，通过测量距离的算法得到未知节点到几个信标节点的距 离；第二步，利用确定位置的算法计算出未知节点的坐标。比较典型的测距算 法有：r s s i 和d v - h o p 等；比较典型的确定位置算法有：三边测量法和多边形 法等。本文主要从测量距离的算法方面对已有算法进行分析优化。 在下文中将会出现一些传感器网络中的专有名词，为了不产生误解以及更方 便书写，下面将给出这些名词的解释【9 j ：信标节点( b e a c o nn o d e ) ：网络中位 置已知的节点；未知节点( u n k n o w nn o d e ) ：网络中位置未知的节点；邻居节 点( n e i 曲b o rn o d e s ) ：节点通信半径内的节点；中间节点：又称为转发节点， 两个节点之间的节点：跳数( h o pc o u n t ) ：两个节点间的跳段总数；每跳平均距 离( a v e r a g e j u m pd i s t a n c e ) ：各节点根据测距算法所获得的到下一节点的距离； 跳段距离：两个节点之间的间隔距离；t o a ( t i m eo fa r r i v a l ) ：信号从一个节点 传播到另一节点所需要的时间；t d o a ( t i m ed i f - f e r e n c eo f a r r i v a l ) ：不同传播速 度的信号到达目标所需要的时间之差；a o a ( a n g l eo fa r r i v a l ) ：节点接收到的 信号相对于自身轴线的角度；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 ) ：节点接 收到无线信号的强度；p i t ( p e r f e c tp o i n ti nt r i a n g u l a t i o nt e s t ) ：最佳三角形内点 测试法；a p i t ( a p p r o x i m a t ep i tt e s t ) ：近似三角形内点测试法；o m n e t + + ( 0 b j e c t i v em o d u l a r n e t w o r kt e s t b e di nc + + ) ：基于组件模块化的网络仿真平台。 2 2 定位算法评价标准 对于一种定位算法如何评价其在实际应用中的性能，参考一些文献本文给 出了几个常用的性能评价标准i lo 】： ( 1 ) 定位误差：定位误差是衡量一种定位技术最重要的评价指标，一般是 用误差值与节点无通信半径的比值表示。定位误差越小表明该定位技术对未知 节点的定位越精确。 ( 2 ) 节点能耗：能耗直接影响传感器网络的稳定性和定位精度。当传感器 网络布置于探测区域后，节点的能量就不可能用人工的方式继续供应，因此在 4 相同的定位精度下，节点在计算量、通信开销以及存储开销上的能量消耗就成 为评价定位算法的重要指标。 ( 3 ) 定位比例：网络中所有能通过定位算法获得自身坐标的未知节点与网 络中未知节点总数的比值。在无线传感器网络中，由于节点分布的随意性，可 能会导致很多节点是孤立的或者其邻居节点很少，以至于其不能被一般的算法 来定位，最大限度获得未知节点的坐标是节点定位技术对节点算法的要求。因 此定位算法的定位比例的高低也就成为衡量算法好坏的一个标准。 ( 4 ) 信标节点密度：即信标节点在所有节点中所占的比例。信标节点的位 置是通过人工部署或g p s 获得。在传感器网络中信标节点的密度越大，所获得 的定位精度也就越高。但是通常情况下人工部署信标节点的方式会受到网络部 署环境的限制，而使用g p s 定位信标节点的费用会比普通节点高很多，这就增 加了整个网络的定位开销。因此，在同样的定位精度下，信标节点密度也成为 了评价指标之一。 ( 5 ) 容错性和自适应性：一般来说定位算法的仿真都是在不考虑各种干扰 的前提下进行的。但真正的传感器节点是要部署在真实的环境中的，这个时候 各种影响因素就会对定位算法造成一定的影响，有些算法受到这些因素的影响 后就会出现较大定位误差甚至根本无法定位。因此，定位算法的容错性和自适 应性，也成为了评价算法性能的指标。 ( 6 ) 定位开销：定位算法在节点的定位过程中所花费的配置时间、基础设 施以及节点成本的总和。无线传感器网络的特点之一就是密集部署，所以每个 节点的成本关系到整个网络的成本。节点定位还需要其他的配套设施，节点算 法定位对配套设施的要求，影响到整个网络的成本。因此定位开销也是衡量定 位算法的一项指标。 以上六项性能指标，并不是评价定位算法性能的全部指标，但在大多数情 况下主要选取以上几项对算法进行评定。在对一种定位算法进行评价时，并不 是要求每项指标都要达到很高的标准，而是要根据具体的定位环境以及定位要 求，对指标的数值进行取舍，从而选择针对该应用环境的最优定位算法。 2 3 定位算法的分类 无线传感器网络节点的定位算法目前并没有一个严格的分类标准，通常情 况下按照不同定位算法的特点可以将定位算法分为以下几种【l 。 1 ) 绝对定位与相对定位：绝对定位所得到未知节点的位置是真实环境中的 坐标；而相对定位通常是以网络中某些节点作为参照物，以这些点建立坐标系， 从而获得未知节点的位置信息，相对定位的定位结果不是现实的地理位置而是 以某些节点为参考的相对坐标。目前所使用的大部分定位算法都属于绝对定位 5 的范畴，相对定位最大的特点就是不需要信标节点的支持，减少了网络的成本， 但其在定位的过程中会消耗大量的节点能量，而且定位准确性也有待提高。 2 ) 集中式定位与分布式定位：集中式定位是指通过网络系统中的某些节点 或者基站对未知节点进行定位。集中式定位时未知节点必须将自己的信息发送 给这些节点或基站，通过这些节点或基站来计算节点的坐标；分布式定位中未 知节点不是将自身的信息传递给信标节点，而是通过与信标节点进行信息交换 的方式，获得若干个信标节点的位置信息后自己进行定位计算。集中式定位中 基站的能量和存储量都很大，定位过程可以不考虑其计算开销，对所得到数据 使用各种方法反复计算，因此所的到的定位坐标比较准确。但以这种方式进行 定位会对基站附近的节点造成很大的通信开销，从而可能会导致整个网络出现 “空穴”，降低了网络的整体稳定性。分布式定位较集中式定位最大的优点就在 于提高了网络的整体稳定性。 3 ) 基于测距技术的定位( r a n g e - b a s e d ) 与非测距技术的定位( r a n g e f r e e ) ： 在2 1 节中提到了大部分定位算法的实现步骤，首先就是测量未知节点到信标 节点间的距离，而这个距离包括了计算距离和估算距离。r a n g e - b a s e d 定位技术 就是通过一些算法计算出信标节点和未知节点间的确切距离，然后使用确定节 点位置的算法获得未知节点的坐标；而r a n g e f r e e 定位技术不是通过计算而是 通过估算来获得未知节点到信标节点的距离。基于测距技术的定位精度要高于 非测距技术的定位精度，但其常需要一些额外硬件支持，从而造成的网络成本 较大。基于非测距技术的定位虽然定位精度相对稍低，但其对硬件上没有过多 的要求，而且随着该定位技术的发展，其定位精度有了很大提高，因此其目前 更适合应用于无线传感器网络节点定位。 4 ) 无信标节点算法和有信标节点算法：无信标节点算法即在传感器网络中 没有信标节点，所有节点的坐标都是未知，算法通过一定的顺序对节点定位， 这种方法很大程度上降低了网络成本，但其在获取未知节点坐标时会造成累积 误差，从而使得其定位误差较大。有信标节点算法就是在网络中随机分布着若 干信标节点，未知节点通过这些信标节点来确定自己的坐标。这种算法会增加 网络的成本，但其定位精度以及定位效率都要远远好于无信标节点的算法。目 前大部分的算法都是基于有信标节点的。 5 ) 测量距离的算法和确定位置的算法：根据定位算法在确定未知节点坐标 时的作用不同，可将算法分为测量距离的算法和确定位置的算法。对于大部分 的定位算法都要包含这两种算法。首先使用测量距离的算法得出未知节点和信 标节点之间的距离，其次使用确定位置的算法计算出节点的位置坐标。 6 2 4 基于测距技术和非测距技术的定位算法 2 4 1 基于测距技术的几种典型定位算法 基于测距技术的定位算法就是通过一些算法计算出信标节点和未知节点间 的确切距离。该算法对节点的定位可分为三步：第一步测距，未知节点通过一 些测距算法( 例如r s s i 算法【1 7 】、基于t o a 的算法和基于t d o a 的算法等) ， 计算出到邻居信标节点的距离；第二步定位，未知节点获得到三个以上信标节 点的距离后利用确定位置的算法( 如三边测量法和三角测量法等) 计算出未知 节点的位置；第三步坐标修正，对求出的未知节点的坐标进行算法修正，减小 节点的定位误差。在测量节点间的实际距离或方位时常采用下面几种算法： 1 ) 基于t o a 的定位：基于到达时间的定位机制。网络中的节点上都装有 时间同步装置，当未知节点发出一个信号时，接收节点就开始计时，假设发射 的信号的传播速度已知，则根据信号从发射节点到接收节点间的传播时间来计 算节点间的距离，然后利用已有的确定节点位置的算法计算出节点的坐标【1 8 】。 最简单的传播信号就是声波【1 9 】，其原理如图2 1 所示。 图2 - 1 声波测距原理 t o a 算法的优点是定位精度高，缺点是传感器节点需要添加额外的硬件， 使得节点的体积和功耗变大，成本增加；并且该算法要求节点间在时间上要保 持一致，这就对硬件提出了很高的要求。因此该算法不适合在大规模传感器网 络中应用。 2 ) 基于t d o a 的定位：基于到达时间差的测距技术。该技术实质上是t o a 技术的改进，其最大的优点是不再需要对时间进行同步。该技术中发送节点不 是发送一种信号，而是同时发送两种传播速度已知的信号，根据它们到达接收 节点的时间差来计算两个节点之间的距离，再通过确定节点位置的算法计算出 节点的位置l ”j 。 7 发送端接收端 t 1 图2 21 r i ) o a 定位原理 如图2 2 所示，阴影部分的宽度代表无线信号从发射节点到接收节点所需 要的时间( t 2 t 1 ) ，而阴影之间的距离代表两种信号到达接收节点的时间差。 发送节点在同一时间发射两种信号：无线信号l 和无线信号2 ，接收节点记录 这两种信号到达的时间t l ，t 2 ，并保存到节点中。假设这两种信号的传播速度 分别为c l ，c 2 ，则两点之间的距离可用公式2 1 求出。 一 m 、c g v 2 一l j 万等，( c l c 2 ) 公式( 2 1 ) l 1 一l 2 t d o a 定位技术虽然定位误差较小，定位比较准确，但该技术需要添加的 辅助硬件较多，网络成本比较大，能耗也较高。因此现阶段它也不适用于大规 模的无线传感器网络。 3 ) 基于a o a 的定位：该技术通过对接收节点中添加一些硬件设备，使得 该节点在收到发送节点发射的信号后，能判断信号是从那个方向发来的，从而 获得两节点之间的相对角度，然后利用确定节点位置的算法即三角测量法来计 算节点的坐标。该算法在实验环境中表现很好，但当节点被布置到真实环境时， 其定位误差就迅速增大。这是因为环境中的许多干扰因素会对节点发射的无线 信号造成干扰，导致角度测量出现很大偏差。而且在该算法中节点添加的硬件 较多，造成的节点的体积和网络成本都很大【2 0 1 。其原理如图2 3 所示。 一 图2 3a o a 定位原理 4 ) 基于r s s i 的定位技术：在传感器网络中，假设所有节点发出的信号强 度都是一定的，并且该信号强度是已知的，发出的信号被接收节点接收后，接 8 收节点就会将该信号的强度与初始信号强度进行对比，通过计算信号在传播过 程中的衰减来计算节点间的距离，信号衰减度与节点间距离的关系通过大量的 实验来获得。得出距离后再用确定节点位置的算法获得未知节点坐标。同样该 算法虽然在在实验环境中定位比较精确，而且能耗较低，但是在实际的应用环 境中由于节点发出的射频信号非常容易受到环境中温度、气压以及障碍物的影 响，所以该算法在真实的应用环境中表现并不理想。 2 4 2 基于非测距技术的几种典型定位算法 由以上分析可知基于测距的定位算法虽然能够对节点进行较精确的定位， 但该技术基本上都要靠节点添加额外的硬件来实现节点的定位，从而限制了节 点的体积，并且增加了节点的能耗，所以基于该技术的算法不能满足w s n 的 要求，基于非测距的定位技术就在这种需求下出现了。基于非测距的定位技术 不对节点间的距离进行精确计算，只是通过一些算法进行估算。在该技术下节 点并不需要添加额外硬件，从而减小了节点的体积和功耗，使得节点定位更加 稳定，且受环境影响较小，但节点的定位误差较测距技术的要更大。基于非测 距的定位算法大致可分为两种：一是通过质心算法，把未知节点假设成为周围 信标节点的质心，从而算出节点的坐标，但该方法在信标节点较少时定位误差 很大；二是首先通过算法估算出信标节点和未知节点之间的距离，然后再通过 定位算法计算节点坐标，该方法较一定位更精确，但所需的计算能耗更大。下 面介绍几种典型算法。 1 ) 质心算法【2 1 】：在传感器网络中，信标节点和未知节点是随机分布的， 一个未知节点周围总会或多或少存在一些信标节点，当未知节点收到足够数量 的信标节点的信息时，就将信标节点相互连接起来形成一个多边形，质心算法 的原理就是把这个多边形的质心作为该未知节点的坐标。 e d c 图2 4 质心定位算法 如图2 - 4 所示假设这些信标节点的坐标分别为a ( x l ，y 1 ) ，b ( x 2 ，y 2 ) ，c ( x 3 ，y 3 ) ， d ( x 4 ，y 4 ) ，e ( x 5 ，y 5 ) ，则可根据公式( 2 - 2 ) 计算出未知节点的坐标： 似力= 掣型掣，型型掣 ) 公式( 2 2 ) 质心算法是一种很特别的算法，它即不需要对未知节点与信标节点间的距离进行 计算，也不需要进行估算，只要未知节点周围存在足够多的信标节点，就可以直接算 出其位置坐标。该算法在信标节点密度较大的情况下还可以使用，一旦信标节点密度 降低，其定位误差就会迅速增大。该算法只适合对未知节点坐标进行大致估算。 2 ) d v - h o p 算法：是一种经典的非测距定位算法。其定位过程可分为三个 阶段：第一阶段：网络中的信标节点通过泛洪广播，使得网络中的未知节点得 到所有信标节点的未知信息；第二阶段：利用信标节点间的距离已知，根据信 标节点间的跳数，计算出未知节点与信标节点的实际跳段距离；再次通过泛洪 广播将计算的平均跳距发送，未知节点仅记录接收到的第一个平均跳距；第三 阶段：当未知节点收到三个或三个以上到信标节点的跳距时，使用确定节点位 置的算法计算节点坐标。d v _ h o p 算法的计算公式如下： f 旷瓦7 1 z 一v t x j1 + v i y j 1 红 j l 公式( 2 3 ) 其中( x i ，y i ) ，( x j ，y j ) 是信标节点的坐标，h 是两信标节点之间的跳数。 3 ) a m o r p h o u s 定位算法【2 2 j ：该算法是d v h o p 算法的一种特例。d v - h o p 算法中的第二步是对每跳平均距离进行估算，但该算法却是直接将节点的通信 半径假设成每跳平均距离，该算法在节点邻居节点较多的情况下所得的结果还 有一定的可取性，一旦邻居节点的数目减少，算法的定位误差就会迅速增加。 算法在高密度节点分布的情况下，定位精度还能符合应用的要求，而且还减少 了网络中的通信开销以及计算开销。但在中低密度下，算法就不再适用。 4 ) a p i t 定位算法【2 3 j ：该算法类似质心算法，但其定位精度要明显高与质 心算法。首先经过一次泛洪广播后，未知节点会获得周围所有信标节点的信息， 把这些信标节点组成一个集合，从中随机抽取三个组成一个三角形区域，通过 p i t 方法判断未知节点是否位于该三角形区域中，如果位于内部则将该三角形 保存，否则抛弃。然后再从集合中抽取另外的信标节点，如此反复，直到将组 合选完。然后将这些三角形叠加，如图2 5 所示，就会出现一多边形，将该多 边形的中心作为未知节点的坐标。 图2 5a p i t 算法 p i t 是用来判断节点是否位于三角形内部的方法，其具体实现方法是：如 果该节点沿着三角形的一条边的法线方向移动，当该节点同时靠近或者同时远 离三角形的三个顶点时，该节点位于三角形的外部，反之，只要不是同时远离 或靠近，就位于三角形内部。如图2 6 所示，节点n 沿着a b 这条边的法线方 向移动，若该节点同时接近或远离a b c 的三个顶点，则节点n 位于a b c 外 部，否则位于a b c 内部。 ， 、 j ，q 、 毋：一二：幻 ， ，7 ， 图2 - 6p i t 原理 2 4 3 确定节点位置的算法 在上面两小节中文章对节点定位的测距阶段所用到算法分别进行了介绍， 测距算法算出未知节点与若干信标节点的距离后，就要通过第二阶段的确定节 点位置的算法对节点的位置进行计算。此阶段常用的算法有三边测量法、三角 测量法和多边形算法等。 ( 1 ) 三边测量法( t r i l a t e r a t i o n ) 【2 4 】：利用节点到三个不在同一条直线上的 信标节点的距离来确定未知节点的坐标。如图2 7 所示，经过定位的第一阶段 后，三个信标节点的坐标a ( x o ，y o ) 、b ( x l ，y 1 ) 、c ( x 2 ，y 2 ) 已知，且未知 节点d 到三个信标节点的距离d o 、d l 、d 2 也己算出，则可以利用公式2 4 算出 未知节点坐标。 7 一、 ， | ， f i l 、 l l g 一) 2 + 一) 2 = “ 、f 堡二兰! 垒二苎! = 盔 公式。2 4 ， l b 一恐) 2 + 一弘) 2= 畋 ( 2 ) 三角测量法【2 5 ：三角测量法( t r i a n g u l a t i o n ) 需要添加额外的硬件， 但其在节点定位的第一阶段不是计算未知节点到信标节点的距离，而是计算角 度，最后计算节点坐标。已知a ( x o ，y o ) 、b ( x l ，y 1 ) 、c ( x 2 ，y 2 ) 和未知节 点d 相对于节点a 、b 、c 的角度么a d c 、么a d b 和么b d c 。算法如图2 8 所 图2 8 三角测量法原理 从上图中可以看到，对于a b c 如果未知节点在其内部，则弧b d c 也位于 三角形内部。那么就能够确定一个且唯一的一个以0 1 ( x o l ，y 0 1 ) 为圆心，以r o 为半径的圆，由此可得么b 0 l c 的角度a = ( 2 7 c 2 么b d c ) ，并有如下公式。 l k 飞) 2 + 眈叫) 2 = k 吨) 2 十k 惕) 2 = l 瓜哥石哥= 牙一暂c 。瓯公式q 。5 l 由上式可得o l 的坐标以及半径r o 。同理可获得0 2 和0 3 的坐标以及r l 和 r 2 。最后算出未知节点d 的坐标。 ( 3 ) 多边形算法：多边形算法是在三边测量法的基础上发展而来的，当信 标节点的数量超过三个时，通过定义方程组，利用多次的方程计算能够更精确 地计算节点的位置。假设未知节点坐标是( x ，y ) ，信标节点坐标分别为( x o ， y o ) ，( x l ，y 1 ) ，( x k ，y k ) ，未知节点到信标节点的距离分别是r o ，r l ， r k 。我们可以得到一组方程： 厂1 = 厂2 = 吆 = 公式( 2 6 ) 可以线性化为：a x = b 6 = 彳= 一2 g o 一) g 。一k ) g 一砟) 其中： o y 七) ( y 。一y 七) 一y 七) 222 22 2 _ 一珞一+ x 七一m + 少七 222 222 眨一一x 2 + x 七一y 2 + y j | ，) 吃一1 一一一l + x 七一少七一1 + y 七 2 4 4 定位算法的对比 ( 1 ) 基于测距技术的定位算法对比 表2 - 1r a n g e - b a s e d 定位算法对比 公式( 2 6 ) 公式( 2 7 ) 公式( 2 8 ) 算法 r s s it o at d o aa o a 精度低很高高局 能耗较小很大很大大 网络成本低高高尚 环境因素影响很大大大大 r s s i 算法的能耗较小，而且网络成本较低，符合传感器网络对节点的 要求。但其定位精度较低，尤其是在真实环境中，由于受环境影响较大 的缘故，使得其定位很不稳定1 2 6 j ； t o a 技术不仅需要节点添加额外的硬件，而且还要求节点之间有很好的 时间同步，虽然定位精度很高，但节点的成本和功耗都较大，不符合网 络对节点的要求； t d o a 技术受环境的影响很大，使得节点定位不稳定，虽然其定位精度 高，但其对节点能量和体积都有很大的要求； a o a 技术需要对节点添加很多的硬件设备，造成节点的能耗和体积都 很大，而且成本也很高，虽然定位精度较高，但受环境的影响大，定位 不稳定。 从上面的分析结果可以看出基于测距算法的定位技术并不适用于对节点有 低功耗、低成本和微体积要求的大规模无线传感器网络节点的定位。 ( 2 ) 基于非测距技术的定位算法对比 通过以上介绍，可以对基于非测距技术的定位算法有了一定的了解，下面 就对所介绍的几种典型算法进行对比分析。 表2 - 2 r a n g e - f r e e 定位算法对比 算法质心 d v h o p a m o 印h o u s a p i t 定位精度一般良好一般良好 节点定位比例低较高较高一般 节点能耗最小最大大大 信标节点影响 较大较