Infraestrutura de acesso em redes sem fio obstruídas: da Intratabilidade à Conectividade - Ferreira Neto, Manassés; Goussevskaia, Olga; dos Santos, Vinicius (Anais Estendidos do Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC), 2018)
Neste trabalho é considerada uma rede sem ﬁo ad hoc realizada em uma grade regular quadrada, na qual a comunicação entre os dispositivos é inﬂuenciada 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 ﬁo de baixa potência. Avalia-se portanto como introduzir eﬁcientemente uma infraestrutura conectada de pontos de acesso em cenários subcríticos, nos quais o raio de transmissão é insuﬁciente 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 um ponto de acesso, 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.