《电子技术应用》

基于Android平台改进的室内WiFi定位算法的研究

2017年电子技术应用第3期 作者:武 一,张冀钊
2017/4/13 15:28:00

武  一,张冀钊

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


    摘  要: 基于Android手机平台设计并实现了WiFi室内定位系统。该系统采用指纹定位算法,通过手机采集室内WiFi信息并建立数据库,当用户发出定位请求时,手机将扫描到的WiFi信息发送给数据库,通过匹配算法进行位置定位。通过对采集后的数据进行加权以及对数据库数据进行预先处理,降低了运算量,同时去除了较小的信号强度的干扰。实验表明,与传统算法相比,该系统定位精度大大增加。

    关键词: 室内定位;WiFi;Android平台指纹算法;改进算法

    中图分类号: 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.

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.

继续阅读>>