0 概述

随着现代通信技术和TDOA定位技术的快速发展, TDOA定位技术凭借其独特的优势成为最流行的定位方法之一。如何准确高效地求解TDOA定位技术中的定位方程组, 得到移动节点的解坐标是实现准确定位的根本, 因此定位求解算法成为研究热点。本质上, 求解TDOA定位方程组就是求解一组非线性方程, 是一个复杂的非线性寻优过程。求解非线性方程的方法有很多, 遗传算法(GA)是一种基于生物界规律和自然遗传机制的并行搜索算法^[1]。GA是通过模拟自然进化过程, 在潜在存在解的空间中搜索最优解的优化算法^[2], 但在应用该算法过程中, 交叉率和变异率可能导致优质个体遭到破坏, 对解的质量造成严重影响并且可能导致结果不收敛。最优保存策略也是优化算法中的一种, 且其在人工智能^[3]、工程计算^[4]等领域均得到了应用。FANG算法^[5]只能用于3个基站对目标平面位置进行确定, 不能充分利用冗余的TDOA测量值。FRIEDLANDER算法^[6]、SX算法^[7]、SI算法^[8]均忽略了变量之间的相关性, 不能达到最优估计。在TDOA的测量值误差满足理想的高斯分布的情况下, CHAN算法^[9]可以达到理论最优值, 若TDOA测量值中包含非视距误差, 则该算法的性能将会显著下降。Taylor算法^[10]需给定一个与实际位置较为接近的初始迭代值, 否则无法保证算法的收敛。文献[11-12]的仿真结果表明, 在实际蜂窝网通信系统中, 解析法中定位性能最好的2种算法为CHAN算法与Taylor算法。

在实际定位环境中, 多径干扰现象普遍存在, 这将会在TDOA测量值中引入非视距误差, CHAN算法在这种情况下不再适用。因此, 相比于CHAN算法, Taylor算法更加适合在实际定位环境中应用。Taylor算法是求解非线性方程的有效方法, 具有精度高等特性^[13]。目前, 已经实现Taylor算法在TDOA二维定位中的应用且取得了很好的求解效果, 但将Taylor算法在TDOA三维定位中应用时, 在某些情况下, Taylor算法会出现大面积无法求解的现象。因此, 找到一种更好的求解算法对于实现高精度的三维定位是十分必要且有意义的。

本文对TDOA三维定位的求解算法进行研究, 开发TDOA三维定位算法仿真软件并对Taylor算法在TDOA三维定位中的应用进行仿真实验。在分析Taylor算法应用受到限制的基础上, 为实现高精度的TDOA三维定位, 本文提出将列文伯格-马夸尔特(Levenberg-Marquardt, LM)算法作为TDOA三维定位的求解算法来弥补Taylor算法的缺陷和不足, 并且在不同的TDOA三维定位模拟环境中进行仿真实验, 对比Taylor算法和LM算法的性能。

1 Taylor算法在TDOA三维定位中的应用

二维定位只能够显示出目标的平面位置, 而三维定位可以显示出目标的空间位置。TDOA三维定位可以实现室内高精度的定位, 这需要一种优良的求解算法来解算一组TDOA三维定位方程组, 而该方程组是由几个非线性方程所组成, 因此可以理解为求解一组非线性方程组。

目前求解非线性方程的典型方法是迭代算法, Taylor算法作为一种典型的迭代算法, 在一般情况下均可以求得较为准确的非线性方程组结果。但该方法需要一个初始值作为Taylor算法执行的初始点, 初始值的选择需要接近真实值以防止泰勒级数收敛到局部最优^[14]。若选择的初始值不恰当, 计算量将会增大且可能导致不收敛, 将会无法得到移动节点的准确位置。Taylor算法在TDOA二维定位中取得了良好的求解效果, 但将该算法应用到TDOA三维定位时, 在定位现场的复杂环境下其应用受到多种条件的限制, 导致不能准确可靠地求得移动节点的解坐标。针对这一问题, 利用TDOA三维定位算法仿真软件对Taylor算法在TDOA三维定位中的应用进行仿真分析。仿真实验中, 在仿真软件中设置4个定位基站的初始坐标, 主基站A(200, 200, 200)、从基站B(600, 200, 600)、从基站C(200, 600, 200)、从基站D(600, 600, 200), 将移动节点的Z坐标设置为固定值, 层高的设置值就是Z坐标的值, 将X坐标和Y坐标的取值范围都设定为0 cm~800 cm, X、Y、Z的初始点坐标为(0, 0, Z), 将X和Y的步距设为40 cm, 参与定位计算的目标点总共有441个, 每当得到一个移动节点的坐标(X, Y, Z)后, 就分别计算(X, Y, Z)到4个基站的距离, 进而计算得到距离差, 这个距离差在实际定位中是由时间差计算所得。在距离差上加上设定的白噪声得到新的距离差, 利用白噪声模拟工况下的实际噪声。再将新的距离差作为已知条件应用到TDOA定位方程组的求解当中, 利用Taylor算法计算得到移动节点的定位坐标(X^*, Y^*, Z^*), 用(X, Y, Z)与(X^*, Y^*, Z^*)之间的距离表示定位误差。

Taylor算法的流程如图 1所示。

1.1 迭代步距对Taylor算法的影响

基站的初始坐标不变, 将移动节点的Z坐标值设定为350 cm, 白噪声的取值范围设定为-5 cm~5 cm。实验对Taylor算法在迭代步距分别为0.1、0.3、0.5、0.7、0.9、1.0、1.5时进行仿真, 将不同迭代步距下的仿真结果分为20组, 在相同条件下, 每组进行100次仿真实验, 将100次仿真结果的平均值作为该组最终的仿真结果, 结果如图 2、图 3所示。Taylor算法在求解TDOA定位方程组的过程中, 求解逆矩阵失败代表求解失败, 也就意味着不能求得移动节点的定位坐标(X^*, Y^*, Z^*)。在每一个迭代步距下进行100次仿真实验, 记录每一次的运行时间, 将仿真结果的平均值作为最终结果, 如图 4所示。

由图 2可知, 在相同的初始条件下, 当迭代步距为0.1、0.3、0.5、0.7时, 求解失败的点数较少且相差不大, 随着迭代步距的继续增加, 求解失败的点数明显增加, 这说明无法求得移动节点定位坐标的范围增大。由图 3可知, 随着迭代步距的增加, 定位结果的精度呈降低趋势。图 2和图 4表明, 在误差范围允许的情况下, 迭代步距越小, 可以求得移动节点坐标的概率越大, 但是增加了计算量和计算时间, 这说明Taylor算法在TDOA三维定位中的应用在很大程度上受到迭代步距的影响。

1.2 基站布局对Taylor算法的影响

在仿真实验的基础上只改变从基站D的坐标为(600, 600, 600), 其他条件保持不变, 在相同的层高和噪声条件下, 在每一个迭代步距下进行100次仿真, 将仿真结果的平均值作为最终结果。结果发现, 当迭代步距为0.1、0.3、0.5、0.7、0.9、1.0、1.5时, 参与定位的441个点全部求解失败。

在相同的层高与迭代步距条件下, 在不同的噪声下进行100次仿真, 将仿真结果的平均值作为最终结果。结果发现, 当噪声分别为10、20、30、40、50、60、70时, 参与定位的441个点全部求解失败。

仿真结果表明, 当基站C和基站D的高度相同时, 由于基站布局的变化, Taylor算法在不同的迭代步距及噪声条件下, 参与定位的441个点全部求解失败, 不能求得移动节点的坐标位置。因此Taylor算法在TDOA三维定位中的应用受到基站布局的严重影响。为了降低外部环境对定位结果的影响, 避免出现大范围求解失败的现象, 提高定位解的精度, 本文提出将LM算法作为TDOA三维定位的求解算法并进行仿真验证。

2 LM算法在TDOA三维定位中的应用分析

对于求解非线性方程得到最优解来说, 除了Taylor算法以外, 典型方法还有梯度下降算法、高斯牛顿算法以及LM算法。

梯度下降算法是求解最优化问题的最重要、最基础的方法, 其一般求解步骤为:

步骤1  根据h=－γJ^T_ke_k, 求解迭代步距h。

步骤2  采用x_k+1=x_k+h进行新的迭代。

步骤3  若|G(x_k+1)－G(x_k)| < ε, 其中ε足够小, 则认为G(x)收敛, 退出迭代, 否则重复步骤1。

在利用梯度下降算法寻找非线性方程的最优解时, 并不是在任何条件下均可以得到方程的全局最优解。该算法的实现存在前提条件, 首先, 要确保目标函数G(x)是凸函数且是可收敛的, 若目标函数G(x)不是凸函数, 梯度下降的最终点就有可能不是全局最小点^[15]。其次, 该算法的收敛速度以及最优解的质量受到迭代步距的影响, 迭代步距较小时, 该算法将会收敛得较慢, 而迭代步距过大时, 该算法会使得结果偏离最优解。

高斯牛顿算法被广泛应用于非线性方程的求解问题, 该算法的逻辑过程是使用目标函数的泰勒级数展开式近似地代替已有的非线性回归模型, 然后循环迭代、修正参数, 直至达到最优解或超过迭代限制^[16]。高斯牛顿算法的一般求解步骤为:

步骤1  根据J_k^TJ^kh_gn=－J_k^Tf_k, 求解迭代步距h。

步骤2  采用x_k+1=x_k+h进行新的迭代。

步骤3  若|F(x_k+1)－F(x_k)| < ε, 其中ε足够小, 则认为F(x)收敛, 退出迭代, 否则重复步骤1。

高斯牛顿算法在求解非线性方程时并不总能保证收敛, 要使该算法在求解时收敛, 必须保证以下2个条件:

1) F(x)是有界函数。

2) 在进行每一次迭代时, 雅克比矩阵必须是满秩的。

当不满足以上2个条件时, 该算法无法保证收敛, 且不能得到方程的全局最优解。

由于Taylor算法无法满足所有系数矩阵都为非奇异的情况, 梯度下降算法和高斯牛顿算法又受到不同使用条件的限制, 因此本文引入新的求解算法——LM算法。LM算法对于求解非线性方程是一个很好的选择, 尤其是在奇异或者非孤立解的情况下^[17]。

文献[18-19]提出一种改进的GN算法, 通过添加阻尼因子(LM参数)使得改进的GN算法具有更宽的收敛域, 可以解决病态非线性最小二乘拟合问题, 称为LM算法。传统LM参数的取值是预先设定的, 而文献[20]提出了一种LM参数更新方法, 证明了改进的LM算法具有全局及二次收敛性。LM算法可以通过修改参数达到结合高斯牛顿算法以及梯度下降算法的优点, 并且不需要固定γ值来确定精度和收敛速度, 同时对两者的不足加以改善, 如高斯牛顿算法中逆矩阵不存在时将无法继续迭代的问题^[21]。LM算法的可靠性优于高斯牛顿算法, 这意味着在很多情况下, 即使从距离实际值很远的地方开始计算, LM算法也能找到解决方案。LM算法的具体实现过程如下:

步骤1  初始化μ₀=τ×max{a_ii}, ν₀=2。

步骤2  求解梯度g_k=J_k^Tf_k, 如果‖g_k‖ < ε₁, 则退出, 否则继续。

步骤3  根据(J^T_kJ_k+λ_kI)h_lm=－J^T_kf_k, 求解迭代步距h_lm。

步骤4  若‖h_lm‖≤ε₂(‖x‖+ε₂), x_new=x_k+h_gn, 计算增益比$\rho = \frac{{F\left( {{x_k}} \right) - F\left( {{x_{k + 1}}} \right)}}{{L(0) - L\left( {{h_{\delta \pi }}} \right)}}$。如果ρ>0, 则${x_{k + 1}} = {x_{{\rm{new}}}}, {u_{k + 1}} = {u_k} \times \max \left( {\frac{1}{3}, 1 - {{(2\rho - 1)}^3}} \right)$, u_k+1=2, 否则u_k+1=u_k×v_k, v_k+1=2×v_k, 重复步骤2。

对于ε₁、ε₂可以选取一个任意小的值(如10^-12), 其只是作为迭代的终止条件, 对于最终的收敛结果影响不大。

为了验证LM算法的可靠性、优劣性及实用性, 在相同条件下分别对Taylor算法和LM算法在TDOA三维定位中的应用进行了仿真。在多径干扰环境下, 由于在距离差中引入了非视距误差, 如果以CHAN算法的计算结果作为迭代初值, 将会引入新的不确定性因素。因此, 将基站空间位置中心作为Taylor算法的迭代初始值。

仿真时参与定位计算的总共有441个点, 在不同的条件下分别进行100次的仿真实验并记录仿真结果, 将仿真结果的平均值作为最终结果。其中, N(T)为Taylor算法求解失败点数的平均值, N(L)为LM算法求解失败点数的平均值, E(T)为Taylor算法结果误差平均值, E(L)为LM算法结果误差平均值, P(T)为Taylor算法的求解率, P(L)为LM算法的求解率。

实验1  基站坐标设置为初始坐标, 层高为50, 噪声为10, 在不同迭代步距下对Taylor算法与LM算法进行仿真实验, 结果如表 1所示。

由表 1可以看出, 随着迭代步距的不断增加, Taylor算法中无法求得解坐标的点数和解算结果的误差平均值均在逐渐增加。LM算法的求解成功率均高于Taylor算法, 当迭代步距大于等于0.5时, 该算法的误差值均小于Taylor算法且相对稳定, 这说明LM算法求得解坐标的质量优于Taylor算法的解算结果。因此, 与Taylor算法相比, LM算法在迭代步距改变时求解率更高、表现得更加稳定, 且解算的结果精度也更高。

实验2  基站坐标设置为初始坐标, 迭代步距为1.0, 层高为50, 在不同噪声下对Taylor算法与LM算法进行仿真实验, 结果如表 2所示。

由表 2可知, 随着外界噪声值的增加, Taylor算法和LM算法中求解失败的点数以及结果的误差平均值均呈增加的趋势, 且Taylor算法的增加量大于LM算法, 同时, Taylor算法求解失败的点数以及误差平均值均大于LM算法, 但Taylor算法的求解率均小于LM算法。因此, 相比Taylor算法, LM算法在不同噪声条件下求得解坐标的质量优于Taylor算法, 且求解率更高、精度更高。

实验3  基站坐标设置为初始坐标, 迭代步距为1.0, 噪声为50, 在不同层高下对2种算法进行仿真实验, 结果如表 3所示。

由表 3可知, 2种算法对于不同高度上的点的求解效果有明显的差别。相比在基站空间外的点, 当目标点在基站空间内时, 2种算法的解算效果相对较好。与Taylor算法相比, LM算法不能完成求解的点数更少, 且误差平均值也更小。这说明LM算法在不同层高条件下求得坐标解的精度更高。

实验4  改变基站D的坐标为(600, 600, 600), 进行以下3种条件的仿真实验:

1) 设置迭代步距为0.5和1.0, 噪声为10, 层高为50。

2) 设置噪声为10和50, 迭代步距为1.0, 层高为50。

3) 设置层高为50和100, 迭代步距为1.0, 噪声为20。

在上述3种实验条件下对2种算法进行仿真实验, 结果如表 4所示。

实验4的结果表明, 基站D与基站C的高度相同时, 由于基站布局发生了变化, Taylor算法虽然全部得到了误差小于1 000的结果, 误差值相对较大, 而且得到的全部是伪解算结果及伪成功率, 仍然认为求解失败。但是LM算法只有少数点无法求得解坐标, 求解率依然可以保证在80%以上, 在这种条件下, LM算法表现出了更好的稳定性、可靠性。

3 结束语

本文在模拟不同的工况环境下, 对Taylor算法以及LM算法在TDOA三维定位中的应用进行了仿真实验, 结果表明, Taylor算法在TDOA三维定位中的应用受到迭代步距和基站布局的严重影响使得大范围的目标点无法求得解坐标。相比Taylor算法, 在相同条件下, LM算法可以高效地完成TDOA三维定位方程组的求解过程, 且求解率更高, 解算结果的精度也更高。在不同评价指标方面, LM算法均表现最好, 验证了LM算法在TDOA三维定位中应用的可行性及实用性。目前研究工作均是在独立单元内的定位, 下一步将放在基于TDOA的多单元以及跨单元定位, 以验证LM算法的可靠性与有效性。