几何射线追踪法算法改进

任亚鹏，石 丹，高 伟，高攸纲，陈亚洲

（1.北京邮电大学 电子工程学院，北京 100876； 2.石家庄军械工程学院，石家庄 050003）

前言

几何射线追踪法是电磁波传播建模的重要工具，在电波传播模拟仿真中有着重要的应用。射线追踪是一种被广泛用于移动通信和个人通信环境(室外宏蜂窝、街道微蜂窝和室内微蜂窝)中预测电波传播特性的技术[1]，其基本思想是从几何光学法演变而来的：将入射电磁场离散成为射线管,对每条射线管的散射路径进行追踪,可以对一般耦合效应进行合理的计算和预估。这使得几何射线追踪法成为处理耦合散射效应的经典方法[2]。然而传统的几何射线追踪法对于发射机采用全向剖分的方法。这势必导致发射射线数量很多。由于接收机位置以及接收天线方向性等问题，这样的无目的性全向剖分导致大多数射线都无法达到接收机，造成了多数射线的无用追踪，从而使得整个射线追踪算法效率低下。在电磁仿真软件设计中，整个射线追踪模块往往是软件运行效率的瓶颈。

针对这些问题，我们在保证射线追踪结果精度的前提下提出了针对射线追踪发射模块的改进算法。将旧算法全向剖分发射射线静态追踪的方法，改进为按照天线的方向图剖分，动态追踪的新方法。达到了在误差允许的范围内，大幅度提高射线追踪算法时间的目的。

1 算法改进思想

针对射线追踪旧算法静态全向剖分的不足，新算法在两个方面将之前的静态追踪优化为了动态追踪。首先是发射模块，由于全向剖分实际上是一种穷举法，将所有可能发射的射线全部都追踪一遍，最终按照是否能到达接受球以及功率是否衰减到阈值之下进行筛选和舍弃。这样的穷举法简单粗暴，目的性太差。而新算法则在发射阶段已经进行了一次筛选，也就是已经按照接收机的位置以及接收机天线的方向图进行了有选择的剖分。从而按照接收机带着强目的性减少了发射射线的条数。显著减少了射线追踪的时间。然而，单纯从这一点改进，存在着明显的不足。首先射线追踪虽然按照接收机进行了有针对性的定向剖分，但仍是一种静态的追踪思想，只是减少了发射射线条数。更重要的是实际应用中会发现，这样设计虽然可以大幅度提高射线追踪算法的时间，然而精度方面明显达不到要求。

针对这些问题，提出了本文算法改进的思想：

第一步：将静态改成两个动态。第一个动态是射线追踪过程中射线的动态。在旧算法中射线追踪条数在发射阶段已然确定，只用以此进行追踪即可。而新算法是动态改变的，换句话说，发射模块发射的射线只是一个初始条件，在整个射线追踪的过程中，射线是动态变化的，然而这个变化不是随机无序的，而是按照能否到达接收机来进行动态的增加和舍弃。第二个动态是接收球的半径是动态变化的，在新算法中接收球是一个半径逐渐减小的动态球。

这两个动态是互相紧密配合的。目的是达到在精度允许的范围内减少射线追踪时间。细化过程如图1 所示。

然而，这种动态变化也产生以下的问题：动态的初始条件如何设定，动态变化如何设计。如果动态初始条件设计得过于精细，确实能够保证在精度方面的准确。然而过度的精细会导致新算法的速度下降，由于存在重复追踪，甚至会导致新算法的速度比旧算法还要慢，这显然和新算法的初衷背道而驰。如果初始条件设计过度粗略，这样算法的速度会很快，但是追踪结果的精度难以保证。

针对这些问题，要进行算法改进的第二步：根据接收机天线的方向图进行动态设计。也就是在接收机天线的主瓣方向要加大细化密度。而在其他地方适度的减小细化密度，从而达到精度和效率的最佳结合点。

2 算法的具体实现

算法的流程图如图2 所示。

图中射线追踪初始化是第一个关键点，本算法采用动态改变射线初始化的方法，也就是根据不同的接收机天线的方向图设计不同的射线剖分方法。

循环截止条件的设定是算法第二个关键点。设计循环截止条件有许多不同的思路。最容易想到的是接收球半径作为截止条件和最小细化角作为循环截止条件。循环截止条件的设定也是难点所在。如果截止条件设置得过分精细，很可能最终输出射线的总功率和场强等参量都比实际值偏小很多，甚至有可能根本接收不到射线。而如果截止条件设置得过分宽泛，有可能收到的射线条数很多。导致最终结果的各个参量都比理论值大很多。

图1 细化过程简图

图2 射线追踪改进算法流程图

算法的第三个关键点是射线的动态更新，要完成这项任务必须设计一种数据结构，里面要存有射线和接受球的动态相交情况以及产生新射线需要的信息。

下面简单介绍下路径节点的存储结构：

路径中每个节点包含三个部分：分别存放产生这条射线的两条父射线信息，以及这条射线本身的信息。而每一条射线信息又包含四个部分：分别是这条射线的起始节点，射线的方向向量，是否与接受球相交，以及路径的信息。详细节点组成图如图3 所示。

发射出的射线采用动态追踪的方式，在每一次追踪到的射线之间再进行细化，产生新射线。追不到的射线及时进行舍弃。避免无用的射线的重复追踪。

动态判断射线和接受球是否相交，并且随着追踪过程随时更新节点和接收球的相交标志位。一定要注意在这个过程中的两个动态：

第一：射线条数是动态的，也就是随时在有新射线的产生和旧射线的舍弃。

第二：接收球半径始终在动态地改变，在整个追踪过程中，每次循环都要改变接受球的半径。

图3 新算法路径节点组成图

表1 新旧算法的执行结果

3 新旧算法结果对比

保持单一变量的原则，也就是新旧算法的对比过程中只有射线追踪模块采用的算法不同而已。其他所有工程参量都一致，比如：接收机都采用半波偶极子天线，而且接收球的半径都是12.4m。

通过计算，直射射线接收功率理论值为-28.5dBm，直射射线产生的场强理论值为0.2542V/m。

新旧算法的执行结果如表1 所示。

从表中可以明显看出，新算法的在允许的误差范围内显著的提高了运行速度，得到比较满意的预期结果。

4 总结

几何射线追踪法作为电波传播模拟仿真的重要工具，在数据仿真运算中有着广泛的应用。而算法耗时过长，往往是整个仿真算法的瓶颈所在。研究发现，每条射线的追踪时间并不长，真正影响算法性能的根本原因是初始化发射射线的条数过多。在接收天线相对集中，而且具有强方向性时，这样全向剖分去发射射线造成了大量的浪费。所以在这样的背景下提出了这种动态追踪的新算法，旨在发射阶段就按照接收机具有强目的性的发射射线。通过结果对比可知，新算法可以较好地在误差范围内减少旧射线追踪算法的运算时间，而且由于方向图的引入，实验的精度也较旧算法全向剖分发射射线有所提高，可以较好地用在电波传播仿真软件的射线追踪模块中。

[1]刘斐，电波传播射线追踪法的研究[J]，信息与电脑，2011，（2）：160.

[2]黄沛霖，一种射线追踪法的效率改进算法研究[J]，北京航空航天大学学报，2003，29（7）.