室内定位中DS-TWR测距算法的优化

袁 枫，焦良葆，陈 楠，顾慧东

(南京工程学院人工智能产业技术研究院，江苏 南京 211167)

0 引 言

在严格的工业环境中需要高精度的定位信息，以满足各种作业场地的应用需求，例如监管变电站工作人员、保证作业人员安全等[1]。目前国内外常见的无线定位技术主要有：射频信号、超宽带(Ultra-wide Band, UWB)、无线局域网(WLAN)、超声波、蓝牙、红外线、GPS定位等[2]。其中GPS能较好地满足室外位置服务的需求，但是难以满足室内定位的精度要求[3]。相较于其余的定位技术，UWB定位技术有着显著的优点：穿透性强、定位精度高、抗干扰能力强、功耗低、时间分辨率好[4]。故本文选择用UWB来进行室内定位研究。

在室内定位技术中，常用的几种测距方法有：接收信号强度[5](Receive Signal Strength, RSS)、接收信号角度[6](Angle of Arrival, AOA)、接收信号时间差[7](Time Difference of Arrival, TDOA)、接收信号时间[8](Time of Arrival, TOA)。其中TOA和TDOA测距算法是室内定位技术中应用最广泛的2种算法[9]。TDOA算法充分利用了UWB信号的时间分辨能力强的特点，此外该算法标签只需要与基站交互一次即可完成测距，且在标签较多的环境内也可保持较低的延迟率[10]。但TDOA算法必须保证基站之间严格的时钟同步，一定程度上加大了技术方案的实施难度[11]。TOA测距算法在接入大量标签时容易因为标签发生通信冲突而产生测距信息丢失的情况，但其完全规避了时钟同步所带来的技术难度和测距误差[12]，并且通过增加标签基站之间的信息交互次数在一定程度上可以减少晶振偏移带来的计时误差，对硬件要求不高。故本文选取TOA算法作为测距算法。

文献[11]中提出一种基于UWB的室内定位系统，使用的是TOA测距算法[13]。TOA算法中存在如果接入大量的标签时，通信冲突严重，使整个系统的定位性能下降的问题。本文对基本的通信流程做出改进，具体如下：先设置一个主基站，标签只需与主基站进行通信，而从基站只需要进行监听，然后通过DS-TWR(Double Sided -Two Way Ranging)算法来解析收到的时戳，实现标签与主从基站之间的测距过程，最终完成室内定位。改进后的流程让通信方案变得简单，使得整个系统的鲁棒性更好。其次，针对TOA算法中多标签冲突的问题，本文提出使用基于Hash算法的时隙分配法，能够通过散列让标签在自己的唯一时隙上，从而使冲突次数降低，使整个系统中可以容纳更多的标签。

1 DS-TWR测距原理及其误差分析

TOA测距算法称作TOF(Time of Fight)算法，一般分为单向测距[14](One Way Ranging, OWR)和双向测距[15](Two Way Ranging, TWR)。OWR算法虽然方法原理简单，但是需要严格的时间同步，实现难度大。而TWR算法虽然不基于时钟同步，通过标签基站之间的多次交互来屏蔽时钟同步带来的误差[16]，实现简单，但是若直接使用TWR算法会因为基站标签之间晶振偏移的影响造成很大的测距误差[17]。故本文使用的是双边双向测距DS-TWR算法。DS-TWR算法与TWR相比有效地减少了晶振偏移带来的测距误差[18]。

DS-TWR测距阶段是通过标签基站之间3次信息交互来计算信号在两者之间的飞行时间，从而实现测距信息获取[19]。其测距原理如图1所示。某时刻节点A向节点B发送一条测距请求并记录下此时的发送时间戳Tsp，节点B记录收到来自节点A信息的接收时间戳Trp，并在一定延时后发送回复信息给节点A，节点A收到来自节点B的回复信息后记录下当前时间戳，并在一定延时后继续回复一条测距信息给节点B，节点B收到测距信息后记录下当时时间戳。上述测距过程共产生6个时间戳，根据式(1)即可求出信号在2个节点间的飞行时间T。

图1 DS-TWR测距原理图

(1)

DS-TWR测距算法中，节点都是以自身的时间戳进行计算，所以能够有效消除时钟同步带来的测距误差，但是晶振偏移依然会影响到测距精度[20]。晶振偏移是以ppm(part per million)为单位，表示百万分之一，例如10 ppm的晶振在1 s内会出现10-5s的误差[21]。若采用高质量晶振，会造成硬件成本和功耗的大幅增加[22]，不符合IEEE802.15.4a中的低功耗要求。所以下面具体分析晶振偏移给测距算法带来的距离误差的原因。

如图1所示，DS-TWR测距算法共产生6个时间戳，令：

(2)

根据式(1)，信号飞行时间的真实值Tprop可表示为：

(3)

考虑到标签基站晶振偏移的影响(λ1和λ2分别为2个节点的晶振偏移，单位为ppm)，信号飞行时间的测量值可表示为：

(4)

令k=Treply1-Treply2，由于工业环境为短距离测量，T远远小于k，所以测距误差可简化为：

(5)

其中，c为光速。从上式可以看出，算法测距误差与晶振偏移和标签基站的信息回复时延之间的差值k有关[23]。仿真实验中，k的值无限趋近于0(设置其为μs级)。图2为DS-TWR在不同的k和λ1-λ2下的测距误差。

图2 不同λ1-λ2和k下的测距误差

从图2可以看出，在极端环境下(时延差值0.1 ms、晶振误差20 ppm)，测距误差接近0.16 m，而在正常时延差值条件下测距误差基本控制在0.02 m以内，该误差可以忽略不计[19]。

2 改进方案的实现

2.1 通信方法的改进

改进DS-TWR算法，需要设定一个主基站，一般主基站为基站注册表中的第一个基站。标签只需要与主基站进行通信，而从基站只需要进行接收监听。图3为改进DS-TWR算法的实现过程。假设主基站为A、从基站为B，位置固定，则基站A与基站B间的距离dAB为定值。

图3 改进DS-TWR算法主基站距标签更近示意图

完成一次改进DS-TWR测距的步骤如下：

Step1标签向空间内广播发送RNG1消息，并记录此时间戳Trng1_tx。

Step2延迟一定时间后标签向空间广播发送RNG2消息，并记录此时间戳Trng2_tx。

Step3主基站接收到标签发送的RNG1和RNG2消息，分别记录收到的时间戳Trng1_rx1和Trng2_rx1。

Step4从基站接收到标签发送的RNG1和RNG2消息，分别记录收到的时间戳Trng1_rx2和Trng2_rx2。

Step5主基站将Trng1_rx1和Trng2_rx2装填进RES帧，将此消息发送出去，记录发送时间戳Tres_tx。

Step6从基站接收到主基站发送的RES消息，记录接收时间戳Tres_rx2，并解析该数据帧。

Step7标签接收到主基站发送的RES消息，记录接收时间戳Tres_rx1。

Step8标签将Trng2_tx、Tres_rx1和Tfin_tx时间戳装填进FIN帧，将此帧发往主基站。

Step9主基站收到FIN消息记录接收时间戳Tfin_rx，并解析FIN帧获得各个时间戳，运用DS-TWR算法求解点对点距离。

从图3的流程图中可得以下的公式：

tA=Trng2_rx1-Trng1_rx1

(6)

tB=Trng2_rx2-Trng1_rx2

(7)

t1=Tres_tx-Trng2_rx1

(8)

t2=Tres_rx2-Trng2_rx2

(9)

根据式(8)和式(9)可得主基站与从基站之间的时钟频偏差比：

(10)

由于主基站在RES数据帧中携带了tA的相关时间戳，所以从基站在本地即可获得时钟频偏差比k。

1)当从基站比主基站离标签远时，由图3从物理角度出发可得关系式：

t2+ΔtAB=t1·k+tAB

(11)

2)当从基站比主基站离标签近时，由图4所示可得关系式：

图4 改进DS-TWR算法主基站距标签更远示意图

t2-ΔtAB=t1·k+tAB

(12)

式(12)相较于式(11)对ΔtAB处理进行了相反的处理，即t2-ΔtAB，而当始终固定ΔtAB为UWB信号从标签到从基站的飞行时间减去UWB信号从标签到主基站的飞行时间时，则图4中ΔtAB应为负值，所以式(12)可以改为式(11)，从而统一关系式的形式。

3)当从基站与主基站离标签一样近时，如图5所示，同样可由式(11)表示，此时的ΔtAB为0，所以可以统一3种情况的表达式为式(11)。

图5 改进DS-TWR算法主从基站距标签同样近示意图

标签在收到RES消息后发送FINAL消息，如图5所示采用标准DS-TWR算法完成标签到主基站的测距，所得距离为dA。此时根据ΔdAB和dA可得标签到从基站的距离dB：

dB=dA+ΔdAB

(13)

在标签与从基站的测距过程中，从基站只进行接收信号的操作，所以可以在空间范围内随意增加基站，都可同理完成测距。改进后的方案只是改进了通信流程及计算距离的方法，并没有改变内部的晶振偏移和标签基站的信息回复时延，故测距误差并没有得到优化。

2.2 时隙分配法

Hash算法又称散列算法，是一种常用于降低冲突率的算法。在UWB通信中，如何防止多个标签发生通信冲突的关键在于：通过一种科学的时隙分配算法将基站和标签分配在唯一的时隙上。

在一个能够通信的区域中，有M个基站(M>3)与N个标签；基站和标签开启后都立刻进行准同步，即主基站周期发送SYN报文，其余的标签接收到SYN报文并进行准同步；发送SYN报文的基站以发送SYN报文的时刻作为基站循环周期起始时刻，标签收到SYN报文的时刻作为该设备的循环周期起始时刻，忽略掉信号在空中的传播时间；从起始时刻开始，设置一个时隙段，然后通过Hash算法将每个标签和基站安排在不同的时隙中。图6为具体通信流程示意图。

图6 通信流程示意图

本文采用的Hash算法为素数求余法，序号为T的标签测距的时隙号TS0[1…5]计算方法如下：该标签所得基站列表即为M个基站的列表A[1…M]，该列表为基站的序号列表，且所有标签列表一致；若M>5，首先对列表A[1…M]进行散列，得到5个下标I[1…5]，第1次定位需要至少4个基站，并设置一个冗余基站：

I[i]=((T+Z)i)%5,i=1,…,5

(14)

TS0[i]=((T+Q)(A[I[i]]+P))%Q,i=1,…,5

(15)

TS1[i]=((T+P)(A[I[i]]+Q))%P,i=1,…,5

(16)

式(14)中T为标签序号，Z为任意一个比5大的质数。

式(15)和式(16)中TS0[i]、TS1[i]为序号为T的标签通过散列获得的时隙号；A[I[i]]为散列后的基站序列号；%是取余符号；Q和P是素数1和素数2，是任意取的质数，目的是为了让得到的时隙号能够散列开。

具体的应用于工程领域的时隙段格式如下所示：

R0|R1|S0[1]|S0[2]|…|S0[29]|R3|S1[1]|S1[2]|…|S1[31]|R4|

其中R0～R3为冗余时隙，由各基站发送准同步信号；S0和S1为定位时隙，一共64个可用时隙，通过质数求余的方法将基站和标签合理地安排在各个时隙中进行通信。

整体的时隙分配图如图7所示。

图7 时隙分配图

时隙分配法可以有效地降低标签与标签之间、标签与基站的通信冲突，让系统中标签的容纳量增加。

3 实验结果

3.1 实验环境的搭建

3.1.1 硬件平台

室内定位系统硬件平台是基于STM32高性能微处理器和DWM1000射频收发芯片并结合各类外围电路设计而成的，具体是由电源管理模块、STM32主控模块、UWB测距模块、指示模块和网络传输模块构成。其中，网络传输模块是基站特有，指示模块是标签特有。由于基站在测距过程中需承载较多功能，如与标签的实时通信、距离解算和数据上传等功能，故选择性能较高的STM32F407ZET6处理器。标签选择的是性能稍弱的STM32F105RCT6。此外基站和标签的主控芯片都是通过SPI总线与DWM1000相连，且通过USART接口调试测距程序。图8为标签实物图，图9为基站实物图。

图8 标签实物图

图9 基站实物图

3.1.2 软件实验平台

本定位系统分为上位机和下位机，上位机是在Linux系统中编写，主要负责将基站上报来的测距信息进行解析最终完成室内定位。下位机软件通信方案的开发平台为Keil uVision5。图10为测距的程序流程图。

图10 测距流程图

标签侧的定时器1和基站侧的定时器1是作为程序的一个大周期，BLK包是为了进行准同步，即前文中的SYN报文，标签侧的设定的定时器2时间是通过散列算法获得的特定时间，设定时器3是为了让标签隔一段时间再发送RNG2包，标签发完所有的包后就进入休眠，等待下一个周期。而从基站全程处于监听状态。

将改进前的代码用Keil先烧录至一个标签中和4个基站中，然后放在视距良好的空旷的房间里，随机选点进行测距，待标签的电量耗尽，记录数据，将标签基站取下，再将改进版的代码烧录至取下的标签和基站中进行测距，从而保证实验环境的统一性，分析实验数据对2套系统的稳定性和功耗进行对比。实验环境如图11所示。

图11 实验环境

3.2 功耗对比

将充满电的标签放入定位系统进行定位实验，直至标签电量耗尽不足以进行定位。在服务器上取其中一个基站与标签的测距数据进行分析，如图12与图13所示，其中改进前通信方案在定点测距中的实际距离为2.664 m，改进后通信方案在定点测距中的实际距离为1.846 m。图中的横坐标为测距获得的样本数量，纵坐标为距离。

图12 改进前的测距信息

图13 改进后的测距信息

表1 方案对比数据表

由图12、图13和表1可知，在标签从满电到电量耗尽，改进后的方案测得的样本数据更多，而且改进后的系统也没有因为标签电量即将耗尽而产生测距大幅度波动，这表明改进后的系统鲁棒性更好，改进后比改进前的标签能耗节省了33.3%，获取的样本数量也增加了26.5%。

3.3 冲突率对比

由于测试冲突率，现实中需要大量的基站和标签，故本文用MATLAB仿真。规定标签的通信顺序是：每个标签与5个基站依次通信，如果第1个基站与1号标签正在通信，2号标签也要与1号基站通信，则算一次冲突，而2号标签在等待1 s后，再与2号基站通信，若2号基站也被占用则再等待1 s后与下一个基站通信，并且冲突次数加1，以此类推。

为了达到与现有通信方式相同，选择从500个标签和200个基站中随机产生5个基站、20个标签进行通信，标签序号定义为1…500，基站序号定义为1…200。基站和标签的周期定为512 ms，测距一次的时间为8 ms。仿真结果如图14所示。图中纵坐标为同一时间内标签与同一基站的通信次数，如果通信次数大于1，则判为冲突；横坐标为总体的测距次数。

图14 改进前通信成功次数

采用时隙分配法时，为了达到条件相同，在200个基站中随机抽取5个基站，在500个标签中抽取20个标签，标签序号定义为1…500，基站序号定义为1…200。一个时隙段取64个时隙，一个时隙取8 ms，基站和标签的周期就是64×8 ms，即512 ms，与现有通信方式条件完全相同。仿真结果如图15所示。求得改进前通信方式冲突率达到39%。用改进后的时隙法进行通信，通信冲突率只有26%，冲突率降低了13个百分点。故时隙分配法能够有效地降低冲突率。

图15 改进后通信成功次数

4 结束语

本文提出了一种基于DS-TWR算法的改进方案。该方案能够有效地减少标签与基站之间的通信次数，使标签处于聆听的状态时长减少，降低标签的功耗，从而延长了标签的待机时间。使用Hash算法使得定位系统中一个定位区域内同时容纳30个标签，冲突率有效降低。但是还有许多问题需要完善：现在的定位系统只能进行时钟准同步，不能达到精准的时钟同步，在进一步的研究中，将会设计通信更加简单的TDOA测距算法，实现更加稳定的定位系统。