基于微粒群优化LSSVM的室内指纹定位算法

赵妍 乐燕芬 施伟斌

摘 要：为了降低利用最小二乘支持向量机（LSSVM）定位过程中参数选取对定位精度的影响，提出一种基于微粒群进行参数优化的室内指纹定位算法。该算法通过离线采集的RSSI数据训练最小二乘支持向量机，利用微粒群算法寻找并确定LSSVM全局最优参数，获得基于位置指纹的LSSVM定位模型。仿真结果表明，相对于传统LSSVM定位，PSO-LSSVM有效提高了定位准确度，并能在小样本情况下保持良好的定位精度。

关键词：指纹定位;微粒群算法;最小二乘支持向量机;RSSI

DOI：10. 11907/rjdk. 182266

中图分类号：TP312文献标识码：A文章编号：1672-7800（2019）004-0087-04

0 引言

随着无线通信技术、互联网技术的不断发展，具有自组网能力的无线传感器网络（WSN）已成为学者们关注的热点[1-2]。传感器节点定位是WSN领域的主要应用之一，然而传感器节点大多布置在矿井下或地下停车场、商场等各种复杂室内环境中，室外基于GPS信号的定位方式易受到环境非视距、干扰多变、多径等因素影响而难以实现。因此，如何获取传感器节点位置信息成为WSN室内定位应用中必须考虑的问题之一[3]。

针对节点定位问题，国内外许多学者进行了深入研究，提出了大量可行的室内定位算法。当前常用定位算法主要包括基于接收信号强度指示 （Received Signal Strength Indicator，RSSI）[4]、到达时间（Time of Arrival，TOA）[5]、到达时间差（Time Difference of Arrival， TDOA）[6]与到达角度（Angle of Arrival，AOA）[7]的定位算法等，其中基于RSSI位置指纹[8]的室内定位算法是 WSN 定位中的一种常用定位算法。该算法基于监控区域内已知若干参考位置点的无线信号强度分布，匹配获得目标移动节点位置。然而，由于受到复杂多变的室内环境因素影响，位置节点的RSS值具有较强时变性，从而降低了定位精度，同时在离线阶段需要训练大量样本点，不利于大场景应用[9]。因此，很多学者提出将机器学习的一些理论，如核岭回归（Kernel-based Ridge Regression）[10-11]、支持向量机（Support Vector Machine，SVM）[12-16]、神经网络[17]等引入室内定位中。

文献[10]、[11]提出基于机器学习理论结合卡尔曼滤波的RSSI指纹定位方法，将核岭回归引入卡尔曼滤波观测方程中，解决了非线性回归问题，并求解了双重优化问题。该算法能够提高定位精度，但其不足之处在于对核函数宽度选取、岭回归方程参数确定比较复杂，定位速度慢;文献[12]、[13]均采用基于SVM分类回归的定位算法，首先对特征数据库数据进行分类训练，然后通过SVM回归算法建立RSS信号与位置的数学模型，从而实现室内定位。该算法对采集特征向量经过无监督聚类后的值建立特征数据库，在一定程度上减少了在线定位階段的计算量，提高了定位准确性。但是随着样本数据的增多，在SVM中求解二次规划问题变得更加复杂，训练时间也会更长，从而影响了其实际应用价值。

为了提高节点定位精度与效率，本文结合最小二乘支持向量机（Least Square Support Vector Machine，LSSVM）和微粒群算法的优点，提出一种基于微粒群优化LSSVM的室内指纹定位算法（PSO-LSSVM）。利用微粒群算法对最小二乘支持向量机参数进行优化，可以有效改善模型训练性能，进而提高LSSVM在室内定位算法中的定位精度。

1 基本理论

1.1 LSSVM原理

支持向量机基本思想是通过一个非线性映射，将数据从输入空间映射到高维特征空间，将实际问题转化成凸二次规划问题。最小二乘支持向量机（LSSVM）修正了支持向量机的损失函数和约束条件，相比于标准SVM算法，其简化了复杂性，从而提高了运算速度[17]。

综上可知，建立基于LSSVM的室内定位模型，通过确定[g]的值有利于参数优化。

1.2 微粒群算法

微粒群优化算法（PSO）是由Kennedy&Eberhart提出的一种智能优化算法[19]，其所需参数少，且容易实现。本文利用粒子群算法对LSSVM参数进行全局最优化，并对优化后的参数建立定位模型，以更好地体现定位输入与输出之间的非线性关系，而且不易受环境因素影响。

2 基于LSSVM的室内指纹定位算法

2.1 算法介绍

室内指纹定位原理是利用位置特征信息，例如信号强度指示、空间频谱、图像亮度等，将相关定位特征信息与该位置建立映射关系，并作为一个信息集合，组成一个独特的指纹信息，建立指纹信息库（Fingerprint或Radio-map）。本文提出的基于LSSVM的室内指纹定位算法主要包括两个阶段：离线训练（地图生成）阶段和在线匹配阶段。

（1）离线训练阶段。在待定位区域放置若干锚节点，通过采集某位置特征信息训练样本数据，即记录每个位置点的RSSI 信息并作为该位置特征数据，称为位置指纹;然后将所有位置指纹保存到数据库中，得到一张无线电地图;最后利用定位区域若干位置点的训练样本进行LSSVM训练，并采用微粒群算法优化LSSVM参数，得出基于位置指纹的LSSVM定位模型。

（2）在线匹配阶段。当移动节点在待定位区域内移动时，将实时接收到的RSSI信息输入到LSSVM模型，通过模型计算出移动节点位置。

综上所述，基于LSSVM的室内指纹定位模型如图1所示。

2.2 PSO-LSSVM定位算法具体步骤

LSSVM参数γ、g对其性能影响很大，然而γ、g通常很难确定，一般工程采用穷举法确定参数。为了优化LSSVM定位模型，本文采用PSO优化LSSVM。步骤如下：

（1）离线训练阶段：①建立训练样本，并对样本数据进行预处理;②导入种群大小、迭代次数、变异概率最大与最小值等参数，以及需要训练的RSSI样本值;③初始化参数γ、g，以及每一个微粒位置、速度、pbest和gbest等，初始化LSSVM模型，并计算初始适应度值;③通过PSO中的粒子运动迭代优化参数γ、g;④按照公式（7）、（8）更新微粒速度与位置，计算适应度值，并更新个体、全局极值;⑤更新微粒群体全局极值;⑥判断是否满足迭代条件，如果满足则终止寻优，输出全局最优值，否则跳转到步骤④继续寻优;⑦由步骤⑥得到最优参数γ和g，并构建定位模型。

（2）在线定位阶段：将需要定位坐标接收的RSSI值输入到LSSVM模型，即可输出对应位置坐标。

算法具体实现过程如图2所示。

3 仿真实验及分析

为了验证粒子群优化最小二乘支持向量机算法的可行性与正确性，首先对传统LSSVM采用试凑法选取模型参数，运用PSO优化算法对LSSVM输入信号进行全局最优选择，并将本文方法与传统LSSVM方法作对比。

3.1 仿真环境

为了测试PSO-LSSVM室内定位算法性能，本文利用Matlab R2016b仿真软件进行验证，并利用奥村-哈他（Okumura-Hata）模型[19，21]生成RSSI 测试数据，即：

本文使用的训练样本数据为900个，测试样本数据为100个，每个样本由9个来自不同锚节点的RSSI值构成。仿真实验环境及参数设置如表1所示。

3.2 结果与分析

本文采用PSO对LSSVM进行参数优化，PSO具体参数如下：种群大小为20，迭代次数为100代。本文将测试样本模型预测结果的均方误差作为适应度，适应度曲线如图3所示。在前60代，适应度逐渐上升，60代之后适应度则逐渐收敛并趋于平稳，此时可得到全局最优参数，即[γ]=2.863 9、[g]=0.008 1，且收敛速度快、定位精度高、效果好。

图4是PSO-LSSVM预测模型与传统LSSVM模型预测结果对比。从图4可看出，相比于传统LSSVM算法，PSO-LSSVM算法误差更小，可将大多数目标位置估计结果控制在2.5m以内，且许多估计误差在1.5m内。从定位误差上可以看出，基于PSO优化的LSSVM算法比传统LSSVM算法定位精度更高，说明采用PSO算法获取LSSVM参数建立的定位模型，能更好地反映输入与输出之间的非线性关系。

PSO-LSSVM与传统LSSVM两种算法定位统计结果如图5所示。由图5可知，PSO-LSSVM算法在2m内的定位概率达到80%以上，而传统LSSVM算法定位概率仅为60%。因此，PSO-LSSVM算法在定位精度方面优于传统LSSVM算法。

表2为分别通过PSO-LSSVM与传统LSSVM方式得到的惩罚因子γ和径向基核函数g，采用PSO优化后预测模型平均定位误差为1.69m，相对了传统LSSVM预测模型定位结果，定位误差有所提高。由此可以看出，粒子群算法改进了最小二乘支持向量机的定位性能，也证明了粒子群优化最小支持向量机定位的可行性。

4 结语

为了降低支持向量机室内定位过程中参数选取对定位精度的影响，提出一种基于微粒群优化LSSVM的室内指纹定位算法。该方法通过微粒群算法寻找最优参数，并利用离线采集的RSSI数据训练最小二乘支持向量机，从而获得基于位置指纹的LSSVM定位模型。仿真实验结果表明，将RSSI作为定位特征向量输入能有效提高PSO-LSSVM的定位精度，尤其在小样本学习情况下从而精度很高。与传统定位算法相比，该算法定位性能更好，具有一定应用价值。但是由于训练样本数据量较大，增加了计算量，训练时间也较长。因此，如何在保证精度的情况下，进一步减少训练时间将是未来的研究方向。

参考文献：

[1] 冯亚超，贺康，杨红丽，等. 一种无线传感器网络数据收集协議的研究与优化[J]. 传感技术学报，2014，27（3）：355-360.

[2] AKYILDIZ W S，SANAKARASUBRAMANIAM Y，CAYICI E，et al. Wireless sensor networks：a survey[J]. Computer Networks，2002，38（4）：393-422.

[3] HAO Z，WANG S. Survey on localization algorithms for wireless sensor networks[J]. Journal of Huazhong University of Science and Technology （Natural Science Edition），2008，36（1）：224-227.

[4] LI X，ZHOU F，DU J. LDTS：a lightweight and dependable trust system for clustered wireless sensor network[J].IEEE Transactions on Information Forensics and Security，2013，99：1.

[5] CHONG C Y，KUMAR S P. Sensor networks：evolution，opportunities， and chanllenges[J]. Proceedings of the IEEE，2003.

[6] 汪炀. 基于无线传感器网络定位技术研究[D]. 合肥：中国科技大学，2007.

[7] 朱晓娟，孟祥瑞. 基于加权质心的无线传感器网络动态节点定位算法[J]. 计算机工程与科学，2011，33（11）：15-19.

[8] JAVIER R，VALENTíN B，ESCUDERO C J. Architecture for multi-technology real-time location systems[J]. Sensors，2013，13（2）：2220-2253.

[9] 徐玉滨，邓志安，马琳. 基于核直接判别分析和支持向量机回归的WLAN室内定位算法[J]. 电子与信息学报，2011，33（4）：13-17.

[10] MAHFOUZ S，MOURAD-CHEHADE F，HONEINE P，et al. Target tracking using machine learning and Kalman filter in wireless sensor networks[J].  Sensors Journal IEEE，2014，14（10）：3715-3725.

[11] 邱爱昆.  基于机器学习的 WiFi 高精度定位研究[D]. 无锡：江南大学，2016.

[12] 桑楠，袁興中，周瑞. 基于SVM分类和回归的WiFi室内定位方法[J]. 计算机应用研究， 2014，31（6）：52-53.

[13] 赵银龙，安胜彪. 基于核化K-means和SVM分类回归的WiFi室内定位算法[J]. 信息技术，2018（1）：26-27.

[14] 杨晋生，林振军.  一种改进支持向量机的无线定位方法[J].  应用科学学报，2017， 35（6）：685-692.

[15] FARJOW W，CHEHRI A，MOUFTAH H，et al. Support vector machines for indoor sensor localization[C]. Wireless Communications & Networking Conference. IEEE， 2011.

[16] CORTES C，VAPNIK V. Support-vector networks[J]. Machine Learning，1995， 20（3）：273-297.

[17] 张会清，石晓伟，邓贵华. 基于BP神经网络和泰勒级数的室内定位算法研究[J]. 计算机科学， 2012， 39（4）：32-35.

[18] 孙斌，姚海涛. 基于 PSO 优化 LSSVM 的短期风速预测[J]. 电力系统保护与控制， 2012， 40（5）：85-89.

[19] 马立新，王宏宇. 基于非支配解的多目标粒子群无功优化[J]. 控制工程，2014，21（5）：748-752.

[20] 申静涛. 基于 RSSI 的对数距离路径损耗模型研究[J]. 电子质量，2013（12）：15-17.

[21] MEDEISIS A，KAJACKAS A. On the use of the universal Okumura-Hata propagation prediction model in rural areas[C]. IEEE Vehicular Technology Conference. IEEE Xplore， 2000.

（责任编辑：黄 健）