Un algoritmo Branch y Cut para un problema de asignación de frecuencias en redes de telefonía celular

Mostrar todas las versiones(2)

En este trabajo se estudia una manera de manejar la interferencia en modelos de optimización combinatoria que representan redes de comunicación inalámbrica. En una red típica se tiene interferencia por co-canalidad cuando dos antenas que solapan sus áreas de cobertura utilizan la misma frecuencia pa...

Descripción completa

Detalles Bibliográficos
Autor principal: Delle Donne, Diego
Formato: Tesis de Grado
Lenguaje:Español
Publicado: Febr
Acceso en línea:https://hdl.handle.net/20.500.12110/seminario_nCOM000358_DelleDonne
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:seminario_nCOM000358_DelleDonne
record_format dspace
spelling todo:seminario_nCOM000358_DelleDonne2023-10-03T16:48:20Z Un algoritmo Branch y Cut para un problema de asignación de frecuencias en redes de telefonía celular Delle Donne, Diego En este trabajo se estudia una manera de manejar la interferencia en modelos de optimización combinatoria que representan redes de comunicación inalámbrica. En una red típica se tiene interferencia por co-canalidad cuando dos antenas que solapan sus áreas de cobertura utilizan la misma frecuencia para establecer las comunicaciones. Por otra parte, se genera una interferencia de menor magnitud cuando estas antenas utilizan canales de frecuencias adyacentes. Esto motiva la formulación del minimum-adjacency vertex coloring problem que, dado un grafo de interferencia G representando la potencial interferencia entre las antenas y un conjunto de colores/canales, consiste en hallar un coloreo de G minimizando la cantidad de aristas cuyos vértices reciben colores adyacentes. Se presentan en este trabajo tres modelos de programación lineal entera y se reportan resultados computacionales para estimar la contribución práctica de cada uno de ellos. Se elije luego la mejor formulación y se realiza un estudio poliedral del politopo asociado. Se presentan cuatro desigualdades válidas, las cuales definen facetas del mismo. Finalmente, se describe la implementación de un algoritmo Branch & Cut y se presentan los resultados computacionales obtenidos. In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation of the minimum-adjacency vertex coloring problem which, given an interference graph G representing the potential interference between the antennas and a set of prespecied colors/channels, asks for a vertex coloring of G minimizing the number of edges receiving adjacent colors. In this work, three integer programming models are presented for this problem and computational results are provided in order to assess the practical contribution of each one. The best formulation is chosen and a polyhedral study is performed on the polytope asociated. Four facet-defining inequalities are presented for this formulation. Finally, an implementation of a Branch & Cut algorithm is described and its computational results are presented. Fil: Delle Donne, Diego. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Febrero de 2009 Tesis de Grado PDF Español info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/seminario_nCOM000358_DelleDonne
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv Español
description En este trabajo se estudia una manera de manejar la interferencia en modelos de optimización combinatoria que representan redes de comunicación inalámbrica. En una red típica se tiene interferencia por co-canalidad cuando dos antenas que solapan sus áreas de cobertura utilizan la misma frecuencia para establecer las comunicaciones. Por otra parte, se genera una interferencia de menor magnitud cuando estas antenas utilizan canales de frecuencias adyacentes. Esto motiva la formulación del minimum-adjacency vertex coloring problem que, dado un grafo de interferencia G representando la potencial interferencia entre las antenas y un conjunto de colores/canales, consiste en hallar un coloreo de G minimizando la cantidad de aristas cuyos vértices reciben colores adyacentes. Se presentan en este trabajo tres modelos de programación lineal entera y se reportan resultados computacionales para estimar la contribución práctica de cada uno de ellos. Se elije luego la mejor formulación y se realiza un estudio poliedral del politopo asociado. Se presentan cuatro desigualdades válidas, las cuales definen facetas del mismo. Finalmente, se describe la implementación de un algoritmo Branch & Cut y se presentan los resultados computacionales obtenidos.
format Tesis de Grado
author Delle Donne, Diego
spellingShingle Delle Donne, Diego
Un algoritmo Branch y Cut para un problema de asignación de frecuencias en redes de telefonía celular
author_facet Delle Donne, Diego
author_sort Delle Donne, Diego
title Un algoritmo Branch y Cut para un problema de asignación de frecuencias en redes de telefonía celular
title_short Un algoritmo Branch y Cut para un problema de asignación de frecuencias en redes de telefonía celular
title_full Un algoritmo Branch y Cut para un problema de asignación de frecuencias en redes de telefonía celular
title_fullStr Un algoritmo Branch y Cut para un problema de asignación de frecuencias en redes de telefonía celular
title_full_unstemmed Un algoritmo Branch y Cut para un problema de asignación de frecuencias en redes de telefonía celular
title_sort un algoritmo branch y cut para un problema de asignación de frecuencias en redes de telefonía celular
publishDate Febr
url https://hdl.handle.net/20.500.12110/seminario_nCOM000358_DelleDonne
work_keys_str_mv AT delledonnediego unalgoritmobranchycutparaunproblemadeasignaciondefrecuenciasenredesdetelefoniacelular
_version_ 1807323612310405120

Ejemplares similares