一种基于MapReduce的射线跟踪加速算法

摘要

本发明公开了一种基于MapReduce的射线跟踪加速算法。首先确定源点和场点，从各源点发射的射线经过建筑物的反射后到达对应的场点；然后判断从源点发射的射线是否为有效射线；如果是，则分别记录射线到达各场点的三维坐标与该射线到达此场点的特征值；最后建立Map函数来处理特征值，得到特征值的场强、到达角、延迟和极化四个参数。本发明采用基于MapReduce的射线跟踪加速算法用于大规模数据集的并行运算。而射线跟踪过程中所跟踪的射线量巨大，计算时间长，各个射线相互独立，具有自然的并行性，因此，在进行射线跟踪时，将射线跟踪与MapReduce结合，射线跟踪的运算效率提高。

说明书

技术领域

本发明涉及计算机并行计算与无线电波传播领域，尤其涉及射线跟踪加速和云计算中的 MapReduce并行编程模式。

背景技术

射线跟踪方法能根据微小区的环境特征，给出微小区电波预测的确定性模型，但是这种 方法对复杂的建筑物环境或建筑物环境的三维模型进行预测时耗时巨大，因此，射线跟踪加 速算法成为人们关注的核心问题。近年来，国内外学者提出很多射线跟踪加速算法。其中空 间分区法虽然能很好的解决反射现象，但是对于绕射现象算法效率的提高不明显。二叉树方 法仅在进行跟踪求场强时缩短了计算时间，对于建立路径树仍然费时。并行处理法在计算精 度相同的情况下能大大缩短计算时间，并且能够利用网络中空闲的计算机资源。

MapReduce是Google提出的一种并行编程模式，MapReduce把对数据集的大规模操作， 分发给一个主节点管理下的各分节点共同完成。一个Map函数对一部分原始数据进行指定的 操作，每个Map操作都针对不同的原始数据，因此Map与Map之间相互独立，这就使得它们 可以充分并行化。一个Reduce操作就是对每个Map所产生的结果进行合并操作，所有Reduce 产生的最终结果经过简单连接就形成了完整的结果集，因此Reduce也可以在并行环境下执 行。

而射线跟踪过程中所跟踪的射线量巨大，计算时间长，但在此过程中，各个射线相互独 立，具有自然的并行性，因此，在进行射线跟踪时，可以将射线跟踪与MapReduce结合，提 高射线跟踪的运算效率。

因此急需一种提高射线跟踪运算效率的加速算法。

发明内容

有鉴于此，本发明所要解决的技术问题是提供一种一种提高射线跟踪运算效率的加速算 法。

本发明的目的是这样实现的：

本发明提供的一种基于MapReduce的射线跟踪加速算法，该方法基于MapReduce框架， 包括以下步骤：

S1：确定源点和场点，从各源点发射的射线经过建筑物的反射后到达对应的场点；

S2：判断从源点发射的射线是否为有效射线；如果否，则该射线到达场点的三维坐标设 为源点坐标，场点的特征值记为0；

S3：如果是，则分别记录射线到达各场点的三维坐标与该射线到达此场点的特征值；

S4：建立Map函数来处理特征值，将特征值中属于同一三维坐标的场点归为一类；

S5：建立Reduce函数来对归类后的特征值进行处理，以Map函数返回的三维坐标值为 关键字，对关键字相同的Map函数处理的场点特征值这一结果进行相应的迭代运算，得到该 场点总特征值。

进一步，所述特征值包括场点的场强、到达角、延迟和极化四个参数。

进一步，所述判断从源点发射的射线是否为有效射线，具体步骤如下：从每个源点发出 的射线，在射线传播的过程中，经过反射、折射或绕射到达场点的射线为有效射线；从每个 源点发出的射线，在射线传播的过程中，能量衰减到规定阀值，确定该射线为无效射线。

进一步，所述从源点发射的不同的射线采用不同的Map函数进行跟踪，每个Map函数包 括场点三维坐标和场点特征值两个参数；对于能够到达同一场点的若干条射线，与之相对应 的Map函数返回的场点的三维坐标值是相同的。

进一步，所述同一场点归为一类是根据Map函数中场点三维坐标值是否相同来归为一类； 如果相同，则归为一类；如果不相同，则单独一类。

进一步，所述每个Map函数分配一条射线，根据需要确定源点角度，从而进一步确定射 线数目，根据射线数目，所述每个Map函数处理自身的射线。

进一步，所述各Map函数相互独立对原始数据进行并行操作。

进一步，所述Map函数，用于跟踪从源点发射的不同的射线，每个Map函数包括场点三 维坐标和场点特征值两个参数；对于能够到达同一场点的若干条射线，与之相对应的Map函 数返回的场点的三维坐标值是相同的；

所述Reduce函数，以Map函数返回的三维坐标值为关键字，对关键字相同的Map函数 处理的场点特征值这一结果进行相应的迭代运算，得到该场点的总特征值。

本发明的优点在于：本发明采用一种基于MapReduce的射线跟踪加速算法：MapReduce 是一种能处理海量数据的并行编程模式，用于大规模数据集的并行运算。而射线跟踪过程中 所跟踪的射线量巨大，计算时间长，但在此过程中，各个射线相互独立，具有自然的并行性， 因此，在进行射线跟踪时，将射线跟踪与MapReduce结合，提高射线跟踪的运算效率。

本发明的其它优点、目标和特征在某种程度上将在随后的说明书中进行阐述，并且在某 种程度上，基于对下文的考察研究对本领域技术人员而言将是显而易见的，或者可以从本发 明的实践中得到教导。本发明的目标和其它优点可以通过下面的说明书，权利要求书，以及 附图中所特别指出的结构来实现和获得。

附图说明

为了使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步的 详细描述，其中：

图1为简单小区环境建筑模型示意图；

图2为利用MapReduce进行射线跟踪的流程图。

具体实施方式

以下将结合附图，对本发明的优选实施例进行详细的描述；应当理解，优选实施例仅为 了说明本发明，而不是为了限制本发明的保护范围。

实施例1

图1为简单小区环境建筑模型示意图，图2为利用MapReduce进行射线跟踪的流程图， 如图所示：本发明提供的一种基于MapReduce的射线跟踪加速算法，包括以下步骤：

S1：确定源点和场点，从各源点发射的射线经过建筑物的反射后到达对应的场点；

S2：判断从源点发射的射线是否为有效射线；如果否，则该射线到达场点的三维坐标设 为源点坐标，场点的特征值记为0；

所述判断从源点发射的射线是否为有效射线，具体步骤如下：从每个源点发出的射线， 在射线传播的过程中，经过反射、折射或绕射到达场点的射线为有效射线；从每个源点发出 的射线，在射线传播的过程中，能量衰减到规定阀值，对场点的总特征值贡献不大，可以忽 略的射线为无效射线。

S3：如果是，则分别记录射线到达各场点的三维坐标与该射线到达此场点的特征值；所 述特征值包括场点的场强、到达角、延迟和极化四个参数。

S4：建立Map函数来处理特征值，将特征值中属于同一三维坐标的场点归为一类；

S5：建立Reduce函数来对归类后的特征值进行处理，以Map函数返回的三维坐标值为 关键字，对关键字相同的Map函数处理的场点特征值这一结果进行相应的迭代运算，得到该 场点总特征值。

Map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce（化 简）函数，用来保证所有映射的键值对中的每一个共享相同的键组。

所述从源点发射的不同的射线采用不同的Map函数进行跟踪，每个Map函数包括场点三 维坐标和场点特征值两个参数；对于能够到达同一场点的若干条射线，与之相对应的Map函 数返回的场点的三维坐标值是相同的。

所述同一场点归为一类是根据Map函数中场点三维坐标值是否相同来归为一类；如果相 同，则归为一类；如果不相同，则单独一类。

所述每个Map函数分配一条射线，根据需要确定源点角度，从而进一步确定射线数目， 所述每个Map函数处理自身的射线。

所述各Map函数相互独立对原始数据进行并行操作。

所述Map函数，用于跟踪从源点发射的不同的射线，每个Map函数包括场点三维坐标和 场点特征值两个参数；对于能够到达同一场点的若干条射线，与之相对应的Map函数返回的 场点的三维坐标值是相同的；

所述Reduce函数，用于以Map函数返回的三维坐标值为关键字，对关键字相同的Map 函数处理的场点特征值这一结果进行相应的迭代运算，得到该场点的总特征值；

实施例2

如图1所示为一个简单的小区环境建筑模型，在此环境中，假设有5个源点 （s1,s2,s3,s4,s5）和3个场点（t1,t2,t3）。每个源点发射一条射线，那么总共有5条射 线。其中源点s1，s2发出的射线经过建筑物的反射后能够顺利的到达场点t1，t2。s3和s4 发出的射线经过反射后到达同一场点t3，因此这四条射线是有效射线，源点s5发出的射线 没有到达场点，因此是无效射线。

在利用MapReduce的思想进行射线跟踪时，首先要编写两个主要函数:

Map:(in_key,in_value)->{(keyj,valuej)|j=1...k}，其中in_key代表射线到达某一 场点后，这一场点的三维坐标；in_value代表射线到达某一场点后，射线在此场点的特征值。

Reduce:(key,[value1,...valuem])->(key,final_value)，将Map函数最后处理结果中 关键字相同（到达同一场点）的归为一类，并对Map函数得出的特征值进行处理，得到此场 点最后总的特征值。

如图2所示，主控程序为每个Map函数分配一条射线，总共需要5个Map函数处理这些 射线。当一条射线到达某场点后，此条射线即为有效射线，从图1可以看出，源点s1，s2， s3，s4发出的射线经过建筑物反射后到达了场点，即为有效射线，那么与之相对应的Map 函数就记录下来到达场点的三维坐标in_key和它们在此场点的特征值in_value；对于那些 没有到达场点但能量衰减到可以忽略的射线，即源点s5发出的射线，相应的Map函数的处 理结果就可以忽略。当所有的Map函数处理完后，主控程序模块再对所有Map函数处理结果 按照关键字进行归类，关键字相同的Map函数，主控程序会归为一类，不相同的单独一类， 归类后交由Reduce函数处理，一个Reduce函数的处理结果是一个场点的总的特征值。在图 1中，s1到达场点t1，它对应一个Reduce函数，s2到达场点t2，对应一个Reduce函数， s3，s4由于到达同一场点t3，经过Map函数处理后，关键字相同，因此它们对应同一个Reduce 函数。经过这些Reduce函数处理后，就可以得出场点t1，t2，t3的特征值。

本发明针对射线跟踪方法自然的并行性，结合MapReduce的并行编程模式来进行射线跟 踪的加速算法，由于在密集复杂的建筑物环境中，射线经过反射、折射、绕射后数量庞大， 而MapReduce又是针对海量数据的并行运算思想，因此对于复杂环境的射线跟踪，此种方法 是十分高效的。

以上所述仅为本发明的优选实施例，并不用于限制本发明，显然，本领域的技术人员可 以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修 改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变 型在内。