一种射线追踪方法转让专利
申请号 : CN202010233725.0
文献号 : CN111490952B
文献日 : 2021-08-17
发明人 : 陈亮 , 纪腾飞 , 王健 , 黄翔东
申请人 : 陈亮
摘要 :
本发明公开了一种射线追踪方法，所述方法包括以下步骤：导入场景数据，确定传播射线路径；根据蚁群算法在传播射线路径中获取优势路径；设定误差阈值；多线程并行加速，在满足误差阈值的前提下输出最优射线路径及传播损耗值；其中，所述根据蚁群算法在传播射线路径中获取优势路径具体为：根据蚁群算法统计优势射线路径组合方案；建立禁忌表存放蚁群算法遍历后的优势射线路径组合方案；在禁忌表中寻找最优射线路径组合方案。本发明在保证精度的前提下，减少射线在场景中的遍历时间，选取优势射线替代所有射线；提高射线追踪的适用性，预测复杂场景的信道特性。
权利要求 :
1.一种射线追踪方法，其特征在于，所述方法包括以下步骤：导入场景数据，确定传播射线路径；根据蚁群算法在传播射线路径中获取优势路径；
设定误差阈值；根据多线程并行计算能力，加速射线在场景中的遍历过程，在满足误差阈值的前提下输出最优射线路径及传播损耗值；
其中，所述根据蚁群算法在传播射线路径中获取优势路径具体为：根据蚁群算法统计优势射线路径组合方案；建立禁忌表存放蚁群算法遍历后的优势射线路径组合方案；
在禁忌表中寻找最优射线路径组合方案；
所述在满足误差阈值的前提下输出最优射线路径及传播损耗值具体为：在禁忌表中选择射线路径组合得到方案φ1,φ2,...,φL，并计算方案φ1,φ2,...,φL‑1中的射线路径组合损耗值Plir；
将方案φ1,φ2,...,φL‑1与φL的路径损耗进行比较，在保证误差ε＝|Plir‑PlL1|满足0＜ε≤εr的情况下，找到误差最小方案的优势射线组合，即为最终确定的优势射线路径。
2.根据权利要求1所述的一种射线追踪方法，其特征在于，所述导入场景数据，确定传播射线路径具体为：
根据场景物理结构确定1条直达径L0，F条一次反射路径L11、L12、…L1F，S条二次反射路径L21、L22、…L2S，…，N条M次反射路径LM1、LM2、…，LMN，其中Lpq代表p次反射的第q条路径，则场景环境中的射线传播总路径条数L：
3.根据权利要求1所述的一种射线追踪方法，其特征在于，所述建立禁忌表存放蚁群算法遍历后的优势射线路径组合方案具体为：分别存放射线直达路径、按接收射线能量从高到低排列的一次反射路径、二次反射路径、…、M次反射路径。
说明书 :
一种射线追踪方法
技术领域
[0001] 本发明涉及通信中的信道估计领域，尤其涉及一种射线追踪方法。
背景技术
[0002] 无线通信系统的研究与开发需要对信道特性有广泛的了解，射线追踪是预测信道特性的一种有效方法。由于完全基于电波传播的物理原理，射线追踪法适用于各类特定场
景的电波传播仿真。
景的电波传播仿真。
[0003] 国外研究人员Eamonn M.Kenny和Eamonn O.Nuallain提出了一种基于点对多点的[1]
三维凸空间射线追踪技术 ，将室内建筑模型划分为自由填充的凸空间，生成一种可计算
和存储的可见性列表，得到一种有效的图像反射和衍射路径生成算法，和传统的射线追踪
技术相比，该技术可以有效地优化基站收发器的位置，并且具有很高的计算效率；Hossein
[2]
Azodi，Uwe Siart以及ThomasF.Eibert等人提出了一种确定性射线追踪模拟器 ，通过体
素化技术定义被测几何图形，提高了这种射线追踪器的灵活性。其光照矩阵能够识别所有
观测点的贡献射线，并简化场强叠加的计算过程。由于使用了大小相同的矩阵，避免了循环
计数，提高了射线追踪的计算效率；在参考文献[3]中，Andres Navarro提出了一种基于接
收球的新技术，在保证精度的前提下，结合数值方法和三维射线追踪模型模拟室内环境中
的多径传播，大幅度提高了射线追踪的追踪效率。
三维凸空间射线追踪技术 ，将室内建筑模型划分为自由填充的凸空间，生成一种可计算
和存储的可见性列表，得到一种有效的图像反射和衍射路径生成算法，和传统的射线追踪
技术相比，该技术可以有效地优化基站收发器的位置，并且具有很高的计算效率；Hossein
[2]
Azodi，Uwe Siart以及ThomasF.Eibert等人提出了一种确定性射线追踪模拟器 ，通过体
素化技术定义被测几何图形，提高了这种射线追踪器的灵活性。其光照矩阵能够识别所有
观测点的贡献射线，并简化场强叠加的计算过程。由于使用了大小相同的矩阵，避免了循环
计数，提高了射线追踪的计算效率；在参考文献[3]中，Andres Navarro提出了一种基于接
收球的新技术，在保证精度的前提下，结合数值方法和三维射线追踪模型模拟室内环境中
的多径传播，大幅度提高了射线追踪的追踪效率。
[0004] 国内研究人员在参考文献[4]中提出了一种局部口面网格优化算法，将射线管总口面划分为局部口面网格，在每局部口面上抽取采样射线管用于判断其贡献级别，并由计
算级别决定是否对局部口面内的射线管进行实际计算，从而避免了大量的无贡献射线管参
与求交计算，节省了射线求交运算时间；参考文献[5][6]分别提出了以捷径法和邻域辅助
径迹法提高射线追踪效率，捷径法通过实际计算并记录一条射线管的轨迹，作为其后若干
条射线管求交计算的优先参考，避免了再次进行漫无目的的遍历式求交，从而大量减少进
行实际计算的射线管数量；邻域径迹辅助法在普通径迹法的基础上进行了改善，针对面元
形式的目标数据，从提高入射点求解的成功率着手，采用增加对参考路径上参考面元的相
邻单元进行相交计算，克服了普通径迹法对射线管划分密度的依赖性；参考文献[7]利用
Gmsh软件把三维室内环境剖分成若干个无缝并且互不重叠的四面体单元，通过研究射线在
各个四面体中的穿行轨迹，进而可以得到每条射线在整个室内环境中的追踪轨迹。文中提
出的场分布快速算法在射线追踪的过程中，不需要和环境中的多面体面进行相交测试，因
此提高了计算效率；参考文献[8]介绍了一种多边形三角化算法，旨在射线发射之前对无效
射线进行滤除，在保证精度的同时，大幅度提高了射线追踪的计算效率。
算级别决定是否对局部口面内的射线管进行实际计算，从而避免了大量的无贡献射线管参
与求交计算，节省了射线求交运算时间；参考文献[5][6]分别提出了以捷径法和邻域辅助
径迹法提高射线追踪效率，捷径法通过实际计算并记录一条射线管的轨迹，作为其后若干
条射线管求交计算的优先参考，避免了再次进行漫无目的的遍历式求交，从而大量减少进
行实际计算的射线管数量；邻域径迹辅助法在普通径迹法的基础上进行了改善，针对面元
形式的目标数据，从提高入射点求解的成功率着手，采用增加对参考路径上参考面元的相
邻单元进行相交计算，克服了普通径迹法对射线管划分密度的依赖性；参考文献[7]利用
Gmsh软件把三维室内环境剖分成若干个无缝并且互不重叠的四面体单元，通过研究射线在
各个四面体中的穿行轨迹，进而可以得到每条射线在整个室内环境中的追踪轨迹。文中提
出的场分布快速算法在射线追踪的过程中，不需要和环境中的多面体面进行相交测试，因
此提高了计算效率；参考文献[8]介绍了一种多边形三角化算法，旨在射线发射之前对无效
射线进行滤除，在保证精度的同时，大幅度提高了射线追踪的计算效率。
[0005] 综上所述，国内外研究人员通过减少模型与射线基元的相交时间、相交数量等方法提高了射线追踪的计算效率，降低了复杂度。然而，以上改善技术均发射了许多条射线，
增加了射线在场景中的遍历时间。
增加了射线在场景中的遍历时间。
[0006] 参考文献
[0007] [1]Kenny E M,Nuallain E O.Convex space building discretization for ray‑tracing[J].IEEE Transactions on Antennas and Propagation,2017,65(5):2578‑
2591.
2591.
[0008] [2]Azodi H,Siart U,Eibert T F.A fast 3‑D deterministic ray tracing coverage simulator including creeping rays based on geometry voxelization
technique[J].IEEE Transactions on Antennas and Propagation,2015,63(1):210‑
220.
technique[J].IEEE Transactions on Antennas and Propagation,2015,63(1):210‑
220.
[0009] [3]Navarro A,Guevara D,Gómez J.A Proposal to Improve Ray Launching Techniques[J].IEEE Antennas and Wireless Propagation Letters,2018,18(1):143‑
146.
146.
[0010] [4]黄沛霖,武哲.一种射线追踪法的效率改进算法研究[J].北京航空航天大学学报,2003,29(7):607‑610.
[0011] [5]黄沛霖,王钢林,武哲.以捷径法提高射线追踪效率[J].北京航空航天大学学报,2004,30(5):425‑428.
[0012] [6]黄敏杰,李葳,武哲.邻域辅助径迹法提高射线追踪效率[J].北京航空航天大学学报,2007,33(3):298‑301.
[0013] [7]黄自强.射线追踪场分布的快速计算与实现[D].南京邮电大学,2015.
[0014] [8]邹新龙.射线追踪室内算法的改进研究[D].北京邮电大学,2015.
发明内容
[0015] 本发明提供了一种射线追踪方法，本发明在保证精度的前提下，减少射线在场景中的遍历时间，选取优势射线替代所有射线；提高射线追踪的适用性，预测复杂场景的信道
特性，详见下文描述：
特性，详见下文描述：
[0016] 一种射线追踪方法，所述方法包括以下步骤：
[0017] 导入场景数据，确定传播射线路径；根据蚁群算法在传播射线路径中获取优势路径；
[0018] 设定误差阈值；多线程并行加速，在满足误差阈值的前提下输出最优射线路径及传播损耗值；
[0019] 其中，所述根据蚁群算法在传播射线路径中获取优势路径具体为：
[0020] 根据蚁群算法统计优势射线路径组合方案；建立禁忌表存放蚁群算法遍历后的优势射线路径组合方案；
[0021] 在禁忌表中寻找最优射线路径组合方案。
[0022] 其中，所述导入场景数据，确定传播射线路径具体为：
[0023] 根据场景物理结构确定1条直达径L0，F条一次反射路径L11、L12、…L1F，S条二次反射路径L21、L22、…L2S，…，N条M次反射路径LM1、LM2、…，LMN，其中Lpq代表p次反射的第q条路径，
则场景环境中的射线传播总路径条数L：
则场景环境中的射线传播总路径条数L：
[0024]
[0025] 其中，所述建立禁忌表存放蚁群算法遍历后的优势射线路径组合方案具体为：
[0026] 分别存放射线直达路径、按接收射线能量从高到低排列的一次反射路径、二次反射路径、…、M次反射路径。
[0027] 进一步地，所述在满足误差阈值的前提下输出最优射线路径及传播损耗值具体为：
[0028] 在禁忌表中选择射线路径组合得到方案φ1,φ2,...,φL，并计算方案φ1,φ2,...,φL‑1中的射线路径组合损耗值Plir；
[0029] 将方案φ1,φ2,...,φL‑1与φL的路径损耗进行比较，在保证误差ε＝|Pir‑PL1|满足0＜ε≤εr的情况下，找到误差最小方案的优势射线组合，即为最终确定的优势射线路径。
[0030] 本发明提供的技术方案的有益效果是：
[0031] 1)本发明通过蚁群算法选取2～3条优势射线路径替代所有的传播路径，结合多线程并行计算技术，在保证精度的同时，减少射线发射条数，大大提高了射线追踪的速度，降
低了复杂度；
低了复杂度；
[0032] 2)采用传统的射线追踪法预测复杂场景信道特性时，将会产生n(n>>+∞)条射线2
路径，计算复杂度为O(n)，国内外研究学者通过减少模型与射线基元相交时间、相交数量
等方法将复杂度逐渐降低到O(n)及目前的O(logn)。本发明通过蚁群算法选取优势射线路
径，将复杂度降低至O(log2)～O(log3)；
路径，计算复杂度为O(n)，国内外研究学者通过减少模型与射线基元相交时间、相交数量
等方法将复杂度逐渐降低到O(n)及目前的O(logn)。本发明通过蚁群算法选取优势射线路
径，将复杂度降低至O(log2)～O(log3)；
[0033] 3)根据蚁群算法改进的射线追踪技术，加速了5G或未来6G不同通信场景的信道特性预测，在通信中的信道估计领域具有很大工程应用价值。
附图说明
[0034] 图1为一种射线追踪方法的流程图；
[0035] 图2为根据蚁群算法确定优势路径的流程图；
[0036] 图3为多线程并行加速流程图；
[0037] 图4为室内二维环境模型；
[0038] 图5为室内三维环境模型；
[0039] 图6为室内射线追踪路径；
[0040] 图7为室内单接收点射线追踪路径；
[0041] 图8为室内单接收点优势射线追踪路径。
具体实施方式
[0042] 为使本发明的目的、技术方案和优点更加清楚，下面对本发明实施方式作进一步地详细描述。
[0043] 实施例1
[0044] 一种射线追踪方法，参见图1，该方法包括以下步骤：
[0045] 步骤101：导入场景数据，确定传播射线路径；
[0046] 步骤102：参见图2，根据蚁群算法在传播射线路径中获取优势路径，具体步骤如下：
[0047] 1)根据蚁群算法统计优势射线路径组合方案；
[0048] 2)建立禁忌表存放蚁群算法遍历后的优势射线路径组合方案；
[0049] 3)在禁忌表中寻找最优射线路径组合方案。
[0050] 步骤103：设定误差阈值；
[0051] 步骤104：参见图3，多线程并行加速，在满足误差阈值的前提下输出最优射线路径及传播损耗值。
[0052] 实施例2
[0053] 下面结合图1至图8对实施例1中的方案进行进一步地介绍，详见下文描述：
[0054] 步骤A：综合考虑各种通信应用场景，采用建模工具对实测场景进行三维建模，统计场景环境中的材质及其相对介电常数、导磁系数等电磁参数，导入电磁仿真软件或编程
软件进行建模仿真。如图4、图5所示，搭建室内环境模型：
软件进行建模仿真。如图4、图5所示，搭建室内环境模型：
[0055] 表1室内环境下不同材质电磁参数
[0056] 材质 导磁系数 相对介电常数 厚度地板和天花板 0.01 9 15.0
墙体 0.01 9 10.0
‑5
门 10 13 4.0
‑5
桌子 10 13 2.0
‑12
窗户 10 7.6 1.0
墙体 0.01 9 10.0
‑5
门 10 13 4.0
‑5
桌子 10 13 2.0
‑12
窗户 10 7.6 1.0
[0057] 表2天线参数设置
[0058]
[0059] 步骤B：根据场景物理结构确定可能出现的1条直达径L0，F条一次反射路径L11、L12、…L1F，S条二次反射路径L21、L22、…L2S，…，N条M次反射路径LM1、LM2、…，LMN，其中Lpq代表p
次反射的第q条路径，则场景环境中的射线传播总路径条数L：
次反射的第q条路径，则场景环境中的射线传播总路径条数L：
[0060]
[0061] 步骤C：根据蚁群算法确定优势路径。
[0062] 根据蚁群算法中路径信息量感知原理，信息素浓度最高的路径组合方案最优，因此在保证精度的前提下，可以找到一部分优势射线路径替代所有传播路径。
[0063] 步骤C1：进行优势射线的选取时，应统计出所有可能出现的射线路径传播方案。根据排列组合原理，从L条路径中选择1条路径传播时对应 种选择方案φ1：φ1
＝[{L0},{L11},{L12},…,{LMN}]；
＝[{L0},{L11},{L12},…,{LMN}]；
[0064] 同理，从L条路径中选择2条路径传播时对应 种选择方案φ2：φ2＝[{L0,L11},{L0,L12},…,{LM(N‑1),LMN}]，…，从L条路中选择L条路径传播时对应
种选择方案φL：φL＝[{L0,L11,L12,…LMN}]，因此共有
种路径选择方案φ：φ＝[φ1,φ2,...,φL]。
种选择方案φL：φL＝[{L0,L11,L12,…LMN}]，因此共有
种路径选择方案φ：φ＝[φ1,φ2,...,φL]。
[0065] 步骤C2：设定误差阈值εr，用于判定最优射线组合方案；
[0066] 步骤C3：建立L个相互独立的禁忌表Chart0,Chart1,…,ChartM，分别存放根据蚁群算法遍历完成后的射线直达路径、按接收射线能量从高到低排列的一次反射路径、二次反
射路径、…、M次反射路径。
射路径、…、M次反射路径。
[0067] 步骤C4：根据选择方案φ在禁忌表Chartj(0≤j≤M)中选择射线路径组合得到方案φ1,φ2,...,φL；并计算方案φ1,φ2,...,φL‑1中的射线路径组合损耗值Plir；
[0068] 其中，(i＝1,2,…,L‑1； )；将方案φ1,φ2,...,φL‑1与φL的路径损耗进行比较，在保证误差ε＝|Pir‑PL1|满足0＜ε≤εr的情况下，找到误差最小方案
的优势射线组合，即为最终确定的优势射线路径。
的优势射线组合，即为最终确定的优势射线路径。
[0069] 设定误差阈值|εr|＝1dB，根据蚁群算法得到室内最优射线路径如图8所示。
[0070] 步骤D根据多线程并行计算能力，加速射线在场景中的遍历过程，其原理见图3。
[0071] 步骤E如表3所示，输出遍历场景后的优势射线及传播的路径损耗值。
[0072] 表3单个接收点射线路径及损耗
[0073]
[0074] 本领域技术人员可以理解附图只是一个优选实施例的示意图，上述本发明实施例序号仅仅为了描述，不代表实施例的优劣。
[0075] 以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。