proyecto fin de máster: desarrollo de protocolo de enrutamiento

Escuela Técnica Superior de Ingeniería

Máster de Automática, Robótica y Telemática

Proyecto Fin de Máster

Desarrollo de protocolo de enrutamiento híbrido basado en

zonas para redes MANET

Estefani Vega Garabitos

Tutor: José Ramiro Martínez de Dios

Proyecto Fin de Máster: Desarrollo de protocolo de enrutamiento

híbrido basado en zonas para redes MANET.

2

Contenido

Capítulo I. Introducción ...............................................................................................................6

1.1. Introducción .........................................................................................................................6

1.2. Objetivo del proyecto ...........................................................................................................6

1.3. Estructura de la memoria .....................................................................................................7

Capítulo II. Estado del arte en protocolos de enrutamiento para redes MANET ..........................8

2.1. Introducción .........................................................................................................................8

2.2. Protocolos de enrutamiento proactivos................................................................................9

2.2.1. Vector distancia Destino-Secuenciado -Destination-Sequenced Distance Vector (DSDV) .......... 11

2.2.2. Protocolo de enrutamiento inalámbrico -Wireless Routing Protocol (WRP) .............................. 12

2.2.3 Enrutamiento de estado de enlace optimizado -Optimized Link State Routing (OLSR) ............... 13

2.2.4. El enrutamiento jerárquico optimizado de estado de enlace -The Hierarchical Optimized Link

State Routing (HOLSR) ....................................................................................................................... 14

2.3. Protocolos de enrutamiento reactivos ................................................................................15

2.3.1. Protocolo vector distancia bajo demanda -Ad hoc On-demand Distance Vector (AODV)........... 16

2.3.2. Enrutamiento de origen dinámico -Dynamic Source Routing (DSR) ........................................... 17

2.3.3. Algoritmo de enrutamiento temporal ordenado -Temporally ordered routing algorithm (TORA)

.......................................................................................................................................................... 18

2.3.4. Protocolo de enrutamiento QoS bajo demanda de redes ad hoc -Ad hoc QoS on-demand routing

(AQOR) .............................................................................................................................................. 19

2.4. Protocolos de enrutamiento híbridos .................................................................................20

2.4.1. Protocolo de enrutamiento basado en zonas -Zone Routing Protocol (ZRP) .............................. 20

2.4.2. Enrutamiento de estado de ojo de pez -Fisheye state routing (FSR) .......................................... 22

2.5. Protocolos basados en posición. .........................................................................................23

2.5.1 Enrutamiento de localización asistida -Location-aided routing (LAR) ......................................... 23

2.5.2. Perímetro de enrutamiento codiciado sin estado -Greedy Perimeter Stateless Routing (GPSR) 24



3

2.6. Conclusiones ......................................................................................................................25

Capítulo III. Protocolo de enrutamiento basado en zonas ..........................................................27

3.1. Introducción .......................................................................................................................27

3.2. Descripción del protocolo de enrutamiento basado en zonas .............................................27

3.3. Protocolo de enrutamiento intrazona.................................................................................28

3.3.1. La noción de una zona de enrutamiento de intrazona .............................................................. 29

3.3.2. Descubrimiento de vecinos en el protocolo de enrutamiento intrazona ................................... 31

3.4. Protocolo de enrutamiento interzona ................................................................................32

3.5. Mecanismos de detección de consulta del protocolo de enrutamiento basado en zonas ..34

3.5.1. Protocolo de resolución de bordercast -Bordercast Resolution Protocol (BRP) ......................... 36

3.5.2. Mecanismo de finalización anticipada- Early Termination (ET).................................................. 36

3.5.3. Procesamiento de retardo aleatorio -Random query-processing delay (RQPD) ......................... 38

3.6. Determinación de la ruta mediante el protocolo de enrutamiento basado en zonas ..........39

3.6.1. Escenario de zonas contiguas ................................................................................................... 39

3.6.2. Escenario de zonas no contiguas .............................................................................................. 42

3.7. Conclusiones ......................................................................................................................44

Capítulo IV. Protocolo de enrutamiento intrazona de PHEZ .......................................................46

4.1. Introducción .......................................................................................................................46

4.2. Descripción del protocolo de enrutamiento intrazona de PHEZ ..........................................46

4.3. Algoritmo del protocolo de enrutamiento intrazona de PHEZ .............................................47

4.4. Escenarios de funcionamiento del protocolo de enrutamiento intrazona de PHEZ .............52

4.4.1. Escenario 1 .............................................................................................................................. 52

4.4.2. Escenario 2: ............................................................................................................................. 54

4.4.3. Escenario 3 .............................................................................................................................. 55

4.4.4. Escenario 4 .............................................................................................................................. 57



4

4.5. Ventajas del algoritmo implementado ................................................................................63

4.6. Conclusiones ......................................................................................................................63

Capítulo V. Protocolo de enrutamiento interzona de PHEZ ........................................................65

5.1. Introducción .......................................................................................................................65

5.2. Descripción del protocolo de enrutamiento interzona de PHEZ ..........................................65

5.3. Algoritmo del protocolo de enrutamiento interzona de PHEZ .............................................67

5.4. Escenarios de funcionamiento del protocolo de enrutamiento interzona de PHEZ .............71

5.4.1. Escenario 1 .............................................................................................................................. 71

5.4.2. Escenario 2 .............................................................................................................................. 73

5.4.3. Escenario 3 .............................................................................................................................. 75

5.5. Ventajas del algoritmo implementado ................................................................................77

5.6. Conclusiones ......................................................................................................................77

Capítulo VI. Simulaciones ..........................................................................................................79

6.1. Introducción .......................................................................................................................79

6.2. Generación de escenarios ..................................................................................................79

6.2.1. Lectura y procesado de los resultados ...................................................................................... 80

6.3. Comportamiento ante diferentes configuraciones .............................................................80

6.3.1. Configuración 1: Caso Favorable .............................................................................................. 81

6.3.2. Configuración 2: Caso intermedio ............................................................................................ 83

6.3.3. Configuración 3: Caso desfavorable.......................................................................................... 85

6.3.4. Comparación............................................................................................................................ 87

6.4. Robustez ............................................................................................................................89

6.4.1. Robustez frente a la velocidad de los nodos ............................................................................. 89

6.4.2. Robustez frente al número de nodos........................................................................................ 91

6.4.3. Robustez frente al tráfico de aplicación .................................................................................... 93



5

6.5. Comparación del protocolo implementado con otros protocolos .......................................94

6.5.1. Robustez de los protocolos AODV, OSLR y PHEZ ....................................................................... 95

6.7. Conclusiones .................................................................................................................... 100

Capítulo VII. Conclusiones y trabajo futuro .............................................................................. 102

7.1. Conclusiones .................................................................................................................... 102

7.2. Trabajo futuro .................................................................................................................. 103

Capítulo VIII. Referencias ........................................................................................................ 105



Introducción 6

Capítulo I. Introducción

1.1. Introducción

El presente proyecto se presenta como Trabajo fin de Máster, del Máster de Automática, Robótica y Telemática, impartido por la Escuela Superior de Ingenieros de Sevilla.

A continuación se describen los objetivos a alcanzar en el proyecto realizado así como la estructura de ésta memoria.

1.2. Objetivo del proyecto

El objetivo principal de este proyecto es desarrollar un protocolo de enrutamiento para establecer la comunicación inalámbrica entre una red de robots móviles, este protocolo debe de cumplir con los siguientes requisitos:

Ser robusto ante el tráfico de la aplicación.

Ser robusto ante cambios de condiciones del canal radio eléctrico.

Ser robusto ante cambios de posición. Al haber cambios en la topología de la red, por razones de crecimiento, reconfiguración o falla, la información conocida acerca de la red también debe cambiar. La información conocida debe reflejar una visión exacta y coherente de la nueva topología.

Tener alta calidad de servicio en el envío de paquetes.

Tener bajo retardo de envío de los paquetes (disminuyendo escalas y ancho de banda) y maximizar el rendimiento total de la red.

Proporcionar la ruta con mínimo número de saltos y descartar las rutas que ya no son válidas.

Ser escalable, con relación al tamaño de la red. Debe tener la capacidad de modificar su configuración o su tamaño, para ajustarse a los cambios. El protocolo debe de mostrar su destreza para operar bajo el incremento continuo de trabajo con fluidez.



Introducción 7

1.3. Estructura de la memoria

La memoria de este proyecto está estructurada en siete capítulos, que se describen brevemente a continuación.

En el capítulo 2, se realiza un repaso de los diferentes tipos de protocolos de enrutamiento que existen para redes móviles, así como las ventajas y desventajas que ofrecen cada uno.

En el capítulo 3, se realiza un estudio del protocolo de enrutamiento basado en zonas, sus principales características, ventajas, desventajas, se describen sus protocolos internos, además se somete a diferentes escenarios de funcionamiento para comprobar su eficiencia.

En el capítulo 4, se muestra de manera detallada el algoritmo implementado del protocolo de enrutamiento intrazona de PHEZ. Una vez se haya detallado paso por paso el algoritmo implementado, se presentan diferentes escenarios, donde se demuestra el funcionamiento del algoritmo. De igual manera, en este capítulo, se presentan las ventajas de la implementación desarrollada del protocolo de enrutamiento intrazona.

En el capítulo 5, se desarrolla el algoritmo implementado del protocolo de enrutamiento interzona de PHEZ, una vez se haya detallado paso por paso el algoritmo desarrollado, se presentan diferentes escenarios, donde se demuestra el funcionamiento del algoritmo. De igual manera, en este capítulo, se presentan las ventajas de la implementación desarrollada del protocolo de enrutamiento interzona.

En el capítulo 6, se presentan los resultados de las simulaciones del protocolo desarrollado, ante diferentes configuraciones de nodos móviles. Se analizan los resultados obtenidos en tres tipos de pruebas: comportamiento del protocolo en diferentes configuraciones, robustez ante variaciones de parámetros del escenario y comparación del protocolo desarrollado con otros métodos.

En el capítulo 7, se presentan las conclusiones obtenidas de este proyecto y se enumeran los trabajos futuros a realizar.



Estado del arte en protocolos de enrutamiento para redes MANET 8

Capítulo II. Estado del arte en protocolos de

enrutamiento para redes MANET

2.1. Introducción

MANET (Mobile ad hoc Network), a veces llamada una red de malla móvil, es una red de auto-configuración de los dispositivos móviles, conectados por enlaces inalámbricos. En otras palabras, una MANET es una red de nodos móviles que desean comunicarse entre sí, pero no tienen ninguna infraestructura fija ni una topología predeterminada de enlaces inalámbricos, [Lee, 2009].

Cada nodo en una MANET es libre de moverse independientemente en cualquier dirección, y por lo tanto va a cambiar sus enlaces a otros dispositivos con frecuencia. El principal desafío en la construcción de una MANET es equipar a cada dispositivo de forma que se pueda mantener la información continua, que es necesaria para enrutar el tráfico adecuadamente, [Lee, 2009].

Las redes tienen una amplia gama de aplicaciones potenciales, estas redes son adecuadas para su uso en situaciones en las que la infraestructura no está disponible o no es de confianza, como una red de comunicación para los soldados militares en un campo, una red móvil de ordenadores portátiles en una conferencia, oficinas temporales en una casa de campaña, redes de sensores inalámbricos para la investigación biológica, las redes sociales móviles como Facebook, MySpace y Twitter, y las redes de malla móviles para los dispositivos Wi-Fi, [Lee, 2009].

La ausencia de una infraestructura fija en una MANET plantea varios tipos de retos. Uno de los desafíos más importantes entre ellos es el enrutamiento, i.e. el proceso de selección de rutas a lo largo de una red para enviar los paquetes de datos.

Un protocolo de enrutamiento ad hoc es una convención o estándar, que controla cómo los nodos deciden en qué dirección encaminar paquetes entre los dispositivos en una red ad-hoc móvil. En las redes ad hoc, los nodos no empiezan a familiarizarse con la topología de su red; en cambio, tienen que descubrirlo. La idea básica es que un nuevo nodo puede anunciar su presencia y debe escuchar los anuncios emitidos por los nodos vecinos, cada nodo se entera de los nodos cercanos y la forma de llegar a ellos, y puede anunciar que se puede llegar a ellos también, [Boukerche et al., 2011].




A lo largo de los años se han desarrollado una alta variedad de protocolos de enrutamiento para MANET, los cuales pueden clasificarse globalmente como protocolos proactivos, reactivos e híbridos. En la figura 1 se muestra un esquema de los principales protocolos desarrollados.

Figura 1. Clasificación de los protocolos de enrutamiento de las redes ad hoc,[Boukerche et al., 2011]

2.2. Protocolos de enrutamiento proactivos

Cada protocolo de enrutamiento dinámico por lo general necesita mantener información precisa en sus tablas de enrutamiento. Los protocolos proactivos intentan mantener la información de rutado a todos los demás nodos de la red consistente y actualizada. Por lo tanto, si un nodo necesita una ruta la obtiene inmediatamente.




Como mantienen la información en tablas, también se los conoce como table-driven. Estas tablas son enviadas periódicamente a todos sus vecinos. Cuando la topología sufre una modificación (un nodo se incorpora, deja de formar parte o cambia de posición), se inunda la red con mensajes de modo broadcast para actualizar las tablas. Aún cuando no sean utilizadas, las rutas a todos los destinos posibles se obtienen y mantienen en cada uno de los nodos, [Robles et al., 2010].

Los algoritmos proactivos emplean estrategias de enrutamiento clásicas tales como enrutamiento vector-distancia o enrutamiento enlace-estado. Mantienen información de

enrutamiento acerca de las trayectorias disponibles en la red aunque estas trayectorias no estén siendo usadas.

Ventajas:

Las rutas a todos los destinos dentro de la red son conocidas y mantenidas antes de su uso, de esta manera si se quiere establecer comunicación con un nodo se puede acceder a la tabla de enrutamiento para buscar la manera de llegar al destino deseado, sin necesidad de inundar la red con mensajes de petición de ruta.

Una vez que las tablas de enrutamiento se configuran, a continuación, la transmisión de datos (paquetes) será tan rápida y fácil como en las redes de cable tradicionales.

Desventajas:

El principal inconveniente de estos enfoques es que el mantenimiento de estas trayectorias o caminos no utilizados puede ocupar una parte significativa del ancho de banda disponible si la topología de la red cambia con frecuencia, [Lee, 2009].

Reacción lenta en la reestructuración de la red y fallos de nodos individuales.

En la tabla 1 se muestran los principales protocolos de enrutamiento proactivos existentes y sus principales características. Seguidamente se describen los algoritmos proactivos más relevantes desarrollados en la literatura.




Protocolo Tablas Intervalo de actualización Nodo crítico Métrica de enrutamiento

SC

DSDV 2 Periódico - SP L

R-DSDV 2 Probabilístico - SP L

OLSR 3 Periódico - SP H

HOLSR 3 Periódico - SP H

CGSR 2 Periódico Clusterhead SP L

WRP 4 Periódico - SP L

GSR 3 Periódico sólo con los vecinos

- SP L

STAR 1 Sólo en eventos específicos

- SP L

QOLSR 3 Periódico - Retardo & HC H

Métrica de enrutamiento: SP= camino más corto; HC= Número de saltos. SC= Sobrecarga de comunicación[alta= H; Media=M; Baja=L]

Tabla 1. Protocolos de enrutamiento proactivos, [Boukerche et al., 2011]

2.2.1. Vector distancia Destino-Secuenciado -Destination-Sequenced Distance

Vector (DSDV)

DSDV [Boukerche et al., 2001], es un esquema de la tabla de enrutamiento para redes móviles ad hoc basado en el algoritmo de Bellman-Ford. La principal contribución del algoritmo era resolver el problema de bucle de enrutamiento. La información de enrutamiento se distribuye entre los nodos mediante el envío de copias completas con poca frecuencia y pequeños cambios incrementales con mayor frecuencia.

Funciona de la siguiente manera, cada nodo calcula la distancia entre el mismo y todos los demás dentro de un mismo sistema autónomo y almacena esta información en una tabla. Cada nodo envía su tabla a todos los nodos vecinos. Cuando un nodo recibe las tablas de distancia de sus vecinos, este calcula la ruta más corta a los demás nodos y actualiza su tabla para reflejar los cambios. Cada camino viene etiquetado con un número de secuencia, que da una indicación temporal sobre la validez de aquel camino: a números de secuencia más altos, corresponden caminos más fiables. Cuando dos caminos tienen el mismo número de secuencia viene elegido aquel que tiene el menor costo (por ejemplo el que menor número de saltos tenga que atravesar). En caso de que un nodo notase que un trayecto hacia un destino no funciona, asigna al número de salto un valor alto (que significa infinito) y al número de secuencia un número impar. Un número de secuencia identificado con un número impar señala que aquel camino es




inalcanzable mientras que, por el contrario, un número par indica que el destino sí es alcanzable.

Ventajas:

DSDV fue uno de los primeros algoritmos desarrollados. Es muy adecuado para la creación de redes ad hoc con pequeño número de nodos.

Desventajas:

Poco escalable.

DSDV requiere una actualización periódica de sus tablas de enrutamiento, lo cual consume energía de la batería y una pequeña cantidad de ancho de banda incluso cuando la red está inactiva.

Cada vez que la topología de la red cambia, se hace necesario la asignación de un nuevo número de secuencia este número se utiliza para dar una indicación temporal sobre la validez de aquel camino, por lo que, DSDV no es adecuado para redes altamente dinámicas, [Lee, 2009].

2.2.2. Protocolo de enrutamiento inalámbrico -Wireless Routing Protocol (WRP)

WRP [Lee, 2009], utiliza una versión mejorada del protocolo de enrutamiento de vector distancia, que utiliza el algoritmo de Bellman-Ford para el cálculo de rutas. Debido a la naturaleza móvil de los nodos dentro de la MANET, el protocolo introduce mecanismos que reducen bucles en la ruta y aseguran los intercambios de mensajes fiables.

Este protocolo emplea un método único de mantenimiento de la información con respecto a la ruta más corta a cada nodo de destino y el penúltimo salto en la ruta del nodo de acceso a cada nodo de destino en la red. Dado que WRP, como DSDV, mantienen actualizado el estado de la red, cada nodo tiene una ruta de fácil acceso a todos los nodos de destino en la red. Se diferencia de DSDV en el mantenimiento de la tabla y en los procedimientos de actualización. Mientras DSDV mantiene sólo una tabla de topología, WRP utiliza un conjunto de tablas para mantener información más precisa.

Las tablas que se mantienen por un nodo son los siguientes: tabla de distancia (DT), la tabla de enrutamiento (RT), tabla de costo del enlace (LCT), y una lista de retransmisión de mensaje (LMR), [Lee, 2009].




Ventajas:

WRP tiene la misma ventaja que el DSDV. Además, tiene una convergencia más rápida e implica un menor número de actualizaciones de la tabla.

Desventajas:

La complejidad de mantenimiento de varias tablas exige mayor empleo de memoria y una mayor potencia de procesamiento de los nodos de la red ad hoc inalámbrica. La actualización de entradas de la tabla es casi la misma que la de DSDV y por lo tanto no es adecuada para una red muy grande, muy dinámica, ya que sufre de escalabilidad limitada.

2.2.3 Enrutamiento de estado de enlace optimizado -Optimized Link State

Routing (OLSR)

OLSR [Clausen et al., 2001], es un protocolo de enrutamiento IP optimizado para redes ad-hoc móviles, que también se puede utilizar en otras redes inalámbricas ad-hoc, utiliza mensajes HELLO y control de topología para descubrir y luego difundir información del estado de los enlaces de toda la red móvil. Estas optimizaciones se centran en seleccionar nodos especiales llamados relevadores multipunto (MPR). En primer lugar, sólo pueden reenviar mensajes los nodos MPR durante el proceso de inundación de información de la ruta, lo que reduce sustancialmente el número total de mensajes enviados.

Además, la información de estado de enlace se genera sólo por los nodos MPR, reduciendo aún más la cantidad de datos que necesita ser diseminada. Por último, los MPR podrían optar por informar sólo los vínculos entre ellos y sus selectores MPR. Esta última técnica de información parcial de estado de enlace es un alejamiento del enfoque tradicional de los protocolos de estado de enlace, que retransmiten en la difusión el estado completo del enlace, [Lee, 2009].

Los nodos MPR tienen como objetivo reducir las retransmisiones de la misma región. Cada nodo selecciona un conjunto de nodos MPR vecinos. Los vecinos del nodo que no son MPR procesan los paquetes pero sólo los MPR pueden reenviar los paquetes.

Ventajas:

Las rutas a todos los destinos dentro de la red son conocidas y mantenidas antes de su uso. Es una ventaja ya que no hay retraso de descubrimiento de ruta asociada a la búsqueda de una nueva ruta, [Lee, 2009].




La sobrecarga de enrutamiento generada, que generalmente es mayor que la de un protocolo reactivo, no aumenta con el número de rutas que se utilizan.

Desventajas:

Siendo un protocolo de enlace-estado, OLSR requiere una cantidad razonable de ancho de banda.

OLSR no incluye ninguna disposición para la detección de la calidad del enlace; simplemente se asume que un enlace está activo si un número de paquetes de saludo se han recibido recientemente, provocando esto pérdida de paquetes.

2.2.4. El enrutamiento jerárquico optimizado de estado de enlace -The

Hierarchical Optimized Link State Routing (HOLSR)

Existen redes en las que algunos nodos tienen los recursos significativamente más altos (rango de transmisión, ancho de banda, la antena direccional y así sucesivamente). Los autores de este protocolo notan que los protocolos de enrutamiento tradicionales, no pueden explotar de manera eficiente las capacidades de los nodos con altos recursos. Para este escenario, los autores proponen el protocolo HOLSR que se basa en el protocolo OLSR introduciendo una arquitectura jerárquica con múltiples redes ad hoc en niveles lógicos distintos dentro de la red, [Villasenor et al., 2005].

La red HOLSR organiza los nodos de la topología en tres niveles, en función de sus capacidades. Los nodos de baja capacidad están en la topología 1, tienen una sola interfaz de red inalámbrica y se comunican con los nodos cercanos. Los nodos en el nivel de topología 2 se supone que tienen dos interfaces inalámbricas, posiblemente contando con diferentes estándares inalámbricos, que les permite comunicarse con nodos en los niveles de topología 1 y 2. Por último, los nodos a nivel de topología 3 son los más poderosos y pueden tener hasta tres interfaces inalámbricas, que les permite comunicarse con los nodos de la topología 1, 2 y 3.

Ventajas:

HOLSR organiza la red en grupos jerárquicos. Esta arquitectura permite reducir el cálculo del costo de enrutamiento, es decir, en caso de que falle un enlace sólo los nodos dentro del mismo grupo tienen que calcular de nuevo su tabla de enrutamiento, mientras que los nodos en los diferentes grupos no se ven afectados.




HOLSR permite la formación de varios grupos de nodos y, a diferencia de OLSR, los nodos dentro de HOLSR pueden intercambiar mensajes HELLO y de control de topología, exclusivamente dentro de cada grupo. Esta restricción reduce el tráfico dentro de la red.

Desventajas:

HOLSR fue diseñado sin medidas de seguridad. Por lo tanto, es vulnerable a ataques de seguridad.

2.3. Protocolos de enrutamiento reactivos

Los protocolos de enrutamiento reactivos no mantienen rutas. Las construyen bajo demanda. Inundando la red con paquetes de solicitud de ruta. La ruta se crea a través de un procedimiento de descubrimiento de ruta que implica la inundación de la red, con paquetes de petición de ruta. Para comenzar se inundan los vecinos inmediatos de la fuente. Una vez que una o múltiples rutas se forman se obtiene el destino. Así el proceso de descubrimiento de ruta llega a su fin. Un procedimiento de mantenimiento de ruta conserva la continuidad de la ruta para el intervalo de tiempo que se necesita por la fuente, reduciendo así la carga en la red cuando sólo un pequeño subconjunto de todas las rutas disponibles está en uso. Sin embargo, aún tienen algunas limitaciones inherentes. Primero, desde rutas que sólo se mantienen mientras están en uso, esto se requiere típicamente para realizar un descubrimiento de ruta antes que los paquetes puedan ser intercambiados. Esto representa un retardo para el primer paquete en ser transmitido. Segundo, a pesar de que el mantenimiento de las rutas de algoritmos reactivos se limita a las rutas actualmente en uso, todavía podría generar una cantidad significativa de tráfico de la red cuando la topología de la red cambia frecuentemente. Finalmente, es probable que los paquetes en ruta hacia el destino se pierdan si la ruta de destino cambia, [Boukerche et al., 2011].

Ventajas:

Evita la sobrecarga originada por el mantenimiento de la tabla de enrutamiento global como en los protocolos proactivos.

Reacción rápida para la reestructuración de la red y el fallo de un nodo.

Desventajas:

Tiempo de alta latencia en la búsqueda de ruta.




Inundaciones en exceso puede llevar a la obstrucción de la red.

En la tabla 3 se muestran los diferentes tipos de protocolos de enrutamiento reactivos y sus principales características:

Tabla 3. Protocolos de enrutamiento reactivo, [Boukerche et al., 2011]

2.3.1. Protocolo vector distancia bajo demanda -Ad hoc On-demand Distance

Vector (AODV)

AODV [Perkins y Royer, 1999], es un protocolo de enrutamiento de tipo reactivo basado en el algoritmo Vector Distancia.

Una característica fundamental del protocolo es que los nodos destino de un trayecto, antes de proporcionar información de direccionamiento, crean un número de secuencia de destino, que proporciona a los nodos un instrumento para evaluar cuanto se ha actualizado un determinado recorrido, evitando la formación de lazos en el camino de enrutamiento. Un nodo fuente que deba elegir entre varios caminos hacia un cierto destino, elegirá aquel caracterizado por el número de secuencia mayor, correspondiente a una información de enrutamiento mas reciente. Además, el protocolo soporta el enrutamiento multidifusión. Este protocolo usa




mensajes particulares llamados RREQ (Route Request), RREP (Route Replies) y RERR (Route Errors) que son enviados y recibidos mediante el protocolo UDP.

Un nodo origen realiza la búsqueda para enviar un paquete de datos a un nodo destino, comprueba su tabla de ruta para ver si tiene una ruta válida hacia el nodo de destino. Si existe una ruta, simplemente reenvía los paquetes al siguiente salto en el camino hacia el destino, por otro lado, si no hay una ruta en la tabla, el nodo de origen inicia un proceso de descubrimiento de ruta. Se emite un paquete de solicitud de ruta (RREQ a sus vecinos inmediatos y aquellos nodos lo transmiten además a sus vecinos hasta que la solicitud alcanza un nodo intermedio con una ruta hacia el destino o el propio nodo de destino, [Perkins y Royer,1999].

Ventajas:

Las rutas se establecen sobre la demanda y los números de secuencia de destino se utilizan para encontrar las últimas rutas hacia el destino. El retraso en la configuración de la conexión es menor. No crea ningún tráfico adicional para la comunicación a lo largo de los vínculos existentes. Además, el enrutamiento vector distancia es simple y no requiere mucha memoria o cálculo, [Johnson et al., 2001].

Desventajas:

AODV requiere más tiempo para establecer una conexión y la comunicación inicial para establecer una ruta, por esta razón es más pesado que otros enfoques.

Todavía tiene posible latencia antes de iniciar la transmisión de datos.

2.3.2. Enrutamiento de origen dinámico -Dynamic Source Routing (DSR)

DSR [Johnson et al., 2001], es un protocolo de enrutamiento que es similar a AODV en el que se forma una ruta bajo demanda cuando se hace una petición. Sin embargo, utiliza el enrutamiento de origen en lugar de depender de la tabla de enrutamiento en cada dispositivo intermedio.

Este protocolo se compone de dos partes: mecanismo de descubrimiento de ruta, mecanismo de mantenimiento de ruta. Estos dos mecanismos le permiten al protocolo conocer el estado de los nodos únicamente en el momento en que se hace la transmisión de paquetes de información. Es un protocolo que trabaja "al vuelo" ya que sólo verifica el estado de las rutas de enrutamiento en el momento. Puede usar u omitir tantos nodos como sea necesario o conveniente para enviar los paquetes a su destino, en caso de que dichos paquetes sean




rebotados, el protocolo se encarga de informarlo. Por tanto es susceptible a posibles fallas en los nodos, por lo que, este protocolo también lleva un registro de errores que se construye constantemente cada vez que ocurre un error de transmisión, reenvío, o recepción de paquetes que le permite tomar decisiones rápidas para cambiar la ruta rápidamente.

Ventajas:

Requiere menos requisitos de memoria en cada nodo ya que no es necesario una tabla de enrutamiento completa.

Baja sobrecarga porque no es necesario ningún mensaje periódico de actualización.

Los nodos no necesitan informar continuamente a los vecinos que están todavía en funcionamiento.

Desventajas:

El mecanismo de mantenimiento de ruta no repara localmente un vínculo roto.

El retardo de conexión es más alto que en protocolos basados en tabla.

Posible latencia de transmisión debido al enfoque reactivo.

A pesar de que el protocolo funciona bien en entornos estáticos y de baja movilidad, el rendimiento se degrada rápidamente con el aumento de la movilidad.

2.3.3. Algoritmo de enrutamiento temporal ordenado -Temporally ordered

routing algorithm (TORA)

TORA [Park y Corson, 1997], se basa en ofrecer al nodo origen múltiples trayectos para alcanzar al destino. Este protocolo fue propuesto para redes muy dinámicas.

Cuando se detecta un cambio en la topología se generan mensajes de control en un pequeño conjunto de nodos cercanos al cambio. Para utilizar estas funciones básicas, definen tres tipos de paquetes de control: query (QRY), update (UPD) y clear (CLR). En las fases de creación y mantenimiento, el paquete QRY se utiliza como petición y el paquete UPD se utiliza como respuesta. Cuando un nodo necesita descubrir una ruta hacia un destino se hace un envío broadcast de mensajes QRY. El destino o un nodo que posea una ruta válida hacia el destino le responde con un mensaje UPD. El paquete CLR se utiliza para eliminar las rutas inválidas




cuando un nodo es inaccesible. Las tres funciones básicas del protocolo son la creación de rutas, mantenimiento de rutas y la supresión de rutas.

Ventajas:

TORA es un protocolo de enrutamiento adaptativo.

La principal fortaleza del protocolo es su enfoque para el manejo de los fallos de enlace. La reacción de TORA ante fallos es optimista invierte los enlaces que han fallado para volver a colocar una ruta alternativa.

Desventajas:

Presenta problemas de escalabilidad.

2.3.4. Protocolo de enrutamiento QoS bajo demanda de redes ad hoc -Ad hoc

QoS on-demand routing (AQOR)

Para proporcionar calidad de servicio en las redes ad hoc, es muy importante resolver el compromiso entre garantizar los requerimientos necesarios y una gestión eficiente de los recursos disponibles. Con el objeto de proporcionar la calidad demandada por la gran mayoría de las aplicaciones actuales (aplicaciones multimedia y en tiempo real, con elevadas restricciones tanto de ancho de banda como de retardo), han surgido muchas propuestas de enrutamiento con calidad de servicio.

Que tratan de proporcionar rutas estables entre ambos extremos de la comunicación garantizando los requerimientos especificados (tasa de error, retardo, ancho de banda) durante la transmisión completa. No obstante, la complejidad de dichas redes presenta todavía una amplia problemática por resolver.

AQOR es un protocolo de enrutamiento bajo demanda permitiendo el soporte para calidad de servicio (QoS – Quality of Service) en términos de ancho de banda y retardo de extremo a extremo (end to end). El mecanismo AQOR estima los requerimientos de retardo de extremo a extremo y de ancho de banda y usa estos parámetros para la admisión de recursos y las decisiones de reserva. AQOR integra descubrimiento de ruta bajo demanda, señalando las funciones de las reservas de recursos, y salto por salto de enrutamiento para proporcionar soporte de QoS en redes ad hoc. El mantenimiento de ruta se lleva a cabo mediante el envío de mensajes HELLO periódicos.




Ventajas:

Los paquetes tienen un parámetro de tiempo de vida (TTL) que detiene los paquetes para que no viajen innecesariamente por toda la red, para reducir aún más la sobrecarga.

Desventajas:

La complejidad de este protocolo presenta todavía una amplia problemática por resolver.

2.4. Protocolos de enrutamiento híbridos

Este tipo de protocolos combina las ventajas del enrutamiento proactivo y reactivo, logrando alcanzar un rendimiento general más alto.

2.4.1. Protocolo de enrutamiento basado en zonas -Zone Routing Protocol (ZRP)

En ZRP [Beijar, 2002], la red se divide en zonas de enrutamiento que se superponen, las cuales pueden usar protocolos independientes dentro y entre cada zona. ZRP se considera como un protocolo híbrido debido a que combina algoritmos proactivos y reactivos para mantener las tablas de rutas válidas sin causar un excesivo sobre-procesamiento. La comunicación dentro de una zona específica se realiza a través del protocolo de enrutamiento IARP (Intrazone Routing Protocol), el cual proporciona descubrimiento de vecinos directamente de forma efectiva (enrutamiento proactivo).

La comunicación entre diferentes zonas, es realizada por el protocolo de enrutamiento IERP (Interzone Routing Protocol), el cual proporciona capacidad de enrutamiento entre nodos que deben de comunicarse entre zonas (enrutamiento reactivo).

IERP está basado en un mecanismo de distribución de mensajes conocido como "Bordercast Resolution Protocol" (BRP). BRP permite que las consultas sean dirigidas fuera de la red local y hacia regiones de la red que no hayan sido cubiertas por la consulta. El proceso de enrutamiento reactivo se divide en dos fases: la fase de solicitud de ruta y la fase de respuesta de ruta. En la solicitud de ruta, el nodo origen envía un mensaje de solicitud de ruta a sus nodos periféricos (que en la literatura británica son llamados bordercasting) usando BRP. BRP es el protocolo responsable de reenviar mensajes de solicitud de ruta a los nodos periféricos del nodo periférico. Si el receptor de un mensaje de solicitud de ruta conoce el destino, responde enviando un mensaje de respuesta de ruta de regreso al nodo origen. De lo contrario, se




continúa el proceso por bordercasting. El proceso bordercasting consiste en una vez el nodo periférico ha recibido un mensaje de solicitud de ruta y no encuentra el nodo destino dentro de su red, debe de reenviar el mensaje a sus nodos periféricos. De esta manera, la solicitud de ruta se extiende por toda la red. Si un nodo recibe varias copias de la misma solicitud de ruta, éstas se consideran como redundantes y se descartan.

El mensaje de respuesta de solicitud de ruta se envía por cualquier nodo que puede proporcionar una ruta hacia el nodo origen.

En la figura 2 podemos ver la arquitectura de ZRP, que se divide en tres módulos IARP, IERP y BRP este último ofrece dos métodos de detección de consulta: QD1 y QD2. En primer lugar, los nodos que transmiten la consulta son capaces de detectar la consulta (QD1). En segundo lugar, en las redes de un sólo canal, es posible escuchar el tráfico de otros nodos dentro de la cobertura de radio (QD2), [Haas y Pearlman, 2001].

Consulta de ruta Respuesta de ruta Error de ruta, etc.

Figura 2. Arquitectura del protocolo ZRP, [Haas, Pearlman ,2001]

Ventajas:

Reduce la sobrecarga de los protocolos proactivos.

Reduce la latencia de los protocolos reactivos.

IP

Localmente proactivo protocolo

de enrutamiento intrazona

(IARP)

Globalmente reactivo protocolo

de enrutamiento de interzona

(IERP)

Bordercasting

(BRP)




Puede usar una o multi trayectorias.

Desventajas:

Radio de la zona óptima se determina para cada situación.

Alta tensión para los nodos intermedios en fallo de enlace.

2.4.2. Enrutamiento de estado de ojo de pez -Fisheye state routing (FSR)

FSR [Pei et al., 2000], utiliza la técnica de “ojo de pez”, propuesta por Kleinrock y Stevens, para reducir la sobrecarga de enrutamiento. El principio básico de esta técnica es la propiedad de los ojos de un pez que pueden capturar información de los píxeles con mayor precisión cerca del punto focal de su ojo. Esta precisión disminuye con un aumento en la distancia desde el centro del punto focal. Esta propiedad se traduce en el enrutamiento en redes inalámbricas ad hoc, en que un nodo mantiene información precisa acerca de los nodos en su topología local, y no la información de manera precisa, acerca de los nodos que se encuentran más lejos, la exactitud de la información de la red disminuye al aumentar la distancia.

Cada nodo mantiene un mapa de topología local de las rutas más cortas que se intercambia periódicamente entre los nodos. Este enfoque hace FSR un protocolo jerárquico implícito, cada nodo mantiene tabla de sus vecinos, tabla de la topología, tabla del próximo salto y una tabla de distancia.

Ventajas:

La idea del alcance de niveles múltiples empleado por FSR, reduce significativamente el ancho de banda consumido por los paquetes de actualización de estado de enlace. Por lo tanto, este protocolo es adecuado para redes ad hoc grandes y altamente móviles.

Desventajas:

La elección del número de saltos asociados con cada nivel de ámbito, tiene una influencia significativa en el rendimiento del protocolo en diferentes valores de movilidad, y por lo tanto, debe elegirse cuidadosamente.




2.5. Protocolos basados en posición.

Los protocolos de enrutamiento basado en posición eliminan algunas de las limitaciones de los algoritmos de enrutamientos basado en topología usando información adicional. Requieren información de la posición física de los nodos disponibles que están participando. Comúnmente cada nodo determina su propia posición a través del uso de GPS o algún otro tipo de dispositivo de posicionamiento. La decisión de enrutamiento en cada nodo se basa entonces en la posición del destino contenida en el paquete y la posición de los vecinos del nodo de reenvío, [Mauve y Widmer, 2001].

Ventajas:

El enrutamiento basado en posición soporta la entrega de paquetes a todos los nodos en una región geográfica determinada de una manera natural.

No requiere establecimiento o mantenimiento de rutas.

Los nodos no tienen que almacenar tablas de enrutamiento.

Desventajas:

Con una mayor movilidad, el intervalo de enrutamiento debe reducirse para mantener las tablas de enrutamiento hasta a la fecha, sin embargo, esto se traduce en una mayor sobrecarga de control.

2.5.1 Enrutamiento de localización asistida -Location-aided routing (LAR)

El protocolo LAR [Ko y Vaidya, 2000], utiliza la información de ubicación para minimizar el espacio de búsqueda para el descubrimiento de ruta hacia el nodo de destino. LAR tiene como objetivo reducir la sobrecarga de enrutamiento para el descubrimiento de ruta y utiliza el Sistema de Posicionamiento Global (GPS) para obtener la información de ubicación de un nodo, [Ko y Vaidya,2000].

La idea detrás del uso de la información de ubicación para enrutar paquetes es muy sencilla y eficaz. Una vez que el nodo de origen sabe la ubicación del nodo de destino y también tiene alguna información de sus características de movilidad, tales como la dirección y velocidad de movimiento del nodo de destino, la fuente envía las solicitudes a los nodos sólo en ''La zona de espera'' del nodo de destino. Si el nodo de origen no tiene ninguna información sobre la velocidad y la dirección del nodo de destino, toda la red se considera como la zona de espera, [Ko y Vaidya,2000].




La manera en cómo funciona este protocolo es, se supone un nodo fuente el cual calcula la distancia entre sí mismo y el nodo destino sobre la base de las coordenadas GPS e incluye estos valores dentro de los paquetes de petición de ruta, un nodo intermediario recibe esta información y calcula su distancia hasta el destino. Si su distancia desde el destino es mayor que la de la fuente, el nodo intermediario no está dentro de la zona de solicitud y por lo tanto, descarta el paquete. De lo contrario envía el paquete a todos los destinos, [Boukerche et al., 2011].

Ventajas:

Dado que las peticiones de ruta se inundan a través de los nodos en sólo la zona de espera, el paquete de sobrecarga de control se reduce considerablemente.

Garantiza la máxima conectividad.

Desventajas:

LAR considera que el nodo fuente conoce de antemano la información de localización y velocidad promedio del nodo destino. Si el nodo fuente no tiene información acerca de la localización del nodo destino, el algoritmo transmite el mensaje en cada dirección, posiblemente inundando la red, intentando encontrar al nodo destino.

2.5.2. Perímetro de enrutamiento codiciado sin estado -Greedy Perimeter

Stateless Routing (GPSR)

GPSR [Karp y Kung, 2000], reacciona rápidamente y es eficiente en redes móviles. Estudia la relación entre la posición y la conectividad geográfica de la red inalámbrica, utilizando las posiciones de los nodos para tomar decisiones de retransmisión de paquetes. Se utiliza en redes móviles vehiculares. Para llevar a cabo el enrutamiento de los paquetes de datos desde un nodo origen hacia un determinado destino, no establece de antemano una ruta por la cual circularán todos los paquetes, sino que cada nodo intermedio decide hacia qué nodo encaminará cada paquete recibido en base a la localización del destino final y la posición de sus nodos vecinos. Para tomar esta decisión, distingue dos modos de enrutamiento: greedy forwarding y perimeter forwarding. Con el primer modo el nodo transmite el paquete de datos a su nodo vecino que más cerca se encuentre del destino, de forma que el paquete se irá aproximando progresivamente al destino final. Sin embargo, cuando un nodo no tenga ningún vecino más próximo al destino que él mismo, cambiará el modo de enrutamiento a perimeter forwarding e intentará encaminar el paquete de datos de manera que bordee la zona en la que




no había ningún nodo disponible. Independientemente del modo de enrutamiento empleado, el proceso se repite en cada nodo retransmisor hasta que el paquete alcanza el nodo destino.

Ventajas:

Tiempo de descubrimiento de ruta menor y un mejor desempeño en la tasa de entrega de paquetes.

Desventaja:

Muestra problemas de enrutamiento en escenarios con presencia de edificios, obstáculos, bifurcaciones e intersecciones.

Incrementa el sobre-procesamiento, la carga de enrutamiento y el sobre-procesamiento general de la red.

2.6. Conclusiones

El enrutamiento en las redes ad hoc o MANET es un factor importante ya que cada vez más, las aplicaciones demandan la movilidad de los nodos. Esto obliga a implementar mecanismos de enrutamiento que faciliten la comunicación entre ellos, y que se adapten a las particularidades de este tipo de medios. Es por ello que en este tipo de redes los protocolos necesitan ser adaptados teniendo en cuenta las características de estos entornos cambiantes sobre todo la topología dinámica de la red.

Después de comparar y evaluar los protocolos seleccionados en este trabajo, se puede evidenciar que los protocolos se pueden dividir en tres grupos según la forma en que los nodos obtienen y mantienen la información de ruteo: proactivos, reactivos e híbridos. Los protocolos proactivos intentan mantener la información de ruteo a todos los demás nodos de la red consistente y actualizada, por lo tanto, si un nodo necesita una ruta la obtiene inmediatamente. Por su parte, en un protocolo reactivo, las rutas son buscadas, únicamente, cuando se necesitan. El proceso de descubrimiento de ruta es iniciado por el origen y, si se encuentra una ruta hacia el destino deseado, esta se mantiene hasta que el destino deja de ser accesible. Los protocolos proactivos tienen la ventaja de un menor retardo end-to-end porque las rutas deberán estar disponibles al momento de querer establecer una conexión. Tienen como desventaja, que generan una gran cantidad de trafico para mantener las tablas actualizadas, por lo que, pueden presentar problemas de escalabilidad en redes grandes. Por último, los protocolos híbridos combinan los meritos de estos dos tipos de protocolos y, además, solucionan sus limitaciones.




Después de estudiar los diferentes protocolos y analizar sus características, ventajas y desventajas, se llegó a la conclusión de que el protocolo más adecuado para ser estudiado en este trabajo es el protocolo de enrutamiento basado en zonas, que se encuentra dentro de los protocolos híbridos, debido a que cumple con los requisitos exigidos. Este tipo de protocolo combina las ventajas del enrutamiento proactivo y reactivo, logrando alcanzar un rendimiento general más alto.

En el siguiente capítulo se hace un análisis más detallado del protocolo de enrutamiento basado en zonas.



Protocolo de enrutamiento basado en zonas 27

Capítulo III. Protocolo de enrutamiento basado en zonas

3.1. Introducción

El propósito principal de este capítulo es describir el funcionamiento del protocolo de enrutamiento basado en zonas. Este es un protocolo híbrido que reduce el alcance proactivo a una zona centrada y utiliza el enrutamiento reactivo para llegar a los nodos más alejados. Así mismo se analizarán cada uno de sus componentes y los diferentes cálculos de rutas que utiliza para detectar las rutas óptimas.

Se estudiarán los protocolos internos del protocolo de enrutamiento basado en zonas, los cuales son: protocolo de enrutamiento intrazona y protocolo de enrutamiento interzona.

Debido a que cada nodo en el protocolo de enrutamiento basado en zonas mantiene su propia zona de enrutamiento, las zonas de los nodos vecinos se pueden solapar. Para solucionar este problema este protocolo ofrece mecanismos de detección de consulta. Entre esos mecanismos están: el protocolo de resolución de bordercast, el procesamiento de retardo aleatorio y el mecanismo de finalización anticipada. Todos estos mecanismos serán detallados en este capítulo.

Se presentarán diferentes escenarios donde se probará el funcionamiento del protocolo de enrutamiento basado en zonas ante diferentes situaciones. Demostrando así que es un protocolo escalable y robusto ante cambios de la movilidad de los nodos.

3.2. Descripción del protocolo de enrutamiento basado en zonas

El protocolo de enrutamiento basado en zonas se considera como un protocolo híbrido debido a que combina algoritmos proactivos y reactivos, para mantener las tablas de rutas válidas, sin causar un excesivo sobre-procesamiento.

La comunicación dentro de una zona específica se realiza a través del protocolo de enrutamiento intrazona. El protocolo de enrutamiento intrazona proporciona descubrimiento de vecinos directamente de forma efectiva (enrutamiento proactivo). La comunicación entre diferentes zonas, es realizada por el protocolo de enrutamiento interzona. Éste último, proporciona el enrutamiento entre nodos que deben de comunicarse entre zonas (enrutamiento reactivo). El protocolo de enrutamiento interzona utiliza un protocolo para la distribución de mensajes conocido como protocolo frontera. La ventaja de este sistema sobre el flooding es que en lugar de recorrer la red nodo por nodo, el protocolo frontera permite que las




consultas sean dirigidas fuera de la red local y hacia regiones de la red que no hayan sido cubiertas por la consulta.

El hecho de que mediante el protocolo de enrutamiento basado en zonas, se pueda acceder a una zona centrada de forma proactiva y de forma reactiva a los nodos más alejados, trae como ventaja que las solicitudes se puedan enrutar de manera más rápida y eficiente, ya que no hay necesidad de consultar a todos los nodos de la red.

Este protocolo opera con redes con grandes cantidades de nodos, alta movilidad y alto tráfico, haciendo a este un protocolo escalable y robusto.

En la figura 3 podemos ver la arquitectura del protocolo de enrutamiento basado en zonas, que se divide en tres módulos: protocolo de enrutamiento intrazona, protocolo de enrutamiento interzona y protocolo frontera.

Consulta de ruta Respuesta de ruta Error de ruta, etc.

Figura 3. Arquitectura del protocolo de enrutamiento basado en zonas.

El protocolo de enrutamiento intrazona se encarga del enrutamiento de intrazona de manera proactiva, éste detallará en el siguiente apartado.

3.3. Protocolo de enrutamiento intrazona

En el protocolo de enrutamiento basado en zonas, un nodo mantiene de forma proactiva rutas a los destinos situados en un vecindario local, a los cuales nos referimos como una zona de

IP

Protocolo de enrutamiento

intrazona

Protocolo de enrutamiento

interzona

Protocolo

frontera




enrutamiento. Más precisamente, la zona de enrutamiento de un nodo se define como una colección de nodos, cuya distancia mínima en saltos desde el nodo origen es inferior a un parámetro conocido como el radio de la zona.

La construcción de una zona de enrutamiento requiere que un nodo sepa primero quiénes son sus vecinos. Un vecino se define como un nodo, con el cual se puede establecer una comunicación directa. La determinación de una conexión directa entre dos nodos se basa típicamente en mediciones de la calidad del enlace, tales como la potencia de la señal recibida, tasa de error de bit (BER), relación señal interferencia (SIR), la estabilidad del enlace, etc.

El protocolo de enrutamiento intrazona se basa en un protocolo de descubrimiento de vecinos, mediante el cual se detectan nuevos nodos vecinos. Mediante este protocolo se envían mensajes HELLO a intervalos regulares. Tras la recepción de un mensaje HELLO, se actualiza la tabla de vecinos. Los vecinos para los cuales no se ha recibido ningún mensaje HELLO en un tiempo especificado se eliminan de la tabla.

Una vez las rutas han sido descubiertas, el protocolo de enrutamiento intrazona ofrece zonas de enrutamiento mejoradas y en tiempo real. En este protocolo tras la detección de un fallo de enlace, un nodo puede elegir en notificar al nodo origen de la ruta dañada o reparar la ruta mediante el descubrimiento de una nueva ruta.

El protocolo de enrutamiento intrazona contiene además un protocolo de estado de enlace simple, basado en un temporizador. Para el seguimiento de la topología de enrutamiento de zonas de R-saltos. Cada nodo envía periódicamente su estado de enlace, para una profundidad de R-saltos, controlada por un tiempo de vida -time-to-live (TTL), campo en el mensaje de actualización.

El alcance de los anuncios de estado de enlace está limitado por un TTL en el paquete de actualización de estado de enlace. El TTL es inicializado a R-1 saltos, por el nodo origen. Cuando un nodo recibe el paquete de actualización, se decrementa el valor de TTL. Cuando el TTL llega a 0, el paquete se descarta.

En el siguiente apartado se presenta un escenario donde se implementa el protocolo de enrutamiento intrazona.

3.3.1. La noción de una zona de enrutamiento de intrazona

La figura 4 muestra la zona de enrutamiento del nodo origen S, de radio de dos saltos. Para el propósito de ilustración, se representan las zonas como círculos alrededor del nodo origen S.




Sin embargo, se debe tener en cuenta que la zona no es una descripción de la distancia física, sino más bien conectividad nodal (número de saltos).

Figura 4. Zona de enrutamiento del nodo origen S.

En este ejemplo, los nodos de la A-I están dentro de la zona de enrutamiento del nodo origen S. El nodo L está fuera de la zona de enrutamiento de S. Los nodos periféricos (que en la literatura británica son llamados nodos bordercasting) son nodos cuya distancia mínima al nodo origen es exactamente igual al radio de la zona. Los nodos restantes se clasifican como nodos interiores. Por tanto, en la figura 4, los nodos A-F son nodos interiores, mientras que los nodos G-I son nodos periféricos.

Para proporcionar una adecuada accesibilidad de la red, es importante que un nodo se pueda conectar a un número suficiente de vecinos. Sin embargo, un número mayor no es necesariamente mejor. Como las áreas de cobertura de los transmisores se hacen más grandes, también lo hacen el número de miembros de las zonas de enrutamiento. Esto puede originar una cantidad excesiva de tráfico de actualización de ruta.

Se dispone cada nodo para que mantenga la información de enrutamiento sólo de los nodos que se encuentran dentro de su zona de enrutamiento. Debido a que las actualizaciones sólo se propagan localmente, el tráfico de actualización requerido para mantener una zona de enrutamiento no depende del número total de nodos de la red.




3.3.1.1. Implementación del protocolo de enrutamiento intrazona empleando

un TTL

El protocolo de enrutamiento intrazona contiene un protocolo de estado de enlace simple, basado en un temporizador. Para el seguimiento de la topología de enrutamiento de zonas de R-saltos, cada nodo envía periódicamente su estado de enlace para una profundidad de R-saltos, controlada por un tiempo de vida -time-to-live (TTL), campo en el mensaje de actualización.

A continuación se presentan los pasos para la implementación del TTL en el protocolo de enrutamiento intrazona:

1- Cada nodo anuncia periódicamente su estado de enlace, el conjunto actual de los vecinos y las listas correspondientes de métricas de enlace, en toda su zona de enrutamiento.

2- Los nodos monitorizan su propio estado de enlace a través de un protocolo de descubrimiento de vecinos.

3- La actualización de estado de enlace, es controlada por un valor de TTL que se lleva en el mensaje de estado de enlace. El TTL se inicializa por el nodo origen.

4- Tras la recepción de un mensaje de actualización de estado de enlace, se almacena el estado del enlace, se recalcula la tabla de enrutamiento y se reduce el valor del TTL.

5- Mientras el valor del TTL sea mayor que 0, el mensaje de actualización de estado de enlace es retransmitido.

3.3.2. Descubrimiento de vecinos en el protocolo de enrutamiento intrazona

El protocolo de enrutamiento intrazona se basa en un protocolo de descubrimiento de vecinos. Mediante este protocolo se envían mensajes HELLO a intervalos regulares. Tras la recepción de un mensaje HELLO, se actualiza la tabla de vecinos. Los vecinos para los cuales no se ha recibido ningún mensaje HELLO en un tiempo especificado se eliminan de la tabla. Tras la detección de un fallo, un nodo puede elegir en notificar al nodo origen de la ruta dañada o reparar la ruta mediante el descubrimiento de una nueva ruta.




3.3.2.2. Generación de mensajes “HELLO”

Los mensajes HELLO son mensajes broadcast que se transmiten por un nodo dentro de la red. Los mensajes HELLO se transmiten de manera proactiva, a intervalos regulares, conocidos como Hello_interval, que es el tiempo máximo entre la transmisión de dos mensajes HELLO sucesivos. El protocolo de enrutamiento intrazona sólo se limita al alcance proactivo de las zonas que se encuentran dentro de su radio R. Las zonas que están fuera de este radio, son cubiertas por el protocolo de enrutamiento interzona, el cual utiliza el enrutamiento reactivo para cubrir esas zonas. El protocolo de enrutamiento interzona será explicado de una manera más detallada en el siguiente apartado, donde se podrán ver sus diferencias con el protocolo de enrutamiento intrazona. Asimismo se verá un escenario donde se hace necesario el uso del protocolo de enrutamiento interzona.

3.4. Protocolo de enrutamiento interzona

El proceso de enrutamiento reactivo se divide en dos fases: la fase de solicitud de ruta y la fase de respuesta de ruta. En la solicitud de ruta, el nodo origen envía un mensaje de solicitud de ruta a sus nodos periféricos usando el protocolo frontera. El protocolo frontera es el responsable de reenviar mensajes de solicitud de ruta a los nodos periféricos del nodo periférico. Si el receptor de un mensaje de solicitud de ruta conoce el destino, responde enviando un mensaje de respuesta de ruta de regreso al nodo origen. De lo contrario, continúa el proceso mediante el reenvío del mensaje a sus nodos periféricos. De esta manera, la solicitud de ruta se extiende por toda la red. Si un nodo recibe varias copias de la misma solicitud de ruta, éstas se consideran como redundantes y se descartan.

El mensaje de respuesta de solicitud de ruta se envía por cualquier nodo que puede proporcionar una ruta hacia el nodo origen. Para poder enviar la respuesta de vuelta al nodo origen, la información de enrutamiento debe irse acumulando cuando la solicitud se envía a través de la red. La información se almacena en el mensaje de solicitud de ruta. Las direcciones del siguiente salto de los nodos, a lo largo del camino, también deben irse almacenando.

A continuación se ilustra un escenario donde se puede apreciar el protocolo de enrutamiento interzona.

Se considera la figura 5. El nodo S tiene un paquete para enviar al nodo X. El radio de la zona es R=2. El nodo utiliza la tabla de enrutamiento proporcionada por el protocolo de enrutamiento intrazona para comprobar si el nodo destino X se encuentra dentro de su zona. Dado que no se encuentra, se transmite un mensaje de solicitud de ruta, utilizando el protocolo de enrutamiento interzona. El mensaje de solicitud de ruta se transmite a los nodos periféricos




(gris en la figura 5). Cada uno de estos nodos comprueba si el destino X se encuentra en su tabla de enrutamiento.

Figura 5. Zona de enrutamiento del nodo S.

El nodo I no encuentra el destino en su tabla de enrutamiento. En consecuencia, transmite el mensaje de solicitud de ruta a sus nodos periféricos, que se muestran en gris en la figura 6. Debido a los mecanismos de control de consulta, el mensaje de solicitud de ruta no se pasa de nuevo a los nodos D, F y S.

Figura 6. Zona de enrutamiento del nodo I.




Por último, el mensaje de solicitud de ruta es recibido por el nodo T, que sí puede encontrar el destino en su zona de enrutamiento, ver figura 7. El nodo T añade la ruta desde sí mismo hacia el nodo X. A continuación, se genera un mensaje de respuesta de ruta, que contiene la ruta hasta X y la cual se transmite al nodo origen. Si se disponen de varias rutas al destino, el nodo origen recibiría varias respuestas.

Figura 7. Zona de enrutamiento del nodo T.

Sin embargo, ya que las zonas de enrutamiento de nodos vecinos se superponen, cada nodo puede retransmitir mensajes de solicitud de ruta varias veces, lo que origina más tráfico. Para resolver este problema, el protocolo de enrutamiento interzona necesita mecanismos de control de consulta. Estos mecanismos que pueden dirigir consultas fuera de las zonas cubiertas y terminar los mensajes de solicitud de ruta antes de ser entregados a los nodos periféricos en las regiones de la red que ya han sido cubiertas. Estos mecanismos de detección de consulta se presentan a continuación.

3.5. Mecanismos de detección de consulta del protocolo de enrutamiento

basado en zonas

Debido a que cada nodo en el protocolo de enrutamiento basado en zonas mantiene su propia zona de enrutamiento, las zonas de los nodos vecinos en gran medida se pueden solapar. Cuando se transmite un mensaje de solicitud de ruta a los nodos periféricos, sólo el nodo periférico es consciente de que la zona de enrutamiento está cubierta por la consulta. Cuando los nodos periféricos continúan el proceso de consulta a sus nodos periféricos, el mensaje de




solicitud de ruta puede ser transmitido a través de los mismos nodos de nuevo. Por ejemplo se tiene la siguiente figura, donde se puede apreciar este problema:

Figura 8. Zona de enrutamiento nodo S.

El nodo origen S en la figura 8 transmite un mensaje de solicitud de ruta a sus nodos periféricos F-J. El mensaje de solicitud de ruta transmitido por el nodo J a sus nodos periféricos C, S y F es redundante, ya que estos nodos se han cubierto por el mensaje anterior. Para ser capaz de evitar que los mensajes de solicitud de ruta reaparezcan en las regiones cubiertas, los nodos deben detectar la actividad de retransmisión de consulta local.

Entre los mecanismos que utiliza el protocolo de enrutamiento interzona para evitar que los mensajes de solicitud de ruta reaparezcan en las regiones que ya han sido cubiertas, están:

Protocolo de resolución de bordercast. Consiste en evitar consultar con mensajes de solicitud de ruta de manera redundante, un nodo periférico que tengan en común varios nodos periféricos. Para dar solución a este problema el protocolo de resolución de bordercast ofrece dos métodos de detección de consulta. Uno donde los nodos son capaces de detectar los mensajes de solicitud de ruta redundantes y otro donde es posible escuchar el tráfico de otros nodos dentro de la cobertura de radio.

Procesamiento de retardo aleatorio. Consiste en que cada nodo periférico programa un retardo aleatorio antes de hacer la construcción de sus nodos periféricos, dentro de la red. Durante este tiempo, el nodo que espera puede detectar los mensajes de solicitud de ruta de los otros nodos periféricos y evitar volver a consultar esos nodos.

Mecanismo de finalización anticipada. Consiste en un procedimiento según el cual si un nodo periférico ya ha sido cubierto por un mensaje de solicitud de ruta, se evita. Se utiliza el conocimiento de la topología local para evitar que los nodos periféricos envíen el mensaje de solicitud de ruta, dentro de las regiones ya cubiertas.




3.5.1. Protocolo de resolución de bordercast -Bordercast Resolution Protocol

(BRP)

El proceso de enrutamiento reactivo se divide en dos fases: la fase de solicitud de ruta y la fase de respuesta de ruta. En la solicitud de ruta, el nodo origen envía un mensaje de solicitud de ruta a sus nodos periféricos usando el protocolo frontera. Si el nodo receptor de un mensaje de solicitud de ruta conoce el destino, responde enviando un mensaje de respuesta de solicitud de ruta de regreso al nodo origen. De lo contrario, se continúa el proceso de reenvío del mensaje de solicitud de ruta a sus nodos periféricos. Sin embargo, ya que las zonas de enrutamiento de nodos vecinos se superponen, un nodo periférico puede recibir mensajes de solicitud de ruta redundantes.

Para resolver este problema BRP ofrece dos métodos de detección de consulta: QD1 y QD2. En primer lugar, QD1 consiste en que un nodo periférico es consciente de que su propia zona ya ha sido cubierta por el mensaje de solicitud de ruta. De esta manera QD1 detecta y suprime los mensajes redundantes que pasan a través de un nodo. En el ejemplo anterior (figura 8), todos los nodos excepto el nodo B transmiten el mensaje de solicitud de ruta de S. Por tanto, son capaces de utilizar QD1.

QD2 consiste en que los nodos puedan escuchar el tráfico de otros nodos. En este caso, los nodos pueden "escuchar" un mensaje de solicitud de ruta redundante, y no retransmitirlo a la red, que ya ha sido cubierta por el mensaje.

Cuando un nodo transmite un mensaje de solicitud de ruta, se necesita algún tiempo para que sea retransmitido a lo largo de la red y para ser detectado a través de los mecanismos de detección de consulta QD1 y QD2.

Durante este tiempo, otro nodo puede transmitir la misma solicitud de ruta. Esto puede ser un problema cuando varios nodos cercanos reciben y retransmiten un mensaje de solicitud de ruta más o menos al mismo tiempo. Para reducir la probabilidad de recibir el mismo mensaje de varios nodos, se debe emplear un mecanismo de procesamiento de retardo aleatorio (RQPD), que será detallado más adelante.

3.5.2. Mecanismo de finalización anticipada- Early Termination (ET)

Con ET, un nodo puede prevenir que un mensaje de solicitud de ruta entre en las regiones ya cubiertas.




El mecanismo de finalización anticipada combina la información obtenida a través de la detección de la solicitud de ruta, con el conocimiento de la topología local, para evitar que los nodos periféricos envíen un mensaje de solicitud de ruta dentro de las regiones cubiertas. El mecanismo ET requiere información de la topología que se extiende fuera de la zona de enrutamiento del nodo. El mecanismo de finalización anticipada (ET) se muestra en la siguiente figura:

Figura 9. Representación método de control de consulta de finalización anticipada.

Primero el nodo X recibe un mensaje de solicitud de ruta para retransmitir por el nodo periférico Y. X a través de QD1 y QD2 puede identificar los nodos interiores de Y como cubiertos. El nodo X, entonces, reconstruye la red que forman los nodos periféricos de Y, y retransmite el mensaje de solicitud de ruta a sus nodos periféricos de dos saltos. Estos nodos periféricos se consideran cubiertos por X. Más tarde, X recibe una segunda copia del mensaje de solicitud de ruta para transmitir en nombre del nodo periférico Z. Al igual que antes, X identifica los nodos interiores de la zona de enrutamiento de Z y reconstruye la red de nodos periféricos de Z. Según los nodos periféricos de Z, X debe retransmitir el mensaje de solicitud de ruta a dos de los nodos periféricos de Z. Sin embargo, X reconoce que ambos nodos periféricos ya han sido cubiertos por el mensaje de solicitud de ruta (uno es un miembro interior de la zona de enrutamiento de Y, y el otro es un nodo periférico de la zona de enrutamiento de Y que ya fue consultado por X). Sobre la base de los criterios de ET, el nodo X puede evitar ambos nodos periféricos y desechar de forma segura el mensaje.

Finalización anticipada

de la red de nodos

periféricos de X, en la

región ya cubierta.

Nodos interiores de nodos periféricos.

Nodos periféricos de nodos periféricos.

Nodos no cubiertos.




3.5.3. Procesamiento de retardo aleatorio -Random query-processing delay

(RQPD)

Cada nodo periférico espera un tiempo aleatorio antes de la construcción de la red de nodos periféricos y la finalización anticipada. Durante este tiempo, el nodo que espera puede detectar los mensajes de solicitud de ruta de los otros nodos periféricos y evitar los nodos periféricos que ya han sido cubiertos por el mensaje.

El beneficio de RQPD es demostrado mediante la figura 10.

Figura 10. Representación método de control de consulta RQPD.

En la figura 10 los nodos X e Y son nodos periféricos que comparten un nodo en común de la zona. Suponiendo que ningún nodo se evita través de ET, X e Y recibirán un mensaje de solicitud de ruta en aproximadamente el mismo tiempo. Sin RQPD, X e Y ambos procederán a la consulta de sus nodos periféricos. Sólo más tarde determinarán los dos nodos, que sus mensajes de solicitud de ruta eran redundantes, ya que, comparten un nodo periférico en común de la zona.

Sin embargo, cuando se aplica RQPD, X e Y cada uno ponen en marcha un período de tiempo aleatorio con una media suficientemente grande. En este caso, permite detectar a Y los nodos periféricos de X antes de transmitir su propio mensaje de solicitud de ruta. X entonces aplica esta información para evitar sus nodos periféricos restantes (ya que todos ellos se encuentran dentro de la zona de direccionamiento de Y).

X e Y reciben simultáneamente un mensaje

de solicitud de ruta. La detección de Y del

nodo periférico de X, es demasiado tarde

para solicitar ET.

A través RQPD Y, detecta al nodo periférico de

X y finaliza su propia consulta redundante.




3.6. Determinación de la ruta mediante el protocolo de enrutamiento basado en

zonas

Para determinar una ruta a un destino en el protocolo de enrutamiento basado en zonas, se siguen los siguientes pasos:

1- Si el nodo destino está en la zona del nodo origen, se realiza la entrega directa de los datos. Por ejemplo en la siguiente red:

Figura 11. Representación de la zona de enrutamiento del nodo S.

Si el nodo origen S quiere llegar a F, como el nodo destino F, se encuentra dentro de su zona de enrutamiento, S puede acceder a él directamente.

2- Si el nodo destino no se encuentra dentro de la zona, el nodo origen transmite un mensaje de solicitud ruta a todos los nodos periféricos de su zona.

3- Si el destino está en la zona del nodo periférico, el nodo responde con la ruta al nodo origen.

4- Si el destino no está en la zona del nodo periférico, el nodo periférico reenvía el mensaje de solicitud de ruta a sus nodos periféricos, hasta encontrar la ruta hacia el destino.

En los siguientes apartados se presentan diferentes escenarios donde se utiliza el protocolo de enrutamiento basado en zonas. Ambos escenarios mostrados son representativos, porque se mostrará la manera en cómo se determina la mejor ruta hacia el destino.

3.6.1. Escenario de zonas contiguas

En la figura 12 se muestra el escenario que se analizará en este apartado. Se ha elegido este escenario ya que contiene zonas contiguas.




En este ejemplo se pondrá de manifiesto el protocolo de enrutamiento interzona. Este protocolo que se utiliza para hallar el nodo destino, cuando este no se encuentra dentro de la zona del nodo origen y se realiza su búsqueda de manera reactiva.

La figura 12 representa la zona de enrutamiento del nodo origen S (representado en azul), S tiene como nodos interiores a B, C y E representados dentro del círculo rojo; como nodos periféricos tiene A, H, G y F representados por el circulo azul.

Figura 12. Representación de la zona de enrutamiento.

La figura 13 representa la transmisión del mensaje de solicitud de ruta del nodo origen S, para llegar al nodo destino D. El nodo S transmite el mensaje de solicitud de ruta a sus nodos periféricos, puesto que D no se encuentra dentro de su zona. La transmisión del mensaje de solicitud de ruta de S, se representa mediante flechas rojas. Una vez sus nodos periféricos reciben el mensaje de solicitud de ruta, buscan si el nodo destino está dentro de su zona.

En la figura 14 se puede notar que el nodo A no retransmite el mensaje de solicitud de ruta al nodo C, porque C esta dentro de la zona de enrutamiento de S. Evitando así mensajes redundantes dentro de la red. Así mismo H no retransmite el mensaje de solicitud de ruta porque todos sus vecinos de dos saltos están dentro de la zona de enrutamiento de S. I no reenvía el mensaje de solicitud de ruta porque este escuchó a G. Los nodos G y F reciben el mensaje de solicitud de ruta.




Figura 13. Representación de la transmisión del mensaje de solicitud de ruta

de S a sus nodos periféricos.

Figura 14. Representación de la zona de A.

Sin embargo, en la figura 15 se puede apreciar que los nodos periféricos, G y F si encuentran una ruta hacia el nodo destino D. Las rutas vienen representadas por las flechas verdes.

El nodo origen obtiene dos respuesta de solicitud de ruta, en la figura 16 se representan ambas rutas por los cuales S puede enviar datos a D. Las rutas están representadas una por la flecha roja [S, F, D] y otra por la flecha azul [S, G, D].




Figura 15. Representación del camino de respuesta de la solicitud de ruta a S.

Figura 16. Representación de las rutas de S al destino D.

3.6.2. Escenario de zonas no contiguas

Supongamos la figura 17, que representa un escenario de zonas no contiguas. El nodo S tiene un paquete para enviar a X, el radio de la zona es R=2. El nodo origen utiliza la tabla de enrutamiento proporcionada por el protocolo de enrutamiento intrazona para comprobar si el nodo destino X se encuentra dentro de su zona. Dado que no se encuentra, un mensaje de solicitud de ruta se transmite utilizando el protocolo de enrutamiento interzona. La solicitud se transmite a los nodos periféricos (gris en la figura 17).




Figura 17. Zona de enrutamiento nodo S.

Cada uno de estos realiza una búsqueda en su tabla de enrutamiento para comprobar si el nodo destino se encuentra dentro de su zona.

Figura 18. Zona de enrutamiento nodo I.

El nodo I no encuentra el nodo destino X en su tabla de enrutamiento. En consecuencia, transmite el mensaje de solicitud de ruta a sus nodos periféricos, que se muestran en gris en la figura 18. Debido a los mecanismos de control de consulta, la solicitud no se pasa de nuevo a los nodos D, F y S.

Por último, el mensaje de solicitud de ruta es recibido por el nodo T, que puede encontrar el nodo destino en su zona de enrutamiento, que se muestra en la figura 19.




Figura 19. Zona de enrutamiento nodo T.

El nodo T añade la ruta desde sí mismo hacia el nodo X en el mensaje de respuesta de solicitud de ruta, este mensaje se envía de nuevo al nodo de origen. Si se dispone de varias rutas al destino, el nodo origen recibiría varias respuestas.

3.7. Conclusiones

El protocolo basado en zonas reduce el alcance proactivo a una zona centrada en cada nodo. En una zona limitada, el mantenimiento de la información de enrutamiento es más fácil. Además, se reduce al mínimo la cantidad de información de enrutamiento que nunca se utiliza. Sin embargo, a los nodos más alejados se puede llegar con el enrutamiento reactivo. Dado que todos los nodos almacenan información de enrutamiento local de forma proactiva, se pueden enrutar las solicitudes de manera más eficiente y sin consultar todos los nodos de la red.

El protocolo basado en zonas opera con redes con grandes cantidades de nodos, alta movilidad y alto tráfico. Haciendo a este protocolo escalable y robusto. Mediante el protocolo basado en zonas se pueden detectar las rutas óptimas. El protocolo tiene la capacidad de auto-adaptación ante cambios en la topología, por lo que puede permitir la búsqueda de la mejor ruta y aliviar la congestión de la red. El protocolo basado en zonas posee mecanismos de detección de consulta que evita que una consulta llegue a zonas que han sido consultadas antes, evitando que se inunde la red con trafico no deseado. Sus protocolos internos protocolo de enrutamiento intrazona y protocolo de enrutamiento interzona, ofrecen zonas de enrutamiento mejoradas, en tiempo real.

Debido a las ventajas y características que presenta el protocolo de enrutamiento basado en zonas, se ha llegado a la conclusión, de que el protocolo a desarrollar en este proyecto estará basado en los principios de funcionamiento de este protocolo de enrutamiento. El protocolo a




desarrollar será denominado Protocolo Híbrido de Enrutamiento basado en Zonas (PHEZ), el cual tendrá diferencias marcadas con los protocolos de enrutamiento basados en zonas existentes. En los próximos capítulos se detallará la implementación desarrollada de los protocolos internos de PHEZ: protocolo de enrutamiento intrazona y protocolo de enrutamiento interzona.



Protocolo de enrutamiento intrazona de PHEZ 46

Capítulo IV. Protocolo de enrutamiento intrazona de

PHEZ

4.1. Introducción

En este capítulo se detallará la implementación desarrollada del protocolo de enrutamiento intrazona de PHEZ. Este protocolo se encarga de mantener de forma proactiva rutas a los destinos situados en un vecindario local, del protocolo desarrollado PHEZ.

En los apartados de este capítulo se mostrará de manera detallada el algoritmo implementado del protocolo de enrutamiento intrazona de PHEZ, dónde se pone de manifiesto el protocolo de descubrimiento de vecinos. Mediante este protocolo de descubrimiento de vecinos, se transmiten mensajes HELLO a intervalos regulares.

Una vez se haya detallado paso por paso el algoritmo implementado, se presentarán diferentes escenarios, donde se probará el funcionamiento del algoritmo. Demostrando así la eficiencia del algoritmo desarrollado del protocolo de enrutamiento intrazona de PHEZ, ante cambios de la movilidad de los nodos de la red.

De igual manera, en este capítulo, se presentarán las ventajas de la implementación desarrollada del protocolo de enrutamiento intrazona de PHEZ.

4.2. Descripción del protocolo de enrutamiento intrazona de PHEZ

Este protocolo mantiene de forma proactiva las rutas a los destinos situados en un vecindario local, a los cuales nos referimos como zona de enrutamiento. Más precisamente, la zona de enrutamiento de un nodo se define como una colección de nodos, cuya distancia mínima en saltos desde el nodo origen es inferior a un parámetro conocido como el radio de la zona.

La construcción de una zona de enrutamiento requiere que un nodo sepa primero quiénes son sus vecinos.

El protocolo de enrutamiento intrazona desarrollado, se basa en un protocolo de descubrimiento de vecinos. Mediante este protocolo de descubrimiento de vecinos, se transmiten mensajes HELLO a intervalos regulares. Tras la recepción de un mensaje HELLO, se actualiza la tabla de vecinos. Los vecinos para los cuales no se ha recibido ningún mensaje HELLO en un tiempo específico se eliminan de la tabla. Tras la detección de un fallo, un nodo




puede elegir en notificar al nodo origen de la ruta dañada o reparar la ruta mediante el descubrimiento de una nueva ruta.

El protocolo de enrutamiento intrazona de PHEZ, no contiene un protocolo de estado de enlace simple, para dar a conocer el estado de enlace de los nodos, controlado por un tiempo de vida -time-to-live (TTL). En cambio en el protocolo de enrutamiento intrazona desarrollado cada nodo, tras la recepción de un mensaje HELLO, enviará un mensaje de respuesta HELLO, que contendrá su tabla de vecinos. De esta manera cada nodo da a conocer su estado de enlace a sus vecinos directos, sin la necesidad de usar un TTL. En el siguiente apartado se muestra la implementación del algoritmo desarrollado, del protocolo de enrutamiento intrazona de PHEZ.

4.3. Algoritmo del protocolo de enrutamiento intrazona de PHEZ

En la figura 20 se enumeran los pasos del algoritmo implementado del protocolo de enrutamiento intrazona de PHEZ.

Algoritmo del protocolo de enrutamiento intrazona de PHEZ

1- Esperar la expiración del temporizador. Se transmite un mensaje HELLO si ha llegado el tiempo establecido.

2- Se transmite un mensaje HELLO. 3- Escuchar el canal. 4- Si se recibe un mensaje:

4.1- Comprobar que es la primera vez que se lee el mensaje. 4.2- Comprobar si es un mensaje HELLO. 4.2.1- Si es un mensaje HELLO se actualiza la tabla de vecinos. 4.3- Comprobar si es un mensaje de respuesta HELLO. 4.3.1- Si es un mensaje de respuesta HELLO se actualiza la tabla de vecinos.

5- Verificar las rutas válidas.

Figura 20. Algoritmo implementado del protocolo de enrutamiento intrazona de PHEZ.

La figura 21 es una representación gráfica de la descripción del algoritmo del protocolo de enrutamiento intrazona de PHEZ.




SI

NO

NO

SI SI

Figura 21. Representación del algoritmo implementado del protocolo de enrutamiento intrazona de PHEZ.

Escuchar el canal.

Actualizar tabla de

vecinos.

Es un Mensaje

de respuesta

HELLO.

Actualizar tabla de

vecinos.

Esperar

temporizador.

Transmisión de mensaje HELLO.

Esperar la expiración del

temporizador.

FIN

INICIO

Es un Mensaje

HELLO.




A continuación se describen uno por uno los pasos del algoritmo implementado.

El paso 1 del algoritmo hace referencia a esperar la expiración del temporizador, esto es debido a que los mensajes HELLO se transmiten de manera proactiva, a intervalos regulares. Se transmite un mensaje HELLO si ha llegado el tiempo establecido mediante un temporizador.

El paso 2 hace alusión a la transmisión de un mensaje HELLO, asumiendo que ya ha llegado el intervalo tiempo establecido en el temporizador. Un mensaje HELLO debe contener:

ID del nodo que transmite el mensaje HELLO.

Identificador del mensaje HELLO.

Una vez se ha transmitido el mensaje, se debe escuchar el canal, que es el paso 3 del algoritmo. Si se recibe un mensaje, tal como lo indica el paso 4, se debe verificar que es la primera vez que se lee el mensaje, para evitar que un nodo lea dos veces un mismo mensaje, agotando así el paso 4.1.

Una vez se ha verificado que es la primera vez que se lee ese mensaje, se debe comprobar si es un mensaje HELLO tal como lo indica el paso 4.2. Se comprueba si es un mensaje HELLO, mediante el identificador de mensajes HELLO. Si es un mensaje HELLO se procede a agotar el paso 4.2.1, actualización de la tabla de vecinos.

Si no es un mensaje HELLO, entonces tal como se indica en el paso 4.3, se debe comprobar si es un mensaje de respuesta HELLO. Los mensajes de respuesta HELLO son generados por un nodo tras la recepción de un mensaje HELLO. El nodo que recibe el mensaje HELLO envía su tabla de vecinos junto con su mensaje de respuesta HELLO. Todos sus vecinos escuchan el mensaje de respuesta HELLO y actualizan sus tablas de vecinos. De esta manera se mantiene el conocimiento de estado de enlace de los nodos de la red, sin necesidad de utilizar un TTL. El mensaje de respuesta HELLO debe contener:

ID del nodo que transmite el mensaje de respuesta HELLO.

Identificador del mensaje de respuesta HELLO.

Tabla de vecinos del nodo que transmite el mensaje de respuesta HELLO.

Tras la recepción de un mensaje de respuesta HELLO se debe actualizar la tabla de vecinos, tal como se indica en el paso 4.3.1.

El último paso pero no menos importante es validar las rutas en las tablas de enrutamiento de cada uno de los nodos que forman la red. Para esto se toma en cuenta un tiempo, para el cual




una ruta después de haber sido puesta en la tabla de enrutamiento se considera válida. Este tiempo se ha llamado tiempo viejo.

Actualización de tablas de vecinos.

Se debe seguir el siguiente procedimiento para la actualización de la tabla de vecinos, tras la recepción de un mensaje HELLO:

Se comprueba si el nodo que transmite el mensaje HELLO está en la tabla de vecinos del nodo que recibe el mensaje HELLO:

Si está en la tabla de vecinos del nodo que recibe el mensaje HELLO: - Se comprueba si tiene un enrutamiento diferente y se actualiza. Colocando en la tabla de vecinos, que puede llegar al nodo que transmite el mensaje HELLO por el mismo y que está a un salto. Una vez se ha actualizado la tabla de vecinos, se coloca el tiempo en el que se realizó la actualización.

- Si el nodo que recibe el mensaje HELLO tiene en su tabla de vecinos, que la manera de llegar al nodo que transmite el mensaje HELLO es por el mismo y que está a un salto, no se actualiza.

Si no está en la tabla de vecinos del nodo que recibe el mensaje HELLO:

- Se le agrega. Colocando en la tabla de vecinos, que puede llegar al nodo que transmite el mensaje HELLO por el mismo y que está a un salto. Una vez se ha actualizado la tabla de vecinos, se coloca el tiempo en el que se realizó la actualización.

El procedimiento de actualización de la tabla de vecinos, tras la recepción de un mensaje de respuesta HELLO es el siguiente:

Se desempaqueta la tabla de vecinos del nodo que transmite el mensaje de respuesta HELLO.

Se compara la tabla de vecinos del nodo que recibe el mensaje de respuesta HELLO, con la tabla de vecinos del nodo que transmite el mensaje de respuesta HELLO.




Se comprueba si el nodo que recibe el mensaje de respuesta HELLO tiene en su tabla de vecinos, los vecinos del nodo que transmitió el mensaje de respuesta HELLO:

- Si tiene en su tabla de vecinos, los vecinos del nodo que transmitió el mensaje de respuesta HELLO, pero contienen un enrutamiento diferente, (más largo que por medio del nodo transmitió el mensaje de respuesta HELLO) se actualiza. Colocando que puede llegar a esos nodos, por medio del nodo que transmitió el mensaje de respuesta HELLO y que se encuentran a dos saltos. Una vez se ha actualizado la tabla de vecinos, se coloca el tiempo en el que se realizó la actualización.

- Si tiene en su tabla de vecinos, los vecinos del nodo que transmitió el mensaje de respuesta HELLO, pero la manera en cómo puede llegar a esos nodos es por ellos mismos y se encuentran a un salto, no actualiza.

Si el nodo que recibe el mensaje de respuesta HELLO no tiene en su tabla de vecinos, los vecinos del nodo que transmitió el mensaje de respuesta HELLO:

- Los agrega. Colocando que puede llegar a esos nodos por medio del nodo que transmitió el mensaje de respuesta HELLO y que se encuentra a dos saltos. Una vez se ha actualizado la tabla de vecinos, se coloca el tiempo en el que se realizó la actualización.

Validación de tablas de enrutamiento.

El procedimiento de borrar de la tabla de enrutamiento las rutas que ya no se consideran válidas es el siguiente:

Primero se comprueba que el tiempo en que se puso la ruta en la tabla de enrutamiento, menos el tiempo actual, es mayor que el tiempo para el cual un mensaje se considera viejo (Tviejo):

Si es mayor se borra la ruta de la tabla, y se completa con -1.

Si no es mayor no se borra ya que no se considera un mensaje viejo.

En el siguiente apartado se mostrarán diferentes escenarios donde se probará el funcionamiento del algoritmo descrito anteriormente.




4.4. Escenarios de funcionamiento del protocolo de enrutamiento intrazona de

PHEZ

A continuación se presentan distintos escenarios, donde se implementa el algoritmo desarrollado del protocolo de enrutamiento intrazona de PHEZ.

4.4.1. Escenario 1

El escenario 1 se representa mediante la configuración de la red que se muestra en la figura 22. En esta configuración el nodo 1 tiene como nodo interior al nodo 2, que se encuentra a un salto. El nodo 1 tiene como nodo periférico al nodo 3, el cual se encuentra a dos saltos de él. Este escenario es interesante ya que es una representación lineal y sencilla de una zona contigua.

Figura 22. Configuración de la red del escenario 1.

Para la construcción de las tablas de enrutamiento de cada nodo se siguen los pasos del algoritmo desarrollado del protocolo de enrutamiento intrazona.

En la figura 23 se representa el proceso de construcción de las tablas de enrutamiento de cada nodo del escenario 1. Se transmiten mensajes HELLO a intervalos regulares. Tras la recepción de un mensaje HELLO, se actualiza la tabla de vecinos. Cada nodo tras la recepción de un mensaje HELLO, enviará un mensaje de respuesta HELLO, que contendrá su tabla de vecinos. Tras la recepción de un mensaje de respuesta HELLO se debe actualizar la tabla de vecinos. De esta manera se mantiene el conocimiento de estado de enlace de los nodos de la red, sin necesidad de utilizar un TTL.

Los mensajes HELLO de cada nodo en particular serán representados por una flecha roja, mientras que los mensajes de respuesta HELLO serán representados por una flecha azul.




Mensajes HELLO. Resp. Mensajes HELLO.

Figura 23. Representación de la transmisión y recepción de mensajes HELLO y respuesta HELLO durante

cada tiempo, de la configuración del escenario 1.

En la siguiente tabla se muestran los resultados de las tablas de enrutamiento de cada nodo del escenario 1: A) B) C)

ID= Identificador del nodo. R= Nodo por el cual se puede enrutar. S= Número de saltos.

Tabla 4. Tablas de enrutamiento de los nodos 1(A), 2(B), 3(C).

Nodo 2

ID R S

1 1 1

3 3 1

Nodo 1

ID R S

2 2 1

3 2 2

Nodo 3

ID R S

2 2 1

1 2 2




4.4.2. Escenario 2:

El escenario 2 se representa mediante la configuración de la red que se muestra en la figura 24. Esta configuración es interesante ya que todos los nodos tienen comunicación directa entre sí.


En la figura 25 se representa el proceso de construcción de las tablas de enrutamiento de cada nodo del escenario 2, mediante la transmisión y recepción de mensajes HELLO y mensajes de respuesta HELLO.

En la siguiente tabla se muestran los resultados de las tablas de enrutamiento de cada nodo del escenario 2: A) B) C)



Nodo 2

ID R S

1 1 1

3 3 1

Nodo 1

ID R S

2 2 1

3 3 1

Nodo 3

ID R S

2 2 1

1 1 1







4.4.3. Escenario 3

El escenario 3 se representa mediante la configuración de la red que se muestra en la figura 26. En esta configuración el nodo 1 tiene como nodo interior al nodo 2, que se encuentra a un salto del nodo 1.




El nodo 1 tiene como nodo periférico, al nodo 3, el cual se encuentra a dos saltos de él. Sin embargo, el nodo 1 no es consciente del nodo 4, ya que, este se encuentra fuera del radio de la zona del nodo 1, que es R=2. Aunque los nodos 2 y 3 si contienen en sus tablas de enrutamiento al nodo 4. Este escenario es interesante ya que es una representación lineal y sencilla de una zona no contigua.


En la figura 27 se representa el proceso de construcción de las tablas de enrutamiento de cada nodo del escenario 3, mediante la transmisión y recepción de mensajes HELLO y mensajes de respuesta HELLO.

En la siguiente tabla se muestran los resultados de las tablas de enrutamiento de cada nodo del escenario 3:

A) B) C) D)


Tabla 6. Tablas de enrutamiento de los nodos 1(A), 2(B), 3(C), 4(D).

Nodo 1

ID R S

2 2 1

3 2 2

Nodo 2

ID R S

1 1 1

3 3 1

4 3 2

Nodo 3

ID R S

2 2 1

1 2 2

4 4 1

Nodo 4

ID R S

3 3 1

2 3 2







4.4.4. Escenario 4

En este escenario se mostrará una configuración inicial donde los nodos cambiarán su posición en diferentes tiempos, provocando esto que la configuración de la red inicial varié. Con este escenario se persigue demostrar la robustez y eficiencia del algoritmo desarrollado, ante cambios en la movilidad de los nodos.

En la figura 28 se representan las diferentes configuraciones del escenario 4.




A)

B)

C)

D)

Figura 28. Configuración de la red del escenario 4 a diferentes tiempos, inicialmente(A), 40 segundos(B),

60 segundos(C), 80 segundos(D).

En las diferentes configuraciones de este escenario los vecinos para los cuales no se ha recibido ningún mensaje HELLO en un tiempo especificado se eliminan de la tabla. De esta manera, el algoritmo mantiene puesta al día las tablas de enrutamiento de los nodos que se encuentran dentro de una zona delimitada.

A continuación se representará el proceso de construcción de las tablas de enrutamiento de cada configuración del escenario 4. Se mostrará el resultado final de las tablas de enrutamiento de cada nodo, una vez se haya llegado a los 80 segundos.




4.4.4.1. Inicialmente:

La figura 29 representa de la transmisión y recepción de mensajes HELLO y mensajes de respuesta HELLO durante cada tiempo, de la configuración inicial del escenario 4, cuya red se representó en la figura 28-A.



cada tiempo, de la configuración inicial del escenario 4.

4.4.4.2. A los 40 segundos:

La figura 30 representa de la transmisión y recepción de mensajes HELLO y mensajes de respuesta HELLO durante cada tiempo, de la configuración del escenario 4 a los 40 segundos, cuya red se representó en la figura 28-B.




En esta red a los 40 segundos el nodo 3 cambia su posición y se puede comunicar directamente con el nodo 1. Mensajes HELLO. Resp. Mensajes HELLO.


cada tiempo, de la configuración del escenario 4, a los 40 segundos.


La figura 31 representa de la transmisión y recepción de mensajes HELLO y respuesta HELLO durante cada tiempo, de la configuración del escenario 4 a los 60 segundos, cuya red se




representó en la figura 28-C. En esta red a los 60 segundos el nodo 4 varía su posición y pierde conexión con el nodo tres.





La figura 32 representa la transmisión y recepción de mensajes HELLO y mensajes de respuesta HELLO durante cada tiempo, de la configuración del escenario 4 a los 80 segundos, cuya red se representó en la figura 28-D. En ésta red a los 80 segundos el nodo 3 cambia su posición una vez más y pierde conexión con el nodo uno y dos.







En la siguiente tabla se muestran los resultados de las tablas de enrutamiento de cada nodo del escenario 4, a los 80 segundos:

A) B) C) D)

ID= Identificador del nodo. R= Nodo por el cual se puede enrutar. S= Número de saltos. -1=espacios vacios.

Tabla 7. Tablas de enrutamiento de los nodos 1(A), 2(B), 3(C), 4(D).

Para la construcción de las tablas de enrutamiento de los nodos, en estos escenarios no se utilizó el TTL. En el siguiente apartado se explicarán las ventajas que ofrece la implementación desarrollada de este algoritmo.

Nodo 1

ID R S

2 2 1

Nodo 2

ID R S

1 1 1

Nodo 3

ID R S

-1 -1 -1

-1 -1 -1

-1 -1 -1

Nodo 4

ID R S

-1 -1 -1

-1 -1 -1




4.5. Ventajas del algoritmo implementado

En la implementación desarrollada del algoritmo del protocolo de enrutamiento intrazona de PHEZ, no se utilizó el tiempo de vida -time-to-live (TTL), para dar conocer el estado de enlace de los nodos. En cambio, en el algoritmo desarrollado, cada nodo tras la recepción de un mensaje HELLO, transmite un mensaje de respuesta HELLO que contiene su tabla de vecinos. A continuación se muestran las ventajas que tiene esta implementación desarrollada:

1- Cada nodo da a conocer su estado de enlace a sus vecinos directos, evitando así inundar la red con mensajes de estado para cada nodo de la red.

2- El algoritmo garantiza que el estado de enlace de cada nodo de la red, llegue a los

demás nodos en el menor tiempo posible, sin comprometer una cantidad desproporcionada de ancho de banda.

3- Los vecinos para los cuales no se ha recibido ningún mensaje HELLO en un tiempo

especificado se eliminan de la tabla. De esta manera el algoritmo mantiene puesta al día, las tablas de enrutamiento de los nodos que se encuentran dentro de una zona delimitada.

4- Al hacer las diferentes pruebas con zonas que variaban en cantidad y configuración de

los nodos, se pudo comprobar la robustez y eficiencia del algoritmo ante cambios de movilidad de los nodos.

5- Con este algoritmo se podrá saber además, a cuantos saltos se encuentra un nodo de

otro, dentro de una zona delimitada. Permitiendo así que cada nodo sepa cuáles son sus nodos periféricos (los que se encuentran a dos saltos) e interiores (los que se encuentran a un salto).

4.6. Conclusiones

El protocolo de enrutamiento intrazona de PHEZ se encarga de mantener puesta al día las tablas de enrutamiento de los nodos que se encuentran dentro de una zona delimitada. Al hacer las diferentes pruebas con zonas que variaban en cantidad y configuración de los nodos, se pudo comprobar la robustez del algoritmo desarrollado ante cambios de movilidad de los nodos.

En este algoritmo desarrollado no se utilizó el TTL, para dar conocer el estado de enlace de los nodos. En cambio, cada nodo tras la recepción de un mensaje HELLO, transmitirá un mensaje




de respuesta HELLO, que contendrá su tabla de vecinos. Evitando así inundar la red con mensajes de estado de enlace de cada nodo.

Este algoritmo desarrollado garantiza que el estado de enlace de cada nodo de la red, llegue a los demás nodos en el menor tiempo posible, sin comprometer una cantidad desproporcionada de ancho de banda.

El protocolo de enrutamiento intrazona de PHEZ sólo se limita al alcance proactivo de las zonas que se encuentran dentro de su radio R. Las zonas que están fuera de este radio, son cubiertas por el protocolo de enrutamiento interzona, el cual utiliza el enrutamiento reactivo para cubrir esas zonas. El algoritmo implementado del protocolo de enrutamiento interzona de PHEZ será explicado de una manera más detallada en el siguiente capítulo.



Protocolo de enrutamiento interzona de PHEZ 65

Capítulo V. Protocolo de enrutamiento interzona de

PHEZ

5.1. Introducción

En este capítulo se detallará la implementación desarrollada del protocolo de enrutamiento interzona de PHEZ. Este protocolo se encarga de proporcionar el enrutamiento entre nodos que deben de comunicarse entre zonas, empleando enrutamiento reactivo.

En los apartados de este capítulo se mostrará de manera detallada el algoritmo implementado del protocolo de enrutamiento interzona de PHEZ, donde se pone de manifiesto el proceso de enrutamiento reactivo. El proceso de enrutamiento reactivo se divide en dos fases: la fase de solicitud de ruta y la fase de respuesta de ruta. En la solicitud de ruta, el nodo origen envía un mensaje de solicitud de ruta a sus nodos periféricos. Si el nodo receptor de un mensaje de solicitud de ruta conoce el destino, responde enviando un mensaje de respuesta de solicitud de ruta, de regreso al nodo origen.

Una vez se haya detallado paso por paso el algoritmo desarrollado, se presentarán diferentes escenarios, donde se probará el funcionamiento del algoritmo. Demostrando así la eficiencia del algoritmo implementado del protocolo de enrutamiento interzona de PHEZ.

5.2. Descripción del protocolo de enrutamiento interzona de PHEZ

En PHEZ la comunicación entre diferentes zonas, es realizada por el protocolo de enrutamiento interzona. El protocolo de enrutamiento interzona de PHEZ utiliza un protocolo para la distribución de mensajes conocido como protocolo frontera. El protocolo frontera permite que los mensajes de solicitud de ruta sean dirigidos fuera de la red local y hacia regiones de la red que no hayan sido cubiertas.

El proceso de enrutamiento reactivo se divide en dos fases: la fase de solicitud de ruta y la fase de respuesta de ruta. En la solicitud de ruta, el nodo origen envía un mensaje de solicitud de ruta a sus nodos periféricos usando el protocolo frontera. El protocolo frontera es el responsable de reenviar mensajes de solicitud de ruta a los nodos periféricos del nodo periférico. Si el nodo receptor de un mensaje de solicitud de ruta conoce el destino, responde enviando un mensaje de respuesta de solicitud de ruta de regreso al nodo origen. De lo contrario, continúa el proceso reenvío del mensaje de solicitud de ruta a sus nodos periféricos. De esta manera, la solicitud de ruta se extiende por toda la red. Si un nodo recibe varias copias de la misma solicitud de ruta, éstas se consideran como redundantes y se descartan.




El mensaje de respuesta de solicitud de ruta se envía por cualquier nodo que puede proporcionar una ruta hacia el nodo origen. Para poder enviar la respuesta de vuelta al nodo origen, la información de enrutamiento debe irse acumulando cuando la solicitud se transmite a través de la red.

Ya que las zonas de enrutamiento de nodos vecinos se superponen, cada nodo puede retransmitir mensajes de solicitud de ruta varias veces, lo que origina más tráfico. Para resolver este problema, se necesitan mecanismos de control de consulta.

Existen diferentes mecanismos de control de consulta, los cuales se mencionan a continuación:

Protocolo de resolución de bordercast. Consiste en evitar consultar con mensajes de solicitud de ruta de manera redundante, un nodo periférico que tengan en común varios nodos periféricos. Para dar solución a este problema el protocolo de resolución de bordercast ofrece dos métodos de detección de consulta. Uno donde los nodos son capaces de detectar los mensajes de solicitud de ruta redundantes y otro donde es posible escuchar el tráfico de otros nodos dentro de la cobertura de radio.

Procesamiento de retardo aleatorio. Consiste en que cada nodo periférico programa un retardo aleatorio antes de hacer la construcción de sus nodos periféricos, dentro de la red. Durante este tiempo, el nodo que espera puede detectar los mensajes de solicitud de ruta de los otros nodos periféricos y evitar volver a consultar esos nodos.

Mecanismo de finalización anticipada. Consiste en un procedimiento según el cual si un nodo periférico ya ha sido cubierto por un mensaje de solicitud de ruta, se evita. Se utiliza el conocimiento de la topología local para evitar que los nodos periféricos envíen el mensaje de solicitud de ruta, dentro de las regiones ya cubiertas.

El protocolo de enrutamiento interzona de PHEZ, no utiliza ninguno de estos mecanismos de control de consulta, para evitar que lleguen mensajes de solicitud de ruta de manera redundante a regiones que ya han sido cubiertas. En cambio, se utiliza un número de secuencia en el mensaje. El mensaje de solicitud de ruta trasmitido por el nodo origen lleva un número de secuencia único. Cada nodo que reciba este mensaje de solicitud de ruta debe guardar la solicitud de ruta, el tiempo en que se realizó y el número de secuencia, en su tabla de petición de ruta. De esta manera si los nodos reciben un mensaje de solicitud de ruta con el mismo número de secuencia lo evitan, porque se considera redundante.

En el siguiente apartado se muestra la implementación desarrollada del algoritmo del protocolo de enrutamiento interzona de PHEZ.




5.3. Algoritmo del protocolo de enrutamiento interzona de PHEZ

En la figura 33 se enumeran los pasos del algoritmo implementado del protocolo de enrutamiento interzona de PHEZ.

Algoritmo del protocolo de enrutamiento interzona de PHEZ

1- Esperar que el nodo origen necesite llegar a un nodo destino que no se encuentra dentro de su zona de enrutamiento. 2- Se transmite un mensaje de solicitud de ruta a los nodos periféricos del nodo origen. 3- Escuchar el canal. 4- Si se recibe un mensaje:

4.1- Comprobar que es la primera vez que se lee el mensaje. 4.2- Comprobar si es un mensaje de solicitud de ruta.

4.2.1 Si es un mensaje de solicitud de ruta, se hace la retransmisión del mensaje de solicitud de ruta al nodo periférico.

4.3- Comprobar si es un mensaje de retransmisión de solicitud de ruta para nodo periférico. 4.3.1- Si es un mensaje de retransmisión de solicitud de ruta, el nodo periférico comprueba que tiene la ruta en su tabla de vecinos y se emite un mensaje de respuesta de solicitud de ruta.

4.4- Comprobar si es un mensaje de respuesta de solicitud de ruta. 4.4.1 Si es un mensaje de respuesta de solicitud de ruta, se desempaqueta y se guarda la ruta en la tabla de enrutamiento.

Figura 33. Algoritmo implementado del protocolo de enrutamiento interzona de PHEZ.

La figura 34 es una representación grafica de la descripción del algoritmo del protocolo de enrutamiento interzona de PHEZ.




NO

NO

SI NO

SI

SI NO NO SI NO

SI

Figura 34. Representación del algoritmo implementado del protocolo de enrutamiento interzona de

PHEZ.

Escuchar el canal.

Descarto el mensaje. Es el nodo interior del nodo periférico.

Retransmisión del mensaje de

solicitud de ruta.

Transmisión de mensaje de

solicitud de ruta.

Esperar que un nodo necesite llegar a un nodo destino, que no se encuentre en su zona.

INICIO

FIN

Desempaqueta y guarda la ruta.

El nodo periférico

tiene la ruta en su

tabla de vecinos.

Crea mensaje de respuesta de solicitud de ruta.

Es un mensaje de

Solicitud de ruta.

Es un mensaje de retransmisión de solicitud de ruta.

Es un mensaje de respuesta de

solicitud de ruta.




A continuación se describen uno por uno los pasos del algoritmo implementado.

El paso 1 hace referencia a esperar que un nodo origen necesite llegar a un nodo destino, que no se encuentre en su zona de enrutamiento. Si el nodo origen quiere enviar un paquete a un nodo destino, que no se encuentra dentro de su tabla de vecinos o tabla de enrutamiento, debe transmitir un mensaje de solicitud de ruta.

El paso 2 hace alusión a la transmisión de un mensaje de solicitud de ruta. Un mensaje de solicitud de ruta debe contener:

ID del nodo que transmite el mensaje de solicitud de ruta.

ID del nodo destino, para el cual se solicita la ruta.

Identificador del mensaje de solicitud de ruta.

Número de secuencia del mensaje.

Una vez se ha transmitido el mensaje de solicitud de ruta, se debe escuchar el canal, que es el paso 3 del algoritmo. Si se recibe un mensaje, tal como lo indica el paso 4, se debe verificar que es la primera vez que se lee el mensaje, para evitar que un nodo lea dos veces un mismo mensaje, agotando así el paso 4.1.

Una vez se ha verificado que es la primera vez que se lee ese mensaje, se debe comprobar si es un mensaje de solicitud de ruta, tal como lo indica el paso 4.2. Se comprueba si es un mensaje de solicitud de ruta, mediante el identificador de mensajes de solicitud de ruta.

Si es un mensaje de solicitud de ruta se procede a agotar el paso 4.2.1, hacer la retransmisión del mensaje de solicitud de ruta al nodo periférico correspondiente.

Se debe comprobar si es un mensaje de retransmisión de solicitud de ruta para nodo periférico, tal como lo indica el paso 4.3. Se comprueba si es un mensaje de retransmisión de solicitud de ruta para nodo periférico, mediante el identificador de mensajes de retransmisión de solicitud de ruta para nodo periférico.

Si se recibe un mensaje de retransmisión de solicitud de ruta para nodo periférico, como lo indica el paso 4.3.1, se debe de verificar que el nodo que recibe el mensaje de retransmisión de solicitud de ruta sea el nodo periférico al cual se le retransmitió el mensaje. Se debe comprobar que es la primera vez que el nodo periférico lee el mensaje de retransmisión de solicitud de ruta. Además el nodo periférico debe comprobar si tiene la ruta en su tabla de vecinos o en su de tabla de enrutamiento. Un mensaje de retransmisión de solicitud de ruta debe contener:




ID del nodo que retransmite el mensaje de solicitud de ruta.

ID del nodo periférico al cual se le envía el mensaje.

ID del nodo destino (para el cual se solicita la ruta).

Identificador del mensaje de retransmisión solicitud de ruta.

Número de secuencia del mensaje de solicitud de ruta.

Se debe comprobar si se recibe un mensaje de respuesta de solicitud de ruta, tal como lo indica el paso 4.4. Esto se puede verificar mediante identificador de mensajes de respuesta de solicitud de ruta. Un mensaje de respuesta de solicitud de ruta debe contener:

ID del nodo que transmite el mensaje de respuesta de solicitud de ruta.

ID del nodo al cual se le envía el mensaje de respuesta de solicitud de ruta.

Identificador del mensaje de respuesta de solicitud de ruta.

Un paquete que contiene la ruta para llegar al nodo destino.

Si se recibe un mensaje de respuesta de solicitud de ruta, como lo indica el paso 4.4.1, se debe desempaquetar el paquete, que contiene la ruta para llegar al nodo destino y guardarla en la tabla de enrutamiento del nodo.

Retransmisión del mensaje de solicitud de ruta al nodo periférico.

A continuación se presentan los procedimientos necesarios para realizar la retransmisión del mensaje de solicitud de ruta al nodo periférico:

Se comprueba que el nodo que recibe el mensaje de solicitud de ruta, sea el nodo interior por el cual se puede llegar al nodo periférico. Se sigue el siguiente procedimiento:

Se busca en la tabla de vecinos del nodo origen, que transmitió el mensaje de solicitud de ruta, los nodos interiores por los cuales se puede llegar a los nodos periféricos del nodo origen:

- Si el nodo interior que recibe el mensaje de solicitud de ruta, es por el cual se puede llegar al nodo periférico. El nodo interior debe retransmitir el mensaje de solicitud de ruta al nodo periférico. El nodo interior debe guardar la solicitud de ruta, el tiempo en que se realizó y el número de secuencia, en su tabla de petición de ruta. De esta manera se evita que este nodo interior reciba mensajes de solicitud de ruta redundantes.




- Si no es el nodo interior por el cual se puede llegar al nodo periférico, se descarta el mensaje de solicitud de ruta.

Comprobar que es la primera vez que el nodo periférico lee el mensaje de retransmisión de solicitud de ruta.

Para comprobar que es la primera vez que el nodo periférico lee el mensaje de retransmisión de solicitud de ruta se deben agotar los siguientes pasos:

Se debe comprobar que el nodo periférico no tenga la solicitud de ruta con el mismo número de secuencia del mensaje, en su tabla de petición de ruta.

- Si no la tiene, el nodo periférico debe guardar la solicitud de ruta, el tiempo en que se realizó y el número de secuencia, en su tabla de enrutamiento. De esta manera se evita que este nodo periférico reciba mensajes de solicitud de ruta redundantes.

-El nodo periférico debe verificar si tiene la ruta hacia el nodo destino en su tabla de vecinos o en su tabla de enrutamiento. Si la tiene emite un mensaje de respuesta de solicitud de ruta al nodo origen. Si no la tiene, reenvía el mensaje de solicitud de ruta a sus nodos periféricos.

- Si el nodo periférico tiene la solicitud de ruta con el mismo número de secuencia del mensaje, en su tabla de petición de ruta, se descarta el mensaje de solicitud de ruta.

En el siguiente apartado se mostrarán diferentes escenarios donde se probará el funcionamiento del algoritmo descrito anteriormente.

5.4. Escenarios de funcionamiento del protocolo de enrutamiento interzona de

PHEZ

A continuación se presentan distintos escenarios, donde se implementa el algoritmo desarrollado del protocolo de enrutamiento interzona de PHEZ.

5.4.1. Escenario 1

El escenario 1 se representa mediante la configuración de la red que se muestra en la figura 35. El nodo origen 1 transmite un mensaje de solicitud de ruta a su nodo periférico 3, para llegar al nodo destino 4. El nodo 2 recibe el mensaje de solicitud de ruta para el nodo periférico 3 y hace la retransmisión.




El nodo 3 tras recibir la retransmisión del mensaje de solicitud de ruta busca el nodo destino en su tabla de vecinos y tabla de enrutamiento. El nodo 3 tiene el nodo destino 4 en su tabla de vecinos, por ende transmite un mensaje de respuesta de solicitud de ruta al nodo 1, con la ruta hacia el nodo 4.


En la figura 36 se representa el proceso de transmisión y recepción de mensajes de solicitud de ruta y mensajes de respuesta de solicitud de ruta, durante cada tiempo del escenario 1.

Mensaje de solicitud de ruta. Retransmisión de mensaje de solicitud de ruta para nodo periférico. Mensaje de respuesta solicitud de ruta.

Figura 36. Representación de la transmisión y recepción de mensajes de solicitud de ruta y mensajes de

respuesta de solicitud de ruta, durante cada tiempo, de la configuración del escenario 1.





A) B)

ID= Identificador del nodo. R= Nodo por el cual se puede enrutar. -1=Espacios vacios.

Tabla 8. Tablas de enrutamiento de los nodos 1(A), 3(B).

5.4.2. Escenario 2

El escenario 2 se representa mediante la configuración de la red que se muestra en la figura 37. El nodo origen 1 transmite un mensaje de solicitud de ruta a sus nodos periféricos 5 y 6, para llegar al nodo destino 8, a través de sus nodos interiores 3 y 4 respectivamente. Los nodos periféricos 6 y 5 tras recibir la retransmisión del mensaje de solicitud de ruta, buscan el nodo destino en sus tablas de vecinos y tablas de enrutamiento. Como ambos nodos tienen el nodo destino 8 en sus tablas de vecinos, transmiten un mensaje de respuesta de solicitud de ruta al nodo 1, con la ruta hacia el nodo 8.




Nodo 1

ID R

4 3

-1 -1

-1 -1

Nodo 3

ID R

4 4

-1 -1

-1 -1




A) B) C)





respuesta de solicitud de ruta durante cada tiempo, de la configuración del escenario 2.

Nodo 6

ID R

8 7

-1 -1

-1 -1

Nodo 1

ID R

8 5

8 6

-1 -1

Nodo 5

ID R

8 7

-1 -1

-1 -1




5.4.3. Escenario 3

En este escenario se mostrará una configuración inicial. Donde el nodo 2 cambiará su posición a los 40 segundos y deja de formar parte de la red. Con este escenario se persigue demostrar la eficiencia del algoritmo desarrollado, ante cambios en la movilidad de los nodos.

El escenario 3 se representa mediante la configuración de la red que se muestra en la figura 39. El nodo origen 1 transmite un mensaje de solicitud de ruta a sus nodos periféricos 5 y 6, para llegar al nodo destino 8, a través de sus nodos interiores 3 y 4 respectivamente. Los nodos periféricos 6 y 5 tras recibir la retransmisión del mensaje de solicitud de ruta, buscan el nodo destino en sus tablas de vecinos y tablas de enrutamiento. Como ambos nodos tienen el nodo destino 8 en sus tablas de vecinos, transmiten un mensaje de respuesta de solicitud de ruta al nodo 1, con la ruta hacia el nodo 8.

A)

B)

Figura 39. Configuración de la red del escenario 3 a diferentes tiempos, inicialmente(A), 40 segundos(B).






A) B) C)





respuesta de solicitud de ruta durante cada tiempo, de la configuración del escenario 3.

Con este escenario se puede concluir que el proceso de solicitud de ruta y respuesta de solicitud de ruta, no se ve afectado por la movilidad de los nodos. En el siguiente apartado se explicarán las ventajas que ofrece la implementación desarrollada de este algoritmo.

Nodo 6

ID R

8 7

-1 -1

-1 -1

Nodo 1

ID R

8 5

8 6

-1 -1

Nodo 5

ID R

8 7

-1 -1

-1 -1




5.5. Ventajas del algoritmo implementado

En la implementación desarrollada del algoritmo del protocolo de enrutamiento interzona de PHEZ, no se utilizaron los mecanismos de detección de mensajes de solicitud de ruta redundantes existentes. En cambio en el protocolo de enrutamiento interzona desarrollado, para evitar que lleguen mensajes de solicitud de ruta de manera redundante a regiones que ya han sido cubiertas, se utiliza un número de secuencia en el mensaje. A continuación se muestran las ventajas que tiene esta implementación desarrollada:

1- Los nodos periféricos no deben esperar un tiempo aleatorio antes de la construcción de la red de nodos periféricos y la finalización anticipada. Haciendo de este algoritmo más rápido y eficiente.

2- Las rutas se almacenan durante un tiempo especificado. De esta manera el algoritmo mantiene puesta al día, las tablas de enrutamiento de los nodos que se encuentran dentro de una zona delimitada.

3- El algoritmo garantiza que los mensajes de solicitud de ruta de cada nodo de la red, lleguen a los demás nodos en el menor tiempo posible, sin comprometer una cantidad desproporcionada de ancho de banda.

4- Se reduce la probabilidad de recibir el mismo mensaje de solicitud de ruta de varios nodos.

5.6. Conclusiones

La comunicación entre diferentes zonas en PHEZ, es realizada por el protocolo de enrutamiento interzona. El protocolo de enrutamiento interzona de PHEZ utiliza un protocolo para la distribución de mensajes conocido como protocolo frontera. El protocolo frontera permite que los mensajes de solicitud de ruta sean dirigidos fuera de la red local y hacia regiones de la red que no hayan sido cubiertas.

En el protocolo de enrutamiento interzona de PHEZ, para evitar que lleguen mensajes de solicitud de ruta de manera redundante a regiones que ya han sido cubiertas, se utiliza un número de secuencia en el mensaje. El mensaje de solicitud de ruta trasmitido por el nodo origen lleva un número de secuencia único. Cada nodo que reciba este mensaje de solicitud de ruta debe guardar la solicitud de ruta, el tiempo en que se realizó y el número de secuencia, en su tabla de petición de ruta. De esta manera si los nodos reciben un mensaje de solicitud de ruta con el mismo número de secuencia lo evitan, porque se considera redundante.




Este algoritmo desarrollado garantiza que los mensajes de solicitud de ruta de cada nodo de la red, lleguen a los demás nodos en el menor tiempo posible, sin comprometer una cantidad desproporcionada de ancho de banda. Reduce la probabilidad de recibir el mismo mensaje de solicitud de ruta de varios nodos.

En el siguiente capítulo se presentarán los resultados de las simulaciones del protocolo híbrido de enrutamiento basado en zonas (PHEZ) desarrollado en este proyecto, ante diferentes configuraciones de nodos móviles.



Simulaciones 79

Capítulo VI. Simulaciones

6.1. Introducción

En este capítulo se presentarán los resultados de las simulaciones del protocolo PHEZ, ante diferentes configuraciones de nodos móviles. Se analizarán los resultados obtenidos en tres tipos de pruebas:

Comportamiento del protocolo en diferentes configuraciones.

Robustez ante variaciones de parámetros del escenario.

Comparación del protocolo desarrollado con otros métodos.

En los apartados de este capítulo se detallarán los parámetros tomados en cuenta para la generación de los escenarios, así como los datos utilizados para su análisis. Se mostrarán de manera detallada los resultados de las simulaciones, bajo diferentes circunstancias. Para las simulaciones se crearon redes de 15, 30 y 50 nodos móviles. Estos escenarios serán simulados bajo diferentes velocidades y frecuencia de transmisión de paquetes de tráfico. Una vez se hayan recogido los datos de las simulaciones, se representarán los resultados del tráfico recibido frente al transmitido y el tráfico cursado del protocolo PHEZ. Se representará la robustez del protocolo ante variaciones de parámetros de los diferentes escenarios y se comparará el protocolo desarrollado con otros dos protocolos de enrutamiento diferentes.

Por último pero no menos importante, se comparará el protocolo desarrollado con otros dos protocolos de enrutamiento diferentes.

6.2. Generación de escenarios

Para la generación de los escenarios se han tomado en cuenta los siguientes parámetros:

Número de nodos: Sera un parámetro clave para probar la escalabilidad del protocolo. Se diseñaron tres redes de 15, 30 y 50 nodos móviles, a los cuales se les fijaron velocidades distintas.

Velocidad de los nodos: La velocidad de los nodos es un parámetro importante ya que determina la dinámica de los diferentes escenarios con el tiempo. Para realizar las simulaciones se han elegido tres velocidades: velocidad baja 0.1 m/s, velocidad media 1.6 m/s y velocidad alta 5.5 m/s.



Simulaciones 80

Canal de transmisión: El canal se modelará mediante la distancia entre los nodos transmisor y receptor, de forma que para cada distancia D existe una probabilidad de que un paquete llegue al receptor. En las diferentes simulaciones para este protocolo se asumirá que nuestros transmisores de radio tienen una cobertura de 200 metros.

Tipo de tráfico: Se han supuesto tres tipos de tráfico diferentes: tráfico bajo, tráfico medio y tráfico alto, los cuales se muestran a continuación:

Tráfico bajo: se transmite un paquete cada 3.3 s.

Tráfico medio: se transmite un paquete cada 1 s.

Tráfico alto: se transmite un paquete cada 0.033 s.

6.2.1. Lectura y procesado de los resultados

Para la lectura y procesado se tomarán en cuenta los siguientes datos, que una vez hayan sido analizados se representarán:

Tráfico transmitido: Es el tráfico de aplicación que cada nodo ha transmitido según la frecuencia de transmisión especificada durante la simulación. En el caso ideal coincidirá con el tráfico deseado e indicado como parámetro inicial a la simulación, pero en una situación realista será algo menor, ya que el nodo no siempre dispone de la ruta al destino. Tráfico recibido: Es el tráfico de aplicación que los nodos han recibido durante la simulación. De nuevo, en el caso ideal será igual al tráfico transmitido, pero pueden producirse errores en los enlaces de las rutas por el movimiento de los nodos. Por tanto, el tráfico recibido normalmente será menor que el tráfico transmitido.

Tráfico del protocolo: Es el tráfico propio del protocolo de rutado vertido al canal.

6.3. Comportamiento ante diferentes configuraciones

Para medir la eficacia y eficiencia del protocolo PHEZ, se han seleccionado tres tipos de configuraciones donde se han modificado las condiciones descritas en el apartado anterior.

Para cada configuración se han generado 10 escenarios donde la ubicación inicial de los nodos es aleatoria. Las configuraciones seleccionadas para la simulación son: caso favorable, caso intermedio y caso desfavorable.



Simulaciones 81

En las simulaciones realizadas el número de nodos, la velocidad y la frecuencia de transmisión de paquetes de tráfico, irán tomando valores distintos. El caso más favorable es aquél que posee una baja velocidad de movilidad de los nodos y baja frecuencia de transmisión de paquetes de tráfico y, el más desfavorable, el de una alta velocidad de movilidad de los nodos y alta frecuencia de transmisión de paquetes de tráfico. En estas simulaciones se medirá el tráfico transmitido y recibido por los nodos y el tráfico del protocolo.

6.3.1. Configuración 1: Caso Favorable

En esta configuración se han seleccionado las condiciones que representan el caso más favorable. Una velocidad baja y tráfico bajo. Estas condiciones se aplicaron a configuraciones de 15, 30 y 50 nodos. La velocidad de los nodos será de 0.1m/s (velocidad baja), por ello la dinámica del escenario variará de forma lenta. La frecuencia con la que se transmiten paquetes de tráfico es de cada 3.3 segundos (tráfico bajo). Los datos elegidos para cada escenario se muestran en la tabla 10.

Número de nodos

Velocidad Rango de cobertura

Tráfico

15 0.1 m/s 200 m Bajo

30 0.1 m/s 200 m Bajo

50 0.1 m/s 200 m Bajo Tabla 10. Parámetros del caso favorable.

En la figura 41 se representa el tráfico transmitido frente al tráfico recibido y tráfico del protocolo de los 10 escenarios distintos de 15, 30 y 50 nodos móviles, bajo los parámetros mencionados anteriormente. Se puede resaltar que en los tres casos el tráfico del protocolo que cursa cada nodo se puede considerar despreciable con respecto al tráfico de aplicación. Aunque el tráfico del protocolo es mayor a medida que aumenta la cantidad de nodos de la red. En la configuración de 30 y 50 nodos, la probabilidad de que los nodos estén aislados es muy baja debido al alto número de nodos y la baja velocidad.

El tráfico que se recibe es menor que el transmitido en los tres casos cuando debería de ser prácticamente igual ya que en esta configuración la mayoría de los nodos son vecinos y su movimiento es mínimo. El motivo es que se ha asumido que los mensajes tienen una probabilidad de pérdida, que aún en el caso más favorable puede tener cierto impacto, ya que la mayoría de los paquetes se retransmiten un cierto número de veces.



Simulaciones 82

1 2 3 4 5 6 7 8 9 100

1

2

3

4

5

6

7

8x 10

4

Escenarios

Trá

fico e

n B

yte

s

15 nodos moviles velocidad baja tráfico bajo

Tráfico transmitido

Tráfico recibido

Tráfico del protocolo

1 2 3 4 5 6 7 8 9 101

2

3

4

5

6

7

8x 10

4 30 nodos móviles velocidad baja tráfico bajo

Escenarios

Trá

fico e

n B

yte

s


Tráfico recibido


1 2 3 4 5 6 7 8 9 102.5

3

3.5

4

4.5

5

5.5

6

6.5

7

7.5x 10

4 50 nodos móviles velocidad baja tráfico bajo

Trá

fico e

n B

yte

s

Escenarios


Tráfico recibido


Figura 41: Tráfico transmitido, recibido y del protocolo cursado por: 15 nodos (arriba), 30 nodos(medio) y

50 nodos (bajo). Caso favorable.



Simulaciones 83

6.3.2. Configuración 2: Caso intermedio

En esta configuración se han seleccionado las condiciones que representan el caso intermedio, una velocidad media y tráfico medio. Estas condiciones se aplicaron a las configuraciones de 15, 30 y 50 nodos móviles. La velocidad de los nodos será de 1.6 m/s (velocidad media), por ello la dinámica del escenario variará de forma más rápida que la anterior. La frecuencia con la que se transmite un paquete de tráfico es de cada 1 segundo (tráfico medio), lo que provocará más tráfico. Indicar que al generar los escenarios de forma aleatoria, sigue existiendo la probabilidad de nodos aislados que no puedan ni transmitir ni recibir ningún mensaje. Los datos elegidos para cada escenario se muestran la tabla 11.

Número de nodos


Tráfico

15 1.6 m/s 200 m Medio

30 1.6 m/s 200 m Medio

50 1.6 m/s 200 m Medio Tabla 11. Parámetros del caso intermedio.

En la figura 42 se representa el tráfico transmitido frente al tráfico recibido y tráfico del protocolo de los 10 escenarios distintos de 15, 30 y 50 nodos móviles, bajo los parámetros mencionados anteriormente.

En este caso el tráfico que se transmite al canal es mayor debido a que la frecuencia con la que se transmite un paquete es de cada 1 segundo. En este caso la pérdida de paquetes es ligeramente mayor debido al mayor movimiento de los nodos.

Niveles muy altos de movilidad provocan la pérdida de paquetes. El proceso de búsqueda de rutas requiere cierto tiempo y en el retardo desde que se descubrió la ruta hasta que se utilizó, la movilidad puede destruir algunas rutas, teniendo como resultado que el paquete se ha cursado pero no llega a su destino. Por este motivo, a medida que se aumenta la velocidad de los nodos, el tráfico recibido de cada nodo irá disminuyendo. El motivo de esta disminución se debe a rupturas de enlaces de comunicación entre dos nodos originada por su movimiento.

El tráfico del protocolo que cursa cada nodo sigue siendo despreciable para los tres casos.



Simulaciones 84

1 2 3 4 5 6 7 8 9 100

0.5

1

1.5

2

2.5x 10

5

Escenarios

15 nodos moviles velocidad media tráfico medio

Trá

fico

en B

ytes


Tráfico recibido


1 2 3 4 5 6 7 8 9 100

0.5

1

1.5

2

2.5x 10

5 30 nodos móviles velocidad media tráfico medio

Trá

fico

en B

ytes

Escenarios


Tráfico enviado


1 2 3 4 5 6 7 8 9 10

0

0.5

1

1.5

2

2.5x 10

5 50 nodos móviles velocidad media tráfico medio

Trá

fico

en B

ytes

Escenarios


Tráfico recibido


Figura 42: Tráfico transmitido, recibido y del protocolo cursado por: 15 nodos (arriba), 30 nodos

(medio) y 50 nodos (bajo). Caso intermedio.



Simulaciones 85

6.3.3. Configuración 3: Caso desfavorable

En esta configuración se han seleccionado condiciones más desfavorables que las mostradas anteriormente. Los nodos tendrán una velocidad alta, por lo que los escenarios sufrirán grandes cambios con el paso del tiempo. Además la frecuencia con la que se transmite un paquete es de 0.033 segundos aumentando esto la cantidad de tráfico. Los datos elegidos para cada escenario se muestran en la tabla 12.

Número de nodos


Tráfico

15 5.5 m/s 200 m Alto

30 5.5 m/s 200 m Alto

50 5.5 m/s 200 m Alto Tabla 12. Parámetros del caso desfavorable.

En la figura 43 se representa el tráfico transmitido frente al tráfico recibido y tráfico del protocolo de los 10 escenarios distintos de 15, 30 y 50 nodos móviles, bajo los parámetros mencionados anteriormente.

Se observa que en los tres casos el tráfico que se recibe es menor que el transmitido debido a la alta movilidad de los nodos y como se explicó anteriormente el motivo de esta disminución se debe a rupturas de enlaces de comunicación entre dos nodos originada por su movimiento. El tráfico que se transmite al canal es mayor debido a que la frecuencia con la que se transmiten los paquetes al canal es mayor.

El tráfico del protocolo que cursa cada nodo sigue siendo despreciable para los tres casos.



Simulaciones 86

1 2 3 4 5 6 7 8 9 100

1

2

3

4

5

6

7x 10

6

Escenarios

Trá

fico e

n B

yte

s

15 nodos móviles velocidad alta trafico alto


Tráfico recibido


1 2 3 4 5 6 7 8 9 100

1

2

3

4

5

6

7x 10

6 30 nodos móviles velocidad alta tráfico alto

Trá

fico e

n B

yte

s

Escenarios


Tráfico enviado


1 2 3 4 5 6 7 8 9 100

1

2

3

4

5

6

7x 10

6 50 nodos móviles velocidad alta tráfico alto

Escenarios

Trá

fico e

n B

yte

s


Tráfico recibido


Figura 43: Tráfico transmitido, recibido y del protocolo cursado por: 15 nodos (arriba), 30 nodos

(medio) y 50 nodos (bajo). Caso desfavorable.



Simulaciones 87

6.3.4. Comparación

En este apartado se presentarán los resultados obtenidos en porcentaje del tráfico recibido frente al transmitido para cada caso: caso favorable, caso intermedio y caso desfavorable.

Caso Favorable

En este caso la velocidad de los nodos era de 0.1 m/s (velocidad baja) y la frecuencia con la que se transmitían los paquetes de tráfico era de cada 3.3 segundos (tráfico bajo). Estos parámetros se aplicaron a las configuraciones de 15, 30 y 50 nodos móviles. Bajo las condiciones mencionadas anteriormente se obtuvieron los siguientes resultados del tráfico recibido frente al transmitido para cada una de las configuraciones:

Número de Nodos

Porcentaje de tráfico recibido frente al transmitido (%)

15 90.53

30 90.22

50 87.86

Tabla 13. Resultados del tráfico recibido frente al transmitido. Caso favorable.

A partir de los resultados en la tabla 13 del tráfico recibido frente al transmitido, para las diferentes configuraciones, se puede intuir que el protocolo PHEZ desarrollado, tiene un buen comportamiento en la gestión de tráfico, en el caso supuesto. Aunque la diferencia no es muy marcada con respecto a la configuración de 50 nodos, es evidente que los escenarios de 15 y 30 nodos posee una probabilidad más alta.

Como se mencionó anteriormente el tráfico que se recibe es menor que el transmitido en los tres casos cuando debería de ser prácticamente igual ya que en esta configuración la mayoría de los nodos son vecinos y su movimiento es mínimo. El motivo es que se ha asumido que los mensajes tienen una probabilidad de pérdida, que aún en el caso más favorable puede tener cierto impacto ya que la mayoría de los paquetes se retransmiten un cierto número de veces.

Caso intermedio

En este caso la velocidad de los nodos era de 1.6 m/s (velocidad media) y la frecuencia con la que se transmitían los paquetes de tráfico era de cada 1 segundo (tráfico medio). Estos parámetros se aplicaron a las configuraciones de 15, 30 y 50 nodos móviles. Bajo las condiciones mencionadas anteriormente se obtuvieron los siguientes resultados para cada una de las configuraciones:



Simulaciones 88

Número de Nodos


15 88.70

30 87.77

50 83.92

Tabla 14. Resultados del tráfico recibido frente al transmitido. Caso intermedio.

En este caso la pérdida de paquetes es ligeramente mayor comparada con el caso favorable, debido al mayor movimiento de los nodos. El motivo de la disminución en el porcentaje de tráfico recibido frente al transmitido en esta configuración, se debe a rupturas de enlaces de comunicación entre dos nodos originada por su movimiento. Por este motivo, a medida que se aumenta la velocidad de los nodos, el tráfico recibido de cada nodo irá disminuyendo.

Caso Desfavorable

En este caso la velocidad de los nodos era de 5.5 m/s (velocidad alta) y la frecuencia con la que se transmitían los paquetes de tráfico era de cada 0.033 segundos (tráfico alto). Estos parámetros se aplicaron a las configuraciones de 15, 30 y 50 nodos móviles. Bajo las condiciones mencionadas anteriormente se obtuvieron los siguientes resultados para cada una de las configuraciones:

Número de Nodos


15 74.43

30 73.49

50 63.79

Tabla 15. Resultados del tráfico recibido frente al transmitido. Caso desfavorable.

Como se observa en la tabla 15 que en las tres configuraciones, el tráfico que se recibe es menor que el transmitido frente a los demás casos. Esto se debe a lo mencionado anteriormente, niveles muy altos de movilidad provocan la pérdida de paquetes.



Simulaciones 89

6.4. Robustez

En este apartado se presentará la robustez del protocolo PHEZ, frente a la variación de la velocidad de los nodos, cantidad de nodos y tráfico de la aplicación, partiendo de los datos recogidos de las pruebas anteriores. En cada uno de los experimentos se modifica uno de los parámetros de entrada y se generan diez escenarios diferentes que se simulan para cada uno de los casos.

6.4.1. Robustez frente a la velocidad de los nodos

Para demostrar la robustez frente a la variación de la velocidad de los nodos, se han cogido los datos de la tabla 16. Se suponen tres velocidades: baja, media y alta.

Velocidad baja: 0.1 m/s.

Velocidad media: 1.6 m/s.

Velocidad alta: 5.5 m/s.

Número de nodos


Tráfico

30 0.1 m/s 200 m Medio

30 1.6 m/s 200 m Medio

30 5.5 m/s 200 m Medio Tabla 16. Parámetros para medir la robustez frente a la velocidad de los nodos.

En la figura 44 se pueden observar los resultados obtenidos del tráfico recibido frente al transmitido, para los datos de la tabla 16. El cambio entre las velocidades media y baja influye poco en el ratio de tráfico recibido frente al transmitido. Sin embargo, en el escenario donde la velocidad es alta existe una brecha mayor entre el tráfico recibido frente al transmitido, esto es debido a que niveles muy altos de movilidad provocan la pérdida de paquetes. El proceso de búsqueda de rutas requiere cierto tiempo y en el retardo desde que se descubrió la ruta hasta que se utilizó, la movilidad puede destruir algunas rutas, teniendo como resultado que el paquete se ha cursado pero no llega a su destino. Por este motivo, a medida que se aumenta la velocidad de los nodos, el tráfico recibido de cada nodo irá disminuyendo.

En la figura 45 se representan los resultados del tráfico cursado del protocolo frente al tráfico de la aplicación recibido de cada configuración. Se puede notar que la velocidad no afecta de



Simulaciones 90

forma significativa al protocolo. El pequeño aumento del ratio del tráfico cursado del protocolo frente al tráfico de la aplicación recibido, al introducir nodos rápidos se debe a que al moverse más se destruyen más enlaces, y PHEZ genera más mensajes de solicitud de rutas.

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.50

10

20

30

40

50

60

70

80

90

100

Velocidades

Porc

enta

je d

e t

ráfico r

ecib

ido f

rente

al tr

ansm

itid

o (

%)

Figura 44. Porcentaje de tráfico recibido frente al transmitido.

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.50

5

10

15

20

25

30

Velocidades

Porc

enta

je d

e t

ráfico

curs

ado d

el pro

tocolo

frente

al tr

áfico

de la a

plic

acio

n r

ecib

ido (

%)

Figura 45. Porcentaje de tráfico cursado del protocolo frente al tráfico de la aplicación recibido.



Simulaciones 91

6.4.2. Robustez frente al número de nodos

Para demostrar la robustez frente a la cantidad de nodos de la red se han cogido los datos de la tabla 17. Se suponen tres tamaños diferentes: 15, 20 y 30 nodos.

Número de nodos


Tráfico

15 1.6 m/s 200 m Medio

30 1.6 m/s 200 m Medio

50 1.6 m/s 200 m Medio Tabla 17. Parámetros para medir la robustez frente al número de nodos.

En la figura 46 se pueden observar los resultados obtenidos entre el tráfico recibido frente al transmitido, para las configuraciones de 15, 30 y 50 nodos móviles. El protocolo desarrollado tiene un buen comportamiento en las diferentes configuraciones. Aunque existe un pequeño descenso del 6% entre el tráfico recibido frente al transmitido entre la configuración de 30 y 50 nodos, el protocolo PHEZ se mantiene constante entorno a un ratio del trafico recibido del 83%, demostrando así que puede ser escalable.

En la figura 47 se representan los resultados del tráfico cursado del protocolo frente al tráfico de la aplicación recibido de cada configuración. A medida que se aumente la cantidad de nodos de la red aumentará también el tráfico del protocolo, debido a que cada nodo debe transmitir mensajes HELLO a intervalos regulares. A mayor número de nodos mayor será la cantidad de mensajes HELLO. Así mismo aumenta la cantidad de mensajes de respuesta HELLO ya que tras la recepción de un mensaje HELLO el nodo debe transmitir un mensaje de respuesta HELLO. Siendo estas circunstancias explicadas, las principales causante de que al aumentar el número de nodos aumente el tráfico del protocolo.



Simulaciones 92

15 20 25 30 35 40 45 500

10

20

30

40

50

60

70

80

90

100

Porc

enta

je d

e t

ráfico r

ecib

ido f

rente

al tr

ansm

itid

o (

%)

Número de nodos Figura 46. Porcentaje de tráfico recibido frente al transmitido.

15 20 25 30 35 40 45 500

10

20

30

40

50

60

70

80

90

100

Número de nodos

Porc

enta

je d

e t

ráfico c

urs

ado d

el pro

tocolo

frente

al tr

áfico d

e la a

plicacio

n r

ecib

ido (

%)




Simulaciones 93

6.4.3. Robustez frente al tráfico de aplicación

Para medir la robustez frente al tráfico de aplicación se han utilizado los datos de la tabla 18. Se suponen tres niveles de tráfico: bajo, medio y alto.


Tráfico medio: se transmite un paquete cada 1 s.


Número de nodos


Tráfico

30 1.6 m/s 200 m Bajo

30 1.6 m/s 200 m Medio

30 1.6 m/s 200 m Alto Tabla 18. Parámetros para medir la robustez frente al tráfico de aplicación.

En la figura 48 se pueden observar los resultados obtenidos del tráfico recibido frente al transmitido, para los tipos de tráfico supuestos. Para los tipos de tráficos supuestos, se tiene una buena respuesta del protocolo PHEZ ante los mensajes de tráfico recibidos frente a los transmitidos. Demostrando así que el protocolo es robusto frente al tráfico de aplicación. En la figura 49 se representan los resultados del porcentaje de tráfico cursado del protocolo frente al tráfico de la aplicación recibido. A medida que se aumenta la frecuencia de tráfico aumentará el tráfico del protocolo. Si la frecuencia envío de tráfico es mayor a la frecuencia de los mensajes HELLO, las tablas de vecinos de los nodos, pueden estar incompletas al momento de transmitir un paquete de tráfico a un nodo destino. Si un nodo quiere transmitir un paquete a un nodo que no tiene en su tabla de vecinos o tabla de enrutamiento, se genera un mensaje de solicitud de ruta. Este mensaje se transmite por la red hasta que se encuentre una ruta hacia el nodo destino, provocando un aumento del tráfico del protocolo cursado.



Simulaciones 94

0 0.5 1 1.5 2 2.5 30

10

20

30

40

50

60

70

80

90

100

Cantidad de tráfico de aplicación

Porc

enta

je d

e t

ráfico r

ecib

ido f

rente

al tr

ansm

itid

o (

%)

Bajo AltoMedio


0 0.5 1 1.5 2 2.5 30

10

20

30

40

50

60

70

80

90

100

Cantidad de tráfico de aplicación

Porc

enta

je d

e

tráfico

curs

ado d

el pro

tocolo

frente

al tr

áfico d

e la a

plic

acio

n r

ecib

ido (

%)

Bajo Medio Alto


6.5. Comparación del protocolo implementado con otros protocolos

En este apartado se mostrarán otros dos protocolos con los cuales se compara el protocolo PHEZ desarrollado en este trabajo. Dichos protocolos han sido implantados por el Grupo de Robótica y Visión (GRVC).



Simulaciones 95

Los dos protocolos con los cuales se compara el protocolo PHEZ son:

AODV (Ad-hoc On Demand Distance Vector): Es un protocolo reactivo de encaminamiento para redes ad-hoc. Está basado en vector de distancias y opera bajo demanda, es decir, que sólo comienza la búsqueda de rutas cuando es requerido o se necesita establecer una comunicación entre dos nodos. El descubrimiento de rutas genera tablas de encaminamiento, las cuales se almacenan localmente en cada nodo y sirven de medio para establecer enlaces con el resto de los nodos. Este protocolo es simple y eficiente, busca una ruta cuando existe una solicitud, y escoge la ruta que responda primero, ya que se asume que la respuesta se transmitió por la ruta más corta. Además, los mensajes de enrutamiento no contienen información de la ruta completa, por lo que tienen un tamaño fijo.

OLSR (Optimiced Link-State Routing Protocol): Es un protocolo diseñado específicamente para MANETs (Mobile Ad-hoc NETworks). Se trata de un protocolo proactivo, lo que implica que cada nodo dispone, en todo momento, de la información necesaria para comunicarse con el resto de nodos de la red. Una de las novedades más interesantes que introduce OLSR es el concepto de MPR (Multipoint Relay), cuya utilidad principal es optimizar los niveles de carga de señalización introducida en la red. Sólo los nodos seleccionados como MPR son responsables de reenviar el tráfico de control, el cual debe difundirse por toda la red.

6.5.1. Robustez de los protocolos AODV, OSLR y PHEZ

A continuación se presentan pruebas que se realizaron a los protocolos AODV, OSLR y el protocolo PHEZ para medir la robustez de estos ante variaciones de ciertos parámetros y poder compararlos. En cada uno de los experimentos que se mostrarán a continuación se varía uno de los parámetros de entrada y se generan veinte escenarios diferentes que se simulan para cada uno de los protocolos.

A continuación se presentan los resultados de la robustez de los tres protocolos en conjunto, con estos datos se pondrán comparar estos dos protocolos con el desarrollado en este proyecto.

Robustez frente a la velocidad de los nodos

Para medir la robustez frente a la velocidad de los nodos se han utilizado los datos que se muestran a continuación:



Simulaciones 96

Velocidad baja: 10 nodos con velocidad de 30 km/h.

Velocidad media: 5 nodos con velocidad de 30 km/h y 5 nodos con velocidad de 80 km/h.

Velocidad alta: 10 nodos con velocidad de 80 km/h.

En la figura 50 se puede observar el tráfico recibido frente al transmitido de los tres protocolos. La velocidad de los diferentes nodos de la red influye poco en el ratio de tráfico recibido frente al transmitido. Sin embargo, el porcentaje de tráfico recibido frente al transmitido del protocolo PHEZ implementado en este trabajo, es mayor que para los protocolos AODV y OSLR.

En cuanto al tráfico del protocolo que se representa en la figura 51, la velocidad de los nodos afecta de forma significativa al protocolo AODV. Sin embargo, el tráfico cursado de los protocolo PHEZ y OSLR no se ve afectado.




Simulaciones 97

Figura 51. Tráfico del protocolo cursado.

Robustez frente al número de nodos

Para medir la robustez frente al tamaño de la red de nodos de los protocolos AODV, OLSR y PHEZ se utilizaron redes con tres tamaños diferentes: 10, 20 y 30 nodos. En la figura 52 tenemos de nuevo el ratio entre el tráfico recibido frente al transmitido. Se observa como PHEZ tiene mejor comportamiento que los otros dos, manteniendo constante su ratio en torno al 72 %. De los tres, AODV es el que se ve más afectado con el aumento de nodos.

En cuanto al tráfico de los protocolos que se muestran en la figura 53, se observa que un aumento en la red provoca un incremento exponencial en el tráfico de AODV, mientras que OLSR y PHEZ se mantienen constantes.



Simulaciones 98





Simulaciones 99

Robustez frente al tráfico de aplicación

Para medir la robustez frente al tráfico de aplicación se utilizaron tres niveles diferentes de tráfico de aplicación: alto, medio y bajo. En la figura 54 se representa el tráfico transmitido frente al recibido para cada uno de los tipos de tráfico supuestos. En general, el ratio de tráfico recibido es bajo en estos tres protocolos debido a que la disposición de los nodos es aleatoria, al igual que los mensajes que se mandan en cada momento. Sin embargo, PHEZ sigue mostrando mejor rendimiento en cuanto a la gestión de tráfico recibido que los protocolos AODV y OSLR.


En cuanto al tráfico de los protocolos que se muestran en la figura 55, se observa que el de AODV crece de manera lineal con el tráfico de aplicación. En cambio, los protocolos PHEZ Y OLSR se mantienen prácticamente sin cambio alguno.



Simulaciones 100


6.7. Conclusiones

En este capítulo se analizó el protocolo PHEZ, tanto en términos del comportamiento ante un conjunto de escenarios, así como en términos de robustez ante cambios de número de nodos, niveles de tráfico y velocidad de los nodos. Una vez obtenidos los datos necesarios de robustez se comparó el protocolo desarrollado con otros dos protocolos de enrutamiento distintos. A continuación se resumen brevemente las conclusiones que pueden deducirse de este análisis.

Ante cambios en la cantidad de nodos de la red, se logró comprobar la escalabilidad del protocolo desarrollado, ya que el porcentaje de tráfico recibido frente al transmitido se mantuvo constante en un ratio del 83% al aumentar el tamaño de la red.

El protocolo PHEZ presenta un buen comportamiento ante el tráfico recibido frente al transmitido, en escenarios de cambios de movilidad de los nodos. Aunque a medida que se aumenta la velocidad de los nodos, el tráfico recibido de cada nodo disminuye, debido a que niveles muy altos de movilidad provocan la pérdida de paquetes.



Simulaciones 101

Para los casos de tráfico supuesto, se obtuvo una buena respuesta del protocolo ante los mensajes de tráfico recibidos frente a los transmitidos, demostrando así su robustez frente al tráfico de la aplicación.

A partir de la comparación realizada con los dos protocolos se puede deducir que desde el punto de vista de la robustez, el protocolo PHEZ tiene mejor comportamiento que AODV y que OLSR. Y dicha capacidad se mantiene con niveles altos de tráfico. Los dos protocolos con los que se compara el protocolo PHEZ tienen robustez similar cuando se modifica la velocidad de los nodos, pero el protocolo desarrollado en este trabajo es capaz de gestionar más tráfico que estos dos protocolos.



Conclusiones y trabajo futuro 102

Capítulo VII. Conclusiones y trabajo futuro

7.1. Conclusiones

A continuación se presentarán las conclusiones obtenidas a través del desarrollo de este proyecto. Para el desarrollo del protocolo PHEZ, se combinaron dos métodos de enrutamiento completamente diferentes. Dentro de la zona de enrutamiento, el componente proactivo se muestra con el protocolo de enrutamiento intrazona, que mantiene puesta al día las tablas de enrutamiento de los nodos. Las rutas fuera de la zona de enrutamiento, se descubren con el componente reactivo que se muestra con el protocolo de enrutamiento interzona. Logrando con esto combinar las ventajas de los protocolos proactivos y reactivos, para hacer más eficiente el protocolo desarrollado en este trabajo.

Con el algoritmo implementado para el protocolo de enrutamiento intrazona de PHEZ se consiguió garantizar que el estado de enlace de cada nodo de la red llegue a los demás nodos en el menor tiempo posible, sin comprometer una cantidad desproporcionada de ancho de banda.

En la implementación desarrollada del algoritmo del protocolo de enrutamiento interzona de PHEZ, para evitar que lleguen mensajes de solicitud de ruta de manera redundante a regiones que ya han sido cubiertas, se utiliza un número de secuencia en el mensaje. Reduciendo así la probabilidad de recibir el mismo mensaje de solicitud de ruta de varios nodos.

El tráfico cursado del protocolo desarrollado es menor, en comparación con los protocolos de enrutamiento puramente proactivos o reactivos. Es capaz de gestionar más tráfico de la aplicación ante diferentes situaciones, comparado con otros protocolos. Proporciona la ruta con menor número de saltos y descarta las rutas que ya no son válidas, cumpliendo así uno de los requisitos planteados para el desarrollo de este protocolo de enrutamiento.

Los resultados mostrados en este trabajo demuestran que el protocolo de enrutamiento desarrollado presenta:

Un buen comportamiento ante cambios en la cantidad de nodos de la red demostrando así que puede ser escalable. Sin embargo, a medida que se aumente la cantidad de nodos de la red aumentará también el tráfico cursado del protocolo.

Un buen comportamiento ante el tráfico de la aplicación recibido frente al transmitido, en escenarios de cambios de movilidad de los nodos. Aunque a medida que se aumenta la velocidad de los nodos, el tráfico de la aplicación recibido de cada nodo irá




disminuyendo, debido a que niveles muy altos de movilidad provocan la pérdida de paquetes.

Una buena respuesta ante los tipos de tráfico de la aplicación supuestos, demostrando así su robustez frente al tráfico de la aplicación.

En conclusión, el protocolo de enrutamiento que se desarrolló en este trabajo resultó ser escalable con relación al tamaño de la red, además se demostró su robustez ante cambios de la velocidad de los nodos así como ante el tráfico de la aplicación, cumpliendo el objetivo principal de este proyecto.

7.2. Trabajo futuro

De cara a realizar trabajos futuros sobre este proyecto, se enumeran posibles líneas de acción o mejoras a tener en cuenta:

Ampliar el tiempo de mantenimiento de una ruta. En el protocolo desarrollado, una vez se establece la ruta entre el nodo origen y el nodo destino, esta queda almacenada en la tabla de enrutamiento durante un tiempo determinado, tras el cual se elimina. Lo que se propone con este nuevo procedimiento es que si antes de que esto ocurra vuelve a requerirse esta ruta, se amplíe el tiempo de mantenimiento. Al ampliar el tiempo de mantenimiento de una ruta, se evitaría volver a realizar una nueva solicitud de ruta, lo que disminuirá la cantidad de tráfico cursado del protocolo y el retardo de descubrimiento de ruta. Para llevar a cabo este trabajo futuro, cada nodo debe tener una tabla donde se almacenan las rutas que están activas. En esta tabla se debe establecer un tiempo durante el cual se mantiene activa la ruta. Si antes de que se elimine de la tabla vuelve a requerirse esta ruta, este tiempo de mantenimiento se amplia. Se deben hacer diversas pruebas con configuraciones de nodos móviles bajo velocidades distintas, para determinar exactamente que tanto debe ampliarse el tiempo durante el cual una ruta se mantendrá activa, para evitar tener almacenadas rutas obsoletas, ya que la movilidad puede destruir algunas rutas.

Incluir otros mecanismos de detección de solicitud de ruta. En el protocolo PHEZ las zonas de enrutamiento de nodos vecinos se superponen, cada nodo puede retransmitir mensajes de solicitud de ruta varias veces, lo que origina más tráfico. Para resolver este problema, se necesitan otros mecanismos de control de consulta, además del que se utilizó en el desarrollo del protocolo PHEZ. Estos mecanismos se encargarían de dirigir consultas fuera de las zonas cubiertas y terminar los mensajes de solicitud de ruta, antes de ser entregados a los nodos periféricos en las regiones de la red que ya han sido




cubiertas. Para este trabajo futuro, se propone implementar el mecanismo de finalización anticipada, que consiste en que un nodo pueda prevenir que un mensaje de solicitud de ruta entre en las regiones ya cubiertas. El mecanismo de finalización anticipada combina la información obtenida a través de la detección de la solicitud de ruta, con el conocimiento de la topología local, para evitar que los nodos periféricos envíen un mensaje de solicitud de ruta dentro de las regiones cubiertas. El mecanismo de finalización anticipada requiere información de la topología que se extiende fuera de la zona de enrutamiento del nodo.

Validar experimentalmente el protocolo PHEZ. Esto está provisto realizarse en el mes de Diciembre del 2014, en el proyecto CITIUS (Command and control for InteroperabIlity of Unmanned Systems).



Referencias 105

Capítulo VIII. Referencias [Beijar, 2002] N. Beijar, “Zone Routing Protocol (ZRP)”, Ad Hoc Networking, Licentiate course on Telecommunications Technology, 2002. [Boukerche et al., 2001] A. Boukerche, S.K. Das, A. Fabbri, “Analysis of a randomized congestion control scheme with DSDV routing in ad hoc wireless networks”, Journal of Parallel and Distributed Computing 61 (7) (2001) 967–995. [Boukerche et al., 2011] A. Boukerche, B. Turgut, N. Aydin, M.Z. Ahmad, L. Bölöni, and D. Turgut, “Routing protocols in ad hoc networks: a survey”, Computer Networks, 55(13):3032–3080, September 2011. [Clausen et al., 2001] T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum, L. Viennot, “Optimized link state routing protocol for ad hoc networks, in: Proceedings of IEEE INMIC”, December 2001, pp. 62–68. [Clausen, Dean, 2008] T. Clausen, J. Dean, “MANET Neighborhood Discovery Protocol (NHDP)”, Ecole Polytechnique, France Naval Research Laboratory March 10, 2008. [Haas, Pearlman, 2001] Z. J. Haas, M.R. Pearlman, “The Performance of Query Control Schemes for the Zone Routing Protocol”, August 2001, IEEE/ACM Transactions on Networking, Vol. 9, No. 4. [Haas et al., 2001] Z. J. Haas, M.R. Pearlman, P. Samar:” Intrazone Routing Protocol (IARP)”, June 2001, IETF Internet Draft, draft-ietf-manet-iarp-01.txt. [Haas et al., 2001] Z. J. Haas, M.R. Pearlman, P. Samar.: “Interzone Routing Protocol (IERP)”, June 2001, IETF Internet Draft, draft-ietf-manet-ierp-01.txt. [Johnson et al., 2001] D.B. Johnson, D.A. Maltz, J. Broch, DSR: the dynamic source routing protocol for multi-hop wireless ad hoc networks, in: C.E. Perkins (Ed.), Ad Hoc Networking, Addison-Wesley, 2001, pp. 139–172 (Chapter 5). [Johnson et al., 2001] D.B. Johnson, D.A. Maltz, J. Broch, “DSR the dynamic source routing protocol for multi-hop wireless ad hoc networks”, in: C.E. Perkins (Ed.), Ad Hoc Networking, Addison-Wesley, 2001, pp. 139–172 (Chapter 5).

http://www.cs.ucf.edu/~turgut

http://www.cs.ucf.edu/~lboloni

http://www.cs.ucf.edu/~turgut



Referencias 106

[Karp y Kung, 2000] B. Karp, H. Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, in: Proceedings of ACM MobiCom, August 2000, pp. 243–254. [Ko, Vaidya, 2000] Y.Ko y N.H.Vaidya, ”Location-Aided Routing (LAR) in mobile Ac Hoc. Networks.” ACM/Baltzer WINET J. vol. 6. No. 4. 2000. pp.307-21. [Lee, 2009] F. Lee, “Routing in Mobile Ad Hoc Networks University of Guam”, USA, 2009. [Liu, Kaiser, 2000] C. Liu, J. Kaiser “A Survey of Mobile Ad Hoc network Routing Protocols”, 2005. [Mauve y Widmer,2001] Martin Mauve, Jörg Widmer. “Position-based routing in ad-hoc wireless networks”. In Mohammad Ilyas, editor, The Handbook of Ad Hoc Wireless Networks, pages 12-1 - 12-14. CRC Press, Boca Raton, FL, U.S.A., December 2002.University of Mannheimn”, NEC Europe, 2001. [Park y Corson, 1997] V.D. Park, M.S. Corson, A highly adaptive distributed routing algorithm for mobile wireless networks, in: Proceedings of INFOCOM, April 1997, pp. 1405–1413. [Pearlman y Haas, 1999] M.R. Pearlman, Z. J. Haas, “Determining the Optimal Configuration for the Zone Routing Protocol”, IEEE journal on selected areas in communications, vol. 17, no. 8, august 1999. [Pei et al., 2000] G. Pei, M. Gerla, T.-W. Chen, “Fisheye state routing: A routing scheme for ad hoc wireless networks,” presented at the IEEE ICC 2000, New Orleans, LA, June 2000. [Perkins y Royer, 1999] C. Perkins, E. Royer, “Ad hoc On-demand Distance Vector Routing, in: Proceedings of the Second IEEE Workshop on Mobile Computing Systems and Applications”, 1999, pp. 99–100. [Robles et al., 2013] M. Robles, L. Marrone, J. Díaz, A. Barbieri, “Comparación de protocolos de ruteo en redes ad-hoc”, XIX Congreso Argentino de Ciencias de la Computación, CACIC 2013. [Schwier,2005] Jason Schwier, Routing in Ad Hoc Wireless Networks, 2005 [Villasenor et al., 2005] L. Villasenor-Gonzalez, Y. Ge, L. Lamont, “HOLSR: a hierarchical proactive routing mechanism for mobile ad hoc networks”, IEEE Communications Magazine 43 (7) (2005) 118–125.



Referencias 107

proyecto fin de máster: desarrollo de protocolo de enrutamiento

Documents