基于随机森林权重补偿的无人机高精度定位算法

方 坤, 李晓辉, 樊 韬

(1. 西安电子科技大学综合业务网国家重点实验室, 陕西 西安 710071;2. 国家计算机网络与信息安全管理中心河南分中心, 河南 郑州 450000)

0 引 言

无人机(unmanned aerial vehicle, UAV)凭借其运动灵活、可操作性大、体积小等特性在户外环境中(警务、交通管制和农场管理)有了广泛的应用,但对UAV的监管也越来越困难,因此UAV定位成为近年来的热门研究课题[1-2]。在利用移动通信基站对UAV进行定位时,由于UAV体反射信号微弱、地面障碍物所引起的多径噪声干扰以及移动通信基站设备信号功率较低等因素导致了难以对UAV进行实时无源定位[3-4]。

对UAV进行无源定位主要分为基于到达角度、图像识别和到达时间差三个方向[4-12]。Liu等[4]和Kim等[5]分别提出了非线性卡尔曼滤波算法对UAV反射信号进行载波相位处理,得到位置信息。但是在估计UAV的到达角度时,对于UAV过小所导致的角度信息误差较大问题都没有很好的解决办法。Stojcsics等[6]提出了一种热成像视觉定位算法。通过热成像检测UAV与环境的温度差,利用图像识别对目标进行定位。这种图像识别算法具有很高的UAV定位精度,但对硬件设备要求过高。Koivisto等[7]、Carrillo等[8]和Chen等[9]分别提出了改进的三边定位算法,通过获取多个基站与UAV的距离信息,建立球体,以球体交点作为目标坐标。但是,对于三边定位算法鲁棒性较差的问题都没有很好地进行解决,均需要多次平滑误差。Su等[10]提出了一种基于非线性补偿的Pilsbon算法,针对UAV信号淹没在噪声中的问题,通过改变迭代最小二乘法的线性度,将UAV定位信号的非线性共振峰效应转化为线性,进而估计目标坐标。然而,该模型只适用于特殊的环境空间,对接收基站的位置选择有较高的要求。文献[11]提出一种基于信号相似度和空间位置的K近邻(K-nearest neighbor, KNN)算法。通过平衡信道状态信息差和信号传播距离来获得UAV定位信息,但其仅适用于距离较小的场景下对于UAV信号进行重构。文献[12]提出一种基于支持向量机(support vector machine, SVM)的UAV定位算法。通过UAV定位信号的功率与相位信息映射高维空间定位,但其对UAV定位数据要求过高,且计算复杂度较高。文献[13,14]提出了基于Chan-Taylor算法的UAV定位算法,将定位结果作为泰勒算法迭代的初值,停止迭代,直到误差低于阈值,最后输出定位结果。

本文提出了一种基于随机森林权重补偿的高精度定位算法,用于对三维空间中单一UAV进行高精度定位。根据Chan-Taylor算法的误差变换和随机森林模型特征提取,推导了距离权重补偿的数值表达式。该算法主要解决了UAV定位过程中多径噪声所导致的定位误差较大问题。在多个定位接收基站的情况下,该模型利用机器学习中计算复杂度较低的随机森林对UAV反射信号数据进行特征提取,结合Chan-Taylor方法,将定位信号多径噪声转化为高斯分布并进行距离误差补偿。在得到定位结果后,对定位结果进行误差标定并校正设备误差,提高定位精度。该算法实现了对UAV的高精度定位且具有实时性和鲁棒性。

1 UAV无源定位系统

在室外较为空旷的环境下,三维定位利用现有移动通信基站广播信号对UAV进行无源定位[15]，系统模型如图1所示。UAV本身不与基站进行信号交互,仅利用移动通信广播信号作为定位信号经UAV反射到接收基站,通过提取信号特征,实现UAV定位。接收信号主要由UAV反射波和噪声组成。

(1)

在对UAV定位信号传播过程中的信号时延与相位偏移分析后,式(1)可以细化为

(2)

图1 系统模型Fig.1 System model

随机森林模型通过对大量的UAV定位数据进行分析和处理,提取出UAV信号x(t)的微弱特征并进行定位。在对UAV信号进行时差估计后得到UAV距离信息xd,因此随机森林模型[16]可建立为

h(xd,θk)=θ0+θ1x1,d+θ2x2,d+θ3x3,d+…+θkxk,d
s.t.k=1,2,…,Ndata;d=1,2,…,Ndata

(3)

式中：θk表示从UAV反射信号特征中提取的第k组数据的分类因子,Ndata为数据集的个数。θk的选择基于Gi(Di):

(4)

式中：pi表示第i种定位数据样本特征区间占整个定位信号数据集该类特征区间的比例；m表示从定位数据中提取的UAV信号特征值，即均值、方差、最小值、最大值、偏度、峰均比、均方根延迟扩展和中位数。通过这些特征的细微变化和大量数据的验证,建立随机森林模型,得到距离误差补偿参数,从而获取UAV的坐标信息。

(5)

本文的创新之处在于采用随机森林算法提取定位信息中的数据特征,并对定位数据进行分类,实现多径噪声情况下对UAV反射的微小信号提取。根据分类结果定义权重矩阵W,对UAV高度数据进行有效修正。此外,利用误差标定来校正设备误差,提高定位精度。

2 随机森林权重补偿定位算法

在多个定位接收基站对检测空间范围内的单一UAV进行定位时,随机森林权值补偿算法通过将随机噪声误差转化为高斯分布并进行去噪后,构建随机森林模型进行定位数据特征提取,获取定位权重矩阵。此外,利用标定UAV对定位结果进行误差标定,降低设备误差,提高定位精度。

2.1 随机森林定位

随机森林算法具有集成度高、建模速度与数据处理快等优点,对于UAV反射信号特征的提取具有良好的适用性。在建立随机森林模型时,通过KNN来解决如何在短时间内获取大量数据用以模型构建,保证模型实时性。此外,Chan-Taylor算法被用于将随机信号噪声转化为高斯分布,降低数据噪声,提高最终定位精度。

KNN算法定义如下:

(6)

在获得大量初始定位数据后,为了解决UAV定位数据中信号噪声过大问题,便于后续特征提取,采用Chan-Taylor算法将随机信号多径噪声转化为高斯分布[19]。

(7)

式中：Φl是Chan-Taylor算法中用于估计第l组训练数据组距离的权重(Φl取单位矩阵)；yl是第l组距离估计的输出；xl是第l组的输入数据；β是该组数据的特征系数,一般取1；nl是该组数据中UAV信号噪声。

对定位数据中的噪声进行处理后,根据定位数据的最小二乘误差,选择与数据特征(均值、方差、最小值、最大值、偏度、峰均比、均方根延迟扩展和中位数)相关的最优阈值,并对决策树节点(单棵决策数特征阈值)进行剪枝,去掉部分决策树的无用阈值分类数值,提高模型的泛化能力。此外,对决策树节点进行剪枝后,可以避免无用数据处理,降低计算复杂度[20,21]。

(8)

式中：V(k)表示所选决策树参数评价得分；Mu表示使用第u个参数后得到的定位结果精度；kc表示数据集的个数。

在选择决策树节点的过程中,Gl(S)用来表示当前定位数据与所需要分类的数据集阈值特征不一致的概率,定义如下：

(9)

式中：Gisplit(S)表示节点的划分依据,通过对Gisplit(S)交叉验证可以自适应地选择θk;Sl表示数据特征中大于训练集所选数据特征θk的数据集个数(这里认为均值、偏度、峰均比、均方根延迟扩展、极值5个数据特征中有3个大于训练集所选数据特征即可);S为数据集总数;Gl为随机森林训练过程中所使用的基尼指数[22],初始值取0.2,由小样本数据实际测试得到,在数据样本增大后,依据式(10)确定最优值。

(10)

式中：pl,f表示位置估计值定位误差小于期望精度(初始期望精度为小样本数据可以得到的最优UAV定位精度,当后续连续定位时,以训练集能达到的最优精度与当前期望精度的中间值作为新的期望精度进行更替)的位置数据样本占总数据集的比例；Dl是第l组数据集；m代表从定位数据中提取的UAV信号特征数量。

随机森林建立过程如图2所示。

图2 随机森林建立过程Fig.2 Random forest establishment process

在对随机森林进行估计后,利用二元混淆矩阵对模型进行评价[16]，如表1所示。

表1 二元混淆矩阵

表1中TP、FN、FP、TN分别表示正确分类且被正确判断、正确分类但被错误判断、错误分类但被正确判断、错误分类且被错误判断。

相对比传统的评价矩阵只以l个数据集的TP作为评价矩阵的主对角线,本文通过分别加入FP和FN作为次对角线,使得第i组训练数据和第(N-l)组训练数据同时对结果进行修正。评价矩阵如下：

(11)

使用权重补偿矩阵P与xd相乘后,得到校正的距离Rl,进一步得到Fvalue作为对UAV随机森林定位模型的评价

(12)

Si代表第i种特征下的正确率与召回率值矩阵。

在对模型进行权值补偿后,进行目标位置信息获取。首先得到距离校正参数

fi, j=1-μ(ri, j-Ri)

(13)

式中：fi, j是距离修正系数。在定位精度为Facc的情况下,设置位置误差的迭代参数μ为Facc/2,便于归一化处理,降低计算复杂度。ri, j是第i个接收基站和第j个中心基站之间的距离。Ri是利用随机森林模型对目标到接收基站的距离校正后的数据。距离校正后的权重矩阵W′定义为

(14)

将更新后的迭代矩阵W′代入式(5),估计出目标UAV的三维坐标。

2.2 误差标定

在检测空间设置一个已知UAV位置的标定目标,获取UAV与各个基站之间的距离(the distance between the UAV and each base station, BSD)和UAV运动速度(the calibration UAV moving rate, CUV)测量值来估计在定位过程中由发射基站和接收基站引起的微小定位误差[23]。

当检测到UAV进入监控区域后,校准UAV开始在检测区域飞行,通过BSD和CUV信息定位待测UAV。对已知坐标UAV进行定位,得到当前设备的定位误差[24](基站坐标误差和距离估计中的小数时延估计误差)。如图3所示。

图3 误差标定Fig.3 Error calibration

(15)

(16)

(17)

(18)

Hα=B+E

(19)

式中:H是时差估计梯度矩阵;α是UAV距离差分矩阵;B是UAV时差矩阵;E是UAV时差估计误差。

(20)

式(21)可由式(17)得

(21)

将式(20)与式(21)结合,得到

(22)

3 系统仿真

在仿真中,6个信号接收基站均匀分布在半径1 000 m的圆周上,一个发射站分布在圆中心。待定位目标是反射面小于0.02 m2的小型UAV,并依据UAV反射信号模型,增加与反射面大小相对应的反射信号功率衰减[27-30]。信号发射基站坐标为(0,0,10)。本文所提算法在Win10系统上,利用Python3.7.9进行仿真。仿真参数见表2。

表2 仿真参数

在表2中所示参数下建立随机森林模型。得到了随机森林定位模型的评价结果，如表3所示。

表3 目标坐标定位决策树的精度分析

其中召回率是正确检索到的结果占所有结果的比例,精确率是正确检索到的结果与所有实际检索到的结果的比例。检验值代表随机森林模型在各坐标轴上的评价得分,用来衡量模型是否与实际相符。Evalue代表随机森林模型在每个坐标轴上的位置估计的准确率。根据表3中的结果,模型最终的评价结果Fvalue可以达到93.05%。

考虑到UAV本身具有的移动速度慢的特点,仿真将对同一位置固定点进行多次重复定位,而单次定位所花费的时间具有偶然性且数值过小,并且该定位时间内,由于定位过程中UAV运动造成的误差转化为UAV运动的距离时,数值过小,故而本文通过对同一个点(200,200,200)处固定位置不变的UAV进行相同参数情况下的多次重复定位后,得到程序的不同算法,同样多次定位累计运行时间,并进行对比,对本文所提算法与其他算法进行复杂度对比。结果如表4所示。

表4 算法运行时间比较

在表4中的定位算法结果数据里,UAV定位时的误差分为两部分:UAV固定位置时,算法定位产生的误差;算法定位时间花费过程中,UAV在此期间运动的距离所导致的误差。而其中,由于定位时间短以及UAV运动缓慢,定位误差主要是由UAV固定位置时,算法定位产生的误差这部分构成。定位误差均值不同是由算法差异所导致的,而定位所用时间只表示不同算法对同一坐标处的UAV进行同样次数的定位所用时间。由表4可知,本文算法与文献[5]、文献[9]和文献[10]等非机器学习算法相对比,定位误差有明显降低,并且定位所用时间相差较小。本文算法与文献[11]中KNN算法与文献[12]中SVM算法这两种常用的机器学习算法进行计算复杂度对比,机器学习定位误差相近,但本文所提算法的计算复杂度有明显优势,这一点在对运动UAV进行连续定位时,可以明显降低最终定位误差。

通过Fvalue对距离数据误差进行了补偿。比较了随机森林模型在视距(line of sight, LOS)条件下和非LOS(non-LOS, NLOS)条件下与现有的其他定位算法进行了比较。

如图4所示,本文的算法在LOS和NLOS下与现有的一些算法进行了仿真比较。随着距离的增加,相应地增加了噪声误差。从总体趋势来看,该方法和其他方法的定位误差随着噪声的增大而增大。但与无迹卡尔曼滤波算法[5]、三边定位方法[9]和非线性补偿Pilsbon算法[10]相比,模型的定位精度有所提高。定位的均方根误差(root mean square error, RMSE)明显优于其他算法。

图4 UAV定位性能比较Fig.4 Comparison of UAV positioning performance

对不同运动速度的UAV进行定位,定位结果如图5所示。

图5 UAV速度变化对定位结果影响Fig.5 Influence of UAV speed change on positioning result

在直径300 m的探测空间内,随机生成41个目标点并进行定位，如图6所示。

在300 m的探测空间范围内,随机生成并定位了41个目标点。蓝色方形是实际的目标点,红色圆形是估计的坐标点。从仿真结果可以得出,该定位算法可以有效地定位目标。

图6 空间随机目标定位检测Fig.6 Spatial random target location and detection

通过改变高度和水平坐标来估计检测空间中的小目标,并获得图7所示的仿真结果。部分估计结果数据如表5所示。

图7 UAV在三维空间中的定位效果Fig.7 Positioning effect of UAV in three-dimensional space

表5 定位结果

由图7分析可以得到,在UAV高度以及水平距离变化时,定位结果的高度误差变化相对较大。随着高度增加,UAV定位误差也随着增大,分析这是由于接收基站的实际高度为0到10 m,因此在算法的定位过程中,由于Z轴值太小,导致定位结果在Z轴方向上具有较大的误差。但是仍然在可接受的误差范围内。当UAV水平距离变化时,UAV定位误差先减小后增大,这是由于UAV过于接近发射基站或离接收基站过近时,UAV与基站之间的距离和基站与基站之间的距离过于接近,导致UAV反射信号与基站之间的直接通信信号到达时间差过小,UAV反射信号淹没在基站与基站之间直接通信的信号当中,定位精度因此降低。在以大量定位结果与实际UAV坐标进行对比后,以估计的UAV坐标点为中心,计算出半径为2.6 m的球体内需要定位的实际坐标点,得到2.6 m-CEP(circular error probable)为92.4%,即代表实际UAV定位在以估计目标为圆心,半径为2.6 m的球内的概率为92.4%。该定位结果明显优于其他基于移动通信基站对UAV进行定位的算法。仿真结果表明,该定位算法能够对UAV实现高精度定位。

4 结 论

针对UAV定位中多径噪声与高度误差较大的问题,提出了一种基于随机森林权重补偿的小目标高精度定位算法,利用UAV对移动通信基站信号的反射进行特征提取,并使用标定UAV校正机器误差,实现对UAV的高精度定位。在距离误差矩阵中,我们提出了定位距离的权重校正矩阵。根据定位信号的特点,通过交叉验证得到随机森林位置模型的决策树参数。我们通过混淆矩阵和泛化误差来校正定位数据,并分配相应的权重以最终获得目标的三维坐标,在此基础上,使用标定UAV来估计设备误差,进而得到待估计UAV的坐标信息。结果表明,随机森林算法比现有的三维空间定位算法定位精度更高,满足了随机森林模型与实际的一致性。