高室内精度定位终端的研制文献综述

文献综述（或调研报告）：

摘要：对现有室内定位算法进行综述研究。首先，从定位算法数学基础出发，阐述三边定位与最大似然估计定位算法，介绍基于无线电信号强度(RSS)定位算法与基于时间差(TDOA)定位算法。其次，从国内外两方面分析室内定位算法研究现状，国外关注室内定位算法与室内定位系统的研究；国内室内定位算法研究较多，但室内定位系统研究较少。再次，对算法与系统对比分析，讨论算法优缺点，分析显示室内定位算法的研究注重定位精度与能耗之间的平衡。最后，指出移动定位与逻辑定位将会是室内定位算法未来的研究方向。

关键词：室内定位；算法综述；逻辑定位；移动定位

1. 引言

室内目标定位存在重要的潜在应用，近年来引来了大量的研究及关注[1, 2, 3]。无线电技术和无线局域网技术的进步，以及定位服务需求的增加，推动了定位技术的发展。在开阔的室外环境中，全球定位系统GPS 提供了非常精确的定位信息，然而由于室内环境的特殊性，当前一些用于室外定位算法和系统很难移植到室内定位的应用中。

随着信息与通信技术的普及，人们对于室内定位信息的需求与日俱增，一些公共场所，像商场、机场、展厅、写字楼、仓库、地下停车场、监狱、军事训练基地等都需要使用准确的定位信息。假如在商场购物过程中，孩子走丢了，如何让父母用最短时间追踪到孩子的位置；在地下停车过程中，如何让司机在没有到达停车场的时候就知道停车位置情况。这些问题都需要室内定位技术来解决。

精确的室内定位信息，能够对可用空间和库存物质实现高效管理；能够导航警察、消防人员、士兵、医务工作人员完成特定的室内任务；智能空间、普适计算等都离不开位置服务，因此室内定位具有广阔的应用前景，是当前研究的热点。

虽然目前已经有了这些研究成果，但是室内定位还有很多地方值得研究。第一，算法与定位节点运动适应能力[8]，即这些节点具有很高的移动性，这项任务很重要，因为节点在移动时平均测量可以影响所有节点的定位精度，并且误差可能会扩大至整个传感覆盖的网络。第二，目前所有定位算法都被设计在二维空间中操作，然而现实世界的应用涉及三维空间，因此，需要研究在三维空间[9]中传感节点的定位算法。第三，定位的实时性，即使在节点数量增加的情况下，实时精确定位传感节点位置算法的能力也不会降低。

本文从定位算法的数学基础开始，分析了基于测量的定位算法，详细介绍了RSS (无线电信号强度)与TDOA (到达时间差)定位算法。然后从国外和国内两个方面总结了近些年室内定位算法的研究情况，国内外关于室内定位算法和室内定位系统的研究比较热，其中运用混合算法来提高定位精度和运用智能手机[10]进行定位研究的研究比较多。对文中讨论的室内定位算法与室内定位系统进行比较，得出目前研究都是在定位精度与能耗之间寻找平衡。最后对室内定位算法的未来研究方向做了分析，得出逻辑定位与移动定位是未来值得研究的方向。

1. 定位算法数学基础

目前室内定位算法一般是基于距离测量的定位算法，所谓距离测量定位算法就是指测得目标节点与其锚节点的距离，然后通过计算得出目标节点的坐标。在平面定位算法中，最少需要已知三个锚节点的位置，通过锚节点与目标节点之间的距离来计算得出目标节点的坐标。

测得距离之后主要利用三边测量法(trilateration)与极大似然估计法（maximum likelihood estimation）进行目标节点的定位。

2.1 三边测量算法

三边测量法（trilateration）原理如图1 所示，已知A、B、C 三个锚节点的位置坐标分别为

，以及它们到目标节点D 的距离分别为，假设目标节点D的坐标为(x, y)。

那么，存在下列公式（1）：

由上式可以得到节点D的坐标为：

如果锚节点位置信息准确、测得的距离准确，那么就可以根据此公式准确得出目标节点的位置。这个结果是理论上最好的结果，但是在实际测量中会存在误差，造成结果的不准确。

目前利用三边测量法的定位算法较多，像经典的基于TDOA 的定位算法，基于RSSI 的定位算法都是测得距离后利用三边测量进行定位的。

• 1. 极大似然估计法

极大似然估计法（ maximum likelihoodestimation）需要已知较多锚节点信息，要求锚节点数量要大于三个，利用这些信息建立方程组，这个方程组能够唯一确定目标节点的位置。原理如图2所示，已知1,2,3,,n等 n 个锚节点的坐标分别为

，它们到目标节点D的举例为假设节点D的坐标为（x,y）。

那么，存在下列公式（2）：

从第一个方程开始分别减去最后一个方程，得：

上式线性方程表示方式为：AX=b，其中：

使用标准的最小均方差估计方法可得到节点D的坐标为：。可以看出，最大似然估计法是利用目标节点周围很多锚节点的信息来进行定位估计的。

根据定位过程中是否测量实际节点间的距离，把定位算法分为基于距离的定位算法和距离无关的定位算法[11]。基于距离定位的唯一问题就是如何在物理层次上测量距离。现在使用最多的两种距离测量分别是基于无线电信号强度(RSS)和基于到达时间差(TDOA)的方法。

1. 国外室内定位

目前国内外关于室内定位算法的研究都比较多，其中国外偏重于室内定位系统的研究，而国内关于室内定位算法的研究比较多。

3.1 国外室内定位算法

国外关于室内定位算法的研究成果比较多，而且大多根据提出的算法实现了定位系统，这些室内定位算法可以分为以下两类，第一类是运用混合算法进行定位的定位方法，这类算法都是利用至少两种算法的结合进行定位，提高定位精度；第二类是具有创新性的算法，这类算法都具有指导意义，是提出的新算法。

1. 混合定位算法

Zhoubing Xiong 等人提出了混合RFID与WSN技术的定位方法[12]，文中提出扩展的卡尔曼滤波与粒子滤波两个方法提高定位精度。Chen Feng 等人将室内定位与压缩感知相结合[13]，利用压缩感知理论进行定位，提高了定位精度，RSS 稀疏信号利用压缩感知理论进行重构。把定位分为粗定位与精定位两个阶段，粗定位利用Affinity Propagation 方法，精定位利用了压缩感知理论。实验结果显示此定位方法比传统的指纹定位方法提高了定位精度，降低了计算复杂度。Chunwang Gao 等人根据加权回归与插值模型、最大似然估计方法相结合的方法，提出了一个室内定位的统计方法[14]提高定位精度，实验结果显示这种定位方法的定位精度在2 米之内。K.Chintalapudi 等人根据RSS 模型设计了室内定位算法[1]，这种算法无需前期部署就能够定位。无需前期部署指无需知道室内的实体布局，包括接入口(AP)的布局。移动设备记录视线所及的相应AP 接收信号强度(RSS)测量值，并发送给定位服务器。同时还需发送室内边缘的位置值。文中重点是EZ 定位算法。所有报告的测量值都受到无线传播物理现象的约束，EZ 模拟这些约束并用遗传算法对其进行计算，实验结果良好，且误差可控制。

1. 创新定位算法

Stephen P. Tarzia 等人运用室内场景指纹技术[3]进行定位，这种指纹被称作Acoustic BackgroundSpectrum(ABS)，这种指纹具有紧密、易计算、对于短暂特殊的声音具有很好的鲁棒性等优势，和其他基于指纹定位技术一样，这种技术需要测量目标周围的指纹，并且与数据库中的指纹相匹配，寻找最相近的一个指纹进行定位。通过实验，并且WI-FI定位进行比较。得出与WI-FI 定位相结合定位精度要比只用WI-FI 的精度提高很多。Tin-Yu Wu 等人分析出定位算法分为基于距离测量与不需要距离测量的两类，指出室内定位过程中有很多信号干扰以及误差，于是提出了基于遗传算法(GA)的定位算法[15]，此算法优势在于不要太多节点信息。Hyuk Lim等人提出的室内定位算法[16]不需要其他配置信息，需要在线输入一些测量信息，在IEEE 802.11 的基础上，把系统进行实验，结果显示此系统具有更好的鲁棒性，并且提高了定位精度。David Madigan等人建立了贝叶斯等级模型进行室内定位的方法[17]，证明了贝叶斯等级模型定位方法所达到的精度和其他定位模型和算法相似。

可以看出，目前研究者们把主要精力放在了复杂室内环境下定位误差和精度[18]的研究上，如何能够提高定位精度而又能够减少能耗和代价，两者之间存在一个平衡问题。

• 1. 国外室内定位系统

国外关于室内定位系统的研究比较成熟，其中有以下几个室内定位系统比较具有代表性：

1. 信号技术定位

信号技术定位是根据无线电信号、红外线信号、射频识别信号、超带宽信号等技术测得节点之间的距离，其中测距方式有很多，比如利用TDOA、RSS等方法都可以得到节点之间的距离，根据节点之间距离，就可以利用三边定位方法对目标节点进行定位。

利用这种方法的定位系统有如下几种：①

Olivetti 研究实验室研制的Active Badage[19]室内定位感知系统，是最早的室内定位跟踪系统之一。它采用了红外线技术实现室内定位，属于无线小区监视接入的相邻法定位系统。每个待定位物体使用红外线发射机定期发送自身唯一的ID 识别码；②麻省理工学院开发的Cricket[5]室内超声波无线射频定位系统，属于基于时间法测距的三边定位系统。Cricket 的定位依据是空气中声波的传播速度远低于无线电波的传播速度，可利用无线射频信号为控制参考信号，计算声波信号的传播时间。剑桥大学开发的Active Bat[20]室内定位系统是基于室内超声波无线射频的定位系统；③SpotON[21]系统是基于射频识别的室内定位系统。该系统基于信号强度分析，发展了一种聚合算法对三维空间进行定位。SpotON系统中硬件标签呈网络状分布，无需中央控制单元，通过标签测试到的信号强弱表征标签之间的几何距离。

1. 指纹匹配定位技术

指纹匹配算法定位技术原理是这样的，首先必须采集大量数据，提取出待测目标节点所处区域的一些特征，这些特征必须保证待定位区域是相互区别的，即在测到这些特征的时候能够确定目标定位节点所处的位置；其次，在定位过程中，根据目标节点所处周围境进行位置匹配，就可以对目标进行定位。

利用这种方式进行定位的定位系统有如下几种：①微软公司研究团队开发的室内跟踪定位的RADAR[22]原型系统，该系统结合经验数据和衰减因子模型，在大量数据采集的基础上通过一定的匹配法则确定目标位置，提供定位服务和应用。后来华盛顿大学的Jiun-Hung Chen 对RADAR 系统的定位算法进行了更深入的研究，他提出了在无线网络环境使用鲁棒性的模块匹配和支持向量匹配对使用者进行定位；②EKahau 公司推出的EKahau 实时定位跟踪软件引擎，也是利用指纹法实现的定位系统。该系统在多种行业得到了广泛应用，其中应用最广的是医疗保健行业，如国外一些医院的室内环境安装了EKahau 定位系统，它的定位精度达到了1 米。

1. 结束语

根据目前研究，室外定位技术已经相当成熟，而室内移动定位和逻辑定位将会是一个很好的研究方向。汪苑等[29]认为，从总体上来说，射频识别技术用在室内定位系统中较为适合，实现起来比较方便，定位精度让人满意，且造价较低，在研究典型系统LANDMARK 系统的基础上，今后可针对其缺陷进行改进，利用2.45GHz 搭建无线网络实现定位，尽量提高定位效率和精度。

由于无线传感网络成本低廉和容易部署，WSN已成为室内定位应用最为广泛的技术，然而由于RF信号在室内传播受到障碍物的阻碍，为了提高定位效果和提升定位精度，Zhoubing Xiong 等提出基于WSN 和RFID 混合室内定位方法[12]。混合式系统应该会成为定位系统的一个发展方向，可以通过多种定位技术结合来优化定位系统的各项指标。

未来的研究热点有：提高移动定位系统的定位精度和准确度，移动定位信息的获取和处理，移动定位应用的研究。考虑因素有[30]：(a) Beacon Nodes（锚节点配置对于定位具有很大影响）。(b) NodeDensity（许多定位算法对于节点密度很敏感，当设计或是分析一个算法时，考虑节点密度需求是很重要的。）(c) Accuracy（位置精度展示计算位置与节点物理位置的切合度。）(d) Cost（一个定位系统的开销主要包括硬件开销和能量开销。）

然而，室内定位也具有相当多的挑战：

1. 室内环境复杂，空间范围狭小，对定位精度要求较高。

2. 无线信号容易受室内摆设、人员频繁移动影响，造成传输过程中的大量衰减和严重反射现象，所以对定位技术以及算法要求苛刻。

3. 室内定位设备要尽量简单、功耗低、成本低廉并且对室内其他设备不造成干扰。

4. 定位系统要更好融入实际场景，不给用户造成过多负担和分散用户过多的注意力。

5. 应尽量减少基础设施数量。

6. 多用户位置检测响应时间问题。

参考文献

[1] K. CHINTALAPUDI, A. P. IYER, V. N. PADMANABHAN.Indoor Localization Without the Pain[C]// Proceedings ofMobiCom. Chicago, Illinois, USA. 2010: 173—184

[2] ELADIO MARTIN, ORIOL VINYALS, GERALDFRIEDLAND, RUZENA BAJCSY. Precise IndoorLocalization Using Smart Phones[C]// Proceedings of ACMMultimedia. Firenze, Italy. 2010: 787—790

[3] STEPHEN P. TARZIA, PETER A. DINDA, ROBERT P.DICK, GOKHAN MEMIK. Indoor Localization WithoutInfrastructure Using the Acoustic BackgroundSpectrum[C]// Proceedings of MobiSys. Bethesda,Maryland, USA. 2011: 155—168

[4] HARTER A, HOPPER A. A Distributed Location Systemfor the Active Office[J]. IEEE Network, 1994, 8(1): 62—70

[5] AKSHAY ATHALYE, VLADIMIR SAVI, MIODRAGBOLI, PETAR M. DJURI. A Radio FrequencyIdentification System for Accurate Indoor Localization[C]//Proceedings of ICASSP. 2011: 1777—1780

[6] A. R. KULAIB, R. M. SHUBAIR, M. A. AL-QUTAYRI,JASON W. P. NG. An Overview of Localization Techniquesfor Wireless Sensor Networks[C]// Proceedings of theInternational Conference on Innovations in InformationTechnology. 2011: 167—172

[7] AMIN Y. TEYMORIAN, Wei CHENG, Liran MA, XiuzhenCHENG, Xicheng LU, Zexin LU. 3D Underwater SensorNetwork Localization[J]. IEEE TRANSACTIONS ONMOBILE COMPUTING. DECEMBER 2009. VOL. 8, NO.12: 1610—1621

[8] IONUT CONSTANDACHE, Xuan BAO, MARTINAZIZYAN. Did You See Bob? Human Localization UsingMobile Phones[C]// Proceedings of MobiCom, Chicago,Illinois, USA. 2010: 149—160

[9] HE T, HUANG C, BLUM B M, STANKOVIC J A,ABDELZAHER T. Range-free Localization Schemes forLarge Scale Sensor Networks[C]// Proceedings ofMobiCom, San Diego, CA. 2003: 81—95

[10] Zhoubing XIONG, FRANCESCO SOTTILE, MAURIZIOA. SPIRITO, ROBERTO GARELLO. Hybrid IndoorPositioning Approaches Based on WSN and RFID[C]//Proceedings of IEEE New Technologies, Mobility andSecurity (NTMS). Paris, France. 2011:1—5

[11] Chen FENG, WAIN SY ANTHEA AU, SHAHROKHVALAEE, Zhenhui TAN. Compressive Sensing BasedPositioning Using RSS of WLAN Access Points[C]//Proceedings of IEEE INFOCOM.San Diego, CA, USA.2010: 1—9

[12] CHUNWANG GAO, ZHEN YU, YAWENWEI, STEVE RUSSELL, YONG GUAN. A Statistical Indoor Localization Method for Supporting Location-basedAccess Control[J]. Mobile Networks and Applications.2009 14:253–263

[13] Tin-Yu WU, I-Ju LIAO, Wei-Tsong LEE, GUAN-HSIUNG,Jen-Wen DING, Chung-Chi WU. Enhancing IndoorLocalization Accuracy of Sensor-based by AdvanceGenetic Algorithms[C]// Proceedings of the 6thInternational Wireless Communications and MobileComputing Conference. ACM. Caen, France. 2010:1218—1222

[14] HYUK LIM, LU-CHUAN KUNG, JENNIFER C. HOU,Haiyun LUO. Zero-configuration Indoor Localization overIEEE 802.11 Wireless Infrastructure[J]. Wireless Networks2010 16:405–420