Exportar este item: EndNote BibTex

Use este identificador para citar ou linkar para este item: https://tede.ufam.edu.br/handle/tede/4137
Tipo do documento: Dissertação
Título: Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio
Autor: Dias, Bruno Raphael Cardoso 
Primeiro orientador: Rodrigues, Rosiane de Freitas
Primeiro coorientador: Maculan Filho, Nelson
Resumo: O problema de alocação de canais é abordado, onde, dado uma rede móvel sem fio com antenas de transmissão distribuídas na região de interesse e dada uma ou mais faixa de frequência limitada discretizada em canais de transmissão, consiste em promover uma alocação de tais canais pelas antenas de tal modo a atender as chamadas em demanda otimizando o uso dos recursos, que neste caso priorizou-se a otimização do uso dos canais alocados, em um problema de otimização Min-Max da distribuição dos canais - o span -, onde o maior canal alocado deve ser o menor possível. Tal problema possui uma importância cada vez maior dado o grande crescimento da demanda e a limitação dos recursos tecnológicos de comunicação envolvidos. A abordagem ao problema é de Otimização Combinatória e áreas afins. Sendo assim, é apresentado um estudo da literatura sobre o tema, com enfoque em redes celulares e redes baseadas em rádios cognitivos. A partir disto, propõe-se novos modelos teóricos para representação do problema utilizando colorações especiais em grafos, escalonamento de tarefas em máquinas paralelas com restrições de recursos e geometria de distâncias com programação por restrições, sendo possível identificar características específicas de alguns cenários de aplicação do problema geral. Com base em tais modelos, são apresentados os algoritmos desenvolvidos e implementados, sendo métodos aproximados, baseados em busca local com ênfase na meta-heurística simulated annealing, e métodos exatos, envolvendo branch-and-cut com a ferramenta IBM/ILOG CPLEX e, por fim, métodos híbridos, branch-prune-and-bound. Os experimentos computacionais realizados são apresentados com uma análise comparativa de desempenho, usando tanto instâncias clássicas da literatura, como o conjunto Philadelphia e suas variantes, como também instâncias artificiais propostas para contemplar variantes abordadas, bem como de maior tamanho, envolvendo redes entre 70 a 150 estações. Os resultados obtidos validam os modelos teóricos propostos e os algoritmos desenvolvidos e implementados, uma vez que, resultados iguais ou melhores aos da literatura foram obtidos, com várias soluções ótimas comprovadas,além da discussão teórica e variantes propostas que se acredita robustecer o entendimento do problema e a literatura relacionada.
Abstract: The channel allocation problem is addressed, where, as a wireless mobile network with transmission antennas distributed in the region of interest and one or more given track limited frequency discretized broadcast channels, is to promote allocation of such channels by the antennas in such a way to meet the demand for calls optimizing the use of resources, which in this case prioritized to optimize the use of channels allocated in an optimization problem Min-Max distribution channel - the Span -, where the highest allocated channel must be as small as possible. This problem has a increasingly important given the large demand growth and limiting technological resources of communication involved. The approach to the problem is Optimization Combinatorics and related fields. Therefore, a literature study is presented on the topic, focusing on mobile phones and networks based on cognitive radio networks. The From this, it is proposed new theoretical model for the problem representation using special stains on graphs, task scheduling on parallel machines resource constraints and geometry distances with constraint programming, and possible to identify specific characteristics of some application scenarios of the problem general. Based on these models, the developed algorithms are presented and implemented, and approximate methods based on local search with emphasis on meta-heuristic simulated annealing, and exact methods, involving branch-and-cut with IBM / ILOG CPLEX tool and, finally, hybrid methods, prune-branch-and-bound. The computational experiments are presented with a comparative analysis of performance, either using classical literature instances, as set Philadelphia and its variants as well as artificial instances proposals to cover variants discussed, as well as larger involving network 70 to to 150 stations. The results validate the proposed theoretical models and algorithms developed and implemented, since, equal or better results to the literature were obtained with several great solutions proven, beyond theoretical discussion and variants proposals believed to strengthen the understanding of the problem and the related literature
Palavras-chave: Algoritmos
Geometria de distâncias
Coloração em grafos
Otimização combinatória
Telecomunicações
Combinatorial optimization
Coloring graphs
Área(s) do CNPq: CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
Idioma: por
País: Brasil
Instituição: Universidade Federal do Amazonas
Sigla da instituição: UFAM
Departamento: Instituto de Computação
Programa: Programa de Pós-graduação em Informática
Citação: DIAS, Bruno Raphael Cardoso. Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio. 2014. 102 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus, 2014.
Tipo de acesso: Acesso Aberto
URI: http://tede.ufam.edu.br/handle/tede/4137
Data de defesa: 20-Mar-2014
Aparece nas coleções:Mestrado em Informática

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Dissertação - Bruno Raphael Cardoso Dias.pdfDissertação - Bruno Raphael Cardoso Dias2,53 MBAdobe PDFThumbnail

Baixar/Abrir Pré-Visualizar


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.