Evaluación mediante simulación de redes de sensores aplicadas a robots móviles

Trabajo Final de M´ aster Evaluaci´on mediante simulaci´on de redes de sensores aplicadas a robots m´oviles y veh´ıculos ligeros Autor: Navarro Alabarta, Jos´e Dirigida por: Dr. Capella Hern´andez, Juan Vicente Dr. Valera Fern´andez, ´ Angel Trabajo Final de M´aster en Autom´atica e Inform´atica Industrial Instituto de Aplicaciones de las Tecnolog´ıas de la Informaci´on y de las Comunicaciones Avanzadas (ITACA) Instituto de Autom´atica e Inform´atica Industrial (ai2) Departamento de Ingenier´ıa de Sistemas y Autom´atica (DISA) Departamento de Inform´atica de Sistemas y Computadores (DISCA) 14 de diciembre de 2015 Resumen En el siguiente Trabajo Final de M´aster se realiza un estudio de los protocolos de enrutamiento de redes vehiculares. Estos protocolos se dividen en dos grandes grupos, los protocolos basados por el encaminamiento y los basados por localizaci´on geogr´afica. Este primer grupo a la vez se divide en dos grupos, los basados en protocolos reactivos y los proactivos. La diferencia entre estos dos subtipos de protocolos es que los reactivos obtienen la informaci´on de direccionamiento en el momento exacto que se necesita y en cambio los protocolos proactivos est´an constantemente enviando y solicitando la informaci´on. Los protocolos m´as representativos de estudio son AODV y DSR en cuanto a protocolos reactivos, y OLSR y DSDV en cuanto a proactivos. Respecto a los protocolos basados en geolocalizaci´on, estos se caracterizan porque necesitan de dispositivos GPS para poder trabajar correctamente. En los ´ultimos a˜nos a este tipo de protocolos se les ha ido a˜nadiendo t´ecnicas de inteligencia artificial para optimizar y hacerlos m´as robustos y fiables. Este tipo de protocolos se integran con sistemas de transporte inteligente, de esta forma, con este tipo de sistema se pretende reducir el n´umero de accidentes y otros factores que afectan a la conducci´on. En cuanto a la etapa de experimentaci´on, el proceso se divide en diversas subetapas, la primera de ellas esta basada en el dise˜no y desarrollo de protocolos confiables y robustos. Una vez superada esta etapa hay que obtener tendencias de conducci´on con los simuladores de movilidad, para as´ı, obtener la dicha informaci´on y suministrarla al simulador de redes inal´ambricas para poder estudiar los diversos comportamientos que van ocurriendo, como es el caso del estudio de la densidad de los nodos, de como afectan las sobrecargas en la red, el retardo en la entrega de los paquetes, adem´as de la tasa de paquetes perdidos. Esta etapa, permite iterar sobre ella, de forma que seg´un los resultados obtenidos se puede redefinir las especificaciones, adem´as permite la evaluaci´on de las propuestas con un gran n´umero de dispositivos sin constes adicionales. Cuando los resultados son los deseados se pasa a la ´ultima etapa del proceso, que consiste en implementar el protocolo en equipos f´ısicos. Este TFM cubre las dos primeras etapas descritas, constituyendo un primer paso necesario para el desarrollo de futuros trabajos en la l´ınea de mejorar los sistemas basados en protocolos de enrutamiento basados en GPS aplicables tanto a veh´ıculos como robots m´oviles. Adem´as se ha propuesto un ecosistema completo para el dise˜no y evaluaci´on de este tipo de protocolos. En esta l´ınea, se ha desarrollado un modelo de protocolo de enrutamiento para VANETs con caracter´ısticas novedosas, habi´endose validado y realizado una completa evaluaci´on del mismo mediante el ecosistema propuesto. Finalmente, tambi´en se han realizado ya las primeras implementaciones y pruebas sobre hardware real que permitir´a la aplicaci´on de los protocolos propuestos, con resultados muy positivos. Resum En aquest Treball Final de M`aster ´es realitza un estudi dels protocols d’encaminament de xarxes vehiculars. Aquestos protocols es divideixen en dos grans grups, els protocols basats per l’encaminament i els basats per localitzaci´o geogr`afica. El primer grup a m´es a m´es, es divideix en altres dos subgrups, els basats amb protocols reactius i amb els proactius. La difer`encia amb ambd´os subtipus de protocols es que al cas dels reactius adquireixen la informaci´o d’encaminament al moment exacte que es necessita, i en canvi estan constantment transmitent-la i sol·licitant-la. Els protocols m´es representatius d’estudi son AODV i DSR en quant al reactius, i OLSR i DSDV en quant als proactius. Pel que fa als protocols basats per geolocalitzaci´o es caracteritzen per emprar dispositius GPS per al seu correcte funcionament. Als ´ultims anys a aquest tipus de protocols se’ls ha anat afegint t`ecniques d’intel·lig`encia artificial per optimitzar i fer-los m´es robustos i fiables. Aquests tipus de protocols s’integren amb els sistemes de transport intel·ligent, d’aquesta manera els sistemes pretenen reduir el nombre d’accidents i altres factors que afecten a l’hora de conduir. En quant a l’etapa d’experimentaci´o el proces es divideix com es diverses subetapes, la primera consta del disseny i desenvolupament dels protocols confiables i robustos. Una vegada superada aquesta etapa hi ha que llan¸car simulacions dels models de mobilitat per a obtindre els resultats, seguidament aquesta informaci´o es subministrada als simuladors de xarxes sense fils per a observar el que va passant, segons canvie la densitat dels nodes, com afecten les sobrecarregues a la xarxa i els temps d’entrega, a m´es a m´es de la taxa de paquets perduts. Aquesta etapa ofereix la possibilitat d’iterar sobre ella mateixa, de tal forma que segons es vagen obtenint els resultats es poden redefinir les especificacions a m´es, d’avaluar les propostes amb un gran nombre de dispositius sense fer despeses addicionals. En quan els resultats son els desitjats es passa a l’´ultima etapa del proces, qu`e consisteix en implementar el protocol en dispositius f´ısics. Aquest TFM cobreix les dos primeres etapes del proc´es mencionat, constituint una primera etapa necess`aria per al desenvolupament de futurs treballs que estiguen orientats en l´ınia de millorar els sistemes basats en protocols d’encaminament basats amb dispositius GPS aplicables tant a vehicles com a robots m`obils. A m´es a m´es. s’ha proposat un ecosistema complet per al disseny i avaluaci´o d’aquest tipus de protocols. En aquesta l´ınia, s’ha desenvolupat un model de protocol d’encaminament per a xarxes VANETs amb noves caracter´ıstiques, havent-se validat i realitzat ja les primeres implementacions i probes sobre dispositius reals que permetran l’aplicaci´o dels protocols proposats, amb resultats prou diferents. Abstract This master thesis presents a study of routing protocols for vehicular networks. These protocols are divided into two main groups: protocols based on routing and protocols based on geographical location. The first group is divided into two groups, proactive and reactive protocols. The difference between these two subtypes of protocols is that the necessary control information is obtained when needed in the reactive protocols while proactive protocols are constantly sending and requesting control information. The most representative reactive protocols are AODV and DSR, and the most representative proactive protocols are OLSR and DSDV. On the other hand, geolocation based protocols are characterized by the necessity of GPS devices to work properly. In recent years, protocols of this last type have been improved applying artificial intelligence techniques to optimize their functioning and increase their robustness and reliability. All these protocols are integrated with intelligent transport systems. In this way, the goal with these systems is to reduce the number of accidents among other factors that affect driving. Regarding the experimental phase, the process is divided into several sub-steps, the first involves the design and development of robust and reliable protocols. Once this step has been passed driving trends should be obtained with the mobility simulators in order to be provided to the network simulators to study and evaluate the behavior and performance. This stage allows iterate over it, so that according to the results you can refine the specification, also allows the evaluation of proposals with a large number of devices without additional costs. Finally, last step consists on the real implementation on physical devices. This TFM covers the first two described stages, being a necessary work that will allow the development of future lines dedicated to improve based on GPS routing protocols that can be applied to both vehicles and mobile robots. Additionally, a complete ecosystem for the design and evaluation of such protocols has been proposed in this thesis. In this line, a model for VANETs routing protocol with new characteristics has been developed and validated. After that, an exhaustive experimentation and evaluation using the proposed ecosystem has been conducted. Finally, early implementations and testing on real hardware that will allow the application of the proposed protocols also have already been carried out, with very interesting results. ´ Indice general Resumen II Resum IV Abstract VI Contenido VIII Lista de Figuras XI Lista de Tablas XIII 1. Introducci´on 1 1.1. Objetivos del Trabajo Final de M´aster .................... 2 1.2. Estructura del TFM .............................. 2 2. Estado del arte 5 2.1. Tecnolog´ıa inal´ambrica ............................. 5 2.2. T´ecnicas de IA para VANETs ......................... 7 2.3. Estudio protocolos ............................... 9 2.3.1. Clasificaci´on Protocolos ........................ 9 2.3.2. ERBA .................................. 10 2.3.3. Hybrid Location Ad-Hoc Routing (HLAR) ............. 13 2.3.4. Intelligent OLSR ............................ 15 2.3.5. Fast energy-aware OLSR ....................... 16 2.3.6. Junction-based Adaptive Reactive Routing (JARR) ........ 18 2.3.7. Reliable Geocast Routing Protocol ................. 20 2.3.8. Routing algorithm for Dense Traffic Density Vehicular Networks (BTDAR) ............................... 22 2.3.9. Intersection-Based Routing Protocol (IBR) ............. 23 2.3.10. Stability and Reliability aware Routing (SRR) ........... 24 3. Herramientas Empleadas 31 3.1. NS-3 ....................................... 31 3.1.1. Arquitectura del simulador ...................... 32 3.2. Simulator Urban MObility - SUMO ..................... 32 ix Chapter 1. Introducci´on 2 donde los veh´ıculos han de ser capaces de tomar decisiones en caso de que los humanos no hayan sido capaces de tomarlas. Figura 1.1: Aglomeraciones en las carreteras 1.1. Objetivos del Trabajo Final de M´aster Tras lo presentado anteriormente los objetivos de este trabajo consiste en: Aprendizaje de las herramientas empleadas para la simulaci´on de redes vehiculares. Investigar en protocolos de redes vehiculares y t´ecnicas de IA que sean aplicadas a veh´ıculos o robots m´oviles. De esta forma que puedan tomar decisiones coordinadas de forma distribuida a trav´es de la informaci´on suministrada por la WSN. Desarrollar un modelo de enrutamiento basado en redes vehiculares. Llevar a cabo la correspondiente experimentaci´on mediante campa˜nas de simulaci´on. Analizar los resultados obtenidos tras el desarrollo y validarlo. En primer lugar se realizar´a una evaluaci´on de las propuestas mediante simulaci´on y posteriormente sobre nodos reales que ser´an adecuados en funci´on de los resultados obtenidos en las campa˜nas de simulaci´on, estudi´andose finalmente su aplicaci´on en la transferencia de informaci´on entre los veh´ıculos ligeros y robots m´oviles. 1.2. Estructura del TFM Este trabajo se estructura de la siguiente forma: En el cap´ıtulo dos se realizar´a una descripci´on de una de las tecnolog´ıas que se emplea Chapter 1. Introducci´on 3 en los Sistemas de Transporte Inteligente (ITS), esta tecnolog´ıa es Wireless Access in Vehicular Environments (WAVE). Despu´es de exponer esta primera parte se proceder´a a explicar una serie de t´ecnicas de Inteligencia Artificial que se est´an aplicando en los ´ultimos a˜nos al an´alisis de protocolos de enrutamiento en las redes vehiculares. Ya con esto presentado, se centrar´a el inter´es en analizar diferentes tipos de protocolos para este tipo de redes. Seguidamente, en el cap´ıtulo tres se introducir´an las herramientas empleadas en este trabajo, para ello se realizar´a una breve descripci´on del simulador de redes basado en eventos discretos NS-3 y se describir´a brevemente su arquitectura. Tambi´en se detallar´a el simulador SUMO, que es un simulador para generar escenarios de movilidad y definir comportamientos de veh´ıculos. Se especificar´a el entorno donde se va a realizar la implementaci´on en equipos reales, esta herramienta es ROS y finalmente se introducir´a los dispositivos electr´onicos que se emplear´an, la tarjeta BeableBoneBlack y la cape ROBOCape. A continuaci´on en el cap´ıtulo cuatro, se expondr´a el trabajo realizado con las tres herramientas introducidas anteriormente y el ecosistema de simulaci´on que ha resultado con la incorporaci´on de un nuevo protocolo. En el cap´ıtulo cinco se presentar´a la experimentaci´on y an´alisis de los resultados obtenidos, comparando los resultados obtenidos con el protocolo propuesto. Adem´as, se describir´a la aplicaci´on realizada sobre la tarjeta BeableBoneBlack mostrando que puede ser aplicable a cualquier sistema robotizado m´ovil. Finalmente, en el cap´ıtulo seis, se expondr´an las conclusiones obtenidas de todo el trabajo, se enunciar´an las publicaciones y colaboraciones que se han realizado durante la elaboraci´on de este trabajo, y finalmente se expondr´a los futuros trabajos que dar´an lugar al desarrollo de la tesis doctoral. Cap´ıtulo 2 Estado del arte 2.1. Tecnolog´ıa inal´ambrica Hoy en d´ıa se conocen aplicaciones para Intelligent Transport Systems (ITS) [1]. Estos sistemas se dividen en dos grupos: Aplicaciones que aportan seguridad. Aplicaciones sin seguridad. La principal diferencia entre estos dos grupos es que la primera est´a orientada a que los veh´ıculos se comuniquen entre s´ı para as´ı poder intercambiarse mensajes frente a accidentes, atascos, estado de las carreteras, y el segundo est´a m´as orientado al ocio. Esto hace que se elaboren una serie protocolos enunciados en 2.3.1 que est´an basados en el est´andar 802.11. Dentro de este est´andar existen diversas variantes como es el caso de los est´andares mas com´unmente conocidos 802.11a/b/g, pero existe el est´andar 802.11p que incorpora la arquitectura necesaria para Wireless Access In Vehicular Environments (WAVE), que es para sistemas de comunicaciones vehiculares, este opera en la banda de 5.8-5.9 GHz con un ancho de banda de 75 MHz. Dentro de este modo de comunicaci´on inal´ambrica se encuentran las conexiones VehicularTo-Vehicular (V2V) [1,2] el cual permite realizar env´ıos de informaci´on entre distintos veh´ıculos y el otro tipo de conexiones es Vehicular-To-Infraestructure (V2I), que permite a los nodos comunicarse con infraestructuras que tienen una localizaci´on fija y est´an dotados de Gateways (GW) Figura 2.1. Los sistemas de comunicaciones V2V est´an libres de usar una infraestructura y tan solo se comunican con los nodos que est´an dentro de su alcance, para que esto se produzca 5 Chapter 2. Estado del arte 6 los veh´ıculos han de estar dotados de sistemas On Board Unit (OBUs), as´ı creando redes ad-hoc, esto permite que exista una alta movilidad din´amica en la red y por tanto requiere un descubrimiento, mantenimiento y recuperaci´on de la ruta. En cuanto a los sistemas de comunicaciones V2I involucran los sistemas OBUs y Roadside Unit (RSUs). Esto permite que las OBUs sean capaces de intercambiar mensajes con las RSUs y estas mediante Access Points (APs) sean capaces conectarse a internet a trav´es de Internet Gateways (IGWs), as´ı adquiriendo un direccionamiento IP global. Esto permite que la gesti´on de la movilidad est´e garantizada y los paquetes de los nodos sean alcanzables. En la Figura 2.2 se muestra el esquema de conexiones. Figura 2.1: Arquitectura Red Vehicular Figura 2.2: Comunicaciones V2V y V2I En este sistema de comunicaciones el direccionamiento IP emplea una topolog´ıa jer´arquica plana debido al r´apido cambio que se produce en la misma. Esta topolog´ıa ha de ser compatible con la existente en modo cableada. Por ello se emplean direcciones IPv6 autoconfigurables. Debido a la elevada movilidad de los nodos se producen fallos de conexi´on, por ello surge la necesidad de emplear mallas de redes inal´ambricas h´ıbridas. Este tipo de redes han de presentar una serie de caracter´ısticas, como por ejemplo; cada Chapter 2. Estado del arte 7 nodo ha de ser capaz de conectarse a internet; todos los nodos de estas redes han de tener un prefijo de red para conectarse a internet; han de tener soporte para diferentes gateways para as´ı moverse libremente; las conexiones en la capa de transporte han de estar constante abiertas. Y el intercambio de IP se puede dividir en tres fases [1]: Handover initiation: fase inicial reconoce la necesidad de la entrega debido a diversos factores. Handover decision: fase intermedia que permite o deniega la transmisi´on Handover execution: fase final que se da despu´es de que se cumplan las dos fases anteriores y permite la conmutaci´on real de una sesi´on activa de una estaci´on base o punto de acceso a otros. Adem´as existen diversos tipos de intercambios de IP: Horizontal: en el cual los puntos de acceso se empleas la misma tecnolog´ıa. Vertical: en el cual existen diferentes tecnolog´ıas para el acceso. 2.2. T´ecnicas de IA para VANETs En los ´ultimos a˜nos los grupos de investigaci´on en VANETs han visto la necesidad de aplicar nuevas t´ecnicas para el an´alisis de diversos par´ametros que conforman las configuraciones de los protocolos de encaminamiento que est´an desarrollando. Con tal de obtener las configuraciones ´optimas y autom´aticas de estos par´ametros se est´an empleando diversas t´ecnicas de inteligencia artificial. Los m´etodos que se est´an usando son Computaci´on Evolutiva (EC) [3,4], t´ecnicas de Fuzzy Logic [5] y redes neuronales. Seguidamente se realizar´a una breve descripci´on de los t´ecnicas enunciadas anteriormente. La EC es una rama de la Computaci´on y la Inteligencia Artificial que comprende m´etodos de b´usqueda y aprendizaje automatizado inspirados en los mecanismos de la evoluci´on natural. Se han propuesto diversos enfoques de la EC: Estrategias Evolutivas,Algoritmos Gen´eticos (GA),Programaci´on Gen´etica,Clasificadores Gen´eticos, Algoritmos Metaheur´ısticos yAlgoritmos Evolutivos Paralelos (PEA) entre otros. Esta serie de m´etodos se les denomina de manera colectiva como Algoritmos Evolutivos (EA) [6], entre los cuales los m´as conocidos son probablemente los GA. Estos algoritmos han sido aplicados exitosamente en la resoluci´on de problemas en distintas ramas de la ingenier´ıa, dise˜no, industria, econom´ıa y ciencias naturales. Debido Chapter 2. Estado del arte 8 a que EA emulan a la evoluci´on natural cabe destacar que comprenden una serie de caracter´ısticas: Una representaci´on o codificaci´on de las soluciones potenciales al problema bajo estudio. Una poblaci´on (conjunto de individuos) de estas soluciones potenciales. Mecanismos para generar nuevos individuos o soluciones potenciales al problema estudiado, a partir de los miembros de la poblaci´on actual (los denominados operadores de mutaci´on y recombinaci´on). Una funci´on de desempe˜no o evaluaci´on (del ingl´es fitness function) que determina la calidad de los individuos en la poblaci´on en su capacidad de resolver el problema bajo estudio. Un m´etodo de selecci´on que otorgue mayores oportunidades de sobrevivir a las buenas soluciones. En la Figura 2.3 se ilustra el esquema general de un algoritmo evolutivo. Figura 2.3: Esquema general EA Otra t´ecnica IA que est´an empleando los grupos de investigaci´on es la Fuzzy Logic. Este tipo de sistema toma un n´umero de entradas relativas a un estudio previo, y con las cuales se obtiene una salida. As´ı, adapt´andose lo mejor posible al mundo real. Estos sistemas tienen un funcionamiento basado en reglas de la forma SI (antecedentes) Entonces (Consecuente) donde su salida es tambi´en un conjunto difuso. Chapter 2. Estado del arte 9 2.3. Estudio protocolos 2.3.1. Clasificaci´on Protocolos Existen dos grandes grupos donde se pueden englobar los protocolos de encaminamiento para las redes inal´ambricas vehiculares [7]. Estos dos grupos son los basados en Enrutamiento por Direccionamiento yEnrutamiento Geogr´afico como se puede observar en la Figura 2.4. El primer grupo nombrado se divide en dos categor´ıas: proactivos y reactivos. El primero se caracteriza por mantener siempre actualizada la informaci´on de direccionamiento entre los nodos, aqu´ı podemos encontrar los protocolos OLSR y DSDV entre otros. Este tipo de protocolos presenta un problema que es la elevada sobrecarga que existe cuando la topolog´ıa de la red cambia y por tanto existe la probabilidad de que la entrega de paquetes no exista debido a la rotura de los enlaces. La segunda subclase se caracteriza por obtener la informaci´on de enrutamiento en el momento que se va a enviar un paquete y no antes de eso como ocurre en la primera subcategor´ıa presentada. Esto hace que exista una sobrecarga menor, pero por contra existe una elevada latencia durante la entrega de paquetes. Los protocolos t´ıpicos de estudio en este subgrupo son AODV y DRS. El segundo grupo basado en m´etodos de geolocalizaci´on parte de que el nodo o veh´ıculo conoce su ubicaci´on actual gracias a un dispositivo GPS y puede tomar decisiones para el reenv´ıo de paquetes de forma directa, gracias a que conoce la ubicaci´on de sus vecinos. A la hora describir este tipo de protocolos, se hace una diferencia entre dos tipos: los protocolos basados en Packet buffering based GPS yNon-Packet buffering based GPS. En el primer subconjunto introduce GeOpps, VADDS. En cuanto a los basados en Non-Packet buffering based GPS se realiza una subdivisi´on en dos subclases: Connectionless routing yConnection-oriented routing protocols. Dentro de esta primera subclase est´an los protocolos CBF, GDBF. La segunda subcategor´ıa se divide en dos tipos de de protocolos: Trajectories-based Geographical Routing Protocols ySource and Map based Routing. En el primer tipo se pueden agrupar los protocolos; Trayectory-Based Fordwarding (TBF) y Motion Vector Schema (MoVe). En el segundo grupo est´an los protocolos GPSR, GSR, GPCRGpsrJ+, CAR, SADV, A-STAR, VCLCR, LOUVRE, RBVT, GyTAR, TO-GO, y Fuzzy Logic-based Route Selection in VANET. Cogiendo lo mejor de estos dos tipos de protocolos, hay autores que han propuesto protocolos h´ıbridos como puede ser el protocolo Stability and Reliability aware Routing (SRR). Chapter 2. Estado del arte 10 Figura 2.4: Taxonom´ıa de los protocolos en redes VANETs El tipo de conexiones presentado en 2.1 conlleva una serie de problemas cuando existe una elevada movilidad de los veh´ıculos, puntos de acceso est´aticos, retardos en el env´ıo de paquetes, links que pueden fallar. De ah´ı que surjan protocolos de movilidad de redes como por ejemplo NEMO BS [1] y los analizados a lo largo de esta secci´on.NEMO Basic Support es un protocolo definido en (RFC 3963) que es capaz de gestionar la movilidad de una red entera basada en IPv6. Es capaz de asegurar la continuidad de una sesi´on para todos los nodos m´oviles que existen en la red, y la actualizaci´on del punto de acceso a internet. De esta forma garantiza la conectividad y accesibilidad de la red m´ovil conforme esta va evolucionando. 2.3.2. ERBA En este apartado se presenta el protocolo de enrutamiento ERBA [8], el cual surge del proyecto Shangai Grid. Sus fuerte es que es eficiente con el consumo energ´etico y emplea las tendencias de movimiento de los veh´ıculos. La principal caracter´ıstica de este proyecto es adquirir las tendencias de una diferente variedad de conductores, y monitorizar el transporte p´ublico. Este protocolo es capaz de distinguir entre los conductores de autobuses y veh´ıculos privados. Esta distinci´on se realiza porque los conductores de autobuses siempre realizan la misma ruta, por ejemplo, el autob´us inicia su recorrido desde la estaci´on y su recorrido siempre acaba en el mismo lugar. Por otro lado, la ruta de los conductores privados es aleatoria. Chapter 2. Estado del arte 11 ERBA est´a probado solamente en entornos urbanos, y cada veh´ıculo esta equipado con distintos dispositivos, GPS, senores, etc. y emplea la notaci´on mostrada en la tabla 2.1 para su funcionamiento. Notations Explication SV the source vehicle DV the destination vehicle CD the current direction ND the next direction VI the distance between the vehicle location to the intersection VT the vehicle type REQ the route request REP the route replay ERR the route error message TTL the time-to-live of a REQ LRS the link reliable significance Cuadro 2.1: Esquema protocolo ERBA Este protocolo emplea t´ecnicas de tablas de enrutamiento para localizar las rutas y autorizar a los veh´ıculos y los nodos a intercambiar mensajes a trav´es de los vecinos hac´ıa los nodos que se alcanzan de forma directa intentando buscar la mejor ruta entre los veh´ıculos. El intercambio de paquetes se realiza de la siguiente forma: En primer lugar, el veh´ıculo origen (SD) env´ıa un mensaje al veh´ıculo destino (DV) y DV devuelve un mensaje. Si DV es un nodo vecino es que existe una comunicaci´on y SV realiza una inundaci´on de mensajes de petici´on (REQ). Cuando realiza esta inundaci´on, los nodos cercanos actualizan su tabla de vecinos. El mensaje REQ est´a compuesto de varios campos (bits): nodo de origen, nodo destino, TTL, y secuencia de n´umeros de ID, CD, ND, VI, VT y LRS. El ´ultimo campo sirve como marca de tiempo, por lo que, los nodos pueden mantener actualizada su informaci´on con los otros nodos. Cuando un nodo env´ıa un mensaje, este aumenta su n´umero de secuencia. En segundo lugar, cuando un nodo recibe un mensaje REQ pueden ocurrir dos cosas: 1. El nodo es el destino o conoce el nodo destino, en el primer caso casi envia un mensaje REP al nodo fuente, en otro caso estima el LRS y env´ıa el mensaje REP. 2. El nodo realiza inundaciones con mensajes REQ. En tercer lugar, el mensaje REP se env´ıa a lo largo de los veh´ıculos que son almacenados en el paquete REQ. As´ı, la trayectoria de la ruta m´as fiable est´a configurada. Finalmente, con el fin de mejorar la estabilidad de ruta, incorpora un mecanismo preventivo para descubrir nuevas rutas antes de ser vencido en los enlaces de la ruta. Chapter 2. Estado del arte 18 superior funcionando como Multipoing Relays (MPR). Pero esta configuraci´on presenta una desventaja: los tiempos de validaci´on son muy altos, por tanto tarda m´as en detectar que un link ha fallado. Aplicando algoritmos paralelos se consigue una mayor eficiencia y velocidad respecto al algoritmo secuencial, por este motivo se aplica esta t´ecnica a los experimentos anteriormente realizados, obteniendo unos valores eficiencia superiores. Como los resultados obtenidos hay que validarlos, esta se realizar´a analizando la energ´ıa, principalmente: energ´ıa de transmisi´on y recepci´on, energ´ıa total y energ´ıa total por veh´ıculo. As´ı, reduciendo significativamente el consumo respecto a la configuraci´on con los par´ametros est´andar de OLSR. Adem´as, se analiza la QoS, centr´andose en el tiempo de envi´o, la sobrecarga de la red y el n´umero de saltos hasta llegar al destino. Obteni´endose una considerable reducci´on en la entrega de paquetes y sobrecarga en la red respecto a la configuraci´on est´andar de OLSR. No se ha tenido en cuenta el uso de un dispositivo de geolocalizaci´on a la hora de enviar los paquetes a los nodos vecinos. 2.3.6. Junction-based Adaptive Reactive Routing (JARR) Se presenta el protocolo Junction-based Adaptive Reactive Routing (JARR) [16]. Este es un protocolo de enrutamiento reactivo adaptativo multisalto, que tiene en cuenta la direcci´on y la velocidad a la que viajan los nodos, adem´as de conocer en qu´e condiciones se encuentra la red. Esta ´ultima caracter´ıstica es una ventaja frente a otros protocolos de enrutamiento, como por ejemplo GPSR. El protocolo no requiere de una infraestructura externa y por tanto soporta una alta escalabilidad en entornos de VANETs. En la implementaci´on del protocolo, el paquete que sirve para establecer el enrutamiento lleva implementados diversos modos, as´ı de esta forma puede adaptarse en redes dispersas y redes con alta densidad de nodos. Obtiene el camino m´as corto para as´ı comparar con otros caminos y obtener la ruta m´as optima. Los veh´ıculos tienen un alcance de unos 250 metros usando dispositivos wireless. En comparaci´on con otros protocolos [17,18], este modifica estrategias de transporte y reenv´ıo para reducir los intervalos. Adem´as de implementar un mecanismo adaptativo de beacons para ofrecer altos ratios en redes dispersas. JARR funciona de la siguiente forma: el paquete se enruta desde un cruce, y se va retransmitiendo hasta llegar a otro cruce, en ese momento se toman las decisiones oportunas para obtener el camino ´optimo a la ruta que seguir´a el nodo. A la hora de calcular la ruta ´optima se tiene en cuenta a la velocidad y la ruta que siguen los veh´ıculos y su posici´on actual. De esta forma se obtiene los pesos para calcular dicha ruta. Chapter 2. Estado del arte 19 La forma obtener la ruta ´optima se realiza empleando grafos dirigidos, donde los v´ertices indican el n´umero de cruces que hay en conectados en la carretera y las aristas representan el n´umero el n´umero de direcciones de las carreteras conectadas a los cruces. El peso de las aristas indica la distancia entre dos cruce y adem´as puede indicar el posible retardo que haya entre dos cruces pr´oximos. La forma de obtener la ruta ´optima es mediante el algoritmo de Dijkstra. En [16] se ha definido la siguiente funci´on para determinar la proximidad de un nodo a un cruce Figura 2.6: Figura 2.6: Funci´on proximidad en cruce Gracias a la informaci´on ofrecida por el mecanismo de los beacons el protocolo JARR es un protocolo adaptativo. Ya que se puede conocer la posici´on, velocidad, direcci´on de trayecto de los nodos vecinos que se encuentran dentro del rango de transmisi´on. Para conocer la densidad en la red se realiza una estimaci´on mediante el radio de beacons y a la velocidad a la que viajan los nodos, ver tabla 2.2. Velocity of Node (m/s) Beaconing (s) Estimated Density of Path Slow (0 - 13) Slow Dense Slow Average Average Slow Fast Sparse Average (¿13 - ¡20) Slow Average Average Average Average Average Fast Sparse Fast ( 20 -25) Slow Average Fast Average Average Fast Fast Sparse Cuadro 2.2: Tabla estimada de densidad En carreteras donde existan carriles con las dos direcciones el veh´ıculo que retransmite el paquete lo enviar´a a los veh´ıculos que vayan en su misma direcci´on Figura 2.7. En la selecci´on del modo de enrutamiento, inicialmente un nodo selecciona como ruta m´as ´optima el camino a la primera intersecci´on con la que se encuentra. A continuaci´on debe de seleccionar mediante el algoritmo una ruta adecuada para retransmitir los datos. El camino se selecciona mediante la informaci´on estimada de la densidad. En caso de Chapter 2. Estado del arte 20 Figura 2.7: Ejemplo de env´ıo de paquetes en la ruta que no existan nodos en una ruta determinada esta tendr´a prioridad baja, pero al mismo tiempo que se va descubriendo los cruces ser´an considerados en el algoritmo. En las simulaciones realizadas y compar´andose con el protocolo GPSR, conforme aumenta el n´umero de conexiones el protocolo JARR obtiene mejores resultados que GPSR, este ´ultimo los resultados obtenidos para el PDR desciende casi a la mitad, mientras que JARR obtiene valores pr´oximos a 0.8. Evaluando la m´etrica de la sobrecarga de paquetes, mientras el n´umero de nodos es muy disperso el n´umero de beacons generados por GPSR es muy inferior a JARR, pero en cuanto el n´umero de nodos va aumentado, y por tanto la densidad, la sobrecarga de JARR es mucho inferior a GPSR. La cobertura de alcance que ofrece este protocolo para los nodos es reducido, aproximadamente de unos 250 metros. Por otro lado no se tiene en cuenta el consumo energ´etico que se produce en los env´ıos de los paquetes. 2.3.7. Reliable Geocast Routing Protocol Debido a la limitaci´ones ofrecidas por el protocolo de enrutamiento AODV, se proponen dos mecanismos [19] como: eficiencia en la transmisi´on de datos al destinatario y usar la inundaci´on dentro del per´ımetro. Para ello se realizan una serie de suposiciones para la mejora del protocolo AODV. Estas suposiciones son: Todos los veh´ıculos est´an dotados de GPS, y por tanto conocen su posici´on. Adem´as se realiza un broadcast a todos los vecinos; Se asume que los bloques de datos se generan para codificar los paquetes que son lo suficientemente grandes para identificar y codificar paquetes despreciables; Existe como m´ınimo un veh´ıculo dentro del rango de recepci´on; Cuando se realiza un broadcast en una regi´on si un coche lo recibe, todos los coches pueden recibir ese mensaje; El est´andar Dedicated Short Range Communication (DSRC) se utiliza para establecer el rango de transmisi´on de veh´ıculos; Todos los nodos se mueven a velocidad constante. Cuando el reenv´ıan mensajes, el origen realiza un broadcast usando el protocolo AODV, y cuando llega al destinatario correcto, este contesta al mensaje con un mensaje unicast informando al origen de cu´al es su ruta. Asumiendo que los nodos conocen su ubicaci´on Chapter 2. Estado del arte 21 la zona de destino se conoce como Zone of Relevance (ZoR) y se asume que es una zona rectangular donde las esquinas que forman los cruces est´an definidas por coordenadas. El mensaje de cabecera incluye el ID la zona de destino. En cuanto a la regi´on de reenv´ıo se le llama Zone of Forwarding (ZoF) y se usa para el reenv´ıo de paquetes. Cuando existe una tasa baja en la entrega de mensajes y un pobre QoS se emplea un generador de n´umeros aleatorios para seleccionar un subconjunto de bloques y se “guardan” juntos para generar un paquete. Este proceso se repite para generar un n´umero K de bloques que ser´an recuperados por el destinatario. En la propuesta realizada para la mejora de AODV el nodo origen env´ıa paquetes codificados de baja tasa de codificaci´on hasta que el destino le env´ıa un mensaje de ACK, esto indica que el n´umero de paquetes recibidos es suficiente. Una vez el origen recibe este mensaje es capaz de enviar nuevos paquetes de datos. El mecanismo de recuperaci´on r´apida ante fallos consiste en que el nodo origen recibe paquetes desde el destino hasta que recibe un paquete de error. Entonces con la informaci´on recibida en este paquete se crea una nueva ruta mediante el proceso de descubrimiento. En las suposiciones realizadas anteriormente el nodo origen solo acepta el primer mensaje recibido y transmite por la ruta creada los datos. Con tal de reducir la perdida de paquetes y QoS se permite la aceptaci´on de mensajes desde diversas rutas. De esta forma tambi´en se reduce el retardo de los mensajes hacia el destino y los mensajes de error no se mantienen para conocer la ruta. Para realizar las simulaciones en el entorno propuesto se emplean cuatro m´etricas para obtener los resultados, estas son, n´umero de paquetes recibidos en la ZoR, la media de retardo de los mensajes, n´umero de paquetes perdidos y la sobrecarga. Los valores obtenidos se compraran con el protocolo IVG. En las simulaciones se observa que con las dos mejoras propuestas al existir diversas rutas para recibir mensajes se reduce el tiempo de retardo en comparaci´on con una ´unica ruta. Tambi´en se reduce la sobrecarga en la ruta, esto implica que la tasa de recuperaci´on ante fallos sea menor. Los m´etodos propuestos con enrutamiento unicast han reducido la sobrecarga de la red en comparaci´on con IVG y con la l´ınea-base definidas. En cuanto al n´umero de paquetes perdidos por la propuesta es casi despreciable por parte del IVG tiene un gran n´umero de paquetes perdidos. E retardo por los m´etodos propuestos es menor y por tanto en un instante de tiempo habr´a m´as paquetes recibidos. Chapter 2. Estado del arte 22 2.3.8. Routing algorithm for Dense Traffic Density Vehicular Networks (BTDAR) (BTDAR) [2] es un protocolo que tiene como objetivo, entregar paquetes de forma fiable y eficiente en entornos con poca y mucha densidad de veh´ıculos. En el modelo intervehicular definido se obtiene el espacio medio que hay entre dos veh´ıculos. Adem´as de la velocidad entre dos veh´ıculos, se definen una serie de ecuaciones para el c´alculo de estas m´etricas y as´ı que los veh´ıculos sean capaces de transmitirse los datos e incluso encolar los datos recibidos en un buffer. Se definen dos tipos de protocolos para la densidad y la escasez de nodos, en los cuales se tiene en cuenta la velocidad relativa, tiempo de vida de las comunicaciones y la probabilidad de espera ante un exceso de tiempo de espera en una cola. Se presenta el protocolo BTDAR-R: Routing algorithm for Dense Traffic Density Vehicular Networks el cual se emplea cuando exista tr´afico denso en los entornos. Este protocolo es capaz de mantener la calidad del servicio en la entrega de paquetes en la ruta ´optima seleccionada. Adem´as, es capaz de mantener reenv´ıos con multisalto. Los nodos candidatos son capaces de reenviar la posici´on de los nodos buscando la ruta ´optima, esta ruta se obtiene buscando el camino con menor tiempo de entrega entre dos nodos satisfaciendo la estabilidad y la calidad del servicio. Se presenta tambi´en el protocolo BTDAR-P: Routing algorithm for Sparse Traffic Density Vehicular Networks este se emplear´a cuando la densidad de tr´afico sea escasa. La conectividad se ver´a afectada por intermitencia provocada por la escasez de veh´ıculos. El protocolo est´a dotado de un buffer que ser´a capaz de reenviar y recibir datos cuando exista conectividad con alg´un nodo vecino. BTDAR se compara con otros protocolos basados en enrutamiento por geolocalizaci´on: GPSI, IBR, JARR. Simulaciones realizadas sobre la densidad de nodos existentes en un entorno muestran que conforme aumenta la densidad, todos tienden a decrementar el tiempo de entrega de los paquetes (PDD), esto se debe a que los protocolos r´apidamente obtienen la mejor ruta para retransmitir. Cabe notar que BTDAR-R tiene los mejores resultados conforme aumenta el n´umero de nodos. En cambio BTDAR-P cuando existen pocos nodos obtienen los mejores resultados. En cuanto a las simulaciones realizadas sobre el tiempo de entrega de los paquetes conforme aumenta la velocidad, se obtiene que todos los protocolos comparados tienden a incrementar el tiempo de retardo, esto es debido a los patrones de movilidad que se han considerado. Se puede observar que en BTDAR-R los tiempos de entrega son inferiores al resto de protocolos presentados. En cuanto al PDR analizado, BTDAR-P y BTDAR-R tienen una tasa muy elevada de paquetes entregados sobre el resto de protocolos analizados. En cuanto a la densidad de nodos es muy escasa BTDAR-P tiene los mejores resultados, seguidos de BTDAR-R, pero en cuanto la densidad aumenta el n´umero de nodos recibidos por BTDAR-R va Chapter 2. Estado del arte 23 aumentado, y BTDAR-P decrementa ligeramente el rendimiento. En cuanto a la simulaci´on realizada para obtener el PDR seg´un los patrones de movilidad establecidos, se obtiene como resultados que BTDAR-R y BTDAR-P tienen un alto porcentaje de entregas en comparaci´on con el resto, aun aumentando la velocidad de los nodos. En cuanto al control de Bytes transmitidos por Bytes de datos entregados, seg´un los resultados obtenidos para la densidad de nodos el protocolo JARR se mantiene constate porque en su definici´on no tiene un modo predictivo. En cuanto a GPSI tiene un aumento considerable en la sobrecarga de control, esto es debido al constante cambio de un modo ”´avido.a un modo predictivo. En cuanto a BTAR conforme aumenta la densidad va mostrando una sobrecarga en la red, pero aun as´ı es mucho menor que al resto de protocolos, por tanto los resultados son mejores. En los test realizados sobre el aumento de la velocidad BTDAR contin´ua teniendo los mejores resultados respecto a los otros protocolos. Finalmente los an´alisis realizados sobre el n´umero de paquetes transmitidos por paquete entregado BTDAR tiene una mejor eficiencia de acceso al canal que el resto de propuestas, esto se debe a que BTDAR entrega los datos a trav´es de rutas estables. 2.3.9. Intersection-Based Routing Protocol (IBR) Se presenta el protocolo IBR [20], el cual est´a basado en la estrategia de transporte y reenv´ıo. Una de sus caracter´ısticas es evitar que el paquete llegue a los coches que van en direcci´on opuesta al veh´ıculo origen. IBR se asume que los coches est´an dotados de un GPS. Cada veh´ıculo ha de mantener su segmento de carretera en la tabla, este segmento incluye la siguiente informaci´on: ID del segmento; n´umero de veh´ıculos en el segmento de carretera; y ultima actualizaci´on de la tabla. IBR sigue los principios b´asicos implicados en el modelo de carretera, adem´as de a˜nadir informaci´on de los cruces y carretera recta. Adopta el m´etodo .avido.en las carreteras rectas. Cuando llega a una intersecci´on la transmisi´on depender´a de la direcci´on de enrutamiento del paquete y direcci´on en que vayan los veh´ıculos incluidos el siguiente reenv´ıo y ”libertador”. Cuando se reenv´ıa el paquete al coche que va en la misma direcci´on el tiempo de vida del paquete se decrementa. Si hay una alta densidad de nodos la tasa de paquetes perdidos y el retardo en la entrega aumenta. Ya que el protocolo solo transmite en la direcci´on en la cual va el veh´ıculo, se establecen cuatro condiciones de encaminamiento. Estas son: Chapter 2. Estado del arte 24 1. Hay al menos un veh´ıculo en el siguiente segmento de carretera del paquete. Es decir, cuando un veh´ıculo se aproxima a una intersecci´on, este intercambia su segmento de carretera con los veh´ıculos que est´en cerca. 2. No hay vecinos en la intersecci´on. Cuando esta condici´on ocurre, el veh´ıculo que ha pasado por la intersecci´on lleva los paquetes hasta que encuentra un veh´ıculo con el que intercambiarlos, y as´ı poder replanificar la ruta. 3. La direcci´on de movimiento de un veh´ıculo es diferente a la direcci´on de transferencia del paquete, pero no hay veh´ıculos en el siguiente segmento de carretera, pero s´ı que hay vecinos en la intersecci´on. Cuando ocurre esta condici´on es porque no se encuentran nodos que vayan en la misma direcci´on que el paquete, y el veh´ıculo bloquea el paquete hasta que encuentra un veh´ıculo que va e la misma direcci´on y a este se le asigna la mejor ruta. 4. Los paquetes llegan tarde a la intersecci´on. Cuando esta condici´on sucede un paquete se reenv´ıa al siguiente segmento de carretera y al segmento de carretera por el cual va. Por tanto se realiza un duplicado de paquetes. 2.3.10. Stability and Reliability aware Routing (SRR) Se describe un nuevo protocolo de enrutamiento basado por geolocalizaci´on, adem´as incluye en su implementaci´on algoritmos de l´ogica difusa. Este protocolo se llama Stability and Reliability aware Routing (SRR) [5]. Debido a la incorporaci´on de un sistema basado en Fuzzy Logic este protocolo es capaz de tomar decisiones m´as r´apidamente que el resto de protocolos, estas decisiones se toman a partir de la distancia y la direcci´on de los veh´ıculos, para as´ı crear un paquete que ser´a retransmitido a los nodos que est´an dentro del radio de cobertura del nodo origen. Por otra parte lleva un mecanismo de decisi´on local para el caso que la red sea dispersa y no se pueda conectar a ning´un nodo vecino, de esta forma el protocolo puede cambiar de modo SRR a modo de encolado y al rev´es. En este ´ultimo modo enunciado se utiliza el mecanismo de carry-and-fordward para el caso en que el nodo no est´e conectado a ninguna red, y se usara como m´etrica de entrada la densidad de tr´afico. SRR est´a adoptado para sistemas de comunicaci´on basados en V2V. La informaci´on se transmite desde un veh´ıculo origen a otro destino mediante multi-hop. El veh´ıculo al llevar un GPS incorporado da la posibilidad de proporcionar su posici´on al resto de veh´ıculos que est´an dentro de la zona de alcance. Un veh´ıculo puede conocer la direcci´on y la ubicaci´on de los veh´ıculos vecinos. Esto se puede conocer ya que el nodo constantemente est´a haciendo boradcasting con mensajes HELLO. Esto facilita la zona de conocimiento de un veh´ıculo. Chapter 2. Estado del arte 25 El protocolo tiene dos modos de funcionamiento Figura 2.10: 1. Packet Routing in Connected Vehicular Sceneario Figura 2.8. En este modo el veh´ıculo origen est´a dentro de un convoy de coches y desea enviar datos a un destinatario. El origen consulta su tabla de vecinos y selecciona el veh´ıculo que mejor ruta presente hacia el destino. Esta ruta se obtiene mediante t´ecnicas Fuzzy. Y entonces env´ıa el dato a ese veh´ıculo. Y este proceso se realiza hasta llegar al veh´ıculo destino. Figura 2.8: Nodo emisor env´ıa un paquete seleccionado la ruta m´as ´optima 2. Tackling Packet Loss in Dis-connected Vehicular Sceneario Figura 2.9. Cuando el veh´ıculo entra en este modo es debido a que no hay ning´un veh´ıculo vecino cerca. Entonces empieza a guardarse en una cache la informaci´on que enviara a un veh´ıculo. En el momento que este veh´ıculo es alcanzado por un convoy de coches este cambiara de modo y se conectara y seleccionara la mejor ruta para enviar el paquete al destino. Figura 2.9: Cambio de modo desconectividad a conectividad Las m´etricas que se emplean en este protocolo ya se han nombrado anteriormente. Pero faltaba comentar porque se seleccionan la distancia y la direcci´on: La primera de ellas, se conoce aplicando el teorema de Pit´agoras, para conocer la distancia que hay entre dos nodos. Una vez conocida la distancia de los nodos vecinos con el origen se decide que los paquetes se han de enviar a los veh´ıculos que est´en a una distancia media. De esta forma se evita el fallo de transmisi´on con los nodos que est´a en el l´ımite del rango de alcance, y en el caso de los nodos m´as cercanos se evita la sobrecarga de paquetes. En cuanto a la direcci´on, los veh´ıculos solo se pueden mover en dos direcciones por limitaciones de Chapter 2. Estado del arte 26 Figura 2.10: Diagrama flujo protocolo SRR Chapter 2. Estado del arte 27 las carreteras. Pero las carreteras no son rectas, ya que tienen curvaturas, por tanto los vectores de direcci´on de los veh´ıculos no son siempre paralelos unos a otros y se necesita conocer siempre que ´angulo existe entre un nodo y otro de la misma direcci´on. Para seleccionar las entradas y salidas para la fuzzificaci´on se han declarado unas funciones llamadas, Less Directed, Mid Directed and More Directed. Estas funciones se emplear´an dependiendo del ´angulo de direcci´on que exista entre el nodo origen y el nodo vecino. El valor de este ´angulo estar´a comprendido en [-1,1] ya que el coseno oscila entre estos valores. En cuanto a la distancia entre un nodo y otro depende del radio de cobertura y se crean tres funciones: Far, Intermediate, Close. Tras esto, surge la necesidad de normalizar los valores. Esta normalizaci´on resulta de dividir la distancia con el radio de alcance, de forma como se ilustra en [5]. Con eso se obtiene las reglas para la estructura de la l´ogica difusa del protocolo 2.3: IF THEN Rule RDistance Degree.Directness Fuzzy-Cost 1 Far Less Directed Low 2 Far Mid Directed Medium 3 Far More Directed High 4 Intermediate Less Directed Medium 5 Intermediate Mid Directed High 6 Intermediate More Directed V. High 7 Close Less Directed V. Low 8 Close Mid Directed Low 9 Close More Directed Medium Cuadro 2.3: Reglas Fuzzy logic En cuanto a las simulaciones realizadas, se ha usado el simulador JiST/SWANS [21]. Dentro del simulador se integr´o la implementaci´on del sistema de inferencia de l´ogica fuzzy. Y se han realizado diversas pruebas para finalmente compararse con el protocolo GPCR. En los primeros resultados analizados se estudia el impacto del “solapamiento” del canal. En la cual se demuestra el efecto sobre la variaci´on del link de error sobre canales inal´ambricos y trafico CBR comparado con el PDR, retardo medio de paquete y sobrecarga de paquetes. Conforme la velocidad de transferencia entre nodos ha ido aumentando hasta 72 Kbps, el valor del PDR ha ido descendiendo tal como se muestran en las gr´aficas. En cuanto a la media del retardo de entrega de los paquetes seg´un se ha incrementado la velocidad de transferencia el retardo medio ha ido increment´andose, y lo mismo ha ocurrido con el control de sobrecarga de los paquetes. En esta simulaci´on se ha comparado con diversos valores del canal de perdida inal´ambrica entre veh´ıculos. En cuanto a la simulaci´on realizada con el impacto de la densidad del tr´afico de los veh´ıculos. Tambi´en se demuestra el efecto sobre la variaci´on del link de error sobre Chapter 3. Herramientas Empleadas 34 Aunque en su nombre aparezcan las palabras “Sistema Operativo” no es tal cual un OS. Ya que funciona sobre un sistema Linux. Es m´as bien una infraestructura de desarrollo, despliegue y ejecuci´on de sistemas robotizados. En el cual existe una gran variedad de paquetes con software para que se pueda realizar un r´apido desarrollo sobre un robot, adem´as de solventar muchos problemas, que otros Frameworks de Desarrollo de Robots, RSF, no solventan. Las soluciones que solventa son las que se detallan a continuaci´on: Abstracci´on de Hardware (HAL) y reutilizaci´on e integraci´on de robots y dispositivos encapsulando estos tras interfaces estables y manteniendo las diferencias en archivos de configuraci´on. Algoritmos de rob´otica con bajo acoplamiento. Es decir, desde algoritmos de bajo nivel de control, cinem´atica, SLAM, etc. Hasta algoritmos de alto nivel como puedan ser los de planificaci´on o aprendizaje. Adem´as de otros tantos m´as espec´ıficos como puede ser que los robots se conecten a una red el´ectrica cuando lo necesiten o incluso coger y dejar objetos. Est´a provisto de un mecanismo de comunicaciones (middleware) distribuido entre los nodos del sistema robotizado. Un nodo es cualquier pieza de software del sistema (desde un algoritmo SLAM hasta un driver para el manejo de un motor). El objetivo de este sistema es doble: Encapsulado/abstracci´on/reutilizaci´on de software; Ubicuidad, es decir, independencia de donde este nodo est´a localizado (un sistema robotizado puede tener muchos procesadores). Estos nodos se comunican entre ellos mediante mecanismos de paso de mensajes RPC o Publish/Subscribe, Service Lookup, etc. Permite crear arquitecturas P2P de componentes robotizados distribuidos. Permite realizar simulaciones de sistemas rob´oticos con din´amicas de s´olidos r´ıgidos. Herramientas de desarrollo, despliegue y monitorizaci´on de sistemas rob´oticos. La diferencia existente entre ROS y otros RSF es que ha logrado agrupar muchas de las mejores caracter´ısticas de otros proyectos, como pueda ser Player/Stage/Gazebo, Yarp, Orocos, Carmen, Orca, OpenRave, Open-RTM, as´ı dando una soluci´on integral y muy uniforme al problema de desarrollo de sistemas rob´oticos. Adem´as de ser un sistema multilenguaje, peer2peer, orientado a herramientas, ligero y OpenSource. Desde que surgi´o hasta la fecha su popularidad ha ido en aumento y esto ha sido debido a que se est´a empleando en diferentes ´ambitos profesionales: Cient´ıfico, Investigaci´on, Divulgaci´on. Chapter 3. Herramientas Empleadas 35 3.4. BeagleBone Black La tarjeta BeagleBoard [25] es producida por la empresa Texas Instruments en asociaci´on con Digi-Key y Newark element14. Surge a mediados de 2008 como el primer micro ordenador de bajo coste del mercado. Desde su aparici´on ha ido evolucionando mediante modelos nuevos que incorporan ciertas mejoras en rendimiento y conectividad. Hoy en d´ıa el modelo m´as reciente es el BeagleBone Black rev c, cuya revisi´on consta de mayo de 2014. Este modelo ofrece un rendimiento y una capacidad de c´omputo que pocas tarjetas de precios similares son capaces de superar. La BeagleBone Black tiene un precio de menos de 50e, y posee un procesador ARM Cortex-A8 a 1000MHz que permite realizar 2000 MIPS, una GPU PowerVR SGX530 a 200MHz que es capaz de procesar 20MPoligonos/s, viene con 512MB de RAM de tipo DDR3 a 800Mhz, una conexi´on Ethernet, salida de v´ıdeo y audio micro-HDMI, un puerto USB, una ranura para tarjeta microSD y dos filas de 46 pines de entrada o salida y dos n´ucleos programables de tiempo real. Hay que tener en cuenta que el voltaje de entrada de la tarjeta es de 5V y que sin conectar nada, la tarjeta sola consume entre 210 y 460mA. Otra de las ventajas m´as destacables de la BeagleBone Black es la conectividad que ofrece. Dispone de un total de 92 pines reconfigurables que incluyen hasta cuatro puertos serie diferentes, la generaci´on de ocho PWM independientes, cuatro temporizadores, un bus CAN, siete entradas anal´ogicas en base a 1.8V con una resoluci´on del conversor AD de 12 bits, varias salidas de alimentaci´on a 5 y 3.3V, dos conexiones SPI, dos puertos I2C para su interconexi´on con cualquier tipo de hardware compatible, adem´as de 65 entradas y salidas digitales reconfigurables. Las extensiones para las tarjetas Beagleboard se denominan capes y hay m´as de 40 modelos diferentes. Del mismo modo que con el resto de tarjetas, su funcionalidad es otorgar mayor facilidad de interconexi´on y/o dotar de nuevas caracter´ısticas a la tarjeta. La BeagleBone Black soporta diversos sistemas operativos basados en la arquitectura ARM Linux como Fedora, Ubuntu u openSUSE, pero tambi´en tiene soporte para Android e incluso para Windows Embedded. Estos sistemas se ejecutan desde la microSD aunque cabe mencionar que la tarjeta dispone de un kernel de auto arranque con Linux Debian en su memoria eMMC de 2GB que se ejecuta cuando no se inserta ninguna microSD. Las opciones de programaci´on en la BeagleBoard son pr´acticamente las mismas que las de un sistema operativo basado en una arquitectura x86. Se pueden utilizar lenguajes como C, C++, Java, Python, JavaScript, Android e incluso tambi´en Matlab-Simulink. Chapter 3. Herramientas Empleadas 36 Empleando la distribuci´on de Linux Ubuntu, se permite la instalaci´on y uso del framework Robot Operating System (ROS) y permite un funcionamiento id´entico a como si se estuviese trabajando con una arquitectura x86. Figura 3.2: Beaglebone Black 3.5. ROBOCape Como se ha mencionado en la secci´on anterior, las extensiones para la tarjeta BeagleBone, se llaman capes. En este apartado se va a dar a conocer la cape ROBOCape [26], la cual ha sido dise˜na por Miguel Albero del servicio de electr´onica del Instituto Universitario de Autom´atica e Inform´atica Industrial. ROBOCape es una placa electr´onica que ha sido dise˜nada exclusivamente para usarla con la tarjeta BeagleBone Black. As´ı se permite un amplio abanico para a˜nadirlo al conjunto a sistemas robotizados y poder hacer mas f´acil la programaci´on de estos sistemas. Durante el dise˜no de esta tarjeta se ha realizado un an´alisis exhaustivo sobre que dispositivos se usan m´as a menudo en este tipo de sistemas. Y gracias a esto permite un amplio abanico de aplicaciones de control para la gran mayor´ıa de robots existentes. Para que esta placa pueda funcionar con la BeagleBone, esta debe estar alimentada con alimentaci´on externa de 5V y 1A o m´as para que el sistema de seguridad no apague la tarjeta. Adem´as incorpora una entrada para conectar una bater´ıa externa de entre 6 y 12V de dos celdas. Las caracter´ısticas t´ecnicas que ofrece son las siguientes. Sistema de alimentaci´on DC/DC independiente, es decir, la tensi´on de entrada tiene que ser tensi´on continua y como m´ınimo de 1A. La entrada m´axima permitida Chapter 3. Herramientas Empleadas 37 Figura 3.3: ROBOCape es de 12V y capaz de ofrecer hasta 3A. Incorpora un sistema para proteger al sistema de cambio de polaridad y protecci´on para evitar sobre-tensiones. El sistema de carga de bater´ıas es para las bater´ıas lipo de 2 c´elulas de 7.4V, adem´as incorpora un jumper para seleccionar el modo de funcionamiento, si carga solo o carga y funciona con alimentaci´on externa. El aceler´ometro que incluye es el MPU-9150. Este, incluye un gir´oscopo que es capaz de devolver la velocidad angular en las coordenadas X, Y, Z con un rango escalable de entre ±250◦a±2000◦/sec. El aceler´ometro es capaz de devolver aceleraciones de entre ±2G hasta ±16G en los 3 ejes, X, Y, Z. Adem´as incluye un magnet´ometro, que obtiene el campo magn´etico en los 3 ejes, gracias a un sensor monol´ıtico de efecto Hall. Este es capaz de devolver una salida con 13 bits de resoluci´on, es decir 0.3T por LSB. El cual est´a conectado al bus I2C. Otro de los componentes que incluye es el alt´ımetro MPL3115A2, y permite conocer la informaci´on a la BBB, referente a la presi´on y altitud, as´ı como la temperatura del entorno en el cual este. Tambi´en se encuentra conectado al bus I2C. El GPS que incorpora es el FGPMMOPA6E, el cual permite obtener una alta precisi´on en la posici´on y velocidad, y con su alta sensibilidad lo hace un buen candidato para funcionar en entornos urbanos. Es capaz de soportar hasta 66 canales. Tiene un rango de funcionamiento de entre 1 y 10 Hz. Y el formato de adquisici´on de datos esta compuesto por el protocolo NMEA. Este dispositivo se conecta a trav´es de una UART. Debido a que la BBB lleva un puerto USB y esto es una limitaci´on, la ROBOCape permite ampliar hasta 4 puertos USB, gracias al HUB TUSB2046B que incorpora. Chapter 3. Herramientas Empleadas 38 Otro de los componentes existentes en esta placa, son los puentes H con los cuales se pueden manejar los motores DC o paso a paso, el controlador (BA6845) integrado permite trabajar con corrientes inferiores a 1A en r´egimen nominal. El control se realiza mediante las se˜nales PWM y los pines de la GPIO. Como cabe esperar, ROBOCape, incluye entradas anal´ogicas, en concreto 4, estas sirven para conectar los sensores de distancia Sharp GP2xx, y admite tensiones de hasta 1.8V, e integra un adaptador de tensiones m´aximas mediante un divisor resistivo. Permite incorporar sensores de ultrasonido HC-SR04, en total se permiten conectar hasta 6 empleando una topolog´ıa en anillo. Gracias a la l´ogica de dise˜no que lleva, permite utilizar un n´umero no muy elevado de pines. El funcionamiento de este modulo sigue la l´ogica de calculo del tiempo de vuelo de la se˜nal. Finalmente existen 4 l´ıneas directas que vienen de los controladores PWM, estas adaptan las se˜nales de la tensi´on t´ıpica en se˜nales para el servo mediante buffers de protecci´on. De esta forma se crea un sistema de protecci´on para los problemas el´ectricos provocados por circuitos externos. Figura 3.4: Descripci´on de conectores, m´odulos, IC’s y distribuci´on Cap´ıtulo 4 Trabajo Desarrollado En el cap´ıtulo actual se describe el trabajo realizado para la elaboraci´on de este trabajo final de m´aster. Primero se demuestra resumidamente como se emplea el simulador de movilidad SUMO y se detalla el escenario creado para obtener el fichero de configuraci´on para el simulador NS-3. En la siguiente secci´on se da a conocer el modelo de propagaci´on empleado e implementado para dicho simulador. Y a continuaci´on se describe el modelado e implementaci´on de un protocolo de enrutamiento para redes vehiculares para el simulador NS-3. Finalmente, en la ´ultima secci´on de este cap´ıtulo se explica el desarrollo que realizado sobre la placa BeagleBone Black, empleando el middleware ROS, y un ejemplo de aplicaci´on para robots humanoides, as´ı mostrando su alta escalabilidad para diferentes plataformas. 4.1. Ecosistema Con las herramientas expuestas anteriormente se ha obtenido un ecosistema que tiene la funcionalidad implementar, ejecutar y analizar una serie de simulaciones basadas en Redes de Sensores Inal´ambricos y Movilidad. Por un lado 3.1 se emplea para desarrollar nuevos protocolos y tecnolog´ıas de red donde poder comparar, analizar y validar todos los desarrollos. Esto permite proponer y evaluar nuevas mejoras y protocolos implementados. Para completar el ecosistema se necesita una serie de patrones de movilidad, que previamente han tenido que ser generados y analizados, de ah´ı la necesidad de emplear SUMO 3.2. 39 Chapter 4. Trabajo Desarrollado 40 Figura 4.1: Diagrama de bloques del ecosistema propuesto 4.2. Generaci´on de escenarios en SUMO La principal necesidad de emplear el simuladores de movilidad es que permite generar comportamientos similares al mundo real. De esta forma se puede analizar la densidad de tr´afico en una zona concreta. En este campo de investigaci´on emplear un simulador de movilidad con las caracter´ısticas que ofrece SUMO es de vital importancia, ya que se pueden generar todo tipo de tendencias de conducci´on, aumentar la densidad del tr´afico, generar posibles accidentes, entre otros comportamientos reales. La obtenci´on de este tipo informaci´on se puede reutilizar para la experimentaci´on y an´alisis de las redes vehiculares, y as´ı poder desarrollar nuevas t´ecnicas y tecnolog´ıas que permitan a los conductores una sensaci´on de seguridad cuando van al volante de su coche. La elecci´on de SUMO como simulador de movilidad ha sido debido a que es de de c´odigo libre y esta escrito bajo licencia GNU General Public License version 3.0 (GPLv3), adem´as de ser portable. Proporciona un paquete de simulaci´on de tr´afico rodado microsc´opico y continuo, est´a dise˜nado para manejar grandes redes de carreteras. Permite la simulaci´on incluyendo peatones intermodales y viene con un gran conjunto de herramientas para la creaci´on de escenarios. Por otra parte, permite un enorme acoplamiento con cualquier simulador de redes, ya que la informaci´on que se obtiene viene en un formato estandarizado, de f´acil y r´apida la conversi´on para los simuladores de redes, como por ejemplo a ns-2 y ns-3. A continuaci´on se describir´an una serie de pasos b´asicos para el r´apido manejo de SUMO. La creaci´on de escenarios en SUMO se puede realizar de dos formas, una mediante la descarga de mapas en formato XML o mediante la edici´on de ficheros XML. Si se Chapter 4. Trabajo Desarrollado 41 emplea la primera mencionada, accediendo previo registro a OpenStreetMap se puede descargar una determinada zona. Como por ejemplo Figura 4.2. Figura 4.2: ´ Area de la Universidad Polit´ecnica de Valencia Cuando el mapa est´e descargado hay que convertirlo a formato XML, esto se realiza con la ayuda del comando netconvert de SUMO. Una vez completado este paso se obtiene el fichero XML que conforma la red de los nodos que forman las calles, carreteras, etc. Para crear un escenario de simulaci´on que se aproxime a la realidad, es decir, a˜nadir zonas verdes, construcciones, etc, hay que emplear el comando polyconvert el cual recibe como entrada el fichero obtenido anteriormente y un fichero que se obtiene de la web de la organizaci´on que lo ha desarrollado. Seguidamente se crean una serie de trayectorias aleatorias, esto se consigue con el comando randomTrips.py el cual recibe como argumento de entrada el fichero que contiene la red de carreteras y como fichero de salida genera un XML con las rutas. Una vez completado esto, se edita un fichero de configuraci´on que sirve para ejecutar la la simulaci´on. Para ejecutar la simulaci´on se escribir´a la orden sumo-gui map.sumo.cfg y se obtendr´a un ventana similar a la mostrada en la Figura 4.3 Una vez cargado el simulador, si se realiza zoom y se pone en ejecuci´on la simulaci´on aparecer´an veh´ıculos en movimiento y sem´aforos cambiando sus luces, en la Figura 4.4 se muestra un ejemplo. Por otra parte, SUMO permite crear escenarios personalizados, para ello se debe de seguir un flujo de trabajo tal como indica el diagrama de la Figura 4.13. Siguiendo el diagrama de flujo de la Figura 4.13 se van creando los ficheros. Primero se crea el archivo que contendr´a los nodos. En la Figura 4.5 se muestra un ejemplo. Chapter 4. Trabajo Desarrollado 42 Figura 4.3: ´ Area simulada de la Universidad Polit´ecnica de Valencia Figura 4.4: Ejemplo simulaci´on Figura 4.5: Ejemplo .nod.xml A continuaci´on se editar´a el fichero que contendr´a las aristas de conexi´on entre los nodos. En la Figura 4.6 se muestra un ejemplo. Figura 4.6: Ejemplo .edg.xml Tras la edici´on de estos dos ficheros y la ejecuci´on de la aplicaci´on netconvertert se obtiene el fichero que contiene la red de nodos que conformar´a el escenario, en la Figura 4.7. Chapter 4. Trabajo Desarrollado 43 Figura 4.7: Ejemplo .net.xml El siguiente paso consiste en generar una serie de flujos de movilidad, ello se consigue con la edici´on del fichero de flujo. Figura 4.8 Figura 4.8: Ejemplo .flow.xml Ejecutando al aplicaci´on duarouter, y indicando el fichero de entrada como el .flow.xml y una serie de par´ametros se obtiene el fichero .rou.xml que contendr´a las rutas a seguir por los veh´ıculos en el escenario dise˜nado. En la Figura 4.9 se muestra en fragmento de c´odigo. Figura 4.9: Ejemplo .rou.xml Una vez llegados hasta este punto, se procede a la edici´on del fichero de configuraci´on de la simulaci´on, para ello, hay que crear un fichero con extensi´on .cfg similar al mostrado en la Figura 4.10, d´onde se indicar´an los ficheros que conforman la red y las rutas, adem´as se puede indicar una serie de par´ametros, como el inicio y finalizaci´on de la simulaci´on, el tama˜no de incremento entre cada instante, entre otros. Figura 4.10: Ejemplo .cfg Chapter 4. Trabajo Desarrollado 50 Figura 4.18: Cabecera mensaje ACK MyPosX yMyPosY: son dos campos de 64 bits del tipo double, se ha optado que tenga esta capacidad porque la informaci´on que adjuntar´a hace uso de la coma flotante del computador en que este, e interesa que el dato sea lo m´as pr´oximo a la realidad, y sin que exista la certeza de que el tama˜no llegue a desbordar y por tanto transmitir un mensaje err´oneo. DistanceToSrc: es un campo de 32 bits que permite informar al nodo que envi´o el mensaje HELLO cual es la distancia que existe entre el nodo origen y destino, adem´as, gracias al signo se puede saber si va en la misma direcci´on o en la direcci´on opuesta. OrientReferenceToSRC: Permite obtener el ´angulo que existe entre el nodo origen y destino, este campo tiene un tama˜no de 32 bits. La clase StatusHeader implementa un paquete de datos, que sirve para informar a un nodo destino que est´e dentro de de la propia red ad-hoc creada. Los campos que conforman este paquete son los mostrados en la Figura 4.19: Figura 4.19: Cabecera mensaje STATUS Chapter 4. Trabajo Desarrollado 51 Hop Count: este campo tiene un tama˜no de 8 bits, y sirve para llevar la cuenta de los saltos que ha realizado un determinado paquete. CoordinateLocation: es un campo de 32 bits que contiene las coordenadas de localizaci´on del nodo emisor. VelocityVehicle: es un campo de 32 bits que contiene la velocidad a la que circula el veh´ıculo en un instante de tiempo determinado. State: tiene una capacidad de 32 bits, y sirve para indicar a los veh´ıculos vecinos del estado actual de calzada. LocationService es una clase abstracta que sirve para localizar un nodo geogr´aficamente, en la versi´on oficial del simulador ns-3 no se encuentra a´un. Este servicio fue creado para protocolos basados en localizaci´on geogr´afica [29] y as´ı poder emular el comportamiento de un GPS. RequestQueue sirve para encolar los mensajes que no han podido ser enviados debidos a una desconexi´on temporal de los nodos. La clase ExpertSystem implementa las reglas descritas en [5] en un sistema experto basado en reglas. Con ella, se permite obtener las funciones de coste, para ayudar a decidir a que vecino hay que enviar los mensajes hacia el destino. De esta forma se intenta obtener un comportamiento aproximado al propuesto en Figura 2.10. Finalmente, en la clase RoutingProtocol se encuentra la l´ogica del protocolo de enrutamiento propuesto en la figura 2.10. Aqu´ı es donde se realizan las funciones de establecer la IP a los nodos que forman la red ad-hoc enviar y recibir los distintos paquetes, adem´as de tomar las decisiones para enviar a un nodo u otro los distintos paquetes. A continuaci´on se va a detallar el funcionamiento de las funciones principales que se emplean en la implementaci´on de este objeto. En la figura 4.20 se muestra el diagrama de flujo del protocolo implementado, las modificaciones realizadas ha sido suprimir el modo desconectividad, y cambiar el sistema basado en Fuzzy Logic por un sistema basado en reglas. Este sistema emplea la misma salida que el propuesto originalmente. Seguidamente se describir´a el funcionamiento del protocolo implementado. Cuando desde el fichero de configuraci´on del escenario se invoca al protocolo, ha este se le pueden pasar una serie de atributos para su configuraci´on. En este conjunto de atributos se encuentra HelloInterval, la cual es una variable del tipo Time que por defecto est´a inicializara a un segundo, con este tiempo se configura un JITTER el cual sirve para la inicializaci´on de la tasa de env´ıo de paquetes HELLO. Este tipo de paquetes se env´ıan peri´odicamente para la construcci´on de la tabla de vecinos de los nodos. Este tipo de mensaje hace una Chapter 4. Trabajo Desarrollado 52 inundaci´on a todos los nodos que est´an dentro de su alcance. En el momento que un nodo que est´a dentro del rango de cobertura y ha recibido este paquete analiza dicha cabecera y crea una entrada en la tabla de vecinos, en caso de que ya existiera la entrada actualiza sus valores. Una vez completado este proceso el nodo env´ıa un paquete ACK al nodo que inici´o la comunicaci´on, trasmitiendo los campos descritos anteriormente. El nodo receptor de este paquete analiza el mensaje y actualiza su entrada de la tabla de vecinos. Una vez, se ha vencido el tiempo de espera para enviar los mensajes de datos entra en funcionamiento las funciones RouteOutput yRouteInput, que est´an mostradas en la figura 4.20. La llamada a RouteOutput se realiza en el momento que el nodo fuente est´a listo para retransmitir el paquete de datos y por tanto a configurar la ruta de salida para que despu´es RouteInput a trav´es de los nodos intermedios sea capaz de alcanzar el destino del paquete, ya sea realizando una entrega directa o retransmisiones, Forwarding. Como se puede observar en la figura 4.20 la funci´on RouteOutput y RouteInput siguen el flujo de datos establecido por el diagrama original 2.10. Cuando RouteOutput entra en ejecuci´on se comprueba que el socket de la direcci´on no est´e vac´ıo, en caso de estarlo devuelve una ruta establecida por defecto en el simulador. El siguiente paso es obtener los distintos atributos del nodo fuente, es decir, su IP, posici´on, y a trav´es del Header obtenemos la direcci´on IP destino.Este destino se establece como siguiente salto a alcanzar dentro de la ruta. Entonces se comprueba si la tabla de vecinos del nodo fuente esta vac´ıa, en caso de estarlo el paquete se descarta. En caso contrario se a˜nade la informaci´on al Header y seguidamente se comprueba si el destino es vecino o no, en caso serlo se configura la ruta de salida para alcanzar el destino. En caso de no ser un nodo vecino el destino entra en funcionamiento el sistema basado en reglas. En este sistema se obtiene el nodo vecino con una mejor funci´on de coste para configurar la ruta. Una vez configurada la ruta por el nodo origen, entra en funcionamiento la funci´on RouteInput, en esta funci´on se peude realizar la llamada a una serie de callbacks para alcanzar el destino, aqu´ı se vuelve a comprobar si la IP destino y su interfaz son destinos, en caso afirmativo se realiza una llamada al callback LocalDeliverCallback y de esta forma el paquete ha alcanzado su destino. En caso contrario se realiza la llamada a la funci´on Forwarding. Esta funci´on tiene un comportamiento similar a RouteOutput. Se obtiene la IP destino, fuente e IP de nodo intermedio, seguidamente se comprueba si la IP destino del paquete es la del nodo destino. En caso afirmativo se configura la ruta para la entrega directa. En el caso contrario se obtiene cual ser´a el mejor nodo candidato para alcanzar Chapter 4. Trabajo Desarrollado 53 (a) RouteOutput (b) RouteInput Figura 4.20: Diagrama flujo protocolo propuesto el destino, esto se realiza de forma similar que en RouteOutput, para poder retransmitir los paquetes se emplea el callback UnicastForwardCallback. En la figura 4.21 se puede apreciar el esquema de comunicaciones que sigue el simulador ns-3 para transmitir el paquete a trav´es del protocolo de transporte y del protocolo IP, y las llamadas que se realizan a la hora de intercambiar el paquete con las capas inferiores de la pila IP. Chapter 4. Trabajo Desarrollado 54 Figura 4.21: Esquema comunicaciones con niveles inferiores de la pila IP Chapter 4. Trabajo Desarrollado 55 4.4. Nodos ROS En paralelo se ha desarrollado parte de la tesis doctoral, esto es la implementaci´on de nodos en ROS para la BeagleBone Black, necesaria para la implementaci´on sobre nodos reales de las propuestas realizadas de protocolos para redes vehiculares previamente simuladas y evaluadas, dado que estos protocolos necesitan de diferentes dispositivos y perif´ericos como GPS, etc. 4.4.1. Descripci´on nodos de ROS En el trabajo realizado se ha integrado la librer´ıa BlackLib [30] dentro de un nodo ROS. Esta librer´ıa ha sido escrita para que el acceso a bajo nivel de los componentes HW de la BBB sea transparente. El lenguajes empleado para su desarrollo es C++, y permite la lectura de las entradas anal´ogicas, generar se˜nales PWM, poder emplear los pines GPIO. Adem´as permite realizar la comunicaci´on con otros dispositivos que empleen la UART, I2C y SPI. Esta integraci´on se ha podido realizar ya que ROS y BlackLib est´an escrito en C++. A la librer´ıa original se le ha han a˜nadido dos objetos como se muestra en la Figura 4.22. Estos dos objetos a˜nadidos permiten leer los valores devueltos por la IMU y por el Alt´ımetro, son los que est´an de color verde. Se ha optado por realizar estas dos clases para facilitar en el futuro el uso de estos dispositivos ya que hab´ıa que realizar la lectura una serie de registros y direcciones de memoria. Para ello se han empleado los datasheets [31,32] de los fabricantes, es donde se describe el mapa de direcciones de los dispositivos. Figura 4.22: Jerarqu´ıa librer´ıa BlackLib Para la implementaci´on en ROS, se ha desarrollado el nodo mostrado en la Figura 4.23, que en el cual existen tres programas que permiten poner en funcionamiento la IMU, el alt´ımetro y el GPS[33]. El primer componente desarrollado ha sido el acceso a la unidad de medida inercial el cual est´a funcionando a una frecuencia de 1 Hz. En este se puede obtener los valores en los 9 ejes, es decir, se puede obtener la aceleraci´on lineal en las coordenadas X Y Z, adem´as de las coordenadas respectivas tanto para la velocidad angular y el campo Chapter 4. Trabajo Desarrollado 56 Figura 4.23: Nodo implementados en ROS magn´etico al cual est´a sometida la BeagleBone Black. Esta informaci´on se publica en los mensajes est´andares de ROS. El segundo componente que se describe es el alt´ımetro, con el cual se pueden obtener a que altitud sobre el nivel del mar a la que se encuentra la placa, adem´as de conocer la temperatura que tiene la placa en un instante de tiempo y cual es la presi´on atmosf´erica a la cual est´a sometida. Como en el caso anterior este nodo tambi´en se puede conocer mediante los mensajes t´ıpicos de ROS y funciona a la misma frecuencia. Otro nodo que ha sido implementado es el acceso al GPS, este est´a funcionado a una frecuencia de 0.5 Hz, el mensaje obtenido por el GPS sigue el est´andar del protocolo NMEA y por tanto se ha tenido que realizar una conversi´on de formato y permite conocer la longitud, latitud y la altura sobre el nivel del mar a la que se encuentra la tarjeta en un momento determinado. Y al igual que en los casos anteriores tambi´en se publica a trav´es de un mensaje de ROS. Y por ´ultimo, se ha creado otro nodo para la lectura de los sensores de tipo Sharp comentados en la secci´on 3.5. Este nodo permite la lectura de los 4 conversores ADC que permite el acceso la cape. Este nodo tambi´en funciona a 1 Hz y publica los datos a trav´es de mensajes de ROS. Chapter 4. Trabajo Desarrollado 57 4.4.2. Integraci´on librer´ıas en ROS Para poder emplear la librer´ıa Blacklib desde un nodo ROS, primero de todo debe de existir una ´area de trabajo para el usuario en ROS, esto se puede realizar de la siguiente forma: mkdir -p ros_workspace / catkin_ws /src cd ros_workspace / catkin_ws / src catkin_init \ _workspace catkin_make Listing 4.1: Comando para configurar ´area de trabajo en ROS Seguidamente, hay que crear se tiene que crear un nodo. Este nodo ha de contener los ficheros necesarios para que pueda ponerse en funcionamiento desde el nodo master. Para crear el nodo hay que ejecutando la orden: catkin_create_pkg ’nombre del nodo ’ Listing 4.2: Crear un nodo en ROS El siguiente a seguir consiste en ubicar los ficheros de cabecera dentro del directorio include/nombre nodo, con los ficheros fuente se realiza una tarea similar pero esta vez en el directorio src. A continuaci´on se ha de editar un fichero fuente el cual deber´a de tener la funci´on main y la funcionalidad que se desee que implemente el nodo. Para completar el proceso de integraci´on hay que editar el fichero CMakeList.txt. En este fichero hay que localizar una serie de funciones que est´an comentadas. Estas funciones son: catkin package: en su interior hay que a˜nadir el directorio include y el nombre de la librer´ıa a emplear, hay que anteponer la palabra lib. add library: hay que a˜nadir el el nombre de la librer´ıa que se ha incorporado al paquete, adem´as de la ruta a los ficheros fuente que se van a emplear. add executable: en esta funci´on se debe de escribir el nombre del ejecutable que a implementar y el nombre del fichero donde est´e su implementaci´on. target link libraries: esta funci´on sirve para vincular el ejecutable con las librer´ıas, por tanto hay que a˜nadir el nombre del ejecutable que se ha dado en la funci´on add executable y el nombre de la librer´ıa dado en catkin package y add library. A la hora de implementar el protocolo de enrutamiento propuesto en este Trabajo Final de Master, se seguir´a una secuencia de trabajo similar a la mencionada en 4.4.2. Cap´ıtulo 5 Experimentaci´on y resultados En el presente cap´ıtulo se describir´a la metodolog´ıa seguida para la validaci´on del protocolo modelado en el cap´ıtulo 4. Para ello, primero se definir´a un escenario similar al propuesto en [5] y se realizar´an una serie de experimentos con los mismos par´ametros de configuraci´on. Seguidamente los resultados obtenidos ser´an analizados para validar dicha implementaci´on. Adem´as se variar´an algunos par´ametros de simulaci´on para analizar los cambios que provocan en la red y evaluar las prestaciones del protocolo. Finalmente, se mostrar´an los resultados obtenidos en la implementaci´on del equipo f´ısico y sus distintas aplicaciones. 5.1. Evaluaci´on del protocolo propuesto Tal como se ha presentado en la secci´on 4.3 se ha desarrollado una aproximaci´on del protocolo de enrutamiento SRR para entornos vehiculares. Para poder validar esta implementaci´on se ha empleado un escenario generado con el simulador SUMO siguiendo los pasos mostrados en 4.2. A continuaci´on se detallan los par´ametros que se han empleado para validar la implementaci´on y los escenarios empleados en el simulador ns-3 para validar dicho protocolo. 5.1.1. Par´ametros de la simulaci´on y escenarios En la realizaci´on del estudio en el impacto del Channel Shadowing se han empleado los siguientes par´ametros: El n´umero de nodos fuente han sido 5 59 Chapter 5. Experimentaci´on y an´alisis de resultados 66 Figura 5.4: Comparaci´on PDR protocolo propuesto (arriba) VS SRR (abajo) 5.1.6. Otros an´alisis Debido a que el simulador ofrece gran libertad para realizar simulaciones realistas, se ha aprovechado y se han cambiado algunos par´ametros. En las siguientes experimentaciones se analizan ha deshabilitado los paquetes de control Clear To Send (CTS) y Request To Send (RTS), cuando su tama˜no sea inferior a 2200 Bytes. Como se puede apreciar en las gr´aficas 5.7, las tendencias son similares, pero debido a deshabilitar el env´ıo de los paquetes de control el retardo medio ha disminuido, y en cambio el PDR ha sufrido un ligero aumento. Otro an´alisis que se han realizado han sido cambiar el n´umero de receptores de la red adhoc, hasta el momento en los an´alisis solo hab´ıa un nodo receptor, en este experimento Chapter 5. Experimentaci´on y an´alisis de resultados 67 Figura 5.5: Comparaci´on Delay protocolo propuesto (arriba) VS SRR (abajo) los nodos fuente son 5 y transmiten al resto de nodos y se han deshabilitado los paquetes de control que tengan un tama˜no inferior a 2200 Bytes. En cuanto a la productividad al incrementar el n´umero de receptores cuando mayor valor de σesta tasa es mayor. Como se puede observar en la figura 5.8 del impacto de seg´un la variaci´on del Channel Shadowing, cuando mayor valor tiene Xσel retardo de entrega de los paquetes se incrementa, esto se debe a que mayor Xσ, el rango de nodos a los que se puede alcanzar es mayor. En cambio cuando menor valor de Xσla tasa de ratio de entrega de paquetes es ligeramente superior en el caso de entregar a un destino que a todos los nodos restantes 5.9. Por ´ultimo, al haber un mayor n´umero de nodos receptores el retardo End-To-End ha sufrido una ligera mejora decrementado el retardo medio, figura 5.10. En cuanto a las otras m´etricas comparadas tienen una tendencia similar. Chapter 5. Experimentaci´on y an´alisis de resultados 68 Figura 5.6: Comparaci´on Overhead protocolo propuesto (arriba) VS SRR (abajo) En la figura 5.11, se muestran los resultados de la simulaci´on dependiendo de la densidad de veh´ıculos que haya en la red. Cuando mayor densidad de nodos, el retardo se incrementa, esto es debido a la gran cantidad de paquetes que est´an viajando a lo largo de la red para alcanzar su destino. El principal factor que influye en este experimento son las colisiones entre paquetes. En cuanto a la entrega de paquetes cuando la densidad de los nodos disminuye la entrega de los paquetes es bastante elevada, se puede observar que conforme la velocidad de transmisi´on va aumentando, la tendencia de entrega va disminuyendo, esto se debe a que conforme aumenta la velocidad el ratio de alcance va disminuyendo paulatinamente. Finalmente, en este experimento, se puede observar que la mejor tasa de productividad existe cuando hay una gran densidad de paquetes, esto se debe a que hay mucho mas intercambio de paquetes en altas densidades que en bajas. Chapter 5. Experimentaci´on y an´alisis de resultados 69 Figura 5.7: Comparaci´on PDR paquetes de control habilitados (arriba) VS deshabilitados (abajo) Chapter 5. Experimentaci´on y an´alisis de resultados 70 Figura 5.8: Comparaci´on Throughput sin paquetes de control con 1 destino (arriba) VS destino todos los nodos de la red (abajo) Chapter 5. Experimentaci´on y an´alisis de resultados 71 Figura 5.9: Comparaci´on PDR sin paquetes de control con 1 destino (arriba) VS destino todos los nodos de la red (abajo) Chapter 5. Experimentaci´on y an´alisis de resultados 72 Figura 5.10: Comparaci´on Delay sin paquetes de control con 1 destino (arriba) VS destino todos los nodos de la red (abajo) Chapter 5. Experimentaci´on y an´alisis de resultados 73 Figura 5.11: Comparaci´on Densidad sin paquetes de control con 1 destino (arriba) VS destino todos los nodos de la red (abajo) Chapter 5. Experimentaci´on y an´alisis de resultados 74 En el an´alisis del impacto de la velocidad a la que se mueven los veh´ıculos, se ha variado de 25 m/s a 30 m/s. Se puede observar que seg´un aumenta la velocidad de transmisi´on, el retardo de los paquetes es mucho mayor 5.12. En caso contrario, en la entrega de paquetes se puede observar una reducci´on, estos fen´omenos se deben a que seg´un va aumentando la velocidad de transmisi´on el espectro es menor, y adem´as a˜nadiendo la velocidad de los nodos esto provoca que los mensajes no lleguen a su destino por posibles desconexiones 5.13. Figura 5.12: Comparaci´on retardo sin paquetes de control con 1 destino (arriba) VS destino todos los nodos de la red (abajo) 5.2. Evaluaci´on Beaglebone Black A continuaci´on se presentan los experimentos realizados con la BeagleBoneBlack y la ROBOCape empleando los nodos de ROS descritos en el apartado 4.4 que permitir´an evaluar la implementaci´on sobre hardware real de las partes del sistema necesarias para Chapter 5. Experimentaci´on y an´alisis de resultados 75 Figura 5.13: Comparaci´on Velocidad sin paquetes de control con 1 destino (abajo) VS destino todos los nodos de la red (abajo) complementar los protocolos de comunicaci´on estudiados previamente basados en GPS. Estos experimentos han consistido en ubicar la BeagleBoneBlack en el veh´ıculo el´ectrico e ir por dentro del campus universitario dando vueltas para obtener los resultados del GPS. Durante estos recorridos se han realizado diversas acciones, como por ejemplo acelerar y desacelerar, adem´as de realizar giros bruscos a derechas e izquierdas para tomar las mediciones de la IMU, la velocidad m´axima alcanzada ha sido de 30 Km/h. El GPS estaba funcionando a una frecuencia de 0.5 Hz y la IMU a 1 Hz. En las figuras 5.14 y5.14 se muestran algunas de las rutas obtenidas con el GPS. Para poder representar las coordenadas en Google Earth se han convertido las coordenadas del GPS de grados sexadecimales a grados decimales. Como se ha podido observar el rendimiento del GPS es bastante bueno aun funcionando a un bajo rendimiento. Como ocurre con todo dispositivo GPS existe un rango de error. Este error se observa cuando se trazan las trayectorias sobre el mapa real. Bibliograf´ıa [1] L. Banda, M. Mzyece, and G. Noel. Ip mobility support: Solutions for vehicular networks. Vehicular Technology Magazine, IEEE, 7(4):77–87, Dec 2012. ISSN 15566072. doi: 10.1109/MVT.2012.2203881. [2] David Chunhu Li, Li-Der Chou, Li-Ming Tseng, Yi-Ming Chen, and Kai-Wei. Kuo. A bipolar traffic density awareness routing protocol for vehicular ad hoc networks. Mobile Information Systems, 2015(2015):1–12, 2015. doi: 10.1155/2015/401518. URL http://dx.doi.org/10.1155/2015/401518. [3] J. Toutouh, J. Garcia-Nieto, and E. Alba. Intelligent olsr routing protocol optimization for vanets. Vehicular Technology, IEEE Transactions on, 61(4):1884–1894, May 2012. ISSN 0018-9545. doi: 10.1109/TVT.2012.2188552. [4] Jamal Toutouh, Sergio Nesmachnow, and Enrique Alba. Fast energy-aware olsr routing in vanets by means of a parallel evolutionary algorithm. Cluster Computing, 16(3):435–450, 2013. ISSN 1386-7857. doi: 10.1007/s10586-012-0208-9. URL http: //dx.doi.org/10.1007/s10586-012-0208-9. [5] Kayhan Zrar Ghafoor, Kamalrulnizam Abu Bakar, Shaharuddin Salleh, Kevin C. Lee, Mohd Murtadha Mohamad, Maznah Kamat, and Marina Md Arshad. Fuzzy logic-assisted geographical routing over vehicular ad hoc networks. International Journal of Innovative Computing, Information and Control, 8(7(B)):5095–5120, July 2012. ISSN 1349-4198. [6] J. E. Smith A. E. Eiben. Introduction to Evolutionary Computing. Springer, 2003. [7] Jaime Lloret Kamalrulnizam Abu Bakar Zaitul M. Zainuddin Kayhan Zrar Ghafoor, Marwan Aziz Mohammed. Routing protocols in vehicular ad hoc networks: Survey and research challenges. Network Protocols and Algorithms, 5(4):39–83, Dec 2013. ISSN 1943-3581. doi: 10.5296/npa.v5i4.4134. URL http://dx.doi.org/10.5296/ npa.v5i4.4134. [8] Daqiang Zhang, Zhijun Yang, Vaskar Raychoudhury, Zhe Chen, and Jaime Lloret. An energy-efficient routing protocol using movement trends in vehicular ad 83 Bibliography 84 hoc networks. The Computer Journal, pages 1–9, 2013. doi: 10.1093/comjnl/ bxt028. URL http://comjnl.oxfordjournals.org/content/early/2013/03/ 21/comjnl.bxt028.abstract. [9] M. Al-Rabayah and R. Malaney. A new scalable hybrid routing protocol for vanets. Vehicular Technology, IEEE Transactions on, 61(6):2625–2635, July 2012. ISSN 0018-9545. doi: 10.1109/TVT.2012.2198837. [10] Douglas S. J. De Couto, Daniel Aguayo, John Bicket, and Robert Morris. A highthroughput path metric for multi-hop wireless routing. pages 134–146, 2003. doi: 10.1145/938985.939000. URL http://doi.acm.org/10.1145/938985.939000. [11] M. Al-Rabayah and R. Malaney. Scalable hybrid location-based routing in vehicular ad hoc networks. pages 1–5, Sept 2011. ISSN 1090-3038. doi: 10.1109/VETECF. 2011.6093116. [12] ns-2. http://www.isi.edu/nsnam/ns/. [Online; accedido Septiembre-2015]. [13] Mallba. http://neo.lcc.uma.es/mallba/easy-mallba/html/mallba.html. [Online; accedido Septiembre-2015]. [14] D. Garc´ıa C. G´omez and J. Paradells. Improving performance of a real ad hoc network by tuning olsr parameters. Proc. 10th IEEE ISCC, pages 16–21, 2005. [15] J. Garc´ıa-Nieto, J. Toutouh, and E. Alba. Automatic tuning of communication protocols for vehicular ad hoc networks using metaheuristics. Engineering Applications of Artificial Intelligence, 23(5):795–805, 2010. ISSN 0952-1976. doi: 10.1016/j.engappai.2010.01.012. URL http://www.sciencedirect.com/science/ article/pii/S0952197610000308. Advances in metaheuristics for hard optimization: new trends and case studies. [16] C.A.T.H. Tee and A. Lee. Adaptive reactive routing for vanet in city environments. pages 610–614, Dec 2009. doi: 10.1109/I-SPAN.2009.39. [17] J. Zhao and G. Cao. Vadd: Vehicle-assisted data delivery in vehicular ad hoc networks. The 25th Conference on Computer Communications (IEEE INFOCOM’06), Apr 2006. [18] A. Fagg J. Davis and B Levine. Wearable computers as packet transport mechanisms in highly-partitioned ad-hoc networks. International Symposium on Wearable Computing, Oct 2001. [19] Zeinab Rezaeifar, Faramarz Hendessi, BehrouzShahgholi Ghahfarokhi, and T.Aaron Gulliver. A reliable geocast routing protocol for vehicular ad hoc networks. Wireless Bibliography 85 Personal Communications, 83(1):281–295, 2015. ISSN 0929-6212. doi: 10.1007/ s11277-015-2393-3. URL http://dx.doi.org/10.1007/s11277-015-2393-3. [20] Li-Der Chou, Jyun-Yan Yang, Ying-Cheng Hsieh, Der-Chyn Chang, and Chi-Feng Tung. Intersection-based routing protocol for vanets. Wireless Personal Communications, 60(1):105–124, 2011. ISSN 0929-6212. doi: 10.1007/s11277-011-0257-z. URL http://dx.doi.org/10.1007/s11277-011-0257-z. [21] Jist/swans. http://jist.ece.cornell.edu/. [Online; accedido Septiembre-2015]. [22] Ns-3 team. https://www.nsnam.org/, 2015. [Online; accedido Septiembre-2015]. [23] Institute of Transportation Systems. Sumo - simulation of urban mobility. http://www.dlr.de/ts/en/desktopdefault.aspx/tabid-9883/16931_ read-41000/, 2015. [Online; accedido Septiembre-2015]. [24] Ros - robot operating system. http://www.ros.org/, 2015. [Online; accedido Septiembre-2015]. [25] Beagleboard. http://www.beagleboard.org/, 2015. [Online; accedido Septiembre2015]. [26] Miguel Albero. Robocape for beagleboneblack. Reporte interno AI2, 2014. [27] T. S. Rappaport. Wireless Communications: Principles and Practice. Prentice Hall PTR, New Jersey, 1996. [28] Bluegiga. https://www.bluegiga.com/en-US/products/wf111-wifi-module/, 2015. [Online; accedido Septiembre-2015]. [29] Ant´onio Fonseca, Andr´e Cam˜oes, and Teresa Vaz˜ao. Geographical routing implementation in ns3. In Proceedings of the 5th International ICST Conference on Simulation Tools and Techniques, SIMUTOOLS ’12, pages 353–358, ICST, Brussels, Belgium, Belgium, 2012. ICST (Institute for Computer Sciences, SocialInformatics and Telecommunications Engineering). ISBN 978-1-4503-1510-4. URL http://dl.acm.org/citation.cfm?id=2263019.2263075. [30] Blacklib. http://blacklib.yigityuce.com/, 2015. [Online; accedido Septiembre2015]. [31] InvenSense Inc. Mpu-6000 and mpu-6050 register map and descriptions. Datasheet, 2012. [32] Freescale Semiconductor. Xtrinsic mpl3115a2 i2c precision altimeter. Datasheet, 2013. Bibliography 86 [33] GlobalTop Technology Inc. Fgpmmopa6h gps standalone module data sheet. Datasheet, 2011.