[0056] 以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。需说明的是，在不冲突的情况下，以下实施例及实施例中的特征可以相互组合。
[0057] 本发明的目的是针对现有技术的缺陷，提供了一种基于KD树和改进加权KNN的室内指纹定位方法。
[0058] 实施例一
[0059] 本实施例提供一种基于KD树和改进加权KNN的室内指纹定位方法，如图1‑2所示，包括步骤：
[0060] 1.1构建RSS指纹数据库；
[0061] 1.2采集不同位置的RSS序列，并对所述采集到的RSS序列进行均值平滑滤波处理，得到滤波后的RSS指纹信息；
[0062] 1.3基于所述RSS指纹数据库构建KD树存储结构，将得到的滤波后的RSS指纹信息输入KD树存储结构进行处理，得到K个近邻点的RSS指纹特征；
[0063] 1.4计算K个近邻点的RSS指纹特征与滤波后的RSS指纹信息的余弦相似度，得到K个近邻点的RSS指纹特征与滤波后的RSS指纹信息的余弦相似度的系数；
[0064] 1.5将得到的余弦相似度系数输入softmax加权KNN算法中进行处理，输出概率相似度作为加权KNN算法的权重，并计算得到指纹的定位结果。
[0065] 室内指纹定位方法包括离线和在线两个阶段，在离线阶段得到样本的RSS指纹数据库；在线阶段对测试点进行定位。
[0066] 第一步：离线阶段：
[0067] 在步骤1.1中，构建RSS指纹数据库。
[0068] 构建RSS指纹数据库是在离线阶段构建的，具体的构建离线阶段指纹数据库的方法为：
[0069] 1.11采集定位目标区域的RSS样本值以及与RSS样本值相对应的坐标，根据采集的RSS样本值与相对应的坐标得到RSS指纹样本信息；
[0070] 首先在给定的目标定位区域布置n个发射源AP，将实验目标区域网格化，采集网格交叉点处各点的RSS样本值与实际的物理坐标，以参考点i为例，得到参考点i的RSS样本序列，即RSS指纹样本信息，表示为：
[0071] RSSi＝(rssi1,rssi2,...,rssin)
[0072] 其中，RSSi表示任意一个参考点所采集的RSS指纹样本信息；rssi×n表示第n个AP接收到的第i个参考点的信号强度值。
[0073] 将采集到的若干个样本点的序列表示成一个RSS指纹矩阵，表示为：
[0074]
[0075] 1.12对得到的RSS指纹样本信息进行均值平滑的预处理，得到均值滤波处理过后的RSS指纹数据库。
[0076] 对n个AP所采集到的RSS样本的进行均值平滑滤波处理，滤波具体方法如下：
[0077] 选取s个与参考点Pi(xi，yi)之间的实际距离的参考点d<δ的参考点，表示为：
[0078]
[0079] 其中，xi，yi表示参考点在二维空间上的位置坐标信息，xj，yj表示选取的s个参考点的位置坐标，δ表示距离的常数，用于控制均值平滑滤波的平滑程度，通常设置为略大于参考点之间平均距离。
[0080] 因此取s个距离最近的参考点的RSS值的均值，并把RSS的平均值赋值给Pi(xi，yi)作为该样本点的RSS值，表示为：
[0081]
[0082] 其中，s表示满足要求的参考点数量，遍历样本序列则得到均值平滑滤波后的RSS′序列。
[0083] 对所采集到的RSS指纹样本进行均值平滑的预处理，得到均值滤波处理过后的RSS指纹库矩阵：
[0084]
[0085] 其中，RSS′库表示对任意一个参考点经过平滑均值滤波处理后RSS指纹数据库；rss′i×n表示第n个AP接收到的第i个参考点滤波后的指纹特征值(接收信号强度值)。
[0086] 在本实施例中，经过平滑均值滤波过后RSS样本序列明显接近理想的RSS值，提高了指纹信号采集的精度。
[0087] 第二步：在线阶段：
[0088] 在步骤1.2中，采集不同位置的RSS序列，并对所述采集到的RSS序列进行均值平滑滤波处理，得到滤波后的RSS指纹信息。
[0089] 构建RSS测试样本，在目标区域，使用不同的接收终端采集m组不同位置的测试RSS样本序列，进行均值平滑滤波处理，得到滤波后的测试点指纹信息，即可构建一个最终需要的m×n的在线定位的测试矩阵，即滤波后的RSS指纹信息，表示为：
[0090]
[0091] 其中，RSS″表示对任意一个测试点经过平滑均值滤波处理后RSS指纹信息；rss″m×n表示在第n个AP接收到的第m个测试点滤波处理后的指纹特征值(接收信号强度值)。
[0092] 在步骤1.3中，基于RSS指纹数据库构建KD树存储结构，将得到的滤波后的RSS指纹信息输入KD树存储结构进行处理，得到K个近邻点的RSS指纹特征。
[0093] 构建KD树存储结构：
[0094] 由于KNN算法的重点在于找出K个最邻近的点，一般情况下，在位置指纹定位的在线阶段，需要线性扫描输入样本点与每一个训练样本点的距离，当离线指纹数据库较大时，计算非常耗时。所以对离线阶段所构建的指纹数据库建立KD树存储结构。KD树(K‑dimension Tree)是一种存储K维空间中的样本向量并且利用其空间二叉树特性提升数据点搜索效率的树形数据结构。
[0095] 基于离线RSS指纹数据库构建KD树的构建步骤为：
[0096] (1)从指纹特征向量数据库中的i个样本的n维接收信号强度特征中，分别计算n个维度特征取值的方差，用方差最大的第k维指纹特征rssk作为根节点。对于这个指纹特征，选择取值的中位数 作为样本的划分点，对于小于该值的样本划分到左子树，对于大于或等于该值的样本划分到右子树。
[0097] (2)对左右子树采用同样的方式找到方差最大的指纹特征作为根节点，递归可产生KD树。
[0098] 在本实施例中，将滤波后的RSS指纹信息输入KD树存储结构进行处理具体为：
[0099] A1.对每个输入的RSS指纹信息利用KD树存储结构搜索K个距离最近的近邻点，得到每个RSS指纹信息升序排列的K个距离序列，
[0100] 当构建好KD树以后，开始搜索K个距离最近的参考点；输入m×n测试样本矩阵的RSS特征向量RSS″＝(rss″1,rss″2,…,rss″n)，其中rssi＝(rss″i,1,rss″i,2,rss″i,3,…,rss″i,n)，rss″i为第i个参考点的指纹特征向量，为第i个指纹特征向量的第n个AP接收到的接收信号强度。
[0101] KD树算法搜索K个距离最近的近邻点的具体方法为：
[0102] (1)对于一个测试RSS样本点，我们首先在KD树里面找到包含目标点的叶子节点。从根结点出发，若切分坐标的坐标值大于输入结点坐标值，则移动到左子结点，否则移动到右子结点。继续向下搜索直至找到叶子结点，以该叶子结点为当前最近邻点；
[0103] (2)从该叶子结点向上递归进行最近邻搜索，若当前结点与输入结点距离小于最近邻点与输入结点距离，更新最近邻点为当前结点，同时以输入结点为圆心，输入结点与最近邻点间的距离为半径绘制超球体，若球体与切分超平面相交，则移动到另一子结点并继续递归进行最近邻搜索。若不相交，向上回退，直至回退到根结点搜索结束。
[0104] 对每个输入的测试RSS序列利用KD树算法搜索K个距离最近的近邻点的得到每个测试点升序排列的K个距离序列，表示为：
[0105] d＝[d1,d2,…,dK]
[0106] A2.计算RSS指纹信息与参考点i的信号强度。
[0107] 距离d的衡量指标采取欧式距离的大小，测试点与参考点i的关于信号强度的欧式距离计算公式如下，表示为：
[0108]
[0109] 其中，di表示RSS指纹信息与参考点i的信号强度。
[0110] 步骤S3中得到K个近邻点的RSS指纹特征，表示为：
[0111]
[0112] 其中， 表示K个近邻点的RSS指纹特征。
[0113] 上述得到K个近邻点的RSS指纹特征的公式可拓展为矩阵形式，表示为：
[0114]
[0115] 在本实施例中，步骤S3中还包括：
[0116] 计算K个近邻点所对应的坐标信息，表示为：
[0117]
[0118] 其中，表示K个近邻点所对应的坐标信息。
[0119] 该算法在在线阶段的定位算法中，面对训练数据较大时，可以加快KNN算法的K邻近搜索过程，极高的提升了定位算法的工作效率。
[0120] 在步骤1.4中，计算K个近邻点的RSS指纹特征与滤波后的RSS指纹信息的余弦相似度，得到K个近邻点的RSS指纹特征与滤波后的RSS指纹信息的余弦相似度的系数。
[0121] 将所得到的第K个近邻点的RSS指纹特征计算余弦相似度，计算得到近邻参考点与测试点的余弦相似度的系数R，表示为：
[0122]
[0123] 其中，R表示余弦相似度的系数；RSS″表示每个测试点的RSS指纹信息； 表示K个近邻点的RSS指纹特征； 表示近邻参考点和测试点的内积，表示RSS特征向量长度的乘积。
[0124] 得到每个测试点的K近邻点的余弦相似度序列为：
[0125] Ri＝[r1,r2,…,rK]
[0126] 其中，Ri表示第i个测试点所对应K个近邻的余弦相似度序列，rK表示测试点与K个近邻点的余弦相似度系数。
[0127] 在室内定位系统中，由于接收终端的不同或环境差异造成在在线阶段针对测试点接收到的信号强度不同，依靠传统方法，即通过参考点和测试点之间欧氏距离的大小计算权重会造成一定的误差。而且在有些情况下，定位算法对参考点的选取会使离测试点较远的参考点参与定位计算，这样也会产生较大误差。
[0128] 在步骤1.5中，将得到的余弦相似度系数输入softmax加权KNN算法中进行处理，输出概率相似度作为加权KNN算法的权重，并计算得到指纹的定位结果。
[0129] 将每个测试点余弦相似度序列作为softmax函数的输入，输出的概率相似度作为加权KNN算法的权重，公式为：
[0130]
[0131] 其中，Si表示第i个指纹特征输出的权重；Ri表示第i个测试点与参考点之间的余弦相似度系数。
[0132] 将得到的权重结合坐标信息采用softmax加权KNN算法进行计算得到指纹的定位结果，表示为：
[0133]
[0134] 其中，(xi，yi)表示K个近邻内第i组参考点的坐标信息；(x′，y′)表示softmax加权KNN最终定位结果。
[0135] 本实施例对KNN室内指纹定位算法进行改进，提出了一种基于KD树和softmax加权KNN的定位算法。该算法对接收的RSS值进行均值平滑处理，通过KD树搜索K邻近，计算K近邻点的余弦相似度，并用softmax加权KNN算法计算待测点的位置。实验结果表明本文的算法在定位精度和定位稳定性上都优与KNN和WKNN算法，平均定位误差为1.59m，并且提升了定位效率和降低了接收终端不同对定位精度产生的影响。
[0136] 实施例二
[0137] 本实施例提供的一种基于KD树和改进加权KNN的室内指纹定位方法与实施例一的不同之处在于：
[0138] 本实施例以某一实验室为例具体说明。
[0139] 实验室长为15m，宽为8m的矩形实验场地。选择路由器作为无线接入器，在室内布置4个AP，分别放置在角落，感知AP的设备采用Android系统的智能手机作为接收终端，型号为华为荣耀20，使用信号测量APP作为RSS值的接收工具，采集来自AP的4维RSS指纹特征样本信息。
[0140] 1)离线阶段，根据定位区域选取合适的AP的个数，将实验区域网格化，采集网格交叉点处各点的RSS值与实际的物理坐标，对RSS值进行均值平滑处理，建立离线指纹数据库。
[0141] 2)在线阶段，收集待测点在某一位置的接收信号强度特征参数，利用KD树算法提升搜索k邻近效率，并采用基于距离相似度的softmax函数加权的KNN算法作为定位算法。
[0142] 在指纹库构建和定位的阶段，对KNN算法、加权K近邻算法与本实施例的Softmax加权KNN算法进行比较实验，采用相同手机终端的情况下，为了降低计算的复杂度，参考点的网格间隔取1m进行实验，分别计算这3种定位算法在不同K值情况下的平均误差，实验结果如图3所示。
[0143] 从图3可以看出，刚开始K值的增大，定位精度逐渐增大，平均定位误差开始降低，当K值取3的时候，平均定位误差取得最小值，再随着K的增大，定位误差开始增大，定位精度开始下降。当K值等于3时，3种算法的平均定位误差取得最小，所以后续实验采取K为3作为K邻近个数。相比于KNN算法和WKNN算法，平均定位误差由1.81m减小到1.59m，说明本实施例的Softmax加权KNN算法定位精度远优于其他算法。
[0144] 定位与指纹库构建阶段，采用相同的手机终端情况，对不同位置定位误差的波动性进行实验对比，图4分别使用传统的KNN算法，WKK算法和softmax加权KNN算法定位，得到待测节点的定位误差。从结果上看，相比于KNN和WKNN算法，本算法的定位误差波动较小，且最大定位误差均小于其他两种算法。
[0145] 由图5给出了构建离线阶段指纹库的KD存储结构的原理图。
[0146] 下表1表示KD树算法在K邻近搜索的效率对比：
[0147]
[0148] 表1
[0149] 从上表1可以看出，在KNN算法搜索K邻近的过程中，KD树算法能够减少算法运行时间，使得样本整体搜索范围变小，提升了算法的定位的工作效率。
[0150] 从图6可以看出，P为参考点，S1、S2是测试点，OS1、OS2是由于接收终端不同而导致向量大小变化不同，而余弦相似度是通过两个向量的夹角余弦值来评估它们的相似度。相比于欧氏距离，余弦相似度更多的关注于两个向量之间方向上的关系。尽管OS1、OS2向量长度数值不同，但其参考点的余弦相似度cosθ的值是不变的，针对同一测试点的权重计算相同，可在一定程度上降低了不同接收终端造成的定位误差。
[0151] 从图7可以看出，本实施例所提出的算法降低了由于接收终端型号不同所造成的在线阶段针对测试点接收到信号强度的差异，对不同终端做对比后，定位结果基本上和AP配置关系不大，在不同接收终端采集RSS信号是理想外界条件的情况下，采用本算法进行在线阶段定位计算可以一定程度上降低不同终端的影响。
[0152] 本实施例针对KNN室内指纹定位算法进行改进，提出了一种基于KD树和softmax加权KNN的定位算法。该算法对接收的RSS值进行均值平滑处理，通过KD树搜索K邻近，计算K近邻点的余弦相似度，并用softmax加权KNN算法计算待测点的位置。实验结果表明本文的算法在定位精度和定位稳定性上都优与KNN和WKNN算法，平均定位误差为1.59m，并且提升了定位效率和降低了接收终端不同对定位精度产生的影响。
[0153] 注意，上述仅为本发明的较佳实施例及所运用技术原理。本领域技术人员会理解，本发明不限于这里所述的特定实施例，对本领域技术人员来说能够进行各种明显的变化、重新调整和替代而不会脱离本发明的保护范围。因此，虽然通过以上实施例对本发明进行了较为详细的说明，但是本发明不仅仅限于以上实施例，在不脱离本发明构思的情况下，还可以包括更多其他等效实施例，而本发明的范围由所附的权利要求范围决定。
