0 引言

    随着通信技术和智能科技的不断发展，定位技术在日常生活中发挥着越来越大的作用，人们对定位服务的需求逐渐增大。室外定位GPS以及基站定位技术已经发展成熟，出现了多种室内定位技术，如：RFID(射频识别)、WiFi、蓝牙、红外线等。定位方法有基于到达时间(TOA)、基于信号强度(RSS)、基于到达角度(AOA)的方法^[1]，还有一些通过加速度传感器等手机内的集成传感器件来实现定位^[2]。现阶段，智能手机相当普及，WiFi也基本覆盖大多数公共场所，WiFi定位无需额外的硬件需求，具有低成本、低功耗、高精度等特点，因此其在众多定位方法中具有很大的优势。

    本文通过扫描室内的WiFi信息，在Android平台上通过改进的指纹匹配定位方法实现室内定位。

1 WiFi位置指纹定位方法

1.1 指纹定位方法

    基于WiFi无线网络的定位技术有很多，其中以基于信号强度RSS的定位技术最为常用^[4]。在基于RSS的定位技术中位置指纹定位方法较为普遍。位置指纹定位方法^[5]分为数据采集阶段和实时定位阶段两部分。在数据采集阶段，在区域内均匀地选择N个数据采集点，在每个采集点，通过安卓手机采集所有AP的RSS信息，并将所有RSS信息以及该点的坐标(x，y)存入数据库^[6]，等待第二阶段调用。在实时定位阶段，用户在未知位置发出定位请求，安卓手机采集该点AP的RSS信息并传送至数据库，通过匹配算法以及第一阶段采集的RSS数据得到位置坐标(x，y)反馈给用户，定位完成^[7]。

    在第二阶段定位过程中，kNN算法是较为常用的一种传统匹配算法。

1.2 kNN算法(最邻近算法)

    临近算法即k最邻近分类算法(kNN，k-NearestNeighbor)^[8]，核心思想是：如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。

    在kNN算法中要准确选择参数k的值，当k较小时，选择临近点数量较小，不能准确地确定参考点的类别，增大了误差；当选择k较大时，则会选择较远的点，导致定位结果不准确。因此，应多次测量决定参数k的值。本实验经多次测试，k为3时误差最小，因此k取3。

    AP_n代表定位区域内的n个WiFi热点。在数据采集阶段，在第i个位置采集n个WiFi的RSS信息，i=1，2，3，…，m，m为参考点个数，每个WiFi热点采集多次RSS取平均值。Rij为在第i个位置采集到的第j个WiFi的RSS的平均值，j=1，2，3，…，n；n为WiFi个数，(x_i，y_i)为i点的实际坐标。在定位阶段，在待定位点测得第j个WiFi的RSS平均值为R_j，则R_ij与R_j之间距离为：

2 改进算法WR-kNN

    由于室内物品较多以及人员的不断走动，使得室内环境变得复杂，人员以及物品的阻挡使WiFi信号发生衰减^[10]，加大了室内的定位难度。本文通过对距离进行加权^[11]以及去除无用组来增加定位精度。在离线阶段对扫描得到的数据进行加权，加大有用数据的权重，在进行定位匹配时，预先将数据按照RSSI均值大小升序排序，取前k个数据进行运算，减少了运算量，降低了小数据对结果的影响。

2.1 加权kNN

    首先对kNN算法中参考点与待测点之间的距离进行加权。kNN算法中，参考点与待测点的距离越接近，相似度越高，在定位中贡献越大。加大贡献大的距离的权值，减小贡献小的距离的权值，有助于提高定位精度。因此，短距离赋予较大的权值w_j，长距离赋予较小的权值w_j：

因此在第i个位置采集到的第j个WiFi的平均RSSI值为R_ijw_j。d_j为两点之间的距离，当参考点离待测点越近时d_j越小，相对应的权值w_j越大，该参考点所采集的RSSI值越大，对定位影响越大，因此可以提高定位的精度。

2.2 数据排序

    在定位阶段，数据库调出采集的RSSI数据，对待测点的数据与数据库调出的数据进行一一对比，选取较为接近的k个数据作为相似组，利用相似组的数据通过质心算法得到最终的待测点的位置坐标。本文改进是在数据调用之前首先将所有采集的数据R_ijw_j通过Comparator接口进行升序的排列，数据库中数据将按照由大到小的顺序在组中排列，在调用数据时，只选取组中前n个较大的数据，然后与待测点扫描数据进行匹配，选取较为接近的k个数据进行定位。此方法不仅消除了无用组信息对定位的干扰，还对数据组进行了删减，删除了对定位结果贡献较小的数据组，可以使系统快速地得出定位结果，提高了系统的定位效率。

    Comparator接口为Java中的一个对集合或者数组对象进行排序的比较器。Comparator接口的实现函数为int compare(Object o1，Object o2)，排序分为升序和降序排列。当o1<o2返回-1(负数)、o1=o2返回0、o1>o2返回1(正数)时，则为升序排列；当o1<o2返回1(正数)、o1=o2返回0、o1>o2返回-1(负数)时，则为降序排列。改进算法中首先将数据放入Gro.Entry<Integer，Integer>中，通过compare(Gro.Entry<Integer，Integer>o1，Gro.Entry<Integer，Integer>o2)函数进行升序排列。

3 实验

3.1 离线数据采集阶段

    实验区域内部有10个AP，每隔2.5 m采样一次，共有12个采样点。首先测试WiFi信号稳定性。随机选取一个WiFi信号，每隔10 s扫描一次，结果如图1所示。

    如图1所示，WiFi信号强度基本分布在-77 dBm～-83 dBm之间，个别时间有较大波动，总体较为稳定。采集时采用平均值作为数据储存，可减小较大波动带来的影响，并可以作为定位所需的参考数据。

    离线数据采集阶段，在采样点，每个AP采样10次，将RSS的平均值计入数据库。将RSSI_j表示第j个AP的RSSI平均值，MAC_i表示第i个采样点的10个AP的mac地址集合，(x_i，y_i)表示第i个采样点坐标。R_i={RSSI_i1，RSSI_i2，…，RSSI_i10}表示第i个采样点所采集的10个AP的RSSI平均值的集合。数据库中一个完整信息为[R_i，MAC_i，(x_i，y_i)]。

3.2 在线定位阶段

    在线定位阶段，随机选取7个测试点进行定位，在每个测试点定位3次，取坐标平均值作为最后测试结果，如图2所示。图2分别显示了测试点坐标即定位结果、原坐标即测试点所在的正确坐标以及传统算法定位所得的坐标。如图所示，改进后的坐标相对传统算法所得坐标更加靠近原坐标。宏观上来看，改进算法相比传统算法更加精确。

    分别基于改进算法WR-kNN以及传统算法所得定位结果进行误差分析，得到如图3所示的误差分布图。由图可看出改进算法误差皆小于传统算法误差。表1为误差数据，分别对应图3中7个采样点。

    由表1可以得出，传统算法平均误差为2.55 m，最小误差1.48 m，最大误差4.09 m，误差波动较大。由于传统算法中直接采用即时数据，室内环境复杂，人员走动频繁，因此WiFi信号波动较大，不加以处理直接存入数据库，使得定位结果与实际差距较大。传统定位算法较为复杂，累积误差较大，选取匹配对象不科学，导致定位结果出现偏差，且定位时间较长。WR-kNN算法在数据采集时通过多次采集数据取均值，然后对其进行加权处理，避免了信号波动带来的影响，同时减小了远距离AP带来的误差。定位阶段通过对调用的数据进行预处理，精简了定位流程，减小了定位所需时间，提高了效率，同时减小了累积误差。因此改进算法误差较小，平均误差仅为1.93 m，相对传统算法平均误差减少了0.62 m，误差在2 m左右波动，较为稳定。

4 结束语

    本文采用一种改进的kNN算法研究了基于Android平台的指纹室内定位。离线定位阶段，通过对采集的数据进行加权，增大有用数据的权值，减小无用数据的权值；在线定位阶段，通过对调用的数据预先进行排序，去除无用组，减小不稳定信号对定位结果的影响。实验表明，该改进算法定位结果较为精确，相对传统算法提高了0.62 m。由于实验环境较为复杂，人员较多，AP较多且部署较为随机，因此对实验结果有影响。如果在较为空旷且AP部署较为规范的实验场地，定位结果将更加精确。

参考文献

[1] 倪巍，王宗欣.基于接收信号强度测量的室内定位算法[J].复旦学报(自然科学版)，2004，43(1)：72-76.

[2] RANTAKOKKO J，RYDELL J，STROMBACK P，et al.Accurate and reliable soldier and first responder indoor positioning：multisensor systems and cooperative localization[J].Wireless Communications，IEEE，2011，18(2)：10-18.

[3] 梁元诚.基于无线局域网的室内定位技术研究与实现[D].成都：电子科技大学，2009.

[4] 崔斌，赵西安.一种基于传播模型和位置指纹的混合室内定位方法[J].测绘通报，2015(6)：35-38，43.

[5] 张明华，张申生，曹健.无线局域网中基于信号强度的室内定位[J].计算机科学，2007，34(6)；68-71.

[6] 张俪文，汪云甲，王行风.仿射传播聚类在室内定位指纹库中的应用研究[J].测绘通报，2014(12)：36-39.

[7] 张明华.基于WLAN的室内定位技术研究[D].上海：上海交通大学，2009.

[8] YANG Z，WU C，LIU Y.Locating in fingerprint space: wireless indoor localization with little human intervention[C].Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.ACM，2012：269-280.

[9] 张晓亮，赵平，徐冠青，等.基于一种优化的KNN算法在室内定位中的应用研究[J].电子设计工程，2013，21(7)：44-46.

[10] 杨凯，郭英，毕京学.基于安卓平台的室内实时定位[J].测绘科学，2015，40(6)：125-128.

[11] 陈振洲，李磊，姚正安.基于SVM的特征加权KNN算法[J].中山大学学报(自然科学版)，2005，44(1)：17-20.

作者信息:

武  一，张冀钊

(河北工业大学 电子信息工程学院，天津300400)