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

《无线传感器网络概论第7章-节点定位技术概述课件.ppt》由会员分享，可在线阅读，更多相关《无线传感器网络概论第7章-节点定位技术概述课件.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第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.节点连接度（nod

2、e 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）：两种不同传播速度的信号从一个节点传播到另一节点所需要的时间之差，或两个发

3、送节点向同一个接收节点同时发送同一种性质的信号，信号传播到接收节点的时间之差。10.到达角度（angle of arrival,AOA）：节点接收信号方向相对于自身轴线的方位角度。7.1.1 节点定位相关的基本术语7.1 节点定位技术概述2.基本原理 无线传感器网络中包含大量传感器节点，通常节点的放置采用随机撒播的方式，如果依靠人工标定来确定每个节点的位置，其工作量巨大，难以完成。另一种可直接获得节点位置的方法是为每个节点配备GPS，但由于节点数目众多，考虑到价格、体积、功耗等因素的限制，通常不采取这种方案。一种较合理的方法是为部分节点事先标定好准确位置，这些节点通常称为锚节点，然后利用这些能

4、确定位置的节点提供的信息和锚节点与非锚节点之间的协作来确定非锚节点的位置，这样所有节点的准确位置就都能得到。7.1.2 节点定位技术的定义及基本原理7.1 节点定位技术概述 无线传感器网络定位问题的一般前提假设是以下四点。（1）网络具有较高的密度。（2）网络内每一个节点具有全网唯一的ID。（3）在没有特别说明的情况下所有节点具有相同的最大通信距离。（4）在定位过程中假设节点相对位置不变。7.1.2 节点定位技术的定义及基本原理7.1 节点定位技术概述 无线传感器网络节点的定位算法有很多，根据分类标准的不同，主要有以下几种分类：1.基于测距技术的定位和无需测距技术的定位2.集中式计算与分布式计算

5、3.绝对定位与相对定位7.1.3 定位算法的分类7.2 基于测距的定位技术 常见的测距机制分为到达时间测距机制、到达角度测距机制和接收信号强度测距机制。1.TOA简介 其中，到达时间TOA测距机制又分为到达时间TOA 和到达时间差TDOA。TOA测距算法的基本原理是距离等于速度和时间的乘积。速度即信号的传播速度，时间即信号从起节点到终节点的传播时间。假设求两个时间同步的节点之间的距离，起节点发送声波信号时，也将发送信号的时间一同发送给终节点，这样终节点在检测到声波信号后，信号传播时间已知，信号传播速度已知，根据公式就能计算出起节点到终节点的距离。7.2.1 测距技术7.2 基于测距的定位技术2

6、.接收信号强度指示 接收信号强度测距机制是指根据信号发射过程中信号发射使得强度和被接收到时的强度的差值，得到在传播过程中的损耗，利用该损耗计算出发射节点与接受节点之间的距离。由于该技术容易实现，对硬件要求低，所以在一些领域中都有使用。接收信号强度测距定位在实际应用中，受外界环境影响较大导致计算有很大的不稳定性，误差较大，定位精度低，所以尽管该算法功率低、成本小，但并未得到广泛应用。7.2.1 测距技术7.2 基于测距的定位技术 已知锚节点A、B、C的坐标分别为（x0,y0）、（x1,y1）、（x2,y3），未知节点D的坐标为（x,y），锚节点到未知目标节点的距离分别为d1、d2、d3。三边测量

7、定位法的基本原理就是分别求以（x0,y0）、（x1,y1）、（x2,y3）为圆心，以d1、d2、d3为半径的三个圆的交点，并以此求出未知节点的坐标，定位方程组如下式所示。7.2.2 三边定位技术7.2 基于测距的定位技术7.2.2 三边定位技术 三边测量法最大的优点是定位精度高，但是对测距过程依赖大，若该工程中出现误差，则上述3个圆无法交于一点，如下图所示。这时若用带误差的距离去计算时需要增加额外算法，使计算更加复杂。因此，三边测量法在实际定位应用不多，三边测量法一般只作为定位的理论基础知识。7.2 基于测距的定位技术 基于AOA测距的定位方法因为利用了信号到达的方向所以被称为三角测量定位法。

8、为了方便说明，假设有三个锚节点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 需要额外的硬件，比如阵列天线等，所以对具有低成本、低功耗要求的传感器网络不

9、太适用。7.2 基于测距的定位技术 最大似然估计法如下图所示，其基本思想是假如一个节点可以根据它和邻居节点中锚节点的距离关系构成二次方程式，当它的邻居节点足够多，就可以构造拥有唯一解的方程组，求解方程组就能得到未知节点的位置信息。7.2.4 最大似然估计定位技术7.2 基于测距的定位技术 几种常用的基于测距的方法的比较如下表所示。7.2.5 测距定位算法性能比较分析7.2 基于测距的定位技术 综上所述各定位算法的特征与性能，对各类定位算法的比较如下表所示。7.2.5 测距定位算法性能比较分析7.3 基于非测距定位技术1.质心算法 多边形的几何中心称为质心，多边形顶点坐标的平均值就是质心节点的坐

10、标。多边形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 典型算

11、法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

12、基于非测距定位技术（2）DV-distance算法 DV-distance算法的基本原理是使用接收信号强度测距机制测量节点之间的距离，然后将与锚节点之间的距离传播出去。锚节点发送的信息中包括其在无线传感器网络中的编号、坐标信息以及一个可以变化的路径长度，该长度初始值为零，当有节点接收到这个消息后，将其测量到的距离累加到这个变量中，条件允许时将其转发出去。如果节点接收到多个锚节点的消息，那么只有现在接收的长度小于原来接收到的路径长度时才将其转发。未知节点得到三个及以上锚节点的距离信息后使用三边测量法定位。7.3.2 典型算法7.3 基于非测距定位技术3.APIT算法 APIT是由T.He等人提出

13、一个类似于质心算法的利用三角形内点测试进行节点位置约束的定位算法。APIT即近似三角形的内点测试法，在该算法中，每个未知节点对自己附近所有的锚节点的相关信息进行监听，假设其邻居锚节点数目为n，则每次从这n个锚节点中取出3个锚节点组成一个三角形，共有Cn3种不同的组合，对于每种组合进行测试分析，判断未知节点是否位于对应组合所组成的三角形内部最后统计出所有包含未知节点的三角形组合，再而计算出所统计的三角形组合重叠区域的重心，并将该重心的位置作为待定位节点的位置。7.3.2 典型算法7.3 基于非测距定位技术4.凸规划法 凸规划定位方法将节点在无线传感器网络中的定位问题转化为凸约束优化问题，其中节点

14、与节点之间的消息通信可以视为对节点坐标的几何约束，那样整个无线传感器网络视为一个凸集，如下图所示，根据未知节点与锚节点之间的通信连接和节点无线射程，计算出未知节点可能存在的区域，该区域是矩形的，然后矩形的质心就是未知节点的估计位置。7.3.2 典型算法7.3 基于非测距定位技术 在基于非测距的定位算法中，质心定位算法实现较简单，由于该算法无需节点间的协调，且其是完全基于网络的连通性，因此该算法通信开销很小，但该算法对锚节点的分布及密度要求较高，只有在锚节点密度比较大的时候才有可能保证较好的定位精度，因此该算法比较适用于锚节点密度较大、分布较均匀且对定位精度要求不高的网络。DV-Hop算法相对于

15、质心算法拥有较好的定位精度，且该算法较易实现，硬件要求较低，但该算法对锚节点的密度大小有所依赖，且该算法的通信开销很大，因此该算法比较适用于大规模，锚节点密度较大且可人工部署锚节点的环境。7.3.3 几种非测距的定位技术性能分析7.3 基于非测距定位技术7.3.3 几种非测距的定位技术性能分析 APIT算法定位精度相对较高，性能比较稳定，通信开销小，对锚节点的分布要求也较低，但该算法对网络的连通性及锚节点的密度要求较高，一般在复杂环境下，信号传播不规则，节点需要在随机部署的网络环境中使用。7.4 协作定位技术7.4.1 刚性体理论概述 协作技术应用到无线传感器网络节点定位中就构成了协作定位技术

16、，在协作定位中，可以有未知节点与锚节点之间的通信，也可以有未知节点与未知节点之间的通信，这样可以获得更多新信息，可以提高定位系统的精度和稳定性。协作定位方法与传统定位方法相比有很大不同。1.传统定位方法与协作定位方法 传统定位方法：未知节点只与锚节点通信，即未知节点的位置直接由锚节点来确定。协作定位方法：各节点间是对等的关系，任何节点间都可以参与测量，充分利用各节点资源。7.4 协作定位技术 如下图所示，传统定位与协作定位的示意图，图中黑色点为锚节点，白色点为未知节点。7.4.1 刚性体理论概述7.4 协作定位技术 7.4.1 刚性体理论概述 左图为传统定位方式，右图为协作定位方式，都以三基站

17、定位方式为例，其中黑色圆点代表MS，A点代表MSA，B点代表MSB，C点代表MSC。7.4 协作定位技术 7.4.1 刚性体理论概述2.协作定位 在无线定位中，协作可以通过以下三种方式体现。（1）迭代协作：首先，某些节点可以收集到足够多的信息，根据这些信息算出这些节点位置；然后这些节点可转化为已知节点，参与到下一轮的位置计算中。协作过程如下图所示，N1，N2，N3是未知节点（图中黑色点），Ai（i=1，26）为锚节点（图中白色点）。7.4 协作定位技术 7.4.1 刚性体理论概述 （2）多跳协作：多跳通信是无线传感器网络通信的特点，源节点与目的节点之间的数据通信以多跳的方式进行，所以在无线传感

18、器网络节点定位技术中，包括锚节点位置信息、节点间距、角度等信息的定位数据也可以用多跳的方式来通信，通过多跳通信的方式，使不在锚节点通信范围内的未知节点也能接收到锚节点的信息，扩大了定位范围，使计算更加精确。（3）缩小定位区域：在无线传感器网络三边法定位时，由于测量误差的影响，未知节点的位置只能被确定在一块区域内，不能准确定位，若此区域过大，那么定位精度则太低。在协作定位技术中，利用协作方法获得信息并将信息优化，可缩小该定位区域，提高定位精度。7.4 协作定位技术 在无线传感器网络协作定位中，定位的第一步就是讲刚性理论应用在网络结构中，用图形结构的方式来描述网络拓扑结构。设传感器网络N中含有n个

19、节点，锚节点占整体节点的比例是s，该网络中有m=ns个锚节点，n-m个未知节点，锚节点与未知节点是随机分布的。每个节点的最大通信距离相同，只要邻近节点的距离在该最大通信距离内，未知节点就能与该邻近节点通信，这样构成通信网络。7.4.2 协作体的定义7.4 协作定位技术 在无线传感器网络协作定位技术中，构建一个稳定的定位协作体是该技术的关键，其主要过程为：无线传感器网络中的节点自主进行网络通信，构成通信链路，根据与未知节点连接的锚节点个数和形式，判断该未知节点是否可以与它的邻居锚节点构建最简单元定位协作体，然后在最简单元定位协作体的基础上依据定理4与定理5的原理将最简单定位协作体扩展，扩展的结果

20、是含有更多未知节点的定位协作体，实现更多节点的定位，同时提高定位精度。7.4.3 协作定位原理习题7.1 节点定位的基本原理是什么？节点定位有哪些评价指标？7.2 请简述三边定位技术的原理。7.3 请根据具体情况分析基于测距的定位技术和基于非测距的定位技术在性能上的优劣性。7.4 使用三边测量法，已知锚节点A、B、C的坐标分别为（10,20）、（25,35）、（30,40），锚节点到未知目标节点的距离分别为10、5、15。求目标节点的位置坐标。7.5 使用三角测量定位技术，计算上题。习题7.6 已知多边形ABCDE的顶点坐标分别为A（10,10）、B（15,10）、C（20,15）、D（25,10）、E（20,10），求其质心坐标。7.7 已知在APS算法中，A、B、C是锚节点，O是未知节点。A、B之间的距离为20m，跳数为 3跳，B、C之间的距离是70m，跳数为8跳，A、C之间距离是120m，跳数为8跳。（1）求A的平均每跳距离C1，B的平均跳距C2，C的平均跳距C3；（2）已知O点距A的最小跳数是4跳，距B点的最小跳数是2跳，距C点的最小跳数是5跳。当未知节点O收到锚节点A、B、C的平均每跳距离时，求O距离A、B、C的距离。