论文研究-基于历史缓存技术的射线跟踪加速算法研究.pdf
需积分: 0 119 浏览量
2019-07-22
21:00:18
上传
评论
收藏 551KB PDF 举报
收稿日期： ２０１０唱０６唱２２； 修回日期： ２０１０唱０７唱２６ 基金项目： 国家“８６３” 计划资助项目（２００７ＡＡ１２Ｚ２２６）
作者简介：袁正午（１９６８唱） ，男，湖南人，教授，博士，主要 研 究 方向 为 ＬＢＳ、移 动 定位、射 线 跟踪、ＧＩＳ 系统 集成 （ ｙｕａｎｚｗ ＠ｃｑｕｐｔ．ｄｅｕ．ｃｎ） ； 沐 维
（１９８５唱），男，四川人，硕士研究生，主要研究方向为电磁场数值计算、射线跟踪；黎 意超（ １９８５唱） ，男，广西人，硕 士研究生，主要研究方 向 为射线跟
踪；李林（１９８５唱） ，男，广西人，硕士研究生，主要研究方向为 ＧＩＳ 系统集成、移动定位．
基 于 历 史 缓 存 技 术 的 射 线 跟 踪 加 速 算 法 研 究
倡
袁正午， 沐 维， 黎意超， 李 林
（重庆邮电大学 计算机科学与技术学院 中韩合作 ＧＩＳ 研究所， 重庆 ４０００６５）
摘 要： 通过分析影响射线跟踪效率的因素，提出一种基于历史缓存技术的射线跟踪加速算法，以提高射线跟
踪的运算效率。 通过建立一个缓存区存储历史信息，用来减少每条射线必须处理的建筑物面的数量和减少计算
无效的交点。 对提出的算法进行仿真计算，仿真结果证明了这种算法的正确性，有效降低了计算的复杂度。
关键词： 射线跟踪； 历史缓存； 求交运算； 加速算法
中图分类号： ＴＮ０１１； ＴＰ３０１畅６ 文献标志码： Ａ 文章编号： １００１唱３６９５（２０１０）１２唱４７２９唱０３
ｄｏｉ：１０．３９６９ ／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１０．１２．０９６
Ｎｅｗ ａｃｃｅｌｅｒａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｒａｙ ｔｒａｃｉｎｇ ｂａｓｅｄ ｏｎ ｈｉｓｔｏｒｙ ｂｕｆｆｅｒ
ＹＵＡＮ Ｚｈｅｎｇ唱ｗｕ， ＭＵ Ｗｅｉ， ＬＩ Ｙｉ唱ｃｈａｏ， ＬＩ Ｌｉｎ
（Ｓｉｎｏ唱Ｋｏｒｅａ ＧＩＳ Ｒｅｓｅａｒｃｈ Ｃｅｎｔｒｅ， Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ＆ Ｔｅｃｈｎｏｌｏｇｙ， Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｃｈｏｎｇｑｉｎｇ ４０００６５ ， Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ： Ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ ｆａｃｔｏｒｓ ａｆｆｅｃｔｉｎｇ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｒａｙ ｔｒａｃｉｎｇ，ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｅｄ ａ ｎｅｗ ａｃｃｅｌｅｒａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｒａｙ
ｔｒａｃｉｎｇ ｂａｓｅｄ ｏｎ ｈｉｓｔｏｒｙ ｂｕｆｆｅｒ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｒａｙ唱ｔｒａｃｉｎｇ ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ｒｅｄｕｃｅ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｉｎｔｅｒ唱
ｓｅｃｔｉｏｎ ｃａｌｃｕｌａｔｉｏｎ ｂｅｔｗｅｅｎ ｒａｙ ａｎｄ ｆａｃｅｓ ｂｙ ｕｓｉｎｇ ａ ｂｕｆｆｅｒ ｔｏ ｓｔｏｒｅ ｔｈｅ ｈｉｓｔｏｒｉｃａｌ ｉｎｆｏｒｍａｔｉｏｎ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｓｉｍｕｌａｔｉｏｎ， ａｎｄ
ｒｅｓｕｌｔｓ ｖｅｒｉｆｙ ｔｈｅ ｖａｌｉｄｉｔｙ ｏｆ ｔｈｅ ｍｅｔｈｏｄ ｗｈｉｃｈ ｅｆｆｅｃｔｉｖｅｌｙ ｒｅｄｕｃｅｓ ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｃａｌｃｕｌａｔｉｏｎｓ．
Ｋｅｙ ｗｏｒｄｓ： ｒａｙ ｔｒａｃｉｎｇ； ｈｉｓｔｏｒｙ ｂｕｆｆｅｒ； ｉｎｔｅｒｓｅｃｔｉｏｎ ｃａｌｃｕｌａｔｉｏｎ； ａｃｃｅｌｅｒａｔｅｄ ａｌｇｏｒｉｔｈｍ
０ 引言
随着移动通信技术的迅猛发展，移动通信用户越来越多。
为了增加通信的容量，小区分裂得越来越小，无线电波传播的
环境也越来越恶劣，同时对话务质量的要求也越来越高。 精确
预测电波传播特性在移动通信系统设计中尤为重要。 电波传
播预测方法大体分为实测统计方法和确定性方法两类。 在微
蜂窝或微微蜂窝移动通信系统中，发射天线处在较低位置，这
时用统计方法得到的经验模型就不再适用，而需使用确定性方
法来预测。
基于几何光学（ＧＯ）
［１］
和一致绕射理论（ ＵＴＤ）
［２］
的射线
跟踪法是确定性方法中较为有效的一种，被广泛用于移动通信
和个人通信环境中的无线电波预测中。 通过射线跟踪辨认出
多径信道中收发点之间所有可能的射线路径。 所有可能的射
线被识别之后，根据电波传播理论计算每条射线的幅度、相位
和极化信息，从而用来进行蜂窝网网络设计、基站选址和网络
优化
［３］
。 由于电波传播环境的复杂性，射线跟踪计算量很大，
大部分的时间都用来求交点运算。 即使采用一些加速算法，如
二叉树分区法、角度分区法及并行处理等，可以提高射线跟踪
算法的效率，但大部分时间还是用于求交点计算
［４］
。 针对上
述问题，提出一种用缓存技术存储历史信息以减少求交点的次
数，使得射线跟踪更加快捷有效。
１ 射线跟踪基本原理
射线跟踪方法是通过模拟射线的传播路径来确定反射、绕
射线路，其应用条件是高频率或短波长。 现在移动通信系统的
工作频率一般比较高，城市微小区环境中的建筑物等散射体的
尺寸远大于电波波长。 此时可以利用几何光学的分析方法来
处理电磁波的传播和散射问题。 射线跟踪的基本思想是：将发
射点视为源点，从源点出发，向周围空间均匀发出大量的射线
束，分别跟踪每条射线束的路径。 射线跟踪过程实际就是射线
与物体进行求交判断的过程。 在遇到阻碍物时产生反射射线
或绕射射线，然后继续追踪，如此递归下去，直到射线强度降到
门限以下或不再发生相交为止。 找出所有到达接收点射线的
传播路径后根据菲涅尔等式和几何绕射理论等，确定反射和绕
射损耗，再将到达接收点的所有路径的场强作相干叠加，从而
实现电波传播预测。
在接收点计算场强时，为了避免由于模型的不精确带来接
收点场强的突变，一般要计算接收点附近一些点的场强，用来
和接收点的值进行平均。 文献［５］ 对此作了大量的探讨。 在
接收点的总场强可以表示为
ｓ（ ｘ，ｙ） ＝钞
Ｎ
ｎ ＝１
ｕ
ｎ
ｅｘｐ［ ｊｋ（ ｘ ｃｏｓ φ
ｎ
＋ｙ ｓｉｎ φ
ｎ
） ＋ｊ矱
ｎ
］ （１）
其中：φ
ｎ
为到达接收点的第 ｎ 个电磁波到达角，电场幅度为
ｕ
ｎ
，相位为 矱
ｎ
（ ｎ ＝１，２，…，Ｎ）；ｋ 为自由空间的波数。 当电磁
波的幅度和相位在区域 Ｓ 内不变或变化很小时，可得式（１）。
这样可以得到接收点的接收功率为
ｐ（ ｘ，ｙ） ＝｜ｓ（ ｘ，ｙ） ｜
２
（２）
２ 历史缓存技术的射线跟踪算法概述
在复杂的环境中，使用传统的射线跟踪算法，射线—平面
第 ２７ 卷第 １２ 期
２０１０ 年 １２ 月
计 算 机 应 用 研 究
Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ
Ｖｏｌ．２７ Ｎｏ．１２
Ｄｅｃ．２０１０
资源评论
