Entrega de datos escalable en redes móviles ad-hoc multi-salto - aplicación a protocolos de descubrimiento de pasarelas

Resumo

Las redes ad-hoc han emergido como una tecnología clave para comprender el futuro de las comunicaciones inalámbricas. El gran éxito de dichas redes subyace en la enorme cantidad de servicios que habilitan en múltiples escenarios diferentes. De hecho, esto ha llevado a definir distintas especializaciones de redes ad-hoc que, aunque mantienen los mismos principios básicos de comunicación autónoma, tienen suficientes diferencias entre ellas que impiden que una misma solución sea la más adecuada para todas. En esta tesis nos centramos en las Redes Móviles Ad-hoc (Mobile Ad-hoc Networks, MANET) y en las Redes Ad-hoc Vehiculares (Vehicular Ad-hoc Networks, VANET). Las MANET se proponen como la tecnología de comunicación más apropiada para permitir comunicaciones entre nodos cuando la infraestructura de red no está desplegada o ha sido destruida, como en el caso de una campaña militar o una operación de rescate ante una catástrofe natural. Por su parte, las VANETs soportan comunicaciones entre vehículos para implementar servicios de seguridad en carretera, de gestión eficiente del tráfico o de entretenimiento para los pasajeros. Sin embargo, antes de desplegar un servicio de este tipo hay que resolver una serie de retos a nivel tecnológico. Diseñar protocolos para redes ad-hoc es una tarea compleja. Los nodos deben colaborar entre ellos para encaminar paquetes a lo largo de caminos multi-salto. En este contexto, los protocolos deben ser adaptables a topologías cambiantes causadas por la movilidad de los nodos de la red y por el dinamismo intrínseco de las comunicaciones inalámbricas. Además, el canal inalámbrico se comparte entre los nodos de la red, de forma que el ancho de banda se reduce para cada uno de ellos. De este modo, los protocolos ad-hoc deben hacer un esfuerzo por no agotar los recursos de la red. De hecho, al compartir el ancho de banda, la capacidad total de la red queda limitada. Por tanto, los protocolos de comunicaciones deben idearse teniendo en cuenta la escalabilidad de la solución como principio básico de diseño. En resumen, cualquier solución realista para redes ad-hoc debería ser adaptable, eficiente y escalable. Además, debería tener en cuenta las características particulares del tipo de red (MANET o VANET en nuestro caso) que se está estudiando. La diseminación de datos es una de las primitivas de comunicación más importantes en las redes ad-hoc. Consiste en entregar un mensaje de datos a todos los nodos de la red (broadcasting) o, de forma más común, a todos los nodos que se sitúan en una región geográfica dada (geocasting o geobroadcasting). Debe implementarse según los requisitos de escalabilidad para redes ad-hoc que ya hemos mencionado. Además, la diseminación de datos debe ser confiable, entendiendo por tal que todos los nodos que deben recibir el mensaje lo reciban realmente. Este tipo de comunicación es de máxima relevancia para muchos servicios específicos de redes ad-hoc. Por ejemplo, los protocolos de enrutamiento MANET emplean diseminación de datos para propagar información topológica de la red. En el caso de las VANET, existen multitud de aplicaciones que van desde los servicios de seguridad en carretera a la gestión del tráfico. Así, un vehículo puede diseminar un mensaje a lo largo de una zona geográfica para alertar de que ha ocurrido un accidente, o de que determinadas calles se encuentran congestionadas de tráfico (los receptores del mensaje pueden elegir una ruta alternativa menos saturada). Para analizar el problema de la diseminación de datos, modelamos las redes con topología dinámica como grafos evolutivos. Esto nos permite introducir el concepto de la estructura mínima de broadcasting, una construcción matemática que representa la solución óptima, en términos de número de transmisiones, de una tarea broadcast en una red dinámica. Demostramos que obtener dicha estructura óptima es un problema NP, de forma que las soluciones en redes reales deben ser de naturaleza heurística. La definición que proporcionamos puede ayudar a diseñar futuros algoritmos para el problema de broadcasting en redes ad-hoc. En esta tesis, la empleamos para definir la clase de complejidad del problema de diseminación de datos y para desarrollar un algoritmo de exploración que encuentra la solución óptima. Dicho algoritmo sirve como la cota superior en cuanto a eficiencia que se puede obtener por una heurística, y lo utilizamos para compararlo en redes pequeñas con nuestro protocolo distribuido para broadcasting de datos: ABSM. ABSM es un protocolo muy eficiente, confiable y escalable para la diseminación de datos broadcast en VANET y MANET. Es una solución "localizada" en el sentido de que cada nodo decide por sí mismo si debe retransmitir o no un mensaje de datos, y para ello sólo utiliza información local. Hemos analizado ABSM de forma exhaustiva en simulaciones realistas de diferentes escenarios vehiculares, además de en pruebas de laboratorio y experimentos de campo con vehículos reales. En los resultados obtenidos se muestra que ABSM proporciona mayor confiabilidad que otras aproximaciones existentes en la literatura. Además, al mismo tiempo reduce drásticamente la sobrecarga de la tarea broadcast. Por último, no aumenta el retardo de la diseminación de datos, a pesar de que no ha sido diseñado con este objetivo en mente. Aunque las redes ad-hoc pueden operar por sí mismas sin requerir que exista infraestructura de red desplegada, hay muchas situaciones en que una mezcla de comunicaciones ad-hoc y basadas en infraestructura es al mismo tiempo posible y deseable. La red ad-hoc necesita al menos una pasarela que pertenezca a ambas redes y actúe como un punto de conexión a la infraestructura. A este tipo de redes se les suele llamar redes ad-hoc híbridas. Por ejemplo, un grupo de personas que lleven dispositivos con capacidad de comunicación pueden crear una MANET entre ellos que esté conectada en algún punto con una pasarela a Internet. Esto incrementa la cobertura radio efectiva del acceso a Internet, mientras que el Proveedor de Servicios de Internet (PSI) se ahorra el despliegue de nueva infraestructura. En el escenario militar o de rescate, la conectividad con Internet permite enviar información en tiempo real al cuartel general para dar soporte a la toma rápida de decisiones. En el caso de los servicios VANET, la presencia de infraestructura es también muy importante. Ella propicia que servicios de seguridad como un sistema post-accidente puedan enviar de forma inmediata un mensaje al centro de emergencias más cercano con información acerca de la localización y gravedad del siniestro. Además, permite que se implementen comunicaciones vehículo-a-vehículo en redes vehiculares dispersas. Por ejemplo, un vehículo podría intentar entregar un mensaje a todos los que se encuentren en un área determinada para avisarles de que una calle colindante está saturada de tráfico. Mientras el mensaje avanza a través de la VANET, éste podría llegar a un punto en que no existan más vehículos en la dirección de la propagación del mensaje. Si hay soporte de la infraestructura, el mensaje puede ser encaminado a través de la red del operador e inyectado de nuevo a la VANET en una localización diferente, donde la propagación puede continuar. De esta forma, las redes ad-hoc pueden beneficiarse del soporte de la infraestructura de red: se habilitan nuevos servicios, y se complementan los que ya se han diseñado. Para llevar a cabo comunicaciones en redes ad-hoc híbridas, la pasarela es el elemento clave que une ambas redes. Todas las comunicaciones entre la red ad-hoc y la de infraestructura pasan por una pasarela. Por tanto, cada nodo en la red ad-hoc que necesite comunicarse con la infraestructura debe estar al tanto de las pasarelas disponibles. Éstas no pueden ser configuradas a mano en cada nodo dada la naturaleza espontánea y no planificada de las redes ad-hoc. Así, un mecanismo automático conocido como protocolo de descubrimiento de pasarelas es necesario. Para ello, las pasarelas envían mensajes que contienen información relevante acerca de ellas mismas (puede verse como un caso particular de diseminación de datos). Estos mensajes son procesados por los nodos ad-hoc que están interesados en comunicarse con elementos que se hallan fuera de la red ad-hoc. De nuevo en este caso, el protocolo utilizado para el intercambio de mensajes debe adherirse a los requisitos de adaptabilidad, eficiencia y escalabilidad propios de las redes ad-hoc. Nuestra propuesta para MANETs consiste en un protocolo de descubrimiento adaptable de pasarelas basado en proxies. En él se anuncia de forma proactiva la información de la pasarela en una porción restringida de la red. Los nodos ad-hoc que se hallan fuera del área proactiva pueden solicitar bajo demanda conectividad con Internet. Cualquier nodo que conozca alguna pasarela puede contestar en lugar de ella, reduciendo en enorme proporción la sobrecarga del descubrimiento de la pasarela. El tamaño de la zona proactiva se adapta de forma dinámica según las condiciones actuales de la red, evitando así la configuración manual de dicho tamaño y permitiendo el uso del protocolo en una gran variedad de escenarios gracias a su adaptabilidad. Por medio de un sencillo modelo analítico y de un estudio basado en simulaciones, nuestro esquema muestra que es capaz de reducir de forma significativa la sobrecarga del protocolo, en comparación con otras propuestas que se encuentran en la literatura. Más aún, nuestra solución escala bien cuando el número de fuentes de datos y/o el de pasarelas en la MANET aumenta. Hasta donde nosotros sabemos, éste es el primer protocolo de descubrimiento de pasarelas escalable que se propuso en la literatura. Nuestra solución para MANET se centra en proporcionar a los nodos ad-hoc los servicios tradicionales de Internet. En el caso de las VANETs, algunos servicios envían mensajes de datos que son tolerantes al retardo por naturaleza. Por tanto, no necesitan cumplir un requisito de retardo demasiado estricto y pueden ser almacenados temporalmente por vehículos intermedios. Estos vehículos transportan el mensaje hasta que pueden reenviarlo a algún vecino que sea apropiado, de forma que la propagación continúe a partir de ahí. Nuestro protocolo GwDisc explota este paradigma almacena-transporta-reenvía para desarrollar un descubrimiento de pasarelas en VANET confiable, eficiente y escalable. Esta solución hereda las principales técnicas empleadas en ABSM. Por medio de simulaciones realistas, se muestra que GwDisc proporciona mayor rendimiento en distintos escenarios vehiculares que otros esquemas propuestos en la literatura. Además, experimentos en laboratorio y de campo demuestran que GwDisc es capaz de integrar la red ad-hoc con la de infraestructura. Por otra parte, se espera que las unidades embarcadas en vehículos estén equipadas con varias interfaces de comunicaciones. Además de las interfaces VANET de corto/medio alcance, los vehículos también se comunicarán a través de redes celulares. Por tanto, dado un flujo de datos que se origina por una aplicación en un vehículo, los protocolos de enrutamiento deben decidir el mejor camino que dicho flujo debe seguir según las necesidades de comunicación de ese servicio en particular. La decisión que tome el protocolo de enrutamiento puede tener un gran impacto en el servicio. Por ejemplo, si el protocolo de enrutamiento elige la red celular para alcanzar un vehículo cercano en una aplicación de diseminación de avisos, la alerta podría llegar demasiado tarde para que el conductor reaccione. En ese caso, el envío a través de la VANET hubiera sido más apropiado. Sin embargo, un comunicación orientada a la conexión con un servidor en Internet sería probablemente más adecuada para la red celular que utilizar un camino hacia la pasarela de la VANET con la red de infraestructura. En realidad, la mejor opción depende de los requisitos de la aplicación y del estado actual de la red. Para ayudar al protocolo de enrutamiento en la toma de decisiones, también desarrollamos el protocolo GwDiscE2E. Consiste en una solución para VANET que garantiza la existencia de un camino extremo a extremo entre la pasarela y cada vehículo que está al tanto de ella. Simulaciones realistas muestran que esta característica puede ser explotada por los protocolos de enrutamiento cuando hay disponible conectividad directa con la red de infraestructura. De esta forma, los flujos de datos sensibles al retardo pueden encaminarse por interfaces alternativas cuando el camino extremo a extremo por la VANET hasta la pasarela no está garantizado. En general, la investigación en redes ad-hoc ha carecido de experimentos en bancos de prueba realistas. La mayoría de artículos sobre el tema abordaban un problema dado analizándolo por medio de técnicas analíticas o por simulación. A pesar de que éstas son dos herramientas muy importantes (y que nosotros también utilizamos) para proporcionar información sobre el problema, pueden llevar a conclusiones erróneas. Frecuentemente esto se debe a la forma en que las comunicaciones inalámbricas se comportan en el mundo real. Suposiciones simplistas en modelos analíticos y de simulación pueden condicionar de manera importante el rendimiento del sistema bajo estudio. Este hecho se hizo presente en la comunidad investigadora, y desde entonces se ha trabajo mucho en proporcionar modelos más precisos. Además, esto propició la aparición de nuevos trabajos en los que se empleaban bancos de prueba y despliegues reales de redes ad-hoc. La experimentación en VANET es especialmente problemática debido al alto nivel de recursos que consume (vehículos, conductores, unidades embarcadas, personal técnico, planificación del experimento). A pesar de esto, nosotros también experimentamos con nuestros protocolos de comunicaciones en vehículos reales bajo situaciones normales de tráfico. La motivación viene dada por partida triple: i) demostrar que nuestros protocolos se pueden implementar y ejecutar en hardware embebido; ii) probar que nuestras soluciones funcionan de forma eficiente en redes reales; y iii) obtener medidas de rendimiento sobre las comunicaciones vehiculares ad-hoc en un entorno realista. Para integrar nuestras soluciones en una plataforma de comunicaciones real, también desarrollamos una arquitectura de comunicaciones para redes vehiculares. La Arquitectura DRIVE proporciona todos los componentes necesarios para integrar diferentes protocolos de comunicaciones. Diseñamos la arquitectura y proporcionamos una implementación, la cual hemos utilizado para probar nuestros protocolos ABSM y GwDisc en pruebas de laboratorio y experimentos de campo. Dichos experimentos se han llevado a cabo en situaciones normales de tráfico a la hora de extraer resultados de rendimiento.