Resumen:
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.
Abstract:
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.
Citación:
---------- APA ----------
Delle Donne, Diego. (2009). Un algoritmo Branch y Cut para un problema de asignación de frecuencias en redes de telefonía celular. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000358_DelleDonne
---------- CHICAGO ----------
Delle Donne, Diego. "Un algoritmo Branch y Cut para un problema de asignación de frecuencias en redes de telefonía celular". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2009.https://hdl.handle.net/20.500.12110/seminario_nCOM000358_DelleDonne
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000358_DelleDonne.pdf
Distrubución geográfica
