一种基于虚拟墙的射线跟踪法

周 林，雒 芳，杨龙频

(1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.北京医院，北京 100730)

一种基于虚拟墙的射线跟踪法

周 林1，雒 芳1，杨龙频2

(1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.北京医院，北京 100730)

针对现有射线跟踪算法效率低下的问题，利用虚拟源思想，设计了一种基于虚拟墙的射线跟踪算法。首先，通过将处于同一平面的墙面合并为“虚拟墙”，降低了算法搜索过程中墙面的遍历次数。在此基础上，通过设计“透光区”、“光扇区”等有效性判决条件，完成节点有效性的判决，避免了无效节点的混入，减少了计算复杂度。最后，利用深度优先搜索算法完成虚拟源树状结构的建立，无须重复遍历即可获得发射点到接收点的全部有效路径。仿真结果表明，该算法路径损耗的预测精度随着树遍历深度的增加而提高，同时降低了算法复杂度。

射线跟踪；虚拟墙；深度优先；遍历

近年来，随着移动通信技术和通信业务的快速发展，通信频谱资源越来越紧缺，微蜂窝、微微蜂窝系统采用频率复用[1]技术降低了基站发射功率，提高了频率利用率，得到了广泛应用。在微蜂窝系统下，原有的无线电波大区传播模型不再适用，基于几何光学(GTO)和一致绕射理论(UTD)[2]的射线跟踪法是一种运用于微小区环境的无线电波传播特性预测技术[3-4]。

目前，射线跟踪法的研究可分为两类：正向射线跟踪法和反向射线跟踪法。正向射线跟踪法采用发射角量化将发射射线从无穷转换成有限多，通过追踪每一根射线的路径，并判断其能否到达接收方，以获得最终有效路径，但是需要在接收点设置接收球进行接收测试，发射角量化间隔和接收球半径大小都会影响接收误差，从而使算法的精度受到影响。反向射线跟踪法利用几何光学的镜像原理求发射源的多级镜像点，得到镜像树，然后从接收点出发，根据几何光学原理，反向追踪每一条能从源点到达场点的路径，能够模拟所有可达的射线路径，得到了广泛应用和研究[5-7]。但是，在街道等现实建筑物场景中，多个墙面往往处于同一水平面上，墙面的镜像点是相同的，无须重复搜索，上述反向射线跟踪算法没有考虑这种普遍情况下墙面的重复搜索问题，造成了算法复杂度的增大。针对这一问题，本文设计了一种基于虚拟墙的射线跟踪算法，通过将多个墙面合并为“虚拟墙”进行统一搜索，降低了墙面的遍历次数。通过设计透光区和光扇区辅助完成节点有效性的判决。在此基础上，利用深度优先搜索算法，完成虚拟源树状结构的建立，获得所有有效路径，提高了已有射线跟踪模型的效率。

1 传统的传播模型建模过程

1.1 城市模型

无线电波传播模型一般分为二维模型和三维模型两种，本文研究的环境是城市微蜂窝环境，收发天线低于周围环境建筑物的高度，可以忽略从建筑物顶部绕射到接收天线的射线[8-10]，因此这种情况下，射线跟踪预测可以直接在城市的二维空间图中进行，从而只考虑两种传播机制：反射和绕射。本文选取的实例是加拿大渥太华市中心的核心俯视图[11]，如图1所示，建筑群被划分为一定的“块”，建筑物则被定义为“多边形”，多边形的“边”代表建筑物的表面，多边形的“顶点”则代表建筑物的拐角。这种简化了的市区平面图大致反映出城市的主体结构，利用它进行射线跟踪，可以得到较为准确的路径损耗。

图1 渥太华市区部分区域二维视图

1.2 基于虚拟源的射线跟踪法

在对城市模型进行建模的基础上，射线跟踪法能够快速确定从发射节点到接收节点的所有传播路径。如图2所示，首先，定义三类源，即发射源、镜像源和绕射源。虚拟源包括镜像源和绕射源。建立虚拟源树结构以及计算每个源的有效性[12]是该算法的关键。基于虚拟源的射线跟踪算法的思想是：在射线跟踪时，电波从源点出发，除直射波外，其他的射线都要经过反射或绕射才能到达场点，所有传播路径都是墙面反射和边缘绕射的组合。这个过程中，射线经过的反射面和绕射边缘可以用树结构图来记录。但是，基于虚拟源的射线跟踪算法镜像源的数目随墙面个数呈幂指数增长，这增加了镜像源的遍历次数，造成算法复杂度增大。

1.3 路径损耗的计算

假设发射机天线是垂直放置的电偶极子，接收天线是具有垂直极化特性的天线，电磁波以球面波的形式向外传播。

图2 源类型示意图

在实际应用中，电波会遇到森林、山丘、地面、楼房等高大建筑物，绝大多数射线在到达接收点之前要经过多次反射和绕射。射线到达接收点的电场强度用以下公式计算

(1)

(2)

2 基于虚拟源的射线跟踪法加速算法

基于虚拟源的射线跟踪算法复杂度较高，且反射源的数目随墙面个数呈幂指数增长的关系。本文从两方面进行了改进：1)针对反射过程，利用“虚拟墙”概念，减少搜索墙面的个数，利用“透光区”、“光扇区”等概念辅助算法设计完成节点有效性的判决，避免了无效节点的混入，减少了计算复杂度；2)利用深度优先的搜索算法，完成虚拟源树状结构建立的同时，获得有效路径，无须再次遍历，从而提高算法效率。

2.1 虚拟墙、透光区、光扇区的构造

1)虚拟墙

本文利用了墙壁“虚拟合并”的思想，将同一条直线上的墙壁被视为“相同”(如图1中曲线所示)，而原先的墙仅仅是该“虚拟墙”的一个可达面。这是因为节点关于这些墙壁的镜像点都重合，无需重复搜素。如表1所示，合并后的虚拟墙面数比真实墙面减少了40%，大大减少了算法后续遍历的复杂度。而在现实中的城市规划布局中，街道建筑往往也具有这种平整性，因此虚拟墙的概念具有一定的应用价值。虚拟墙虽然降低了墙面的遍历次数，但也增加了无效节点的混入。本文通过引入透光区和光扇区，最大限度地抑制无效节点的混入。

表1 虚拟合并前后的墙壁数目对比

2)透光区

镜像节点是源节点关于真实墙面对称的虚拟源，其本身并不发出射线。如图3所示，若源节点发出的射线被遮挡，则仅有部分墙面能够收到光线，称这部分区域为该墙面的透光区。可以看出3种墙面面积之间的关系为：透光区≤真实墙≤虚拟墙。

图3 概念示意图

3)光扇区

虚拟源与其相应透光区的连线扫过的区域，会形成如图所示的扇区，称其为光扇区。只有光扇区内的墙面才有可能产生下一次反射。利用光扇区的这一特性，能够进一步减少遍历墙面的个数。

2.2 虚拟源多叉树的建立

本文通过构造虚拟源多叉树对可达路径进行搜索，并利用深度优先算法进行加速。射线跟踪过程由反射过程和绕射过程级联组成，在反射过程中，根据上述辅助概念，设计多叉树下一级镜像节点或绕射节点的有效性判决条件(加入树的充要条件)。

镜像节点加入树的充要条件为：该节点对应的虚拟墙(反射墙)中至少有一点处于透光区，且该点与虚拟源节点之间无遮拦物存在。

绕射节点加入树的充要条件是绕射点在虚拟源相应的光扇区内，且绕射点与虚拟源之间无遮拦。

在绕射过程中，绕射节点和发射节点相同，均可向所有有效区域发射射线，如图2所示，绕射源的有效区域为建筑物拐角外的区域，因此当绕射节点加入搜索树之后，将绕射节点当作发射源，搜索下一级有效节点。在此基础上，如图4所示，采用深度优先算法，建立虚拟源多叉树，树的每一个分支代表一个路径，若当前路径能够到达接收节点，则为有效路径。

2.3 改进算法的实现步骤

加速算法的实现步骤如图5所示，在传统的射线跟踪算法基础上，加入改进的节点有效性判决模块，以此来加速搜索过程，节点有效性判决模块包括镜像节点有效性判决和绕射节点有效性判决。

图4 虚拟源树示意图

图5 改进算法的流程图

3 仿真分析

选取图1所示的建筑物街道模型，分别设置发射点坐标为(300，230)，接收点坐标设置为(500，200)，对所提加速算法进行仿真。图6显示了存在最多7次反射和最多2次绕射的全部路径，图7和图8显示路径是图6的子集。观察发现图7中射线条数明显少于图8，并且图6射线主要是通过绕射实现，由此可判断当发射节点和源节点不存在直射路径时，射线主要通过绕射才能到达接收节点。

由于无线电波在传输过程中，会随传输距离的增大、反射绕射次数的增多而衰减，为了限定仿真规模，本文设置当只有反射时，最多存在7次发射；当既有反射又有绕射时，最多存在3次反射和1次绕射。按照文献[14]所示的无线电波路径损耗、反射、绕射衰减模型，设置无线电波频率为1GHz，墙面的相对介电常数为9、电导率为0.1S/m，地面的相对介电常数为15，电导率为7S/m。固定发射点位置为(500，220)，分别对图9所示的接收点位置的接收信号强度进行仿真计算。

图6 最多7次反射和最多2次绕射的全部路径

图7 最多2次反射和最多1次绕射的全部路径

图8 最多1次反射和最多2次绕射的全部路径

图9 接收点坐标设置图

如图10所示，仿真1中限定最大反射次数为4，最大绕射次数为1来计算各接收点处路径损耗；仿真2限定最大反射次数为7，最大绕射次数为3。仿真规模随可允许的发射和绕射次数增加而增大，此时仿真的精度也随之提高，仿真结果接近实际测量值。并且路径损耗随接收点的位置改变而改变，当接收点被建筑物遮挡较多时，路径衰减较大，当接收点被建筑物遮挡较多时，路径衰减较小。在路口位置，由于存在丰富的绕射环境，路径衰减相对较小。因此，为了增大基站的覆盖范围，可以将基站布设在路口位置。

图10 图9中各接收点位置的路径损耗仿真图

4 小结

本文针对射线跟踪法复杂度高的问题，利用虚拟墙合并方法、“透光区”、“光扇区”等辅助判决概念，减少了节点有效性判决中墙面的遍历次数。利用深度优先的搜索算法完成虚拟源树状结构的建立，提高了基于虚拟源的射线跟踪模型的预测效率。仿真结果表明，算法路径损耗的预测精度随着树遍历深度的增加而提高，能够用于任何复杂的传播环境。

[1]曹鹏，彭华，张金成.频率选择性衰落信道下OFDM子载波数盲估计[J].电视技术，2011，35(3)：67-70.

[2]贺之莉，黄锴，蒋晓博，等.一种稳定高效的NURBS建模MOM-PO法[J].西安电子科技大学学报：自然科学版，2012，39(3)：56-61.

[3]SONG H B，WANG H G，HONG K，et al.A novel source localization scheme based on unitary esprit and city electronic maps in urban environments[J].Progress In Electromagnetics Research，2009(94)：243-262.

[4]王利东.三维城市环境下电波场强预测加速模型研究[D].长沙：湖南科技大学，2012.

[5]廖斌，赵昵丽，朱守正.基于虚拟源树的射线跟踪算法的研究[J].华东师范大学学报：自然科学版，2008(3)：103-108.

[6]李朝奎，王利东，李拥，等.一种利用镜像理论的射线跟踪改进算法[J].武汉大学学报：信息科学版，2012，37(7)：784-788.

[7]刘忠玉，郭立新，种稚萌，等.城市微蜂窝环境下一种改进的射线跟踪预测模型[J].西安电子科技大学学报：自然科学版，2014，41(2)：137-143.

[8]YACKOSKI J，AZIMI-SADJADI B，NAMAZI A，et al.Mobile network performance evaluation using the radio frequency network channel emulation simulation tool(RFnest?)[C]//Proc.19th annual international conference on Mobile computing & networking.[S.l.]：ACM Press，2013：155-158.[9]ZHANG Z B，GUO L，LIU Z Y.An improved algorithm of reverse ray tracing for radio propagation prediction in urban[C]//Proc.IEEE International Conference on Microwave Technology & Computational Electromagnetics (ICMTCE) .[S.l.]：IEEE Press，2011：346-349.

[10]SON H W，MYUNG N H.A deterministic ray tube method for microcellular wave propagation prediction model[J].IEEE Trans. Antennas and Propagation，1999，47(8)：1344-1350.

[11]TAN S Y，TAN H S.Propagation model for microcellular communications applied to path loss measurements in Ottawa city streets[J].IEEE Trans.Vehicular Technology，1995，44(2)：313-317.

[12]顾晓龙，章文勋，云正清，等.利用可见性概念改进基于镜像原理的射线追踪法[J].电波科学学报，2001，16(4)：464-467.

[13]GMELIN M，KREUZINGER J，PFEFFER M，et al.Agent-based distributed computing with jmessengers[M].Innovative Internet Computing Systems：Springer Berlin Heidelberg，2001.

[14]吴剑锋，曹伟.用于微蜂窝电波传播预测的二维射线跟踪模型[J].南京邮电学院学报，2001，21(2)：45-51.

周 林(1963— )，硕士生导师，主要研究方向无线通信、计算机网络、物联网开发等；

雒 芳(1987— )，女，硕士生，主研无线信道。

责任编辑：许 盈

Ray Tracing Algorithm Based on Virtual Wall

ZHOU Lin1, LUO Fang1, YANG Longpin2

(1.DepartmentofCommunicationandInformationEngineering,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China;2.BeijingHospital,Beijing100730)

Aiming at the low efficiency problem of the existing ray tracing algorithm, using the idea of virtual source, a ray tracing algorithm based on the virtual wall is designed.Firstly, walls in the same plane are merged into a "virtual wall" to reduce the traversal times of walls in the search process.Secondly, in order to avoid the interfusion of the invalid nodes and reduce the computational complexity, the assisted judgment conditions such as "the photic zone", "light sector" are designed to accomplish the validity judgement of the nodes.Finally, the depth-first search algorithm is used to complete the establishment of virtual source tree structure, avoiding the repeated traversal in the search process of all effective paths.The simulation results show that the prediction accuracy of path loss increases with the depth of the tree as well as the computational complexity of the proposed algorithm is reduced.

ray tracing; virtual wall; depth-first; traversal

【本文献信息】周林，雒芳.一种基于虚拟墙的射线跟踪法[J].电视技术,2015，39(3).

国家自然科学基金项目(61171190)

TN915；TP301.6

A

10.16280/j.videoe.2015.03.035

2014-09-05