唐 瑞， 孙冰洁， 周礼争， 余 敏

(1.江西师范大学 软件学院，江西 南昌 330022； 2.江西师范大学 计算机信息工程学院，江西 南昌 330022)

基于RSSI的KNN—PIT室内自适应定位算法*

唐 瑞1， 孙冰洁1， 周礼争2， 余 敏2

(1.江西师范大学 软件学院，江西 南昌 330022； 2.江西师范大学 计算机信息工程学院，江西 南昌 330022)

针对基于接收信号强度指示(RSSI)的K最近邻(KNN)算法在室内定位精度较低的问题，提出一种改进的KNN—三角形内点(KNN—PIT)室内定位算法。根据室内空间结构特征，建立具有类标号的位置指纹库。引入虚拟参考点，利用PIT原理进一步约束目标点的定位区域，自适应地使用定位算法进行定位。综合运用高斯滤波、均值滤波技术，降低离线和在线阶段的信号随机误差。结果表明：改进后的KNN—PIT定位算法可以更好地估计用户的实际位置，降低定位误差，定位精度提高12.5 %。

室内定位； K最近邻； 三角形内点； 虚拟参考点； 自适应

0 引 言

随着通信技术的发展，全球定位系统(global positioning system，GPS)已成为室外导航定位中的主要技术。但是，在人类活动密集的地方，如,大型购物中心、办公楼、图书馆等复杂环境中，GPS因信号受干扰、遮挡等不能精确定位。基于接收信号强度指示(received signal strength indication，RSSI)的室内定位技术成为研究的热点[1,2]。目前研究的热点包括如何降低离线指纹库采集的工作量、减少在线匹配的复杂度、改进算法提高定位实时性与准确性[3,4]。

文献[5]指出K最近邻(K-nearest neighbor，KNN)算法中K参数的改变与定位精度不存在单一的正比例关系；文献[6]提出表征点位几何特性的点散发性强度概念，并利用该强度值动态地选择KNN参数K；文献[7]用主成分分析(principal component analysis，PCA)和最小二乘支持向量回归机(least square support vector regression，LSSVR)实现数据降维和位置回归预测；文献[8]结合煤矿井下环境提出一种自适应RSSI三角质心定位算法；文献[9]研究了RSSI值与几何距离的关系，提出了一种基于特征尺度的KNN。

由于RSSI受到多径效应、阴影效应等的影响，本文在离线阶段，对样本数据进行高斯滤波，获得表征较为真实的位置指纹数据，在线阶段使用均值滤波降低实时采样RSSI带来的较大误差。利用最佳三角形内点 (point in triangulation，PIT) 测试法和虚拟点进一步约束定位点的所属区域，提出KNN—PIT算法，自适应地使用定位算法进行定位。

1 具有类标号的位置指纹库构建

基于RSSI位置指纹的室内定位方法分为离线信号采集构建指纹库阶段和在线实时定位两个阶段。离线阶段，在待定位区域建立平面坐标系并划分网格，以网格点作为参考点(reference point，RP)。在各RP上采集周边各接入点(access point，AP)的RSSI，建立各个参考点对应的位置和信号强度的关系，即位置指纹库。

具有类标号的位置指纹库在传统指纹库中添加新的属性，即类标签。根据室内的空间结构特征，将各区域的RP归为一类，位置指纹库如表1所示。

表1 具有类标号的指纹库

位置指纹集为S={(L1,R1,C1),(L2,R2,C2),…,(Ln,Rn,Cn),Rn={RSSIn1,RSSIn2,…,RSSInm}∈Rm,Cn∈{1,2,…,j)，其中,Ln=(xn,yn)表示参考点n的二维位置坐标,RSSInm表示参考点n处接收第m个AP的信号强度值,Cn表示参考点n的类标号，取值为1～j。

2 KNN与PIT原理

KNN定位算法首先计算定位点处测得的RSSI向量与各RP点测得的RSSI向量的余弦相似度。两向量的余弦相似度如下所示

(1)

然后在位置指纹库中寻找最接近的k个RSSI向量。由于指纹库中每个RSSI向量唯一对应一个参考点的二维坐标。最终定位点的位置估计为k个参考点二维坐标的加权值，第i个参考点的权值为wi

(2)

其中，si为第i个参考点与定位点的空间相似度。最终定位点的位置估计为

(3)

PIT原理如图1所示。当存在一个方向，节点T沿着这个方向移动会同时远离或接近三角形顶点A,B和C，判定该节点不在三角形内;否则,判定该节点在三角形内。

图1 PIT原理

目前数学理论上还有面积法、内角和法、同向法等判定一点T是否在三角形ABC中。本文采用面积法定性的判断定位点是否在三角形内，使用空间向量之间的距离代替指纹点之间的距离。

设三角形顶点坐标A,B和C处的位置指纹为： (LA,RA,CA),(LB,RB,CB)和(LC,RC,CC)。定位点处的RSSI向量为RT,则

(4)

由秦九韶—海伦公式得三角形ABC的面积SABC为

(5)

同理，可计算SABT,SBCT和SACT，若SABC=SABT+SBCT+SACT，判定定位点在三角形ABC内;否则，判定定位点在三角形外。实际实验时，由于存在信号的随机误差，假定满足SABC-(SABT+SBCT+SACT)<δ，δ为设定的阈值，即认为点在三角形内。

3 自适应的KNN—PIT定位算法

根据无线信号传播理论，当两点比较近时，中间点处的RSSI可由两点RSSI的均值近似代替，因此,可以添加虚拟参考点进一步约束定位点的所在区域，实现更精确的定位。但是，若参考点不在同一类时，表明中间有墙体阻隔，引入虚拟点可能带来更大的定位误差。同时，若k个参考点在同一直线上则无法构成三角形，因此，需要分类讨论。

3.1KNN算法匹配前3个点属同一类

如图2所示，KNN匹配前3个参考点K1,K2,K3同类但不构成三角形，引入K4，且K4与原参考点属于同一类。增加虚拟参考点P，P点处的RSSI由K1和K4的RSSI均值代替。通过面积法计算得定位点在三角形K1K2P内，则定位点T的位置估计为

(6)

图2 K1,K2,K3不构成三角形

如图3所示，K1,K2和K3属于同一类且构成三角形，通过面积法计算得定位点在三角形K1K2P内，则定位点T的位置估计由式(6)得出。

图3 在未调整的三角形内

如图4所示，K1,K2和K3属于同一类且构成三角形，但定位点不在虚拟点P组成的三角形K1K2P和K2K3P内。引入K4参考点，通过面积法计算得定位点在三角形K1K4P内，则定位点T的位置估计为

(7)

图4 在调整后的三角形内

如图5所示，K1,K2和K3属于同一类且构成三角形，但定位点不在三角形K1K2P和K2K3P内，引入K4与原参考点不属同一类，则定位点T的位置估计为

(8)

图5 K1,K2,K3,K4不同类

3.2 KNN算法匹配前3个点不属同一类

如图6所示，K1,K2和K3不属于同一类,则定位点T的位置估计由式(8)得出。

图6 K1,K2,K3不同类

综上，自适应的KNN—PIT定位模型如图7所示。

图7 KNN—PIT定位模型

4 实验与分析

为了检测本文提出的KNN—PIT算法在室内的定位效果，实验在先骕楼7楼进行。实验环境的平面图如图8所示，参考点间距为2m，AP型号为TL—WR885N，移动采集终端为华为手机G606。

图8 空间结构和AP的布局

为了降低RSSI不稳定的影响，各参考点采集各AP的RSSI值300次。通过大量实测数据分析，在某一点处测得某一AP的RSSI值整体呈正态分布，如图9所示。

图9 某点处采集某AP的RSSI值

本文离线阶段采用高斯滤波技术，舍弃发生概率较低的数值，对高概率发生数值求均值，降低信号噪声影响。在线阶段使用均值滤波技术，将实时采集的若干次RSSI求均值作为实时RSSI，降低信号的随机误差。

考虑离线阶段样本采样次数影响离线阶段的工作量，也可能直接影响室内定位的精度。随机以RSSI值采样次数为30,60,90,120,150,180,210,240,270和300次进行对比实验。实验结果如图10所示。

图10 KNN和KNN—PIT算法对比

图10表明:当位置指纹点采集的RSSI次数相同时，KNN—PIT算法在室内定位中具有更高的精度，定位精度平均提高12.5 %。

为了验证在实时定位时均值滤波的效果和必要性，进行单次RSSI和3次RSSI作均值滤波处理对比实验,每次定位误差的实验结果如图11所示。

由图11知，使用单次测得的RSSI进行定位，定位误差波动性较大，而使用均值滤波技术后，定位误差基本稳定在1.40m左右，标准差小，具有更好的适应性。

图11 定位阶段是否使用均值滤波技术的定位误差

5 结 论

本文采用KNN—PIT算法进行室内定位，不仅有效降低了传统KNN算法在室内定位的较大误差，而且可以在不同环境下自适应地定位。实验表明:改进后的算法具有更高的定位精度和可靠性。

[1]GuYanying,LoANiemegeersI.Asurveyofindoorpositioningsystemsforwirelesspersonalnetworks[J].CommunicationsSurveys&Tutorials,IEEE,2009,11(1):13-32.

[2]PrietoJ,MazuelasS,BahilloA,etal.Adaptivedatafusionforwirelesslocalizationinharshenvironments[J].IEEETransactionsonSignalProcessing,2012,60(4):1585-1596.

[3]JiangJoeAir,ZhengXiangyao,ChenYuan,etal.AdistributedRSS-basedlocalizationusingadynamiccircleexpandingmechanism[J].IEEESensorsJournal,2013,13(10):3754-3766.

[4] 花 超,吉小军,蔡 萍,等.基于RSSI差分修正的加权质心定位算法[J].传感器与微系统,2012,31(5):139-141.

[5]HonkavirtaV,PeralaT,Ali-LoyttyS,etal.AcomparativesurveyofWLANlocationfingerprintingmethods[C]∥WPNC2009,Hannover,Germany,2009:243- 251.

[6] 刘春燕,王 坚.基于几何聚类指纹库的约束KNN室内定位模型[J].武汉大学学报·信息科学版，2014,39(11):1287-1292.

[7] 张 勇,黄 杰,徐科宇.基于PCA-LSSVR算法的WLAN室内定位方法[J].仪器仪表学报,2015,36(2):408-414.

[8] 曹开来,余 敏.无线传感器网络煤矿井下RSSI自适应定位算法[J].传感器与微系统,2014,33(6):129-132.

[9]LiDong,ZhangBaoxian,YaoZheng,etal.Afeaturescalingbasedk-Nearestneighboralgorithmforindoorpositioningsyste-m[C]∥GlobalCommunicationsConference,Austin,TX,2014:436-441.

Indoor adaptive KNN-PIT positioning algorithm based on RSSI*

TANG Rui1, SUN Bing-jie1, ZHOU Li-zheng2, YU Min2

(1.School of Software,Jiangxi Normal University,Nanchang 330022,China; 2.School of Computer Information and Engineering,Jiangxi Normal University,Nanchang 330022,China )

Aiming at problem of KNN algorithm low precision of indoor positioning based on RSSI,an improved KNN—PIT indoor positioning algorithm is put forward.According to structure feature of indoor space,establish location fingerprint database which has class labels.Introduce virtual reference points,use theory of PIT to further constrain localization area of target point,use positioning algorithm adaptively to carry out positioning. Comprehensively use Gauss filtering and mean filtering to reduce random errors of signal in online and offline stages.Results show that the improved KNN—PIT algorithm can better estimate the user’s actual location,and decrease significantly localization errors,positioning precision is improved by 12.5 %.

indoor positioning; K-nearest neighbor(KNN); point in triangulation(PIT); visual reference points; adaptive

10.13873/J.1000—9787(2015)07—0128—04

2015—05—11

国家自然科学基金资助项目(41374039)； 中国—波兰国际科技合作项目(35—14)

TP 393

A

1000—9787(2015)07—0128—04

唐 瑞(1991-)，男，安徽合肥人，硕士研究生，主要研究方向为无线传感器网络、室内定位。