基于ABC-SVM的室内定位方法研究

孟国华，崔英花

(北京信息科技大学 信息与通信工程学院，北京 100192)

0 引言

近年来，随着互联网技术的蓬勃发展，人们对位置信息需求量越来越大，其中对室内位置信息具有更实际的需求，因为人们生活与实际生产多数在室内进行，但是目前室内定位的精确度有待提高，有很多问题需要解决。由于信号的严重衰减和多径效应，室外定位设施在室内定位中表现较差。WiFi作为基础的定位设施是目前最常见的基于无线信号的定位方法，其他技术，如蓝牙、RFID等，也常用于室内定位，但它们普及程度不及WiFi，且使用RFID需要额外的安装硬件的花费。WiFi信号的设计初衷并不是为了定位，因此在单天线、窄带宽、复杂的信号传播环境中，传统的基于到达时间(time of arrive,TOA)和基于到达时间差(time difference of arrive,TDOA)的测距方法，以及基于到达信号角度(angle of arrive,AOA)[1]的方法难以实现，因此目前广为应用的是位置指纹法。最常用的信号特征是RSSI(received signal strength indication)。机器学习方法可以构建特征RSSI与位置坐标的非线性映射模型。通常使用的机器学习方法有k最近邻算法(k-nearest neighbor, kNN)、逻辑斯蒂回归(logistic regression, LR)、支持向量机(support vector machine, SVM)[2]。kNN算法对训练数据依赖程度高，效率较低，定位实时性较差；LR算法容易欠拟合，定位精度不高；SVM算法在解决小样本、非线性以及高维空间问题中具有较大优越性[3]。

在SVM理论应用过程中，决定SVM性能的因素都是参数的选择，尤其是引入核函数后，参数的选择更为重要。为使训练模型具有更好的泛化能力，参数的寻优选择是必要的。目前，已有众多人工智能算法应用于SVM参数优化中，如遗传算法(genetic algorithm,GA)、蚁群算法(ant colony optimization,ACO)、粒子群算法(particle swarm optimization,PSO)和果蝇算法(fruit fly optimization algorithm,FOA)[4]。文献[5]证明GA优化比网格优化定位更精确，更符合实时性要求；文献[6]采用蚁群算法优化支持向量机的参数,能够有效地进行分类。上述优化方法在寻优过程中可能会陷入局部最优，无法得到全局最优。人工蜂群算法是一种新的群体智能算法,通过模拟蜂群分工寻找花蜜的原理，解决多维优化问题，具有较好的优化机理和收敛性能[7]。本文在室内定位过程中的离线阶段，利用人工蜂群算法优化SVM参数，得到预测模型ABC-SVM，将此模型与PSO-SVM、ACO-SVM两种预测模型进行对比，可以看出ABC-SVM模型可以在室内定位中得到更高的定位精度。

1 算法介绍

1.1 支持向量机

设收集到的定位样本训练集为{(xi,yi)}(i=1,2,…,n)，支持向量机的回归函数为

f(x)=wT·x+b

(1)

在精准度为ε的情况下，假定存在一个函数能对每个数据进行逐个估计，将w的最小化进行转换，形成一个新的凸优化的问题：

(2)

(3)

通过给每一个约束条件加上一个拉格朗日乘子α，定义拉格朗日函数为

(4)

求解其对偶问题可得:

(5)

将式(4)求偏导，得到回归函数为

(6)

当训练数据是非线性时，要将原来的输入空间映射到一个高维特征空间，而核函数的优点就在于不需要直接处理高维特征空间，可以解决可能出现的“维数灾难”问题[8]，此时优化目标函数就可以通过核函数表示，式(5)就转化为

(7)

与之对应，回归函数相应变化为

(8)

1.2 人工蜂群算法

人工蜂群算法(artificial bee colony,ABC)是近年出现的较为新颖的群体智能优化算法，是一种模拟蜂群分工寻找花蜜的原理来解决多维优化问题的群集智能算法[9]。通过各蜜蜂的局部寻优行为，最终使全局最优值凸显出来，从而进行实参优化。

人工蜂群分为采蜜蜂、观察蜂和侦察蜂[10]。随机产生相当于食物源位置的NP个优化解的初始值，NP为蜂群规模；每个侯选优化解Xi(i=1,2,…,NP)是一个D维的向量，D为待优化解中参数个数。初始化后，采蜜蜂、观察蜂和侦察蜂将进行kmax次循环寻找食物源的搜索过程，为最大迭代次数。每个蜜源的位置代表问题的一个可能解，蜜源的花蜜量对应于相应解的适应度，采蜜蜂与蜜源是一一对应的，采蜜蜂依据式(9)寻找新蜜源：

vij=xij+φij(xij-xkj)

(9)

式中：i∈{1,2,…,D},k∈{1,2,…,NP},且满足k≠i；φij为[-1,1]之间的随机数。ABC算法将新生成的可能解与原来的解进行比较，采用贪婪选择保留较好的解，观察蜂依据概率选择蜜源，概率为

(10)

式中F(i)为第i个解的适应度。如果被发现食物源的花蜜太劣质，它将被侦察蜂随机寻找新的食物源来代替。侦察蜂通过式(11)搜索新的可能解:

(11)

1.3 ABC优化SVM参数

在SVM回归预测模型中，惩罚参数C和核函数参数δ与SVM的性能直接相关，因此参数的优化选择对SVM的预测精度影响很大。目前，优化SVM参数常用的方法有遗传算法、粒子群优化算法等，但这些算法在寻优过程中会陷入局部最优，人工蜂群算法可兼顾局部最优解和全局最优解[11]。因此采用ABC算法优化SVM参数，能够有效地提高预测精度和效率。

2 ABC-SVM的室内定位算法

ABC-SVM的室内定位算法分为两个阶段：

1)离线阶段：在待定位区域放置若干锚节点，通过采集各位置点的RSSI信息作为该位置的特征数据，称为位置指纹，然后将所有位置指纹保存到数据库中，得到一张无线电地图，进而将得到的训练样本进行支持向量机训练，采用人工蜂群算法优化支持向量机参数，得到最优支持向量机训练模型。

2)在线阶段：将待定位点的特征RSSI输入离线阶段所得的训练模型中，可得出待定位点的位置坐标。

基于ABC-SVM的室内定位流程如图1所示。算法具体的实现过程如图2所示。

3 实验仿真及分析

3.1 实验数据

在众多文献中，往往在实际场地内布置设备进行测量，使用实测数据分析和验证各定位算法的性能，但实际测量的工作量较大且灵活性较小，所得数据不全面，因此本文通过仿真的方法获取RSSI数据[12]。射线跟踪技术的部分仿真参数设置如下：房间的长度为20 m，宽度为15 m，高度为4 m，其中信号频率为2400 MHz，位置点间隔为0.01 m，AP个数为6，坐标分别为(1,1)、(10,1)、(19,1)、(1,14)、(10,14)、(19,14)，默认信号源的高度为1 m，使用射线跟踪计算相应位置的RSSI，返回的是一个三维数组，即数据集为1999×1499×6，第一维和第二维是房间尺寸，第三维代表不同的AP，记录计算出的RSSI值，就得到RSSI仿真环境数据集。

数据集的部分数据如表1所示。

表1 RSSI数据

3.2 实验结果与分析

从数据库中选择100组数据进行仿真预测。本实验应用的PC机试验环境为Windows8操作系统和MATLAB R2016b。设置SVM参数的搜索范围是(0.01,1000)，经过多次实验，ABC初始化参数设置如下：群体数量为20，蜜源数量是群体数的一半，即为10，最大搜索次数为100，最大迭代次数为800。

定位精度是评价不同定位算法性能优劣的普遍标准，其衡量方法主要是定位误差和累计分布函数。

定位误差为待定位点的估计位置与实际位置之间的欧氏距离：

(12)

式中：(xt,yt)为估计位置坐标；(x0,y0)为实际位置坐标。

累积分布函数(cumulative distribution function,CDF)为定位误差小于某个值的概率：

F(E0)=P(E

(13)

图3是ABC-SVM模型与SVM模型关于预测样本的定位误差对比，由图可以直观地看出，ABC-SVM模型的定位误差主要集中在1～2 m之间，而SVM模型的定位误差大部分大于1.5 m。ABC-SVM模型在2 m内的定位精度达到86%，SVM大约是60%。因此就定位误差方面而言，相比于传统SVM预测模型，基于ABC-SVM预测模型的定位精度更高。

此外，为验证模型的有效性，分别建立ABC-SVM、PSO-SVM及ACO-SVM三种预测模型对坐标值进行预测。对3种预测模型进行仿真，对比结果如图4所示。从图中可以看到，ABC-SVM 模型的定位精度最高，相比 PSO-SVM和 ACO-SVM 模型，优势明显。这是由于PSO和 ACO 算法在参数寻优的过程中，会不同程度地陷入局部最优解，而ABC 算法能够兼顾局部最优和全局最优，可以有效地避免陷入局部最优。

4 结束语

为了提高室内定位的精度，将机器学习中的支持向量机算法应用到定位过程中，而在SVM回归预测模型中，惩罚参数C及核函数参数δ与SVM的性能直接相关，参数的优化选择对SVM的预测精度影响很大；此外相比于传统优化算法，人工蜂群算法可同时对局部最优解和全局最优解进行搜索。因此本文提出一种基于人工蜂群算法优化SVM参数的定位模型ABC-SVM。仿真实验表明，该算法的定位误差小于SVM算法及传统的PSO-SVM和ACO-SVM模型，具有更高的定位精度。由于训练时间会随着训练样本的增多而增加，今后需要进一步研究如何减少模型训练时间，又因相比于其他群智能算法，ABC算法提出的时间比较短，改进ABC算法也是未来的研究方向。