Revisión de Articulos.

INCREASE IN CAPACITY OF MULTIUSER OFDM SYSTEM USING DYNAMIC SUBCHANNEL ALLOCATION

Wonjong Rhee and John M. Cioffi

Este articulo resuelve de manera optima el problema de asignación de recursos en OFDMA con un enfoque max-min, utilizando programas de optimización comerciales. Sin embargo dada la complexidad de dicha solución propone un algoritmos heurístico que asigna ordenadamente el mejor canal disponible para cada usuario, y mientras aún queden canales disponibles, asigna el mejor canal disponible extra al usuario que menor capacidad tenga hasta el momento.

Puntos claves del articulo:

• Water filling con modulación adaptativa es la solución optima para la asignación de potencia en OFDM.
• Water filling solo puede ser utilizado en sistemas de un solo usuario o bien con multi-usiario con asignación fija de recursos.
• TDMA Y FDMA asignar recursos de manera fija sin tomar en cuenta la respuesta del canal.
• Dada una asignación de canales para cada usuario puede aplicarse water-filling para optimizar la trasmisión sobre de ellos. Sin embargo las tasas de trasmisiones quedan muy por debajo de las obtenidas con asignación adaptativa de recursos.
• En TDMA cuando el valor de potencia considerado en la perdida de trayectoria es alto (4 para el caso de este estudio) usuarios con distantes a las estaciones base tienen una tasa de trasmisión muy baja. Y el sistema se vuelve injusto con esos usuarios.
• Es bien conocido que la solución de water filing de un único usuario tiene una capacidad cercana a aquella obtenida de una asignación de potencias planas utilizando unicamente los canales con buenas condiciones de trasmisión.

Proponen finalmente dos modelos matemáticos para la resolución del problema de asignación dinámica óptima, que buscan maximizar la capacidad de trasmisiónlibre de errores (formula de Shannon) del usuario con menor capacidad, incluyendo la restricción de que cada canal puede asignarse unicamente a un usuario, y que la suma de la potencia utilizada en todos los canales tiene que ser menor o igual a la potencia máxima permitida. EL segundo modelo ademas toma en consideración una transferencia de datos requerida por cada usuario. Sin embargo la resolución óptima requiere de un intenso trabajo computacional debido a la naturaleza recursiva de la resolución de problemas de optimización convexos.

Por este motivo proponen una solución heurística que obtiene resultados cercanos al optimo utilizando potencias idénticas en todos los canales. El algoritmo que utilizan es el siguiente:

• Para cada usuario (i):
  • Busca el canal con mejor condición disponible. (CSI)
  • Asigna el canal al usuario (i).
• Mientras CanalesDisponibles > 0:
  • Busca el usuario con menor capacidad actual
    • Busca el canal con mejor condición disponible. (CSI)
    • Asigna el canal al usuario

Power Allocation / Adaptive Modulation

---

En los sistemas de trasmisión OFDM cada canal puede ser finamente ajustado en la potencia con la cual se trasmitirá. Esto permite hacer uso de las condiciones de canal instantáneas (CSI) para asignar la potencia de forma optima entre los canales de forma que se maximice la velocidad de trasmisión con un presupuesto de potencia total definido (rate adaptative) o bien minimizar la potencia necesaria para alcanzar una cierta velocidad requerida por el usuario (margin adaptive).
Usualmente la formula de la Capacidad de Shannon es utilizada para estimar la tasa de trasferencia que cada canal puede alcanzar como un máximo teórico. Sin embargo, esta formula considera que incrementos infinitodecimales de potencia producen cambios infinitodecimales en la capacidad del canal, cuando en conexiones inalámbricas esto no representa la realidad, ya que cada canal puede trasmitir tantos bits por símbolo como la modulación que se utiliza lo permita.
Cuando la potencia es ajustada con el objetivo de maximizar la capacidad teórica de la trasmisión el problema es conocido como Asignación de Potencia, es un problema con variables que pertenecen a los reales. En cambio si se considera que cada canal puede ser modulado unicamente en un conjunto de tipos de modulación, los cuales cada uno tienen un numero de bits por símbolo (usualmente 1,2,4,8), entonces el problema se vuelve un problema combinatorio, donde las soluciones están compuestas por un vector de variables discretas, este problema es conocido como Modulación Adaptativa.
Cuando se asigna una potencia entonces la modulación se escoge mediante la Relación-Señal-Ruido (SNR) resultante de la asignación y el Radio de Error por Bit BER que busca alcanzar. En cambio en el esquema de modulación adaptativa designa una de las modulaciones disponibles, por lo que un SNR es requerido para cumplir las condiciones de BER, con ello puede calcularse la potencia necesaria para utilizar dicha modulación. Ambas estrategias pueden utilizarse ya sea para maximizar la velocidad de trasmisión o minimizar la potencia.

Problema de Asignación de Potencia.

$$\begin{equation*} \begin{aligned} & \underset{P}{\text{maximize}} & & B \sum_{\forall n} \log_2 \bigg( 1 + \frac{p_n (h_n)^2}{\sigma^2} \bigg) \\ & \text{subject to} & & \sum_{\forall n} p_n \leq p_{max} \end{aligned} \end{equation*}$$
En este problema debe asignarse la potencia a cada canal como un valor numerico real, entre un rango de 0 a $p_{max}$. Y tiene como restricción que la suma de todas las potencias debe ser menor o igual a la potencia máxima. Este problema tiene una solución optima utilizando multiplicadores de Lagrange, conocido como watter-filling, sin embargo resulta en potencias negativas por lo que un pos-procesamiento es requerido para encontrar una solución viable.

Problema de Modulación Adaptativa.

$$\begin{equation*} \begin{aligned} & \underset{P}{\text{maximize}} & & \sum_{\forall n} f \bigg( \frac{p_n (h_n)^2}{\sigma^2}, P_{err]} \bigg) \\ & \text{subject to} & & \sum_{\forall n} p_n \leq p_{max} \end{aligned} \end{equation*}$$
En MA a cada canal le es indicado la modulación sobre la cual trasmitiran, y dada esta modulacion la potencia necesaria es calculada, con base a la probabilidad de error requerida y el CSI. Segun la modulación es el numero de bits que son trasmitidos por simbolo, y por tanto la velocidad de trasmision, la funcion $f$ en este caso devuelve el numero de bits que pueden ser trasmitidos dado el SNR y $P{err}$. La restricción en este caso es igual al de MA. Escoger una modulacion alta, requiere una potencia alta, dependiendo del CSI, lo cual reduce la potencia disponible para los demas canales.

Introducción OFDMA

---

OFDMA es un método eficiente de acceso múltiple que ha ganado popularidad para ser adoptado en las redes inalámbricas de las futuras generaciones por su alta eficiencia espectral. Es capaz de obtener un gran beneficio al utilizar la información de la diversidad de multi-usuario si la asignación dinámica de los recursos es bien aprovechada. Por esta razón mucho esfuerzo científico ha sido invertido en desarrollar algoritmos novedosos de asignación de canal, bit, y potencia que obtengan configuraciones optimas o cercanas al optimo, de forma que OFDMA sea una técnica de modulación prometedora para los próximos estándares de comunicación.

-Ahmadi, H. & Chew, Y.H., 2009. Adaptive subcarrier-and-bit allocation in multiclass multiuser OFDM systems using genetic algorithm.

La solución al problema de asignación de recursos en OFDMA ha sido comúnmente separado en dos categorías conocidas en ingles como: Margin Adaptive (MA) y Rate Adaptive (RA).

-A Low Complexity Algorithm for Proportional Resource Allocation in OFDMA Systems.

Donde el objetivo de MA es minimizar la potencia utilizada para la comunicación en todos los canales, con la restricción de que cada usuario alcance una tasa de transferencia requerida. En cambio, RA busca que la tasa de trasferencia del sistema sea maximizada teniendo en cuenta un limite en la potencia total permitida. Ambas estrategias juegan con la asignación de los canales disponibles en el sistema para ser asignados a los usuarios (Channel Allocation), y la potencia (o modulación) con la que se trasmitirá en cada canal.

Cuando la potencia es ajustada con el objetivo de maximizar la capacidad teórica de la trasmisión el problema es conocido como Asignación de Potencia (Power Allocation), es un problema con variables que pertenecen a los reales. En cambio si se considera que cada canal puede ser modulado unicamente en un conjunto de tipos de modulación, los cuales cada uno tienen un numero de bits por símbolo (usualmente 1,2,4,8), entonces el problema se vuelve un problema combinatorio, donde las soluciones están compuestas por un vector de variables discretas, este problema es conocido como Modulación Adaptativa (Adaptive Modulation). Power/Modulation

En MA todos los usuarios en el sistema obtienen al menos la tasa de transferencia que requieren, ya que esta es una restricción del problema. En cambio en RA se tiene un potencia disponible, conocida como el presupuesto de potencia (Power Budget), y el sistema asigna canales con su potencia/modulación para los usuarios, de forma que la suma de las trasferencias de todos los canales sea máxima.

La solución optima utilizando Asignación de Potencia en RA es bien conocida, basta con utilizar potencias equitativas (Equal Power Allocation) y asignar cada canal unicamente al usuario que obtenga la mayor tasa de transferencia al hacer uso del mismo, esto puede calcularse conociendo la información del estado del canal (Channel State Information), la potencia utilizada en el canal, el ancho de banda y el nivel de ruido (comúnmente igual para todos los canales).

-Jang, J., Member, S. & Lee, K.B., 2003. Transmit Power Adaptation for Multiuser OFDM Systems.

El trabajo de Jang demuestra que asignar cada canal a un único usuario, el que mejor lo aprovecha es la configuración optima, ademas que la asignación de potencias fijas idénticas no tiene un rendimiento significantemente menor en comparación con la asignación de potencia utilizando el bien conocido algoritmo watter fillign. Otro aspecto importante es que con forme el numero de usuarios aumenta, entonces la diversidad de multi-usuarios también, por lo que la tasa de trasferencia del sistema aumenta también. Aunque esto podría considerarse un punto positivo conlleva un problema conocido como hambruna de recursos, ya que puede ser que a algunos usuarios no les sea asignado ningún recurso, ya que el RA no tiene ninguna restricción al respecto.

Es por ello que esta solución optima no es utilizada, ya que obtener altas tasas de trasferencia de datos a costa de dejar sin servicio a los usuarios no es benéfico para los operadores. referencia Una solución a la hambruna es considerar la equidad en la distribución de los recursos. Sin embargo considerar la equidad no es simple ya que asignar el mismo numero de recursos para cada usuarios no resulta en velocidades de trasmisiones iguales debido a la naturaleza del desvanecimiento a la que se encuentren expuestos. Este tema es abordado en la sección de Equidad en OFDMA.

Finalmente el problema se considera como un problema de optimización con alta complejidad, perteneciente al grupo de problemas NP-Hard. Debido a esto se considera el problema como intratable, por lo que no existe una solución determinista y enumerar todas las soluciones para encontrar el óptimo es virtualmente imposible en un tiempo coherente. Formas eficientes de asignar los recursos han sido ampliamente investigadas y desarrolladas en los ultmos años, en general todas las propuestas para generar asignaciones dinámicas en OFDMA se van en uno de los 3 diferentes métodos:

• Relajando la restricción de asignación de bit enteros, o la asignación única del canal a un usuario. Pos–procesamiento es requerido después de obtener los resultados para llegar a una solución aplicable.
• El problema se divide en dos etapas, primero a cada terminal se le asigna un numero de sub–portadoras (sub–carrier allocation), luego las sub–portadoras especificas son asignadas a los usuarios, formando los pares sub–portadora usuario.
• Es resolver los problemas de rate adaptive o margin adaptive con heurísticas mayormente basados en algoritmos de ordenamiento.

-Dynamic Mechanisms in OFDM Wireless Systems: A Survey on Mathematical and System Engineering Contributions 2006

En la sección del Estado del Arte se analízan diversos estudios relacionados en el tema, y se mencionan sus principales contribuciones.

Hace un tiempo atrás comencé a retomar el interés en el desarrollo web, después de algunos años dedicados a la investigación científica. Con forme pasaba el tiempo reconocía nuevas tecnologías que entendía poco, pero parecían ser muy populares en Internet.

En mis primeros tiempo de desarrollador web autodidacta habían tres principales cosas que debías conocer: HTML, CSS, JavaScriopt,. Si tu estas leyendo esta entrada, supongo que debes tener una clara idea de que son estos 3. Con los años surge HTML5 y CSS3 que fue un gran paso en la madures de estas tecnologías ampliando las posibilidades dinámicas de la web, y ofreciendo una manera estable y bien establecida dar formato a las paginas y que el código resultase mucho mas sencillo de leer, aun para novatos. Junto con estas tecnologías nace el auge de redes sociales como Facebook y Twitter, que traen consigo librerías JavaScript potentes para la actualización dinámica de las paginas, es decir poder obtener o enviar información al servidor sin tener que refrescar toda la pagina, así como la modificación de los elementos DOM de la pagina de manera muy sencilla y practica. Para ese entonces jQuery fue la solución JavaScript en la que inverti mi tiempo para aprender y divertirme jugando con sus nuevas posibilidades.

Otras tecnologías paralelas a estas, ocurren en el lado del servidor, como PHP que era la opción a tomar si querías utilizar bases de datos. Después se abrieron camino otros lenguajes que permitían generar el contenido que seria enviado al cliente web, dependiendo de la petición realizada por el mismo, dentro de las cuales únicamente llegue a probar Python, ya que conocía el lenguaje.

Sin embargo actualmente existe un gran incremento en las posibilidades y nuevas abstracciones que han sido desarrolladas, que permiten realizar aplicaciones web de manera mucho mas sencilla, utilizando piezas de software como componentes agregados sobre las tecnologias bien conocidas HTML, CSS y JavaScript. Por nombrar algunos se tiene Node.js, Angular.js, Sass, Botstrap, entre otras.

Inicialmente encontrar sentido a todas estas tecnologias nuevas no fue tan claro para mi, sobretodo ya que muchos de estos se utilizan en conjunto, y una te lleva a la otra y pareciera que tienes que usar todo. Primeramente todas las mencionadas sirven para un propósito distinto y pueden ser utilizadas independientemente. Sin embargo la mayoría de estas aplicaciones, y muchas mas, se vinculan de cierto modo con Node.js no porque sea necesario, sino porque ofrece un servicio en terminal ("una consola de tu computadora") llamado npm para descargar y mantener actualizado cada uno de estos componentes, ademas de muchas mas cosas, cargándolos de forma modular, lo que simplifica mucho el arreglo de los archivos.

Node.js es un framework que permite ejecutar el lenguaje JavaScript en un ordenador, mediante el motor v8 que es opensource. Ademas de dotarlo con acceso al API del sistema, independientemente del sistema operativo en el que se ejecute, y de funciones que simplifican la creación de servidores web personalizados, para ofrecer contenido dinámico desde el servidor hasta el cliente utilizando únicamente JavaScript. La popularidad de Node.js viene en conjunto con la multitud de módulos disponibles para ser descargados y ejecutados de manera simple, así como la apertura del lenguaje que antes solo podía ser usado en lado del cliente web. Este lenguaje es sencillo y potente, y permite una amplia personalización.

Botstrap es un framework dedicado a la estructura y diseño de paginas web responsivas. Es decir que se adaptan de manera adecuada a diferentes tamaños de pantalla y por tanto a los diferentes dispositivos. Esto resulta muy útil, ya que realizar este proceso por propia cuenta es engorroso y lleno de trucos en CSS para que las cosas se desplieguen como uno esperaría. Funciona de manera sencilla simplemente agregando clases a las etiquetas, según el comportamiento que se espera de cada uno, y ademas ofrece múltiples estilos predefinidos, y un conjunto de aplicaciones mas complejas como Carusell para imagenes, entre otros.

Sass por su cuenta es un lenguaje CSS que permite el uso de variables y ciclos, para mantener grandes tramos codigo de manera sencilla y escalable. El archivo sass debe ser compilado para ser convertido en un archivo css que interprete el navegador de manera usual.

Buscando aprender un poco mas sobre estas nuevas tecnologías me propuse realizar un proyecto que estare compartiendo en este blog, una serie de entradas denominadas Pomodoro Task, es una ayuda para la concentración en las tareas, así como para llevar un registro el tiempo invertido en ellas. Pomodoro es una tecnica de consentración que propone trabajar por 25 minutos de manera intensa y tomar descansos de 5 min. Despues de 3 iteraciones se puede tomar un descanso mas amplio de 15 a 25 min. Para mas informacion ver Pomodoro en Wikipedia.