无线传感器网络定位技术

《无线传感器网络技术》讲义第七章、定位技术2007年8月20日内容提要1.WSN定位概述2.基于测距（range-based）的定位技术3.无需测距（range-free）的定位技术4.定位相关的其它技术5.典型定位系统6.展望7.主要参考文献内容提要1.WSN定位概述2.基于测距（range-based）的定位技术3.无需测距（range-free）的定位技术4.定位相关的其它技术5.典型定位系统6.展望7.主要参考文献1.WSN定位概述①什么是定位？②定位的应用领域③定位的技术指标④定位系统的设计要点⑤定位服务的标准化1.WSN定位概述-什么是定位？①定位就是确定位置。②定位的两种意义：一种是确定及自己的在系统中的位置；一种是系统确定目标在系统中的位置。③位置信息的类型：物理位置指目标在特定坐标系下的位置数值，表示目标的相对或者绝对位置。符号位置指在目标与一个基站或者多个基站接近程度的信息，表示目标与基站之间的连通关系，提供目标大致的所在范围。1.WSN定位概述-定位的应用领域①导航：了解移动物体在坐标系中的位置，指导移动物体成功到达目的地的工作②跟踪：系统实时地了解物体所处位置和移动的轨迹③虚拟现实：定位物体的位置和方向④网络路由：优化的路由可以提高系统性能、安全性，节省宝贵的电能⑤基于位置的服务（LBS,LocationBasedService）：新的增值服务1.WSN定位概述-定位的技术指标(1)①最重要的指标，指定位系统提供的位置信息的精确程度。绝对精度指以长度为单位度量的精度。相对精度，通常以节点之间距离的百分比来定义。②覆盖范围是另一个重要指标，它和精度是一对矛盾。精度覆盖范围超声波分米级十多米Wi-Fi和蓝牙3米100米GSM系统100米公里级1.WSN定位概述-定位的技术指标(2)①刷新速度是提供位置信息的频率。比如GPS每秒钟刷新1次②WSN相关的指标功耗，WSN是功耗受限制的带宽，协议栈开销+数据的有效载荷节点密度，节点密度要求越高，单次定位的通信开销越大，消耗的电能越多。1.WSN定位概述-定位系统的设计要点①两个主要因素：①定位机制的物理特性②相应的算法②其他设计要求：①节点密度②扩展性③鲁棒性的要求1.WSN定位概述-定位服务的标准化①定位系统往往是订制系统，没有统一的标准①GPS系统，事实标准②E-911，1996年美国联邦通信委员会（FCC）制定的运营商（紧急救援）服务标准1.WSN定位概述2.基于测距（range-based）的定位技术3.无需测距（range-free）的定位技术4.定位相关的其它技术5.典型定位系统6.展望7.主要参考文献内容提要2.基于测距（range-based）的定位技术①三边定位和多边定位①信号强度（RSS）②信号传播时间/时间差（TOA/TDOA/RTOF）③接收信号相位（PDOA）④近场电磁测距（NFER）②接收信号角度定位2.基于测距的定位技术-三边定位和多边定位多边定位Multilateration①多次测量方程的个数大于变量的个数②估计方法：①最小二乘（LS，LeastSquare）②极大似然（MLE,MaximumLikelihoodEstimation）③最小均方差（MMSE,MinimumMeanSquareError）A1A2A3A4A5Nr1r2r3r4r52.基于测距的定位技术-三边定位和多边定位三边定位Trilateration（多边定位特例）•多次测量方程的个数等于变量的个数•需要考虑无解的情况，求最优近似解A1A2A3Nr1r2r3A1A2A3Nr1r2r3(a)(b)2.基于测距的定位技术-三边定位和多边定位信号强度（RSS）①通过信号在传播中的衰减来估计节点之间的距离②根据信道模型求解距离：③信道的时变特性：①信道由于受到多径衰减（Multi-pathFading）②非视距阻挡（Non-of-SightBlockage）的影响XddndPLdPL00log10)()(2.基于测距的定位技术-三边定位和多边定位信号传播时间/时间差（TOA/TDOA/RTOF）T0T1发射机接收机发射机接收机T0T1T2T3T0T3发射机接收机T2T1TOATDOARTOFVTTd*)(012*)]()[(1203VTTTTdUSRFUSRFVVVVTTTTd**)]()[(02132.基于测距的定位技术-三边定位和多边定位接收信号相位（PDOA）通过测相位差，求出信号往返的传播时间，计算出往返距离其中，fc是信号频率，λ是信号的波长，φ是发送信号和反射信号的相位差。由上式可知d的范围是[0,λ]。不同的距离如果相差λ倍，则测量获得的相位相同。222ccfcfcd2.基于测距的定位技术-三边定位和多边定位近场电磁测距（NFER）利用了在近场电场与磁场的相位差来测量距离。射频信号包括电场和磁场2部分。相位(度)范围（波长）90756045301500.10.20.30.40.5近场电磁测距方法的测距范围0.05λ~0.5λ之间，最佳测量范围0.08λ~0.3λ之间。2.基于测距的定位技术-接收信号角度定位利用角度关系定位A1A2Nα1α2A1A3A2Nβαγ1211122212111222cotcot)cot()cot(tantan)tan()tan(yxyxyxyxyx)cos1(2)()()()()()(2123232121221221211211CccCCCCCCryyxxryyxxryyxx已知一个顶点和夹角的射线确定一点已知三点和三个夹角确定一点1.WSN定位概述2.基于测距（range-based）的定位技术3.无需测距（range-free）的定位技术4.定位相关的其它技术5.典型定位系统6.展望7.主要参考文献内容提要3.无需测距（range-free）的定位技术①质心算法②DV-Hop算法③不定形（Amorphous）定位算法④APIT算法3.无需测距的定位技术-质心算法①质心（Centroid）指多边形的几何中心，是多边形顶点坐标的平均值。设多边形定点位置的向量表示为pi=（xi,yi）T，则质心为②连通度和RSSI信息的质心定位加权算法（W-Centroid）)1,1(),(11niiniiestestYnXnYX)...1(..,),(1111NiCMtsPYPPXPYXiniiniiiniiniiiestestL3AL1L23.无需测距的定位技术-DV-Hop算法①测量确定分布在2个参考节点之间的待定节点构成的多跳网络的跳数，估算出每一跳的距离，从而确定每个节点的位置。②精度：网络平均连通度为10，参考节点比例为10%的各向同性网络中定位精度约为33%。③缺点：仅仅在各向同性的密集网络中，校正值才能合理地估算平均每跳距离。3.无需测距的定位技术-不定形定位算法①在不定形计算机（AmorphousComputer）上实现的定位算法。②不定形计算机是一种并行计算结构，和智能群（蚁群、鸟群、粒子群等）很相似。③本质上，不定形算法是DV-Hop算法的增强，引入了多参考点测量进行估计求精的步骤。④两个重要的参数修正：①不定形算法通过平滑（smoothing）修正节点到参考节点的梯度跳数。②采用通信半径作为每跳距离，使得节点到参考节点的最终估计距离偏大。不定形算法采用下面的公式来修正每跳距离：3.无需测距的定位技术-APIT算法①近似三角形内点测试法（APIT,ApproximatePoint-In-Triangulationtest）找到若干个由参考节点构成的三角形，则节点必然在这些三角形的交集内。使用这个交集的重心估计节点的位置。②APIT算法分四步：（1）信标交换，（2）三角形内点测试（PIT,Point-In-Triangulationtesting），（3）交集运算计算三角形的重合区域，（4）重心（COG,CenterofGravity）计算求节点的位置。1.WSN定位概述2.基于测距（range-based）的定位技术3.无需测距（range-free）的定位技术4.定位相关的其它技术5.典型定位系统6.展望7.主要参考文献内容提要4.定位相关的其它技术①节点和事件的跟踪②测距方式对精度的影响③贝叶斯滤波④卡尔曼滤波⑤其它技术4.定位相关的其它技术-节点和事件的跟踪①定位是跟踪的技术基础②跟踪是WSN的重要应用①目标或现象的检测、定位、数据收集与分享、以及预测和组管理。②对移动的目标或者事件进行动态的监测③目标：让尽可能少的、足够的节点参与跟踪任务，最大可能地降低电能的消耗和信道的开销④方案：协同信号与信息处理(CSIP,collaborativesignalandinformationprocessing)4.定位相关的其它技术-测距方式对精度的影响①Radio（VHF、UWB、CDMA、光、红外光）0.10.31310301003001K3K技术壁垒室内室外局域室外全球GSM/3G蜂窝电话Cell-IDAOATOATDOAGPSDGPSWLANDECT蓝牙RSSTDOA专有微波方案TDOARTOF自动化/控制等跟踪/导航等一米的壁垒：更高的精度非常困难4.定位相关的其它技术-测距方式对精度的影响②声音（声波、超声波）①超声波的传播速度约300m/s，设TDOA达到的时钟精度为1ms，则测距精度30cm。②1ms的时钟精度是很低的，经过优化的时间同步方案可以提供几十微秒的精度。那么使用超声波测距的方法可以达到1cm的精度。③超声波的传播速度受到环境的影响，同时传播距离在几米到几十米的范围。由于声波接收的方向性，需要小心的部署。4.定位相关的其它技术-贝叶斯滤波①滤波可以看作是根据观测数据，推断系统内部状态的过程。顺序估计就是通过后验密度（PosteriorDensity）②给定了滤波密度就可以通过估计子计算系统的状态。估计子有很多种，最常用的是均值估计子：③实际应用：顺序蒙特卡罗（SMC,sequentialMonteCarlo）和马尔可夫蒙特卡罗（MCMC,MarkovChainMonteCarlo）的基本原理。kkkkkkpyyyYxxxXYX,,,,),|(2121且其中kkkkkkkdpExYxxYxx)|(|ˆ4.定位相关的其它技术-卡尔曼滤波①卡尔曼滤波：贝叶斯滤波的特例②要求：线性系统，高斯噪声③非线性非高斯系统：扩展卡尔曼滤波①线性化运动方程和观测方程②Jacobian矩阵计算协方差④非察觉型卡尔曼滤波器（UnscentedKalmanfilter）①更加精确的捕捉真实的均值和方差的方法②使用一个确定的采样技术选取均值附近的采样点的最小集合（SigmaPoints,SP）4.定位相关的其它技术-其它技术①模式匹配②数据融合等算法③数据压缩④数据库⑤多媒体技术以RADAR系统为例，该系统采用RSS方式进行实时定位，定位主要分成两个阶段：（1）离线阶段测量并记录移动节点在现场不同位置情况下各个参考节点的RSS，构成RSS指纹库（footprint）；（2）实时阶段将收到的信号强度与指纹库中的数据进行比较，估计出节点位置。1.WSN定位概述2.基于测距（range-based）的定位技术3.无需测距（range-free）的定位技术4.定位相关的其它技术5.典型定位系统6.展望7.主要参考文献内容提要5.典型定位系统①全球和区域导航系统①全球导航系统②地区导航系统②无线传感器网络定位系统①使用RSS方式定位的系统②使用TOA/TDOA方式定位的系统③混合定位系统④无需测距的定位系统5.典型定位系统-全球和区域导航系统①全球导航系统：全球范围①GPSGPS（GlobalPositioningSystem）二十世纪70年代由美国陆海空