基于改进高斯-牛顿法的NLOS 误差消除三维定位模型

刘晨

(江苏省物联网应用技术重点建设实验室(无锡太湖学院),江苏 无锡 214064)

0 引言

随着无线局域网、智能终端的高速发展以及惯性传感器的普及，人们对于位置信息的需求正在逐步增加.GPS和北斗卫星导航系统(BDS)通常用于室外定位，定位精度高，但信号在穿透固体时会受到衰减，无法实现室内的快速定位.室内三维定位过程中，无线信号在传播时易受非视距(NLOS)阻挡、多径传播、多址干扰[1]等环境因素影响，导致基站到终端传播时间的测量值与精确值之间存在误差，这些误差极大地降低了定位精度.

如何减小NLOS 环境下的定位误差是室内定位算法的研究重点.到达时间(TOA)的定位和到达时间差(TDOA)的定位[2]实现简单，并且计算精度高，是蜂窝网络定位中最常用的技术[3].距离观测在各种高精度测距定位中广泛应用，其方程为非线性函数模型.除确定待定点位置坐标参数外，再附加多余参数以精化平差函数模型，其有关平差模型都是非线性的，当平差模型的非线性强度较高时，选取不同初始值及近似正交过程，可导致线性近似引起的系数矩阵扰动和截断误差偏大，常用的测距观测方程非线性平差方法有高斯-牛顿法、扩展牛顿迭代法[4].文献[5]提出了一种NLOS 环境下接收信号强度(RSS)和TDOA 联合的信源被动定位方法，通过建立加权最小二乘模型来抑制NLOS 误差对定位精度的影响，并利用迭代法估计NLOS 误差与信源位置以提高定位精度；文献[6]提出了一种基于测距信息的加权最小二乘法定位算法，根据测量距离构建加权矩阵，但该方法忽略了链路中随机噪声的影响[7]；文献[8]基于典型的NLOS 室内环境下的信道测量，对TOA和信号接收强度的估计误差进行建模，但该方法只适合在相对较短的距离内，超出距离则无法保证室内环境的定位精度.田昕等[9]提出了基于TOA 测距下的改进扩展卡尔曼滤波器(EKF)算法.采用预测和测量比较阈值以及误差分析结合的方法完成NLOS 状态的辨识，抛弃包含NLOS 误差的测量，使用剩下的测量值实现定位[10]，这种方法在实际定位环境中会导致测量值有限，无法保证定位精度.Cheng等[11]为解决室内定位中NLOS 因素降低定位精度的问题，将锚节点分成若干组，并通过最大似然估计(MLE)获得每组目标节点的位置信息，利用NLOS 识别算法丢弃包含NLOS 误差的位置估计，通过建立多概率矩阵并结合位置估计来获得目标位置.Chen等[12]提出一种非凸鲁棒加权最小二乘问题来定位多个目标节点，并联合估计目标节点位置，将鲁棒加权最小二乘问题转化成混合半定和二阶锥规划问题.文献[13]对测量噪声建立有色噪声模型，滤波参数根据NLOS环境的恶劣情况动态调整，再结合卡尔曼滤波算法，进而实时调整滤波过程以获得最优估计，但增益系数需要提前设置.文献[14]提出了一种基于卡尔曼滤波TDOA和到达角度的混合定位算法，利用卡尔曼滤波器的估计值计算NLOS 数据的方差，通过调节卡尔曼滤波器的参数从而减小测量值的NLOS 误差，但NLOS 误差需服从指数分布，NLOS 误差分布模型又受实际地理环境的影响.

针对上述问题，本文提出一种基于高斯-牛顿法的NLOS 误差消除三维定位模型.该模型以最小二乘法为基础得到终端的估计坐标，引入遗传算法选取高斯-牛顿迭代的初始参数，并构建循环迭代，使之逐渐逼近真实目标位置，从而达到提高定位精度的目的.

1 基于测量距离的定位方法

1.1 NLOS 误差概述

理想情况下，每个基站发射携带时间戳的信号[9]，终端在接收到信号后，通过接收和发送的时间差可计算终端与基站之间距离dt，计算公式为

式中：c为光速，取值 3 ×108m/s；tr为接收到数据的时间；ts为发送数据的时间.由于NLOS 环境下观测到的无线信号传播时间有误差，会导致观测距离值大于真实距离值，即存在一个非负的测距误差.图1为不同终端个数下的观测距离值和真实距离值的误差图.

图1 观测距离值和真实距离值的误差图

当用户终端(MS)即目标位置收到4 个基站(BS)的信息(三维空间下至少需要4 个)，以4 个基站的坐标为圆心，其到终端的距离为半径可以得出4 个相交的圆，4 个圆的交点坐标即为用户终端坐标，如图2 所示.在NLOS 环境下，受NLOS 误差的影响，4 个圆的相交部分不一定是终端的准确位置，而是处于4 个圆的重叠区域，如图3 所示.

图2 理想情况下三维定位示意图

图3 实际情况下三维定位示意图

1.2 最小二乘估计初始位置

由于NLOS 下4 个以距离为半径的圆交于一片区域，终端的位置求解可转换成最优估计问题.假设终端的坐标为(x,y,z)，4 个基站的坐标分别(x1,y1,z1)、(x2,y2,z2)、(x3,y3,z3)、(x4,y4,z4)，dt1、dt2、dt3、dt4分别为终端到4 个基站之间的测量距离，计算方程为

将式(2)中的前三项分别减去第四项，可得

式(3)的矩阵形式为

式中：

由于测量距离dt有误差，式(2)中所列方程式的个数少于方程中所包含的未知量的个数，一般无相容解，则不存在满足矩阵(4)的解.引入平方误差准则函数

对式(5)求导，并令其等于0，可得最小二乘估计为

2 目标位置估计的迭代求解

2.1 高斯-牛顿法

高斯-牛顿法是一种非线性回归模型中求回归参数进行最小二乘的迭代方法，利用泰勒展开式近似代替非线性模型，然后进行反复迭代，多次修正回归系数，使回归系数逼近非线性模型的最佳系数，最后使原模型的残差平方和达到最小[15].其一般步骤为：

1)初始值的选取，给定一个初始值x0；

2)将非线性回归模型在x0附近泰勒级数展开，并忽略二阶及二阶以上偏导分量；

3)利用最小平方法估计修正因子，得到第一个迭代值；

4)对于第k次迭代，寻找一个增量Δxk，使得残差平方和达到极小值；

5)当Δx足够小时终止迭代，此时的xk作为优化结果输出，否则继续进入下一次迭代.

2.2 改进的高斯-牛顿法

高斯-牛顿法在求解局部最优解时，若参数初值选择适当，则收敛速度快且精确度较高.当估计坐标位置远离真实值或非线性强度大，测距方程出现相关病态问题时，高斯-牛顿法可能会出现迭代不收敛或收敛到错误结果[16].因此，本文基于遗传算法[17]对终端坐标初始值进行选取，得到一个全局最优近似解，并将此近似解作为高斯-牛顿法的迭代初值进行迭代搜索，最终得到精确终端坐标.遗传算法的具体实施过程是从初始种群出发，计算个体适应度，并通过复制、交换、突变、反复迭代等操作选出新一代种群，直到得到符合设定的最优解[18].合理的参数初值的选择按照适应度函数进行选取，在本文定位模型中采用的适应度函数为

选择概率为

式中，Fit(i)为个体适应值，选取适应度最高的点为初始值.具体步骤为：

1)随机选取M个图3 中重叠区域的终端坐标(xi,yi,zi)，i=1,2,3···,N，对所选初始值进行编码；

2)对输入的种群进行初始化并计算个体适应度，根据计算结果执行复制、交换、突变等操作；

3)若个体适应度值符合误差要求，则获取最优初始值，否则重复上述步骤直到样本误差满足定位要求，停止迭代；

4)将最优初始值作为高斯-牛顿法的迭代初值进行迭代搜索，最终得到精确的终端坐标.

2.3 基于改进高斯-牛顿法的定位模型

终端到基站 B Si实际距离为di，i=1,2,3···,n，在复杂的室内环境下，将测量距离减去NLOS 误差 εi，可以得di=dti-εi，i=1,2,3,···,n.基站与终端之间测量距离与实际距离之间的差值函数为

假设(x0,y0,z0)为遗传算法选取出的终端最优初始值，将式(9)在初始位置(x0,y0,z0)领域内用泰勒级数展开，忽略二阶偏导以上分量，得

式(10)中，将fi(x0,y0,z0) 表示为Fi，当测量距离与实际距离之间的差值fi(x,y,z)足够小，由式(10)可得

Δx、Δy和Δz分别为x、y和z的偏差；

3 实验与分析

为验证改进模型的定位性能，利用具有20 个基站、20×1 000 个TOA 测量数据以及1 000 个终端真实坐标的数据集进行测试.随机选取600 个待测终端的定位结果，给出如图4 所示的二维平面和如图5 所示的三维坐标图.其中，终端的实际坐标为(,,)，i=1,2,···,N，改进的定位模型的定位坐标为(xi,yi,zi)，i=1,2,···,N.由图4 可知，本文的定位模型在二维平面上几乎都可以准确定位.图5 表明本文模型在z方向上存在误差，但误差基本都在0.8 m 以内，NLOS误差消除效果显著.

图4 终端二维平面坐标图

图5 终端三维坐标图

为了进一步衡量定位性能，列出600 个待测终端在各个方向上的平均定位误差、最大定位误差、最小定位误差以及定位误差小于1 m 的概率，相应误差结果如表1 所示.

由表1 可知，在600 个测试点中，本文定位模型在x方向平均误差为0.168 m，在y方向平均误差为0.171 m，在z方向平均误差为0.719 m.定位效果在x、y、z方向上最小定位误差分别为0.006 m、0.002 m、0.014 m，效果最差的情况下定位误差分别为0.806 m、0.974 m、1.190 m，最大误差均不超过1.2 m.从实验结果可以看出，室内定位时终端z方向上的定位误差较大，但其误差小于1 m 的概率为89.2%.

表2 展示了1 000 个待测终端在各个方向上的平均定位误差、最大定位误差、最小定位误差以及定位误差小于 1 m 的概率.

表2 1 000 个测试点定位误差统计结果

由表2 可知，在1 000 个测试点中本文定位模型在x方向平均误差为0.175 m，在y方向平均误差为0.179 m，在z方向平均误差为0.721 m.定位效果在x、y、z方向上最小定位误差分别为0.001 m、0.001 m、0.014 m，效果最差情况下的定位误差分别为1.013 m、1.198 m、1.220 m，最大误差均约在1.2 m.定义三维空间的平均误差为

由式(15)可求得，1 000 个测试点在三维空间的平均定位误差为0.642 m，误差小于1 m 的概率为88.2%，误差小于1.2 m 的概率能达到96.5%，平均误差相比于文献[19]约小0.65 m.通过测试数据可知，室内三维定位较大误差出现概率相对较低，符合本文定位模型预期.此外，几种定位模型的误差累积分布函数曲线(CDF)如图6 所示，横坐标为定位精度，纵坐标为定位模型达到某一精度的概率.

图6 定位误差累积分布函数曲线图

图6 中基于最小二乘法的基本定位模型的定位误差小于1 m 的概率约为24%，文献[19]定位模型的定位误差小于1 m 的概率约为68%，本文定位模型的定位误差小于1 m 的概率约为88%.可以看出，本文定位模型比基于最小二乘法的基本定位模型和文献[19]的模型具有更好的定位精度，可以满足大部分室内定位的需求.

4 结束语

本文分析了NLOS 环境下基于测量距离定位方法的误差，针对无线传感网络进行室内定位过程中由于信号NLOS 传播而导致精度低的问题，提出一种基于改进高斯-牛顿法的NLOS 误差消除室内三维定位模型.利用最小二乘得到被测终端的初始位置，并通过遗传算法对初始位置进行选取，得到最优初始值后再用高斯-牛顿法进行迭代以细化具体位置.实验结果表明，本文所提模型可有效降低 NLOS 误差的影响，定位精度显著提高.