ISSN 0718-3291 Versión Impresa

ISSN 0718-3305 Versión en línea

Volumen 23 N° 4, Octubre - Diciembre 2015

pdf Índice

Aplicación web basada en programación por restricciones para ingeniería de asignación de espectro

 

 

Fabio G. Guerrero1 Juan Francisco Díaz2 Carlos Andrés Delgado2

 

1Escuela de Ingeniería Eléctrica y Electrónica. Universidad del Valle. Calle 13 100-00. Edificio 355, Oficina 2005. Cali, Colombia. E-mail: fabio.guerrero@correounivalle.edu.co
2Escuela de Ingeniería de Sistemas y Computación. Universidad del Valle. Calle 13 100-00. Edificio 331, Oficina 2111. Cali, Colombia. E-mail: juanfco.diaz@correounivalle.edu.co; carlos.andres.delgado@correounivalle.edu.co


RESUMEN

La flexibilidad de uso del espectro radioeléctrico que requieren los paradigmas emergentes, la demanda del espectro radioeléctrico impulsada por las nuevas tecnologías inalámbricas, las nuevas aplicaciones y las políticas gubernamentales orientadas a la masificación del uso de Internet, requieren que las autoridades administradoras del espectro cuenten con herramientas cada vez más inteligentes para hacer su labor de forma eficiente. En este trabajo se presenta el diseño e implementación de una aplicación web de ayuda a las actividades de gestión del espectro radioeléctrico usando programación por restricciones. El diseño incluye un modelo matemático de restricciones de asignación, un modelo matemático de restricciones para interferencias, una base de datos relacional del Cuadro Nacional de Atribución de Bandas de Frecuencia considerando bandas, canales y servicios asociados a la división geopolítica de Colombia, y una base de datos de asignación de operadores. La herramienta permite crear y parametrizar diferentes niveles de restricciones estableciendo diferentes criterios y pesos de costos. En el módulo de análisis de interferencias se tiene en cuenta la ubicación geográfica y las características técnicas de las estaciones transmisoras. La herramienta desarrollada en este trabajo puede ser de utilidad, entre otros, en estudios de optimización de asignación, valoración de políticas de reasignación de espectro, análisis de asignación para maximizar criterios específicos, reducción de costos tecnológicos de implementación de tecnologías específicas y ayudar a identificar variables objetivas en la estimación del precio del espectro. Para facilitar la comprensión y explotación de la aplicación se incluyen varios ejemplos de carácter didáctico.

Palabras clave: Asignación de espectro radioeléctrico, programación por restricciones, planeación de espectro radioeléctrico, gestión inteligente del espectro radioeléctrico, búsqueda combinatoria.


ABSTRACT

The flexibility of spectrum usage required by emerging paradigms, radio spectrum demand driven by new wireless technologies, new applications and government policies oriented to massive use of Internet require spectrum management authorities to have smarter tools to do their work in an efficient way. This paper presents the design and implementation of a web application to support spectrum management activities using constraints programming. The design includes a mathematical model for allocation constraints, a mathematical model for interference constraints, a relational database of the National Allocation Table considering bands, channels and services associated with geopolitical division of Colombia, and an operator allocation database. These tools allow creating and to parameterize different levels of restrictions establishing different costs and weights. The interference analysis module takes into account the geographical location and technical characteristics of transmitting stations. The tool developed in this work can be used, among others, in allocation optimization studies, assessing policies of spectrum reallocation, allocation analysis to maximize specific criteria, reducing technology costs of implementing specific technologies and help identifying objective variables for spectrum price estimation. To facilitate the understanding and exploitation of the application several didactic examples are included.

Keywords: Radio spectrum allocation, constraint programming, radio spectrum planning, intelligent radio spectrum management, combinatorial search.


INTRODUCCIÓN

La mayoría de reguladores nacionales cuentan con sofisticadas herramientas para gestión del espectro y análisis de interferencia. Sin embargo, existen tareas en la labor de las administraciones que por requerir la búsqueda de la mejor solución en grandes espacios de búsqueda toman una gran cantidad de tiempo y, por su naturaleza repetitiva, son propensas a errores humanos. Esto hace que se consuma tiempo de personal altamente capacitado y disminuya la eficiencia en la respuesta en los procesos administrativos. Por esto es importante aprovechar las técnicas computacionales actuales para el desarrollo de herramientas inteligentes que complementen las capacidades de las herramientas de gestión del espectro. Una gestión inteligente puede disminuir los tiempos de respuesta del regulador, haciendo esta tarea más eficiente, con más ingeniería y liberando de operaciones rutinarias y de alto consumo de tiempo a los ingenieros en el regulador. En este contexto la toma de decisiones se torna complicada porque es muy difícil prever todas las formas en las que un resultado puede darse, ya que el tamaño del espacio de búsqueda donde se deben encontrar las soluciones puede ser muy grande. Por esta razón, contar con herramientas de ingeniería que permitan establecer criterios de raciocinio para la búsqueda de una solución cuando se necesita explorar espacios de búsqueda gigantescos ayuda a tomar decisiones más inteligentes, permite evaluar los posibles efectos de las decisiones antes de llevarlas a la práctica y aumentar el grado de control sobre el problema.

El espectro radioeléctrico es un recurso que está limitado por las leyes fundamentales de la naturaleza. Para aplicaciones de comunicaciones a frecuencias por encima de 300 GHz el uso del espectro radioeléctrico es extremadamente difícil por la elevada atenuación de las señales causada por la absorción atmosférica, la muy baja eficiencia para convertir la potencia de alimentación de los dispositivos en potencia radiada y la dificultad para producir niveles útiles de potencia a esas frecuencias [1]. Por otra parte, el gran crecimiento del número de usuarios de dispositivos móviles, las políticas gubernamentales de aumento del acceso a Internet usando tecnologías inalámbricas y la naturaleza de las nuevas aplicaciones móviles, entre otros, han aumentado la necesidad de identificar nuevos segmentos en el espectro radioeléctrico, el que forma un sistema de coordenadas frecuencia-espacio-tiempo. Estudios realizados en Estados Unidos y Europa sobre la ocupación del espectro coinciden en que la utilización promedio del espectro es baja y se caracteriza por no ser homogénea [2-3]. Hoy el uso rígido del espectro es la principal causa de las ineficiencias y que se requiere un uso más flexible [4]. La forma tradicional de asignación donde el principal objetivo es evitar la interferencia entre servicios ha llevado a una subutilización en espacio y tiempo del espectro [5].

Las administraciones necesitan ser flexibles y eficientes en el proceso de la asignación para no frenar la innovación. Por ejemplo, el aumento de número de usuarios de teléfonos inteligentes y tabletas y las nuevas aplicaciones que necesitan mayores velocidades de datos, aparte de requerir nuevos segmentos de espectro para la comunicación entre dispositivos móviles y estaciones base, aumenta los requerimientos de los enlaces de microondas que transportan la información hacia el núcleo de la red del operador. La reacomodación de frecuencias para estos enlaces se hace generalmente hacia bandas más altas del espectro, las que al ya estar siendo usadas por otros servicios requieren una planeación cuidadosa por parte de los reguladores. Reorganizar el espectro de manera inteligente hace posible liberar segmentos que pueden ser aprovechados a lo largo de un territorio nacional por nuevas tecnologías. Un uso eficiente del espectro también se justifica desde el punto de vista del valor. Las ganancias que produce la explotación del espectro electromagnético por parte de las empresas de telecomunicaciones son considerables. Por esta razón, el costo de las licencias de espectro es usualmente alto, a pesar de estar gobernado por las leyes de oferta y demanda, cuando se otorgan por subasta [6]. Un análisis objetivo para estimar el precio base del espectro para subasta pública debería incluir también qué tan fácil sería usar en todo el territorio nacional una misma frecuencia. Un precio demasiado alto del espectro puede retardar su asignación por falta de proponentes y por tanto la introducción de las nuevas tecnologías oportunamente. Un precio del espectro debidamente estimado puede hacer más asequible el espectro y promover mayor competencia.

En este trabajo se presenta el diseño e implementación de una aplicación web basada en programación por restricciones como una herramienta de apoyo en la toma de decisiones para asignar el espectro. El sistema permite experimentar, planear, e investigar nuevas asignaciones o estrategias sin causar interferencia sobre las tareas en marcha. Debido a que los criterios de optimalidad pueden ser configurados por el usuario, la aplicación permite realizar una amplia gama de tareas hacia una gestión más inteligente. La aplicación que se presenta en este trabajo puede ser útil, entre otros, para evaluar el impacto del reordenamiento del espectro, proponer estrategias para la valoración del espectro en subastas, en el estudio de sistemas de gestión de espectro adaptativa, en la síntesis de planes de frecuencia, y en los análisis de los esquemas de asignación. También puede facilitar el estudio de la asignación en dos zonas geográficas contiguas de canales en frecuencias diferentes, o donde se necesite dejar zonas geográficas donde una frecuencia no sea utilizada de forma deliberada, como por ejemplo en las fronteras de países [7] o como se especifica, por ejemplo en la Recomendación ITU-R SM.1049.

En [8] se presenta el uso de algoritmos de alineamiento aplicado al problema de asignación de frecuencias a transmisores. En [9] se presenta el uso de teoría de grafos en la planeación de frecuencias. En [10] se presenta el uso de teoría de juegos al problema de asignación de frecuencias en radio cognitiva. El problema de asignación de frecuencias (canales) a los equipos radiotransceptores en estaciones base donde las variables esenciales son interferencia y distancia ha sido abordado a través de diversas técnicas computacionales como redes neuronales, evolución diferencial, modelos inspirados en la naturaleza, programación por restricciones, estrategias evolutivas y aprendizaje competitivo, y algoritmos de búsqueda tabú. Una evaluación de diferentes algoritmos para este problema específico se presenta en [11]. En este artículo se enfatiza en el diseño e implementación de la aplicación como una herramienta de ingeniería de apoyo a la gestión del espectro. Una discusión con mayor detalle de los aspectos computacionales de la solución se puede ver en [12].

La asignación de espectro desde la perspectiva matemática es un problema de asignación de recursos, pero la información del cuadro de atribución de frecuencias y su asignación a diferentes operadores, estatales o privados, en diferentes zonas geográficas puede llegar a ser muy grande. En ingeniería existe una clase de problemas deterministas donde la solución se obtiene por medio de la búsqueda entre una gran cantidad de opciones. Entre este tipo de problemas se encuentran los problemas de planificación y entre ellos están algunos de los problemas de asignación de espectro. La programación por restricciones (constraint programming) es una técnica de computación usada, entre otras cosas, para resolver problemas de optimización combinatoria a gran escala. Los criterios de restricción, definidos por el usuario, permiten precisar las características del tipo de solución que se está buscando, de forma flexible, y aprovecharlas de forma operativa para reducir el espacio de búsqueda y, por tanto, acelerar el proceso de encontrar soluciones. La programación por restricciones, a diferencia de los paradigmas donde los resultados finales se traducen en estimaciones de probabilidad, entrega soluciones exactas. Los compromisos fundamentales son el tiempo de ejecución y la capacidad de cómputo. Una de las ventajas de usar programación por restricciones, es que esta puede ser utilizada no solo para reducir el tamaño del espacio de búsqueda, sino también para orientar la búsqueda y encontrar rápidamente al menos una solución que mejore la actual de acuerdo al criterio que se desee mejorar (por ejemplo, contigüidad, disponibilidad, o ambos). La estrategia de asignación de canales usando programación por restricciones no solo puede servir a los entes reguladores, sino a los mismos operadores para el caso de tecnologías que permiten agregación de canales. Existen muchos ejemplos de uso de la programación por restricciones en la solución de problemas del mundo real. El Grupo de Investigación en Ambientes Visuales de Programación Aplicativa de la Universidad del Valle y la Universidad Javeriana (AVISPA3), por ejemplo, ha aplicado este paradigma a problemas de programación de las aperturas de compuertas de una represa [13], de asignación de horarios y salones de una universidad [14-15], de reconfiguración de redes de distribución de energía eléctrica [16-18], problemas de asignación de evaluadores para un evento científico [19-20], de despacho económico de plantas de generación de energía [21], de reconfiguración de una red de antenas celulares para mejorar la calidad del servicio[22] y simulación del comportamiento de diferentes agentes en el mercado eléctrico colombiano [23-24].

El artículo se encuentra organizado de la siguiente forma. Inicialmente, se presenta la arquitectura del diseño, el modelo matemático, y las herramientas usadas en la construcción de la aplicación. Posteriormente, se presentan varios ejemplos de los resultados que permite obtener la aplicación desarrollada. Después, se presenta una discusión de los resultados, identificando las variables fundamentales del desempeño, ventajas y desventajas del sistema implementado. Finalmente, se resumen las principales conclusiones del trabajo.

APLICACIÓN Y MODELO DE RESTRICCIONES

Descripción de la aplicación: La Figura 1 muestra el diagrama general de la aplicación CAFESA (Constraint-based Application for Engineering Spectrum Allocation).



Figura 1. Aplicación CAFESA.

La aplicación está diseñada en modo cliente-servidor. El servidor web y el motor del modelo de restricciones se encuentran instalados en un servidor Blade de la Escuela de Ingeniería de Sistemas y Computación de la Universidad del Valle. La aplicación acepta como entrada un archivo en formato XML, el que especifica las necesidades de asignación de canales por parte de los operadores. El módulo de parametrización de restricciones permite definir criterios, fortalezas, debilidades y costo de las restricciones. La salida entrega los resultados en forma gráfica con la posibilidad de guardar la información en formato XML. Las entradas y salidas de datos se especifican en el formato XML con el fin de facilitar la interoperabilidad con otros sistemas y aplicaciones web. El motor de la base de datos es PostgreSQL y la ejecución del modelo de programación por restricciones se realiza en Mozart/Oz (http://mozart-oz.org). En la base de datos se encuentra sistematizada la información del CNABF (Cuadro Nacional de Atribución de Bancas de Frecuencia)4, incluyendo bandas de frecuencias, canalización, servicios definidos para las canalizaciones y operadores haciendo uso del espectro. Dado que la asignación del espectro es frecuencia-espacio-temporal se ha incluido en la base de datos el concepto del uso del espectro por divisiones territoriales (nación, regiones y ciudades).

La Figura 2 muestra los diferentes módulos de gestión de la aplicación. El grupo de módulos de gestión de la base de datos permite realizar las tareas de creación y modificación de frecuencias, canalización, servicios, operadores y zonas geográficas. El grupo de módulos de gestión XML permite crear un archivo en formato XML que sea entendido por el motor del modelo de programación por restricciones a partir de los requerimientos de entrada del usuario. El módulo de administración de entradas permite ingresar, ver las solicitudes y el estado de la banda actual, almacenar y borrar archivos XML de entrada. El módulo de administración de salidas permite ingresar, ver las soluciones, descargar, almacenar y borrar archivos XML de salida. Las consultas a la base de datos se pueden realizar por las diferentes combinaciones de divisiones territoriales, bandas generales, rangos de frecuencias y operadores.



Figura 2. Módulos de gestión CAFESA.

Descripción del modelo matemático: El modelo matemático está planteado en términos de restricciones de forma que pueda ser llevado fácilmente a una implementación con herramientas de programación por restricciones. En la representación de la asignación del espectro se emplean matrices binarias como lo muestra la Figura 3.



Figura 3. Representación matricial de asignación.

A continuación se describen los aspectos más importantes del modelo matemático de restricciones que funciona en el núcleo de la aplicación CAFESA.

Entradas: L={l1, lk}: Conjunto de etiquetas de identificación de operadores. El concepto de operadores se refiere a entes de carácter estatal o privado que hagan o deseen hacer uso del espectro radioeléctrico.

S = {chj : 1 j n}: Conjunto de canales definidos para un servicio dado en el CNABF para una zona geográfica GR.

U = {u L: u es un operador asignado que ya tiene canales asignados en S}

R = {r L: r es un operador solicitando canales en S}

request [r] *: Número de canales solicitados por el operador r eR.

Occupancy *: Número de operadores simultáneos permitidos por canal.

Separation *: Separación de canales mínima entre diferentes operadores.

kca {0, 1}: Indica si la asignación actual de un operador en U R debe ser mantenida.

Variables internas: Número de operadores usando actualmente canales en 5 : nu = |U|;0 nu n.

Número de operadores solicitando canales: nr = |R|;0 nr n.

T= U R: Conjunto de operadores ya establecidos y solicitantes (un operador ya establecido puede solicitar asignación adicional).

A[u, ch]: Matriz de asignación de canales para el operador u y canal ch previo al proceso de asignación. Esta información es tomada de la base de datos.

Asr[ch] {0, 1}: Indica si un canal ch está siendo usado en alguna división geográfica de GR.

CH[j] {0, 1}: Indica si chj está disponible. CH[j] = 1 si y solo si chj está disponible.

reserved [j] {0, 1}: indica si chj está reservado.
reserved [j] = 1 si y solo si chj no es utilizable.

unusable [j] {0, 1}: indica si chj no es utilizable.
unusable [j] = 1 si y solo si chj no es utilizable.

Salidas: A'[u, ch]: Matriz de asignación de canales para el operador u y canal ch posterior al proceso de asignación.

Restricciones:

Disponibilidad de canales: La disponibilidad del canal chj está determinada por la siguiente restricción, ecuación (1).

(1)

Esta evaluación se realiza para cada canal chj S.

Ocupación: Están permitidos Occupancy operadores por canal (esta restricción, ecuación (2), permite tener en cuenta, por ejemplo el uso del mismo espectro por dos o más operadores diferentes en distintos horarios).

(2)

Canales no utilizables: Los canales marcados como inutilizables u ocupados no pueden ser usados, ecuación (3).

(3)

Asignación a nuevos operadores: Esta restricción, ecuación (4), permite asignar canales a los operadores solicitantes nuevos.

(4)

Asignación a operadores existentes: Esta restricción, ecuación (5), permite asignar a operadores existentes nuevos canales y mantener la asignación de los canales ya asignados.

(5)

Separación de canales: Mediante esta restricción, ecuación (6), se asegura que exista una separación mínima entre cualquier par de canales de diferentes operadores.

(6)

Chsepj {0, 1}: Indica si se cumple o no el requerimiento de separación para el canal Chj.

Restricciones triviales: La siguiente restricción, ecuación (7), asegura mantener la asignación actual de un operador si así se solicita:

(7)

La siguiente restricción, ecuación (8), asegura no modificar la asignación de operadores que no han solicitado asignación:

(8)

Análisis de interferencias: Para un análisis detallado de interferencias se deben emplear herramientas avanzadas como ICS Telecom. El módulo de análisis de interferencias implementado en este trabajo emplea un algoritmo sencillo basado en modelos de pérdidas de propagación y atenuación por máscara en el receptor. La salida del módulo es un valor booleano que indica presencia o ausencia de un valor de alta probabilidad de interferencia para una estación entrante. El algoritmo de este módulo es el siguiente:

Modelo de interfaces
• Se hace un filtrado de las estaciones por banda de frecuencia.
• Solo se determina si al ingresar unas estaciones se supera un tope en dB de interferencia
• El modelo solo determina si una solución es válida o bien si es una solución con advertencia de interferencia. En el modelo se toman coordenadas en dos dimensiones (x,y) respecto de un punto de referencia, el usuario ingresa coordenadas georreferenciadas.
• Unidades de trabajo: potencia en dBm, interferencias en dBm, distancias en kilómetros, frecuencias en kiloHertz (kHz).

Datos de entrada
• Fc Frecuencia central en kHz de los canales en la banda
• C Número de canales
• NE Número de estaciones que ya se encuentran en la zona
• NI Número de estaciones que los operadores desean ingresar
• Le Lista de canales de transmisión de una estación e
• ?e Valor en dBm de interferencia permitido en una estación e
• Pec Potencia de transmisión en dBm de una estación e en un canal c
• He Altura en metros de una estación e
• HTe Factor de corrección de transmisión de una estación e
• We Ancho en banda en kHz de una estación e
• Oe Operador de la estación e
• Xe Posición en x en km de una estación e, respecto de un plano normalizado
• Ye Posición en y en km de una estación e, respecto de un plano normalizado
• EP = {ek, 1 k NP} Es el conjunto de estaciones que actualmente se encuentran en la zona de trabajo
• EI = {ek, 1 k NI}Es el conjunto de estaciones que se desean ingresar a la zona de trabajo
• ET = EP EI Es el conjunto total de estaciones

Variables de decisión
• Sol {0, 1} Se utiliza para indicar si la solución del problema es válida
• IEiEpCei,ep,c Indica el nivel de interferencia de una estación que ingresa ei sobre canal de transmisión c de las estaciones existentes ep
• MaxIntEiEPei,ep {0, 1} Indica el máximo nivel de interferencia de una estación ei calculado para cada estación existente ep
• IntEIEPei,ep {0, 1} Indica si una estación que ingresa ei supera el nivel de interferencia permitido en cada estación existente ep
• InteTEIEPCep,c Es el nivel de interferencia percibido en un canal c de una estación existente ep debido a todas las estaciones que ingresan.
• MaxIntTEIEPep Es el máximo nivel de interferencia que percibe una estación ep debido a todas las estaciones que ingresan
• IntTEIEPep {0, 1} Indica si una estación que existe ep percibe un nivel de interferencia mayor al tolerado debido a las estaciones que ingresan
• IntETEPCep,c Es el nivel de interferencia percibido en un canal c de una estación existente ep debido al resto de estaciones
• MaxIntETEPep Es el máximo nivel de interferencia percibido en una estación existente ep debido al resto de estaciones
• IntETEPep {0, 1} Indica si una estación existente ep percibe un nivel de interferencia mayor al permitido debido al resto de estaciones
• InteTEPECICei,c Es el nivel de interferencia percibido en un canal c de una estación que ingresa ei debido a todas las estaciones que existen
• MaxIntTEPEIei Es el máximo nivel de interferencia percibido en una estación que ingresa ei debido a todas las estaciones que existen
• IntTEPEIei {0, 1} Indica si una estación que ingresa ei percibe un nivel de interferencia mayor al permitido debido a las estaciones existentes
• IntETEICei,c Es el nivel de interferencia percibido en un canal c de una estación que ingresa ei debido a todas las estaciones
• MaxIntETEIei Es el máximo nivel de interferencia percibido en una estación que ingresa ei debido a todas las estaciones
• IntETEIei {0, 1} Indica si una estación que ingresa ei percibe un nivel de interferencia mayor al permitido debido a las estaciones que ingresan
• S1 {0, 1} Indica el efecto de interferencia de una estación que ingresa es mayor al permitido en una estación existente
• S2 {0, 1} Indica si el efecto de interferencia del conjunto las estaciones que ingresan es mayor al permitido en una estación existente
• S3 {0, 1} Indica si el efecto de interferencia del conjunto total de estaciones es mayor al permitido en una estación existente.

Funciones auxiliares
• d(x0, y0, X1, y1) Esta función calcula la distancia cartesiana entre dos puntos en un plano de dos dimensiones
• signal_level(Pe1, He1, Fc1, Fc0, We1, HTe1, d) Calcule la potencia de la señal que se percibe en la frecuencia central de un canal c0 de una estación e0 debido a la transmisión en la frecuencia central de un canal con potencia P en dBm, con altura H en metros, con ancho de banda W, con factor de corrección a la transmisión HT y con distancia d en km.

Restricciones
Caso 1. Interferencia de una estación solicitante a las estaciones presentes: El nivel de interferencia en un canal c0 de una estación presente ep debido a una estación que ingresa ei es la suma de los aportes de nivel de señal de cada uno de sus canales c;, ecuación (9).

(9)

El máximo nivel de interferencia percibido en una estación presente ep debido a una estación que ingresa ei es la suma de los niveles percibidos en sus canales c0, ecuación (10).

(10)

Una estación ingresa ei interfiere una estación presente ep si y solo si el máximo nivel de interferencia en dBm es mayor al nivel permitido, ecuación (11).

(11)

Una estación que ingresa ei no interfiere una estación presente ep si y solo si el máximo nivel de interferencia en dBm es menor o igual al nivel de interferencia permitido, ecuación (12).

(12)

Caso 2. Interferencia del conjunto de estaciones solicitantes a las estaciones presentes: El nivel de interferencia percibido en un canal co de una estación presente ep es la suma de aportes de cada una de las estaciones que ingresan, ecuación (13).

(13)

iEl nivel máximo de interferencia percibido en una estación presente ep debido al conjunto de estaciones que ingresan, es la suma de los valores encontrados para cada uno de los canales co de la estación presente, ecuación (14).

(14)

El conjunto de estaciones que ingresan interfieren a una estación presente ep si el máximo nivel de interferencia en dBm encontrado en una estación supera el valor de interferencia permitido, ecuación (15).

(15)

El conjunto de estaciones que ingresan no interfieren a una estación presente ep si y solo si el máximo nivel de interferencia en dBm encontrado en una estación es menor o igual al valor de interferencia permitido, ecuación (16).

(16)

El conjunto de estaciones que ingresan no interfieren a una estación presente ep si y solo el máximo nivel de interferencia en dBm encontrado en una estación es menor o igual al valor de interferencia permitido, ecuación (17).

(17)

Caso 3. Interferencia del total de estación sobre las estaciones presentes: El nivel de interferencia percibido en una estación presente ep debido al resto de estaciones es la suma de aportes de cada una de las estaciones, ecuación (18).

(18)

El máximo nivel de interferencia percibido en una estación existente ep debido al resto de estaciones es la suma de los percibidos en cada uno de sus canales c0, ecuación (19).

(19)

Una estación existente ep se encuentra interferida debido al resto de estaciones si el máximo nivel de interferencia es mayor al permitido, ecuación (20).

(20)

Una estación existente ep no se encuentra interferida debido al resto de estaciones si y solo si el máximo nivel de interferencia es menor o igual al permitido, ecuación (21).

(21)

Restricciones de solución del problema: Si existe interferencia en, al menos, una estación presente ep debido a una estación que ingresa ei entonces S1 es 1 en caso contrario es 0, ecuación (22).

(22)

Si existe interferencia en estación presente ep debido al conjunto de estaciones que ingresan entonces S2 es 1 en caso contrario 0, ecuación (23).

(23)

Si existe interferencia en estación presente ep debido al conjunto total de estaciones entonces S3 es 1 en caso contrario 0, ecuación (24).

(24)

Si existe interferencia en alguna de las estaciones que ingresan ei debido al conjunto de estaciones existentes entonces S4 es 1 en caso contrario 0, ecuación (25).

(25)

Si existe interferencia en alguna de las estaciones que ingresan debido al conjunto total de estaciones existentes entonces S5 es 1 en caso contrario 0, ecuación (26).

(26)

Si existe interferencia en alguna de las estaciones presentes la solución es inviable en caso contrario es viable, ecuación (27).

(27)

EXPERIMENTACIÓN Y RESULTADOS

La experimentación se realizó en dos fases: primero, respecto de la asignación de espectro como tal; y segundo, respecto del análisis de interferencias.

Análisis de asignación del espectro: Para estudiar la aplicabilidad de este desarrollo a casos reales, y ante la dificultad de contar con datos reales para este efecto, se diseñó de manera sintética una serie de escenarios con diferentes características: número de canales de la banda (menos de 20 canales, entre 20 y 100 canales, más de 100 canales), bandas con o sin asignación previa, número de operadores con requerimientos de nuevos canales (3, 4, 6 ,8, 10 y 20 operadores), número de canales pedidos por operador (homogéneo, es decir, el mismo número para todos los operadores, o heterogéneo, es decir, distinto número para cada operador), y tope (10 u 80). También se diseñaron tres escenarios en los cuales es imposible encontrar una asignación que satisfaga los requerimientos solicitados, ya sea porque es imposible no violar el tope, o porque los requerimientos sobrepasan la capacidad de la banda. En la Tabla 1 se describen las entradas:


Tabla 1. Escenarios de pruebas.

Una vez definidos los escenarios de prueba, se definieron los parámetros técnicos para la ejecución de las pruebas (tiempo máximo para búsqueda de soluciones, motor de búsqueda y estrategia de distribución a utilizar), los parámetros que se medirían para los análisis posteriores (número de soluciones encontradas, mejor costo encontrado), y los grupos de pruebas para analizar diversos aspectos (sensibilidad al tamaño de la entrada, a la distribución de asignación en la banda, a la homogeneidad o heterogeneidad de los requerimientos, al tamaño de los requerimientos, y a la flexibilidad de las restricciones).

Analizando los resultados podemos concluir lo siguiente:

• El tiempo asignado para la búsqueda de soluciones (hasta 20 segundos) fue bastante reducido; en la vida real se podría contar con bastante más tiempo que este. En todo caso, 20 segundos no fueron suficientes para encontrar soluciones óptimas.
Las estrategias de distribución predefinidas siempre perdieron contra las estrategias de distribución específicas dependientes del problema. Es fundamental usar estrategias orientadas por el problema.
• En general, las diferentes estrategias de distribución dependientes del problema no influyen en la calidad de la solución encontrada, aunque sí en el espacio necesitado para hacerlo.
Definitivamente enfocar esfuerzos en definir estrategias de distribución orientadas por el problema tiene un efecto mucho más positivo que el contar con mejores recursos de máquina (procesadores más rápidos o más memoria RAM).

Análisis de interferencia: La Tabla 2 muestra los valores de las distintas estaciones. X e Y representan las estaciones solicitantes y A, B y C las estaciones existentes.


Tabla 2. Parámetros de estaciones para análisis de interferencia.

Las distancias entre la estación X y las estaciones A, B y C son 11 km, 17 km y 20 km respectivamente. Las distancias entre la estación Y y las estaciones A, B y C son 28 km, 16 km y 15 km respectivamente. La atenuación por máscara espectral de los receptores es 10 dB/octava. En la Tabla 2 se asume que los canales tienen 1 MHz de ancho de banda y la frecuencia indicada es la frecuencia central de cada canal. La variable Y es el nivel de señal de interferencia aceptable [25]. La aplicación web que se reporta en este artículo ha sido dada a conocer a la Agencia Nacional del Espectro (ANE) en Colombia, siendo recibida con interés para el desarrollo de aplicaciones futuro. Si bien en el módulo de análisis de interferencias se puede incluir la ecuación de cualquier modelo de propagación analítico, en este ejemplo se considera el modelo de Hata para zonas abiertas y rurales:

(28)

En la ecuación (28), la frecuencia fc está en MHz, la distancia d en km, la altura de las antenas htx en m. El factor de corrección altura antena receptora, ?(hrx), para zonas abiertas y rurales se puede ignorar.

Con los valores de la Tabla 2, para el caso 1 (efecto individual de cada estación solicitante sobre cada estación existente), los valores de la interferencia producida por la estación X sobre las estaciones A, B, y C son -97,7542 dBm, -106,049 dBm y -108,398 dBm, respectivamente. Los valores de la interferencia producida por la estación Y sobre las estaciones A, B, y C, en dBm, son -100,172 dBm, -92,7786 dBm y -91,7973 dBm, respectivamente. Debido a que en todos los casos la interferencia estuvo por debajo de los umbrales (g) de cada estación receptora, IntEIEPei,ep = 1 para cada una de las seis posibles combinaciones. En este ejemplo se puede observar que la variable de mayor incidencia sobre la interferencia es la distancia.

En la Tabla 3 se muestran los valores correspondientes a un ejemplo de una estación que ingresa X, en un área donde se encuentran las estaciones A, B y C, las distancias de X a A, B y C son 11,3 km, 7,4 km, 2,7 km, respectivamente.


Tabla 3. Parámetros de estaciones para análisis de interferencia.

Los valores de interferencia encontrados son -109,13 dBm en la estación A, -75,19 dBm para la estación B y -75,10 dBm para la estación C, lo que claramente indica que las estaciones B y C se encuentran interferidas, ya que se superan los umbrales.

En este ejemplo, al igual que en el anterior, se encuentra que la variable de mayor efecto en la interferencia es la distancia. Aunque el valor de potencia de transmisión de la estación X es mayor al del ejemplo anterior, existe interferencia sobre las estaciones presentes más cercanas.

Análisis de cuadro nacional de atribución de bandas de frecuencia: La Figura 4 muestra la estructura básica del cuadro nacional de atribución de bandas de frecuencia, el que a su vez está basado en el cuadro general de las regulaciones de radio (RR) de ITU-R.



Figura 4. Organización y uso geográfico del espectro radioeléctrico.

Las bandas de frecuencia normalmente están asociadas a diferentes servicios y para un servicio específico existen una canalización definida. Para el caso de Colombia el CNABF define 81 servicios a título primario y 35 a título secundario. Los canales asociados a un mismo servicio pueden estar en bandas de frecuencia no contiguas. La distinción geográfica es de importancia porque no siempre es posible lograr para un mismo servicio una asignación idéntica en una misma zona geográfica como ocurre por ejemplo, en el caso de la televisión.

La reorganización del espectro es una tarea de mucha importancia. Facilitaría, por ejemplo, a los operadores de sistemas de comunicaciones móviles tener bloques de espectro más grandes y contiguos, facilitaría la investigación en nuevas tecnologías inalámbricas, facilitaría analizar costos de migración tecnológica, etc.

Considerando las 556 bandas de frecuencia definidas en el CNABF entre 0 Hz y 300 GHz, servicios a título primario y secundario, un promedio de cuatro servicios por banda, un promedio de diez canales por banda y las divisiones territoriales de Colombia (1023 municipios, 32 departamentos y seis divisiones territoriales), se puede tener una mejor idea del tamaño del espacio de búsqueda de soluciones de este problema. Si se agrega el uso del espectro dependiendo de la hora del día, el espacio sería aún más grande, aunque en la práctica muchas asignaciones no serán técnicamente viables ni de interés.

En el contexto de los valores del ejemplo de esta sección se puede ver que la variable que más efecto tiene en la interferencia es la distancia. El análisis de interferencia que se ha considerado solo tiene en cuenta las pérdidas de propagación y la atenuación por máscara espectral en el receptor. En un entorno más avanzado se puede considerar el resultado que brindan herramientas especializadas en análisis de propagación (por ejemplo Seamcat, Sms4dc, ICS Telecom), las que consideran muchos más detalles y pueden hacer predicciones más precisas.

CONCLUSIONES

En un ambiente en donde la demanda por el espectro radioeléctrico aumenta de manera casi constante debido a la gran dinámica en el desarrollo del amplio espectro de tecnologías inalámbricas y los nuevos servicios que posibilitan el aumento de la capacidad de transmisión, es muy útil que las autoridades que administran el espectro puedan acceder a herramientas inteligentes que complementen las capacidades de las herramientas de gestión y análisis de interferencia con las que usualmente cuentan. La programación por restricciones permite expresar los problemas a alto nivel y debido a que las expresiones están formadas por restricciones ofrece una estrategia muy versátil para probar diferentes esquemas bajo distintos criterios. Sin embargo, para resolver problemas mediante programación por restricciones se requiere tener un sólido modelo matemático del problema con un nivel de abstracción adecuado que permita establecer relaciones entre las entidades del modelo que sean de interés para el usuario. La programación por restricciones es especialmente apropiada para sistemas complejos de composición jerárquica donde el razonamiento está basado en reglas, como ocurre en el caso de problemas de asignación espectral. Las aplicaciones basadas en programación por restricciones brindan una muy buena alternativa puesto que el número de combinaciones en el contexto de la asignación espectral puede llegar a ser muy grande, permitiendo probar diferentes esquemas de asignación bajo una gran variedad de criterios de optimalidad antes de llevar a la práctica cualquier asignación. El módulo de análisis de interferencia utilizado en este trabajo ha considerado un modelo de pérdidas basado en un modelo de propagación de baja complejidad. Sin embargo, es posible incorporar modelos más avanzados debido a que en la estructura del modelo de restricciones el efecto de la interferencia se convierte en una variable boolena de viabilidad de asignación.

Para amplificar la utilidad de aplicaciones como la mencionada en este artículo, sería deseable ofrecer al usuario final una interfaz mucho más cercana a su objeto de trabajo que le permita especificar en un lenguaje más natural el tipo de solución que desea, y traducir de forma transparente al usuario, esta especificación en términos de las máquinas de búsqueda y estrategias de distribución que se encuentran implementadas por debajo.

3http://avispa.univalle.edu.co
4http://www.ane.gov.co/cnabf/

AGRADECIMIENTOS

Los autores desean agradecer al ingeniero Carlos Martínez y a los estudiantes de pregrado de la Universidad del Valle María Cruz y Felipe Vargas por sus aportes en el desarrollo del proyecto. Igualmente a la Universidad de Valle por la financiación de este proyecto (código 2665).

REFERENCIAS

[1] C.M. Armstrong. "The Truth About Terahertz". IEEE Spectrum. Vol. 49, Issue 9, pp. 28-33. September, 2012. ISSN: 0018-9235. DOI: 10.1109/MSPEC.2012.6281131

[2] V. Valenta, R. Marsalek, G. Baudoin, M. Villegas, M. Suarez and F. Robert. "Survey on spectrum utilization in Europe: Measurements, analyses and observations". Cognitive Radio Oriented Wireless Networks & Communications (CROWNCOM), Proceedings of the Fifth International Conference, pp. 1-5. Cannes, Francia. 2010.

[3] M.A. McHenry, D. McCloskey and G. Lane-Roberts. "Spectrum Occupancy Measurements Location 4 of 6: Republican National Convention New York City". New York, EEUU. 2005. Date of visit: January 3, 2015. URL: http://www.sharedspectrum.com/wpcontent/uploads/4_NSF_NYC_Report.pdf

[4] J.H. Reed, J.T. Bernhard and J. Park. "Spectrum Access Technologies: The Past, the Present, and the Future". Proceedings of the IEEE. Vol. 100, Special Centennial Issue, pp. 1676-1684. May, 2012. ISSN: 0018-9219: DOI: 10.1109/JPROC.2012.2187140.

[5] M.J. Marcus. "Spectrum Policy for Radio Spectrum Access". Proceedings of the IEEE. Vol. 100, Special Centennial Issue, pp. 1685-1691. May, 2012. ISSN: 0018-9219. DOI: 10.1109/JPROC.2012.2187132.

[6] E.M. Noam. "The Economists' Contribution to Radio Spectrum Access: The Past, the Present, and the Future". Proceedings of the IEEE. Vol. 100, pp. 1692-1697. May, 2012. ISSN: 0018-9219. DOI: 10.1109/JPROC.2012.2187133.

[7] D. Makris, G. Gardikis and A. Kourtis. "Quantifying TV White Space Capacity: A Geolocation-Based Approach". IEEE Communications Magazine. Vol. 50, Issue 9, pp. 145-152. September, 2012. ISSN: 01636804. DOI: 10.1109/MCOM.2012. 6295725.

[8] S. Hurley and D.H. Smith. "Fixed spectrum frequency assignment using natural algorithms". GALESIA. First International Conference. Sheffield, Inglaterra. 1995.

[9] A. Quellmalz. A. Knalmann and B. Muller. "Efficient frequency assignment with simulated annealing". Antennas and Propagation. Ninth International Conference. Vol. 2, pp. 301-304. Eindhoven, Holanda. 1995.

[10] C. An, L. Zhang and W. Liu. "A Spectrum Allocation Algorithm Based on Matching Game". Wireless Communications, Networking and Mobile Computing. WiCom'09. 5th International Conference. Pekin, China. 2009.

[11] D.H. Smith, L. A. Hughes, J.N.J. Moon and R. Montemanni. "Measuring the Effectiveness of Frequency Assignment Algorithms". Vehicular Technology, IEEE Transactions. Vol. 56, Issue 1, pp. 331-341. 2007. ISSN: 0018-9545. DOI: 10.1109/TVT.2006.883770.

[12] C.A. Delgado Saavedra, J.F. Díaz and F.G. Guerrero. "Design and implementation of a prototype application for spectrum allocation using constraint programming". VIII Congreso Colombiano de Computación. Armenia, Colombia. 2013.

[13] J.F. Diaz Frias y C. Rueda Calderon. "VISiR: Software de soporte para la toma de decisiones de vertimiento de agua en la represa del Alto Anchicayá usando programación concurrente por restricciones". Ingeniería y Competitividad. Vol. 3 N° 2, pp. 7-14. 2001. ISSN: 0302-9743. DOI: 10.1007/978-3-540-31845-3_25.

[14] J.F. Díaz Frías, L.O. Quesada Ramírez, C. Rueda Calderón, C. García Ordóñez and S. Cetina. "PATHOS: Object-Oriented Concurrent Constraint Timetabling for Real World Cases". XXVIII Conferencia Latinoamericana de Informática. Montevideo, Uruguay, 2002.

[15] A. Delgado, J.A. Pérez, G. Pabón, R. Jordan, J.F. Díaz and C. Rueda. "An interactive tool for the controlled execution of an automated timetabling constraint engine". Proceedings of the Second international conference on Multiparadigm Programming in Mozart/Oz. Vol. 3389 of LNCS, P. Roy, Ed. Springer Berlin Heidelberg, pp. 317-327. 2005. ISSN: 0302-9743. DOI: 10.1007/978-3-540-31845-3_26.

[16] N.G. Caicedo, C.A. Lozano, J.F. Díaz, C. Rueda, G. Gutiérrez and C. Olarte. "Loss reduction in distribution networks using concurrent constraint programming". Probabilistic Methods Applied to Power Systems, International Conference. Pekín, China. 2004.

[17] J.F. Díaz, G. Gutiérrez, C.A. Olarte and C. Rueda. "CRE2: A CP Application for Reconfiguring a Power Distribution Network for Power Losses Reduction". Principles and Practice of Constraint Programming-CP 2004 SE-92. Vol. 3258 of LNCS, M. Wallace, Ed. Springer Berlin Heidelberg, pp. 813-814. 2004. ISSN: 0302-9743. DOI: 10.1007/978-3-540-30201-8_92.

[18] J.F. Díaz, G. Gutiérrez, C.A. Olarte and C. Rueda. "Using Constraint Programming for Reconfiguration of Electrical Power Distribution Networks". Multiparadigm Programming in Mozart/Oz SE - 22. Vol. 3389 of LNCS, P. Roy, Ed. Springer Berlin Heidelberg, pp. 263-276. 2005. ISSN: 0302-9743. DOI: 10.1007/978-3-540-31845-3_22.

[19] J.A. Aranda, J.F. Díaz y J.J. Ortiz. "CREAR: Consejero para la Repartición de Artículos y Evaluadores en Eventos Académicos". Ingeniería y Competitividad. Vol. 6 N° 1, pp. 53-62. 2004. ISSN: 0123-3033.

[20] J.A. Aranda, J.F. Díaz and J.J. Ortíz. "The Problem of Assigning Evaluators to the Articles Submitted in an Academic Event: A Practical Solution Incorporating Constraint Programming and Heuristics". Multiparadigm Programming in Mozart/Oz SE-25. Vol. 3389 of LNCS, P. Roy, Ed. Springer Berlin Heidelberg. pp. 305-316. 2005. ISSN: 0302-9743. DOI: 10.1007/978-3-540-31845-3_25.

[21] J.F. Díaz, I.J. Romero and C. Lozano. "Solving the Short Run Economic Dispatch Problem Using Concurrent Constraint Programming". Toward Category-Level Object Recognition. Vol. 4170 of LNCS, pp. 265-274. 2006. ISSN: 1571-5736. DOI: 10.1007/978-0-387-34749-3_28.

[22] E. Arias y A. Villegas. "OztNet: Mejoramiento del servicio de una red de comunicaciones móviles usando programación por restricciones en Mozart". Tesis para optar al título de Ingeniero de Sistemas. Universidad del Valle. Colombia. 2006.

[23] C. Ramírez. "Prototipo basado en agentes inteligentes y restricciones para simular el comportamiento del mercado de electricidad colombiano". Tesis para optar al título de Ingeniero de Sistemas y Computación. Universidad del Valle. Colombia. 2009.

[24] A.L. Cañizález. "Prototipo de entrenamiento para subastas en el mercado eléctrico-PRESUME". Tesis de pregrado. Universidad del Valle. 2010.

[25] International Communications Union (ITU). "Radiocommunication Bureau, National Spectrum Management Handbook". Chapter 3. 2005. Date of visit: January 3, 2015. URL: http://www.itu.int/dms_pub/itu-r/opb/hdb/R-HDB-21-2005-R1-PDF-E.pdf


Recibido 4 de octubre de 2013, aceptado 3 de marzo de 2015



Otros Artículos

# Título Ver
1
Desarrollando sistemas de información centrados en la calidad de datos (2013)
Angélica Caro, Alejandra Fuentes, M. Antonieta Soto
HTML | PDF
2
Control heurístico difuso de un agitador electrodinámico en pruebas aceleradas de HALT / HASS (2019)
Juliane Donadel, Herbert Martins Gomes
HTML | PDF
3
Grado y dirección de la diversificación de las empresas industriales españolas: un análisis de la estrategia de la estrategia de diversificación relacionada (2006)
Patricia Huerta Riveros, José Emilio Navas López
HTML | PDF

Desarrollado por: Cristian Díaz Fonseca - cfonseca@matiasluke.cl