1. Infraestrutura de acesso em redes sem fio obstruídas: da Intratabilidade à Conectividade
- Author
-
Manasses Ferreira Neto, Olga Nikolaevna Goussevskaia, Vinicius Fernandes dos Santos, Antonio Alfredo Ferreira Loureiro, and Mario Sergio Ferreira Alvim Junior
- Subjects
Escalabilidade ,Modelagem analítica ,Problemas NP-completo ,Redes sem fio obstruídas ,Redes de Comunicação sem fio obstruídas ,Computação ,algoritmos de aproximação ,Algoritmos aproximativos ,Validação de modelos ,Limites fundamentais ,NP-Completude ,Métodos de simulação ,Metodos de simulação - Abstract
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.
- Published
- 2017