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

1. Problem Statement

The paper addresses the challenge of configuring Beyond Diagonal Reconfigurable Intelligent Surfaces (BD-RIS) in Multi-User Multiple-Input Single-Output (MU-MISO) communication systems.

• Context: While standard Reconfigurable Intelligent Surfaces (RIS) use diagonal phase-shift matrices to reflect signals, BD-RIS utilizes a more sophisticated circuit topology with interconnected elements. This allows for a full matrix (non-diagonal) configuration, offering significantly more degrees of freedom to manipulate electromagnetic waves.
• The Core Challenge: The objective is to maximize the overall channel strength (received signal power) by optimizing the BD-RIS configuration matrix $\Theta$.
• Mathematical Difficulty: The optimization problem is non-convex and NP-hard. The search space for the matrix entries (impedance values or phase shifts) is prohibitively large, making exhaustive search impossible for practical system sizes. Existing methods often rely on manifold optimization (high complexity) or low-complexity heuristics that may sacrifice performance, particularly in scenarios with obstructed direct channels.

2. Methodology

The authors propose a Depth-First Tree Search (DFTS) algorithm with pruning to solve the BD-RIS configuration problem. The methodology is developed in two stages:

A. System Model

• MU-MISO Setup: A Base Station (BS) with $L$ antennas serves $K$ single-antenna users via a BD-RIS with $N$ elements.
• Channel Model: The overall channel includes both the direct link (BS-to-UE) and the cascaded link (BS-to-BD-RIS-to-UE).
• Constraints: The BD-RIS matrix $\Theta$ must be unitary ($\Theta^\dagger \Theta = I$) to ensure lossless reflection and symmetric ($\Theta = \Theta^\top$) due to the reciprocal nature of the passive circuit components (resistors, capacitors, inductors).

B. The Proposed Algorithm (Algorithm 2)

The algorithm extends a simpler SISO version (Algorithm 1) to the general MU-MISO case. Key features include:

1. Discrete Search Space: The continuous phase-shift space is discretized into a set $Q$. The algorithm searches for the optimal combination of these discrete values.
2. Tree Structure:
   • The search is organized as a tree where each level corresponds to a specific entry (or pair of symmetric entries) in the BD-RIS matrix.
   • Diagonal Entries: Explored individually.
   • Off-Diagonal Entries: Explored in pairs ($\Theta_{ij}$ and $\Theta_{ji}$) to maintain symmetry.
3. Heuristic Pruning:
   • A suitability metric ($r$ or $w$) is calculated at each node to estimate how well a candidate phase shift aligns the channel vectors.
   • Pruning Parameter ($\epsilon$): If a candidate's suitability score exceeds a threshold $\epsilon$, the algorithm proceeds deeper into that branch (Depth-First). If not, the branch is pruned.
   • Early Termination Parameter ($\rho$): To further reduce complexity, the algorithm monitors the performance improvement between adjacent branches. If the improvement falls below a threshold $\rho$, the search in that branch is terminated prematurely.
4. Projection Functions:
   • UNISYM: Since the discrete search may yield a matrix that is not perfectly unitary or symmetric, a projection function is used. It computes the closest symmetric unitary matrix using Singular Value Decomposition (SVD) to satisfy the physical constraints before evaluating the metric.

3. Key Contributions

• First Integration of Tree Search with BD-RIS: This is the first work to apply tree search algorithms specifically to the configuration of BD-RIS matrices, leveraging the added degrees of freedom.
• Flexible Complexity-Performance Trade-off: By tuning the pruning parameters ($\epsilon$ and $\rho$), the algorithm can dynamically adjust between near-optimal performance (approaching the exhaustive search bound) and low computational complexity.
• Robustness in Obstructed Channels: The algorithm demonstrates superior performance compared to existing low-complexity baselines, particularly when the direct line-of-sight channel is blocked (a common scenario where RIS/BD-RIS is most critical).
• Scalability: The proposed method achieves polynomial computational complexity, making it scalable for larger BD-RIS arrays where exhaustive search is infeasible.

4. Numerical Results

The authors validated the algorithm through computational simulations:

• Performance (Channel Gain):
  • In SISO systems, the algorithm achieves the analytical upper bound for channel gain when the discrete set size is sufficient ($\log_2|Q| = 4$).
  • In MU-MISO systems, the algorithm outperforms the baseline low-complexity method from previous literature (e.g., [5]).
  • Obstructed Channel Scenario: When the direct channel is blocked, the proposed algorithm shows a significant performance gain over the baseline, which relies on first-order approximations that fail in this scenario.
• Computational Complexity:
  • Exhaustive Search: Without pruning, complexity scales as $O(|Q|N^5)$.
  • With Pruning: By setting appropriate values for $\epsilon$ and $\rho$, the complexity is reduced significantly (observed to scale closer to $O(N^2)$ in simulations).
  • Runtime: Simulations on a standard consumer CPU show that the algorithm remains computationally feasible for large matrix sizes (e.g., $N=64$) when pruning is enabled, whereas the unpruned version becomes prohibitive.

5. Significance and Future Work

• Significance: This work provides a practical, scalable solution for configuring the next generation of BD-RIS hardware. It bridges the gap between theoretical optimality and computational feasibility, proving that tree search can effectively handle the non-convex, high-dimensional optimization required for BD-RIS.
• Future Directions: The authors identify several areas for future research:
  • Joint Optimization: Integrating the BD-RIS configuration with active beamforming at the Base Station.
  • Imperfect CSI: Analyzing the algorithm's robustness when Channel State Information is estimated with errors (noting potential benefits from channel hardening).
  • Architecture Variations: Adapting the algorithm for different BD-RIS topologies (group-connected, tree-connected) beyond the fully-connected model used here.
  • Mapping Strategies: Exploring different mappings between tree levels and matrix entries to optimize search efficiency.

In conclusion, the paper establishes a foundational framework for using heuristic tree search to configure BD-RIS, offering a highly scalable alternative to existing optimization methods with a tunable balance between performance and computational cost.