自适应动态K的WKNN室内定位方法

胡久松，刘宏立，徐 琨

(湖南大学 电气与信息工程学院，长沙 410082)

0 引 言

随着移动设备和移动通信技术的广泛使用和移动互联网的广泛发展，人们对室内定位服务(indoor positioning service，IPS)的需求不断增加。由于WiFi网络的普及，WiFi接入点可以在室内环境中随处可见，并且几乎所有移动设备都具有内置的WiFi接收模块。因此，WiFi室内定位已成为开发室内定位的最有吸引力的研究课题。WiFi室内定位已被广泛研究，并且提出了许多解决方案[1-4]，其中，接收信号强度(received signal strength, RSS)作为位置的度量测定方法(位置指纹算法)被大多数室内定位系统所采用，因为它不需要WiFi接入点的位置。加权K-最近邻(weighted K-nearest neighbor, WKNN)算法，通过获取K个参考点位置(reference points, RPs)的加权平均进行位置估计，是目前使用最广泛的位置指纹算法之一[5-26]。由于很难获取一个最优的K值，大多数文献采用的WKNN算法会选择一个固定的K值或者考虑K为多个值的情况：文献[6]选用了固定值K=4；文献[7,23]选用了固定值K=3；文献[27]选用了固定值K=4；文献[8]对比了K=1,3,5,…,23的情况；文献[14]提出了一种加强的WKNN算法，对比了K=2,…,5的情况；RADAR[22]讨论了不同K值下WKNN算法对定位精度的影响，在其试验中随着K值的增大，定位精度变高，但达到某个值时，定位会呈下降趋势等。

需要繁琐的不同K值的结果对比才能获得一个较好的定位结果是选用固定K值的弊端。这是由于室内环境的不同，参考点选取的位置不同，测试点所在的位置不同等原因，K取值过大，则有可能会将一些较远的无益邻居也包含进来，而K取值较小，则有可能会将一些较近的有益邻居排除在外。因此，在线阶段，需要动态选择适当的K值，以提高定位精度。文献[13]提出了一种动态K的方案——EWKNN (enhanced weighted k-nearest neighbor)，通过相似度度量的均值作为阈值来动态判定K的取值。文献[5]在文献[13]的基础上将阈值乘以参数c(c∈[0.1,2])。尽管这些动态K的方案在一定条件下使得WKNN算法的定位精度有了一定的提升，但存在着以下问题。

1)引入新的不确定性参数。文献[13]中，通过RT进行初步的参考点筛选结果对K的获取影响较大，从而影响最终的定位精度；文献[5]引入了参数c，某种程度上降低了文献[13]中RT的影响，但等价于同时引入了RT和c这2个不确定性参数。

2)忽略K=1的情况。当最优K较小时，通过相似度度量的均值作为阈值来动态判定K的取值的方法会很难获取到一个较小的K值，特别是最优K值为1的情况(事实上，文献[5，13]令K≥2,直接忽略了K=1的情况)，会导致定位精度下降。例如,当测试点位置在临近参考位置，甚至就在参考位置时，K=1的定位精度显然是最好的。

针对以上问题提出了一种自适应动态K的WKNN室内定位方法——SAWKNN(self adaptive weighted K-nearest neighbor)。该算法在不引入新的不确定参数的前提下，采用“多雷达搜索策略”的方式自适应选择近邻数K值进行位置估计。实验结果表明，提出的算法可根据在线情况自适应调整K值，获得了较好的定位精度。

1 系统模型

1.1 基于指纹的室内定位系统框架

基于指纹的室内定位系统框架，包含离线和在线2个阶段，如图1所示。离线阶段负责建立指纹数据库。首先在规划好的等距点使用移动设备收集WiFi信号；然后将搜集的WiFi信号求取平均值、标准差、处理丢失值等后形成指纹存储在数据库中；在线过程负责处理用户的定位查询服务。当系统收到用户的定位查询时，系统对搜集的指纹与数据库中的指纹进行相似度度量计算。通过动态K算法选择确定K的值，然后从中选出最可能的K个参考点，最后通过这K个的参考点位置加权和得到最终的位置估计。

图1 基于指纹的室内定位系统框架Fig.1 Block diagram of indoor location system

1.2 离线过程

(1)

∀i={1,2,…,L},∀j={1,2,…,N}

(2)

RSSo中的每个列向量代表每个参考点RPj在设备面向方向o时的指纹数据为

(3)

(3)式中，[]T表示向量的转置。

1.3 在线定位过程

定位引擎在收到定位查询后，首先根据AP选择算法筛选出较强信号的AP，然后计算接收到的指纹与数据库中参考位置的相似度度量。根据相似度度量，定位引擎确定K的值，最后从中选出K个最相似的指纹对应的参考位置进行加权求和得到位置估计。

1.3.1 相似度度量计算

定义在线过程在第r个测试点任意方向位置LOC(xr,yr)接收到的测量向量为

rssr=[rss1,r,rss2,r,…,rssL,r]T

(4)

试验过程中，整个楼层内共检测到L=339个AP信号,每个参考点分别被9～40个不同的AP信号所覆盖。对于某一位置而言，并不是所有检测到的AP信号对于定位都是有益的，事实上大多数都是无益的，这种现象在商场、寝室等覆盖大量AP信号的公共区域特别常见，因此，需要对AP进行选择。这里通过大多数文献常用的最强信号强度法[28]对AP进行选择。

定义一个1×L的行向量为

pm=[0,…,1,…,0],∀m∈{1,2,…,M}

(5)

(5)式中：行向量中只有一位为1，其他位均为0，为1的位即代表该位对应的AP被选中。将(4)式中信号强度值按序排列，选取信号强度最强的前M个，其中每个选择均可用一个(5)式中的行向量表示。所有的行向量组成M×L的AP选择矩阵P。因此，第r个测试点与第j个参考点间的相似度度量计算公式为

∀j∈{1,2,…,N},o∈O

(6)

(6)式中，sim(r,j)o表示第r个测试点与朝向o的第j个参考点间的相似度度量。‖‖2表示求取欧式距离。(6)式中除以M表示取欧式距离的均值作为对比对象。

1.3.2K的自适应取值

由物理距离构建的地图称之为物理地图，而经过计算相似度度量之后，由相似度度量构建的地图本文称之为SIM地图。K的自适应取值是通过“多雷达搜索策略”的方式在SIM地图上获取的。在搜索策略中，需要首先获取雷达的发射距离单元，并假设雷达是可以以成倍的发射距离单元发射信号搜索目标的。这个发射距离单元，称之为相似度邻域半径，每个参考点上的相似度邻域半径表示为simRj。雷达的搜索目标为测试点。在计算相似度度量之后，每个参考点以b·simRj为发射距离发射信号搜寻目标。显然只有相似度度量在发射距离范围内的目标才会被雷达发现。b是从值1开始的自然数，当所有的雷达搜索不到信号时，将会扩大发射距离，即b值增大。而同时搜索到目标的雷达个数即为K值

K=count(sim(r,j)o<=b·simRj)，

∀j∈{1,2,…,N}

(7)

(8)

求解为simRj=1，反应了在SIM地图上参考点之间“相互独立”的相似度邻域半径平均范围，即当测试点落在某一参考点此相似度邻域半径范围内时，测试点发生在该参考点的可能性远大于其他参考点。显然，这种获取K值的方式没有引入新的不确定性参数，仅只依赖于离线和在线数据。值得注意的是，simRj的值会根据参考点的布置不同而不同，但在同一场景下会发生微弱变化，可以视为是不变的。

相对于固定K值的WKNN算法，SAWKNN算法在在线定位阶段只是增加了b×N次的判断来自适应选取K值。这种判断的耗时几乎可以忽略不计，因此，SAWKNN算法与固定K值的WKNN算法的耗时是差不多的。

1.3.3 位置估计

最后的位置估计采用K个最有可能的位置加权求和得到

(9)

(9)式中：ωl=1/sim(r,l)o；LOC(xj,yj)是第l个可能指纹的位置。

2 试验结果和分析

2.1 试验环境搭建

指纹采集是湖南大学电气院13舍实验楼第7层进行的，覆盖面积50 m×18 m，总共测试了22间约8 m×4 m的房间和一个50 m×1.8 m的走廊如图2所示。图3为房间的大小信息和参考点(RPs)的位置信息(三角状所示)的示意图。RPs之间的间隔大部分为3块瓷砖间距(0.9 m)，部分因为房间布局、障碍物等原因，分布和间距都进行了调整。总共设置了538个RPs和在RPs之间随机选择了924个测试点(test points，TPs)，其中，每个房间布置了16～23个RPs和26～48个TPs，走廊布置了112个RPs和172个TPs。

图2 定位区域平面图Fig.2 Plan of interest area

图3 大小和位置示意图Fig.3 Size and location of interest area

指纹采集使用的是安卓手机华为荣耀4c，配置如图4所示。所有AP热点都来自于已有安装。

图4 华为荣耀4c配置图Fig.4 Configuration of Huawei glory 4c

每个RPs分别对东南西北4个方向搜集了40组数据，取平均值以及对应坐标存入数据库中，共形成了2 152条参考指纹数据和924条测试数据。另在测试数据中混入随机抽取的少量(16条)来自于参考位置的原始数据。

2.2 试验结果评估方法

(10)

误差在1 m以内的百分比即为R个TPs中ME≤1所占的比例。

2.3 手机朝向的影响

文献[22,29]都讨论了手机朝向的影响，其主要原因在于人体对信号的遮挡造成的信号衰减。采用WKNN算法，令K=4，M取参考点中AP覆盖数的最小值9，对(E,W,S,N)4个方向上以及合并的库Total进行定位的结果，如图5所示。由于测试点的方向随意，在各个方向的表现略有差异，其中，Total的在平均定位误差上表现最佳，但应考虑的是，若选择Total为参考库，则算法的运算时间是选择单方向的将近4倍。之后的试验选择单方向S和Total为代表作为参考库进行。

图5 不同方向的参考库定位的结果Fig.5 Position results using different orientation database

2.4 M的取值

每个参考点分别被9～40个不同的AP信号所覆盖，因此，M的取值为9～40。采用WKNN算法，令K=4，M=9,10,…,40，对S和Total参考库进行定位的结果，如图6所示。在S上，M=25平均定位误差最小，而在Total上M=16为最小。由于M的取值为多少合适，没有较好的判断准则，因此，为了减少计算量，之后的试验均采用M=9进行试验(M的取值并不影响算法之间的优劣比较结果)。

2.5 相关算法的局限性

2.5.1 固定K值

采用WKNN算法，令K=1,2,…,80，M=9，对S和Total参考库进行定位的结果，如图7所示。试验结果与RADAR[22]结果一致：随着K值的增大，定位精度变高，但达到某个值时，定位误差转而上升，其中，Total由于考虑了多个方向，下降趋势要慢一些。这是由于K的取值过大，有可能则会将一些较远的无益邻居也包含进来，而K的取值较小，则有可能会将一些较近的有益邻居排除在外。因此，在线阶段，需要动态选择适当的K值，以提高定位精度。图7中曲线最低端对应的K值通常称之为最优固定K值。

图6 不同的M值的定位结果Fig.6 Position results using different value of M

图7 不同的K值的定位结果Fig.7 Position results using different value of K

2.5.2 参数RT的取值

文献[13]提出的动态K方案——EWKNN是通过公式(6)计算相似度度量之后，通过阈值RT进行初步筛选后，即将相似度度量大于RT的参考点去除后，将剩余相似度度量的均值作为阈值，计算小于该阈值的参考点个数即为K值。该方法受参数RT的影响较大。试验中，相似度度量为(0,15)。采用EWKNN算法，令M=9，RT={1，2,…,15}(根据文献[13]描述，K最小值应取2，因此，当小于RT的个数小于2时，令K=2)，对S和Total参考库进行定位的结果，如图8所示。显然，不同RT值会导致不同的计算结果。RT=3的平均定位误差是最小的，因此，之后的试验采用RT=3。

图8 不同的RT值的定位结果Fig.8 Position results using different value of RT

2.5.3 参数c的取值

文献[5,13]的基础上将阈值乘以了参数c(c∈[0.1,2])，旨在通过调整阈值的程度使得定位精度有一定的提升。采用EWKNN算法，令M=9，RT=3，c={0.2,0.3,…,2}，对S和Total参考库进行定位的结果，如图9所示。由试验结果可知，只有在c=1附近的值对定位精度有少量提升，其他范围的值反而会降低定位精度。事实上要获取参数c的值使得定位结果有提升有很大的不确定性。

图9 不同的c值的定位结果Fig.9 Position results using different value of c

2.6 SAWKNN算法

动态K方案应在不引入新的不确定参数的前提下，解决K的选择问题，显然文献[5,13]的方案引入了新的不确定性参数。因此，不能满足要求。SAWKNN的定位结果，如图10所示。并与不同固定K值的情况进行了比较。由图10可知，SAWKNN的定位结果接近于最优固定K值的结果。表1列举了常用的WKNN-K=1，WKNN-K=2，WKNN-K=3，WKNN-K=4以及EWKNN-Rt=3,c=1和SAWKNN算法的定位结果详细数据(横向一组2个数据分别表示在S和Total上的定位结果)。由表1可知，SAWKNN在平均误差和1 m内误差上都获得了较好的定位结果。尽管EWKNN也同样也能获得较好的定位结果，但是需要较好的选择RT和c的值，事实上RT和c具有不确定性。

图10 SAWKNN的定位结果Fig.10 Position results of SAWKNN

算法平均误差/m误差在1 m内的百分比/%STotalSTotalWKNN-K=11.82.03229WKNN-K=21.61.84034WKNN-K=31.61.84036WKNN-K=41.51.84136EWKNN-RT=3,c=11.51.84135SAWKNN1.51.73937

图11 定位查询来自于参考点的定位结果Fig.11 Position results of location query from RPs

显然只有考虑了K=1的情况，才能获得精准的参考点定位结果(误差为0)。这种对刚好来自于参考点本身的情况进行精准定位非常有利于动态追踪算法的误差校正、数据库的指纹更新等应用。WKNN的K的自适应调整图如图12所示。

图12 K值自适应变化Fig.12 Adaptive change of K value

可见，K值会根据在线情况自适应调整K值，且包含了K=1的情况。

3 结 论

使用WiFi无线技术获取室内定位信息作为位置服务的上下文，这对室内定位应用的发展具有重要意义。针对WKNN算法需要动态变化K值的问题上，在不引入不确定性参数的前提下，提出了自适应动态K的SAWKNN定位方法。提出的算法仅依赖于离线和在线数据。在真实环境中采样了大量数据进行了试验。在平均定位误差、误差1 m内的比例的评估标准上进行了试验分析。试验结果表明，提出的算法相比其他算法，具有以下优点。

1)在不引入新的不确定性参数的前提下，根据离线和在线情况自适应调整K值；

2)定位精度上接近最优固定K值的定位结果；

3)考虑了K=1的情况。

基于以上的优点，提出的算法将能更好地应用于实际中。