《电子技术应用》
您所在的位置:首页 > 嵌入式技术 > 设计应用 > 基于Android平台改进的室内WiFi定位算法的研究
基于Android平台改进的室内WiFi定位算法的研究
2017年电子技术应用第3期
武 一,张冀钊
河北工业大学 电子信息工程学院,天津300400
摘要: 基于Android手机平台设计并实现了WiFi室内定位系统。该系统采用指纹定位算法,通过手机采集室内WiFi信息并建立数据库,当用户发出定位请求时,手机将扫描到的WiFi信息发送给数据库,通过匹配算法进行位置定位。通过对采集后的数据进行加权以及对数据库数据进行预先处理,降低了运算量,同时去除了较小的信号强度的干扰。实验表明,与传统算法相比,该系统定位精度大大增加。
中图分类号: TN92
文献标识码: A
DOI:10.16157/j.issn.0258-7998.2017.03.019
中文引用格式: 武一,张冀钊. 基于Android平台改进的室内WiFi定位算法的研究[J].电子技术应用,2017,43(3):77-79.
英文引用格式: Wu Yi ,Zhang Jizhao. Research of improved indoor WiFi localization algorithm based on Android platform[J].Application of Electronic Technique,2017,43(3):77-79.
Research of improved indoor WiFi localization algorithm based on Android platform
Wu Yi,Zhang Jizhao
School of Electronic and Information Engineering,Hebei University of Technology,Tianjin 300400,China
Abstract: This article designed and implemented the WiFi indoor positioning system on the Android mobile phone platform. The system uses fingerprint positioning algorithm,collects indoor WiFi information through the mobile phone and establishes the database. When a user sends a location request, mobile phone will scan the WiFi information,send them to the database,and do location based on matching algorithm. The positioning accuracy is improved by weighting to the collected data. In advance,the data in database is processed. It reduces the amount of computation, and at the same time removes the interference of the signal strength of the smaller. The experimental results show that the positioning accuracy of the system is greatly increased compared with the traditional algorithm.
Key words : indoor positioning;WiFi;Android platform;fingerprint algorithm;improved algorithm

0 引言

    随着通信技术和智能科技的不断发展,定位技术在日常生活中发挥着越来越大的作用,人们对定位服务的需求逐渐增大。室外定位GPS以及基站定位技术已经发展成熟,出现了多种室内定位技术,如:RFID(射频识别)、WiFi、蓝牙、红外线等。定位方法有基于到达时间(TOA)、基于信号强度(RSS)、基于到达角度(AOA)的方法[1],还有一些通过加速度传感器等手机内的集成传感器件来实现定位[2]。现阶段,智能手机相当普及,WiFi也基本覆盖大多数公共场所,WiFi定位无需额外的硬件需求,具有低成本、低功耗、高精度等特点,因此其在众多定位方法中具有很大的优势。

    本文通过扫描室内的WiFi信息,在Android平台上通过改进的指纹匹配定位方法实现室内定位。

1 WiFi位置指纹定位方法

1.1 指纹定位方法

    基于WiFi无线网络的定位技术有很多,其中以基于信号强度RSS的定位技术最为常用[4]。在基于RSS的定位技术中位置指纹定位方法较为普遍。位置指纹定位方法[5]分为数据采集阶段和实时定位阶段两部分。在数据采集阶段,在区域内均匀地选择N个数据采集点,在每个采集点,通过安卓手机采集所有AP的RSS信息,并将所有RSS信息以及该点的坐标(x,y)存入数据库[6],等待第二阶段调用。在实时定位阶段,用户在未知位置发出定位请求,安卓手机采集该点AP的RSS信息并传送至数据库,通过匹配算法以及第一阶段采集的RSS数据得到位置坐标(x,y)反馈给用户,定位完成[7]

    在第二阶段定位过程中,kNN算法是较为常用的一种传统匹配算法。

1.2 kNN算法(最邻近算法)

    临近算法即k最邻近分类算法(kNN,k-NearestNeighbor)[8],核心思想是:如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。

    在kNN算法中要准确选择参数k的值,当k较小时,选择临近点数量较小,不能准确地确定参考点的类别,增大了误差;当选择k较大时,则会选择较远的点,导致定位结果不准确。因此,应多次测量决定参数k的值。本实验经多次测试,k为3时误差最小,因此k取3。

    APn代表定位区域内的n个WiFi热点。在数据采集阶段,在第i个位置采集n个WiFi的RSS信息,i=1,2,3,…,m,m为参考点个数,每个WiFi热点采集多次RSS取平均值。Rij为在第i个位置采集到的第j个WiFi的RSS的平均值,j=1,2,3,…,n;n为WiFi个数,(xi,yi)为i点的实际坐标。在定位阶段,在待定位点测得第j个WiFi的RSS平均值为Rj,则Rij与Rj之间距离为:

ck2-gs1-2.gif

2 改进算法WR-kNN

    由于室内物品较多以及人员的不断走动,使得室内环境变得复杂,人员以及物品的阻挡使WiFi信号发生衰减[10],加大了室内的定位难度。本文通过对距离进行加权[11]以及去除无用组来增加定位精度。在离线阶段对扫描得到的数据进行加权,加大有用数据的权重,在进行定位匹配时,预先将数据按照RSSI均值大小升序排序,取前k个数据进行运算,减少了运算量,降低了小数据对结果的影响。

2.1 加权kNN

    首先对kNN算法中参考点与待测点之间的距离进行加权。kNN算法中,参考点与待测点的距离越接近,相似度越高,在定位中贡献越大。加大贡献大的距离的权值,减小贡献小的距离的权值,有助于提高定位精度。因此,短距离赋予较大的权值wj,长距离赋予较小的权值wj

    ck2-gs3.gif

因此在第i个位置采集到的第j个WiFi的平均RSSI值为Rijwj。dj为两点之间的距离,当参考点离待测点越近时dj越小,相对应的权值wj越大,该参考点所采集的RSSI值越大,对定位影响越大,因此可以提高定位的精度。

2.2 数据排序

    在定位阶段,数据库调出采集的RSSI数据,对待测点的数据与数据库调出的数据进行一一对比,选取较为接近的k个数据作为相似组,利用相似组的数据通过质心算法得到最终的待测点的位置坐标。本文改进是在数据调用之前首先将所有采集的数据Rijwj通过Comparator接口进行升序的排列,数据库中数据将按照由大到小的顺序在组中排列,在调用数据时,只选取组中前n个较大的数据,然后与待测点扫描数据进行匹配,选取较为接近的k个数据进行定位。此方法不仅消除了无用组信息对定位的干扰,还对数据组进行了删减,删除了对定位结果贡献较小的数据组,可以使系统快速地得出定位结果,提高了系统的定位效率。

    Comparator接口为Java中的一个对集合或者数组对象进行排序的比较器。Comparator接口的实现函数为int compare(Object o1,Object o2),排序分为升序和降序排列。当o1<o2返回-1(负数)、o1=o2返回0、o1>o2返回1(正数)时,则为升序排列;当o1<o2返回1(正数)、o1=o2返回0、o1>o2返回-1(负数)时,则为降序排列。改进算法中首先将数据放入Gro.Entry<Integer,Integer>中,通过compare(Gro.Entry<Integer,Integer>o1,Gro.Entry<Integer,Integer>o2)函数进行升序排列。

3 实验

3.1 离线数据采集阶段

    实验区域内部有10个AP,每隔2.5 m采样一次,共有12个采样点。首先测试WiFi信号稳定性。随机选取一个WiFi信号,每隔10 s扫描一次,结果如图1所示。

ck2-t1.gif

    如图1所示,WiFi信号强度基本分布在-77 dBm~-83 dBm之间,个别时间有较大波动,总体较为稳定。采集时采用平均值作为数据储存,可减小较大波动带来的影响,并可以作为定位所需的参考数据。

    离线数据采集阶段,在采样点,每个AP采样10次,将RSS的平均值计入数据库。将RSSIj表示第j个AP的RSSI平均值,MACi表示第i个采样点的10个AP的mac地址集合,(xi,yi)表示第i个采样点坐标。Ri={RSSIi1,RSSIi2,…,RSSIi10}表示第i个采样点所采集的10个AP的RSSI平均值的集合。数据库中一个完整信息为[Ri,MACi,(xi,yi)]。

3.2 在线定位阶段

    在线定位阶段,随机选取7个测试点进行定位,在每个测试点定位3次,取坐标平均值作为最后测试结果,如图2所示。图2分别显示了测试点坐标即定位结果、原坐标即测试点所在的正确坐标以及传统算法定位所得的坐标。如图所示,改进后的坐标相对传统算法所得坐标更加靠近原坐标。宏观上来看,改进算法相比传统算法更加精确。

ck2-t2.gif

    分别基于改进算法WR-kNN以及传统算法所得定位结果进行误差分析,得到如图3所示的误差分布图。由图可看出改进算法误差皆小于传统算法误差。表1为误差数据,分别对应图3中7个采样点。

ck2-t3.gif

ck2-b1.gif

    由表1可以得出,传统算法平均误差为2.55 m,最小误差1.48 m,最大误差4.09 m,误差波动较大。由于传统算法中直接采用即时数据,室内环境复杂,人员走动频繁,因此WiFi信号波动较大,不加以处理直接存入数据库,使得定位结果与实际差距较大。传统定位算法较为复杂,累积误差较大,选取匹配对象不科学,导致定位结果出现偏差,且定位时间较长。WR-kNN算法在数据采集时通过多次采集数据取均值,然后对其进行加权处理,避免了信号波动带来的影响,同时减小了远距离AP带来的误差。定位阶段通过对调用的数据进行预处理,精简了定位流程,减小了定位所需时间,提高了效率,同时减小了累积误差。因此改进算法误差较小,平均误差仅为1.93 m,相对传统算法平均误差减少了0.62 m,误差在2 m左右波动,较为稳定。

4 结束语

    本文采用一种改进的kNN算法研究了基于Android平台的指纹室内定位。离线定位阶段,通过对采集的数据进行加权,增大有用数据的权值,减小无用数据的权值;在线定位阶段,通过对调用的数据预先进行排序,去除无用组,减小不稳定信号对定位结果的影响。实验表明,该改进算法定位结果较为精确,相对传统算法提高了0.62 m。由于实验环境较为复杂,人员较多,AP较多且部署较为随机,因此对实验结果有影响。如果在较为空旷且AP部署较为规范的实验场地,定位结果将更加精确。

参考文献

[1] 倪巍,王宗欣.基于接收信号强度测量的室内定位算法[J].复旦学报(自然科学版),2004,43(1):72-76.

[2] RANTAKOKKO J,RYDELL J,STROMBACK P,et al.Accurate and reliable soldier and first responder indoor positioning:multisensor systems and cooperative localization[J].Wireless Communications,IEEE,2011,18(2):10-18.

[3] 梁元诚.基于无线局域网的室内定位技术研究与实现[D].成都:电子科技大学,2009.

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

[5] 张明华,张申生,曹健.无线局域网中基于信号强度的室内定位[J].计算机科学,2007,34(6);68-71.

[6] 张俪文,汪云甲,王行风.仿射传播聚类在室内定位指纹库中的应用研究[J].测绘通报,2014(12):36-39.

[7] 张明华.基于WLAN的室内定位技术研究[D].上海:上海交通大学,2009.

[8] YANG Z,WU C,LIU Y.Locating in fingerprint space: wireless indoor localization with little human intervention[C].Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.ACM,2012:269-280.

[9] 张晓亮,赵平,徐冠青,等.基于一种优化的KNN算法在室内定位中的应用研究[J].电子设计工程,2013,21(7):44-46.

[10] 杨凯,郭英,毕京学.基于安卓平台的室内实时定位[J].测绘科学,2015,40(6):125-128.

[11] 陈振洲,李磊,姚正安.基于SVM的特征加权KNN算法[J].中山大学学报(自然科学版),2005,44(1):17-20.



作者信息:

武  一,张冀钊

(河北工业大学 电子信息工程学院,天津300400)