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

논문 요약: MU-MISO 통신 시스템에서 BD-RIS 구성을 위한 트리 탐색 알고리즘 적용

1. 연구 배경 및 문제 정의 (Problem)

• 배경: 재구성 가능한 지능형 표면 (RIS) 은 6G 통신의 핵심 기술로 주목받고 있으나, 기존 RIS 는 대각선 행렬 (Diagonal Matrix) 로 제한된 위상 조정만 가능하여 유연성이 부족합니다. 이를 극복하기 위해 제안된 초대각선 재구성 가능한 지능형 표면 (BD-RIS, Beyond Diagonal RIS) 은 요소 간 상호 연결을 통해 더 복잡한 회위 토폴로지를 제공하며, 신호 반사에 대한 추가적인 자유도를 확보합니다.
• 문제: BD-RIS 의 잠재력을 최대한 활용하기 위해서는 행렬 구성 (Configuration) 을 최적화해야 합니다. 그러나 채널 강도 (Channel Strength) 를 최대화하는 BD-RIS 행렬을 직접 조정하는 문제는 NP-hard 문제이며, 탐색 공간이 매우 광범위하여 기존 최적화 기법 (예: 맨ifold 최적화) 은 높은 계산 복잡도를 가집니다.
• 목표: 다중 사용자 다중 입력 단일 출력 (MU-MISO) 시스템에서 BD-RIS 행렬을 구성하여 전체 채널 강도를 최대화하되, 계산 복잡도와 성능 간의 균형을 맞추는 효율적인 알고리즘을 제안하는 것입니다.

2. 제안된 방법론 (Methodology)

저자는 깊이 우선 탐색 (Depth-First Search, DFS) 기반의 트리 탐색 알고리즘을 제안하며, 이는 SISO(단일 사용자) 시스템에서 시작하여 MU-MISO 시스템으로 확장됩니다.

• 알고리즘 핵심 (Algorithm 1 & 2):
  • 트리 탐색 구조: BD-RIS 구성 행렬의 각 요소 (위상 천이 값) 를 트리 노드로 간주하고, 이산화된 위상 집합 $Q$에서 후보 값을 탐색합니다.
  • 가지치기 (Pruning): 탐색 과정에서 현재 후보가 목적 함수 (채널 강도) 에 기여할 가능성이 낮다고 판단되면 해당 분기를 즉시 중단하여 계산량을 줄입니다.
    • $\epsilon$ (임계값): 후보의 적합성을 판단하는 기준.
    • $\rho$ (성능 개선 임계값): 인접 분기 간의 성능 개선이 미미할 경우 탐색을 조기에 종료하는 파라미터.
  • 대칭 및 유니타리 제약 처리: BD-RIS 는 대칭 행렬 ($\Theta = \Theta^\top$) 이고 유니타리 제약 ($\Theta^\dagger \Theta = I$) 을 만족해야 합니다. 알고리즘은 이산화된 행렬을 생성한 후, UNISYM 함수를 통해 가장 가까운 대칭 유니타리 행렬로 투영 (SVD 활용) 하여 제약 조건을 만족시킵니다.
  • MU-MISO 확장: 직접 경로 (Direct Channel) 가 존재하거나 차단된 경우를 모두 고려하여 목적 함수를 재구성하고, 트리 탐색을 적용합니다.

3. 주요 기여 (Key Contributions)

1. BD-RIS 구성을 위한 최초의 트리 탐색 알고리즘: BD-RIS 행렬 구성 문제에 트리 탐색 알고리즘을 적용한 최초의 연구로, 기존 NP-hard 문제를 효율적으로 해결합니다.
2. 성능과 복잡도의 유연한 트레이드오프: 가지치기 파라미터 ($\epsilon, \rho$) 를 조절하여 사용자는 원하는 성능 수준에 따라 계산 복잡도를 유연하게 조절할 수 있습니다.
3. SISO 및 MU-MISO 시스템 검증: 단순 SISO 시스템에서 이론적 상한선 (Upper Bound) 에 근접하는 성능을 입증하고, 이를 MU-MISO 시스템으로 확장하여 다양한 시나리오 (직접 경로 유무) 에서의 유효성을 검증했습니다.
4. 다항식 복잡도 달성: 가지치기를 적용할 경우, 알고리즘의 계산 복잡도가 $O(N^5)$에서 $O(N^2)$ 수준으로 크게 감소함을 증명했습니다.

4. 실험 결과 (Results)

• 성능 평가:
  • SISO 시스템: 제안된 알고리즘은 $\log_2|Q|=4$ (16 개의 위상 단계) 설정 시, BD-RIS 의 이론적 상한선 (Analytical Upper Bound) 에 거의 도달하는 성능을 보였습니다.
  • MU-MISO 시스템 (직접 경로 차단 시): 기존 저복잡도 방법론 (Low-complexity baseline) 보다 훨씬 우수한 채널 이득을 달성했습니다. 이는 BD-RIS 의 추가 자유도를 효과적으로 활용했기 때문입니다.
  • MU-MISO 시스템 (직접 경로 존재 시): 가지치기를 적용하지 않은 경우 (완전 탐색) 와 유사한 성능을 내면서도, 가지치기를 적용하면 성능 손실은 최소화하면서 복잡도를 획기적으로 줄였습니다.
• 계산 복잡도:
  • 가지치기를 사용하지 않을 경우 복잡도는 $O(|Q|N^5)$ 수준이지만, 적절한 파라미터 ($\rho$) 설정 시 $O(N^2)$ 수준으로 감소하여 대규모 BD-RIS 요소 ($N$) 에도 확장 가능 (Scalable) 함을 입증했습니다.
  • 시뮬레이션 결과, 가지치기 파라미터를 조절함으로써 탐색된 행렬 요소의 수를 정밀하게 제어할 수 있음을 시각적으로 확인했습니다.

5. 의의 및 결론 (Significance)

• 기술적 의의: BD-RIS 의 복잡한 구성 문제를 해결하기 위해 최적화 이론 대신 휴리스틱 트리 탐색을 도입함으로써, 고차원 최적화 문제에서 발생하는 계산적 병목 현상을 효과적으로 우회했습니다.
• 실용성: 제안된 알고리즘은 하드웨어 구현 시 필요한 계산 자원을 줄이면서도 RIS 의 이점을 극대화할 수 있는 실용적인 솔루션을 제공합니다.
• 미래 전망: 이 연구는 BD-RIS 구성을 위한 새로운 패러다임을 제시하며, 향후 능동 빔포밍 (Active Beamforming) 통합, 불완전한 채널 상태 정보 (CSI) 하에서의 동작, 그리고 다양한 BD-RIS 아키텍처 (그룹 연결, 트리 연결 등) 로의 확장을 위한 기초를 마련했습니다.

결론적으로, 본 논문은 BD-RIS 기술을 차세대 통신 시스템에 적용하기 위해 필요한 계산 효율성과 성능 최적화 사이의 균형을 성공적으로 달성한 획기적인 알고리즘을 제시했습니다.