基于入侵杂草算法的水下目标TDOA 定位方法*

2021-08-07林云航张贞凯

火力与指挥控制 2021年7期

林云航，张贞凯，江峰

（江苏科技大学电子信息学院，江苏镇江 212003）

0 引言

水下无线传感器网络（Underwater Wireless Sensor Network，UWSN）是部署在水下一定数量的传感器构成的网络，是当今一个备受关注的研究热点［1］；在传感器网络中，节点位置信息的获取与处理就变得尤为重要［2］；作为传感器网络的主要支撑技术，定位技术的重要性就显现出来了。当前主要有两种定位方式：距离相关与距离无关［3］。距离相关的定位方法包括两个步骤：测距与定位算法。基于测距的方法一般有利用到达时间差（Time Difference of Arrival，TDOA）［4-6］和利用到达时间（Time of Arrival，TOA）［7-8］等，定位方法则包含三边测量法和最小二乘法等。距离无关的定位方法也包含两个步骤：估计距离与定位算法。主要使用的是Distance Vector-Hop（DV-HOP）［9-10］算法与质心算法［11］。两类方法各有优缺点，可以根据条件来进行选择。

本文基于TDOA 来实现水下目标的定位，文献［12］提出了基于泰勒级数展开的TDOA 定位方法，泰勒算法需要一个与实际位置接近的初值才能够实现算法的收敛。文献［13］针对定位问题提出了Chan 算法，该算法在测量误差满足高斯分布时能够达到最好效果，但是实际误差并不满足高斯分布，导致定位效果性能显著下降。文献［14］提出了一种两步加权最小二乘算法，先引入中间变量建立一组关于TDOA 的伪线性方程，通过第1 次加权最小二乘算法，求出中间变量和未知节点的粗略解，随后利用中间变量与目标之间的关系进行第2 次加权最小二乘算法来进一步提高精度。考虑到这种算法的计算量大、过程复杂，可以选择利用优化算法来提高求解的效率。

本文提出了一种基于入侵杂草优化（Invasive Weeds Optimization，IWO）算法与加权最小二乘算法协同定位的方法，利用IWO 算法求出初值，从而可以得到中间变量；然后将初值与中间变量引入一个距离干扰参数，求得粗略解；再通过估计相关的误差取得精确解。

1 算法原理

1.1 基于TDOA 的水下定位算法

TDOA 是通过测量未知节点到两个已知坐标传感器之间的时间差来确定未知节点的位置。假设在一个三维空间中，有M 个传感器节点随机分布，未知节点的坐标为u=［x，y，z］T，第i 个传感器节点的实际坐标为si=［xi，yi，zi］T，则未知节点到传感器节点的距离为：

将式（3）移项可得：R-Ri+R1=N，理论上，R-Ri+R1应该是为零矩阵。但是由于噪声的存在，它的值不会等于零，因此，R-Ri+R1的最优解就是它的最小值。利用范数的形式来求取最小值，同时把范数平方，可以保证范数的值在0 的两边都可以收敛。所以未知节点的估计坐标可以这样来求：

式（4）如果采用解析法来求解的话，过程十分复杂，因此，在本文采用入侵杂草算法来求解未知节点的估计值。

图1 是水下节点定位时示意图，可以通过以上方法求出水下未知节点的估计坐标。

图1 水下节点示意图

1.2 入侵杂草算法

入侵杂草算法［15］是在2006 年受杂草繁殖的启发提出的一种优化算法，通过效仿杂草繁殖时，种子在空间中扩散、生长和繁殖的过程演变而来的。与其他算法相比较，该算法在种子扩散的过程中满足正态分布，每一株父代杂草均能繁衍出下一代种子。杂草的适应度越强，就能繁衍出越多的子代杂草，在整个算法的过程中既可以保全杂草的多样性，又可以使其具备一定的竞争能力。该算法的基本流程是：

1）根据要解决的问题，对种群X=（X1，X2，…，Xpmin）进行初始化，其中，确定初始种群数pmin，并设定最大种群数pmax。

2）计算每个杂草的适应度值，种子的数量是由其父代杂草的适应度数值所决定，它们之间呈一个线性关系。其线性关系如下所示：

式（5）中，weedt代表种子数量，f 代表杂草的适应度，fmax与fmin则是最大与最小的适应值，Smax与Smin分别为可产生的最大与最小种子数量。

3）种子依照正态分布的规律扩散在父代杂草产生的周围，通过公式可表示为：

式（6）中，σ 是标准差。根据迭代的过程，σ 一直在变化，其变化规律可以表现为：

式（7）中，σmin、σmax分别表示最终标准差与初始标准差的数值，itermax、iter 分别表示最大迭代次数与当前迭代次数，β 代表非线性调节因子，一般将它设置为3。

4）若当前的种群数量比最大种群数pmax还要大时，算法就会开启竞争机制，将所有的杂草按照适应度的数值从大到小来进行排序，将适应度好的前pmax个杂草保留，其余杂草则淘汰，然后进入下一次迭代。

5）判断是否迭代次数是否大于最大迭代次数itermax。若是，那么结束循环输出最优解；若否，则返回2）继续循环。

2 IWO 算法与加权最小二乘算法协同定位

本节中首先使用IWO 算法求出TDOA 定位的初值。式（4）使用解析法时计算量太过巨大，因此，选用IWO 算法来进行求解。为了求解式（4），将适应度函数设置为：式中，f 为杂草的适应度函数，R-Ri+R1表示定位误差。公式表示当适应度函数f 取得最优值时，此时的坐标就是未知节点的初值uiwo。

第1 阶段：利用改进的加权最小二乘算法和初值uiwo来求未知节点的粗略解。

将式（10）以加权最小二乘算法的伪线性模型来表示：

通过加权最小二乘算法，可得到第1 阶段未知节点的粗略解：式中，W=（BQBT）-1，W 的值跟未知节点的坐标有关；利用uiwo来确定中间变量r1和ri的数值并求出W的值。Q 为TDOA 测量值误差的协方差矩阵。

第2 阶段：得到了粗略解u*之后，要进一步来细化它。设：

其中，Δu 是估计的误差项。

将式（13）带入到r1中，可得：r1=||u-s1||=||u*-Δu-s1||。当估计误差较小时，即||Δu||<<||u-s1||，r1进行一阶泰勒级数展开可变式为：

考虑所有的传感器，上式可表示为：

式（17）的加权最小二乘解为：

其中，W=（BQBT）-1，可以利用第1 阶段的粗略解求得。

在估计误差求出来之后，便可以求出未知节点的精确解：

3 克拉美罗下界

为了验证所提算法的性能，对TDOA 定位的克拉美罗下界（Cramer-Rao Lower Bound，CRLB）进行分析。

将误差估计项Δu 表示为：

其中，δ 是估计误差。

将式（13）和式（20）代入式（19），得到u^-u=-δ，可知最终解的期望偏差为-E（δ）。将式（17）进行移项变为：h2=BN+AΔu，再将其代入到式（18）可以得到δ 的表达式：

其中，因为矩阵A 和N 均包含噪声项，所以期望偏差-E（δ）比较困难。但是在噪声小的条件下，A 中的测量值的噪声可以忽略。

此时，式（21）表达成误差项δ 与关于噪声N的线性等式，由于N 服从零均值的高斯噪声分布，从而-E（δ）=0，即E（u^-u）=0。因此，所提算法在噪声小的情况下，可以求出未知节点坐标的无偏估计值。

CRLB 是无偏估计量的估计方差的下限，即无偏估计量的方差只能逼近克拉美罗界，而不可能小于它。由文献［14，16］可知：对于TDOA 定位而言，它的CRLB 矩阵可以写成：

因此，TDOA 定位的克拉美罗下界可以表示为：

4 仿真结果及分析

本节中为了验证本方法在水下定位的效果，使用Matlab 平台来对算法进行仿真实验。假设在水下区域中布置一个传感器网络，总共5 个传感器。第1个传感器为参考传感器，另外4 个是坐标随机的传感器。实验过程是使用本方法，在不同坐标的传感器和标准差不同的噪声下，求出未知节点的坐标。假设TDOA 测量值误差之间是相互独立的，则测量值误差的协方差矩阵为Q=delta2IM-1×M-1，其中，delta2是测量噪声的方差，I 是对角线元素为1，其余元素为0.5 的矩阵，下标表示它的维度。所有仿真均采用蒙特卡罗随机实验，以均方误差（MSE）、偏差（BIAS）和累积分布函数（CDF）为评价指标，并求出在不同的噪声中的理论最小方差克拉美罗下界（CRLB）。相同条件下所提算法与传统的Chan 算法（图注为TDOA-CHAN）、未进行误差估计的IWO 算法（图注为TDOA-IWO）进行比较。

MSE 与BIAS 的计算公式如下所示：

其中，L 是蒙特卡罗实验次数，没有特定的说明，L=100。

累积分布函数是在某一个门限误差下，算法定位误差低于门限误差的次数占仿真总次数的比例。CDF 在图中上升的趋势越快，表示低于门限误差的次数越多。

入侵杂草算法初始化参数设置为：初始种群数pmin=5，最大杂草个数pmax=10，最大迭代次数itermax=350，初始标准差σmax=30，最终标准差σmin=0.005，最大种子数Smax=20 和最小种子数Smin=0。

仿真1 5 个传感器坐标中，参考传感器坐标为［70，30，15］T，4 个随机的传感器坐标分别为［30，0，50］T，［0，40，80］T，［-30，0，50］T和［0，-40，20］T，未知节点的真实坐标是［-150，100，30］T，单位均为m。

图2 为3 种算法以及CRLB 之间的均方误差比较图，图3 为3 种算法之间的偏差比较图，研究的都是算法精确度。仿真结果所示：在噪声较小时，算法之间的性能还是比较接近的。但在噪声变大之后，所提算法的定位均方误差与偏差要明显小于其余两种算法，即精度会更准确一些。

图2 均方误差比较结果

图3 偏差比较结果

图4 是3 种算法在噪声标准差为3 时的累积分布函数，横坐标表示定位误差平方的对数形式。仿真结果表明，在相同的噪声中，所提算法的上升趋势要明显优于其余两种，也就是所提算法的性能要好于其余两种。

图4 累积分布函数对比结果

仿真2 5 个传感器坐标中，参考传感器坐标为［70，30，15］T，4 个随机的传感器坐标分别为［130，0，50］T，［0，400，180］T，［-130，0，500］T和［0，-400，80］T，未知节点的真实坐标是［-150，100，30］T，单位均为m。

图5 为3 种算法以及CRLB 之间的均方误差比较图，图6 为3 种算法之间的偏差比较图，研究的都是算法精确度。仿真结果所示：所提算法的均方误差与偏差在相同条件之下都更小，说明所提算法精度更高。

图5 均方误差比较结果

图6 偏差比较结果

图7 是3 种算法在噪声标准差为3 时的累积分布函数。仿真结果表明，在相同的噪声中，所提算法的误差低于门限误差的次数要少于其余两种算法，可以看出，所提算法的性能优于另外两种算法。

图7 累积分布函数对比结果

仿真1 和仿真2 的结果均表明，所提算法要比其余两种算法定位更为精确，得出的估计值更接近于实际位置。从图中可以看出，TDOA-IWO 的精度要优于TDOA-CHAN，这是因为Chan 算法在进行最小二乘算法时会引入误差的二次项，而TDOA-IWO 是直接对定位误差的范数来进行搜索。当误差较小时，两算法的性能差别不大，但是误差变大时，TDOA-CHAN 二次项不能忽略，而TDOA-IWO 没有受到二次项误差的影响，因此，TDOA-IWO 定位效果好于TDOA-CHAN。所提算法是在TDOA-IWO 的基础上来进行误差项估计，即所提算法的解会比TDOA-IWO 的解精度更高，也可以看出，噪声较大时，所提算法相比于其余两种算法要更加接近CRLB，所提算法能更好地适应噪声较大的环境。