基于LS_SVM的超宽带定位算法
  计算机系统应用  2018, Vol. 27 Issue (8): 237-240   PDF    
基于LS_SVM的超宽带定位算法
程启国     
江南大学 轻工过程先进控制教育部重点实验室, 无锡 214122
摘要:针对超宽带在非视距环境下测距误差大引起定位误差较大的问题, 提出了一种基于最小二乘支持向量机支持向量机(Least Squares_Support Vector Machine, LS_SVM)算法的测距误差处理. 该方法将室内区域划分为多个相等的小区域, 建立每个区域的采样信号的特征值和节点位置的非线性关系, 利用LS_SVM对其进行分类和回归进行定位, 对于非视距测距结果赋予较小的一个权重. 实验仿真表明, 相比K邻近算法(K-Nearest Neighbors, K-NN)误差精度在7 cm内提高10%, 说明本算法能够有效的提高定位精度.
关键词: 超宽带    定位    支持向量机    误差消除    
Ultra-Wideband Location Algorithm Based on LS_SVM
CHENG Qi-Guo     
Key Laboratory of Advanced Process Control for Light Industry (Ministry of Education), Jiangnan University, Wuxi 214122, China
Foundation item: Joint Research Project on Joint Venture Capital of Jiangsu Province (BY2014023-31); Project for Six Kinds of Talents of Jiangsu Province (WLW_007)
Abstract: Designated to solve the problem of large positioning error caused by large ranging errors in the non-line-of-sight (UWB) environment, a tracking error based on Least Squares Support Vector Machine (LS_SVM) is proposed. The method divides the indoor area into several equal small areas, establishes the non-linear relationship between the eigenvalues of the sampled signals and the node locations in each area, classifies and regulates them by using LS_SVM. For non-line-of-sight distance measurement results, a smaller weight is given. Experimental results show that the error of K-Nearest Neighbors (K-NN) is improved by 10% within 7 cm, which shows that this algorithm can effectively improve the positioning accuracy.
Key words: UWB     location     support vector machine     error elimination    

近年来, 随着不断对无线传感器网络(Wireless Sensor Networks, WSN)技术的需求增加, 其中在安全救援, 监狱管理, 资产跟踪和室内导航等领域应用的越来越广泛[1]. 全球定位系统(Global Positioning System, GPS)能够定位, 但是GPS信号受到建筑物或者其它障碍物阻挡, 导致定位精度不高[2], 而脉冲超宽带(Impulse Radio-Ultra WideBand, IR-UWB)具有时间分辨率高, 抗多径干扰能力比较强, 功耗低, 安全性能高, 定位精度高等优点, 已成为室内定位重要方法之一[3].

由于室内环境比较复杂, 信号容易受到多径干扰, 墙壁的阻挡与反射等, 给节点定位误差较大, 因此在非视距(Not Line of Sight, NLOS)环境下对室内定位误差降低具有一定的重要性[4,5]. 文献[6]在室内环境下, 验证了视距环境下的定位精度比非视距定位精度高, 并没有说明在NLOS环境下如何降低定位误差. 文献[7]对于脉冲超宽带定位精度不高, 提出了一种联合分布式同步定位方法, 减少估计位置的不确定性, 但是对硬件要求比较高. 文献[8]提出了在NLOS环境下基于卡尔曼滤波器和到达时间差/到达角混合定位算法的定位, 随着到达角测量值的精度降低, 定位误差越高.

本文提出了一种LS_SVM的超宽带测距误差处理, 利用LS_SVM对采样到的信号特征值进行分析, 判断接收信号是否为视距。与支持向量机相比, 本文对于非视距采样信号测距加一个较小的权重以纠正测距误差. 降低定位误差. 结果表明, LS_SVM算法对于室内定位精度更精确.

1 超宽带信号特征

发射脉冲超宽带进行室内定位时, 信号经过多径传播及穿透障碍物, 接收机接收到的信号表示为:

$h\left( t \right) = \sum\limits_{i = 1}^N {{a_i}p\left( {t - {\tau _i}} \right)} + n\left( t \right)$ (1)

式中, N为多径分量的个数. ${a_i}$ ${\tau _i}$ 为信号分量的幅度和时延. $n\left( t \right)$ 为高斯白噪声, 均值为0. $p\left( t \right)$ 位发射机发射的高斯窄脉冲, 信号采样间隔 ${T_s} = 60\;{\rm{ns}}$ .

(1)采样信号最大幅度: 在视距环境下, 接收机接收到的采样信号能量比较集中, 幅度最大值会在直达径分量周围, 与其他的分量比较, 幅度差异比较明显. 在非视距环境下, 接收机接收到的采样信号能量比较分散, 幅度跟视距环境下没有那么明显区别.

$r = \max \left| {h\left( t \right)} \right|\;\;\;\;$ (2)

(2)采样信号均值

$u = \frac{{\sum\limits_{i = 1}^N {h\left( {n{T_s}} \right)} }}{N}$ (3)

(3)采样信号方差

${\sigma ^2}{\rm{ = }}\frac{{\sum\limits_{i = 1}^N {{{\left( {h\left( {n{T_s}} \right) - u} \right)}^2}} }}{N}$ (4)

(4)能量: 随着测距的增加, 信号能量会逐渐衰减. 视距环境下, 接收到的采样信号能量大部分都集中在直达径附近, 非视距环境下, 信号能量没有那么集中.

$E = {\int_T {\left| {h\left( t \right)} \right|} ^2}dt$ (5)

(5)峭度(kurtosis): 反映接收机接收到信号陡峭程度. 假如信号峭度越大说明信号波形陡峭, 有较大的峰值, 波形能量越集中, 说明直达径的分量是最强. 如果峭度较小说明直达分量比较弱, 直达分量受到较大的干扰.

$k = \frac{{E\left[ {{{\left( {{{\left| {h\left( t \right)} \right|}^2} - {u_{\left| h \right|}}} \right)}^4}} \right]}}{{\sigma _{\left| h \right|}^4}}$ (6)

(6)超量时延(Mean Excess Delay, MED): 多径分量的时延扩展, 时延越大说明采样信号的多径分量比例比较大, 直达分量相比比较弱.

${\tau _{\rm{MED}}}{\rm{ = }}\frac{{\int_T {t{{\left| {h\left( t \right)} \right|}^2}dt} }}{{\int_T {{{\left| {h\left( t \right)} \right|}^2}dt} }}$ (7)

(7)均方根时延(Root Mean quare delay Spread, RMS): 描述一个信号的时延特性和时间色散程度的重要参数.

${\tau _{\rm{RMS}}}{\rm{ = }}\frac{{\int_T {{{\left( {T{\rm{ - }}{\tau _{\rm{MED}}}} \right)}^2}{{\left| {h\left( t \right)} \right|}^2}dt} }}{{\int_T {{{\left| {h\left( t \right)} \right|}^2}dt} }}$ (8)

(8)距离估计值 $\hat d$ : 测距误差与测距大小也有一定的关系.

对每一个接收到的采样信号计算以上8个信号特征, 并将它们组成一个多维向量, 表示采样信号畸变程度, 设为向量 ${X}$ :

${X} = \left[ {r,u,{\sigma ^2},k,{\tau _{\rm{RMS}}},{\tau _{\rm{MED}}},E,\hat d} \right]$ (9)
2 基于最小二乘支持向量机误差处理 2.1 非视距鉴别

输入采样数据为: $T{\rm{ = }}\left\{ {\left( {{{X}_1},{y_1}} \right),\left( {{{X}_2},{y_2}} \right), \cdots, \left( {{{X}_N},{y_N}} \right)} \right\}$ $y \in \left\{ { + 1, - 1} \right\}$ , +1和–1分别表示为LOS和NLOS情况. 回归器对于采样数据构造一个线性回归函数:

$y\left( x \right) = {W^{\rm T}}\varphi \left( x \right) + b$ (10)

那么采样的样本点都在这个超平面附近, 即可以求解为:

$\left\{ \begin{gathered} \begin{array}{*{20}{c}} {\arg }&{\begin{array}{*{20}{c}} {\mathop {\min }\limits_{w,b,e} }&{\frac{1}{2}} \end{array}} \end{array}{\left\| w \right\|^2} + \gamma \frac{1}{2}\sum\limits_{k = 1}^N {e_k^2} \\ \begin{array}{*{20}{c}} {\rm{s.t.}}&{{y_k} = \phi \left( {{x_i}} \right) \cdot w + b + {e_k},\forall k} \end{array} \\ \end{gathered} \right.$ (11)

式中, $\gamma $ 为惩罚因子. 通过引入Lagrange函数来优化问题:

$L = \frac{1}{2}{\left\| w \right\|^2} + \frac{1}{2}\gamma \sum\limits_{k = 1}^N {e_k^2} - \sum\limits_{k = 1}^N {{\alpha _k}} \left( {\varphi \left( {{x_k}} \right) \cdot w + b + {e_k} - {y_k}} \right)$ (12)

对拉格朗日公式, 分别对 $w,b,e$ $\alpha $ 求偏导数, 得:

$\left\{ \begin{gathered} w = \sum\limits_{k = 1}^N {{\alpha _k}\left( {{\varphi _k}} \right)} \\ \sum\limits_{k = 1}^N {{\alpha _k}} = 0 \\ {\alpha _k} = \gamma {e_k} \\ w\varphi \left( {{x_k}} \right) + b + {e_k} - {y_k} = 0 \\ \end{gathered} \right.$ (13)

消除 $e$ $w$ , 得到一个线性方程组:

$\left( {\begin{array}{*{20}{c}} 0&1& \ldots &1 \\ 1&{K\left( {{x_1},{x_1}} \right) + \frac{1}{\gamma }}& \ldots &{K\left( {{x_1},{x_k}} \right)} \\ \vdots & \vdots & \vdots & \vdots \\ 1&{K\left( {{x_k},{x_1}} \right)}& \ldots &{K\left( {{x_k},{x_k}} \right) + \frac{1}{\gamma }} \end{array}} \right) \cdot \left[ {\begin{array}{*{20}{c}} b \\ {{\alpha _1}} \\ {{\alpha _2}} \\ \begin{gathered} \vdots \\ {\alpha _k} \\ \end{gathered} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 0 \\ {{y_1}} \\ {{y_2}} \\ \vdots \\ {{y_k}} \end{array}} \right]$ (14)

用最小二乘求出 ${\alpha _i}$ $b$ , 进而得到回归函数表达式:

$y\left( x \right) = \sum\limits_{k = 1}^N {{\alpha _k}K\left( {x,{x_k}} \right)} + b$ (15)

式中, $K\left( {x,{x_k}} \right)$ 为核函数.

2.2 误差处理

由于室内定位环境复杂性, 导致接收机接收到信号会有所一定的误差. 在LOS的环境下, 直达分量能量最强且第一个被接收机接收到, 因此进行到达时间(Time of Arrival, TOA)估计, 测距误差低. 在NLOS的环境下, 由于墙壁或者其它东西阻挡和多径影响加强, 导致信号畸变和信号衰减, 使接收机接收到的直达径的信号不是最强信号和不是第一时间到达的, 会导致TOA估计精度降低, 从而使测距产生较大的误差.

根据LOS和NLOS鉴别结果, 我们采取对非视距测得结果加上一个权重, 这个权重为实际距离与回归误差的差, 即为: $\hat d = d + \Delta d$ .

Step 1. 构建样本库: 记录接收机接收到的波形和测距误差.

Step 2. 提取特征值和真实误差: 提取采样信号中的波形畸变量 ${X}$ , 记录真实误差 ${y_i}$ 得到训练集 $T = \left\{ {\left( {{{X}_1},{y_1}} \right),\left( {{{X}_2},{y_2}} \right),\cdots,\left( {{{X}_N},{y_N}} \right)} \right\}$ .

Step 3. 选取合适的核函数: 在室内环境下, 选取的核函数为:

$K\left( {x,{x_i}} \right) = \exp \left\{ {\frac{{ - \left\| {x - {x_i}} \right\|}}{{2{\sigma ^2}}}} \right\}$ (16)

式中, $\sigma $ 一般取值为2, 惩罚因子初始值为3.

Step 4. 样本预处理: 将采样点信号进行训练, 对非视距的信号测距结果赋予一个较小的权重.

Step 5. 测试样本: 将采样数据点的波形畸变量, 带入到回归器中, 得到回归误差. 然后以实际的误差减去回归器得到的误差, 即为消除的误差.

根据最小二乘支持向量机, 其消除误差步骤按图1所示.

图 1 LS_SVM误差消除

3 仿真与分析

仿真场景设置如图2所示, 在两个相邻的房间进行测距, 超宽带节点固定, 采样信号, 标签防止网格的位置中, 标签发出的的信号受到有墙壁的阻挡, 接收机接收采样信号在视距和非视距会出现多种波形. 为了避免采样信号的偶然性, 我们在每个网格点测试一百次信号, 其中五个为一组, 然后将五个数取平均数作为一个数, 这样一个待测点, 二十次测距, 记录测距波形与实际测距误差.

图 2 定位场景图

对NLOS或LOS的准确率, 定义检测概率 ${P_c} =$ $ P\left( {NLOS/NLOS} \right)$ , 虚警概率 ${P_{fa}} = P\left( {NLOS/LOS} \right)$ . 图3为不同特征值的对NLOS的鉴别准确性, 当采用所有的特征值进行训练, 训练出来的模型具有良好的性能, 检测概率位97.4%, 虚警概率2.5%.

图 3 不同特征鉴别率

图4为文中算法与SVM算法、K-NN累积分布图, 经过非视距的鉴别, 在同一信噪比使用大量的采样数据进行训练, 测距在误差7cm范围, LS_SVM算法比K-NN算法提高10%. 能够有效的提高了定位误差.

图 4 消除误差累计分布

图5为在不同信噪比的条件下, 同一标签未使用LS_SVM算法校正前和使用LS_SVM算法校正后的均方根误差图. 随着信噪比的增加, 测距误差都会明显降低. 使用LS_SVM 算法比原始的测距定位精度提高.

4 结论

本文针对在非视距环境下定位误差大, 提出了一种LS_SVM算法在非视距误差处理. 利用采样数据在机器学习算法下训练得到一个训练结果, 无需对对信道统计特征进行分析, 实用性强. 理论分析和实验仿真表明, 该算法有效的降低测距误差, 从而提高定位精度.

图 5 不同信噪比定位误差

参考文献
[1]
蒙静, 张钦宇, 张乃通, 等. IR-UWB定位系统距离误差建模及性能研究. 通信学报, 2011, 32(6): 10-16. DOI:10.3969/j.issn.1000-436X.2011.06.002
[2]
杨德君. 室内精确定位导航系统的设计与实现[硕士学位论文]. 北京: 北京邮电大学, 2011.
[3]
Soganci H, Gezici S, Poor HV. Accurate positioning in ultra-wideband systems. IEEE Wireless Communications, 2011, 18(2): 19-27. DOI:10.1109/MWC.2011.5751292
[4]
张然, 宋来亮, 冉龙俊. 一种基于非视距误差补偿的协同定位算法. 北京航空航天大学学报, 2017, 43(7): 1426-1432.
[5]
Savic V, Larsson EG, Ferrer-Coll J, et al. Kernel methods for accurate UWB-based ranging with reduced complexity. IEEE Transactions on Wireless Communications, 2016, 15(3): 1783-1793. DOI:10.1109/TWC.2015.2496584
[6]
吴绍华, 张钦宇, 张乃通. IR-UWB测距中NLOS状态的鉴别. 电子与信息学报, 2008, 30(11): 2541-2546.
[7]
Denis B, Pierrot JB, Abou-Rjeily C. Joint distributed synchronization and positioning in UWB ad hoc networks using TOA. IEEE Transactions on Microwave Theory and Techniques, 2006, 54(4): 1896-1911. DOI:10.1109/TMTT.2006.872082
[8]
刘琚, 李静. 一种在非视距环境中的TDOA/AOA混合定位方法. 通信学报, 2005, 26(5): 63-68. DOI:10.3321/j.issn:1000-436X.2005.05.010