0 引言

位置指纹定位^[1]是目前室内定位中应用较多的定位方式，其在线定位阶段中检测值与数据库快速匹配决定了定位效率，而聚类算法^[2]能降低大量数据的维度，减少匹配计算量，故使用较多。

文献[3]采用K-means聚类的方法对KNN方法进行改进，该方法利用K-means聚类对初始点邻域进行筛选，用算法减小了奇异点对于计算的影响，但是其定位效率不高。文献[4]提出应用K-means聚类的方法对指纹空间进行聚类，将整个解空间分为若干子空间。该方法降低了匹配工作的计算量，但不能保证聚类算法得到最优解。而且以上两种K-means聚类算法都是被动依托于环境中AP的条件，存在聚类结果受初始值的影响较大和极易陷入局部最值的问题。待测环境中AP数量多，即可用算法去筛选最优点，滤除极差点；若环境中AP数量较少，以上方法则差强人意。

试验中发现AP位置布局变化会对定位精度产生较大影响，而关于这方面的研究极少。本文提出一种AP主动布局优化方法，在不增加AP数量条件下由改进的K-means聚类算法提高定位系统整体性能和定位精度。

1 室内定位AP部署优化模型

1.1 部署优化的目标函数

空间中无线电传播损耗^[5]模型一般用下式表示：

其中，s、t为定位空间的边界长度。

1.2 计算步骤

单纯形法(Simplex Method，SM)^[6]进行寻优计算的理论较为完善，但在室内指纹定位研究中涉及文献较少。在传统单纯形法迭代计算过程中，对初始三角形进行拉伸、收缩、对称等计算操作，剔除模型中残差最大的顶点，补充一个新的顶点构建新的三角形，不断重复这个寻找过程，当目标函数值满足约束条件时，对通过迭代计算得到的三角形选取残差最小的点即最佳逼近解。

模拟退火（Simulated Annealing，SA）^[7]算法是一种模拟物理降温过程的优化算法，其核心思想是：较高初温时粒子能量较高，渐进冷却时粒子渐趋有序，最后在常温时粒子达到最终稳定状态。模拟退火算法主要由解空间、目标函数和初始解3部分组成。

模拟退火算法对于全局控制稳定但收敛慢，单纯形法计算速度快，但极易局部最优，两者优势互补。单纯形-模拟退火（SMSA）融合算法的思路是先利用单纯形算法搜索到局部最小值，然后利用模拟退火算法的突跳性使它能跳出局部极小值，搜索是否有单纯形新的局部最小极值，若有以该点替代初值继续搜索，伴随退温操作通过循环而趋近于全局最优解。计算步骤如下：

2 改进K-means聚类算法

传统K-means聚类算法^[8]随机产生K个子类的中心，根据与各子类中心的距离将剩余的每个对象划分到距离最短的子类中，然后重新计算每个子类中所有对象的平均值并将其作为新的聚类中心，不断重复操作，直到误差平方和函数收敛为止。传统方法缺点是计算量大、效率低，有可能得到局部最优解，原因在于初始聚类中心的选择，当聚类中心接近空间数据分布稠密区间点时，定位效率高、运算时间短，但空间数据分布稀疏时效果差。

研究中对于聚类算法的初始聚类中心加以改进设置，不是随机选取，而以部署优化后的AP为初始中心，以测试点到AP的欧式距离作为目标函数来聚类，聚类过程中舍弃奇异点。优化部署AP时的目标函数本质是距离误差达到最小，因此选取离AP最近坐标对应的RSS信号特征向量对数据库进行聚类效率最高。

改进K-means 聚类算法步骤如下：

(1)Offline采集阶段

Input：信号采样数据集X={X₁，X₂，…，X_n}

Output：s个类C_n(1≤s≤n)

①初始化程序中的聚类参数，规划聚类数k(21，h₂，…，h_k，设置迭代门限条件为均方差最小或者迭代次数达到阈值。

②计算X_p(p=1，2，…，n)与各初始类中心坐标的欧式距离dij，求均值降序排序，并将每个排序点分配到最近邻的类中心的子类中。

③计算子类中所有参考点之间欧式距离和，选取最小值对应的点作为新的聚类中心。

④迭代停止条件判断：若不满足最小平均方差或者未达迭代门限条件，返回执行步骤②，用新聚类中心重新聚类；否则，终止程序。

(2)Online定位阶段

Input：目标信号采样样本点数据X_rssi

Output：比对输出位置坐标值

①计算定位目标X_rssi与各聚类中心的欧式距离d_rssi，则区分目标点所属子类。

②计算X_rssi与类目中心的欧式距离，用KNN法匹配出目标点的位置坐标值并输出运算结果。

3 实验结果与分析

3.1 实验平台

由美国Signal Hound公司的SA44B型频谱仪测量接收机和Intel公司的Minnow Board Turbott嵌入式微系统组成信号采集处理模块，其中USB端口连接Tenda的W311MA型无线网卡，与其他采集模块AP节点一起组成无线传感器网络。经由JCG的JHR-N926R型无线路由器将采集到的数据发送至联想ThinkPad E440笔记本电脑服务器上。

为验证AP位置优化算法的有效性，实验在实验楼10 m×13 m的空旷教室中进行，如图1所示，以0.8 m间距设置参考坐标点间距（这是地砖的尺寸，以便测量），位置点依次设置为A、B、C、D，文献[9]验证了较小定位空间内选用4个AP时性价比最高，故选用4个AP，各AP初始坐标为A(2.0，2.0)，B(2.0，8.0)，C(6.6，8.0)，D(6.6，2.0)，并组成矩形阵列。

信号源采用USPRB200型发生器，其中心频率可设置为70 MHz～6 GHz。发射源频率调制为840 MHz来模拟手机干扰源频率，信号功率为15 dB，信号源的万向天线与支架的中心轴线重合，支架平面距地面0.5 m，较低的信号源高度可以减少地面的反射波的测量扰动，以每间隔1 m选取参考坐标进行指纹信息数据采集，支架中心轴对准参考点标记，采集时间为15 s，采集期间人员手机关闭以净化电波环境，降低外界干扰。离线阶段共采集参考位置40个，每个指纹位置采集3次，其中排除靠近建筑拐角和堆积杂物的区域，以及与AP太近和重合的参考位置。

3.2 实验及误差分析

对定位环境中的指纹点和参考点依次进行数据采集，并将初始坐标进行单纯形法位置优化，优化后的位置坐标为A1(3.8，0.4)，B1(11.3，1.9)，C1(1.9，9.6)，D1(7.8，12.3)，将接收机放置于优化后的新坐标点上，如图2所示，采用K-means聚类算法进行定位。根据文献[10]的验证结论，当K=3时对目标的定位精度相对最高，因此本文定位算法的参数K设置为3。

从图3可知，应用SMSA算法优化后的测试点平均定位误差均略有下降，当进行AP位置优化后定位精度也明显提高了很多，K-means平均定位误差为1.5 m时的概率达到68%，比优化前提高了13.8%。同时经过SMSA算法优化后的K-means聚类算法的运算效率明显提升，如图4所示，由于以布局优化后AP坐标作为初始聚类中心，初始聚类运算速度很快，经过布局优化的改进K-means聚类算法的总耗时为55.23 s，比优化前减少了13.26 s，其室内定位结果达到定位要求。

4 结论

本文采用先进的嵌入式和频谱接收机建立了室内定位系统，利用SMSA融合算法对室内定位模型进行了寻优计算，确定了室内环境的最优化布局。实验证明，本文提出的室内AP主动布局优化方法和改进的K-means聚类算法合理利用了AP资源，提高了定位精度。如何实现对室内环境复杂和人员流动较密集区域的AP部署优化以及对动态目标的准确定位，还需要在今后实验中去验证。

参考文献

[1] 邓中亮.室内定位现状与发展趋势研究[J].中国通信，2013，10(3)：42-55.

[2] 何海平，郭杭，方爽.基于模糊聚类的ZigBee室内定位系统设计[J].电子技术应用，2016，42(5)：71-73，77.

[3] 崔斌，赵西安.一种基于传播模型和位置指纹的混合室内定位方法[J].测绘通报，2015，43(6)：35-38 .

[4] 都伊林．一种模糊聚类KNN位置指纹定位算法[J].微型机与应用，2012，31(23)：55-58.

[5] 孙凤，施伟斌，黄灵凤.基于无线传感器网络的室内定位技术的研究[J].电子技术应用，2013，39(10)：80-83.

[6] 李健，高永涛，谢玉玲，等.基于无需测速的单纯形法微地震定位改进研究[J].岩石力学与工程学报，2014，33(7)：1336-1346.

[7] 刘彦隆，吕显朋，王相国.混合遗传算法在WSNs定位中的应用[J].传感器与微系统，2014，33(2)：150-153.

[8] 陈空，宋春雷，陈家斌.基于改进WKNN的位置指纹室内定位算法[J].导航定位与授时，2016，3(4)：58-64.

[9] 周牧，蒲巧林，田增山.室内WLAN定位中位置指纹优化的接入点部署方法[J].通信学报，2015，36(Z1)：30-41.

[10] 陈望，贾振红，覃锡忠，等.基于改进K-means聚类算法的室内WLAN定位研究[J].激光杂志，2014，39(7)：11-14.

作者信息:

陈云飞1，2，杜太行1，3，江春冬1，3，王景玉1，李娟妹1

（1.河北工业大学 控制科学与工程学院，天津300130；2.邢台职业技术学院 电气工程系，河北 邢台054000；

3.河北省控制工程研究中心，天津300130）