基于到达时间差的多目标定位的泰勒松弛‑分部迭代算法

摘要

本发明公开了一种基于到达时间差(time difference of arrival TDOA)的多目标定位的泰勒松弛‑分部迭代算法，首先构造原始问题模型；然后使用泰勒松弛方法将原问题非凸约束松弛为凸约束，将整数变量松弛为连续变量；并通过粗略的半正定松弛和二次锥松弛得到本算法所需要的初始点；使用二部图匹配，得到整数解；将已得到的整数解带入模型，求得待定位的各个目标的最优估计坐标值。本发明利用泰勒松弛将非凸约束转化为凸约束，同时将离散的整数变量松弛为连续变量能大大降低原问题的复杂度，提高问题的可解性，在合适选择初始点，合理布局基站的前提下，能够得到全域最优解。

说明书

技术领域

本发明属于基于无线信号定位技术领域，特别涉及一种多目标定位问题的凸优化算法，适用于基于TDOA的多目标定位问题。

背景技术

无线定位技术，最早用于二战时期对舰艇和战斗机等军事目标的定位问题。随着科技的发展，无线定位技术越来越多的在工业、民用和国防等领域得到了广泛的应用。比如紧急救援响应，危险物品实时追踪，手机定位，过程控制。通过数学方法来改进无线定位算法的估计速度和精度一直是相关领域的研究热点。

得益于凸优化算法的发展，高效的凸优化松弛技术能应用于目标定位问题。随着大数据、移动互联网和物联网等的快速发展，多目标定位问题已成为一个无线定位领域的研究热点。TDOA是一种利用时间差进行定位的方法，他公国目标发生的信号到达不同基站的时间差来实现对目标的定位。TDOA不存在香味模糊问题，可以解决信号耦合问题，并且有着很高的定位的精度，因此有着很好的应用前景。目前的主要研究关注于使用凸优化算法去完善单目标定位问题，主要使用了半正定松弛，二次锥松弛、交替迭代和分枝界限法等方法来解决单目标定位问题。其中为了提高计算效率，一阶加速算法，拟牛顿法和内点法等高收敛速度的算法也应用在计算以上的松弛后的问题中，但是由于问题本身是一个非凸问题，因此很难保证算法在实际应用中收敛到全局最优。

特别地，对于多目标定位问题，因为基站不能识别信号源于哪一个目标，因此该问题是一个NP-hard问题，现有多目标定位算法只能在合理布置基站，然后目标分布在特定范围，选择合适的起始估计点的条件下得到一个全局最优解。否则，只能确保收敛到一个局部最优解。并且为了解决NP-hard问题，计算复杂度随着目标数量的增加而呈现出指数级的增加，并且容易陷于局部最优解。因此TDOA-MSL是一个值得去深入研究的问题。

发明内容

针对上述现有技术的不足，本发明的目的在于提出一种基于到达时间差(TDOA)的多目标定位的泰勒松弛-分部迭代算法(time difference of arrival based multiplesource localization problem TDOA-MSL)，该算法最突出的优势在于，利用泰勒松弛将非凸约束转化为凸约束，同时将离散的整数变量松弛为连续变量能大大降低原问题的复杂度，提高问题的可解性，在合适选择初始点，合理布局基站的前提下，能够得到全域最优解。

本发明是这样实现的：

基于到达时间差(TDOA)的多目标定位的泰勒松弛-分部迭代算法(TS)，首先构造原始问题模型(1)；然后使用泰勒松弛方法将原问题非凸约束松弛为凸约束，将整数变量松弛为连续变量；并通过粗略的半正定松弛和二次锥松弛得到本算法所需要的初始点；使用二部图匹配，得到整数解；将已得到的整数解带入模型(2)，求得待定位的各个目标的最优估计坐标值。

本发明具体的步骤如下：

基于到达时间差(TDOA)的多目标定位的泰勒松弛-分部迭代算法(TS)，是根据最大似然估计(MLE)模型得到一个混合整数非凸优化问题，通过泰勒松弛后，得到一个混合整数凸优化问题，然后得到多目标的位置估计值，包括以下步骤：

a)通过TDOA的定义，使用最大似然估计构造了一个混合整数、非凸的原始问题模型(1)；

b)通过采用泰勒松弛和二次锥松弛的方法，将原问题松弛为一个混合整数-凸优化问题模型(2)；

通过半正定松弛和二次锥松弛等方法松弛原始问题模型(1)得到问题(3)，解此问题得到算法所需的位置变量的初始点；

c)通过二部图匹配得到混合整数-凸优化问题模型(2)对应的整数解P；

d)固定整数解部分，混合整数凸优化问题模型(2)对应的问题变为一个连续凸问题模型(3)，通过迭代解连续凸问题模型(3)得到连续部分的最优解。

更进一步的方案是：

步骤a)包括：

ⅰ.TDOA定义,在L维空间内，假设有K个目标待定位x对应一个L×K矩阵，M个基站s对一个L×M矩阵，其中基站的位置行列式s已知，到达时间d对应的K×M矩阵已知，目标的位置x所对应的矩阵未知。第k个目标到第i个基站和第1个基站的的到达时间差t_k,i如下所示：

其中，第一个等式是TDOA的定义(含有噪声)，最后一项为噪音，不失一般性的，我们假设每个噪声都服从高斯分布，并且独立同分布；第二个等式是TOA的定义。

多目标定位中，假设对于每一个基站不能识别他获得的信号来自于哪一个目标(表示为)，为了识别每一个目标，我们引入了为每一个基站置换矩阵(permutationmatrix)以识别每一个目标，方法如下：

对第i个基站，可以通过其对应的置换矩阵的第k行去识别所接收的数据中对应第k个目标的到达时间差数据。

ⅱ.通过最大似然估计，目标函数为最小化噪声的2次范数，基于此我们构造了如下多目标定位模型：

Z_k，i≥0，Pⁱ∈Π

原始问题模型(1)

其中，Pⁱ表示第i个基站对应的置换矩阵；为第i个基站接受的TDOA数据；Z_k,i表示第k个目标与第i个基站的实际TOA数据与估计数据的差异的平方；t_k,i⁰为待计算的第k个目标与第i个基站和第1个基站的实际TDOA值；第二个约束是TDOA的物理定义。显而易见的，该问题是一个非凸混合整数问题，现有的定位算法很难得到全局最优解。

更进一步的方案是：

步骤b)包括：

ⅰ.模型(1)中第二个约束条件等价于以下不等式：

ⅱ.i中第一个不等式中非凸的变量可以使用包括但不限于泰勒一阶松弛、泰勒二阶或者泰勒高阶松弛从而变为一个凸的约束条件；

ⅲ.i中第二个不等式中非凸的第三的变量可以使用包括但不限于泰勒一阶松弛、泰勒二阶或者泰勒高阶松弛从而变为一个凸的约束条件。

ⅳ.以iii中的变量定位为g(x)，使用泰勒一阶松弛为例，可以得到如下的凸函数：

其中x_:,kⁿ为迭代k次的已知x估计值；

更进一步的方案是：

步骤c)包括：

ⅰ.对原始问题(1)进行包括但不限于半正定松弛、二次锥松弛和泰勒松弛，以使得原问题变为凸问题模型(3)，以降低计算复杂度；

ⅱ.通过解问题模型(3)可以得到泰勒松弛后的问题模型所需要的初始点；

ⅲ.该问题可以使用包括但不限于内点法、梯度下降法(固定步长，变化步长)和牛顿法等成熟的凸优化算法来得到该子问题的最优解和最优函数值。

更进一步的方案是：

步骤d)包括：

得到整数解的二部图匹配方法包括但不限于：最大匹配，完美匹配等方法。

更进一步的方案是：

步骤e)包括：

固定整数解后模型(2)经过泰勒松弛后就变为了一个连续凸优化问题，得到模型(4)，可以使用包括但不限于内点法、梯度下降法(固定步长，变化步长)和牛顿法等成熟的凸优化算法来得到该子问题的最优解和最优函数值。

更进一步的方案是：

构建最大似然估计(MLE)模型，包括：

ⅰ.建立噪声的概率密度函数(包括但不限于服从高斯分布)：

ⅱ.计算实际到达时间表示为t⁰+ε；

ⅲ.目标函数为使得噪声的平方和最小化；

ⅳ.考虑的噪声信噪比(SNR)主要范围为0-100dB。

更进一步的方案是：

以使用一阶泰勒松弛为例，在步骤b)中，得到以下松弛后的最大似然估计问题模型。

Pⁱ∈Π

其中第一个约束条件和第二个约束条件是泰勒一阶松弛后不等式约束条件。

泰勒一阶松弛后得到的模型(2)变为了一个混合整数-凸优化问题。

将整数部分松弛为0-1区间内连续变量，则模型(2)则变为了一个连续凸优化问题，可以使用成熟的凸优化方法得到最优解x^*，基于此迭代更新第一个约束条件和第二个约束条件中的常数项x_:,k⁰直到收敛或者迭代次数超过了预设的最大迭代次数。

更进一步的方案是：

所述凸问题模型(3)具有以下形式：

凸问题模型(3)

更进一步的方案是：

步骤e)通过二部图匹配得到混合整数凸优化问题模型(2)对应的整数解P，固定整数解后模型(2)变为了连续凸问题，可以使用前述算法得到最终的目标的位置估计信息。

本专利首先将原问题整数变量松弛为连续变量，大大降低了算法的计算复杂度，再通过使用二部图匹配得到整数解。该算法能有效提高算法的收敛速度。该方法可应用于手机定位，救援定位，雷达不明飞行物定位等领域中。

附图说明

图1为本发明流程示意图；

图2为本发明实施例1计算的门特卡罗模拟结果图；

图3为本发明实施例2计算的门特卡罗模拟结果图。

具体实施方式

下面结合具体实施方式对本发明作进一步的说明。

如附图1所示，基于到达时间差(TDOA)的多目标定位的泰勒松弛-分部迭代算法(TS)，是根据最大似然估计(MLE)模型得到一个混合整数非凸优化问题，通过泰勒松弛后，得到一个混合整数凸优化问题，然后得到多目标的位置估计值，包括以下步骤：

a)通过TDOA的定义，使用最大似然估计构造了一个混合整数、非凸的原始问题模型(1)；

b)通过采用泰勒松弛和二次锥松弛的方法，将原问题松弛为一个混合整数-凸优化问题模型(2)；

通过半正定松弛和二次锥松弛等方法松弛原始问题模型(1)得到问题(3)，解此问题得到算法所需的位置变量的初始点；

c)通过二部图匹配得到混合整数-凸优化问题模型(2)对应的整数解P；

d)固定整数解部分，混合整数凸优化问题模型(2)对应的问题变为一个连续凸问题模型(3)，通过迭代解连续凸问题模型(3)得到连续部分的最优解。

更进一步的方案是：

步骤a)包括：

ⅰ.TDOA定义,在L维空间内，假设有K个目标待定位x对应一个L×K矩阵，M个基站s对一个L×M矩阵，其中基站的位置行列式s已知，到达时间d对应的K×M矩阵已知，目标的位置x所对应的矩阵未知。第k个目标到第i个基站和第1个基站的的到达时间差t_k,i如下所示：

其中，第一个等式是TDOA的定义(含有噪声)，最后一项为噪音，不失一般性的，我们假设每个噪声都服从高斯分布，并且独立同分布；第二个等式是TOA物理的定义。

多目标定位中，假设对于每一个基站不能识别他获得的信号来自于哪一个目标(表示为)，为了识别每一个目标，我们为每一个基站引入了置换矩阵(permutationmatrix)以识别每一个目标，方法如下：

对第i个基站，可以通过其对应的置换矩阵的第k行去识别所接收的数据中对应第k个目标的到达时间差数据。

ⅱ.通过最大似然估计，目标函数为最小化噪声的2次范数，基于此我们构造了如下多目标定位模型：

Z_k，i≥0，Pⁱ∈Π

原始问题模型(1)

其中，Pⁱ表示第i个基站对应的置换矩阵；为第i个基站接收的TDOA数据；Z_k,i表示第k个目标与第i个基站的实际TOA数据与估计数据的差异的平方；t_k,i⁰为待计算的第k个目标与第i个基站和第1个基站的实际TDOA值；第二个约束是TDOA的物理定义。显而易见的，该问题是一个非凸混合整数问题，现有的定位算法很难得到全局最优解。

更进一步的方案是：

步骤b)包括：

ⅰ.模型(1)中第二个约束条件等价于以下不等式：

ⅱ.i中第一个不等式中非凸的变量可以使用包括但不限于泰勒一阶松弛、泰勒二阶或者泰勒高阶松弛从而变为一个凸的约束条件；

ⅲ.i中第二个不等式中非凸的变量可以使用包括但不限于泰勒一阶松弛、泰勒二阶或者泰勒高阶松弛从而变为一个凸的约束条件。

ⅳ.以iii中的变量定位为g(x)，使用泰勒一阶松弛为例，n次迭代后可以得到如下的凸函数：

其中x_:,kⁿ为迭代k次的已知x估计值；

更进一步的方案是：

步骤c)包括：

ⅰ.对原始问题(1)进行包括但不限于半正定松弛、二次锥松弛和泰勒松弛，以使得原问题变为凸问题模型(3)，以降低计算复杂度；

ⅱ.通过求解问题模型(3)可以得到泰勒松弛后的问题模型所需要的初始点；

ⅲ.该问题可以使用包括但不限于内点法、梯度下降法(固定步长，变化步长)和牛顿法等成熟的凸优化算法来得到该子问题的最优解和最优函数值。

更进一步的方案是：

步骤d)包括：

得到整数解的二部图匹配方法包括但不限于：最大匹配，完美匹配等方法。

更进一步的方案是：

步骤e)包括：

固定整数解后模型(2)经过泰勒松弛后就变为了一个连续凸优化问题，得到模型(4)，可以使用包括但不限于内点法、梯度下降法(固定步长，变化步长)和牛顿法等成熟的凸优化算法来得到该子问题的最优解和最优函数值。

更进一步的方案是：

构建最大似然估计(MLE)模型，包括：

ⅰ.建立噪声的概率密度函数(服从高斯分布)：

ⅱ.计算实际到达时间表示为t⁰+ε；

ⅲ.目标函数为使得噪声的平方和最小化；

ⅳ.考虑的噪声信噪比(SNR)主要范围为0-100dB。

更进一步的方案是：

以使用一阶泰勒松弛为例，在步骤b)中，得到以下松弛后的最大似然估计问题模型。

Pⁱ∈П

其中第一个约束条件和第二个约束条件是泰勒一阶松弛后不等式约束条件。

泰勒一阶松弛后得到的模型(2)变为了一个混合整数-凸优化问题。

将整数部分松弛为0-1区间内连续变量，则模型(2)则变为了一个连续凸优化问题，可以使用成熟的凸优化方法得到最优解x*，基于此迭代更新第一个约束条件和第二个约束条件中的常数项x_:,k⁰直到收敛或者迭代次数超过了预设的最大迭代次数。

更进一步的方案是：

迭代初始点可以通过以下松弛凸问题求得，所述凸问题模型(3)具有以下形式：

凸问题模型(3)

通过其他粗略松弛手段得到的解也可以作为本专利的迭代初始点。

更进一步的方案是：

步骤e)通过二部图匹配得到混合整数凸优化问题模型(2)对应的整数解P，固定整数解后模型(2)变为了连续凸问题，可以使用前述算法得到最终的目标的位置估计信息。

下面根据实际情况举出两个更具体的实施例进行说明。

实施例1

基站：

s＝

4040-40-4040-4040-40

待定位的目标：

x＝

10-2030-10-2520

信噪比

100次蒙特卡洛模拟后，计算的目标位置均方根估计误差如附图2所示。

实施例2

基站：

s＝

20-10-40-40-25040-40

待定位的目标：

x＝

10-20-10-10-2520

100次蒙特卡洛模拟后，计算的目标位置散点图如附图3所示。

从附图2、3可以看到，门特卡罗模拟结果在经过多次模拟后具有相当的准确性。

所有数值实验都是由笔记本电脑完成，由Figure 1，Figure 2可知本专利所描述的算法能解决TDOA-MSL定位问题，在信噪比大于等于20dB时，能得到不错的数值结果，得到接近CRLB精度的估计值。

尽管这里参照本发明的解释性实施例对本发明进行了描述，上述实施例仅为本发明较佳的实施方式，本发明的实施方式并不受上述实施例的限制，应该理解，本领域技术人员可以设计出很多其他的修改和实施方式，这些修改和实施方式将落在本申请公开的原则范围和精神之内。