基于改进型KNN算法和Android平台的室内定位技术研究
微信号：guoguoma2727扫码免费领取用友软件使用权
复制微信号
基于改进型KNN算法和Android平台的室内定位技术研究
摘 要：通过分析基于WiFi定位的传统位置指纹算法的不足之处，文中提出了一种旨在提高精度并减小计算复杂度的改进型KNN算法。通过Android平台对该算法进行实现和测试，分析比较K的取值、AP的位置及数量等因素对定位精度的影响。测试结果表明，该算法不但能够保证位置指纹室内定位的精度，还能有效减小计算复杂度，具有一定的可行性。 关键词：精度；计算复杂度；改进型KNN算法；Android平台 中图分类号：TP301；TN92 文献标识码：A 文章编号：2095--00-05 0 引 言 伴随着互联网应用的快速发展，人们在室内停留的时间越来越多，室内位置信息对人们的日常生活愈加重要，因此人们对室内定位有着愈发强烈的需求[1-3]。由于利用GPS和AGPS这两种定位方式进行室内定位时，信号会受到各种障碍物的遮挡[4]，因此亟待出现新型的室内定位方式。 随着无线局域网络遍布各地，智能手机和平板电脑等个人电子设备发展迅速，这些设备几乎都使用WiFi连接网络，用户可使用WiFi?M行定位[5-7]。iOS，Android和WP是目前三大主流移动操作系统。其中，Android系统所占的市场份额日益增大，因此完全可以选择Android系统作为载体，设计基于WiFi的室内定位系统[8-11]。本文基于Android平台设计了一种基于改进的位置指纹算法，首先收集采样点的信号强度值信息，并将其保存到数据库中，然后将定位时的数据和数据库相互对比进行估算，得到所要定位的坐标信息。 1 基于WiFi的室内定位技术简介 虽然目前实现WiFi室内定位的方法有很多，但主要使用基于测距的定位方法。其中基于RSSI的定位方法最受关注[12-16]。基于RSSI的定位算法流程如图1所示。 2 传统位置指纹定位技术 目前，在研究基于WiFi的室内定位时，位置指纹定位技术使用较多[17-21]，受到了广泛关注。 技术原理 基于位置指纹定位算法的原理图如图2所示。 从图2可以看出，位置指纹定位算法主要包括离线工作阶段和在线工作阶段。离线阶段即数据收集阶段，首先选择一个区域，从中选取多个采样点，然后收集这些点WiFi信号的强度值RSSI，并将其作为位置指纹保存到指纹数据库中。在这个指纹数据库中，每个指纹都由一组RSSI值组成，且对应一个位置坐标。在线阶段即定位阶段，将待测目标定位的信息与指纹库进行匹配，最后估算出当前位置坐标，完成定位[22]。在WiFi环境下，使用位置指纹定位算法RSSI定位工作过程如图3所示。 在选取的定位区域中，l个采样点可以收集n个RSSI值来表示一个指纹，遍历所有采样点并获得各自的RSSI值，保存于指纹库中。指纹库内容如式所示： 其中：RSSIji表示在第i个采样点所测的WiFi信号的第j个RSSI值；FPi=表示任意一个位置的指纹数据，同时该指纹数据也可用坐标表示。因此，指纹数据与坐标相互对应，其坐标如式所示： 位置指纹数据库由式和式共同组成。 除了在离线阶段创建一个比较准确的指纹数据库，在线阶段指纹库的匹配算法也十分重要[23]。常用的匹配算法有最近邻法、K近邻法和加权K近邻法。 最近邻算法 最近邻算法是一种比较常用的匹配算法，当待测目标进入定位所选区域时，可获得一个相关的指纹信息lf=，然后将这个指纹信息与指纹数据库中的信息相匹配，再算出它们之间的距离，其距离如式所示[24，25]，其中距离最小也就是相似度最大指纹信息min)，即待测目标的位置。 式中：RSSIj和RSSIji分别为定位点和指纹点的强度值；n是WiFi信号的个数。 最近邻算法操作十分简单，且容易实现，但是其可选择的参考点较为单一，定位时容易产生误差，精度不高。 K近邻算法 相较于最近邻算法，K近邻算法可选择的参考点有所增多。匹配待测目标的指纹信息，并找出与指纹数据库中最近邻的K个指纹信息，通过计算坐标的平均值就可以估算出待测目标的位置，其位置如式所示[26，27]： 式中：是被选择的第i个指纹数据库中的信息所对应的坐标。 加权K 近邻法 加权K近邻法是对K近邻法的一种改进。K近邻法选取的K个最小距离对最后的定位结果贡献相同，取平均值，但距离越小对定位结果坐标的贡献越大。因此，对所取的K个最小距离进行权值分配，距离越小，权值越大。K个权值ωk之和为1。ωk可自行设定，也可由式计算得出[28，29]： 技术性能与存在的问题 当前的位置指纹算法虽然可以实现室内定位，但该算法依然存在一些问题，主要体现在以下方面： 算法模型过于简单，仅能满足较为简单的室内环境的定位要求。当室内环境较为复杂，如家具等陈设较多、