5/26/2018 ProyectoFundamentosRedesMiguelTenezaca

1/8

ANALISIS COMPARATIVO DE LOS PROTOCOLOS DE ENRUTAMIENTO

AODV Y DSDV, SIMULADOS CON NS2

Liliana Enciso QuispeMiembro IEEE-UPM

Technical University of Loja

Loja, Ecuador

Email: lenciso@utpl.edu.ec

Miguel Tenezaca LimaFundamentos de Redes y Telecomunicaciones

Universidad T ecnica Particular de Loja

Loja, Ecuador

Email: matenezaca@utpl.edu.ec

AbstractEl presente trabajo realizado es sobre un estudiode analisis comparativo entre los protocolos de enrutamientoen redes moviles Ad Hoc - MANET (MOBILE AD HOCNETWORK WORKING GROUP), con los protocolos de en-rutamiento DSR y AOMDV, analizados en dos escenarios(90 y120 nodos) y dos tipos de conexiones(30 y 60 conexiones).

Palabras clave-Redes Ad Hoc, Manet, ns2, protocolos deenrutamiento, AODV, DSR, DSDV, AOMDV.

I. INTRODUCCION

La simulacion es la manera mas propicia para evaluar

soluciones, es especial la experimentacion de nuevas redes

con tecnologas aun no disponibles, como tambien nos

permite simular escenarios predeterminados a buscar una

optima solucion de comunicacion ante las catastofes que

nuestro planeta enfrenta hoy en da.

Las Mobile ad hoc network (MANET) en algunas

ocasiones denominada tambien como malla de nodosmoviles (mobile mesh network), se trata de una red

de dispositivos conectados por wireless y que poseen

propiedades de auto-configuracon, ademas de poseer cierta

mobilidad. Las MANETs son un tipo de wireless ad

hoc networks que forman, por regla general, una malla

enrutable en forma de una capa de enlace de datos. Cada

dispositivo en una MANET posee libertad para desplazarse

independientemente en cualquier direccion, y eso permite

que cambien dinamicamente las condiciones de enlace entre

los dispositivos. [10]

II. REDES MOVILES AD-HOC O MANET

Una red movil Ad hoc es un tipo de red formadapor un grupo de nodos o hosts moviles que forman una

red sin la ayuda de ninguna infraestructura externa. Para

que esto se pueda llevar a la practica es necesario que

los nodos se puedan ayudar mutuamente para conseguir

un objetivo comun: que cualquier paquete llegue a su

destino aunque el destinatario no sea accesible directamente

desde el nodo fuerte. El protocolo de enrutamiento es el

responsable de descubrir las rutas entre los nodos para hacer

posible la comunicacion. Entre ellos estan aplicaciones

militares, operaciones de emergencia de busqueda y rescate,

convenciones, etc. [1] [9]

Los protocolos de enrutamiento Ad- Hoc se clasifican

en: [1]

Reactivos

Proactivos

Hbridos

Jerarquicos

Protocolos de enrutamiento Reactivos

Los protocolos de enrutamiento reactivo o bajo demanda

son aquellos en los cuales se hallan las rutas entre un nodo

origen y un nodo destino bajo demanda de la fuente. Es

decir, que slo cuando sea necesario iniciar una transmision

se buscar una ruta para realizarla. Una vez establecida

la ruta, los nodos que participen en la transmision se

encargaran de su mantenimiento. Las ventajas de este tipo

de protocolos es que no necesitan demasiada senalizacion,

lo cual reduce el overhead y optimiza el uso de las bateras,

al contrario de lo que sucede con los protocolos proactivos.

Sin embargo, el tiempo de establecimiento de las rutas

es mayor, ya que cuando se necesita la ruta se inicia el

mecanismo de descubrimiento de ruta y hasta que ste no

termina no se puede iniciar la transmision [2].

Se diferencian porque entre ellos se encuentran en la

implementacion del mecanismo de descubrimiento de ruta

y en las optimizaciones del mismo, se clasifican en: [2]

AODV(Ad Hoc On Demand Distance Vector Routing)

ABR (Associativity-Based Routing)

CBRP (Cluster-Based Routing Protocol)

DYMO (Dynamic MANET On demand)

DSR (Dynamic Source Routing)

LAR (Location-Aided Routing)

TORA (Temporally Ordered Routing Algorithm)

5/26/2018 ProyectoFundamentosRedesMiguelTenezaca

2/8

Protocolo de enrutamiento AODV (Ad Hoc On Demand

Distance Vector Routing): Fue creado por Charles E. Perkins

como evolucin de su anterior protocolo DSDV (Destination-

Sequenced Distance-Vector). El DSDV inundaba la red de

mensajes de control, de forma que la red se congestionaba

y limitaba la duracion de las bateras de los terminales. [3]

AODV es un protocolo de emrutamiento reactivo disenadopara redes ad hoc de hasta miles de nodos. En este sentido,

los nodos mantienen tablas de enrutamiento tradicional que

especifica el proximo salto a tomar para llegar al destino.

Si no hay informacion en la tabla de enrutamiento de la

fuente entonces una solicitud de ruta es un broadcast. [4] [5]

Cuando un nodo quiere transmitir un paquete a un

destino, lo primero que debe hacer es buscar en su tabla de

encaminamiento a ver si existe una ruta hacia este destino

previamente calculada. En el caso de encontrarla no iniciara

ningn proceso de descubrimiento de ruta, supondra que la

que tiene almacenada en su tabla de encaminamiento es

correcta y esta actualizada. En el caso contrario, comenzar

el proceso de descubrimiento de ruta (Route Discovery)para

encontrar un camino vlido. [8]

El proceso comienza con el envo de un paquete RREQ

(Route Request) en modo broadcast. Este paquete llega

a los nodos vecinos que se encuentran a un salto de

distancia y estos a su vez lo reenvan a sus vecinos y as

sucesivamente hasta llegar al destino. Cualquier nodo que

durante el proceso de busqueda conozca la ruta hacia el

destino, puede contestar con un paquete de RREP al nodo

origen indicando la ruta que necesita. [3] [5]

Protocolo de enrutamiento DSR (Dynamic Source Rout-

ing): Es un protocolo reactivo basado en la fuente, esen-

cialmente crea las rutas unicamente en el caso de que un

nodo fuente necesite enviar datos hacia un nodo destino

(Descubrimiento de Ruta). Se diseo para optimizar el uso del

ancho de banda dentro de una red Ad Hoc, al eliminar los

mensajes de actualizacion periodica que usan los protocolos

proactivos. [11] [12]

Protocolos de enrutamiento Proactivos

Los protocolos de encaminamiento proactivos intentan

mantener tablas de las rutas actualizadas constantemente.

Eso significa que cada nodo debe mantener actualizadauna tabla con todas las rutas hacia los otros nodos. La

informacion que contienen las tablas debe actualizarse

periodicamente y ante cualquier cambio de la topologa

de red. Esta actualizacion constante provoca que estos

protocolos generen una gran cantidad de paquetes de

senalizacion (overhead) lo cual afecta a la utilizacion del

ancho de banda, el throughput y el consumo de energa

entre otras cosas. La ventaja principal que aportan estos

protocolos es que el establecimiento de una nueva ruta para

iniciar una transmision precisa de un tiempo muy pequeno

al tener todos los nodos las tablas de rutas actualizadas.

Ademas, el overhead aunque sea elevado tambien es

bastante estable en el tiempo. El principal problema con

el que se encuentran estos protocolos es cuando las redes

son muy densas y los nodos tienen una movilidad alta ya

que en estos casos el overhead crece muy rapidamente ylas tablas pueden llegar a ser demasiado grandes. [2]

Se distinguen por el numero de tablas, clasificandose

en:

ADV(Adaptative Distance Vector)

CGSR (Cluster Gateway Switch Routing)

DSDV (Destination-Sequenced Distance Vector)

DREAM (Distance Routing Effect Algorithm for Mo-

bility)

HSR (Hierarchical State Routing)

MMWN (Multimedia support in Mobile Wireless Net-works)

OLSR (Optimised Link State Routing)

STAR (Source-Tree Adaptaive Routing)

TBRPF (Topology Dissemination Based on Reverse-

Path Forwarding)

WRP (Wireless Routing Protocol)

Protocolo de enrutamiento DSDV (Destination-Sequenced

Distance Vector):DSDV es esencialmente una modificacion

del algoritmo de encaminamiento Vector Distancia Bellman-

Ford, bien conocido por su utilidad en redes fijas, como

por ejemplo en el protocolo RIP. En este algoritmo, los

nodos vecinos intercambian periodicamente (proactivo) sus

tablas de encaminamiento enteras para estimar la distancia

a la que se encuentran los demas nodos no vecinos.

Las modificaciones introducidas por DSDV proporcionan

basicamente la obtencion de rutas sin bucles mediante la

introduccion de numeros de secuencia para la determinacion

de las rutas mas nuevas. Aunque DSDV solo proporciona

un camino para cada destino, siempre elige el camino mas

corto basandose en el numero de saltos hacia este destino.

DSDV utiliza dos tipos de mensajes de actualizacion,

uno mas grande (full-dump) y otro mucho mas pequeno

(incremental). Los mensajes incrementales pueden utilizarse

para actualizaciones intermedias entre envos periodicos(fulldump) de la tabla entera de encaminamiento. Ademas

se realizan estimaciones de los tiempos de establecimientos

de ruta que retrasaran el envo de mensajes incrementales

para evitar en cadena de estos mensajes. [6] [7]

Protocolo de enrutamiento AOMDV: Comparte muchas

caractersticas en su funcionamiento basico con AODV. Se

basa en el concepto de vector distancia y utiliza aprox-

imacion de salto en salto. Este protocolo ademas des-

5/26/2018 ProyectoFundamentosRedesMiguelTenezaca

3/8

cubre rutas bajo demanda utilizando un procedimiento de

descubrimiento de ruta. En AOMDV la propagacion de

Routers de encaminamiento del nodo origen al nodo destino

establece multiples caminos en reversa junto con los nodos

intermedios al igual que el nodo de destino.

Varios routers de encaminamiento atraviesan rutas de

retorno utilizando varios puntos. AOMDV tambien proveenodos intermedios con camino alternos, de esta manera se

puede reducir la frecuencia de descubrimiento de rutas.

El nucleo del protocolo de enrutamiento AOMDV busca

asegurar que se descubran multiples caminos libres de lazos,

ademas de la eficiencia al encontrar rutas mediante una

multitud de nodos en la red. [7]

Este protocolo actualiza las reglas aplicadas localmente

a un nodo, juega un papel fundamental al mantener la

red libre de bucles.

Este protocolo confa en la informacion de ruteo

disponible bajo los lineamientos de AODV, en general

no emplea ningun control de paquetes, de hecho el

envo de Rutas de encaminamiento y de respuesta

para descubrir multiples rutas y mantenerlas, junto con

campos extra en los campos de ruteo constituye la unica

sobrecarga para el protocolo. [7]

III. HERRAMIENTAS A UTILIZAR

A. Simulador ns2

NS-2 o Network Simulator- 2 es un simulador de redes

de eventos discretos. NS-2 esta basado en dos lenguajes,

uno basado en la simulacion orientada a objetos, escrita en

C++, y un interprete OTcl (una extension de Tcl orientada

a objetos), usada para ejecutar los comandos del usuario

(scripts). El simulador, como consecuencia debe soportaruna jerarqua de clases en C++, o jerarqua compilada, y

una jerarqua de clases equivalente en OTcl, o jerarqua

interpretada.

El simulador permite la configuracion de gran cantidad

de parametros tales como la topologa de la red, la pila

de protocolos y parametros especficos de cada protocolo,

tambien permite evaluar el impacto de diferentes tipos de

trafico de red. [13]

B. Tracegraph

TraceGraph es una herramienta libre, para graficar

y especialmente analizar las trazas generadas (*.tr) porel simulador de redes NS-2. Para el funcionamiento de

Tracegraph es necesario tener instalado en nuestro sistema,

ciertas libreras de Matlab, y un convertidor de archivos

.tr (generados por ns-2) a archivos tracegraph, el cual es

llamado TraceConverter. [15]

Los tipos de traza que TraceGraph soporta, grafica y

analiza son los siguientes:

Wired.

satellite.

wireless (old and new trace).

new trace.

wired-wireless.

C. TexmakerTexmaker es un programa de Qt4, que integra muchas

herramientas necesarias para desarrollar documentos con

LaTeX, en una sola aplicacion. Texmaker se ejecuta na-

tivamente en Unix, Mac OS X y sistemas win32. Tex-

maker incluye soporte Unicode, correccion ortografica, auto-

completado, plegado de codigo y un visor incorporado

en pdf con el apoyo synctex y el modo de visualizacion

continua. Texmaker es un editor gratuito, LaTeX mod-

erna y multi-plataforma para Linux, MacOSX y Windows,

que integra muchas herramientas necesarias para desarrol-

lar documentos con LaTeX, en una sola aplicacion. Tex-

maker incluye soporte Unicode, correccion ortografica, auto-

completado, plegado de codigo y un visor incorporadoen pdf con el apoyo synctex y el modo de visualizacion

continua. Texmaker es facil de usar y configurar. [?]

IV. PARAMETROS DE SIMULACION

A. M etricas

Thoughput: Representa el rendimiento de la tasa media

de exito de los paquetes de datos recibidos en destino.

Por lo general se mide en bits por segundo (bit/s o

bit/bps), y a veces en paquetes de datos por segundo.

[16]

Drop: Representan los paquetes perdidos o borrados. Send: Representa el envio de paquetes.

Resend: Representa el reenvio de paquetes.

End to End Delay: Representa el retraso en la

transmision de los datos, es decir el retraso debido a

la ruta de descubrimiento, de propagacion y el tiempo

de transferencia. [16]

V. DESARROLLO

Para el respetivo desarrollo de la simulacion debemos

tener instalado:

1) ns2: Software simulacion.

2) Tracegraph: Trazar graficas de resultados.

Para simular redes moviles Ad Hoc en ns2, debemos contar

con los siguientes archivos

1) Archivo que describe el patron de movimiento de los

nodos (Escenario).

2) Archivo que describe el trafico o patron de comuni-

cacion en la red (Conexiones).

3) Y por suspuesto el script que define la simulacion

(.tcl).

5/26/2018 ProyectoFundamentosRedesMiguelTenezaca

4/8

A. Generador de movilidad de los nodos (Escenario)

El generador de movimiento esta disponible en el

directorio ns-allinone-2.34/ns-2.34/indep-utils/cmu-

scen-gen/setdest donde ns-allinone-2.34/ns-2.34 es el

directorio donde se instalo el paquete del simulador

y el archivo setdest es un ejecutable (Figura 1). Para

generar nuestro archivo de movilidad ejecutamos el

siguiente comando ./setdest - v < 2 > -n < nodes > -s< speedtype > -m < minspeed > -M < maxspeed > -t< simulationtime > -P < pausetime > -x < maxX >-y < maxY > > [outdir/file] [1]

Figure 1. Creacion de escenarios

Donde:

1) version del generador de movimiento2) < nodes > numero de nodos3) < speedtype > tipo de velocidad (1= Uniforme)4) < minspeed > velocidad mnima en m/s5) < maxspeed > velocidad maxima en m/s6) < simulationtime > tiempo de simulacion en se-

gundos

7) < pausetime > pausa de simulacion en segundos8) < maxX > dimension X del terreno en que se

mueven los nodos en metros

9) < maxY > dimension Y del terreno en que semueven los nodos en metros

10) [outdir/file] Nombre del archivo de movimiento

B. Generador de tr afico (Conexiones)

El archivo de comunicacion es uno de los mas

importantes. El cual lo generamos con la siguiente lnea

de comando: ns cbrgen.tcl -type cbr|tcp -nn nodes -seedseed -mc connections -rate rate > [outdir/file] [1]

Donde:

cbr|tcp tipo de trafico. nodes numero de nodos en la simulacion.

seed semilla aleatoria.

connections numero de conexiones

rate velocidad de transferencia en pkts/seg.

[outdir/file] Nombre del archivo de movimiento.

La lnea que ejecutamos para realizar nuestro archivo de

conexiones fue (Figura 2):

30 conexiones con 90 nodos: ns cbrgen.tcl -type tcp

-nn 90 -seed 1 -mc 30 -rate 5 >conexion1-30 60 conexiones con 90 nodos: ns cbrgen.tcl -type tcp

-nn 90 -seed 1 -mc 60 -rate 5 >conexion1-60

30 conexiones con 100 nodos: ns cbrgen.tcl -type tcp

-nn 100 -seed 1 -mc 30 -rate 5 >conexion2-30 60 conexiones con 100 nodos: ns cbrgen.tcl -type tcp

-nn 100 -seed 1 -mc 60 -rate 5 >conexion2-60

Figure 2. Directorio de Escenarios

Una vez generados nuestros archivos son incluidos al

script .tcl que define la simulacion (Figura 3). Como resul-

tado de la ejecucion del archivo .tcl se generan dos archivos,

uno que definira la traza .tr y el otro nos permitira tener

una visualizacion grafica con el Network animator (.nam)

(Figura 4).

Figure 3. Ejecucion del archivo .tcl

Figure 4. Archivos .nam y .tr

VI . SIMULACION

Para abrir la aplicacion del Tracegraph ejecutamos el sigu-

iente comando desde el directorio donde este se encuentra

instalado :./trgraph (Figura 5).

5/26/2018 ProyectoFundamentosRedesMiguelTenezaca

5/8

Figure 5. Ventana del Tracegraph

A. Informacion de trazas

Los datos que nos proporciona son de vital importancia ya

que estas nos daran la informacion necesaria para conocer

como actua cada protocolo al generar, enviar o recibirpaquetes en el escenario, y poder generar las respectivas

graficas comparativas (Figura 6).

Figure 6. Informacion DSR (120 nodos - 30 conexiones)

B. Visualizacion NAM

Como nos menciona Jordi Chalmeta [2] en su artculo,

NAM (Network Animator) es una herramienta de soportepara poder interpretar y entender las simulaciones de un

modo visual. Dicha herramienta es fundamental para en-

tender que es lo que esta sucediendo en la simulacion y as

saber como tratar los resultados obtenidos, el cual podemos

observar en la (Figura 7), capturadas en dicha herramienta

con cada uno de los protocolos.

Figure 7. DSR- NAM (90 nodos - 30 conexiones)

C. Throughput of generating packets

(Figura 8).

Figure 8. Rendimiento de paquetes generados DSR (120 nodos - 30conexiones)

D. Throughput of sending packets

(Figura 9).

5/26/2018 ProyectoFundamentosRedesMiguelTenezaca

6/8

Figure 9. Rendimiento de paquetes enviados DSR (120 nodos - 30conexiones)

E. Throughput of receiving packets

(Figura 10).

Figure 10. Rendimiento de paquetes recibidos DSR (120 nodos - 30conexiones)

F. Throughput of dropping packets

(Figura 11).

Figure 11. Rendimiento de paquetes borrados DSR (120 nodos - 30conexiones)

VII. RESULTADOS

A. En la tabla I y figura 12 se muestra el analisis dePaquetes Generados

Table IPAQUETES G ENERADOS

Figure 12. Paquetes generados protocolos DSR y OMDV

B. En la tabla II y figura 13 se muestra el analisis de

Paquetes Enviados

Table IIPAQUETES E NVIADOS

5/26/2018 ProyectoFundamentosRedesMiguelTenezaca

7/8

Figure 13. Paquetes enviados protocolos DSR y OMDV

C. En la tabla III y figura 14 se muestra el analisis de

Paquetes Recibidos

Table IIIPAQUETES R ECIBIDOS

Figure 14. Paquetes recibidos protocolos DSR y OMDV

D. En la tabla IV y figura 15 se muestra el analisis de

Paquetes Borrados

Table IVPAQUETES B ORRADOS

Figure 15. Paquetes borrados protocolos DSR y OMDV

E. En la tabla V y figura 16 se muestra el analisis Delays

Table VDELAYS

Figure 16. Grafica delays protocolos DSR y OMDV

F. En la tabla VI y figura 17 se muestra el analisis Through-

put

Table VITHROUGHPUT

Figure 17. Grafica throughput protocolos DSR y OMDV

VIII. CONCLUSIONES

Haciendo un analisis comparativo entre los protocolos

AODV y DSDV, se puede concluir que el mejor proto-

colo en cuanto a Delays es el DSDV.

Con la grafica de Throughput (Rendimiento = (Paque-

tesEnviados + PaquetesRecibidos + PaquetesBorrados)

/ Delays) se puede concluir que el protocolo AODV

tiene mejor rendimiento en cuanto a la red.

5/26/2018 ProyectoFundamentosRedesMiguelTenezaca

8/8

Para determinar la distancia mas corta entre un nodo

y otro se empleo el algoritmo de Dijkstra. Durante la

ejecucion del algoritmo, se mantiene un pseudoflujo

x que satisface las condiciones de optimizacion y se

aumenta una cantidad determinada de flujo a traves dela

ruta mas corta.

El protocolo AODV es un protocolo reactivo que buscauna ruta solo cuando se necesita y aunque su topologa

cambie, AODV usa tablas de encaminamiento tradi-

cionales.

BIBLIOGRAFIA

[1] J. A. V. Cruz, Seguridad en el enrutamiento del protocoloaodv para redes moviles ad hoc, Ph.D. dissertation, CentroNacional de Investigacion y desarrollo Tecnologico, 2005.

[2] J. C. Ugas, Estudio y analisis de prestaciones de redesmoviles ad hoc mediante simulaciones ns-2 para validarmodelos analticos. Masters thesis, Universitat Politecnicade Catalunya, 2009.

[3] A. M. Santos, Comparativa de los protocolos aodv y olsr conun emulador de redes ad-hoc, Masters thesis, UniversitatPolitecnica de Catalunya, 2006.

[4] I. Vijaya, P. B. Mishra, A. K. Rath, and A. R. Dash, Influenceof routing protocols in performance of wireless mobile adhocnetwork, Emerging Applications of Information Technology,

International Conference on, vol. 0, pp. 340344, 2011.

[5] S. Rastogi, Optimizing routing protocols for ad hoc net-work, IEEE International Conference on Mobile Adhoc andSensor Systems Conference, vol. 0, pp. 813818, 2006.

[6] D. A. L. F. Roberto Subiela Dura, Simulacin de protocolosde encaminamiento en redes mviles ad hoc con ns-2, in ?

[7] A. Tuteja, R. Gujral, and S. Thalia, Comparative perfor-mance analysis of dsdv, aodv and dsr routing protocolsin manet using ns2, Advances in Computer Engineering,

International Conference on, vol. 0, pp. 330333, 2010.

[8] S. R. Raju, K. Runkana, and J. Mungara, Zrp versusaodv and dsr: A comprehensive study on zrp performanceon manets, Computational Intelligence and Communication

Networks, International Conference on, vol. 0, pp. 194199,2010.

[9] H. Doumenec, Estudio comparativo de protocolos de en-caminamiento en redes vanet, Masters thesis, UniversidadPolitecnica de Madrid, 2008.

[10] L. F. Rubio, Networks mesh based on points of intelligentaccess 802.11 open source (i). Masters thesis, UniversitatPolitecnica de Catalunya, 2005.

[11] Y. Chaba, Y. Singh, and M. Joon, Performance evaluationand analysis of cluster based routing protocols in manets, in

Advances in Computing, Control, Telecommunication Tech-nologies, 2009. ACT 09. International Conference on, dec.2009, pp. 64 66.

[12] M. Yassein and N. Hijazi, Improvement on cluster basedrouting protocol by using vice cluster head, in Next Gener-ation Mobile Applications, Services and Technologies (NG-

MAST), 2010 Fourth International Conference on, july 2010,pp. 137 141.

[13] The ns Manual.

[14] User Guide CityMob for Roadmaps C4R.

[15] TRACEGRAPH Y SUS NUMEROSAS UTILIDADES.

[16] P. Nand and S. Sharma, Comparative study and performanceanalysis of fsr, zrp and aodv routing protocols for manet,

IJCA Proceedings on International Conference and workshopon Emerging Trends in Technology (ICWET), no. 2, pp. 1419, 2011, published by Foundation of Computer Science.