基于改进加权KNN算法的室内无线电发射源定位研究

杜太行 孟岩 孙曙光 江春冬 田朋

摘要：针对室内无线电发射源的位置指纹定位问题，提出一种改进加权KNN定位算法。在分析现有定位算法的基础上，建立测试点和参考点的余弦相似度关系，并把该余弦相似度用作KNN在线定位计算的权重，计算出第一次加权质心定位结果，根据此结果判断是否进行二次加权来确定测试点最终的估计位置，最后进行算法的仿真测试。结果表明，较之传统位置指纹算法该算法定位准确度提高17%左右，不仅克服传统算法在发射源定位中由于在线阶段针对测试点接收到的信號强度不同造成的定位稳定性差的问题，还避免当存在离测试点较远的参考点时造成的定位误差大的问题。

关键词：位置指纹定位;KNN算法;余弦相似度;二次加权质心算法;参考点

中图分类号：TP391;TH823 文献标志码：A 文章编号：1674-5124（2019）09-0105-07

收稿日期：2019-01-10;收到修改稿日期：2019-02-28

基金项目：河北省教育厅资助科研项目（ZD2016108）

作者简介：杜太行（1963-），男，天津市人，教授，博士生导师，主要研究方向为电器检测、计算机应用。

通信作者：孙曙光（1979-），男，河北河间市人，副教授，博士，主要研究方向为智能检测、故障诊断。

0 引言

随着无线电技术的发展，查找室内无线电信号发射源非法使用者的位置是无线电管理中的一项重要工作。位置指纹定位算法是当前研究较热的室内定位算法之一[1]，它一般利用室内无线局域网中的接入点（access point，AP），在参考点处用接收端接收到的指纹信号建立离线数据库，在线阶段利用相应的定位算法确定移动接收端的位置。位置指纹定位技术由于其无需部署其他设备，操作简单且定位精度高，成为当前室内定位技术中越来越受欢迎的定位技术之一。

以上AP是固定的发射源，被定位的是接收端[2]。考虑到位置指纹定位技术在定位中的优势，可以将其从定位接收端引入到所研究的定位发射源的问题上。同时，也会面临一些问题。问题主要集中在两方面[3]：一是离线阶段指纹信号的采集及其处理，它直接影响指纹数据库的准确性。文献[4]探究了离线阶段建立的指纹数据库受采样间距的影响;文献[5]提出了增大参考点之间的欧氏距离确定接收端位置的方案;文献[6]中利用平滑均值滤波方法对采集信号的接收信号强度（received signal strength，RSS）值进行均值平滑处理，提高信号采集的精度。二是在线定位算法的适用性，它会影响整个定位系统的精度。文献[7]提出了改进的基于区域划分的定位算法;文献[8]提出一种以位置指纹离散度作为权值参考的改进加权K近邻（weighted K nearestneighbor，WKNN）位置指纹定位算法;文献[9]提出了改进型 KNN（K nearest neighbor，KNN）算法，旨在提高精度减小计算复杂度。而在发射源的定位系统中，而由于接收机型号不同或环境差异造成在在线阶段针对测试点接收到的信号强度不同，依靠传统方法，即通过参考点和测试点之间欧氏距离的大小计算权重会造成一定的误差。而且在有些情况下，定位算法对参考点的选取会使离测试点较远的参考点参与定位计算，这样也会产生较大误差。

本文从定位算法方面人手，针对发射源的定位系统中由于在线阶段针对测试点接收到的信号强度不同和存在离测试点较远的参考点的问题，提出了一种改进加权KNN算法。将余弦相似度用作加权质心算法的权重，并根据初始定位结果选择二次加权算法来确定测试点的最终估计位置。最后利用仿真实验进行了验证，将所得结果与传统的KNN算法进行比对。

1 发射源的位置指纹定位技术

1.1 定位原理

位置指纹定位通常分为两个阶段：离线阶段和在线阶段。由图1所示，离线阶段的主要工作是建立指纹数据库。

首先选定一个区域，如图2所示，根据空间大小及实际现场环境选择采集节点AP的个数，并固定采集节点的位置。从区域中选取多个参考点，然后把这些参考点的强度信息和位置信息一并存入离线指纹数据库中。在线阶段即指纹匹配阶段，用某种定位算法将测试点强度信息与指纹数据库中的指纹进行匹配，得到测试点的位置坐标，从而实现定位。

离线阶段建立的数据库中的指纹信号强度表示如下：

[YSSl7 rssi，…rssi”1

RSSi=（YSSi]，YSSi2，" " " ，YSSin）表示任意一个参考点的指纹信息，YSSin表示第n个采集节点接收到的第i个参考点的信号强度值。

要准确地确定测试点的位置信息，除了要在离线阶段建立一个高质量的数据库，在线阶段的定位算法也同样重要。常用的位置指纹算法有最近邻（nearest neighbor，NN）法、K近邻法和基于欧氏距离的加权K近邻法。

1.2 位置指纹定位算法

1）最近邻法

最近邻法是位置指纹定位最基本的匹配算法，它通过接收机接收到的发射源的信号强度与指纹数据库中保存的信号强度进行比较，找出欧几里德距离最小的参考点，其坐标即为测试点的定位结果。

测试点与参考点i的关于信号强度的欧氏距离矢量表示为：其中RSS=（rss₁，rss₂，…，rss_n）为采集节点对测试点测得的信号强度特征值。

2）K近邻法

K近邻是在最近邻法基础上做出的改进。对式（2）取最近的K个距离，（xk，Yk）为第k组参考点的坐标信息，将这K个距离所对应的参考点的坐标的平均值作为测试点的定位结果。如式（3）所示：

3）基于欧氏距离的加权K近邻法

加权K近邻法是基于K近邻法的改进。K近邻法取的是K个最小欧氏距离所对应的参考点的坐标的平均值。但根据信号传播模型，距离越小，信号强度值越大，对定位结果的影响程度就越大，因此对这K个最小欧氏距离所对应的坐标采用权值分配，距离越小，权值就越大。如式（4）所示：其中w_k=1/L_k为第k个参考点的权重，为相应欧氏距离的倒数。

2 基于余弦相似度的二次加权KNN定位算法

2.1 基于余弦相似度的权重分配

如上所述欧氏距离表示空间中两点的真实距离，作为一种最基本的相似性度量方法，由于算法简单，成为KNN算法的核心。在室内定位技术中，参考点的RSS值越接近于测试点的Rss值，得到的欧氏距离就越小。而在实际中由于接收机型号不同或环境差异造成在线阶段针对测试点接收到的信号强度不同。如图3所示，以3个接收机为例，即信号强度特征向量为3维，图3中尸是数据库中的参考点，RSS_P表示P的信号强度的特征向量，即为图3中的OP矢量。S₁、S₂是测试点，RSS_S是测试点的信号强度特征向量，即为OS矢量，OS₁与OS₂正是反映由于接收机型号不同或环境差异导致信号强度不同问题所造成的向量大小的变化刀巧{和PS₂表示接收机在同一测试点位置接收到的信号强度得出的参考点与测试点之间的欧氏距离，在这种情况下采用欧氏距离进行参考点权重计算，会造成针对同一测试点的参考点权重计算不同，进而造成较大的定位误差。

而余弦相似度[10]是通过两个向量的夹角余弦值来评估它们的相似度。相比于欧氏距离表示空间中两点之间的实际直线距离，余弦相似度更多的关注于两个向量之间方向上的关系。因此可基于此对加权KNN算法進行改进，利用余弦相似度代替欧氏距离的倒数作为权重进行定位，即计算参考点对应的强度特征向量与测试点对应的强度特征向量的相似度情况。表示为：其中P，RSS_S>是点P和点S的信号强度特征向量的内积，|RSS_P|·|RSS_S|是信号强度特征向量的长度的乘积。基于上述原理在图3中尽管OS₁与OS₂向量长度数值上有差异，但其与参考点的余弦相似度cosθ的数值是不变的，也即针对同一测试点的参考点权重计算相同，可消除接收机型号不同或环境差异造成的在线阶段针对测试点接收到的信号强度不同造成的定位误差问题。既而可以结合KNN原理求出参与定位计算的K个参考点。

2.2 二次加权质心算法的位置估计

在上述基础上，利用加权质心算法进行位置估计，将最终确定的K个参考点组成一个多边形，然后计算多边形的质心作为测试点的估算位置。

当所求得的参考点的分布较为均匀时，采用质心算法可以取得较高的定位精度。但是，有时候K个参考点中常常存在离测试点比较远的点，采用一次质心算法就会容易受到这些点的干扰，定位结果就会不同程度的偏向这些点，在这种情况下，一次质心算法会产生比较大的定位误差，如图4所示，A为离测试点较远的参考点，I'为一次质心算法的定位结果，而s为测试点的真实位置。

因此，本文采用二次加权质心算法[11]。第一次质心加权算法预估出测试点的初始位置，然后计算初始位置与每个参考点的距离，与提前设置的阈值进行比较，阈值根据实验环境和参考点的布局间距综合考虑选取，若都小于该阈值，则完成定位，直接输出定位结果;若超出该阈值，则用第一次定位结果来取代离初始位置较远的参考点，进行二次加权质心计算估算出测试点的准确位置，在图5中，用I'取代A，再利用B、C、D、E、I'组成的多边形的质心I作为最终的定位结果。

由此，基于余弦相似度的二次加权KNN定位算法如下：其中，（x_i，y_i）表示第_i组参考点的坐标信息，r_i表示第i个参考点与测试点之间的余弦相似度关系。（x'，y'）为一次加权定位结果，（x"，y"）为二次加权定位结果，S_j为一次加权定位结果与第j个参考点的距离，Thr为设定的阈值，在此第j个参考点为离测试点较远的参考点。

3 室内定位仿真实验原理

3.1 信号传播模型

为了验证本文所提的改进加权KNN算法的合理性，应用仿真实验来模拟实际环境中无线电发射源的定位，信号传播模型选用最常用的对数距离衰减模型，模型表示为：

PL（d）=PL（d₀）+10_nnlg（d/d_n）（7）其中，PL（d）是距离发射源d处的信号传播损耗，PL（d₀）为近地参考距离的路径损耗，在室内，近地距离d₀一般取1m，n₀为路径损耗因数，自由空间中一般取2，在实际环境中，n₀会有所不同，室内办公室一般在1.8～2.8[12]。

3.2 仿真实验步骤

1）离线阶段，根据定位区域选取合适的接收机的个数并部署接收机的位置。然后利用仿真信号传播模型进行离线阶段参考点指纹信号采集，把采集到的强度信息和位置信息一并存入指纹数据库。

2）在线阶段，仿真采集测试点的强度信息，并与指纹数据中的数据进行比对，选用基于余弦相似度的二次加权KNN算法作为定位算法。仿真实验定位流程如图6所示。

4 仿真实验及结果分析

利用Matlab仿真平台，对本文提出的改进加权KNN算法进行仿真验证，为了模拟实际环境中接收机型号不同或环境差异引起的接收信号强度差异，在线阶段中，在每次测试中针对测试点的强度信息仿真采集，在信号传播模型中加入一随机值，以模拟接收机接收强度的差异;定位环境选择为10m×10m、 20m×20m，使用了4个接收机，并根据经验部署接收机的位置。参考点的布局间距取1，2，3m分别建立数据库。定位误差如下：式中，（x_p，y_p）表示第p个测试点的实际位置坐标，（x_p'，y_p'）表示第P个测试点的估计位置坐标。

为分析余弦相似度作为权重在解决由于接收机型号不同或环境差异造成在线阶段针对测试点接收到的信号强度不同而带来的定位误差问题，下面分别在10m×10m和20m×20m的环境下进行仿真验证，并用基于余弦相似度的KNN算法与KNN算法和基于欧氏距离的WKNN算法进行结果对比。

4.1 10m×10m定位实验分析

10m×10m的环境下，在不同的K值下，参考点的布局间距分别取1m、2m进行实验。K=3，布局间距为2m时基于余弦相似度的KNN算法与传统的KNN和WKNN算法在各个测试点的定位误差如图7所示。相比于其他两种算法，基于余弦相似度的KNN算法的定位误差波动较小，且最大定位误差均小于其他两种算法。

将图7中25个测试点的定位误差进行统计得到图8中的累计误差概率分布，由统计结果可知，基于余弦相似度的KNN算法的小误差累计概率更高。

为了考察不同K值时的定位效果，表1为上述环境下，参考点的布局间距为1m，K值取3～7时，基于余弦相似度的KNN算法与其他两种传统算法平均定位误差的对比，可见基于余弦相似度的KNN算法的定位平均误差均小于其他两种算法。

4.2 20m×20m定位实验分析

20m×20m的环境下，在尺二3时，参考点的布局间距分别取1m、2m、3m进行实验，3种算法的平均定位误差如表2所示，结合实验结果，同时为了降低计算复杂度，在此布局间距选取为3m。

K=3时3种定位算法在各个测试点的定位误差如图9所示。图10为36个测试点的累计误差概率统计结果。3种算法在K值取3～7时的平均定位误差比较如表3所示。

综上，由图7～图10和表1～表3所得结果均能说明本文的基于余弦相似的KNN算法提高了定位精度，克服了定位中由于接收机型号不同或环境差异造成在在线阶段针对测试点接收到的信号强度不同引起的定位稳定性差的问题。

4.3 一次加权与二次加权质心算法的误差对比分析

为了分析二次加权在存在离测试点较远的参考点时的修正作用，在20m×20m的环境下，参考点的布局间距为3m，K=3时一次加权与二次加权算法在各个测试点的定位误差如图11所示，均采用基于余弦相似度的权重分配。由结果可知，由于离测试点较远的参考点参与在线定位计算造成了某些测试点误差较大，在经过二次加权计算之后误差有所降低。

表4为上述环境下，K值取3～7时，一次加权与二次加权算法的平均定位误差对比结果，二次加权算法的平均定位误差均小于一次加权结果。尺毕3的条件下，进一步与表3中KNN算法和WKNN算方法进行对比，得出本文算法的平均定位误差由约2m减小到了1.65m，平均定位精度提高了17%左右。

综合以上3种实验分析，本文基于余弦相似度的KNN算法相比传统的KNN和WKNN算法，解决了接收信号强度的差异造成的定位稳定性差的问题，提高了定位精度。在此基础上采用二次加权质心算法，修正了较远参考J点带来的定位误差大的问题。

5 结束语

本文提出一种基于余弦相似度的二次加权KNN定位算法，用于对发射源的定位。以余弦相似度作为KNN在线定位计算的权重;并根据情况进行二次加权以准确估计测试点的位置。仿真结果验证了该算法的合理性，相比传统的KNN和WKNN算法定位精度提高了17%左右，采用基于余弦相似度的权重分配，解决了由于接收机型号不同或环境差异造成在线阶段针对测试点接收到的信号强度不同引起的定位稳定性差的问题;二次加权改善了由于较远参考点造成的定位误差大的问题。将本文算法应用到复杂的实际环境中，优化接收机的部署位置，是后续需要研究的内容。

参考文献

[1]李昊.位置指纹定位技术[J].山西电子技术，2007（5）：84-87.

[2]谢代军.无线局域网室内定位技术研究[D].郑州：解放军信息工程大学，2013.

[3]秦泗明.基于位置指纹的WiFi室内定位技术研究[D].成都：电子科技大学，2013.

[4]罗宇锋，刘艳辉，李晓春.WiFi指纹定位中采样间距对定位精度的影响[J].全球定位系统，2018，43（3）：77-81，94.

[5]杜太行，李娟妹，江春冬，等.平台侧位置指纹定位系统中接收端问题的优化[J].电讯技术，2017，57（8）：950-956.

[6]汪伦杰，廖兴宇，潘伟杰，等.基于信号均值滤波+k-means+WKNN的Wifi指纹定位算法研究[J].微电子学与计算机，2017，34（3）：30-34.

[7]蔡朝晖，夏溪，胡波，等.室内信号强度指纹定位算法改进[J].计算机科学，2014，41（11）：178-181.

[8]田洪亮，钱志鸿，梁潇，等.离散度WKNN位置指纹Wi-Fi定位算法[J].哈尔滨工业大学学报，2017（5）：94-99.

[9]李昂，肖甫，李雷.基于改進型KNN算法和Android平台的室内定位技术研究[J].物联网技术， 2018，8（3）：21-25.

[10]赵聪.基于位置指纹的WLAN室内定位算法研究[D].哈尔滨：哈尔滨工业大学，2014.

[11]王缓缓，邱建文.基于区域分割的二次质心定位算法[J].计算机应用与软件，2015（4）：279-282.

[12]李红丽.基于WiFi的室内定位技术的研究[D].北京：北京交通大学，2014.

（编辑：刘杨）