基于遗传-拟牛顿混合算法的地下震源定位

0 引言

随着现代信号处理技术、微电子技术、无线通信技术、计算机网络技术的飞速发展，人们对无线移动通信的需求逐渐加强。传统的基于中心控制、依赖预置网络基础设施的无线移动通信网络，如蜂窝移动通信网络、无线局域网商用无线网络等，已远远不能满足人们在某些特殊场合（如地下探测、灾后救援、野外巡查等）的应用需求。在这种背景下，无线传感器网络应运而生。时钟同步是无线自组织网络重要的基础支撑技术，是完成数据融合、多址接入、协作感知、定位技术、能量管理等功能的必要前提。

在无线传感器网络定位中，第一个重要的环节是各个节点需要进行时钟同步，其中需要精确的时间戳来确保准确的定位。最近，几个传感器网络的时钟同步算法已被设计成能够进行时钟同步，且效果非常好。目前已有时钟同步算法包括：参考广播同步^[1]、梯度时间同步协议^[2]等。文献[3]主要研究了脉冲耦合在生物振子方面的应用；文献[4]对一类无线传感器网络的时钟同步进行了讨论，并分析同步的鲁棒性；文献[5]讨论了脉冲耦合无线传感器网络时钟同步的可扩展性；文献[6]主要提出了优化的相响应函数，该响应函数能快速实现脉冲耦合。

第二个重要的环节是定位。通常，最简单的无线传感器网络定位方法就是为各个节点装载全球定位系统（GPS）接收器，用以确定节点位置。但是，由于成本，各个节点能量及GPS对环境有一定要求等诸多条件的限制，实际中每个节点不能都装备GPS接收器，即使都装备GPS，也不能精确定位到毫米级别。所以本文使用到达时间差（Time Difference of Arrival，TDOA）的方法对地下未知震源进行定位。传统的TDOA定位方法是：两种不同传播速度的无线信号在发射节点和接收节点之间进行传播，测得到达时间差，随之计算信号点到接收点的距离。常见的无线传感器网络测距方法包括：到达时间^[7]（Time of Arrival，TOA）测距，该方法要求硬件之间有较高的时间同步；到达角度^[8]（Angle of Arrival，AOA）测距，该方法要求传感器节点拥有测量角度的功能等。

随着传感器网络和定位技术的快速发展，人们对定位方法的研究越来越多，定位精度的要求也较高。迄今为止，在陆面上技术发展已比较成熟^[9-10]，但是对瓦斯定位，及对未知震源的定位技术还不够成熟，所以本文提出了一种基于遗传-拟牛顿混合算法的远场地下震源定位方法。本文提出一种新颖的TDOA定位方法，即利用震源发出的脉冲信号到不同传感器网络节点的到达时间差来实现对地下震源的定位。

本文主要研究了无线传感器网络的震源定位系统，首先使用脉冲耦合时钟同步算法，同步所有节点时钟；然后，测得震源到4个传感器节点的到达时间，使用MATLAB仿真软件计算出震源到各个节点的TDOA，建立相应目标函数；最后，利用遗传算法在整个求解空间内进行快速搜索，得到精确解的近似值后将其作为拟牛顿算法的初始值，快速收敛到精确的震源坐标。实验结果表明，把拟牛顿算法和遗传-拟牛顿混合算法的寻优结果作对比，遗传-拟牛顿混合算法结合了遗传算法快速全局寻优和拟牛顿算法的快速局部寻优能力的优点，使得测量结果与真实结果较接近，且误差较小，从而证明了该算法收敛速度快，稳定性高且精度高。

1 无线传感器网络脉冲耦合时钟同步算法

无线传感器网络脉冲耦合时钟同步算法的最初思想在文献[11]和[12]中得以呈现。在其基础上本文进行了改进，本文采用脉冲耦合振荡器对无线传感器网络时钟同步算法进行系统建模分析，网络中的节点相当于一个可以调节的振荡器，控制节点周期性的触发振荡器。将相位变量与每个传感器节点（振荡器）相联系。脉冲耦合时钟同步算法如下：每个振荡器的脉冲相位以均匀频率增加，当脉冲相位达到最大值时，振荡器发出一个脉冲并重置其相位为0。当振荡器接收脉冲时，它利用耦合强度和相位值函数更新相位，称为相响应函数，其具体表达式为：

       （1）

由相响应函数可知，耦合强度为相响应函数的斜率，在这个算法中，最佳的时钟同步是使用以下相响应函数：

 （2）

在某一时刻读取计时器的值即为节点的相位，计时器的最大计数值就是该节点的相位最大值，是一个具有适当单位的任意值，一旦节点达到计时最大值，计时器溢出中断即相当于Mirollo和Strogatz模型^[13]中的振荡器触发，并通过向其它节点广播信号，产生节点间的耦合效应，在产生耦合效应的同时计时器本身将清零，并重新开始计数，系统开始进入下一个同步周期。节点间通过发送和接收极窄的脉冲信号来完成相互的耦合作用，实现网络中所有节点的时钟同步。

2 TDOA定位方法

为简单起见，本文主要考虑了二维平面内的定位问题，由二维的定位结论，也可以扩展到三维定位问题。设震源位置为，其中为第个传感器节点的坐标，则震源与第个节点的欧氏距离为：

       （3）

本文主要是先测得震源到各个节点的到达时间（TOA），所发出的震源位于中。如图1所示，震源发出一个球状的脉冲波。测得震波的TOA，起源于，起始时间为，在传感器处，位于径向距离处的震源，给出：

 （4）

其中是波速，是误差，假设震波在均匀介质中传播。为了准确地确定震源的位置，一个单一的传感器的测量是不够的，因此，需要结合整个传感器网络进行综合定位。由于震源在某段未知时刻发出一段脉冲波，所以时间的起始量为未知，而且代表一个额外的未知数，定位可以通过考虑传感器和参考传感器的TDOA进行计算。（5）

其中，是第个节点与参考节点之间的误差。把传感器作为参考节点，最大似然估计^[14]（Maximum Likelihood Estimation，MLE）震源的位置为：

（6）

图1 震源定位模型

然而，在实际中，由于测量和定位系统存在不可避免的误差，所以的位置不能精确的确定。因此，公式（6）得出的具体位置只能估计为：

                   （7）

其中是节点的有界位置误差，。

由式（7）可以设立所需目标函数，其为：（8）

图2 定位流程图

在传感器网络中，一个给定的传感器节点只需计数邻居节点和收集TOA值。因此，各个节点之间的信息交换在传感器网络中起着至关重要的作用。基于公式（7）的推导，每一个传感器解决了本节点对震源的定位问题，然后与所有节点的定位结果相结合，最后平均化获得一个精确位置。为了定位出未知震源的坐标，需要求解上式目标函数的解，即找到使式（8）最小的向量值。本文选用遗传算法搜索出离精确解最近的坐标，将其作为拟牛顿算法的初始值进行快速迭代收敛至精确坐标，其具体的定位流程图如图2所示。

3 遗传-拟牛顿混合算法

3.1 遗传算法

遗传算法（Genetic Algorithm，GA）是一种非常有效地解决最优化问题的方法，其可以进行快速搜索得到接近精确解的近似解。GA是模拟达尔文的自然选择和自然淘汰的生物进化过程的计算模型，也是近年来优化领域的热点。遗传算法具有全局搜索的功能，其前期寻优搜索速度很快，因此，在解决很多复杂和状态多变的优化问题方面具有很大优势。本文将震源定位中的目标函数作为适应度函数，其具体的原理如下：

其中本文选用杂交概率为，变异概率为，学习率为，最大迭代次数。首先需要给定搜索的空间范围和随机产生由400个个体组成的一个群体，GA以此400个个体为初始点开始迭代。然后选择能够达到符合预期期望的适应度函数，即为本文的目标函数。最后模拟种群随机交配原理，种群之间进行选择、交叉和变异产生子代，变异出新个体，进行自然选择，逐步选择适应新环境较强的个体，淘汰劣势个体，周而复始，直到满足所设迭代条件后，方可跳出算法，其具体的算法流程图如下：

图3 遗传算法流程图

3.2 拟牛顿算法

拟牛顿法是牛顿法的改进，其实际上可以认为是属于局部收敛的算法^[15]。遗传算法具有前期快速收敛寻优的功能，能够快速搜索到离精确值较近的近似解，而拟牛顿法正好利用了局部寻优的功能，将GA寻优的结果作为拟牛顿算法寻优的初始点进行局部快速搜索。

对于N维函数法，可以写成：

（9）

其中和分别为函数的一阶导数和二阶导数。从此函数中可以发现经过数次迭代过程，有可能会陷入局部极小值点，所以拟牛顿算法要求初始点离极值点不能太远，然而遗传算法刚好弥补了此缺点。拟牛顿算法具体过程如表1所示。

表1 拟牛顿算法

4 仿真结果与分析

本文主要研究的是对地下震源发出的脉冲波进行定位。对一个震源所产生的脉冲波进行定位，其完全取决于震源瞬间产生的脉冲波。震源发出的脉冲波的起始时间显然未知，所以，基于TDOA的定位方法是非常合理且值得实际应用。本文采用四个传感器节点，值得说明的是，如果采用较多的传感器节点可以提高定位的精度，但是过多的传感器节点，其往往会增加成本和带来更多的干扰信号，所以为了在通信质量和定位精度之间达到良好的折中，本文选用四个传感器组成的传感器网络。其传感器网络节点的坐标分别是，，，，波速为。在假定均匀介质中，波速传播速度一定，分别使用拟牛顿算法和遗传-拟牛顿混合算法对同一震源进行模拟定位，仿真模拟结果如下图所示：

图4拟牛顿算法横纵坐标迭代仿真图

由图4拟牛顿算法和坐标的定位可知，大概经过30次迭代后，横坐标趋于稳定值为19.55，纵坐标为24.47，,可得目标位置为，其与标准值之间的误差约为3%。但是拟牛顿算法对初值的要求比较高，如果初值离精确值较近，则能快速收敛到精确值；如果初始值离精确值较远，则拟牛顿算法迭代求解的值很可能发散，无法得到精确解。

图5 遗传-拟牛顿混合算法横纵坐标仿真图

如图5所示，本文使用遗传-拟牛顿混合算法对未知震源坐标进行定位，充分融合了遗传算法和拟牛顿算法各自的优点，即利用了遗传算法前期快速全局寻优的优点和拟牛顿算法后期局部迅速寻优的优点。由仿真结果图5所示得出遗传-拟牛顿混合算法经过大约2次迭代就已经趋于稳定值：最后稳定值的横坐标为19.75，纵坐标为24.51，目标坐标为，其与标准值之间的误差约为1.5%，其精度得到大大提升。由此可得出：对于地下震源的定位，综合比较拟牛顿算法和遗传-拟牛顿混合算法的收敛速度及精确度的优点，本文选用遗传-拟牛顿混合算法对地下震源进行定位。

5 结论

为了提高无线传感器网络的定位精度及效率，本文提出了一种基于遗传-拟牛顿混合算法的到达时间差定位方法，因为地下震源的起始时间未知且无法实际测量，所以提出到达时间差的定位方法更具优势。假定波速在均匀介质的条件下传播，建立目标函数，通过遗传-拟牛顿混合算法进行求解。如果单纯的使用拟牛顿算法进行定位，有可能陷入局部最优点、搜索精度不高的缺点，所以本文提出用遗传算法前期进行全局快速寻优，搜索出离精确值较近的坐标，然后将其作为拟牛顿算法的初始点，再进行局部寻优，最终能够搜寻出比较逼近真实值的坐标，分析了理论上的误差。由仿真结果对比可知，本文所选遗传-拟牛顿混合算法比拟牛顿算法定位收敛速度快，定位精度高，且定位稳定性好。

参考文献

[1] Sheu J P, Hu W K, Lin J C. Ratio based time synchronization protocol in wireless sensor networks[J]. Telecommunication Systems, 2008, 39(1): 25-35.

[2] Yildirim K S, Kantarci A. External gradient time synchronization in wireless sensor networks[J]. IEEE Transactions on Parallel & Distributed Systems, 2014, 25(3): 633-641.

[3] Pazó D, Montbrió E. Low dimensional dynamics of populations of pulse coupled oscillators[J]. Physical Review X, 2014, 4(1):147-241.

[4] Simeone O, Spagnolini U, Bar Ness Y, et al. Distributed synchronization in wireless networks[J]. IEEE Signal Processing Magazine, 2008, 25(5): 81-97.

[5] Hu A S, Servetto S D. On the scalability of cooperative time synchronization in pulse connected networks[J]. IEEE Transactions on Information Theory, 2006, 52(6): 2725-2748.

[6] Wang Yongqiang, Doyle F J III. Optimal phase response functions for fast pulse coupled synchronization in wireless sensor networks[J]. IEEE Transactions on Signal Processing, 2012, 60(10): 5583-5588.

[7] Gao Y, Shen D. Context aware anatomical landmark detection: application to deformable model initialization in prostate CT images[C]//Wu Guorong, Zhang Daoqiang, Zhou Luping. Proceedings of International Workshop on Machine Learing in Medical Imaging. Boston, USA: Springer, 2014, 8(4): 491-502.

[8] Capkun S, Hamdi M, Hubaux J P. GPS free positioning in mobile ad-hoc networks[J]. Cluster Computing, 2002, 5(2): 157-167.

[9] 邓艳容，景新幸，任华娟. 基于麦克风阵列的震源定位研究[J]. 电子技术应用，2010,36(2):87-90.

[10] 陈辉，熊辉，殷昌盛等. 基于无线传感器网络时钟同步的定位算法研究[J]. 现代电子技术，2015,438(7):23-27.

[11] Wang Y, Núñez F, Rd D F. Energy efficient pulse coupled synchronization strategy design for wireless sensor networks through reduced idle listening[J]. IEEE Transactions on Signal Processing, 2012, 60(10): 5293-5306.

[12] Wang Y, Núñez F, Doyle F J. Statistical analysis of the pulse coupled synchronization strategy for wireless sensor networks[J]. IEEE Transactions on Signal Processing, 2013, 61(21): 5193-5204.

[13] Mirollo R E, Strogatz S H. Synchronization of pulse coupled biological oscillators[J]. SIAM Journal on Applied Mathematics. 1990, 50(6): 1645-1662.

[14] Patwari N, Hero A O I, Perkins M, et al. Relative location estimation in wireless sensor networks[J]. IEEE Transactions on Signal Processing, 2015, 51(8): 2137-2148.

[15] 叶海，马昌凤. 求解非线性不等式组的混合遗传算法[J]. 福建师范大学学报（自然科学版），2010, 26(1):18-21.