Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio
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 m...
| Autor principal: | Dias, Bruno Raphael Cardoso |
|---|---|
| Outros Autores: | http://lattes.cnpq.br/4185623104237943 |
| Grau: | Dissertação |
| Idioma: | por |
| Publicado em: |
Universidade Federal do Amazonas
2015
|
| Assuntos: | |
| Acesso em linha: |
http://tede.ufam.edu.br/handle/tede/4137 |
| id |
oai:https:--tede.ufam.edu.br-handle-:tede-4137 |
|---|---|
| recordtype |
dspace |
| spelling |
oai:https:--tede.ufam.edu.br-handle-:tede-41372016-05-11T14:35:04Z Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio Dias, Bruno Raphael Cardoso Rodrigues, Rosiane de Freitas http://lattes.cnpq.br/4185623104237943 http://lattes.cnpq.br/8358219976594707 Algoritmos Geometria de distâncias Coloração em grafos Otimização combinatória Telecomunicações Combinatorial optimization Coloring graphs CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO 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. 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 CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior 2015-06-18T18:58:47Z 2014-03-20 Dissertaçã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. http://tede.ufam.edu.br/handle/tede/4137 por Acesso Aberto application/pdf Universidade Federal do Amazonas Instituto de Computação Brasil UFAM Programa de Pós-graduação em Informática |
| institution |
TEDE - Universidade Federal do Amazonas |
| collection |
TEDE-UFAM |
| language |
por |
| topic |
Algoritmos Geometria de distâncias Coloração em grafos Otimização combinatória Telecomunicações Combinatorial optimization Coloring graphs CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO |
| spellingShingle |
Algoritmos Geometria de distâncias Coloração em grafos Otimização combinatória Telecomunicações Combinatorial optimization Coloring graphs CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃ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 |
| topic_facet |
Algoritmos Geometria de distâncias Coloração em grafos Otimização combinatória Telecomunicações Combinatorial optimization Coloring graphs CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO |
| description |
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. |
| author_additional |
Rodrigues, Rosiane de Freitas |
| author_additionalStr |
Rodrigues, Rosiane de Freitas |
| format |
Dissertação |
| author |
Dias, Bruno Raphael Cardoso |
| author2 |
http://lattes.cnpq.br/4185623104237943 |
| author2Str |
http://lattes.cnpq.br/4185623104237943 |
| title |
Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio |
| title_short |
Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio |
| title_full |
Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio |
| title_fullStr |
Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio |
| title_full_unstemmed |
Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio |
| title_sort |
modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio |
| publisher |
Universidade Federal do Amazonas |
| publishDate |
2015 |
| url |
http://tede.ufam.edu.br/handle/tede/4137 |
| _version_ |
1831969238768680960 |
| score |
11.755432 |