第07章、定位技术v1.1.ppt

1、无线传感器网络技术讲义,第七章、定位技术,2007年8月20日,内容提要,WSN定位概述 基于测距（range-based）的定位技术 无需测距（range-free）的定位技术 定位相关的其它技术 典型定位系统 展望 主要参考文献,内容提要,WSN定位概述 基于测距（range-based）的定位技术 无需测距（range-free）的定位技术 定位相关的其它技术 典型定位系统 展望 主要参考文献,1. WSN定位概述,什么是定位？ 定位的应用领域 定位的技术指标 定位系统的设计要点 定位服务的标准化,1. WSN定位概述-什么是定位？,定位就是确定位置。 定位的两种意义： 一种是确定及自己

2、的在系统中的位置； 一种是系统确定目标在系统中的位置。 位置信息的类型： 物理位置指目标在特定坐标系下的位置数值，表示目标的相对或者绝对位置。 符号位置指在目标与一个基站或者多个基站接近程度的信息，表示目标与基站之间的连通关系，提供目标大致的所在范围。,1. WSN定位概述-定位的应用领域,导航：了解移动物体在坐标系中的位置，指导移动物体成功到达目的地的工作 跟踪：系统实时地了解物体所处位置和移动的轨迹 虚拟现实：定位物体的位置和方向 网络路由：优化的路由可以提高系统性能、安全性，节省宝贵的电能 基于位置的服务（LBS, Location Based Service） ：新的增值服务,1. W

3、SN定位概述-定位的技术指标(1),最重要的指标，指定位系统提供的位置信息的精确程度。 绝对精度指以长度为单位度量的精度。 相对精度，通常以节点之间距离的百分比来定义。 覆盖范围是另一个重要指标，它和精度是一对矛盾。,1. WSN定位概述-定位的技术指标(2),刷新速度是提供位置信息的频率。比如GPS每秒钟刷新1次 WSN相关的指标 功耗，WSN是功耗受限制的 带宽，协议栈开销+数据的有效载荷 节点密度，节点密度要求越高，单次定位的通信开销越大，消耗的电能越多。,1. WSN定位概述-定位系统的设计要点,两个主要因素： 定位机制的物理特性 相应的算法 其他设计要求： 节点密度 扩展性 鲁棒性的

4、要求,1. WSN定位概述-定位服务的标准化,定位系统往往是订制系统，没有统一的标准 GPS系统，事实标准 E-911，1996年美国联邦通信委员会（FCC） 制定的运营商（紧急救援）服务标准,WSN定位概述 基于测距（range-based）的定位技术 无需测距（range-free）的定位技术 定位相关的其它技术 典型定位系统 展望 主要参考文献,内容提要,2. 基于测距（range-based）的定位技术,三边定位和多边定位 信号强度（RSS） 信号传播时间/时间差（TOA/TDOA/RTOF） 接收信号相位（PDOA） 近场电磁测距（NFER） 接收信号角度定位,2. 基于测距的定位技

5、术-三边定位和多边定位,多边定位Multilateration 多次测量方程的个数大于变量的个数 估计方法： 最小二乘（LS，Least Square） 极大似然（MLE, Maximum Likelihood Estimation） 最小均方差（MMSE, Minimum Mean Square Error）,2. 基于测距的定位技术-三边定位和多边定位,三边定位Trilateration（多边定位特例） 多次测量方程的个数等于变量的个数 需要考虑无解的情况，求最优近似解,2. 基于测距的定位技术-三边定位和多边定位,信号强度（RSS ） 通过信号在传播中的衰减来估计节点之间的距离 根据信道

6、模型求解距离： 信道的时变特性： 信道由于受到多径衰减（Multi-path Fading） 非视距阻挡（Non-of-Sight Blockage）的影响,2. 基于测距的定位技术-三边定位和多边定位,信号传播时间/时间差（TOA/TDOA/RTOF）,TOA,TDOA,RTOF,2. 基于测距的定位技术-三边定位和多边定位,接收信号相位（PDOA） 通过测相位差，求出信号往返的传播时间，计算出往返距离 其中，fc是信号频率，是信号的波长，是发送信号和反射信号的相位差。由上式可知d的范围是0, 。不同的距离如果相差倍，则测量获得的相位相同。,2. 基于测距的定位技术-三边定位和多边定位,近场

7、电磁测距（NFER） 利用了在近场电场与磁场的相位差来测量距离。射频信号包括电场和磁场2部分。,近场电磁测距方法的测距范围0.05 0.5 之间，最佳测量范围0.08 0.3 之间。,2. 基于测距的定位技术-接收信号角度定位,利用角度关系定位,已知一个顶点和夹角的射线确定一点,已知三点和三个夹角确定一点,WSN定位概述 基于测距（range-based）的定位技术 无需测距（range-free）的定位技术 定位相关的其它技术 典型定位系统 展望 主要参考文献,内容提要,3. 无需测距（range-free）的定位技术,质心算法 DV-Hop算法 不定形（Amorphous）定位算法 API

8、T算法,3. 无需测距的定位技术-质心算法,质心（Centroid）指多边形的几何中心，是多边形顶点坐标的平均值。设多边形定点位置的向量表示为 pi=（xi, yi）T，则质心为 连通度和RSSI信息的质心定位加权算法（W-Centroid）,3. 无需测距的定位技术- DV-Hop算法,测量确定分布在2个参考节点之间的待定节点构成的多跳网络的跳数，估算出每一跳的距离，从而确定每个节点的位置。 精度：网络平均连通度为10，参考节点比例为10%的各向同性网络中定位精度约为33%。 缺点：仅仅在各向同性的密集网络中，校正值才能合理地估算平均每跳距离。,3. 无需测距的定位技术-不定形定位算法,在不

9、定形计算机（Amorphous Computer）上实现的定位算法。 不定形计算机是一种并行计算结构，和智能群（蚁群、鸟群、粒子群等）很相似。 本质上，不定形算法是DV-Hop算法的增强，引入了多参考点测量进行估计求精的步骤。 两个重要的参数修正： 不定形算法通过平滑（smoothing）修正节点到参考节点的梯度跳数。 采用通信半径作为每跳距离，使得节点到参考节点的最终估计距离偏大。不定形算法采用下面的公式来修正每跳距离：,3. 无需测距的定位技术- APIT算法,近似三角形内点测试法（APIT, Approximate Point-In-Triangulation test）找到若干个由参考

10、节点构成的三角形，则节点必然在这些三角形的交集内。使用这个交集的重心估计节点的位置。 APIT算法分四步：（1）信标交换，（2）三角形内点测试（PIT, Point-In-Triangulation testing），（3） 交集运算计算三角形的重合区域，（4）重心（COG, Center of Gravity）计算求节点的位置。,WSN定位概述 基于测距（range-based）的定位技术 无需测距（range-free）的定位技术 定位相关的其它技术 典型定位系统 展望 主要参考文献,内容提要,4. 定位相关的其它技术,节点和事件的跟踪 测距方式对精度的影响 贝叶斯滤波 卡尔曼滤波 其它技

11、术,4. 定位相关的其它技术-节点和事件的跟踪,定位是跟踪的技术基础 跟踪是WSN的重要应用 目标或现象的检测、定位、数据收集与分享、以及预测和组管理。 对移动的目标或者事件进行动态的监测 目标：让尽可能少的、足够的节点参与跟踪任务，最大可能地降低电能的消耗和信道的开销 方案：协同信号与信息处理(CSIP, collaborative signal and information processing),4. 定位相关的其它技术-测距方式对精度的影响,Radio（VHF、UWB、CDMA、光、红外光）,一米的壁垒：更高的精度非常困难,4. 定位相关的其它技术-测距方式对精度的影响,声音（声波、

12、超声波） 超声波的传播速度约300m/s，设TDOA达到的时钟精度为1ms，则测距精度30cm。 1ms的时钟精度是很低的，经过优化的时间同步方案可以提供几十微秒的精度。那么使用超声波测距的方法可以达到1cm的精度。 超声波的传播速度受到环境的影响，同时传播距离在几米到几十米的范围。由于声波接收的方向性，需要小心的部署。,4. 定位相关的其它技术-贝叶斯滤波,滤波可以看作是根据观测数据，推断系统内部状态的过程。顺序估计就是通过后验密度（Posterior Density） 给定了滤波密度就可以通过估计子计算系统的状态。估计子有很多种，最常用的是均值估计子： 实际应用：顺序蒙特卡罗（SMC, s

13、equential Monte Carlo）和马尔可夫蒙特卡罗（MCMC, Markov Chain Monte Carlo）的基本原理。,4. 定位相关的其它技术-卡尔曼滤波,卡尔曼滤波：贝叶斯滤波的特例 要求：线性系统，高斯噪声 非线性非高斯系统：扩展卡尔曼滤波 线性化运动方程和观测方程 Jacobian矩阵计算协方差 非察觉型卡尔曼滤波器（Unscented Kalman filter） 更加精确的捕捉真实的均值和方差的方法 使用一个确定的采样技术选取均值附近的采样点的最小集合（Sigma Points, SP）,4. 定位相关的其它技术-其它技术,模式匹配 数据融合等算法 数据压缩 数

14、据库 多媒体技术,以RADAR系统为例，该系统采用RSS方式进行实时定位，定位主要分成两个阶段： （1） 离线阶段测量并记录移动节点在现场不同位置情况下各个参考节点的RSS，构成RSS指纹库（footprint）；（2） 实时阶段将收到的信号强度与指纹库中的数据进行比较，估计出节点位置。,WSN定位概述 基于测距（range-based）的定位技术 无需测距（range-free）的定位技术 定位相关的其它技术 典型定位系统 展望 主要参考文献,内容提要,5. 典型定位系统,全球和区域导航系统 全球导航系统 地区导航系统 无线传感器网络定位系统 使用RSS方式定位的系统 使用TOA/TDOA方

15、式定位的系统 混合定位系统 无需测距的定位系统,5. 典型定位系统-全球和区域导航系统,全球导航系统：全球范围 GPS GPS（Global Positioning System）二十世纪70年代由美国陆海空三军联合研制的新一代空间卫星导航定位系统。 起初为了军事目的。 Galileo系统 伽利略系统（GALILEO satellite radio navigation system）是欧洲自主的、独立的全球多模式卫星定位导航系统，提供高精度、高可靠性的定位服务，同时它实现完全非军方控制、管理。,5. 典型定位系统-全球和区域导航系统,全球导航系统：全球范围 GPS GPS使用24颗人造卫星在

16、离地面约2万公里的高空上，以12小时的周期环绕地球运行。在地面上的任意一点都可以同时观测到4颗以上的卫星。由于卫星的位置精确可知，通过4颗卫星发出的信号，我们可得到卫星到接收机的距离。 GPS精度达到5m，专用车载GPS导航仪已经广泛使用于车辆导航等应用领域。,5. 典型定位系统-全球和区域导航系统,全球导航系统：全球范围 Galileo系统 伽利略系统是中高度圆轨道（MEO）方案，该系统将由30颗中高度圆轨道卫星和2个地面控制中心组成，其中27颗卫星为工作卫星，3颗为候补。卫星高度为24126公里，位于3个倾角为56度的轨道平面内。 伽利略系统可以分发实时的米级定位精度信息，这是现有的卫星导

17、航系统所没有的。同时伽利略系统能够保证在许多特殊情况下提供服务,5. 典型定位系统-全球和区域导航系统,地区导航系统：区域范围 LORAN系统 LORAN（LOng RAnge Navigation）是一种地区导航系统。基站以一定的时间间隔发送低频无线信号，船只、飞机等接收到多个信号基站的信号后，可以计算出自身所处的位置。LORAN系统发展经历LORAN-A、LORAN-C、LORAN-D和LORAN-F，最为重要的是LORAN-C系统。LORAN-C是测量脉冲和测量相位相结合的双曲线导航系统，工作频段90110kHz，1957年开始建设，直到现在已经建成大量电台链，覆盖了北半球大部分地区。

18、北斗 北斗双星定位系统是我国自行建立起来的一种区域性定位系统（RDSS）。2003年5月25日，我国成功发射了第三颗“北斗一号”导航定位卫星，作为“北斗导航定位系统”的备份星，连同2000年10月31日和12月21日发射升空的两颗“北斗一号”导航定位卫星和一个地面中心站，形成了一个较为完善的“双星导航定位系统”。“双星导航定位系统”应归于“卫星无线电定位服务”（RDSS）。,5. 典型定位系统-无线传感器网络定位系统,使用RSS方式定位的系统 RADAR（1998） Microsoft的RADAR定位系统利用“指纹识别”技术进行定位，解决WLAN中定位移动计算设备的问题。 SpotON（199

19、9）,5. 典型定位系统-无线传感器网络定位系统,使用RSS方式定位的系统 RADAR（1998） 通过对特定环境下的RF信号衰落特征值进行处理实现的。 数据处理处理分成2个阶段：离线阶段（office-line phase）和实时阶段（real-time phase）。离线阶段记录目标节点的位置所对应3个基站的信号信息，生成以位置为变量的信号信息函数。实时阶段在采集3个基站的信号信息，根据信号信息函数求解位置。,5. 典型定位系统-无线传感器网络定位系统,使用RSS方式定位的系统 SpotON（1999） SpotOn标签的硬件由Dragonball EZ处理器、在916.5MHz的TR10

20、00射频收发器和10-bit A/D转换器构成。 该系统基于射频接收信号强度（RSS）分析的三维位置感知方法，实现小范围内的定位。,5. 典型定位系统-无线传感器网络定位系统,使用TOA/TDOA方式定位的系统 Bat System（1999） Cricket（2000）,5. 典型定位系统-无线传感器网络定位系统,使用TOA/TDOA方式定位的系统 Bat System（1999） Cricket（2000）,室内定位系统Badge系统是Active Badge的后继发展，是一种基于测距（range-based）的定位技术。如图 719，该系统使用超声波信号的TOA实现三维空间定位，使用多边

21、定位方法提高精度。Bat系统的定位精度最高达到3cm。,MIT提出了一种融合TDOA和信号到达相位差的硬件解决方案Cricket Compass，其原型系统可在40角内以5的误差确定接收信号方向。 Cricket系统是麻省理工学院的Oxygen项目的一部分，用来确定移动或静止节点在大楼内的具体所在房间位置。该定位系统利用射频信号与超声波信号到达时间间隔和各自的传播速度，计算出未知位置节点到已知位置节点的距离。,5. 典型定位系统-无线传感器网络定位系统,混合定位系统 Calamari AHLoS（Ad Hoc Localization System）（2001）,两个系统本质上都是cell-b

22、ased方式定位的系统,5. 典型定位系统-无线传感器网络定位系统,混合定位系统 Calamari,Calamar采用超声波传播时间（TOA）和接收电信号强度（RSS）方式定位。使用超声波的测距，将49个节点部署在144 平方米的范围。定位中等误差0.53m。使用RSS，系统分别在半个足球场，定位中等误差4.1m。,5. 典型定位系统-无线传感器网络定位系统,混合定位系统 AHLoS（Ad Hoc Localization System）（2001） AHLoS使用RSS进行接近情况探测，同时使用RF和超声波的收发时间进行TDOA测量。 AHLoS系统中使用3种多边定位算法：原子式（atom

23、multilateration）、协作式（collaborative multilateration）和迭代式（iterative multilateration）。原子式多边定位就是普通的最大似然估计定位。,5. 典型定位系统-无线传感器网络定位系统,无需测距的定位系统 Active Badge（1992） 每一个目标上安装一个badge。每个badge周期地每15秒钟，红外线发送大约持续0.1秒的唯一ID号。已知位置的参考节点收到这些信号，传送到网络。系统知道当前某个badge在哪一个cell附近。Active Badge系统的缺点是部署大规模网络困难，同时，红外线容易受到光线的干扰，尤其

24、是在户外。因此，Active Badge是一个室内的基于蜂窝单元（cell-based）的定位系统。,5. 典型定位系统-无线传感器网络定位系统,无需测距的定位系统 UC Berkeley（2006） 使用Trio传感器节点 多传感器融合算法，使用空间相关性，融合后的二进制测量值提供更加精细的位置信息。融合后的数据通过数据关联的马尔可夫-蒙特卡罗算法（Markov chain Monte Carlo Data Association - MCMCDA） 跟踪未知个数的目标。,WSN定位概述 基于测距（range-based）的定位技术 无需测距（range-free）的定位技术 定位相关的其它

25、技术 典型定位系统 展望 主要参考文献,内容提要,6. 展望,UWB定位 Nanotron CSS定位,6. 展望-UWB定位,随着通信技术，特别是物理层的发展，UWB（Ultra Wide Band，超宽带）可能成为下一个广泛使用的技术。UWB具有一系列优良独特的技术特性，是一种极具竞争力的短距无线传输技术。UWB不采用正弦载波，而是利用纳秒级的非正弦波窄脉冲传输数据，因此其所占的频谱范围很宽。UWB适用于高速、近距离的无线个人通信。按照FCC的规定，从3.1GHz到10.6GHz之间的7.5GHz的带宽频率为UWB所使用的频率范围。 UWB解决了困扰传统无线技术多年的有关传播方面的重大难题

26、，具有对信道衰落不敏感、发射信号功率谱密度低、被截获的可能性低、系统复杂度低、厘米级的定位精度等优点。 虽然UWB有厘米级的定位精度，但是UWB的通信范围仅有几米，对于很多定位和跟踪应用，几米的范围显然太小了。,6. 展望-Nanotron CSS定位,2006年10月最终确定为德国Nanotron公司的CSS提案为IEEE 802.15.4a标准，淘汰了UWB方案。CSS（Chirp Spread Spectrum）工作于ISM 2.4GHz。用于电池供电和中等速率应用场合，提供可靠的传输。CSS是啁啾脉冲的MDMA （Multi Dimensional Multiple Access）调制

27、技术的首次实现。MDMA调制技术基于啁啾脉冲的调制技术，与海豚、蝙蝠定位原理相似，具有鲁棒性，电路简单的特点，因此，可以增加电池使用时间和降低成本。数据速率可以根据应用需要调整，最优化使用信道。,6. 展望-Nanotron CSS定位,CSS提供中等带宽（1 to 2 Mbps）、低功耗，高距离。当chirp pulse的持续时间固定为1s，数据率达到2Mbps。 CSS还考虑到定位需求，提供SDS-TWR （Symmetrical Double-Sided Two Way Ranging）测距服务，以TOA的方式测距、定位，用于确定使用CSS调制方式通信的两个无线设备直接距离的方法，使用了

28、相当复杂的算法。 CSS的最大通信范围是室内环境60米的、户外环境900米。这是一个相当大的覆盖范围，提供几十厘米的精度。就目前技术而言，这种定位技术方案相对于基于Wi-Fi和超声波技术的定位系统有一定应用范围内的优势。,主要参考文献,1 S. S. Wang, M. Green, and M. Malkawa, “E-911 Location Standards and Location Commercial Services,” Proceedings of IEEE Emerging Technologies Symposium on Broadband, Wireless Intern

29、et Access, April 2000. 2 N.B. Priyantha, A. Chakraborty, and H. Balakrishnan. The Cricket location-support system. In ACM/IEEE MOBICOM, 3243, 2000. 3 Niculescu D, Nath B. DV based positioning in ad hoc networks. Journal of Telecommunication Systems, 2003,22(1/4):267-280. 4 Nicolescu D, Nath B. Ad-Ho

30、c positioning systems (APS). In: Proc. of the 2001 IEEE Global Telecommunications Conf. Vol.5, San Antonio: IEEE Communications Society, 2001. 2926-2931 5 P. Bahl V. N. Padmanabhan, RADAR: An In-Building RF-Based User Location and Tracking System, Proceedings of IEEE INFOCOM 2000, Vol. 2, Tel-Aviv,

31、Israel (March 2000): 775-784 6 D. Moore, J. Leonard, D. Rus, and S. Teller, “Robust Distributed Network Localization with Noisy Range Measurement,” SenSys04, Nov 2004. 7 D. Niculescu and B. Nath. Ad hoc positioning system (APS) using AoA. In IEEE INFOCOM, San Francisco, 2003, pp. 17341743. 8 N. Bulu

32、su, J. Heidemann, D. Estrin. Density Adaptive Algorithms for Beacon Placement in Wireless Sensor Networks. Technical Report ULCA-CS-010013, 2001 9 X. Shen, Z. Wang, P. Jiang, R. Lin, and Y. Sun, Connectivity and RSSI Based Localization Scheme for Wireless Sensor Networks. 2005 International Conferen

33、ce on Intelligent Computing, Lecture Notes on Computer Science. Vol.3645, p.578-587, Aug.2005. 10 D. Niculescu, and B. Nath, “Ad Hoc Positioning System (APS)”, Proceedings of IEEE Globecom 2001, Texas, USA, pp. 2826-2931, November, 2001.,主要参考文献,11 D. Niculescu, and B. Nath, “DV-based Positioning in

34、Ad Hoc Networks”, Kluwer Journal of Telecommunication Systems, Vol. 22, No. 1, pp. 267-280, January, 2003. 12 R. Nagpal, H. Shrobe, and J. Bachrach. Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network. In Proceedings of 2nd Intl Workshop on Information Processing

35、 in Sensor Networks(IPSN03). Palo Alto, USA, April 2003. 13 T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher. Range-Free Localization Schemes for Large Scale Sensor Networks. Proc. 9th Annual Intl Conf. on Mobile Computing and Networking(MobiCom), San Diego, CA., 2003. pp. 8195 14 F.

36、Zhao, J. Liu, J. J. Liu, L. Guibas, and J. Reich. Collaborative signal and information processing: an information directed approach. Proceedings of IEEE, 91(8):11991209, 2003. 15 Feng Zhao and Leonidas J. Guibas. Wireless Sensor Networks: An Information Processing Approach. The Morgan Kaufmann Serie

37、s in Networking. Morgan Kaufmann Publishers, 2004. 16 M.; Wiebking, L.; Gulden, P.; Wieghardt, J.; Hoffmann, C.; Heide, P. Wireless local positioning, Vossiek, IEEE Microwave Magazine, pp. 77-86, Dec. 2003. 17 A. M. R. Ward Sensor-driven Computing, PhD thesis, Cambridge University, August 1998. 18 H

38、arter A, Hopper A, Steggles P, Ward A, Webster P. The anatomy of a context-aware application. In: Proc. of the 5th Annual ACM/IEEE Intl Conf. on Mobile Computing and Networking. Seattle: ACM Press, 1999. 59-68. 19 M. Addlesee, R. Durwen, S. Hodges, J. Newman, P. Steggles, A. Ward, and A. Hopper. Imp

39、lementing a sentient computing system. Computer, 34(8), 5056, 2001. 20 Andy Harter, Andy Hopper, Pete Steggles, Andy Ward and Paul Webster The anatomy of a Context-Aware Application, In Wireless Networks, Vol. 8, pp. 187-197, February 2002.,主要参考文献,21 L. Hu and D. Evans, Localization for mobile senso

40、r networks, in Proceedings of the 10th annual international conference on Mobile computing and networking, Philadelphia, PA, USA, 2004, pp. 45-57. 22 B. D. Anderson and J. B. Moore. Optimal Filtering. Prentice-Hall, Englewood Cliffs, New Jersey, 1979. 23 S. J. Julier and J. K. Uhlmann. Unscented fil

41、tering and nonlinear estimation. Proceedings of IEEE, 2004, 92(3):401-422. 24 H. Chen, D. Ping, Y. Xu, and X. Li, A Novel Localization Scheme Based on RSS Data for Wireless Sensor Networks, Advanced Web and Network Technologies, and Applications, LNCS Volume 3842, 2006. 25 H. Chen, P. Deng, Y. Xu, a

42、nd X. Li, A robust location algorithm with biased extended Kalman filtering of TDOA data for wireless sensor networks, In Proceedings of International Conference on Wireless Communications, Networking and Mobile Computing 2005, pp. 883-886. 26 P. Enge, and P. Misra, Special Issue on GPS: The Global

43、positioning System, Proc. of the IEEE, pp. 3-172, January 1999 27 P. Bahl and V.N. Padmanabhan. RADAR: an in-building RF-based user location and tracking system. In IEEE INFOCOM, 2, 775784, 2000. 28 Hightower J, Boriello G, Want R. SpotON: An indoor 3D location sensing technology based on RF signal strength. Technical Report UW CSE 2000-02-02, Seattle: Department of Computer Science and Engineering, University of Washington, 2000. 29 Jeffrey Hightower, SpotON: Ad-hoc Location Sensing using Radio Signal S