1. Introducción
Nuestra generación es testigo de la gran revolución de las telecomunicaciones, solo comparable con la gran revolución industrial. Los avances en las comunicaciones en los últimos años han sido realmente importantes, al punto que lograron transformar la forma de vida de las personas, vivimos en un mundo totalmente interconectado donde el flujo y volumen de información es cada vez mayor. Por lo que es vital hoy en día poder contar con una infraestructura de telecomunicaciones moderna, eficiente y dinámica.
Dentro de los sistemas de comunicaciones, los sistemas móviles han sido de los más desarrollados y los que más rápido han crecido. Estos sistemas se caracterizan por la gran cantidad de usuarios que soportan, por el uso eficiente del espectro y la amplia cobertura. Su funcionamiento se basa en el uso de sistemas celulares (Mouly & Pautet, 1992), donde la disponibilidad del servicio está garantizada por la distribución sistemática de las estaciones bases situadas en la región geográfica que se desea cubrir y la forma en que se utilice la frecuencia.
A partir de la segunda generación el crecimiento de los sistemas móviles fue realmente impresionante. Las redes 2G o GSM(Global System for Mobile Communications) (Mouly & Pautet, 1992) (Ayuso, Ceña, Fernández, Millán, & Saturnina Torre, 1999) llegaron a representar más del 75% de la infraestructura móvil a nivel mundial, debido al éxito y la gran acogida, hoy esta tecnología convive con nuevas generaciones tecnológicas como 3G, 3.5G y 4G.
Entre los problemas más frecuentes en los sistemas móviles se encuentra como diseñar la red que garantice una máxima cobertura. Este problema de optimización supone, entre otras tareas de planificación, seleccionar las localizaciones donde instalar las Estaciones Base (BTSs) que garanticen la cobertura de toda el área. Conocidos en la literatura como: Planificación de celdas (Automatic Cell Planning, ACP) ( Zhao, Wang, Wang, & Wu, 2014) está siendo estudiados para escenarios muy diversos (Wang, Zhao, & Wang, 2015) (Ghazzai, Yaacoub, Alouini, Dawy, & Abu-Dayya, 2016) (Wang & Chuang, 2015) (Xu, Saad, Zhang, Xu, & Zhou, 2015).
Estos problemas caen en la categoría de NP-complejos por lo que han sido sujeto a un gran número de propuestas de solución. Entre los modelos más estudiados se encuentran las Meta-heurísticas Evolutivas (Bäck, Hammel, & Schwefel, 1997) (Cano, Herrera, & Lozano, 2003), las cuales utilizan el principio de la evolución de las especies para explorar espacios de búsqueda complejos. En (Luna Valero, 2008) se pueden encontrar las propuestas de optimización evolutiva más relevantes para este problema.
Además, los algoritmos basados en Inteligencia Colectiva (Bonabeau, 1999) (Engelbrecht, 2006) tales como la Optimización basada en Enjambre de Partículas (PSO) y la Optimización basada en Colonia de Hormigas (ACO) representan otro grupo de modelos computacionales utilizados para resolver problemas de optimización complejos. Específicamente ACO se basa en la tarea que realizan las hormigas naturales para encontrar sus alimentos y fue introducido a principio de los 90 para solucionar problemas discretos.
Esta meta-heurística ha sido aplicada al diseño de redes de radio de los sistemas de telefonía móvil, específicamente al problema de asignación de frecuencias, como se muestra en ( Zhuma & Puris, 2015), donde los autores proponen una alternativa de solución conocida como Colonia de Hormigas en dos Etapas y cuyos resultados mostraron la eficiencia de la propuesta. Sin embargo, en la revisión bibliográfica realizada no se encontró ninguna investigación que abordara la solución del problema de Planificación de Celdas.
Por tal motivo, en este trabajo se presenta una propuesta de la Optimización basada en Colonia de Hormigas para la solución del problema de Planificación de Celdas, utilizando un modelo discreto donde el objetivo es obtener una cobertura máxima con la menor cantidad de antenas. El algoritmo propuesto es probado con varias instancias del problema y comparado con 3 algoritmos evolutivos referentes en el estado del arte.
2. Metodología
Para el desarrollo de este trabajo se realizó una extensa búsqueda bibliográfica ubicando los principales aportes en la solución del problema de Planificación de Celdas. Los resultados mostraron que dicho problema ha sido ampliamente estudiado con Meta-heurísticas Evolutivas y donde se evidenció la ausencia de estudios con algoritmos basados en Colonia de Hormigas.
A partir de estos resultados, se realizó una modelación matemática para aplicar la meta-heurística ACO a una variante relajada y discreta del problema de Planificación de Celdas, basándonos en estudios realizados de la aplicación de algunos algoritmos ACO al problema de Cubrimiento de Conjuntos. Este problema representa una generalidad del problema de Planificación de Celdas por lo que resultó de mucha importancia su análisis.
Por último, seleccionamos 4 algoritmos evolutivos referentes en el estado del arte para probar en un ambiente competitivo, la calidad de nuestra propuesta. Los algoritmos seleccionados son de diferentes naturalezas y formas de exploración.
3. Resultados y Discusión
En este capítulo se describe una forma discreta de Planificación de Celdas, la forma de aplicar las Optimización basada en Colonias de Hormigas, así como el estudio comparativo con otros algoritmos del estado del arte.
3.1 Problema de Planificación de celdas. Definición y estructura
Este problema también conocido como Diseño de Redes de Radio (RND) se describe como un problema de cobertura cuyo objetivo es establecer los lugares donde colocar las antenas logrando que brinden el máximo de cobertura a una zona determinada, con la menor cantidad de antenas posibles. Para resolver dicho problema, es necesario un estudio previo que identifique los lugares donde se pueden colocar las antenas, conocidos como Ubicaciones Candidatas (Available Location Sites, ALS) así como tener en cuenta las características de los tipos de antenas existentes.
Por la complejidad de este problema real, la mayoría de los autores (Calégari, Guidec, Kuonen, & Kobler, 1997) han empleado una forma discreta y relajada que contempla una rejilla cuadrada de 287 x 287 sectores identificados por coordenadas 
, donde existen un conjunto de ALS e igual número de transmisores. Cada trasmisor cubre un área cuadrada de 41 x 41 sectores, donde el cubrimiento total se puede lograr con 49 trasmisores distribuidos regularmente en grupos de 7 x 7. La Figura 1 muestra un ejemplo de una rejilla de 10 x 10, donde las casillas identificadas con el número 2 representan las ubicaciones candidatas.
Fig. 1:
Rejilla de 10 x 10 celdas con 10 ALS distribuidos.
Por su parte la Figura 2 muestra en la escena a) lo que sucede cuando se ubica una antena en una de las localizaciones candidatas y el área que cubre. La ubicación de una antena es representada por el número 3 y cubre de manera total un área de 5 x 5 celdas (identificadas por el número 1). La escena b) presenta un ejemplo, donde aún no se ha cubierto toda la rejilla, debido a una mala asignación de las antenas. Y finalmente la escena c) presenta la solución óptima a este problema, donde se puede observar un cubrimiento total de la rejilla con el número mínimo de antenas.
Fig. 2:
Ejemplos de cubrimiento a) cobertura de una antena; b) cobertura no óptima con 4 antenas; c) solución óptima lograda con 4 antenas.
3.2. Optimización basada en Colonia de Hormigas
Los algoritmos basados en Colonia de Hormigas representan una alternativa de solución para problemas de optimización discretos. Se inspiran en el comportamiento de la Hormigas naturales específicamente en la forma en la que encuentran sus alimentos. Para aplicar estos algoritmos, es necesario modelar el problema como un grafo 
, donde 
representa el conjunto los estados del problema y 
el conjunto de arcos que definen la posibilidad de cambiar de estado.
Para encontrar la solución al problema, los algoritmos ACO dependen de un conjunto de 
hormigas artificiales que son inicialmente asignadas de forma aleatoria a un estado del grafo. Luego, cada una de ellas se mueve por los arcos, utilizando una función probabilística que depende de la deseabilidad del estado y la información heurística del mismo. El recorrido de cada hormiga termina cuando hayan construido una solución. La deseabilidad de los estados depende de un valor numérico que representa los rastros de feromona y determina de forma proporcional cuantas hormigas han seleccionado dicho estado. Este proceso se ejecuta hasta que se ha alcanzado una condición de terminación.
Entre los algoritmos ACO, el Sistema de Colonia de Hormigas (Ant Colony System, ACS) es de los más referenciados. Se diferencia de los demás algoritmos en que utiliza una función de transición de estado seudo-aleatoria, para lo cual el algoritmo incorpora un nuevo parámetro 
, que establece un compromiso entre la exploración de nuevas conexiones y la explotación de la información disponible hasta el momento. De manera que si 
se aplica la expresión (1) seleccionándose el nodo que mayor valor obtenga.
En caso contrario 
se aplica la siguiente expresión (2) probabilística:
En estas funciones, 
representa la cantidad de feromona en el arco y 
la función heurística que evalúa la calidad de transitar del estado 
al 
.
Otro de los aspectos que caracteriza al algoritmo ACS es la actualización en línea paso a paso de los rastros de feromona (ecuación 3). Esta actualización se aplica luego que cada hormiga incorpora un nuevo estado y el objetivo es disminuir la feromona para propiciar la exploración de nuevos estados.
Donde 
representa el valor inicial de la feromona y 
es otro parámetro que favorece el decremento de la feromona.
Por último, el algoritmo realiza una actualización global de los rastros de feromona, involucrando solamente los estados que conforman la mejor solución encontrada hasta el momento 
y su calidad. La expresión se presenta en la expresión (4)
3.4 Estudio experimental
Para el estudio experimental se utilizan 5 instancias del problema, compuestas por 149, 199, 249, 299 y 349 ALS y el objetivo es encontrar el cubrimiento total con un conjunto de 49 antenas (7 x 7).
Los parámetros del algoritmo utilizados para los experimento fueron el resultado de un refinamiento previo de los mismos (por razones de espacio, no fueron incluidas en este trabajo). La Tabla 1 presenta los valores de los mismos y su descripción.
Fig. 4:
Algoritmo ACS para el problema de Planificación de Celdas.
Tabla 1
Valores de los parámetros del algoritmo.
| Parámetro | Valor | Descripción |
| β | 3 | Peso de la función heurística en la solución |
| m | 10 | Cantidad de hormigas |
| p | 10 | Constante de evaporación global de la feromona |
| q
0
| 0.9 | Factor de exploración |
| ϕ | 0.1 | Constante de evaporación local de la feromona |
La Figura 5 presenta la cantidad de iteraciones utilizadas para encontrar la solución óptima, en 10 ejecuciones independientes del algoritmo ACS para las diferentes instancias del problema.
En la instancia 149 se puede observar como el algoritmo describe casi una línea recta interpretándose como un alto grado de convergencia, debido a que representa la instancia más pequeña de las utilizadas. En los otros casos, como las instancias van aumentando de tamaño, se puede apreciar como los cambios en la gráfica van siendo más abruptos. Este resultado es totalmente consistente con el aumento de la complejidad de los escenarios de prueba utilizados.
Para el estudio comparativo se tomaron los resultados de 3 algoritmos evolutivos SA, CHC y dssGA8 presentados en (Alba, Molina, & Nebro, 2011) donde utilizaron las mismas instancias descritas en este trabajo.
Fig. 5:
Cantidad de iteraciones en 10 ejecuciones independientes del algoritmo ACO.
Para las comparaciones se tuvo en cuenta que la estrategia ACO es un modelo constructivo que realiza sucesivas evaluaciones parciales de la función objetivo para decidir el próximo movimiento. Por tal motivo, se utilizó una función que transforma la cantidad de iteraciones utilizadas por el algoritmo, en cantidad de evaluaciones de la función objetivo. Para ello se aplicó la expresión (6).
Donde determina la cantidad de hormigas y 
la cantidad de iteraciones promedio necesarias para alcanzar la solución óptima en cada instancia cuyos valores se presentaron en la figura 5.
Como se puede apreciar en la Tabla 2 hay una disminución considerable de la cantidad de evaluaciones de la función objetivo por parte de la propuesta ACS. Su comportamiento es significativamente mejor que los otros algoritmos evolutivos y representa un resultado a considerar si se tiene en cuenta la importancia de reducir el costo computacional de los algoritmos.
Tabla 2
Comparación de los resultados obtenidos por diferentes estrategias.
| Instancias | SA | CHC | dssGA8 | ACS |
|---|
| 149 | 8,68E+04 | 3,03E+04 | 7,86E+05 | 1,72E+02 |
| 199 | 1,97E+05 | 7,86E+04 | 1,47E+06 | 2,32E+02 |
| 249 | 3,34E+05 | 1,49E+05 | 2,48E+06 | 2,66E+02 |
| 299 | 6,38E+05 | 2,29E+05 | 3,00E+06 | 2,83E+02 |
| 349 | 8,11E+05 | 3,80E+05 | 4,71E+06 | 3,19E+02 |
Para comprobar estos resultados, se aplicó un test no paramétrico de Friedman con un valor de significancia de 0.05, donde el valor obtenido por el test (0.00018) fue menor que el respectivo valor de significancia, por lo cual se encontraron diferencias significativas en los resultados. Para estudiar cada caso en particular, se aplicó el test de comparaciones múltiples de Holms, tomando como muestra de control el algoritmo ACS y aplicándose comparaciones sucesivas con cada uno de los restantes algoritmos. La Tabla 3 muestra valor-p\alpha, donde alpha representa el patrón de comparación en cada caso y su valor depende de la cantidad de comparaciones ejecutadas. Se puede apreciar que en todos los casos el valor-p obtenido por el test es menor que su respectivo valor de alpha, por tal motivo se rechaza la hipótesis nula de igualdad de media en cada caso y se concluye que las diferencias existentes son significativas a favor del algoritmo ACS.
Tabla 3
Comparación de los resultados obtenidos por diferentes estrategias.
4. Conclusiones
En el transcurso de la presente investigación se obtuvo un modelo computacional que permite aplicar la meta-heurística ACO al problema de planificación de celdas. El planteamiento de un modelo discreto del mismo fue fundamental, ya que hizo posible una representación matemática de los resultados acorde con las necesidades del algoritmo de optimización seleccionado. Además, se desarrolló una variante del algoritmo Sistema de Colonia de Hormigas utilizando una función heurística que estimula la selección de los ALS que incorporen mayor cubrimiento a la solución. Los estudios se realizaron a partir de 5 instancias del problema con diferentes dimensiones, conociéndose en todos los casos la solución óptima (49 ALS) y cuyo objetivo fue minimizar el costo computacional (cantidad de iteraciones). En los resultados se pudo observar una taza de convergencia bastante estable en las 10 ejecuciones independientes que se realizaron; esto es inversamente proporcional a la dimensión de las instancias. Además, se realizó un estudio comparativo con 3 de los principales modelos evolutivos presentes en el estado del arte donde se pudo corroborar que aunque todas las propuestas ejecutadas fueron capaces de encontrar el valor óptimo en cada instancia, los resultados alcanzados por la propuesta ACS redujo de manera considerable el costo computacional de la búsqueda. Este resultado avala la necesidad de seguir profundizando en la aplicación de la meta-heurística ACO al problema de planificación de celdas.
. Donde 
contiene las coordenadas 
las coordenadas 
es un vector binario cuyo valor 1 representa la asignación de una antena en la ALS correspondiente. La 
determina la cantidad de celdas no cubiertas que se pueden cubrir si se asigna una antena en el ALS j-ésimo y 
representa el conjunto de locaciones que aún no tienen antena.
es más alto en aquellas ubicaciones donde de asignarse una antena cubriría la mayor cantidad de sectores.