一种基于层次聚类的快速楼层判别算法

室内定位技术可以实现室内定位, 但是现如今大部分是针对二维平面内的定位算法进行研究, 然而有些情况下需要知道目标所在楼层[1]。例如:商场内人流量大, 小孩容易丢失, 追踪小孩只知道其二维位置是不够的, 还需要知道其具体楼层;在医院对医疗物品进行定位, 医院仪器被多人使用, 未被放回原位, 当需要使用时难以找到, 利用定位, 可方便寻找等。

Firas Alsehly等[2]提出1、最近楼层判别算法, 在离线阶段通过记录每个参考点信号最大AP (无线信号发射器) 编号以及该参考点所在楼层号, 通过对比, 选择与测量信号最接近的点的楼层作为结果。2、群方差算法, 统计每层楼的无线信号的范围、方差、可用性与接收的信号进行概率比对, 来判断楼层;自所有标记AP的信号值, 计算置信区间从而判别楼层。但上述方法在楼层判别中存在相应的缺陷, 并且判别精度都不是很理想。据此, 提出了一种基于层次聚类的楼层判别方法, 并与最近楼层算法和群方差算法进行了对比, 进一步提高了楼层判别效率。

一、基于层次聚类的多楼层定位算法

利用WiFi进行室内定位一般都需要两个步骤[3]:1、在离线阶段, 将待定位区域进行均匀划分, 将部署的WLAN信号网络中的AP (无线信号发射器) 进行编号, 在均匀划分的地点进行信号采集, 采集信号为来自各个AP的信号强度值, 然后存储。2、在在线阶段, 根据用户实时采集的无线信号值与存储的数据利用相应的匹配算法进行匹配, 将最相似的信号所在地作为用户的最终坐标。

在离线阶段通过对每一层定位区域进行均匀划分, 然后在每一层每个参考点分别进行信号采集, 将每个层单独聚类, 通过计算每个参考点之间的欧氏距离按照层次聚类的聚类法则进行聚类, 最终将每层定位区域划分为多个聚类, 并计算出每个类的质心信号强度以及楼层号进行存储, 质心信号计算如下所示:, k表示该类中元素的个数, RSSIin表示在i位置接收来自APn的信号值, 进行楼层判别时候根据实时采集的信号与每个类的质心进行欧氏距离的计算, 选取欧式距离最小的质心所在的类的楼层作为最终判别, 即可得到楼层号。

二、仿真验证

为了显示该算法的楼层判别性能, 本文在贵州大学教学楼区域进行了实验, 实验区域为该学院楼的第二层F2, 第三层F3, 第四层F4。利用该楼部署好的无线网络进行数据的采集, AP具体位置未知。为了得到最好的分类效果, 在聚类的过程中选取了不同的阈值T进行对比, 同时将采集的实时定位数据输入进行实验。

最终根据实验结果得出T=9为最优阈值, 当T>9精度开始降低, 从定位平均时间上看, 选取的阈值越小, 每层所划分的聚类数越多, 匹配所计算的数值越大, 导致时间会不断加大, 综合考虑精度和时间, 此次实验中, 选取T为9, 即当类聚类距离为9时, 停止聚类。

测试楼层判别效果时候, 实验者匀速走在定位区域, 并进行多次采集, 输入程序中进行多次判别与最近楼层算法和群方差算法对比正确率。

经过对比可以看到本文提出的方法较其他两种方法精度有很大提升, 并且从定位时间上来看, 最近楼层算法需要匹配每个元素, 所耗时间最长, 群方差算法虽然消耗时间和层次聚类方法差不多, 但是其精度过低所以效果较差, 综合考虑本文提出的层次聚类算法可以有效的判别楼层号。

三、结论

为了提高楼层判别正确率, 以及提高楼层判别速度, 本文提出了一种基于层次聚类中均值距离的聚类方法, 通过计算每类质心所包含的无线信号强度与实时信号强度的欧氏距离大小, 选取距离最近的类所在的楼层作为最终判定结果, 经过在相关区域进行实验, 验证了方法的可行性, 并与最近楼层算法和群方差算法进行比较, 结果显示, 本文方法可以在一定程度上提高楼层判别准确率。

通过楼层信号的判别我们可以在大楼灾难救援, 寻找丢失人群, 根据楼层提供相应信息等作用, 接下来在判别楼层的基础上对人员的具体位置进行判别研究, 优化定位算法。

摘要：在WiFi指纹室内定位中, 楼层判别可以有效降低位置指纹搜索空间, 提高速度和精度。现如今, 大部分的判别楼层的方法是利用特殊的硬件设施, 或者特定的传感器组合, 这些方法加大了成本, 而其他的方法虽然不利用额外的硬件, 但是方法的时效性不好, 消耗的时间多, 效率低下。因此, 本文提出了一种改进的使用层次聚类的算法用来提高判别楼层的效率, 该方法不需要额外的硬件设施或者传感器, 仅仅利用接收到的无线信号强度即可实现楼层判别, 同时提高了楼层判别效率和准确率。

关键词：室内定位,楼层判别,无线信号强度,数据挖掘,层次聚类

参考文献

[1] .孙永亮.基于位置指纹的WLAN室内定位技术研究.哈尔滨:哈尔滨工业大学电子与信息工程学院, 2013.

[2] . Alsehly F, Arslan T, Sevak Z. Indoor positioning with floor determination in multi story buildings//Indoor Positioning and Indoor Navigation (IPIN) , 2011 International Conference on. IEEE, 2011:1-7.

[3] .陈黎飞, 姜青山, 王声瑞.基于层次划分的最佳聚类数确定方法.软件学报, 2008, 19 (1) :62-72.