无线传感器网络概论第7章-节点定位技术概述课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,7,章 节点定位技术概述,本章目录,7.1 节点定位技术概述,7.2,基于测距的定位技术,7.3,基于非测距定位技术,7.4,协作定位技术,7.1 节点定位技术概述,1.,锚节点（beacon node）：也称参考节点，即已知自身位置信息的节点，可通过 GPS 定位设备或人工部署等方式预先获取位置信息，为其他节点提供参考坐标。,2.,未知节点（blind node）：也称盲节点、普通节点，即自身位置未知的节点，需要定位的节点。,3.,邻居节点（neighborhood node）：如果两个节点之间能够相互通信发送消息，则它们互称为邻居节点。,4.,跳数（hop count）：两个节点之间跳段的总数。,5.,节点连接度（node degree）：就是节点可以探测发现到的邻居节点个数。,6.,网络连接度（network degree）：就是所有节点的邻居个数取平均值，反映传感器配置的密集程度。,7.1.1 节点定位相关的基本术语,7.1 节点定位技术概述,7.,接收信号强度（receive signal strength indicator,RSSI）：节点接收到无线信号的强度大小。,8.,到达时间（time of arrival,TOA）：信号从一个节点传播到另一节点所需要的时间。,9.,到达时间差（time different of arrival,TDOA）：两种不同传播速度的信号从一个节点传播到另一节点所需要的时间之差，或两个发送节点向同一个接收节点同时发送同一种性质的信号，信号传播到接收节点的时间之差。,10.,到达角度（angle of arrival,AOA）：节点接收信号方向相对于自身轴线的方位角度。,7.1.1 节点定位相关的基本术语,7.1 节点定位技术概述,2.基本原理,无线传感器网络中包含大量传感器节点，通常节点的放置采用随机撒播的方式，如果依靠人工标定来确定每个节点的位置，其工作量巨大，难以完成。另一种可直接获得节点位置的方法是为每个节点配备GPS，但由于节点数目众多，考虑到价格、体积、功耗等因素的限制，通常不采取这种方案。一种较合理的方法是为部分节点事先标定好准确位置，这些节点通常称为锚节点，然后利用这些能确定位置的节点提供的信息和锚节点与非锚节点之间的协作来确定非锚节点的位置，这样所有节点的准确位置就都能得到。,7.1.2 节点定位技术的定义及基本原理,7.1 节点定位技术概述,无线传感器网络定位问题的一般前提假设是以下四点。,（1）网络具有较高的密度。,（2）网络内每一个节点具有全网唯一的ID。,（3）在没有特别说明的情况下所有节点具有相同的最大通信距离。,（4）在定位过程中假设节点相对位置不变。,7.1.2 节点定位技术的定义及基本原理,7.1 节点定位技术概述,无线传感器网络节点的定位算法有很多，根据分类标准的不同，主要有以下几种分类：,1.,基于测距技术的定位和无需测距技术的定位,2.,集中式计算与分布式计算,3.,绝对定位与相对定位,7.1.3 定位算法的分类,7.2 基于测距的定位技术,常见的测距机制分为到达时间测距机制、到达角度测距机制和接收信号强度测距机制。,1.TOA简介,其中，到达时间TOA测距机制又分为到达时间TOA 和到达时间差TDOA。,TOA测距算法的基本原理是距离等于速度和时间的乘积。速度即信号的传播速度，时间即信号从起节点到终节点的传播时间。假设求两个时间同步的节点之间的距离，起节点发送声波信号时，也将发送信号的时间一同发送给终节点，这样终节点在检测到声波信号后，信号传播时间已知，信号传播速度已知，根据公式就能计算出起节点到终节点的距离。,7.2.1 测距技术,7.2 基于测距的定位技术,2.接收信号强度指示,接收信号强度测距机制是指根据信号发射过程中信号发射使得强度和被接收到时的强度的差值，得到在传播过程中的损耗，利用该损耗计算出发射节点与接受节点之间的距离。由于该技术容易实现，对硬件要求低，所以在一些领域中都有使用。,接收信号强度测距定位在实际应用中，受外界环境影响较大导致计算有很大的不稳定性，误差较大，定位精度低，所以尽管该算法功率低、成本小，但并未得到广泛应用。,7.2.1 测距技术,7.2 基于测距的定位技术,已知锚节点A、B、C的坐标分别为（x0,y0）、（x1,y1）、（x2,y3），未知节点D的坐标为（x,y），锚节点到未知目标节点的距离分别为d1、d2、d3。三边测量定位法的基本原理就是分别求以（x0,y0）、（x1,y1）、（x2,y3）为圆心，以d1、d2、d3为半径的三个圆的交点，并以此求出未知节点的坐标，定位方程组如下式所示。,7.2.2 三边定位技术,7.2 基于测距的定位技术,7.2.2 三边定位技术,三边测量法最大的优点是定位精度高，但是对测距过程依赖大，若该工程中出现误差，则上述,3,个圆无法交于一点，如下图所示。,这时若用带误差的距离去计算时需要增加额外算法，使计算更加复杂。因此，三边测量法在实际定位应用不多，三边测量法一般只作为定位的理论基础知识。,7.2 基于测距的定位技术,基于AOA测距的定位方法因为利用了信号到达的方向所以被称为三角测量定位法。为了方便说明，假设有三个锚节点A、B、C的坐标分别为（x1,y1）,（x2,y2），,（x3,y3）,未知节点O的位置（xo,yo），三角测量法示意图如下图所示。,7.2.3 三角测量定位技术,7.2 基于测距的定位技术,同理可确定圆心,O2,（,xo2,，,yo2,），,O3,（,xo3,，,yo3,）及对应半径,r2,，,r3,。最后利用三边测量法计算节点,O,（,x,，,y,），即：,7.2.3 三角测量定位技术,7.2 基于测距的定位技术,由上式求得,O,的坐标为：,7.2.3 三角测量定位技术,基于,AOA,定位测距技术易受外界环境影响，噪声对它的影响比较明显，而且,AOA,需要额外的硬件，比如阵列天线等，所以对具有低成本、低功耗要求的传感器网络不太适用。,7.2 基于测距的定位技术,最大似然估计法如下图所示，其基本思想是假如一个节点可以根据它和邻居节点中锚节点的距离关系构成二次方程式，当它的邻居节点足够多，就可以构造拥有唯一解的方程组，求解方程组就能得到未知节点的位置信息。,7.2.4 最大似然估计定位技术,7.2 基于测距的定位技术,几种常用的基于测距的方法的比较如下表所示。,7.2.5 测距定位算法性能比较分析,7.2 基于测距的定位技术,综上所述各定位算法的特征与性能，对各类定位算法的比较如下表所示。,7.2.5 测距定位算法性能比较分析,7.3 基于非测距定位技术,1.质心算法,多边形的几何中心称为质心，多边形顶点坐标的平均值就是质心节点的坐标。多边形ABCDE的顶点坐标分别为A（x1，y1）、B（x2，y2）、C（x3，y3）、D（x4，y4）、E（x5，y5），其质心O的坐标,请见下方公式：,质心定位算法的核心思想是根据某未知节点的通信范围内的锚节点组成多边形，求出其质心坐标，该坐标就是未知节点的估计坐标。,7.3.,2,典型算法,7.3 基于非测距定位技术,在下方图,中，A、B、C、D、E、F、G 为可以发送信息的锚节点，坐标分别为（xA，yA）、（xB，yB）、（xC，yC）、（xD，yD）、（xE，yE）、（xF，yF）、（xG，yG），O 为未知节点，坐标假设为（x，y），利用质心算法计算出的未知节点的坐标如式：,7.3.,2,典型算法,7.3 基于非测距定位技术,2.APS算法,APS是根据距离矢量路由和GPS定位的原理提出的一系列定位算法。它包括6种定位算法：DV-Hop、DV-distance、Euclidean、DV-coordinate、D-Bearing 和 DV-Radial。,（1）DV-Hop算法,DV-Hop 利用典型的距离向量机制进行定位。其基本思想是，未知节点与锚节点之间的距离用平均每跳距离与未知节点和锚节点之间的跳数总数的乘积来表示。,7.3.,2,典型算法,7.3 基于非测距定位技术,则我们可以根据公式得到A的平均每跳距离为C1，B的平均跳距为C2，C的平均跳距为C3，公式如下：,7.3.,2,典型算法,7.3 基于非测距定位技术,（2）DV-distance算法,DV-distance算法的基本原理是使用接收信号强度测距机制测量节点之间的距离，然后将与锚节点之间的距离传播出去。锚节点发送的信息中包括其在无线传感器网络中的编号、坐标信息以及一个可以变化的路径长度，该长度初始值为零，当有节点接收到这个消息后，将其测量到的距离累加到这个变量中，条件允许时将其转发出去。如果节点接收到多个锚节点的消息，那么只有现在接收的长度小于原来接收到的路径长度时才将其转发。未知节点得到三个及以上锚节点的距离信息后使用三边测量法定位。,7.3.,2,典型算法,7.3 基于非测距定位技术,3.APIT算法,APIT是由T.He等人提出一个类似于质心算法的利用三角形内点测试进行节点位置约束的定位算法。APIT即近似三角形的内点测试法，在该算法中，每个未知节点对自己附近所有的锚节点的相关信息进行监听，假设其邻居锚节点数目为n，则每次从这n个锚节点中取出3个锚节点组成一个三角形，共有Cn3种不同的组合，对于每种组合进行测试分析，判断未知节点是否位于对应组合所组成的三角形内部最后统计出所有包含未知节点的三角形组合，再而计算出所统计的三角形组合重叠区域的重心，并将该重心的位置作为待定位节点的位置。,7.3.,2,典型算法,7.3 基于非测距定位技术,4.凸规划法,凸规划定位方法将节点在无线传感器网络中的定位问题转化为凸约束优化问题，其中节点与节点之间的消息通信可以视为对节点坐标的几何约束，那样整个无线传感器网络视为一个凸集,，,如下图所示，根据未知节点与锚节点之间的通信连接和节点无线射程，计算出未知节点可能存在的区域，该区域是矩形的，然后矩形的质心就是未知节点的估计位置。,7.3.,2,典型算法,7.3 基于非测距定位技术,在基于非测距的定位算法中，质心定位算法实现较简单，由于该算法无需节点间的协调，且其是完全基于网络的连通性，因此该算法通信开销很小，但该算法对锚节点的分布及密度要求较高，只有在锚节点密度比较大的时候才有可能保证较好的定位精度，因此该算法比较适用于锚节点密度较大、分布较均匀且对定位精度要求不高的网络。,DV-Hop算法相对于质心算法拥有较好的定位精度，且该算法较易实现，硬件要求较低，但该算法对锚节点的密度大小有所依赖，且该算法的通信开销很大，因此该算法比较适用于大规模，锚节点密度较大且可人工部署锚节点的环境。,7.3.,3,几种非测距的定位技术性能分析,7.3 基于非测距定位技术,7.3.,3,几种非测距的定位技术性能分析,APIT算法定位精度相对较高，性能比较稳定，通信开销