卞佳興，朱 榮，陳 玄

(武漢大學 計算機學院，武漢 430072)(*通信作者電子郵箱zhurong@whu.edu.cn)

基于改進雙向測距-到達時間差定位算法的超寬帶定位系統(tǒng)

卞佳興，朱 榮*，陳 玄

(武漢大學 計算機學院，武漢 430072)(*通信作者電子郵箱zhurong@whu.edu.cn)

針對傳統(tǒng)無線定位技術在室內定位精度不高的問題，設計實現(xiàn)了一種基于超寬帶(UWB)技術的室內定位系統(tǒng)。首先，提出了定位服務器與移動端APP實時交互的系統(tǒng)結構，解決室內移動人員自主定位與導航的問題。其次，在雙向測距(TWR)算法中增加一條無線電信息以減小時鐘偏移引起的測距誤差，從而提高算法性能。最后，將通過到達時間差(TDOA)定位算法得到的雙曲面方程組進行線性化處理后結合Jacobi迭代法完成求解，避免了使用標準TDOA定位算法難以直接解算的情況。經(jīng)測試，該系統(tǒng)在樓道房間等場景中能穩(wěn)定工作且定位誤差控制在30 cm以內，相比基于WiFi、藍牙等技術的定位系統(tǒng)在定位精度上提高了10倍左右，能夠滿足在復雜室內環(huán)境中的精確移動定位需求。

室內定位；超寬帶；雙向測距；到達時間差

0 引言

隨著智能設備的普及和移動互聯(lián)網(wǎng)的發(fā)展，人們對室內定位的需求也日益增加?；谑覂鹊奈恢梅湛梢灾С衷S多應用場景，比如公共安全及應急響應、定位導覽和交友互動等。基于全球定位系統(tǒng)(Global Positioning System, GPS)和地圖的位置服務已被廣泛應用，但由于GPS定位信號無法穿透建筑物，其在室內已無法正常工作。為了克服GPS的定位缺陷并實現(xiàn)在復雜室內環(huán)境中的精確定位，國內外研究人員在室內定位中引入了紅外線、WiFi、藍牙、ZigBee、超聲波、射頻識別(Radio Frequency Identification, RFID)等多種技術。紅外線[1]由于本身的特性覆蓋范圍較窄，而且易受外界環(huán)境的影響，定位精度只能達5 m。WiFi[2]、藍牙[3]、ZigBee[4]只能定位約幾十米的區(qū)域，其定位精度也只能達3 m，無法滿足精確室內移動定位需求。超聲波[5]室內定位受多徑和非視距的影響，室內定位效果較差。而RFID[6]技術只能進行存在識別，無法實時定位，定位精度也在5 m左右。

超寬帶(Ultra WideBand, UWB)[7]技術是一種無載波的通信技術，它利用納秒級或納秒以下的極窄脈沖信號來傳輸數(shù)據(jù)，這使得超寬帶信號有著很高的時間分辨率，進而能夠實現(xiàn)很高的定位精度，而且其功耗低、抗多徑效果好、安全性高、系統(tǒng)復雜度低，能夠基本彌補上述技術的缺點，將會成為未來室內定位的優(yōu)先選擇之一。因此，本文基于超寬帶技術設計了一套無線室內定位系統(tǒng)，采用改進的雙向測距(Two-Way Ranging, TWR)算法提高測距精度，針對到達時間差(Time Difference Of Arrival, TDOA )算法在誤差存在的情況下難以求解的問題，提出了改進的TDOA定位算法，最后基于Android平臺實現(xiàn)。將該系統(tǒng)應用到電廠巡檢人員定位的場景，實驗證明了整個系統(tǒng)的可行性，定位算法的精度達到30 cm。系統(tǒng)可以對電廠中需要追蹤的巡檢人員位置進行實時精確定位，同時也可以幫助巡檢人員導航。

1 系統(tǒng)結構設計

本文提出的室內定位系統(tǒng)結構如圖1所示。系統(tǒng)由標簽、基站、路由器、定位服務器以及移動端APP組成。標簽由巡檢人員隨身攜帶，基站安裝在工廠四周，當巡檢人員在該局域網(wǎng)內通過手機登錄移動端APP后，就可以在工廠內實現(xiàn)實時精確定位與導航。以4個定位基站組成的系統(tǒng)為例，理論上可以覆蓋上萬平米左右的范圍，增加基站數(shù)可以進一步擴大定位場景。

圖1 系統(tǒng)結構圖

標簽在固定的時隙內發(fā)送超寬帶信號，各定位基站截獲此信號后調用測距算法獲得與標簽之間的距離，然后將距離信息通過路由器以無線方式傳送至定位服務器，最后由定位服務器調用定位算法對標簽進行定位并將定位結果實時推送至移動端APP顯示。因此，整套系統(tǒng)的工作流程主要由測距和定位兩個部分組成，精確的測距算法是實現(xiàn)精確定位的前提和基礎。

2 測距算法設計

距離測量是超寬帶定位的第一步。雙向測距(TWR)[8]是通過確定兩個物體之間信號的飛行時間來計算距離，物體之間的距離可以用無線電波的速度與飛行時間相乘計算得到。本文采用改進的TWR算法，提高了測距階段的測距精度。

2.1 TWR算法

系統(tǒng)的超寬帶無線收發(fā)模塊選用半導體公司DecaWave推出的DWM1000模塊[9]。如果使用一對DWM1000，分別設計為設備A和設備B。設備A作為距離測量的發(fā)起者可以發(fā)起測距請求，而設備B作為響應者可以偵聽和響應設備A發(fā)來的無線電信息，那么對于基本的雙向測距可以作如下描述：A給B發(fā)送一個無線電信息并記錄它的發(fā)送時間戳t1，B接收到了信息并在一個特定的時延treplyB后發(fā)送一個回復給A，最后A接收到回復并記錄一個接收時間戳t2。其測距過程如圖2所示。

利用各自的本地時鐘，設備A可以知道自己的發(fā)送時間戳t1和接收時間戳t2，從而計算出計算出往返時間：

troundA=t2-t1

(1)

而設備B可以知道自己的時延treplyB，則信號的飛行時間可以由下面的公式確定：

TOF=(t2-t1-treplyB)/2

(2)

如果認為無線電波在空氣中的傳播速度等于光速c的話，那么A和B之間的距離R可以由下面的公式計算得到：

(3)

圖2 雙向測距過程

2.2 改進的TWR算法

在使用上述的雙向測距方法來進行測距時，由于時鐘偏移會引起較大的誤差[10-11]。假定設備A和設備B相對于它們的標稱頻率都有一個固定的時鐘偏移誤差，分別設為eA和eB。接下來對TWR算法的誤差進行分析，并考慮如何對其進行改進。在雙向測距過程中，設備A的往返時間為：

troundA=2TOF+treplyB

(4)

提取出飛行時間：

(5)

考慮到時鐘偏移，設備A實際得到的飛行時間估計為：

(6)

則飛行時間估計與真實的飛行時間之間的差值為：

(7)

為了減少時鐘偏移引起的誤差，需要對上述的雙向測距算法進行改進。本文設計的一種改進做法是：當A接收到回復并記錄一個接收時間戳t2后，再經(jīng)過一個特定的時延treplyA發(fā)送一個無線電信息給B并記錄自己的發(fā)送時間戳t3，最后B接收到了信息并記錄一個接收時間戳t4。圖3展示了這種改進的雙向測距過程。

利用t0和t4，設備B可以計算出往返時間troundB；利用t1和t2，設備A可以計算出往返時間troundA；treplyA和treplyB均已知，則可以得到：

TroundA=TreplyB+2TOF=t2-t1

圖書館以積分的形式實時累計、查詢、顯示某段時間(年度、季度或月)讀者的閱讀量，再利用最新的網(wǎng)絡科技手段創(chuàng)新閱讀文化活動，使閱讀的專欄集趣味性、導讀性和參與性一體，激發(fā)讀者閱讀的主觀能動性，更進一步強化閱讀興趣。如武漢大學圖書館開展的“拯救小布之消失”的經(jīng)典活動，以動漫游戲的方式，讓讀者通過娛樂回答與名家經(jīng)典相關的問題，完成闖關?；陂喿x積分制的閱讀推廣平臺可以參考此方式，使讀者獲得閱讀積分，贏得禮品，晉升等級，滿足自己的成就感和自豪感。通過閱讀積分制，在讀者和讀者之間形成一種閱讀競爭的場面[4]。

(8)

TroundB=TreplyA+2TOF=t4-t0

(9)

那么，信號的飛行時間可以表示為：

TOF=(troundA-treplyA+troundB-treplyB)/4

(10)

對改進的雙向測距算法也進行誤差分析。考慮到時鐘偏移，設備B實際得到的飛行時間估計為：

(11)

則飛行時間估計與真實的飛行時間之間的差值為：

(12)

令treplyA=treply，treplyB=treply+Δreply，那么差值變?yōu)椋?/p>

(13)

比較兩種測距方式的誤差可知，Δ2<Δ1，即采用改進的雙向測距算法在時鐘偏移的情況下比基本的雙向測距算法具有更高的測距精度。

圖3 改進的雙向測距過程

3 定位算法設計

3.1 TDOA定位算法

目前，超寬帶定位技術通常運用到達時間差(TDOA)[12-13]方法來實現(xiàn)定位。假設三維空間中分布著N個定位基站，定位標簽的位置為(x,y,z)，第i個基站的位置為(xi,yi,zi)，其與定位標簽之間的距離為Ri(i=1,2,…,N)，則基于TDOA的三維定位分布示意圖如圖4所示。

圖4 基于TDOA的三維定位分布示意圖

定位標簽作為被定位的目標，其位置需要調用定位算法被實時解算出來；而定位基站作為定位的參考節(jié)點，其位置在調用定位算法之前已知。TDOA定位算法的具體計算過程是：在前面測距的過程中可以獲得標簽與每個基站之間的到達時間(即信號的飛行時間)，每兩個到達時間之間的差值就是TDOA測量值，利用TDOA測量值可以計算出定位目標與兩個基站之間的距離差，多個TDOA測量值計算距離差的方程便構成了一個關于目標位置的雙曲面方程組，求解該方程組就可以得到目標的估計位置。

由此可以得到TDOA方程組：

(14)

其中τi就是各自對應的飛行時間估計TOF，各基站與定位標簽之間的距離為：

(15)

3.2 改進的TDOA定位算法

標準TDOA定位算法中的雙曲面非線性方程組難以求解，本文利用數(shù)學方法對非線性方程組進行了線性化處理?？紤]到測距誤差和非視距(Non-line Of Sight, NLOS)誤差的存在，并沒有采用Fang算法[14-15]之類的非迭代算法進行直接解算，而是基于Jacobi迭代法[16]進行求解，避免了非迭代算法無法直接解算的情況。

首先，將式(15)兩邊同時取平方可得：

Ri2=Ki-2xix-2yiy-2ziz+x2+y2+z2

(16)

定位標簽與第i個基站和與基站1的距離差為：

Ri,1=cτi,1=c(τi-τ1)=Ri-R1

(17)

其中τi,1為TDOA的測量值。由于：

Ki-2xix-2yiy-2ziz+x2+y2+z2

(18)

令i=1可得：

R12=K1-2x1x-2y1y-2z1z+x2+y2+z2

(19)

式(18)～式(19)，整理后可以得到：

(20)

其中：xi,1=xi-x1，yi,1=yi-y1，zi,1=zi-z1。把x、y、z看成未知數(shù)，式(20)就變成了線性方程組。

AX=b

(21)

其中，系數(shù)矩陣A和矩陣b均為常數(shù)矩陣，式(21)表示的是一個線性方程組，求解出線性方程組中x、y、z的值便可以得到標簽的位置坐標。

由于測距過程中會有誤差，而且當其中某個或某些基站與標簽之間存在NLOS通信時，還會帶來NLOS誤差，TDOA的3個雙曲面就無法交于一點，而是形成一定的區(qū)域，目標的估計位置就將落在這一隨機區(qū)域內，顯然，使用Fang算法之類的非迭代算法直接進行求解是得不到估計位置的值的。

本文基于Jacobi迭代法進行了求解，可以得到目標估計位置的精確近似值。Jacobi迭代法計算公式簡單，每迭代一次只需計算一次矩陣和向量的乘法，且計算過程中原始矩陣A始終不變，比較容易并行計算。

基于Jacobi迭代法求解的主要步驟：

1)用兩個一維數(shù)組X0=(x0,y0,z0)和X1=(x1,y1,z1)存放相鄰兩次的迭代結果。任意選定初始向量存放在X0中。用(X0)i、(X1)i分別表示第i個數(shù)組元素。

3)用變量ε存放迭代誤差界，當δ<ε時，停止迭代，(X1)i(i=1,2,…,n)為近似解。

圖5 改進的定位算法工作流程

4 系統(tǒng)實現(xiàn)

系統(tǒng)實現(xiàn)包括硬件實現(xiàn)和軟件實現(xiàn)兩部分。在硬件實現(xiàn)部分，為基站和標簽設計了電路并完成了超寬帶測距通信程序設計?；颈葮撕灦嗔艘粋€型號為ESP8266的WiFi模塊，用于與服務器建立連接，它們都采用STM32103RC作為控制單元以及DWM1000模塊作為超寬帶無線收發(fā)模塊。超寬帶測距通信程序設計時，選擇110 kb/s的傳輸數(shù)據(jù)率、中心頻率為3 993.6 MHz的信道以及499.2 MHz的帶寬，可以很好地兼顧工作范圍和功率消耗兩方面。標簽采用了小尺寸設計，標簽和基站實物分別如圖6所示。

圖6 標簽和基站實物圖

軟件實現(xiàn)部分，基于Android平臺設計了定位服務器程序并開發(fā)了室內定位APP。室內定位APP的實時定位模塊如圖7所示，實時定位模塊主要是用來幫助巡檢人員實現(xiàn)精確定位與導航，通過WiFi網(wǎng)絡自動更新地圖可切換到其他工作場景。

圖7 實時定位界面圖

5 實驗與誤差分析

5.1 測距誤差分析

為兩種測距算法分別設計了程序，對各自的測距誤差進行了實驗對比。在10 m的測距范圍內，每隔1 m設置一個距離點，在每個距離點上都采集了大量的測量值，分別取各自測量值的平均值進行比較，如表1所示。從表中可以看出，改進的雙向測距誤差始終是小于基本的雙向測距的，距離測量值的均方差在大多數(shù)情況下也是小于基本的雙向測距的，即數(shù)據(jù)波動性更小。實驗結果也表明，增加一次無線電信息的發(fā)送之后，系統(tǒng)在測距階段的測距精度更高。

表1 兩種測距方式誤差對比

5.2 定位誤差分析

本文選擇12.3 m×7 m的矩形會議室作為測試場地，如圖8所示。定位時，隨機在會議室中行走，記錄下定位數(shù)據(jù)和此時位置。測試時，在測試場地的二維平面地圖上選取了38個基準點進行了誤差分析，每個基準點上面的定位數(shù)據(jù)作為測量點，結果如圖9所示。

圖8 測試場地圖

圖9 實際定位結果

從圖9中可以看出，測量點與基準點的在橫向或縱向上的偏差都在30 cm之內，能夠滿足精準室內移動定位的需求。為了更具體地描述系統(tǒng)定位誤差，從38個基準點中挑選出了10個在位置上具有代表性的點，將每個點上的定位結果與其實際坐標進行比較，計算出定位誤差，結果如表2所示。從表中可以看出，10組定位結果的平均誤差為12 cm，最小誤差為5 cm，最大誤差為26 cm。測試過程中沒有出現(xiàn)無定位或偏離較大的情形，說明系統(tǒng)也具有很好的穩(wěn)定性。

表2 實際坐標與定位結果比較

本文將定位算法應用在了小范圍的精確定位，測試時使用了4個基站，定位服務器獲取了3組TDOA數(shù)據(jù)，組成了一個定位單元，其誤差可以控制在30 cm之內。當需要應用到更大范圍的場景中時，增加基站數(shù)，把多個定位單元求解結果的均值作為最終定位結果可以有效減小定位誤差。

6 結語

基于超寬帶技術設計了一套室內定位系統(tǒng)，描述了系統(tǒng)結構，重點研究了系統(tǒng)的測距算法和定位算法實現(xiàn)。對雙向測距算法進行了改進，增加一次無線電信息的發(fā)送，可以減小由于時鐘偏移引起的誤差，有效地提高系統(tǒng)的測距精度。對基本的TDOA定位算法也進行了改進，加入了線性化處理與Jacobi迭代求解，避免了方程組由于誤差存在而無法直接解算的情況，有利于系統(tǒng)的穩(wěn)定性。經(jīng)測試，該系統(tǒng)定位精度達30 cm，可在多種場景下進行使用，能夠彌補GPS以及WiFi、藍牙對室內高精度定位無法滿足的情形，且該定位系統(tǒng)具有成本低、軟件易擴展的特點。目前主要實現(xiàn)了定位功能，未來在此基礎上可擴展服務信息推送、社交等更多元化功能，顯著提升基于室內的位置服務品質。

References)

[1] 吳軍,于之靖,諸葛晶昌,等.采用紅外掃描激光與超聲技術的室內空間定位[J].光學精密工程,2016,34(10):2417-2423.(WU J, YU Z J, ZHUGE J C, et al. Indoor positioning by using scanning infrared laser and ultrasonic technology [J]. Optics and Precision Engineering, 2016, 34(10): 2417-2423.)

[2] 王陽,葉芝慧,馮奇,等.基于Android的室內WiFi定位系統(tǒng)設計與實現(xiàn)[J].電子測量技術,2016,39(9):16-19.(WANG Y, YE Z H, FENG Q, et al. Design of indoor WiFi positioning system based on Android platform and its implementation [J]. Electronic Measurement Technology, 2016, 39(9): 16-19.)

[3] KAJIOKA S, MORI T, UCHIYA T, et al. Experiment of indoor position presumption based on RSSI of Bluetooth LE beacon [C]// Proceedings of the 2014 IEEE 3rd Global Conference on Consumer Electronics. Piscataway, NJ: IEEE, 2015: 337-339.

[4] HUANG C N, CHAN C T. ZigBee-based indoor location system byk-nearest neighbor algorithm with weighted RSSI [J]. Procedia Computer Science, 2011, 5: 58-65.

[5] LINDO A, GARCIA E, URENA J, et al. Multiband waveform design for an ultrasonic indoor positioning system [J]. IEEE Sensors Journal, 2015, 15(12): 7190-7199.

[6] 李軍懷,賈金朋,王懷軍,等.基于信號強度差的RFID室內定位研究[J].計算機科學,2015,42(11):154-157.(LI J H, JIA J P, WANG H J, et al. Research on SSD-based RFID indoor location method [J]. Computer Science, 2015, 42(11): 154-157.)

[7] SHI G, MING Y. Survey of indoor positioning systems based on Ultra-WideBand (UWB) technology [M]// Wireless Communications, Networking and Applications. Berlin: Springer, 2016: 1269-1278.

[8] KREISER D, MARTYNENKO D, KLYMENKO O, et al. Simple and efficient localization method for IR-UWB systems based on two-way ranging [C]// Proceedings of the 2015 IEEE MTT-S International Conference on Microwaves for Intelligent Mobility. Piscataway, NJ: IEEE, 2015: 1-4.

[9] DecaWave. DWM1000 datasheet [R]. Dublin, Ireland: Deca-Wave, 2016.

[10] DecaWave. Application note: APS011 [R]. Dublin, Ireland: DecaWave, 2014.

[11] LIM J M, YOO S H, PARK J K, et al. Error analysis of cooperative positioning system using two-way ranging measurements [C]// Proceedings of the 2014 8th International Conference on Signal Processing and Communication Systems. Piscataway, NJ: IEEE, 2014: 1-4.

[12] KOLAKOWSKI M, DJAJA-JOSKO V. TDOA-TWR based positioning algorithm for UWB localization system [C]// Proceedings of the 2016 21st International Conference on Microwave, Radar and Wireless Communications. Piscataway, NJ: IEEE, 2016: 1-4.

[13] 蔣康榮.蜂窩網(wǎng)絡中基于TDOA的定位算法研究[D].南京:南京郵電大學,2016:25-35.(JIANG K R. Study on positioning algorithms based on TDOA in cellular networks [D]. Nanjing: Nanjing University of Posts and Telecommunications, 2016: 25-35.)

[14] FANG B T. Simple solutions for hyperbolic and related position fixes [J]. IEEE Transactions on Aerospace & Electronic Systems, 1990, 26(5): 748-753.

[15] 王彪,傅忠謙.基于超寬帶技術的TDOA室內三維定位算法研究[J].微型機與應用,2013,32(14):83-86.(WANG B, FU Z Q. The research of TDOA indoor three-dimensional positioning algorithm based on ultra-wideband technology [J]. Microcomputer & Its Applications, 2013, 32(14): 83-86.)

[16] FANG X, WEI C. The general modulus-based Jacobi iteration method for linear complementarity problems [J]. Filomat, 2015, 29(8): 1821-1830.

Ultrawidebandlocalizationsystembasedonimprovedtwo-wayrangingandtimedifferenceofarrivalpositioningalgorithm

BIAN Jiaxing, ZHU Rong*, CHEN Xuan

(SchoolofComputer,WuhanUniversity,WuhanHubei430072,China)

Aiming at the poor positioning accuracy of traditional wireless indoor positioning technology, an indoor positioning system based on Ultra Wide Band (UWB) technology was designed and implemented. Firstly, to solve the problem of autonomous localization and navigation, the system architecture of real-time interaction between the location server and the mobile terminal APP was proposed. Secondly, a radio message was added to the Two-Way Ranging (TWR) algorithm to reduce the ranging error caused by clock drift, so as to improve the performance of the algorithm. Finally, the hyperboloid equation set achieved by Time Difference Of Arrival (TDOA) positioning algorithm was linearized and then solved by Jacobi iteration method, which avoids the cases that standard TDOA localization algorithm is difficult to directly solve. The test results show that the system based on this method can work stably and control the range of error within 30 cm in the corridor room scene. Compared with the positioning systems based on WiFi and Bluetooth, the positioning accuracy of this system is improved by about 10 times, which can meet the requirement of precise mobile positioning in complex indoor environment.

indoor positioning; Ultra Wide Band (UWB); Two-Way Ranging (TWR); Time Difference Of Arrival (TDOA)

2017- 03- 06;

2017- 04- 10。

武漢市應用基礎研究計劃項目(2016010101010025)。

卞佳興(1993—)，男，江蘇揚州人，碩士研究生，主要研究方向：多媒體網(wǎng)絡通信、物聯(lián)網(wǎng)； 朱榮(1964—)，男，湖北武漢人，副教授，博士，主要研究方向：多媒體網(wǎng)絡通信、人臉識別與可信身份認證； 陳玄(1990—)，男，湖北隨州人，碩士研究生，主要研究方向：圖像處理、模式識別。

1001- 9081(2017)09- 2496- 05

10.11772/j.issn.1001- 9081.2017.09.2496

TP393.09

A

This work is partially supported by the Basic Research Program of Wuhan (2016010101010025).

BIANJiaxing, born in 1993, M. S. candidate. His research interests include multimedia network communication, Internet of things.

ZHURong, born in 1964, Ph. D., associate professor. His research interests include multimedia network communication, face recognition and authentication.

CHENXuan, born in 1990, M. S. candidate. His research interests include image processing, pattern recognition.