Repositorio Institucional de Documentos

PROYECTO FIN DE CARRERA ESTUDIO DE ESTRATEGIAS DISTRIBUIDAS DE REPARTO DE RECURSOS EN REDES INALÁMBRICAS COGNITIVAS MEDIANTE TEORÍA DE JUEGOS Departamento de Ingeniería Electrónica y Comunicaciones Escuela de Ingeniería y Arquitectura PROYECTO FIN DE CARRERA ESTUDIO DE ESTRATEGIAS DISTRIBUIDAS DE REPARTO DE RECURSOS EN REDES INALÁMBRICAS COGNITIVAS MEDIANTE TEORÍA DE JUEGOS Ingeniería de Telecomunicación Departamento de Ingeniería Electrónica y Comunicaciones Ingeniería Telemática Escuela de Ingeniería y Arquitectura Universidad de Zaragoza Curso 2010-2011 Zaragoza, Julio 2011 Autor: Rafael Ciria Camino Directora: María Canales Compés ESTUDIO DE ESTRATEGIAS DISTRIBUIDAS DE REPARTO DE RECURSOS EN REDES INALÁMBRICAS COGNITIVAS MEDIANTE Departamento de Ingeniería Electrónica y Comunicaciones Autor: Rafael Ciria Camino Directora: María Canales Compés Resumen 3 ESTUDIO DE ESTRATEGIAS DISTRIBUIDAS DE REPARTO DE RECURSOS EN REDES INALÁMBRICAS COGNITIVAS MEDIANTE TEORÍA DE JUEGOS. RESUMEN Este proyecto se enmarca dentro del estudio de técnicas eficientes de reconfiguración y adaptación al entorno en un contexto de redes inalámbricas multisalto distribuidas. El proyecto propone técnicas distribuidas de reparto de recursos evaluadas mediante teoría de juegos. La teoría de juegos es una herramienta matemática que analiza las interacciones estratégicas entre múltiples agentes que toman decisiones. Por ello, resulta adecuada para analizar las prestaciones de este tipo de redes, donde cada nodo debe decidir sus parámetros de configuración de manera competitiva. Sin embargo, la complejidad matemática de los problemas a resolver resulta difícil de abordar computacionalmente. Por ello, una aproximación alternativa es el desarrollo de simuladores que modelan las interacciones entre los individuos, partiendo de diversas condiciones iniciales, que permiten evaluar las soluciones propuestas al problema planteado. En este proyecto se ha modificado un simulador ya existente sobre el que se han implementado las distintas estrategias distribuidas de reparto de recursos. Cada alternativa propuesta pretendía mejorar a las anteriores introduciendo un mayor grado de realismo en las simulaciones. Como conclusión, se ha comprobado la capacidad de la teoría de juegos para modelar mecanismos de gestión de recursos radio en redes cognitivas y se han diseñado propuestas distribuidas locales (necesitan poca información de señalización) con buenas prestaciones, comparadas con una solución que garantiza la convergencia y la proximidad al máximo (juego potencial). Por último, se ha demostrado que la incorporación de aprendizaje “no-regret” permite hacer frente a situaciones de no convergencia demostrando la potencialidad de las soluciones propuestas para adaptarse a escenarios variantes. Todo esto permite establecer el punto de partida para desarrollar en el futuro algoritmos distribuidos de gestión de recursos radio y su implementación en protocolos en redes mesh cognitivas. Índice 5 ÍNDICE 1. INTRODUCCIÓN .................................................................................................. 11 1.1 Objetivo y alcance del proyecto .............................................................. 11 1.2 Trabajo previo y contexto ........................................................................ 11 1.3 Metodología de trabajo ........................................................................... 14 1.4 Contenido de la memoria ........................................................................ 14 2 TEORÍA DE JUEGOS .............................................................................................. 17 2.1 Elementos básicos de un juego ............................................................... 18 2.2 Modelos básicos de juego ....................................................................... 19 2.2.1 Juegos “Normal Form”........................................................... 19 2.2.2 Juegos repetidos .................................................................... 19 2.2.3 Juegos repetidos con miopía ................................................. 19 2.3 Juegos no cooperativos y Equilibrio de Nash .......................................... 20 2.4 Juegos potenciales ................................................................................... 21 2.5 Juegos repetidos, convergencia al equilibrio .......................................... 22 2.5.1 Temporización de decisiones ................................................ 22 2.5.2 Reglas de decisión ................................................................. 23 3 MECANISMOS DE GESTIÓN DE RECURSOS RADIO MEDIANTE JUEGOS .............. 25 3.1 Modelo del sistema ................................................................................. 26 3.2 Modelo de interferencia .......................................................................... 26 3.3 Utilidad de red ......................................................................................... 28 3.4 Modelo de juego ...................................................................................... 28 3.5 Propuestas de gestión de recursos. Modelos de juego ........................... 29 3.5.1 Modelo de partida: Juego potencial ...................................... 29 3.5.2 Alternativas propuestas para reducir la información necesaria ................................................................................ 31 3.5.3 Modelado más realista .......................................................... 33 4 APRENDIZAJE EN JUEGOS .................................................................................... 37 4.1 Definición de Coarse Correlated Equilibrium ........................................... 38 4.2 Incorporación de aprendizaje no-regret sobre los juegos propuestos ... 39 4.3 Ajuste de la potencia de transmisión ...................................................... 41 5 ANÁLISIS DE RESULTADOS ................................................................................... 45 5.1 Descripción del escenario de simulación ................................................. 45 5.2 Métricas de evaluación ............................................................................ 47 5.3 Evaluación de las prestaciones de las distintas propuestas .................... 47 5.3.1 Juego potencial de referencia (CC). Valoración de la propuesta de juego potencial ................................................ 48 Índice 6 5.3.2 Aproximación al juego potencial sin información global: estrategia basada en conjunto de enlaces vecinos ............... 51 5.3.3 Modelado más realista: incorporación de la restricción de SINR en la toma de decisiones .......................................... 54 5.3.4 Modelado realista de capacidad (capacidad discreta) .......... 55 5.3.5 Modelado realista de capacidad (número de enlaces establecidos) .......................................................................... 57 5.3.6 Juego local con aprendizaje ................................................... 59 6 CONCLUSIONES Y LÍNEAS FUTURAS .................................................................... 65 BIBLIOGRAFÍA ...................................................................................................... 67 ANEXO A: El simulador ........................................................................................ 69 1. Simulador principal: juego ....................................................................... 69 2. Simulador auxiliar: algoritmo genético ................................................... 84 Lista de Acrónimos 7 LISTA DE ACRÓNIMOS DIEC Departamento de Ingeniería Electrónica y Comunicaciones GTC Grupo de Tecnologías de las Comunicaciones I3A Instituto de Investigación de Ingeniería en Aragón UWB Ultra Wide Band CN Cognitive Network CR Cognitive Radio WLAN Wireless local area Network EPG Exact Potential Game OPG Ordinal Potential Game RR Round Robin AS Asíncrono SNR Signal to Noise Ratio SINR Signal to Interference and Noise Ratio UR Utilidad de Red NE Equilibrio de Nash BER Bit Error Rate VoIP Voz sobre IP MAL Multi-Agent Learning CCE Coarse Correlated Equilibrium CC Capacidad Continua EV Enlaces Vecinos CD Capacidad Discreta EA Enlaces Activos CP Corrección de Potencia AP Aprendizaje SCP Sin Corrección de Potencia GA Genetic Algorithm Índice de figuras 8 ÍNDICE DE FIGURAS • Figura 1: Aprovechamiento de los huecos espectrales en una red inalámbrica cognitiva. .................................................................................................................. 13 • Figura 2: Modelo de red mesh cognitiva. Enlaces establecidos entre pares. .......... 26 • Figura 3: Comparativa de la capacidad continua agregada con las estrategias de juego potencial y local. ........................................................................................ 48 • Figura 4: Pasos necesarios para alcanzar el NE (valores medios). Estrategias de juego potencial y local, con capacidad continua (Shannon). .............................. 49 • Figura 5: Capacidad dependiente del número de saltos en la estrategia basada en el conjunto de enlaces vecinos comparada con el caso del juego potencial. Escenario de 300 enlaces. ....................................................................... 51 • Figura 6: Capacidad agregada para la estrategia basada en el conjunto de enlaces vecinos dependientes del número de saltos. Escenario de superficie doble (3,4 Km). ......................................................................................................... 52 • Figura 7: Capacidad agregada de la red considerando los enlaces que superan la SINR umbral. Comparativa teniendo en cuenta la SINR en el proceso de decisión. ................................................................................................................... 54 • Figura 8: Comparativa de la capacidad discreta agregada de la red. ...................... 56 • Figura 9: Comparativa de los enlaces establecidos. Estrategias de juego (potencial y local) basadas en capacidad binaria. .................................................... 57 • Figura 10: Comparativa de la capacidad discreta agregada de la red. Estrategia de juego local basada en capacidad binaria. .......................................... 58 • Figura 11: Comparativa del número de enlaces activos con y sin el algoritmo de aprendizaje. ......................................................................................................... 59 • Figura 12: Comparativa de la capacidad discreta agregada de la red con y sin el algoritmo de aprendizaje. .................................................................................... 60 • Figura 13: Comparativa de los enlaces activos entre el juego local, el algoritmo de aprendizaje con y sin corrección de potencia y el algoritmo genético. ................................................................................................................... 61 • Figura 14: Comparativa de la capacidad discreta total de la red entre el juego local, el algoritmo de aprendizaje con y sin corrección de potencia y el algoritmo genético. .................................................................................................. 61 • Figura 15: Evolución de la utilidad de red en el juego local, basado en capacidad discreta, con aprendizaje (CP), en un escenario de 400 enlaces. ........... 62 • Figura 16: Evolución de los pesos los pesos   para dos enlaces concretos. Juego local, capacidad discreta, aprendizaje CP. Escenario de 300 enlaces. ........... 63 • Figura 17: Diagrama de flujo de la función principal ............................................... 73 • Figura 18: Diagrama de flujo representando la función lk_change_strategy ......... 74 Índice de tablas 9 ÍNDICE DE TABLAS • Tabla 1: Comparativa de utilidades para las estrategias de EA y CD sin y con corrección de potencia. .......................................................................... 43 • Tabla 2: Parámetros en las simulaciones del algoritmo genético................. 47 • Tabla 3: Probabilidades de convergencia en CC. .......................................... 50 • Tabla 4: Reducción de la información y número medio de vecinos dependientes del número de saltos  para 300 enlaces, utilizando la estrategia del conjunto de enlaces vecinos. ................................................. 52 • Tabla 5: Comparativa en tanto por ciento de la utilidad referenciada al caso del juego potencial. ............................................................................... 53 • Tabla 6: Ficheros de entrada y salida del simulador principal ...................... 75 Capítulo 2: Teoría de juegos 17 Capítulo 2: TEORÍA DE JUEGOS Esta sección expone todo lo referente a la teoría de juegos desde el punto de vista de las redes inalámbricas cognitivas. La teoría de juegos es una herramienta matemática que permite modelar y analizar las interacciones entre agentes racionales que toman decisiones, tanto en contextos egoístas como con cierto grado de cooperación. Puesto que los nodos de una red cognitiva compiten por la ocupación oportunista de los recursos y deciden su reconfiguración al respecto, las interacciones entre todos los nodos pueden modelarse mediante esta herramienta [9]. Concretamente, una de las decisiones clave que tienen que realizar los usuarios cognitivos en relación al recurso a ocupar es la elección del par formado por la potencia de transmisión y el canal frecuencial. Esta decisión no es más que un problema de optimización, que podría ser resuelto con la presencia de una entidad central que coordinara dichas decisiones para toda la red. Sin embargo, debido a la naturaleza distribuida de las redes inalámbricas analizadas en este proyecto (redes mesh o ad hoc) se necesita buscar otro tipo de soluciones. Al carecer de una entidad central, la asignación se realiza gracias a las decisiones individuales de los nodos modeladas mediante juegos. Capítulo 2: Teoría de juegos 18 Este proyecto se centra precisamente en resolver la problemática antes comentada. La definición de estrategias de selección de estos parámetros, modeladas mediante teoría de juegos, pretende servir para diseñar mecanismos distribuidos de gestión de recursos. 2.1 Elementos básicos de un juego De manera formal, un juego se define como la terna {!,($  ),(&  )} [9], compuesta por: • Un número finito de jugadores representados por !. • Un conjunto de acciones o estrategias, representado por $  , para cada jugador (. • Una función de utilidad, &  :$→* (donde $ representa el conjunto de acciones, $=× ∈. $  ), que mide el beneficio o utilidad obtenida por el jugador ( determinada por sus acciones así como las acciones del resto de jugadores. Definición 1: Juego Un juego es un modelo de un proceso de decisión interactivo. Definición 2: Teoría de juegos La teoría de juegos es una colección de modelos (juegos) y herramientas analíticas utilizadas para estudiar procesos de decisión interactivos. A continuación, se van a ir introduciendo todos los conceptos relacionados con la teoría de juegos. Capítulo 2: Teoría de juegos 19 2.2 Modelos básicos de juego En esta sección se van a diferenciar las dos definiciones más habituales en juegos como son “Normal Form” y “Repeated Game” (juegos repetidos). En los siguientes dos apartados se presentan algunos detalles sobre ellos. 2.2.1 Juegos “Normal Form” Este tipo de juegos es el modelo más simple y utilizado para describir el proceso de decisión. El juego “Normal Form” asume las siguientes reglas: • Todos los jugadores toman sus decisiones de forma simultánea y sólo toman una decisión. • Los jugadores tienen información perfecta. Conocen sus propias funciones de utilidad como función del conjunto de acciones, $, y también las funciones de utilidad del resto de jugadores en el juego. 2.2.2 Juegos repetidos Un juego repetido es una sucesión juegos, donde cada uno de ellos es un juego “Normal Form”. Debido a la repetición del juego, se asume que el juego es síncrono, es decir, que todos juegan a la vez en cada etapa. Gracias al conocimiento creado en el juego (acciones anteriores, expectativas futuras y observaciones en el momento), los jugadores eligen sus estrategias (una en cada paso). 2.2.3 Juegos repetidos con miopía Esta es una pequeña variación de los juegos repetidos. En lugar de considerar acciones pasadas, expectativas futuras y observaciones en el momento, los jugadores participantes en el juego también pueden comportarse teniendo un cierto grado de “miopía”. En este caso, asumimos que no hay comunicación entre jugadores, tampoco recuerdan eventos pasados ni especulan acerca de eventos futuros. Cada decisión de un jugador con miopía se basa en su observación más reciente del escenario donde se está jugando. Este proyecto se va a centrar en los juegos repetidos, más en concreto en el último caso de juegos repetidos con miopía. Esto es debido a que se ajustan mejor al contexto de las redes cognitivas. Los nodos van observando el entorno y, paso a paso, tratan de adaptarse a lo observado. Capítulo 2: Teoría de juegos 20 2.3 Juegos no cooperativos y equilibrio de Nash Un juego no cooperativo es aquel en el que cada jugador solo se preocupa de su propio beneficio e ignora al resto de jugadores, por lo cual intenta elegir la estrategia óptima para maximizar su función de utilidad. Uno de los resultados más utilizados en el contexto de juegos no cooperativos es el llamado Equilibrio de Nash. El equilibrio de Nash se define formalmente de la siguiente manera: Definición 3: Equilibrio de Nash Un equilibrio de Nash en un juego no cooperativo {!,($  ),(&  )} es un perfil de acciones 0 ∗ Є $ tal que, para cada jugador ( Є ! se cumple: &  (0 ∗ ,0 3 ∗ ) ≥ &  (0  ,0 3 ∗ ) (1) Para todas las 0  Є $  donde 0  denota la estrategia del jugador ( y 0 3 indica las estrategias del resto de jugadores. En otras palabras, se puede decir que el juego ha llegado a un equilibrio de Nash cuando ningún jugador puede mejorar su propia utilidad cambiando su estrategia si el resto de jugadores mantienen las suyas. Por lo tanto, el equilibrio de Nash define la estrategia con mejor respuesta (Best Response) de cada jugador. El concepto de Best Response (regla de decisión) se define en el apartado 2.5.2: 0 ∗ ∈ 5  (0 3 ∗ ) ∀ ( ∈! (2) 5  se define como la función de mejor respuesta para cada jugador: 5  (0 3 )={0  ∈$  : &  (0 3 ,0  ) ≥ &  (0 3 ,0 ´ )} ∀ 0 ´ ∈ $  (3) Como hemos visto hasta ahora, el equilibrio de Nash es el resultado esperado del juego; pero el problema que ahora nos surge es verificar que dicho equilibrio exista. Además, el equilibrio de Nash no tiene por qué ser único, es más, sólo para ciertos casos especiales se cumple esta propiedad. De hecho, incluso probada su existencia, sigue abierto el problema de cómo alcanzar esta situación de equilibrio. Una forma de intentar llegar a este resultado es permitir a los jugadores ajustar sus estrategias de una forma iterativa basada en las observaciones a lo largo del juego. Capítulo 2: Teoría de juegos 21 Como se ha comentado anteriormente, hay ciertos tipos particulares de juego en los que, por sus características, se puede afirmar que existe el equilibrio de Nash y que se puede converger a él de forma iterativa. Uno de esos casos es el juego potencial, cuyas características se definen a continuación. 2.4 Juegos Potenciales Debido a sus propiedades (existencia de equilibrio, convergencia) y a su adaptación al contexto de redes cognitivas, los juegos potenciales son ampliamente utilizados en el modelado de redes cognitivas [9]. A continuación, se presenta una definición formal del juego potencial. Definición 4: Juego Potencial Un juego {!,($(),(&  )} es un juego potencial si existe una función 7:$→* que cumpla una de las siguientes propiedades: • 7(0  ,0 3 )−7(0 ´ ,0 3 )= &  (0  ,0 3 ) − &  (0 ´ ,0 3 ) (4) • 9:;(7(0  ,0 3 )−7(0 ´ ,0 3 ))= 9:;(&  (0  ,0 3 ) − &  (0 ´ ,0 3 )) (5) Para cada ( ∈!,0 ∈$ < 0 ´ ∈$  , donde 9:; es la función de signo. Si el juego potencial cumple la primera definición se le llama juego potencial exacto (EPG – Exact Potential Game). Si cumple la segunda se le denomina juego potencial ordinal (OPG – Ordinal Potential Game). De este modo, de acuerdo a la definición, un juego potencial es un tipo de juego caracterizado por la función potencial 7 y la relación entre ésta y las funciones de utilidad &  . En el caso concreto de los EPG, que serán los juegos potenciales que van a considerarse en este proyecto, se cumple que las desviaciones unilaterales en la función de utilidad (cambio de &  de un único jugador, al modificar únicamente éste su estrategia) se traducen en una desviación equivalente en la función potencial (7 cambia en la misma medida). Otra propiedad importante es que los equilibrios de Nash son máximos de la función potencial 7. Un juego potencial en el que sus jugadores toman las decisiones mediante una política Best Response de forma secuencial (elección de la mejor estrategia posible Capítulo 2: Teoría de juegos 22 frente al perfil observado de sus oponentes) acabará alcanzando el equilibrio de Nash en un número finito de pasos. Además, maximizará la función potencial. Teniendo en cuenta esta propiedad, si en una red inalámbrica cognitiva podemos modelar el proceso iterativo de decisión de los recursos a utilizar mediante un juego potencial, podremos asegurar la existencia de soluciones de equilibrio. Si además, esta función potencial se corresponde con la función objetivo a maximizar en la red (la utilidad), conseguiremos que jugando dicho juego, se pueda resolver el problema de la asignación de recursos. 2.5 Juegos Repetidos, convergencia al equilibrio Tal y como se han descrito los juegos repetidos hasta ahora, los nodos presentes en una red van tomando decisiones de forma iterativa. Esta toma de decisiones puede converger o no a una solución concreta que, además, puede ser o no un equilibrio de Nash. Esto dependerá de las reglas que rijan cómo se toman esas decisiones y, por supuesto, del tipo de juego. En esta sección se van a introducir dos conceptos: en qué orden tomar las decisiones (temporización de decisiones) y con qué criterio decidir (reglas de decisión). 2.5.1 Temporización de decisiones Un juego repetido consta de múltiples iteraciones. Uno de los problemas que se presentan es decidir cuándo va a actuar cada jugador. En principio, todas las decisiones que se hacen en cada iteración se realizan simultáneamente. Sin embargo, en redes cognitivas suele ser complicado conseguir dicha sincronización, por lo que se emplean otro tipo de técnicas para decidir en qué orden se toman las decisiones, como es la utilización de juegos repetidos miopes no sincronizados. Lo que nos permite esta técnica es limitar el número de jugadores que pueden actualizar su estrategia en cada paso. Obviamente, hay varias formas de realizarlo. En este proyecto se han utilizado dos de ellas, que se explican a continuación: • Round Robin (RR): En cada ronda actúa un único jugador. Esto implica que ese jugador no volverá a actualizar su estrategia hasta que todos los demás lo hayan hecho, por lo que tendrá que esperar un número de rondas igual al número de jugadores. Capítulo 2: Teoría de juegos 23 • Asíncrono (AS): En cada ronda, cada jugador tiene una probabilidad de actualizar su estrategia igual a 1/!, donde ! es el número total de jugadores. Con esta práctica, puede haber varios jugadores cambiando su estrategia en el mismo paso. 2.5.2 Reglas de decisión En este apartado se van a presentar dos criterios distintos con los que decidir cómo jugar. Son el Best Response y el Better Response: Definición 5: Best Response Una regla de decisión >  :$→$  es una Best Response si cada cambio de estrategia maximiza la utilidad individual manteniendo el resto de jugadores sus estrategias. >  (0)∈{?  ∈ $  :&  (?  ,0 3 )≥&  (0  ,0 3 ) ∀ 0  ∈$  } (6) Definición 6: Better Response Una regla de decisión >  :$→$  es una Better Response si cada cambio de estrategia mejora la utilidad individual manteniendo el resto de jugadores sus estrategias. >  (0)∈5  (0) (@ 5  (0)≠∅ < >  (0)=0  en caso contrario donde 5  (0)={?  ∈ $  :&  (?  ,0 3 )> &  (0  ,0 3 )} (7) Todas estas definiciones pueden ser trasladadas a los EPG. En un EPG donde existe una función potencial 7, tal que 7:$→*, se cumple la siguiente propiedad: ∆&  = &  (0  ,0 3 )− &  E0 ´ ,0 3 F= ∆7=7(0  ,0 3 )− 7E0 ´ ,0 3 F ∀ (∈!,∀ 0  ,0 ´ ∈$  (8) Esta propiedad implica que, si un jugador actúa en cada paso y dicho jugador maximiza (Best Response) o mejora (Better Response) su utilidad, el proceso convergerá a un equilibrio de Nash sin importar el orden de juego ni las condiciones iniciales. Por otra parte, si el juego no es potencial o no garantiza la existencia del equilibrio de Nash, no se puede asegurar que jugando repetidamente (RR o AS) se Capítulo 2: Teoría de juegos 24 llegue a converger a una solución de equilibrio. Existen ciertas propiedades matemáticas de un juego (no siendo potencial) que nos pueden permitir conocer la posible convergencia. No obstante, dicho análisis matemático no es el objetivo del proyecto. Por el contrario, el objetivo principal es la propuesta de estrategias de juego y su evaluación mediante simulación. Dicha evaluación será la que permita concluir la posible convergencia y existencia de situaciones de equilibrio de acuerdo a los modelos de juego planteados. Más concretamente, los juegos potenciales, serán utilizados como un planteamiento inicial, bastante prometedor (dada la existencia y convergencia al equilibrio) pero que, como se demostrará en el apartado correspondiente, puede resultar complejo y costoso computacionalmente. De este modo, tomando dicho modelo de juego como punto inicial, se plantearán alternativas de las que se verificarán sus prestaciones mediante simulación, siguiendo la estrategia de juego repetido miope de acuerdo a las reglas de juego aquí comentadas. Para aquellos casos en los que no pueda verificarse la existencia de equilibrio, utilizaremos un tipo de técnicas (técnicas con aprendizaje) que nos permitirán alcanzar otro tipo de soluciones en estos escenarios. Toda esta información se detallará más en profundidad en secciones posteriores. Una vez introducidos los aspectos clave de la teoría de juegos, a continuación se detalla cómo se ha utilizado esta herramienta matemática para definir los mecanismos distribuidos de gestión de recursos radio, que es el objetivo del proyecto. Capítulo 3: Mecanismos de gestión de recursos radio 25 Capítulo 3: MECANISMOS DE GESTIÓN DE RECURSOS RADIO MEDIANTE JUEGOS En este apartado se van a comentar todas y cada una de las soluciones que han sido propuestas para tratar el problema de la asignación de recursos en las redes cognitivas, consideradas en el estudio. Comienza la sección hablando del contexto en el que comenzó el proyecto, se definirán parámetros, se explicará el modelo del sistema así como la evolución que se ha seguido y el porqué de cada uno de los escenarios propuestos. En esta sección se tratará el grueso del proyecto, que se ha basado en la creación y el estudio de diversas alternativas de gestión de recursos mediante teoría de juegos sin introducir el concepto del aprendizaje, que se introduce en el capítulo siguiente. Capítulo 3: Mecanismos de gestión de recursos radio 32 • Definición del conjunto de enlaces vecinos Como sabemos, el juego potencial, gracias a sus propiedades matemáticas, garantiza la convergencia al equilibrio de Nash; sin embargo, presenta el importante inconveniente de la gran cantidad de información que requiere. El juego local, que podría ser una solución interesante debido a su simplicidad, no garantiza la convergencia, como se mostrará en el apartado de resultados. Como alternativa al juego local, se ha planteado una variación del juego potencial manteniendo la filosofía comentada en la sección 3.5.1 (compensar el efecto negativo sobre los enlaces a los que se interfiere); pero con una menor carga en la información de señalización requerida. Se definirá un conjunto de vecinos de señalización (vecinos a  saltos), menor que el total de nodos en la red, entre los que se limitará el intercambio de información. La idea es similar a la del Protocol Model, ya que se desprecia el impacto sobre los enlaces lejanos. Al limitar el número de enlaces que cada nodo tendrá en cuenta en el cálculo de su &  , se reduce la información necesaria, manteniendo cierta aproximación a su valor real. El conjunto de vecinos de señalización define qué nodos van a intercambiarse la información. El conjunto total de enlaces O G descrito en la expresión (14), quedará reducido a un conjunto O u , como se muestra en la nueva función de utilidad en la expresión (17). Como refleja dicha expresión, a la hora de compensar el efecto sobre el resto de nodos de la red, sólo se consideran nodos afectados aquellos dentro del conjunto O u . No obstante, hay que destacar que los sumatorios que reflejan el valor de la interferencia sufrida por cada enlace recorren el conjunto completo O G , ya que dicha interferencia se considera un valor detectado por cada receptor (y por tanto intercambiando dentro de la información de control). &(9,93)=bf _ ·cd:el1 + N· :, P.+∑Nj· :j, j ∈ V W j X m− − n o o o p [bf _ ·cd:e n o p 1 + NL· :L,L P.+ ∑Nj· :j,L j∈V W jX jXL q r s L∈V v f _ tf h XL −[bf _ ·cd:e n o p 1 + NL· :L,L P.+ ∑Nj· :j,L j∈V W jXL q r s L∈V v f _ tf h XL q r r r s (17) Capítulo 3: Mecanismos de gestión de recursos radio 33 El conjunto de enlaces vecinos, O u , está definido como aquellos enlaces cuyo transmisor está a un número determinado de saltos  del receptor del enlace que estamos tratando. Cuanto mayor sea el número de saltos, mayor será el número de enlaces vecinos y, por tanto, mayor será la información a tratar y la complejidad aumentará; pero también los resultados se aproximarán más al juego potencial. Es por ello, que el considerar un número acertado de saltos es vital para el tratamiento de este problema. En el apartado de resultados lo analizaremos. 3.5.3. Modelado más realista Como hemos venido comentando a lo largo de la memoria, uno de los objetivos del proyecto es ir introduciendo un mayor grado de realismo en el modelado del sistema. Es por ello que, basándonos en las alternativas planteadas hasta ahora, se van a introducir pequeños cambios para acercarnos a esta meta. • Decisión basada en el cumplimiento de la restricción de SINR Se ha comentado que el cumplimiento de la SINR condiciona la satisfacción del usuario en el juego, por lo tanto, parece lógico incluir dicha condición en la evaluación de la utilidad de cada enlace. Hasta ahora, la utilidad &  se calculaba en función de la capacidad máxima teórica de Shannon (11), para todo valor de la SINR. En realidad, cuando la SINR está por debajo de un cierto umbral (tal y como se definió en el apartado 3.1), la capacidad obtenida no tiene ningún significado lógico, ya que el enlace no se puede establecer. Por lo tanto, desde un punto de vista de implementación real, considerar no establecer el enlace será la decisión más acertada, ya que de esta manera se anula la interferencia que podría crear al resto de enlaces de la red. De hecho, una asignación de recursos en la que hay enlaces con una SINR menor que la umbral lo que realmente indica es que, dada la capacidad máxima de la red, no es posible mantener activos todos los enlaces garantizándoles a todos sus prestaciones. De este modo, el objetivo principal de esta alternativa es limitar el número de enlaces que van a transmitir, precisamente para ajustarse al número de enlaces que realmente pueden transmitir correctamente de acuerdo a la capacidad máxima de la red. Para ello, la SINR umbral establece la condición mínima necesaria en términos de la relación de la señal con el ruido y la interferencia para que la transmisión sea aceptada. Los enlaces que no cumplan esta SINR umbral con ninguna de las estrategias de juego no transmitirán, actualizando su potencia de transmisión a cero. Con esta variación, se consigue que un enlace que no tenga unas condiciones mínimas para Capítulo 3: Mecanismos de gestión de recursos radio 34 realizar una transmisión no la haga, evitando que interfiera al resto de enlaces que se sitúan en el mismo canal que él. Esta modificación puede incluirse en cualquiera de los juegos propuestos anteriormente (potencial, con información limitada a vecinos o local) modificando adecuadamente la función de utilidad &  . En todos los casos, la inclusión de la SINR en el proceso de decisión pretende añadir un cierto grado de cooperación: si no se puede conseguir la capacidad individual de un enlace, el hecho de no transmitir puede mejorar la calidad del resto de enlaces. Esta cooperación puede resultar especialmente interesante en el caso del juego local, ya que estamos reduciendo el egoísmo de este juego sin introducir información de señalización adicional. Una manera de introducir esta modificación es definir la función de utilidad como: &  (9  ,9 3 )=w −1 0<QR!*  <Y b f_ ×cd: e (1+QR!*  ) QR!*  ≥ Y y (18) Esta expresión muestra la utilidad de un enlace incluyendo la condición de la SINR umbral, Y en la expresión (18). Si el enlace supera dicha SINR umbral, calculará su utilidad con la fórmula de la capacidad de Shannon, si por el contrario, no alcanza la SINR necesaria, se le penalizará con el valor -1, que implica que es mejor que no transmita a que lo haga con una potencia que no le permite superar la SINR umbral. Este valor de penalización sólo tiene efecto en términos de decisión a la hora de jugar y no como utilidad real. Es decir, un jugador (enlace), que implementa una Better/Best Response como regla de decisión, nunca elegirá una estrategia con una potencia de transmisión que implique no superar la SINR umbral. Obviamente, si no puede utilizar ninguna potencia, a la hora de elegir la estrategia a jugar, deberá optar por no transmitir (N  =0), que es lo mejor en términos globales. Esto, tendrá como consecuencia que su capacidad individual real sea 0 (no -1). • Redefinición de capacidad: niveles de modulación Hasta ahora, calculábamos la utilidad de los enlaces en términos de capacidad, expresada mediante el límite teórico definido por la fórmula de Shannon. Sin embargo, en un sistema real, la tasa de transmisión viene dada por un conjunto discreto de valores, dependientes básicamente de la modulación y la codificación del canal que garantice una tasa de error en el bit (BER – Bit Error Rate) determinada para la SINR con la que se trabaja. Capítulo 3: Mecanismos de gestión de recursos radio 35 Vamos a intentar introducir esta discretización en la capacidad de una manera sencilla, manteniendo la relación con la definición de la capacidad de Shannon utilizada hasta ahora. Para ello, aplicamos la ley de Hartley, que establece la capacidad máxima que se puede conseguir para un número determinado de niveles en una modulación, z  : \  ≤2·b f_ ·cd: e (z  ) (19) A partir de esta expresión y de la capacidad teórica de Shannon descrita en (11), asumiendo que el número de niveles de modulación debe ser una potencia de dos, el máximo valor permitido para z  para una determinada QR!*  , se obtiene como muestra la siguiente expresión: z  =2 |}~(]^.I_)/e (20) El valor mínimo para z  es z j =2. Fijando el valor de z já , quedan definidas el conjunto de capacidades para cada enlace. En nuestro caso, se ha considerado un valor z já =256. Esto implica que tenemos 8 niveles de modulación cuyos valores serán los siguientes: z=2,4,8,16,32,64,128 y 256. De este modo, la utilidad de la red, como capacidad agregada, se calculará mediante la expresión: Z*= [ 2·b f_ ·cd: e (z  ) (21)  ∈ VW ]^.I_`a • Redefinición de capacidad: Enlaces establecidos Continuando con nuestro objetivo de redefinir el concepto de capacidad para que vaya adoptando connotaciones cada vez más realistas, proponemos una nueva forma de calcularla, consistente en contabilizar el número de enlaces que están activos. Capítulo 3: Mecanismos de gestión de recursos radio 36 Esta definición de utilidad de red puede ser útil en aplicaciones con demandas de tasa fija (como puede ser el caso de servicios de voz sobre IP – VoIP). En estas aplicaciones, el único requerimiento es establecer el enlace con una SINR mayor que la umbral. En este caso, la capacidad del enlace ( puede definirse directamente como \  =1, indicando que el enlace está establecido. Por lo tanto, la capacidad total de la red se contabilizará como el número de enlaces activos, de acuerdo a la siguiente expresión: Z*= [ 1 ∈VW ]^.I_`a (22) Una vez introducida esta nueva definición de capacidad, es importante considerar que, a la hora de evaluar las prestaciones de la red, puede ser interesante medir tanto el número de enlaces activos como la capacidad total del sistema, independientemente de la capacidad utilizada en la definición de utilidad de cada enlace. Obviamente, si el objetivo es la maximización de la capacidad, el número de enlaces activos no tiene por qué ser el óptimo, y más todavía si lo comparamos con el caso en el que sí que buscamos maximizar los enlaces activos. Sin embargo, ambos valores son medidas que deberían ser consideradas a la hora de evaluar las prestaciones del sistema (podría considerarse en el futuro ponderar diversos criterios de maximización, o diferenciar las utilidades de los enlaces de acuerdo a las aplicaciones demandadas en cada uno de ellos). Por esta razón, se considerarán ambas para valorar los distintos resultados que se presentarán en el capítulo 5. Como ya se ha ido introduciendo al explicar las distintas propuestas de juego, sólo en el caso de un juego potencial se puede garantizar la convergencia al NE. Para el resto de casos, la evaluación por simulación servirá para verificar o no dicha convergencia. Sin embargo, aquellos juegos para los que no existe un equilibrio puro de Nash, pueden converger a otro tipo de soluciones (equilibrio mixto, equilibrio correlado). Para estos casos, es posible que técnicas como el Better o Best Response no sean suficientes. Es por ello que en este contexto se plantean las técnicas de aprendizaje multi-agente [12], [13]. En el siguiente apartado consideraremos la incorporación de aprendizaje al juego, lo que puede ser de utilidad para mejorar las prestaciones, principalmente en el caso del juego egoísta. Capítulo 4: Aprendizaje en juegos 37 Capítulo 4: APRENDIZAJE EN JUEGOS El aprendizaje multi-agente (Multi-Agent Learning, MAL) [12], [13] estudia la interacción de distintos agentes presentes en un entorno cambiante que, desde las perspectiva de un único agente, incluye el comportamiento de sus oponentes. Los agentes ajustan su comportamiento gracias a algoritmos que aprenden de la experiencia previa (medida a través de cierta recompensa o “reward”). Aunque la perspectiva de MAL proviene de un campo de investigación diferente al que estamos tratando (comunidad científica en inteligencia artificial), puede relacionarse con la teoría de juegos [12]. De hecho, existen un gran número de estudios realizados relacionados con el cálculo del equilibrio desde el punto de vista del aprendizaje. En este contexto, las técnicas de aprendizaje denominadas “no-regret” [14] presentan ciertas propiedades que permiten converger a soluciones que van más allá del equilibrio de Nash (“coarse correlated equilibria”). A continuación se explicará con más detalle. En este apartado se explicarán primero los conceptos básicos de aprendizaje en juegos cuya aplicación se ha considerado en este proyecto. Más tarde, se describirá la propuesta de aplicación para mejorar el comportamiento de los juegos que no garantizan la convergencia al NE (egoístas o locales). Capítulo 4: Aprendizaje en juegos 38 4.1. Definición de Coarse Correlated Equilibrium Hasta ahora sólo se había definido un tipo de equilibrio: el equilibrio de Nash. Este es el equilibrio más usado en teoría de juegos y se define como un perfil de acciones fijo para el cual, todo agente que juega y elige la estrategia de dicho perfil, no tiene ningún incentivo para desviarse de él. En esta sección se plantea un nuevo tipo de equilibrio en el que las estrategias no se definen como acciones concretas, sino que son definidas como distribuciones de probabilidad en el espacio de acciones (estrategias mixtas). En este caso, el juego consistirá en elegir aleatoriamente una acción para jugar. Por lo tanto, una solución de equilibrio se definirá como la distribución de probabilidades con la que cada uno decide jugar y respecto a la que, como en el NE, no hay ningún incentivo para desviarse (no hay otra distribución de probabilidades mejor). Anteriormente se ha definido un juego como la terna {!,(Q  ),(&  )} (apartado 2.1). Para el caso que nos compete ahora, deberemos definir un nuevo juego, llamado juego repetido con estrategias mixtas, definido como {!,(Q  ),(&  ),(  )}, compuesta nuevamente por: • Un número finito de jugadores representados por !. • Un conjunto de acciones, representado por Q  , para cada jugador (. • Una función de utilidad, &  :Q→*. • Un conjunto de estrategias mixtas del jugador ( sobre su conjunto Q  ,   .   ∈  representará la probabilidad de elegir la estrategia 9  ∈ Q  en cada paso del juego repetido. Para aquellos juegos en los que no existe un NE puro, pueden existir otros tipos de equilibrio basados en estrategias mixtas [13], [15]. A continuación, se va a definir uno de los equilibrios más utilizados en estrategias mixtas, como es el Coarse Correlated Equilibrium. Capítulo 4: Aprendizaje en juegos 39 Definición 7: Coarse Correlated Equilibrium (CCE) Un equilibrio Coarse Correlated se define como una distribución de probabilidades   =E9 () F,…,E9 (||) F sobre el conjunto de acciones Q=9 () ,…,9 (||) , con E9 () F siendo la probabilidad de observar el conjunto de acciones 9 () que satisface: ∀(∈! < ∀9  ∈Q  , [ &  ( _∈]_ 9  ,9 3 )  3 (9 3 )≤&  E9 , 9 3 FE9 , 9 3 F (23) Donde  3 (9 3 ) representa la distribución de probabilidad marginal de todos los jugadores excepto del (, y viene dada por:  3 (9 3 )=[E9 , 9 3 F _∈]_ (24) En otras palabras, un CCE implica que, la distribución de probabilidades   de cada jugador, da como resultado una distribución de probabilidades   (Q) sobre los perfiles de soluciones (acciones conjuntas) y que, si se juega de acuerdo a dicho perfil observado (por ejemplo, aprendido), no hay incentivo para desviarse. 4.2. Incorporación de aprendizaje no-regret sobre los juegos propuestos Los algoritmos de no-regret learning son estrategias probabilísticas de aprendizaje en las que los jugadores exploran el espacio de acciones jugando las mismas con una probabilidad distinta de cero. A partir de allí, se incrementa la probabilidad de las estrategias que proporcionan mejores resultados (mayor utilidad). Este tipo de algoritmos converge al conjunto de equilibrios Coarse Correlated [14], que incluso pueden proporcionar mejores resultados que el NE. Por lo tanto, su aplicación sobre los juegos que no convergen al NE puede ser útil. Concretamente, como ya se ha comentado anteriormente, el juego egoísta puede tener problemas para converger al NE (como se demostrará en el apartado correspondiente de Capítulo 4: Aprendizaje en juegos 40 resultados). Es por ello que se plantean nuevas alternativas para, en lugar de alcanzar el NE, llegar a un equilibrio Coarse Correlated basado en un juego de estrategias mixtas. La incorporación del aprendizaje se realizó después de la evaluación inicial de las propuestas planteadas anteriormente. La utilización del aprendizaje se consideró una vez constatada la falta de convergencia para soluciones locales (egoísta) que, sin embargo, podrían resultar más atractivas en escenarios distribuidos con señalización limitada. Por ello, las propuestas que se plantean a continuación, no se aplican sobre el juego potencial (que converge al NE). Las estrategias mixtas se definen asignando un peso o probabilidad a cada acción dentro del conjunto Q  de cada enlace. El algoritmo de aprendizaje calculará y adaptará los pesos de acuerdo a los resultados que cada acción presente en las distintas etapas del juego repetido. El algoritmo empleado para calcular los pesos fue originalmente desarrollado por Freund y Shapire [8], [16]. En concordancia con ello, la ecuación de actualización de los pesos corresponde con la expresión siguiente:   (9  )=(1+) _(_) ∑(1+) _(_) _∈]_ (25) En esta ecuación, definimos los siguientes términos: •   (9  ) representa el peso de la estrategia 9  del enlace ( en el instante +1. • Z  (9  ) representa la utilidad acumulada obtenida por el enlace ( hasta el instante  eligiendo la estrategia 9  : Z  (9  )=[&  (9 , Q 3   t ) (26) La función mostrada en (25) representa el peso de la estrategia 9  del enlace ( en el instante +1. El peso depende directamente de la utilidad acumulada por dicha estrategia hasta el instante .  es un parámetro cuya única condición es que sea mayor que cero. El denominador de la expresión representa el sumatorio Capítulo 4: Aprendizaje en juegos 41 perteneciente a todas las estrategias del enlace, que nos permitirá que el peso pueda ser tratado como una probabilidad, ya que su valor estará comprendido entre 0 y 1. Los pesos de cada estrategia deben ser actualizados en cada iteración del juego, aunque esa estrategia no se haya jugado. Dicha actualización es posible dado que consiste en calcular la utilidad que se obtendría si se realizara esa acción, aunque no sea así. En el juego puro se evaluaba dicho valor para decidir específicamente la acción a jugar (Better o Best Response). Cada enlace es capaz de medir la &  sin necesidad de ejecutar la acción. De acuerdo a la definición de los pesos (25), aquellas acciones que proporcionan más utilidad se ponderan con un peso mayor en la estrategia mixta. Este modo de funcionamiento puede generar algún problema al aplicarlo a los escenarios realistas propuestos (capacidad discreta o utilidad medida por activación del enlace). A continuación, se describe concretamente esta particularidad y se propone una modificación del juego para solucionar el problema. 4.3. Ajuste de la potencia de transmisión La diferencia entre el juego potencial y local radica, principalmente, en la cooperación entre los nodos, que se incluye directamente en la propia definición de la utilidad individual. Esta falta de cooperación en el juego local puede dificultar llegar a una situación de equilibrio estable, como ya se ha venido comentando. Por el contrario, al introducir el concepto del aprendizaje, se añade cierto grado de cooperación que facilita la convergencia: la probabilidad para utilizar una acción viene determinada por la utilidad acumulada observada, dependiente del entorno, es decir, de lo que hacen el resto de agentes. De esta manera, para llegar a una solución próxima al óptimo, lo esperable sería conseguir que los pesos reflejaran la importancia de aquellas acciones que dan mejores resultados globales. Sin embargo, para las funciones de utilidad del juego local basadas en la capacidad discreta y en la activación de enlaces, existen varias estrategias que se valoran con la misma utilidad, independientemente del efecto sobre el resto, por lo que estamos ante una “mala” cooperación, lo que genera pesos equivalentes y la consecuente oscilación entre acciones que, como resultado, podrían llegar a converger a una utilidad media global que no fuera la máxima. Comenzamos describiendo el problema real para el caso en el que la capacidad se describe como el número de enlaces activos. Capítulo 5: Análisis de resultados 48 5.3.1. Juego potencial de referencia (CC). Valoración de la propuesta de juego local En este apartado se considera como punto de partida el juego potencial basado en la capacidad teórica de Shannon. Dicho juego de referencia se compara con la primera de las propuestas planteadas para reducir la carga de señalización asociada, es decir, con el juego local o egoísta, basado únicamente en maximizar individualmente la capacidad de cada enlace. En esta sección se van a comparar las tres estrategias posibles: el juego potencial, representado por las funciones potencial 1 y potencial 2 (explicadas en el apartado 3.5.1) y el juego local. Todas las estrategias simuladas se han analizado considerando las dos variantes de temporización (RR y AS). Las prestaciones obtenidas se comparan con el resultado de referencia obtenido mediante el método heurístico de optimización basado en GA. Figura 3: Comparativa de la capacidad continua agregada con las estrategias de juego potencial y local. La figura 3 representa la capacidad agregada resultante de cada una de las estrategias con los dos métodos de temporización posibles. En esta gráfica podemos observar cómo las estrategias del juego potencial (potencial 1 y potencial 2) presentan 200 400 600 800 1000 0 50 100 150 200 250 300 350 400 potencial 1 RR potencial 1 AS potencial 2 RR potencial 2 AS Local RR Local AS Genético Capacidad de la red Número de Enlaces Capítulo 5: Análisis de resultados 49 mejores resultados que el juego egoísta o local. También observamos que los métodos de temporización no suponen diferencia alguna en el valor del equilibrio en términos de utilidad. Las dos versiones del juego potencial, como ya se describió en el apartado 3.5.1, se corresponden en realidad con la misma función potencial, lo que se constata comprobando la igualdad de los resultados. Hay que destacar que, en el caso del juego local, los resultados muestran los valores medios en aquellos escenarios en los que se ha alcanzado el equilibrio. A diferencia del juego potencial, el juego local no garantiza la existencia y convergencia al equilibrio, lo que se comprueba analizando detenidamente dicha convergencia, como se muestra a continuación. Figura 4: Pasos necesarios para alcanzar el NE (valores medios). Estrategias de juego potencial y local, con capacidad continua (Shannon). La figura 4 representa el número medio de pasos necesarios para alcanzar el equilibrio de Nash. El juego potencial converge siempre al equilibrio, dadas las propiedades características de este tipo de juegos. Dada la secuencialidad del juego repetido (un jugador por paso, estrictamente (temporización RR) o en media (temporización AS)) la convergencia es más lenta cuantos más enlaces se consideran. Sin embargo, el juego egoísta no converge siempre, especialmente cuando el número de enlaces aumenta. Para este juego se han simulado 10.000 iteraciones para los casos de 50, 100 y 200 enlaces, 20.000 para 300 y 50.000 para 400 enlaces. Se puede comprobar en la figura 4, que para 400 enlaces, tan sólo uno ha llegado al equilibrio (en RR) después de esos 50.000 pasos, es por ello que para estudiar la convergencia de 0 2000 4000 6000 8000 10000 12000 14000 0 50 100 150 200 250 300 350 400 potencial 1 RR potencial 1 AS potencial 2 RR potencial 2 AS Local RR Local AS Pasos para NE Número de enlaces Capítulo 5: Análisis de resultados 50 esta estrategia se utilizarán las alternativas con aprendizaje explicadas en secciones anteriores. A continuación, se presenta la tabla 2, en la que se relaciona el número de enlaces totales y la probabilidad de convergencia. Tabla 3: Probabilidades de convergencia en CC. Número de Enlaces Probabilidad de convergencia (RR) Probabilidad de convergencia (AS) 50 99 % 100 % 100 99 % 99 % 200 95 % 89 % 300 34 % 82 % 400 1 % 0 % Otra conclusión que se obtiene de la figura 4 es que el método de temporización del Round Robin converge mucho más rápido que el asíncrono y además, como se ha comprobado en la figura 3, se obtiene prácticamente la misma utilidad. Por este hecho, a partir de ahora mostraremos sólo los resultados pertenecientes al método RR, ya que implica una menor carga computacional, aunque el método AS sea más realista al no requerir sincronización entre los terminales. Así mismo, las alternativas potencial 1 y potencial 2, presentan la misma utilidad, como era esperable, dado que implementan el mismo tipo de función. Por lo tanto, una vez verificada su correcta implementación, dado que el cálculo en el caso de la función potencial 2 tiene un menor coste computacional, a partir de ahora únicamente se considera esta definición para el juego potencial. Tal y como se ha comprobado, los resultados obtenidos para la capacidad agregada del juego potencial se aproximan a valores óptimos (los obtenidos heurísticamente mediante GA), lo que concuerda con la definición del propio juego (el NE maximiza la función potencial, que hemos definido justo como la capacidad agregada del sistema). Como hemos comentado en apartados anteriores, esta estrategia necesita una gran cantidad de información. La estrategia local planteada como alternativa no muestra unas prestaciones comparables (capacidad agregada menor y falta de convergencia). A continuación se valoran las siguientes soluciones propuestas para reducir la información de señalización garantizando unas prestaciones próximas a las obtenidas con el juego potencial. Capítulo 5: Análisis de resultados 51 5.3.2. Aproximación al juego potencial sin información global: estrategia basada en el conjunto de enlaces vecinos Como se ha comentado, vamos a analizar la utilidad que proporciona la estrategia basada en el conjunto de enlaces vecinos a  saltos. Figura 5: Capacidad dependiente del número de saltos en la estrategia basada en el conjunto de enlaces vecinos comparada con el caso del juego potencial (k = infinito). Escenario de 300 enlaces. La figura 5 muestra la utilidad (capacidad agregada) en una red de 300 enlaces para los distintos números de saltos considerados en la definición del conjunto de enlaces vecinos. El concepto de infinito se refiere al juego potencial, en el que se tiene información de todos los enlaces de la red. En esta gráfica se observa que, dependiendo del grado de exactitud que necesitemos, nos puede servir con considerar como enlaces interferentes aquellos que estén a dos saltos. En la tabla 3 se presenta, para el caso de 300 enlaces, el número medio de enlaces vecinos en función del número de saltos, así como el tanto por ciento en el que se reduciría la información a tratar si eligiéramos ese valor de . Capítulo 5: Análisis de resultados 52 Tabla 4: Reducción de la información y número medio de vecinos dependiente del número de saltos  para 300 enlaces, utilizando la estrategia del conjunto de enlaces vecinos. Número de saltos (  ) Número de vecinos Reducción de información 1 12 96 % 2 25 91 % 3 53 82 % 4 104 65 % En la tabla 4 se observa que, dependiendo del grado de exactitud que necesitemos, la reducción de la información de señalización será mayor o menor, pero siempre será un valor considerablemente alto. Para verificar la escalabilidad de esta propuesta se han obtenido resultados en escenarios mayores que doblan la superficie, el número de nodos y el número de enlaces, por lo cual, sus características son las siguientes: • Cuadrícula de 3,4 Km de lado. • 400 nodos distribuidos aleatoriamente. • Varios números de enlaces (100, 200, 400, 600 y 800). Figura 6: Capacidad agregada para Figura 6: Capacidad agregada para Figura 6: Capacidad agregada para Figura 6: Capacidad agregada para la estrategia basada en la estrategia basada en la estrategia basada en la estrategia basada en el conjunto de enlaces vecinos dependiente el conjunto de enlaces vecinos dependiente el conjunto de enlaces vecinos dependiente el conjunto de enlaces vecinos dependiente del número de saltos. del número de saltos.del número de saltos. del número de saltos. Escenario de superficie doble (3,4 Km) Escenario de superficie doble (3,4 Km)Escenario de superficie doble (3,4 Km) Escenario de superficie doble (3,4 Km).... 500 700 900 1100 1300 1500 1700 1900 0 100 200 300 400 500 600 700 800 EV 1 EV 2 EV 3 EV 4 Local Potencial Capacidad agregada Número de enlaces Capítulo 5: Análisis de resultados 53 La figura 6 muestra la capacidad agregada para la estrategia del conjunto de enlaces vecinos dependiente del número de saltos y comparada con el juego potencial y local. Se observa que, al igual que en el escenario menor, el juego local presenta peores prestaciones que el resto. Además, respecto a los juegos que representa la estrategia de EV, a partir del valor =2 se obtienen capacidades semejantes al caso del juego potencial, como ocurría en el caso anterior. A continuación, se presenta una tabla comparativa para los dos escenarios, que muestra el tanto por ciento que supone la utilidad de cada variante de los EV comparada con la capacidad del juego potencial. Tabla 5: Comparativa en tanto por ciento de la utilidad referenciada al caso del juego potencial (para los casos de 400 y 800 enlaces). Estrategia Escenario Pequeño Escenario grande EV 1 96,57 % 96,71 % EV 2 99,30 % 99,23 % EV 3 99,80 % 99,82 % EV 4 99,96 % 99,94 % Local 75,11 % 79,72 % Los resultados, en términos relativos, son prácticamente iguales en ambos escenarios, lo que efectivamente verifica la escalabilidad de resultados. Además, como se había comentado anteriormente en los dos escenarios, para =2 la utilidad se asemeja en más de un 99 % a la del juego potencial, por lo que la conclusión de elegir ese valor para reducir la información de señalización es correcta. Gracias a estas conclusiones, las simulaciones del resto de alternativas podrán realizarse en escenarios pequeños, con el ahorro computacional que ello supone, sabiendo que los resultados obtenidos pueden ser extrapolados a redes de mayor tamaño. Con la introducción del conjunto de enlaces vecinos hemos conseguido reducir la información de señalización que considera cada enlace para estimar su efecto interferente sobre el resto de la red. Como resultado, se obtienen unas prestaciones próximas a las conseguidas al tener en cuenta la red al completo (juego potencial). Capítulo 5: Análisis de resultados 54 5.3.3. Modelado más realista: incorporación de la restricción de SINR en la toma de decisiones Hasta ahora, todos los modelos de juego (potencial y local) se basaban en una definición de capacidad de enlace teórica de acuerdo a la fórmula de Shannon. La capacidad, así calculada, depende del valor de la SINR, sin tener en cuenta si ésta es mayor o no que la SINR umbral. Esto implica que, en realidad, aquellos enlaces con valores de SINR por debajo de la SINR umbral serían inviables, por lo que la capacidad de red real sería menor que la que se está obteniendo. Teniendo esto en cuenta, en el apartado 3.5.3 se proponía incluir en el proceso de decisión la restricción del cumplimiento de la SINR umbral para considerar un enlace establecido y, por lo tanto, con una capacidad mayor que cero. A continuación se muestra el impacto de esta modificación realizada sobre los juegos, tanto potencial como local. Igualmente, se incluyen como referencia las prestaciones obtenidas mediante optimización heurística centralizada basada en GA. Figura 7: Capacidad agregada de la red considerando los enlaces que superan la SINR umbral (SINR th ). Comparativa teniendo en cuenta la SINR en el proceso de decisión. 200 400 600 800 1000 1200 0 50 100 150 200 250 300 350 400 Potencial SINR Local SINR Genético SINR Potencial CC (SINR > SINR th ) Local CC (SINR > SINR th ) Capacidad agregada Número de enlaces Capítulo 5: Análisis de resultados 55 La figura 7 muestra una comparativa entre el juego local, el potencial y el algoritmo genético de la capacidad agregada de la red condicionada a superar la SINR umbral establecida y los resultados de la CC que superan dicha SINR umbral. La CC no tiene exigencias de SINR umbral, por lo tanto, pese a no superar esa SINR umbral transmite contribuyendo a la capacidad global de la red. Calculando la capacidad agregada debida a los enlaces que superan esa SINR, el resultado de la capacidad es menor que en el caso de la SINR umbral. En la figura 7 se observa que las capacidades resultantes para todos los juegos de la SINR son parecidas. El juego local, en contra de lo que sucedía en casos anteriores, alcanza valores de capacidad similares al juego potencial. Además, estos valores se acercan al óptimo, ya que la capacidad obtenida con el algoritmo genético también es similar. El hecho de que el juego local se asemeje en resultados al potencial es debido a que, con la inclusión de la SINR umbral, se introduce cierto grado de cooperación (como en el juego potencial, donde la función de utilidad se definía también pensando en cómo la transmisión de un enlace podía afectar al resto). Por lo tanto, si el juego local proporciona prestaciones semejantes al juego potencial, sin la carga de señalización asociada, se presenta como una solución bastante prometedora (buenas prestaciones, totalmente local). Así, la opción anteriormente estudiada de limitar el conjunto de enlaces vecinos se descarta, ya que tiene más carga, aunque sea menor que la del potencial. Una vez visto el impacto de incluir la SINR umbral en la decisión, constatando además el beneficio sobre el juego egoísta, se mantiene su utilización para el resto de modelos propuestos. 5.3.4. Modelo realista de capacidad (capacidad discreta) Una vez centrados en la comparativa de las estrategias potencial y egoísta, con SINR umbral, en este apartado se analizan las prestaciones de los juegos modificando la definición de capacidad (manteniendo la formulación de utilidad, cambiando sólo cómo se calcula la capacidad) de acuerdo a un contexto más realista. Hasta el momento, todos los resultados que se han presentado se basan en una definición de capacidad teórica (límite de Shannon). Ahora se ha planteado un nuevo escenario más realista, donde la capacidad se ajusta sólo a valores de acuerdo a los niveles posibles de modulación, como se ha descrito en el apartado 3.3.4. Capítulo 5: Análisis de resultados 56 Figura 8: Comparativa de la capacidad discreta agregada de la red. La figura 8 muestra la comparativa entre las distintas estrategias que estamos considerando (potencial y local) para el valor de la capacidad discreta agregada de la red. Al igual que en el caso anterior, los resultados del juego potencial y local son equiparables, estando próximos a los resultados obtenidos con el algoritmo genético considerado como referencia. Así, aparentemente, el juego local permite obtener buenas prestaciones sin carga de señalización. No obstante, como ya se ha comentado previamente, dicho juego no garantiza ni la existencia del equilibrio ni la convergencia. En cualquier caso, la viabilidad de los resultados obtenidos tanto en los casos de convergencia como en los que ésta no se alcanza parece indicar la posibilidad de llegar a soluciones de compromiso que proporcionan unas buenas prestaciones. Por esto, más adelante se analizarán alternativas de juego (dinámica basada en aprendizaje, como se explicó en el apartado 4.2) que permitan conseguir alcanzar otras soluciones de equilibrio. 100 300 500 700 900 1100 0 50 100 150 200 250 300 350 400 Potencial Local Genético Capacidad agregada Número de enlaces Capítulo 5: Análisis de resultados 57 5.3.5. Modelo realista de capacidad (número de enlaces establecidos) Como se ha comentado en el apartado 3.5.3, hay aplicaciones de tasa fija en las que sólo importa que la SINR supere el umbral establecido. En este caso, la capacidad de un enlace puede considerarse binaria: activo (1) o no (0), de acuerdo a si el valor de la SINR supera o no el umbral requerido. Introduciendo esta definición de capacidad, el juego tiene como objetivo establecer el máximo número de enlaces. Del mismo modo, el cálculo heurístico centralizado basado en GA utilizado como referencia se basa en buscar dicho número máximo. Así, la métrica de evaluación, la utilidad global de la red (UR) medida como capacidad agregada, en este caso refleja el número de enlaces activos. No obstante, como medida comparativa, también se considera el cálculo de la capacidad discreta agregada. Figura 9: Comparativa del número de enlaces establecidos. Estrategias de juego (potencial y local) basadas en capacidad binaria. La figura 9 muestra la comparativa de los enlaces establecidos para cada una de las estrategias. Nuevamente los resultados son similares para todas las estrategias, acercándose al valor de referencia calculado mediante el algoritmo genético. 40 60 80 100 120 140 160 180 200 0 50 100 150 200 250 300 350 400 Potencial Local Genético Enlaces establecidos Número de enlaces Capítulo 5: Análisis de resultados 64 La figura 15 muestra la evolución de la utilidad de red (capacidad discreta agregada) en un escenario de 300 enlaces. Se observa que a partir de un cierto número de pasos, la utilidad de la red se estabiliza. La figura 16 muestra la evolución de los pesos en dos enlaces concretos del escenario utilizado de ejemplo (300 enlaces). Como puede observarse en la figura 16(a), algunos enlaces convergen a una situación de estrategia pura (una única estrategia que jugar, ponderada con un peso igual a 1). Otros enlaces, en cambio, como muestra la figura 16(b), convergen a situaciones mixtas, en las que diversas estrategias tienen una probabilidad no nula de elegirse, resultando el valor medio oscilante en la utilidad, observado en la figura 15. A pesar de que este método implica que puedan existir nodos cambiando aleatoriamente de estrategia (y por tanto de canal y potencia de transmisión), esta variación en la asignación de recursos proporciona buenas prestaciones en términos de utilidad de red media, permitiendo alcanzar situaciones relativamente estables a las que no se puede llegar siguiendo una dinámica Best Response. Capítulo 6: Conclusiones y líneas futuras 65 Capítulo 6: CONCLUSIONES Y LÍNEAS FUTURAS Para finalizar la descripción del proyecto, en este capítulo se presentan las principales conclusiones extraídas de la realización del mismo. También se plantean las posibles líneas futuras de trabajo que puedan continuar con la tarea iniciada en este proyecto, así como ampliar todos aquellos aspectos que no se han tenido en cuenta. Tras la finalización de este proyecto se ha conseguido el objetivo propuesto de crear estrategias distribuidas de reparto de recursos que permitan un buen aprovechamiento de una red inalámbrica real. Este objetivo principal se ha llevado a cabo gracias a objetivos parciales que se han ido alcanzando, como ha sido la programación en C++ del entorno de simulación adecuado modificando el simulador ya existente y adaptándolo al nuevo modelo de interferencia (creación de las nuevas estrategias bajo el modelo del Physical Model), así como introduciendo nuevos conceptos necesarios para evaluar las prestaciones de las estrategias propuestas (creación de vectores con el conjunto de enlaces vecinos, programación de nuevas estadísticas, modificación del fichero de parámetros, etc.). Las alternativas propuestas se han basado en la teoría de juegos y se ha demostrado la validez de esta herramienta para modelar las interacciones entre los usuarios de la red cognitiva. Gracias a ello, se ha verificado que la propuesta del juego Capítulo 6: Conclusiones y líneas futuras 66 local es potencialmente la mejor, ya que una vez introducidas las condiciones necesarias para modelar un escenario real, ofrece utilidades de red semejantes al juego potencial, pero con el beneficio de que apenas requiere información de señalización. Resultados a partir de estas conclusiones han sido aceptados en un congreso internacional [18]. Por otra parte, el problema de la convergencia que el juego local presentaba al inicio del proyecto, se ha reducido con la introducción de los algoritmos con aprendizaje. A su vez, se ha solucionado la problemática que este algoritmo presentaba a la hora de seleccionar estrategias con menor potencia de transmisión (mejores en términos de capacidad global), mediante la programación de funciones que permitían modificar correctamente los pesos de elección de estrategias de acuerdo a dicha potencia. Este proyecto sienta las bases para la aplicación de la teoría de juegos y aprendizaje en el contexto de las redes inalámbricas distribuidas. Si bien se han obtenido interesantes conclusiones preliminares, los resultados obtenidos abren nuevas posibilidades de investigación. A continuación se enumeran algunas de las principales líneas futuras de trabajo: • Analizar matemáticamente los juegos propuestos para verificar la existencia del equilibrio (NE o coarse correlated) contrastando los resultados analíticos con la simulación. • Aumentar la complejidad del estudio mediante la inclusión de distintos tipos de usuarios con prestaciones diferenciadas de calidad de servicio. Analizar la justicia del sistema de reparto conseguido. • Extender las propuestas a escenarios multisalto, incorporando decisiones de encaminamiento. • Integración de las propuestas en protocolos de acceso al medio (y encaminamiento) para redes mesh cognitivas. Bibliografía 67 BIBLIOGRAFÍA [1] J Mitola III, G.Q. Maguire Jr., Cognitive radio: making software radios more personal. IEEE Personal Communications 6(4), 13-18 (1999). [2] I.F. Akylidiz, X. Wang, “A survey on wireless mesh networks”, IEEE Communications Magazine, vol 43, no.9, pp S23-S30, seept. 2005 [3] I.F. Akyildiz, W-Y Lee, K. R. Chowdhury, “CRAHNs: Cognitive Radio ad hoc Networks”, Ad Hoc Networks, vol 7, no. 5, pp. 810-836, Julio 2009. [4] C.A. Haro, L. Giupponi. Radio y Redes Cognitivas. 2010. [5] A. B. MacKenzie, P. Athanas, R.M. Buehrer. Cognitive Radio and Networking Research at Virginia Tech. vol. 97, no. 4, pp. 660–688, 2009. [6] I. F. Akyildiz, Won-Yeol Lee, M.C. Vuran, S Mohanty. A Survey on Spectrum Management in Cognitive Radio Networks, Georgia Institute of Technology. 2008. [7] I. F. Akyildiz, Won-Yeol Lee, M.C. Vuran, S Mohanty. Next generation/dynamic spectrum access/cognitive radio wireless networks: A survey, Georgia Institute of Technology, EE.UU, 2006. Bibliografía 68 [8] A Jafari, A Greenwald, D Gondek, G Ercal, On No-Regret Learning, Fictitious Play, and Nash Equilibrium, Proceedings. of the Eighteenth International Conference on Machine Learning, ICML '01, San Francisco, EE.UU, 2001. [9] J Neel, Analysis and design of cognitive radio networks and distributed radio resource management algorithms, Tesis Doctoral, Virginia Polytechnic Institute and State University, 2006. [10] P Gupta, PR Kumar, The capacity of wireless networks. IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388-404, 2000. [11] M. Canales, J.R: Gallego. Potential Game for joint Channel and Power Allocation in Cognitive Radio Networks, in Electronics Engineering and Communications, University of Zaragoza, 2010. [12] Y Shoham, R Powers, T Grenager, If multi-agent learning is the answer, what is the question? Artificial Intelligence, vol. 171, no. 7, pp. 365-377, 2007. [13] HP Young, The possible and the impossible in multi-agent learning. Artificial Intelligence vol. 171, no. 7, pp. 429–433, 2007. [14] GJ Gordon, A Greenwald, C Marks, No-regret learning in convex games, Proceedings of the 25th international conference on Machine learning (ICML '08). ACM, Nueva York, NY, EE.UU., pp. 360-367, 2008. [15] B Kleinberg, K Ligett, E Tardos, Beyond the Nash equilibrium barrier, in Proceedings of the Second Symposium on Innovations in Computer Science (ICS 2011), pp. 125 – 140, 2011. [16] Y Freund, R Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Proceedings of the Second European Conference on Computational Learning Theory (EuroCOLT’95), pp. 23-37, 1995. [17] K. Sastry, “Single and Multiobjective Genetic Algorithm Toolbox in C++”, IlliGAL Report No. 2007016, Illinois Genetic Algorithms Laboratory, University of Illinois, June 2007. [18] M. Canales, J.R. Gallego, R. Ciria. Distributed Channel Allocation and Power Control in Cognitive Radio networks using Game Theory. IEEE 74th Vehicular Technology Conference: VTC2011-Fall, 5-8 Septemeber 2011, San Francisco (EE.UU). Pendiente de publicación en libro de actas.