一种基于灰色关联度的改进位置指纹定位方法

朱 律，沈云中

(同济大学 测绘与地理信息学院，上海 200092)



一种基于灰色关联度的改进位置指纹定位方法

朱 律，沈云中

(同济大学 测绘与地理信息学院，上海 200092)

针对传统位置指纹算法中没有充分挖掘和利用原始数据中的方差信息的问题，提出一种基于灰色关联度的改进加权K最近邻法(WKNN)的定位方法：将方差应用到关联度的计算中，通过对关联系数求加权平均值，一定程度上削弱了WiFi信号不稳定带来的影响。实验结果表明，该方法能有效提高定位精度。

WKNN；灰色关联度；位置指纹算法；精度分析

0 引言

在室外环境，卫星导航技术已经广泛应用于经济、军事、生产和生活的各个领域。随着移动通信与互联网技术的飞速发展，室内环境的定位需求也越来越多。由于室内环境复杂，存在较为严重的反射、衍射等非视距(non light of sight，NLOS)传播以及多径等情况，导致室内定位存在着诸多难题[1]。为了克服这些难题，基于红外线、超宽带等专用设备的定位方法采用特殊信号实现室内定位，虽然定位精度很高，但需要预先部署特定硬件设备甚至特定的定位终端，导致定位费用过高，普适度过低[2]。另一方面，随着“无线城市”的发展，国内各大城市的公共场所、商业圈覆盖了相当密集的无线保真(wireless fidelity，WiFi)节点，这让最早由美国微软研究院开发的基于无线局域网络(wireless local area networks，WLAN)的室内定位系统[3]有了更为广阔的发展和应用空间。基于WiFi的室内定位技术，只要求WiFi接入点(access point, AP)发射信号，利用移动用户接收和测量的信号就可实现室内定位；对硬件设备要求很低，能够显著降低建设与运营成本，成为室内定位的趋势[4]。目前，基于接收信号强度(received signal strength indication, RSSI)位置指纹的WiFi定位技术因其在成本、精度、系统复杂度以及环境适应性等方面的优势，成为室内定位系统主要采用的技术并被广泛应用[5]。根据保存在数据库中位置指纹记录的不同形式，可以将指纹定位分为概率分布法和确定性方法2大类。在确定性方法中，由于传统的最近邻法(nearest neighbor，NN)和K最近邻法(K-nearest neighbor，KNN)对移动终端位置估计效果不佳[6]，一些学者相继提出了一些改进：如基于群组的指纹定位算法[7]、基于RSSI相关系数的指纹定位算法[8]、基于聚类的位置指纹技术研究[9]等。这些方法在定位阶段中，只采用RSSI均值来计算信号的空间距离，并没有充分挖掘和利用原始数据中的方差信息。

本文将灰色关联分析法[10]引入到位置指纹定位中，把采集信号指纹与实测信号之间相似度的匹配问题转化为计算它们之间关联度的问题，提出改进的加权K最近邻法(weighted K-nearest neighbor, WKNN)算法。首先计算实测信号与每个采集信号的关联度，在关联度的计算过程中，考虑到采集点信号强度分布的方差信息，设计出每个AP的计算权值，并对每个AP的关联系数求加权平均值得到关联度，以削弱RSSI不稳定的接入点对关联度计算的影响。然后对每个采集信号做出综合比较和排序，在传统的WKNN定位方法基础上，以关联度大小的排序结果代替欧式距离大小的排序结果，改进传统的WKNN算法。

1 位置指纹定位

1.1 基本原理

位置指纹定位是指通过前期在参考点(reference place，RP)上采集数据，提取参考点信号特征来构建指纹数据库，并将待定点的AP信号特征与RP的AP信号特征进行对比，利用匹配算法得到待定点的定位结果。

1.2 算法

位置指纹定位算法是将一定采样时间内的RSSI均值保存到位置指纹记录中，然后度量RSSI测量值与指纹数据库之间的相似度，找出相似度最高的一个或者几个指纹位置作为定位目标的估计位置[12]。目前常用欧式距离来进行相似度计算，即

(1)

(2)

WKNN算法考虑到K个参考点位置坐标对最后定位的贡献不同，将权值分别分配给对应的坐标，即

(3)

式中wi表示参考点i的定位权值，它的取值取决于参考点与待测点的RSSI欧式距离，通常其计算公式为

(4)

式中ε为很小的正数，防止分母中出现0。

1.3 基于灰色关联度的改进WKNN算法

灰色关联分析是对一个系统发展态势的定性描述和比较，它通过参考序列和比较序列各点之间的距离分析来确定各序列之间的接近性和差异性。灰色关联分析的关键在于计算关联度。传统的邓氏关联度本身也存在很多问题，必然影响到权数的正确程度。本文将方差的倒数作为系数加入到关联度的计算中，采用灰色加权平均关联度来匹配离线阶段与在线阶段数据，从而获得待定点的最优位置。

将在线阶段测试点采集的各个AP信号强度RSSI视为参考序列

X0=[RSSI1RSSI2… RSSIm]T。

(5)

式中m为AP个数。离线阶段每个采集点采集的各个AP信号强度视为比较序列

(i=1,2,…,n)。

(6)

式中m、n分别为AP个数和参考点个数。参考序列和所有采集点的比较序列构成比较矩阵

S=[X0┇X1X2…Xn]。

(7)

首先对S中所有元素进行均值化处理，即每一个元素除以该元素所在列的均值。该处理方法能保留各变量取值差异程度的信息，得到新的均值矩阵

(8)

从第二列开始，每一列元素分别减去第一列对应元素，再求绝对值。得到关联矩阵

H=[H1H2…Hn]。

(9)

(10)

δ=[δ1δ2…δn]。

(11)

(12)

(13)

式中:ε为很小的正数，防止分母中出现0。通过对i个参考点的γi的大小进行排序，将得到的关联度的排序结果代替欧式距离大小的排序结果，改进了传统的WKNN算法。具体流程如图2所示。

计算关联度时，将方差的倒数作为系数加入到关联度的计算中，降低方差大的AP的接收信号强度在关联度计算时所占的权重，从而能一定程度上削弱RSSI波动带来的影响，提高最终的定位精度。

2 实验与结果分析

2.1WiFi信号传播特性及信号预处理

为了探究接收信号强度随时间变化的关系，利用安卓手机应用程序编程接口(applicationprogramminginterface，API)中提供的方法，在布设有WiFi节点的同济大学信息馆底楼，采用TP-LINK_0F784E路由器以及HTCD861t手机进行RSSI测试。测试时间在下午1：00左右，人员干扰较少。每更新800次RSSI数据自动将采集结果保存并导出。图3为距TP-LINK_0F784E路由器1.2m处(均值为-67.687 5dBm，标准差为2.251 4dBm)800个采样值的处理结果。实验结果表明，同一个路由器，在某个固定位置，长时间对接收信号强度进行采样，其数值在一定范围内波动，且符合类正态分布[14]。剔除大于3倍中误差的值(例如图3中的-53dBm)后，求取信号强度的平均值作为该点的WiFi信号特征。图4为经过数据预处理之后的RSSI采样值频率分布直方图。

2.2 实验平台

实验环境搭建在同济大学体育馆底楼，场地面积为14.4m×14.4m，右上角为楼梯，占用7.68m2。在楼梯区域外每隔1.6m采集RSSI信号特征。室内平面图如图5所示。

在图5所示位置部署7个AP。在箭头所示位置采集到的AP信息如表1所示，VAR表示采集到的方差信息。

表1 七个定位AP相关信息

2.3 结果分析

采集软件在安卓手机端实现，采样频率为1次/s，离线阶段每个采集点采集30 s，在线阶段每个测试点采样10 s。以平面图所示的方向建立坐标系，以第一个采集点的位置为原点，在待定位区域建立密度为1.6 m×1.6 m的网格采样密度分布。不同的K值定位的误差不同，K=3时KNN定位误差最小[8]，所以取K=3时利用基于灰色关联度的改进WKNN算法对待定点进行定位。测试点真实坐标和定位坐标如图6所示，共测试了88个点，每个点每个AP采集30个RSSI数据，预处理后求得的方差信息保存至位置指纹数据库中。由于图中右上角为楼梯区域，此区域内未进行数据采集与测试，与真实环境相同。

为了验证改进算法对定位效果有普遍性提高，对所有测试点的定位误差进行统计，累积分布如图7所示，定位误差累积分布曲线上的点表示定位误差小于横坐标值的概率.

从图7可以看出，改进WKNN算法的误差集中在0～5 m之间，几乎没有5 m以上的误差，而传统WKNN算法最大误差达到将近7 m。计算了88个测试点的定位精度，分别和传统WKNN方法、加权相关系数方法[7]定位效果做对比，如图8、图9所示。

从图7、图8和图9可以看出，基于灰色关联度的改进WKNN算法能有效提高定位精度。实验最终实现了88个测试点的定位误差均值为1.457 5 m，最大值为5.059 m，90 %的测试点定位误差在2.343 m以下的定位效果。X和Y坐标的中误差为:

(14)

从图10可以看出，当K≥2时，基于灰色关联度的WKNN方法的定位效果优于其余3种方法，传统WKNN方法只有在K=1的时候优于基于灰色关联度的WKNN方法，而K=1的时候WKNN算法已经退化为NN算法，并不能作为反例，所以基于灰色关联度的WKNN方法能有效提高定位精度。

4 结束语

本文将灰色关联分析法引入到位置指纹定位传统WKNN算法中，并对每个AP的关联系数求加权平均值得到关联度，削弱了RSSI不稳定的接入点对定位结果的影响。利用同济大学信息馆底楼实验场地实际测试数据，分析了WiFi信号传播特性，剔除了波动较大的RSSI值。在同济大学体育馆底楼利用88个点的实测WiFi定位数据进行了分析，结果表明基于灰色关联度的改进WKNN方法相比于传统WKNN方法、加权相关系数法以及加权欧式距离的改进WKNN方法，能更加有效地提高定位精度。

[1] 万群，郭贤生，陈章鑫，等.室内定位理论、方法与应用[M].北京：电子工业出版社，2012：2-3.

[2] 席瑞，李玉军，侯孟书，等.室内定位方法综述[J].计算机科学，2016，43(4)：1-5.

[3] BAHL P, BALACHANDRAN A, PADMANABHAN V N. Enhancements to the RADAR user location and tracking system[R].Seattle:Microsoft Research,2000.

[4] 王福伟，黄智刚.室内定位中移动目标轨迹跟踪研究[J].导航定位学报，2016，4(1)：33-36.

[5] 陈丽娜.基于WLAN的位置指纹室内定位技术[M].北京：科学出版社，2015：10-11.

[6] 邓中亮，余彦培，徐连明，等.室内外无线定位与导航[M].北京：北京邮电大学出版社，2013：77-78.

[7] 李树军，于建江.基于群组的Wi-Fi指纹室内定位研究[J].长春理工大学学报(自然科学版)，2013，36(6)：153-156.

[8] 李奇.一种基于RSSI相关系数的指纹定位技术方法[J].广东通信技术，2013 (3)：29-32.

[9] 杜书敏.基于位置指纹的室内定位技术研究与实现[D].昆明:云南大学，2013：19-25.

[10]邓聚龙.农业系统灰色理论与方法[M].济南：山东科学技术出版社，1988：42-47.

[11]杨萌，修春娣，邹坤，等.一种基于感知概率的室内定位匹配算法[J].导航定位学报，2014，2(4)：49-57.

[12]李燕君，徐凯锋，邵剑集.利用众包更新Wi-Fi室内定位指纹库的方法研究[J].传感技术学报，2014，27(12)：1692-1698.

[13]曹新建，董文洪，任建广，等.灰色综合关联分析法的空空导弹武器系统作战效能评估[J].海军航空工程学院学报，2008，23(2)：203-206.

[14]雷家毅. Android平台基于WiFi的定位算法与系统设计[D].上海:华东理工大学，2012：26-31.

[15]陈空，宋春雷，陈家斌，等.基于改进WKNN的位置指纹室内定位算法[J].导航定位与授时，2016，3(4):58-64.

An improved position fingerprinting algorithm based on grey relativity

ZHULv,SHENYunzhong

(College of Surveying and Geo-Informatics, Tongji University, Shanghai 200092, China)

Aiming at the problem that the variance information of the original data is not fully excavated and utilized in the traditional position fingerprinting algorithm, the paper proposed the positioning algorithm that is an improved WKNN method based on grey relativity: the variance information was taken into consideration in the calculation of relativity, and the impact of instable WiFi signal was eliminated to some degree through solving the weighted average values of the correlation coefficients.Experimental result showed that the proposed method could efficiently improve the accuracy of positioning.

WKNN; grey relativity; position fingerprinting algorithm; accuracy analysis

2016-10-21

作者简介：朱律(1991—)，男，硕士研究生，研究方向为测量数据处理、室内定位理论与方法。

朱律，沈云中.一种基于灰色关联度的改进位置指纹定位方法[J].导航定位学报,2017,5(2):44-48,71.(ZHULv,SHENYunzhong.Animprovedpositionfingerprintingalgorithmbasedongreyrelativity[J].JournalofNavigationandPositioning,2017,5(2):44-48,71.)DOI：10.16547/j.cnki.10-1096.20170208.

P

A

2095-4999(2017)02-0044-06