基于Wi-Fi指纹的改进型室内定位算法研究

秦国威， 孙新柱， 陈孟元

(安徽工程大学 安徽省电气传动与控制重点实验室， 安徽 芜湖 241000)

近几年，伴随着无线通讯技术、物联网技术和高级移动终端的飞速发展，人们愈发迫切地希望得到与所在位置相关的服务。基于位置服务的室内定位系统能够准确获得用户的位置信息，具备很好的发展和应用前景。当前，全球定位系统[1](Global Position System，GPS)是主流的定位和导航技术，在人们的生活和工作中运用非常广泛，其技术是通过卫星获取地理位置信息，但是在室内环境下，由于卫星信号易受障碍物、多径效应等因素的干扰，使得定位目标和卫星之间无法进行视距内的通信，因此，GPS用于室内定位存在一定的局限性。

随着Wi-Fi技术的成熟与普及，基于Wi-Fi的室内定位技术逐渐成为当前定位领域的研究热点[2-4]。相比于其他定位技术(如蓝牙[5]、Zigbee[6]定位)，Wi-Fi定位技术具有如下的优势：(1)无遮挡，覆盖面广，Wi-Fi信号覆盖半径可以达到约100 m，受非视距影响小；(2)传输速率快，能够在短时间内快速传输信息；(3)不存在激光、视觉等常见的特征提取和数据关联困难的问题等等。目前，常用的室内定位方法可分为传播模型法[7-8]和信号分布模型匹配法[9]。传播模型法是指利用无线信号，得到手持设备和信号发射端(Access Points，AP)之间的距离信息，从而推算出目前此接收设备所处的位置。传播模型法中常用的包括信号到达时间法[10](Time of Arrival，TOA)、信号到达时间差法[11](Time Difference of Arrival，TDOA)、信号到达角法[12](Angel of Arrival，AOA)。其中，使用TOA技术定位比较稳定，但需要AP端和信号接收端的时钟同步，对所有需要定位的接收设备皆进行时钟校准显然是不现实的。而TDOA方法虽不需要进行AP和接收设备时钟的同步校准，但是将接收设备与AP之间的时间同步问题转化为了AP与AP之间的时间同步问题，然而Wi-Fi的传输速率相当快，瞬间的误差将会导致测距上极大的偏差，为了提高测算位置的精度，此方法必需要对AP端进行硬件改造，以获得精准的测量时间。另外，信号到达角法是通过接收设备接收到两个信号发射端信号的角度来估计自身位置，这种方法一般需要一种特殊的天线来得到精确的角度信息，这无疑会增加接收器的成本及功耗，难以实现。因此，传播模型法在实际应用中存在较大的距离或角度误差，难以完成室内较大范围内的精确定位。信号分布模型匹配法通常分为两个阶段进行：离线采集阶段和在线定位阶段。在离线阶段利用信号特征建立信号指纹数据库，将实时采集的信号特征信息与指纹数据库中的特征信息进行匹配，利用相应的匹配算法，最终得出最优的位置估计。此方法相对传播模型法定位具有明显的优势。

为此，本文选择基于概率模型的信号分布模型匹配法进行室内定位。但是由于室内环境的复杂性，数据库指纹的非连续性，导致匹配精度还有很大的提升空间。同时目前利用的传统的KNN、加权KNN[13]等算法，效率比较低，定位时间相对较长。本文基于此运用一种丰富位置指纹特征的方法以提高定位精度。此方法将手持设备的方向角和信号发射点的数目，加入指纹库，丰富数据库的位置特征。同时在线匹配过程中采用K-means[14-15]聚类加权KNN算法以提高匹配的效率。

1 位置指纹定位方法

在Wi-Fi等无线通讯技术定位领域，通常用到的测量参数有信号强度(RSSI)与信噪比(SNR)。RSSI指信号接收端接收到的Wi-Fi信号强度，在通信上用来判定链接质量；SNR是指放大器的输出信号电压与同时输出的噪声电压之比，很显然，SNR越小表明信号中包含的噪声越大。由于室内环境的障碍物及多径效应等影响，室内环境中RSSI值相比于SNR更为稳定。因此，本文采用的Wi-Fi定位方法为位置指纹定位方法，此方法在常规的基于RSSI的位置指纹定位的基础上，加入手持接收方向x和信号发射点数目R以扩展位置指纹离线数据库，进而提高匹配的精度。其中，人体手持设备的朝向角θ可以通过手机自带的电子罗盘测得。

1.1 离线采集阶段

离线采集阶段的主要任务是构建一个位置指纹数据库。首先绘制定位区域地图，在定位区域合理规划好一系列的测试参考点。之后依次测量各参考点来自各接入点AP的RSSI值(多次测量取平均值)，手持设备朝向角θ以及接入点AP的数量R，按一定的格式记录在数据库中，该数据库就是离线位置数据库。建立方法如下，在室内定位环境下，按照一定的原则选取参考点，且在各个参考点上对每个接入点AP不间断采样一段时间，并保持手持设备的角度不变，得到每个AP的均值mLi存入数据库中，构成位置指纹图IM：

IM={Z,A,M,Maci,θ}，

(1)

1.2 在线定位阶段

在线定位阶段是利用手持设备测得在某一位置处的Wi-Fi信号强度RSSI值，通过相应的匹配算法，将实测的数据信息与离线数据库中的指纹信息进行类比，将会在离线数据库中获得一组相似的Wi-Fi指纹信息。 手持设备朝向角由手机电子罗盘自动测得，从而完成定位。目前常用的在线匹配算法主要有K近邻算法(KNN)和K加权近邻算法(WKNN)等。

1.2.1 K近邻算法

K近邻算法的主要思想是将实测的Wi-Fi强度信息与离线指纹数据库中指纹信息进行匹配，通过一一计算实时测量的RSSI样本数据与离线指纹数据库中所有的RSSI值之间的欧几里得距离，进而找出与实时定位点相似度最高的K个指纹点，最终将这K个点的质心作为定位估计结果。K近邻算法定位流程如图1所示。

图1 K近邻算法定位流程图

(1)取第i个实时采样点与指纹点之间的欧几里德距离为di，计算式如下

(2)

(2)将实时采样点与所有参考点的RSSI值的欧氏距离进行排序，逐一比较，可以得出欧氏距离最小的K个参考点，然后计算出它们的质心为

(3)

1.2.2 K加权近邻算法

根据上述的K近邻算法可以清晰找出RSSI值欧氏距离最小的K个指纹参考点，再对此K个指纹参考点的位置坐标按照相似度属性赋予不同的权重系数ωi，表达式为

(4)

最终将这个指纹参考点的位置坐标加权求和，得出定位结果：

(5)

其中(x，y)是待定点的坐标，(xi，yi)是指纹点的坐标。

2 基于聚类的K加权近邻Wi-Fi定位算法

2.1 K-means聚类算法

K-means聚类算法首先要从数据集中随机选定K个聚类中心，形成随机的K个簇;其次按照最近邻的原则分配样本，将各个数据对象分配到相应的簇中；接着，将每个簇中的所有数据对象的质心作为新的聚类中心，进而计算准则目标函数的值；重复迭代该步骤，直到聚类中心点恒定为止。在迭代过程中，一次次中心点的更新会使得准则目标函数的值逐渐减小，最终收敛至一个固定的值。

K-means算法与其他聚类算法相比具备的优势在于，它不可能出现多重聚类中心的情况，因此在很大程度上可以规避聚类中心模糊问题。

K-means算法的准则目标函数为

(6)

其中K表示簇的个数，Ci表示第i个簇，ci表示簇Ci的聚类中心，θk表示簇内标准差，x表示任意的数据对象。

综上，K-means聚类算法的目标即是使得准则目标函数值J(C)最小。K-means的K值会影响最小J值。K-means算法的核心在于如何确定聚类数，保证目标函数最小。K-means算法的流程如图2所示。

图2 K-means算法流程图

2.2 基于K-means的K加权近邻Wi-Fi定位算法

在Wi-Fi室内定位中，基于聚类和KNN结合的Wi-Fi定位算法CKNN同样分为离线(训练)和在线(推理)定位两个阶段完成。首先在离线阶段，将所有的参考样本进行聚类，进而确定每个类别的中心以及每个数据对象所对应的簇。其次在推理定位阶段，先是查找出目标样本与聚类中最相似的簇，然后通过类比，再找到最相似簇中K个最相似的邻参考样本，接着对这K个参考样本所对应的位置加权取平均，最终可得到需预测的目标样本所对应的位置。

(7)

按照此步骤依次计算，计算r向量与其他簇聚类中心RSSI的cosine相似度，可以得到w个cosine相似度(T1，T2，…，Tw)，其中T值最大的即为Dw与r是最相似的。由上式可确定最相似类别Dw与r向量最相似的k个样本rk1，rk2，…，rkk，其对应的位置坐标为(xk1，yk1)，(xk2，yk2)，…，(xkk，ykk)。进一步对相似度进行归一化处理，将其影响权重定义为{wk1，wk2，…，wkk}，计算如下：

(8)

将求得的样本坐标按上述的权重加权，最终确定的目标位置的坐标如下：

(9)

3 仿真实验及分析

本实验是在安徽工程大学行政楼A座的三楼档案室完成的，实验中采用的移动站接收设备是一款华为荣耀8手机，共布置有4个AP，使用的都是普通型号的路由器DIR-629。下载一种基于Android平台的Wi-Fi信号网络RSSI测量软件。实验过程中，每个时段均采用1 s的采样率采集数据3 min，分别采集34个指纹点和20个待定位点。其具体的分布如图3所示。

图3 指纹采集区域图

3.1 AP个数与匹配精度的相关性

利用上述方法完成离线采集的数据以后，图4给出了不同接入点AP个数对K加权近邻法(WKNN)与基于K-means加权的K近邻法(CKNN)定位的精度影响。

图4 不同AP个数精度对比图

由图4可以清晰看出，当信号发射端AP数目为1～4个时，定位的精度都在不断提高，与此同时，两种算法定位的精度差别并不大。当AP个数为2～3个时，定位精度迅速提高，此后，当AP个数为3～4个时，虽然精度还在不断提高，但是变化已经很缓慢，基本上趋于相同，最终的定位精度在1.5 m以下。由此可知，信号发射端AP个数对Wi-Fi定位的精度有很重要的作用，不可忽视。综合考虑，本文以下所做的对比实验采用的AP个数为4个。

3.2 定位误差比较

为了验证本文提出的将手持设备方向角加入离线数据库中能够提高定位的精度，本文选择若干个测试点测试该方法的性能。定位性能通常由均方根误差和定位误差累积概率作为参考标准。

3.2.1 均方根误差

在目前实际的定位系统中，不管采用何种定位方法，最终的估计位置和理想位置总会存在一定程度的偏差，这即为定位系统的位置误差。

假设待定位点的实际位置为(xa，ya)，估计位置为(xe，ye)，定位系统的均方根误差为

(10)

3.2.2 定位误差累积概率

定位误差的累积概率表示位置误差小于或等于某个值的概率，可表示为

P=P(e≤ea)。

(11)

位置误差累积概率分布曲线从左至右趋势是上升的，而且是收敛的，曲线收敛的速率表征定位误差的大小，速率越快表明定位误差越小，反之，误差越大。

离线阶段分别采用常规指纹库和扩展指纹库，在线阶段采用加权KNN算法的定位性能测试如图5所示。

图5 定位误差对比图

图6 定位精度对比图

图7 定位时间对比图

3.3 算法性能对比

在相同型号和配置的计算机上运行K加权近邻算法和基于聚类的K加权近邻算法，从以下3个指标对两种算法进行对比并作评价。3个指标分别为最大误差、误差平均值、定位误差的方差，对比的结果如表1所示，定位的精度对比如图6所示。

表1 算法性能对比

由表1看出，同一种算法在不同指纹库的最大误差和误差的平均值还是有差距的，然而不同的算法在同一个指纹库的最大误差和误差平均值相差无几，进而得出两种算法在同一种离线指纹库下进行在线计算的精度差距很小，同种算法在扩展指纹库比在常规指纹库下定位的精度得到了很大提升。同时在图6中可以清晰地看出扩展指纹库定位的精度明显高于离线指纹库，所以离线扩展指纹库更有利于提高Wi-Fi定位的精度。

3.4 实时性对比

由3.3节可知，K加权近邻算法(WKNN)和基于聚类的K加权近邻算法(CKNN)在同种离线数据库的状态下，精度相差无几，因此，实时性成为评价两种算法优劣的决定性因素。二者定位时间如图7所示。

不难看出，基于聚类的K加权近邻算法(CKNN)几乎要比K加权近邻算法(WKNN)定位要快一倍。因此，基于聚类的K加权近邻算法更具有实时性。

4 结 论

Wi-Fi室内定位是目前的研究热点之一，本文将信号发射端AP的数目和手持设备的方向角加入到Wi-Fi位置指纹数据库中，实验表明，加入手持设备的方向角和接入点的数量改进后的指纹数据库与常规数据库相比，精度有了明显的提升。在线定位阶段采用将K-means聚类算法与加权K近邻算法相结合的算法，与加权的K近邻算法相比，Wi-Fi指纹定位的精度有了明显改善，定位时间明显缩短，定位速率明显加快。因此，离线阶段建立扩展指纹库，在线阶段运用基于聚类的K加权近邻算法不仅使得Wi-Fi定位精度得到很好的改善，实用性也得到了明显的改进。虽然，本文Wi-Fi定位性能得到了明显的改善，但是算法性能还有待提高，相似度公式较繁杂等，这将是接下来要集中精力研究的方面。

[ 参 考 文 献 ]

[1] AFRAIMOVICH E L.GPS global detection of the ionospheric response to solar flares.Radio Science，2016，35(6)：1417-1424.

[2]ZHOU Zi-mu，WU Chen-shu，YANG Zheng，et al.Sensorless Sensing with Wi-Fi.Tsinghua Science and Technology，2015，20(1)：1-6.

[3]ZHU Nan，ZHAO Hong-bo，FENG Wen-quan，et al.A novel particle filter approach for indoor positioning by fusing Wi-Fi and inertial sensors.Chinese Journal of Aeronautics，2015，28(6)：1725-1734.

[4]陈斌涛，刘任任，陈益强，等.动态环境中的Wi-Fi指纹自适应室内定位方法.传感技术学报，2015，28(5)：729-738

[5]HALLBERG J，NILSSON M.Positioning with Bluetooth，IrDA and RFID.Luleå：Luleå University of Technology，2016.

[6]ROY U K.Modified source-routing for large-scale pseudo-linear ZigBee networks//IEEE International Conference on Research in Computational Intelligence and Communication Networks.Kolkata：IEEE，2016：85-89.

[7]刘光.基于无线传感器的移动机器人定位研究.天津：南开大学，2010.

[8]YUAN J，HUANG Y，TAO F S T.Active exploration using a scheme for autonomous allocation of landmarks.Robotica，2014，32(5)：757-782.

[9]路飞，田国会，刘国良，等.智能空间下基于Wi-Fi指纹定位与粒子滤波的服务机器人复合全局定位系统设计.机器人，2016，38(2)：178-184.

[10] PAK J M，AHN C K，PENG S，et al.Distributed Hybrid Particle/FIR Filtering for Mitigating NLOS Effects in TOA Based Localization Using Wireless Sensor Networks.IEEE Transactions on Industrial Electronics，2016(99)：1.

[11] XIONG H，CHEN Z，AN W，et al.Robust TDOA localization algorithm for asynchronous wireless sensor networks.International Journal of Distributed Sensor Networks，2015，2015：10.

[12] WANG Y，HO K C.An Asymptotically Efficient Estimator in Closed-Form for 3-D AOA Localization Using a Sensor Network.IEEE Transactions on Wireless Communications，2015，14(12)：6524-6535.

[13] MAILLO J，RAMIREZ S，TRIGUERO I，et al.kNN-IS：An Iterative Spark-based design of the k-Nearest Neighbors Classifier for Big Data.Knowledge-Based Systems，2017，117：3-15.

[14] 吴夙慧，成颖，郑彦宁，等.K-means算法研究综述.现代图书情报技术，2011(5)：28-35.

[15] 白雪峰，蒋国栋.基于改进K-means聚类算法的负荷建模及应用.电力自动化设备，2010，30(7)：80-83.