基于SVR和粒子滤波的室内导航方法

杨 智，严 华

(四川大学 电子信息学院，成都 610065)



基于SVR和粒子滤波的室内导航方法

杨 智，严 华

(四川大学 电子信息学院，成都 610065)

针对室内环境复杂性造成的室内定位精度不足问题，提出一种基于支持向量机回归和粒子滤波的室内导航方法；离线阶段通过采集室内接收信号强度并利用统计学习方法，构建室内RSS与物理位置之间的支持向量回归映射模型，定位阶段使用智能移动设备采集加速度、方向角等运动状态信息和Wifi模块感知的环境信息，并利用粒子滤波将运动数据和回归结果进行融合处理，推算移动用户运动轨迹；室内实验结果表明，本方法最大定位误差为1.891 m，平均误差为0.669 m，有效地提高了室内定位导航精度。

支持向量机回归；粒子滤波；WLAN；接收信号强度

0 引言

目前最流行的定位方法是GPS(全球定位系统)，在户外区域，包含GPS芯片组的便携式手持设备可以很方便地提供存在有限误差的地理位置信息。但是由于建筑物的遮挡以及室内环境的复杂性会造成无线信号阻塞或信号衰减，限制GPS在室内定位领域的应用，而基于无线局域网技术的无线基础设施非常适合用来实现室内定位和位置追踪。

无线基础设施，包括基于IEEE 802.11的WLAN、基于IEEE 802.15.4的ZigBee、基于IEEE 802.15.4a的超宽带(UWB)、蓝牙等等。WLAN作为有线网络的延伸，随着技术标准的完善，以其高速通信、高可靠性、部署便捷、使用灵活、易于扩展等特点，快速融入到人们的日常生活中，逐渐成为现代移动办公、移动生活娱乐必不可少的一部分，而基于WLAN的定位技术研究在这种背景下快速发展起来[1-2]，逐渐成为国内外研究的热点。

常用的定位技术有TOA、TDOA、RTOF、AOA、RSS、FDOA以及AOA/TDOA联合定位技术和TDOA/FDOA联合定位技术[1,3-4]等，结合无线定位算法如三边测量、三角测量、小区ID(蜂窝)和指纹等进行位置估计。由于WLAN室内环境的复杂性和多径效应的影响，RSS信号呈现非线性、非高斯的统计特性[5]，传统定位技术往往无法满足用户的定位需求。

随着无线通信网络技术的快速发展，智能手机正逐渐深入社会生活的各个层面，其计算、存储和处理能力等得到大幅提升，各种各样的传感器加入到手机中，包括加速度传感器、方向传感器、陀螺仪等，使得智能手机能够为室内定位与导航提供必要的感知信息，而将智能手机惯性导航与传统定位技术结合已成为目前的发展趋势。

本文主要研究基于SVR和粒子滤波的室内导航算法，通过离线阶段采集室内信号强度数据，训练室内信号强度与坐标的SVR回归模型，定位阶段将智能手机惯性导航数据和SVR回归确定的绝对位置，利用粒子滤波进行数据融合，确定用户运动轨迹，以满足用户室内定位需求。

1 基于手机的室内无线导航方法

传统的行人航迹推算技术不能获得用户的绝对定位信息，且使用智能手机内置的传感器会带来较大误差，因此本文引入支持向量机回归和粒子滤波，通过在离线阶段采集室内空间中RSS样本，并通过支持向量机回归学习，构建室内信号强度序列与位置点的回归映射模型。在定位阶段，利用手机内置的加速度传感器、方向传感器对用户的运动行为进行感知，利用WIFI模块对用户环境进行感知[6]，并通过粒子滤波将用户运动信息和经由回归模型确定的绝对位置信息进行滤波融合，以提高室内导航精度。算法整体结构如图1所示。

图1 室内导航方法整体框架图

1.1 基于手机的航位推算

随着智能手机中MEMS(Micro-Electro- Mechanical System)的发展，用于航位推算的传感器尺寸、重量、成本大大降低，精度有所提升，使得航位推算在行人导航中得以应用[7]。常用的航位推算方法有两种：基于距离和基于步态的航位推算。第一种方法通过对加速度传感器采集的数据进行连续积分处理，推算用户行进距离，这种方式需要大量积分，且存在零状态漂移误差；第二种方法通过对加速度传感数据进行数值转换和滤波处理，获取用户步态特征，并推算出用户行进步数和步长[8]。

文献[9]中的步伐探测算法是通过对合加速度的局部方差进行平滑滤波来提取用户步态特征，但从设备获取的原始加速度值准确度有限，且其中错误的加速度计值和噪声拥有高频特性，此时的步伐探测算法不能很好的滤除干扰因素，因此本文根据用户运动频率特性，引入低通巴特沃斯滤波对合加速度数据进行滤波，并根据文献[9]中使用的步伐探测、步长计算和方向判断方法，对用户航位进行推算。

1.2 支持向量机回归

Wifi信号在室内环境存在复杂的衍射、反射现象，室内不同位置点存在不同的衰减情况，使得信号强度与室内位置之间存在复杂的非线性关系，很难求出准确的的解析表达式，而支持向量机(SVM)是一种基于统计学和VC维理论的机器学习方法，它以最小化结构风险为目标，已在解决高维和非线性问题方面表现出了很多优势，因此选择支持向量机回归来构造室内RSS信号与物理位置之间的非线性映射关系，回归模型示意图如图2所示。

图2 回归模型示意图

支持向量机回归可表述为：给定训练数据集D={(ri，(xi，yi))|i=1，2，…，n}，其中ri= (RSSIi1，RSSIi2，…，RSSIim)，RSSIij为第j个信号源在采样节点i处的信号强度，(xi，yi)为采样参考点的二维坐标。通过一个非线性映射φ(·)将输入样本数据映射到一个高维特征空间，然后在高维特征空间构造回归估计函数：

(1)

根据结构风险最小化原则，原始问题可以转化成求解凸二次规划问题：

(2)

引入Lagrange函数，构造支持向量回归函数：

(3)

其中:函数K为核函数。这里通过对离线阶段采集的样本进行训练和参数寻优，得到两个独立的分别输出两维物理位置坐标的SVR回归函数。

1.3 粒子滤波融合

粒子滤波是一种基于顺序蒙特卡洛方法(sequential Monte Carlo)的贝叶斯推理(Bayesian inference)过程，广泛应用于机器人定位和跟踪的方法。本文将经由回归模型确定的绝对位置信息作为环境观测，并利用粒子滤波将其与智能手机检测到的用户运动信息进行滤波融合，基本步骤如下。

1)初始化阶段：

2)转移阶段：

粒子状态转移，也就是用户位置随时间的更新过程[6]。这里以每一个步态周期为单位进行粒子状态转移，不同粒子将根据用户在此步态周期中的步长和方向产生不同的路径。

(4)

3)决策阶段：

利用当前位置点采集的信号强度序列，经离线阶段训练的支持向量机回归模型，得到定位绝对坐标 (xt,SVR，yt,SVR)，以此作为环境观测值来更新粒子权重，公式如下：

(5)

其中:R是测量噪声。

粒子权值归一化：

(6)

采用粒子加权和来确定用户位置：

(7)

4)重采样阶段：

为避免粒子退化，需要进行重采样，这里采用随机采样方法[6]，剔除低权重的粒子，复制权值高的粒子。

5)重复步骤2～4，逐步确认用户位置，直到导航结束。

2 实验测试

为评估本文提出的基于SVR和粒子滤波的室内导航方法的性能，本文在21 m*13 m的室内环境内进行多次实验。选取的实验环境为研究所部分实验室区间，整个区域总共可以采集到15个AP节点信号，这里只选取布置于测试环境内的3个AP节点进行测试。实验采用的数据采集设备为小米1 s，整个算法分为离线训练和在线定位两个阶段，离线阶段在图3所示环境中，以人体平均步长75 cm为间隔，对室内可行区域进行采样，实际划分了221个采样点，并在每个采样点以每秒采集一次的速率采集10次。然后利用LIBSVM工具箱[10]对采集到的2210个样本数据进行训练，选择ε-SVR和RBF核函数，并进行网格参数寻优，构建室内信号强度与物理位置之间的回归映射模型。

图3 室内采样点分布示意图

2.1 步态检测

本文引入低通巴特沃斯滤波对手机航位推算进行优化，并对其有效性进行验证，结果如图4、表1所示。

图4 合加速度巴特沃斯滤波结果

测试用例步数测试次数准确率距离平均误差/m1502095%1.02621002090%1.513

从上述图表可以看出，本文使用的低通巴特沃斯滤波效果较好，且步行距离误差小于实际距离的3%，结果表明该方法可以准确测量行人步数和行走距离。

2.2 室内导航性能测试

为评估在线定位阶段室内导航方法的可行性和有效性，在智能手机上实现航位推算算法，然后由实验者手持智能移动设备按照预先设定的轨迹以正常步速绕行3圈，采集行走过程中每个步态周期的步长、方向和周围环境实时的RSS信号强度，以此数据集作为在线定位阶段的测试数据，并将导航定位结果与基于手机的航位推算定位结果进行误差对比。

实验者手持智能设备在图5中约6.5 m*12 m的室内区域，按照箭头方向绕行三圈。图5中带箭头的方框即为预设的理想步行轨迹，其中带实心圆的曲线为行人航位推算的轨迹，可以看出其与理想轨迹严重偏离，且误差较大。

图5 航迹推算轨迹图

图6所示为本文提出的基于SVR和粒子滤波的室内导航方法对同一运动数据集的处理结果，从图6中可以看出本算法处理所得行人轨迹曲线与理想轨迹重合度较高。

图6 本方法测试轨迹图

图7中描述了本算法和航位推算的定位误差，其中航位推算最大定位误差为5.252 m，平均误差为2.623 m，本文提出的室内导航算法最大定位误差为1.891 m，平均误差为0.669 m，相比于航位推算，平均误差减少了74.49%。

图7 航迹与本算法定位误差对比

3 结论

本文将智能手机惯性导航与传统定位技术结合，提出一种基于SVR和粒子滤波的室内导航方法，通过将离线阶段训练所得室内信号强度与物理坐标的SVR回归映射模型作为观测条件，并利用粒子滤波将其与航位推算进行融合处理，推算移动用户位置。实验结果表明，本文提出的方法提高了定位精度，并拥有良好的定位效果，能够满足用户的室内定位需求。

[1] 梁久祯. 无线定位系统[M]. 北京: 电子工业出版社, 2013.

[2] 郎昕培,许 可,赵 明. 基于无线局域网的位置定位技术研究和发展[J]. 计算机科学, 2006, 33(6): 21-24.[3] Yamasaki R,Ogino A,Tamaki T. TDOA location system for IEEE 802.11b WLAN[A].Proc of Wireless Communications and Networking Conference[C]. IEEE Press, 2005: 2338-2343.

[4] 韦 丹. 基于移动终端的室内关键定位技术研究 [D]. 北京: 北京邮电大学, 2014.

[5] 邓志安,徐玉滨. 基于支持向量机回归算法的WLAN室内定位系统[J].仪器仪表学报, 2009, 30(6): 578-582.

[6] 赵逢达,闫亭亭,孔令富. 一种基于粒子滤波的智能移动终端室内行人定位算法[J]. 小型微型计算机系统, 2014, 35(8): 1842-1847.

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

[8] Jeong Won Kim, Han Jin Jang, Dong-Hwan Hwang, et al. A step, stride and heading determination for the pedestrian navigation system [J]. Journal of Global Positioning Systems, 2004, 3(1): 273-279.

[9] 朱建佳. 基于Android平台的室内导航系统的设计与实现[D]. 北京: 北京邮电大学, 2014.

[10] Chang Chihchung,Lin Chihjen. LIBSVM: a library for support vector machines [EB/OL]. (2013-04-01)[2013-07-14]. http:// www. csie. ntu. edu. tw/～cjlin/libsvm.

Indoor Navigation Method Based on SVR and Particle Filter

Yang Zhi，Yan Hua

(College of Electronics and Information Engineering, Sichuan University, Chengdu 610065, China)

Aiming at the lack of indoor positioning accuracy caused by the complex indoor environment, a method of indoor navigation based on support vector regression (SVR) and particle filter is proposed. At the offline stage, the indoor received signal strength (RSS) is collected, and statistical learning methods are used to construct support vector regression model indoor mapping between received signal strength and physical location. At positioning stage, intelligent mobile equipment is used to capture acceleration, direction angle and environmental information perceived by WIFI module. Based on the particle filter, the motion data and the regression result are fused to calculate the motion trajectory of the mobile user. Experimental results show that the maximum location error of proposed method is 1.891 m, while the average error is 0.669 m, and indoor location and navigation accuracy can be effectively improved.

support vector regression; particle filter; wireless local area networks; received signal strength

2016-04-01；

2016-04-29。

国家自然科学基金项目(61172181)。

杨 智(1992-)，男，湖南衡阳人，硕士研究生，主要从事模式识别与智能系统方向的研究。

严 华(1971-)，男，四川渠县人，教授，硕士研究生导师，主要从事模式识别与智能系统、嵌入式系统方向的研究。

1671-4598(2016)09-0231-03

10.16526/j.cnki.11-4762/tp.2016.09.064

TP393

A