DS-TWR算法室內定位批量測距系統的優化研究

2022-02-12 03:12:26孫宏偉曹雪虹焦良葆孟琳劉子恒袁楓

電信科學 2022年1期

孫宏偉，曹雪虹，焦良葆，孟琳，劉子恒，袁楓

研究與開發

孫宏偉，曹雪虹，焦良葆，孟琳，劉子恒，袁楓

（南京工程學院人工智能產業技術研究院，江蘇南京 211167）

針對現階段基于雙邊雙向測距（double sided two-way ranging，DS-TWR）算法的超寬帶（ultra wide band，UWB）室內定位系統存在通信次數較多、多標簽環境下沖突率較高的問題，提出了一種改進的算法。該方法通過Hash算法對標簽和基站的通信內容進行哈希分布，使得基站在每次測距流程中，能夠對多個標簽進行有規則的統一回復，大大減少了基站發送RES（responds）數據的次數。結果表明，改進算法后，單個標簽和基站的通信次數較傳統DS-TWR算法減少了15%，增加了基站接收狀態在測距中的時間占比，由此降低了基站在接收RNG（range）數據包的沖突率，測距成功率提高了43.6%。由于每個定位周期內所需要通信次數的減少且數據包之間沖突率的降低，將需要更小的信道容量，由此增加了定位系統的標簽容納量，具有較強的工程意義。

超寬帶定位；室內定位；哈希算法；雙邊雙向測距

0 引言

隨著5G通信技術和新能源汽車的發展，電力需求量日益增加。在電力系統前端，尤其是在具有安全風險的礦井、發電廠和變電站等環境中，電能在大量產出的同時也伴隨著風險的提高[1-2]。高速準確的定位系統能夠給作業人員提供更大程度的安全保護[3]。現階段，國內外的室內定位技術主要有全球定位系統（global positioning system，GPS）、無線局域網（wireless local area network，WLAN）、超寬帶（ultra wideband，UWB）等[4]。GPS在理想情況下精度能夠達到3 m，單純的GPS無法滿足工業生產需要的高精度定位需求[5]。現階段WLAN定位被廣泛應用于商場等公共場合，但常見的WLAN定位系統傳輸距離短，可傳輸數據量小，不適用于工業生產[6]。UWB在復雜的工業環境下有相當顯著的優點[7]：定位精度高、具有較強的穿透性、抗干擾能力強、功耗低[8]。基于綜合考量，本文選用UWB進行室內定位。

目前，接收信號強度（received signal strength，RSS）、到達角度測距（angle of arrival，AOA）、信號到達時間（time of arrival，TOA）、信號到達時間差（time difference of arrival，TDOA）、DS-TWR（double sided two-way ranging）等測距算法比較常見[9]，其中TOA和TDOA算法應用較為廣泛[10]。TDOA算法能夠實現標簽與基站僅需一次通信即可完成測距，但需要所有基站的時鐘完全同步，工程實現比較困難[11]。TOA算法利用測距信號在標簽和基站之間的飛行時間計算距離，在TOA算法基礎上衍生出的DS-TWR算法，通過標簽和基站的多次通信實現了無須時鐘同步的測距算法[12]。顧慧東等[13]基于DS-TWR算法設計實現了基站對標簽的準確定位，定位精度為15～30 cm。該算法能夠消除時鐘同步引入的誤差，但在每個測距周期中需要基站和標簽多次通信，這在一定程度上增加了通信沖突概率并引起測距失敗，降低了整個系統的標簽容納量。袁楓等[14]提出了一種按時序分配標簽等待時間的方法，在通信沖突問題上有較好的效果，在對60個標簽進行定位的測試中，實現了通信沖突率降低13%，提高了多標簽下的通信成功率。但是此方案維持了傳統的DS-TWR的通信流程，無法減少測距過程中的通信次數，而沖突的發生是因為多標簽情況下通信次數的增加。

本文對通信流程做出如下改進：基站對標簽的應答不再是及時回復，而是經過一段時間后對所有標簽進行廣播回復，各標簽根據Hash算法從特定位置讀取基站的回復信息，最終利用DS-TWR算法解析數據包、計算位置信息。改進后的流程大幅減少了信道中的信息量，降低數據沖突概率，提高整個系統在準確定位前提下能夠容納的標簽數量（標簽容納量）。

1 傳統DS-TWR測距原理

DS-TWR算法是對雙向測距（two-way ranging，TWR）優化而來[15]，TWR不基于雙邊時間同步，實現簡單，但該算法受設備晶振偏移影響[16]，TWR測距流程如圖1所示，誤差函數如式（1）所示。

DS-TWR由此問題出發，著重于減少設備晶振對測距誤差的影響[18]。DS-TWR相比TWR測距算法，在每個測距周期內增加了一輪標簽和基站的通信流程，由此獲得了額外兩個時間節點，實現了一次測距流程獲得兩次距離結果[19]。DS-TWR測距流程如圖2所示，信號飛行時間如式（2）所示，誤差函數如式（3）所示。

對比式（1）和式（3），DS-TWR算法的誤差函數中，影響因素是節點A、B回復時間間隔的差值，在相同配置環境下，DS-TWR算法可以更容易控制并減小誤差[20]。

圖1 TWR測距流程

圖2 DS-TWR測距流程

誤差分析如圖3所示，由于晶振偏移引入的測距誤差限制了TWR測距精度；而DS-TWR測距算法可以人為地減小晶振偏移對最終測距結果的影響，使測距誤差可以滿足設計要求。

2 改進方案的實現

2.1 通信方法的改進

在通信過程中，理想的數字信道的信道容量滿足奈奎斯特準則：

圖3 誤差分析

其中，為信道容量，為帶寬，為信號編碼級數。

改進后的測距流程具體有以下5個步驟。

步驟1 標簽1向基站發送RNG_1數據包，并記錄發送數據包的時間戳TRNG1_tx。

圖4 改進后的通信流程

步驟5 基站接收到FIN_數據包后，記錄接收時間戳TFIN_n_rx，解析FIN_數據包獲取各個時間戳引入DS-TWR算法計算距離信息。

對于標簽1，記消息單次飛行時間為prop。由圖4可得以下計算式：

由式（4）～式（6）可得：

2.2 Hash分配數據包位置

改進后的測距流程的步驟（3）中，基站需要在RES數據包中加入多個標簽的回復信息，為了使標簽能夠讀取到正確數據，需要對RES數據包引入特定的構建規則。本文采用Hash算法對數據位置進行哈希分布。

哈希流程如下：基站接收RNG數據時，解析出RNG發送方MAC編號作為key進行Hash運算獲得Hash值，計算得出的Hash值與標簽數據位置對應。同時考慮到Hash沖突問題，即不同標簽計算后的Hash值相同，則通過再Hash算法，利用MAC編號和第一次Hash計算后的地址再次進行Hash運算，獲得新的Hash值。

本文Hash計算采用素數求余法，單次通信最大限制為1 023 byte，每個標簽需要的RES回復數據為12 byte，即單次回復標簽數量限制為85個，所以本文采用最大素數=83，RES數據包數據位置如圖5所示，計算式如式（9）所示。

若出現Hash沖突，則利用式（9）進行再Hash：

至此可以實現在0～82按相同概率分配數據位置。

利用Hash分布數據幀存放位置可以最大化利用數據包。相比較順序堆放數據幀，接收方在解析數據時需要遍歷數據包，極其浪費資源，尤其對標簽需要計量功耗的設備。利用Hash算法，可以減少標簽解析數據包所消耗的資源，即使出現Hash沖突，解析的次數也遠小于遍歷數據包的次數。該算法的引入可以在提升系統容納量的同時降低功耗。

圖5 RES數據包數據位置

圖5中，FC和SN作為數據包頭部，PANID為通信信道，?_0為延遲時間，DST_ADDR為目的設備編號，SCR_ADDR為發送設備編號，TYPE為數據包類型，FSC為效驗碼。

3 實驗結果

3.1 實驗環境

在硬件設計上，使用STM32高性能微處理器作為主控器件，配合DecaWave公司設計生產的DWM1000射頻收發芯片實現UWB信號的收發。考慮到基站需要進行通信、距離計算以及數據上報，且基站無須功耗控制，所以使用性能較強的STM32F407ZET6處理器，基站實物如圖6所示；標簽則采用體積小、功耗低的STM32F105RCT6處理器，標簽實物如圖7所示。

圖6 基站實物

圖7 標簽實物

在軟件設計上，此套定位系統分為上位機和下位機兩大部分。上位機為Linux系統的臺式計算機，通過用戶數據報協議（user datagram protocol，UDP）和基站保持定時通信，負責接收基站上報的測距信息并計算各標簽的三維空間坐標，實現室內精確定位。下位機由基站和標簽構成，其軟件開發通過Keil uVision5實現，軟件設計流程如圖8所示。

流程圖中IAP（in-application-programming，IAP）為遠程升級功能不參與測距。定時器1為測距周期定時器，基站側定時器2為接收超時定時器，定時器3為?定時器。基站測距前發送的BLK（blink，BLK）數據包是用來提供標簽通信注冊表信息。為了得出功耗和穩定性數據，本文采用兩個標簽和4個基站的最小系統進行測試，步驟如下。

步驟1 將改進前的代碼燒錄到兩個標簽和4個基站中，讓標簽電池保持滿電狀態。將其放在空曠且無遮擋的環境中，隨機選擇標簽放置點進行測距通信，直至標簽電量耗盡，測距終止，導出測距日志數據。

步驟2 將步驟（1）中的標簽和基站取下，分別燒錄改進后的通信代碼，給標簽電池重新充滿電量，保持基站和標簽位置不變進行測距通信直至標簽電量再次耗盡，導出測距日志數據。

在測試中，保持測試地點、測試設備以及測試位置均未改變，從而保證了測試環境的一致性，確保最終數據差異能夠顯著反映兩套系統的性能參數。

圖8 軟件設計流程

3.2 測距數據分析

將充滿電的標簽開啟后放置到測試環境中，直至標簽電量耗盡。在服務器上讀取標簽的定位信息日志進行分析，分析結果如圖9所示，測距軸數據見表1。

表1中樣本數量為基站和標簽之間的通信次數，通信時長為標簽從開始測距到電量耗盡時的運行時長，有效通信時長為標簽從開始測距至測距誤差出現顯著增加時的運行時長。

表1 測距X軸數據

由圖9和表1的數據分析可知，在電池充滿的情況下，原方案總通信時長和單位時間的樣本量大于改進后的方案，這是由于DWM1000射頻芯片接收功耗相較于發送功耗更大，而改進后的方案標簽的接收等待時間會大于原方案。但原始方案中電壓下降一定程度后，測距誤差明顯增大，無法達到定位要求，而改進后的方案在低電壓情況下較原方案有很大優勢，所以改進后的方案比原方案的有效通信時長并無顯著減少。同時在測距誤差方面，改進后的方案較原方案也有提升：對標簽1、2，測距標準差由原方案的2.282 39和0.993 38下降到了2.238 83和0.960 32。樣本數量由原方案791 711和785 710個下降至668 276和638 276個，分別降低了15.59%和18.76%。從測試結果分析可知，改進后的系統憑借通信流程的改進，在測距誤差未增加的情況下，通信次數顯著下降，具備更強的穩定性。

3.3 測距通信沖突分析

在實際測試通信沖突情況時，需要大量標簽同時運行，故本文采用MATLAB仿真模擬多標簽通信。模擬通信規則如下：設定4個基站，每個標簽和4個基站依次通信，如果標簽在發起通信的時刻，基站未處于接收狀態或基站正在與其他標簽通信，則標簽等待1 s后，繼續與下一個基站通信并記錄一次通信沖突，以此類推，最終統計通信成功的標簽數量。

改進前通信方法：從200個基站中隨機選擇4個基站，從500個標簽中隨機選擇60個標簽進行通信。按照單次通信2 ms，測距一次6 ms，定位周期400 ms進行仿真。改進前的通信分配情況如圖10所示，橫坐標表示單個標簽在定位周期中分配到的時刻，縱坐標表示60個標簽的通信空隙分配次數。

圖10 改進前的通信分配情況

改進后通信方法：從200個基站中隨機選擇4個基站，從500個標簽中隨機選擇60個標簽計算次數。按照單次通信2 ms，測距一次40 ms，第2～18 ms為基站接收時間，定位周期400 ms。改進后的通信分配情況如圖11所示，橫坐標表示第2.2節中計算出的83個分配到的時刻，縱坐標表示60個標簽的Hash計算次數。

分析仿真結果，獲得改進前系統存在21次通信分配沖突，最終實現了39個標簽的正常通信，沖突率為35%。袁楓等[14]論文中的方案實現了通信沖突由39%下降至26%。在本文改進后的系統中，最終實現通過240次Hash計算，56個標簽的正常通信，沖突率下降至6.7%。結果表明，改進后的通信流程能夠緩解通信沖突引發的通信失敗問題，測距成功率提高了43.6%。

圖11 改進后的通信分配情況

4 結束語

本文提出了一種基于DS-TWR算法的改進型通信方案，該方案增加了基站處于接收狀態的時長，確保了在標簽發送消息時基站能夠處于接收模式，有效減少整個系統完成測距所需要的通信次數，而通信次數的降低就可以降低沖突發生。同時引入Hash算法，在單次通信流程中對批量測距信息的位置進行離散分配，減少標簽解析數據包的時間，降低測距誤差的同時提高了測距成功率。該改進方案在人員聚集的環境下，能夠實現準確定位，在實際工程應用中有較大意義。

[1] 萬明遠. 火力發電廠當前面臨的問題及其對策[J]. 電子世界, 2017(11): 61.

WAN M Y. Current problems and countermeasures of thermal power plants[J]. Electronics World, 2017(11): 61.

[2] 常琳. UWB技術在精準人員管理系統中的應用[J]. 煤礦安全, 2021, 52(5): 163-165, 169.

CHANG L. Application of UWB technology in accurate personnel positioning system[J]. Safety in Coal Mines, 2021, 52(5): 163-165, 169.

[3] 趙林, 孫增榮, 王紀強, 等. 基于超寬帶技術的礦用人員精準定位系統[J]. 山東科學, 2021, 34(2): 48-53.

ZHAO L, SUN Z R, WANG J Q, et al. Precise positioning system for mine personnel based on ultra wide band technology[J]. Shandong Science, 2021, 34(2): 48-53.

[4] 陶偲. 基于UWB的室內SDS-TWR測距算法優化和定位算法融合的研究[D]. 武漢: 華中師范大學, 2016.

TAO (C/S). Research on optimization of SDS-TWR and fusion of location algorithm in indoor position based on UWB[D]. Wuhan: Central China Normal University, 2016.

[5] 劉關迪, 趙璐. 基于UWB技術的室內智能跟隨系統的實現與優化[J]. 計算機應用與軟件, 2020, 37(12): 95-100.

LIU G D, ZHAO L. Improvement and implementation of indoor intelligent following system based on UWB technology[J]. Computer Applications and Software, 2020, 37(12): 95-100.

[6] 葉偉. 煤礦井下目標定位的研究現狀與展望[J]. 中國礦業, 2021, 30(1): 82-89, 105.

YE W. Status and prospects of research on positioning of targets in underground coal mines[J]. China Mining Magazine, 2021, 30(1): 82-89, 105.

[7] 曾紀鈞, 沈桂泉, 張金波. 基于UWB定位技術的作業風險管控智能終端設備研究[J]. 電測與儀表, 2021: 1-9.

ZENG J J, SHEN G Q, ZHANG J B. Research on intelligent terminal equipment for operation risk management and control based on UWB positioning technology[J]. Electrical Measurement and Instrumentation, 2021: 1-9.

[8] 劉琦, 沈鋒, 王銳. 基于UWB定位系統硬件平臺設計[J]. 電子科技, 2019, 32(10): 22-27.

LIU Q, SHEN F, WANG R. Design of hardware platform for UWB positioning system[J]. Electronic Science and Technology, 2019, 32(10): 22-27.

[9] 朱冰, 陶曉文, 趙健, 等. 智能汽車兩階段UWB定位算法[J]. 交通運輸工程學報, 2021, 21(2): 256-266.

ZHU B, TAO X W, ZHAO J, et al. Two-stage UWB positioning algorithm of intelligent vehicle[J]. Journal of Traffic and Transportation Engineering, 2021, 21(2): 256-266.

[10] ZHANG W, ZHU X Z, ZHAO Z Q, et al. High accuracy positioning system based on multistation UWB time-of-flight measurements[C]//Proceedings of 2020 IEEE International Conference on Computational Electromagnetics. Piscataway: IEEE Press, 2020: 268-270.

[11] 許佩佩. 基于TOA方案的超寬帶室內定位技術研究[D]. 南京: 東南大學, 2016.

XU P P. Research of UWBindoor positioning technology based on TOA scheme[D]. Nanjing: Southeast University, 2016.

[12] SANGC L, ADAMSM, H?RMANNT, et al. Numerical and experimental evaluation of error estimation for two-way ranging methods[J]. Sensors (Basel, Switzerland), 2019, 19(3): 616.

[13] 顧慧東, 焦良葆, 周健. 室內UWB通信高精度定位系統設計[J]. 軟件導刊, 2020, 19(4): 159-163.

GU H D, JIAO L B, ZHOU J. Indoor high-precision positioning system design based on UWB[J]. Software Guide, 2020, 19(4): 159-163.

[14] 袁楓, 焦良葆, 陳楠, 等. 室內定位中DS-TWR測距算法的優化[J]. 計算機與現代化, 2021(10): 100-106.

YUAN F, JIAO L B, CHEN N, et al. Optimization of DS-TWR ranging algorithm in indoor positioning[J]. Computer and Modernization, 2021(10): 100-106.

[15] 劉永立, 吳聞軒, 單麒源, 等. 井下人員定位的超寬帶TWR改進算法[J]. 黑龍江科技大學學報, 2021, 31(2): 135-139.

LIU Y L, WU W X, SHAN Q Y, et al. Improvement algorithm of ultra wide band TWR for underground personnel positioning[J]. Journal of Heilongjiang University of Science and Technology, 2021, 31(2): 135-139.

[16] ZHANGK, SHENC, GAO Q, et al. Research on similarity metric distance algorithm for indoor and outdoor firefighting personnel precision wireless location system based on vague set on UWB[C]//Proceedings of 2017 IEEE 17th International Conference on Communication Technology. Piscataway: IEEE Press, 2017: 1162-1165.

[17] 嚴嘉祺. 基于UWB的室內定位系統的算法與誤差分析[D].哈爾濱工業大學, 2020.

YAN J Q. Algorithm and error analysis of indoor positioning system based on UWB[D]. Harbin Institute of Technology, 2020.

[18] LIU J H, JING H, XIANG Y X, et al. Simulation Research of UWB location algorithm[C]//Proceedings of 2018 Chinese Control and Decision Conference (CCDC). Piscataway: IEEE Press, 2018: 4825-4830.

[19] 朱自強. 超寬帶定位的關鍵技術研究[D].成都: 電子科技大學, 2019.

ZHU Z Q. Research on the key technology of ultra-wideband positioning[D]. Chengdu: University of Electronic Science and Technology of China, 2019.

[20] 范強, 張涵, 隋心. UWB TW-TOA測距誤差分析與削弱[J]. 測繪通報, 2017(9): 19-22, 50.

FAN Q, ZHANG H, SUI X. Error analysis and weakening of UWB TW-TOA ranging[J]. Bulletin of Surveying and Mapping, 2017(9): 19-22, 50.

[21] 楊慶生, 蔡文郁, 官靖凱, 等. 基于長距離UWB的無人水面艇定位技術研究[J]. 杭州電子科技大學學報(自然科學版), 2021, 41(3): 30-36.

YANG Q S, CAI W Y, GUAN J K, et al. Long-distance localization system applied to ocean unmanned surface vessel[J]. Journal of Hangzhou Dianzi University (Natural Sciences), 2021, 41(3): 30-36.

[22] ZHANG X J, LIU Y J, LI S D, et al. Simulation and analysis of influence of ranging error on location estimation accuracy[C]//Proceedings of 2017 Sixth Asia-Pacific Conference on Antennas and Propagation (APCAP). Piscataway: IEEE Press, 2017: 1-3.

Research on optimization of indoor positioning batch ranging system based on DS-TWR algorithm

SUN Hongwei, CAO Xuehong, JIAO Liangbao, MENG Lin, LIU Ziheng, YUAN Feng

Institute of Artificial Intelligence Industry Technology, Nanjing Institute of Technology, Nanjing 211167, China

Aiming at the current problems of the ultra wide band (UWB) indoor positioning system based on the double sided two-way ranging (DS-TWR) algorithm, there are more communication times and a higher conflict rate in a multi-tag environment, an improved algorithm was proposed. The Hash algorithm to hash and distribute the communication content between the tag and the anchor was used, so that the anchor could reply to multiple tags in a regular and unified manner during each ranging process, which greatly reduced the number of times the anchor sends RES (responds) data. Experimental results show that the improved algorithms’ communication times between a tag and the anchor were reduced by 15% compared with the traditional DS-TWR algorithm, which increases the time proportion of the anchor receiving state in ranging, thereby reducing the anchor receiving RNG (range) data. The collision rate of packets, the success rate of ranging has increased by 43.6%. Due to the reduction in the number of communications required in each positioning cycle and the reduction in the collision rate between data packets, a smaller channel capacity would be required, thereby increasing the label capacity of the positioning system, which has strong engineering significance.

UWB, indoor positioning, hash algorithm, DS-TWR

TN925

10.11959/j.issn.1000?0801.2022018

2021?09?17；

2022?01?10

孫宏偉，sun.h.w@foxmail.com

國家自然科學基金青年基金資助項目（No.61903183）

The National Nature Science Foundation Youth Fund of China (No.61903183)

孫宏偉（1997?），男，南京工程學院人工智能產業技術研究院碩士生，主要研究方向為室內定位。