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

摘要 无线传感器网络( w s n ) 作为一种全新的信息获取和处理平台，广泛应用在环 境恶劣、不可到达领域，实现监测与跟踪任务。在这些应用中，节点位置的确定扮 演着重要角色，因此，对w s n 节点自身定位的研究具有非常重要的实用价值。本 文在分析基于测距技术的w s n 定位算法和无需测距技术的w s n 定位算法基础 上，重点对基于测距技术的移动w s n 节点定位算法进行了研究。 首先，在查阅大量相关文献的基础上，本文综述了w s n 定位技术的国内外研 究现状，介绍了w s n 定位系统和算法的性能评价标准和分类方法，并详细分析和 讨论了近年来该领域具有代表性的算法。 其次，考虑w s n 中的节点随机均匀部署在野# 1 - - 维特定应用环境，信标节点 固定，未知节点采用随机漫步模型，提出了一种到主信标节点信号强度差定位算 法( s s d l b ) 与运动预测定位算法( m p l ) 相结合的基于分布式的高覆盖率移动 w s n 节点定位算法。在定位过程中，信标节点周期性地向网络中发送报文，未知 节点在定位时刻接收邻居信标节点发送的报文，然后根据未知节点的邻居信标节 点的个数( n ) 采用不同的定位方法：当n 3 和一3 且不共线情形，采用s s d l b 定位算法；当n 3a n dn = 3 ( n o te o l l i n e a r ) ，i tu s e ss s d l ba l g o r i t h m ； w h e nn f i 9 2 3t h es e n s o rn e t w o r kp r o t o c o ls t a c k 3 1 i 图2 3 传感器网络协议栈【3 1 j 广1 ； | 雕| i 络 ；剐 理 | | l j 湖南科技大学硕士学位论文 任务管理平台：在一个给定的区域内平衡和调度监测任务。 图2 3 ( b ) 是在上一种协议栈的基础上经过改进得到的另一种协议栈模型。 3 、w s n 的特点 目前常见的无线网络包括移动通信网、无线局域网、蓝牙网络、a do c 网络等， 与这些网络相比，w s n 具有以下特点： ( 1 ) 硬件资源有限。节点由于受价格、体积和功耗的限制，其计算能力、存储 空间和内存空间比普通的计算机功能要弱很多。这就决定了在节点操作系统设计 中，协议层次不能太复杂。 ( 2 ) e g 源容量有限。w s n 节点一般由电池供电，电池的容量一般不是很大。其 特殊的应用领域决定了在使用过程中，不能给电池充电或更换电池，一旦电池能 量用完，这个节点也就失去了作用。因此在传感器网络设计的基本原则都要以节 能为前提。 ( 3 ) 无中心。w s n 中没有严格的控制中心，所有节点地位平等，是一个对等式 网络，节点可以随时加入或离开网络，任何节点的故障不会影响整个网络的运行， 具有很强的抗毁性。 ( 4 ) 自组织。网络的布设和展开无需依赖于任何预设的基础设施：节点通过分 层协议和分布式算法协调各自的行为，节点开机后就可以快速、自动地组成一个 独立的网络。 ( 5 ) 多跳路由。网络中节点通信距离有限，一般在几百米范围内，节点只能与 它的邻居直接通信。如果希望与其射频覆盖范围之外的节点进行通信，则需要通 过中间节点进行路由。常用网络的多跳路由是使用网关和路由器来实现，而w s n 中的多跳路由是由普通网络节点完成的，没有专门的路由设备。这样每个节点既 可以是信息的发起者，也是信息的转发者。 ( 6 ) 动态拓扑。w s n 是一个动态的网络，节点可以随处移动。一个节点可能会 因为电池能量耗尽或其他故障，退出网络运行；一个节点也可能由于工作需要而 被添加到网络中。这些都会使网络的拓扑结构随时发生变化，因此网络应该具有 动态拓扑组织功能。 ( 7 ) 节点数量众多，分布密集。为了对一个区域执行监测或跟踪任务，往往有 成千上万传感器节点部署到该区域。传感器节点分布非常密集，利用节点之间高 度连通性来保证系统的容错性和抗毁性。 2 2无线传感器网络节点定位的基本原理 w s n 中现有绝大多数的节点定位方法都包含两个基本步骤：( 1 ) 距离( 或角 度) 测量；( 2 ) 定位计算。下面将从这两个方面论述节点定位的基本原理。 第二章无线传感器网络节点定位技术概述 2 2 1 基本概念描述 在w s n 节点自身定位算法的研究中，根据节点是否已知自身的位置信息，把 传感器节点分类为信标节点( b e a c o nn o d e ) 和未知节点( u n k n o w nn o d e ) 。信标节点 通过人工部署或配置g p s 定位设备等手段获得自身的精确位置信息，它们在w s n 中所占的比例比较小，其部署目的就是协助未知节点进行定位。而分布在w s n 中 的未知节点则是依靠信标节点提供的辅助信息，按照一定的算法来计算得到自身 的估计位置。信标节点和未知节点在w s n 中的部署情况如图2 4 示。 信标节点 0 未知节点 f i 9 2 4b e a c o nn o d e sa n du n k n o wn o d e ss c a t t e r e di nw s n 图2 4w s n 中信标节点和未知节点的分布 其他的相关概念1 3 1 1 包括： 邻居节点( n e i g h b o rn o d e ) ：指传感器节点通信半径内的所有其他节点； 跳数( h o pc o u n t ) ：指两个节点之间间隔的跳段总数： 跳段距离( h o pd i s t a n c e ) - 指两个节点之间间隔的各跳距离之和： 堪础设施( i n f r a s t r u c t u r e ) ：指协助传感器节点定位的已知自身位置的固定设施； 到达时间( t i m eo fa r r i v a l ，t o a ) 指信号从一个节点传播到另一个节点所需 的时间； 到达时间差( t i m ed i f f e r e n c eo fa r r v i a l ，t d o a ) ：指两种不同传播速度的信号 从一个节点传播到另一个节点所需要的时间之差； 接受信号强度指数( 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 ，r s s i ) ：指节点接收到的 无线信号的强度大小： 到达角度( a n g l eo f a r r i v a l ，a o a ) ：指节点接受到的信号相对于自身轴线的角 度； 视线关系( 1 i n eo fs i g h t ，l o s ) ：指两个节点之间没有障碍物间隔，能够直接 无线通信，称为两个节点间存在视线关系： 非视线关系( n ol i n eo fs i g h t ，n l o s ) ：指两个节点之间存在障碍物； 测距误差( r a n g ee r r o r ) ：指测距的误差值与节点的通信半径的比值： 定位误差( p o s i t i o ne r r o r ) ：指定位算法计算的坐标与实际坐标的误差值与节点 的通信半径的比值。 湖南科技大学硕士学位论文 2 2 2节点间距离( 或角度) 的测量方法 在无线传感器网络中，节点间距离或角度的测量技术常用的有r s s i 【”l 、 t o a 9 1 、t d o ae 1 8 l 和a o a t l 8 , 1 9 。 r s s i t l 7 l ( 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 ) ：已知发射功率，在接收节点测 量接收功率，计算传播损耗，使用理论或经验的信号传播模型将传播损耗转化为 距离，该技术主要使用r f 信号。因传感器节点本身具有无线通信能力，故其是一 种低功率、廉价的测距技术，r a d a r t 3 引、s p o t o n t 3 3 】等许多项目中使用了该技术。 它的主要误差来源是环境影响所造成的信号传播模型的建模复杂性：反射、多径 传播、非视线关系( n l o s ) ，天线增益等问题都会对相同的距离产生显著不同的 传播损耗。通常将其看作为一种粗糙的测距技术，有可能产生5 0 的测距误差。 t o a t 9 1 ( t i m eo fa r r i v a l ) ：该技术通过测量信号传播时间来测量距离。使用 t o a 技术最基本的定位系统是g p s ，g p s 系统需要昂贵、高能耗的电子设备来精 确同步卫星时钟。因w s n 节点硬件尺寸、价格和功耗限制，g p s 和其他t o a 技 术对无线传感器网络而言几乎是不可行的。 t d o a f 8 】( t i m ed i f f e r e n c eo na r r i v a l ) ：t d o a 测距技术被广泛应用在w s n 的定位方案中。w s n 在利用t d o a 技术测量节点间距时与蜂窝无线网络的移动台 定位和机器人导航定位不同。如图2 5 所示，一般是在节点上安装超声波收发器和 r f 收发器。测距时，在发射端两种收发器同时发射信号，利用声波与电磁波在空 气中传播速度的巨大差异在接收端通过记录两种不同的信号( 常使用r f 和超声波 信号) 到达时间差异，基于己知信号传播速度，直接把时间转化为距离。已有多 种定位算法使用t d o a 实现测距。该技术的测距精度较r s s i 高，可达到厘米级， 但受限于超声波传播距离有限( 超声波信号通常传播距离仅为2 0 3 0 英尺，因而 网络需要密集部署) 和n l o s 问题对超声波信号的传播影响。虽然己有发现并减 轻n l o s 影响的技术，但都需要大量计算和通信开销，不一定适用于低功耗的w s n 应用中。 发射端 接收端 r a d i o 信号 超声波脉冲 f i 9 2 5t d o ae s t i m a t i o nt e c h n o l o g y 图2 5t d o a 测距技术 a o a 埔，1 9 1 ( a n g l eo fa r r i v a l ) ：这是一种估算邻居节点发送信号方向的技术， 第二章无线传感器网络节点定位技术概述 可以通过天线阵列或多个接收器结合来实现，除定位外，还能提供节点的方向信 息，如m i t 的t h ec r i c k e tc o m p a s s 等项目中就利用多个接收器提出了基于a o a 的硬件解决方案，其原型系统可在4 0 。角内以5 。的误差确定接收信号的方 向。同样，a o a 技术也受外界环境影响，如噪声、n l o s 问题等都会对测量结果 产生不同影响。同时，a o a 需要额外硬件，在硬件尺寸和功耗上可能无法用于传 感器节点。 以上四种测距方法各有利弊，以r s s i 和t d o a 两种方法最为常用。 2 2 3 节点定位计算方法 在传感器节点定位过程中，当未知节点在获得邻近信标节点的距离时，可以 采用三边测量法( t r i l a t e r a t i o n ) 或极大似然估计法( m u l t i l a t e r a t i o n s ) 来计算未知 节点位置；未知节点在获得邻近信标节点的角度时，可以采用三角测量法 ( t r i a n g u l a t i o n ) 来计算未知节点位置。 1 、三边测量法 三边测量法( t r i l a t e r a t i o n ) 如图2 6 所示，已知彳，曰，c 三个信标节点的坐标 分别为：o 。，) ，。) ，o 。，y 。) ， 。，) ，。) ，以及它们到未知节点d 的距离分别为d a , d 。，d 。， 假设未知节点d 的坐标为伍，) ，) ，那么存在下列公式： 瓜i 了瓦j 了；d 。 厄i 丁石j 了d 。 拓j 了瓦j 了d 。 ( 2 1 ) 由( 2 1 ) 可以得到未知节点d 的坐标为： e 一 呈s 芝二量；慕：二羹；】以 薹二喜：；二；：兰；二三主】 c 2 2 ， f i 9 2 6m e a s u r e m e n to ft h et r i l a t e r a l 图2 6 三边测量法 2 、极大似然估计法 l f i 9 2 7m a x i m u ml i k e l i h o o de s t i m a t i o n 图2 7 极大似然估计法 极大似然估计法( m a x i m u ml i k e l i h o o de s t i m a t i o n ) 如图2 7 所示，已知1 , 2 ，3 ，以 个信标节点的坐标分别为 ，y ，) ，o ：，y ：) ， ，y ，) ，x n ，y 。) ，它们到未知节点d 的距 离分别为：d l , d 2 ，d3 一d 。，假设未知节点d 的坐标为o ，y ) 。那么存在下列公式： 湖南科技大学硕士学位论文 f g ，一z ) 2 + ( y 。- y ) 2 一d ? i ( 2 4 ) l o 。一z ) 2 + ( y 。一) ，) 2 一d ： k 一2 2 ( x l x n h + y 2 一y 2 2 ( y 1 - y 。) ) ，- d ? 一d ： !( 2 5 ) i 巧2 一l 一2 2 0 乇一1 一x n 冷+ y 2 l y ：一2 ( y 。1 一y 。) yt d 二1 一d ： 彳= 【三：二二：，差三_ ：， ，6 一i 卜x 1 2 1 - - ，g 一2 石： 1 + y ? y i ，2 一y ：+ 2d ：一2d l ，】，x 2 ；】 j = 似r 彳) 一1 a 丁b 厄再百i 万一 厄再百而，l ( 2 3 阮一t ) 2 + ( y 。- y 。) 2 一轨2 - 2 1 1 2 c o s ( x 由( 2 3 ) 能够确定圆心o l 点的坐标和半径 。同理对于节点a ，b ，角z a d b 和b ，c 和角厶m c 分别所确定的圆心0 2 0 0 2 ，y 。：) 、半径r 2 与圆心0 ，0 0 3 ，y 0 3 ) 、半径，3 ， 1 l ，1 ) ， f i 9 2 8m e a s u r e m e n to ft r i a n g u l a t i o n 图2 8 三角测量法 第二章无线传感器网络节点定位技术概述 最后利用三边测量法，由点d ( x ，y ) ，0 1 ( x o i ，y 0 1 ) ，0 2 ( x 0 2 ，y 屯) ，0 3 ( x q ，) 0 3 ) 确 定未知节点d 的坐标。 2 3 本章小结 本章首先从w s n 的体系结构、协议层次、特点以及节点的体系结构来对w s n 作了一个总体的概述，然后介绍了w s n 节点定位基本原理，并详细叙述了常用的 节点间距离或角度的测量方法：r s s i 1 7 】、t o a t 9 l 、t d o a 8 和a o a t l 8 1 9 1 ，以 及节点定位计算方法：三边测量法、极大似然估计法和三角测量法。 湖南科技大学硕士学位论文 第三章无线传感器网络自身定位算法相关内容研究 本章将从w s n 自身定位系统和算法的性能评价标准开始，对这一领域现有典 型定位算法进行分析和比较，并讨论不同算法在不同应用中的优劣。 3 1 现有无线传感器网络自身定位系统和算法的性能评价 w s n 自身定位系统和算法的性能直接影响其可用性，如何评价它们是一个需 要深入研究的问题。下面定性地讨论几个常用的评价标准。 定位精度一一定位技术首要的评价指标就是定位精度，一般用误差值与节点 无线射程的比例表示，例如，定位精度为2 0 表示定位误差相当于节点无线射程 的2 0 。也有部分定位系统将二维网络部署区域划分为网格，其定位结果的精度 也就是网格的大小，如微软的r a d a r l 3 2 1 ，w i r e l e s sc o r p o r a t i o n 的r a d i o c a m e r a 等。 规模一一不同的定位系统或算法也许可在园区内、建筑物内、一层建筑物或 仅仅是一个房间内实现定位。另外，给定一定数量的基础设施或在一段时间内， 一种技术可以定位多少目标也是一个重要的评价指标。例如，r a d a r 3 2 1 系统仅可 在建筑物的一层内实现目标定位，剑桥的a c t i v eo f f i c e l 3 4 1 定位系统每2 0 0 m s 定位 一个节点。 - 信标节点密度一一信标节点定位通常依赖人工部署或g p s 实现。人工部署信 标节点的方式不仅受网络部署环境的限制，还严重制约了网络和应用的可扩展性。 而使用g p s 定位，信标节点的费用会比普通节点高两个数量级【z l ，这意味着即使 仅有1 0 的节点是信标节点，整个网络的价格也将增加1 0 倍。因此，信标节点密 度也是评价定位系统和算法性能的重要指标之一。 节点密度在w s n 中，节点密度增大不仅意味着网络部署费用的增加，而 且会因为节点间的通信冲突问题带来有限带宽的阻塞。节点密度通常以网络的平 均连通度来表示。许多定位算法的精度受节点密度的影响，如d v - h o p 算法【z 】仅 可在节点密集部署的情况下合理地估算节点位置。 定位覆盖率( c o v e r a g e ) 定义为可实现定位的未知节点与未知节点总数的 比例。尽管密集部署是w s n 的特点之一，但总会有一些不可达或连通度极低( 小 于3 ) 的未知节点存在，除这些节点，实现尽可能多的未知节点的精确定位也是自 身定位算法和系统的追求目标之一。 容错性和自适应性一一通常，定位系统和算法都需要比较理想的无线通信环 第三章无线传感器网络自身定位算法相关内容研究 境和可靠的网络节点设备。但在真实应用场合中常会有诸如以下的问题：外界环 境中存在严重的多径传播、衰减、非视距( n l o s ) 、通信盲点等问题；网络节点 由于周围环境或自身原因( 如电池耗尽、物理损伤) 而出现失效的问题；外界影 响和节点硬件精度限制造成节点间点到点的距离或角度测量误差增大的问题。由 于环境、能耗和其他原因，物理地维护或替换传感器节点或使用其他高精度的测 量手段常常是十分困难或不可行的。因此，定位系统和算法的软、硬件必须具有 很强的容错性和自适应性，能够通过自动调整或重构纠正错误、适应环境、减小 各种误差的影响，以提高定位精度。 功耗一一对w s n 的设计和实现影响最大的因素之一。由于传感器节点电池能 量有限，因此在保证定位精度的前提下，与功耗密切相关的定位所需的计算量、 通信开销、存储开销、时间复杂性是一组关键性指标。 代价一一定位系统或算法的代价可从几个不同方面来评价。时间代价包括一 个系统的安装时间、配置时间、定位所需时间。空间代价包括一个定位系统或算 法所需基础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一种定位 系统或算法的基础设施、节点设备的总费用。 上述8 个性能指标不仅是评价w s n 自身定位系统和算法的标准，也是其设计 和实现的优化目标。为了实现这些目标的优化，有大量的研究工作需要完成。同 时，这些性能指标是相互关联的，必须根据应用的具体需求做出权衡，以选择和 设计合适的定位算法。 3 2 现有无线传感器网络自身定位系统和算法的分类 1 、基于测距( r a n g e - b a s e d ) 的定位和无需测距( r a n g e f r e e ) 的定位【1 6 l 基于测距的定位通过测量节点间点到点的距离或角度信息，使用三边测量 ( t r i l a t e r a t i o n ) 、三角测量( t r i a n g u l a t i o n ) 或最大似然估计( m u l t i l a t e r a t i o n ) 定位 法计算节点位置：无须测距的定位则无须距离和角度信息，仅根据网络连通性等 信息即可实现。前者常用的测距技术有r s s i 【1 7 l ，t o a 【9 l ，t d o a s 和a o a p s ，1 9 1 。 为了采用基于测距的定位算法，就必须在传感器节点上额外配备测距装置，这在 一定程度上增加了节点的成本和功耗，并且由于目前的测距技术误差比较大，这 直接影响了节点定位的精度，一般的做法是通过多次测量和循环定位求精来减小 测距误差对定位的影响，但这一过程又需要额外的计算量和通信量。基于测距的 定位算法与无需测距的定位算法相比虽然有着成本较高、能耗较高、计算量和通 信量较大的不足，但是前者的定位精度一般都要比后者高。可以相信，随着技术 进步，更精确、能耗更小的测距技术的出现，以及对定位精度的更高要求，基于 测距的定位算法将获得更好的发展空间。 湖南科技大学硕士学位论文 目前对于两种定位方式的研究都出了很多成果，例如基于测距的定位系统和 算法有c r i c k e t 定位系统 3 5 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 ) 相对定位算法【矧、 t w o p h a s ep o s i t i o n i n g 定位算法1 3 7 1 、n h o pm u l t i l a t e r a t i o np r i m i t i v e 定位算法1 3 8 1 和 t p s 定位算法 3 9 1 等；无需测距的定位算法有a p s 算法集1 4 0 1 中的d v - h o p 定位算法 1 2 1 、m d s m a p 算法【4 1 1 和凸规划( c o n v e xo p t i m i z a t i o n ) 7 】等。 2 、集中式计算的定位与分布式计算的定位 4 2 1 集中式计算的定位是指把所需信息传送到某个中心节点( 例如，一台服务器) ， 并在那里进行节点定位计算的方式；分布式计算的定位是指依赖节点间的信息交 换和协调，由节点自行计算的定位方式。集中式计算的优点在于从全局角度统筹 规划，计算量和存储量几乎没有限制，可以获得相对精确的位置估算。它的缺点 包括与中心节点位置较近的节点会因为通信开销大而过早地消耗完能量，导致整 个网络与中心节点信息交流的中断，无法实时定位等【叫。集中式定位算法包括凸 规划1 7 1 ，m d s m a p 4 1 1 等。n h o pm u l t i l a t e r a t i o np r i m i t i v e 3 a l 定位算法可以根据应用 需求采用两种不同的计算模式。 3 、基于信标节点的定位和无信标节点的定位【，- l 基于信标节点的定位与无信标节点的定位是从定位手段上是否采用信标节点 来进行分类。基于信标节点的定位算法在定位过程中使用了信标节点，并以它作 为定位中的参考点，各未知节点定位后产生整体绝对坐标系统；无信标节点的定 位算法不用部署信标节点，它依靠节点间的相对位置，以网络中的某些节点作为 参考点，形成局部坐标系，相邻的局部坐标系再依次转换合并，最后产生整体相 对坐标系统。 3 3 现有典型无线传感器网络自身定位算法分析 3 1 1 基于无需测距的定位算法分析 距离无关的定位技术无需测量节点间的绝对距离或方位，降低了对节点硬件 的要求，但定位的误差也相对有所增加。目前提出了两类主要的距离无关的定位 方法：一类方法是先对未知节点和信标节点之间的距离进行估计，然后利用三边测 量法或极大似然估计法进行定位；另一类方法是通过邻居节点和信标节点确定包含 未知节点的区域，然后把这个区域的质心作为未知节点的坐标。 1 、质心定位算法【2 0 1 质心法【2 0 j 是南加州大学n i r u p a m ab u l u s u 等学者提出的一种仅基于网络连通 性的室外定位算法。该算法的中心思想是：未知节点以所有在其通信范围内的信 标节点的几何质心作为自己的估计位置。多边形a b c d e 的顶点坐标分别为： 彳 l ，y 1 ) ，a ( x 2 ，y 2 ) ，c ( x 3 ，y 3 ) ，o ( x 。，y 。) ，e ( x 5 ，y 5 ) ，其质心坐标为： 第三章无线传感器网络自身定位算法相关内容研究 仅，y ) 。芦兰坐生三生三! ! 羔2 兰! ! ! 岛 ( 3 1 ) 7 、 5 。 5 7 质心定位算法首先确定包含未知节点的区域，计算这个区域的质心，并将其作为 未知节点的位置。在质心定位算法中，信标节点周期性地向临近节点广播信标分 组，信标分组中包含信标节点的标识号和位置信息。当未知节点接收到来自不同 信标节点的信标分组数量超过某一门限或接收一定时间后，就确定自身位置为这 些信标节点所组成的多边形的质心。由于质心算法完全基于网络连通性，无需信 标节点和未知节点之间的协调，因此简单、易于实现，但需要较多的信标节点。 2 、d v - h o p 定位算法【2 l 】 d v - h o p 算法【2 1 l 由d n i c u l e s c u 和b n a t h 等人提出的，其算法原理与经典的距 离矢量路由算法比较相似。算法分3 个阶段。首先使用典型的距离矢量交换协议， 使网络中所有节点获得距信标节点的跳数。第2 阶段，在获得其他信标节点位置 和相隔跳距之后，信标节点计算网络平均每跳距离，然后将其作为一个校正值广 播至网络中。校正值采用可控洪泛法在网络中传播，这意味着一个节点仅接受获 得的第1 个校正值，而丢弃所有后来者，这个策略确保了绝大多数节点可从最近 的信标节点接收校正值。在大型网络中，可通过为数据包设置一个t t l 域来减少 通信量。当接收到校正值后，节点根据跳数计算与信标节点之间的距离。当未知 节点获得与3 个或更多信标节点的距离时，则在第3 阶段执行三边测量定位。 如图3 1 所示，已知信标节点l l 与l 2 ，l 3 之间的距离和跳数。l 2 计算得到 校正值( 即平均每跳距离) ( 4 0 + 7 5 ) ( 2 + 5 ) = 1 6 4 2 。在上例中，假设a 从l 2 获得校正 值，则它与3 个信标节点之间的距离分别为l 1 3 1 6 4 2 ，l 2 2 1 6 4 2 ，1 , 3 3 1 6 4 2 ，然后使用三边测量法确定节点a 的位置。 f i 9 3 1d v o h o pa l g o r i t h m f i 9 3 2b o u n d i n gb o xl o c a l i z a t i o na l g o r i t h m 图3 1d v o h o p 算法图3 2b o u n d i n gb o x 定位算法 d v h o p 算法与基于测距算法具有相似之处，都需要获得未知节点到信标节点 的距离，但是d v h o p 获得距离的方法是通过网络中拓扑结构信息的计算而不是 通过无线电波信号的测量。在基于测距的方法中，未知节点只能获得到自己射频 覆盖范围内的信标节点的距离，而d v h o p 算法可以获得到未知节点无线射程以 外的信标节点的距离，这样就可以获得更多的有用数据，提高定位精度。 湖南科技大学硕士学镶论文 3 、d v - d i s t a n c e 定位算法f 刎 d v - d i s t a n c e 算法l 蚓与d v - h o p 算法1 2 1 】l 类似，所不同的是相邻节点使用r s s i 测量节点闻点到点距离，然瑶利用类似于距离矢量路由的方法传播与信标节点的 累计距离。当未知节点获得与3 个或更多信标节点的距离后使用三边测量定位。 d v - d i s t a n c e 算法也仅适用予各向同性的密集爨络。实验显示，该算法豹定位耩度 为2 0 ( 网络平均连通度为9 ，信标节点比例为1 0 ，测距误差小于1 0 ) ；但随着 测距误差的增大，定位误差也急剧增大。 4 、a p i t 定位算法f l q 近似三角形内点测试法( 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 p i t ) 首先 确定多今包含未知节点的三是形区域，这些三热形区域的交集是一个多边形，它 确定了更小的包含未知节点的区域；然后计算这个多边形区域的质心，并将质心 律舞来知苇点的链黑。 a p i t 定位具体步骤： 、 s t e p l收集信息：未知节点收集临近信标节点的信息，如位置、标识号、接 收到的信号强度等，邻居节点之闻交换各鸯接收到豹信标节点的信患； s t e p 2 a p i t 测试：测试未知节点是否在不同信标节点组合成的三角形内部； s t e p 3 计算重叠区域：统计包食来知繁点豹三角形，谤算所有三角形的重叠 区域； s t e p 4 计算未知带点位置；计算重叠区域的震心位置，作势未知节点的位置。 在无线信号传播模式不规剐和传感器节点随机部署的情况下，a p i t 算法的定 位精度高，性能稳定，但a p i t 测试对网络的连通性提出了较高的要求。 s 、b o u n d i n gb o x 定位算法f 嘲 b o u n d i n gb o x 定义了一个特殊的通信模型，假定节点通信范围是以囟己为中 心、二倍逶蔷半径建边长辩正方形，称为离教遴信模型。如果一个节点熊够与a 个信标节点通信，则该节点在这a 个信标节点的正方形通信区域的交叠矩形区域 中，如图3 2 所示。该区域可通过公式( 3 。2 ) 褥到，节点以该区域的中心作为自己的 估测像置。 m a x o f - g ) ，m a x t y l 一尺) 】 m i n ( x , + r ) ，m i n ( y i + 尺) jl - l 2 ，“ ( 3 2 ) 这种算法的计算和通露量都禳夸，两且哭接收溃息( 接收毙发送麓耗低) ，符台 传感器网络低功耗的要求。采用分布式本地计算方式，可扩展性好，定位时间延 迟与网络规模无关。但是这两种算法是典型的受信标节点稀疏阕题限制算法，定 位精度严重依赖予信标节点的密度和分布情况。 6 、a m o r p h o u s 定位算法【1 8 l a m o r p h o u s 定德算法也分淹三个阶段： 第一阶段，采用与d v - h o p 算法类似的方法获得距离信标节点的最小跳数， 第三章无线传感器网络自身定位算法相关内容研究 称为梯度值。 第二阶段，未知节点收集邻居节点的梯度值，计算关于某个信标节点的局部 梯度平均值，如公式( 3 3 ) 所示。 皇，+ 吃 毋一# 型 一o 5 ( 3 3 ) l n b r s ( i ) l + 1 其中，甩6 船“) 表示节点i 的邻居集； h ：表示节点f 与信标节点间的跳数； h ；表示邻居节点f 与该信标节点间的跳数。 第三阶段，与d v - h o p 算法不同的是，a m o r p h o u s 算法假定预先知道网络的密 度，然后离线计算网络的平均每跳距离。当获得3 个或更多信标节点的梯度值以 后，未知节点计算与每个信标节点的距离，并使用三边测量法和极大似然估计法 估算自身位置。 该算法使用的模型比d v - h o p 更合理，但是要离线计算平均每跳距离，可扩展 性差。 7 、凸规划定位算法【训 该算法由加州大学伯克利分校的d o h e r t y 等人提出。基本思想是将节点到节点 的通信连接看作节点位置的几何约束，把整个网络模型化为一个凸集，从而将节 点定位问题转化为凸约束优化问题，然后使用半定规划和线性规划方法得到一个 全局优化的解决方案，确定未知节点的位置。它根据未知节点与信标节点之间的 通信连接和节点无线射程，计算出未知节点可能存在的区域( 图3 3 中阴影部分) ， 并得到相应矩形区域，然后以矩形的质心作为未知节点的位置。 凸规划是一种集中式定位算法，在信标节点数比例占1 0 的以上时，定位精 度可以接近实际值。为了保证凸规划算法高效工作，信标节点应尽力放置在网络 的边缘，否则节点的位置估算会向网络中心偏移。 作为对凸规划算法的改进，文献【4 5 1 中提出了将节点间没有通信连接但同样视 为节点位置约束的思想来提高定位精度。 f i 9 3 3c o n v e xo p t i m i z a t i o na l g o r i t h m 图3 3 凸规划定位算法 f i 9 3 4e u c l i d e a na l g o r i t h m 图3 4 e u c l i d e a n 定位算法 湖南科技大学硕士学位论文 8 、m d s m a p 定位算法【4 l l m d s m a p 是一种集中式定位算法，可在r a n g e - f r e e 和r a n g e b a s e d 两种情况 下运行，并可根据情况实现相对定位和绝对定位。它采用了一种源自心理测量学 和精神物理学的数据分析技术多维定标( m u l t i d i m e n s i o n a ls c a l i n g ) ，该技术常 用于探索性数据分析或信息可视化。 m d s m a p 定位算法可分为如下三个步骤： s t e p l ：首先从全局角度生成网络拓扑连通图，并为图中每条边赋予距离值。 当节点具有测距能力时，该值就是测距结果。当仅拥有连通性信息时，所有边都 赋值为1 ，然后使用最短路径算法，生成节点间距离矩阵。 s t e p 2 ：对节点间距离矩阵应用m d s 技术，生成整个网络的2 维或3 维相对 坐标系统。 s t e p 3 当拥有足够的信标节点时( 2 维至少需要3 个，3 维至少需要4 个) ，将 相对坐标系统转化为绝对坐标系统。 该算法在节点密集的w s n 中，即网络连通度较高时具有较高的定位精度，因 此，该算法适合节点数较多、节点高密度分布的大规模网络。 9 、e u c l i d e a n 定位算法【删 e u c l i d e a n 定位算法给出了计算与信标节点相隔两跳的未知节点位置的方法。 假设节点拥有r s s i 测距能力，如图3 4 所示，已知未知节点b ，c 在信标节点l 的无线射程内，b c 距离已知或通过r s s i 测量获得；节点a 与b ，c 相邻。对于 四边形a b c l ，所有边长和一条对角线b c 已知，根据三角形的性质可以计算出 a l 的长度( 节点a 与l 的距离) 。使用这种方法，当未知节点获得与3 个或更多 信标节点之间的距离后就可以进行节点定位。 3 1 2 基于测距的定位算法分析 1 、基于非度量多维标度的w s n 节点定位算法【4 7 1 文献【4 7 】提出了n m d s - r s s i ( n o n m e t r i cm u t l t i d i m e n s i o n a ls c a l i n ga n dr e c e i v e d s i g n a ls t r e n g t hi n d i c a t i o n ) 定位算法，它利用非度量多维标度技术直接根据无线信号 强度值来进行节点的定位，避开了以前利用无线信号强度的定位算法中先把信号 强度转换成距离再进行定位所带来的计算误差和计算开销。仿真与真实传感器节 点的实验结果显示算法取得了较好的定位效果。 2 、基于信号强度差的w s n 节点定位算法【船l 文献l 船l 利用无线信号强度实现了煤矿安全监测w s n 节点间的自定位，在现有 传统的r s s i 定位算法基础上，提出了提高定位精度的改进方案：利用邻居信标节 点信号强度差和自己与某个邻居信标节点( 主信标节点) 的距离以及主信标节点与 其它邻居信标节点之间的约束关系来对节点进行定位。这减少了把所有的信号强 第三章无线传感器网络自身定位算法相关内容研究 度转化成距离所带来的计算误差和计算开销。假由于没有考虑主信标节点的选择 问题，这对定位误差将会有很大的影响。 3 、基于r s s i 的w s n 加权质心定位算法 4 9 1 文献【4 9 1 通过对无线电传播路径损耗模型的分析，提出了加权质心定位算法， 利用信标节点对未知节点的不同影响力来确定加权因子，以提离定位精度。并且 还提出了优选信标节点进行节点定位计算的规则，以此进一步提高节点定位精度。 加权质心定位算法计算简单，节点定位精度较常用的极大似然估计算法高。 4 、基于r s s i 的一维经验模型定位算法f 瑚 文献 s o l 针对w s n 在道路监控、管道传输等一维中出现的因经验模型基站移动 或环境发生改变时需要重新建立数据库的闻题，提出了基于r s s i 的一维经验模型 定位算法。该算法基于一维线性定位的思想，利用信号强度比值来确定未知节点 的位置，所以只需要建立一次信号强度的比值数据库。这种算法降低了硬件要求， 大大减少了数据的传输量和计算开销，缩短了定位时间，降低了能耗。 3 。重。3 基于移动节点定位算法分析 。 在w s n 基于移动节点定位算法中，节点移动包括信标节点的移动和未知节点 的移动。下面将对这些情况所对应的定位算法进行分析。 1 、基于倍标节移动的定位算法 文献f 5 l 】从信标节点稀疏闽题的角度出发，提出使用单独一个移动的信标节点 在网络中不断广播自己的位置信息，帮助未知节点进行距离无关定位。并考虑了 两种应用情况的特点，基于距离无关算法常用的两种原理，分别设计了基于邻近 关系的移动信标节点辅助定位算法( p m a l o c ，p r o x i m i t y - b a s e dm o b i l eb e a c o n a s s i s t e dl o c a l i z a t i o n ) 和基于跳计数的移动信标节点辅助定位算法( h m a l o c ， h o p s b a s e dm o b i l eb e a c o n a s s i s t e dl o c a l i z a t i o n ) 。 文献f 5 2 】为了更好地解决w s n 节点定位精度和复杂测距技术之间的矛盾，并 减少信标节点的个数以降低整个网络成本，提出一种基于信标节点以一定的几何 图形进行移动的菲测距的定位技术。9 个装备有g p s 接收机的可移动信标节点形 成一个圆形定位区域，位于定位区域内的未知节点接收信标节点发射的信号，并 记录接收信号强度，比较接收信号强度确定自墨所在区域，扶而实现定位。仿真 结果表明，该节点定位技术平均定位精度约为1 0 ，与其他类似定位技术相比， 能够明显提高节点定位精度。但是在实际应用环境中，信标节点整体且以一定的 几何图形进行移动是比较难做到的。 这些基于移动信标节点进行传感器节点进行定位，大大减少了需要的信标节 点数量，从面降低了整个网络成本。傻由于信标节点数量夺，信标节点的移动路 径就显得尤为蘑要，因此必须寻找信标节点的最优移动路径，来减少移动所带来 湖南科技大学硕士学位论文 的开销。文献 5 3 1 根据被监测区域首先给出了充分三重覆盖此被监测区域所需要的 信标发射位置数量计算方法；接着针对矩形被监测区域提出了一种简单的信标发 射位置确定方法；之后针对任意形状被监测区域提出了利用虚拟力获取信标发射 位置坐标的方法。最后，采用流浪旅行商算法获取遍历这些发射位置点的最优路 径，并基予多边测量方法进行传感器节点定位。这为在信标节点移动路径选择上 提供了很好的方法。 2 、基于未知节点移动的定位算法 文献f 别针对移动w s n 节点移动的特性，研究背景是基于煤矿井下，提出了 基于m o n t ec a r l o 方法的精准定位算法。该算法是利用对节点前几个位置( 至少三个 进行牛顿二维插值得到移动节点大致的运动轨迹来预测移动繁点的运动方向及速 度，然后根据其运动方向和速度进行移动节点下一位置的预测采样，采样个数为 。然后根据移动节点在前一时刻到当前时刻运动过程中所接收到信标节点的情 况形成滤波条件，滤掉不满足条件的预测值，保留满足条件的预测值。如果满足 条件的预测值个数小于，则重新采样，滤波，直到找到个满足条件的值，最 后对这个值进行平均来得到未知节点的定位坐标。 这种定位算法不需要特殊的测距硬件，信标节点分布密度较低，未知节点的 部署没有旋律，并霹以随机移动。算法利用未知节点的移动提高了定位精度翔减 少了信标节点的数目。但由于前几个时刻位置的确定将直接影响移动节点以后时 刻的定位精度，丽文中并没有绘出具体的计算方法。 文献f 3 0 l 研究了进一步提高定位算法在低信标节点密度下的适应能力，利糟运 动的连续性，把移动节点的运动预测和测量到的距离相结合，提出运动预测的节 点定位算法。 算法分两个部分： 当某一定位时刻未知节点的邻居信标节点令数n 芝3 时，利用加权e u c l i d e a n 算法来计算未知节点的坐标； 当某一定位时刻未知节点的邻居信标节点个数n 3 和n l i b3 且不共 线一一到主信标节点的信号强度差定位算法( s s d l b ) 在实际的w s n 中，节点是可以测量并记录来自其它节点的信号强度，根据文 献【4 8 】，由( 4 1 ) 可以得到： d d o x 1 0 片一咒4 。一只d + z a l 7 1 叻 ( 4 2 ) 由于x 口一l v ( 0 , v 2 ) ，它的对数概率密度函数可表示为： 俐一壶g 卜节1 肌仙小型掣h m 咿等 对于( 4 2 ) 可以求得距离d 的期望“) 方差d ( d ) ，即： e ( d ) 一e ，+ 曰佗 ， d ( d ) e 2 ，+ 刃0 刃一1 ) ( 4 3 ) ( 4 4 ) 通常情况下，取氐为拥，则( 4 4 ) 中7 ，的表达式可简化为) ，。墨二型丝堑) 二旦1 1 1 1 0 。 。looj 由文中假设w s n 节点定位是在二维空间下进行，则可假设一未知节点d 的坐 标为o ，) ，) ，某一定位时刻其所有邻居信标节点的坐标分别为( x ；，) 以及未知节点 d 接收到各邻居信标节点的信号强度分别为巧，f - 1 , 2 ，