毫米波室内传播场景的蚁群优势路径搜索方法

纪腾飞 杨铖 赵毅

（1.天津大学，天津 300072；2.青岛中科创电子技术有限公司，青岛 266200）

引 言

5G和6G通信系统将毫米波频段作为了主要频段之一，使得毫米波通信机理研究、传播特性分析等领域成为?近年来国内外广泛关注和研究的热点[1-6].毫米波通信借助毫米波为传输信息的载体进行通信，其载波频率覆盖范围为26.5～300 GHz，带宽最高可达273.5 GHz[7]. 由于毫米波属于极高频段，干扰源很少，可以稳定地在室内或室外环境中传播；同时在相同天线尺寸下毫米波的波束要比微波窄很多，可以分辨相距更近的小目标. 因此，毫米波通信是一种典型的具有高质量、恒定参数的无线传输信道的通信技术[8]. 室内毫米波信号传播环境复杂，多径效应明显，需要精确的场景模型预测信号覆盖，以便提高信号服务质量和频谱效率[9]. 室内无线通信系统的研究与开发需要对信道特性[10-11]有广泛的了解，射线追踪及其改进模型是预测室内信道特性的一种有效方法[11]，主要成果有：1) 文献[12]提出了一种适用于办公室会议环境的信道模型. 该模型考虑了传输损耗、信道聚类以及极化等影响，利用射线追踪法验证了信道的统计模型. 2) 文献[13]提出了一种基于图形处理器(graphics processing unit, GPU)的KDtree加速波束跟踪方法. 该方法包含了一种基于插接器坐标的有效波束-三角形相交算法和一种扩展到波束跟踪的KD-tree遍历算法，克服了射线追踪方法中的离散采样效应，大大减少了计算时间. 3) 文献[14]采用射线追踪法检测了室内办公环境中毫米波信道参数，并与空间交替广义期望最大化(spatial-alternation generalized expectation-maximization，SAGE)估 计 算法处理的信道测量数据进行比较，发现在视距和非视距两种情况下，优势路径的模拟性能和实测性能都能达到很好的一致性. 4) 德国AWE Communications GMBH公司开发了WinProp室内和室外传播分析软件. 该工具强大的传播引擎包括经验和半经验模型以及三维射线跟踪模型和独有的优势路径模型，其预测结果与实际测量结果能够保持着很好的一致性，也使该工具成为了当今无线电波传播与无线网络规划领域内的标准工具[15]. 5)文献[16]提出了一种快速射线追踪算法，在对数字高程模型(digital elevation model，DEM)数据进行三角形剖分的基础上，利用射线跟踪方法对不规则地形进行了大量的覆盖预测，分析了场分布和信道特性. 6)文献[17]介绍了一种通用的射线追踪模型，并根据我国的实际情况给出了相关参数的获取方法. 仿真证明算法具有实用性强、计算精度高的特点. (7)文献[18]提出了一种改进的空间分割射线追踪算法跟踪电磁波在海面上的传播路径，对无人机与船之间的移动信道进行了仿真和建模.

由于射线在复杂的室内环境中传播时间长，计算复杂度高，导致室内毫米波研究受到了很大限制.因此，为了满足工程需要，急需改善传统的射线追踪技术，提高算法效率. 国内学者利用捷径法[19]、邻域辅助径迹法[20]、优化射线追踪场[21]及改善接收球方法[22]等在一定程度上提升了射线追踪效率. 为在保障预测精度的基础上进一步提升算法效率，本文利用蚁群分布计算和启发式搜索原理寻找电波传播优势射线路径，选取室内传播中能量较高的优势射线路径代替所有射线路径，用以提高射线追踪的计算效率，降低算法复杂度.

1 基于蚁群算法的优势路径确定

传统的射线追踪法是基于几何光学和均匀衍射理论[7]通过射线寻迹过程，寻找从发射源发出并到达接收点的所有可能传播路径，计算反射、绕射和透射系数，将各条路径的射线能量合并，从而得到接收点电平和传播延时. 传统的射线追踪法在测试场景中发射大量射线，预测射线传播的信道特性，计算效率低下，复杂度极高[23].

针对不同复杂的室内环境，本文引入蚁群算法用于选取室内传播中能量较高的几条优势射线路径代替所有射线路径，去除大量贡献小的射线，大幅度降低了射线在室内环境传播的复杂度. 此外，在此基础上，通过设置一定的误差阈值，结合计算机多线程并行计算技术，在保证精度的前提下，可以大大提高射线追踪的追踪速度，减小计算复杂度. 快速射线追踪与传统射线追踪对比如表1所示.

表1 快速射线追踪与传统射线追踪对比Tab. 1 Comparison of fast ray tracing and traditional ray tracing processes

蚁群算法的研究模型源于对真实蚂蚁觅食行为的模拟. 蚂蚁在觅食过程中，会在所经路径上释放出一种具有挥发性的物质——信息素，不同蚂蚁个体通过感知信息素的存在及其强度指导自己的移动方向. 研究表明，蚂蚁更倾向于选择信息量较大的路径，由此形成一种正反馈机制：最优路径上的信息量越来越大，其他路径上的信息量则随时间逐渐衰减.蚂蚁个体间通过感知信息素交换路径信息，最终整个蚁群在这种自组织作用下搜索出巢穴与食物源之间的最优路径.

根据蚁群算法中路径信息量感知原理[24]，信息素浓度最高的路径组合方案最优，因此在蚁群算法中输入发射点、反射点及接收点三维坐标，经蚁群算法搜索后，在保证精度的前提下，可以输出一部分优势 射线路径替代所有传播路径.

1 .1 优势路径搜索

1.1.2 射线方案禁忌表的建立

建立L个相互独立的禁忌表：Chart1、Chart2、 ···、ChartL，分别存放射线路径组合方案 φ1、φ2、 ···、 φL. 基于蚁群算法分布计算和启发式搜索原理并行搜索L个禁忌表中的路径组合方案，搜索结束后的每个禁忌表分别存放按接收射线传输衰减从低到高排列的射 线路径组合方案φ′1、φ′2、 · ··、φ′L.

1.1.3 最优射线路径方案搜索

满足 0＜ε≤εr且 0≤Δε≤0.01 dB的情况下，寻找优势射线数量最少的路径组合方案，即为最终确定的优势射线路径. 式中，εp和εp+1(0＜p＜L-1)分别为满足约束条件下第p、p+1个禁忌表最优路径组合方案的均方误差.

分析发现：传统射线追踪法发射角度间隔均匀的射线，通过一次次判交运算及是否到达接收点筛选符合条件的射线路径，计算时间较长；而快速射线追踪法根据蚁群算法确定到达接收点的射线路径组合方案，避免大量无用或贡献小的射线参与，进而省略判交运算时间，并结合计算机多线程并行计算技术，加速射线最优路径组合方案的筛选过程，从本质上提高了射线追踪的追踪速度，极大地降低了追踪复 杂度.

1.2 射线传播特性分析

射线在复杂的室内场景中进行传播时，将不可避免地与建筑面发生反射、绕射和透射[25-26]. 由于射线在不同电磁参数的建筑面衰减不同，需要考虑不同场景下射线的筛选情况. 当射线在室内外之间的大场景传播时，需要计算射线路径上的自由空间传播损耗，以及在建筑面产生的反射、绕射和透射损耗等. 然而，室内小场景中穿透建筑的射线将会产生很大损耗，因此不考虑作为优势射线[27]. 选取优势射线，计算收发点间的自由空间传播损耗、反射损耗、绕射损耗等，可以很好地预测室内毫米波信道特性.

1.3 多线程并行计算

根据分布计算理念，在此采用四核CPU、Parpool并行池提供多核并行运算工具，将所有禁忌表中不同方案的路径损耗计算任务分配给4个CPU同时运算，实现CPU的并行运算. 同时，每个CPU拿到分配的禁忌表方案后，逐个计算每种禁忌表中射线路径组合方案的损耗值，实现禁忌表方案的多线程运算.采用多线程并行运算技术可以大幅度提高CPU的利用率[25]. 如快速射线追踪法所示，蚁群算法确定射线路径组合方案后，采用多线程并行计算加速不同组合方案的筛选情况，直到得到最优射线组合方案. 利用多线程并行计算技术实现最优路径组合方案的加速筛选，其流程如图1所示.

图1 多线程并行计算流程Fig. 1 Multi-threading parallel computing process

2 仿真讨论

基于上述理论，室内毫米波信道特性预测时，首先根据室内环境场景数据导入算法；基于此，利用蚁群算法确定优势射线路径，设定误差阈值，采用多线程并行加速；最后，在满足误差阈值的前提下，统计输出优势射线的路径损耗值及预测误差.

2.1 场景设置

在此，利用AutoCAD软件对室内实测场景进行二维建模，统计室内环境中的材质、高度及相对介电常数，并导入算法，放置收发天线(1个发射点，2个接收点)，进行建模仿真. 仿真室内环境二、三维建模及收发机位置如图2所示，室内大小为13.8 m×12.1 m，并放有12张办公桌子，6台电脑，发射机位置(1，4.9)，2个接收机位置即两个接收点分别为(6.225，4.9)、(11.289 5，4.9). 室内建筑材质及电磁参数如表2所示，室内收发天线参数设置如表3所示.

图2 室内二、三维环境模型及收发机位置Fig. 2 Indoor 2D, 3D environment model and transceiver location

表2 室内建筑材质参数Tab. 2 Interior building material parameters

表3 室内收发天线参数设置Tab. 3 Setting of indoor transmitting and receiving antenna parameters

2.2 优势射线路径的确定

图3 优势射线路径的确定流程Fig. 3 Determination process of dominant ray path

图4 室内射线传播路径Fig. 4 Indoor ray propagation path

采用多线程并行计算技术分别计算两个接收点禁忌表中射线路径组合方案的路径损耗值lPi与lPL，在满足公式(6)、(7)的约束条件下，寻找最优射线路径组 合方案.

2.2.1 基于接收点1优势射线路径规划

Step1. 基于蚁群算法寻找接收点1最优射线路径组合方案：计算第一个接收点禁忌表Chart1、Chart2、 ···、Chart25的射线路径组合方案的损耗值，并与WinProp传统射线追踪法预测结果进行对比，计算路径损耗的均方误差. 在本仿真案例中发现，在第一个接收点最优射线路径组合方案的筛选过程中，发现禁忌表Chart5中首个射线组合方案{L0，L11，L13，L12，L21}的均方误差ε5=0.751 0 dB满足不大于1 dB要求，与禁忌表Chart6中首个射线组合方案的均方误差(ε6=0.750 1 dB)的偏差为0.000 9 dB，满足收敛误差不大于0.01 dB的要求.

Step2. 保存接收点1最优射线路径组合方案：由Step1可知，接收点1的最优射线路径组合方案为{L0，L11，L13，L12，L21}，优势射线路径如图5所示.

图5 室内第一个接收点优势射线路径Fig. 5 The dominant ray path of the first receiving point in the room

设定误差阈值εr=1 dB，对第一个接收点建立25个禁忌表：Chart1、Chart2、 ···、Chart25. 采用蚁群算法搜索第一个接收点的25个方案集合，并将搜索完成的方案集合放入对应禁忌表中：Chart1存放排列后的方案φ′1=[{L0}，{L11}，{L13}，{L14}，{L12}， ···，{L219}]；Chart2存放排列后的方案 φ′2=[{L0，L11}，{L0，L13}，{L0，L14}，{L0,L12}， ···， {L20，L19}]； ···；Chart25存放排列后的方案φ′25= [{L0，L11，L13， · ··，L219}].

同理，对第二个接收点建立23个禁忌表：Chart1、Chart2、 ···、Chart23. 分别存放蚁群算法搜索后的射线路径组合方案：Chart1存放排列后的方案φ′1=[{L0}，{L11}，{L13}，{L14}，{L12}， ···，{L217}]；Chart2存放排列后的方案 φ′2=[{L0，L11}，{L0，L13}，{L0，L14}，{L0,L12}， ···， {L18，L17}]； ···；Chart23存放排列后的方Step3. 最优射线路径组合方案的确定：由最优射线路径组合方案获知优势射线为1条直达路径、3条一次反射路径、1条二次反射路径，然而从室内电波传播机理角度考虑，确定该5条优势射线路径的筛选方法如图6所示.

图6 5条优势射线路径的确定流程Fig. 6 Determination process of dominant 5 ray paths

导入场景数据后，先判断室内收发机之间的射线直达路径是否存在，之后再对一次反射及二次反射路径进行统计筛选. 如果直达路径存在，最终的5条优势射线路径应为1条直达路径、一次反射中3条最短路径、二次反射中1条最短路径；若收发机之间的直达路径不存在，则5条优势射线路径为一次反射中4条最短路径、二次反射中1条最短路径.

Step4. 采用接收点1的最优射线路径组合方案验证接收点2的场景：在未知接收点2最优射线路径组合方案的基础上，利用上述接收点1确定的最优方案{L0，L11，L13，L12，L21}直接计算第二个接收点，发现接收点2的均方误差ε5=0.774 0 dB和收敛误差Δε5=0.004 8 dB满足要求，初步验证了选取5条优势射线路径替代全射线路径分析在保证精度的前提下可以很好地达到预测效果. 由上述过程初步可以看出：由于仅有5条路径参与计算，大大简化了运算量 ，运算量降低了80%.

2.2.2 基于接收点2优势射线路径规划

Step1. 基于蚁群算法寻找接收点2最优射线路径组合方案：首先计算第二个接收点各禁忌表Chart1、Chart2、 ···、Chart22的射线路径组合方案的损耗值，并与WinProp预测结果进行对比，发现禁忌表Chart4、Chart5和Chart6的首个路径组合方案{L0，L11，L13，L12}、{L0，L11，L13，L12，L21}和{L0，L11，L13，L12，L21，L14}的 均 方 误 差 分 别 为ε4=0.854 6 dB、ε5=0.774 1 dB和ε6=0.769 3 dB，收 敛 误 差 分 别 为：Δε4=0.080 5 dB、Δε5=0.004 8 dB和Δε6=0.001 3 dB. 不难发现当取禁忌表Chart5首个射线路径方案时，方可满足误差阈值不大于1 dB和收敛误差不大于0.01 dB的要求.

Step2. 保存接收点2最优射线路径组合方案：由Step1可知，接收点2的最优射线路径组合方案为{L0，L11，L13，L12，L21}，优势射线路径如图7所示.

图7 室内第二个接收点优势射线路径Fig. 7 The dominant ray path of the second receiving point in the room

Step3. 采用接收点2的最优射线路径组合方案验证接收点1的场景：假定在未知接收点1最优射线路径组合方案的基础上，利用接收点2的最优射线路径组合方案直接计算接收点1的均方误差为0.751 0 dB，收敛误差为0.000 9 dB，满足误差要求. 由上述过程同样可以看出：由于仅有5条路径参与计算 ，大大简化了运算量，运算量降低了78%.

2.2.3 小结

在本文仿真案例中，收发机高度1.8 m高于室内家具的建筑高度，因此两个接收点的射线路径均为收发机之间的直达射线路径以及在墙面上反射的射线路径. 在此基础上，观察2.2.1及2.2.2节两接收点射线路径组合方案的交叉验证结果，发现禁忌表Chart5的最优方案即为最优射线路径组合方案. 因此，在保证精度的前提下，选取5条优势射线替代全射线路径分析可以在本质上改善射线追踪算法，提高射线追踪效率，降低复杂度，运算量降低了约80%.最后，统计两个接收点各禁忌表最优方案的路径损耗误差如图8所示，发现误差统计结果可以宏观地验 证上述结论.

图8 室内两接收点各禁忌表最优方案路径损耗误差Fig. 8 The path loss error of the optimal scheme of the tabu tables at 2 indoor receiving points

2.3 结果对比

在2.2节最优射线路径组合方案的基础上，统计两个接收点分别在28 GHz、32 GHz和38 GHz频率下的路径损耗如图9所示：两个接收点的路径损耗值随着频率的增加而增加；由于第一个接收点距离发射机较近，所以射线在室内传播到达接收点的路径损耗小于第二个接收点. 可以看出接收点1下本文方法较WinProp路径损耗低，而接收点2两种方法下路径损耗相差较小，主要由于本文方法在挑选接收点1优势路径时，除常规路径外，还融入经上方远端一次反射路径能量，体现出蚁群优势路径搜索方法的优势.

图9 两个接收点在28 GHz、32 GHz和38 GHz下的路径损耗对比Fig. 9 Path-loss comparison of 2 receiring points at 28 GHz, 32 GHz and 38 GHz frequency

近几年国内外研究学者提出了许多优秀的射线追踪改善方法：网格剖分加速法、基于KD-tree的快速剪枝法等. 基于本文接收点1仿真案例，网格剖分加速法[28-29]对某一条射线进行追踪时，首先计算该条射线起点在二维平面的投影，然后根据该射线的传播方向，不断与其路径沿线网格中的三角面(每个网格存放两个三角面)进行判交运算，当遇见交点时停止判断. 因此，网格剖分法得到表示向上取整)条射线路径，虽然精度很高，但由于并未对优势路径进行提取，即使采用GPU加速技术，仍需计算高达种射线路径组合方案，计算复杂度将会很高. 基于KD-tree的快速剪枝法[24]将本文案例中的室内场景进行网格剖分，并将三角面元信息存储到KD-tree中，通过遍历KD-tree树，将不满足要求的射线路径进行快速剪枝，减少射线与三角面元判交计算的次数. 因此，基于KD-tree的快速剪枝法相比于网格剖分法降低了射线的判交运算时间. 然而，最终得到的射线路径仍然是本文中接收点1的25条射线路径，需要计算的射线路径组合方案为种，计算复杂度仍然很高. 相比于上述两种方法，本文对两个接收点众多的射线路径组合方案分类存放到禁忌表中，并利用蚁群算法搜索每个禁忌表中的射线路径组合方案，依托多线程并行计算技术，最终得到满足误差阈值的最优射线路径组合方案，大幅降低了射线追踪的计算时间及复杂度.

对比上述方法，统计快速射线追踪法的计算效率和复杂度如表4所示(计算机仿真配置为Windows10系统、处理器i5-2430M、主频2.4 G、运行内存2 G).在追踪时间方面：采用传统射线追踪法预测本案例室内信道特性时耗时最长为1.929 0 s；虽然国内外其他改善方法追踪时间明显降低，但仍然高于本文方法的追踪时间0.402 8 s. 在提速效果方面，提速量为

表4 射线追踪改善方法性能对比Tab. 4 Improved ray tracing method, calculation efficiency and complexity

式中：tΔ为 传统射线追踪法的追踪时间；to为射线追踪改善方法的追踪时间. 本文方法提速效果378.9%，远大于其他改善方法. 在计算复杂度方面：由于传统射线追踪法将室内场景剖分为ξ2个单元格，需要发射条射线进行判交运算，因此复杂度最高为网格剖分法通过划分三角面元寻找射线与面元交点，需要发射条射线进行判交运算，将复杂度降低至O(ξ|lg ξ|)；基于KD-tree的快速剪枝法将面元信息存储到二叉树结构中，遍历满足要求的射线路径，只需发射ξ条射线路径进行判交运算，复杂度为O(ξ)；而本文方法只需发射优势路径进行判交运算，故复杂度最低为O(5). 对比不同射线追踪改善方法，本文基于蚁群算法的优势射线路径追踪在保证精度的前提下，大幅提高了计算效率，降低了复杂度.

表5 不同测试频率下的路径损耗及均方根误差Tab. 5 Path loss and prediction error at different test frequencies

3 结 论

针对毫米波在室内传播情况，基于蚁群分布计算和启发式搜索原理，能够寻找电波传播优势射线路径代替所有射线路径. 文中依托多线程并行计算技术，预测了室内28 GHz、32 GHz及38 GHz频率下的路径损耗. 经仿真分析可以看出：1)在降低计算时间和复杂度方面，本文方法较网格剖分法及KD-tree快速剪枝法具有很大优势，在保证预测精度的前提下，可以大幅提高射线追踪的计算效率，降低复杂度.2)文中方法基于蚁群算法选取5条优势射线路径，可以在保证误差的前提下很好地预测室内毫米波传播特性. 3)在确定性室内场景下，利用蚁群算法搜索第一组收发机之间的优势射线路径，作为相似位置在优势路径选择方案，能够在保证路径损耗预测结果准确性的基础上，加速场景的整体预测过程.

上述成果提升了毫米波在室内场景下的仿真效率，可为毫米波传播分析、无线电业务规划等方面提供参考依据.