多类智能终端基于灰色关联度的WKNN定位效果分析

王 威，陈正宇，张 帅，胡纪元

（1.中国能源建设集团江苏省电力设计院有限公司，江苏 南京 211102；2.武汉大学 测绘学院，湖北 武汉 430079）

近年来，随着无线通信技术的发展以及用户对基于位置服务（LBS）需求的增长，出现了很多室内外定位技术。全球卫星导航系统（GNSS）已广泛应用于室外定位[1]，但在室内环境中，卫星信号很难到达室内定位终端，难以提供有效的室内定位精度，因此在过去的20多a里出现了很多室内定位系统（IPSs），以提高室内定位的可靠性和精度[2]。相较于其他无线室内定位技术，WiFi室内定位无需额外布设硬件，可利用建筑物中已有的WiFi网络基础设施，如以WiFi路由器为定位信号源；更重要的是，几乎每种现有的移动设备都支持WiFi接收功能，因此该技术得以广泛应用。

虽然WiFi信号接收设备接收信号的强度和信号发射器与接收器之间的距离有关，但在复杂的室内环境下很难用简单的公式描述，因此有研究者提出了以WiFi的RSS值为位置指纹的定位技术[3]。在室内定位环境不变的情况下，离线阶段和定位阶段采用相同的设备将得到较高的定位精度；但在定位阶段不同类型和品牌的设备测量的RSS值与所建立的指纹库不能有效匹配，将导致定位精度下降，因此找到一种稳健的指纹定位技术来提供精确、可靠的室内定位服务十分紧迫和必要。

Park J G[4]等发现不同设备的RSS值之间存在线性模型，可利用回归分析得到两种设备之间的线性校准模型，但需要大量的信号采集和模型训练；FANG S H[5]等比较了几种不同的免校准方法，但这些方法在相同设备下的定位效果通常不如传统算法好；Tsui A W[6]和HAN S[7]等分别利用皮尔森相关系数和余弦相似度衡量了指纹和测试阶段RSS值之间的相关程度，在一定程度上消除了设备接收信号的差异性。本文提出了以灰色关联度取代欧氏距离的改进WKNN算法，无需任何校准工作和复杂计算，且适用于不同的智能终端。实验结果表明，相较于传统WKNN算法，基于灰色关联度的改进WKNN算法降低了不同智能终端对WiFi定位精度的影响。

1 指纹定位算法

指纹定位算法是WiFi室内定位中经常使用的一种算法，包括离线训练和在线定位两个阶段。实现过程如图1所示。

图1 指纹定位算法流程图

1.1 离线训练阶段

在定位区域均匀布设参考点（RP，图2中绿色圆点），RP的密度应控制在一个合理的范围内，密度太小会影响定位精度，密度太大则会在建立指纹库时增加人工采集和计算的成本。移动终端在RP采集多个接入点（AP）的RSS值时，连同对应的MAC值和RP位置信息记录在指纹库中。AP的RSS值受环境和AP自身影响存在波动，因此在录入指纹库前需对RSS值进行预处理。

图2 指纹定位算法示意图

1.2 在线定位阶段

移动终端将利用某种匹配算法在测试点（TP，图2中红色菱形点）接收到的RSS值与指纹库数据进行匹配，从而得到当前位置。本文以近邻算法（NN）[8]为例：

假设利用终端设备在第i个RP处从m个AP采集到RSS的向量为Ri=(ri1,ri2,ri3,…,rim)，用户在某个TP处从m个AP在线采集到RSS的向量为S=(s1,s2,s3,…,sm)，其中ri和s为每个AP的RSS值。通过某些准则，将用户接收到的RSS向量与数据库中的指纹进行最佳匹配。通常采用欧氏距离作为衡量准则，其原理简单，只需少量计算。在WiFi定位系统中，欧氏距离是指RP与TP向量在信号空间上的距离。对于每个RP而言，欧氏距离可被定义为：

式中，i=1,2,…,n，n为RP的数量；Di为RP与TP向量之间的欧氏距离，Di越小，RP和TP之间的距离越短，通常与TP信号距离最短的那个RP点的坐标即为用户的位置。

K最近邻算法（KNN）与WKNN算法、NN算法类似，是以与TP欧氏距离最短的K个RP坐标的平均值为TP位置，表达式为：

式中，(xi,yi)为第K个RP的坐标。

WKNN算法考虑了K个RP坐标上对应的权值，需从TP与每个RP的欧氏距离中选取K个最近的欧氏距离的倒数作为每个RP的权值，表达式为：

式中，wi为第K个RP坐标中第i个坐标的权值。

NN算法、KNN算法和WKNN算法是WiFi指纹定位中的常用算法，即基于欧氏距离的定位算法；其他指纹定位方法包括极大似然估计（ML）、支持向量机（SVM）、线性判别分析、神经网络和典型相关分析（CCA）等[9-13]。

2 基于灰色关联度的改进WKNN定位算法

本文从灰色关联度的角度出发，提出了一种替代传统WKNN算法来衡量TP与指纹库中RP相似度的方法。在传统WKNN算法中，RSS值之间的欧氏距离越大，RSS的差异性就越大，但当遇到不同类型智能终端时，TP与RP的RSS值之间的小差异将造成欧氏距离的较大偏差，若忽略了RSS向量的内在特征和变化趋势，将导致定位精度的严重下降甚至定位失败[14]。欧氏距离仅在参考设备与用户设备相同时可达到满意的定位精度。本文利用灰色关联度替代了传统信号空间上的欧氏距离，灰色关联度可通过灰色关联分析（GRA）获得。GRA可分析不同终端RSS向量的关联程度。不同终端设备采集的RSS向量各对应元素的值之间可能有很大差异，但向量之间的变化趋势和形状具有很大的相似度，可利用灰色关联度代替欧氏距离匹配测试数据与指纹库的离线数据，从而得到TP坐标。灰色关联度的具体实现流程如图3所示[15]。

图3 基于灰色关联度的改进WKNN算法流程图

1）确定参考序列与比较序列。将在线阶段TP采集的m个AP信号强度RSS视为参考序列，即

将离线阶段n个RP采集的m个AP信号强度RSS视为比较序列，即

2）对参考序列与比较序列进行均值化处理。参考序列和所有TP序列构成比较矩阵，即

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

从R1′开始到Rn′每列都减去R0′对应元素，再求绝对值，得到式（8）的关联矩阵；然后求绝对值，得到关联矩阵。

3）求参考序列与比较序列之间的灰色关联系数。首先求解关联矩阵H中所有元素的最大值hmax和最小值hmin；然后利用关联系数公式对H中的每个元素作以下处理：

4）求取关联度。关联度的计算公式为：

指纹库中采集的第i个RP第j个AP的RSS值的方差为D(i,j)，方差越大，权值越小，则的计算公式为：

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

5）关联度排序。对指纹库中i个RP的γi大小进行排序，并将得到的排序结果代替欧氏距离，从而对传统WKNN算法进行改进。

3 实验结果与分析

在利用本文提出的基于灰色关联度的改进WKNN算法对多类智能终端进行定位前，需对不同终端接收到的RSS值进行分析与比较。不同的智能终端具有不同WiFi芯片型号、不同的WiFi信道、不同的天线位置以及不同的操作系统，这些都会影响RSS值的大小[16]。

三星S7、红米Note1、iPad2018、Acer E1四种终端的WiFi模块情况如表1所示，本文对利用这些设备在同一位置接收到的6个AP的RSS值进行对比，结果如图4所示，可以看出，不同终端设备在同一位置接收到的6个AP的RSS值有很大差别，如三星S7与红米Note1采集的平均RSS值差异可达11 dBm；但4种设备的RSS折线图保持着相同的趋势。通过这种趋势的关联度分析可得到测试设备与指纹库建立所用参考设备采集的RSS值的关联度比较。

表1 不同智能终端的WiFi模块情况

图4 4种设备的6个AP接收信号强度值

为了验证基于灰色关联度的改进WKNN算法的定位效果，在长10 m、宽6 m的房间进行了实验，如图5所示，在场地内布置6个WiFi路由器作为信号接入点，利用三星S7采集48个RP（绿色圆点），RP之间的横向距离为1.6 m、纵向距离为0.8 m，在每个RP手持设备面向同一个方向采集60 s作为指纹库数据；选取35个点作为TP（红色圆点），在每个TP利用不同设备采集15 s作为测试数据，采样频率均为1 Hz。为了保证只有终端设备这一个变化量，本文选择在机房环境稳定时进行数据采集，且采集人为同一个人。

将基于灰色关联度的改进WKNN算法与传统WKNN算法的定位结果进行对比，一般K=4时的定位精度较好[17]。红米Note1、iPad2018、Acer E1分别利用两种方法的累积误差分布如图6～8所示，可以看出，本文提出的算法在2 m定位精度内的概率分别提升了21%、18%和14%；且红米Note1和Acer E1的最大误差分别下降了约0.5 m和1 m。

图5 实验场景平面示意图

图6 红米Note1的累积误差概率

图7 iPad 2018的累积误差概率

图8 Acer E1的累积误差概率

为了充分验证定位结果的普适性，对3种终端的不同K取值进行分析，结果如图9所示，可以看出，不同K值下，基于灰色关联度的改进WKNN算法比传统算法的定位中误差小，定位精度更高，且在K值较小的情况下，定位精度改进效果更好。

图9 不同K值情况下两种方法的定位效果

4 结 语

随着智能手机和其他终端设备的广泛使用，不同设备的RSS值差异成为影响WiFi室内定位精度的一个重要因素。为了减少设备不同对定位精度的影响，本文分析了不同智能终端的RSS差异性和共同点，提出了基于灰色关联度的改进WKNN算法，并将改进后的定位算法与传统算法进行了对比。实验结果表明，利用不同设备进行WiFi定位时，相较于传统WKNN算法，基于灰色关联度的改进WKNN算法在定位精度上有很大提升，有效提高了不同终端的定位精度和普适性。