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

无线传感器网络概论第7章节点定位技术概述本章目录7.1节点定位技术概述7.2基于测距的定位技术7.3基于非测距定位技术7.4协作定位技术7.1节点定位技术概述1.锚节点（beaconnode）：也称参考节点，即已知自身位置信息的节点，可通过GPS定位设备或人工部署等方式预先获取位置信息，为其他节点提供参考坐标。2.未知节点（blindnode）：也称盲节点、普通节点，即自身位置未知的节点，需要定位的节点。3.邻居节点（neighborhoodnode）：如果两个节点之间能够相互通信发送消息，则它们互称为邻居节点。4.跳数（hopcount）：两个节点之间跳段的总数。5.节点连接度（nodedegree）：就是节点可以探测发现到的邻居节点个数。6.网络连接度（networkdegree）：就是所有节点的邻居个数取平均值，反映传感器配置的密集程度。7.1.1节点定位相关的基本术语7.1节点定位技术概述7.接收信号强度（receivesignalstrengthindicator,RSSI）：节点接收到无线信号的强度大小。8.到达时间（timeofarrival,TOA）：信号从一个节点传播到另一节点所需要的时间。9.到达时间差（timedifferentofarrival,TDOA）：两种不同传播速度的信号从一个节点传播到另一节点所需要的时间之差，或两个发送节点向同一个接收节点同时发送同一种性质的信号，信号传播到接收节点的时间之差。10.到达角度（angleofarrival,AOA）：节点接收信号方向相对于自身轴线的方位角度。7.1.1节点定位相关的基本术语7.1节点定位技术概述1.定义无线传感器节点定位，即通过一定的技术、方法和手段获取节点的绝对（相对于地理经纬度）或相对位置信息的过程。节点定位技术就是借助少数锚节点，通过邻居节点之间的距离测量、角度测量或连通信息、拓扑关系估算未知节点的位置。7.1.2节点定位技术的定义及基本原理7.1节点定位技术概述2.基本原理无线传感器网络中包含大量传感器节点，通常节点的放置采用随机撒播的方式，如果依靠人工标定来确定每个节点的位置，其工作量巨大，难以完成。另一种可直接获得节点位置的方法是为每个节点配备GPS，但由于节点数目众多，考虑到价格、体积、功耗等因素的限制，通常不采取这种方案。一种较合理的方法是为部分节点事先标定好准确位置，这些节点通常称为锚节点，然后利用这些能确定位置的节点提供的信息和锚节点与非锚节点之间的协作来确定非锚节点的位置，这样所有节点的准确位置就都能得到。7.1.2节点定位技术的定义及基本原理7.1节点定位技术概述无线传感器网络定位问题的一般前提假设是以下四点。（1）网络具有较高的密度。（2）网络内每一个节点具有全网唯一的ID。（3）在没有特别说明的情况下所有节点具有相同的最大通信距离。（4）在定位过程中假设节点相对位置不变。7.1.2节点定位技术的定义及基本原理7.1节点定位技术概述无线传感器网络节点的定位算法有很多，根据分类 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的不同，主要有以下几种分类：1.基于测距技术的定位和无需测距技术的定位2.集中式计算与分布式计算3.绝对定位与相对定位7.1.3定位算法的分类7.1节点定位技术概述在无线传感器网络的某些重要功能，如环境监控、目标定位、未知空间探测中，节点定位技术起着奠定基础的作用。节点定位技术及其算法是无线传感器网络最基本的功能之一，在整个无线传感器网络中占据重要地位。首先，无线传感器网络是基于应用的网络，在许多实际的应用场景中，只有知道了发生事件的节点的准确位置，控制中心才能够根据位置及发生的事件作出相应的反应。其次，如果要确定整个网络的覆盖范围，也需要知道节点位置信息。最后，许多无线传感器网络路由 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 也是基于节点位置信息的。7.1.4节点定位的意义及必要性7.2基于测距的定位技术常见的测距 机制 综治信访维稳工作机制反恐怖工作机制企业员工晋升机制公司员工晋升机制员工晋升机制图 分为到达时间测距机制、到达角度测距机制和接收信号强度测距机制。1.TOA简介其中，到达时间TOA测距机制又分为到达时间TOA和到达时间差TDOA。TOA测距算法的基本原理是距离等于速度和时间的乘积。速度即信号的传播速度，时间即信号从起节点到终节点的传播时间。假设求两个时间同步的节点之间的距离，起节点发送声波信号时，也将发送信号的时间一同发送给终节点，这样终节点在检测到声波信号后，信号传播时间已知，信号传播速度已知，根据公式就能计算出起节点到终节点的距离。7.2.1测距技术7.2基于测距的定位技术2.接收信号强度指示接收信号强度测距机制是指根据信号发射过程中信号发射使得强度和被接收到时的强度的差值，得到在传播过程中的损耗，利用该损耗计算出发射节点与接受节点之间的距离。由于该技术容易实现，对硬件要求低，所以在一些领域中都有使用。接收信号强度测距定位在实际应用中，受外界环境影响较大导致计算有很大的不稳定性，误差较大，定位精度低，所以尽管该算法功率低、成本小，但并未得到广泛应用。7.2.1测距技术7.2基于测距的定位技术基于TOA测距的定位技术因为利用了节点与三个及以上锚节点的距离来定位，所以又被称为三边定位技术。三边测量法的示意图如下图所示。7.2.2三边定位技术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三边定位技术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基于测距的定位技术假设各个锚节点已通过天线阵列测量得到节点O发出信号的到达方向，方位角确定之后，可计算出∠AOC、∠COB和∠AOB。节点A、C和∠AOC可以唯一确定一个圆心为O1（xo1,yo1），半径为r1的圆，其中∠AOB=2π-2∠AOB。则通过以下方程组能够确定圆心O1和半经r1：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测距定位算法性能比较 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 7.2基于测距的定位技术综上所述各定位算法的特征与性能，对各类定位算法的比较如下表所示。7.2.5测距定位算法性能比较分析7.3基于非测距定位技术现有的非测距定位算法，一般基于一跳或多跳原理，即节点不需要知道邻居节点的距离和方位，只需要能够通信并确定其邻居节点。如下图所示，节点A分别被节点B、C感知到与自己存在一跳关系，其中假设节点具有理想的球型传播模型，且节点通信半径为r。多跳几何原理则是对节点信息广播的过程进行跳数统计，然后使用两节点间的跳数信息，估算它们间的距离。7.3.1基本原理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基于非测距定位技术（1）DV-Hop算法定位过程：未知节点计算到每个锚节点的跳数、计算平均每跳距离和计算未知节点坐标下面我们举DV-Hop算法的一个简单的例子。A、B、C是锚节点，O是未知节点。A、B之间的距离为30m，跳数为2跳，B、C之间的距离是60m，跳数为5跳，A、C之间距离是100m，跳数为6跳。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算法PIT（PerfectPointinTriangulationTest）是最佳三角形内点测试法，即测试未知节点是在三个锚节点所组成的三角形内部还是外部。如下图所示，点M与另外三个节点A、B、C所组成三角形处于同一平面，如果存在这样一个方向使得节点M沿着该方向移动则该节点会同时接近或远离三角形的任一节点，则可判断此节点在三角形外，否则，则可判断此节点在三角形内部。内点测试的示意图如下：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算法定位精度相对较高，性能比较稳定，通信开销小，对锚节点的分布要求也较低，但该算法对网络的连通性及锚节点的密度要求较高，一般在复杂环境下，信号传播不规则，节点需要在随机部署的网络环境中使用。7.4协作定位技术7.4.1刚性体理论概述协作技术应用到无线传感器网络节点定位中就构成了协作定位技术，在协作定位中，可以有未知节点与锚节点之间的通信，也可以有未知节点与未知节点之间的通信，这样可以获得更多新信息，可以提高定位系统的精度和稳定性。协作定位方法与传统定位方法相比有很大不同。1.传统定位方法与协作定位方法传统定位方法：未知节点只与锚节点通信，即未知节点的位置直接由锚节点来确定。协作定位方法：各节点间是对等的关系，任何节点间都可以参与测量，充分利用各节点资源。7.4协作定位技术如下图所示，传统定位与协作定位的示意图，图中黑色点为锚节点，白色点为未知节点。7.4.1刚性体理论概述7.4协作定位技术7.4.1刚性体理论概述左图为传统定位方式，右图为协作定位方式，都以三基站定位方式为例，其中黑色圆点代表MS，A点代表MSA，B点代表MSB，C点代表MSC。7.4协作定位技术7.4.1刚性体理论概述2.协作定位在无线定位中，协作可以通过以下三种方式体现。（1）迭代协作：首先，某些节点可以收集到足够多的信息，根据这些信息算出这些节点位置；然后这些节点可转化为已知节点，参与到下一轮的位置计算中。协作过程如下图所示，N1，N2，N3是未知节点（图中黑色点），Ai（i=1，2…6）为锚节点（图中白色点）。7.4协作定位技术7.4.1刚性体理论概述（2）多跳协作：多跳通信是无线传感器网络通信的特点，源节点与目的节点之间的数据通信以多跳的方式进行，所以在无线传感器网络节点定位技术中，包括锚节点位置信息、节点间距、角度等信息的定位数据也可以用多跳的方式来通信，通过多跳通信的方式，使不在锚节点通信范围内的未知节点也能接收到锚节点的信息，扩大了定位范围，使计算更加精确。（3）缩小定位区域：在无线传感器网络三边法定位时，由于测量误差的影响，未知节点的位置只能被确定在一块区域内，不能准确定位，若此区域过大，那么定位精度则太低。在协作定位技术中，利用协作方法获得信息并将信息优化，可缩小该定位区域，提高定位精度。7.4协作定位技术在无线传感器网络协作定位中，定位的第一步就是讲刚性理论应用在网络结构中，用图形结构的方式来描述网络拓扑结构。设传感器网络N中含有n个节点，锚节点占整体节点的比例是s，该网络中有m=ns个锚节点，n-m个未知节点，锚节点与未知节点是随机分布的。每个节点的最大通信距离相同，只要邻近节点的距离在该最大通信距离内，未知节点就能与该邻近节点通信，这样构成通信网络。7.4.2协作体的定义7.4协作定位技术在无线传感器网络协作定位技术中，构建一个稳定的定位协作体是该技术的关键，其主要过程为：无线传感器网络中的节点自主进行网络通信，构成通信链路，根据与未知节点连接的锚节点个数和形式，判断该未知节点是否可以与它的邻居锚节点构建最简单元定位协作体，然后在最简单元定位协作体的基础上依据定理4与定理5的原理将最简单定位协作体扩展，扩展的结果是含有更多未知节点的定位协作体，实现更多节点的定位，同时提高定位精度。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的距离。