基于核直接判别分析和支持向量回归的WLAN室内定位算法

第33卷第4期电子与信息学报Vol.33No.4 2011年4月 Journal of Electronics & Information Technology Apr. 2011

基于核直接判别分析和支持向量回归的WLAN室内定位算法

徐玉滨邓志安*马琳

(哈尔滨工业大学电子与信息工程学院哈尔滨 150001)

摘要：该文针对RSS信号的时变性降低WLAN室内定位精度的问题，提出了一种新的基于核直接判别分析和支持向量回归的定位算法。该算法利用核直接判别分析对原始RSS信号进行定位信息重组，去除冗余定位特征和噪声，提取最具判别力的定位特征，然后采用支持向量回归算法建立定位特征与物理位置的映射关系。实验结果表明，提出算法的定位精度明显高于传统定位算法，且大大降低了离线阶段数据采集的工作量。

关键词：无线局域网；室内定位；核直接判别分析；支持向量回归

中图分类号：TP393.17 文献标识码：A 文章编号：1009-5896(2011)-04-0896-06 DOI: 10.3724/SP.J.1146.2010.00813

WLAN Indoor Positioning Algorithm Based on KDDA and SVR

Xu Yu-bin Deng Zhi-an Ma Lin

(School of Electronics and Information Engineering, Harbin Institute of Technology, Harbin 150001, China)

Abstract: The time-varying Received Signal Strength (RSS) drastically degrades the indoor positioning accuracy in Wireless Local Area Network (WLAN). A new positioning algorithm based on Kernel Direct Discriminant Analysis (KDDA) and Support Vector Regression (SVR) is proposed to resolve the problem in this paper. The proposed algorithm employs KDDA to reconstruct the localization information contained in the RSS signal. The most discriminative localization features are then extracted while the redundant localization features and noise are discarded by KDDA. The extracted localization features are taken as inputs to SVR learning machine and the mapping between localization features and physical locations is established. The experimental results show that the proposed algorithm obtains significant accuracy improvement while requiring a much smaller set of RSS training data than previous methods.

Key words:Wireless Local Area Network (WLAN); Indoor positioning; Kernel Direct Discriminant Analysis (KDDA); Support Vector Regression (SVR)

1引言

近年来，人们对室内位置信息服务如个性化信息传递、医疗服务、目标发现等的需求与日俱增[1]。由于传统的GPS和蜂窝网定位技术无法满足室内定位的要求，基于接收信号强度(RSS)的无线局域网(WLAN)室内定位系统受到越来越广泛的关注[2]。该定位系统仅由现有的广泛存在的WLAN架构和移动终端即可实现，不需要任何额外的专用设备，而且其较高的定位精度能满足复杂室内环境下大多数位置信息服务的要求。

目前最普遍的WLAN室内定位系统是基于位置指纹定位架构的[3]。该方法分为离线和在线两个阶段。离线阶段，在选定的参考点位置上采集来自各个接入点(Access Point，AP)的RSS值，以建立位

2010-08-05收到，2010-11-01改回

国家863计划项目(2008AA12Z305)资助课题

*通信作者：邓志安 dengzhianan@http://www.77cn.com.cn 置指纹数据库即所谓的无线电地图；在线阶段，将实时采集的RSS信号与无线电地图比较，匹配出用户位置。位置指纹定位法可以被看作是典型的模式识别过程，目前已有部分模式识别算法[35]?应用于WLAN室内定位。

在实际WLAN室内定位环境中，由于多径、阴影效应、人员走动等影响[6]，固定位置上来自各个AP的RSS值往往表现出复杂的时变统计特性，降低定位精度和增加系统复杂度。一方面，直接采用各个AP的RSS值为输入的定位特征分量，RSS信号的时变性将严重影响定位精度。首先是因为方差较大，位置分辨能力较弱的AP的RSS信号将引入大量的噪声；其次不同AP的定位特征分量的相关性造成输入特征空间的冗余。另一方面，为获得RSS 信号的时变统计特性，离线阶段需要耗费大量的人工时间在每个参考点上采集多个RSS样本，不利于定位系统的大规模部署。针对输入定位特征，文献[7,8]中分别采用不同的方法选择最具判别力的AP

第4期 徐玉滨等： 基于核直接判别分析和支持向量回归的WLAN 室内定位算法 897

对应的RSS 信号作为输入定位特征。由于未选中AP 所对应的RSS 定位信息都将被抛弃，将降低定位精度，尤其是当可利用的AP 个数较少的时候。文献[9]利用主成份分析(Principal Component Analysis ，PCA)进行定位特征提取，去除定位特征分量之间的相关性。但是PCA 的线性特性限制了非线性定位特征的提取，而且PCA 无法有效提取有判别力的定位特征。

本文提出基于核直接判别分析(KDDA)和支持向量回归(SVR)的WLAN 室内定位算法(KDDA- SVR)。KDDA 可以有效提取非线性定位特征。而且，与其它特征提取方法[10]不同的是，KDDA 按照判别力大小重组RSS 定位信息，从中提取最具判别力的定位特征，同时将判别力小的冗余定位特征当作噪声去除。判别力即定位特征区分不同物理位置的能力，是影响WLAN 指纹定位精度的关键因素。基于SVR 在解决有限样本的非线性回归问题的特有优 势[11]，结合SVR 学习和建立定位特征与物理位置的映射关系。实验结果表明，本文算法在明显提高定位精度的同时，大大减少了参考点数据采集的工作量。

2 基本理论

2.1 KDDA 变换基本原理

KDDA [10]算法是Fisher 线性判别分析(Linear Discriminant Analysis ，LDA)的核推广形式。LDA 作为一种常用的特征提取方法，被广泛应用于多类分类问题中，以寻找能最优化区分不同类别的特征分量。核方法为许多标准的线性变换提供了有效的非线性拓展[11]，因此KDDA 可以有效提取RSS 信号的非线性定位特征。

为了挖掘非线性定位特征，KDDA 将原始RSS 信号r 映射至高维非线性空间：:φ∈r R d → ()φ∈r F ，其中R d 表示由d 个AP 组成的RSS 信号空间。然后KDDA 以Fisher 判别式为优化准则，在核空间F 中寻找最具判别力的基向量1[,ψ′′=ψ

,]M

ψ′"： T BTW T WTH tr()arg max tr()????′?=??????S S ψψψψψψ (1) 式(1)中S BTW 和S WTH 分别为类间和类内离散度矩

阵：

T BTW 11()()C

i i i C

φφφφ==??∑S (2)

()()T WTH 111(())(())C n

i i i i i t t t L φφφφ===??∑∑S r r (3)

其中()11/()n

i i t n t φφ==?∑r ，11/C

i i C φφ==?∑分别 为参考点L i 上对应C i 类的均值中心和所有类别的

均值中心，设()i t r 和n 分别为参考点L i 上的第t 个RSS 向量样本和样本数目，C 为整个定位环境中总的参考点数目，L n C =?为RSS 样本总数。 2.2 SVR 统计学习理论

SVR 算法以统计学习的VC(Vapnik and Chervonenkis)维[11]理论为基础。学习机器的实际风险R (w )的上界由经验风险值R em (w )和置信范围值(/)n h φ两部分决定：

()()(/)em R w R w n h φ≤+ (4) 其中w 表示学习函数的参数，(/)n h φ是单调递减函数，h 表示学习函数的VC 维，n 为训练样本数。传统学习机 …… 此处隐藏：11347字，全部文档内容请下载后查看。喜欢就下载吧 ……