Tesis > Documento


Ver el documento (formato PDF)   Marenco, Javier L..  "Politopos de planificación cromática asociados al problema de asignación de frecuencias en sistemas de radio punto a multipunto"  (2005)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
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.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : 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
Autor : Marenco, Javier L.
Director : Grötschel, Martín
Annegret, Wagler
Jurados : Cornuejols, G.  ; Mundez Diaz. I.  ; Nasini, G.
Año : 2005
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Departamento de Computación
Grado obtenido : Doctor de la Universidad de Buenos Aires en Ciencias de la Computación
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_3788_Marenco
Idioma : Inglés
Area Temática : Computación / Comunicación
Computación / Redes
Palabras claves : ASIGNACION DE FRECUENCIAS; COMBINATORIA POLIEDRAL; BANDWIDTH ALLOCATION; POLYHEDRAL COMBINATORICS
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     http://digital.bl.fcen.uba.ar
Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34