Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto

Mostrar todas las versiones(3)

Lo sistemas de radio punto a multipunto son conjuntos de antenas de radio que proveen acceso inalámbrico a redes de comunicación de voz y datos. Este tipo de sistemas debe ser operado utilizando un cierto espectro de frecuencia de radio, lo cual normalmente produce problemas de capacidad. Por lo tan...

Descripción completa

Detalles Bibliográficos
Autor principal: Marenco, Javier L.
Otros Autores: Grötschel, Martín
Formato: Tesis doctoral publishedVersion
Lenguaje:Inglés
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2005
Materias:
ASIGNACION DE FRECUENCIAS
COMBINATORIA POLIEDRAL
BANDWIDTH ALLOCATION
POLYHEDRAL COMBINATORICS
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n3788_Marenco
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n3788_Marenco_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n3788_Marenco_oai
record_format dspace
spelling I28-R145-tesis_n3788_Marenco_oai2024-09-02 Grötschel, Martín Annegret, Wagler Marenco, Javier L. 2005 Lo sistemas de radio punto a multipunto son conjuntos de antenas de radio que proveen acceso inalámbrico a redes de comunicación de voz y datos. Este tipo de sistemas debe ser operado utilizando un cierto espectro de frecuencia de radio, lo cual normalmente produce problemas de capacidad. Por lo tanto es necesario reutilizar frecuencias, pero este reuso no debe generar interferencia entre las señales. El problema de determinar las frecuencias para los enlaces se conoce como el problema de asignación de frecuencias, y en este tipo de sistemas es un caso especial de los problemas de planificación cromática. Estos problemas son NP-hard, y no existen algoritmos aproximados polinomiales con una garantía de calidad fija. Como los métodos de planos de corte han demostrado ser efectivos para muchos otros problemas de optimización combinatoria, el objetivo es aplicar estos métodos al problema de asignación de frecuencias en sistemas punto a multipunto. Para esto, es necesario estudiar previamente los politopos asociados con el problema. El presente trabajo contribuye a este estudio. Introducimos una formulación del problema de asignación de frecuencias en sistemas punto a multipunto como un problema de programación lineal entera, y definimos los politipos de planificación cromática asociados a esta formulación. Estudiamos en primer lugar la estructura combinatoria de estos politipos, analizando los distintos estados - vacuidad, no vacuidad pero dimensión incompleta, dimensión completa pero inestabilidad combinatoria, y estabilidad combinatoria - a medida que el ancho de banda disponible aumenta. Por otra parte, exploramos las relaciones de los politipos de planificación cromática con el politipo de ordenamiento lineal. Desde el punto de vista geométrico, los politipos de planificación cromática son de un interés particular debido a su simetría. como consecuencia de esta propiedad, desarrollamos una importante herramienta para identificar desigualdades que definen facetas sin requerir información sobre la dimensión del politipo. Esto nos permite identificar las restricciones del modelo de programación lineal entera que definen facetas del politipo asociado. Las restantes restricciones del modelo deben ser reforzadas mediante estructuras basadas en cliques del grafo de interferencia para obtener desigualdades que definen facetas. En particular, las desigualdades de clique en cubrimiento generan una gran familia de facetas, y además presentamos varias clases de facetas que provienen de generalizaciones y variaciones de estas desigualdades. Introducimos clases adicionales de facetas basadas en distintos conceptos, y estudiamos la complejidad de los problemas de separación asociados. Fil: Marenco, Javier L.. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n3788_Marenco eng Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar ASIGNACION DE FRECUENCIAS COMBINATORIA POLIEDRAL BANDWIDTH ALLOCATION POLYHEDRAL COMBINATORICS Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto Chromatic scheduling polytopes coming from the bandwidth allocation problem in point to multipoint radio access systems info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n3788_Marenco_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Inglés
orig_language_str_mv eng
topic ASIGNACION DE FRECUENCIAS
COMBINATORIA POLIEDRAL
BANDWIDTH ALLOCATION
POLYHEDRAL COMBINATORICS
spellingShingle ASIGNACION DE FRECUENCIAS
COMBINATORIA POLIEDRAL
BANDWIDTH ALLOCATION
POLYHEDRAL COMBINATORICS
Marenco, Javier L.
Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto
topic_facet ASIGNACION DE FRECUENCIAS
COMBINATORIA POLIEDRAL
BANDWIDTH ALLOCATION
POLYHEDRAL COMBINATORICS
description Lo sistemas de radio punto a multipunto son conjuntos de antenas de radio que proveen acceso inalámbrico a redes de comunicación de voz y datos. Este tipo de sistemas debe ser operado utilizando un cierto espectro de frecuencia de radio, lo cual normalmente produce problemas de capacidad. Por lo tanto es necesario reutilizar frecuencias, pero este reuso no debe generar interferencia entre las señales. El problema de determinar las frecuencias para los enlaces se conoce como el problema de asignación de frecuencias, y en este tipo de sistemas es un caso especial de los problemas de planificación cromática. Estos problemas son NP-hard, y no existen algoritmos aproximados polinomiales con una garantía de calidad fija. Como los métodos de planos de corte han demostrado ser efectivos para muchos otros problemas de optimización combinatoria, el objetivo es aplicar estos métodos al problema de asignación de frecuencias en sistemas punto a multipunto. Para esto, es necesario estudiar previamente los politopos asociados con el problema. El presente trabajo contribuye a este estudio. Introducimos una formulación del problema de asignación de frecuencias en sistemas punto a multipunto como un problema de programación lineal entera, y definimos los politipos de planificación cromática asociados a esta formulación. Estudiamos en primer lugar la estructura combinatoria de estos politipos, analizando los distintos estados - vacuidad, no vacuidad pero dimensión incompleta, dimensión completa pero inestabilidad combinatoria, y estabilidad combinatoria - a medida que el ancho de banda disponible aumenta. Por otra parte, exploramos las relaciones de los politipos de planificación cromática con el politipo de ordenamiento lineal. Desde el punto de vista geométrico, los politipos de planificación cromática son de un interés particular debido a su simetría. como consecuencia de esta propiedad, desarrollamos una importante herramienta para identificar desigualdades que definen facetas sin requerir información sobre la dimensión del politipo. Esto nos permite identificar las restricciones del modelo de programación lineal entera que definen facetas del politipo asociado. Las restantes restricciones del modelo deben ser reforzadas mediante estructuras basadas en cliques del grafo de interferencia para obtener desigualdades que definen facetas. En particular, las desigualdades de clique en cubrimiento generan una gran familia de facetas, y además presentamos varias clases de facetas que provienen de generalizaciones y variaciones de estas desigualdades. Introducimos clases adicionales de facetas basadas en distintos conceptos, y estudiamos la complejidad de los problemas de separación asociados.
author2 Grötschel, Martín
author_facet Grötschel, Martín
Marenco, Javier L.
format Tesis doctoral
Tesis doctoral
publishedVersion
author Marenco, Javier L.
author_sort Marenco, Javier L.
title Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto
title_short Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto
title_full Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto
title_fullStr Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto
title_full_unstemmed Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto
title_sort politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2005
url https://hdl.handle.net/20.500.12110/tesis_n3788_Marenco
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n3788_Marenco_oai
work_keys_str_mv AT marencojavierl politoposdeplanificacioncromaticaasociadosalproblemadeasignaciondefrecuenciasensistemasderadiopuntoamultipunto
AT marencojavierl chromaticschedulingpolytopescomingfromthebandwidthallocationprobleminpointtomultipointradioaccesssystems
_version_ 1824356169363226624

Ejemplares similares