基于KDDA和SFLA-LSSVR算法的WLAN室内定位算法

2017-05-13李飞腾王昱洁

计算机研究与发展 2017年5期

关键词：测试点定位精度指纹

张勇李飞腾王昱洁

1(合肥工业大学计算机与信息学院合肥 230009)2 (芜湖创业园留学人员博士后科研工作站安徽芜湖 241000) (hfgdwhb@163.com)

基于KDDA和SFLA-LSSVR算法的WLAN室内定位算法

张勇1,2李飞腾1王昱洁1

1(合肥工业大学计算机与信息学院合肥 230009)2(芜湖创业园留学人员博士后科研工作站安徽芜湖 241000) (hfgdwhb@163.com)

针对接收信号强度(received signal strength, RSS)的时变性降低WLAN室内定位精度的问题，提出了一种基于核直接判别分析(kernel direct discriminant analysis, KDDA)和混洗蛙跳最小二乘支持向量回归机(SFLA-LSSVR)的定位算法,该算法通过核函数策略将采集的各接入点(access point, AP)的RSS信号映射到非线性领域，有效提取了非线性定位特征，重组定位信息，去除冗余定位特征和噪声；然后采用LSSVR算法构建指纹点定位特征数据与物理位置的映射关系模型，采用SFLA算法优化该关系模型的参数，并用该关系模型对测试点的位置进行回归预测.实验结果表明:提出算法在相同的采样次数下的定位精度明显优于WKNN,ANN,LSSVR算法，并且在相同的定位精度下，采样次数较大减少，是一种性能良好的WLAN室内定位算法.

接收信号强度;无线局域网;室内定位;核直接判别分析;混洗蛙跳算法;最小二乘支持向量回归机

随着智能手机的普及以及移动互联网的发展，室内位置服务越来越受到重视，尤其在复杂的室内环境，如机场大厅、医院、地铁站、地下停车场等环境中，常常需要确定用户在室内环境的位置信息[1].在室内环境中，基于接收信号强度(received signal strength, RSS)的无线局域网(wireless local area network, WLAN)室内定位技术[2]要比北斗、GPS、蜂窝网等定位技术的定位精度更高一些.该定位系统热点廉价、部署容易、无需专门的硬件、接入方便，其带宽高、穿透力强、覆盖范围广，因此得到了广泛的关注.

WLAN室内定位主要方法有定位感知、几何测量、场景分析等[3].场景分析法包括指纹识别法和信号传播模型法.指纹识别法由于其算法灵活、定位相对准确，成为了研究的热门方向.

位置指纹定位算法[4]分为2个方面：1)离线阶段无线电地图(radio map)的建立方法；2)在线阶段匹配radio map实现定位的方法.其中匹配定位算法主要有加权K邻居(weightedk-nearest neighbors, WKNN)算法、人工神经网络(artificial neural network, ANN)算法[5]、概率法以及支持向量机(support vector machine, SVM)算法等.WKNN算法[6]找出多个测试点RSS和指纹点RSS有着最小距离的指纹点，然后根据距离的大小加权，将指纹点坐标的加权值作为测试点的坐标；WKNN算法简单且容易实现，但是由于其只是考虑到单一的测试点和指纹点之间的关系，而忽略了不同指纹点之间的RSS更深层次的关系，因此定位精度不高.文献[7]提出一种基于BP神经网络定位的模型，由于BP神经网络本质上是梯度下降法且是一种局部搜索的优化方法，因此收敛速度慢且容易陷入局部最优.文献[8]提出采用SVR构建接收信号强度与物理位置的非线性映射关系，使得定位精度有所提高，但其受RSS的时变性影响较大.radio map的建立方法主要是RSS特征值法.

在WLAN室内定位环境中，多径效应和人员走动造成信号受到不规律干扰，阴影效应造成信号损耗,以上这几种影响使得在相同位置接收到各个接入点(access point, AP)的RSS值具有复杂的时变统计特性，从而降低了室内定位的精度.在建立radio map过程中，如果直接采用各个AP的RSS值作为输入的定位特征值，那么RSS信号的时变性、不同AP之间的相关性，以及判别能力弱的AP的RSS值将会受采集设备硬件所产生的噪声和外界环境影响所产生的噪声的影响比较大，以上3个因素对室内定位的精度影响较大.针对这个问题，本文提出应用基于核直接判别分析[9-10](kernel direct discriminant analysis, KDDA)变换将采集各个AP的原始RSS信号映射到高维非线性空间，挖掘非线性定位特征，提取主要定位特征.在在线匹配定位过程中，由于SVM在统计样本量较少的情况下也能获得良好的统计规律；混洗蛙跳算法[11](shuffled frog leaping algorithm, SFLA)因其容易实现和更强的全局优化能力的特点而被广泛应用于多元函数优化、带约束优化问题等.本文提出应用基于混洗蛙跳算法优化的最小二乘支持向量回归机(SFLA-LSSVR)，首先使用最小二乘支持向量回归机[12-14](least square support vector regression, LSSVR)来建立radio map与其对应位置坐标的非线性关系；其次，通过SFLA算法对LSSVR进行参数优化；最后，以优化后的关系对测试点的位置进行回归预测.通过实验对比验证了KDDA提取非线性定位特征的有效性及SFLA-LSSVR的参数优化和建立回归方程的优势.同时通过与LSSVR,WKNN,ANN,KDDA-LSSVR算法的实验结果对比，表明了该算法具有较高的定位精度.

1 KDDA-SFLA-LSSVR算法

指纹识别算法是通过观察者在场景中各个指纹点和测试点上测得来自各AP的信号强度值，然后将测试点的信号强度值和指纹点的信号强度值进行匹配，预测出测试点的位置信息.指纹识别算法分为2个部分：离线阶段和在线阶段.

1) 离线阶段.在场景中选定指纹点，然后采集各个指纹点上的RSS值，通过KDDA变换提取原始RSS样本的定位特征值；将定位特征和相应的指纹点位置为输入样本对，采用SFLA算法来优化LSSVR算法的参数，完成LSSVR的学习训练过程，得出定位特征和物理位置的最小二乘支持向量回归函数.

2) 在线阶段，在场景中选定测试点，将采集到的测试点RSS值通过KDDA变换，输入构建好的最小二乘支持向量回归函数中，估计出测试点的实际位置.该定位算法的流程如图1所示：

Fig. 1 KDDA-SFLA-LSSVR localization algorithm process图1 KDDA-SFLA-LSSVR定位算法流程

1.1 KDDA变换原理

KDDA变换基本原理：通过建立从输入空间到隐式的高维特征空间的非线性映射，使得在输入空间非线性和复杂的分布模型在高维特征空间变得线性可分和简单化，再应用常规的Fisher线性判别分析[15](linear discriminant analysis, LDA)提取有效的非线性定位特征.

设RSS样本集为Zij∈N，定位环境中参考点的数目为C，每个样本采集各AP的RSS值的次数为Ci，RSS样本总数为表示使用AP的个数，Zij表示在第i个参考点上第j次采集各AP的RSS值，其中i=1,2,…,C，j=1,2,…,Ci.

将原始的RSS信号映射到高维非线性空间：Zij∈N→φ(Zij)∈F.特征空间F中的类间、类内散度矩阵分别为

KDDA变换的优化目标是在F中找出最具判别力的M维基向量Ψ：

满足式(3)的最具判别力基向量Ψ所提取的原始RSS样本的定位特征具有类间离散度最大化、类内离散度最小化，因此KDDA变换能最大程度上的区分不同参考点从而有效地判别定位.

KDDA变换首先计算出SBTW的特征值和相应的特征向量，分别设为λi和ei，然后选取m个最大的特征值及其对应的特征向量，m≤C-1.令：

E=(e1,e2,…,em)V=(v1,v2,…,vm)=ΦbE，

UTSBTWU=I.

计算出UTSWTHU的特征值和特征向量，分别记为λi和pi，其中i=1,2,…,m;然后选取最小的M(≤m)个特征值及其所对应的特征向量，分别记为

Λw=diag(λ1,λ2,…,λM)，

P=(p1,p2,…,pM).

设矩阵Q=UP可以得到：

QTSWIHQ=ΛW，

那么最优判别基向量可以表示为

因此RSS样本集Zij在最优判别基上的投影系数为

YZ=ΨT·φ(Z)=Θ·γ(φ(Z))，

其中,γ(φ(Z))为RSS样本集Zij∈N的核矩阵：

Θ是一个M×L的变换矩阵：

1.2 SFLA-LSSVR算法

由式(11)得出通过KDDA变换分别得到新的指纹点定位特征样本集Z′=Yzi∈M和新的测试点定位特征测试集T′=Ycj∈M；与其相对应的物理坐标分别为LPi=(xpi,ypi)和LQj=(xqj,yqj)，其中i=1,2,…,L，j=1,2,…,Qc，L为指纹点的总个数，Qc为测试点的总个数.LSSVR是支持向量回归机(support vector regression, SVR)的改进，很好地解决了小样本、非线性、高维数的问题，提高了求解速度和泛化能力.依据结构风险化最小原则，LSSVR优化问题如下：

s.t.yi=ωTΦ(Z′)+b+ηi,

其中，i=1,2,…,L，ω为权系数，b为偏置，C为惩罚参数，ηi为误差，Φ(·)为输入空间到特征空间的映射.

可采用拉格朗日函数求解式(14)(15)：

其中，α=(a1,a2,…,ap)T，αi是拉格朗日乘子.

LSSVR使用的是参数相对少、适应能力较强的径向基核函数：

因此得出位置坐标和RSS值的回归函数分别是：

核宽度δ和惩罚参数C是LSSVR算法重要的2个参数，它们的选取直接影响着该算法的学习能力和泛化能力.

SFLA有着良好的全局优化能力，并且参数设置比较简单，可以对LSSVR模型的(C,δ)的参数组合进行优化；因而采用SFLA和LSSVR的混合算法来计算最小二乘支持向量回归函数.

使用SFLA-LSSVR算法回归预测步骤如下：

步骤1. 初始化种群，种群的数目F=M×N，M表示整个种群被分成子种群的个数，N表示每个子种群青蛙的个数，每个子种群最大迭代次数Nmax，在C∈[Cmin,Cmax]和δ∈[δmin,δmax]的范围中随机给每只青蛙一组参数序列(C,δ).

步骤2. 将整个种群中的F只青蛙按照指定的适应度的降序排序，适应度计算：

fit=1(1+E)，

步骤3. 将整个种群分成M组：Y1,Y2,…,YM，每组有N只青蛙，第1只青蛙进入Y1，第2只青蛙进入Y2，直到第M只青蛙进入到YM，然后再将第M+1只青蛙分入Y1，第M+2只青蛙分入Y2，以此类推，直到所有青蛙分配完毕.

步骤4. 用Pg表示整个种群中最好位置的青蛙，Pb表示本组位置最好的青蛙，Pw表示本组位置最差的青蛙，每次进化中更新最差位置的青蛙：

蛙跳步长更新：

Si=rand()×(Pb-Pw).

位置更新：

Pw(k+1)=Pw(k)+Si，

其中，Smax≥Si≥-Smax，rand()∈[0,1]，k=1,2,…,N，Smax是允许青蛙移动的最大距离.如果计算后新的解较优，则用其替代最差个体，否则用Pg代替Pb重复上过程，如果还不能生成更好的青蛙，就随机生成一个新的位置的青蛙取代原来最坏的青蛙Pw.

步骤5. 将青蛙混合，重新按照适应度的值降序排序，并且及时更新Pg.每个子种群执行着自身的局部搜索策略，直到子群体进化到一定阶段后，再将所有青蛙混合来实现各子种群之间的全局交换，全局交换和局部深度搜索的平衡策略使得该算法能够跳出局部极值点，向着全局最优的方向进行.

步骤6. 达到最大迭代次数Nmax时，停止迭代，输出(C,δ)最优参数组合，转入步骤7；否则跳转至步骤3.

步骤7. 用优化得到(C,δ)构建最小二乘支持向量回归函数，将T′输入到回归函数中，得出测试点的估计物理位置.

2 实验结果与分析

2.1 实验条件

实验环境如图2所示，该室内定位环境是在合肥工业大学逸夫楼6楼，定位区域包括办公室、过道，办公室内有办公桌椅、书柜等物品，墙的材料是混凝土，铝合金窗户和金属门，其中办公室为定位区域A，过道为定位区域B.实验选用6个型号为DWL-2414N的AP，固定高度为2 m，使用三星GT-N5110的平板电脑采集各AP的RSS值，采集位置离地高度是1.2 m.实验选取了25个指纹点和30个测试点，其中A区域选取9个指纹点和10个测试点，B区域选取16个指纹点和20个测试点.指纹点的间距是3 m，测试点位置是随机选取.每个位置采集200个样本，每秒2个样本.

Fig. 2 Experimental environment of WLAN indoor positioning图2 WLAN 室内定位实验环境

定义第i个测试点的定位误差erri和平均定位误差AverErr：

2.2 实验结果分析

为了验证KDDA-SFLA-LSSVR算法的有效性，实验对比了WKNN算法、ANN算法、LSSVR算法和KDDA-LSSVR算法.KDDA算法中m表示保留类间散度矩阵最大特征值所对应的特征向量的个数，M表示保留类内散度矩阵最小特征值所对应的特征向量的个数，通过多次试验在50次、100次、150次、200次采样样本时最优参数组合m和M的取值分别是：7，4；8，5；9，5；10，8.SFLA算法种群数目为1000，子种群数为100，迭代次数为6，Cmin，Cmax，δmin，δmax分别为0.01，1000，0.01，1000.KDDA算法和LSSVR都是选择高斯核函数；WKNN算法的近邻数K为3；ANN算法隐藏层神经元数为20的6-20-2的3层BP神经网络结构.

图3所示是在KDDA变换中参数m和M的变化对KDDA-LSSVR算法平均定位误差的影响，实验使用了100个样本.随着m的增大，最优平均定位误差分别是2.285 m，2.122 m，1.989 m，1.913 m，2.062 m，其中m=8且M=5时，平均定位误差最小.随着m的变大，所获得的类间离散度信息变大，定位特征的判别力变大，平均定位误差减小；当m=8且M=5时到达拐点，此时平均定位误差最小；当m继续变大时，所加入的定位特征判别能力弱，且引入了采集设备硬件所产生的噪声、外界环境影响所产生的噪声等，导致平均定位误差变大.

Fig. 3 The influence of parameters m and M on the average positioning error 图3 参数m和M对平均定位误差的影响

图4所示的是使用SFLA优化算法平均定位误差的对比，对于由KDDA提取出的有效的定位特征通过LSSVR构建定位特征和物理位置的映射关系的过程，SFLA有着良好的全局优化LSSVR算法的核宽度参数δ和惩罚参数C的能力，使得LSSSVR有着更好的学习能力和泛化能力，在采样次数为50，100，150，200次时，KDDA-LSSVR比KDDA-SFLA-LSSVR平均定位误差分别高出11.03%，8.98%，7.61%，3.05%，结果表明使用SFLA优化算法对KDDA-LSSVR算法的定位精度有着较大的提高.

Fig. 4 The average positioning error comparison for the use of SFLA optimization algorithm图4 使用SFLA算法优化算法平均定位误差的对比

图5所示的是在不同的采样次数下4种定位算法平均定位误差的对比.LSSVR算法平均定位精度要比WKNN和ANN算法高.WKNN算法没有充分利用到RSS的统计特性，平均定位误差最大；ANN算法利用到了RSS的统计特性，但是容易陷入局部最优，平均定位精度要高于WKNN算法；LSSVR算法相对于ANN算法有着更快的求解速度和更好的泛化能力，因此以上3种算法中LSSVR算法平均定位精度最高.KDDA-SFLA-LSSVR算法定位精度明显高于上面3种算法，在采样次数为50次时，KDDA-SFLA-LSSVR算法平均定位误差为1.985 m，小于上面3种算法在采样次数200次时的平均定位误差，它们分别是2.120 m，2.099 m，2.053 m，因而使用KDDA-SFLA-LSSVR算法能够较大减少样本的采样次数.KDDA算法对原始RSS信号进行了有效的定位特征挖掘和提取，SFLA算法优化LSSVR参数，使得KDDA-SFLA-LSSVR算法平均定位精度明显要高于WKNN，ANN，LSSVR算法.

Fig. 5 The average positioning error comparison under four kinds of positioning algorithms图5 4种定位算法平均定位误差的对比

Fig. 6 The positioning error’s cumulative distribution probability under four kinds of positioning algorithms图6 4种定位算法定位误差累计概率分布对比

图6所示的是在RSS信号采样次数为150次时，4种定位算法定位误差累计概率分布曲线图.当定位误差小于等于2 m时，KDDA-SFLA-LSSVR算法累计概率是73.33%，WKNN，ANN，LSSVR算法的累计概率分别是43.33%，46.67%，60.00%，当累计概率为50%时，KDDA-SFLA-LSSVR，LSSVR，ANN，WKNN算法定位误差值分别为1.28 m，1.71 m，2.07 m，2.16 m，从统计学概率分布可以得出相比于其他3种算法，KDDA-SFLA-LSSVR算法有着更高的定位精度.

3 结束语

针对RSS的时变性影响WLAN室内定位精度的问题，本文提出了一种基于KDDA和SFLA-LSSVR结合的WLAN室内定位算法.一方面从理论分析说明了该算法的可行性，首先将原始的RSS信号通过KDDA算法映射到高维的非线性空间，挖掘出非线性定位特征，使得各样本点之间离散度最大、样本点内部之间的离散度最小，去除冗余定位特征和噪声;然后将提取出的定位特征和物理坐标作为输入样本对输入到LSSVR算法中来建立定位特征和物理位置的最小二乘支持向量回归函数，通过SFLA算法优化LSSVR算法的核宽度参数δ和惩罚参数C;最后将测试点RSS信号经KDDA变换后输入回归函数，得到测试点估计位置.另一方面通过实验对比可以看出KDDA-SFLA-LSSVR算法在相同的采样次数情况下的定位精度明显高于WKNN，ANN，LSSVR算法，在定位精度相同的情况下能较大减少采样样本数，是一种性能良好的WLAN室内定位方法.

[1]Yang Yinggu, Lo A, Niemegeers I. A survey of indoor positioning systems for wireless personal networks [J]. IEEE Communications Surveys & Tutorials, 2009, 11(1): 13-32

[2]Zhang Minghua, Zhang Shensheng, Cao Jian. Indoor location based on signal strength in wireless local area network [J]. Computer Science, 2007, 34(6): 68-75 (in Chinese)(张明华, 张申生, 曹健. 无线局域网中基于信号强度的室内定位[J]. 计算机科学, 2007, 34(6): 68-75)

[3]Du Feng, Tian Shiwei, Li Guangxia. WLAN positioning review[C/CD/OL] //Proc of the 5th China Satellite Navigation Conf. Beijing: CNKI, 2014 [2016-01-01]. http://www.docin.com/p-1412405289.html (in Chinese) (杜峰, 田世伟, 李广侠. WLAN定位综述[C/CD/OL]. //第5届中国卫星导航学术年会论文集. 北京: 中国知网, 2014 [2016-01-01]. http://www.docin.com/p-1412405289.html)

[4]Liu Jianglong, Wan Yihe, Xu Baogen, et al. A novel indoor positioning method based on location fingerprinting [C] //Proc of the 9th Int Conf on Communications, Circuits and Systems (ICCCAS). Piscataway, NJ: IEEE, 2013: 239-242

[5]Borenovic M, Neskovic A. ANN based models for positioning in indoor WLAN environments [C] //Proc of the 19th Telecommunications Forum. Piscataway, NJ: IEEE, 2011: 305-312

[6]Zhang Guowei, Xu Zhan, Liu Dan. Research and improvement on indoor localization based on RSSI fingerprint database and K-nearest neighbor points [C] //Proc of the 9th Int Conf on Communications, Circuits and Systems (ICCCAS). Piscataway, NJ: IEEE, 2013: 68-71

[7]Li Ying, Hu Zhigang. An indoor location model based on BP neural network [J]. Computer Technology and Automation, 2007, 26(2): 78-80 (in Chinese)(李瑛, 胡志刚. 一种基于BP神经网络的室内定位模型 [J]. 计算机技术与自动化, 2007, 26(2): 78-80)

[8]Deng Zhian, Xu Yubing. A support vector regression algorithm for indoor positioning in wireless local area network [J]. Chinese Journal of Scientific Instrument, 2009, 30(6): 578-582 (in Chinese)(邓志安, 徐玉滨. 基于支持向量机回归算法的WLAN室内定位系统[J]. 仪器仪表学报, 2009, 30(6): 578-582)

[9]Lu J W, Plataniotis K N, Venetsanopoulos A N. Face recognition using kernel direct discriminant analysis algorithms [J]. IEEE Trans on Neural Networks, 2003, 14(1): 117-126

[10]Guo Jinyu, Li Yuan, Kong Xiaoguang, et al. Palm print identification based on local projection and kernel direct discriminant analysis [J]. Journal of Optoelectronics Laser, 2011, 22(1): 128-130 (in Chinese)(郭金玉, 李元, 孔晓光, 等. 基于局部保持投影和核直接判别分析的掌纹识别 [J]. 光电子激光, 2011, 22(1): 128-130)

[11]Hasanien H M. Shuffled frog leaping algorithm-based static synchronous compensator for transient stability improvement of a grid-connected wind farm [J]. IET Renewable Power Generation, 2014, 8(6): 722-730

[12]Mustafa M W, Sulaiman M H, Shareefh H, et al. Reactive power tracing in pool-based power system utilising the hybrid genetic algorithm and least squares support vector machine [J]. IET Generation, Transmission & Distribution, 2012, 6(2): 133-141

[13]Issac N S, Palanisamy P, Zhang W J, et al. Log-gabor wavelets based breast carcinoma classification using least square support vector machine [C] //Proc of the 4th IEEE Int Conf on Imaging Systems and Techniques (IST). Piscataway, NJ: IEEE, 2011: 219-223

[14]Suykens J A K, Gestel T V, Brabanter J D, et al. Least Square Support Vector Machines [M]. River Edge, NJ: World Scientific Publishing, 2002: 71-111

[15]Lu J W, Plataniotis K N, Venetsanopoulos A N. Face recognition using LDA-based algorithms[J]. IEEE Trans on Neural Networks, 2003, 14(1): 192-200

Indoor Positioning Algorithm for WLAN Based on KDDA and SFLA-LSSVR

Zhang Yong1,2, Li Feiteng1, and Wang Yujie1

1(School of Computer and Information, Hefei University of Technology, Hefei 230009)2(Post-Doctoral Research Center of Wuhu Overseas Student Pioneer Park, Wuhu, Anhui 241000)

The time-varying received signal strength (RSS) degrades the indoor positioning accuracy in wireless local area network (WLAN). A novel indoor positioning algorithm based on kernel direct discriminant analysis (KDDA) and shuffled frog leaping algorithm and least square support vector regression (SFLA-LSSVR) is proposed to address the problem. Firstly the proposed algorithm employs kernel function strategy to map RSS signal to the field of nonlinear, which is sampled from each access point (AP), and extracts nonlinear features effectively, and reconstructs the positioning information, and discards the redundant positioning features and noise. Secondly, LSSVR algorithm is employed to build the mapping relation model between positioning features and physical locations, and SFLA is employed to optimize the parameters of the relation model, and then test points’ locations are predicted by using the relation model. Experimental results show that the positioning accuracy of the proposed algorithm is much superior to WKNN, ANN, LSSVR algorithm under the condition of the same sampling numbers, and the number of RSS signal which is sampled from each AP is significantly reduced in the same positioning accuracy, and the proposed algorithm is a WLAN indoor positioning algorithm with good performance.

received signal strength (RSS); wireless local area network (WLAN); indoor positioning; kernel direct discriminant analysis (KDDA); shuffled frog leaping algorithm (SFLA); least square support vector regression (LSSVR)

Zhang Yong, born in 1973. Postdoctoral, associate professor. His main research interests include intelligent information processing, WLAN indoor positioning.

Li Feiteng, born in 1991. Master candidate. His main research interests include intelligent information processing, WLAN indoor positioning, pattern recognition.