基于参考位置指纹离散程度的WKNN定位方法*

赵 芳

(新乡学院 计算机与信息工程学院， 河南 新乡 453003)

人们对无线通信的需求随着网络科技的飞速进步呈现出多样化特征，而位置服务[1-3]就是这些需求中最为关键的一项，然而位置服务会受到无线定位技术的限制.无线定位技术以地理位置为前提能够进行室内和室外定位[4-5].通常情况下能够经过北斗和GPS等卫星导航系统加以A-GPS辅助完成室外定位，且具有定位精度良好且效率高等特点.然而卫星信号穿透能力非常微弱，与此同时建筑物的墙壁也会对其产生阻挠作用，这在很大程度上使得卫星信号不能为室内设备提供定位服务.另外室内无线信号环境又非常繁杂，建筑物墙体和房间布局等很多因素都能致使无线信号产生多径效应.

随着智能手机等内部配置无线接入仪器的迅速发展，Wi-Fi信号已运用至大部分室内环境，同时以Wi-Fi技术为基础的位置指纹定位可以利用无线接入点在建筑内相异坐标的信号强度值，构建位置坐标和离线信号强度的指纹数据库，并将其作为在线定位的基础[6-7].通常情况下此方式的定位精度和效率会受到离线指纹数据库的有效性和位置相互匹配算法扰动的影响，因而本文提出了一种基于Wi-Fi指纹离散程度的WKNN定位算法(DD-WKNN算法).

1 离线位置指纹数据聚类

1.1 构建初始位置指纹数据库

设构建某个定位区域离线位置指纹数据库需有D个指纹信息采集点数据，同时其二维空间位置坐标为Li=(xi，yi)，i=1，2，…，D.各采样点可得到N个无线接入点的信号强度值，即

Ri=(ri1，ri2，…，riN)

(1)

各组指纹信息的数据结构可以表示为

Fi=(Li，Ri)=(xi，yi，ri1，ri2，…，riN)

(2)

将采样获得的数据运用行方式完成保存，进而获得其所有离线位置的数据库，即

(3)

式中，xD和yD分别为D指纹信息采集点的横坐标和纵坐标.

1.2 基于K-means算法的数据聚类

第一步：从D个指纹信息中随意择取K个指纹作为初始聚类中心集合C，且C=(C1，C2，…，CK)，Ci的数值与随意择取的位置指纹数据Ri(i=1，2，…，K)相等，即

C=(R1，R2，…，RK)

(4)

第二步：运算剩余的D-K个指纹和C中每个聚类中心Ci的欧氏距离，从而获得与此指纹相对最为逼近的聚类中心Ci，随之将其归至此聚类中，进而获得包括D个指纹信息的K个聚类，将各聚类中指纹信息个数定义为nCi(i=1，2，…，K).

第三步：重新运算K个聚类各自的聚类中心，随后用其替换原有的聚类中心，即

(5)

式中，Rm为第i个聚类中第m个位置的指纹数据.

第四步：以此循环往复第二、第三步直至运算获得的聚类中心值等于上个步骤的数值，换言之就是其收敛至极值，进而获得最终离线位置指纹信息聚类[8-9].

2 DD-WKNN位置指纹定位算法

在基于参考位置指纹离散程度的WKNN定位算法中，需要在上述所得数据内择取和在线实测RSSI值欧氏距离相对最为逼近的指纹数据，然后依照其离散程度设置位置估算参考权重的权值，令k个位置指纹的变异系数代表离散程度，随之完成归一化加权求和，其具体算法流程如下：

1) 在待定位位置实测各Wi-Fi无线接入点的RSSI采样值，记为RL，其表达式为

RL=(rL1，rL2，…，rLn)

(6)

式中，rLn为第n个Wi-Fi无线接入点在此待定位位置的信号强度RSSI采集值.

2) 依照RSSI采集值搜索与之对应的离线位置指纹数据库，利用式(7)择取k个和RSSI采样值欧氏距离最小的离线位置指纹数据库Fk，即

(7)

(8)

(9)

(10)

(11)

4) 将vi归一化后转化为权重系数wi，且二者关系为

(12)

5) 依照获得的权重系数完成对每个参考点的加权求和运算以估算其位置坐标，即

(13)

DD-WKNN算法具体实现流程如图1所示.

图1 DD-WKNN算法流程图

3 结果分析

择取实验地点为某大学能够感知多个Wi-Fi无线接入点RSSI值的办公区楼道，其Wi-Fi型号为AP6476，然后择取一块20 m×2 m的条形区域，此楼道区间能够同时得到大于等于8个未知位置传输出来的接入点信号，同时可测得其RSSI值.择取(0 m，1 m)～(20 m，1 m)作为待定位位置实际坐标区间，按照1 m间隔距离设定17个待定位位置，每间隔3 s完成一次各接入点信号的RSSI采样值记录，1 min后运算其平均值作为最终RSSI采样值.待定位位置具体布置如图2所示.

由于存在于所选区间房间内的Wi-Fi型号相同，同时每个房间都包含书桌、电脑和书柜等很多物体，且各房间门均为防盗门，因而所选区域Wi-Fi无线接入点的RSSI值可以认为是均匀分布的.在此区域内利用智能手机装置Wi-Fi检视仪获取周围Wi-Fi无线接入点的RSSI值[10].离线位置指纹数据的采样点择取楼道两边房间门所处的两条直线上，在(0 m，0 m)～(20 m，0 m)和(0 m，2 m)～(20 m，2 m)坐标范围内，每间隔1.5 m设定一个待测位置，且待定位位置总数为28，完成对8个Wi-Fi无线接入点RSSI值的采集后，取其平均值保存至指纹数据库，设K-means算法的聚类数目为3，最终获得的数据如表1所示.

图2 待定位位置布置

表1 指纹数据库中的采样点位置数据

为了检验从各位置采集到的Wi-Fi无线接入点数目对算法定位误差的扰动程度，从Wi-Fi无线接入点中择取4～8个点与最近邻NN算法进行对比分析，两种算法的定位误差分布如图3所示.

图3 无线接入点数目的扰动箱线图

由图3可见，当参考Wi-Fi无线接入点数目从4扩增至8时，最近邻NN算法[11]定位误差中值约从3.4 m缩减至3 m以下，而DD-WKNN算法则约从2.5 m缩减至0.5 m，可见，参考Wi-Fi无线接入点数目对位置指纹定位具有一定扰动，同时表现出正相关关系，即随着Wi-Fi无线接入点数目的不断扩大，最近邻NN算法和DD-WKNN算法的定位精度都有所改善.另外，在择取一致的Wi-Fi无线接入点数目情况下，DD-WKNN算法定位精度高于NN算法，同时其误差波动情况相对更小.

将本文算法、最近邻NN算法和基于欧氏距离的传统WKNN算法进行定位精度对比分析.分别在实验区域的(0 m，0.5 m)～(20 m，0.5 m)和(0 m，1.5 m)～(20 m，1.5 m)坐标范围内每距离1 m完成对待定位位置的RSSI值采集，且待定位位置总数为42.各采样点每间隔1 min完成对各无线接入点RSSI值的10次采样，同时择取其平均值作为实际测量值，分别运用三种算法完成对待定位位置坐标的估算，各算法的误差累积概率分布如图4所示.

图4 三种算法的实测性能对比

由图4可知，最近邻NN算法定位误差具有较高的数值，误差累积函数收敛速度相对最为缓慢，同时还具有相对较高的最大误差值.基于欧氏距离的传统WKNN算法的定位精度相比NN算法具有较大的优势，其最大误差值约为2.5 m.DD-WKNN算法的定位精度表现更加良好，其误差累积函数具有很快的收敛速度，同时其最大定位误差值约为1.6 m.综上所述，DD-WKNN算法在很大程度上提高了定位精度，同时具有相对更小的误差波动区间.

4 结 论

DD-WKNN算法将k个和待定位位置实际测量RSSI值欧氏距离相对最为逼近的指纹数据作为位置估计参照点，同时以其离散度作为权重系数的基础，对k个位置指纹数据进行加权求和运算以完成位置估计.依照位置指纹离散度权重信息将离散度相对较小的位置指纹数据赋予相对较高的权重，这能够在很大程度上防止Wi-Fi无线接入点由于室内布局导致RSSI值出现较大改变而引发的定位误差问题.实验分析结果表明：DD-WKNN算法的定位精度高于以欧氏距离作为权重系数的传统WKNN算法和最近邻NN算法，且DD-WKNN算法具有更小的误差波动.