第7章 节点定位

1、7.1节点定位概述无线传感器网络中的节点定位主要是指对位置信息未知的节点进行一个相对位置或者绝对位置的标定与获知，基本方法是根据少数已知位置的节点，按照某种算法计算出位置信息的过程。7.1节点定位概述节点定位可以分为两种：一种是确定自己在系统中的位置信息，即节点自身定位；另一种是确定目标节点在系统中的位置信息，即目标定位。7.1节点定位概述在无线传感器节点的定位过程中，没有最优的定位算法，只有最适合具体应用的算法，因此在设计定位算法的时候，需要根据具体应用的特点进行特定的优化。一般情况下，在设计无线传感器网络的节点定位算法时需要考虑如下传感器网络的特性：7.1节点定位概述1.自组织性2.容错性

2、3.分布计算4.能量高效7.2节点定位的分类（1）基于测距的定位方法。在基于测距的定位方法中，首先要计算出节点之间的距离，然后再实现定位。常用的测距技术主要有RSSI、TOA、TDOA和AOA等。（2）无需测距的定位方法。由于测距的定位方法在应用中会产生较大的能耗与成本，因而，人们更多采用的是无需测距的定位方法。如质心法、DV-Hop法和APIT法等等。1.基于测距和无需测距的定位方法7.2节点定位的分类（1）基于测距的定位方法。在基于测距的定位方法中，首先要计算出节点之间的距离，然后再实现定位。常用的测距技术主要有RSSI、TOA、TDOA和AOA等。（2）无需测距的定位方法。由于测距的定位

3、方法在应用中会产生较大的能耗与成本，因而，人们更多采用的是无需测距的定位方法。如质心法、DV-Hop法和APIT法等等。1.基于测距和无需测距的定位方法7.2节点定位的分类集中式定位方法需要一个中心节点负责定位所有的未知节点。在分布式节点定位方法中，节点根据本地的局部信息进行定位，这种方法具有很好的容错性，同时符合无线传感器的网络的分布式特点，因而在研究中被广泛应用。2.基于集中式和分布式的定位方法7.2节点定位的分类有参考节点的为绝对定位法，无参考节点的为相对定位法。绝对定位中节点位置唯一，受节点的移动性影响小，应用较为广泛。相对定位无需信标节点，对系统硬件的要求低，成本低，可以满足一定的应

4、用需求。3.基于绝对定位和相对定位的的定位方法。7.3节点定位的基本术语7.3节点定位的基本术语1.信标节点：有时也称作锚点，指通过其他方式预先获得坐标位置的节点。网络中相应的其余节点称为未知节点或非锚点。2.测距（Ranging）：指两个相互通信的节点通过测量方式来估计出彼此之间的距离与角度。7.3节点定位的基本术语3.邻居节点（Neighbor Nodes）：传感器节点通信半径范围内，无需经过其他节点就能够直接与之通信的节点，统称为邻居节点。4.跳数（Hop Count）：两个要实现通信的节点之间信息转发所需的跳段总数。7.3节点定位的基本术语5.跳段距离（Hop Distance）：两个

5、要实现通信的节点之间的跳段距离的总和。6.连通度（Connectivity）：一个节点拥有的邻居节点的数目。7.3节点定位的基本术语7.到达角度（Angle Of Arrival，AOA）：节点接收到的信号相对于自身轴线的角度。8.到达时间（Time Of Arrival）：信号从一个节点传播到另一个节点所需要的时间。7.3节点定位的基本术语9.接收信号传播时间差（Time Difference Of Arrival，TDOA）：信号在传输过程中，同时发出的两种不同频率的信号到达同一目的地时由于不同的传输速度造成的时间差。10.接收信号强度指示（Received Signal Strength

6、 Indicator，RSSI）：节点接收到的无线信号的强度大小。7.3节点定位的基本术语11.视线关系（Line Of Sight，LOS）：如果传感器网络的两个节点之间没有障碍物，能够实现直接通信，则称两个节点间存在视线关系。12.非视线关系（Non Line Of Sight）：传感器网络的两个节点之间存在障碍物，影响了他们直接的无线通信。7.4节点定位的技术指标定位精度是指节点位置信息与其真实位置之间的接近程度。定位精度是定位系统中最重要的指标，精度越高，技术要求越严格，成本也会越高。1.定位精度7.4节点定位的技术指标定位覆盖是指定位系统中，能够实现定位的未知节点的数目占整个未知节点

7、数目的比例。在无线传感器网络中，只有大范围的节点都能被定位，定位算法才是有效的。定位覆盖范围与定位精度是一对相互矛盾的性能指标。覆盖范围越大，提供的精度就越低，很难实现大范围的高精度定位。2.定位覆盖7.4节点定位的技术指标刷新速度是指提供位置信息的频率。对于导航类型的定位算法，在物体移动的过程中，如果位置信息的刷新速率较慢，则会出现位置信息滞留的现象，导致导航失误等问题的发生。因此，刷新速率影响了定位系统的精度。3.刷新速度7.4节点定位的技术指标由于传感器被随机部署到目标监测区域，需要长时间使用，如果传感器耗能过快，则会导致定位失败。因此，定位技术是否能够满足低功耗是衡量定位性能的一项重要

8、指标。4.功耗7.4节点定位的技术指标定位算法的复杂程度也会对定位服务产生一定的影响，因此，定位技术必须简单高效，快速收敛。5.算法复杂度7.4节点定位的技术指标系统的安全性是保护自己不受外部影响和攻击的能力。由于传感器可能被放到恶劣的环境当中，这时需要无线传感网络的定位系统具有一定的保护能力，使系统不会因为环境的影响或者人为的破坏而影响到整个系统的定位功能。6.安全性7.5基于测距的节点定位基于测距的节点定位分为两个阶段，第一阶段是测距阶段，利用常用的测距技术来计算出未知节点与信标节点的绝对距离值，常用的测距技术有TOA、TDOA和RSSI方法等；第二阶段是定位，确定坐标阶段，即利用第一阶段

9、计算出来的距离确定未知节点的坐标，常用的方法有：三边定位、极大似然估计定位和Min-Max方法等。7.5基于测距的节点定位1.TOA测距通常采用传播速度v较慢的物理信号，如超声波来测量时间。这种方法要求节点间保持精确的时间同步，时间测量上较小的误差可能导致较大的误差结果，对传感器节点的硬件和功耗提出了较高的要求。7.5.1测距阶段vTTd)(017.5基于测距的节点定位2.TDOA测距通常采用无线射频信号和超声波信号，其中，接收节点记录的两种信号到达时间分别为T1和T2，已知无线射频信号和超声波信号的传播速度为c1和c2。7.5.1测距阶段)(12TTkd)/(2121cccck7.5基于测距

10、的节点定位3.RSSI测距当无线信号在大气中传播时，由于各种因素的干扰，信号强度会随着距离的增大而衰减，这表明在信号强度变化与传播距离之间存在某种数学关系，利用这种关系建立起的数学模型就可以求出发射节点和接收节点之间的距离。7.5.1测距阶段XddndPLdPL00lg10)()(7.5基于测距的节点定位1.三边定位法7.5.2定位阶段7.5基于测距的节点定位1.三边定位法7.5.2定位阶段222222222CCCBBBAAAdyyxxdyyxxdyyxx)()()()(21)()()()(21222222222222222222222222CBCACBCAACCACACBBCCBCACACB

11、CACBCABCCBCACAACCACACAxxyyyyxxddyyxxxxddyyxxxxyxxyyyyxxddyyxxyyddyyxxyyx7.5基于测距的节点定位2.多边极大似然估计法7.5.2定位阶段7.5基于测距的节点定位2.多边极大似然估计法7.5.2定位阶段222222222212121)()()()()()(nnndyyxxdyyxxdyyxx7.5基于测距的节点定位2.多边极大似然估计法从第一个方程开始分别减去最后一个方程可得如下线性方程：7.5.2定位阶段221122112212222222222222112211221)(2)(2)(2)(2)(2)(2nnnnnnnnn

12、nnnnnnnnnnnddyyyyyxxxxxddyyyyyxxxxxddyyyyyxxxxx7.5基于测距的节点定位2.多边极大似然估计法可以简化为矩阵相乘的方式：AX=b，其中使用极大似然估计方法可以得到节点D的坐标为：7.5.2定位阶段)( 2)( 2)( 2)( 21111nnnnnnyyxxyyxxA212221221212221221nnnnnnnnnddyyxxddyyxxbyxXbAAAXTT1)(7.5基于测距的节点定位3.Min-max定位方法Min-max定位是根据若干锚点位置和到未知节点的测距值，创建多个正方形边界框，所有边界框的交集为一矩形，取其矩形的质心作为未知节点

13、的坐标。7.5.2定位阶段7.5基于测距的节点定位3.Min-max定位方法7.5.2定位阶段2)min()max(2)min()max(iiiiiiiidydyydxdxx7.6无需测距的节点定位1.算法介绍多边形的几何中心称为质心。在质心算法中，锚节点周期性地向邻近节点广播锚节点分组，锚节点分组中包含锚节点的标识号和位置信息，当未知节点接受到来自不同的锚节点的信标分组数量超过某一个门限k或接收一定时间后，就确定自身位置为这些锚节点所组成的多边形质心。7.6.1质心算法66fedcbafedcbayyyyyyxxxxxxyx，7.6无需测距的节点定位2.算法分析7.6.1质心算法7.6无需测

14、距的节点定位2.算法分析质心的精度依赖于锚节点分布的密度和分布情况。虽然增加锚节点数量可以改进定位精度，但需要更多的节点间通信，这将极大地增加节点能量的消耗。此外，如果在未知节点周围用于定位的锚节点以未知节点为中心分布很均匀的话，定位精度会得到提高。相反分布不均匀将直接导致定位精度下降。7.6.1质心算法7.6无需测距的节点定位3.质心算法的优缺点质心定位算法最大的优点是它非常简单，计算量小，完全基于网络的连通性；缺点是需要较多的锚节点，误差相对较高。7.6.1质心算法7.6无需测距的节点定位1.算法介绍DV-Hop（Distance Vector Hop）算法，即基于距离向量跳数的定位方法。

15、该算法借鉴了经典的距离向量路由算法。定位过程一共分为三个阶段。7.6.2 DV-Hop定位7.6无需测距的节点定位1.算法介绍（1）计算未知节点与每个信标节点的最小跳数。这个阶段使用经典的距离向量交换协议，每个节点维护一个表，记录到信标节点的坐标和跳数。每个信标节点发送一个广播分组，该分组包含自身的位置信息和跳段数，跳段数初始化为0。节点收到信标节点的广播分组后，检验该分组跳段数是否小于本节点表内的存储值，如果是，则更新该表，然后跳段数加1并广播该分组，否则丢弃该分组。最终所有的未知节点均能获得所有信标节点的最小跳数。7.6.2 DV-Hop定位7.6无需测距的节点定位1.算法介绍（2）计算未

16、知节点与信标节点的距离每个信标节点根据自身表中记录的其他信标节点的坐标信息和跳数，按照公式（7-10）计算平均跳段距离ci。为了确保绝大多数节点可以从最近的信标节点接收平均跳段距离，把计算出来的平均跳段距离利用可控洪泛法进行广播，每个节点均接收第一个跳段的距离，忽略后来到达的节点。最后未知节点便可以计算出自己到达相应信标节点的距离（平均跳段距离*跳数）。7.6.2 DV-Hop定位ijjijjijiihyyxxc22)()(7.6无需测距的节点定位1.算法介绍（3）计算未知节点的坐标经过前两个阶段，现在已知信标节点L1、L2与L3之间的距离和跳数，如图7-9所示。假设L2计算得到平均跳段距离为

17、（40+80）/（2+5）=17.14。假设节点A从节点L2获得平均跳段距离，则它与信标节点L1、L2、L3的距离分别为317.14、217.14、317.14。7.6.2 DV-Hop定位7.6无需测距的节点定位2.算法分析（1）DV-Hop定位方法与基于测距定位方法具有相似之处，就是都需要获得未知节点到锚节点的距离，基于测距的定位方法得到的是精确距离，而DV-Hop定位方法使用平均跳段距离估算距离，存在一定的误差。7.6.2 DV-Hop定位7.6无需测距的节点定位2.算法分析（2）基于测距的定位方法在计算距离时依靠测量无线电波信号，这就限定了未知节点只能获得自己射频覆盖范围内的锚节点的距

18、离，而DV-Hop定位方法依靠的是网络连通性和网络拓扑结构，这样就可以获得更多的有用数据，提高定位精度。7.6.2 DV-Hop定位7.6无需测距的节点定位2.算法分析（3）由于DV-Hop定位方法在定位过程中两次洪泛，能量开销比较大。（4）该算法主要用于节点稀疏的网络中对未知节点定位的场合。（5）总得来说，DV-Hop定位方法对硬件要求比较低，实现起来比较简单。7.6.2 DV-Hop定位7.6无需测距的节点定位1.算法介绍APIT（Approximate Point-in-Triangulation Test）称为近似三角形内点测试法，属于距离无关、区域相关的定位策略。该算法实现简单、定位成本低、传感器节点功耗小、定位精度高，因而得到广泛应用。7.6.3 APIT定位7.6无需测距的节点定位1.算法介绍它的基本思路是从未知节点周围的锚节点中任意选取三个，组合成一个三角形，判断该点是否位于该三