⚡ electrical engineering

Tree Search Algorithms Applied to the BD-RIS Configuration in MU-MISO Communication Systems

本文针对多用户多输入单输出通信系统中的超对角可重构智能表面（BD-RIS）配置问题，提出了一种深度优先树搜索算法，在最大化信道增益性能与计算复杂度之间实现了卓越的平衡。

原作者： Pedro H. C. de Souza (National Institute of Telecommunications), Luciano Mendes (National Institute of Telecommunications)

发布于 2026-04-09

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Pedro H. C. de Souza (National Institute of Telecommunications), Luciano Mendes (National Institute of Telecommunications)

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文主要讲的是如何给一种叫**“超智能反射面”（BD-RIS）**的高科技设备“调音”，让它在无线通信中发挥最大威力。

为了让你轻松理解，我们可以把整个通信系统想象成一个**“超级派对”，把信号传输想象成“传递派对邀请函”**。

1. 背景：派对上的“回声墙” (RIS vs. BD-RIS)

想象一下，你（发射塔/基站）想给派对上的朋友们（用户手机）发送邀请函（无线信号）。

问题：有时候，你和朋友之间有一堵墙（障碍物），或者距离太远，信号传不过去，或者传过去很弱。
传统方案 (RIS)：以前，科学家发明了一面“智能镜子”（RIS）。这面镜子由很多小镜片组成，每个镜片可以独立调整角度，把信号反射给朋友。这就像一面普通的镜子，每个小镜片只能自己转，互不干扰。
新方案 (BD-RIS)：这篇论文提出的BD-RIS，就像是一面**“超级魔法镜子”**。它的每个小镜片之间不仅有连接，还能互相“商量”和“配合”。它不仅能反射信号，还能让信号在镜片之间流动、混合，产生更复杂的反射效果。
- 比喻：普通镜子（RIS）像是一群各自为战的士兵；而 BD-RIS 像是一支训练有素的交响乐团，每个乐器（镜片）之间都有连线，可以演奏出更和谐、更宏大的乐章。

2. 核心难题：如何“调音”？

虽然 BD-RIS 很强大，但它太复杂了。

这面“魔法镜子”有 $N \times N$ 个镜片，每个镜片都有很多种角度（相位）可以选。
如果要把所有镜片的角度都试一遍，找出最好的组合，就像是要在一秒钟内尝试完宇宙中所有可能的原子排列组合。这在数学上被称为"NP 难问题”，也就是计算量大到电脑会直接死机。
以前的方法要么算得太慢，要么只能找到“差不多”的答案，不够完美。

3. 解决方案：聪明的“寻宝游戏” (树搜索算法)

这篇论文的作者提出了一种**“深度优先树搜索算法”。我们可以把它想象成一个“聪明的寻宝游戏”**：

传统的笨办法（穷举）：像无头苍蝇一样，把所有可能的路都走一遍，直到找到宝藏。这太慢了。
作者的新办法（剪枝搜索）：
1. 画地图（树结构）：把寻找最佳角度的过程画成一棵大树。树的每一层代表一个镜片的调整，每一个分叉代表一种角度选择。
2. 深度优先（钻到底）：算法先顺着一条路一直往下走，看看这条路能不能通向宝藏。
3. 智能剪枝（关键！）：这是最精彩的部分。在探索过程中，算法会不断问自己：“嘿，这条路看起来越来越没希望了，再走下去也找不到比现在更好的结果，干脆别走了，直接剪掉！"
- 比喻：就像你在迷宫里找出口。如果你发现前面是一条死胡同，或者你发现现在的方向离出口越来越远，你就立刻掉头，不再浪费时间去探索那条路。
- 参数 $\epsilon$ 和 $\rho$ ：这两个参数就像是**“耐心值”**。
  - 如果你把耐心值设得很高（ $\epsilon$ 很小），算法就会很挑剔，只走那些看起来非常有希望的路，剪掉很多路，速度极快，但可能错过一点点完美的宝藏。
  - 如果你把耐心值设得很低（ $\epsilon$ 很大），算法就会更谨慎，多走几条路，找到的结果更接近完美，但速度会变慢。

4. 实验结果：既快又好

作者用电脑模拟了各种场景（比如信号被墙挡住，或者有很多用户同时通信）：

当信号被挡住时：BD-RIS 的优势最大。作者的算法能找到非常接近“理论完美值”的信号强度，比以前的老方法强很多。
计算速度：通过“剪枝”（智能放弃坏路），算法的计算量从“天文数字”降到了“普通电脑能处理”的范围。
灵活性：就像调节收音机一样，你可以根据需要，在“追求完美”和“追求速度”之间自由切换。

5. 总结：这有什么用？

这篇论文的核心贡献就是发明了一个**“聪明的导航员”**。

它能让未来的 6G 网络中的BD-RIS设备，在极短的时间内，自动找到最佳的信号反射方案。
这意味着，未来的手机信号将不再受墙壁、距离的阻碍，即使在地下室或高楼林立的城市峡谷里，也能像站在空旷草地上一样信号满格。

一句话总结：
作者设计了一种**“会偷懒的聪明算法”，它懂得在寻找最佳信号配置时，果断放弃那些没希望的路，从而在极快的速度下，找到了几乎完美**的通信方案。

这是一份关于论文《Tree Search Algorithms Applied to the BD-RIS Configuration in MU-MISO Communication Systems》（树搜索算法在多用户 MISO 通信系统中的 BD-RIS 配置应用）的详细技术总结。

1. 研究背景与问题定义 (Problem)

背景：可重构智能表面（RIS）被视为 6G 网络的关键技术，能够动态操控电磁波反射。然而，传统 RIS 的反射系数矩阵通常被限制为对角矩阵（即每个单元独立调整），这限制了其自由度。
新技术：超对角可重构智能表面（BD-RIS, Beyond Diagonal RIS）被提出。BD-RIS 通过更复杂的电路拓扑（互连阻抗）将反射单元连接起来，其配置矩阵是非对角的，从而提供了更多的自由度来优化信号反射。
核心问题：
- 在**多用户多输入单输出（MU-MISO）**系统中，如何配置 BD-RIS 的相位偏移矩阵 $\Theta$ ，以最大化整体信道强度（Channel Strength）。
- 该优化问题是一个非凸优化问题，且由于 BD-RIS 矩阵的非对角特性，直接求解是 NP-hard 的。
- 现有的启发式算法或流形优化方法往往面临计算复杂度高或系统扩展性差的问题，难以在大规模 BD-RIS 部署中实用。

2. 方法论 (Methodology)

作者提出了一种**带有剪枝的深度优先树搜索算法（Depth-First Tree Search with Pruning）**来解决 BD-RIS 的配置问题。

2.1 系统模型

场景：基站（BS）配备 $L$ 根天线，服务 $K$ 个单天线用户（UE），辅助以包含 $N$ 个单元的 BD-RIS。
信道模型：总信道包括直射链路（BS-UE）和级联链路（BS-BD-RIS-UE）。
优化目标：最大化接收信号的信道范数平方 $\|G^\dagger + H^\dagger \Theta \Upsilon\|_F^2$ 。
约束条件：
1. 酉约束（Unitary Constraint）： $\Theta^\dagger \Theta = I$ ，确保反射信号功率不超过入射功率。
2. 对称约束（Symmetry Constraint）： $\Theta = \Theta^\top$ ，基于互易阻抗元件的物理特性。

2.2 算法核心步骤

算法分为两个阶段：首先针对 SISO 系统简化模型提出基础算法（Algorithm 1），然后推广至 MU-MISO 系统（Algorithm 2）。

离散化搜索空间：将连续的相位偏移离散化为集合 $Q$ 。
深度优先搜索 (DFS)：
- 将 BD-RIS 矩阵的每个元素（从对角线开始，再到非对角线）映射为搜索树的节点。
- 逐层遍历，为每个矩阵元素尝试集合 $Q$ 中的离散相位值。
剪枝策略 (Pruning)：
- 引入阈值参数 $\epsilon$ 和 $\rho$ 。
- 在搜索过程中，计算当前候选配置对信道强度的贡献（通过投影或迹函数评估）。
- 如果当前分支的潜在增益低于阈值 $\epsilon$ ，或者相邻分支的性能提升小于 $\rho$ ，则剪枝（停止该分支的进一步搜索），从而大幅降低计算量。
投影处理 (Projection)：
- 由于离散化后的矩阵可能不满足酉约束和对称约束，算法中嵌入了 UNISYM 函数。
- 该函数利用奇异值分解 (SVD) 计算离散矩阵到“对称酉矩阵”空间的最接近投影，确保物理可行性。
MU-MISO 扩展：
- 针对 MU-MISO 系统，目标函数被展开为包含迹（Trace）运算的形式。
- 算法根据直射链路是否存在（阻塞或非阻塞），动态调整评估函数（VARCALC），利用柯西 - 施瓦茨不等式和冯·诺依曼迹定理进行归一化评估。

3. 主要贡献 (Key Contributions)

首创性应用：据作者所知，这是首次将树搜索算法应用于 BD-RIS 配置矩阵的优化，填补了该领域的空白。
性能与复杂度的权衡：通过启发式剪枝参数（ $\epsilon, \rho$ ），算法能够在“信道强度最大化性能”和“计算复杂度”之间实现灵活且显著的权衡。
SISO 与 MU-MISO 的通用性：
- 在 SISO 系统中，算法证明了可以达到理论上的信道增益上界。
- 在 MU-MISO 系统中，算法表现出良好的可扩展性。
低复杂度实现：相比于穷举搜索（ $O(|Q|^{N^2})$ ）或某些流形优化方法，提出的算法在剪枝开启时，计算复杂度显著降低（仿真显示约为 $O(N^2)$ 到 $O(N^5)$ 之间，取决于剪枝强度）。

4. 实验结果 (Results)

作者通过数值模拟验证了算法的有效性：

SISO 系统验证：
- 当离散相位集大小 $\log_2|Q| = 4$ 时，算法性能几乎达到了 BD-RIS 的理论分析上界，且优于传统对角 RIS。
- 证明了算法可以通过调整参数灵活平衡性能与复杂度。
MU-MISO 系统性能：
- 直射链路存在时：算法性能接近低复杂度基准方法（文献 [5] 中的方法），但在开启剪枝时计算量大幅减少。
- 直射链路阻塞时：算法性能显著优于低复杂度基准方法。这是因为基准方法使用了一阶近似，而树搜索能更精确地利用 BD-RIS 的非对角自由度来建立级联链路。
计算复杂度分析：
- 无剪枝时的理论复杂度上界为 $O(|Q|N^5)$ 。
- 开启剪枝后，平均运行时间随 $N$ 的增长呈现 $O(N^2)$ 的趋势，证明了其极高的可扩展性。
- 通过调整参数 $\rho$ （最小提升阈值）和 $d$ （允许失败次数），可以精细控制搜索深度和计算成本。

5. 意义与未来展望 (Significance & Future Work)

实际意义：该研究为 BD-RIS 在 6G 网络中的实际部署提供了一套可扩展、低复杂度的配置方案。它解决了 BD-RIS 配置中 NP-hard 问题的计算瓶颈，使得在大规模天线和反射单元场景下实时优化成为可能。
未来方向：
- 联合波束成形：将 BD-RIS 配置与基站的主动波束成形（Active Beamforming）联合优化。
- 非完美 CSI：研究在信道状态信息（CSI）不完美或存在估计误差情况下的算法鲁棒性。
- 架构扩展：将算法适配到 BD-RIS 的其他拓扑结构（如分组连接、树状连接等），并探索不同的矩阵元素映射策略。

总结：这篇论文提出了一种创新的基于树搜索的 BD-RIS 配置算法，成功解决了多用户场景下非凸优化难题。通过引入剪枝机制，该算法在保持接近最优性能的同时，极大地降低了计算复杂度，为下一代智能无线通信系统的实现奠定了重要的理论基础和技术路径。