《物联网通信技术》课件第16章.ppt

1、 第16章WSN的节点定位16.1节点定位的概念及基本原理节点定位的概念及基本原理16.2距离定位距离定位16.3距离无关的定位算法距离无关的定位算法本章小结本章小结16.1 节点定位的概念及基本原理节点定位的概念及基本原理16.1.1 定位的几个相关概念定位的几个相关概念一般情况下，信标节点在WSN节点中所占的比例很小，可以通过诸如GPS等定位设备获得自身的精确位置。信标节点是未知节点定位的参考点。未知节点可以通过信标节点的位置信息来确定自身位置。如图16.1.1所示，M代表信标节点，S代表未知节点。S节点通过与邻居节点M的位置信息及节点间的通信，并采用一定的定位算法计算出自身的位置。（1）

2、邻居节点(Neighbor Nodes)：传感器节点通信半径内所有的其他节点称为该节点的邻居节点。（2）跳数(Hop Count)：两个节点之间间隔的跳段总数称为两个节点间的跳数。（3）跳段距离(Hop Distance)：两个节点之间间隔的各跳段距离之和称为两节点间的跳段距离。（4）基础设施(Infrastructure)：用于WSN节点定位的固定或移动设备，如卫星、基站、GPS等。（5）到达时间(Time of Arrival，TOA)：信号从一个节点传播到另一节点所需要的时间称为信号的到达时间。（6）到达时间差(Time Difference of Arrival,TDOA)：两种不同传

3、播速度的信号从一个节点传播到另一个节点所需要的时间之差称为信号的到达时间差。（7）接收信号强度指示(Received Signal Strength Indicator，RSSI)：节点接收到无线信号的强度大小称为接收信号的强度指示。（8）到达角度(Angle of Arrival，AOA)：节点接收到的信号相对于节点自身轴线的角度称为信号相对接收节点的到达角度。（9）视线(Line of Sight，LOS)：两个节点间没有障碍物间隔，双方能“看见”，并能够直接通信称为两个节点间在视线内。（10）非视线关系(No LOS,NLOS)：两个节点之间存在障碍物，双方“看不见”。图16.1.1 信

4、标节点与未知节点图16.1.2 三边测量法示意图16.1.2 节点定位的基本原理节点定位的基本原理1.三边测量法如图16.1.2所示，已知节点A、B、C三个节点的坐标已知分别为(xa,ya)、(xb,yb)和(xc,yc)，它们与未知节点D的距离分别da、db和dc，则D的坐标(x,y)可由下式确定。(16.1.1)则D点的坐标(x,y)为(16.1.2)2.三角测量法(Triangulation)如图16.1.3所示，已知A、B、C三个节点的坐标分别为(xa,ya)、(xb,yb)和(xc,yc)，节点D相对于A、B、C的角度分别为ADB、ADC、BDC。节点D的坐标为(x,y)，对于节点A

5、、C和角ADC，如果弧AC在ABC内，则能够唯一确定一个圆。设圆心为O1(x1,y1)，半径为r1，于是=AO1C=（22ADC)，并有由式(16.1.2)可确定圆心O1点的坐标(x1,y1)和半径r1。同理，可分别确定相应的圆心O2、r2及O3、r3，最后利用三边测量法，由O1(x1,y1)、O2(x2,y2)和O3(x3,y3)确定D点坐标(x,y)。该方法是利用角度和已知节点的坐标将问题转化为求三边法中的距离d，即半径r来求出未知节点坐标的。3.极大似然估计法极大似然估计法(Maximum Likelihood Estimation)如图16.1.4所示。已知1、2、3等n个节点的坐标分

6、别为(x1,y1)，(x2,y2)，(x3,y3)，(xn,yn)，它们到节点D的距离分别为d1，d2，d3，dn，假设节点D的坐标为(x,y)。图16.1.4 极大似然估计示意图节点D与节点1、2、3、n之间有如下关系：(16.1.4)用最后一个方程去减第一个，直到最后第二个方程,有(16.1.5)将式(16.1.5)表示为线性方程:Ax=b式中对式(16.1.6)用最小均方差进行估计，即求解f=(AXb)T(AXb)的极小值。令Y=AXb，则令上式等于零，即(16.1.7)16.1.3 定位算法的分类定位算法的分类（1）基于距离的定位算法和距离无关的定位算法。根据定位过程中是否测量实际节点

7、间的距离，把定位算法分为基于距离的(Range Based)定位算法和距离无关的(Range Free)定位算法。前者需要测量相邻节点间的绝对距离或方位，并利用节点间的实际距离来计算出未知节点的位置；后者无需测量节点间的绝对距离或方位，而是利用节点间的估计距离计算出节点位置。（2）递增式的定位算法和并发式的定位算法。根据节点定位的先后次序不同，把定位算法分为递增式的(Incremental)定位算法和并发式的(Concurrent)定位算法。递增式的定位算法通话从信标节点开始，信标节点附近的节点首先开始定位，依次向外延伸，各节点依次进行定位。这类算法的主要缺点是定位过程中累积和传播了大量的测量

8、误差。并发式的定位算法中所有的节点同时进行定位计算。（3）基于信标的定位算法和无信标的定位法。根据定位过程中是否使用信标节点，把定位算法分为基于信标节点的(Beacon Based)定位算法和无信标节点的(Beacon Free)定位算法。前者在定位过程中，以信标节点作为定位的参考点，各节点定位后产生整体绝对坐标系统；后者只关心节点间的相对位置，在定位过程中无需信标节点，各节点先以自身作为参考点，将邻近的节点包含到自己定义的坐标系中，相邻的坐标系统依次转换合并，最后产生整体相对坐标系统。16.2 距距 离离 定定 位位基于距离的定位机制是通过测量相邻节点间的实际距离或方位来定位的。定位过程可分

9、为测距阶段、定位阶段和修正阶段。在测距阶段，未知节点先测量到邻居节点的距离或角度，然后计算到邻近信标节点的距离或方位。在计算到邻近信标节点的距离时，可以计算未知节点到信标节点的直线距离，也可以用两者间的跳段距离作为直线距离的近似。在定位阶段，未知节点在计算出到达三个或三个以上信标节点的距离或角度后，利用三边测量法、三角测量法或极大似然估计法计算未知节点的坐标。在修正阶段，需对求得的节点的坐标进行修正，以提高定位精度，减少误差。定位距离时，测量节点间的距离或方位主要有到达时间(TOA)、到达时间差(TDOA)、接收信号强度指示(RSSI)和到达角度(AOA)等定位方法。16.2.1 TOA定位定

10、位在利用到达时间TOA的定位机制中，已知信号的传播速度，可根据信号的传播时间计算节点间的距离，然后利用已有算法计算出节点的位置。该方法计算量小、算法简单且定位精度高。一般采用如图16.2.1所示的声音收发装置来完成测距和定位。图16.2.1 音频收发定位装置假设两个节点的时间同步，发送端的扬声器发送声音信号的同时，无线通信模块发送同步消息通知接收节点的声音信号发送的时间，接收节点的拾音器模块在接收到声音信号后，根据声波信号的传播时间和速度计算发送节点和接收节点之间的距离。节点在计算出相邻的多个信标节点的距离后，可以利用三边测量算法或极大似然估计算法计算出自身的位置。16.2.2 TDOA定位定

11、位到达时间差（TDOA）定位是采用两种信号到达的时间差以及两个不同的传播速率来计算距离的。以下介绍一种典型的基于TDOA的AHLoS(Ad Hoc Localization System)算法。TDOA定位算法的原理如图16.2.2所示。图16.2.2 TDOA定位算法原理图图16.2.2中，发射节点同时接收节点发送的无线信号和声音信号，这两个信号到达接收节点的时间分别为t1和t2，无线信号和声音信号的传播速度分别为v1和v2，那么发射与接收节点间的距离s为212112vvvvtts(16.2.1)AHLoS算法是一种基于TDOA定位算法的迭代算法。在该算法的起始阶段，信标节点对外广播自身的位

12、置信息，使定位节点能测量与其相邻的信标节点之间的距离，并可知道信标节点的位置信息。当信标节点的数量为3个或3个以上时，就可使用最大似然估计法计算节点的位置信息。如果带定位节点的位置信息已经计算出来，该节点就转化为信标节点，开始向外广播自身位置信息。因此WSN中信标节点的数量随着定位算法的进程在逐渐增多。根据WSN中待定位节点周围的信标节点的分布情况不同，AHLoS算法定义了以下三种不同的子算法：（1）原子多边算法。当未定位节点相邻的信标数为3个或3个以上时，使用最大似然估计法，这里也叫原子多边算法。这里所讲的信标数是指传感器网络部署完毕后初始的情况下还没有执行定位算法之前，因为要执行定位算法，

13、一部分未定位节点就可能转化成了信标节点。（2）迭代多边算法。当待定位节点相邻的信标节点数小于3个时，与之相邻的信标节点通过广播自身的位置信息并被待定位节点获知，经过对这些信息运算处理后，确定了自身的位置，也成为信标节点。当未知节点的相邻信标节点的数量达到3个或3个以上时，使用最大似然估计法进行未知节点的定位计算。（3）协作多边算法。WSN中传感器节点的部署在很多应用场合中是随机的，而且信标节点的数量也很少，这种情况下如果要使用信标的信息来对未知节点进行定位，就无法使用原子多边算法或迭代多边算法。协作多边算法是这样一种算法：经过多次迭代定位以后，待定位节点的邻居数量仍然不足3个，此时要依托多跳的

14、局部信息（即通过其他节点的协助）来计算自身的位置。图16.2.3是协作多边算法的示例。图16.2.3 协作多边算法示例在图16.2.3中，节点C为待定位节点，其信标节点仅有相邻节点A、E两个，数量还是不足三个，此时需要通过计算到达信标节点的多跳距离获得E和F的位置信息，再利用原子多边算法完成定位计算。该算法主要应用于传感器网络中信标密度较高、网络规模不太大的情况。16.2.3 AOA定位定位AOA定位技术称为到达角交汇定位技术。该技术在两个以上的位置点设置方向性天线或天线阵列，获得节点发射的无线电波角度信息，通过阵列天线或多个接收机联合确定相邻节点发送信号的方向，从而构成一个从接收机到发射机的

15、方位线，两个方位线的交点即为待定位节点的位置。如图16.2.4所示，待定位节点在获得与参考点A和B所构成的角度后，通过交汇法可确定自身的位置。图16.2.4 两方为线相交确定待定位节点示意图另外AOA信息还可以与其他一些信息一起形成定位精度更高的混合定位算法，但AOA定位法所采用的系统较为复杂。基于AOA的APS(Ad Hoc Positioning System)算法是利用两个能测量方向信息和距离信息的接收器的相互之间的几何关系来确定未知节点坐标的定位的。其原理如图16.2.5所示，图中的两个接收器间的距离为L，节点A在这两个接收器连线的中点上，以此中点做该连线的中垂线，该中垂线为计算两个相

16、邻节点间的方位角的基准线。当测出节点B到接收器1的距离为x1，到接收器2的距离为x2后，根据几何关系可以容易地确定节点A、B之间的方向角。在图16.2.6中，A、B和C三个节点是已知其自身位置信息的信标节点，节点D是待定位节点。如果已知节点D与A、B和C三个节点之间的方向角，从图中的几何关系中就可以得出ADB、ADC和BDC，并应用三角测量法确定节点D的坐标。图16.2.5 由几何关系确定节点间方向图16.2.6 三角测量原理图16.2.4 RSSI定位定位基于接收信号强度指示的RSSI定位算法是一种利用接收信号强度指示测距的定位算法。该算法通过测量发送功率与接收功率来计算传播损耗，并利用理论

17、和经验模型将传播损耗转化为发送器与接收器的距离。该方法易于实现，无需在节点上安装辅助定位设备。当遇到非均匀传播环境、有障碍物造成多径反射或信号传播模型过于不精确时，RSSI测距精度和可靠性降低，一般将RSSI和其他测量方法综合起来实现定位。比较著名的RSSI定位系统有微软研发的RADAR系统。RADAR系统定位的基本原理是：在建筑物内(监测区域)部署数个基站，对建筑物的需监测区域进行覆盖，基站一旦部署完毕，一般情况不再进行位置移动，而被监测的建筑物内部区域中可以随机地部署位置可移动的传感器节点，即具有移动性的客户端。通过测量移动终端处的信号强度值，并与预先建立的信号强度区域中各参考点的分布经验

18、数据值进行对比匹配，根据信号传播模型和信号传输损耗确定移动终端与基站之间的距离，在此基础上应用三边测量法计算节点位置。RADAR系统工作的示意图如图16.2.7所示。建筑物内的被监测区域部署了三台基站，对指定区域进行了覆盖；移动终端的位置是随机移动的，它们与基站之间随时可进行通畅的无线通信。图16.2.7 RADAR系统工作示意图1.信号强度经验数据表匹配算法在建筑物内的监测区域内，当基站部署后，选取若干个信号强度经验数据测试点来测试信号的强度，以测得的数据进行定位。每个基站记录移动终端放置在这些测试点时所能接收到的信号强度为Ss。这样就建立了一个测试点信号强度经验数据库(x,y,Ss1,Ss

19、2,Ss3)。经比较，该均方差序列中最小值对应的节点的坐标就是该待定位节点的坐标。为提高数据处理的精度，采用对同一个监测点采集的多个信号强度数据取平均值的方法，也可以选取均方差序列中几个最小的均方差值对应的几个点，使用它们的质心作为待定位节点的位置。2.信号传播模型算法由于建筑物内部的墙壁内含有钢筋等金属媒质，会对无线信号产生较大衰减及反射干扰，所以无线信号在室内的传播远比室外空旷空间的传播复杂。在WSN的传输中，当数据从汇聚节点向远程监控中心的传送过程中，经过室内障碍物或墙壁后，信号功率将衰减相当大的一部分。RADAR系统充分地考虑了这种衰减，建立了信号衰减和传播距离之间的关系。如考虑了室内

20、的障碍物结构对无线信号的传播产生反射、折射、散射和透过衰减等综合性因素后，国外学者提出了一种墙壁衰减系数模型，也称为WAF(Wall Attenuation Factor)模型。该模型根据三个基站实际测量所得到信号强度数据，经过理论分析、经验及仿真得到的一个公式，可计算出待定位节点与三个基站之间的距离，然后利用三边测量法计算出待定位节点的位置。计算基站接收到待定位节点发送的无线信号强度为(16.2.2)式中，P(d0)表示基站接收到参考点d0处发送信号的强度（假设各点发送信号强度均相同），n为路径长度和路径损耗之间的比例因子，d为待定位节点与基站间的距离，d0为参考节点到基站的距离；nW为待定

21、位节点与基站间相隔的墙壁数目，C为无线信号穿过墙壁数目的阈值，WAF为无线信号穿过墙壁时的衰耗因子（它取决于建筑物的具体结构和墙壁的建筑材料），dBm为信号的功率单位。当采用式(16.2.2)计算出基站接收到待定位节点发送的无线信号强度后，与基站接收到参考点d0处的发送信号的强度比较，就可以解出待定位节点和基站之间的距离，在此基础之上解出位置坐标信息。无线信号穿过墙壁传输时的衰耗系数可以采用经验值。基于信号传播模型的算法与根据信号强度经验数据表匹配的算法相比其成本低，无需先建立一个监测区域中各测试点的信号强度经验数据值数据库，而且在建筑物内的基站重新部署后，也无需重新建立该数据库；但基于信号传

22、播模型的算法的定位精度不如根据信号强度经验数据表匹配的算法的定位精度。16.3 距离无关的定位算法距离无关的定位算法16.3.1 质心算法质心算法质心是指多边形的几何中心，多边形顶点坐标的平均值就是质心节点的坐标。如图16.3.1所示，多边形ABCDE的顶点坐标分别为A(x1,y1)、B(x2,y2)、C(x3,y3)、D(x4,y4)、E(x5,y5)，其质心坐标为（16.3.1)质心定位算法首先确定包含未知节点的区域，计算这个区域的质心，将其作为未知节点的位置。在质心算法中，信标节点周期性地向邻近节点广播信标分组，信标分组中包含信标节点的标识号和位置信息。当未知节点接收到来自不同信标节点的

23、信标分组数量超过某一门限k或接收一定时间后，就将其自身位置确定为这些信标节点所组成的多边形的质心，即(16.3.2)式中，(xi1,yi1),(xi2,yi2),，(xik,yik)为未知节点能够接收到其分组的信标节点坐标。质心算法完全依赖于网络连通性，无需信标节点和未知节点之间的协调，因此比较简单，容易实现。但质心算法假设节点都拥有理想的球形无线信号传播模型，而实际上无线信号的传播模型井非如此，因此存在着较大的误差。16.3.2 DV-Hop算法算法在距离向量-跳段(Distance Vector-Hop,DV-Hop)算法中，未知节点首先计算与信标节点的最小跳数，然后估算平均每跳的距离，利

24、用最小跳数乘以平均每跳距离，得到未知节点与信标节点之间的估计距离，再利用三边测量法或极大似然估计法计算未知节点的坐标。DV-Hop算法的定位过程有以下三个阶段：第一阶段，计算未知节点与每个信标节点之间的最小跳数。定位算法开始，WSN中的每个信标节点都向其邻居节点广播发送消息分组，包含自身的位置信息以及跳数，此时的初始跳数值设置为0。接收到信标节点消息分组的节点将自己的跳数由初始的0加1后，连同含有信标节点的位置信息一起再转发给邻居节点。这个过程覆盖整个网络，最后所有的节点都获得了每一个信标节点的位置信息和最小跳数参数。在以中继方式传递信标节点的位置信息和确定各节点到所有信标节点的最小跳数的过程

25、中，如果某节点重复收到另一个信标节点的消息分组或该节点到另一个信标节点的最小跳数大于已经收到最小跳数值，则此时发生了信标节点的信息冗余，因此将其舍去。第二阶段，计算每个信标节点与其他信标节点的实际跳段距离。当第一阶段结束后，WSN中每个信标节点都记录了到其他信标节点的位置信息和它们之间距离的跳数。利用这些信息就可以估算出平均每跳距离，并向整个网络广播该消息分组。第i个信标节点平均每一跳的距离ci为(16.3.3)现以图16.3.2为例说明每跳平均距离的计算。节点A、B、C为信标节点，它们均有明确的坐标信息。节点A与B的距离为60 m，节点A到C的距离为120 m，节点B到C的距离为90 m。节

26、点A到B的跳数为2跳，节点A到C的跳数为6跳。应用式(16.3.3)可得到：节点A的每跳平均距离为（60+120)/(2+6)=22.5（m），节点B的每跳平均距离为(60+90)/(2+5)=21.4(m)，节点C的每跳平均距离为(120+90)/(5+6)=19.1(m)。图16.3.2 DV-Hop算法示意图一个信标节点在计算完与其他各信标节点每跳的平均距离后，在对邻居节点广播的消息分组中，包含了各信标节点的最新信息。这样，其他的节点可以得到信标节点的最新位置信息，一般是周围的相邻节点先得到该消息。在网络中，位置信息以广播的方式发射，网络中的节点在收到位置信息时就与原来收到的位置信息进行

27、比较，如果新收到的位置信息比原来的位置信息更新，就抛弃原来的位置信息，将新收到的位置信息储存起来，这样就可以保证节点只储存l条最新的位置信息。第三阶段，完成未知节点的位置估计。未知节点利用第二个阶段获取的网络中每一个信标节点与其他信标节点的实际跳段距离的数据，使用三边测量法和最大似然估计法来估算未知节点的位置信息。从图16.3.2可知，经过第一、二阶段的计算，已知网络中各信标节点之间的实际距离和跳数，未知节点M从信标节点B上获得每跳平均距离为21.4 m，则节点M与A、B、C三个信标节点之间的距离分别为l1=321.4=64.2 m，l2=221.4=42.8 m，l3=321.4=64.2

28、m，最后使用三边测量法可计算出M点的坐标。DV-Hop算法的优点是比较简单，无需进行节点之间的距离测量，可以避免测量时带来的误差，传感器节点不需要其他的附加硬件支持，是无线传感器网络节点定位的一个较经济可行的方案。但是这种算法仍存在一些需要改进的地方：在获得平均每跳的计算过程中，节点之间通信量较大，而且没有考虑网络中存在不良节点的影响，易造成平均定位误差较大。16.3.3 其他距离无关的定位算法其他距离无关的定位算法1.DV-Distance算法DV-Distance算法类似于DV-Hop算法，它们之间的区别在于：DV-Hop算法通过节点的平均每跳距离和跳数算出节点间的距离；而DV-Dista

29、nce算法是通过节点的射频通信来测量出节点间的距离的，它利用了RSSI定位来测量节点间的距离，然后再应用三角测量法计算出节点的位置。与DV-Hop算法相比较，DV-Distance算法对传感器节点的功能要求比较低，不要求节点要能够储存网络中各个节点的位置信息，同时还较大幅度地减少了节点间的通信量，从而也降低了节点工作能耗。不足之处在于，因为DV-Distance算法直接测量节点间的距离，这样对距离的敏感性要求较高，尤其对测距的误差很敏感，因此算法的误差较大。2.改进的DV-Hop算法DV-Hop算法在实现的过程中，由于要获得信标节点的最新位置信息和跳数信息，所以节点间的通信量很大，另外由于没有

30、考虑到网络中存在无法定位的节点而导致算法会与实际的情况有较大的误差。为此，人们对该算法进行了改进，提出了改进的DV-Hop算法。经过改进的DV-Hop算法不但排除了WSN中的不良节点，而且利用了多个信标节点的冗余信息，从而降低了定位误差和传感器节点的能耗。本本 章章 小小 结结定位可以确定WSN节点确切的地理位置，为感知提供更为全面的信息，尤其是对于环境监测、突发事件的监控、目标的跟踪等方面。节点的定位对于WSN的有效运行也具有非常重要的作用，对于提高路由控制、网络管理、网络的覆盖质量等方面都有非常大的帮助。定位算法应满足自组织性要求、鲁棒性要求、分布式计算要求和能量高效要求。节点定位的基本原

31、理主要有三边测量法、三角测量法和极大似然估计法。定位算法通常可分为以下几种：（1）基于距离的定位算法和距离无关的定位算法。（2）递增式的定位算法和并发式的定位算法。（3）基于信标的定位算法和无信标的定位算法。基于距离的定位机制是通过测量相邻节点间的实际距离或方位来定位的。定位过程可分为测距阶段、定位阶段和修正阶段。距离无关的定位技术无需测量节点间的绝对距离或方位，降低了对节点硬件的要求，但定位的误差也随之有所增加。目前提出了两类主要的距离无关的定位方法：一类方法是先对未知节点和信标节点间的距离进行估计，然后利用三边测量法或极大似然估计法进行定位；另一类方法是通过邻居节点和信标节点确定包含未知节点的区域，然后把这个区域的质心作为未知节点的坐标。尽管距离无关的定位方法精度低，但能满足大多数应用的要求。