科技飞速发展的今天，人们对于位置服务的需求愈加强烈，在室外利用全球卫星导航系统(global navigation satellite system, GNSS)可以实时确定自己的位置。但由于室内环境的复杂性及障碍物的遮挡作用，无法利用GNSS技术获得高精度的室内定位结果^{[1, 2]}。目前，室内定位技术主要有：蓝牙(bluetooth)定位技术、WiFi定位技术、ZigBee技术、超宽带技术(ultra-wideband, UWB)等。其中，UWB是一种在极大带宽上进行数据传输的无载波通信技术，具有高数据率、穿透力强等特点，能获得分米级的定位结果，是众多室内定位技术中较为重要的技术之一^{[3, 4]}。

UWB技术在时域的高分辨率能力，为无线定位提供了一种极好的手段，其定位的基本机制包括：基于到达角度(angle of arrival, AOA)、基于到达时间(time of arrival, TOA)、基于到达时间差(time difference of arrival, TDOA)以及基于到达信号强度(received signal strength, RSS)^[5]等。由此学者们提出了大量的UWB定位算法。如文献[6]提出Fang算法，通过线性化双曲线方程估计目标的位置，原理简单，能够得到基于距离差的最优解，在视距(line of sight, LOS)条件下定位精度较高，但无法通过冗余信息提高精度，易受随机误差影响；文献[7]提出Chan算法，通过导出最大似然(maximum likelihood，ML)方程，从而估计待测目标位置，在误差服从高斯分布时有良好的定位精度，计算量小，通过增加基站数量可以提高精度。但ML检测算法的复杂度随着发射天线数和调制阶数的增加呈现指数式增加^[8]。距离交会定位算法简单、易于操作，对基站数量要求低，节省成本，是最常用的室内定位方法；但由于测距误差的存在，很难建立精准的、适于实际情况的损耗模型^[9]。

TOA定位精度主要受时钟同步误差和时间的测量误差影响，要求基站与目标做到精确的时钟同步；TDOA定位以双曲线为模型，要求基站之间时钟同步；RSS定位需要知道信道衰弱模型，受多径影响极为严重；AOA定位要求基站必须装备方向敏感的天线阵列，角度值的极小偏差都能引起较大的定位误差。而距离交会定位不需要时钟同步，只需测得距离值即可定位，更易于实现，也是最常用的室内定位方法。利用现有设备，本文主要对基于距离交会原理的最小二乘算法和几何方法进行比较与分析，以寻求其中效率更高、收敛性更好、能够更为准确估计目标位置信息的算法。

1 距离交会定位

在基于距离交会的定位方法中，假设存在3个基站A_i(x_i, y_i)(i=1, 2, 3)，待测目标为T_ag(x, y)，其到各个基站的距离为R_i(i=1, 2, 3)。以基站A_i为圆心，距离R_i为半径，形成3个定位圆，即可唯一确定待测节点的位置。

理想的距离交会定位中，几个定位圆必然交于一点，能够唯一确定目标的位置，但由于距离测量存在误差，将会交于一个小区域，使得待测节点位置信息与理想位置不同^[10]。

1.1 最小二乘算法

最小二乘(least squares, LS)算法是一种局部搜索算法^[11]。若有N个基站，其坐标为A_i(x_i, y_i)(i=1, 2, …, N)，到标签Tag(x, y)之间的距离为R_i，设其坐标之间存在函数关系：

$ {\mathit{f}_i}\left( {\mathit{x}, \mathit{y}} \right) = \sqrt {{{\left( {{\mathit{x}_i} - \mathit{x}} \right)}^2} + {{\left( {{\mathit{y}_i} - \mathit{y}} \right)}^2}} $

(1)

选定初始点(x₀, y₀)，对式(1)进行泰勒级数展开可得到式(2)：

$ {\mathit{f}_i}\left( {\mathit{x}, \mathit{y}} \right) = {\mathit{f}_i}\left( {{\mathit{x}_0}, {\mathit{y}_0}} \right) + \left( {\Delta x\frac{\partial }{{\partial x}} + \Delta y\frac{\partial }{{\partial y}}} \right){\mathit{f}_i}\left( {{\mathit{x}_0}, {\mathit{y}_0}} \right) $

(2)

将式(2)转换为矩阵形式有：

$ \mathit{v} = \mathit{\boldsymbol{BX}} - \mathit{\boldsymbol{l}} $

(3)

式中，$\mathit{\boldsymbol{X}} = \left[ {\begin{array}{*{20}{l}} {\Delta x}\\ {\Delta y} \end{array}} \right];\mathit{\boldsymbol{B}} = \left[ {\begin{array}{*{20}{c}} { - \left( {{x_1} - {x_0}} \right)/R_1^0}&{ - \left( {{y_1} - {y_0}} \right)/R_1^0}\\ { - \left( {{x_2} - {x_0}} \right)/R_2^0}&{ - \left( {{y_2} - {y_0}} \right)/R_2^0}\\ \vdots & \vdots \\ { - \left( {{x_N} - {x_0}} \right)/R_N^0}&{ - \left( {{y_N} - {y_0}} \right)/R_N^0} \end{array}} \right];\mathit{\boldsymbol{l}} = \left[ {\begin{array}{*{20}{c}} {{R_1} - R_1^0}\\ {{R_2} - R_2^0}\\ \vdots \\ {{R_N} - R_N^0} \end{array}} \right]。$

通过加权最小二乘对式(3)求解得到式(4)，P表示观测值的权阵：

$ \mathit{\boldsymbol{X}} = {\left( {{\mathit{\boldsymbol{B}}^T}\mathit{\boldsymbol{PB}}} \right)^{ - 1}}\left( {{\mathit{\boldsymbol{B}}^T}\mathit{\boldsymbol{Pl}}} \right) $

(4)

$ \mathit{x} = {\mathit{x}_0} + \Delta x, \mathit{y} = {\mathit{y}_0} + \Delta \mathit{y} $

(5)

通过式(4)、式(5)改变初始值进行下一次计算，直到满足|Δx| < ε和|Δy| < ε时，结束迭代。

最小二乘算法是目前求解非线性方程有效的方法之一，当观测数据服从正态分布时，是所有估计中的最优估计，定位精度高；但其计算过程较为复杂，不具备抗差性，少量的粗差即可造成不可靠的参数估计，并且迭代次数和位置精度均受初始值的影响^[12]。

1.2 几何方法

假设存在4个基站P_i(x_i, y_i, z_i)(i=1, 2, 3, 4)，待测目标为T(x, y, z)，待测节点到各个基站的距离为r_i，则几何方法流程如图 2所示。其中几何精度因子(geometric dilution of precision, GDOP)是衡量定位精度的重要标准之一。

由直线L与第4个定位圆的位置关系估计待测目标的最优解时需要进行如下判断。

记由3个基站估计得到的两个位置为T₁、T₂，联立L与第4个球可得一元二次方程：

$ \mathit{a}{\mathit{\mu }^2} + \mathit{b\mu } + \mathit{c} = 0 $

(6)

其中，$\left\{ {\begin{array}{*{20}{l}} {{\rm{d}}x = {x_{{T_2}}} - {x_{{T_1}}}}\\ {{\rm{d}}y = {y_{{T_2}}} - {y_{{T_1}}}}\\ {{\rm{d}}z = {z_{{T_2}}} - {z_{{T_{\rm{1}}}}}} \end{array}} \right.;\left\{ {\begin{array}{*{20}{l}} {a = {{({\rm{d}}x)}^2} + {{({\rm{d}}y)}^2} + {{({\rm{d}}z)}^2}}\\ {b = 2\left[ {{\rm{d}}x\left( {{x_{{T_1}}} - {x_4}} \right) + {\rm{d}}y\left( {{y_{{T_1}}} - {y_4}} \right) + {\rm{d}}z\left( {{z_{{T_1}}} - {z_4}} \right)} \right]}\\ {c = x_4^2 + y_4^2 + z_4^2 + x_{{T_1}}^2 + y_{{T_1}}^2 + z_{{T_1}}^2 - 2\left( {{x_4}{x_{{T_1}}} + } \right.}\\ {\;\;\;\;\;\left. {{y_4}{y_{{T_1}}} + {z_4}{z_{{T_1}}}} \right) - r_4^2} \end{array}} \right.$

μ的取值范围表示交点在直线上与T₁、T₂的相对位置关系。

由式(7)即可得到标签位置的最终估计结果。

$ \overrightarrow T = {\overrightarrow T _1} + \mu \left( {{{\overrightarrow T }_2} - {{\overrightarrow T }_1}} \right) $

(7)

2 实验与分析

本文对所介绍的最小二乘算法以及几何方法进行了实验，并对两种算法做了性能比较。

2.1 实验设备

测距阶段使用DWM1000模块，设4个基站A_i(i=0, 1, 2, 3)，标签安置于导轨上，通过导轨开关控制标签沿直线段匀速运动。DWM1000是UWB无线通信模块，负责时间戳的标记和模块间的通信。其测距原理主要是基于双向飞行法(two way-time of flight，TW-TOF)^{[13, 14]}。

如图 3所示，T_round为基站从发射请求信号到接收回应信号的时间，T_reply为标签从接收请求信号到发射回应信号的时间，由此，信号在两个模块之间单向飞行路程可由式(8)得到：

$ {T_{{\rm{prop}}}} = \left( {{T_{{\rm{round}}}} - {T_{{\rm{reply}}}}} \right)/2 $

(8)

2.2 实验过程

考虑场景为4 m×4 m的正方形区域，该区域中布置有已知位置坐标的基站以及一条导轨，导轨上架设待定位标签。在实验过程中，利用DWM1000模块获得的距离数据，分别采用LS算法和几何方法进行处理，比较最终定位结果。

在实验过程中，4个基站的位置不变，坐标分别为：A₀(-1.2, 1.2, 0.9)、A₁(-1.2, -1.8, 0.9)、A₂(1.8，-1.8, 0.9)、A₃(1.8，1.2, 0.9)，在相同环境下进行了两组实验。

2.3 实验分析

定位平面结果与LS定位平面结果如图 4、图 5所示。从图 4、图 5中数据可以看出，两种定位算法都能较为准确地估计标签的运动轨迹，但LS算法的定位结果收敛性优于几何方法结果；由表 1可知，与真实轨迹相比，LS算法定位偏差值小于0.02 cm，平均水平优于5 cm，胜过几何方法。

在两次实验中，对LS算法和几何定位算法的计算效率进行比较。计算两种算法定位所需时间，结果表明，几何定位算法运行时间约为LS算法的1/300，计算效率显著优于LS算法。对LS算法运行过程中的时间分配做了进一步分析发现，在使用LS算法对目标运动轨迹进行估计时，99.7%的时间均用于矩阵运算，而几何法只需进行简单的矢量运算。

3 结束语

实验表明，与几何方法相比，LS算法可以更为准确地估计待测目标的位置，但计算时间更长。在实际生活中，定位目标的运动范围往往更大，为较好地确定其运动轨迹，需要的定位次数也将大大增加，在这种情况下，采用几何方法定位所节省的时间是很可观的。并且，从图 4和图 5可以看出，两种算法的轨迹并不平滑，这是由于测量值及定位算法本身存在误差，下一步可以考虑采用卡尔曼滤波对结果进行预测和修正，从而得到平滑轨迹；并且引入并行方法加速矩阵运算，在海量数据情况下提高LS算法的计算效率。