第05章-定位技术

第5章定位技术内容提要1.WSN定位技术简介2.定位计算方法和测距方法3.经典定位算法基于测距（range-based）的定位技术无需测距（range-free）的定位技术定位相关的其它技术典型定位系统1.WSN定位技术简介①什么是定位？②定位的应用领域③定位的技术指标④定位系统的设计要点⑤定位服务的标准化什么是定位？①定位就是确定位置。②定位的两种意义：一种是确定自己在系统中的位置；一种是系统确定目标在系统中的位置。③位置信息的类型：物理位置指目标在特定坐标系下的位置数值，表示目标的相对或者绝对位置。符号位置指在目标与一个基站或者多个基站接近程度的信息，表示目标与基站之间的连通关系，提供目标大致的所在范围。WSN定位机制的重要性•定位机制是WSN的基本机制–没有位置信息的检测消息是没有意义的；–应用：战场侦查、目标跟踪、入侵检测、灾难预报等•节点定位是基本的定位机制–随机部署的网络，需要确定节点位置；–只有节点定位以后，才能确定节点检测事件的位置；•定位的其他用途–报告事件发生的地点–目标跟踪和定位–协助路由/协作网络管理定位的应用领域①导航：了解移动物体在坐标系中的位置，指导移动物体成功到达目的地的工作②跟踪：系统实时地了解物体所处位置和移动的轨迹③虚拟现实：定位物体的位置和方向④网络路由：优化的路由可以提高系统性能、安全性，节省宝贵的电能⑤基于位置的服务（LBS,LocationBasedService）：新的增值服务定位的技术指标(1)①最重要的指标，指定位系统提供的位置信息的精确程度。绝对精度指以长度为单位度量的精度。相对精度，通常以节点之间距离的百分比来定义。②覆盖范围是另一个重要指标，它和精度是一对矛盾。精度覆盖范围超声波分米级十多米Wi-Fi和蓝牙3米100米GSM系统100米公里级定位的技术指标(2)①刷新速度是提供位置信息的频率。比如GPS每秒钟刷新1次②WSN相关的指标功耗，WSN是功耗受限制的带宽，协议栈开销+数据的有效载荷节点密度，节点密度要求越高，单次定位的通信开销越大，消耗的电能越多。定位系统的设计要点①两个主要因素：①定位机制的物理特性②相应的算法②其他设计要求：①节点密度②扩展性③鲁棒性的要求定位服务的标准化①定位系统往往是订制系统，没有统一的标准①GPS系统，事实标准②E-911，1996年美国联邦通信委员会（FCC）制定的运营商（紧急救援）服务标准现有的定位系统•GPS：精度高、实时性好、抗干扰能力强；无遮挡的室外环境、固定的基础设施、成本比较高•机器人：节点的移动性、自组织性；携带充足的能量供应和精确地测距设备、节点数量少定位算法的特点•自组织性：节点随机分布，不能依靠全局的基础设施协助定位•健壮性：节点测量数据时有误差，算法需具有良好的容错性。•能量高效：算法计算复杂度要小，减少通信开销，延长网络的生命周期。•分布式计算：节点计算自身的位置，不能将信息集中到某个节点进行计算。相关术语•信标节点和未知节点•邻居节点•跳数、跳段距离•基础设施•到达时间、到达时间差•接收信号强度指示•到达角度•视线关系、非视线关系内容提要1.WSN定位技术简介2.定位计算方法和测距方法3.经典定位算法基于测距（range-based）的定位技术无需测距（range-free）的定位技术定位相关的其它技术典型定位系统三边定位算法•已知A、B、C三个节点的坐标，以及它们到节点D的距离，确定节点D的坐标为；三角定位算法•已知A、B、C三个节点的坐标，节点D相对于节点A、B、C的角度，确定节点D的坐标；•转换为三边测量法；极大似然估计法•知1、2、3等n个节点的坐标，及它们到节点D到距离，确定节点D的坐标；•最小均方差估计算法；定位算法的分类(1)•根据定位过程中是否测量实际节点间的距离，把定位算法分为：–基于距离的（range-based）定位•利用测量节点间实际距离或方位计算未知节点位置；–距离无关的（range-free）定位•利用节点间的估计距离计算未知节点位置；测距方法•接收信号强度指示法（RSSI）•到达时间法（TOA）•到达时间差法（TDOA）•到达角法（AOA）定位算法的分类(2)•根据定位过程中节点定位先后次序的不同，把定位算法分为：•递增式的（Incremental）定位–信标节点附近的节点首先开始定位，依次向外延伸，各节点逐次进行定位；累计和传播测量误差•并发式的（Concurrent）定位–所有的节点同时进行位置计算；定位算法的分类(3)•根据根据定位过程中是否使用信标节点的位置信息，把定位算法分为：•基于信标节点（beacon-based）定位–以信标节点作为定位中的参考点，各节点定位后产生整体绝对坐标系统；•无信标节点的(beacon-free)定位–各节点先以自身作为参考点，将邻近节点纳入自己定义的坐标系中，相邻的坐标系统依次转换合并，最后产生整体相对坐标系统；内容提要1.WSN定位技术简介2.定位计算方法和测距方法3.经典定位算法基于测距（range-based）的定位技术无需测距（range-free）的定位技术定位相关的其它技术典型定位系统基于距离的定位机制•基本思想（range-based）–通过测量节点与信标节点间的实际距离或方位进行定位。•三个阶段–测距阶段：未知节点首先测量到邻居节点的距离或角度，然后进一步计算到邻近信标节点的距离或方位；–定位阶段：未知节点在计算出到达三个或三个以上信标节点的距离或角度后，利用三边测量法、三角测量法或极大似然估计法计算未知节点的坐标；–修正阶段：对求得的节点的坐标进行求精，提高定位精度，减少误差；2.基于测距（range-based）的定位技术①三边定位和多边定位①信号强度（RSS）②信号传播时间/时间差（TOA/TDOA/RTOF）③接收信号相位（PDOA）④近场电磁测距（NFER）②接收信号角度定位2.基于测距的定位技术-三边定位和多边定位信号强度（RSS）①通过信号在传播中的衰减来估计节点之间的距离②根据信道模型求解距离：③信道的时变特性：①信道由于受到多径衰减（Multi-pathFading）②非视距阻挡（Non-of-SightBlockage）的影响XddndPLdPL00log10)()(2.基于测距的定位技术-三边定位和多边定位多边定位Multilateration①多次测量方程的个数大于变量的个数②估计方法：①最小二乘（LS，LeastSquare）②极大似然（MLE,MaximumLikelihoodEstimation）③最小均方差（MMSE,MinimumMeanSquareError）A1A2A3A4A5Nr1r2r3r4r52.基于测距的定位技术-三边定位和多边定位三边定位Trilateration（多边定位特例）•多次测量方程的个数等于变量的个数•需要考虑无解的情况，求最优近似解A1A2A3Nr1r2r3A1A2A3Nr1r2r3(a)(b)2.基于测距的定位技术-三边定位和多边定位信号传播时间/时间差（TOA/TDOA/RTOF）T0T1发射机接收机发射机接收机T0T1T2T3T0T3发射机接收机T2T1TOATDOARTOFVTTd*)(012*)]()[(1203VTTTTdUSRFUSRFVVVVTTTTd**)]()[(0213Roundtriptimeofflight基于TOA定位机制（1）•基本思想–已知信号的传播速度，根据信号的传播时间来计算节点间的距离，然后利用三边或极大似然估计法等计算出节点的位置；•评价–精度高；–要求节点间精确的时间同步；–对传感器节点的硬件和功耗较高的要求；基于TOA定位机制（2）•思想：伪噪声序列信号作为声波信号；•组成：扬声器模块、麦克风模块、无线电模块和CPU模块；•过程：发送节点的扬声器模块在发送伪噪声序列信号的同时，无线电模块通过无线电同步消息通知接收节点伪噪声序列信号发送的时间，接收节点的麦克风模块在检测到伪噪声序列信号后，根据传播时间和速度计算发送节点和接收节点之间的距离；利用三边测量算法或极大似然估计算法计算出自身位置；基于TDOA的定位（1）•原理–发射节点同时发射两种不同传播速度的无线信号，接收节点根据两种信号到达的时间差以及已知这两种信号的传播速度，计算两个节点之间的距离，再通过已有基本的定位算法计算出节点的位置；接收信号相位（PDOA）通过测相位差，求出信号往返的传播时间，计算出往返距离其中，fc是信号频率，λ是信号的波长，φ是发送信号和反射信号的相位差。由上式可知d的范围是[0,λ]。不同的距离如果相差λ倍，则测量获得的相位相同。2.基于测距的定位技术-三边定位和多边定位222ccfcfcd2.基于测距的定位技术-接收信号角度定位利用角度关系定位A1A2Nα1α2A1A3A2Nβαγ1211122212111222cotcot)cot()cot(tantan)tan()tan(yxyxyxyxyx)cos1(2)()()()()()(2123232121221221211211CccCCCCCCryyxxryyxxryyxx已知一个顶点和夹角的射线确定一点已知三点和三个夹角确定一点基于AOA的定位（1）•基本思想–接收节点通过天线阵列或多个超声波接收机感知发射节点信号的到达方向，计算接收节点和发射节点之间的相对方位或角度，再通过三角测量法计算出节点的位置；基于AOA的定位过程•第一步：相邻节点之间方位角的测定–节点A的两个接收机R1、R2间距离是L，接收机连线中点的位置代表节点A位置；将两个接收机连线的中垂线作为节点A的轴线，作为确定邻居节点方位角度基准线；基于AOA的定位过程•第二步：相对信标节点的方位角测量–目标：计算与信标节点不相邻的未知节点与各信标节点之间的方位；–L节点是信标节点，A、B、C节点互为邻居节点；–⊿ABC、⊿LBC的内部角度已经计算，从而能够计算出四边形ACLB的角度信息，进而计算出信标节点L相对于节点A的方位；基于AOA的定位过程•第三步：利用方位信息计算节点的位置–从n个信标节点中任选三个信标节点A、B、C；利用三角测量算法或极大似然估计算法计算节点D坐标；•评价–不仅能确定节点的坐标，还能提供节点的方位信息；–测距技术易受外界环境影响，且需要额外硬件，不适用于大规模的传感器网络内容提要1.WSN定位技术简介2.定位计算方法和测距方法3.经典定位算法基于测距（range-based）的定位技术无需测距（range-free）的定位技术定位相关的其它技术典型定位系统3.无需测距（range-free）的定位技术①质心算法②DV-Hop算法③不定形（Amorphous）定位算法④APIT算法质心算法（1）•多边形的几何中心，称为质心，多边形顶点坐标的平均值就是质心节点的坐标。•质心定位算法首先确定包含未知节点的区域，计算这个区域的质心，并将其作为未知节点的位置质心算法（2）•基本过程–信标节点周期性向邻近节点广播信标分组，信标分组中包含信标节点的标识号和位置信息；–当未知节点接收到来自不同信标节点的信标分组数量超过某一个门限k或接收一定时间后，就确定自身位置为这些信标节点所组成的多边形的质心。•评价–简单：基于网络连通性，无信标节点和未知节点协调；–假设节点都拥有理想的球型无线信号传播模型，而实际上无线信号的传播模型；–位置估计精确度和信标节点的密度和分布有很大关系。距离向量-跳段定位算法•DistanceVector－Hop，类似于传统网络中的距离向量路由机制•基本思想–首先：计算未知节点与信标节点的最小跳数；–然后：估算平均每跳的距离，利用最小跳数乘以平均每跳距离，得到未知节点与信标节点之间的估计距离，–最后：利用三边测量法或极大似然估计法计算未知节点的坐标DV-Hop算法的定位过程•计算未知节点与每个信标节点的最小