Contribution to the design of VANET routing protocols for realistic urban environments
One of the main concerns of the cities' administration is mobility management. In Intelligent Transportation Systems (ITS) pedestrians, vehicles and public transportation systems could share information and react to any situation in the city. The information sensed by vehicles could be useful for other vehicles and for the mobility authorities. Vehicular Ad hoc Networks (VANETs) make possible the communication between vehicles (V2I) and also between vehicles and fixed infrastructure (V2I) managed by the city's authorities. In addition, VANET routing protocols minimize the use of fixed infrastructure since they employ multi hop V2V communication to reach reporting access points of the city. This thesis aims to contribute in the design of VANET routing protocols to enable reporting services (e.g. vehicular traffic notifications) in urban environments. The first step to achieve this global objective has been the study of components and tools to mimic a realistic VANET scenario. Moreover, we have analyzed the impact of the realism of each one of those components in the simulation results. Then, we have improved the Address Resolution procedure in VANETs by including it in the routing signaling messages. Our approach simplifies the VANET operation and increases the packet delivery ratio as consequence. Afterwards, we have tackled the issue of having duplicate packets in unicast communications and we have proposed routing filters to lower their presence. This way we have been able to increase the available bandwidth and reduce the average packet delay with a slight increase of the packet losses. Besides, we have proposed a Multi Metric Map aware routing protocol (MMMR) that incorporates four routing metrics (distance, trajectory, vehicle density and available bandwidth) to take the forwarding decisions. With the aim of increasing the number of delivered packets in MMMR, we have developed a Geographical Heuristic Routing (GHR) algorithm. GHR integrates Tabu and Simulated Annealing heuristic optimization techniques to adapt its behavior to the specific scenario characteristics. GHR is generic because it could use any geographical routing protocol to take the forwarding decisions. Additionally, we have designed an easy to implement forwarding strategy based on an extended topology information area of two hops, called 2 hops Geographical Anycast Routing (2hGAR) protocol. Results show that controlled randomness introduced by GHR improves the default operation of MMMR. On the other hand, 2hGAR presents lower delays than GHR and higher packet delivery ratio, especially in high density scenarios. Finally, we have proposed two mixed (integer and linear) optimization models to detect the best positions in the city to locate the Road Side Units (RSUs) which are in charge of gathering all the reporting information generated by vehicles. Una de las principales preocupaciones en la administracion de las ciudades es la gestion de la movilidad de sus vehiculos, debido a los problemas de trafico como atascos y accidentes. En los sistemas inteligentes de transporte (SIT) peatones, vehiculos y transporte publico podran compartir informacion y adaptarse a cualquier situacion que suceda en la ciudad. La informacion obtenida por los sensores de los vehiculos puede ser util para otros vehiculos y para las autoridades de movilidad. Las redes ad hoc vehiculares (VANETs) hacen posible la comunicacion entre los propios vehiculos (V2V) y entre vehiculos y la infraestructura fija de la red de la ciudad (V2I) Asimismo, los protocolos de encaminamiento para redes vehiculares minimizan el uso de infraestructura fija de red, ya que los protocolos de encaminamiento VANET emplean comunicaciones multisalto entre vehiculos para encaminar los mensajes hasta los puntos de acceso de la red en la ciudad. El objetivo de esta tesis doctoral es contribuir en el diseno de protocolos de encaminamiento en redes ad hoc vehiculares para servicios de notificaciones (p.ej. reportes del estado del trafico) en entornos urbanos. El primer paso para alcanzar este objetivo general ha sido el estudio de componentes y herramientas para simular un escenario realista de red ad hoc vehicular. Ademas, se ha analizado el impacto del nivel de realismo de cada uno de los componentes de simulacion en los resultados obtenidos. Asi tambien, se ha propuesto un mecanismo de resolucion de direcciones automatico y coherente para redes VANET a traves del uso de los propios mensajes de senalizacion de los protocolos de encaminamiento. Esta mejora simplifica la operacion de una red ad hoc vehicular y como consecuencia aumenta la tasa de recepcion de paquetes. A continuacion, se ha abordado el problema de la aparicion inesperada de paquetes de datos duplicados en una comunicacion punto a punto. Para ello, se ha propuesto el filtrado de paquetes duplicados a nivel del protocolo de encaminamiento. Esto ha producido un incremento del ancho disponible en el canal y una reduccion del retardo medio en la trasmision de un paquete, a costa de un minimo aumento de la perdida de paquetes. Por otra parte, hemos propuesto un protocolo de encaminamiento multi metrica MMMR (Multi Metric Map aware Routing protocol) el cual incorpora cuatro metricas (distancia al destino, trayectoria, densidad de vehiculos y ancho de banda) en las decisiones de encaminamiento. Con el objetivo de aumentar la tasa de entrega de paquetes en MMMR, hemos desarrollado un algoritmo heuristico de encaminamiento geografico denominado GHR (Geographical Heuristic Routing) Esta propuesta integra las tecnicas de optimizacion Tabu y Simulated Annealing, que permiten a GHR adaptarse a las caracteristicas especificas del escenario. Adicionalmente, hemos propuesto 2hGAR (2 hops Geographical Anycast Routing) un protocolo de encaminamiento anycast que emplea informacion de la topologia de red a dos saltos de distancia para tomar la decision de encaminamiento de los mensajes. Los resultados muestran que la aleatoriedad controlada de GHR en su operacion mejora el rendimiento de MMMR. Asimismo, 2hGAR presenta retardos de paquete menores a los obtenidos por GHR y una mayor tasa de paquetes entregados, especialmente en escenarios con alta densidad de vehiculos. Finalmente, se han propuesto dos modelos de optimizacion mixtos (enteros y lineales) para detectar los mejores lugares de la ciudad donde ubicar los puntos de acceso de la red, los cuales se encargan de recolectar los reportes generados por los vehiculos.