基于自适用权重的最近邻居法室内定位方法研究

刘宏

(湖南衡阳北方光电信息技术有限公司，衡阳 421001)

基于自适用权重的最近邻居法室内定位方法研究

刘宏

(湖南衡阳北方光电信息技术有限公司，衡阳 421001)

由于室内物体的移动导致室内定位精度影响整个网络数据。目前算法所能解决的一般为二维空间，对于三维移动物体的定位精度较差。自适用权重的最近邻居法通过赋予邻居不同权值求取平均值来确定移动物体的位置，通过周边三个不同位置的加权平均值从三个角度来定位移动物体，以此来提高三维移动物体的定位精度，实验表明自适用权重的最近邻居法比传统的定位算法具有更高的适用性和定位精度。

室内定位；定位精度；定位；移动物体

1 定位算法的理论分析

最早的基于无线局域网的定位系统是微软公司开发出的RADAR系统。RADAR系统提出依靠信号强度指纹数据库的、采用NNSS-AVGN或者NSS算法来实现定位。RADAR系统包括校准阶段和定位阶段这两个阶段来实现定位。

校准阶段需要建立指纹数据库[1]，又被称为离线训练阶段。创建指纹数据库的步骤如下：

第一步：布置n个无线信号源APl…APn。

第二步：设置参考点，并且在参考点处收集无线信号。RSSIi表示采集到的第i个AP节点发射的无线信号强度值，n个信号构成一组信号强度值，例如（RSSI1，RSSI2，RSSI3…，RSSIn）。

第三步：同一个参考点采集X次，然后对每一个AP（ii=l…n）计算信号强度平均值RSSI1，n个信号构成一组的信号强度均值

第四步：将该组参考点坐标位置和信号强度均值保存到指纹数据库。

第五步：选则下一个参考点，并且重复第二步到第四步的过程，一直到满足系统所需要参考点数目为止。

NNSS（Nearest Neighbors in Signal Space），又被称作最近邻居法[2,3]。在RADAR系统，无线信号空间距离也被称为为欧氏距离。而与测试点欧氏距离相离最近参考点则被看作为最近邻。以下是欧氏距离的计算公式：

如果在RADAR系统使用NNSS算法来实现系统的定位功能，定位阶段的步骤如下所示：

输入在校准阶段所创建的指纹数据库，n个无线信号发射点为APl…APn，存在一个待测点，就是定位点。

输出待测点位置坐标。

第二步：根据公式（1），计算出该信号强度值与数据库中的各个信号强度值的欧氏距离D，并找出最小D值的指纹数据。

第三步：将D值最小的参考点的位置坐标作为待测点的位置坐标。

采用NNSS算法作为定位方式，待测点的估计坐标只能选择参考点的位置坐标[4,5]，这会导致定位结果呈离散状。定位精度也会受到影响。NNSS-AVG（Nearest Neighbors in Signal Space-Average）算法则可以将定位的结果分散到连续的空间。在RADAR系统

在公式中，（x,y）表示的是待测点坐标，（xi，yi）表示前k个D值最小的参考点的位置坐标。

根据线性距离的路径损耗模型L（d）=ad+lo可以看出[6]，待测点信号强度和发射点与待测点的距离可以看作为线性关系。由于室内的环境存在遮挡的情况，所以无线信号传播模型也存在着很大误差，但是在无线信号发射点与待测点距离较短的情况下，我们仍然可以将距离与信号强度的关系线性化。为了利于讨论定位算法性能，在短距离空间内，我们可以采用位置的欧氏距离去代替信号强度的欧式距离。

假设有四个参考点A、B、C、D，点的坐标分别设为（0，0）、（0，4）、（4，0）、（4，4）。T坐标为（2，2），横坐标和纵坐标的单位都为米，如图1所示。A与T的欧氏距离为米，这与B、C、D点与T点之间的欧氏距离相等。如果使用NNSS算法把待测点定位于A，B，C，D点其中任意一点。定位误差约为米，如果使用NNSS-AVG算法，假设k=4，用公式2可以估算出待测点的位置为（2，2），误差为 0 米。的定位阶段的第二步中，与NNSS算法步骤只取一个D值最小的参考点不同，采用NNSS.AVG实现室内定位时，将欧氏距离值D进行排序，选取k个D值最小的参考点。并且在定位阶段的第三步中，把k个参考点的坐标求取平均值，并且由此估算出待测点的位置坐标。以下是待测点坐标计算公式：

图1 定位误差分析

这样看来，NNSS-AVG算法比NNSS算法精度更高，不过在待测点与其中一个参考点相接近时，即假设参考点 A、B、C、D 点的坐标分别为（0，0）、（0，4）、（4，0）、（4，4），待测点 T 的坐标为（1，0），横坐标和纵坐标的单位为米，如图2所示。A、B、C、D点与T的欧式距离分别为1米、4.123米、3米、5米。根据NNSS算法将，待测点定位于A点即位置坐标为（0，0）的点。根据公式误差米。如果使用NNSSAVG算法，假设k=4，用公式2可以估算出待测点的位置为（2，2），定位误差为米。这个时候NNSS算法又比NNSS-AVG算法精度更高。这种结果的原因是T点离A点距离很近，离B、C、D点较远。T点的真实位置应在A点的旁边，但是由于引入B、C、D点，导致了定位误差的加大。因此对于不同邻居，我们不能统一的看待，但是可以通过赋予它们不同权值代替求取平均值。接下来介绍一种基于权重的NNSS-AVG算法即WNNSS-AVG算法。

图2 加权定位误差分析

2 自适用权重的最近邻居法

NNSS-AVG算法中各个近邻权值可以看成1/k，NNSS-AVG算法的加权方式如公式（3），（4）所示：

在公式（3）中wi表示第i个邻居权重。在公式4中D表示信号空间欧氏距离。利用WNNSS-AVG算法，用位置欧氏距离来代替信号强度欧氏距离。假设k=4，利用公式3、4可以估算出待测点坐标为（0.5，0.33），定位误差为米，与N算法和NNSS-AVG算法相比，WNNSS-AVG算法的定位精度有了很大幅度的提高。

3 信号强度指纹方法的性能研究

在下面的实验环境中，进行Wi-Fi信号的统计特性实验，并且对NNSS，NNSS-AVG，WNNSS-AVG的定位性能进行研究分析，然后确定Wi-Fi定位系统的最优定位引擎方案。

第一步：对整个商场建立一个横轴为x纵轴为y的二维坐标系。

第二步：选取目标周围较近三个节点为参考节点，计算出它们的坐标，三点的坐标分别为（160，30），（180，18），（168，29）。

第三步：使用基于RSSI模型公式分别对目标节点与三个参考节点间进行测距，测出目标到第一个节点的距离为5米，到第二个点的距离为9米，到第三个节点的距离为7米。

第四步：采用三边测量法公式对目标节点进行定位，此时定位并不精确，本文采用极大后验概率确定目标在坐标点（162,25）的概率最大。通过以上几步得到目标的最终坐标（162,25）。

4 实验及数据分析

（1）实验场地和数据收集

实验所需硬件：一台红外线测距仪、4个无线路由器、一台Android平板电脑。实验所需软件：安装在Android平板电脑上的Wi-Fi指纹采集系统。实验场所：由一条走廊和一间会议室组成的室内场所。选取会议室中的一个墙角作为原点，并且建立横坐标、纵坐标。在横轴和纵轴上面每隔0.5米取一点。如图3所示，在坐标为（3.25，0.5），（0.5，3），（5.5，3），（3.25，5.5）处分别放置4个无线路由器，并分别作标记APl，AP2，AP3，AP4。然后在这个坐标平面上进行实验，并且对定位结果进行数据分析。

（2）测试数据取平均值的实验

在各种因素的干扰下导致单次的取值可能会存在误差较大情况。通过Wi-Fi信号强度概率分布实验，我们可以得知通过多次的取值，并且计算位置的平均值能降低单次取值所引起的误差。因此，在实验的测试数据收集中，分别在45个测试点各选取了30组信号强度数据。然后从各个点的数据中，选取出连续的3组或10组数据，求取平均值后来作为一个计算数据。并且每个点取2个计算数据，计算在WNNSS-AVG算法存在的定位误差。最后与只选取了一组数据作为计算数据的情况进行对，对比情况如表1所示。

图3 数据采集的实验布置1

表1 WNNSS-AVG不同取值方案位置误差（米）统计

通过数据分析，1组、3组、10组方案平均误差分别为1.3138米、1.2628米和1.2076米。在0.5米内，1组、3组、10组方案的定位误差累积率分别为20.12%、12.123%、17.81%。在1.5米内，1组、3组、10组方案的定位误差累积率分别为65.47%、63.41%、64.39%。从该定位算法误差累积的概率分布图可以看出，在1.5米内，3组和10组的方案并没有优于1组的方案。但是在2米之后，3组和10组的方案明显优于1组。在2米之内，l组、3组、10组方案定位误差的累积率分别为78.98%、86.76%、85.67%。3组和10组方案的最大定位误差都在4米以内，然而1组的方案有1.21%概率定位误差在4米以上。

5 结语

以目前的Wi-Fi室内定位的水平，允许存在2米之内的定位误差。所以使用3组和10组的方案可以有效防止系统出现4米以上的较大误差。但是考虑系统的实时性，系统每选取一组数据大约需要1秒的时间，如果选择10组的方案，定位时间将会大于10秒。综合考虑定位误差和实时性，因此室内定位方案应该选择3组方案的WNNSS-AVG算法比其他算法的适用性和精度都要高。

[1]魏叶华,李仁发.无线传感网络中的一种二阶段定位算法[J].计算机应用与软件,2012,30（2）:204-207

[2]黄学青,房鼎益.基邻居筛选的质心迭代定位算法[J].杭州电子科技大学学报，2011,28（6）:59-62

[3]汪炀,黄刘生.一种基于RSSI校验的无线传感网络节点定位算法[J].小型微计算机系统,2012,30（1）:59-62

[4]王福豹,史龙.无线传感网络中的自身定位系统和算法[J].软件学报,2005,16（5）:857-868

[5]马玉秋.基于无线传感器网络的定位技术研究及实现[D].北京：北京邮电大学，2006,23-24

[6]田洪强.智能建筑无线传感器网络控制节点的设计实现[D].北京：北京交通大学，2010,59-62

Abstract：The positioning accuracy affects the whole network data due to the movement of indoor objects.At present,the algorithm can solve the twodimensional space,and the positioning accuracy of 3D moving objects is poor.Adaptive weighted nearest neighbors method by giving differ⁃ent weights to neighbors are normalized to determine the position of the moving object,through the surrounding a weighted average of the three different position from three angles to locate the moving objects,in order to improve the positioning precision of the 3D moving object,the experiments show that the adaptive weight nearest neighbors method than the traditional localization algorithm has higher applicability and localization accuracy.

Keywords：Indoor Localization;Positioning Accuracy;Positioning;Moving Object

Research on the Nearest Neighbors Localization Method Based on Adaptive Weighted

LIU Hong

（Hunan Hengyang North Photoelectric Information Technology Co.Ltd.,Hengyang 421001）

1007-1423（2017）26-0029-04

10.3969/j.issn.1007-1423.2017.26.007

刘宏（1980-）,男,湖南衡阳人,本科,研究方向为数据挖掘、智能信息处理、红外跟踪、红外制导

2017-08-24

2017-09-10