Infraestrutura de acesso em redes sem fio obstruídas: da Intratabilidade à Conectividade
Resumo
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 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.
Referências
Garey, M. R. and Johnson, D. S. (2002). Computers and intractability, volume 29. wh freeman New York.
Levin, A. (2008). Approximating the unweighted k-set cover problem: greedy meets local search. SIAM Journal on Discrete Mathematics, 23(1):251–264.
Neto, M. F., Goussevskaia, O., and dos Santos, V. F. (2017). Connectivity with backbone structures in obstructed wireless networks. Computer Networks, 127:266 – 281.
