Schemes for multi-hop dissemination of non-safety information in VANETs

Vehicular Ad Hoc Networks (VANETs) are a special case of Mobile Ad Hoc Network (MANET), whose nodes are vehicles and occasional fixed devices with communication capabilities. What makes them special is the limited range of possible movements of the mobile nodes (they can only travel on the existing roads or rails) and their high speed. The potential applications in this new type of network are almost endless. Researchers have typically classified them in four groups: active safety, public service support, improved driving and business/entertainment. The communication patterns that they require are varied, being information dissemination one of them. It is aimed at reaching a group of vehicles in an area that is larger than the reception range of a single node, so that a multi-hop broadcast is necessary. It can take multiple forms depending on the type of message. For example, a warning caused by a sudden brake requires a fast and reliable dissemination, whereas a blocked route announcement is tolerant to delays up to a few seconds and may miss some target without risking safety. The work in this PhD thesis is focused on this last type of use. The objective is to create schemes that would allow for the multi-hop dissemination of messages that do not have hard delay and delivery requirements (typically, any non-safety information). Our goals for this solution are four. First, we want it to be useful in roadways as well as inside cities. Vehicles movements and the occurrence of obstacles to the signal propagation are very different in both scenarios and so we need to adapt it to both. Second, we want it to be independent of infrastructure. The cost of deploying fixed units along every road and street is high and it may take a long time until there is global coverage. Our intention is that this solution can be used regardlessly of the deployment point. In addition, it must avoid the broadcast storm problem by reducing as much as possible the number of generated duplicates. Lastly, the scheme needs to cope with intermittent partitions in the vehicular network. Implementing a store-carry-forward mechanism that allows a message reach disconnected groups of vehicles inside the destination area rises the number of necessary duplicates. In order to achieve the aforementioned goals, we first study how typical infrastructure-less dissemination schemes from the state of the art in MANETs, plus a new specific one, apply to VANETs. According to their results in relation to a series of metrics, we learn that the distance-based scheme is the one that best meets our requirements. We select it to create an optimized scheme for the two existing scenarios-roadways and urban areas. Regarding the adaptation for roadways, we begin by optimizing the scheme so that its forwarding ratio is as close to the minimum as possible, and analyzing its average per-hop delay in a connected network (i.e., there is at least one feasible route between any two nodes in the network). Next, we study how to add a custom store-carry-forward mechanism that, with minimal additions, manages to overcome short-lived network partitions. We validate the addition and the complete scheme under different channel loads and in contrast with a well-known protocol aimed at the same type of traffic, DV-CAST. Our work on the version for urban scenarios parts from the assumption that we need to detect junctions and react accordingly in order to spread the dissemination in new directions and reach as many vehicles as possible. We create two different modifications of the basic distance-based scheme, each using a different method to detect intersections, and test them along with the basic one. This first step leads us to discovering that it is not necessary to detect intersections in order to achieve good results. Then, similarly to the process for the roadway scenario, we work on optimizing the scheme and creating a suitable store-carry-forward mechanism. We follow the same reasoning but this time we consider three different options for subsequent retransmissions. We test each version of the scheme throughly via simulations using real city maps and compare the results to those of the urban counterpart of DV-CAST, named UV-CAST. We use validated simulators as ns-2 and the Veins framework for testing realistically the different stages of our work. The performance of the resulting schemes meet our requirements to a high degree and so we consider that we have fulfilled our goals. In addition, the work done so far opens the door to new lines of research that are either the natural consequence or an application of our achievements.La expresión inglesa Vehicular Ad Hoc Networks (VANETs) nombra a un tipo especial de Mobile Ad Hoc Network (MANET), cuyos nodos son vehículos y, ocasionalmente, dispositivos fijos con capacidad de comunicación. Lo que las hace especiales es el rango limitado de movimientos posibles para los nodos móviles (ya que sólo pueden viajar por las vías existentes) y su alta velocidad. Las aplicaciones potenciales de este nuevo tipo de red son casi infinitas. La comunidad investigadora las ha clasificado típicamente en cuatro grupos: seguridad activa, apoyo a servicios públicos, asistencia a la conducción y negocios/entretenimiento. Los patrones de comunicación que precisan son variados, siendo la diseminación de información uno de ellos. Su objetivo es alcanzar a un grupo de vehículos en un área mayor que el de la cobertura alcanzada por un nodo, de modo que es necesaria una difusión multisalto. Esta puede tomar múltiples formas dependiendo del tipo de mensaje. Por ejemplo, una alarma provocada por un frenazo brusco requiere una diseminación rápida y confiable, mientras que un aviso de calle cortada es tolerante a retardos de hasta algunos segundos y si no alcanza a algún destinatario no supone un riesgo para la seguridad. El trabajo contenido en esta tesis se enfoca en este último caso de uso. La meta es crear esquemas que permitan la diseminación multisalto de mensajes que no tienen requisitos fuertes en cuanto a retardo y entrega (típicamente, cualquier información no relacionada con la seguridad). Nuestros objetivos para esta solución son cuatro. Primero, queremos que sea útil en carretera así como en ciudad. Los movimientos de los vehículos y la existencia de obstáculos para la propagación de la señal son muy diferentes en ambos escenarios y por tanto necesitamos adaptarla a ambos. Segundo, queremos que no dependa de infraestructura. El coste de desplegar unidades fijas a lo largo de cada calle y carretera es alto, y puede llevar un largo tiempo hasta que haya cobertura global. Nuestra intención es que esta solución pueda ser usada en cualquier punto del proceso de despliegue. Además, debe evitar el problema conocido como “tormenta broadcast”, reduciendo en la medida de lo posible el número de duplicados generados. Por último, el esquema necesita hacer frente a particiones intermitentes de la red vehicular. Implementar un mecanismo de los llamados “store-carry-forward” (guardar-llevar-reenviar), que permita a un mensaje llegar a grupos desconectados de vehículos dentro de la zona de destino, aumenta el número de duplicados necesarios. Para conseguir estos objetivos, primero estudiamos cómo esquemas típicos de diseminación sin apoyo de infraestructura, tomados del estado del arte en MANETs, más uno nuevo y específico, se pueden aplicar en VANETs. De acuerdo con los resultados en relación con una serie de métricas, hemos aprendido que el esquema basado en distancia es el que mejor cubre nuestros requisitos. Seleccionamos este para crear un esquema optimizado para los dos tipos de escenarios existentes: carretera (entorno interurbano) y ciudad (entorno urbano). En cuanto a la adaptación al entorno interurbano, comenzamos optimizando el esquema de modo que su tasa de reenvío esté tan cerca del mínimo como sea posible, y analizando su retardo medio por salto en una red conectada (es decir, que hay al menos una ruta posible entre dos nodos cualesquiera de la red). A continuación, estudiamos cómo añadir un mecanismo “store-carry-forward" específico para nuestra solución que, con cambios mínimos, consiga superar particiones de red breves. Validamos este añadido y el esquema completo bajo diferentes cargas de canal y en contraste con un conocido protocolo para este mismo tipo de tráfico, DV-CAST. Nuestro trabajo en la versión para escenarios urbanos parte del supuesto de que necesitamos detectar intersecciones y reaccionar en consecuencia para poder extender la diseminación en nuevas direcciones y alcanzar tantos vehículos como sea posible. Creamos dos modificaciones del esquema basado en distancia, cada una en base a un método distinto para detectar cruces, y las probamos junto con el esquema básico. Este primer paso nos lleva a descubrir que no es necesaria dicha detección para poder conseguir buenos resultados. Después, de forma similar al proceso que seguimos para el escenario de carretera, trabajamos en optimizar el esquema y crear un mecanismo “store-carry-forward" apropiado. Seguimos el mismo razonamiento pero en esta ocasión consideramos tres opciones diferentes para las repetidas retransmisiones. Probamos cada versión del esquema concienzudamente con simulaciones, utilizando mapas reales de ciudades, y comparamos los resultados con los del equivalente urbano de DV-CAST, llamado UV-CAST. Usamos simuladores validados como ns-2 y Veins para probar de forma realista las diferentes etapas de nuestro trabajo. Las prestaciones de los esquemas resultantes cumplen con nuestros requisitos en un alto grado, por lo que consideramos que hemos conseguido alcanzar nuestros objetivos. Además, el trabajo realizado hasta el momento abre la puerta a nuevas líneas de investigación que son, bien consecuencia natural, bien aplicación de nuestros logros.Programa Oficial de Doctorado en Ingeniería TelemáticaPresidente: Juan Carlos Cano Escriba.- Secretario: Florina Almenares Mendoza.- Vocal: José Marta Barcelo Ordina