摘 要： 阐述了位置指纹定位算法在室内WLAN环境中的应用，分析了KNN定位算法存在的不足，提出一种模糊聚类KNN位置指纹定位算法。该算法首先选取与空间相关性较好的4个信号参数，构成多径纹信号数据库；然后应用主分量分析法（PCA）对原始信号数据库作降维运算，滤除奇异性接入点（AP）；最后用模糊C均值聚类算法（FCM）处理数据，进一步滤除奇异性参考点（RP），实现提高定位算法效率与精度的目的。实验表明，改进后的定位算法产生的定位误差明显减小。
关键词： 位置指纹；室内定位；模糊聚类；KNN定位算法；信号数据库
随着现代通信技术和网络技术的发展，人们可携带计算设备的广泛应用，以及国内城市开展无线城市试点工作，用户可以通过计算设备随时随地接入互联网，由此，基于位置的服务LBS（Location-based Services）也受到了社会越来越多的关注。与此同时，基于卫星导航定位技术的全球定位系统GPS（Global Position System）已在众多领域得到普及。
然而，在室内环境下，由于卫星信号被物体阻挡，无线信号不能正常传输，GPS的导航功能无法正常实现，且无线传感定位系统要有专用传感器和网络支持，需化费较多人力和财力。因此，应用室内区域的WLAN网络（如Wi-Fi）进行移动目标的定位管理是一个较适宜的解决方案。
1 定位算法
基于Wi-Fi网络的室内定位系统大多数是利用接收信号强度（RSS）的均值，其方法一般分为信号传输模型法和位置指纹识别法两类。前者是利用待测点接收至少3个接入点之间的距离信息，由一定算法估计待测点的位置；后者是通过待测点多径信号特征指纹信息与数据库预存参考点多径信息进行比对分析，系统需运行大量数据，用一定算法估计待测点坐标。
1.1 信号传输模型定位算法
信号传输模型定位算法可以分为测距与定位两个阶段。首先，待测点接收来自3个不同已知位置接入点AP的信号强度值，通过中值滤波技术提取均值；然后，根据无线信号的室内传输损耗模型，将接收信号强度转换为待测点与相应AP的距离；最后，应用三角形定位算法估算。
无线信号的室内传播模型[1，9]，一般简化为：
FCM算法是一个简单的迭代与优化过程：用值在0~1间的随机数初始化隶属矩阵U，或初始化聚类中心，通过反复的迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果。该算法适合于正态分布的数据聚类，对于奇异性孤立点数据有敏感性，因此，可用于基于信号强度的定位算法。
FCM算法因算法简单，收敛速度快，且能处理大批量数据，解决应用性问题广。本文应用FCM算法可以实现从待测点角度对相关数据进行有效的处理；聚类处理后可以滤除奇异性RP。聚类处理前后数据比较如图1所示。实际上这类RP距离待测点较远，会引起较大的定位误差。因此，FCM算法能起到“数学聚焦”的功能，有助于提高定位精度。所谓奇异性RP是指影响定位精度较大的参考点。
2 模糊聚类KNN定位算法
2.1信号指纹数据库
为了克服信号强度RSS值对信道传输模型的依赖性，如多径效应、墙壁阻挡和环境条件的变化等因素，提出了使用位置指纹定位算法。本文分析了信号强度各类特征参数与空间相关性的关系，认为选取4种参数构成数据库较为合适，能更多地保留空间信道的相关信息，即信号强度的均值、中值、最大值和最小值为特征参数。
由于室内多径信号传播对环境有很大的依赖性，某一位置上信道的多径结构理论上是唯一的，终端无线信号经过反射和折射传输，产生与周围环境密切相关的特定模式的多径信号，这种多径特征的信号可认为是某位置上的“信号纹”，因此选取网格化参考点RP，构建了多径信号数据库，进行离线训练学习过程，用主分量分析法（PCA）降维和优化数据库。由此建立了信号特征参数与空间位置的内在对应关系，为后续比对分析提供保障，并以主分量数据进行存储，可以节省容量和提高运算效率。4×k维的多径信号数据库结构如图2所示。
2.2 定位算法
2.2.1 主分量分析法PCA
首先，从宏观上，用主分量分析法（PCA）处理高维度数据库，在不损失主要信息的基础上，以低维度线性组合的数据进行运算，采用正交变换矩阵和拉格朗日乘子法[7]，根据估计坐标与参考坐标的均方差最小化原则，选取参考点RP对应的合适接入点AP和参数构成信号纹数据库。其次，从微观上，用模糊C均值聚类算法（FCM）处理待测点数据，通过设置相应的隶属度和相似性的阈值，进行数学筛选；将大于隶属度阈值及小于相似性阈值的奇异性数据识别与挖掘出来，滤除奇异性参考点RP；在数学运算上，通过模糊分类矩阵实现目标函数的最小化，以确保聚类的数据具有较好的相似性，以提高定位精度。
在线定位阶段是收集待测点在某一位置的信号特征参数，也是其收集周边若干AP的信号及AP的宏地址，由待测点标签再发回至定位服务器；通过模糊聚类KNN算法，将实测数据与预存数据进行对比分析，根据目标函数最小化原则，保留起主要作用的RP，提取待测点周边的RP预存值，即确定聚类范围；计算待测点与参考点的距离，选取相似性好的RP，即以距离为依据选取RP，从而估计待测点的实际坐标。具体步骤如图3的下面3个方框所示。
3 定位实验
3.1 实验平台
为了评估本文定位算法的实际性能，设置的实验环境是：警院安防科技园3楼5间100 m2的展示区，隔墙材料为轻质石膏板，层高为3.3 m。将12只定位AP均匀排列，安装高度为2.4 m，实现Wi-Fi无线信号全覆盖，定位主机设在第二展区内，用网线连接各AP至一台交换机，组成定位系统局域网。网格化参考点RP间隔为2 m，呈方格排列[11]，待测点为双向有源标签。具体平面布局如图4所示。
实验采用定位服务器配置：CPU为4核处理器，主频2.4 GHz以上，内存为8 GB以上，硬盘为256 GB以上。数据库服务器按以上标准另行配置。定位服务器软件运行环境为：操作系统为Windows 2003/2008 Server 32 bit，数据库为Microsoft SQL server 2005/2008，电子地图采用JPG格式。定位服务器软件实现与定位器（AP）和标签（Tag）之间的指令，以及相关数据的交互。根据标签发往AP的回传信号数据，由定位算法分析标签（测试点）与预存信息（参考点）的匹配关系，估算出标签的实际位置。AP定位器主要指标为：2.4 GHz，IEEE802.11b/g，最高速率为54 Mb/s，天线增益2 dBi，同时扫描标签128个/s。胸卡式标签：2.4 GHz，速率为1 Mb/s，双向通信，最大发射功率为20 dBm，发射间隔为1 s，48 bit唯一ID号。
3.2 实验结果
在定位实验区，当处于离线训练学习阶段时，在地面打好256个网格化参考点位（即网格的交叉点上），用胸卡式标签采集及回传无线信号，由主机定位服务器进行处理与存储。当在线定位阶段，采用人员配带胸卡标签的方式进行测试，具体人数为25人，胸卡式标签为200只。为了评估本文算法与KNN算法性能的优劣，收集标签数量与平均定位误差比较图。采样点数据是通过电子地图上显示待测点位置与实际标签位置的比较计算得到的，每个点位采样为20次，取平均值，获得平均定位误差数据。在采样过程中，忽略了因人员走动时信号漂移等现象引起的明显误差。模糊聚类算法（改进算法）与KNN算法比较如图5所示，可知改进算法的定位精度有比较明显的改善，大约提高了5%左右。
在KNN定位算法的基础上，通过本算法可以有效地克服KNN运算中丢失位置信息的不足，从而提高定位算法的定位精度。实验表明，当室内人员较多且人员快速移动时，还会出现无线信号的漂移和时延显示等现象；这一类信号传输问题有待于今后进一步优化定位算法，实现能自适应物理环境变化的定位算法。
参考文献
[1] 唐文胜，李姗，匡旺秋.RF室内定位指纹库空间相关生成算法[J].计算机工程与应用，2008，44（23）：226-229.
[2] 卢恒惠，刘兴川，张超，等.基于三角形与位置指纹识别算法的WiFi定位比较[J].移动通信，2010（10）：72-76.
[3] 汤丽，徐玉滨，周牧，等.基于K近邻算法的WLAN室内定位技术研究[J].计算机科学，2009，36（4B）：54-55，92.
[4] 刘兴川，林孝康.基于聚类的快速Wi-Fi定位算法[J].计算机工程，2011，37（8）：285-287.
[5] 李文杰，李文明.基于K-近邻算法的定位方法设计和仿真[J].计算机仿真，2009，26（4）：194-196.
[6] 潘玉奇，周劲，杨秀丽.基于模糊聚类分析的数据检索的应用[J].微电子学与计算机，2005，22（6）：167-172.
[7] Zhou Mu， Xu Yubin， Ma Lin. Radio-map establishment based on Fuzzy clustering for WLAN hybrid KNN/ANN indoor positioning[J]. China Communications，2010（7）：64-79.
[8] Yang Qiang， PAN S J， ZHENG V W. Estimating location using Wi-Fi[J]. IEEE Intelligent Systems， 2008，23（1）：8-13.
[9] 戴立伟，李向阳，程赟.无线传感器网络的RSSI定位技术研究[J].计算机工程与设计，2009，30（19）：4395-4397.
[10] TRAN Q， TANTRA J W， FOH C H， et al. Wireless indoor positioning system with enhanced nearest neighbors in signal space algorithm[C]. IEEE 64th Vehicular Technology Conference，2006：1-5.
[11] 李昊.位置指纹定位技术[J].山西电子技术，2007（5）：84-87.