Asignación de frecuencias en redes de telefonía celular basado en el algoritmo Ants
Resumen
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