《电子技术应用》
您所在的位置:首页 > 测试测量 > 设计应用 > 改进指纹库精度下的室内定位算法研究
改进指纹库精度下的室内定位算法研究
2018年电子技术应用第10期
王培良1,2,张 婷3,肖英杰1
1.上海海事大学 商船学院,航运仿真技术教育部工程研究中心,上海201306; 2.潍坊科技学院,山东 潍坊262700;3.山东交通职业学院,山东 潍坊261206
摘要: 随着传感器网络的不断发展,基于位置服务逐步成为研究热点,其中的室内定位技术发展更为迅猛。为准确而快速地确定室内待测节点位置,通过对ZigBee无线网络的研究,提出在离线建库阶段使用基于离群点检测与双阈值滤波算法(频率阈值和均值阈值)处理采集到的不同接入点(Access Point, AP)的信号强度指示(Received Signal Strength Indication, RSSI),建立高精度指纹数据库,然后在线定位阶段,结合使用模糊C均值聚类(Fuzzy C-Means, FCM)和基于频率因子的加权K最邻近算法(Weighting K-Nearest Neighbor, WKNN)计算出待测节点的最终位置,并给出“备用位置”。结果表明,采用该研究方法建立的指纹库在精度上有较大提升,同时定位精度也显著提高。
中图分类号: TN914
文献标识码: A
DOI:10.16157/j.issn.0258-7998.180768
中文引用格式: 王培良,张婷,肖英杰. 改进指纹库精度下的室内定位算法研究[J].电子技术应用,2018,44(10):97-101,105.
英文引用格式: Wang Peiliang,Zhang Ting,Xiao Yingjie. Research on indoor positioning algorithm based on improved fingerprint library accuracy[J]. Application of Electronic Technique,2018,44(10):97-101,105.
Research on indoor positioning algorithm based on improved fingerprint library accuracy
Wang Peiliang1,2,Zhang Ting3,Xiao Yingjie1
1.Engineering Research Center of Simulation Technology of the Ministry of Education, Merchant Marine College,Shanghai Maritime University,Shanghai 201306,China; 2.Weifang University of Science and Technology,Weifang 262700,China; 3.Shandong Transport Vocational College,Weifang 261206,China
Abstract: With the continuous development of sensor networks, location-based services have gradually become the research hotspots, and indoor positioning technology is one of the most which are the fastest developing technology. In order to accurately and quickly position the location of indoor nodes to be measured, this research based on ZigBee wireless network proposes to use the algorithm based on outlier detection and double threshold filtering (frequency threshold and mean threshold) to process the RSSI data ,which are from different access points(APs), to establishes a high-precision fingerprint database. Then the final position of the node to be measured is calculated by using fuzzy C-Means(FCM) and the weighted K-nearest neighbor(WKNN) algorithm based on the frequency factor, and the“spare location” is also obtained. The result shows that the fingerprint database established by this research method has a great improvement in accuracy and the positioning accuracy has also been significantly improved.
Key words : indoor positioning;ZigBee wireless network;fuzzy c-means;weighted k-nearest neighbor

0 引言

    随着无线传感器网络(WSN)技术的不断发展,基于位置感知的服务和计算在实际中得到广泛使用。目前,室内定位技术主要有:超声波[1]、红外线、RFID[2]、WiFi、UWB[3]等技术。本文使用成本低、功耗低、复杂度低的德州仪器公司CC2530芯片基于ZigBee协议进行研究,通过节点间的接收信号强度指示(Received Signal Strength Indication,RSSI)值进行室内定位。依据定位算法过程中是否使用节点间距离,定位方式分为基于测距和非测距方式两种,本文使用的指纹数据库即为非测距方式。

    指纹数据库定位需经历两个阶段:离线建库阶段和在线定位阶段[4-5],其原理如图1所示。在离线建库阶段,通过采集预设定的接入点(Access Point,AP)与各参考节点(Reference Point,RP)之间的RSSI值来建立原始指纹库[6-8]。文献[9]通过使用K-Means聚类算法,实现众包指纹库建模。本文在采集原始数据的基础上,通过离群点检测发现其与大部分数据存在显著差别的数据对象,将其视为噪声而丢弃,然后使用双阈值滤波处理得到最终的高精度指纹数据库。

ck5-t1.gif

    在线定位阶段,通过将实时采集到的待测点RSSI值与指纹数据库中的数据集进行比对,计算得到待测节点的位置坐标。广泛使用的典型定位算法主要包括核函数法、最近邻法、最大似然概率法以及朴素贝叶斯法。文献[10]-[12]通过研究提出增强型的聚类策略、权值算法以及优化质心等,可显著提升定位速度和精度。上述研究方法通常易受待测点RSSI值波动的影响,同时在计算速度和精度上难以满足要求。本文通过使用FCM算法将待测节点的RSSI值进行聚类,从而剔除跳变点,然后使用基于频率因子的加权K最邻近算法(Weighting K-Nearest Neighbor,WKNN),计算得到待测点的位置,并且给出“备用位置”。

1 理论与方法

1.1 离线建库阶段

    高精度指纹数据库的建立是提高定位准确度的前提条件[13]。由于在AP点进行信息采集时,其数据存在大量噪声影响指纹库的精度,因此本文使用下述方法提高建库精度。

    假定定位区域网格化后有m个AP和n个RP,其分别记为集合{AP1,AP2,…,APm}、{RP1,RP2,…,RPn},其中m值亦为每个AP点的标签,且每个AP接收到s组数据,记为:

ck5-gs1.gif

1.1.1 离群点检测方法

    本文首先使用基于聚类分析的离群点检测算法将原始数据中噪声去除,其步骤:

    (1)选择合适的聚类算法对RSSIn进行聚类分析,本文使用K-Means算法。

    (2)计算RSSIn中各点与最近质心的欧式距离,公式为:

ck5-gs2.gif

其中,Z表示各类质心的坐标。

    (3)与给定的阈值η1进行比较,若Di1,则该RSSIi视为离群点,并将该点从源数据中剔除。

1.1.2 双阈值滤波方法

    在进行离群点检测时,某些离群点可能形成小簇从而逃避检测,因此需要使用双阈值滤波对其进一步处理。首先对数据进行数据频率阈值滤波,设频率阈值为:

ck5-gs3-5.gif

1.2 在线定位阶段

    为剔除待测节点RSSI值的噪声,同时为增大数据有效性,本文在在线定位阶段使用基于FCM与WKNN相结合的方法对数据进行处理。

1.2.1 FCM算法论述

ck5-gs6-8.gif

    具体过程如下:首先用加权指数m和分类数c初始化隶属度矩阵,然后重复迭代使用式(7)、式(8)求解聚类中心和新的隶属度矩阵并将结果待入式(6),直到Jm(U,V)小于给定的正数ε或者达到最大迭代步长,则聚类过程结束,得到待测节点数据集X={x1,x2,…,xi},其中i∈(1,l)表示聚类之后的数据量。

1.2.2 WKNN算法论述

    最邻近定位算法通过计算待测节点的RSSI实时测量值与指纹库中各对应指纹数据之间的欧式距离,从中搜寻距离最小的指纹点,然后将各个指纹数据通过平均或加权平均作为待测目标的位置。欧式距离计算公式如下:

ck5-gs9-10.gif

ck5-gs11-12.gif

其中,Ij表示距离最近的前K个AP节点所分别对应的标签值。

    为防止出现小概率性的错误定位问题,本文同时给出待测节点的“备用位置”作为参考。其原理为使用上述加权K最邻近定位算法迭代计算出与待测节点相近的多个节点并进行排序(其中Lc计算出的位置节点除外),选择前2~4位节点作为待测节点的方向估计,第1位节点作为待测节点的“备用位置”估计。

2 实验结果及分析

    本文选用信号干扰强、设备多、使用环境复杂的校园多媒体教室进行实验,选定其中20 m×20 m的为本次实验区域。

    在本实验的离线建库阶段,共设置100个AP节点,每个AP节点连续采集120 s的信号强度值数据,然后对本段时间内的数据进行处理从而建立指纹库。下面选取第4个AP节点数据进行分析,其原始数据如图2所示。

ck5-t2.gif

    为清晰表达算法处理过程,后续处理时以本节点的REF1参考节点数据值为对象,且RSSI值绘图时使用其绝对值表示。

2.1 指纹库建立

    首先对数据值进行离群点检测,其中设定离散点阈值为0.7,最大迭代次数设置为500,则处理结果如图3所示。

ck5-t3.gif

    从图3可知,距离误差超过阈值的所有点,均视为离群点,应从数据集中剔除,以免影响后续数据处理过程。

    离群点剔除后对数据集进行双阈值滤波处理,其结果如图4所示。

ck5-t4.gif

    分析图4可知,数据经过双阈值滤波后,能够进一步抑制噪声的干扰,并且可降低后续指纹数据库建立的复杂度。

    同理,将此AP点接收的其他REF数据进行上述处理,从而得到最终的该AP点对应于每个RP点的指纹数据,并建立数据库。

2.2 定位结果

    在实验区域内,共设置10个待测节点,每个节点连续采集信号时间亦均为120 s,现选取任意待测点数据进行分析,其原始数据如图5所示。

ck5-t5.gif

    在使用算法对待测节点数据进行分析前,需将其每次接收到的不同RP点的RSSI值进行统一化处理,并将其作为待测节点数据集中的一个观测值(行属性),其统计结果如图6所示。

ck5-t6.gif

    然后使用FCM算法对此数据集进行处理,其目标函数中隶属度幂指数为3,最大迭代次数为200,目标函数的终止容限位1×10-6。经反复试验,最终本文选用分类数为2,不同分类数结果如图7所示。

ck5-t7.gif

    对图7趋势分析可知,针对本次研究数据,当分类数为2时,处理效果优于其他分类数。

最后使用基于频率因子的WKNN算法对上述分类后的数据进行计算,得到待测节点位置,其定位误差为1.85 m,备用位置的定位误差为2.13 m。同理,可得其余待测节点的位置误差。通过对比本文研究方法与传统原始定位方法(未滤波指纹数据库定位和未优化FCM+WKNN定位算法),可明显看出其定位精度的提升,结果如表1所示。

ck5-b1.gif

3 结论

    本文首先通过离群点检测与双阈值滤波结合的方式对不同AP点采集的原始RSSI值数据进行处理,建立高精度指纹数据库,然后使用FCM算法对待测节点的RSSI值进行分类,最后使用WKNN算法计算出待测节点的位置信息。经过实验证明,本文的研究方法相比于未滤波数据库和未优化算法等方式,在定位精度上有明显提高,并能给出“备用位置”信息。

参考文献

[1] 叶宝玉,王钦若,熊建斌,等.基于超声波的模型船舶室内定位系统研究[J].计算机工程,2012,38(19):258-260,265.

[2] 马卜林,杨帆.煤矿井下WiFi人员定位GIS系统设计与实现[J].西安科技大学学报,2012,32(3):301-305.

[3] 肖竹,王勇超,田斌,等.超宽带定位研究与应用:回顾和展望[J].电子学报,2011,39(1):133-141.

[4] 张翔,熊剑,武和雷,等.基于MNN改进粒子滤波的指纹库定位算法研究[J].计算机工程与设计,2014,35(7):2283-2288.

[5] 方爽,郭杭,洪海斌,等.一种虚拟空间划分的室内指纹库定位方法[J].测绘科学,2015,40(1):93-97.

[6] 刘小康,郭杭.基于Zigbee室内定位系统的指纹库优化算法[J].计算机工程,2014,40(2):193-198.

[7] HOU Y,SUM G,FAN B.The indoor wireless location technology research based on WiFi[C].International Conference on Natural Computation.IEEE,2014:1044-1049.

[8] GUO S,ZHONG Z,HE T.FIND:faulty node detection for wireless sensor networks[C].ACM Conference on Embedded Networked Sensor Systems.ACM,2009:253-266.

[9] ZHOU M,TIAN Z,XU K,et al.SCaNME: Location tracking system in large-scale campus Wi-Fi environment using unlabeled mobility map[J].Expert Systems with Applications,2014,41(7):3429-3443.

[10] 霍欢,杨沪沪,郑德原,等.一种改进的RSSI指纹库定位算法[J].计算机应用研究,2017,34(9):2786-2790.

[11] 戴国华,易灵芝,王根平.一种新的基于ZigBee技术定位算法[J].计算机测量与控制,2012,20(4):1105-1107.

[12] 赵山,彭力.基于ZigBee网络的移动节点定位技术研究[J].测控技术,2014,33(10):51-55.

[13] 王顶,马娟,赵颐轩.基于RSS空时处理的指纹定位算法[J].计算机应用研究,2012,29(12):4726-4728.



作者信息:

王培良1,2,张  婷3,肖英杰1

(1.上海海事大学 商船学院,航运仿真技术教育部工程研究中心,上海201306;

2.潍坊科技学院,山东 潍坊262700;3.山东交通职业学院,山东 潍坊261206)