无线传感器网络原理及应用第4章-定位技术-课件.ppt

1、第4章 定位技术 第4章 定位技术 4.1 定位技术简介定位技术简介 4.2 基于距离的定位基于距离的定位 4.3 与距离无关的定位算法与距离无关的定位算法 第4章 定位技术 4.1 定位技术简介定位技术简介4.1.1 定位技术的概念、常见算法和分类定位技术的概念、常见算法和分类1.无线传感器网络定位技术概念无线传感器网络定位技术概念在传感器网络节点定位技术中，根据节点是否已知自身的位置，把传感器节点分为信标节点(beacon node)和未知节点(unknown node)。信标节点在网络节点中所占的比例很小，可以通过携带GPS定位设备等手段获得自身的精确位置。信标节点是未知节点定位的参考点

2、。除了信标节点以外，其他传感器节点就是未知节点，它们通过信标节点的位置信息第4章 定位技术 来确定自身位置。在如图4-1所示的传感网络中，M代表信标节点，S代表未知节点。S节点通过与邻近M节点或已经得到位置信息的S节点之间的通信，根据一定的定位算法计算出自身的位置。第4章 定位技术 图4-1 传感器网络中信标节点和未知节点第4章 定位技术 2节点位置计算的常见方法节点位置计算的常见方法传感器节点定位过程中，未知节点在获得对于邻近信标节点的距离，或者获得邻近的信标节点与未知节点之间的相对角度后，通常使用下列方法计算自己的位置。第4章 定位技术 1)三边测量定位法(trilateration)三边

3、测量定位法是一种常见的目标定位方法，其理论依据是在二维空间中，当一个节点获得三个或者三个以上参考节点的距离时，就可以确定该节点的坐标。三边测量技术建立在几何学的基础上，它用多个点与目标之间的距离来计算目标的坐标位置。如图4-2所示，在二维空间中，最少需要得到三个参考点的距离才能唯一地确定一点的坐标。假设目标节点的坐标为(x，y)，三个信标节点A、B、C的坐标分别为(x1，y1)、(x2，y2)、(x3，y3)，以及它们到未知目标节点的距离分别为1、2、3，则根据二维空间距离计算公式，可以建立如下方程组：第4章 定位技术 图4-2 三边测量定位法第4章 定位技术 由公式(4-1)即可解出节点D的

4、坐标(x，y)：232332222221211)()()()()()(yyxxyyxxyyxx(4-1)222323222322212333212321132323131)(2)(2)(2)(2yyxxyyxxyyxxyyxxyx第4章 定位技术 2)三角测量法(triangulation)三角测量法的原理如图4-3所示，已知A、B、C三个节点的坐标分别为(x1，y1)、(x2，y2)、(x3，y3)，节点D到A、B、C的角度分别为ADB、ADC、BDC、假设节点D的坐标为(x，y)。对于节点A、C和ADC，确定圆心为O1(xO1，yO1)、半径为r1的圆，则cos22)()()()()()(

5、212123123112212211211211rryyxxryyxxryyxxOOOO(4-2)第4章 定位技术 图4-3 三角测量法原理图第4章 定位技术 由公式(4-2)能够确定圆心O1的坐标和半径r1。同理对A、B、ADB和B、C、BDC，也能够确定相应的圆心O2(xO2，yO2)、O3(xO3，yO3)，半径r2、r3。最后利用三边测量法，由O1、O2、O3确定D节点的坐标(x，y)。第4章 定位技术 3)极大似然估计法(maximum likelihood estimation)如图4-4所示，已知获得信标节点1、2、3n的坐标分别为(x1，y1)、(x2，y2)、(x3，y3)(

6、xn，yn)，它们到待定位节点D的距离分别为1，2，3n，假设D的坐标为(x，y)，则存在公式：222222221212121)()()()()()(nnnyyxxyyxxyyxx(4-3)第4章 定位技术 图4-4 极大似然估计法第4章 定位技术 公式(4-3)可表示为线性方程式AX=b，其中)(2)(2)(2)(2)(2)(2112211nnnnnnnnyyxxyyxxyyxxA212221221222222222212221221nnnnnnnnnnnnyyxxyyxxyyxxbyxX使用标准的最小均方差估计方法可以得到节点D的坐标为bAAAXT1T)(第4章 定位技术 4.1.2 定位

7、算法分类定位算法分类在传感器网络中，根据定位过程中是否测量实际节点间的距离，把定位算法分为基于距离的(range-based)定位算法和与距离无关的(range-free)定位算法，前者需要测量相邻节点间的绝对距离或方位，并利用节点间的实际距离来计算未知节点的位置；后者无需测量节点间的绝对距离或方位，而是利用节点间估计的距离计算节点位置。第4章 定位技术 4.2 基于距离的定位基于距离的定位基于距离的定位机制(range-based)是通过测量相邻节点间的实际距离或方位进行定位的。具体过程通常分为三个阶段：第一个阶段是测距阶段，首先测量未知节点到邻居节点的距离或角度，然后进一步计算到邻近信标节

8、点的距离或方位，在计算到邻近信标节点的距离时，可以计算未知节点到信标节点的直线距离，也可以用二者之间的跳断距离作为直线距离的近似；第二个阶段是定位阶段，计算出未知节点到达三个或三个以上信标节点的距离或角度后，利用三边测量法、三角测量法或极大似然估计法计算未知节点的坐标；第三个阶段是修正阶段，对求得的节点的坐标进行求精，提高定位精度，减少误差。第4章 定位技术 基于距离的定位算法通过获取电波信号的参数，如接收信号强度(RSSI)、信号传输时间(TOA)、信号到达时间差(TDOA)、信号到达角度(AOA)等，再通过合适的定位算法来计算节点或目标的位置。4.2.1 基于基于TOA的定位的定位在TOA

9、方法中，主要利用信号传输所消耗的时间预测节点和参考点之间的距离。系统通常使用慢速信号(如超声波)测量信号到达的时间，原理如图4-5所示。超声信号从发送节点传递到接收节点，而后接收节点再发送另一个信号给发送节点作为响应。通过双方的“握手”，发送节点即能从节点的周期延迟中推断出距离为第4章 定位技术 式中，V代表超声波信号的传递速度。这种测量方法的误差主要来自信号的处理时间(如计算延迟以及在接收端的位置延迟T2-T1)。基于TOA的定位精度高，但要求节点间保持精确的时间同步，因此对传感器的硬件和功能提出了较高的要求。2)()(1203VTTTT第4章 定位技术 图4-5 TOA测量原理图第4章 定

10、位技术 4.2.2 基于基于TDOA的定位的定位TDOA测距技术被广泛应用在WSN定位方案中。一般是在节点上安装超声波收发器和RF收发器。测距时，在发射端两种收发器同时发射信号，利用声波与电磁波在空气中传播速度的巨大差异，在接收端通过记录两种不同信号到达时间的差异，基于已知信号传播速度，则可以直接把时间转化为距离。该技术的测距精度较RSSI高，可达到厘米级，但受限于超声波传播距离有限和非视距(NLOS)问题对超声波信号的传播影响。第4章 定位技术 如图4-6所示，发射节点同时发射无线射频信号和超声波信号，接收节点记录两种信号分别到达的时间为T1和T2，已知无线射频信号和超声波的传播速度分别为c

11、1和c2，那么两点之间的距离为(T2-T1)S，其中S=c1c2/(c1-c2)。在实际应用中，TDOA的测距方法可以达到较高的精度。第4章 定位技术 图4-6 TDOA定位原理图第4章 定位技术 4.2.3 基于基于AOA的定位的定位另外一种方法是利用角度估算代替距离估计。估算邻居节点发送信号方向的技术，可通过天线阵列或多个接收器结合来实现。信标节点发出较窄的旋转波束，波束的旋转度数是常数，并且对所有节点都是已知的。于是节点可以测量每个波束的到达时间，并计算两个依次到达信号的时间差。如图4-7所示，接收节点通过麦克风列阵，通知发射节点信号的到达方向。下面以每个节点配有两个接收机为例，简单阐述

12、AOA测定方位角和定位的实现过程。第4章 定位技术 图4-7 AOA定位图 第4章 定位技术 1.相邻节点之间方位角的测定相邻节点之间方位角的测定如图4-8所示，节点A的两个接收机R1、R2间的距离是L，接收机连线中点的位置代表节点A的位置。将两个接收机连线的中垂线作为节点A的轴线，该轴线作为确定邻居节点方位角度的基准线。在图4-9中，节点A、B、C互为邻居节点，节点A的轴线方向为节点A处箭头所示方向，节点B相对于节点A的方位角是，节点C相对于节点A的方位角是。在图4-9中，节点A的两个接收机收到节点B的信号后，利用TOA技术测量出R1、R2到节点B的距离x1，x2，再根据几何关系，计算节点B

13、到节点A的方位角，它对应图4-8中的方位角，实际中利用天线阵列可获得精确的角度信息。同样再获得方位角，最后得到。第4章 定位技术 图4-8 节点结构图 第4章 定位技术 图4-9 方位角图 第4章 定位技术 2.相对信标节点的方位角测量相对信标节点的方位角测量在图4-10中，L节点是信标节点，A、B、C节点互为邻居。计算出A、B、C三点之间的相对方位信息。假定已经测得信标节点L、节点B和节点C之间的方位信息，只需要确定信标节点L相对于节点A的方位即可。第4章 定位技术 图4-10 方位角测量 第4章 定位技术 3.利用方位信息计算节点的位置利用方位信息计算节点的位置如图4-11所示，节点D是未

14、知节点，在节点D计算出n(n3)个信标节点相对于自己的方位角度后，从个信标节点中任选三个信标节点A、B、C。的值是信标节点A和B相对于节点D的方位角度之差，同理可计算出和的角度值，这样就确定了信标节点A、B、C和节点D之间的角度。第4章 定位技术 当信标节点数目n为3时，利用三角测量算法直接计算节点D坐标。当信标节点数目大于3时，将三角测量算法转化为极大似然算法来提高定位精度，如图4-12所示，对于节点A、B、D，能够确定以点O为圆心，以OB或OA为半径的圆，圆上的所有点都满足的关系，将点O作为新的信标节点，OD长度就是圆的半径。因此，从n个信标节点中任选两个节点，可以将问题转化为有个信标节点

15、的极大似然估计算法，从而确定D点坐标。AOA定位不仅能够确定节点的坐标，还能提供节点的方位信息。但AOA测距技术易受外界环境影响，且AOA需要额外硬件，在硬件尺寸和功耗上不适用于大规模的传感器网络。2nC第4章 定位技术 图4-11 三角测量法图示 第4章 定位技术 图4-12 三角测量法转化为三边测量法 第4章 定位技术 4.2.4 基于基于RSSI的定位的定位RSSI随着通信距离的变化而变化，通常是节点间距离越远，RSSI值相对越低。一般来说，利用RSSI来估计节点之间的距离需要使用的方法是：已知发射节点的发射功率，在接收节点处测量接收功率；计算无线电波的传播损耗，再使用理论或经验的无线电

16、波传播模型将传播损耗转化为距离。常用的无线信号传播模型为其中，Pr,dB(d)是以d0为参考点的信号的接收功率；是路径衰减常数；X,dB是以2为方差的正态分布，为了说明障碍物的影响。dB,00dB,dB,lg10)()(XdddPdPrr(4-4)第4章 定位技术 公式(4-4)是无线信号较常使用的传播损耗模型，如果参考点的距离d0和接收功率已知，就可以通过该公式计算出距离d。理论上，如果环境条件已知，路径衰减常数为常量，接收信号强度就可以应用于距离估计。然而，不一致的衰减关系影响了距离估计的质量，这就是RSSI-RF信号测距技术的误差经常为米级的原因。在某些特定的环境条件下，基于RSSI的测

17、距技术可以达到较好的精度，可以适当地补偿RSSI造成的误差。虽然在实验环境中RSSI表现出良好的特性，但是在现实环境中，温度、障碍物、传播模式等条件往往都是变化的，这使得该技术在实际应用中仍然存在困难。第4章 定位技术 4.3 与距离无关的定位算法与距离无关的定位算法尽管基于距离的定位能够实现精确定位，但是对无线传感器节点的硬件要求很高，因而使得硬件的成本增加，能耗增高。基于这些原因，人们提出了距离无关的定位技术。距离无关的定位技术无需测量节点间的绝对距离或方位，降低了对节点硬件的要求，但定位的误差也相应有所增加。第4章 定位技术 目前提出了两类主要的与距离无关的定位方法：一类方法是先对未知节

18、点和信标节点之间的距离进行估计，然后利用三边测量法或极大似然估计法进行定位；另一类方法是通过邻居节点和信标节点确定包含未知节点的区域，然后把这个区域的质心作为未知节点的坐标。与距离无关的定位方法精度低，但能满足大多数应用的要求。与距离无关的定位算法主要有质心定位算法、DV-Hop算法、APIT算法、凸规划定位算法等，下面分别介绍这几种算法。第4章 定位技术 4.3.1 质心定位算法质心定位算法质心定位算法是南加州大学的Nirupama Bulusu等学者提出的一种仅基于网络连通性的室外定位算法。如图4-13所示，该算法的核心思想是：传感器节点以所有在其通信范围内的信标节点的几何质心作为自己的估

19、计位置。具体的算法过程为：信标节点每隔一段时间向邻居节点广播一个信标信号，该信号中包含节点自身的ID和位置信息；当传感器节点在一段侦听时间内接收到来自信标节点的信标信号数量超过某一个预设门限后，该节点认为与此信标节点连通，并将自身位置确定为所有与之连通的信标节点所组成的多边形的质心；当传感器节点接收到所有与之连通的信标节点的第4章 定位技术 图4-13 质心定位法示意图第4章 定位技术 位置信息后，就可以根据由这些信标节点所组成的多边形的顶点坐标来估算自己的位置了。假设这些坐标分别为(x1，y1)、(x2，y2)、(xk，yk)，则可根据下式计算出传感器节点的坐标：另外，该算法仅能实现粗粒度定

20、位，需要较高的信标节点密度。但它实现简单，完全基于网络的连通性，无需信标节点和传感器节点间的协调，可以满足那些对位置精度要求不太苛刻的应用。kyy，kxxyxkk11estest),(第4章 定位技术 4.3.2 DV-Hop算法算法DV-Hop算法的定位过程可以分为以下三个阶段：(1)计算未知节点与每个信标节点的最小跳数。首先使用典型的距离矢量交换协议，使网络中的所有节点获得距离信标节点的跳数(distance in hops)。信标节点向邻居节点广播自身位置的信息分组，其中包括跳段数和初始化0。接收节点记录具有到每个信标节点的最小跳数，忽略来自同一个信标节点的较大跳段数，然后将跳段数加1，

21、并转发给邻居节点，通过这个方法，可以使网络中的每个节点获得每个信标节点的最小跳数。(2)计算未知节点与信标节点的实际跳段距离。第4章 定位技术 每个信标节点根据第一个阶段中记录的其他信标节点的位置信息和相距跳段数，利用公式(4-6)估算平均每跳的实际距离其中，(xi，yi)，(xj，yj)是信标节点i、j的坐标，hj是信标节点i与j(ji)之间的跳段数。22()()ijijj iijj ixxyyHopsizeh(4-6)第4章 定位技术 然后，信标节点将计算的每跳平均距离用带有生存期字段的分组广播到网络中，未知节点只记录接收到的第一个每跳平均距离，并转发给邻居节点。这个策略保证了绝大多数节点

22、仅从最近的信标节点接收平均每跳距离值。未知节点接收到每跳平均距离后，根据记录的跳段数(hops)来估算它到信标节点的距离Di=hopsHopsizeave第4章 定位技术(3)利用三边测量法或者极大似然估计法计算自身的位置。估算出未知节点到信标节点的距离后，就可以用三边测量法或者极大似然估计法计算出未知节点的自身坐标。举例说明：如图4-14所示，已知锚节点L1与L2、L3之间的距离和跳数。由L2计算得到平均每跳距离(40+75)/(2+5)=16.42。假设A从L2获取平均每跳距离，则它与三个节点之间的距离分别为L1：316.42，L2：216.42，L3：316.42，然后使用三边测量法确定

23、节点A的位置。第4章 定位技术 图4-14 计算平均每跳距离 第4章 定位技术 DV-Hop算法在网络平均连通度为10，信标节点比例为10%的各向同性网络中平均定位精度大约为33%。其缺点是仅在各向同性的密集网络中，校正值才能合理地估算平均每跳距离。从上面的描述中可以看出，此方法利用平均每跳距离计算实际距离，对节点的硬件要求低，实现简单，然而存在一定的误差。练习：如图4-15所示，在100 m100 m的矩形区域中，随机布置100个传感器节点，通信半径为15 m，利用DV-Hop定位算法进行未知节点定位。第4章 定位技术 图4-15 DV-Hop定位仿真图 第4章 定位技术 4.3.3 API

24、T算法算法T.He等人提出的APIT(Approximate Point-In-triangulation Test)算法的基本思想是三角形覆盖逼近，传感器节点处于多个三角形覆盖区域的重叠部分中。传感器节点从所有邻居信标节点集合中选择三个节点，测试它是否位于由这三个节点组成的三角形的内部，重复这一过程直到穷举所有的三元组合或者达到期望的精度，然后以所有覆盖传感器节点的三角形的重叠部分的质心作为其位置并计算该位置。如图4-16所示，阴影部分区域是包含传感器节点的所有三角形的重叠区域，黑色圆点表示的质心位置作为传感器节点的位置。第4章 定位技术 图4-16 APIT算法示意图 第4章 定位技术 算

25、法的理论基础是最佳三角形内点测试法(Perfect point-In-triangulation Test，PIT)，为了在静态网络中执行PIT测试，APIT(Approximate PIT Test)测试应运而生：假如节点M的邻居节点没有同时远离或靠近三个信标节点A、B、C，那么节点M就在节点ABC内；否则，节点M在ABC外。APIT算法利用无线传感器网络较高的节点密度来模拟节点移动，利用无线信号的传播特性来判断节点是否远离或靠近信标节点，通过邻居节点间的信息交换，仿效PTT测试的节点移动。第4章 定位技术 如图4-17(a)所示，节点M通过与邻居节点1交换信息，得知自身如果运动至节点1，将

26、远离信标节点B和C，但会接近信标节点A，与邻居节点2、3、4的通信和判断过程类似，最终确定自身位于ABC中；而在图4-17(b)中，节点M可知假如自身运动至邻居节点3处，将同时远离信标节点A、B、C，故判断自身不在ABC中。在APIT算法中，一个目标节点任选三个相邻信标节点，测试自己是否位于它们所组成的三角形中，使用不同信标节点组合重复测试，直到穷尽所有组合或达到所需定位精度。第4章 定位技术 图4-17 APIT测试示意图 第4章 定位技术 APIT测试结束后，APIT用grid SCAN算法进行重叠区域的计算，如图4-18所示。在此算法中，网格阵列代表节点可能存在的最大区域。每个网格的初值

27、都为0。如果判断出节点在三角形内，相应的三角形所在的网格区域的值加1；同样，如果判断出节点在三角形外，相应的三角形所在的网格区域的值减1。计算出所有的三角形区域的值后，找出具有最大值的重叠区域(图4-18中值为2的区域)，最后计算出这个重叠区域的质心即为该节点的位置。第4章 定位技术 图4-18 grid SCAN示意图 第4章 定位技术 在无线信号传播模式不规则和传感器节点随机部署的情况下，APIT算法的定位精度高、性能稳定，测试错误概率相对较小(最坏情况下为14%)，平均定位误差小于节点无线射程的40%。但因细分定位区域和传感器节点必须与信标节点相邻的需求，该算法要求较高的信标节点密度。A

28、PIT定位具体步骤如下：(1)收集信息。未知节点收集邻近信标节点的信息，如未知、标志号、接收到的信号强度等，邻居节点之间交换各自收到的信标节点的信息。第4章 定位技术(2)APIT测试。测试未知节点是否在不同的信标节点组合成的三角形内部。(3)计算重叠区域。统计包含未知节点的三角形，计算所有三角形的重叠区域。(4)计算未知节点位置。计算重叠区域的质心位置，作为未知节点的位置。在无线信号传播模式不规则和传感器节点随机部署的情况下，APIT算法的定位精度高，性能稳定，但APIT测试对网络的连通性提出了较高的要求。相对于计算简单的质心定位算法，APIT算法精度高，对信标节点的分布要求低。第4章 定位

29、技术 练习：在100 m100 m的矩形区域中，随机布置100个传感器节点，通信半径为15 m。考虑当网络中锚节点数分别为30、40、50、60、70、80个时，定位的误差率和覆盖率的变化情况。图4-19为定位覆盖率随锚节点数变化的情况，这里采用蒙特卡洛法求定位覆盖率。在锚节点为30个时，APIT算法的定位覆盖率只达到了10%左右，说明此时只有很少一部分节点可以得到自己的位置信息，算法的有效性非常低，这是由APIT算法对网络密集性和锚节点分布均匀性的要求导致的。APIT算法只有在网络布置密集，且锚节点分布均匀的情况下，算法才能有效执行。而改进算法能够以虚拟锚节点的方式不断升级锚节点的数量，因此

30、即使在锚节点数量很少的情况下，依然能够保持50%以上的定位覆盖率。第4章 定位技术 图4-19 定位覆盖率 第4章 定位技术 定位算法的有效性不能仅通过定位覆盖率来体现，另外一个重要指标是定位的误差率。定位误差率利用公式(4-7)求得。其中，(x，y)为节点的真实位置，(xest，yest)为节点的估计位置，为未知节点个数，R为节点通信半径。定位误差率随锚节点变化曲线仿真图如图4-20所示。由定位误差率曲线可以看出来，在锚节点数较少的情况下，改进的算法误差率明显较小。22estest1()()nixxyyerrornR(4-7)第4章 定位技术 图4-20 定位误差率 第4章 定位技术 4.3

31、.4 凸规划定位算法凸规划定位算法加州大学伯克利分校的Doherty等人将节点间点到点的通信连接视为节点位置的几何约束，把整个网络模型化为一个凸集，从而将节点定位问题转化为凸约束优化问题，然后使用半定规划和线性规划方法得到一个全局优化的解决方案，确定节点位置，同时也给出了一种计算传感器节点有可能存在的矩形空间的方法。如图4-21所示，根据传感器节点与信标节点之间的通信连接和节点无线通信射程，可以估算出节点可能存在的区域(图中阴影部分)，并得到相应矩形区域，然后以矩形的质心作为传感器节点的位置。第4章 定位技术 图4-21 凸规划定位算法示意图第4章 定位技术 凸规划是一种集中式定位算法，定位误差约等于节点的无线射程(信标节点比例为10%)。为了高效工作，信标节点需要被部署在网络的边缘，否则外围节点的位置估算会向网络中心偏移。