基于洪泛机制准同步的UWB定位效率优化研究

刘子恒，焦良葆，孙宏伟，袁 枫，路绳方

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

0 引言

近年来，随着物联网技术的发展和自动化水平的不断提高，国家对高危工业环境的安全要求越来越高。在复杂的工业环境中对作业人员进行高精度的定位，可以满足各种作业场地的应用需求，有效保证作业人员的人身安全[1]。目前国内外常见的无线定位技术主要有：射频识别技术(RFID, radio frequency identification)、超宽带(UWB, ultra-wide band)、无线局域网(WLAN,wireless local area network)、激光雷达(LiDAR, light detection and ranging)、超声波、蓝牙、红外线、全球定位系统(GPS, global positioning system)等[2]。与其他定位技术相比，UWB定位技术具有传输速率高、穿透性强、定位精度高、抗多径干扰能力强、发射功率低、时间分辨率好的优点[3]，因此广泛应用在高精度室内定位中。

UWB室内定位技术中常用的测距方法有：接收信号强度[4](RSS, receive signal strength)、接收信号角度[5](AOA，angle of arrival)、接收信号时间差[6](TDOA，time difference of arrival)、接收信号时间[7](TOA, time of arrival)，其中TOA和TDOA测距算法是室内定位技术中应用最广泛的两种算法[8]，TDOA算法充分利用了UWB信号对时间的高精度分辨能力，通过检测信号到达两个基站的绝对时间差，而不是到达的飞行时间来确定目标的位置，整个过程只需与基站交互一次，具有测距通信量少、延迟率低、抗多径干扰能力强的优点。TDOA算法降低了标签与各基站之间的时间同步难度，但它提高了基站间的时间同步要求，基站间必须保证严格的时钟同步，这在一定程度上加大了技术方案的实施难度[9]。TOA测距算法主要通过基站标签间多次通信实现，具有实现难度低、硬件要求低的优点。与TDOA算法要求基站间严格时钟同步不同，TOA算法仅要求基站和标签之间时钟准同步[10]，并且增加标签与基站间的通信次数可以在一定程度上减少晶振偏移带来的计时误差[11],提高测距系统的精度，因其实现难度比TDOA低，故本文选用TOA算法为测距算法。

文献[12]设计的室内定位系统以UWB技术为基础，通过TOA算法来确定目标的位置。虽然该定位系统测距均值与真实值误差不超过15 cm，均值与真实值间误差不超过30 cm，实现了较高的测距精度和定位精度，但当系统接入标签量较多时存在严重的通信冲突，测距信息大量丢失，实际使用效果并不好[13]。本文针对TOA算法通信质量无法保证、多标签情况下通信冲突的问题，本文提出了一种基于洪泛机制准同步的高效UWB定位方法，先通过洪泛机制实现时钟准同步，再对每个设备序列号进行时隙分配，在保证精度的同时有效减少了标签之间的冲突，从而提高了系统标签容纳量，并通过减少标签与基站间的无效通信降低了系统功耗，能够满足较高的工业级要求。

1 原理及其误差分析

UWB定位系统一般可分为测距和定位两部分，接下来针对这两部分进行原理介绍及误差分析。

1.1 测距原理

TOA测距算法又称作TOF(timeofflight)算法，主要是根据测量接收信号在基站和标签之间的到达时间并将其转换为距离，从而进行定位。TOA测距方法的时间取决于时钟精度，为减少时钟偏移造成的测距误差，通常采用正反两个方向的测量方法[14]，通过测量飞行时间平均值来减少两者之间的时间偏移，从而提高测距精度。目前TOA定位方案有两种发展趋势：基于通信节点间严格时间同步的单向测距[15](OWR，one way ranging)方案和基于双向信号传输双向测距[16](TWR，two way ranging)方案。OWR算法原理简单，但需要严格同步系统中所有器件的时钟，考虑到UWB对定位精度的要求非常高，对处于移动中的标签实现同步难度大。TWR方案通过标签和基站间交换时间戳信息来降低设备间时钟同步的难度[17]，实现了系统复杂度和成本的降低，但其定位精度受设备自身晶振偏移影响[18]。本文采用的是双边双向测距(DS-TWR, double sided -two way ranging)算法，该方法有效降低了晶振偏移带来的测距误差[19]。

在测距阶段，标签与基站会进行三次信息交互并记录相应时间节点的时间戳，进而计算出飞行距离[20]，其测距原理如图1所示。

第一步：任意时间点节点A接收到测距请求后，发送rng消息并记录发送时间戳TSP，等待节点B回复。

第二步：节点B接收到消息后立即记录当前时间戳TRP，在短暂时延后回复节点A一个res消息，记录下发送回复消息的时间戳TSR。

第三步：节点A一旦收到res消息，则立刻记录接收时间戳TRR，一定时延后回复节点A一个fin消息，并记录回复时间戳TSF。

第四步：节点B收到A回复的fin信息后，记录该时刻时间戳TRF，根据整个测距过程中产生的6个时间戳求解出消息在空气中的飞行时间T，飞行时间T乘以电磁波传输速率即可得到基站与标签间的距离。

图1 DS-TWR测距原理

由图1可得式(1)：

(1)

计算整个过程中无线信号的飞行时间：

(2)

由于式(2)是无线信号在两节点之间传播四次的结果，联立式(1)和式(2)可得理想信号飞行时间T：

(3)

1.2 定位原理

以基站作为参考节点，标签为非参考节点，非参考节点所在范围内参考节点坐标已知，根据立体几何原理，以各参考点为球心，非参考点与各参考点间距离为半径画球，标签所在位置即为各球的交点。在定位空间内建立坐标系，则基站坐标(xi，yi，zi)与标签坐标(x，y，z)应满足以下关系：

(4)

如图2所示，空间内存在4个基站时，利用融合Taylor级数和无迹卡尔曼滤波的定位算法对标签位置的求解超限定方程组式(6)[20]，求解出的x、y、z即为标签在定位空间内的三维坐标。

图2 TOA定位过程

1.3 误差分析

UWB定位系统中最常见的两类误差为多址干扰造成的误差和时钟精度带来的误差[21]。

多址干扰是指在多标签环境下，其他标签的信号对目标信号造成干扰从而降低了估计的准确性。针对该问题本文通过把来自不同标签的信号从时间上分开，降低了多址干扰情况的发生。

由于TOA定位算法需要目标节点与参考节点之间的精确的时间同步，非精确的时间同步将导致UWB系统的定位误差。假设ka和kb为两节点实际时钟频率和期望时钟频率之比，则真实信号飞行时间为：

(5)

假设无线信号的飞行速度为c，则测距误差可写为：

(6)

响应时间分别为50 μs、100 μs、200 μs时不同时钟差与测距误差之间的关系如图3所示。从图中可以看出，响应时间及时钟差均与测距误差成正比[22]，响应时间越短，时钟差越小，则测距误差越小。由于响应时间的大小无法人为控制，本文选择通过降低时钟差来提高精度。

图3 不同ka-kb下的测距误差

2 改进方案

改进方案分为两部分，先通过洪泛机制实现时钟准同步，在此基础上再进行时隙分配。接下来对这两部分进行详细介绍。

2.1 时钟准同步

洪泛算法是一种无线传感器网络领域常用的算法，它可以通过单个同步分组实现节点对之间的同步，具有鲁棒性好、适应性强的优点。本文采用了洪泛算法，需要设定一个主基站，其余基站均为被分配适应级别的从基站。基于洪泛机制准同步的UWB定位整体流程如下：

Step1：主机站作为时间基准点向空间内广播发送包含当前时钟读数的SYN消息；

Step2：从基站和标签接收到SYN消息后估算时延等参数并调整自身逻辑时钟值以和基准点达成同步；

Step3：达成同步后的从基站或标签以自身为新的基准点一环一环向外同步，实现所有从基站、标签与主基站时钟准同步；

Step4：标签与距离最近的基站通信，在接收到基站发出的注册表后，记录发送时间戳Trng_tx，给基站回复RNG消息；

Step5：基站接收到RNG消息后记录接收时间戳Trng_rx，记录发送时间戳Tres_tx并给标签回复RES消息；

Step6：标签接收到RES消息后记录接收时间戳Tres_rx，记录发送时间戳Tfin_tx后将消息装填入FIN消息中并发送；

Step7：基站接收到FIN消息后记录Tfin_rx，根据解析FIN消息获得的6个时间戳运用DS-TWR算法求解测距距离；

Step8：由于标签所在范围内基站坐标已知，根据测得的标签到各基站的距离可求解定位空间内各标签的位置；

假设经过3次洪泛传播后标签与基站开始测距，主基站为0级，从基站可分为1级和2级，改进后的DS-TWR算法测距流程如图4所示。

图4 改进DS-TWR算法示意图

洪泛机制中存在的最大问题是基站一级一级向下传递会产生误差的积累，而累计误差会影响系统的测距效果。若此处标签是与主基站通信，则时延和硬件带来的误差会累计3次，这将极大影响测距效果。但是在本方案中，标签只需要与相邻的基站进行测距交互，不受累计误差的影响。

改进后的DS-TWR算法利用洪泛机制实现了标签和基站之间的时钟准同步，在一定程度上提高了TOA算法的测距精度，同时为接下来的时隙分配法奠定了基础。

2.2 时隙分配法

散列算法又称哈希算法或杂凑算法，是一种从任意文件中创造小的数字的方法。本文采用散列算法实现了科学的时隙分配，解决UWB通信中多标签情况下的通信冲突问题。

由于通信分配没有协调好，会经常出现通信冲突：多个标签同时向一个基站通信，先与基站交互的标签先通信，后到的标签必须要等一定的响应时间后才能与其他基站通信，这样导致基站与标签之间通信速度慢，系统反应慢。假设在有定位需求的场所中有基站m个(m>3)，标签n个。在主基站发送SYN报文通过洪泛机制实现标签和基站、基站和基站之间的时钟准同步后，基站侧以发送SYN报文的时刻作为循环周期起始时刻，标签侧以收到SYN报文的时刻作为的循环周期起始时刻，忽略掉信号在空中的传播时间；从起始时刻开始，设置一个时隙段，通过Hash运算后得到的散列序号给每个标签和基站分配不同的时隙，图5为时隙分配流程图。

图5 时隙分配流程图

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

I[i]=((TID+7)*i)%5,i=1，...，5

(7)

THash1(TID)={(TID+Q)*A[I[i]]}%P，

i=1，...，5

(8)

式(15)中，TID为标签的序列号，P表示帧的长度，此处P取大小接近帧长度的质数目的是为了均匀分配时隙，保证运算效果。A[I[i]]为散列后的基站序列号；Q为任意取值的质数，目的是为了让得到的时隙号能够散列开。

在经过一次hash计算后，标签之间依旧可能存在冲突。当再次遇到冲突时引入上次散列后的结果再次进行散列，直至冲突消失，计算公式如下：

THashj(TID)={(TID+Q+THashj-1)*A[I[i]]}%

[P+THashj-1]

i=1，...，5,j为大于1的正整数

(9)

在实际工程领域中具体时隙段格式如下：

R0|T0[1] |T0[2] |...|T0[31] |R2|T1[1] |T1[2] |...|T1[31] | 。

其中:N为洪泛次数，R0和R1为冗余时隙，基站和标签在冗余时隙中进行时钟准同步；测距时隙为T0和T1，在测距时隙中标签和基站通信记录收发时间戳。

时隙分配如图6所示，通过多次Hash运算分配时隙能够显著降低标签之间以及标签和基站之间的通信冲突，有效增加系统中标签的容量。

图6 时隙分配示意图

3 软件设计

定位系统由上位机和下位机两部分组成，上位机采用Ubuntu系统编写，在将上报的测距信息记录进数据库后，根据库中数据解析出目标位置；下位机采用Keil uVision5软件编写，负责点对点之间的测距。下位机主要通过3个定时器控制测距流程：定时器1控制整个测距周期，定时向上位机发送测距结果；定时器2控制基站定时广播blk消息发起测距，由标签先发出测距信息，通过装填测距信息中的注册表记录每次收发的时间戳，完成测距信息交互后基站根据注册表中信息可计算出点对点间的距离；为防止出现标签老化，设定定时器3定时等待应答，若无应答则重新发起测距。下位机基站和标签测距流程如图7、图8所示。

图7 标签测距流程

图8 基站测距流程

为了方便在上位机实时定位目标的位置，通过QT软件设计室内定位人员轨迹展示界面。一只手举着标签在定位区域内以约1.5 m/s的速度快速移动获得的定位轨迹如图9所示，标签轨迹基本符合人员实际活动轨迹。

图9 室内定位人员轨迹展示图

4 实验结果与分析

为了验证优化效果，搭建了相应的实验环境并对改进后的系统进行了测试。

4.1 实验环境的搭建

以STM32高性能微处理器和DWM1000射频收发芯片为基础，结合各种外围电路设计了室内定位系统硬件平台，主要包括测距模块、stm32主控制模块、数据传输模块和指示模块。相对于标签而言，基站处理的任务更多，因此基站采用性能较高的STM32F407ZET6处理器，标签采用性能较低的STM32F105RCT6处理器。

4.2 功耗实验

在多标签与单基站通信的情况下，某一时刻多个标签同时向基站发出通信请求，此时只有第一个与基站通信的标签发出的请求有效，其余标签发出的请求均为无效。假设1个基站与50个标签通信，若要所有标签都与基站完成通信则共计需发出1 275次通信请求，这就大大提高了系统的功耗。而本文提出的时隙分配法可以使标签按顺序与基站通信，大量减少了无效通信的次数。在1个基站与50个标签通信的情况下标签仅需发出50次通信请求，这就极大地降低了功耗。

功耗实验测试改进前后多标签情况下系统中某一标签从满电到电量耗尽过程中的样本数量和通信时长。实验采用1 700毫安的锂电池给标签供电，在给所有电池充满电后，测试改进前后4个基站与20个标签在通信距离相同的情况下系统中某一标签的功耗情况。图10和11为改进前后系统在单基站多标签情况下通信获得的测距数据分析图，其中横坐标为样本数量，纵坐标为标签与基站间距离。

图10 改进前的测距信息

图11 改进后的测距信息

改进前后方案对比数据如表1所示，改进后系统中标签能耗相对改进前降低了30%，单位时间内获取数据量提高了27.8%。实验结果证明，改进后的方案功耗更低，获得数据更多，且测距效果不会受标签剩余电量影响产生大幅波动，系统鲁棒性得到了提升。

改进前后通信时长和单位时间内通信次数提升效率表达式如下所示：

Ph=(h2-h1)/h2*100%

(10)

PN=(N2-N1)/N2*100%

(11)

式中,h1和h2分别为改进前后的通信时长；N1和N2分别为改进前后的单位时间内的通信次数。

表1 方案对比数据表

4.3 通信成功率实验

标签通信流程如下：在时钟准同步后，各标签与4个末级基站依次通信，若基站a与标签a处于通信状态时，标签b向基站a发出通信请求，则记为一次冲突；标签b在等待1秒后向基站b发出通信请求，若基站b也处于通信状态，则记为二次冲突；继续等待1秒后再与下一个基站通信……依此类推，直至成功与某一基站进入通信状态。

针对通信成功率进行仿真实验，设定从200个标签和50个基站中随机选择5个基站，20个标签进行十万次通信。如图12所示为对改进前数据做的直方概率图，图中横坐标为对应每一次通信的通信成功率，左侧坐标为通信次数，右侧纵坐标为累计百分比。改进前在发生冲突情况下通信成功率最高80%，最低40%，平均通信成功率仅有62%，通信成功率较低，数据丢包严重。

图12 改进前

保持条件不变，对改进后的代码进行仿真，对仿真后得到的数据集作直方概率图如图13所示。改进后通信成功率最高为100%，最低为60%，平均通信成功率达到了78%，相较于改进前提高了16%，系统在多标签情况下的通信成功率得到了显著提高。

图13 改进后

5 结束语

针对UWB定位中的标签容量限制和通信冲突的问题，提出了一种基于洪泛机制准同步的改进定位方法。利用洪泛机制实现了系统内所有设备间的时钟准同步，一方面满足了TOA算法对基站和标签时钟准同步的需求，在一定程度上提高了测距精度；另一方面为时隙分配法奠定了基础。针对多标签情况下易产生冲突的问题，提出一种基于Hash运算的时隙分配法，在时钟准同步后通过Hash运算给每个标签分配唯一的时隙编号，有效降低了多标签下的冲突率，使得通信成功率大大提高。