Asignación de frecuencias en redes de telefonía celular basado en el algoritmo Ants

Abstract

En la presente tesis se analiza un algoritmo de asignaci¶on de frecuencias en redes de telefon¶³a celular, llamado algoritmo ants, que ha demostrado ser m¶as e¯caz que m¶etodos cl¶asicos de optimizaci¶on combinatoria, como el simulated annealing o los algoritmos gen¶eticos. La licencia de explotaci¶on del espectro radioel¶ectrico es uno de los costos principales que debe afrontar un operador de telefon¶³a m¶ovil. De este modo, la reducci¶on del n¶umero de frecuencias en el tendido de una red puede suponer un ahorro de inversi¶on considerable. Igualmente, supuesto un espectro ¯jo, la capacidad de tr¶a¯co de una red puede ser aumentada mediante un mejor aprovechamiento de las frecuencias disponibles, en el caso de que una frecuencia pueda reutilizarse en distintos puntos de la red celular. As¶³ la necesidad de operar con terminales ligeros (lo que se traduce en bajos niveles de potencia y, por tanto, en radios de cobertura estrechos), y la posibilidad de reutilizar una misma frecuencia en zonas no interferentes incrementa la capacidad de tr¶a¯co, llevando a los operadores de telefon¶³a m¶ovil a emplazar y distribuir geogr¶a¯camente sus estaciones transmisoras-receptoras a lo largo de redes o mallas m¶as o menos regulares, conocidas como redes celulares. Una red celular puede describirse matem¶aticamente mediante un grafo, es decir, un con- junto de nodos unidos entre s¶³ por aristas. Cada arista puede tener asociado un peso o etiqueta (0, 1, 2, etc.). Los nodos del grafo representan, en el contexto de la telefon¶³a m¶ovil, las celdas o los transmisores (en caso de que cada celda disponga de m¶as de un transmisor) de la red celular mientras que los pesos de las aristas indican la separaci¶on que deben guardar entre s¶³, por motivos de interferencias, las frecuencias correspondientes a las celdas o transmisores que conecta cada arista. El coloreado de un grafo es un problema cl¶asico en combinatoria que consiste en asignar colores (esto es, frecuencias) a los distintos nodos de un grafo de modo que la distancia entre los colores de dos nodos (de¯nida como el valor absoluto de su diferencia) sea mayor o igual al peso de la arista que los une. De este modo, la asignaci¶on de frecuencias en una red celular puede resolverse coloreando el grafo que representa dicha red. El algoritmo ants es un algoritmo de asignaci¶on, basado en la idea de b¶usqueda paralela, que distribuye un cierto n¶umero de agentes (hormigas) a trav¶es de los nodos del grafo, co- lore¶andolos conforme a un criterio de optimizaci¶on local. En cada iteraci¶on cada una de las hormigas se desplaza desde el nodo actual al nodo adyacente que incumple m¶as restricciones (esto es, cuya frecuencia es incompatible con un mayor n¶umero de frecuencias de transmisores vecinos), y sustituye la antigua frecuencia (o color) del nodo por una nueva frecuencia que minimiza el n¶umero de restricciones