基于奇异值检测和AP聚类的室内指纹定位算法

蒋亚虎

（广东松山职业技术学院 计算机系，广东 韶关512126）

0 引 言

如何利用无线局域网的基础设施完成室内定位，是室内定位技术的热点问题。基于接收信号强度的无线局域网指纹定位技术是无线局域网定位算法中具有较好效果的定位方法［1，2］。很多研究者对无线局域网指纹定位算法进行了深入研究，文献 ［3］提出了基于阈值分类及信号加权的室内定位算法，文献 ［4］提出了基于物理邻近点辅助的指纹定位算法，体现了物理地形与位置指纹之间的关联性，能够得到精度较高的算法。

1 接收信号强度值指纹定位算法

RSSI指纹定位算法有两个步骤：

（2）在线定位：移动节点运动到某位置时可将该位置接收到的各无线节点强度记录下来，并发送到上位机，上位机将该数据与离线训练系统得到的数据库信号指纹匹配，通过对比，信号强度最匹配所对应的位置即是移动节点的位置。其中匹配算法的优劣直接关系到定位算法的准确性［6］。

2 奇异值检测

无线局域网指纹定位算法离线阶段采集各节点数据时，由于存在多径干扰等因素影响，一个参考点接收来自某无线节点的信号强度值会出现不同程度的抖动，严重的抖动会对该位置的RSSI均值和标准差引起较大变化，降低定位性能，所以有效去除信号强度抖动可以提高离线训练系统性能，本文融合了Hampel滤波器与核密度估计，提出了一种奇异值检测方法。

2.1 Hampel滤波器

Hampel滤波器与3σ准则相似，3σ准则通过数据集合中的均值和标准差，确定某数据为正常数据还是可以数据，但是由于奇异值对均值和标准差的影响较大，这种效应会影响3σ准则的判断效果［7］。Hampel滤波器与3σ准则具有类似的规则，但是判断数据集中数据是否为奇异值不再依赖均值和标准差，而是中值和偏离中值绝对值的中值 （median absolute deviate from median，MAD）。对于数据集合P ＝｛pi｝，median（P）表示中值，MAD 用R 表示，R 计算公式如下

中值和MAD 值计算简单，适用与无线节点网络。Hampel滤波器的弊端是，当数据集中大多数数据相等时，MAD 值为0，这样导致所有数据均被判断为奇异值。

2.2 核密度估计

核密度估计可以用来评估数据集的分布，核密度估计是评估随机变量概率密度函数的方法，其估算量f∧（p）定义如下［8］

式中：［P］——数据集合P 的个数，pi——数据集合中的一个采样，其分布可通过核函数来评估，不同的核函数对评估性能影响不大，Epanechnikov核函数具有较优的最小方差感知效果，其计算公式如下

2.3 一种奇异值检测算法

KDE算法与Hampel滤波器在评估效果方面有互补作用，KDE算法可以克服Hampel滤波器的不足，Hampel滤波器也可以在奇异值造成核密度过高时正确识别奇异值。本文将KDE算法与Hampel滤波器结合起来，给出了奇异值检测算法，算法步骤如图1所示。

图1 奇异值检测算法流程

定义MAD 规模分变量，该变量由Hampel滤波器中的R 引申，MAD 规模分计算如下

MAD 规模分是数据集样本偏离中值的程度，将Hampel滤波器与KDE概率密度估计联合起来可得到可信度ci

prob（pi）由核密度计算得到。当概率密度较大、MAD规模分较低，可信指标值较高，数据可信，当概率密度较小、MAD规模分较高，可信指标较低，数据不可信。在指纹定位算法离线训练阶段，设定某阈值，对上式计算得到的可信度进行检测，小于门限值的接收点信号强度视为奇异值剔除。

3 AP聚类算法

无线局域网指纹定位算法中，随着定位区域的扩大，离线训练系统中的数据量也变得越来越大，后期在线定位系统需要参与运算的数据就增多，为了克服这一问题，减少不相干的数据，可以用AP 聚类算法将目标区域划分为多个小区域，缩小定位计算复杂度。

AP聚类根据数据之间的相似度分类，这些相似度构成了相似度矩阵S，并且每个元素都添加负号成为负数，计算公式如下［9］

AP聚类不需要事先制定聚类数目，所有数据都是潜在的聚类中心，相似度矩阵对角线上的值s（k，k）是k作为聚类中心的判断标准，值越大，可能性越大，该值也称为参考度p。AP聚类算法中体现两种信息，吸引度信息和归属度信息［10］。吸引度反映了j点是否可作为i 点的聚类中心，计算方法如下

a（i，j）是归属度，反映了i是否选择j 作为聚类中心

自归属度a（j，j）反映的是点j作为聚类中心的证据，计算方法如下

a （j，j）越大，j作为聚类中心的可能性越大，a（i，j）＋r（i，j）值最大的j点就是i 的聚类中心，聚类算法循环迭代每个点的归属度和吸引度

λ是阻尼因子，0＜λ＜1，研究表明，λ＝0.65时所需计算成本最小，聚类中心连续迭代10次而未发生变化或者迭代次数为100次时，可认为迭代完成。

4 基于AP聚类的粗定位与细定位

随着无线局域网定位区域的增大，定位算法变得更为复杂，AP聚类算法可以简化计算复杂度，消除误差，本文利用在线测量的RSSI与AP 聚类中心点的RSSI向量之间的相似度进行粗定位。

4.1 基于AP聚类的粗定位

在线移动端接收到的RSSI向量数据传输到服务器，服务器计算该向量与数据库各类中心点向量之间的相似度，据此，判断数据属于哪个类，在算法实际运行过程中，可能会出现移动终端与两个或多个类相似度接近，这时如果将移动终端划分到其中某个类可能会导致不准确的判断，因此需要选择一组与测量向量有最大相似度的聚类中心集合S，其成员为C，归属关系如下

在向量相似度计算时，本文选择计算复杂度较低的方法：s（r，j）＝－－，α是门限值，通过该门限获得一组聚类中心点，因为该值的大小直接关系到聚类中心数目的多少，影响计算复杂度的高低，在此，本文定义其取值如下

其中，α1＋α2＝1。

4.2 细定位

细定位用于确定移动终端的最终位置，加权k近邻算法具有较好的效果，在粗定位将数据集合减少为C 后，运用加权k近邻算法完成细定位。具体过程如下

设RSSx＝｛RSSx1，RSSx2，…RSSxm｝表示在x 点处接收到的信号强度，n 是无线节点个数，RSS′i＝｛RSS′i1，RSS′i2，…，RSS′i3｝表示指纹库中i点的信号强度，若定位区域有m 个位置参考点，则记为向量｛RSS′1，RSS′2，…，RSS′m｝，其与位置｛L1，L2，…，Lm｝对应。实时信号强度与数据库位置i处信号强度的欧式距离为

实时移动终端的位置为

加权k近邻算法是选取欧式距离最小的k 个点，计算这些点的加权平均，将其作为位置估计点，加权k 近邻算法的计算公式如下

式中：d——一个数值很小的正数，防止公式中分母出现零的情况。

5 基于奇异值检测和AP聚类定位算法

本文提出了基于奇异值检测和AP聚类定位的无线局域网指纹定位算法，算法流程如图2所示，具体步骤如下：

（1）将定位区域划分为网格，设置位置参考点，侦测不同参考点所接收的不同无线信号强度值RSSI。

（2）将本文提出的奇异值检测算法应用到第一步得到的RSSI值中，去除奇异值。

（3）对经过奇异值检测的RSSI向量值进行AP 聚类，并生成最终的指纹数据库。

（4）进行基于AP 聚类的位置初定位，确定位置的聚类信息。

（5）用加权k近邻算法评估的到移动用户最终的位置，完成定位过程，得到定位结果。

图2 定位算法流程

6 实验结果分析

仿真场景是大小为22m×22m 的区域，不同参考点之间的距离为2 m，区域中放置4 个无线节点，型号是TPlink，均匀标记121个参考点，在实际环境中，无线局域网信号均有不同程度抖动，所以本文在模拟RSS时加入了抖动因子。在离线采集阶段，每个参考点生成200 个接收信号强度值，然后将强度值通过奇异值检测算法，去除奇异值，再根据AP聚类法对模拟环境中的参考点聚类，经过粗定位，用户会归属到某个聚类中。假设参考点可分为M类，每类有参考点N 个，则未进行粗定位时，定位算法的复杂度为Ο（M×N），而用本文定位计算复杂度为Ο（M ＋N）。在本文仿真环境中即可看出，采用本文算法，在线定位阶段，最多需计算23次，而其它算法均需计算121 次，计算量大大降低。

在仿真区域中随机选择200个样点，对每个样点用本文算法和其它典型的定位算法分别定位100次，得到定位误差累积分布图，如下所示，从仿真结果来看，本文算法定位精度优于文献 ［7］算法，平均误差在3m 内的概率为61%左右，算法计算时间缩短，具有较好的定位性能。

不同算法误差累计概率如图3所示。

图3 不同算法误差累计概率

7 结束语

本文提出了一种基于奇异值检测和AP 聚类的无线局域网室内定位算法，该方法首先对奇异值检测算法进行了探讨，结合Hampel滤波器和核密度估计给出了一种奇异值检测算法，然后将AP 聚类应用到离线训练系统中，经过粗检测和细检测完成室内目标定位。实验结果表明本文算法能够有效对无线环境中的目标进行定位，且定位误差在3m 内的概率为61%，平均定位误差有降低，减小了计算复杂度，是一种有效的室内目标定位算法。

［1］DONG Zhe，WU Yao，SUN Dehui.Multi－source data fusion algorithm on indoor location technology ［J］.Computer Engineering and Design，2014，35 （5）：1527－1530 （in Chinese）.［董哲， 吴瑶，孙德辉.室内定位技术的多源数据融合算法研究 ［J］.计算机工程与设计，2014，35 （5）：1527－1530.］

［2］SHI Xin，YIN Aimin，CHEN Xi.RSSI and multidimensional scaling based indoor localization algorithm ［J］.Chinese Journal of Scientific Instrument，2014，35 （2）：261－267 （in Chinese）.［石欣，印爱民，陈曦.基于RSSI的多维度室内定位算法 ［J］.仪器仪表学报，2014，35 （2）：261－267.］

［3］YANG Xiaoliang，YE Ayong，LING Yuanjing.Indoor localization algorithm based on threshold classification and signal strength weighting ［J］.Journal of Computer Applications，2013，33 （10）：2711－2714 （in Chinese）. ［杨小亮，叶阿勇，凌远景.基于阈值分类及信号强度加权的室内定位算法 ［J］.计算机应用，2013，33 （10）：2711－2714.］

［4］ZHOU Mu，ZHANG Qiao，QIU Feng.Fingerprinting location method for WLAN using physical neighbor points information ［J］.Journal of Computer Applications，2014，34 （6）：1563－1566 （in Chinese）.［周牧，张巧，邱枫.基于物理邻近点辅助的无线局域网指纹定位方法 ［J］.计算机应用，2014，34 （6）：1563－1566.］

［5］WU Bin，LI Jun’e.Application of wireless sensor network in indoor localization ［J］.Computer Science，2013，40 （5）：115－117 （in Chinese）.［吴彬，李俊娥.无线传感器网络在室内定位中的应用研究 ［J］.计算机科学，2013，40 （5）：115－117.］

［6］XU Jin，ZHAO Dongming，WU Xiaojun.Improved difference correction algorithm of wireless localization based on RSSI［J］.Instrument Technique and Sensor，2014 （5）：77－79 （in Chinese）.［徐进，赵东明，吴小军.基于RSSI的无线定位差分修正改进算法 ［J］.仪表技术与传感器，2014 （5）：77－79.］

［7］Pearson RK.Outliers in process modeling and identification［J］.IEEE Transactions on Control Systems Technology，2002，10 （1）：55－63.

［8］Chen YC，Sun WC，Juang JC.Outlie detection technique for RSS－based localization problems in wireless sensor networks［C］／／Proceedings of SICE Annual Conference，2010：657－662.

［9］Tian Z，Tang X，Zhou M，et al.Fingerprint indoor positioning algorithm based on affinity propagation clustering ［J］.EURASIP Journal on Wireless Communications and Networking，2013 （1）：272.

［10］LIN Haijuan，CHEN Xiaoyun.Clustering of combining AP with NN based on time series［J］.Computer Engineering and Applications，2014，50 （2）：153－155 （in Chinese）. ［林海娟，陈晓云.基于时间序列的AP－NN 混合模型聚类 ［J］.计算机工程与应用，2014，50 （2）：153－155.］