DS-TWR算法室内定位批量测距系统的优化研究

孙宏伟，曹雪虹，焦良葆，孟琳，刘子恒，袁枫

研究与开发

DS-TWR算法室内定位批量测距系统的优化研究

孙宏伟，曹雪虹，焦良葆，孟琳，刘子恒，袁枫

（南京工程学院人工智能产业技术研究院，江苏 南京 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

A

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−），男，南京工程学院人工智能产业技术研究院硕士生，主要研究方向为室内定位。

曹雪虹（1964−），女，博士，南京工程学院人工智能产业技术研究院教授，主要研究方向为无线通信系统、信息理论。

焦良葆（1972−），男，博士，南京工程学院人工智能产业技术研究院教授，主要研究方向为图像信号处理、视觉信息理解。

孟琳（1989−），女，博士，南京工程学院人工智能产业技术研究院讲师，主要研究方向为控制科学与技术。

刘子恒（1997−），男，南京工程学院人工智能产业技术研究院硕士生，主要研究方向为室内定位。

袁枫（1997−），男，南京工程学院人工智能产业技术研究院硕士生，主要研究方向为室内定位。