Journal Information

Article Information


Optimización basada en Colonia de Hormigas aplicada al problema de Planificación de Celdas en redes de radio para sistemas de telefonía móvil


Resumen:

En este trabajo se presenta una propuesta computacional para la solución del problema de Planificación de Celdas. La importancia de dicho problema en el área de las Telecomunicaciones lo impone como un referente en la búsqueda de nuevos métodos de optimización. Por la complejidad del problema, en este trabajo se utiliza una relajación discreta del mismo y se propone un modelo matemático para la aplicación de la Meta-heurística Optimización basada en Colonia de Hormigas (ACO). Para el análisis de los resultados se seleccionaron 5 instancias del problema de diferentes tamaños y se aplicó el algoritmo Sistema de Hormigas (AS). Lo resultados muestran que la propuesta explora de manera eficiente el espacio de búsqueda, encontrando la solución óptima a cada instancia con un costo computacional relativamente bajo. Estos resultados son comparados con 3 alternativas evolutivas de referencia internacional que han sido aplicadas a las mismas instancias de estudio, constatándose una mejora significativa por parte de nuestra propuesta.

Abstract:

This paper presents a computational proposal for the solution of the Cell Planning Problem. The importance of this problem in the area of Telecommunications imposes it as a reference in the search for new methods of optimization. Due to the complexity of the problem, this work uses a discrete relaxation and proposes a mathematical model for the application of the Meta-heuristic Ant Colony Optimization (ACO). For the analysis of the results, 5 instances of the problem of different sizes were selected and the Ants System (AS) algorithm was applied. The results show that the proposal efficiently explores the search space, finding the optimal solution for each instance with a relatively low computational cost. These results are compared with 3 evolutionary alternatives of international reference that have been applied to the same study instances, showing a significant improvement by our proposal.


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 1390-6542-enfoqueute-8-02-00056-i001.png, 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.

1390-6542-enfoqueute-8-02-00056-gf1.png

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.

1390-6542-enfoqueute-8-02-00056-gf2.png

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 1390-6542-enfoqueute-8-02-00056-i004.png, donde 1390-6542-enfoqueute-8-02-00056-i005.png representa el conjunto los estados del problema y 1390-6542-enfoqueute-8-02-00056-i006.png 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 1390-6542-enfoqueute-8-02-00056-i007.png 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 1390-6542-enfoqueute-8-02-00056-i008.png, 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 1390-6542-enfoqueute-8-02-00056-i009.png se aplica la expresión (1) seleccionándose el nodo que mayor valor obtenga.

(1)
1390-6542-enfoqueute-8-02-00056-e1.png

En caso contrario 1390-6542-enfoqueute-8-02-00056-i011.png se aplica la siguiente expresión (2) probabilística:

(2)
1390-6542-enfoqueute-8-02-00056-e2.png

En estas funciones, 1390-6542-enfoqueute-8-02-00056-i013.pngrepresenta la cantidad de feromona en el arco 1390-6542-enfoqueute-8-02-00056-i001.png y 1390-6542-enfoqueute-8-02-00056-i014.png la función heurística que evalúa la calidad de transitar del estado 1390-6542-enfoqueute-8-02-00056-i015.png al 1390-6542-enfoqueute-8-02-00056-i016.png.

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.

(3)
1390-6542-enfoqueute-8-02-00056-e3.png

Donde 1390-6542-enfoqueute-8-02-00056-i018.png representa el valor inicial de la feromona y 1390-6542-enfoqueute-8-02-00056-i019.png 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 1390-6542-enfoqueute-8-02-00056-i020.png y su calidad. La expresión se presenta en la expresión (4)

(4)
1390-6542-enfoqueute-8-02-00056-e4.png

3.3 Modelo de aplicación

Para aplicar el algoritmo ACS al problema de Planificación de Celdas, este se define como un grafo totalmente conexo, donde los nodos determinan las posibles locaciones candidatas y las soluciones se representan a partir de 3 vectores 1390-6542-enfoqueute-8-02-00056-i022.png. Donde 1390-6542-enfoqueute-8-02-00056-i023.png contiene las coordenadas 1390-6542-enfoqueute-8-02-00056-i015.png de las ALS, 1390-6542-enfoqueute-8-02-00056-i024.png las coordenadas 1390-6542-enfoqueute-8-02-00056-i016.png y por su parte 1390-6542-enfoqueute-8-02-00056-i025.png es un vector binario cuyo valor 1 representa la asignación de una antena en la ALS correspondiente. La Figura 3 muestra lo que sería la representación matemática de la solución planteada en la escena c) de la Figura 2.

Fig. 3:

Representación matemática de la escena c) de la Figura 2.

1390-6542-enfoqueute-8-02-00056-gf3.png

Por su parte, la función heurística que se establece como base de la expresión probabilística que utiliza la hormiga para cambiar de estado, se define a partir de la expresión (5) donde 1390-6542-enfoqueute-8-02-00056-i027.png determina la cantidad de celdas no cubiertas que se pueden cubrir si se asigna una antena en el ALS j-ésimo y 1390-6542-enfoqueute-8-02-00056-i028.png representa el conjunto de locaciones que aún no tienen antena.

(5)
1390-6542-enfoqueute-8-02-00056-e5.png

Se puede observar que el valor de 1390-6542-enfoqueute-8-02-00056-i030.png es más alto en aquellas ubicaciones donde de asignarse una antena cubriría la mayor cantidad de sectores.

De manera general la Figura 4 presenta el algoritmo ACO aplicado para el caso de estudio.

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.

1390-6542-enfoqueute-8-02-00056-gf4.jpg

Tabla 1

Valores de los parámetros del algoritmo.

ParámetroValorDescripción
β3Peso de la función heurística en la solución
m10Cantidad de hormigas
p10Constante de evaporación global de la feromona
q 0 0.9Factor de exploración
ϕ0.1Constante 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.

1390-6542-enfoqueute-8-02-00056-gf5.png

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).

(6)
1390-6542-enfoqueute-8-02-00056-e6.png

Donde 1390-6542-enfoqueute-8-02-00056-i007.png determina la cantidad de hormigas y 1390-6542-enfoqueute-8-02-00056-i034.png 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.

InstanciasSACHCdssGA8ACS
1498,68E+043,03E+047,86E+051,72E+02
1991,97E+057,86E+041,47E+062,32E+02
2493,34E+051,49E+052,48E+062,66E+02
2996,38E+052,29E+053,00E+062,83E+02
3498,11E+053,80E+054,71E+063,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.

1390-6542-enfoqueute-8-02-00056-gt3.jpg

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.

Bibliografía

1 

Alba, E., Molina, G., & Nebro, A. J. (2011). Disposición óptima de antenas usando CHC multiobjetivo.

2 

Ayuso, R., Ceña, B., Fernández, M., Millán, B., & Saturnina Torre, M. (1999). Comunicaciones móviles GSM. Fundación Airtel.

3 

Bäck, T., Hammel, U., & Schwefel, H. (1997). Evolutionary Computation: Comments on the History and Current State. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 3-17.

4 

Bonabeau, E. (1999). Swarm Intelligence: From natural to artificial systems. Oxford University Press.

5 

Calégari, P., Guidec, F., Kuonen, P., & Kobler, D. (1997). Parallel Island-Based Genetic Algorithm for Radio Network Design. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 86-90.

6 

Cano, J. R., Herrera, F., & Lozano, M. (2003). Using Evolutionary Algorithms as Instance Selection for Data Reduction in KDD: An Experimental Study. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 561-575.

7 

Engelbrecht, A. P. (2006). Fundamentals of Computational Swarm Intelligence. John Wiley & Sons.

8 

Ghazzai, H., Yaacoub, E., Alouini, M.-S., Dawy, Z., & Abu-Dayya, A. (2016). Optimized LTE Cell Planning With Varying Spatial and Temporal User Densities. IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, 1575-1589.

9 

Luna Valero, F. (2008). Meta-heurísticas avanzadas para problemas reales en redes de telecomunicaciones. Málaga: UNIVERSIDAD DE MÁLAGA.

10 

Mouly, M., & Pautet, M. B. (1992). The GSM System for Mobile Communications. France: Paliseau.

11 

Wang, S., Zhao, W., & Wang, C. (2015). Budgeted Cell Planning for Cellular Networks With Small Cells. IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, 4797-4806.

12 

Wang, Y.-C., & Chuang, C.-A. (2015). Efficient eNB deployment strategy for heterogeneous cells in 4G LTE systems. Computer Networks, 297-312.

13 

Xu, X., Saad, W., Zhang, X., Xu, X., & Zhou, S. (2015). Joint Deployment of Small Cells and Wireless Backhaul Links in Next-Generation Networks. IEEE COMMUNICATIONS LETTERS, 2250-2253.

14 

Zhao, W., Wang, S., Wang, C., & Wu, X. (2014). Cell Planning for Heterogeneous Networks: An Approximation Algorithm. IEEE INFOCOM, 1087-1095.

15 

Zhuma, E., & Puris, A. (2015). Asignación de frecuencias en redes móviles GSM utilizando Meta- Heurística ACO. Publicando, 47-64.