Infraestrutura de acesso em redes sem fio obstruídas: da Intratabilidade à Conectividade

Neste trabalho é considerada uma rede sem fio ad hoc realizada em uma grade regular quadrada, na qual a comunicação entre os dispositivos é influenciada por obstáculos regularmente espaçados. O raio crítico de transmissão para obter conectividade nesse tipo de rede cresce com o tamanho da grade, o que pode prejudicar a viabilidade em larga escala de tecnologias sem fio de baixa potência. Avalia-se portanto como introduzir eficientemente uma infraestrutura conectada de pontos de acesso em cenários subcríticos, nos quais o raio de transmissão é insuficiente para estabelecer a conectividade. Formula-se o problema de posicionar o menor número de pontos de acesso, de tal modo que todo componente conectado seja coberto por pelo menos uma estação base, e denomina-se esse problema de Obstructed Wireless Network Backbone Cover Problem (OWN-BC). Prova-se que OWN-BC é NP-Completo e propõe-se um algoritmo 2-aproximativo para obter soluções com garantia de qualidade. Realiza-se simulações para ilustrar o desempenho do algoritmo em diferentes cenários. Além disso, é feita uma caracterização de cenários para os quais o algoritmo proposto obtêm soluções ótimas em tempo polinomial com alta probabilidade.