基于无线局域网接收信号强度分析的混合室内定位方法

夏 英，王 磊，刘兆宏

(重庆邮电大学计算机科学与技术学院，重庆 400065)

0 引言

随着移动通信、空间定位、信息服务等技术的快速发展，定位导航、兴趣点查询等位置服务(locationbased services，LBS)［1］得到了广泛应用，特别是基于GPS［2］的户外位置服务已经非常普遍。近年来，随着城市化进程的不断推进，写字楼、商厦、机场、地铁站等大型建筑物成为人们工作生活的重要场所，在这样的室内环境中，人们对于位置服务的需求日益强烈。

要提供高质量的室内位置服务，必须首先获得用户在室内的准确位置。由于非视距传播、多径传播、环境变化等因素的影响，传统的GPS等定位技术并不适用于室内环境。但逐渐密集的无线局域网(wireless local area network，WLAN)为实现室内定位提供了良好的环境。基于无线局域网的室内定位主要包括三角定位和指纹定位算法。三角定位算法［3］利用待测目标到3个已知无线接入点(access point，AP)位置之间的距离估算目标位置。这类算法简单，计算效率高，定位精度主要依赖于距离损耗模型。指纹定位算法［4］利用信号分布图表征室内无线AP的接收信号强度(received signal strength，RSS)与物理位置的直接或间接的映射关系，通过待测目标处采集到的无线AP信号与信号分布图进行匹配，从而估算目标位置。这类算法精度较高，大多可以达到3 m以内，但需要预先离线采集无线AP信号，建立信号分布图的周期长，成本高，而且数据库难以更新，不能很好地适应环境变化。

考虑到大型建筑物内结构复杂、人员密集且流动性大，加之用户终端种类繁多，信号接收情况不一，传统的三角定位和指纹定位算法各有优劣。为了提供一种适应性强的室内定位方法，在现有三角定位和指纹定位算法的基础上，通过分析用户终端实际接收到的无线AP个数和RSS进行混合定位。

1 相关技术基础

1.1 距离损耗模型

距离损耗模型用于计算参考点与无线AP的距离，选择合适的距离损耗模型可以有效地降低室内定位误差。常用的距离损耗传播模型［5］为

(1)式中:d0为近地参考距离，一般室内为1 m;d为无线AP与参考节点之间的距离;P0为距离为d0时无线AP的RSS;P(d)为距离为d时无线AP的RSS;n为路径损耗指数，表明路径损耗随距离增长的速率，依赖于周围环境和建筑物类型，在自由空间内，n为2，在复杂的环境中，n一般介于4和5之间。

常用的室内信号传播模型有对数距离路径损耗模型、衰减因子模型等。对数距离路径损耗模型引入环境因子反映遮挡物、人员走动等不确定因素带来的影响，但环境因子会因室内环境的变化而变化，计算比较困难;衰减因子模型考虑了墙、楼层等多种障碍物的影响，在解决障碍物较多的复杂室内环境的室内定位时，模型比较准确，但障碍物因素的计算本身就是个难题。

1.2 三角定位算法

依照距离损耗模型计算出用户终端与3个RSS的最大无线AP距离后，利用三角定位算法估算用户终端的位置。根据文献［3］提出的三角形质心定位算法，首先计算三圆交叠区域的3个特征点坐标，然后，以这3个点为三角形的顶点，三角形质心位置即为定位结果，该算法适用于结构简单的环境。文献［6］提出基于RSS校正的三角形质心算法，它利用AP之间的精确信息校正RSS值，极大减小了距离误差，与传统的算法相比，性能大大提高。文献［7］提出了一种加权质心定位算法，该算法在三角形质心定位算法的基础上，通过选择加权因子体现各个无线AP的影响力。

1.3 指纹定位算法

指纹定位算法大致分为离线采集和在线定位两个阶段。离线采集阶段的目标是构造室内无线AP信号分布图的RSS数据库。为了生成该数据库，需要在定位空间确定若干采集点作为参考点，记录下每个参考点测量的无线AP的RSS，最后将它们保存在数据库中。在线定位阶段，当用户终端移动到某一位置时，根据实时收到的无线AP信号，通过相应的匹配算法，将其与RSS数据库匹配，计算出该用户的位置。指纹定位算法根据在线定位阶段匹配算法的不同分为最近邻法(nearest neighborhood，NN)，K近邻法(K nearest neighborhood，KNN)，K 加权近邻法(K weighted nearest neighborhood，KWNN)，概率算法等［4］。NN定位算法计算用户终端测量的RSS与RSS数据库相应参考节点之间的距离，选取最小距离对应的位置坐标为用户终端位置;KNN定位算法是NN的改进型算法，其区别在于不是选取最小距离对应的那个坐标位置，而是从最小距离开始选取K(K≥2)个最接近的位置坐标，再计算它们的平均坐标作为用户终端位置;KWNN定位算法与K近邻法的不同之处在于选取了K个最接近的位置后，不是计算它们的平均坐标作为用户终端的位置，而是给每个位置坐标乘上加权系数，计算结果作为用户终端位置;概率定位算法根据测量的RSS出现的概率权重，估算出用户终端的位置。文献［4］采用平均距离差作为性能标尺，对上述指纹定位算法的精度性能作了比较分析，结果表明KNN定位算法最好。

2 室内混合定位方法

基于无线AP的RSS分析，结合三角定位和指纹定位算法的优势进行混合室内定位。该方法包括离线分析和在线定位两个阶段。离线分析阶段主要进行室内参考点选取、RSS阈值设定、RSS数据建库和无线AP位置估算。在线定位阶段，根据用户终端接收到的无线AP个数和RSS，选择三角定位算法或指纹定位算法进行位置计算。

2.1 参考点选取

参考点是指无线AP信号的测量和采集点。在离线分析阶段，首先将室内区域划分为若干网格，将各网格的中心视为参考点。由于网格的大小将直接影响定位的计算复杂度和精度，可依据室内障碍物、人员密集程度等情况进行网格划分，通常环境越复杂的区域网格越小。

2.2 RSS阈值设定

三角定位和指纹定位算法分别适用于不同的无线AP信号环境，RSS阈值用于两个算法的切换，提高室内混合定位的有效性。可依据室内信号传播模型和定位精度要求，利用(1)式计算室内RSS阈值RSSthres。如定位精度要求为10 m以内，则将d=10代入(1)式，计算出的P(d)即为RSSthres。

2.3 RSS数据建库

由于受散射、折射、障碍物等多种干扰因素的影响，无线AP信号采集时所得到的RSS数据具有不稳定性［8］。在每个参考点上进行多次信号采集，计算各无线AP的RSS平均值并存入RSS数据库。数据记录结构为(RefID，APMAC，AvgRSS，X，Y)，其中，RefID是参考点编号;APMAC是无线AP的介质访问控制(medium/media access control，MAC)地址;AvgRSS是无线AP的平均RSS值;X，Y分别是参考点的位置坐标。

2.4 无线AP位置估算

信号采集完成后，对每一个无线 AP选择AvgRSS最大的3个参考点，利用3个参考点的位置，采用三角形质心算法估算出各无线AP的位置并存储到RSS数据库中，其结构为(APMAC，X，Y)，其中，X，Y分别是某无线AP的位置坐标。

2.5 用户位置计算

当系统收到用户终端发出的定位请求时，即进行在线定位，其过程描述如下。

1)用户终端将接收到的多个无线AP信号发至定位模块;

2)定位模块将接收到的多个无线AP的MAC地址分别与RSS数据库对比，判断这些无线AP的位置是否已知;

3)若位置已知的无线AP至少有3个RSS值高于RSSthres，首先利用信号传播模型分别计算出RSS值最高的3个无线AP与用户终端的距离，然后，采用三角形质心算法［3］计算用户终端位置并返回;

4)若位置已知的无线AP不足3个或数量高于3个，但最多有2个RSS值高于RSSthres，则采用KNN定位算法［4］计算用户终端位置并返回。

3 实验结果与分析

为了检测混合定位方法的性能，设计并实现了一个室内定位原型系统。开发工具采用MyE-clipse8.5，服务器为 Tomcat6.0，数据库选用 Oracle10.0，操作系统为 Windows XP，系统内存为2 GByte，测试手机型号为MOTO Me525，MOTO A953和三星 I908E，根据定位精度要求，RSSthres设定为－70 dBm。

3.1 测试环境

在某商厦B1层进行实地测试。该区域面积约为7 000 m2，部署了大约80个无线AP，将现场划分成1.2 m×1.2 m的网格作为参考点。如图1所示，三角形标记的是已知无线AP的位置，正方形代表参考点，圆圈代表测试点。

图1 测试区域示意图Fig.1 Sketch map of test area

确定参考点后，利用测试手机分别采集各参考点的无线AP信息，其界面如图2所示。在每个参考点采集到的信息包括各无线AP的APID，APMAC，RSS值等。利用这些信息计算各无线AP的位置并建立RSS数据库。

3.2 定位精度测试

本文在三角形质心定位算法和KNN定位算法的基础上，根据无线局域网的接收信号强度分析进行混合室内定位。为了检验混合定位算法的精度指标，分别利用三角形质心定位算法、KNN定位算法与本文描述的混合定位算法进行定位精度测试，利用在测试点采集的无线AP信息计算测试点位置，并与测试点的实际位置进行对比，分析3种定位算法的误差情况。假设计算得到的测试点位置为(Xe，Ye)，而其真实位置为(Xt，Yt)，那么定位误差E为

图2 测试手机采集无线AP信号示意图Fig.2 Sketch map of testing mobile collecting AP signal

假设计算得到的n个测试点的误差分别为E1，E2，…，En。那么定位平均误差E为

试验1 参考点信号采集和定位测试在不同时间段完成。参考点信号采集在周末人员密集的时段，利用MOTO Me525，MOTO A953手机完成，共采集1 063个参考点信息并录入RSS数据库;在周二人员较少的时段利用三星I908E在30个测试点进行定位测试。表1比较了信号采集与定位测试发生在不同时段的3种定位算法的定位误差。

表1 定位误差比较(信号采集与定位测试发生在不同时段)Tab.1 Error comparison(signal collection and positioning test in different period)

如表1所示，混合定位算法的定位精度高于KNN定位算法和三角形质心定位算法，其主要原因是，三角形质心定位算法的定位精度取决于信号传播模型的精确性，本文采用简单传播模型，在估算无线AP位置和定位测试时忽略了障碍物的影响，定位误差较大;选择参考点和定位测试点时的时段、环境和设备有差异，一定程度上影响了无线AP信号的一致性，导致KNN定位算法误差较大。混合定位算法根据室内信号传播模型和定位精度要求确定合理的阈值，减少了差异因素的影响，提高了定位精度，更具有普适性。

试验2 参考点信号采集和定位测试在相同时间段完成。在周二人员较少的环境中，利用三星T959同时采集1 071个参考点，并进行30次定位测试。如表2所示，KNN定位算法和混合定位算法的定位精度远远高于三角形质心定位算法，其主要原因是，三角形质心定位算法在估算无线AP位置和定位测试时忽略了障碍物的影响;选择参考点和定位测试点的时段、环境和设备一致，保持了无线AP信号的一致性，指纹定位算法误差较小;而混合定位算法根据室内信号传播模型和定位精度要求确定合理的阈值，保持定位精度的稳定性。

表2 定位误差比较(信号采集与定位测试发生在相同时段)Tab.2 Error comparison(signal collection and positioning test in the same period)

对比表1、表2可知，参考点采集与定位测试发生在同一环境、相同时段时，三角形质心定位算法精度变化不大，混合定位算法的定位精度有所提高，KNN定位算法精度提高明显。由此可知，三角形质心定位算法和混合定位算法不受RSS数据库和定位环境的影响，精度相对稳定，能够较好地适应环境的变化。另外，混合定位算法的精度高于三角形质心定位算法的精度，且由于三角形质心定位算法需要确定至少3个无线AP的位置及精确的信道传播模型，因此，不管在具体实施还是定位精度上，混合定位算法具有较大的优越性。

4 结束语

本文在三角定位和指纹定位算法的基础上，根据接收信号强度进行混合室内定位。该方法离线进行参考点选取、RSS阈值设定、RSS数据建库和无线AP位置估算，根据用户终端实际接收到的无线AP个数和RSS，自动选择三角定位算法或指纹定位算法进行位置计算。实验表明，该方法具有受环境影响小、定位精度稳定等特点。下一步研究中还将分析无线AP位置移动和数量改变的情形，并考虑与室内的地理空间分析相结合从而进一步提高定位精度。

［1］CAO Hai-bing，XIA Ying，GE Jun-wei，et al.Analysis and compare of location technologies supporting LBS［J］.Journal of Chongqing University of Posts and Tele-communications，2004，16(5):42-45.

［2］李吉忠，武穆清，李筱叶.利用 Marquardt算法进行两颗卫星的AGPS定位［J］.北京邮电大学学报，2009，32(2):39-42.LI Ji-zhong，WU Mu-qing，LI Xiao-ye.Two Satellites Positioning Methods of AGPS with Marquardt Algorithm［J］.Journal of Beijing University of Posts and Telecommunication，2009，32(2):39-42.

［3］林玮，陈传峰.基于RSSI的无线传感器网络三角形质心定位算法［J］.现代电子技术，2009，32(2):180-182.LIN Wei，CHEN Chuan-feng.RSSI-based Triangle and Centroid Location in Wireless Sensor Network［J］.Modern Electronics Technique，2009，32(2):180-182.

［4］李昊.位置指纹定位技术［J］.山西电子技术，2007，34(5):84-87.LI Hao.Indoor Position Techniques Based on Location Fingerprint［J］.Shanxi Electronic Technology，2007，34(5):84-87.

［5］KONG Q R，YANG X Y，DAI X J.Research of An Improved Weighted Centroid Localization Algorithm and Anchor Distribution［C］//IEEE.Proceedings of International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery.Washington，DC，USA:IEEE Computer Society Press，2010:400-405.

［6］吕振，谭鹏立.一种基于RSSI校正的三角形质心定位算法［J］.传感器与微系统，2010，29(5):122-124.LV Zhen，TAN Peng-li.Triangle centroid location algorithm based on RSSI correction［J］.Transducer and Microsystem Technology，2010，29(5):122-124.

［7］张婵爱，马艳艳，白凤娥，等.基于RSSI的加权质心定位算法的实现［J］.太原理工大学学报，2009，40(2):146-147.ZHANG Chan-ai，MA Yan-yan，BAI Feng-e，et al.Implement of Weighted Centroid Localization Algorithm Based on RSSI［J］.Journal of Taiyuan University of Technology，2009，40(2):146-147.

［8］BOSE A，FOH C H.A Practical Path Loss Model for Indoor WiFi Positioning Enhancement［C］//IEEE.Proceedings of International Conference on Information，Communications and Signal Processing.Singapore:IEEE ICICS，2007:1-5.