redes de acceso y transporte -...

1

DESCUBRIMIENTO ADAPTATIVO DE

PASARELAS EN REDES MANET CONECTADAS A

INTERNET Antonio Jesús Yuste Delgado

Directores: Alicia Triviño Cabrera

Eduardo Casilari Pérez

TESIS DOCTORAL UNIVERSIDAD DE MÁLAGA

Málaga, 10 de abril de 2012

Índice

1. Introducción a las redes ad hoc

2. Integración de redes MANET en Internet

3. Caracterización del enlace hacia Internet

4. Aplicando la lógica difusa tipo II

5. Conclusiones y Líneas Futuras

2 de 46

2

1. Definición red ad hoc (1)

MANET: Mobile Ad hoc NETwork


Interconexión de equipos móviles que se han unido sólo y exclusivamente para este fin.

3 de 46

de 46 4

Ejemplos de redes MANET

Redes personales (Wireless Personal Area Network, WPAN) Redes de vehículos (Vehicular Ad hoc Network, VANET) Redes de sensores inalámbricos móviles (Mobile Wireless

Sensor Network, MWSN) Redes de sensores corporales (Body Sensor Network, BSN).

1. Definición red ad hoc (2)


3

1. Características de las MANET


Falta de infraestructura central Topología dinámica Reparación automática de los enlaces Cooperación entre los nodos

Características generales

Alcance de transmisión limitado Dispositivos heterogéneos Recursos energéticos finitos Potencia de cálculo modesta Movilidad

Características de los nodos

Necesidad de protocolos específicos

5 de 46

1. Clasificación de protocolos MANET

Establecimiento de las rutas

Bajo demanda o reactivas (AODV, DSR) Los nodos empiezan los descubrimientos de rutas sólo cuando son necesarios. Preventivas o proactivas (OLSR ,TBRPF) Los nodos intercambian información con sus vecinos.

1. Introducción a las redes ad hoc 6 de 46

4






7 de 46

2. Ejemplo de aplicación

2. Integración de redes MANET en Internet 8 de 46

5

2. Internet y MANET

Aplicaciones comerciales Extender redes inalámbricas Paradigma de la conectividad total

Necesidad de la integración

Movilidad de los nodos No aplicación de principios de la red fija Direcciones IP cambiantes Descubrimiento de pasarelas

Problemas de la integración

9 de 46 2. Integración de redes MANET en Internet

2. Fases de la integración

1. Identificación y selección de pasarelas

10 de 46

2. Identificación del prefijo de red

3. Obtención de parámetros

4. Elaboración de la dirección de red

5. Resolución de direcciones de otros nodos

6. Detección de direcciones duplicadas

7. Mecanismos de movilidad


6

2. Descubrimiento de pasarelas en IPv6

NDP: Neighbor Discovery Protocol RA: Router Advertisement RS: Router Solicitation

11 de 46

Redes salto único


2. Conectividad en MANET

Modificación de mensajes preventivos RA -> MRA (Modified Router Advertisement)

Modificación de mensajes bajo demanda RS -> MRS (Modified Router Solicitation)

Adaptación en MANET

Distintas técnicas

Conectividad Global para MANET IPv6 (Wakikawa) Configuración automática de direcciones para redes ad hoc

IPv6(Jelger) Soporte extendido (Cha) Soporte móvil multipasarela (Singh) Configuración automática de direcciones IPv6 para MANET con

múltiples pasarelas (Ruffino)

12 de 46 2. Integración de redes MANET en Internet

7

2. Conectividad global para MANET IPv6 (1)

Pasarela

13 de 46

MRA (Modified Router Advertisement) MRS (Modified Router Solicitation)

Bajo demanda

Pide ruta


de 46 14


Pasarela

MRA (Modified Router advertisement) MRS (Modified Router Solicitation)

Preventivo

T


8

de 46 15 15


Pasarela

MRA (Modified Router advertisement) MRS (Modified Router Solicitation)

Híbrido

T

Zona proactiva


2. Adaptabilidad

ADD

RMD

Bajo demanda

16 de 46

ADD (Adaptive Distributed gateway Discovery) RMD (Regulated Mobility Degree)

Adaptación del intervalo T y/o TTL


9

de 46 17

2. Mecanismos propuestos

Propuesta Caso

Función del número de vecinos 3

Función de la media de los vecinos 3

Función de la conectividad 3

Función del factor de estabilidad 3

Lógica difusa (tipo I) 3

Envío Selectivo 2

Enlaces estables 2

Lógica difusa (tipo II) 2







18 de 46

10

3. ¿Qué enlace se utiliza?

2

3. Caracterización del enlace hacia Internet 19 de 46

1

3

3. Propuesta de reenvío MRA

Sólo reenvían los nodos con enlaces estables a Internet La estabilidad se basa en los tiempos de conectividad Es necesario definir las propiedades estadísticas de estos

tiempos Se compara con modelos estadísticos muy conocidos Se determina el tiempo de vida residual

te


tf 𝑡 = 𝑡𝑓 − 𝑡𝑒

11

3. Características del escenario


Área de simulación 1500 x 300 m2

Tiempo de simulación 1000 s (100 s transitorio)

Protocolo ad hoc AODV

Patrón de movilidad Máxima velocidad: 2-10 m/s Tiempo de pausa:10 s Velocidad mínima:1 m/s

Tráfico de datos 5 fuentes VBR 50% actividad 38’4 kbps 320 bytes

Coordenadas pasarelas (0,150) m (1500,150) m

Modelos de Movilidad Random Waypoint Model Time-Variant Community Mobility

3. Comparativa RWP

Lognormal

Normal

Gamma

Weibull

Exponencial

Rayleigh

Binomial negativa

Geométrica

Pareto

0 0,05 0,1 0,15 0,2 0,25 0,3 0,35 0,4

Test de Kolmogorov-Smirnov


Random WayPoint (RWP)

12

3. Comparativa TVCM

Ajuste visual


Time-Variant Community Mobility (TVCM)

3. Cálculo MRL

Tiempo de vida residual o MRL (Mean Residual Lifetime)

𝑀𝑅𝐿 𝑎𝑔𝑒 = 𝐸 (𝐷𝐸 − 𝑎𝑔𝑒) 𝐷𝐸 > 𝑎𝑔𝑒

Como DE sigue una distribución logaritmo normal

𝑀𝑅𝐿 𝑎𝑔𝑒 = 𝜇 ∙ 𝑒𝜎2

2

1 + 𝑒𝑟𝑓𝜎2 − 𝑙𝑜𝑔

𝑎𝑔𝑒𝜇

𝜎 2

𝑒𝑟𝑓𝑐𝑙𝑜𝑔

𝑎𝑔𝑒𝜇

𝜎 2


13

3. Aplicación en MANET híbridas

Restricción del reenvío de los paquetes

𝑀𝑅𝐿 𝑎𝑔𝑒 ≥ 𝑇

Sólo se anuncian los enlaces más estables Disminuye el número de mensajes de control totales Disminuye el número de cambios de rutas

Consecuencias

Mejora de las prestaciones Más estabilidad del sistema


3. Resultados RWP (1)


Retardo

26 de 46

REA (Reactivo) ADD (Adaptive Distributed gateway Discovery) RMD (Regulated Mobility Degree) DPEE (Descubrimiento de pasarelas basado en Enlaces Estables)

14

Pérdidas




Sobrecarga normalizada




15






29 de 46

Existen más parámetros para definir la estabilidad EL problema es reunirlas en una única métrica

Aleatoriedad de los nodos Sistemas no lineales Rango de alcance, potencia, etc. heterogéneos Cuellos de botella en función de localización pasarelas Pocos eventos para tomar decisiones Topologías muy cambiantes Otras interferencias Medidas de parámetros inciertos

Incertidumbre

4. Estabilidad

Lógica difusa Tipo II

4. Aplicación de la lógica difusa tipo II 30 de 46

16

4. Lógica difusa (I)

Lógica difusa Tipo I


Razonamiento humano es impreciso Si la Temperatura es baja entonces subir calefacción Modela matemáticamente parámetros de entrada/salida Conjuntos difusos Tipo I: una salida

de 46 32

Lógica difusa Tipo II

Maneja más incertidumbre Los parámetros tienen un intervalo de pertenencia Salida: un intervalo [Zmin,Zmax]

4. Lógica difusa (II)

4. Aplicación de la lógica difusa tipo II

FOU (Footprint Of Uncertainty)

17

4. Entradas (1)

Probabilidad asociada al tiempo de vida del enlace hacia la pasarela

Longitud de las rutas

𝑝 =

1 + 𝑒𝑟𝑓𝜇

2𝜎−

1

2𝜎𝑙𝑛 𝑎𝑔𝑒 + 𝑇

1 + 𝑒𝑟𝑓𝜇

2𝜎−

1

2𝜎𝑙𝑛 𝑎𝑔𝑒

𝐿 =𝑑

𝑑 + ℎ


4. Entradas (2)

Número de enlaces activos respecto del total de las fuentes

Cociente entre las ruta erróneos y las rutas solicitadas


𝑈𝐸𝐸𝐷 = 𝑁𝐹

𝑁𝐹 + 𝑁𝐸

𝑅𝑃𝐶 = 1 − 𝑃𝐸

𝑃𝐸 + 𝑃𝑆

18

4. Diagrama flujo


Sistema de Decisión Difuso

p L UEDD RPC

Zmin Zmax

Zmin >Udatos Zmax >Ulibre

DATOS NO DATOS

CONFIGURAR

36

4. Características escenario

4. Aplicación de la lógica difusa tipo II de 46

Área de simulación 1200 x 1200 m2

Tiempo de simulación 1000 s (100 s transitorio)

Protocolo ad hoc AODV

Patrón de movilidad Máxima velocidad: 2-10 m/s Tiempo de pausa:10 s Velocidad mínima:1 m/s

Tráfico de datos 10 fuentes VBR 50 % actividad 9’6 kbps 120 bytes

Coordenadas pasarelas (300,300) m (900,900) m

Modelo de movimiento Random Trip

19

de 46 37

Udatos como 0.3 Ulibre como 0.8

4. Configuración umbrales (6)

4. Aplicación de la lógica difusa tipo II

00.2

0.40.6

0.81

0

0.5

10.02

0.04

0.06

0.08

0.1

0.12

0.14

0.16

Udatos

Ulibre

Reta

rdo (

s)

00.2

0.40.6

0.81

0

0.5

10.01

0.011

0.012

0.013

0.014

0.015

0.016

Udatos

Ulibre

Pérd

idas

00.2

0.40.6

0.81

0

0.2

0.4

0.6

0.8

1

1

1.5

2

2.5

3

Udatos

Ulibre

Sobre

carg

a N

orm

aliz

ada

4. Resultados

Cambios en la velocidad máxima de los nodos


Cambios en la tasa de paquetes • Diferentes tasas a una velocidad fija (5 m/s)

Cambios en la posición y número de las pasarelas • Se incrementa el número de pasarelas de 2 hasta 6

Tres pruebas distintas

20

de 46 39

REA (Reactivo) ADD (Adaptive Distributed gateway

Discovery) RMD (Regulated Mobility Degree) DPEE (Descubrimiento de pasarelas

basado en Enlaces Estables) SDD (Sistema de Decisión Difuso)

4. Resultados: cambios velocidad (1)

2 4 6 8 100.5

1

1.5

Velocidad máxima del nodo (m/s)

Sob

reca

rga

Nor

mal

izad

a

REA

ADD

RMD

DPEE

SDD

2 4 6 8 10

5

6

7

8

9

10

11

x 10-3


Tasa

de

Pér

dida

s

REA

ADD

RMD

DPEE

SDD

2 4 6 8 10

0.05

0.1

0.15

0.2


Ret

ardo

(s)

REA

ADD

RMD

DPEE

SDD

de 46 40

4. Resultados: cambios tasa de paquetes (2)


Discovery) RMD (Regulated Mobility Degree) DPEE (Descubrimiento de pasarelas

basado en Enlaces Estables) SDD (Sistema de Decisión Difuso) 10 20 30 40

1

2

3

4

5

Tasa de tráfico (kbps)

Sob

reca

rga

Nor

mal

izad

a

REA

ADD

RMD

DPEE

SDD

10 20 30 400.01

0.02

0.03

0.04

0.05

0.06

0.07

0.08


Tasa

de P

érd

idas

REA

ADD

RMD

DPEE

SDD

10 20 30 400.02

0.04

0.06

0.08

0.1

0.12

0.14

0.16


Ret

ardo

(s)

REA

ADD

RMD

DPEE

SDD

21

de 46 41 4. Aplicación de la lógica difusa tipo II


Discovery) RMD (Regulated Mobility Degree) DPEE (Descubrimiento de pasarelas basado

en Enlaces Estables) SDD (Sistema de Decisión Difuso)

4. Resultados: cambios número pasarelas (3)

2 3 4 5 62

3

4

5

6

7

8

Número de pasarelas

Sobr

ecar

ga N

orm

aliz

ada

REA

ADD

RMD

DPEE

SDD

2 3 4 5 60.02

0.03

0.04

0.05

0.06

0.07

0.08

0.09


Tasa

de P

érd

idas

REA

ADD

RMD

DPEE

SDD

2 3 4 5 60.05

0.1

0.15

0.2

0.25


Reta

rdo (

s)

REA

ADD

RMD

DPEE

SDD






42 de 46

22

5. Conclusiones

La difusión de los mensajes MRA afecta a las prestaciones de la red

La difusión simple de estos mensajes no es adecuada Hay que buscar mecanismos adaptables a los cambios en la red La duración efectiva de los enlaces sigue una distribución

lognormal La lógica difusa tipo II es muy aplicable a estos casos por su

adaptación a situaciones de gran incertidumbre

5. Conclusiones y líneas futuras 43 de 46

5. Líneas futuras

Enlaces estables Selección de muestras Análisis de variables Aplicación a otras redes

Lógica difusa Más variables Proceso de aprendizaje automático de reglas Umbrales dinámicos Reducir la complejidad del sistema difuso

Otras posibilidades Selección de pasarelas Adaptación simultánea de T y TTL Más métricas de prestaciones

5. Conclusiones y líneas futuras 44 de 46

23

Publicaciones

5 revistas JCR (2)

• IET Communications • Electronic Letters

Otros índices de calidad(3)

7 congresos internacionales CORE (4) Otros(3)

1 capítulo de libro

1 congreso nacional

45 de 46 Publicaciones

46 de 46

DESCUBRIMIENTO ADAPTATIVO DE

PASARELAS EN REDES MANET CONECTADAS A

INTERNET

Antonio Jesús Yuste Delgado

Directores: Alicia Triviño Cabrera Eduardo Casilari Pérez

Tesis Doctoral

redes de acceso y transporte -...

Documents