基于选择TDOA的改进遗传蚁群混合定位方法及装置

基于选择tdoa的改进遗传蚁群混合定位方法及装置
技术领域
1.本发明涉及无线定位技术领域，尤其涉及一种基于选择tdoa的改进遗传蚁群混合定位方法及装置。


背景技术：

2.近些年，5g网络建设速度非常快，随着5g时代的来临，5g作为一张物理网络，可以提供多种能力和服务，5g定位与通信融合，最大程度体现了“一网多用”的优势。5g无线网络与传统的宏蜂窝网络的区别，主要体现在其能够为移动定位所需的基础数据提供有效增益。在5g网络中，小蜂窝和d2d传输将占主导地位，这样的布局方式缩短了基站和移动设备之间的距离，较短的距离将增加视线(los)概率，而且无线网络带宽的增加会使定位更加准确。5g定位主要用到的是一种下行定位(o-tdoa)方法,在用户处观察(即测量)两个基站发送的基于专用定位参考信号(prs)的参考信号时差(rstd)，从而定义用户所在的双曲线。然后可通过对多个不同的基站发出的下行定位参考信号prs产生的到达时间差rstd进行解析计算，并最终得到实际的位置坐标。
3.在实际应用中，传播环境可分为视距传播和非视距传播，nlos传播将直接影响tdoa观测量的测量精度，从而在本质上降低定位算法的精度和稳定性，成为了急需解决的问题。目前，解决定位算法中nlos误差问题主要集中在以下三种方案，第一种，识别los和nlos路径。该方法需要首先通过识别算法对los路径和nlos路径做出识别判断，放弃nlos路径，仅仅选择los路径进行定位解析，但是该方法局限性很大，在los路劲极少或是只有nlos路径时可能无法进行有效定位。第二种，nlos误差建模。首先对nlos误差进行建模，然后利用预测模型减小观测量中的nlos误差，但该方法在实际应用中有着很大的困难，以及不确定性，因为信号的传播模型在实际的定位环境中十分复杂。第三种，利用最优化理论优化定位解算过程。针对第三种，现有技术中有在两步加权最小二乘(wls)算法的基础上做改进从而提高定位精度的，也有基于因子图算法进行两步定位的，还有基于los/nlos的先验知识的自适应toa估计定位的，以及通过机器学习的方法将nlos分类来提高定位精度的，或者利用卷积神经网络(cnn)识别信道的脉冲响应图，以此达到高精度识别los/nlos信道的目的。上述的定位方法能够在一定程度上或在某一方面、某一阶段提高定位精度，但仍不能满足在nlos环境下对高定位精度的要求。
4.因此，有必要研究一种新的基于选择tdoa的改进遗传蚁群混合定位方法来应对现有技术的不足，以解决或减轻上述一个或多个问题。


技术实现要素：

5.有鉴于此，本发明提供了一种基于选择tdoa的改进遗传蚁群混合定位方法及装置，能够提高在求解空间中的求解效率和收敛性，改善传统tdoa算法在非视距下的定位精度不佳的问题。
6.一方面，本发明提供一种基于选择tdoa的改进遗传蚁群混合定位方法，所述方法
的步骤包括：
7.s1、找到具有最小残差子集的基站组合作为定位所需的参考点；
8.s2、将参考点的tdoa值代入chan算法进行求解，得到粗略坐标估计结果；
9.s3、将粗略坐标估计结果作为遗传蚁群算法的节点坐标进行全局搜索，把包含信息素最多的节点作为最优解；
10.s4、将最优解作为初始值代入taylor算法进行迭代求解，得到最终的目标定位结果。
11.如上所述的方面和任一可能的实现方式，进一步提供一种实现方式，步骤s1的内容包括：
12.s11、从基站总集中选择出所有个数为m的基站组合；m为不小于4的正整数；
13.s12、计算各基站组合的残差，并利用最小残差法进行筛选，将具有最小残差子集的基站组合作为定位所需的参考点；
14.所述残差定义为距离差观测值和使用中间位置计算出预测值之间的差值。
15.如上所述的方面和任一可能的实现方式，进一步提供一种实现方式，步骤s3中遗传蚁群算法对节点坐标进行全局搜索的内容包括：
16.s31、以遗传算法为主对节点坐标进行处理，快速产生初始的信息素，在保证全局收敛的同时随机分布在解空间中；
17.s32、采用改进的蚁群算法进行搜索：根据信息素，从多点出发寻找最优解，从而利用正反馈的优势提高在全局中求解最优解的效率。
18.如上所述的方面和任一可能的实现方式，进一步提供一种实现方式，步骤s31的具体内容包括：
19.采用实数编码的方式对编码对象进行编码，以便于处理复杂的变量约束条件；
20.采用faure序列在目标搜索空间内随机产生原始种群，设置原始种群个体的数量，并确定种群中每个单独个体的取值范围；
21.确定适应度函数；
22.确定遗传算子；
23.采用精英保留策略保留现有解中的部分优良个体，使其直接成为下一代种群的成员；
24.重复进行遗传算法的计算过程，直到满足预设的终止条件，然后将现在所选的最优个体作为输出结果；
25.根据输出结果生成信息素。
26.如上所述的方面和任一可能的实现方式，进一步提供一种实现方式，所述信息素包括：最优个体的坐标数据和随机生成的数据。
27.如上所述的方面和任一可能的实现方式，进一步提供一种实现方式，所述适应度函数为：
[0028][0029]
其中，ri表示移动目标的真实坐标到第i个基站的
距离，表示移动目标的估计坐标位置到第i个基站的距离，ni表示服从高斯分布的噪声误差，m为基站的数量。
[0030]
如上所述的方面和任一可能的实现方式，进一步提供一种实现方式，确定遗传算子时，交叉概率值为0.9，变异概率值为0.05。
[0031]
如上所述的方面和任一可能的实现方式，进一步提供一种实现方式，步骤s32的具体内容包括：
[0032]
按照搜索规则进行搜索，并以迁移概率进行迁移；
[0033]
t时刻蚂蚁k从位置i移动到位置j的迁移概率p的表达式为：
[0034][0035]
其中，α为信息素启发因子，β为期望启发因子，t为时间，η
ij
表示路径(i,j)能见度，τ
ij
(t)表示t时刻路径(i,j)上现有的信息素量；allowed为蚂蚁k待访问的坐标点的集合，s是allowed中的一个坐标点，η
is
表示从i坐标到s坐标的启发程度；
[0036]
信息素更新：更新路径信息素强度和信息素增量。
[0037]
如上所述的方面和任一可能的实现方式，进一步提供一种实现方式，第k只蚂蚁在路径(i,j)上每遍历一次所留的信息素增量为：
[0038][0039]
式中，lk表示蚂蚁k留下信息素的路途长度，q为蚁群遍历一遍的信息素总量；
[0040]
t+1时刻路径(i,j)上现有的信息素强度为：
[0041]
τ
i,j
(t+1)＝(1-ρ)τ
i,j
(t)+δτ
i,j
(t,t+1)，
[0042]
式中，τ
ij
(t)表示t时刻路径(i,j)上现有的信息素量，(1-ρ)表示信息素残留系数，δτ
ij
(t,t+1)表示蚁群总体在时间(t,t+1)遍历一次的信息素增量；
[0043]
表示编号为k的蚂蚁在时间(t,t+1)的信息素增量。
[0044]
另一方面，本发明提供一种基于选择tdoa的改进遗传蚁群混合定位装置，包括存储器、处理器以及存储在所述存储器中并能在所述处理器上运行的计算机程序，其特征在于：所述处理器执行所述计算机程序时实现如上任一所述方法的步骤。
[0045]
与现有技术相比，上述技术方案中的一个技术方案具有如下优点或有益效果：该算法提高了在求解空间中的求解效率和收敛性，改善了传统tdoa算法在非视距下的定位精度不佳的问题；
[0046]
上述技术方案中的另一个技术方案具有如下优点或有益效果：经仿真实验结果表明，本发明的定位算法相比其他算法具有更好的定位精度和稳定性，最接近克拉美罗下界。
[0047]
当然，实施本发明的任一产品并不一定需要同时达到以上所述的所有技术效果。
附图说明
[0048]
为了更清楚地说明本发明实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其它的附图。
[0049]
图1是本发明一个实施例提供的基于选择tdoa的改进遗传蚁群混合定位方法流程图；
[0050]
图2是本发明一个实施例提供的tdoa定位原理图；
[0051]
图3是本发明一个实施例提供的改进遗传蚁群算法的流程图；
[0052]
图4是本发明一个实施例提供的最小残差加权chan-taylor联合算法流程图；
[0053]
图5是本发明一个实施例提供的ga-aco混合算法的收敛性能比较图；
[0054]
图6是本发明一个实施例提供的不同基站数量下rwc-gaa-t算法的性能比较图；
[0055]
图7是本发明一个实施例提供的不同基站数量时rwc-gaa-t算法的cdf与rmse的关系曲线；
[0056]
图8是本发明一个实施例提供的不同基站下的定位均方根误差；
[0057]
图9是本发明一个实施例提供的各个算法在不同基站下的rmse性能比较，其中，图(a)bs＝4，图(b)bs＝5，图(c)bs＝6,图(d)bs＝7；
[0058]
图10是本发明一个实施例提供的各个算法在不同基站下的cdf与rmse的关系曲线图，其中，图(a)bs＝4，图(b)bs＝5，图(c)bs＝6，图(d)bs＝7；
[0059]
图11是本发明一个实施例提供的不同基站半径的定位均方根误差图；
[0060]
图12是本发明一个实施例提供的7个基站时rwc-gaa-t算法的性能提升百分比折线图。
具体实施方式
[0061]
为了更好的理解本发明的技术方案，下面结合附图对本发明实施例进行详细描述。
[0062]
应当明确，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。
[0063]
针对传统tdoa定位算法不能在非视距(nlos)传播条件下取得良好定位效果的问题，本发明提出一种基于选择tdoa的改进遗传蚁群混合定位算法。首先，利用最小残差原则改进chan算法在位置估计中对于基站的筛选组合方式，并在加权过程中赋予不同的权值增加分组区分度，然后将改进chan算法得到的估计坐标作蚁群算法的节点位置，并利用遗传算法优化蚁群算法的初始信息素的生成过程，最后将改进算法求解的估计坐标作为taylor算法的初始值，通过迭代求解最终定位结果。图1是本发明定位方法的流程图。
[0064]
1.本发明的定位模型
[0065]
1.1tdoa测量模型
[0066]
基于tdoa的定位模型从几何模型的角度看也可称为双曲线定位模型。在实际情况
中，因为信号在空中的传输时间的计算难度较大，无法实现两端时间的精准同步，所以tdoa定位使用移动目标位置到其中两个基站的时间差作为观测量，利用无线电传播速度将时间差转化为距离差，然后建立几何关系方程，移动目标位置的坐标就是所作双曲线的交点坐标。tdoa定位原理如图2所示。
[0067]
tdoa定位至少需要三个基站参与定位，假设bs1，bs2，bs3为参考基站，其位置坐标分别为(x1,y1),(x2,y2),(x3,y3)，移动目标的位置坐标为(x,y)，tdoa定位要选择服务基站作为基准参考，假设服务基站为基站1。ri表示基站i到目标位置之间的距离，r
i,1
表示基站1到目标位置的距离与第i个基站到目标位置的距离相减的距离之差。
[0068]
基站和目标位置的关系方程为：
[0069][0070]
根据式(1)可建立(x,y)和距离差之间的关系方程组：
[0071][0072]
其中，r
i1
＝r
i-r1＝ct
i1
＝c(t
i-t1)，i＝2,...,n，c为信号传播速度，ti为从目标位置发出的信号到达第i个从基站的toa时间，t1为从目标位置发出的信号到达主基站的toa时间。对方程组(2)进行化简可得：
[0073][0074]
式(3)中
[0075][0076]
由式(3)最终可解得移动目标的位置坐标。
[0077]
1.2无线定位误差来源分析
[0078]
在非视距情况下测量到的信号相关数据(如tdoa、toa、aoa等)无法正确反映待测目标与基站间的几何关系。在tdoa技术的实际测量中，因为非视距的影响会导致测量的时间值远高于实际值，反映到距离位置上就会有很大的位置差距。
[0079]
若有n个基站参与移动目标的定位，用ri表示移动目标到第i个基站间的测量距离，表示移动目标到第i个基站间的实际距离，移动目标的距离模型可表示为：
[0080][0081]
其中，c为信号传播速度，ti为移动目标发出的信号到第i个基站的传播时间，ni是视距传播条件下服从零均值的高斯分布的系统测量误差，ωi表示非视距传播误差，在只有视距传播时ωi为0。
[0082]
2.改进定位算法
[0083]
2.1最小残差加权算法
[0084]
三维空间下的tdoa定位算法至少需要4个基站进行定位，首先需要从基站总数中选择所有个数等于4的基站组合，然后分别求出每个组合的位置估计，判断出los传播路径。传统的残差加权算法使用的是穷举的方法，但在基站个数较多时，这样的方法会极大的增
加计算复杂度。为了能够有效降低计算的复杂度，本发明通过选择具有最小残差子集的基站组合的方式代替传统的穷举方法来降低计算复杂度。具体算法步骤如下所示。
[0085]
(1)假设进行定位的基站共有m个，tdoa的测量值的数量为m,则m＝m-1个,首先筛选出基站个数为4的tdoa测量值的组合：
[0086][0087]
式中，n表示所需基站数最小组合的个数，tdoa测量值的索引集定义为{sk|k＝1,2,...,m}。
[0088]
(2)目标物的坐标向量的中间值通过使用最小二乘法计算得出，每个分组的残差表示为距离差观测值和使用中间位置计算出预测值之间的差值，利用最小残差法筛选从n个基站组合子集中的每个组合，对每个组合计算找到具有最小的组合并将索引集sk更新为s
min
，设从n个基站组合中筛选的最小组合定义为:
[0089][0090]
基站和移动目标之间的测量距离用ri表示，基站坐标记作xi，s1表示m个基站完成分组的全部集合，表示由m个基站共同估计得到的目标位置坐标。将残差进行归一化处理，可有效消除定位基站数量对权值大小的影响，可定义归一化残差：
[0091][0092]
(3)设补集s
min
中的共有p个元素，将q中的每个元素分别放入补集s
min
中，形成一个新的索引集{sk|i＝1,2,...,n-p}，此时，新的sk中的元素个数为p+1。对于n-p个新组合，再次计算找到具有最小的组合。
[0093]
例如从全站中选择p+1个基站，设从n-p个基站组合中的最小定义为:
[0094][0095][0096]
(4)然后比较和如果说明该基站组合的los传播路径要优于上一个组合，则将此位置估计加入到最终的位置估计集合中，更新s
min
并重复上述步骤，直到不再随着选择不同的基站组合发生变化时，说明当前选择的基站的传播路径为los传播，当索引集大小为m时,结束操作并进入到下一步骤。
[0097]
(5)将之前步骤中所有计算得到的位置估计值根据残差进行加权，得到最终的位置估计结果。
[0098][0099]
其中，v为得到的位置估计的数目。
[0100]
考虑到传统残差加权算法的加权过程是，非特殊情况下，残差值的大小和nlos的误差大小成反比。当los基站数量明显多于nlos基站组合才会产生较大的残差，可以为los基站组合赋予更高的权重。但是，在nlos基站数量明显多于los基站组合时,传统残差加权算法加全过程中直接取残差值的倒数作为权重的效果则很不理想，残差值可能会明显小于nlos误差。针对这种情况，本发明在上面的计算过程中将残差的高次幂作为权重函数，取值n＝2，这样的好处是函数值的变化可以更为明显，如公式(12)所示
[0101][0102]
该最小残差加权算法的原理主要是从定位基站组合中求解最小组合并将冗余基站的信息以补集的方式逐步添加到新的索引集中，利用最小残差准则，逐渐缩小索引集，根据最小残差原则不断重复迭代直至出现最优估计值，最后对符合最小残差准则的位置估计值进行加权，提高了los基站数据的利用率，也降低了传统残差加权算法的计算复杂度。
[0103]
2.2改进遗传蚁群混合算法
[0104]
蚁群算法在解算初期会因为存在信息素匮乏而导致解算速度慢这一问题，而遗传算法存在因为不能有效利用反馈信息从而造成了求精确解效率低的问题。为了解决上面提到的两种算法存在的问题，本发明将遗传算法与改进的蚁群算法相结合，充分利用这两种启发式算法各自所具备的快速性和精确性，弥补两个算法的不足。混合算法的基本思路分为两部分，算法的前期以遗传算法为主，充分利用其为改进的蚁群算法快速产生初始信息素，在保证全局收敛的同时随机分布在解空间中；融合算法的后期采用改进的蚁群算法进行搜索，改进的蚁群算法根据前期产生的初始信息素通过强并行能力从多点出发寻找最优解，利用正反馈的优势提高了在全局中求解最优解的效率。具体设计步骤如下：
[0105]
(1)本发明采用实数编码的方式对编码对象进行编码，便于处理复杂的变量约束条件，无需经常操作编码也可保证在种群数量最大情况下得到最优的结果。
[0106]
(2)本发明采用faure序列在目标搜索空间内随机产生原始种群，设置遗传算法的原始种群个体数量为50，并对种群中的每一个单独个体设立适当的取值范围，遗传算法地运算效率与取值范围有直接关系，恰当的取值可提高算法的求解效率，种群中的个体即表示移动目标的初始猜测位置。
[0107]
(3)选择合适的适应度函数。
[0108]
假设(xi,yi,zi)用来表示移动目标的真实坐标位置，估计的坐标位置记为移动目标的真实坐标到第i个基站的距离记为ri，移动目标的估计坐标位置到第i个基站的距离记为噪声误差ni服从高斯分布，可得真实坐标与估计坐标的距离差值δr为：
[0109][0110]
所以本发明的适应度函数可表示为：
[0111][0112]
(4)遗传算子的选择。
[0113]
本发明选择算子的操作方法确定为轮盘赌选择方法，遗传向下一代的优良个体是根据种群中个体的适应度值占群体适应度值的比例选择出来的。优良个体的选中概率为：
[0114][0115]
本发明设定的交叉概率值为pc＝0.9，交叉算子的操作方式选择两点交叉方法，根据预先设定的交叉概率，随机将两个优良个体中特定的基因片段进行交换，重组得到具有新性状的优良个体。
[0116]
本发明设定的变异概率值为pm＝0.05，变异算子的操作方式选择均匀变异的方法，指定种群中的基因变异点，依据变异概率随机进行替换，变异算子的操作是维持遗传算法中种群多样性的关键，既有利于提升算法的局部搜索能力又避免了混合算法中出现局部最优解。
[0117]
(5)采用精英保留策略，保留现有解中的部分优良个体，无需继续参加遗传过程直接成为下一代种群的成员，这样能有效地提高遗传算法的全局效果。
[0118]
(6)重复计算过程直到系统判定达到终止条件，将现在所选的最优个体作为结果输出。
[0119]
(7)生成信息素，信息素由两部分组成，第一部分是把利用遗传算法得到的最优解坐标作为信息素，第二部分是随机生成的一部分信息素。初始时刻信息素生成规则：
[0120]
τ
′s＝τ
′c+τ
′gꢀꢀꢀ
(16)
[0121]
其中：τ
′c是在蚁群算法路径上随机生成的信息素常量；τ
′g是经遗传算法生成的信息素。
[0122]
(8)路径选择，蚁群会在每个节点处对遗留在每条岔路上的信息素强度做出判断，选择信息素量多的路径，因为选择该路径的蚂蚁越多，所以该路径的信息素量也越多，这样的正反馈机制也是蚁群算法求解效率高的原因。
[0123]
蚂蚁在t(t≠0)时刻的移动方向由各条路径上信息素的累积量决定，而信息素累积量的多少与路径的长度有关，蚂蚁k从位置i到位置j的转移概率的数学模型如下所示：
[0124][0125]
α为信息素启发因子，β为期望启发因子，ρ为信息素的挥发度，信息素残留系数用
(1-ρ)表示且ρ要满足(0≤ρ《1)，m为蚁群中的个体数量，q为蚁群遍历一遍的信息素总量，η
ij
表示路径(i,j)能见度，一般取η
ij
＝1/d
ij
，t时刻路径(i,j)上现有的信息素量用τ
ij
(t)表示，t时刻蚂蚁k从i移动到j的概率为
[0126]
allowed为蚂蚁k待访问的坐标点的集合，s是allowed中的一个坐标点，η
is
表示从i坐标到s坐标的启发程度，τ
ij
(t)表示t时刻时路径(i,j)上现有的信息素量。
[0127]
(9)信息素更新，假设在t时刻蚁群已经完成一次遍历，那t+1时刻信息素应按式(18)-式(19)方式更新。
[0128]
τ
i,j
(t+1)＝(1-ρ)τ
i,j
(t)+δτ
i,j
(t,t+1)
ꢀꢀꢀ
(18)
[0129][0130][0131]
式中的lk表示蚂蚁k留下信息素的路途长度，δτ
ij
代表路径(i,j)上每遍历一次的信息素增量，代表第k只蚂蚁在路径(i,j)上每遍历一次所留的信息素增量，表示编号为k的蚂蚁在时间(t,t+1)的信息素增量，δτ
ij
(t,t+1)表示蚁群总体在时间(t,t+1)遍历一次的信息素增量。
[0132]
改进遗传蚁群混合算法的过程如图3所示。
[0133]
2.3chan-taylor联合算法
[0134]
遗传蚁群混合算法进行全局搜索后得到的是包含信息素最多路径上的节点坐标，也就是chan算法粗略估计出的最优位置解，并未涉及到对最佳路径的使用，只将最优位置解输出作为taylor算法的初始值，思路如下所述。
[0135]
首先将改进后的chan算法得到的估计目标的坐标值作为蚁群算法中所需的节点坐标，遗传算法经过选择、交叉、变异操作生成部分蚁群算法所需的初始信息素；然后再利用蚁群算法进行全局搜索，选出包含信息素最多路径上的节点坐标，即初始最优位置解；最后，将筛选出的最优位置解代入taylor算法，作为taylor算法的初始值进行迭代求解。
[0136]
假设三维空间中的基站坐标为(xi,yi,zi)，基站总数量为n(n≥4)，用(x,y,z)表示移动目标的位置坐标，ri表示移动目标与基站之间的测量距离，通常在众多基站中选择第一个作为主服务基站，其余基站设为从基站，r
i1
就是移动目标到服务基站与从基站的测量距离差。根据式(1)可推导得到下式：
[0137][0138]
上式的x
i1
,y
i1
,z
i1
可分别表示为x
i1
＝x
i-x1，y
i1
＝y
i-y1，z
i1
＝z
i-z1化简得：
[0139][0140]
在式(22)中：
[0141][0142]
现假设x,y,z,r1均是无线性相关的，令z＝[x y z r1]
t
，测量误差向量用ψ表示，式(22)的矩阵形式为：
[0143]
h＝gz0+ψ
ꢀꢀꢀ
(24)
[0144]
其中z对应的真实位置为z0,
[0145][0146]
如果测量误差ψ服从高斯分布，则可运用加权最小二乘求解式(24)：
[0147][0148]
式(26)中的∑-1
为权重矩阵。
[0149]
∑＝e(ψψ
t
)＝c2bqb
ꢀꢀꢀ
(27)
[0150]
其中，∑是测量误差ψ的协方差矩阵，q＝e(nn
t
)是时延误差的协方差矩阵，c为无线电信号的传播速度，在目标位置相距基站特别远的时候可认为趋近于一个常数。假设b≈rai，则可用q来近似代替σ，可得方程变形如下：
[0151][0152]
chan算法得到目标位置的初始值且第一次加权最小二乘结束。
[0153]
在噪声条件较小的情况下：
[0154][0155]
因h0＝g0z0再结合式(24)和式(29)可得：
[0156]
ψ＝δh-δgz0ꢀꢀꢀ
(30)
[0157]
令z＝z0+δz，结合式(27)和式(30)可得δz和z协方差矩阵的表达式：
[0158][0159]
式(31)中的bn＝ψ/c，向量z是一个元素为z1,z2,z3,z4的随机向量，对应z的元素的估计误差分别为e1,e2,e3,e4，那么z1＝x0+e1，z2＝y0+e2，z3＝z0+e3，就是z的元素的表达式，利用向量z中的z1,z2,z3元素分别减去编号为1的基站在三个坐标轴上的x1,y1,z1，接着平方运算已经处理过的元素，就能得出如下线性方程组表达式：
[0160]
ψ
′
＝h
′‑g′z′ꢀꢀꢀ
(32)
[0161]
式中ψ
′
表示新的误差向量，且：
[0162][0163]
对式(32)做最小二乘计算可得：
[0164][0165]
其中∑
′
为ψ
′
的近似协方差矩阵且：
[0166][0167]
最终得到第二次最小加权结果：
[0168][0169]
完成上述工作并把最小残差加权chan算法求解得到位置坐标记作(x0,y0,z0)，在得到taylor算法的初始值后接着推导了三维空间下的taylor算法，具体工作如下。
[0170]
现假设三维空间中的基站数量共有n(n≥4)个，移动目标的位置坐标用(x,y,z)表示，基站坐标则可以表示为(xi,yi,zi)，用(x0,y0,z0)表示taylor算法的初始估计坐标，把主基站设为第一个基站，测量噪声服从零均值高斯分布，真实位置和初始估计位置之间的估计误差为σ
x
,σy,σz。
[0171]
依据tdoa定位的几何模型，函数定义如下：
[0172][0173]
对上式进行化简可得：
[0174]fi
(x,y,z)＝r
i1
ꢀꢀꢀ
(38)
[0175]
真实坐标与初始估计坐标的关系可表示为：
[0176][0177]
利用taylor级数展开法展开式(30)中的(x0,y0,z0)并抛弃二阶以上项可得：
[0178][0179]
其中偏导数项目值为：
[0180][0181]
式(40)可以转化为
[0182][0183]
令则可以得到测量值的误差向量为：
[0184]
ψ＝h-gσ
ꢀꢀꢀ
(44)
[0185]
让误差函数ψ＝0，根据加权最小二乘法，得到如下结果：
[0186]
σ＝(g
t
q-1
g)-1gt
q-1hꢀꢀꢀ
(45)
[0187]
其中q表示测量误差的协方差矩阵，假设测量误差之间是相互独立的，表式每个基站的测量误差的方差，则可得到：
[0188][0189]
taylor级数展开法是迭代类算法的其中一种，估计的初始位置坐标随着下一次迭代变为(x0+σ
x
,y0+σy,z0+σz)，设置门限值μ，当|σ
x
|+|σy|+|σz|≤μ时，结束迭代，反之如果|σ
x
|+|σy|+|σz|》μ则重复上面的推导过程，利用最小二乘法求解估计坐标。也可在最初时预设一个最大迭代次数n，当完成n次后，σ
x
|+|σy|+|σz|≤μ是否成立都强制退出迭代。
[0190]
基于tdoa的最小残差加权chan-taylor联合算法步骤如图4所示。
[0191]
2.4改进定位算法整体步骤
[0192]
首先利用最小残差原则改进筛选基站的组合方式，逐渐缩小索引集，根据最小残差原则不断重复迭代直至出现最优的tdoa测量值组合，把得到的tdoa值代入chan算法并求解，在加权过程中将原本的一阶项变换为残差函数的高阶项。然后将得到的结果作为产生
改进后的遗传蚁群混合算法求解所需的节点，改进遗传蚁群混合算法的任务就是从这些结点中找到信息素分布最多的最优解。最后以最优解作taylor算法的初始值，再经过taylor算法在迭代求解过程中反复比较对误差阈值的设定，如不满足条件，重新迭代求解，若满足条件，则结束迭代，并输出最终目标位置结果。
[0193]
如图1所示，该定位算法的具体步骤包括：
[0194]
第一步，首先利用改进的残差加权chan算法在整个定位范围空间内，对基站进行个数为4的分组，然后将分组后计算得到的粗略坐标估计值记录，最后把估计值结果输出为改进的遗传蚁群算法的节点坐标，表示为pi(xi,yi,zi)。
[0195]
第二步，利用改进的遗传蚁群混合算法对这些节点坐标pi(xi,yi,zi)进行全局搜索，把包含信息素最多的节点作为最优解输出到taylor算法的初始值，此时初始值在nlos环境下已经具有较高的定位精度。
[0196]
第三步，利用taylor算法迭代求解得到最终目标。
[0197]
3.仿真结果与分析
[0198]
本发明对nlos环境下的三维改进的遗传蚁群混合定位算法(rwc-gaa-t算法)进行matlab仿真，先是分析了基站数量对定位精度的影响，然后与几种算法的定位性能做了比较分析。算法参数设置如下：共有7个基站，其坐标分别为(0,0,0)，(350,600,20)，(700,0,30)，(-350,600,30)，(-700,0,40)，(-350,-600,50)，(350,-600,35)，信道模型选用t1p1信道模型的闹市场景，基站半径为400m，遗传算法种群中的个体数量m＝50，交叉概率pc＝0.9，变异概率pm＝0.01，蚁群算法中蚂蚁的数目m＝20，α＝0.8，β＝0.2，ρ＝0.7，两个算法的最大迭代次数均为100次。假设tdoa测量值误差相互独立，在参数不发生变化的情况下运行200次并取其平均值。
[0199]
如图5所示，首先对改进的遗传蚁群混合算法与遗传算法和蚁群算法的收敛性和最优值精度做了比较。从图中可以看出遗传算法的开始收敛速度最快，改进后的算法略慢于遗传算法，蚁群算法的收敛速度最慢，这是因为改进算法在开始阶段继承了遗传算法全局快速收敛的特点。改进算法有着最高的最优解精度，其次是蚁群算法，遗传算法最低，这是因为改进后的算法可看作有较好初始值的蚁群算法，所以最优解精度可以更高。
[0200]
结果如图6所示，rwc-gaa-t算法的定位精度会随着基站数量的增多而呈上升趋势，当有7个基站参与定位时，该算法的定位精度相比只有4个基站参与定位时有了较大幅度的提高。可以看出较多的冗余基站能够对该算法的定位精度起到直接的帮助，这是因为随着基站数量的增加产生了更多可加以利用的冗余tdoa测量数据，在只有4个基站即可完成定位的情况下充分利用这些冗余基站的测量数据，该算法就能有更多不同的基站分组方案，避免了测量数据较少且其中存在较大的nlos误差干扰所导致的定位误差较大的问题，从而使定位精度能够得到提高。
[0201]
如图7所示，可更直观地看出该算法的定位性能随着基站数量的增加有所提高，基站数量越多，分布在较小均方根误差的可能性也越大。
[0202]
如图8所示，本发明所提出的rwc-gaa-t算法在基本参数一致且在满足最低定位基站条件下明显优于其他定位算法，最接近crlb下界。rwc-t算法的定位性能仅次于rwc-gaa-t算法，定位性能最差的是chan算法，因为该算法受非视距误差的影响较大。随着参与定位的基站数量不断增加，所有算法的定位精度都在提高，均方根误差在逐渐减小。
[0203]
如图9所示，rwc-gaa-t算法的定位性能最好，最接近crlb下界，rwc-t算法次之，说明加入改进的遗传蚁群混合算法改善了原有算法在nlos环境下定位下降的问题。随着基站数量的增加，在nlos环境中taylor算法的定位性能逐渐优于chan算法和rwgh算法。所有算法的均方根误差均比在los环境中有所增大，说明nlos传播的误差干扰对定位性能还是有很大影响的。但也可看出rwc-gaa-t算法的精度始终高于其他算法，这是因为该算法做了以下改变，首先利用基于最小残差加权的chan算法对现有基站进行分组，并根据nlos误差的干扰情况赋予不同的权重降低了nlos误差，最后得到的坐标生成蚁群算法中所需的节点位置。接着利用改进后的遗传蚁群算法进行全局搜索，把最优位置坐标作为taylor算法的初始坐标，经过不断迭代过程得到目标估计值。该算法经过两次降低nlos误差的操作，很大程度降低了nlos的干扰。虽然所有算法的均方根误差值都会随着测距误差的增大而出现上涨，但可看出rwc-gaa-t算法增长幅度较为平缓，说明该算法抗干扰能力较强，定位性能较为稳定。
[0204]
如图10所示，rwc-gaa-t算法的定位性能最佳，在只有4个基站参与定位时，有超过80％的均方根误差小于25m，chan算法的定位性能最差，有80％的均方根误差小于38m。随着基站数量的增加，所有算法的性能都有所提升，当基站数量增加到7个时，从图10(d)中可看出rwc-gaa-t算法有超过80％的均方根误差小于21m，可以在在nlos环境中取得较好的定位效果。从图中跟直观地看出改进算法相比其余算法在nlos环境中的优势，证明了其良好的定位性能。
[0205]
如图11所示，所有算法的均方根误差都随着基站半径的增加而增大，其中chan算法的增长幅度最大，rwgh算法次之，rwchan-taylor算法和rwc-gaa-t算法的均方根误差增长幅度较小，且rwc-gaa-t算法的均方根误差最小。随着基站半径的增大，非视距误差的干扰也越来越大，相比其他算法，rwc-gaa-t算法的优势也越加明显。
[0206]
图12中提升百分比的计算方法如下：
[0207][0208]
在图12中，为了更直观地看出本发明所提算法较其他算法的性能变化，同样把chan算法作为比较的标准参考算法，比较了rwchan-taylor算法和rwc-gaa-t算法相较传统chan算法的性能提升情况。从图中可看出改进后的算法有了较大幅度的提升，rwc-gaa-t算法大约比rwchan-taylor算法提高了20％。说明在nlos环境下，rwc-gaa-t算法对nlos误差起到了有效抑制的作用，适合解决在nlos环境下的定位问题。
[0209]
以上对本技术实施例所提供的一种基于选择tdoa的改进遗传蚁群混合定位方法，进行了详细介绍。以上实施例的说明只是用于帮助理解本技术的方法及其核心思想；同时，对于本领域的一般技术人员，依据本技术的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本技术的限制。

技术特征：
1.一种基于选择tdoa的改进遗传蚁群混合定位方法，其特征在于，所述方法的步骤包括：s1、找到具有最小残差子集的基站组合作为定位所需的参考点；s2、将参考点的tdoa值代入chan算法进行求解，得到粗略坐标估计结果；s3、将粗略坐标估计结果作为遗传蚁群算法的节点坐标进行全局搜索，把包含信息素最多的节点作为最优解；s4、将最优解作为初始值代入taylor算法进行迭代求解，得到最终的目标定位结果。2.根据权利要求1所述的基于选择tdoa的改进遗传蚁群混合定位方法，其特征在于，步骤s1的内容包括：s11、从基站总集中选择出所有个数为m的基站组合；m为不小于4的正整数；s12、计算各基站组合的残差，并利用最小残差法进行筛选，将具有最小残差子集的基站组合作为定位所需的参考点；所述残差定义为距离差观测值和使用中间位置计算出预测值之间的差值。3.根据权利要求1所述的基于选择tdoa的改进遗传蚁群混合定位方法，其特征在于，步骤s3中遗传蚁群算法对节点坐标进行全局搜索的内容包括：s31、以遗传算法为主对节点坐标进行处理，快速产生初始的信息素，在保证全局收敛的同时随机分布在解空间中；s32、采用改进的蚁群算法进行搜索：根据信息素，从多点出发寻找最优解，从而利用正反馈的优势提高在全局中求解最优解的效率。4.根据权利要求3所述的基于选择tdoa的改进遗传蚁群混合定位方法，其特征在于，步骤s31的具体内容包括：采用实数编码的方式对编码对象进行编码，以便于处理复杂的变量约束条件；采用faure序列在目标搜索空间内随机产生原始种群，设置原始种群个体的数量，并确定种群中每个单独个体的取值范围；确定适应度函数；确定遗传算子；采用精英保留策略保留现有解中的部分优良个体，使其直接成为下一代种群的成员；重复进行遗传算法的计算过程，直到满足预设的终止条件，然后将现在所选的最优个体作为输出结果；根据输出结果生成信息素。5.根据权利要求4所述的基于选择tdoa的改进遗传蚁群混合定位方法，其特征在于，所述信息素包括：最优个体的坐标数据和随机生成的数据。6.根据权利要求4所述的基于选择tdoa的改进遗传蚁群混合定位方法，其特征在于，所述适应度函数为：其中，r
i
表示移动目标的真实坐标到第i个基站的距离，表示移动目标的估计坐标位置到第i个基站的距离，n
i
表示服从高斯分布的噪声误差，m
为基站的数量。7.根据权利要求4所述的基于选择tdoa的改进遗传蚁群混合定位方法，其特征在于，确定遗传算子时，交叉概率值为0.9，变异概率值为0.05。8.根据权利要求4所述的基于选择tdoa的改进遗传蚁群混合定位方法，其特征在于，步骤s32的具体内容包括：按照搜索规则进行搜索，并以迁移概率进行迁移；t时刻蚂蚁k从位置i移动到位置j的迁移概率p的表达式为：其中，α为信息素启发因子，β为期望启发因子，t为时间，η
ij
表示路径(i,j)能见度，τ
ij
(t)表示t时刻路径(i,j)上现有的信息素量；allowed为蚂蚁k待访问的坐标点的集合，s是allowed中的一个坐标点，η
is
表示从i坐标到s坐标的启发程度；信息素更新：更新路径信息素强度和信息素增量。9.根据权利要求8所述的基于选择tdoa的改进遗传蚁群混合定位方法，其特征在于，第k只蚂蚁在路径(i,j)上每遍历一次所留的信息素增量为：式中，l
k
表示蚂蚁k留下信息素的路途长度，q为蚁群遍历一遍的信息素总量；t+1时刻路径(i,j)上现有的信息素强度为：τ
i,j
(t+1)＝(1-ρ)τ
i,j
(t)+δτ
i,j
(t,t+1)，式中，τ
ij
(t)表示t时刻路径(i,j)上现有的信息素量，(1-ρ)表示信息素残留系数，δτ
ij
(t,t+1)表示蚁群总体在时间(t,t+1)遍历一次的信息素增量；(t,t+1)表示蚁群总体在时间(t,t+1)遍历一次的信息素增量；表示编号为k的蚂蚁在时间(t,t+1)的信息素增量。10.一种基于选择tdoa的改进遗传蚁群混合定位装置，包括存储器、处理器以及存储在所述存储器中并能在所述处理器上运行的计算机程序，其特征在于：所述处理器执行所述计算机程序时实现如权利要求1-9任一所述方法的步骤。

技术总结
本发明涉及一种基于选择TDOA的改进遗传蚁群混合定位方法及装置，属于无线定位技术领域，能够提高在求解空间中的求解效率和收敛性，改善传统TDOA算法在非视距下的定位精度不佳的问题；该方法包括：S1、找到具有最小残差子集的基站组合作为定位所需的参考点；S2、将参考点的TDOA值代入Chan算法进行求解，得到粗略坐标估计结果；S3、将粗略坐标估计结果作为遗传蚁群算法的节点坐标进行全局搜索，把包含信息素最多的节点作为最优解；S4、将最优解作为初始值代入Taylor算法进行迭代求解，得到最终的目标定位结果。的目标定位结果。的目标定位结果。


技术研发人员：刘洋 韩宇飞 雷雪梅 刘中艳 陈泽
受保护的技术使用者：内蒙古大学
技术研发日：2022.07.21
技术公布日：2022/11/1