基于TDOA的二分查找定位方法

摘要

本发明公开了一种基于TDOA的二分查找定位方法，其通过坐标转换、二分查找等步骤对估计位置给出精确估计，并且对于存在高度差的情况，通过高度补偿的方法弥补了二维定位误差，保证了定位精度。该方法计算量小，便于后续实时系统的研发，可广泛用于对移动终端的位置估计。

说明书

技术领域

本发明涉及室内定位领域，尤其涉及一种基于TDOA的二分查找定位方法。

背景技术

随着互联网技术和通信技术的发展，位置信息的重要性不断凸显，由此引起的定位问题受到了人们的广泛关注。目前，GPS等技术能够较精确地完成室外定位。但是，随着社会的发展，大型建筑(比如商场)的数目在不断增加，由此使人们对室内定位的需求不断增加，然而GPS却无法在室内完成精确定位，这就需要一种精确的室内定位技术。目前用于室内定位的技术有基于RF、光学、地磁、音频等，无论采用哪种定位技术，室内定位方法主要有以下几种：指纹法、基于方向角、基于到达时间差(Time Difference of Arrival，TDOA)、和基于到达时间(Time of Arrival，TOA)，其中指纹法需要在定位之前建立和维护指纹库，这需要较大的工作量且该方法的精确度较差；基于方向角的定位方法往往需要较高的硬件成本；TDOA和TOA可以实现高精度的室内定位，但两者相比，TOA需要更严格的时钟同步条件。

现有的基于TDOA的定位方法主要有Chan算法、Taylor算法等，其中Chan算法依据最小二乘原理，求取估计距离差与理论距离差相差最小时的坐标，然而，在真实应用中，TDOA数据可能会有一定的误差，Chan算法在该情况得到的估计位置稳定性差而且计算量大。Taylor算法需要一个初始值，该初始值的选取采用Chan算法多次计算取平均得到，之后便可求得估计位置，该算法计算量大，并且与初始值选取有很大关系。本发明提到了的一种基于TDOA的二分查找定位方法可以较稳定地估计位置，而且计算量小，易于后续移植。

在室内定位中，二维位置估计可满足大部分的需求。但在实际的室内定位布置中，基站可能放置在墙面、天花板等处，从而导致基站所构平面与目标所在水平面存在高度差，该高度差影响定位精度。目前人们通常采用三维定位来解决这一问题，但是这将增加运算量。

发明内容

本发明的目的是提供一种基于TDOA的二分查找定位方法，该方法可快速准确的获取目标二维坐标，且计算量较小。

本发明的目的是通过以下技术方案实现的：

一种基于TDOA的二分查找定位方法，包括：

获取TDOA信息；

判断接收点所构平面与目标所在水平面是否存在高度差，由各点的高度决定；

情况1：若不存在高度差，则根据TDOA信息计算距离差，以任意两个距离差使用二分查找算法进行目标位置的初步估算，再根据初步估算出的所有目标位置的均值及其标准差对初步估算出的目标位置进行筛选，并更新均值及其标准差，直至标准差满足要求，则均值的位置即为目标最终位置；

情况2：若存在高度差，则利用TDOA信息计算原始距离差，再以任意两个原始距离差采用二分查找算法初步估算目标点的估计位置，在估计位置处计算有高度差和无高度差时距离差的差值，之后将原始距离差减去相应差值，以此更新距离差，之后将更新后的距离差结合情况1的方式完成定位。

所述获取TDOA信息包括：

由目标发射信号源，不同位置接收点接收到该信号源的时间差；

或者，由各个接收点发射信号源，目标接收到不同基站的信号源的时间差。

所述情况1中获得目标最终位置的具体过程如下：

假设有目标点P，以及A、B、C三个接收点，且三个接收点所构平面与目标点P所在水平面平行；目标点P发射音频信号，在A、B、C三个接收点通过麦克风接收音频信号，并通过相关检测算法，判断信号到达时刻；从而计算到达A点、B点的时间差Δt1，以及到达B点、C点的时间差Δt2，再记R1为目标位置P点到接收点A的距离，与目标位置P点到接收点B的距离之间的距离差；记R2为目标位置P点到接收点B的距离，与目标位置P点到接收点C的距离之间的距离差，c为声速，则：

再使用二分查找定位方法初步估计目标位置，步骤如下：

a、坐标转换：假设(x_A,y_A)、(x_B,y_B)、(x_C,y_C)分别为接收点A、B、C的坐标，通过平移将接收点A移到原点(0，0)，然后按下式绕接收点A逆时针方向旋转一个角度θ，使接收点B与C的坐标变成(x′_B,0)、(x′_C,y′_C)；

b、判断距离差R1是否等于0，若等于0，则目标位置位于接收点A与B之间的中垂线，获得目标位置坐标(x′_B/2，0)；否则估计目标位置位于一条双曲线上，且双曲线以接收点A与B为焦点，并继续下一步骤；

c、初始化P1点与P2点纵坐标，使这两点的纵坐标分别对应为接收点B与C两点的纵坐标，P1点与P2点的横坐标由下式计算，计算过程中根据x′_B的正负确定开方的正负，确保横坐标的绝对值小于x′_B的绝对值；再取P1点与P2点纵坐标中值作为P点横坐标，代下式得到点P的纵坐标：

其中，a＝0.5*R1,c＝0.5*x′_B，b²＝c²-a²，且||P1A||-||P1B||＝R1，||P2A||-||P2B||＝R1，P1A、P1B、P2A、P2B分别为P1点到接收点A的距离、P1点到接收点B的距离、P2点到接收点A的距离、P1点到接收点B的距离；

d、计算下述两个式子，并根据计算结果更新P1点或P2点：

其中，P1C、PB、PC、P2C分别为P1点到接收点C的距离、P点到接收点B的距离、P点到接收点C的距离、P2点到接收点C的距离；

如果第一个式子大于0，则固定P2点，将P1点移动到P点；如果第二个式子大于0，则固定P1点，将P2点移动到P点；

e、重复上述步骤d，直到||P1P2||＜δ，其中δ为设定值，此时初步得到估计位置的纵坐标为P1点与P2点的中点，横坐标由步骤c中的公式计算，从而获得目标位置坐标，再按照步骤a的原理将坐标进行转换，转换后的坐标即为初步估计的目标位置，记为pos1；

重复上述步骤a～e获得n个初步估计的目标位置，再计算均值与标准差；

如果标准差大于阈值，则将n个初步估计的目标位置与均值位置相距最远的位置排除，由剩下的目标位置重新计算均值和标准差；并不断重复这一过程，直至标准差满足要求，则剩余的目标位置均值的位置即为目标最终位置。

所述情况2中获得目标最终位置的具体过程如下：

基于TDOA信息计算原始距离差信息，其中，目标位置P点到接收点A的距离，与目标位置P点到接收点B的距离之间的距离差记为R1'；目标位置P点到接收点B的距离，与目标位置P点到接收点C的距离之间的距离差记为R2'；

其次，利用距离差R1'与R2'并结合情况1中的步骤a～e，获得一个初步定位结果(x′,y′)；

然后，利用下式计算(x′,y′)处有高度差h和无高度差时距离差的差值，记为ΔR1,ΔR2：

再更新距离差：

最后，根据更新后的距离差R1”与R2”采用情况1方式来计算目标最终位置。

由上述本发明提供的技术方案可以看出，其通过坐标转换、二分查找等步骤对估计位置给出精确估计，并且对于存在高度差的情况，通过高度补偿的方法弥补了二维定位误差，保证了定位精度。该方法计算量小，便于后续实时系统的研发，可广泛用于对移动终端的位置估计。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域的普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他附图。

图1为本发明实施例提供的一种基于TDOA的二分查找定位方法的流程图；

图2为本发明实施例提供的二分查找定位方法模型图；

图3为本发明实施例提供的多次估计位置加权平均获取最终结果示意图

图4为本发明实施例提供的高度补偿定位示意图。

具体实施方式

下面结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明的保护范围。

图1为本发明实施例提供的一种基于TDOA的二分查找定位方法的流程图。如图1所示，其主要包括如下步骤：

步骤11、获取TDOA信息。

本发明实施例中，TDOA信息可以采用如下两种方式来获取：由目标发射信号源，不同位置接收点接收到该信号源的时间差；或者，由各个接收点发射信号源，目标接收到不同基站的信号源的时间差。

示例性的，可以假设以音频作为定位手段，提供一种基于TDOA的二分查找定位方法。如图2所示，目标点P发射音频信号，在A、B、C三点(以矩形为例)通过麦克风接收音频信号，并通过相关检测算法，判断信号到达时刻，并计算到达A点、B点的时间差Δt1，以及到达B点、C点的时间差Δt2，记R1为目标位置P点到接收点A的距离，与目标位置P点到接收点B的距离之间的距离差；R2为目标位置P点到接收点B的距离，与目标位置P点到接收点C的距离之间的距离差，c为声速，那么有：

另外，本发明实施例中，三个接收点所构平面与目标所在水平面平行。

步骤12、判断接收点所构平面与目标所在水平面是否存在高度差。

本发明实施例中，根据是否存在高度差的分为两种情况来进行计算；情况1为不存在高度差，转入步骤13；情况2为存在高度差，转入步骤14。

步骤13、根据TDOA信息计算距离差，以任意两个距离差使用二分查找算法进行目标位置的初步估算，再根据初步估算出的所有目标位置的均值及其标准差对初步估算出的目标位置进行筛选，并更新均值及其标准差，直至标准差满足要求，则均值的位置即为目标最终位置。

本步骤的场景依然参见图2，及共有A、B、C三个接收点，且三个接收点所构平面与目标所在水平面平行。

前文给出了根据TDOA信息计算距离差R1与R2的方式；本发明实施例为了便于后续描述，还给出一种几何方法来计算距离差R1与R2；具体如下：

设(x,y)为目标位置P点的坐标，(x_A,y_A)、(x_B,y_B)、(x_C,y_C)分别为接收点A、B、C的坐标，根据距离差公式有：

其中，R1为目标位置P点到接收点A的距离，与目标位置P点到接收点B的距离之间的距离差；R2为目标位置P点到接收点B的距离，与目标位置P点到接收点C的距离之间的距离差。

再使用二分查找定位方法初步估计目标位置，步骤如下：

a、坐标转换：通过平移将接收点A移到原点(0，0)，然后按下式绕接收点A逆时针方向旋转一个角度θ，使接收点B与C的坐标变成(x′_B,0)、(x′_C,y′_C)。

b、判断距离差R1是否等于0，若等于0，则目标位置位于接收点A与B之间的中垂线，获得目标位置坐标(x′_B/2，0)(还需要经步骤e所述的方式进行坐标转换为初步估计的目标位置)；否则估计目标位置位于一条双曲线上，且双曲线以接收点A与B为焦点，并继续下一步骤。

c、初始化P1点与P2点纵坐标，使这两点的纵坐标分别对应为接收点B与C两点的纵坐标，P1点与P2点的横坐标由下式计算，计算过程中根据x′_B的正负确定开方的正负，确保横坐标的绝对值小于x′_B的绝对值；再取P1点与P2点纵坐标中值作为P点横坐标，代下式得到点P的纵坐标：

其中，a＝0.5*R1,c＝0.5*x′_B，b²＝c²-a²，且||P1A||-||P1B||＝R1，||P2A||-||P2B||＝R1，P1A、P1B、P2A、P2B分别为P1点到接收点A的距离、P1点到接收点B的距离、P2点到接收点A的距离、P1点到接收点B的距离。

举例来说，P1点与P2点的纵坐标(即y)都是已知的，分别带入上式，可以求解出两个x，也就获得了P1点与P2点的坐标。之后，再将两个x的中值带入上式，可以求解出一个y，也就获得了点P的坐标，但是，此时结果并不可靠，还需要继续执行后续步骤。

d、计算下述两个式子，并根据计算结果更新P1点或P2点：

其中，P1C、PB、PC、P2C分别为P1点到接收点C的距离、P点到接收点B的距离、P点到接收点C的距离、P2点到接收点C的距离；

如果第一个式子大于0，则固定P2点，将P1点移动到P点；如果第二个式子大于0，则固定P1点，将P2点移动到P点；

e、重复上述步骤d，直到||P1P2||＜δ，其中δ为设定值，此时初步得到估计位置的纵坐标为P1点与P2点的中点，横坐标由步骤c中的公式计算，从而获得目标位置坐标，再按照步骤a的原理将坐标进行转换，转换后的坐标即为初步估计的目标位置，记为pos1。

重复上述步骤a～e获得n个初步估计的目标位置，再计算均值与标准差。上述计算的目标位置是在固定距离差R1的基础上计算得来，采用类似的方法，可以得到固定距离差R2时计算到的目标位置pos2；同理，还可以固定目标位置P点到接收点A的距离，与目标位置P点到接收点C的距离之间的距离差R3，来计算目标位置pos3，等等。基于这样的原理，最终可以获得n个初步估计的目标位置，再计算其均值与标准差。

如图3所示，如果标准差大于阈值，则将n个初步估计的目标位置与均值位置相距最远的位置排除，由剩下的目标位置重新计算均值和标准差；并不断重复这一过程，直至标准差满足要求，则剩余的目标位置均值的位置即为目标最终位置。

本领域技术人员可以理解，文中所涉及的阈值、设定值都可以根据实际情况来设定，同时，所述的标准差满足要求，也可以理解为标准差达到一个较小的值(预设值)

步骤14、通过TDOA信息(声速*时间差)得到原始距离差信息，但是此时有高度的影响，直接按照前面的步骤13估计位置，有较大误差，故采用高度补偿的方法。具体如下：利用TDOA信息计算原始距离差信息，再以任意两个原始距离差采用二分查找算法(即步骤13中的步骤a～e)初步估算目标点的估计位置P4，在P4点处计算有高度差和无高度差时距离差的差值，之后将原始距离差减去该差值，以此完成更新距离差的目的，之后将新的距离差结合情况1的方式完成定位，最后按此过程迭代完成最终定位。

本发明实施例中，存在高度差时，原始距离差信息同样使用TDOA信息计算，如前文的式(1)所示，为了与情况1区分，情况2中目标位置P点到接收点A的距离，与目标位置P点到接收点B的距离之间的距离差记为R1'；目标位置P点到接收点B的距离，与目标位置P点到接收点C的距离之间的距离差记为R2'。

当然，也可以几何方法来描述距离差R1'与R2'，如图4所示，在情况1的基础上，考虑了存在高度差的问题，公式(2)变成如下所示通过高度补偿的方法进一步提高了目标定位精度：

其中，h为高度差，为已知值或者在一定范围内浮动。

其次，利用距离差R1'与R2'并结合情况1中的步骤a～e，获得一个初步定位结果P4(x′,y′)。简单来说，就是用R1'与R2'替换步骤a～e中的R1与R2，则步骤e将获得转换坐标后的目标位置，也即初步定位结果P4(x′,y′)。

然后，利用下式计算(x′,y′)处有高度差h和无高度差时距离差的差值，记为ΔR1,ΔR2：

再更新距离差：

最后，根据更新后的距离差R1”与R2”采用情况1方式再来完成一次位置估计，得到位置估计后，进行迭代，迭代过程如下：在当前估计位置再次计算ΔR1,ΔR2，并按(3)式将原始距离差信息再次更新，重复迭代多次，得到最终的检测点。

迭代过程中一旦固定一个后，不会改变，也就是说根据R1”和R2”可以得到两个估计位置，分别为固定R1”和固定R2”。当接收点较多时，至少三个接收点可以得到两个距离差。

本发明实施例上述方案，通过坐标转换、二分查找等步骤对估计位置给出精确估计，并且对于存在高度差的情况，通过高度补偿的方法弥补了二维定位误差，保证了定位精度。该方法计算量小，便于后续实时系统的研发，可广泛用于对移动终端的估计。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到上述实施例可以通过软件实现，也可以借助软件加必要的通用硬件平台的方式来实现。基于这样的理解，上述实施例的技术方案可以以软件产品的形式体现出来，该软件产品可以存储在一个非易失性存储介质(可以是CD-ROM，U盘，移动硬盘等)中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述的方法。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明披露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求书的保护范围为准。