Repositorio Institucional de Documentos

Proyecto Fin de Carrera Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Autor Francisco Javier Bravo Jiménez Director y ponente Jorge Ortín Gracia José Ramón Gállego Martínez Escuela de Ingeniería y Arquitectura Ingeniería Superior de Telecomunicaciones Convocatoria Septiembre 2012 2 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 (ad hoc, mesh), específicamente en el estudio de técnicas distribuidas de reparto de recursos evaluadas mediante teoría de juegos. Al tratarse de redes multisalto, es necesario abordar el diseño conjunto del encaminamiento (establecimiento de las rutas extremo a extremo) y la gestión de recursos de nivel de enlace (selección de canales, potencias de transmisión, etc.), lo que conlleva la resolución de problemas matemáticos complejos difícilmente aplicables en un contexto distribuido. Como alternativa, la teoría de juegos es una herramienta matemática que analiza las interacciones estratégicas entre múltiples agentes que toman decisiones. Por esta razón, resulta adecuada para analizar de una manera más formal las prestaciones de este tipo de redes, donde cada nodo debe decidir sus parámetros de configuración de manera autónoma. Sin embargo, la complejidad matemática de los problemas a resolver resulta difícil de abordar computacionalmente. Una alternativa es el desarrollo de simuladores que modelan las interacciones entre los individuos los nodos de la red, partiendo de diversas condiciones iniciales, que permiten resolver, de manera heurística, el problema planteado. En este proyecto se ha modificado un simulador ya existente sobre el que se han implementado distintas soluciones relativas a la generación de una topología de red mesh realista y a la selección de nodos Gateways en la misma, analizando mediante la aplicación de la teoría de juegos los flujos establecidos finalmente en la red. Respecto a la topología, se ha optado por programar una estructura en la que las posiciones de los nodos se corresponden a los cruces de una cuadrícula, pudiendo introducir un error en la posición de los mismos para moldear un escenario real en la que la disponibilidad geográfica de los puntos 3 exactos está limitada. A partir de esta topología se han desarrollado varios algoritmos para la selección de los Gateways de la red y la generación de las rutas desde los distintos nodos de la red a dichos Gateways. Seguidamente, se ha obtenido el número mínimo de nodos Gateway necesarios y su configuración espacial dentro de la topología de la red para asegurar una conectividad total en la red (esto es, que no queden nodos en la topología que no dispongan de conexión con un Gateway). Estos resultados se han obtenido mediante simulación y aplicando teoría de juegos para los distintas configuraciones de topología que se han planteado. Finalmente, se ha analizado cómo afecta al sistema la presencia de perturbación en la posición de los nodos de la red, obteniendo la degradación en términos de conectividad que dichos errores provocan. Todo esto permite establecer el punto de partida para desarrollar en el futuro algoritmos de gestión de recursos de nivel de enlace junto con el diseño del encaminamiento y su implementación en protocolos en redes mesh cognitivas. 4 1. Introducción 7 1.1. Objetivo y alcance del proyecto 7 1.2. Trabajo previo y contexto 7 1.3. Metodología de trabajo 8 1.4. Contenido de la memoria 11 2. Modelado del sistema 13 2.1. Topología 13 2.1.1. Topología uniforme 13 2.1.2. Topología uniforme con perturbación 14 2.2. Conectividad 17 2.2.1. Conectividad de la red: Enlaces 17 2.2.2. Conectividad de la red: Flujos 20 2.3. Algoritmo de Dijkstra 22 2.4. Asignación de recursos: Juego de flujos 25 3. Algoritmo de selección de Gateways 29 3.1. Algoritmo determinista de selección de nodos Gateways 29 3.2. Algoritmo heurístico probabilístico 31 4. Análisis de resultados 35 4.1. Descripción del escenario de simulación 35 4.2. Métricas de evaluación 36 4.3. Evaluación de las prestaciones de red 37 4.3.1. Evaluación de rutas activas 37 4.3.2. Comparativa número de rutas 40 4.3.3. Modelo más realista: introducción de perturbación en la topología 41 4.3.4. Algoritmo probabilístico de elección de nodos Gateways 42 5. Conclusiones y líneas futuras 44 6. Bibliografía 46 5 6 Índice de figuras y tablas Figura 1.- Tipo de red cuya infraestructura tiene dos tipos de nodos de acceso y Gateways (Página 10). Figura 2.- Esquema de la topología uniforme de una red inalámbrica (Página 14). Figura 3.- Distancia de perturbación respecto a la posición inicial (Página 15). Figura 4.- Perturbación en la fase respecto a la posición inicial (Página 16). Figura 5.- Cálculo de la perturbación final respecto de la posición fija inicial (Página 16). Figura 6.- Diferencia entre topología uniforme y perturbada (Página 17). Figura 7.- Establecimiento de links entre nodos adyacentes (Página 20). Figura 8.- Dos ejemplos de flujos creados en la red mesh (Página 22). Figura 9.- Árbol de decisión de algoritmo de Dijkstra (Página 24). Figura 10.- Algoritmo de Dijkstra (Página 25). Figura 11.- Disposición de nodos Gateway con , con el primer nodo Gateway en la posición (Página 31). Figura 12.- Diagrama de flujo de la función principal (Página 33). Figura 13.- Diagrama de flujo de algoritmo probabilístico de auto-asignación de nodos Gateways (Página 34). Figura 14.- Comparativa de porcentaje de flujos activos en función del nº de canales y nodos Gateway (Página 38). Figura 15.- Evaluación de rutas activas en función del número de canales (Página 39). Figura 16.- Comparativa de Links/flujo con 100% de flujos activos (Página 40). Figura 17.- Comparativa número de rutas con 12 canales (Página 41). Figura 18.- Evaluación de introducción de error en topología fija uniforme (Página 42). Tabla 1.- Tabla de resultados de nodos Gateway e iteraciones con algoritmo probabilístico (Página 43). Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 7 1. Introducción 1.1. Objetivo y alcance del proyecto Tal y como se ha comentado en el resumen, este proyecto se enmarca dentro del contexto de redes inalámbricas cognitivas distribuidas (ad hoc, mesh). Al tratarse de redes multisalto, es necesario abordar el diseño conjunto del encaminamiento (establecimiento de las rutas extremo a extremo) y la gestión de recursos de nivel de enlace (selección de canales, potencias de transmisión, etc.) Específicamente, el objetivo principal es el diseño de topologías realistas, la selección en la disposición espacial de nodos Gateways dentro de estas topologías, así como el estudio de estrategias de selección las rutas [1] a establecer entre los distintos nodos de la red. 1.2. Trabajo previo y contexto Este proyecto se realiza en el Departamento de Ingeniería Electrónica y Comunicaciones (DIEC), dentro del Grupo de Tecnologías de las Comunicaciones (GTC). El grupo GTC es uno de los componentes del Instituto de Investigación de Ingeniería en Aragón (I3A) que se ha reconocido como Grupo Consolidado de Investigación por el Gobierno de Aragón. Dentro de las múltiples áreas de investigación que realiza este grupo, el proyecto se enmarca en el contexto de “comunicaciones móviles”. Esta línea de investigación genérica tiene como objetivos planificar y optimizar sistemas de comunicaciones móviles, la gestión de recursos de radio y control de acceso en redes celulares de tercera generación, prestación de servicios de calidad en el contexto de las redes híbridas de móviles con circulación heterogénea, redes “ad-hoc” y utilización de tecnología de banda ultra ancha (UWB). A continuación, se comenta el contexto específico en el que se ha desarrollado el proyecto. Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 8 El gran crecimiento que han experimentado las aplicaciones inalámbricas en los últimos años ha generado un crecimiento exponencial en el uso de bandas frecuenciales sin licencia, provocando problemas de escasez en el ancho de banda disponible. Este problema no sólo es debido a las limitaciones “reales” en el ancho de banda disponible, sino también a la gestión ineficiente que se hace del espectro radioeléctrico. Como respuesta a esta problemática surge el concepto emergente de redes inalámbricas cognitivas. Dichas redes están formadas por dispositivos que permiten que usuarios sin licencia (secundarios) puedan utilizar estas bandas frecuenciales con licencia de manera oportunista y dinámica, garantizando que no se va a generar interferencia sobre los usuarios con licencia (primarios). En un sentido más amplio, las “radios cognitivas” [6] son dispositivos inalámbricos completamente programables capaces de identificar las condiciones de su entorno y adaptarse dinámicamente a ellas modificando su configuración, desde niveles físicos hasta cualquier nivel de la pila de protocolos. En esta línea se sitúan las redes inalámbricas cognitivas, en cuyo estudio se centra este proyecto. 1.3. Metodología de trabajo Cómo se ha planteado anteriormente, el objetivo del proyecto es abordar el análisis de topologías realistas, y la selección de Gateways y rutas en una red mesh inalámbrica dentro de las topologías planteadas. Para conseguir la evaluación de la red, y poder obtener resultados, las propuestas planteadas se evaluarán mediante simulación. Para ello, se ha seguido la línea de trabajo de investigaciones ya existentes, basadas en el modelado de la interacción de los usuarios mediante teoría de juegos. Las redes mesh inalámbricas son redes fijas en las que los distintos nodos de la red establecen enlaces inalámbricos entre sí formando una topología mallada multisalto. Habitualmente, este tipo de redes se dividen en dos niveles, el nivel de acceso, mediante el cual los usuarios se conectan a la red vía Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 9 inalámbrica, y el nivel de transporte, que dota de interconexión entre los distintos nodos de la red, también de modo inalámbrico. Dentro de esta red de dos niveles, cabe diferenciar dos tipos de nodos que se encuentran colocados de manera estratégica en la topología de red:  Nodo de acceso, conforman el primer nivel de acceso o última milla de la red. Se encuadran la mayoría de los nodos que componen la red. Son nodos que generan la interconexión entre los usuarios (pcs, dispositivos móviles, pdas, impresoras…) y la red. A su vez conforman enlaces entre ellos, para encaminar el tráfico hacia el Gateway más cercano.  Nodo Gateway, conforman el segundo nivel o nivel de transporte de la red. Estos nodos disponen de conexión a Internet, y encaminan la salida de la red hacía otras posibles redes externas, para dotar de conexión a los usuarios. Esto implica, que debe existir al menos un flujo activo (con sus enlaces correspondientes) entre todos y cada uno de los nodos de acceso y un nodo Gateway para dotar a la red de un 100% de conectividad. En la figura 1, se observa de manera gráfica un esquema de red mesh, diferenciando entre nodos acceso y nodos Gateway, estableciendo enlaces entre sí. Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 16 Siendo el valor que toma la fase correspondiente al nodo . Figura 4.- Perturbación en la fase respecto a la posición inicial  Cálculo de la perturbación final respecto de la posición fija inicial: Figura 5.- Cálculo de la perturbación final respecto de la posición fija inicial En la siguiente figura se puede observar la diferencia final entre una topología fija sin y con perturbación. Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 17 Figura 6.- Diferencia entre topología uniforme y perturbada Con la introducción de esta perturbación, se consigue uno de los objetivos marcados en el proyecto de dotar al simulador de un mayor realismo. En el capítulo 4 en el que se analizan los diferentes resultados obtenidos en las simulaciones, se estudia cómo afecta la perturbación en la disposición de los nodos, al establecimiento de flujos y el encaminamiento de rutas. 2.2. Conectividad En esta sección se va a comentar cómo se establecen las distintas conexiones en la red, creando distintos enlaces entre nodos que a su vez se unen para formar flujo entre nodos acceso y nodos Gateway. 2.2.1. Conectividad de la red: Enlaces Dentro del sistema implementado, para dotar de conectividad a la red, los nodos establecen entre sí enlaces radio, usando uno de los canales que tiene disponible. Para ello en primer lugar debe definirse un modelo de interferencia que permita caracterizar el entorno en una red inalámbrica. Concretamente en este Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 18 proyecto se ha utilizado el modelo físico de interferencia (Physical Model [5]), ya implementado en el simulador previamente existente. El modelo físico es un modelo de interferencia en el que todo transmisor contribuye al nivel de interferencia en los receptores que transmiten en el mismo canal que él. Así, la correcta decodificación de la señal en un enlace depende de la relación señal a ruido e interferencia recibida (SINR - Signal to Interference and Noise Ratio), y esta depende de la potencia recibida en su receptor y de la interferencia de cualquier otro transmisor en el entorno. Este modelo introduce un mayor grado de complejidad que el más sencillo modelo de protocolo (Protocol Model [5]) modelando un entorno más realista. Supongamos que tenemos una red inalámbrica multi-salto con nodos y canales no solapados. Asumimos, como se ha comentado anteriormente, que cada nodo puede transmitir solamente en un subconjunto específico de estos canales, que pueden variar desde un nodo a otro, por ejemplo, debido a la existencia de usuarios primarios (con licencia de transmisión). Asumimos también que cada enlace solo puede transmitir en un canal y que la potencia de transmisión está discretizada en niveles, equidistantes de 0 y de la máxima potencia de transmisión . Así, la potencia de transmisión del enlace es: (5) con En este modelo, una comunicación en un enlace es viable cuando la relación señal a ruido e interferencia supera determinado umbral  . En la expresión (6) se muestra dicha condición, donde dado un enlace entre un par de nodos la ganancia entre el transmisor y el receptor se define como ; siendo la distancia entre el transmisor y el receptor y el índice de pérdidas de propagación o Path Loss. Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 19 De manera análoga, ; representa la ganancia desde el transmisor del enlace hasta el receptor del enlace . Asumimos que el enlace utiliza únicamente un canal . es la potencia de transmisión asignada al enlace , es el conjunto de todos los enlaces de la red y es la potencia de ruido. (6) Con este modelo de interferencia se asume que cada comunicación ocupa siempre todo el ancho de banda disponible del canal utilizado y que pueden establecerse varias comunicaciones de forma simultánea en un mismo canal siempre y cuando la SINR de cada una de ellas sea mayor que el umbral establecido. Dado este modelo, la capacidad de un enlace , puede definirse de varias maneras, dependiendo del objetivo de diseño del sistema. En el caso de querer maximizar la capacidad en bps, sería interesante definir la capacidad los enlaces en bps. Sin embargo, puesto que el objetivo en este proyecto es el establecimiento de flujos entre los nodos de acceso y los Gateways, el único requisito exigible a los enlaces es que sean viables (es decir, que su SINR sea superior al umbral). De esta manera, podemos definir la capacidad de los enlaces de manera binaria: Concretamente, en la topología utilizada en este proyecto, y debido a las restricciones del modelo físico de interferencia, consideramos que solo se pueden establecer enlaces entre nodos adyacentes. En la figura 7 se pueden observar todos los posibles enlaces que un nodo puede establecer. Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 20 Figura 7.- Establecimiento de links entre nodos adyacentes 2.2.2. Conectividad de la red: Flujos Se define un flujo, como el camino físico a través de diferentes enlaces, entre un nodo de acceso y un nodo Gateway. Por tanto, un flujo no es más que la unión consecutiva de varios enlaces. En el contexto de este proyecto cada nodo de acceso dispone de dos rutas multi-salto a sus dos Gateways más cercanos. Para ello se ha adaptado en el simulador ya implementado, modificando el cálculo de rutas a dos nodos Gateways diferentes, frente al cálculo de dos rutas diferentes al mismo nodo Gateway desde cada nodo fuente acceso. El objetivo perseguido es obtener un flujo activo, utilizando una de esas dos rutas, entre cada nodo de acceso y un Gateway. En el capítulo de resultados se obtiene mediante simulación el número de nodos Gateway mínimos a implementar en cada topología en función del número de canales disponibles en cada una de ellas para cumplir este objetivo. Como se ha comentado anteriormente, en este escenario un flujo es factible sí y sólo sí todos los enlaces de una de sus rutas puede ser Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 21 establecidos simultáneamente. La capacidad de una ruta específica en un flujo será 1 si todos los enlaces del flujo están activos y 0 en caso contrario. Teniendo en cuenta la anterior definición de tenemos: (8) Donde denota el subconjunto de links que pertenecen a la ruta del flujo . Por la propia definición de nuestro problema, solo una ruta del flujo va a estar activa al mismo tiempo: Disponemos de dos posibles rutas para cada nodo de acceso, pero solo necesitamos que una de las dos esté activa. Así, de manera formal, la capacidad del flujo puede obtenerse de la siguiente forma: (9) Dicha capacidad será 1 si existe una ruta con todos los enlaces activos y 0 en caso contrario. En el siguiente esquema, se explica de manera visual la definición de un flujo con dos rutas a los dos nodos Gateway más cercanos. La línea azul representa el flujo con la ruta al Gateway más cercano y la roja al segundo Gateway más cercano. Por tanto este flujo dispone de ambas rutas para tratar de establecer la conexión entre el nodo origen y el Gateway destino. Notar que los flujos siempre se establecen utilizando el menor número de saltos (links) posibles, para hacer una ruta lo más corta posible y minimizar la interferencia de la red, a los dos nodos Gateway más cercanos. Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 22 Figura 8.- Dos ejemplos de flujos creados en la red mesh 2.3. Algoritmo de Dijkstra A continuación se detalla de forma teórica el algoritmo de Dijkstra [4], utilizado en el marco de este proyecto, para el cálculo de las rutas multi-salto para dar solución al problema de encaminamiento en redes mesh. Concretamente, se ha utilizado el algoritmo de Dijkstra ya implementado en el simulador, adaptándolo para el cálculo de las rutas más cortas entre nodos acceso y nodos Gateways. El algoritmo de Dijkstra, es un algoritmo eficiente que sirve para encontrar el camino de coste mínimo desde un nodo origen a todos los demás nodos del grafo. Fue diseñado por el holandés Edsger Wybe Dijkstra en 1959. El desarrollo del algoritmo de Dijkstra se hace en dos etapas. La primera etapa trata el problema de determinar el costo del camino de mínimo coste que parte de un nodo y termina en cada uno de los demás nodos del grafo. La segunda etapa almacena además la secuencia de nodos que conforman dicho camino. Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 23 Etapa 1.- Inicialización y búsqueda de camino (10) Encontramos: (11) Puede existir un empate, en tal caso se elige uno arbitrariamente o de acuerdo a un criterio marcado (12) Si contiene a todos los nodos se para, si no continuamos con la etapa 2. Etapa 2.- Actualización } (13) En concreto, a la hora de elegir la ruta más corta, con la topología de red que se presenta en este proyecto el peso entre todos los nodos adyacentes es 1, con lo que nos encontramos en un caso particular del algoritmo de Dijkstra conocido con Breadth First Search (BFS). BFS va formando un árbol a medida que va recorriendo un grafo. Ver figura 9 Tal y como se indica en la figura 9, todo parte de un nodo inicial que será la raíz del árbol que se forma, luego ve los adyacentes a ese nodo y los agrega en un cola, como la prioridad de una cola es FIFO (primero en entrar es el primero en salir), los siguientes nodos a evaluar serán los adyacentes previamente insertados. Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 24 Una cosa muy importante es el hecho de que no se puede visitar dos veces el mismo nodo o estado, ya que si no podríamos terminar en un ciclo interminable o simplemente no hallar el punto deseado en el menor número de pasos. Figura 9.- Árbol de decisión de algoritmo de Dijkstra Se detalla a continuación el algoritmo de Dijkstra (BFS) en pseudocódigo. Para entrar en más detalle, se recomienda consultar el apartado correspondiente del anexo A, dentro de la función implementada en C++ T_routes_calculation se encuentra la aplicación del algoritmo de Dijkstra para encontrar el camino más corto entre nodos. Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 25 Figura 10.- Algoritmo de Dijkstra 2.4. Asignación de recursos: Juego de flujos. Ya se ha explicado, de manera detallada, la topología de red y se ha definido el algoritmo de Dijkstra para el cálculo de las rutas más cortas entre nodos acceso y nodos Gateway. Una vez han quedado definidas estas rutas, necesitamos abordar el problema de la asignación de recursos (potencias y canales), para garantizar la conectividad de la red mediante el establecimiento de enlaces y flujos. Esta asignación puede plantearse como 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 se necesita buscar otro tipo de soluciones. Al carecer de una entidad central, la asignación de recursos se realiza gracias a las decisiones individuales de los nodos modeladas mediante juegos. La teoría de juegos [7] es una herramienta matemática que permite modelar y analizar las interacciones entre agentes racionales que toman Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 32 tan solo un nodo Gateway dispuesto de manera óptima en la red (en el centro de la misma, con la menor distancia posible al resto de nodos). Una vez se ha ejecutado el juego de flujos, se evalúan las prestaciones obtenidas Se evalúan el número de flujos activos y sus nodos fuente. Estos nodos fuente con flujos establecidos y activos a un nodo Gateway después del juego, van a permanecer como nodos de acceso en la siguiente interacción del algoritmo. Entre el resto de nodos de acceso que no tienen flujos activos, se van a elegir los nodos que se van a convertir en Gateways para la siguiente iteración de manera probabilística. Para ello, de forma independiente, cada nodo de acceso sin flujos activos, se convierte o no en nodo Gateway de acuerdo a una probabilidad en forma de parámetro de entrada. Una vez se han definido los nuevos nodos Gateways a disponer en la red, se vuelve a la posición de comienzo del juego, hasta conseguir el objetivo propuesto de 100% de flujos activos en la red. A continuación se dispone de un diagrama de flujos, que indica de manera visual y simplificada el algoritmo mostrado en este capítulo. En el siguiente diagrama de flujo (figura 12), se indica el algoritmo seguido en la función principal. En la siguiente página, concretamente la figura 13, se presenta el diagrama de flujo de algoritmo de autoselección de nodos Gateway presentado en este capítulo. Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 33 Figura 12.- Diagrama de flujo de la función principal El flujo representado en la figura 13, para la selección de Gateways de manera probabilística, se complementa con la función principal (figura 12), donde se explican los juegos. Concretamente se encapsula entre los estados evaluación de las estadísticas y fin de la simulación para subir en cada iteración al juego de flujos. Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 34 Figura 13.- Diagrama de flujo de algoritmo probabilístico de auto-asignación de nodos Gateways Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 35 4. Análisis de resultados En este capítulo se va a presentar un informe detallado de los resultados que se han obtenido a lo largo del proyecto. Todas las alternativas se han evaluado mediante simulación, introduciendo diferentes variantes para dotar al simulador de mayor realismo tal y cómo se ha indicado en los capítulos anteriores. 4.1. Descripción del escenario de simulación Como entorno de simulación se ha modificado un simulador ya existente implementado en C++, utilizando el modelo de interferencia (Physical Model), e introduciendo diferentes alternativas para dar solución al problema del encaminamiento propuesto al principio del proyecto. En el Anexo A se explica cómo se ha implementado dicho simulador, detallando un breve manual de uso. Los juegos han sido evaluados en escenarios con distinto números de nodos Gateway y distintas densidades de enlaces, manteniendo una topología uniforme de red, obteniendo diferentes resultados. Se detalla a continuación las características de la topología fija utilizada en las simulaciones realizadas. La red consiste en un conjunto de 144 nodos distribuidos uniformemente en un área cuadrada de 1200 metros de lado. Se han considerado varios números diferentes de nodos Gateway, números cuadrados perfectos desde 1 hasta 36, tal y cómo se comenta en el apartado 3.2. A su vez se ha simulado con diferentes números de canales desde 4 a 56, y con una o 2 rutas a diferentes nodos Gateway dentro de un mismo flujo manteniendo el número canales constante a 12. La potencia máxima, es 20 dBm; la potencia de transmisión ha sido discretizada en 16 niveles; el coeficiente de pérdidas por propagación es , y, por simplicidad, el ancho de banda que ocupa cada canal, se ha normalizado a 1. La umbral (6) es 10 dB. El rango de transmisión máximo Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 36 se ha fijado en 250 metros (aunque como se ha comentado en el apartado 2.2.1, solo se establecen enlaces entre nodos adyacentes), por lo tanto, la potencia de ruido, , será -85,9 dBm. Los resultados que se van a presentar se han obtenido mediante el cálculo de la media de 100 simulaciones por cada estrategia, previamente procesados mediante un pequeño programa implementado en Matlab que se detalla en el Anexo B. El juego está adaptado hasta alcanzar un Equlibrio de Nash.. Como se especifica en los apartados correspondientes, en situaciones puntuales se ha extendido la simulación en el número de canales para verificar la convergencia al 100% de flujos activos. El encaminamiento entre nodos se ha implementado usando el algoritmo de Dijkstra comentado en el apartado 2.1.3. Un breve resumen de la implementación de dicho algoritmo se presenta en el anexo A. En el caso de 4 nodos Gateways, se ha aumentado el número de canales hasta 56 para verificar su convergencia a 100 % de flujos activos. También se incluye como referencia el resultado de las simulaciones realizadas con el algoritmo heurístico probabilístico de elección de nodos Gateways que se presenta en el capítulo 3.2. En el anexo A, se puede consultar todo lo relacionado con el simulador implementado en C++. 4.2. Métricas de evaluación Para evaluar las distintas propuestas se han considerado diversas métricas, tal y como se especifica a continuación:  Porcentaje de Flujos activos: Muestra el porcentaje de flujos que se han establecido en la red. El objetivo es el 100% ya que necesitamos que todos los usuarios conectados a un nodo acceso Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 37 tenga al menos un flujo activo a un nodo Gateway para dotar de conexión a dicho usuario.  Número de Gateways: Se muestra el número de Gateways mínimo necesario, para diferentes canales, para obtener un porcentaje de flujos activos del 100%.  Número medio de links por flujo; Indica el número medio de links por flujo, cuando el 100% de estos flujos están establecidos. 4.3. Evaluación de las prestaciones de red Como ya se ha comentado, en este apartado vamos a analizar los resultados conseguidos a través de las métricas de evaluación ya propuestas. La presentación de resultados responde a la secuencia que se ha seguido en el proyecto, desde el escenario de referencia usando el modelo físico de interferencia (inclusión de una topología fija uniformemente distribuida en el simulador previo y diseño e implementación de un algoritmo determinista para elección de nodos Gateway), la evaluación de las prestaciones con diferentes parámetros, la introducción de mayor realismo con la introducción de la topología perturbada respecto a la uniforme, y la incorporación de un algoritmo probabilístico para la auto-elección de nodos Gateway. 4.3.1. Evaluación de rutas activas En este apartado se analiza el porcentaje de flujos activos, en función de diferentes parámetros de configuración como número de nodos Gateway, o número de enlaces. Se complementa mostrando el número medio de links por flujo cuando la red tiene un 100% de flujos activos, Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 38 Figura 14.- Comparativa de porcentaje de flujos activos en función del nº de canales y nodos Gateway Tal y cómo se observa en la figura 14, si se disponen en la red 16 o 36 nodos Gateway (un 11,1% o un 25% de los nodos son Gateways), se consigue, con diferente número de canales, obtener un 100% de flujos activos, lo que significa que la red estaría dimensionada para dar acceso a los usuarios que consigan establecer conexión con cualquiera de los nodos acceso dispuestos en la red mesh. Se observa como con 36 nodos Gateway tan solo serían necesarios 12 canales para obtener total conectividad de red, así como con 16 nodos Gateway serían necesarios al menos 16 canales para garantizar dicha conectividad. La figura 15, que se muestra a continuación, nos enseña que con un número de canales inferior a 12 no es posible garantizar el 100% de conectividad a todos los nodos acceso de la red. 0 10 20 30 40 50 60 70 80 90 100 1 4 9 16 36 % Flujos Activos Nº de Gateways Nº de Canales 4 Canales 8 Canales 12 Canales 16 Canales 20 Canales Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 39 Figura 15.- Evaluación de rutas activas en función del número de canales También se extrae de la Figura 15, que para conseguir total conectividad de la red, para 16 y 36 nodos Gateway se necesitan un número relativamente reducido de canales, para 9 Gateways estaríamos en un punto intermedio, y vemos como para 4 nodos Gateway, para garantizar el 100% de flujos activos, se dispara hasta 56 canales. Esto es previsible, debido a que al disponer de tan solo cuatro nodos Gateway en la red, los flujos son excesivamente largos, y se incrementa notablemente el número de enlaces activos en la red, lo que genera una interferencia muy elevada. También se desprende de la gráfica anterior, haciendo una estimación de las simulaciones realizadas, que al disponer de tan solo un nodo Gateway en la red, no se garantiza la convergencia al 100% de rutas activas, a no ser que incrementáramos en gran medida el número de canales disponibles 0 10 20 30 40 50 60 70 80 90 100 4 8 12 16 20 24 28 32 36 40 44 48 52 56 % Flujos Activos Nº de Canales Nº de Gateways 1 Gateway 4 Gateways 9 Gateways 16 Gateways 36 Gateways Lineal (1 Gateway) Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 40 En la siguiente figura, se realiza una comparación entre el número medio de links por flujo necesarios con diferente número de nodos Gateways cuando han alcanzado el 100% de flujos activos. Se observa que a partir de 16 Gateways ya solo es necesario un link por flujo activo, así como con 4 son necesarios más de dos links de media por flujo. Figura 16.- Comparativa de Links/flujo con 100% de flujos activos 4.3.2. Comparativa número de rutas La figura 17 realiza una comparativa entre la conectividad conseguida por la red con diferentes números de nodos Gateway, diferenciando entre flujos con una ruta o flujos con dos rutas. Podemos extraer de los resultados obtenidos, que el rendimiento con una ruta o dos rutas disponibles es muy similar. Pero como se indica en el capítulo de conclusiones, al ser resultados parejos, interesa dotar a la red de 2 rutas, ya que dispone de redundancia y mejora la robustez de la red, ante 0 0,5 1 1,5 2 2,5 4 9 16 36 Nº de Gateways Link/flujo Estudio de estrategias de selección de ruta en redes mesh cognitivas mediante teoría de juegos Francisco Javier Bravo Jiménez 41 posibles perturbaciones en los enlaces establecidos o cualquier fallo en uno de los dos nodos Gateway. Figura 17.- Comparativa número de rutas con 12 canales 4.3.3. Modelo más realista: introducción de perturbación en la topología Con el objetivo de dotar de mayor realismo a la topología, se introduce el concepto del error en la disposición uniforme. Se observa en la figura 18 que hasta un 20% de error sobre la disposición uniforme no conlleva repercusión negativa en la conectividad de la red, no siendo así con una perturbación del 40%, cuando sí que se observa repercusión negativa en la red. 0 10 20 30 40 50 60 70 80 90 100 4 9 16 36 %Flujos Activos Nº de Gateways Nº de Rutas 2 Rutas 1 Ruta