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

Título: Algoritmos de Busca em Árvore Aplicados à Configuração de BD-RIS em Sistemas de Comunicação MU-MISO

1. Problema Abordado

O artigo foca no desafio de configurar Superfícies Inteligentes Reconfiguráveis Além da Diagonal (BD-RIS) em sistemas de comunicação Multi-Usuário com Múltiplas Entradas e Uma Saída (MU-MISO).

• Contexto: As RIS tradicionais possuem uma topologia de circuito restrita a uma matriz diagonal (elementos independentes). A BD-RIS, por outro lado, utiliza uma topologia mais sofisticada com impedâncias interconectadas, permitindo uma matriz de configuração não diagonal (simétrica e unitária), o que oferece mais graus de liberdade para manipular as ondas eletromagnéticas.
• Desafio: O objetivo é maximizar a força do canal (channel strength) considerando tanto o canal direto (Transmissor-Receptor) quanto o canal em cascata (Transmissor-BD-RIS-Receptor).
• Complexidade: A otimização direta dos parâmetros da matriz BD-RIS é um problema NP-difícil (não convexo), com um número proibitivo de combinações de busca, especialmente à medida que o tamanho da matriz aumenta. Algoritmos de otimização convencionais (como otimização em variedades) podem ter alta complexidade computacional e baixa escalabilidade.

2. Metodologia

Os autores propõem um algoritmo de busca em árvore de profundidade (Depth-First Search - DFS) com técnicas de poda (pruning) para configurar a matriz BD-RIS de forma eficiente.

• Modelo do Sistema:

  • Considera uma Estação Base (BS) com $L$ antenas servindo $K$ usuários (UEs) com uma BD-RIS de $N$ elementos.
  • O canal total é modelado como a soma do canal direto e do canal refletido pela BD-RIS.
  • A matriz de configuração $\Theta$ deve ser unitária ($\Theta^\dagger \Theta = I$) e simétrica ($\Theta = \Theta^\top$), refletindo a física dos componentes passivos interconectados.

• Algoritmo Proposto (Algoritmo 2):

  • Estrutura de Árvore: O algoritmo explora um espaço de busca discreto de deslocamentos de fase para cada entrada da matriz $\Theta$.
  • Abordagem Diagonal-Primeiro: A exploração começa pelas entradas diagonais e prossegue para as entradas fora da diagonal.
  • Projeção Unitária Simétrica: Para garantir que as restrições físicas sejam atendidas durante a busca, o algoritmo utiliza uma função (UNISYM) que projeta a matriz candidata discreta para a matriz unitária simétrica mais próxima (usando Decomposição em Valores Singulares - SVD).
  • Método de Poda (Pruning):
    • Um parâmetro de limiar ($\epsilon$) determina se um candidato de fase é "suficientemente bom" para continuar a busca naquele ramo.
    • Um parâmetro de melhoria mínima ($\rho$) permite interromper a execução prematuramente se não houver ganho significativo de desempenho entre ramos adjacentes.
  • Objetivo: Maximizar a norma de Frobenius do canal total, equilibrando a busca exaustiva com a eficiência computacional.

3. Principais Contribuições

• Primeira Integração: Este trabalho apresenta a primeira aplicação de algoritmos de busca em árvore para a configuração de matrizes BD-RIS.
• Escalabilidade: Demonstra que é possível alcançar um equilíbrio flexível entre o desempenho de maximização da força do canal e a complexidade computacional através da parametrização heurística ($\epsilon$ e $\rho$).
• Validação em Cenários Diversos: O algoritmo foi validado tanto para sistemas SISO (Single-Input Single-Output) quanto para MU-MISO, cobrindo cenários com e sem canal direto (obstruído).
• Análise de Complexidade: Fornece uma análise detalhada da complexidade, mostrando que, com poda adequada, o custo pode ser reduzido de exponencial (ou polinomial de alto grau) para algo próximo de $O(N^2)$.

4. Resultados

As simulações computacionais validaram a eficácia do algoritmo:

• Desempenho em SISO: O algoritmo atinge o limite superior analítico (upper bound) para sistemas SISO, especialmente quando o conjunto de fases discretas é suficientemente grande ($\log_2|Q| = 4$).
• Desempenho em MU-MISO (Canal Direto Livre): O desempenho é comparável a métodos de baixa complexidade existentes na literatura, mas com a vantagem de ser um algoritmo de busca mais robusto.
• Desempenho em MU-MISO (Canal Direto Obstruído): O algoritmo proposto superou significativamente os métodos de baixa complexidade (baseados em aproximações de primeira ordem), demonstrando sua superioridade em cenários onde o canal direto é bloqueado e a reflexão é crítica.
• Complexidade Computacional:
  • Sem poda, a complexidade é aproximadamente $O(|Q|N^5)$.
  • Com poda ativa (parâmetros $\epsilon$ e $\rho$ ajustados), a complexidade cai drasticamente para aproximadamente $O(N^2)$, tornando o algoritmo viável para matrizes maiores.
  • O tempo de execução cresce polinomialmente, permitindo configurações escaláveis.

5. Significado e Impacto

• Viabilidade Prática: O trabalho oferece uma solução escalável para um problema de otimização que anteriormente era considerado computacionalmente proibitivo para sistemas grandes.
• Flexibilidade: A capacidade de ajustar o trade-off entre desempenho e complexidade permite que o algoritmo seja adaptado a diferentes requisitos de hardware e latência em redes 6G.
• Futuro da RIS: Ao demonstrar que a topologia BD-RIS pode ser configurada eficientemente, o artigo abre caminho para a adoção prática dessas superfícies mais avançadas, que prometem melhorias significativas na cobertura e capacidade de redes sem fio, especialmente em ambientes com obstruções severas.
• Base para Pesquisa: O artigo estabelece uma fundação para futuras pesquisas, sugerindo extensões para integração com beamforming ativo, tratamento de CSI imperfeito e adaptação a outras arquiteturas de BD-RIS (como conectividade em grupo ou árvore).

Em resumo, o artigo propõe uma solução heurística inteligente que torna a configuração de BD-RIS em sistemas multi-usuário viável e eficiente, superando as limitações de métodos de otimização convexa e busca exaustiva.