﻿ 一种基于UWB TDOA定位模式的迭代最小二乘算法
 文章快速检索 高级检索
 大地测量与地球动力学  2021, Vol. 41 Issue (8): 806-809  DOI: 10.14075/j.jgg.2021.08.007

### 引用本文

HE Chengwen, YUAN Yunbin, TAN Bingfeng. An Iterative Least Squares Algorithm Based on UWB TDOA Positioning Model[J]. Journal of Geodesy and Geodynamics, 2021, 41(8): 806-809.

### Foundation support

Independent Deployment Project of State Key Laboratory of Geodesy and Earth's Dynamics, Innovation Academy for Precision Measurement Science and Technology (APM), CAS, No. E025011001.

### 第一作者简介

HE Chengwen, PhD candidate, majors in wireless sensor network localization and signal processing, E-mail: cwhe_10@163.com.

### 文章历史

1. 中国科学院精密测量科学与技术创新研究院大地测量与地球动力学国家重点实验室，武汉市徐东大街340号，430077;
2. 中国科学院大学，北京市玉泉路19号甲，100049

1 算法描述

 $\begin{gathered} d_{i, 1}=\sqrt{\left(x-x_{i}\right)^{2}+\left(y-y_{i}\right)^{2}}- \\ \sqrt{\left(x-x_{1}\right)^{2}+\left(y-y_{1}\right)^{2}}+\eta_{i} \end{gathered}$ (1)

 $\boldsymbol{G}=\left[\begin{array}{ccc} x_{2}-x_{1} & y_{2}-y_{1} & d_{2,1} \\ x_{3}-x_{1} & y_{3}-y_{1} & d_{3,1} \\ \vdots & \vdots & \vdots \\ x_{N}-x_{1} & y_{N}-y_{1} & d_{N, 1} \end{array}\right]$ (2)
 $\boldsymbol{u}_{1}=[x, y, R]^{\mathrm{T}}$ (3)
 $\boldsymbol{h}=\frac{1}{2}\left[R_{2}^{2}-R_{1}^{2}-d_{2,1}^{2} \quad \cdots \quad R_{N}^{2}-R_{1}^{2}-d_{N, 1}^{2}\right]^{\mathrm{T}}$ (4)

 $R^{2}=\left(\boldsymbol{u}_{0}-\boldsymbol{s}_{1}\right)^{\mathrm{T}}\left(\boldsymbol{u}_{0}-\boldsymbol{s}_{1}\right)$ (5)

 \begin{aligned} &\min \left(\boldsymbol{h}-\boldsymbol{G} \boldsymbol{u}_{1}\right)^{\mathrm{T}} \boldsymbol{W}\left(\boldsymbol{h}-\boldsymbol{G} \boldsymbol{u}_{1}\right) \\ &\mathrm{s} . \mathrm{t} . \quad R^{2}=\left(\boldsymbol{u}_{0}-\boldsymbol{s}_{1}\right)^{\mathrm{T}}\left(\boldsymbol{u}_{0}-\boldsymbol{s}_{1}\right) \end{aligned} (6)

CWLS算法已有较为快速的解法，但在定位精度方面仍存在较大的提升空间。为进一步提高CWLS算法的定位精度和运算速度，并解决约束方程的非凸问题，Qu等[6]提出迭代约束加权最小二乘(ICWLS)算法。该算法通过新的等式变换，将具有非凸特性的CWLS算法表达式转化成具有凸性的新表达式。尽管仿真实验证实了该算法的有效性，但在大噪声环境下却存在定位发散的缺点。

 $d_{i, 1}=\sqrt{\left(x-x_{i}\right)^{2}+\left(y-y_{i}\right)^{2}}-\sqrt{x^{2}+y^{2}}+\eta_{i}$ (7)

 $\left(d_{i, 1}+R\right)^{2}=\left(x-x_{i}\right)^{2}+\left(y-y_{i}\right)^{2}$ (8)

 $2 d_{i, 1} R=x_{i}^{2}+y_{i}^{2}-d_{i, 1}^{2}-2 x_{i} x-2 y_{i} y$ (9)

 $\boldsymbol{A}=\left[\begin{array}{ccc} d_{2,1} & \cdots & d_{N, 1} \end{array}\right]^{\mathrm{T}}$ (10)
 $\boldsymbol{C}= {\left[\begin{array}{c} x_{2}^{2}+y_{2}^{2}-d_{2,1}^{2} \\ \vdots \\ x_{N}^{2}+y_{N}^{2}-d_{N, 1}^{2} \end{array}\right]}$ (11)
 $\boldsymbol{B}=\left[\begin{array}{cc} x_{2} & y_{2} \\ \vdots & \vdots \\ x_{N} & y_{N} \end{array}\right]$ (12)

 $2 \boldsymbol{A} R=\boldsymbol{C}-2 \boldsymbol{B} \boldsymbol{X}_{*}$ (13)

 $\boldsymbol{B} \boldsymbol{X}_{*}=\frac{1}{2}\left(\boldsymbol{C}-2 \boldsymbol{A} \sqrt{\boldsymbol{X}_{*}^{\mathrm{T}} \boldsymbol{X}_{*}}\right)$ (14)

 $\boldsymbol{X}_{*}^{(k+1)}=\frac{1}{2}\left(\boldsymbol{B}^{\mathrm{T}} \boldsymbol{B}\right)^{-1} \boldsymbol{B}^{\mathrm{T}}\left(\boldsymbol{C}-2 \boldsymbol{A} \sqrt{\left(\boldsymbol{X}_{*}^{(k)}\right)^{\mathrm{T}} \boldsymbol{X}_{*}^{(k)}}\right)$ (15)

 $\sqrt{\left(\boldsymbol{X}^{(k+1)}-\boldsymbol{X}^{(k)}\right)^{\mathrm{T}}\left(\boldsymbol{X}^{(k+1)}-\boldsymbol{X}^{(k)}\right)} \leqslant \varepsilon$ (16)

 \begin{aligned} &E\left(\boldsymbol{X}_{*}^{(k+1)}\right)=\\ &E\left(\frac{1}{2}\left(\boldsymbol{B}^{\mathrm{T}} \boldsymbol{B}\right)^{-1} \boldsymbol{B}^{\mathrm{T}}\left(\boldsymbol{C}-2 \boldsymbol{A} \sqrt{\left(\boldsymbol{X}_{*}^{(k)}\right)^{\mathrm{T}} \boldsymbol{X}_{*}^{(k)}}\right)\right)=\\ &E\left(\frac{1}{2}\left(\boldsymbol{B}^{\mathrm{T}} \boldsymbol{B}\right)^{-1} \boldsymbol{B}^{\mathrm{T}}(\boldsymbol{C}-2 \boldsymbol{A} R)\right)=\\ &E\left(\frac{1}{2}\left(\boldsymbol{B}^{\mathrm{T}} \boldsymbol{B}\right)^{-1} \boldsymbol{B}^{\mathrm{T}}\left(2 \boldsymbol{B} \boldsymbol{X}_{*}^{(k)}\right)\right)=\\ &\left(\boldsymbol{B}^{\mathrm{T}} \boldsymbol{B}\right)^{-1} \boldsymbol{B}^{\mathrm{T}} \boldsymbol{B} \cdot E\left(\boldsymbol{X}_{*}^{(k)}\right)=E\left(\boldsymbol{X}_{*}^{(k)}\right) \end{aligned} (17)

2 仿真实验

 $\mathrm{RMSE}=\frac{1}{2\ 000} \sum\limits_{i=1}^{2\ 000} \sqrt{\left(\boldsymbol{X}_{i^{*}}-\tilde{\boldsymbol{X}}_{i}\right)^{\mathrm{T}}\left(\boldsymbol{X}_{i^{*}}-\tilde{\boldsymbol{X}}_{i}\right)}。$
2.1 实验1

 图 1 2种算法在不同点处的定位精度 Fig. 1 RMSE of two methods at different points
2.2 实验2

 图 2 2种算法在随机点环境下的定位精度 Fig. 2 RMSE of two methods at random point
2.3 实验3

 图 3 2种算法在不同点处的定位坐标 Fig. 3 Coordinates of two methods at different points

3 结语

 [1] 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 DOI:10.1109/78.301830 (0) [2] Huang Y T, Benesty J, Elko G W, et al. Real-Time Passive Source Localization: A Practical Linear-Correction Least-Squares Approach[J]. IEEE Transactions on Speech and Audio Processing, 2001, 9(8): 943-956 DOI:10.1109/89.966097 (0) [3] Yu H G, Huang G M, Gao J, et al. An Efficient Constrained Weighted Least Squares Algorithm for Moving Source Location Using TDOA and FDOA Measurements[J]. IEEE Transactions on Wireless Communications, 2012, 11(1): 44-47 DOI:10.1109/TWC.2011.102611.110728 (0) [4] Quo F C, Ho K C. A Quadratic Constraint Solution Method for TDOA and FDOA Localization[C]. IEEE International Conference on Acoustics, Speech and Signal Processing(ICASSP), Prague, 2011 (0) [5] Lin L X, So H C, Chan F K W, et al. A New Constrained Weighted Least Squares Algorithm for TDOA-Based Localization[J]. Signal Processing, 2013, 93(11): 2872-2878 DOI:10.1016/j.sigpro.2013.04.004 (0) [6] Qu X M, Xie L H, Tan W R. Iterative Constrained Weighted Least Squares Source Localization Using TDOA and FDOA Measurements[J]. IEEE Transactions on Signal Processing, 2017, 65(15): 3990-4003 DOI:10.1109/TSP.2017.2703667 (0) [7] Li J Z, Guo F C, Yang L, et al. On the Use of Calibration Sensors in Source Localization Using TDOA and FDOA Measurements[J]. Digital Signal Processing, 2014, 27: 33-43 DOI:10.1016/j.dsp.2013.12.011 (0) [8] Qiao T Z, Zhang Y, Liu H P. Nonlinear Expectation Maximization Estimator for TDOA Localization[J]. IEEE Wireless Communications Letters, 2014, 3(6): 637-640 DOI:10.1109/LWC.2014.2364023 (0) [9] Jia T Y, Wang H Y, Shen X H, et al. Target Localization Based on Structured Total Least Squares with Hybrid TDOA-AOA Measurements[J]. Signal Processing, 2018, 143: 211-221 DOI:10.1016/j.sigpro.2017.09.011 (0) [10] Qu X M, Xie L H. An Efficient Convex Constrained Weighted Least Squares Source Localization Algorithm Based on TDOA Measurements[J]. Signal Processing, 2016, 119: 142-152 DOI:10.1016/j.sigpro.2015.08.001 (0) [11] Xu B, Qi W D, Wei L, et al. Turbo-TSWLS: Enhanced Two-Step Weighted Least Squares Estimator for TDOA-Based Localization[J]. Electronics Letters, 2012, 48(25): 1597-1598 DOI:10.1049/el.2012.2848 (0) [12] Zou Y B, Liu H P, Wan Q. An Iterative Method for Moving Target Localization Using TDOA and FDOA Measurements[J]. IEEE Access, 2018, 6: 2746-2574 DOI:10.1109/ACCESS.2017.2785182 (0) [13] Wang G, Li Y M, Ansari N. A Semidefinite Relaxation Method for Source Localization Using TDOA and FDOA Measurements[J]. IEEE Transactions on Vehicular Technology, 2013, 62(2): 853-862 DOI:10.1109/TVT.2012.2225074 (0) [14] Noroozi A, Oveis A H, Hosseini S M, et al. Improved Algebraic Solution for Source Localization from TDOA and FDOA Measurements[J]. IEEE Wireless Communications Letters, 2018, 7(3): 352-355 DOI:10.1109/LWC.2017.2777995 (0)
An Iterative Least Squares Algorithm Based on UWB TDOA Positioning Model
HE Chengwen1,2     YUAN Yunbin1     TAN Bingfeng1
1. State Key Laboratory of Geodesy and Earth's Dynamics, Innovation Academy for Precision Measurement Science and Technology, CAS, 340 Xudong Street, Wuhan 430077, China;
2. University of Chinese Academy of Sciences, A19 Yuquan Road, Beijing 100049, China
Abstract: Aiming at the problem of low accuracy and divergence of positioning algorithm for ultra-wideband (UWB) sensors in time-different-of-arrival (TDOA) positioning mode, we propose a simple iterative least squares algorithm. This method has the advantages of a simple formula, convergent coordinates and high positioning accuracy. The main idea is to transform the TDOA localization equation into a nonstandard least squares form by the Pythagorean theorem. Then, the equation constraint relation between unknown variables is combined to transform the form with two unknown variables into a form with only one unknown variable. Finally, the convergence coordinate of UWB tag is calculated by iteration. Monte Carlo simulation results show that the proposed algorithm is superior to the iterative constrained weighted least squares algorithm in positioning accuracy in high-noise environment.
Key words: time-different-of-arrival; ultra wideband; iterative least squares algorithm