protocolos de enrutamiento con servicios de...

SIMULACIÓN DE PROTOCOLOS DE ENRUTAMIENTOPARA REDES MÓVILES AD-HOC MEDIANTE

HERRRAMIENTA DE SIMULACIÓN NS-3

Protocolos de enrutamiento con servicios de

localización

Outline

1. Introducción

2. Sistemas de localización

3. Servicios de localización

4. Protocolos de enrutamiento

Loja - 2014Simulación de Protocolos de Enrutamiento para MANET con ns-3

2

¿Qué es un sistema/servicio de localización?

� Sistema de localización proporciona la posición geográfica, más o menos exacta, de una entidad móvil.• Posición que se ofrece al propio dispositivo móvil• Evento que se transmite a un servidor remoto de forma

transparente

� Un servicio de localización es una base de datos con información de posición de los nodos.

Conceptos generales


información de posición de los nodos.

� El objetivo de un servicio de localización es el mapeo dinámico de la dirección lógica de un nodo con su posición física en la red.

3

¿Qué es un servicio de localización?

� Las dos operaciones básicas asociadas a un servicio de localización son:• Actualización de la posición

o El nodo móvil debe ir informando de su posición.• La consulta de la posición de un nodo

o Si un emisor necesita localizar a un nodo dentro de la red.

� Es un servicio que proporciona el nivel de red.Routing, forwarding and localization

Conceptos generales


o Routing, forwarding and localization

4

Ejemplo de Servicio de localización en redes con infraestructura

� En redes móviles con infraestructura como GSM la posición de un nodo queda almacenada en el Home Location Register/Visitor Location Register.

� HLR/VLR son servidores centralizados.

N

(x,y)M

Position LookUp N

Conceptos generales


Location Service

(Base de Datos)

(x,y)

Position Update (N, (x,y))

N is at (x,y)

5

Ejemplo de Servicio de localización en redes ad hoc

� En una red ad hoc los nodos deben implementar este servicio por ellos mismos.

� Servidor de localización está distribuido entre los nodos.• Alguno o todos los nodos mantienen la información de la

posición.• Los nodos pueden tener una copia de toda o parte de la base

de datos. N

(x,y)M

Conceptos generales


(x,y)M

Position Update (N, (x,y))Position LookUp N

N is at (x,y)

Location Servers

6

Sistemas de localización

Sistema de localización: Principios básicos

� Clasificación de los sistemas de localización:• Sistemas de localización para exteriores• Sistemas de localización para interiores

� Sistema de localización se basan en el tratamiento de señales:• Retardos de propagación y desfase de señales• Potencia de señal recibida

� Receptores:

Sistemas de localización


� Receptores:• Cada vez más pequeños y baratos.• Precisión receptor satélite (20m) y telefonía (100m).

� Tecnologías:• Tecnologías inalámbricas estándar:

o Móviles, satéliteso WirelessLAN, Bluetooth, RFID (Radio-frequency

identification),NFC (Near field communication)

8

Sistema de localización para exteriores: GPS I

� Global Positioning System (GPS)• Sistema compuesto por 26 satélites.• Ofrece información de localización, velocidad y hora.• Basado en el concepto de triangulación• Cobertura global y gran precisión (<m)• Controlados por la fuerza Aérea EEUU

GPS


9

Sistema de localización para exteriores: GPS II

Determining PositionA GPS receiver "knows" the location of thesatellites, because that information isincluded in satellite transmissions. Byestimating how far away a satellite is, thereceiver also "knows" it is locatedsomewhere on the surface of an imaginaryspherecenteredat thesatellite. It then

GPS


spherecenteredat thesatellite. It thendetermines the sizes of several spheres, onefor each satellite. The receiver is locatedwhere these spheres intersect.

http://www.nasm.si.edu/gps/work.html

10

Sistema de localización para exteriores: Galileo

� Galileo• Propuesta europea de posicionacimiento global por satélite• 30 satélite• Vocación comercial:

o Servicio gratuito de posición (error < 5 metros)o Servicios de pago de mayor precisión

• Compatibilidad GPS y GalileoPendientes de acuerdo

Galileo


o Pendientes de acuerdo• Se espera poner en marcha en 2014

11

Sistema de localización de exteriores de telefonía móvil

� Servicio LCS (Location Service)• Define la funcionalidad, interfaces y mensajes necesarios para

localizar terminales en una red de telefonía móvil (GSM, UMTS, etc).

� Categorías LCS:• LCS Comercial

o Proporciona servicios de valor añadido a los usuarios.• LCS Interno

Servicio LCS


• LCS Internoo Utilizados por la propia operadora de acceso. Medidas de

tráfico, información de cobertura, servicios suplementarios• LCS de Emergencia

o Permiten dar asistencia a llamadas de emergencia. Obligatorio en algunos países. Ofrecen la posición del llamante a los servicios que responden a la llamada.

• LCS Legalo Utilizados para combatir delitos.

12

Mecanismos de posicionamiento para LCS

� Algunas técnicas de localización:• Identificación de la célula (Cell ID)• Cell ID + Timing Advanced (TA)• Cell ID + Timing of Arrival (TOA)

• Enhanced Observer Time Difference (E-OTD)

• Angle Of Arrival (AOA)

Servicio LCS


13

Cell ID (Identificación de la célula )

� Método muy sencillo

� La posición del terminal, MS, se estima a partir de laidentificación de la estación base.

� La exactitud de la estimación depende del area decovertura de la célula.

• Femtocell: pocos metros

Servicio LCS


• Urbano: 500m-2km

• Rural: hasta 30km

Diámetro de la celda:

- 50 m (indoor picocell)

- 30 km (rural macrocell)

14

Cell ID + TA (Timing Advanced )

� Utilizado en GSM, GPRS

• TA se calcula en la estación base y se envía al MS para lasincronización en un sistema TDMA.

� En UMTS se consiguen medidas del RTT (Round Trip Time)con exactitud mayores de 36m

� El RTT o TA se utiliza para calcular la distancia entre laestación base y el MS.

Servicio LCS


estación base y el MS.

15

Cell ID + TOA (Timing of Arrival )

� Varias estaciones base miden el TOA de una señal enviadadesde el MS.

• El retardo de transmisión se resuelve tomandodiferencias de tiempo.

• La diferencia entre dos TOA define una hiperbola.

• Tres TOA definen una localización 2D.

Servicio LCS


• Tres TOA definen una localización 2D.

trama?

TOA1

TOA3

TOA2

trama?

TOA3=?+ D3/cTDOA21=TOA2-TOA1=(r2-r1)/c

r1r2

16

E-OTD Enhanced Observer Time Difference (OTDOA UMTS)

� Método parecido anterior, pero ahora las medidas las realiza el propio terminal móvil

� Se calcula la posición a partir del tiempo de llegada de una señal enviada por varias estaciones base. • El MS compara el tiempo de llegada de las señales y

estima su distancia a cada BS. Calcula su posición final por medio de triangulación.

� Se necesita modificar el software de los MS GSM.

Servicio LCS


� Se necesita modificar el software de los MS GSM.Los terminales UMTS ya están actualizados. trama

trama

trama

El MS mide diferencias de tiempo entre estaciones base.

Si la red no está perfectamente sincronizada, el MS tiene que conocer las diferencias en el tiempo entre las estaciones base

17

E-OTD

� Se introduce un nuevo dispositivo, el LMU (LocationMeasurement Unit) tiene un reloj GPS con el que puede medir los tiempos de transmisión de cada estación base de forma precisa. • EL LMU informa a las BSs de la diferencias de sincronización.• La red envía información adicional al MS para que pueda

obtener la posición mediante triangulación (TDOA).

Servicio LCS

E-OTD Enhanced Observer Time Difference (OTDOA UMTS)


LMUInformación

adicional

18

AOA (Angle of Arrival )

� El ángulo de llegada de las señales desde el MS a diferentesBS.

� La posición se calcula basado en el AOA en diferentes BS yel centro de localización, LMU, calcula la posición.

Servicio LCS

NodeB with directional NodeB with directional NodeB with directional NodeB with directional antennaantennaantennaantenna


trama

19

Ejemplos de aplicación para sistemas de localización para

exteriores


Casio Satellite Navi GPS watch PET TRACKING PACK

Localizador para personas con Alzhéimer

20

Sistemas de localización para interiores I

� Triangulación de radiofrecuencia• Se miden las distancias a varios puntos a partir de las señales

recibidas y la intersección determina la posición.• Se suele utilizar la potencia de la señal recibida.

o A menor potencia, más lejano se encuentra el objeto que emitió la señal.

Sistemas de localización en interiores


21

Sistemas de localización para interiores II

� Vector de potencias (distancia mínima)• Conocer la situación de los APs• Fase de entrenamiento: almacenamiento de las señales

obtenidas de los distintos APs por el usuario en diferentes puntos.

• Estimación de la posición a partir de los niveles más cercanos al vector de señales.

V1=(P11, P12 ,P13)



V1=(P11, P12 ,P13)

Vm=(Pm1, Pm2 ,Pm3)

V3=(P31, P32 ,P33)

V4=(P41, P42 ,P43)

V2=(P21, P22 ,P23)

22

Sistemas de localización para interiores III

� Balizas de infrarrojos y radiofrecuencia• La localización depende de la asociación de objetos con zonas

o balizas (fingerprint).• Se basa en la recolección de información del entorno “a priori”.

Esta información es clasificada y almacenada en una base de datos.

• El móvil mide la “huella” y la envía al centro de localización donde se debe encontrar la mejor asociación de esta “huella” con una localización.



con una localización.

23

Ejemplos de sistemas de localización

� EKAHAU• http://www.ekahau.com/• RSS de los APs• Wi-Fi tags

� AeroScout• http://www.aeroscout.com/• http://www.aeroscout.com/solutions

Ejemplos


• http://www.aeroscout.com/solutions• Wi-Fi y RFID• Utilizan el método de tiempo de llegada o de potencia de señal

recibida para determinar la posición del móvil o de la etiqueta RFID o WiFi.

24

Ekahau Real Time Location System (RTL)

Wi-Fi Based Asset Management and People Tracking Solution

For Hospitals and Other Enterprises


Small, battery-powered Wi-Fi tagsare attached to the tracked assets, or are carried by people. Alternatively, existing Wi-Fi devices like phones, tablets or laptops can be tracked.

Ekahau RTLS processes the locations, rules, messages, and environmental data - and turns this information into maps, alerts, and reports.

The system also allows you to monitor environmental conditions wirelessly, such as temperature and humidity.

25

Ekahau Real Time Location System (RTLS)


26

Servicios de localización

•DREAM

•Virtual Home

•Grid-like structure

Servicios de Localización reactivos

� Una solución simple para la localización de los nodos consiste en la inundación de los mensajes de solicitud de localización a través de la red.• Solución no escalable• Para redes pequeñas.

� Mejora: Controlar el área de inundación• Incrementar gradualmente hasta que el nodo es localizado el

Servicio de localización


• Incrementar gradualmente hasta que el nodo es localizado el número de saltos involucrados en la propagación de la inundación.

� Inundación es un servicio de localización reactivo.• No se mantiene información

28

Servicios de Localización proactivos

� Dividen su funcionamiento en dos fases:• Construyen y mantienen estructuras de datos que almacenan la

información de posición de cada nodo.• Solicitan información a estas estructuras.

Servicios de localización


29

Distance Routing Effect Algorithm for Mobility (DREAM)

� DREAM servicio de localización proactivo.� Todos los nodos mantienen información de localización de todos

los otros nodos.� Cada nodo utiliza la técnica de inundación para transmitir su

localización.� Para reducir el overhead el nodo puede controlar la frecuencia de

los mensajes de actualización y el número de hops a los cualesse entregan esos mensajes.

DREAM


se entregan esos mensajes.• Los nodos más cercanos se actualizan más frecuentemente.

o La exactitud de la posición de un nodo decrece con la distancia del nodo.

• El campo time-to-live se utiliza para controlar que lejos se propagael mensaje

• Efecto de la distancia: “Cuanto mayor es la distancia que separa a dos nodos, más despacio parece que se mueven uno con respecto a otro”o Por lo tanto la falta de exactitud con la distancia se ecualiza.

30

Virtual Home

� Servicios de localización que seleccionan un nodo de una subred de nodos para almacenar la posición.• La función del home location server está distribuido en varios

nodos de la red ad hoc.• A cada nodo se le asocia un virtual home donde se almacena

su posición.• La asociación entre el nodo y su virtual home se realiza a

través de una función hash que se aplica a su identificador de

Virtual Home


través de una función hash que se aplica a su identificador de nodo.

• La solicitud de posición de un nodo es dirigida a su virtual home donde la información está almacenada.

31

Grid-like structure I

� Subconjunto de nodos actúan como servidores de localización

� Se asume una estructura cuadriculada que se superpone en la red ad hoc.• Todos los nodos conocen a priori esta estructura.

� La cuadrícula se organiza en una jerarquía de cuadrados que simplifican la actualización y la consulta.• La jerarquía de la cuadrícula y el identificador del nodo definen

Grid-like structure


• La jerarquía de la cuadrícula y el identificador del nodo definen para cada nodo móvil su conjunto de servidores.

• Un nodo desconoce sus servidores, pero el protocolo define un procedimiento distribuido y independiente para reconocerlos.

• El nodo solamente envía su posición hacia los nodos de la cuadrícula.

• Cada nodo en la cuadrícula, encuentra el servidor para ese nodo.

• Se utiliza el mismo procedimiento para resolver las consultas.

32

Grid-like structure II

Localization server:

the least ID greater than B


the least ID greater than B

33

Grid-like structure III

How does A find the location of B?


34

Protocolos de enrutamiento

• LAR

• DREAM

• GEDIR

Protocolos de enrutamiento con servicios de localización

� Para enviar los paquetes se necesita la posición de los nodos.• sistemas de localización: GPS u otros mecanismos.

� Los paquetes de datos y control se envían hacía la zona geográfica donde se sabe que está el nodo destino.

� Se adaptan rápido a los cambios de topología


36

Location-Aided Routing (LAR)

� LAR 1998.

� Exploits location information to limit scope of route request flood

• Location information may be obtained using GPS

� Expected Zone is determined as a region that is expected to hold the current location of the destination

LAR


to hold the current location of the destination• Expected region determined based on potentially old location

information, and knowledge of the destination’s speed

� Route requests limited to a Request Zone that contains the Expected Zone and location of the sender node

37

Expected Zone in LAR

X = last known location of nodeD, at time t0

Y = location of node D at currenttime t1, unknown to node S

r = (t1 - t0) * estimate of D’s speed

LAR


X

Y

r

speed

Expected Zone

38

Request Zone in LAR

Request Zone

Network Space

LAR


X

Y

r

S

BA

39

LAR (Location Aided Routing )

� Only nodes within the request zone forward route requests• Node A does not forward RREQ, but node B does.

� Request zone explicitly specified in the route request

� Each node must know its physical location to determine whether it is within the request zone

LAR


� If route discovery using the smaller request zone fails to find a route, the sender initiates another route discovery (after a timeout) using a larger request zone• the larger request zone may be the entire network

� Rest of route discovery protocol similar to DSR

40

Advantatges and disadvantages (LAR)

� Advantages• reduces the scope of route request flood• reduces overhead of route discovery

� Disadvantages• Nodes need to know their physical locations• Does not take into account possible existence of obstructions

for radio transmissions

�LAR


for radio transmissions

41

Distance Routing Effect Algorithm for Mobility (DREAM) I

� Uses location and speed information (like LAR)� Utiliza el servicio de localización DREAM:

• Todos los nodos almacenan la información de todos los nodos.• Nodes periodically broadcast their physical location• Nearby nodes are updated more frequently, far away nodes

less frequently

� DREAM uses flooding of data packets as the routing

DREAM


� DREAM uses flooding of data packets as the routing mechanism (unlike LAR)• DREAM uses location information to limit the flood of data

packets to a small region

42

Distance Routing Effect Algorithm for Mobility (DREAM) II

D

Expected zone

Node A, on receiving thedata packet, forwards it toits neighbors within the cone rooted at node A

DREAM


S

A

cone rooted at node A

S sends data packet to all neighbors in the cone rooted at node S

43

Geographic Distance Routing (GEDIR) I

� Location of the destination node is assumed known� Each node knows location of its neighbors� Each node forwards a packet to its neighbor closest to the

destination� Route taken from S to D shown below

�GEDIR


S

A

B

D

C FE

obstruction

H

G

44

Geographic Distance Routing (GEDIR) II

� The algorithm terminates when same edge traversed twice consecutively

� Algorithm fails to route from S to E• Node G is the neighbor of C who is closest from destination E,

but C does not have a route to E

A DH

�GEDIR


S

A

B

D

C FE

obstruction

H

G

45

Routing with Guaranteed Delivery

� Improves on GEDIR

� Guarantees delivery (using location information) provided that a path exists from source to destination

� Routes around obstacles if necessary

�GEDIR


46

Referencias

References

� S. Basagni, I. Chlamtac, V. Syrotiuk, B. Woodward, “A distance routing effect algorithm for mobility (DREAM)”, MOBICOM, 98.

� J. Li, J. Jannotti, D. De Couto et al, “A scalable locationservice for geographic ad hoc routing”, MOBICOM 2000.

� Young-Bae Ko and Nitin H. Vaidya, “Location-Aided Routing(LAR) in mobile ad hoc networks,” Wireless Networks, Vol.6, 2000.


2000.� Xu Lin , Ivan Stojmenovic ,”GPS based distributed routing

algorithms for wireless networks”, Unpublished manuscript, 2000.

48

protocolos de enrutamiento con servicios de...

Documents