基于LS-SVR的混合定位算法

夏 斌，梁春燕，袁文浩，谢 楠

(山东理工大学 计算机科学与技术学院，山东 淄博 255000)

0 引 言

准确地获取节点的位置信息是物联网应用中的基本要求。例如，智能机器人[1,2]、交通运输[3,4]等应用均需节点的位置信息。因此，精确定位的研究对物联网的位置服务应用至关重要。机器学习是利用经验来改善自身性能的一种学习方法，而最小二乘支持向量回归[5,6](least-square support vector regression，LS-SVR)作为机器学习中的一种模式，在解决小样本、非线性及高维模式识别等方面有着其特有的优势。基于LS-SVR的节点定位算法利用机器学习算法的特性，实现物联网节点定位，成为近年来一个研究热点。

文献[7]提出了基于测距的支持向量回归定位算法，采用一对一决策准则。文献[8]采用粒子群优化算法对最小二乘支持向量回归参数进行优化；文献[9]采用人工蜂群算法解决支持向量回归的参数选择问题；文献[10]提出了利用差分进化算法进行优化的LS-SVR算法等。通过不同算法与LS-SVR相结合，在定位精度方面有所改进，但没有考虑在定位过程中，未知节点之间的距离信息对定位的有效修正作用，导致得到的定位精度并不高。文献[11,12]利用未知节点间的距离信息，对传统的Taylor定位模型进行了改进。改进后的多元Taylor定位模型在定位精度上有所提高，但是算法的精度严重依赖初始值。鉴于此，本文提出了一种混合定位算法，充分发挥多元Taylor级数展开法和LS-SVR算法的优点，实现定位性能的整体最优化。

1 LS-SVR算法

LS-SVR算法的主要思想是将优化目标中松弛变量的一次惩罚项，转变成二次约束条件，从而将二次规划问题简化为较易计算的线性方程组问题，提高了计算效率。其具体步骤如下：

步骤1 设已知训练样本集T={(u1,v1),…,(uM,vM)}，其中um为输入向量，vm是输出变量(m=1,2,…,M)；

步骤2 选择核函数K(um,un)及适当的正则化参数γ(γ>0)；

步骤3 构造并求最优化问题

(1)

s.t.vm=wTφ(um)+b+ζm

(2)

其中，αm∈R。分别求L(w,b,ζ,α)对w,b,ζ,α偏微分，根据最优化条件可以得到如下线性方程

(3)

进而求出α,b解析表达式

(4)

步骤4 构造决策函数

(5)

2 基于LS-SVR的混合定位算法

传统的LS-SVR定位算法未考虑未知节点之间的距离信息在定位过程中的有效修正作用，导致定位信息不够全面，定位精度不高。因此，提出了一种基于LS-SVR的混合算法，充分利用未知节点之间的距离信息，提高定位精度。首先利用LS-SVR算法求得未知节点的初始位置，其次对构建的多元Taylor定位模型进行精确求解。具体步骤如下：

步骤1 用t×t的方格对定位区域进行网格化，得到不同的网格节点，根据网格节点的坐标以及它到锚节点的实际距离组成的距离向量，构建训练样本集。

步骤2 由于径向基(radial basis function，RBF)核函数在大样本、小样本、高维度、低维度等情况下，都能带来比较好的回归效果。并且此核函数具有较宽的收敛域，唯一最佳逼近的特性，同时在学习和训练样本过程中有较快的收敛速度。因此，我们选取RBF核函数。

步骤3 选择适当的正则化参数γ和RBF的核参数σ′2，利用LS-SVR算法对训练样本集进行学习，得到定位回归模型。

步骤4 将测量得到的未知节点到锚节点之间的距离数据输入已经建立好的定位回归模型，通过计算得到未知节点的初始值。

(6)

步骤6 利用加权最小二乘法可求解出节点位置偏差为

(7)

(8)

混合算法的流程如图1所示。

图1 混合定位算法的流程

3 仿真结果和分析

3.1 测距误差对定位误差的影响

LS-SVR算法和混合算法的定位误差随测距误差的方差变化如图2所示。从图中可得，随着测距误差方差的增加，这两种算法的定位误差也都增加，但是混合算法的定位误差却明显小于LS-SVR定位算法。这是因为多元Taylor模型在定位过程中多考虑了未知节点间的距离信息，使混合算法的定位精度相对于LS-SVR算法有明显提高。

表1 仿真参数

图2 测距误差对定位误差的影响(γ=15，σ′2=5)

3.2 定位误差的累积分布函数

如图3和图4所示，横坐标表示定位误差，纵坐标表示当前定位误差对应的累积分布函数。从图3可以看出，在90%的累积分布点，传统算法的定位误差在1.8 m以内，而混合算法的定位精度在0.5 m以内，混合算法的定位精度相比于传统算法得到进一步提高。

图3 σ2为0.5时，累积分布函数(K=4，γ=15，σ′2=5)

图4 σ2为1时，累积分布函数(K=4，γ=15，σ′2=5)

3.3 核参数的选取对定位误差的影响

图5给出了核参数对定位误差影响的曲线。当正则化参数γ一定时，增加核参数，LS-SVR定位误差显著降低，当增加到一定值时，定位误差趋于稳定。当σ′2<5时，核参数的选取影响LS-SVR定位算法的精度，而对混合算法精度的影响较小。这说明混合算法采用的多元Taylor级数展开模型充分利用未知节点之间的距离信息，减少了核参数对定位误差的影响。

图5 核参数对定位误差影响的曲线(K=4)

3.4 正则化参数的选取对定位误差的影响

图6给出了正则化参数对定位误差影响的曲线图。从图可以看出正则化参数γ的选取明显影响LS-SVR定位算法的精度，而对混合算法精度的影响较小，说明混合定位算法能减少正则化参数对定位误差的影响。

图6 正则化参数对定位误差影响的曲线(K=4)

4 结束语

物联网精确定位具有巨大的社会价值和商业价值，对基于位置服务的实现、提高人们生活质量有重要的基础支撑与保障作用。在传统LS-SVR算法基础上，通过多元Taylor级数展开法，充分利用未知节点之间的距离信息，实现未知节点位置的最优。仿真结果表明：混合定位算法在测距误差、核参数、正则化参数等评价定位性能方面，均优于传统LS-SVR定位算法。