Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

BCHPE: Protocolo de Enrutamiento Basado en Clustering para R

No description
by

Andrea Carrión

on 30 July 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of BCHPE: Protocolo de Enrutamiento Basado en Clustering para R

Protocolos de Enrutamiento para Redes Móviles Ad-Hoc.
Hernán A. Samaniego Armijos
Máster en Telemática y Redes de Telecomunicación
UNIVERSIDAD TÉCNICA PARTICULAR DE LOJA
Departamento de Ciencias de la Computación y Electrónica
Sección Departamental de Telecomunicaciones y Redes

BCHPE
¿Qué es?
¿Para qué se utiliza?
Protocolos de Enrutamiento
Motivaciones para BCHPE
Objetivos BCHPE
Aplicaciones BCHPE
Investigaciones Futuras
Trabajos Realizados BCHPE
Introducción
¿Qué es una
MANET?
Protocolos de Enrutamiento MANET
MANET
Movile Ad-Hoc Network
Nodos móviles
Sin Infraestructura
Las rutas varían en el tiempo
Rápido despliegue
Rentables
Ventajas / Desafíos
MANET
Movile Ad-Hoc Network
Topología dinámica
Canales de radio variables
Consumo de energía
Fiabilidad de comunicación
Desafíos
Conexión Inalámbrica
Proactivos
Buscan rutas bajo demanda
Reactivos
Buscan rutas periódicamente
Híbridos
Combinación de las mejores propiedades de ambos enfoques
DSR
AODV
TORA
DSDV
OLSR
ZRP
TBRF
Reactivos Proactivos
Solamente busca una ruta cuando se necesita.

Se utiliza la ruta hasta que la comunicación finaliza.

Las rutas están disponibles dependiendo de la topología cambiante.

Alta latencia para el primer paquete.

Se prefiere utilizar en redes altamente dinámicas
Periódicamente envían información de las rutas.

Se crean tablas de enrutamiento.

Almacena rutas no dispobibles.

Alta sobrecarga de red, tiempo de convergencia alto.

No se utiliza en redes altamente dinámicas.

¿Qué solución adoptar?
Motivación 1
Motivación
Implementar un protocolo de enrutamiento MANET para redes altamente dinámicas.
Problema
En las redes altamente dinámicas, las rutas cambian rápidamente.
Solución
Utilizar protocolos de enrutamiento reactivos.
Motivación 2
Implementar un protocolo de enrutamiento MANET para redes con alta densidad de nodos. (>10)
Para determinar una ruta disponible entre dos nodos, es necesario inundar toda la red (flooding controlado) desde el origen hasta alcanzar el destino.
El clustering implica agrupar varios nodos en un clúster, elegir un jefe de clúster y el procedimiento de inundación solo ocurrirá entre los jefes de clúster.
Implementar un protocolo de enrutamiento MANET para redes con alto rendimiento (latencia, througput).
Cuando el jefe de clúster desaparece, todos nodos del clúster pierden conectividad.
Elegir un jefe de clúster de respaldo, que tome el lugar del jefe de clúster principal, cuando este no se encuentre disponible.

BCHP

Implementar un protocolo de enrutamiento MANET para redes con alto rendimiento (disponibilidad).
El jefe de clúster es el nodo que consume mayor cantidad de energía, y cuando esta se consume en su totalidad, se pierde un nodo de la red.
Evitar que el jefe del clúster consuma toda la carga de su batería, convirtiéndose antes en un nodo común.

BCHPE: Backup Cluster Head Protocol Enhanced
BCHP
Redes con movimiento
Alta densidad de nodos
Alto rendimiento
Motivación 3
Motivación 4
Motivación
Motivación
Motivación
Problema
Problema
Problema
Solución
Solución
Solución
Backup Cluster Head Protocol
Mejorar la gestión de redes MANET
BCHP
Incluir estrategia proactiva
Evaluar
Latencia
Throughput
Disponibilidad
Analizar protocolos
Carga de batería
Ejemplo 1
Ejemplo 2
Situaciones de emergencia y rescate
Juegos
Educación
Ejemplo 3
Ejemplo 4
Simulación en NS-3
QoS
Especificación en SDL
MANET
Las topologías dinámicas cambian las rutas
¿Cómo se soluciona?
ENRUTAMIENTO
BCHPE
Inicialización de los nodos
BCHPE
Formación del Clúster
BCHPE
Descubrimiento del Clúster adyacente
BCHPE
Mantenimiento del Clúster
Jefe de clúster
¿Cuál es la carga del jefe de clúster?
Jefe de clúster
m=2
m=3
m=4
Mi carga es 14%
Se pierde el Jefe de Clúster
Descubrimiento de Ruta
Ingresa un nodo común
Ingresa un Jefe de Clúster de respaldo
Ingresa un Jefe de Clúster
Se pierde el nodo común
Se pierde el Jefe de Clúster de respaldo
Militar
Preguntas
Entornos completamente simétricos.
Todos los nodos tienen las mismas capacidades y responsabilidades.

Entornos asimétricos. Pueden variar:
Los rangos de transmisión
La duración de las baterías
La capacidad de proceso
La velocidad de movimiento
Capacidad de enrutamiento
Algunos nodos pueden tener mayores responsabilidades (nodos líder)
Tecnologías inalámbricas (bit rate,..)
Tipos de redes Ad Hoc
Patrones de movilidad
Gente esperando en el aeropuerto
La red de taxis
Movimientos militares
Personal area network

Características de la movilidad
Velocidad
Predicción de movimientos
Patrón de movimiento
La dirección
Uniformidad entre los nodos.
Variaciones de las redes Ad Hoc
Conceptos generales de enrutamiento
Objetivo:
Enviar los mensajes de un nodo a otro hasta llegar al destino.
¿Cuál es el mejor camino?
El más corto (menos nodos)
El más rápido (menor retardo)
Otros factores: baterías, ancho de banda…

¿Quién decide: la fuente o los nodos intermedios?
Source routing. (servicio áereo)
La fuente decide el camino
Los nodos intermedios reenvian el mensaje al siguiente nodo.
hop-by-hop routing. (servicio correo)
La fuente especifica el destino en la cabecera del mensaje.
Los nodos intermedios observan la dirección destino y consultan en sus tablas de enrutamiento para seleccionar el siguiente salto.
Características del enrutamiento en una MANET:
Gran probabilidad de fallo en el enlace, lo que causa frecuentes cambios de ruta.
Topología dinámica (sin predicciones).
Ancho de banda limitado.
Cada dispositivo potencialmente puede comportarse como un router.
No hay administrador.

Aparecen nuevos criterios de enrutamiento:
Estabilidad de las rutas.
Consumo de potencia.
Enrutamiento en redes Ad Hoc I
Se han propuesto muchos protocolos:
Algunos específicos.
Otros adaptados de las redes cableadas.
Ninguno funciona bien en todos los entornos.

Funciones de un protocolo de encaminamiento:
Descubrimiento de la ruta:
“Necesito hablar con Pepe, ¿donde está?”

Mantenimiento de la rutas:
“¿Dónde se fue Pepe?”
“¿Dónde se fue el chico que sabía donde estaba Pepe?”
Enrutamiento en redes Ad Hoc II
Descubrimiento y mantenimiento de las rutas
Dos filosofías básicas para el descubrimiento de rutas:
Conocimiento de la topología de la red.
Pregunta-respuesta.


Procedimientos para el mantenimiento de las rutas:
Intercambio periódico de mensajes.
Escucha de mensajes.
Temporizadores.
Periódicamente envían información de las rutas, por ejemplo cada T segundos.

Se crean tablas de enrutamiento.

Si T es demasiado grande, las rutas pueden quedar obsoletas, y eso puede producir más retardo y pérdidas.

Si T es demasiado pequeño, saturación de información de control, también puede causar retardo y pérdidas.
Características de los protocolos proactivos
Características de los protocolos reactivos
Solamente se busca una ruta cuando se necesita.

Se utiliza la ruta hasta que la comunicación finaliza.

Se busca una nueva ruta cuando la anterior falla.

Protocolos de Enturamiento
Flooding Controlado
Ventajas del Flooding
Sencillo

Robusto, porque la entrega de paquetes se puede realizar por múltiples rutas.

Es más eficiente cuando la tasa de envío de paquetes de información es más baja que el overhead de los procesos de búsqueda y mantenimiento de rutas.

Por ejemplo en el caso de que los nodos transmitan pocos mensajes de datos de tamaño pequeño y que la topología cambie a menudo.
Overhead potencialmente muy alto.

En el peor de los casos todos los nodos alcanzables por la fuente recibirán los datos.

Potencialmente la entrega de datos es menos fiable debido a posibles colisiones y al uso del modo broadcast que no lleva asociado el paquete de reconocimiento ACK.
Desventajas del Flooding
Aspectos a tener en cuenta sobre el Flooding
Muchos protocolos utilizan el flooding (limitado) de los paquetes de control, en vez de los paquetes de datos.
Los paquetes de control se utilizan para descubrir rutas.
Las rutas establecidas se utilizan posteriormente para enviar los paquetes de datos.
La sobrecarga que se debe al flooding de los paquetes de control se compensa gracias a los paquetes de datos transmitidos entre los floodings consecutivos de paquetes de control.
Protocolos de Enrutamiento
AODV
Los paquetes de datos no tiene que contener rutas

Las rutas se mantienen sólo entre nodos que necesitan comunicarse

Cuando el nodo S quiere enviar un paquete al nodo D a priori no conoce la ruta, por lo que debe iniciar un descubrimiento de la ruta.

El nodo S envía por inundación un paquete Route Request (RREQ) .

Cuando un nodo retransmite un paquete Route Request RREQ, preestablece la ruta de vuelta hacia la fuente.
AODV asume enlaces bidireccionales.

Cuando el destino recibe el paquete Route Request RREQ, responde enviando un paquet Route Reply RREP.

El paquete Route Reply RREP recorre la ruta activada a través del envío del Route Request
AODV
Full transcript