到时差计算中并行相关算法实验及性能分析

闫广等

摘 要：针对震动波波速成像过程中遇到的海量数据处理问题，提出了分布式实现到时差相关运算，提出了在MapReduce框架下到时差计算的程序设计思路，并在hadhoop环境下进行测试。测试结果表明使用MapReduce作为海量传感器数据的处理框架是可行的；在进行并行的到时差相关运算时，hadoop集群运算所需时间受待计算数据量和data node个数的影响，待计算数据量越大，或data node个数越少，运算所需时间越长，但这两组关系均非线性；平均Map时间与待计算数据量和data node个数无关，仅与Map函数的执行内容有关。

关键词：到时差；分布式矿震监测；MapReduce框架；hadoop集群；计算用时

中图分类号：TP391 文献标识码：A 文章编号：2095-1302（2015）02-00-04

0 引 言

对于煤矿井下的地震勘探来说，其探测的尺度相对于一般的地震勘探来说要小得多，为了实现小尺寸地质结构的探测，传感器的布置相对来说要更密集些[1]。随着传感器布置密度的提高，地震勘探系统采集到的数据量将随之增加，在使用单机进行处理的情况下，到时差的计算及后续的反演计算用时将随之延长[2]，这对系统的实时性是极为不利的。

针对待处理数据量激增的情况，本文基于MapReduce并行计算系统引入数据处理过程，以实际的震动数据为例，测试并分析了并行计算系统计算到时差的用时与待处理数据量、计算用时和集群节点之间的关系。本文的主要贡献在于：

（1）提出了到时差计算中相关算法的并行实现思路。

（2）测试并分析了并行相关算法的性能及影响因素，给出了进一步改进的思路。

1 背景知识与问题描述

1.1 煤炭井下震动波波速成像原理

震动波波速成像原理如图1所示。

当介质均匀时，可以认为震波沿直线传播，此时，可以通过测量震波到达各传感器的到时差来计算介质的平均速度[3]。当介质不均匀时，认为震波的传播路径将按照斯奈尔定律在不同介质的分界面上发生改变，假设图1中各方格速度为v1·vn，震动波波速成像体现为寻找到一组最佳的v1·vn组合，使得通过射线追踪方法计算得到的震波理论到时与实测到时之间的误差最小[4]。

图1 震动波波速成像原理

各传感器间到时差的测量可以通过对不同传感器接收到的震动信号的相关计算来实现，实现的方法如下：

假设传感器c1接收到的震动信号为序列x（n），传感器c2接收到的震动信号序列为y（n），定义信号x（n）与信号y（n）的互相关函数为：，该式表示rxy（n）在时刻m时的值，等于将x（n）保持不动而y（n）移动m个采样周期后两个序列对应相乘再相加的结果。从互相关函数的定义式可见，当c1和c2接收到的为经过同一路径到达的震波，在不考虑不同频率衰减的情况下，相关法测得的到时差精度仅取决于采样周期。

1.2 分布式矿震监测系统

分布式矿震监测系统结构如图2所示：

系统工作过程如下：矿震传感器通过授时子网保持各传感器之间的高精度时钟同步，经测试，时钟同步精度小于1μs。矿震传感器在采集到震动信号以后将震动信号及接收到信号的时间通过数据传输子网发送到数据中心进行处理，用户通过因特网访问数据中心即可对采集到的震动信号进行查看[5]。

图2 分布式矿震监测系统

矿震传感器使用ADI公司出品的AD7606芯片作为A/D转换器，支持8通道同步采样，采样分辨率为16 b，最高采样率可达200 kSPS。由于分布式矿震监测系统以以太网作为数据传输通路，因此，在网络带宽允许的前提下，矿震传感器的布置个数不受限制。

1.3 MapReduce框架

MapReduce框架的工作流程如图3所示：

图3 MapReduce框架的工作流程

在MapReduce框架中，用户需指定Map和Reduce函数的工作内容[6]。Map函数读入输入的键值对（Key/Value），然后根据用户的需要完成指定的工作，处理完成后，Map函数将结果保存为一系列的中间键值对[7]。Reduce函数合并所有具有相同键值的中间键值对，按照用户的需求完成指定工作后将结果输出给用户。

从MapReduce框架的工作流程中可以看出，Map函数之间和Reduce函数之间均是并行执行的，因此，MapReduce模型的数据处理能力仅受限于Map和Reduce的个数，当待处理数据量增大时，可以通过增加Map和Reduce的个数来提高集群的运算能力。

1.4 问题描述

从震动波波速成像的过程可见，提高网格划分密度将提高反演的精细度和质量，而随着网格划分密度的提高，要使v1+vn能够收敛到唯一解，则需要提高穿过网格的射线密度[8]。提高射线密度的方法有两种思路，一是保持矿震传感器数量不变，提高震动的次数，二是保持震动次数不变，提高矿震传感器的数量。显然，在实际情况下，当震动次数一定的时候，提高矿震传感器的数量是唯一可行的方法。

矿震传感器数量的提高意味着传感器之间道间距的缩小，随着道间距的缩小，震波到达传感器的到时差也相应缩小[9]，因此，各传感器节点间到时差的测量精度也应该相应提高。从1.1中的分析可知，相关法的到时差测量精度取决于采样周期，因此，若要实现高精度的时差测量，应降低采样周期亦即提高采样频率。

显然，当信号的采样频率提高时，在保持传感器数量和采样分辨率不变的前提下，信号所需要的传输带宽将相应提高，举例如下：

假设某煤矿井下布设的单分量矿震传感器数量为100个，信号的采样频率为1 kSPS，即到时差的测量精度为1 ms，则信号传输所需的最小带宽可计算如下：

B=16/8×1 000×100=200 KB/s （1）

随着道间距的缩小，需要提高采样频率，假设采样频率提高到1 MSPS，此时到时差的测量精度为1 μs，则信号传输所需的最小带宽为：

B=16/8×1 000 000×100=200 KB/s （2）

可见，采样频率相较原来提高k倍，将导致信号传输所需的最小带宽相应提高k倍，存储和处理这些数据所需的计算量将很容易超过单机的处理能力。

2 MapReduce框架下相关算法设计

从1.4中的分析可见，当信号采样频率提高时，海量传感器数据的处理将超出单机处理能力，而MapReduce框架作为一种并行处理方法，其处理能力可以随着机器数的增加而增加[9]，因此，使用MapReduce作为海量传感器数据的处理框架是可行的。

当分布式矿震监测系统中的数据中心接收到海量的传感器数据后的数据处理过程分为如下几个步骤：（1）数据被存储到分布式文件系统中，在分布式文件系统中，为了保证存储的可靠性，文件一般会被保存为N份副本；（2）识别矿震信号，并将有效的矿震信号取出；（3）针对某一次矿震，计算相邻矿震传感器节点之间的到时差；（4）根据到时差反演监测区域的速度分布情况。

本文仅针对数据处理过程中的步骤（3），提出MapReduce框架下到时差计算的程序设计思路并在hadoop环境[10] 下对这种思路的性能进行测试。

根据1.1中相关计算的公式，信号x（n）与信号y（n）的互相关函数定义为：

（3）

假设两信号的实际到时差为m'，则当m=m'时rxy（m）将取得最大值，为了找到这个值，需要在m1≤m≤m2的范围内计算rxy（m）的值并找到其中的最大值，一般取，m1=-D12/V，m2=D12/V，其中D12为传感器c1和传感器c2间距，V为介质中震波的平均速度。

显然，当m取不同的点时序列互相关值的计算是相互独立的，可以设计为并行算法实现。因此，可将MapReduce框架下相关算法的实现思路设计如下[6]：

（1）根据待计算的序列值生成所有待计算的序列对或等价的计算式，比如，待计算序列为x（n）和y（n），则其所有待计算的序列对为x（n）·y（n+m1）…x（n）·y（n+m2）。

（2）Map函数将计算对作为Value读入，并将计算结果作为Value输出给Reduce函数。

（3）Reduce函数将计算结果输出即得序列的相关结果。

本实验中，待计算序列保存为txt格式的单一文件，两相邻的序列用0X0D和0X0A间隔开，同一行中的两个序列x（n）与y（n+m）用0X21间隔开。最终生成的文件格式如下：

（4）

应注意的是，这样生成的待计算序列将占用较大的存储空间，不适用于实时或准实时计算。

Map函数的执行流程如图4所示：

图4 Map函数的执行流程

Reduce函数将接收到的值不做处理直接输出即可得互相关序列。

3 实验结果与分析

3.1 实验环境

由16台普通PC组成集群，一台机器作为name node，其余15台机器作为data node，机器配置相同，具体配置如表1所示。

表1 PC集群的配置

CPU 内存 硬盘 网卡 操作系统 Hadoop版本 JDK版本

Intel Pentium E5300 DDR3

1 GB 500 GB 7 200转 SATA2 100 M Ubuntu 13.10 server 2.2.0 1.7.0_71-b14

实验数据为两组实测的震动数据，数据采样率为1MSPS，数据位数16 b，时长10 ms，每个序列的数据点数为104个，如图5所示。

3.2 实验内容与结果

3.2.1 运算量与平均运算速度

按照公式（4）所示格式，以100行为间隔，依次生成待计算数据，最终生成1 500行待计算数据，依次将数据传入HDFS并启动互相关算法，多次实验，记录作业完成时间的平均值，实验结果如图6所示。

图5 两组实测震动数据

图6 实验结果

从实验结果可以看出，随着运算量的增加，算法执行的平均时间也随之增加，但平均执行时间与运算量之间并非线性关系。

定义执行时间的变化率为，则平均执行时间的变化率如图7所示。

图7 平均执行时间变化率

可见，当待计算数据行数在100～600范围内的时候，平均执行时间的变化率较小。通过hadoop日志分析发现，当待计算数据行数超过600时系统出现Map任务排队，说明此时待执行的总Map任务数超过系统最大并发任务数，因此平均执行时间会延长。

3.2.2 运算量与平均Map时间

在3.2.1所述实验过程中，记录每次互相关计算的每次Map任务执行的平均时间，实验结果如图8所示。

图8 实验结果

平均Map时间的变化率如图9所示：

图9 平均Map时间的变化率

对比平均Map时间变化率和平均执行时间变化率可见，平均Map时间与运算量之间无明显关系。

3.2.3 节点数与平均运算速度

按照公式（4）所示格式，生成1 100行待计算数据，将数据送入有6个data node的集群中，保持数据量不变，依次增加data node的个数直至15个data node为止，多次实验，记录作业完成的平均时间，实验结果如图10所示：

图10 1 100行数据平均执行时间

1 100行数据平均执行时间的变化率如图11所示：

图11 1 100行数据平均执行时间变化率

显然，对于相同的运算量来说，data node数的增加将降低平均执行时间，加快执行速度，但节点数和平均执行时间的关系并非线性的，随着节点数的增加，平均执行时间的下降速率是减小的。

3.2.4 节点数与平均Map时间

在3.2.3的实验中平均Map时间与节点数的关系如图12所示：

图12 平均Map时间与节点数的关系

可见，平均Map时间不受节点数的影响，此外，比照3.2.2中的平均Map时间可以发现，两次实验中的平均Map时间基本一致，这说明平均Map时间与运算量、节点数无关。

4 结 语

本文针对震动波波速成像过程中遇到的海量数据处理问题，提出在分布式条件下实现到时差相关运算的思路并以此思路为基础完成相关实验，从实验结果来看，可以得到以下几点结论：

（1）到时差相关运算的并行实现可分成两个步骤实现，首先将待计算序列转化为待计算序列对，然后将所有待计算序列对送入并行计算系统即可得计算结果。但是在具体实现时应注意的是，如果直接将待计算序列按照本文所述方法进行转化的话会造成待计算序列对体积的急剧膨胀，不利于提高计算的速度。

（2）在进行并行的到时差相关运算时，hadoop集群运算所需时间受待计算数据量和data node个数的影响，待计算数据量越大，或data node个数越少，运算所需时间越长，但这两组关系均非线性。对于某一次具体运算来说，当待计算数据量小于集群最大并行计算量时运算所需时间最小。

（3）平均Map时间与待计算数据量和data node个数无关，仅与Map函数的执行内容有关。

参考文献

[1] 左国平. 地震记录初至拾取方法对比和研究 [D].北京：中国地质大学， 2006.

[2] 张凌云. 高密度电阻率勘探反演的非线性方法研究 [D].太原：太原理工大学，2011.

[3] Xiang Z， Ce Y. Fast n-point correlation function approximation with recursive convolution for scalar fields[C]. IEEE 3rd International Conference on Cloud Computing Technology and Science （CloudCom 2011）， Los Alamitos， USA： IEEE Computer Society，2011.

[4] 靳朋飞， 曹菡， 余婧，等. MapReduce模型下Voronoi图栅格生成算法[J]. 计算机科学与探索，2013（2）：160-167.

[5] 贾宝新. 矿震监测的理论与应用研究 [D]. 阜新：辽宁工程技术大学，2013.

[6] 刘义， 景宁， 陈荦，等. MapReduce框架下基于R-树的k-近邻连接算法[J]. 软件学报. 2013，24（8）：1836-1851.

[7] Afrati F N， Ullman J D. Optimizing joins in a map-reduce environment[C]. 13th International Conference on Extending Database Technology： Advances in Database Technology， Lausanne， Switzerland： Association for Computing Machinery，2010.

[8] 顾汉明， 周鸿秋， 张学强. 初至时间的自动拾取[J]. 物探与化探. 1992（2）：120-128.

[9] 黄翼坚. 多井源距VSP速度分析及逆时偏移 [D].西安：长安大学，2010.

[10] Joshi S B.Apache hadoop performance-tuning methodologies and best practices[C]. 3rd Joint WOSP/SIPEW International Conference on Performance Engineering， Boston， United states： Association for Computing Machinery，2012.