基于最小二乘法和BP神经网络的TOA定位算法

浦佳祺，陈德旺

(1.福州大学 数学与计算机科学学院，福建 福州 350108； 2.福州大学 轨道交通研究院，福建 福州 350108)

1 概 述

在户外的应用场景中，GPS定位技术已经得到了广泛的使用[1-2]。而到了室内，由于室内遮挡物对信号的影响，另一方面室内定位的精度要求比室外高，因此无法满足室内定位的需求。所以室内无线定位技术受到了重视并有了长足进展，例如：RFID定位[3]、超声波定位[4]、WIFI定位[5-6]等。

从技术角度来看，现代商用通信网络对于三维定位的需求，是使用尽可能少的基站完成对终端设备的定位、算法收敛速度快、对干扰和噪声具有鲁棒性等。相比于GPS等商用卫星定位系统，基于通信基站的定位问题具有如下特殊性：通信基站的目标区域是GPS等卫星定位系统无法实现定位的场景。在高楼林立的城区，建筑物内部、地下停车场等区域，GPS等系统是无法满足定位需求的。而这些应用场景基站、终端密集，是基站定位可以实现突破的地方。

常用的定位技术有到达时间(TOA)、到达时间差(TDOA)、角度到达(AOA)和接受信号强度(RSSI)等[7]。其中对TOA模型的解法有最小二乘法[8]等经典算法。而对TDOA模型，有Chan算法[9]等经典算法进行求解。对RSSI，则有BP神经网络对其进行研究[10-11]。

由于通信基站所处的电磁信号环境较之GPS等系统更加复杂，以室内环境为例，无线电信号的传播过程中会经过墙面的多次反射、室内物体的折射和吸收等。这些物理因素会导致通信基站测量得到的诸如距离、角度等信息存在噪声而产生非视距的环境。基于这些有噪声的测量，得到对于位置信息的准确估计，也是通信基站实现对终端定位需要解决的问题。对于TDOA的实现算法主要有Chan算法、Fang算法[12]和Taylor算法[13]。而这些算法的不足之处在于，Fang算法不能充分利用多个基站提供的冗余信息；Taylor算法需要一个与实际位置接近的初始值，并且运算量较大；Chan算法虽然计算快捷，但是在非视距(NLOS)环境下定位性能显著下降。而在改进方法中，有一种方法是基于Elman神经网络，对NLOS误差进行修正,再利用Chan算法定位[14]。

对此，文中提出了一种在NLOS环境下的改进算法。先通过最小二乘估计来减小NLOS环境中数据的噪声，并且获得一个与实际位置接近的初始值。之后运用BP神经网络通过训练学习，再次优化所得到的结果，从而获得最终结果。

2 算法说明

该算法考虑从减少TOA的噪声方面入手，主要由两部分组成。第一部分通过最小二乘法先去除部分NLOS环境下的噪声，第二部分通过BP神经网络训练对最后的模型进行修正。

2.1 误差项估计

考虑在非视距环境下，在极大似然估计法中基站BSi到移动端MS的距离di存在多种噪声误差，包括时间同步噪声、非视距环境噪声等，但是其主要因素应该为非视距环境噪声。TDOA/TOA测量误差的正均值通常具有随移动台与基站之间距离线性增加的趋势[15]。所以考虑在极大似然估计法中引入一个线性误差项：

di=di,real+M·di+N

(1)

其中，di,real表示第i个基站BSi到移动端MS的真实距离；M·di+N为一个线性误差项。则最小二乘法的公式转化为如下形式：

(2)

对应的方程组变为：

AX=b'

(3)

其中

(4)

X=(x,y,z)T

(5)

(6)

在保证基站个数大于6的情况下，求解上面的式子可以得到初始值(x,y,z)和线性误差项的系数M,N，这样就获得了所需要的数据。

2.2 基于BP神经网络的定位误差修正

BP神经网络的多层前馈网络应用最为普遍的是单隐层网络，己经证明单隐层的神经网络可以模拟任何连续函数。考虑定位模型的复杂度并不是太大，并且经过实验验证后，选取单隐层的三层神经网络结构作为建立的模型。

基于BP神经网络的定位误差测量值修正模型，输入层3个神经元的输入为前面一部分用带误差项的极大似然估计得到的定位的三维坐标，输出层也由3个神经元构成,为修正后得到的最终定位的三维坐标。其中有一个单隐层，wij为输入层与隐藏层之间的权值矩阵，wjk为隐藏层与输出层之间的权值矩阵。之后通过训练来修改对应的权值，以逼近想要的连续函数。

3 数据集和算法参数设置

3.1 实验平台及数据集说明

文中使用的软件为Matlab R2014a。数据集来自华为公司提供的TOA定位数据。每个场景下的数据集包括：该场景下基站的个数，每个基站的三维坐标，每个终端在该场景中每个基站记录的TOA时间。

测试数据包括5组不同场景下的TOA数据，给定的基站的x,y轴的范围是-400～400 m，z轴的范围为0～6 m。分别给20，30，40，50，60个基站的5组数据，对应每个场景分别包含1 000，1 100，1 200，1 300，1 400个移动端定位信息。

3.2 定位流程

首先对给定的数据进行预处理，用极大似然法，获得一个初步定位后的三维坐标。然后输入BP神经网络进行训练，获得最终的定位模型。

BP神经网络的实验利用Matlab的神经网络工具箱，在测试大量的参数(如隐层的节点数、隐层的个数等)后，实验参数设置为：隐层激活函数sigmoid，隐层节点个数10，单隐层。

对于5组不同场景下的数据，把这些数据抽样随机划分为两个独立的数据子集，一部分作为训练数据集，占总数据的70%，另一部分作为验证数据集，占30%。

4 实验结果分析与比较

为了验证实验结果，利用统计学中的均方根误差来检验模型的有效性。

RMSE=

(7)

首先对加入误差项的极大似然估计法与未加入误差项的极大似然估计法之间的均方根误差进行对比，如表1所示。

表1 极大似然估计法误差对比

从表1可以看出，加入线性误差项后的定位精度大大增加。不过定位误差还是超过10 m以上，仍不满足一般情况下的定位要求，所以有进一步减小误差的可能。

之后对上一步得到的结果随机划分为70%的训练集和30%的测试集，每个场景分别对这些训练集进行10次训练，训练结果的均方根误差如图1所示。

可以看到，对于训练结果，除了第五组的场景，其他场景的训练误差都小于0.5 m。而就算是训练结果最差的第五组，其训练误差也不超过1 m，说明训练效果较好。并且对每个场景而言，10次训练结果的波动范围不大，说明训练有较好的稳定性。同时通过对场景一中训练集的第1次测试结果的误差分布可知，场景一中的测试集的点数总计为770个，其中有超过半数的三维坐标误差平方和小于0.5 m，大致有600个点的误差平方和小于1，说明BP神经网络对于误差的训练十分之有效。

图1 各个场景下BP神经网络训练后的误差

对于每个场景，每组实验得到的测试结果如图2所示。可以看到，测试结果与训练结果基本上相近。除了第五组的测试误差较大，其他各个场景的测试误差都比较接近，最大的测试误差也小于1 m，可见BP神经网络有效修正了初次定位后的误差。

图2 各个场景下BP神经网络测试后的误差

同时通过对场景一中测试集的第10次测试结果的误差分布，场景一中的测试集的点数总计为330个，其中有超过半数的三维坐标误差平方和小于0.5 m，大致有300个点的误差平方和小于1。可以看出，BP神经网络对于误差的训练十分有效。其他各个场景和每次实验的测试数据的误差平方和也与之类似，大部分的误差值都小于1 m，个别测量点的误差大于1 m以上，所以就不一一展示了。

然后将定位算法的实验结果分别与Chan算法和加入误差项的极大似然估计法进行了比较。由于BP神经网络的随机性，文中算法的均方根误差使用之前10次实验的平均值作为其最后的误差平方和。具体结果如图3所示。

图3 三种方法的误差比较

三种方法在各个场景下具体误差值的比较如表2所示。

表2 三种定位方法的均方根误差值

很明显可以看出，文中算法相比经典算法，效果有着显著的提升，能够有效地把误差缩减到1 m甚至更低。这应该主要归功于BP神经网络强大的连续函数逼近能力，通过训练有效地消除极大似然定位中的误差。

最后对不同场景下测得的模型是否具有通用性进行了测试。对每个场景的模型分别用了另外4组场景的测试集进行测试，并且做了对比，选取场景五下的误差，具体如图4所示。

图4 场景五模型的测试集误差

从图4可以看出，在其他场景模型下，即使是不同场景的测试数据最后的定位误差都小于2 m，与其他两种算法相比，精确度也较高。在通过BP神经网络的训练后，提高了算法针对不同环境的普适性。所以可以通过这种方式来忽略场景的影响。

5 结束语

提出了一种基于最小二乘估计和BP神经网络的混合定位算法，该算法利用神经网络的强大非线性映射能力,修正在NLOS环境下最小二乘法的定位误差,增大了定位精度。实验结果表明，该算法定位精度高，可靠性好，定位性能好于最小二乘法和Chan算法，并且具有较强的抗NLOS误差能力，提高了针对不同环境的普适性。

参考文献：

[1] BAJAJ R,RANANWEERA S L,AGRAWAL D P.GPS:location-tracking technology[J].Computer,2002,35(4):92-94.

[2] PIKANDER M,ESKELINEN P.Differential GPS dynamic location experiments at sea[J].IEEE Aerospace and Electronic Systems Magazine,2004,19(4):36-39.

[3] JO M,YOUN H Y.Intelligent recognition of RFID tag position[J].Electronics Letters,2008,44(4):308-309.

[4] 王 凡,彭 勇.基于TDOA的室内超声波定位方法的改进[J].计算机技术与发展,2014,24(6):250-252.

[5] 肖金红,刘 智,杨 阳,等.基于CDMA-TDOA的室内超声波定位系统[J].吉林大学学报:信息科学版,2012,30(2):213-217.

[6] 黄华晋,秦建息.基于三角定位算法的WiFi室内定位系统设计[J].广西科学院学报,2016,32(1):59-61.

[7] 范平志,邓 平,刘 林.蜂窝网无线定位[M].成都：电子工业出版社,2002:80-91.

[8] 孙 瑜．射频识别(RFID)室内定位算法研究[D].成都：西南交通大学，2005.

[9] CHAN Y T,HO K C.A simple and efficient estimator for hyperbolic location[J].IEEE Transactions on Signal Processing,1994,42(8):1905-1915.

[10] 王 千,金 光,钮 俊.一种基于RSSI的混合定位算法[J].传感技术学报,2015,28(12):1823-1829.

[11] 兰雪梅,朱 健,黄承明,等.BP网络的MATLAB实现[J].微型电脑应用,2003,19(1):6-8.

[12] FANG B T.Simple solutions for hyperbolic and related position fixes[J].IEEE Transactions on Aerospace & Electronic Systems,1990,26(5):748-753.

[13] FOY W H.Position-location solutions by Taylor-series estimation[J].IEEE Transactions on Aerospace & Electronic Systems,1976,12(2):187-194.

[14] 吴燕红,关维国,王艳峰.基于Elman神经网络的TDOA定位算法[J].计算机应用,2011,31(3):629-631.

[15] 杨洪娟.蜂窝网络无线定位技术的研究[D].哈尔滨：哈尔滨工业大学,2009.