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

基于最小HDOP選站下的到達(dá)時(shí)間差定位算法

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

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

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

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

0 引言

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

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

1 基于到達(dá)時(shí)間差的定位方法

1.1 TDOA定位原理

1.2 基于TDOA的定位解算算法

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

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

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

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

TDOA噪聲的線性方程為

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

建立線性方程組：

1.3 水平精度分析

令方向余弦

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

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

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

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

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

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

圖1 BFS算法選站流程圖

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

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

圖2 地下試驗(yàn)場真實(shí)場景

圖3 模擬場景俯視圖

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

圖4 A、B點(diǎn)俯視圖

圖4中圓點(diǎn)為測試坐標(biāo)點(diǎn)，小三角為基站坐標(biāo)點(diǎn)，其中，距離A點(diǎn)最近的3個(gè)基站為BS3，BS6，BS7，距離B點(diǎn)最近的3個(gè)基站為BS1，BS2，BS8。

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

表1 A測試點(diǎn)的基站組合及HDOP值

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

表2 B測試點(diǎn)的基站組合及HDOP值

圖5 本次測試的主要設(shè)備

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

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

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

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

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

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

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

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

圖7為B點(diǎn)在最優(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īng)速度。特別地，當(dāng)最優(yōu)定位基站組合為距離目標(biāo)終端最近的3個(gè)基站，單次解算速度提升最快，相比全站參與解算速度提升了51.14%，說明本算法具有較強(qiáng)的實(shí)時(shí)性。本文通過最優(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)復(fù)雜環(huán)境UWB定位算法研究[D]. 南京: 南京郵電大學(xué), 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]. 應(yīng)用數(shù)學(xué)進(jìn)展, 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ù)估計(jì)的LTE定位技術(shù)研究[D]. 南京: 南京郵電大學(xué), 2015.

[13] 李典鋒. LTE及其演進(jìn)系統(tǒng)中定位技術(shù)的研究[D]. 北京: 北京郵電大學(xué), 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)絡(luò)中基于TDOA的定位算法研究[D]. 南京: 南京郵電大學(xué), 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]. 電子與信息學(xué)報(bào), 2016, 38(9): 2336-2343.

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

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

[25] 王永梅. GNSS導(dǎo)航系統(tǒng)快速選星算法研究[J]. 電子設(shè)計(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]. 計(jì)算機(jī)光盤軟件與應(yīng)用, 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選站下的到達(dá)時(shí)間差定位算法[J]. 時(shí)間頻率學(xué)報(bào), 2021, 44(3): 183-196.

2021-04-19；

2021-05-21

二代導(dǎo)航重大專項(xiàng)資助項(xiàng)目（ZFS19001D（03））