基于地形分区的射线跟踪法加速方法的研究
2014-03-05李朋朋陈亚洲高攸纲
李朋朋，陈亚洲，石 丹，高攸纲
（北京邮电大学 电子工程学院，北京 100876）
引言
随着现代信息技术的快速发展，武器装备信息化的程度不断提高，大量的电子信息装备使得开放的战场空间中的电磁信号非常密集，形成了极为复杂的电磁环境，无线电传播的环境越来越复杂。精确预测电波传播特性在战场信息化上显得尤为重要。
射线跟踪法是在几何光学理论、几何绕射理论和一致绕射理论基础上发展起来的，为获得有用的仿真结果提供了精确的特定点方法，被广泛应用于电磁环境仿真中[1-3]。然而传统的射线跟踪法虽然能够适应复杂环境的电波预测，但是计算量巨大导致计算效率降低，因此提高射线跟踪法的计算效率成为大量学者的研究重点。在开放的地理环境中主要考虑的是射线与地面求交点的运算时间消耗，该部分耗时最大，针对这样的问题，本文提出一种减少射线与地面相交点个数的算法，同时在计算机程序中使用多线程技术来提高射线跟踪法的计算效率。
1 射线跟踪理论基础
1.1 射线跟踪法基本思想
射线跟踪法的基本思想是将从源点辐射出的电磁波看作一条条射线，能量在各自独立的射线管内传播。对每一条射线的传播进行追踪，直到射线到达目标点或射线能量低于需要考虑限度时，在这过程中计算出射线的能量，求得所有到达场点的射线后，采用矢量叠加的方法得出辐射源的影响[4]。射线在传播过程中，遇到障碍物时发生反射或绕射，根据镜面反射原理和一致性绕射原理计算出反射点和绕射点处的场强。射线的场强衰减到预先设置的阈值后，放弃跟踪本条射线，继续跟踪下一条射线。可见射线跟踪过程是一个复杂的递归过程。
在接收点出的场强（单位：dB）可表示为：
式（1）中n为到达接受点的射线数量，Ei为第i条到达接受点射线的场强矢量。Ei由下式计算：
1.2 影响射线跟踪法的因素
1）辐射源发射的射线数目，它决定了需要跟踪的射线数目，计算发射射线数目的公式是n=2π/φ，其中φ为发射张角，因此发射张角的大小直接影响射线跟踪法的运算效率。
2）地形环境的复杂程度决定了射线求交运算的运算次数，从而影响射线跟踪法的运算效率。
3）当射线碰到地形面时，将会发生反射或绕射现象，此时反射及绕射系数的经度对射线跟踪法的运算效率也会产生影响。
在上述的因素中，发射张角是固定不变的，即辐射源发射的射线数目通常是不变的，而反射及绕射系数也是固定不变的，因此地形复杂程度就决定了发射点及绕射点所需要的求交运算次数。地形越复杂，需要的求交运算的次数越多，并且大多数求交运算是需要舍弃的无用运算。因此，大量无用的求交运算就是影响射线跟踪法运算效率的主要因素[6-7]。
2 地形分区
由射线跟踪法的过程可知，射线与地形发生碰撞后会反射和绕射，只有确定碰撞交点才能继续跟踪射线。在传统的射线跟踪法中，需要射线与地形面进行求交运算才能确定反射点或者绕射点，当地形面比较复杂的时候，这种求交运算就会很费时，并且绕射点的增多将进一步增加射线的数量和求交运算的次数。本文提出对地形分区的思想，将减少求交运算的次数，提高计算的效率。
2.1 地形的组成
本文所采用的地形是由数字高程模型（DEM）转化而成的地形文件，它采用了三角网格剖分技术，将地形面由多个三角面组成近似表示。之所以采用三角剖分技术，是因为三角剖分技术是众多技术中最科学的表达方式之一，也是最常用的一种技术。由于我们只能获取DEM数据文件，因此要转化成三角网格地形面需要一定的算法提取高程值进行三角面构造。
2.1.1 DEM数据解析
在构造地形面之前，我们必须提取DEM中的高程数据，因此我们必须了解DEM中数据的组织形式。
通常我们能够获取到的DEM数据为1°×1°的格式，其数据组织方式如图1。
图1 DEM Data Organization
从图1中可以看到数据是以点矩阵的形式存储的，在文件中存储的顺序是从Pt1点开始将每一列映射到文件中的一行数据。文件中的第一行会存储一些关于该地形的信息，比如说西南角和东北角坐标（经纬度），数据的行数和列数，间隔秒数等。在图1中可以看出DEM数据X和Y方向的采样点间隔为3秒（约70米，不同地区长度不同），形成一个三秒网格。文件中除了第一行外，其余全部由采样点相对应的高程值组成。
2.1.2 地形的构造
根据DEM数据存储的规律我们可以轻松的编程提取到高程值和地形坐标范围，但是如何存储这些数据使它们能够便利的构成三角面？
在本文中设计了一种文件按照一定的格式来存储这些数据，定义为ter文件。Ter文件中的数据按照一定的规律存储，且要能够表示出三角面的组成元素，即三个顶点坐标，以
式中phi为纬度，theta为经度。
对应图1数据的三角面的组织形式如图2所示，一个三秒网格对应两个三角面。
根据上述的三角面的组织形式，地形就可以从DEM中转化出来。本文在C++编程环境下调用OpenSG图形开发标准库开发出显示界面，地形显示效果如图3所示。
图3表明，通过DEM转换出来的ter文件可以通过OpenSG开发的界面近似的显示出地形的态势，表示该转换过程的有效性。
2.2 地形的分区
传统的射线跟踪法要求计算出射线与碰撞面的反射点和绕射点才能继续跟踪射线路径，由于辐射源位置及射线的方向性的不可知性，通常求射线与地形某个三角面的交点需要遍历判断整个地形的每个三角面与射线是否相交。若相交，判断交点是否在三角面内的过程，直到得到满足条件的结果。然后从这些交点中求出射线方向的上离辐射源最近的一个交点即得到正确的结果。
虽然这种算法可以满足需求并得到满意的结果，但是其复杂度为O(N)，其中N为组成地形的三角面的个数。对于小的地形该算法可以满足快速计算，但是对于由上十万个三角面组成的大地形而言，该算法将耗时过长。另外程序需要计算上千条射线，因此该算法的计算量巨大，影响计算效率。
本文提出一种优化求交点速度的算法，基本思想是通过研究射线的方向特性减少需要判断是否相交的三角面的个数，从而减少计算的时间复杂度，达到提高计算速度的目的。具体的实现步骤如下：
1）已知辐射源的坐标和辐射源发出的射线的方向向量。通过查找辐射源坐标的位置，可以将地形分为四块，如图4(a)所示。
2）根据辐射源发射的射线的方向向量可以判断射线将向某个方向射出，因此射线只与该方向区域内的三角面有相遇的可能，如图4(b)所显示的区域。
3）再根据射线的X和Y向量形成的夹角进一步缩小射线可能经过的三角面的范围，如图4(c)所显示的区域。
图2 三角面组织形式
图3 地形显示
4）由于辐射源处于地形面上，因此有一定的高度，根据射线方向向量的Z向量判断射线是空间向上还是空间向下射出，由此再缩小可能相交的三角面的个数，只计算比辐射源高或低的三角面即可。
理论上经过以上步骤可以将需要计算的三角面的个数平均减少至原算法的 ，从而将算法的计算效率提高至原算法的16倍。
3 多线程技术的使用
3.1 多线程概念
多线程是指从软件或者硬件上实现多个线程迸发执行的技术。具有多线程能力的计算机因有硬件支持而能够在同一时间执行多于一个执行绪，进而提升整体处理性能。多线程处理可以同时运行多个线程。由于多线程应用程序将程序划分成多个独立的任务,因此可以在以下方面显著提高性能:
1）多线程技术使程序的响应速度更快 ,因为用户界面可以在进行其它工作的同时一直处于活动状态；
2）当前没有进行处理的任务时可以将处理器时间让给其它任务；
3）占用大量处理时间的任务可以定期将处理器时间让给其它任务；
4）可以随时停止任务；
5）可以分别设置各个任务的优先级以优化性能。
3.2 多线程的实现
图4
在复杂电磁环境中，往往存在着多个发射机与多个接收机。发射机之间的电磁干扰可忽略，接收机处的电场强度可由辐射源独立产生的电场强度的叠加得到。
设有N个辐射源，每个辐射源Tn在接收机R处产生的电场为En，En在x、y、z方向上的分量分别为Enx、Eny、Enz。叠加后的总磁场为E,E在x、y、z方向上的分量分别为Ex、Ey、Ez,。可由公式(5)-(7)得到叠加后接收机R处的电场。
另外还有研究意义的是电场强度的幅值，可由公式（8）得到
由公式可以得出，一个接收机接收到的由同一频段所有发射机发射的电场强度的幅值的平方可以分解为该接收机接收到的每一个发射机的电场强度的实部之和与虚部之和的平方和。这就为多线程的使用提供了一定的理论基础。
部分实现代码如下：
一般情况下，使用多线程技术提高的效率与cpu的核数有正比的关系，如cpu是N核处理器，那么使用多线程可以将计算效率提高近N倍。
4 仿真分析
为了验证上述加速方法的有效性，选取多块不同三角面个数的地形分别使用传统射线跟踪法和本文所提出的方法进行求交运算，比较两种方法仿真所需要求交的面数和使用的时间。为了方便比较，我们均将反射源的点设置在地形的中心，进行200条不同方向射线的求交计算。使用的仿真平台为Intel i5处理器，1G内存，VS2010，OpenSG。
比较结果如表1所示。
从表1中可以得到以下结论：
1）改进方法需要计算相交的面数比传统方法所需要的面数少，当地形总三角面数越多越明显。
2）由于需要计算的相交的面数少，所以在计算时间上改进方法比传统方法所需时间少。
3）当地形三角面较少时，两种方法计算时间上没有太大的差距，而随着三角面数量增多这种差距就明显了。
4）由于计算的面数与辐射源的位置有一定的关系，可能导致计算的时间与传统方法有时相差不大，但是平均来说，改进方法所需的计算时间总是比传统方法少，且地形越复杂越是明显。
当然，提高计算速度的同时也要保证计算的精度，不过在本算法中并不会影响到精度，因为两种方法中射线与地形相交的点并不会发生改变，那么就不会影响下一次射线的计算，所以精度并没有受到影响。
表1 传统方法与加速方法仿真所需求交面数和使用时间比较
5 结论
本文根据分析射线的特性提出一种将地形分区的方法，该方法可以减少求交运算中需要运算的面的个数，从而减少了计算求交运算的时间；同时使用多线程技术提高计算机资源利用率，并在多核cpu下提高计算效率。仿真比较结果表明，该方法在复杂的地形中可以有效地减少计算量，降低计算的时间，提高了射线跟踪法的计算效率，因此有一定研究意义。
[1] Torres R P, Valle L, Domingo M, Loredo S.An efficient raytracing method for radio propagation based on the modif ed BSP algorithm.Vehicular Technology Conference,1999.P 1967～1971.
[2] LIU Hai-tao, LI Bin-hong, XIE Yong, QI Dong-sheng. Parallel raytracing algorithm and its application for propagation prediction in urban micro cellular environments[J]. CHINESE JOURNAL OF RADIO SCIENCE ,2004,19(5):P 581～585.
[3] 刘斐. 电波传播射线追踪法的研究[J]. 信息与电脑,2011, 2, P160.
[4] Chen Shin-Hon, Jeng Shyh-kang.An SBR/Image approach for radio wave propagation indoor environments with metallic furniture[J].IEEE Transaction on Antennas and Propagation,1997,45（1）:P 98-106.
[5] Tan S Y, Tan H S. A microcelluar communications propagation model based on the uniform theory of diffraction and multiple image theory[J]. IEEE Transactions on Antennas and Propagation,1996,44（10）:P 1317-1326.
[6] 袁正午，黎意超，李林，沐维. 基于动态分区的射线跟踪加速方法[J].计算机工程与应用, 2010, 46（27): P 77-79.
[7] 董金梁,金荣洪,耿军平,王伟. 改进射线跟踪法效率的新方法[J].微波学报 2006, 22(6):P6-9.
