结合位置指纹和行人航迹的室内定位技术①

罗思奇,罗笑玲,李敏澄,李志锋,陈建城,周娴玮,潘家辉

(华南师范大学 软件学院,南海 528225)

结合位置指纹和行人航迹的室内定位技术①

罗思奇,罗笑玲,李敏澄,李志锋,陈建城,周娴玮,潘家辉

(华南师范大学 软件学院,南海 528225)

主要对室内定位技术展开研究,首先通过手持智能设备收集指定范围样本点的坐标及wifi热点信息;然后应用位置指纹定位方法进行绝对定位;为了提高行走过程中定位的准确性和实时性,采用行人航迹推算算法,即通过手机传感器采集并经处理的数据进行步频检测、步长估算和方向检测,实现相对位置变化的估算.行人航迹算法克服位置指纹定位的不稳定性,而位置指纹定位算法及时调整行人航迹算法带来的累积误差.实验结果表明两种室内定位技术的结合有效提高了室内定位的准确性,能充分应用到实际生活中.

室内定位;安卓平台;wifi;位置指纹定位;行人航迹推算

1 引言

1.1 研究背景

现今社会,全球卫星导航系统已经得到了广泛应用.然而,随着巨型建筑物的增加和人们对导航系统的要求不断增多,全球卫星导航系统的局限性逐渐显露:由于卫星定位精度低和无法穿透建筑物等问题,导致了全球卫星导航系统无法进行室内定位.因此,室内导航系统有巨大的市场潜力及发展空间.

随着Android智能手机硬件的发展,绝大多数手机都自带惯性传感器,为室内导航提供了基本的条件.国外在室内导航技术方面研究得比较早,但实际应用还在进一步研究当中;国内还没有出现成熟的大规模室内导航研究应用.

1.2 研究现状

早前,已经初步取得成果的是Google[1]、NOKIA[2]和富士通[3]的室内定位研究,Google是通过事前的大量数据收集,通过wifi等设备来获取用户在室内的位置;NOKIA是利用分布在空间上方的定位发射器,基于蓝牙设备运用三角定位方法对用户进行定位;富士通则是通过超宽带无线电(UWB)技术来实现的.而近年来越来越多的公司对室内定位进行了大量的研究,例如基于移动通信网络的辅助GPS(A-GPS)、伪卫星(Pseudolite)、射频标签(RFID)室内定位、ZigBee室内定位、手机自主惯性传感器定位导航、红外室内定位、计算机视觉室内定位、光跟踪定位、超声波室内定位等[4].

现阶段各种主要的室内定位技术的概述如下:

(1)蓝牙技术

蓝牙技术通过测量信号强度进行定位.这是一种短距离低功耗的无线传输技术,需要用户开启蓝牙设备,与周围的蓝牙设备连成蓝牙局域网.蓝牙局域网内蓝牙设备通过交换数据,就可以获得用户的位置信息.蓝牙技术主要应用于小范围定位,优点是设备体积小,易于携带,容易推广.其不足是,蓝牙器件和设备的价格比较昂贵,而且对于复杂的空间环境,蓝牙系统的稳定性稍差,受噪声信号干扰大.

(2)射频识别技术

射频识别技术通过无线电讯号识别特定目标并交换数据以达到识别和定位的目的.这种技术作用距离短,一般最长为几十米.但它可以在几毫秒内得到厘米级定位精度的信息,且传输范围很大,成本较低.同时由于其非接触和非视距等优点,可望成为优选的室内定位技术.优点是标识的体积比较小,造价比较低,但是作用距离近,不具有通信能力,而且不便于整合到其他系统之中.

(3)wifi技术

wifi定位技术是通过采集周围的wifi热点的信号,进行信息匹配得到位置信息.由于wifi热点廉价、布设容易,很容易通过增加wifi热点来提高室内定位精度.当前比较流行的wifi定位是无线局域网络系列标准之IEEE802.11的一种定位解决方案,采用经验测试和信号传播模型相结合的方式,易于安装,需要的基站不多,可以采用相同的底层无线网络结构,精度总体较高.它的优点是使用与范围小的室内环境,成本低,只要周围的热点设备布置合理,定位的精度可以得到保证.缺点是很容易受到其他信号的干扰,从而影响其精度,定位器的能耗也较高.

(4)ZigBee技术

ZigBee是介于射频识别和蓝牙之间的一种新兴的短距离、低速率无线网络技术,也可以用于室内定位.在距离短、功耗低且传输速率不高的各种电子设备之间进行数据传输,从而获得具体位置信息,实现定位.其优点是通信效率高,而且低功耗.不足是ZigBee的信号传输受多径效应和移动的影响都很大,而且定位精度取决于信道物理品质、信号源密度、环境和算法的准确性,造成定位软件的成本较高.

各种室内定位技术都有其优缺点,根据不同的应用环境选择不同的技术.本文的研究重点是:基于wifi的室内定位技术的原理,以及详细介绍位置指纹定位技术的实现方法;实现精确定位之后,运用行人航迹推算技术进行位置估算,提高定位的实时性.主要阐述基于wifi室内定位技术和行人航迹推算技术相结合的室内定位方案.

2 位置指纹定位基本原理和实现

2.1 无线信号强度基于物理位置的唯一性

位置指纹[5]是基于无线信号强度信号RSSI的定位方法.由于环境因素的影响,在不同位置搜集的同一个wifi热点的信号强度都不相同,具有唯一性.具体来说,需要收集特定位置的所有wifi热点信号强度存储到指纹数据库,基于其信号强度唯一性,对比手机移动端接收到的wifi热点信号与指纹数据库,通过某个匹配算法算出当前移动端最匹配的位置.

2.2 KNN算法设计

基于wifi环境下的位置指纹定位技术[13],采用的算法为K近邻法[6](KNN,K Nearest Neighborhood).这是最近邻算法(NN,Nearest Neighborhood)的改进型算法,两者的区别在于,NN算法是选取最小距离的矢量值,KNN算法是从最小距离开始选取K(K>=2)个最接近的数据,再求平均值,求出的平均坐标值为待测目标的位置.

此算法如公式(1)所示,假设存放某区域内的wifi热点AP的信号强度数据库中,共有m个参考坐标,n个wifi热点AP.

其中i=1,2,……,m;j=1,2,……,n.bj表示移动者在特定位置接收的第j个wifi热点的信号强度.Bij表示在数据库中第i个参考坐标的第j个wifi热点信号的强度.当a=1时,dis为曼哈顿距离;a=2时,dis为欧几里徳距离.

从结果中选择K个dis值最小的样本坐标值,取这K个坐标值的均值作为待测点的坐标.公式如下,在本文中设a=1,K=5.

KNN近邻算法用平均距离减少了误差,提高了精确度,而且实现起来比较容易操作.

2.3 wifi信号采集和定位

位置指纹定位需要两个阶段:数据采集和定位阶段[6][7].数据采集首先通过手机端收集wifi信号,上传到服务器,存储到数据库.室内定位阶段则是先采集所在位置的wifi热点信息,通过与数据库中的wifi数据作匹配[8].

图1 指纹定位实现流程图

图2 定位流程图

3 行人航迹推算算法基本原理和实现

行人航迹推算(PDR,以下简称PDR)[9]技术是一种基于传感器信息计算行人相对位置的定位技术[10],它首先通过传感器检测行人的步数并估算出步长,然后通过磁阻传感器和陀螺仪计算出行人的方位角,最后获取人体移动的相对位置从而实现定位.手机自包含的传感器包括:惯性传感器(加速度传感器和陀螺仪传感器)、数字罗盘、气压计、视觉传感器等.行走航迹推算技术是通过跨步时的生理特征,通过传感器的值估计出行人的跨步和步长,相较于其他室内定位方法, PDR不受外界环境影响,定位精度较高,但只能获取相对位置信息.

3.1 基于卡尔曼滤波算法的惯性导航技术的原理

卡尔曼滤波是以最小均方误差为估计的最佳准则,来寻求一套递推估计的算法,其基本思想是:采用信号与噪声的状态空间模型,利用前一时刻的估计值和现时刻的观测值来更新对状态变量的估计,求出现时刻的估计值.其核心思想是“预测”+“测量反馈”,通过对上一个结果卡尔曼滤波计算和加权平均预测出下一个结果.

现设线性时变系统的离散状态防城和观测方程为:

其中,X(k)和Y(k)分别是k时刻的状态矢量和观测矢量, F(k,k-1)为状态转移矩阵,U(k)为k时刻动态噪声, T(k,k-1)为系统控制矩阵,H(k)为k时刻观测矩阵,N(k)为k时刻观测噪声.则卡尔曼滤波的算法流程为:

1)预估计

2)计算预估计协方差矩阵

3)计算卡尔曼增益矩阵

4)更新估计

5)计算更新后估计协防差矩阵

重复以上步骤.

3.2 基于卡尔曼滤波算法的惯性导航技术与PDR技术的比较

两种技术都需要实时获取手机传感器的数据,再通过一定计算得到结果.基于卡尔曼滤波算法的惯性导航技术普遍适用于一切运动对象,但是实现测量反馈需要传感器实时获取数据并计算,这需要比较高的计算能力和数据采集率,要求高精度的传感器.而且卡尔曼滤波算法的流程复杂,计算量较大,其计算是一个递推的过程,随着滤波步数的增加,舍入误差逐渐积累,可能使增益矩阵的计算值逐渐失去加权作用而导致滤波发散.而PDR技术是利用行人运动特征,通过检测行人是否行走一步和估算行人一步的步长来获得行人位置的变化.为了便于技术的推广,必须考虑到硬件成本和软件实现的复杂度.手机上的传感器往往无法满足惯性导航的要求.相较于惯性导航技术, PDR技术利用行人运动特征,降低了对加速度传感器精度的要求,同时也降低了算法的复杂度,在现有的安卓手机上PDR技术更容易实现.

3.3 PDR算法基本原理

PDR算法,即从一个已知的坐标位置开始,通过传感器获取行人在该位置的运动方向、速度等数据来推算行人在下一时刻出现的位置的过程.由于其定位过程不受环境因素的影响,能够随时随地提供连续的二维位置信息.PDR的原理[14]如图3所示.

图3 相对位置定位技术原理图

设某一时刻行人的位置在Pn-1(En-1,Nn-1),运动了d距离后到达Pn(En,Nn),两个位置偏离的角度为ɑ,则Pn-1和Pn之间的关系如下:

3.4 PDR算法流程

PDR技术包括四大重要核心:步频检测、步长估算、方向检测和位置估算.图4清晰地展示了行人航迹推算机制的算法流程,探测行人行走时的加速度值,通过滤波模型等有关模型推算出步长以及行走的方向,从而得出行人的位置、距离、速度和方向等信息.

图4 行人航迹推算算法流程图

3.4.1 信号采集

系统需要使用手机上的加速计采集三轴加速度的值[11].由于最后需要得到行人行走的总加速度,所以得通过以下公式得出总加速度:

3.4.2 步频检测和步长估算

(1)阈值判断方法和加速度信号峰值检测

① 滑动查找窗口大小设置

大多数文献中根据斜率的正负转折点来查找双峰值[12],但因为实际上的各种误差,使得峰值会因受到微小震荡而出现误差.因此,我们采用阈值判断方法,通过设置滑动查找窗口的大小来控制峰值检测结果.滑动查找窗口大小的设置对于峰值检测结果有着举足轻重的作用,若窗口值设置得太大,会使很多正确的峰值被舍弃掉;若窗口值设置的过小,则会受到严重的误差干扰,将细微的波动当做是峰值.

② 峰值检测

通过滑动查找窗口值的约束,根据斜率的变化来确定峰顶和峰谷.本文的的峰值查找思想如下:

a.通过三轴加速计采集加速度值,经过滤波处理后,然后进行峰值检测;

b.计算该值与上一次峰值的物理差值和时间差值,如果物理差值超过阈值或者时间差值不在时间窗口范围内,则转第一步执行;否则将该结果作为峰值按序存储.

③ 时间窗口的设定

根据人走路的时间估计每一步需要走多长的时间,从而排除不合理的步伐.通过大量实验并且根据人体的极限行走速度分析,时间窗口的范围为0.2s-2s之间.时间窗口值得设定对于步频检测的准确性有着重要的影响,如果时间窗口值范围设得太大,很可能导致步数的误判.因此,我们需要不断调整时间窗口的大小,适应不同的变化,使之达到合理的范围.

(2)步频检测

确定了步频检测的各个参数后,接下来处理的问题是实现算法流程.步频检测需要实时采集数据,实时计算,实时显示.算法流程如图5所示:

图5 步频检测算法流程图

(3)步长估算

PDR定位精确度与步长估算的精确度有着极大的联系,因此实现PDR的一大重点是实现步长估算.在Android平台上实现PDR,本文通过一种非线性步长估算模型,提高不同步长下步长估算的精度,公式为:

3.4.3 方向检测

在实现PDR技术[9]的过程中,需要获取行人在行走过程中的方向,继而通过方向和行走的距离推算出行人所处的具体位置.

在Android智能手机平台上,检测手机的方向角是通过获取地磁场传感器的数值和加速度传感器的数值来计算的.与此同时,由于手机朝向的不同,所检测出的方向角也会相对不同,因此,在行走过程中,要保持手机的朝向尽可能稳定,才能得到相对准确的数据.

3.4.4 位置估算

获取行人的步频、步长和方向角后,最后就是进行位置估算[9,12].本课题通过基于WiFi网络的室内定位技术获取了行人的初始位置,那么,通过步频、步长和方向角和初始位置就可以推算出行人行走后的大致位置.具体位置的计算公式分为X轴方向的公式和Y轴方向的公式:

4 系统测试结果与分析

本次实验于校图书馆四楼进行,实验过程中实验人员手持Android智能手机从特地位置出发,按照预设路线行走.其中,第一组数据仅通过PDR算法来实现定位,因而实验数据的起始点与预设路线起点一致;第二组数据是仅通过指纹定位算法实现;第三组数据是使用PDR与指纹定位相结合的算法实现.在实验过程当中,记录每次实验的实际数据,存储到数据库,计算得到三组与正确数据的误差值,用matlab将三组轨迹绘制出来如图6所示.其中,x轴表示坐标编号,y轴表示误差值;图7为使用PDR和位置指纹定位算法结合得到的行人轨迹和实际行人轨迹的对比图;图8为采样点与wifi热点位置的分布图.

图6 三组算法误差对比图

图7 行人实际位置与实验位置对比图

图8 采样点与wifi热点位置分布图

1)图6实线代表仅用PDR算法定位得到的误差,由于PDR的起点与实际起点一致,因此在起点的误差为0.通过图像可知,随着时间的延长,PDR存在的累积误差将越来越大.仅靠PDR算法,适用于短时间,短距离内的定位,但是不满足实际需求,因此不可取.

2)图6红色虚线代表仅用wifi位置指纹定位得到的误差,其平均误差为11.38米.从图像可知,位置指纹定位的误差的跳跃性非常大,图中误差的震荡区间为[1.0,21.5].实验数据中最大误差距离达到21.5米,对于在图书馆内的导航,如果误差超过了20米,那么导航的意义微乎其微.对比PDR算法定位,其优势并不明显.由于环境、天气因素均对wifi信号强度有很大的影响,所以仅用位置指纹定位对于实际需求很难满足.

3)图6蓝色虚线是结合了位置指纹定位算法和PDR算法得到的误差值,其平均误差为6.74米.从图中可以看出,对比红色虚线,其趋势比较平滑、稳定.对比实线,前6个点,其误差值大于PDR算法.但从第7个点开始,PDR算法的误差开始大于联合定位的误差,而联合定位的误差值继续趋向稳定.因此,对于长距离和长时间的定位,联合定位明显优于PDR算法,而且其平均误差比位置指纹定位算法的误差小,对于实际情况的应用更加合适.

4)图7中蓝色实线是由实验数据得到的行人轨迹,红色实线则是行人实际的轨迹,两条轨迹中选取了12个坐标点进行比较.其中蓝色轨迹在方向上与红色轨迹大致一致,但存在着一定误差.

综上所述,采用位置指纹与PDR算法联合使用的定位算法,达到PDR算法克服位置指纹定位的不稳定性,又通过位置指纹定位算法的绝对性调整具体位置,消除PDR算法的累积误差.说明结合位置指纹和行人航迹算法的室内定位技术具有一定的可行性.

5 总结

本文针对wifi室内定位技术和PDR技术的组合,就如何降低定位误差进行了深入的思考.本文特色在于通过wifi室内定位技术和PDR技术的相辅相成,很大程度上减少了定位的偶然误差.

但与市场上商业化的,成熟的室内定位技术相比,依旧存在很多不足,本文采用的wifi室内定位技术需要大量的室内wifi信号数据,为系统投入使用的前期准备工作带来了一定的困难,但一旦数据齐全,定位的准确性也比较高.

1谷歌升级 Android版谷歌地图,新增室内导航功能. http://www.36kr.com/p/63722.html.

2 诺基亚室内导航地图.http://www.cnbeta.com/articles/ 164013.htm.

3日本富士通室内导航系统.http://www.cnbeta.com/articles/ 195110.htm.

4国家测绘地理信息局.介绍几种室内定位技术. http://www.sbsm.gov.cn/article/zszygx/zjlt/200812/20081200 045814.shtml.2008.

5李昊.位置指纹定位技术.山西电子技术,2007,(5):84–87.

6陈伟.基于GPS和自包含传感器的行人室内外无缝定位算法研究[硕士学位论文].合肥:中国科学技术大学,2010.

7陈聪传,程良伦.区域细化的RFID室内定位算法.计算机应用与软件,2011,28(1):50–52.

8王立剑.基于Android平台的手机室内定位及导航系统的设计与实现[硕士学位论文].青岛:中国海洋大学,2013.

9徐伟.基于Android手机的室内定位技术研究与实现[硕士学位论文].武汉:华中师范大学,2014.

10裘昕,朱林.行走航迹推算技术的研究.http://www.paper. edu.cn/releasepaper/content/201111-410.[2011-11-24].

11叶震.数字信号处理中的矩阵运算化简.合肥工业大学学报,1985,(1):44–48.

12谢如花.步数检测方法及在手腕式计步器中的应用研究[硕士学位论文].兰州:兰州交通大学,2013.

13 Li B,Wang Y,Lee HK,Dempster A.Method for yielding a database of location fingerprints in WLAN.IEEE Proc. Communications,2005,152(5):580–586.

14 Beauregard S,Haas H.Pedestrian dead reckoning:A basis for personal positioning.Proc.of the 3rd Workshop on Positioning,Navigation and Communication.2006.27–35.

Indoor Positioning Technology Based on Location Fingerprint and Pedestrian Track

LUO Si-Qi,LUO Xiao-Ling,LI Min-Cheng,LI Zhi-Feng,CHEN Jian-Cheng,ZHOU Xian-Wei,PAN Jia-Hui

(School of Software,South China Normal University,Nanhai 528225,China)

On this paper,the research mainly focuses on the technology of indoor location.First,we collect coordinates of sample spots by handheld smart device in the specified range and information of wifi wireless hotspot,with which the location fingerprint technique is applied to absolute positioning;In order to improve the real-time performance and accuracy of indoor positioning,the pedestrian dead reckoning algorithm which will measure stride frequency,estimate step size and detect the direction with data collected and processed by the mobile phone sensor is used to achieve relative position estimation.The pedestrian dead reckoning algorithm can overcome the instability of the location fingerprint technique and the latter can reduce the cumulative error that the former brings.The result shows the combination of the two technologies is able to effectively improve the accuracy of indoor location and be fully used in the real world.

indoor positioning;Android platform;wifi;location fingerprinting technique;pedestrian dead reckoning

广东大学生科技创新培育专项资金(“攀登计划”专项资金)(pdjh2016b0129);国家自然科学基金青年科学基金(61503143);广东省自然科学基金博士科研启动项目(2014A030310244)

2016-09-04;收到修改稿时间:2016-11-03

10.15888/j.cnki.csa.005784