| 标题 | 基于信号幅值分布的室内指纹定位算法 |
| 范文 | 丁承君 宇中强 朱志辉 摘 ?要： 室内定位算法是基于位置服务领域研究的难点之一。针对室内定位应用场合和精度问题，提出了利用K?means和KNN融合算法对覆盖率广的WiFi信号进行指纹定位。WiFi指纹定位主要问题是前期指纹库数据的精确以及后期数据的匹配效果。首先，对WiFi信号的概率分布进行研究，弥补了一直以来由于K?means是无监督学习带来的k值的难以选取的缺陷，提高了指纹库的精确性，同时确保数据实时性。后期在线数据处理利用KNN分类算法进行后期在线定位过程的准确性。经多个实验场景测试结果表明，该算法在室内定位精度上3 m定位精度概率保持在78.4%，4 m精度保持在93.6%，基本上保证了室内定位精度的要求。 关键词： 信号幅值; 指纹定位; 概率分布; K?means; KNN分类算法; WiFi信号 中图分类号： TN911?34; TP393 ? ? ? ? ? ? ? ?文献标识码： A ? ? ? ? ? ? ? ? ? ? ?文章编号： 1004?373X（2018）10?0039?04 Abstract： Indoor positioning algorithm is one of difficulties in location?based service field research. In allusion to the application scene and precision problems of indoor positioning， the view that using the K?means and KNN fusion algorithm to perform fingerprint positioning for wide?coverage WiFi signals is proposed. The main problems of WiFi fingerprint positioning lie in the data accuracy of the front?stage fingerprint database and the matching effect of late?stage data. The probability distribution of WiFi signals is studied to make up the defect that it is difficult to select the k value as K?means is an unsupervised learning for a long time， which can improve the accuracy of the fingerprint database， and meanwhile ensure the real?time performance of data. During the process of late?stage online data processing， the KNN classification algorithm is adopted to obtain the accuracy of the late?stage online positioning. The algorithm was tested in multiple experimental scenes. The results show that the 3 m positioning accuracy probability of the algorithm remains 78.4% in indoor positioning accuracy， and the 4 m positioning accuracy probability remains 93.6%， which can basically ensure the accuracy requirement of indoor positioning. Keywords： signal amplitude; fingerprint positioning; probability distribution; K?means; KNN classification algorithm; WiFi signal0 ?引 ?言 基于位置服务（Location Based Services，LBS）的其中一项内容是室内定位。由于室内布局和临时遮挡物的因素会造成信号不稳定，所以对于定位精度，室内定位较之于室外定位难度大[1]。现阶段国内外基于室内定位采取的技术手段中WiFi为最佳选择[2]。原因是成本低、覆盖范围广、精度高，用户的移动接收设备可直接用于定位，已覆盖WiFi的室内场所无需铺设其他硬件设备，可移植扩展[3]。定位方法有两种：一种是基于无线信号强度传播模型，将信号的幅值与距离进行公式化建模，例如经典的对数距离模型[4]，然而在室内遮挡物较多且容易移动，模型会因无线信号受遮挡物影响衰减而变得不准确;另一种是基于位置?指纹进行定位。相比较来说，指纹定位会有更好的表现[5]。 本文重点分析了WiFi信号的概率分布，并获得了WiFi信号幅值的概率分布情况。使用K?means联合KNN算法，在提高了指纹库的准确性的同时，减少了计算量，增加了定位精度和稳定性[6]。通过办公室、实验楼、家庭住宅等多个平面场所进行的实际测试得出定位精度提高到1～2 m范围内。1 ?WiFi指纹定位技术 WiFi定位指紋分为两个阶段：离线训练数据库阶段和在线定位阶段。离线训练是作者采集并处理信号，构建指纹数据库。在线定位阶段，是将检测到的WiFi强度值用匹配算法与指纹库里的数据进行在线匹配，得到最佳定位值。图1为指纹算法的流程图。 离线采集阶段：在坐标点采集WiFi幅值后，先进行预处理，目的是精确指纹库并且减少计算量;而后进行K?means聚类并入库;在线定位阶段通过后期采集的数据与指纹库数据进行KNN算法，加权求和后，得到定位位置。指纹库的准确性和在线匹配的稳定性是保证最终定位结果精度的关键，这也是本文所要重点研究的内容。 1.1 ?指纹定位技术分析 指纹定位技术可以分为两类：确定性技术和概率技术。确定性技术，例如KNN，KWNN，它们是对采样信号相关的k个近似值求均值或权值来定位[7]。概率技术在研究信号强度分布特性之后，进行最大似然估计。国外专家学者已经证明概率方法有更高的精度。但是不同的试验场景存在复杂性，WiFi信号强度分布在一些测试点会与标准高斯分布表现不同，其结果的准确性会影响概率方法的模型建立和参数的准确性。所以，本文依旧选用KNN算法。为了弥补使用KNN算法带来的精度损失，研究了WiFi信号的分布规律来增强前期指纹库的准确性。 1.2 ?WiFi信号的分布规律 WiFi幅值理论上服从高斯分布，具有一个波峰。但在实际探究固定位置采集单个信号分布情况，其幅值会在一定阈值内上下波动。笔者在一个月之内连续对上述三个场景内的多个WiFi信号进行长时间数据采集、归总，发现WiFi信号幅值发生的概率呈现单峰值或双峰值两种。图2为WiFi信号单峰值与双峰值显示。 进一步梳理采集到的数据，发现双峰出现的并非小概率事件，如表1所示，呈现双峰所占比例为20%～40%。可见，对于室内复杂环境这一分布特性应引起重视。 上面这些数据都是构成指纹库的必要准备。当然，采集更多的数据，指纹库必然更准确，然而这也会加大系统的运算量。2 ?聚类与指纹库的构建 指纹库是指纹定位方法的标尺，指纹库的准确性会直接影响最终定位结果的精度。 在离线数据采集阶段，采集每个采样点的位置坐标，同时在该坐标处采集接收到的RSS信号，将每个AP的坐标和RSS值按照一定的格式存储在指纹数据库中。 2.1 ?指纹框架的建立 离线数据库阶段，在采集点用一定的方法采集AP坐标和RSS信号，并绑定一起存储在指纹数据库里。假设第i次采集到的数据用集合[Mi]表示，则定义[8]： 2.3 ?生成指纹数据库的方法 预处理和K?means是两项高度相关的工作。预处理试图删除那些显著偏离多数的异常情况，而聚类则是发现集中数据并据此入库。 经过预处理，留下的数据具有一定的可信度。接着需要提取数据集的最佳参考值。在此采用聚类方法K?means，它是与某种规则进行聚类，分成k组，把相似度数据分到一组，分别提取最佳值[10]。 主要过程如下：样本有N个数据点，需要预知该样本的聚类中心有K个，选取k个采样点数据作为作为聚类中心，其余（N-K）个数据依照曼哈顿距离归为最相似的簇，重新计算这k个平均值，再把其余（N-K）个数据重新归位，计算均值。直到最后k个中心值保持在一定阈值之内，即该簇内的其他值距该中心点的曼哈顿距离收敛到最小值，如下所示： 使用K?means的难点是分类之前并不知需要分成几类。之前章节实验数据说明的信号幅值分布为单峰值或是双峰值，放到这里可解决k值的选取为1或2的问题。为了保证两种k值的情况，将预处理后的数据，先以k=2进行K?means聚类，若得到两个结果幅值差大于2，则说明该数据为双峰值，保留这两个数值入库;反之，若幅值差小于等于2，重新再以k=1进行聚类。对于双峰值来说，把概率较高值称为主幅值，即[RSSImain]，则另一个峰值副幅值表示为[RSSImain+Δ]。其中[Δ]=副幅值-主幅值。 对于入库，单峰值聚类结果直接写入即可。对于双峰值，为了区别于单峰值，表示为主幅值加差值[Δ]：[RSSI=RSSImain+Δ]。3 ?后期在线定位方法（KNN结合概率） 后期定位方法采用KNN。区别于K?means，它是一种已知指纹库数据的分类方法。其是把新的样本数据与已知库数据进行比对，寻找k个最相似数据，再对k个数据进行分类处理。同样，会遇到k值的选取问题。对于k值的选取，可以有以下几个备选值[11]。 由于开始将二维空间进行矩形划分，若定位到一点，周围会有相邻8个区域，把k设为8。还可以简化运算，设k=4。此外k=1时，选取欧氏距离相距最近的坐标。对于k=4，k=8这两种情况，分别选出距离最近的4组、8组数据。然而每组数据的距离不同，距离远，数据说明能力弱;反之则强。所以，采取距离倒数方法，分别作为其坐标的权值，再进行单位化归一，最后把几组值代入权值欧拉公式，得到最终定位结果。分别对k=1，k=4，k=8在选取的100个参考点进行试验，定位结果与指纹数据库值比对算出直线误差，求取平均值数据如下：k=1时，平均直线误差为5.28 m;k=4时，平均直线误差为4.42 m;k=8时，平均直线误差为4.63 m。 经分析如下：k=1时，定位结果的直线误差大于其他其余两个;k=4和k=8的定位误差相近，但由于k=8的计算量明显大过k=4。所以，对于本文KNN算法，选取k=4为最佳值。4 ?实验及分析 本文以教室、实验楼、办公室、商场四个不同场景为实验场景，进行室内定位研究。以实验楼二楼为典型的例子：长23 m、宽13 m的地方，有复杂的拐角、许多实验室的门与窗;实验楼有11个固定常开的WiFi信号分布在约[300 m2]的空间内;因为有拐角等复杂地形，分为90个方形区域，每个区域为2 m×2 m，靠墙和楼梯口略有减小。在离线训练阶段，每个AP采取1 000个样本训练指纹库，每个采样点的采样频率为1。实验结果结果如表2所示。 由表3可知，在4 m范围精度达到89.7%，3 m精度达到76.3%，5 m精度达到93.3%。在实验中，该方法的平均误差为4.83 m。5 ?结 ?语 室内定位中，在研究过WiFi分布规律后，去掉离群点数据，增强数据可靠性的同时，降低了数据量。结合K?means聚类算法构建指纹库、KNN后期定位算法，降低整体指纹算法的计算量，提高了系统实时性。在四个真实场景进行大量数据测试，分析了该算法的定位效果，数据结果表明，定位精度可以提高到4～5 m。参考文献 [1] 周傲英，杨彬，金澈清，等.基于位置的服务：架构与进展[J].计算机学报，2011，34（7）：1155?1171. ZHOU Aoying， YANG Bin， JIN Cheqing， et al. Location?based services： architecture and progress [J]. Chinese journal of computers， 2011， 34（7）： 1155?1171. [2] 席瑞，李玉军，侯孟书.室内定位方法综述[J].计算机科学，2016，43（4）：1?6. XI Rui， LI Yujun， HOU Mengshu. Survey on indoor localization [J]. Computer science， 2016， 43（4）： 1?6. [3] 陆音，缪辉辉.复杂室内环境下的WiFi定位技术研究[J].计算机科学，2016，43（11）：152?154. LU Yin， MIAO Huihui. Study on WiFi location technology under complex indoor environment [J]. Computer science， 2016， 43（11）： 152?154. [4] 江春冬，惠慧，陈云飞，等.与强度无关的位置指纹在线定位改进算法[J].电讯技术，2016，56（2）：128?134. JIANG Chundong， HUI Hui， CHEN Yunfei， et al. An improved online position fingerprint algorithm for strength?independent interference source location [J]. Telecommunication engineering， 2016， 56（2）： 128?134. [5] 蔡朝晖，夏溪，胡波，等.室内信号强度指纹定位算法改进[J].计算机科学，2014，41（11）：178?181. CAI Zhaohui， XIA Xi， HU Bo， et al. Improvements of indoor signal strength fingerprint location algorithm [J]. Computer science， 2014， 41（11）： 178?181. [6] 周瑞.应用室内结构布局提高WiFi定位精度和稳定性[J].电子科技大学学报，2013，42（2）：295?299. ZHOU Rui. Improve the accuracy and stability of WiFi fingerprinting by applying the interior structure of buildings [J]. Journal of University of Electronic Science and Technology of China， 2013， 42（2）： 295?299. [7] 赵宇，周文刚.基于智能手机的室内定位[J].计算机应用与软件，2015，32（6）：91?93. ZHAO Yu， ZHOU Wengang. Indoor localisation based on smartphone [J]. Computer applications and software， 2015， 32（6）： 91?93. [8] 唐洋，白勇，马跃，等.基于WiFi的指纹匹配算法在室内定位中的应用研究[J].计算机科学，2016，43（5）：73?75. TANG Yang， BAI Yong， MA Yue， et al. Research of WiFi?based fingerprinting matching algorithm in indoor positioning [J]. Computer science， 2016， 43（5）： 73?75. [9] 赵战营，成长生.基于聚类分析局部离群点挖掘改进算法的研究与实现[J].计算机应用与软件，2010，27（11）：255?258. （上接第42页） ZHAO Zhanying， CHENG Changsheng. On improved algorithm for local outlier mining based on cluster analysis and its implementation [J]. Computer applications and software， 2010， 27（11）： 255?258. [10] 华辉有，陈启买，刘海，等.一种融合K?means和KNN的网络入侵检测算法[J].计算机科学，2016，43（3）：158?162. HUA Huiyou， CHEN Qimai， LIU Hai， et al. Hybrid K?means with KNN for network intrusion detection algorithm [J]. Computer science， 2016， 43（3）： 158?162. [11] 刘春燕，王坚.基于几何聚类指纹库的约束KNN室内定位模型[J].武汉大学学报（信息科学版），2014，39（11）：1287?1292. LIU Chunyan， WANG Jian. A constrained KNN indoor positioning model based on a geometric clustering fingerprinting technique [J]. Geomatics and information science of Wuhan University， 2014， 39（11）： 1287?1292. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。