基于改进TDOA算法的设计与仿真

吴端坡， 李俊杰， 许晓荣， 冯 维， 刘兆霆

（杭州电子科技大学通信工程学院，杭州310018）

0 引 言

随着移动通信和无线传感技术的发展，基于位置的服务应用广泛［1］。众所周知，人们在室内环境下的活动时间占据其生活极大比重。人们希望可以获得更加精准的室内位置信息。一种比较常见且简单有效的定位方法是到达时间差（Time Difference of Arrival，TDOA）［2-3］算法，它是一种基于测距的定位方法，通过测量节点间的距离信息来计算节点的位置，其对定位基站与移动目标之间的时钟同步要求不是十分严格。本文选取不要求基站和移动目标之间严格同步的TDOA算法，使得其应用范围更加广泛。

TDOA算法在定位领域广泛应用，但传播信号受非视距等因素的影响，定位精度不可避免地有所降低。为减小定位误差，Kolakowski［4］利用TDOA计算结果以及相应加速度计测量值来优化定位精度。Li 等［5］分析TDOA算法与非视距（Non-line-of-sight，NLOS）的相关性来定位静态目标问题。Choi 等［6］在时间递归的鲁棒最小二乘估计框架下，提出了一种TDOA 位置估计器。该法可以将一组不同时间的测量值递归地组合在一起，产生更精确的定位结果。Yang 等［7］提出了一种考虑视距的TDOA改进方法，引入一个传递函数，将给定接收机的场与源的场作为频率和位置的函数联系起来，缓解了NLOS效应，并将传播通道校准回自由空间。Kim［8］则将障碍物信息考虑进去，提出了一种合理、时间有效的辐射源估计方法。从上述的算法设计中，可以发现它们对定位区域范围、行人最大移动速度等实验环境的固有信息运用很少。本文在TDOA算法的基础上引入了速度受限和区域受限的定位模型，提出基于速度和区域受限的改进TDOA 算法，并在Matlab仿真平台上进行验证。

1 TDOA算法

TDOA［9-10］算法是对到达时间（Time of Arrival，TOA）算法的改进，它不是直接利用信号到达时间，而是用多个基站接收到信号的时间差［11-12］来确定移动台位置，与TOA算法相比，它不需要加入专门的时间戳，定位精度也有所提高。

假定室内基站位置为A1（0，0）、A2（m2，0）和A3（m3，n3），移动目标位置为（xt，yt），t 为采样间隔可得［13-14］：

式中：R1，t、R2，t和R3，t分别为基站与移动目标之间的距离。求解式（1）可得目标位置（xt，yt）。

2 改进TDOA算法

2.1 速度受限定位算法

由先验知识可知，实际室内环境是复杂多变的（如错落的桌椅、人流等），人们在室内移动速度缓慢，可视为一种低速的移动状态，即速度受限状态。假设使用速度受限算法优化和未优化的定位结果分别为Tt（xt，yt）和，目标移动轨迹如图1 所示。图中：dt，t-1为Tt和T′t之间的距离；和分别平行于y轴和x 轴，D 为它们的交点。若目标最大移动速度为vmax，采样频率为f，则目标单位采样间隔内的最大移动距离为dmax＝vmax／f。

图1 定位目标移动轨迹示意图

如果dt，t-1的值大于目标的最大移动距离为dmax，那么Tt将会约束到图1 中的T′t点。根据相似三角形定理，可得：

2.2 区域受限定位算法

室内环境中存在有一些不可逾越的障碍，包括床、衣柜和墙壁等。室内环境可以看作是有限的区域。将区域受限定位算法分为内部移动和区域转换两个案例。并将算法的研究场景设置为矩形区域。

图2 区域受限定位算法分析示意图

分析内部移动场景，算法分析示意如图2 所示。图中：Bi（i ＝1，2，3，4）为区域边界点；Tt和分别表示使用和未使用区域受限定位算法的定位结果；D1D2为房门；I1和I2分别为射线D1和射线D2与圆T′t-1的交点；R1和R2分别为线段T′t-1Tt与墙壁的交点和线段TtD2与圆D2的交点；UR1和UR2为阴影区域。wi（i ＝1，2，3，4）根据直线B1B3和B2B4将可移动区域外围分为4 个部分。

若假设目标移动时，不存在房门D1D2，那么根据区域边界的限制，需将Tt点约束到R1，该点即为修正点T′t。根据相似三角形定理，可得：

式中，J 为线段T′tR1和T′tTt的比值。化简式（4）可得：

式中，wi（i ＝1，2，3，4）为目标所在不可移动的区域，可以根据离目标最近两相邻拐点和最小值决定。因而，可得：

式中，i与c（i）为相邻拐点。

其次，分析区域转化场景下的定位修正方法。若边界B2B3存在房门D1D2，那么目标除了UR1和UR2区域，其他都可能到达。若目标超出可移动区域边界，则将其约束到圆Dk（Dk表示门的边界点，k ＝1，2）上的R2点，那么该点即为所求的修正点。若G 为线段和DkTt线段的比值，那么G的值为：

式中：

P1和P2为区域UR1和UR2。Pi（i ＝1，2）的确定可依据目标离门边界点Dk的距离，可得：

设Fi＝［gk，hk］，根据三角形相似定理可得：

化简可得：

故而，区域受限定位算法可整理为：

式中：w ＝w1∪w2∪w3∪w4；p ＝ ｛（x，y）｜ （x -g1）2＋。

2.3 改进TDOA算法

速度受限定位算法适用于区域内部的目标定位，而区域受限定位算法适用于区域边界的目标定位，所以将两种算法融合使用可以更好地实现室内目标的定位功能。利用TDOA算法获得目标定位坐标信息。使用速度受限定位算法分析目标的可移动区域，根据其与上一定位点之间的距离dt，t-1，判断目标点是否超过最大移动距离阈值dmax。若超过阈值，则将目标点约束到同方向、距离上一定位点dmax的位置，该点即为速度受限定位算法的修正结果。将该结果传入区域受限定位算法进行进一步约束，以修正穿墙的异常定位点，并将目标的可移动区域进一步细化，进一步修正定位结果。算法流程如图3 所示。

图3 改进TDOA算法流程图

详细步骤如下：

步骤1使用式（1）计算得目标位置Tt（xt，yt）。

步骤2分析dmax和dt，t-1之间的大小，将Tt的值代入式（3）中修正超出可移动范围的异常值。

步骤3分析｜T′tDk｜和dmax的大小，若｜T′tDk｜ ＜dmax，根据式（9）计算k，代入式（8）得到G。将G 和步骤2 中得到的修正值代入式（11）中可得区域受限定位算法优化后的修正值。若｜T′tDk｜＞dmax，则根据式（7）计算i，将其代入式（6）确定J，将J 和步骤2 中得到的修正值代入式（5）得区域受限定位算法优化后的修正值。

步骤4步骤3 中的修正值即为改进TDOA算法的优化结果。

3 实验结果

本文分析了影响定位精度的3 种因素，分别为测量误差、目标最大移动速度和采样频率。本文设置的实验环境为10 m×10 m的正方形区域，实验的测量误差设置为0.1 m，目标的最大移动速度为1 m／s，采样频率为10 Hz。对比算法为TDOA算法。

本实验定位目标的移动轨迹设置为B1-B2-B3，如果分别控制目标的测量误差、采样频率和最大移动速度的变化，可以得到3 组数据进行分析。平均定位误差（Mean Positioning Error，MPE）eMPE与测量误差（Measuring Error，ME）eME变化关系仿真结果如图4 ～6 所示。

图4 测量误差对定位精度的影响

图5 目标最大移速对定位精度的影响

图6 采样频率对对定位精度的影响

由图4 可见，改进TDOA 算法和速度受限定位算法受测量误差的影响不大，而区域受限定位算法和TDOA算法则随测量误差的增大而增大。改进TDOA算法平均定位误差一直保持最小，定位精度最高。

由图5 可见，改进TDOA 算法和速度受限定位算法都随着移动速度的提高而不断增大，而区域受限定位算法和TDOA算法则不受移动速度的影响，基本保持不变。明显可以看到改进TDOA算法有着最好的定位精度。

由图6 可见，改进TDOA 算法和速度受限定位算法都随着采样频率的提高而不断减少，而区域受限定位算法和TDOA算法则不受采样频率的影响，基本保持不变。总体而言，改进TDOA 算法的平均定位误差最小，定位精度最高。

总之，当测量目标的测量误差、目标最大移动速度和采样频率发生改变时，改进TDOA 算法都保持这最低的平均定位误差，有着最高的定位精度，减弱了非视距等环境因素对定位精度的影响。

4 结 语

本文提出了一种基于速度受限和区域受限的改进TDOA算法。仿真结果表明，该算法可以明显改善非视距等环境因素对TDOA算法定位结果的影响。并且通过对改进TDOA算法的虚拟仿真，可以启发学生对实验仿真方法和改进方法的思考。