一种基于差分梯度匹配算法的Wi-Fi定位方法

张乾初，刘正熙

（四川大学计算机学院，成都　610065）

一种基于差分梯度匹配算法的Wi-Fi定位方法

张乾初，刘正熙

（四川大学计算机学院，成都610065）

Wi-Fi指纹定位；差分梯度匹配；卡尔曼滤波

0　引言

随着Wi-Fi技术的不断发展，无线城市的推动，越来越多的地方覆盖了Wi-Fi信号。同时位置信息对各种现实需求有着重要的作用，如车辆定位、宠物定位、井下人员定位、室内商场定位、建筑工地管理等。GPS广泛用于各种位置定位，同时在许多领域得到了推广应用。然而，其信号却极易受障碍物的干扰和阻断，在密集的城市地带、隧道、室内等环境定位不可靠甚至于失效。因此，基于Wi-Fi的定位技术越来越受到人们的关注。Wi-Fi定位技术随着Wi-Fi信号的普遍覆盖，越来越多的商城会采用这个方式进行定位。

1　差分梯度匹配算法原理

路由器在传播Wi-Fi时，手机或其他Wi-Fi接收器所接收到的信号极易受障碍物的干扰和阻断，如果单纯通过RSSI即Wi-Fi信号强度的大小来得到带定位点与路由器直接距离，则所得距离偏差将会很大。Wi-Fi路由器所发出的信号强度范围在-1dBm到-120dBm之间。Wi-Fi接收器在接收到的信号基本没有什么衰减的情况下，一般能达到-35dBm。在信号强度小于-90dbm时，Wi-Fi接收器就基本上无法连接到该路由器。因此当Wi-Fi接收器接收某个路由器的Wi-Fi信号强度特别大，则表明该接收器距离此路由器距离相对较近。差分梯度匹配算法即基于以上所述的Wi-Fi信号传播特点而提出的。

Wi-Fi定位依靠和表征特征的指纹数据库进行匹配来进行识别。其定位过程包含两个阶段，即训练阶段和定位阶段。

其流程如图1 所示。

1.1训练阶段

训练阶段为定位阶段建立匹配的位置指纹识别数据库。首先，对待定位区域以一定的几何规律选择合理的指纹点分布，通常采用网格式指纹点分布。指纹点分布要确保能为定位阶段提供足够的信息。接着在每个指纹点上采集来自不同路由器的RSSI值，将对应的MAC地址和指纹点位置信息记录到数据库中。接着依次遍历所有选定的指纹点，并采集相应的信息。由于信号强度极易受干扰，为了得到相对稳定的信号强度值，需对采集的RSS值进行滤波处理，通常采用卡尔曼滤波算法来得到稳定的RSSI值。

1.2差分梯度匹配算法

指纹识别库中记录了每个参考指纹点所能接收到的Wi-Fi路由器的MAC地址和相应的RSSI值。

图1　Wi-Fi定位流程

设指纹库中的指纹点所保存的信息为：（lon，lat，mac1，lev1，mac2，lev2，…，maci，levi，…）其中i∈[1，n]，lon表示经度，lat表示纬度，mac表示路由器MAC地址，lev表示信号强度。

当前待定位点所采集到的信息设为：

（dmac1，dlev1，dmac2，dlev2，…，dmaci，dlevi，…）其中i∈[1，m]，lon表示经度，lat表示纬度，mac表示路由器MAC地址，lev表示信号强度。

在进行匹配时，必须保证计算的RSS值来自同一个路由器。因而首先对当前点所接收到的信号依据路由器的MAC地址进行排序。算法用两个vector，设为pa1，pa2，来保存两个位置点所接收到的不同路由器的信号值，当指纹点没有接收到待定位点所接收的路由器的Wi-Fi信号时，将对应的值保存为minLevel，即Wi-Fi接收器所能接收的最小的信号强度值。同样当待定位点没有收到指纹点所对应的路由器的Wi-Fi信号时，也将对应位置的值保存为minLevel。这样pa1和pa2即保存了指纹点和待定位点的所能接收到的所有的路由器的信号值的大小。

接下来需计算指纹点和待定位点之间的匹配率。计算方法采用差分梯度算法，即对Wi-Fi信号值进行梯度划分，将-1dBm到-10dBm作为第一梯度，当指纹点所接收到的信号值和待定位点所接收到的信号值都大于-10dBm，将其匹配率乘以该梯度的匹配率0.1，并同时检测指纹点和带定位点的信号值的差分平方是否小于100，若是小于100则将匹配率再乘以0.5。用差分平方的目的在于比较两者之间的信号强度大小的距离值。若是指纹点和待定位点的RSSI差值比较小，则表明两点在地理位置上比较接近。同样将-11dBm到-20dBm作为第二梯度，两者的信号值都大于-20dBm时，匹配率乘以该梯度的匹配率0.2，并同时检测指纹点和带定位点的信号值的差分平方是否小于100，若是小于100则将匹配率再乘以0.5。依次将-21dBm到-100dBm进行梯度划分，并将匹配率乘以相应梯度的匹配率。默认的总的匹配率为100。由于各点所能接收到的Wi-Fi路由器信号数量不一样，因而必须对所得值进行归一化处理。

算法流程图如下：

图2　差分梯度匹配算法流程

1.3定位阶段

Wi-Fi接收器接收到环境中的Wi-Fi信号后，依据上述的差分梯度匹配算法依次对指纹库里面的所有指纹点进行差分梯度匹配算法，计算指纹库中所有点的匹配率大小。找出匹配率最大的K个点，取出这K个点的经纬度，计算这K个点的几何中心，即为待定位点的位置坐标。

2　实验结果及分析

本文选择一个地下停车场作为测试环境，其地图如图3 所示。采用华为WS832型号的路由器作为Wi-Fi信号发射器，并采用华为荣耀3C手机作为信号接收器。在停车场中选择367个点作为指纹参考点，选择125个点作为待测点，其中A区有60个点，B区有65个点。所有数据用MySQL5.6进行保存，并利用C++进行定位处理。实验结果数据通过MATLAB进行统计分析。

图3　停车场微地图

表1统计了在不同误差范围内的点的数量，通过统计表明，70.4%的点误差都在4m以内。其中图4 的横轴表示所接收的路由器中Wi-Fi信号强度最大的点的信号值，纵轴表示计算结果和实际距离误差大小，通过图4 可以看出，当待测点的所接收到的最强的信号值较小时，所算的的误差将会偏大。

表1　匹配结果误差统计

图4　位置距离偏差大小和Wi-Fi信号强度的关系

从上图中可以看出，在Wi-Fi信号比较强的区域，本文所用算法偏差很小。然而当待定位点所在区域的信号均十分微弱时，定位偏差变的很大。其可能原因如下：

由于在距离路由器较近的地方信号衰减不是很大，但当距离路由器较远时，信号衰减随距离增加变化将非常大，因而采用线性方式对Wi-Fi信号强度值进行划分存在一定的不合理性。

由于待定位点是通过匹配指纹库中的参考点的信息，所有待定位点附近的参考点数量，也在一定程度上影响该点的定位精度。

3　结语

本文将讲解了Wi-Fi指纹定位的一般方法，并提出了一种基于差分梯度匹配的算法。在实验中通过对比传统的指纹匹配算法，可以发现本文算法在Wi-Fi信号强度较大的地方其匹配效果明显高于传统方法，但当待定位点处于Wi-Fi信号强度比较弱的地方时，其定位效果明显变差。本文算法可以结合KNN匹配算法进行定位，其信号间距离可采用欧氏距离。在匹配前先判断待定位点的信号强度，若信号强度有明显的一个或多个较大的值时采用本文算法，若所采集的所有的信号值都比较小则采用KNN匹配算法。从而弥补了由于信号强度较小而对定位产生的偏差。

[1]R.E.Kalman.A New Approach to Linear Filtering and Prediction Problems[J].Transactions of the ASME Journal of Basic Engineering，1960:35-45

[2]林玮，陈传峰.基于RSSI的无线传感器网络三角形质心定位算法[J]．现代电子技术，2009（2）：180-182．

[3]张明华，张申生，曹健.无线局域网基于信号强度的室内定位[J].计算机科学，2007（6）:68-71.

[4]陈文周著.Wi-Fi技术的研究与应用.数据通信，2008（2）.

[5]王晖.基于RSSI的无线传感器网络室内定位算法设计与实现[D].北京：北京邮电大学，2010.

Wi-Fi Fingerprint Positioning;Differential Gradient Match;Kalman Filter

A New Wi-Fi Location Method Based on Differential Gradient Matching Algorithm

ZHANG Qian-chu，LIU Zheng-xi
（College of Computer Science，Sichuan University，Chengdu 610065）

张乾初（1989-），男，安徽六安人，硕士研究生，研究方向为数字图像处理及地理信息系统

2015-12-08

2016-01-08

GPS定位系统被普遍使用在军用和民用系统中，但是由于房屋等障碍物的遮挡，GPS无法用于室内定位。随着经济的发展，Wi-Fi覆盖范围越来广，基于Wi-Fi的定位系统的实现越来越成为可能。提出一种基于差分梯度匹配算法的Wi-Fi定位方法，差分梯度匹配即对Wi-Fi的信号强度进行梯度划分，不同梯度对应不同的匹配率，通过计算当前待定位点和指纹库里所有指纹的匹配率，找到匹配率最高的K个点，以这K个点的几何中心作为带定位点的位置坐标。

刘正熙（1962-），男，四川成都人，教授，研究方向为数字图像处理、智能系统与信息处理

GPS positioning system is widely used in the military and civil systems,but because of housing and other obstacles,GPS cannot be used for indoor positioning.With the development of economy,the wide range of Wi-Fi coverage,the realization of the positioning system based on Wi-Fi is becoming more and more possible.Proposes a kind of based on differential graded matching algorithm of Wi-Fi location method,differential gradient matching is that dividing Wi-Fi signal strength to different gradient,different gradient corresponding to different matching rate,by calculating the current positioning and fingerprint library’s data matching rate and find the matching rate of the highest k points,the geometric center of the K points regard as the position coordinates of the current point positioning.