Comparación de protocolos unicast y geocast para redes Vanets

Comparación de protocolos unicast y geocast para redes VANET

Comparision of unicast and geocast protocols for Vanets networks

Gonzalo Jiménez Pinto¹, Edilberto Fernández Santos², Jaider Ospina Navas³

¹Ingeniero Electrónico, candidato a magíster en Ciencias de la Información y las Comunicaciones. Investigador de la Universidad Distrital Francisco José de Caldas. Bogotá, Colombia. Contacto: gjimenezp@udistrital.edu.co
²Administrador Ambiental, especialista en Gerencia de Proyectos, candidato a Magíster en Ingeniería Industrial. Investigador de la Universidad Distrital Francisco José de Caldas. Bogotá, Colombia. Contacto: efernandezs@udistrital.edu.co
³Ingeniero Electrónico, candidato a magíster en Ciencias de la Información y las Comunicaciones. Investigador de la Universidad Distrital Francisco José de Caldas. Bogotá, Colombia. Contacto: jospinan@udistrital.edu.co

Fecha de recepción: 15 de mayo de 2012 Fecha de aceptación: 27 de noviembre de 2012

Resumen

Las condiciones particulares presentes en una red VANET como la velocidad de los nodos comunicantes, la concentración en área y el control distribuido de red (producto de la ausencia de una infraestructura de control centralizada), traen consigo una serie de retos específicos que generan desafíos tecnológicos que obligan a un tratamiento desde una óptica diferente a la que dicta los protocolos de enrutamiento clásicos, dado que estos no están pensados para topologías cambiantes donde los nodos son responsables del encaminamiento y del mantenimiento de la red.

Este artículo muestra un análisis descriptivo de los protocolos más conocidos y la comparación de resultados obtenidos en trabajos anteriores mediante simulación del comportamiento de una red, para finalmente presentar el análisis de resultados y conclusiones del comportamiento de los protocolos evaluados.

Palabras clave: geocast, rendimiento, unicast, VANET.

Abstract

Particular conditions within a VANET network (such as speed of the communicating nodes and network concentration in areas of distributed control), resulting from a lack oficentralized monitoring infrastructure, bring a number of specific requirements that generate technological challenges. These challenges stray the main focus of such technologies from the perspective oficlassical routing protocols, since these are not intended for changing topologies, where nodes are responsible for both routing and network maintenance.

This paper presents a descriptive analysis of some of the most widely known protocols. Performance is compared to other results obtained in previous work by simulating the behavior of a network. Finally, analysis and conclusions are provided regarding protocol behavior.

Key words: geocast, performance, unicast, VANET

1. Introducción

Las redes ad-hoc vehiculares (Vehicular Ad-Hoc Networks) conocidas como VANET, son redes móviles que emplean vehículos como nodos de red, los cuales suministran información sobre el tráfico vehicular, por lo que se han convertidoen la actualidad en uno de los mayores focos de interés en el estudio y desarrollo de aplicaciones [1]. Las redes VANET se consideran como un caso particular de las conocidas MANET (Mobile Ad-hoc Networks) enfocadas a entornos vehiculares, cobijadas con la adopción del estándar 802.11a [2].

Gracias a su capacidad para suministrar información sobre tráfico vehicular y su potencial uso para evitar congestiones y mejorar la seguridad de los pasajeros, estas redes se han convertido en un gran foco de interés para investigadores y la industria [3]. Este último aspecto cobra gran interés si se tienen en cuenta estadísticas que señalan que los accidentes de tráfico ocupan el noveno lugar en el índice de mortalidad mundial [4].

Dentro de las características que tipifican este tipo de redes se debe citar la ausencia de un nodo central, lo que permite una autonomía a los nodos, que son capaces de procesar y encaminar información. Dicho de otra manera, en determinado momento deben actuar como una estación, nodo central o router. Otro aspecto importante es el cambio constante de topología a consecuencia delmovimiento arbitrario de los nodos, lo que afecta las condiciones de comunicación y potencia pérdidas de paquetes.

A partir de lo anterior se evidencian retos tecnológicos dentro de los que se identifica la limitación en el ancho de banda [5], tema que se ha convertido en trabajo de constante investigación, junto a aspectos como tiempos de respuesta de conductores, recepción de señal por nodos adyacentes y control de diseminación de mensajes [6]. Sobre este último aspecto, control de la diseminación de mensajes, se adelantan estudios en busca de algoritmos que permitan su uso por parte de la policía y organismos de emergencia, como medida en la atención y prevención de eventuales desastres.

Por otra parte, y como es de esperar en un medio naturalmente susceptible a limitaciones de ancho de banda, características como la redundancia en las comunicaciones [7] deben ser evaluadas y optimizadas a fin de evitar congestiones de red.

Este trabajo analiza y compara el rendimiento de los protocolos AODV y de tipo geocast. De manera particular se ha dado especial interés al protoloco Ad-hoc On-Demand Distance-Vector Routing (AODV) [8], debido a que es uno de los más representativos y que muestra mejores características de desempeño [9].

2. Características De Protocolos

2.1 AODV

El protocolo AODV, propuesto en 1999 [11], es un protocolo reactivo unicast para redes ad-hoc que establece la ruta por demanda, es decir, la ruta no se encuentra preestablecida, lo cual no indica que los mensajes sean enviados a ciegas, ya que el nodo receptor valida las rutas comparando su número de secuencia. Si un nodo quiere establecer comunicación con otro nodo, y la ruta no está establecida, envía un mensaje broadcast de solicitud de ruta ROUTE REQUEST (RREQ) [8]. Los nodos por los que tiene que pasar este mensaje registran la información sobre la ruta inversa hacia el nodo de inicio.

A cada nodo se asocia una tabla de encaminamiento que contiene el identificador de origen, el identificador de destino, el número de secuencia de origen, el número de secuencia de destino, el identificador de emisión, el tiempo de vida y un contador de salto. Al llegar a un nodo y encontrar la ruta válida se comprueba el número de secuencia (DestSeqNum). Si este número es mayor al número de secuencia guardado, se considera que la ruta es válida, y este nodo envía un mensaje tipo ROUTE REPLY (RREP), con la información sobre la ruta inversa hacia el nodo de inicio [12]

Una vez establecida la ruta, esta se mantiene por un tiempo, para no tener que realizar todo el proceso cada vez que se envía un paquete. Si un nodo intermedio se mueve, la topología cambia, por lo que este nodo ya no será utilizado y el nodo inmediatamente anterior, de fuente a destino, notifica, mediante un mensaje de error en la ruta (Router Error - RERR), el movimiento del nodo, y así el nodo de inicio deberá volver a comenzar el descubrimiento de ruta. También podría darse el caso del movimiento del nodo de inicio, en este caso el mismo nodo debe reiniciar el descubrimiento de ruta.

Por otra parte, debido a que muchos nodos están transmitiendo se pueden recibir números de secuencia de destino repetidos, en ese caso los números repetidos se eliminan. Este protocolo tiene como ventaja que puede ser utilizado en redes altamente escalables. Una desventaja es el incremento del número de secuencia y el decremento de número de saltos, de una manera engañosa, que puede generar errores en la ruta [13].

2.2 DSR

El protocolo DSR [14] está diseñado específica-mente para redes inalámbricas multi-hop y redes ad-hoc. Este protocolo, propuesto en 1996 [14], tiene dos componentes básicos: el descubrimiento de ruta, mecanismo mediante el cual si un nodo desea enviar un mensaje a un nodo desconocido se obtiene una ruta de destino; y el mantenimiento de ruta, mecanismo mediante el cual si un nodo quiere enviar un mensaje a un nodo destino, detecta cuando la topología ha cambiado, por el movimiento de los nodos, y busca otra ruta o llama al descubrimiento de ruta para establecer una nueva [14], [15].

Este es un protocolo que funciona básicamente como el AODV pero a diferencia de este, no genera una tabla de enrutamiento inversa. Se basa en el encaminamiento desde el origen, para lo cualse inserta una cabecera con la información sobre los nodos que se deben recorrer para llegar al destino. Una de las características de este protocolo es que con las optimizaciones disponibles puede ser utilizado en redes pequeñas [16], con la ventaja de un menor overhead respecto a AODV.

2.3 Tora

Este es un protocolo propuesto en 1996 para mejorar el rendimiento de las redes altamente dinámicas. Funciona básicamente como DSR, pero a diferencia de este, elimina las rutas inválidas, busca una nueva ruta y la establece en un solo paso, mientras que DSR lo hace en 3 pasos [17].

3. Protocolos Geocast

Los protocolos geocast son un caso particular de protocolos multicast que son muy usados en redes VANET. Son protocolos donde los grupos están organizados en función de la posición geográfica de los nodos de la red. Se usan protocolos geocast cuando se desea mandar un mensaje a un grupo de vehículos de una determinada zona geográfica, para advertir sobre riesgos, por ejemplo, en la carretera. Dentro de los protocolos geocast conocidos están los siguientes.

3.1 LBM

El LBM (Location Based Multicast)[18], [19] es un protocolo orientado a la transmisión de datos que se basa en el protocolo unicast LAR (Location Aiden Routing), propuesto en 1998 [20]. Este protocolo usa el mismo método de descubrimiento de ruta que el protocolo DSDV, pero a diferencia de este, la información no se envía a todos los vecinos, sino que basándose en la información geográfica, la inundación de la red se hace de manera controlada. LBM se basa en un fooding tradicional pero los nodos tienen que decidir si retransmiten o no a los demás nodos según dos esquemas para determinar la zona forwarding: LMB box y LMB step.

3.1.1 LMB box

En este esquema el nodo solo reenvía el paquete cuando los nodos vecinos se encuentran dentro de la zona forwarding, que es el rectángulo mínimo que contiene el origen del paquete geocast y la zona geocast. El esquema LMB box se presenta en la figura 1.

3.1.2 LMB step

Como se muestra en la figura 2, en este esquema el nodo que recibe (A) solo reenvía el paquete cuando se encuentra más cerca, una distancia 0, del centro de la zona forwarding que el nodo que le envió (B) el paquete. De esta manera se trata de asegurar que en cada retransmisión el paquete esté más cerca de la región geocast.

3.2 Geotora

Como su nombre lo indica, está basado en el protocolo TORA y consiste en una variación de la versión anycast de TORA [22]. Se mantiene un único DAG (Directed Acyclic Graph) para todo el grupo geocast, con el fin de que cualquiera de los nodos que se encuentren en la zona geocast pueda servir como destino. El protocolo realiza un envío anycast hacia un nodo de la zona geocast. Cuando el nodo recibe el paquete de anycast, se encarga de retransmitir en modo f ooding a todos los nodos que se encuentran en su zona geocast.

3.3 Gamer

El protocolo GAMER (Geocast Adaptative Mesh Environment for Routing), propuesto en 2003 [23], es un protocolo geocast basado en la idea de crear rutas redundantes estructuradas con mallas hacia una zona geocast. Aunque responde en forma dinámica al cambio de la topología de la red y al tamaño de la zona forwarding, tiene como característica su baja respuesta en entornos de alta movilidad.

4. Resultados

Como indicadores de rendimiento de la red se tienen en cuenta:

• Porcentaje de éxito: es el porcentaje de paquetes que llegan a su destino.
• Overhead: son los paquetes de control generados por cada protocolo.
• Retardo extremo a extremo: lapso necesario para que un paquete viaje de la fuente al destino.

Para llevar a cabo la comparación se utiliza como herramienta el programa NS2, que permite plantear el uso de protocolos como el AODV y el LBM. Analizando los resultados obtenidos se observa que los protocolos reactivos presentan mejor desempeño para las redes VANETs. En relación a los proactivos [6], [9], [15] - [17], [21] se observa que el protocolo AODV es el de mejor rendimiento entre los protocolos unicast por tiempo de respuesta y menor cantidad de paquetes perdidos. Por otra parte, una comparación de protocolos geocast realizada en trabajos anteriores [19], [21] dedujo que el protocolo LBM presenta mejores características que los anteriormente evaluados.

Los resultados de la comparación entre el protocolo AODV y el protocolo LBM en circuitos urbanos de alta y baja densidad se presentan en la figura 3.

Como se puede observar en la figura 3, la comunicación se logra establecer antes de 4 segundos y se mantiene estable hasta el final del tiempo de simulación.

5. Conclusiones

Como se puede observar, los protocolos LBM presentan un mayor porcentaje de éxito, menos overhead y un menor retardo en escenarios urba-nos de alta densidad, mientras que en escenarios de baja densidad el protocolo AODV presenta un mayor porcentaje de éxito, aunque menor overhead y mayor retardo. En general, se puede decir que en el caso de escenarios de alta densidad los protocolos geocast tienen mejor rendimiento, mientras que en escenarios de baja densidad, depende de lo que se busque y del escenario que se presente, se puede elegir o un protocolo rápido como un geocast o un protocolo con un alto porcentaje de éxito como el protocolo AODV.

Referencias

[ 1]. H. Hartenstein, B. B., A. Ebner, M. Lott, M. Radimirsch, and D. Vollmer, "Hoc Wireless Networks for Inter-vehicle Communications: The Fleenet Project". In Symposium on Mobile Ad Hoc Networking and Computing, MobiHOC. New York, 2001.

[2]. IEEE. (2005), "802.11". [En línea]. Disponible en: http://standards.ieee.org/findstds/standard/802.11e-2005.html

[3]. T.A. Kosch, C. J. Adler, S. Eichler, C. Schroth, and M. Strassberger, "The Scalability Problem of Vehicular Ad Hoc Networks and How to Solve it", Wireless Communications IEEE, 2006, no. 13, pp. 22-28.

[4]. Bogotá, C.d.C.d. Observatorio de Movilidad. [en línea]. Disponible: http://camara.ccb.org.co/documentos/4419_boletin_de_accidentalidad.pdf.

[5]. M. Torrent Monero, P. Santi, and H. Hartenstein. Fair Sharing of Bandwidth in VANETs, in 2nd ACM International Workshop on Vehicular Ad Hoc Networks, 2005.

[6]. X. L. Yang, N. H. Vaidya, and F. Zhao, "A Vehicle-to-Vehicle Communication Protocol for Cooperative Collision Warning", in Mobile and Ubiquitous Systems: Networking and Services, 2004. Boston, Massachusetts, USA: Illinois University, 2004.

[7]. I. M.Calinescy, P.J. Wan, and A. Zelikovskya, Selecting Forwarding Neighbors in Wireless Ad Hoc Networks, in 2nd ACM international workshop on Vehicular ad hoc networks, 2005.

[8]. IEEE. RFC 3561. [online] Available: http://www.faqs.org/rfics/rfic3561.html

[9]. S. Jaap , M. Becler, L. Wolf, Evaluation of Routing Protocols for Vehicular Ad Hoc Networks in City Trafj c Scenarios, in 11th EUNICE Open European Summer School on Networked Applications, 2005.

[10]. M. H.Fiore, F. Filali, and C. Bonnet, "Vehicular Mobility Simulation for VANETs", in Simulation Symposium, 2007. ANSS ‘07. 40th Annual. Norfolk: IEEE, 2007.

[11]. C. E. Perkins and E. M. Royer, "Ad-hoc on-demand distance vector routing", in Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications,1999. IEEE Computer Society.

[12]. C. E.Perkins, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers. in SIGCOMM ‘94 Communications architectures, protocols and applications,1994.

[13]. Kamaljit. Lakhtaria, Patel N.Bhaskar., N. Patel , Mr. Satish G.Prajapati, and N. N. Jani, "Securing AODV for MANETs using Message Digest with Secret Key". Network Security & Its Applications (IJNSA), vol. 1, no. 3, pp. 111-116, 2009.

[14]. D. Johnson, D.A. Maltz , and Y.C. Hu, DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 2001.

[15]. Y. H., Johnson, and D. Maltz, RFC 4728 on The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4,2007. [online] Available: http://www.rfic-editor.org/rfic/rfic4728.txt

[16]. R. Kumar Jha, Suresh.V.Linkar., Dr. Upena D. Dalai, "A Performance Comparison of Routing Protocols (DSR and TORA) for Security Issue", in Mobile Ad-hoc Networks MANETs, 2010. Published by Foundation of Computer Science.

[17]. Abdul Hadi Abd Rahman, and Zuriati Ahmad Zukarnain, "Performance Comparison of AODV, DSDV and I-DSDV Routing Protocols in Mobile Ad Hoc Networks", European Journal of Scientijc Research, vol. 31, no. 4, pp. 566-576, 2009.

[18]. Young Bae Ko, and Nitin H. Vaidya., Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithms. New Orleans, LA. Department of Computer Science, Texas AM University, 1999.

[19]. Yao, E. Krohne., T. Camp. Performance Comparison of Geocast Routing Protocols for a MANET. Dept. of Math, & Comput. Sci., Colorado Sch. of Mines, Golden, CO, USA. 2004.

[20]. Young Bae Ko, and Nitin HVaidya, Location-Aided Routing (LAR) in mobile ad hoc networks, Texas AM University, no. 6, pp. 307-321, 2007.

[21]. H .Doumenc, Estudio comparativo de protocolos de encaminamiento en redes Vanet, Madrid: Universidad Politecnica de Madrid, 2008.

[22]. Y.B. Ko, and N. H. Vaidya, GeoTORA: a protocol for geocasting in mobile ad hoc networks in Network Protocols 2000.

[23]. T. Camp, and Y. Liu, "An adaptive meshbased protocol for geocast routing Parallel and Distributed Computing", Journal. Parallel and Distributed Computing, vol. 63, no. 2, pp. 197-213, 2003.