基于改进双向测距-到达时间差定位算法的超宽带定位系统

卞佳兴，朱 荣，陈 玄

(武汉大学 计算机学院，武汉 430072)(*通信作者电子邮箱zhurong@whu.edu.cn)

基于改进双向测距-到达时间差定位算法的超宽带定位系统

卞佳兴，朱 荣*，陈 玄

(武汉大学 计算机学院，武汉 430072)(*通信作者电子邮箱zhurong@whu.edu.cn)

针对传统无线定位技术在室内定位精度不高的问题，设计实现了一种基于超宽带(UWB)技术的室内定位系统。首先，提出了定位服务器与移动端APP实时交互的系统结构，解决室内移动人员自主定位与导航的问题。其次，在双向测距(TWR)算法中增加一条无线电信息以减小时钟偏移引起的测距误差，从而提高算法性能。最后，将通过到达时间差(TDOA)定位算法得到的双曲面方程组进行线性化处理后结合Jacobi迭代法完成求解，避免了使用标准TDOA定位算法难以直接解算的情况。经测试，该系统在楼道房间等场景中能稳定工作且定位误差控制在30 cm以内，相比基于WiFi、蓝牙等技术的定位系统在定位精度上提高了10倍左右，能够满足在复杂室内环境中的精确移动定位需求。

室内定位；超宽带；双向测距；到达时间差

0 引言

随着智能设备的普及和移动互联网的发展，人们对室内定位的需求也日益增加。基于室内的位置服务可以支持许多应用场景，比如公共安全及应急响应、定位导览和交友互动等。基于全球定位系统(Global Positioning System, GPS)和地图的位置服务已被广泛应用，但由于GPS定位信号无法穿透建筑物，其在室内已无法正常工作。为了克服GPS的定位缺陷并实现在复杂室内环境中的精确定位，国内外研究人员在室内定位中引入了红外线、WiFi、蓝牙、ZigBee、超声波、射频识别(Radio Frequency Identification, RFID)等多种技术。红外线[1]由于本身的特性覆盖范围较窄，而且易受外界环境的影响，定位精度只能达5 m。WiFi[2]、蓝牙[3]、ZigBee[4]只能定位约几十米的区域，其定位精度也只能达3 m，无法满足精确室内移动定位需求。超声波[5]室内定位受多径和非视距的影响，室内定位效果较差。而RFID[6]技术只能进行存在识别，无法实时定位，定位精度也在5 m左右。

超宽带(Ultra WideBand, UWB)[7]技术是一种无载波的通信技术，它利用纳秒级或纳秒以下的极窄脉冲信号来传输数据，这使得超宽带信号有着很高的时间分辨率，进而能够实现很高的定位精度，而且其功耗低、抗多径效果好、安全性高、系统复杂度低，能够基本弥补上述技术的缺点，将会成为未来室内定位的优先选择之一。因此，本文基于超宽带技术设计了一套无线室内定位系统，采用改进的双向测距(Two-Way Ranging, TWR)算法提高测距精度，针对到达时间差(Time Difference Of Arrival, TDOA )算法在误差存在的情况下难以求解的问题，提出了改进的TDOA定位算法，最后基于Android平台实现。将该系统应用到电厂巡检人员定位的场景，实验证明了整个系统的可行性，定位算法的精度达到30 cm。系统可以对电厂中需要追踪的巡检人员位置进行实时精确定位，同时也可以帮助巡检人员导航。

1 系统结构设计

本文提出的室内定位系统结构如图1所示。系统由标签、基站、路由器、定位服务器以及移动端APP组成。标签由巡检人员随身携带，基站安装在工厂四周，当巡检人员在该局域网内通过手机登录移动端APP后，就可以在工厂内实现实时精确定位与导航。以4个定位基站组成的系统为例，理论上可以覆盖上万平米左右的范围，增加基站数可以进一步扩大定位场景。

图1 系统结构图

标签在固定的时隙内发送超宽带信号，各定位基站截获此信号后调用测距算法获得与标签之间的距离，然后将距离信息通过路由器以无线方式传送至定位服务器，最后由定位服务器调用定位算法对标签进行定位并将定位结果实时推送至移动端APP显示。因此，整套系统的工作流程主要由测距和定位两个部分组成，精确的测距算法是实现精确定位的前提和基础。

2 测距算法设计

距离测量是超宽带定位的第一步。双向测距(TWR)[8]是通过确定两个物体之间信号的飞行时间来计算距离，物体之间的距离可以用无线电波的速度与飞行时间相乘计算得到。本文采用改进的TWR算法，提高了测距阶段的测距精度。

2.1 TWR算法

系统的超宽带无线收发模块选用半导体公司DecaWave推出的DWM1000模块[9]。如果使用一对DWM1000，分别设计为设备A和设备B。设备A作为距离测量的发起者可以发起测距请求，而设备B作为响应者可以侦听和响应设备A发来的无线电信息，那么对于基本的双向测距可以作如下描述：A给B发送一个无线电信息并记录它的发送时间戳t1，B接收到了信息并在一个特定的时延treplyB后发送一个回复给A，最后A接收到回复并记录一个接收时间戳t2。其测距过程如图2所示。

利用各自的本地时钟，设备A可以知道自己的发送时间戳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后，再经过一个特定的时延treplyA发送一个无线电信息给B并记录自己的发送时间戳t3，最后B接收到了信息并记录一个接收时间戳t4。图3展示了这种改进的双向测距过程。

利用t0和t4，设备B可以计算出往返时间troundB；利用t1和t2，设备A可以计算出往返时间troundA；treplyA和treplyB均已知，则可以得到：

TroundA=TreplyB+2TOF=t2-t1

图书馆以积分的形式实时累计、查询、显示某段时间(年度、季度或月)读者的阅读量，再利用最新的网络科技手段创新阅读文化活动，使阅读的专栏集趣味性、导读性和参与性一体，激发读者阅读的主观能动性，更进一步强化阅读兴趣。如武汉大学图书馆开展的“拯救小布之消失”的经典活动，以动漫游戏的方式，让读者通过娱乐回答与名家经典相关的问题，完成闯关。基于阅读积分制的阅读推广平台可以参考此方式，使读者获得阅读积分，赢得礼品，晋升等级，满足自己的成就感和自豪感。通过阅读积分制，在读者和读者之间形成一种阅读竞争的场面[4]。

(8)

TroundB=TreplyA+2TOF=t4-t0

(9)

那么，信号的飞行时间可以表示为：

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

(10)

对改进的双向测距算法也进行误差分析。考虑到时钟偏移，设备B实际得到的飞行时间估计为：

(11)

则飞行时间估计与真实的飞行时间之间的差值为：

(12)

令treplyA=treply，treplyB=treply+Δreply，那么差值变为：

(13)

比较两种测距方式的误差可知，Δ2<Δ1，即采用改进的双向测距算法在时钟偏移的情况下比基本的双向测距算法具有更高的测距精度。

图3 改进的双向测距过程

3 定位算法设计

3.1 TDOA定位算法

目前，超宽带定位技术通常运用到达时间差(TDOA)[12-13]方法来实现定位。假设三维空间中分布着N个定位基站，定位标签的位置为(x,y,z)，第i个基站的位置为(xi,yi,zi)，其与定位标签之间的距离为Ri(i=1,2,…,N)，则基于TDOA的三维定位分布示意图如图4所示。

图4 基于TDOA的三维定位分布示意图

定位标签作为被定位的目标，其位置需要调用定位算法被实时解算出来；而定位基站作为定位的参考节点，其位置在调用定位算法之前已知。TDOA定位算法的具体计算过程是：在前面测距的过程中可以获得标签与每个基站之间的到达时间(即信号的飞行时间)，每两个到达时间之间的差值就是TDOA测量值，利用TDOA测量值可以计算出定位目标与两个基站之间的距离差，多个TDOA测量值计算距离差的方程便构成了一个关于目标位置的双曲面方程组，求解该方程组就可以得到目标的估计位置。

由此可以得到TDOA方程组：

(14)

其中τi就是各自对应的飞行时间估计TOF，各基站与定位标签之间的距离为：

(15)

3.2 改进的TDOA定位算法

标准TDOA定位算法中的双曲面非线性方程组难以求解，本文利用数学方法对非线性方程组进行了线性化处理。考虑到测距误差和非视距(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看成未知数，式(20)就变成了线性方程组。

AX=b

(21)

其中，系数矩阵A和矩阵b均为常数矩阵，式(21)表示的是一个线性方程组，求解出线性方程组中x、y、z的值便可以得到标签的位置坐标。

由于测距过程中会有误差，而且当其中某个或某些基站与标签之间存在NLOS通信时，还会带来NLOS误差，TDOA的3个双曲面就无法交于一点，而是形成一定的区域，目标的估计位置就将落在这一随机区域内，显然，使用Fang算法之类的非迭代算法直接进行求解是得不到估计位置的值的。

本文基于Jacobi迭代法进行了求解，可以得到目标估计位置的精确近似值。Jacobi迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法，且计算过程中原始矩阵A始终不变，比较容易并行计算。

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

1)用两个一维数组X0=(x0,y0,z0)和X1=(x1,y1,z1)存放相邻两次的迭代结果。任意选定初始向量存放在X0中。用(X0)i、(X1)i分别表示第i个数组元素。

3)用变量ε存放迭代误差界，当δ<ε时，停止迭代，(X1)i(i=1,2,…,n)为近似解。

图5 改进的定位算法工作流程

4 系统实现

系统实现包括硬件实现和软件实现两部分。在硬件实现部分，为基站和标签设计了电路并完成了超宽带测距通信程序设计。基站比标签多了一个型号为ESP8266的WiFi模块，用于与服务器建立连接，它们都采用STM32103RC作为控制单元以及DWM1000模块作为超宽带无线收发模块。超宽带测距通信程序设计时，选择110 kb/s的传输数据率、中心频率为3 993.6 MHz的信道以及499.2 MHz的带宽，可以很好地兼顾工作范围和功率消耗两方面。标签采用了小尺寸设计，标签和基站实物分别如图6所示。

图6 标签和基站实物图

软件实现部分，基于Android平台设计了定位服务器程序并开发了室内定位APP。室内定位APP的实时定位模块如图7所示，实时定位模块主要是用来帮助巡检人员实现精确定位与导航，通过WiFi网络自动更新地图可切换到其他工作场景。

图7 实时定位界面图

5 实验与误差分析

5.1 测距误差分析

为两种测距算法分别设计了程序，对各自的测距误差进行了实验对比。在10 m的测距范围内，每隔1 m设置一个距离点，在每个距离点上都采集了大量的测量值，分别取各自测量值的平均值进行比较，如表1所示。从表中可以看出，改进的双向测距误差始终是小于基本的双向测距的，距离测量值的均方差在大多数情况下也是小于基本的双向测距的，即数据波动性更小。实验结果也表明，增加一次无线电信息的发送之后，系统在测距阶段的测距精度更高。

表1 两种测距方式误差对比

5.2 定位误差分析

本文选择12.3 m×7 m的矩形会议室作为测试场地，如图8所示。定位时，随机在会议室中行走，记录下定位数据和此时位置。测试时，在测试场地的二维平面地图上选取了38个基准点进行了误差分析，每个基准点上面的定位数据作为测量点，结果如图9所示。

图8 测试场地图

图9 实际定位结果

从图9中可以看出，测量点与基准点的在横向或纵向上的偏差都在30 cm之内，能够满足精准室内移动定位的需求。为了更具体地描述系统定位误差，从38个基准点中挑选出了10个在位置上具有代表性的点，将每个点上的定位结果与其实际坐标进行比较，计算出定位误差，结果如表2所示。从表中可以看出，10组定位结果的平均误差为12 cm，最小误差为5 cm，最大误差为26 cm。测试过程中没有出现无定位或偏离较大的情形，说明系统也具有很好的稳定性。

表2 实际坐标与定位结果比较

本文将定位算法应用在了小范围的精确定位，测试时使用了4个基站，定位服务器获取了3组TDOA数据，组成了一个定位单元，其误差可以控制在30 cm之内。当需要应用到更大范围的场景中时，增加基站数，把多个定位单元求解结果的均值作为最终定位结果可以有效减小定位误差。

6 结语

基于超宽带技术设计了一套室内定位系统，描述了系统结构，重点研究了系统的测距算法和定位算法实现。对双向测距算法进行了改进，增加一次无线电信息的发送，可以减小由于时钟偏移引起的误差，有效地提高系统的测距精度。对基本的TDOA定位算法也进行了改进，加入了线性化处理与Jacobi迭代求解，避免了方程组由于误差存在而无法直接解算的情况，有利于系统的稳定性。经测试，该系统定位精度达30 cm，可在多种场景下进行使用，能够弥补GPS以及WiFi、蓝牙对室内高精度定位无法满足的情形，且该定位系统具有成本低、软件易扩展的特点。目前主要实现了定位功能，未来在此基础上可扩展服务信息推送、社交等更多元化功能，显著提升基于室内的位置服务品质。

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定位系统设计与实现[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] 蒋康荣.蜂窝网络中基于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—)，男，江苏扬州人，硕士研究生，主要研究方向：多媒体网络通信、物联网； 朱荣(1964—)，男，湖北武汉人，副教授，博士，主要研究方向：多媒体网络通信、人脸识别与可信身份认证； 陈玄(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.