Infraestrutura de acesso em redes sem fio obstruídas: da Intratabilidade à Conectividade
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Vinicius Fernandes dos Santos
Antonio Alfredo Ferreira Loureiro
Mario Sergio Ferreira Alvim Junior
Antonio Alfredo Ferreira Loureiro
Mario Sergio Ferreira Alvim Junior
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 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.
Abstract
Assunto
Metodos de simulação, Computação, Métodos de simulação, Redes sem fio obstruídas, algoritmos de aproximação, Problemas NP-completo
Palavras-chave
Algoritmos aproximativos, NP-Completude, Validação de modelos, Escalabilidade, Modelagem analítica, Limites fundamentais, Redes de Comunicação sem fio obstruídas