一种基于遗传神经网络的煤矿井下定位算法

逄明祥，王善培，李 乾，程学珍

（1.山东科技大学a.电子信息工程学院；b.电气与自动化工程学院，山东青岛 266590；2.中车青岛四方车辆研究所有限公司，山东青岛 266011）

0 引言

煤炭作为我国的第一大能源，对于国民生产和经济具有重要意义。近年来煤矿生产安全事故频发，引起全社会的高度关注［1-3］。提高我国煤矿的信息化程度，成为保障煤矿安全生产的重要手段，其中煤矿井下人员定位系统是煤矿信息化建设的重要组成部分，煤矿井下定位算法［4-6］的研究也成为重要课题。

煤矿井下定位算法大致可分为基于测距的和非测距的算法两大类［7-9］。非测距定位算法主要是依据网络的连通性来实现对待测点的定位，如质心算法、DVHop、APIT 等常见算法［10-14］；测距定位算法主要是通过测量信标节点与待测未知节点之间的距离或角度来实现定位，如TOA、TDOA、RSSI 等算法。TOA 测距定位算法主要有：基于改进均值滤波和参数拟合的矿井TOA几何定位方法［15］、基于WiFi 和计时误差抑制的TOA煤矿井下目标定位算法［16］、基于WiFi 信号二次扩频的矿井TOA测距方法［17］和基于测距值二次重构的弯曲巷道目标定位方法［18］，该类定位方法很难实现目标点与基站之间的时间同步［19］，造成测距误差。在复杂的井下环境中，NLOS 是造成无线定位误差的主要原因［20］。本文提出的利用遗传神经网络来拟合TDOA测量值和目标点坐标值之间的映射关系，依靠神经网络强大的非线性映射能力来减小TDOA测量值中包含的NLOS 误差所造成的定位误差，基于Chan-Taylor算法，将遗传神经网络算法与Taylor 算法相结合，进一步提高定位精度。

1 基于遗传神经网络的超宽带井下定位算法

1.1 遗传算法的数学模型

遗传算法的具体实施过程包括编码、产生初始群体、计算个体适应度、复制、交换、突变、反复迭代、种植等操作。设G 为遗传算法迭代次数。需要确定一组初始权值和阈值的编码方式以及字符串长度L，这里采用实数编码方式。对输入的种群进行初始化，确定群体规模M。以此计算群体中各个个体的适应度。在室内定位时，输入训练样本，以输出结果与样本期望值的误差平方和倒数作为适应度，误差越小，适应度越大，据此评价权值和阈值的优劣。适应度函数为：

式中：N为输出层神经元个数；Xpj为第p个输入样本在第j个神经元的实际值，Opj则为第p个输入样本在第j个神经元的输出值。

通过式（1）计算出适应度值，根据计算结果依次执行复制、交换、突变等操作。

步骤1复制操作。设复制概率为Pt，j为复制次数，根据适应度的大小，选择个体进行复制，并加入下一代新群体中，直到复制个体数达到Pt·M 时停止。同时删除适应度较低的个体，将剩余个体加入下一代群体之中，并保持群体规模为M不变。

步骤2交换操作。设交换概率为Pe，根据适应度选择2 个个体进行交换操作，然后将交换后的2 个个体代替原个体插入群体之中，交换次数满足Pe·M时停止。

步骤3突变操作。突变操作针对的是个体编码中的字符，设突变概率为Pm，则发生突变的字符数量为Pm·L·M。经过以上这3 步操作产生新一代群体之后，重新计算个体适应度，重复上述操作，不断优化初始确定的连接权值和阈值，直到训练的样本误差满足定位要求时停止迭代。遗传算法优化BP 神经网络的具体流程如图1 所示。

图1 遗传神经网络的工作流程图

1.2 BP神经网络的定位模型

神经网络种类繁多，本文以BP 神经网络作为基础。BP神经网络虽然应用比较广泛，但仍然存在许多不足，主要有收敛速度慢，网络极易陷入局部极值点，以及对于初始权值、阈值的选择缺乏依据等［21-23］。为克服BP神经网络不足，可利用遗传算法优化BP神经网络的初始权值和阈值，来提高神经网络算法的性能。遗传算法［24］是一种以优化变量的遗传编码为运算和搜索对象的算法，它根据适应度信息来指导搜索，具有很强的全局优化能力。

神经网络主要由输入层、隐含层、输出层组成，在输入层输入的是带有非视距误差的TDOA 测量值，输出层输出的是目标点的坐标值。确定神经网络模型的难点主要在于隐含层的层数和隐含层神经元数量以及各层激励函数和训练函数的选择，目前并没有具体理论上的指导。结合仿真经验考虑，一层隐含层的神经网络就能够很好地满足算法需求，并且一层隐含层的网络结构比较简单，训练时间较短，比较容易实现，所以隐含层数确定为1。对于隐含层神经元数量的确定也比较棘手，通过大量的实验，人们总结出了估算隐含层神经元数量的方法［25］：

式中：INnum、Onum分别为输入层和输出层的节点个数；Hnum为隐含层神经元数量；n 为1～10 之间的任意值。其中对于隐含层的激励函数，采用Sigmoid 函数f1（x）tan h（x），对于输出层激励函数，采用线性函数f2（x）=kx。

在本模型的仿真中，输入层为各定位基站与目标点的TDOA测量值，本文设定共7 个基站，所以输入层节点为6 个，输出层为目标点坐标值，根据仿真分析和上述公式，设定隐含层神经元个数为17 个，整个神经网络为6：17：2 的结构。图2 为煤矿井下非视距环境中的神经网络定位模型。

图2 用于井下定位的BP神经网络模型

1.3 基于TDOA的Taylor算法模型

Taylor算法［26］是一种递归算法，其数学原理是在初始值处对非线性方程组进行泰勒级数展开转化为线性方程［27］，利用加权最小二乘法估计目标节点的位置，使用新的估计值作为初始值重复以上步骤，直到得到满足所需误差精度的最终结果。

假定在二维平面上任意的分布着M 个定位基站（base station，BS），设第i 个基站BSi位置为（xi，yi），其中BS1为参考基站，待定位点MS 坐标为（x，y），和BSi之间的距离为ri，第i个定位基站和参考基站之间的测量距离差为ri，1，信号传输速度为c。当定位过程存在测距误差时：

式中：Ri，1为目标节点与各基站的TDOA真实值；ni，1为目标节点与各基站的TDOA测距误差。假设目标节点真实坐标为（^x，^y），估计坐标的误差表示为（σx，σy），那么估计坐标（x，y）表示为：

将式（4）在初始点（x0，y0）处进行一阶泰勒展开得：

式（7）的矩阵式为

式中：

对式（8）作加权最小二乘估计得：

式中，Q 为TDOA 测量误差的协方差矩阵。假设误差门限为ε，如果迭代运算之后的结果与初值满足：

此时的结果就是要求的目标节点的估计坐标。

Taylor需要一个比较精确的初始值才能够保证算法得收敛，但在目标节点未知的情况下往往很难提供这个初始位置，这种情况下Taylor 算法不仅计算量比较大，而且不能保证收敛。将遗传神经网络定位算法结合使用，将遗传神经网络的输出作为Taylor 算法的初始坐标进行迭代计算，来获取更高的定位精度。

2 仿真与分析

为了验证遗传神经网络定位算法（GA-BP）的定位性能，采用Matlab 软件进行算法仿真，并与几种传统的室内定位算法进行比较。假设一段煤矿井下巷道长为40 m，宽为5 m，巷道中设置7 个基站。其中参考基站BS0位于巷道中央，坐标设置为（0，0），单位为cm，则定位基站坐标按照蜂窝式结构分别设置为：BS1（1 000，250），BS2（2 000，0），BS3（1 000，-250），BS4（-1 000，-250），BS5（-2 000，0），BS6（-1 000，250）。定位目标节点的位置则是在巷道范围内随机产生。在井下环境中NLOS引起的测距误差一般服从高斯、Delta 或者均匀分布，在仿真中假设其服从（0，σ2）高斯分布。

在巷道范围的环境下随机获取2 000 个目标点坐标，分别计算6 个定位基站关于目标点的TDOA 数据作为训练样本，代入遗传神经网络中，结合目标点真实坐标对其进行训练。对于遗传算法部分，设定遗传算法的群体规模为50，最大遗传代数为10，变异率为0.001，交叉率为0.6。

通过测定若干组随机目标节点在NLOS 环境下的TDOA数据，输入训练好的遗传神经网络模型中来获得定位结果。

图3 是遗传神经网络定位算法与传统的Chan 算法在σ取值为0.1 情况下的定位性能比较，由1 000次独立位置估计得到。Chan 算法是简单实用的定位算法，在视距环境下具有比较好的定位性能。此时NLOS导致的TDOA 测量误差非常小，近似于视距传播。图中横坐标为定位误差，纵坐标为累积分布函数（Cumulative distribution function，CDF）。累积分布函数是指定位误差在某个设定好的阈值之内的定位次数占总的定位次数的比例，可直观看出定位系统在某种精度下的定位成功率。由图可见，在测距误差较小的情况下，Chan算法的定位性能明显好于GA-BP算法。

图3 σ为0.1时的定位性能

当TDOA测距误差的增大，算法的定位性能会受到不同程度的影响。图4 是在σ的取值为0.7 情况下的两种算法的定位性能比较，此时的Chan 算法性能低于遗传神经网络算法，说明在较高的TDOA 测量误差的环境下，Chan算法的定位性能会有明显下降。

图4 σ为0.7时的定位精度

图5 是Chan算法和GA-BP算法随着测距误差的增大其定位性能的变化情况。其中横坐标为a，纵坐标为定位算法的均方根误差。为了减小计算量，图中均方根误差（RMSE）值由100 次独立位置估计计算获得。由图5 可见，Chan算法在TDOA测量误差比较小的情况下具有较高的定位精度，但是随着TDOA 测量误差的提高，其定位精度迅速下降，证明在非视距传播条件下，Chan算法定位性能很差。而遗传神经网络算法的定位性能明显更好，即使是在比较大的TDOA 测量误差的情况下，其定位精度的变化也比较平稳，证明了遗传神经网络起到了减小TDOA 测量误差的作用，能够很好地拟好TDOA测量数据与目标节点坐标之间的映射关系。

图5 Chan算法与GA-BP算法的RMSE曲线图

对Chan-Taylor 协同算法进行仿真，并与Chan 算法、遗传神经网络算法进行比较。Chan-Taylor 协同算法是结合Chan算法和Taylor 算法二者优点的一种定位算法，该算法将Chan 算法的结果作为初始值代入Taylor算法来获得更高的定位精度，如图6 所示。

图6 4种算法的RMSE曲线对比图

由图可见，Chan-Taylor 算法相较于Chan 算法定位性能确实有所提升，尤其是在TDOA 测量误差很小的情况下，其定位精度非常高，但是随着TDOA测量误差的提高，其整体变化趋势与Chan 算法类似，在测量误差较高的情况下遗传神经网络算法结合Taylor算法能够获得更好的定位精度。

参考Chan-Taylor协同算法，将遗传神经网络算法与Taylor算法相结合（GA-BP-Taylor）达到提高定位精度的目的。最终4 种算法的均方根误差（RMSE）值见表1。由表1 可见，遗传神经网络结合Taylor 算法确实能够获得更好的定位效果。

表1 4 种算法的RMSE值cm

3 结语

本文提出了一种基于遗传神经网络和Taylor算法相结合的井下定位算法。该算法利用遗传算法优化神经网络，克服了其易陷入局部最优的缺点，依靠神经网络逼近任意非线性映射的能力和较快的学习特性来拟合TDOA测量值和目标点坐标值之间的映射关系，减小非视距传播造成的TDOA 测量误差，有效地克服诸如Chan算法之类的常用定位算法易受NLOS 影响的缺陷。仿真结果表明，该算法对于非视距环境下的测距误差具有明显的抑制性能，与传统定位算法相比具有更高的定位精度和更好的稳定性。