王騰輝，武建鋒，焦喜康，朱靖川

基于最小HDOP選站下的到達時間差定位算法

王騰輝1,2，武建鋒1，焦喜康1,2，朱靖川1,2

（1. 中國科學院 國家授時中心，西安 710600；2. 中國科學院大學 電子電氣與通信工程學院，北京 101048）

傳統(tǒng)蜂窩網(wǎng)絡系統(tǒng)雖支持基于到達時間差（TDOA）的定位方法，但是精度較差。第五代移動通信(5G)可在室內(nèi)定位分配系統(tǒng)中提供準確的多個TDOA測量值，可顯著提高室內(nèi)定位能力。隨著5G微基站的大規(guī)模普及，目標終端從基站一側(cè)可選擇的測量值也越多，按照傳統(tǒng)方法直接進行解算，測速運算量大且無法剔除誤差較大的觀測值。本文提出一種定位基站最優(yōu)組合方法，使用廣度優(yōu)先搜索（BFS）篩選出水平精度因子（HDOP）最小的定位基站組合，并考慮每個TDOA測量誤差具有不同的方差，采用加權(quán)最小二乘算法估計在基站最優(yōu)組合條件下目標終端的位置。通過仿真分析和試驗驗證，基于最小HDOP選站下的到達時間差定位算法在保證了定位準確度的前提下，單次定位解算速度提高了51.14%，顯著提升了定位響應速度。

到達時間差；第五代移動通信；水平精度因子；廣度優(yōu)先搜索；最小二乘

0 引言

室內(nèi)定位對于基于位置的服務，物聯(lián)網(wǎng)和電力服務等非常重要[1]。目前市場流行的幾種定位技術(shù)包括藍牙信標技術(shù)、超寬帶無線技術(shù)以及基于蜂窩網(wǎng)絡定位技術(shù)。其中，藍牙信標技術(shù)是目前主流的一種室內(nèi)定位方案，該技術(shù)最大的優(yōu)點是設備體積小，容易集成于手機等移動設備中，但對于復雜的空間環(huán)境，藍牙系統(tǒng)容易受到噪聲信號干擾，且藍牙器件和設備價格比較昂貴[2-3]。超寬帶（UWB）無線技術(shù)是近年來提出的室內(nèi)無線定位技術(shù)，具有定位精度高、穿透力強等優(yōu)點，然而布局該系統(tǒng)成本太高[4-5]。5G定位技術(shù)的出現(xiàn)能夠滿足高精度定位對無線網(wǎng)絡的需求[6]，5G的毫米波通信具有高頻、高帶寬的特點，有利于提高多徑分辨率，不易受噪聲信號干擾[7]，并且5G具有成熟的室內(nèi)分配方案包括5G分布式天線系統(tǒng)（DAS）與5G數(shù)字室分，通過利用舊的DAS完成室內(nèi)5G覆蓋，可以有效地降低布局成本[8]。

LTE移動通信系統(tǒng)提供的到達時間差估計技術(shù)使用定位參考信號（PRS）進行測距，PRS部分響應信號的帶寬只有1.4～20 MHz，帶寬的有限無法保證定位的精度[9-13]。而在5G系統(tǒng)下，PRS信號的帶寬可以提高到100 MHz[14]，因此5G系統(tǒng)可以在較大的帶寬以及連續(xù)的上下行信號上提供高精度的TDOA（time difference of arrival）測量值。微基站的大規(guī)模普及使得從基站一側(cè)可以提供的測量數(shù)據(jù)十分充 裕，在這種情況下，對目標的定位問題由原來的非線性方程精確求解問題轉(zhuǎn)換成了非線性最優(yōu)化估計問題[15]。目前有很多定位算法用于TDOA測量方程的解，這些算法可以分為迭代算法和閉式求解算法，Taylor級數(shù)展開法是一種常用的迭代算法，當給定初始位置不準確時，迭代算法不能保證收斂，即出現(xiàn)較大誤差[16]，閉式求解算法可以避免收斂問題，最常用的閉式算法為兩步加權(quán)最小二乘（WLS）算法[17]，該算法在TDOA誤差足夠小時，可達到克拉美羅下界。當存在大量TDOA測量值時，按照傳統(tǒng)方法直接解算運算量大且有誤差較大觀測值的干擾[18-22]。本文在使用兩步加權(quán)最小二乘解算前，對誤差較大的TDOA觀測值進行剔除，從而提高定位精度與響應速度。

1 基于到達時間差的定位方法

1.1 TDOA定位原理

1.2 基于TDOA的定位解算算法

由于二維定位至少需要3個基站，所以TDOA的解算算法只能基于基站個數(shù)至少是3個才可以進行定位，實際工程中應用最廣的為最小二乘。最小二乘算法大致可以分為兩類，即具有解析表達式的算法和遞歸算法。二維情況下，Chan氏算法分為三基站定位和三基站以上定位兩種情況，兩步加權(quán)最小二乘近似一個最大似然估計器。

1.2.1 基站個數(shù)為3的情況

1.2.2 基站個數(shù)大于3的情況

① 第一次加權(quán)最小二乘估計

TDOA噪聲的線性方程為

② 第二次加權(quán)最小二乘估計

建立線性方程組：

1.3 水平精度分析

令方向余弦

式（13）表示為矩陣形式為

考慮每個基站的TDOA測量誤差不同，因此不同于普通最小二乘，使用加權(quán)最小二乘解算，解算式為

HDOP是描述水平坐標精度的誤差程度，考慮實際工程中每個TDOA測量誤差不同，故使用加權(quán)最小二乘得出此方法下的HDOP表達式：

1.4 基于廣度優(yōu)先搜索的選站方法

微基站的大規(guī)模普及使得終端接收機附近存在多個基站，接收機一側(cè)接收到的測量數(shù)據(jù)就變得十分充裕，在這種情況下，通過選取對定位結(jié)果最優(yōu)的基站組合，不僅能剔除誤差較大的觀測值，也能提高解算速度。

廣度優(yōu)先搜索（BFS）作為搜索算法的一種，被廣泛應用在圖論算法模型中，圖論中的Dijkstra算法和Prim最小生成樹算法都是由廣度優(yōu)先搜索演變而來[28]，廣度優(yōu)先搜索算法的核心思想是從當前的節(jié)點向外擴展，用數(shù)據(jù)結(jié)構(gòu)中的棧維護可以采用的節(jié)點，直到所有節(jié)點都被訪問，棧組中存在的節(jié)點即是最后需要的節(jié)點。

圖1 BFS算法選站流程圖

2 仿真結(jié)果與分析

為分析基于最小HDOP準則下的選站組合對定位精度影響，根據(jù)中國科學院國家授時中心試驗廠區(qū)的真實場景，建立一個模擬場景，真實的場景如圖2所示，開發(fā)的模擬場景俯視圖如圖3所示。真實場景試驗區(qū)為50×30 m的長方形區(qū)域，建立笛卡爾坐標系。

圖2 地下試驗場真實場景

圖3 模擬場景俯視圖

在圖3中笛卡爾坐標系以米為單位，根據(jù)試驗場真實環(huán)境，選取兩個具有代表性的測試點，分別位于場景右半邊A點和左半邊B點，如圖4所示。

圖4 A、B點俯視圖

圖4中圓點為測試坐標點，小三角為基站坐標點，其中，距離A點最近的3個基站為BS3，BS6，BS7，距離B點最近的3個基站為BS1，BS2，BS8。

使用廣度優(yōu)先搜索算法對A點篩選最優(yōu)定位基站組合，首先選取距離終端A點最近的基站BS7，再依次遍歷。按照圖1的算法流程，選出的A點最小HDOP的基站組合BS1，BS3，BS5，BS6，BS7。為了驗證算法的準確性，對A點的幾組基站組合單獨進行HDOP計算，由表1可以看出，提出的廣度優(yōu)先遍歷算法選出的基站組合HDOP值最小，值為1.54，距離A點最近的3個基站BS3，BS6，BS7的HDOP為2.24，全站參與下的A點HDOP值為1.61。

表1 A測試點的基站組合及HDOP值

同理，對B點篩選最優(yōu)定位基站組合，首先選取距離B點最近的基站BS1，按照圖1的算法流程，選出的B點最小HDOP的基站組合BS1，BS2，BS8。選取的最優(yōu)基站組合是距離B點最近的3個基站，為驗證算法準確性，在BS1，BS2，BS8基礎(chǔ)上增加B點周邊基站，計算各組合HDOP。由表2可以看出最優(yōu)基站組合HDOP值為1.87，且為距離B點最近的3個基站，在此基礎(chǔ)上增加基站數(shù)量，都會增大HDOP的值。

表2 B測試點的基站組合及HDOP值

圖5 本次測試的主要設備

表3和表4為A測試點下的最優(yōu)基站組合與全站的測試結(jié)果，其中，在499次的有效測試點中，最優(yōu)組合的最大單次解算耗時為0.354 s，平均單次解算耗時為0.178 s。在498次的有效測試點中，全站參與下的最大解算耗時為0.423 s，平均單次解算耗時為0.312 s，可以看出本文所提算法在效率上提高了42.94%。

表3 A點最優(yōu)組合基站的測試結(jié)果

表4 A點全站的測試結(jié)果

圖6為A點在最優(yōu)基站組合與全站組合下單方向誤差比較，可以看出，最優(yōu)基站組合方向和方向上的均方根誤差均小于全站參與，最優(yōu)組合下的方向平均偏差為0.159 m，方向平均偏差為0.075 m，全站組合下的方向平均偏差為-0.164 m，方向平均偏差0.081 m。

對B點進行測試，最優(yōu)基站布局對應BS1，BS2，BS8坐標位置，5G終端對應B點坐標位置，對最優(yōu)基站組合下終端解算觀測次數(shù)為500次。

表5和表6為B測試點下的最優(yōu)基站組合與全站的測試結(jié)果，其中，在495次的有效測試點中，最優(yōu)組合的最大單次解算耗時為0.234 s，平均單次解算耗時為0.128 s。在494次有效測試點中，全站參與下的最大解算耗時為0.354 s，平均單次解算耗時為0.262 s，可以看出本文所提算法在效率上提高了51.14%。

表5 B點最優(yōu)組合下的測試結(jié)果

表6 B點全站組合下的測試結(jié)果

圖7為B點在最優(yōu)基站組合與全站組合下單方向誤差比較，可以看出，最優(yōu)基站組合方向和方向上的均方根誤差均小于全站參與，最優(yōu)組合下的方向平均偏差為0.348 m，方向平均偏差為-0.069 m，全站組合下的方向平均偏差為-0.350 m，方向平均偏差為0.065 m。

3 結(jié)語

本文通過使用廣度優(yōu)先遍歷搜索篩選出HDOP最小的定位基站組合，在5G系統(tǒng)大量TDOA觀測量的前提下，剔除了誤差較大的觀測量，能夠在保證定位精度的前提下提高定位響應速度。特別地，當最優(yōu)定位基站組合為距離目標終端最近的3個基站，單次解算速度提升最快，相比全站參與解算速度提升了51.14%，說明本算法具有較強的實時性。本文通過最優(yōu)定位基站組合與全基站定位誤差比較，可以得出最優(yōu)基站組合的HDOP值與全站HDOP值相差越大，定位精度提升越好。

[1] XIE T, JIANG H J, ZHAO X J, et al. A Wi-Fi-based wireless indoor position sensing system with multipath interference mitigation[J]. Sensors, 2019, 19(18): 1-20.

[2] KEONSOO L, NAM Y Y, MIN S D. An indoor localization solution using bluetooth RSSI and multiple sensors on a smartphone[J]. Multimedia Tools and Applications, 2018, 77(10): 12635-12654.

[3] LIE M M K, KUSUMA G P. A fingerprint-based coarse-to-fine algorithm for indoor positioning system using bluetooth low energy[J]. Neural Computing and Applications, 2020, 33(1): 1-17.

[4] 孫頂明. 基于CHAN-Taylor的室內(nèi)復雜環(huán)境UWB定位算法研究[D]. 南京: 南京郵電大學, 2019.

[5] BAKKALI M E, TOUHAMI N A, ELHAMADI T E, et al. High gain 0.18μm-GaAs MMIC cascode-distributed low-noise amplifier for UWB application[J]. Microelectronics Journal, 2020, 108(1): 104970.

[6] Networks-wireless communications and networks; Researchers from tampere university of technology describe findings in wireless communications and networks (joint device positioning and clock synchronization in 5G ultra-dense networks)[J]. Computers, Networks & Communications, 2017.

[7] 3GPP.3GPP TS 22.261 v16.7.0, Service Requirements for the 5G system; Stage 1[EB/OL]. (2017-03-13)[2021-03-18].https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=3107

[8] 劉翔翔, 張昌瀚. 基于地理信息系統(tǒng)的通信基站優(yōu)化選址與布局[J]. 科技和產(chǎn)業(yè), 2020, 20(9): 191-197+224.

[9] 蘇煜琴, 付小寧, 張娜. TDOA localization algorithm based on lagrange constraint factor to modify the initial value of iteration[J]. 應用數(shù)學進展, 2020, 9(3): 372-381.

[10] GADKA P, SADOWSKI J, STEFANSKI J, et al. Detection of the first component of the received LTE signal in the OTDoA method[J]. Wireless Communications and Mobile Computing, 2019: 1-12.

[11] LEE K, LEE D H, HWANG W J, et al. A new D2D-Aided OTDOA positioning method for 3GPP LTE system[J]. IEICE Transactions on Communications, 2017, E100, B(3): 473-483.

[12] 王寶全. 基于TDOA參數(shù)估計的LTE定位技術(shù)研究[D]. 南京: 南京郵電大學, 2015.

[13] 李典鋒. LTE及其演進系統(tǒng)中定位技術(shù)的研究[D]. 北京: 北京郵電大學, 2018.

[14] 3GPP.3GPP TR22.872 v16.1.0, Study on Positioning Use Cases; Stage 1[EB/OL]. (2017-03-13)[2021-03-18].https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=3280.

[15] MISHRA P, KUMAR V, RANA K P S. An efficient method for parameter estimation of a nonlinear system using backtracking search algorithm[J]. Engineering Science and Technology, an International Journal, 2018, 21(3): 338-350.

[16] DINIYA J, SHONEY S. Taylor series method in TDOA approach for indoor positioning system[J]. International Journal of Electrical and Computer Engineering, 2019, 9(5): 3927-3933.

[17] KOHLER M, KRZY?AK A. Pricing of American options in discrete time using least squares estimates with complexity penalties[J]. Journal of Statistical Planning and Inference, 2012, 142(8): 2289-2307.

[18] 蔣康榮. 蜂窩網(wǎng)絡中基于TDOA的定位算法研究[D]. 南京: 南京郵電大學, 2016.

[19] ZHANG H W, ZHENG Z, WANG W Q, et al. Source localization using TDOA and FDOA measurements under unknown noise power knowledge[J]. IET Signal Processing, 2020, 14(7): 435-439.

[20] 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(2): 142-152.

[21] TOVKACH I O, ZHUK S Y. Adaptive filtration of parameters of the UAV movement based on the TDOA-measurement sensor networks[J]. Journal of Aerospace Technology and Management, 2019, 11(11): 1-10.

[22] 趙擁軍, 趙勇勝, 趙闖. 基于正則化約束總體最小二乘的單站DOA-TDOA無源定位算法[J]. 電子與信息學報, 2016, 38(9): 2336-2343.

[23] 竇雪倩, 李華, 許博. 基于幾何稀釋度的多站外源時差定位最優(yōu)布站方法[J]. 電子信息對抗技術(shù), 2018, 33(5): 37-40+72.

[24] 邱明, 嚴勇杰, 孫蕊, 等. 基于帝國競爭優(yōu)化的雙目標綜合決策選星算法[J/OL]. 北京航空航天大學學報: 1-12[2021-03-17]. https://doi.org/10.13700/j.bh.1001-5965.2020.0235.

[25] 王永梅. GNSS導航系統(tǒng)快速選星算法研究[J]. 電子設計工程, 2018, 26(3): 65-69.

[26] BANERJEE N, SANKARDEEP C, RAMAN V, et al. Space efficient linear time algorithms for BFS, DFS and applications[J]. Theory of Computing Systems, 2018, 62(8): 1736-1762.

[27] GYO X S, ZHANG Y, ZENG B T. Passive localization using time difference of arrival and frequency difference of arrivalWC[J]. Journal of Computer and Communications, 2018, 6(1): 21-29.

[28] 孟慶偉.Prim(普里姆)算法與Dijkstra(迪杰斯特拉)算法分析比較[J]. 計算機光盤軟件與應用, 2013(16): 96-97.

[29] ROSADO J A D P, SALCEDO J A L, GRANADOS G, et al. Preliminary analysis of the positioning capabilities of the positioning reference signal of 3GPP LTE[C]//Proceedings of the 5th European Workshop on GNSS Signals and Signal Processing, Toulouse, 2011.

Positioning algorithm based on the time difference of arrival with the minimum HDOP of station selection

WANG Teng-hui1,2, WU Jian-feng1, JIAO Xi-kang1,2, ZHU Jing-chuan1,2

(1. National Time Service Center, Chinese Academy of Sciences, Xi’an 710600, China;2. School of Electronic, Electrical and Communication Engineering, University of Chinese Academy of Sciences, Beijing 101048, China)

The traditional cellular network system supports the positioning method based on the time difference of arrival (TDOA), but the precision is poor. The 5th-generation mobile communication (5G) can provide accurate multiple TDOA measurement values in the indoor positioning distribution system, which can improve the indoor positioning capability significantly. With the large-scale popularization of 5G micro base stations, the target terminal can select more measurement values from the base stations, then the calculation of speed measurement is much larger and the observation values with big errors cannot be eliminated while used the traditional method for the calculation directly. This study proposes a method of optimal combination for positioning base stations, which used the breadth-first search (BFS) to filter out the minimum HDOP (horizontal dilution of precision) of the positioning base station combination, and it also considered the different variance of each TDOA measurement, then used the weighted least squares to estimate the location of the target terminal. The simulation analysis and experimental verification shown that the positioning algorithm based on the time difference of arrival with the minimum HDOP of station selection ensures the positioning accuracy, and it also increased the speed of single positioning solution by 51.14%, which significantly improves the speed of positioning response.

time difference of arrival; 5G system; horizontal dilution of precision(HDOP); breadth first search; least squares estimation

10.13875/j.issn.1674-0637.2021-03-0183-14

王騰輝, 武建鋒, 焦喜康, 等. 基于最小HDOP選站下的到達時間差定位算法[J]. 時間頻率學報, 2021, 44(3): 183-196.

2021-04-19；

2021-05-21

二代導航重大專項資助項目（ZFS19001D（03））