Sistemi Mobili M - unibo.itlia.deis.unibo.it/Courses/sm1415-info/lucidi/03-Mobility(2x).pdf · 4...

1

Mobile IP e Posizionamento - Sistemi Mobili M 1

Sistemi Mobili M

Alma Mater Studiorum - Università di Bologna

CdS Laurea Magistrale in Ingegneria Informatica

II Ciclo - A.A. 2014/2015

Corso di Sistemi Mobili M (8 cfu)

03 – Mobile IP e Posizionamento

Docente: Paolo Bellavista

[email protected]

http://lia.deis.unibo.it/Courses/sm1415-info/

http://lia.deis.unibo.it/Staff/PaoloBellavista/


Mobilità e Gestione Handoff

Networking wireless permette a utenti mobili di usufruire di connettività Internet

Ovviamente, i movimenti utente devono essere gestiti da un’area di copertura ad un’altra Inoltre un utente potrebbe decidere di comandare il passaggio fra

diverse opportunità di comunicazione (ad es. da WiFi a 3G)

Le connessioni attive in corso dovrebbero essere mantenute indipendentemente dai movimenti utente

In reti GSM/UMTS questo richiede acquisizione di risorse per allocazione di canale (preallocazione per continuità di servizio)

In reti IP-based “potrebbe bastare” e “risultare piuttosto semplice” se fosse possibile mantenere lo stesso indirizzo IP per un utente in movimento

mailto:[email protected]

2


Tradeoff in Location Management

Due possibili approcci di principio per consentire la

conoscenza della locazione approssimata dei nodi mobili:

Tramite location update (location registration)

L’infrastruttura di rete è informata dall’esterno della locazione

dell’utente mobile, ad es. per sua esplicita registrazione necessaria

dopo ogni handoff

Tramite location search (terminal paging)

L’infrastruttura di rete è responsabile per il ritrovamento della

locazione dell’utente mobile

Quale tradeoff ottimale fra update e search?

Dipendenza da frequenza di comunicazione rispetto a cambio di

locazione, ricerca dinamica della nuova locazione e costo in

termini di latenza


Location Update

Soluzioni di location update

Statiche (triggering dell’aggiornamento quando si esce da un’area

locale prefissata – non necessariamente singola cella, anzi…)

Dinamiche (triggering dipendente da comunicazioni utente e da

pattern di mobilità)

Location update dinamico

Time-based (ad es. con periodicità prefissata)

Movement-based (forwarding pointer e valutazione dinamica di catene di forwarding troppo lunghe)

Distance-based (quando la distanza percorsa dall’ultimo update è

considerata troppo ampia)

Anche replicazione di informazione di locazione (caching

o replicazione proattiva vera e propria), sia con organizzazione

flat che gerarchica (come sempre per motivi di scalabilità)

3


Location Search o Terminal Paging

Solo qualche cenno su terminal paging (tanto ricordate quanto detto per tecnologie wireless specifiche nelle settimane scorse…)

Blanket polling

Ad es. tutte le celle in una località sotto controllo di MSC vengono

polled quando arriva una chiamata

Alto costo di paging

Expanding ring search

Parte dall’ultima locazione conosciuta per terminale mobile

Sequential paging

Basato su probabilità stimata di locazione (distribuzione di probabilità)

Esplorazione sequenziale, più o meno rigida


Problema della Mobilità

in Rete IP

Problema di overlapping di funzionalità di identificazione

e di locator di IP

Indirizzo IP associato con un nodo mobile è dipendente

dalla rete che fornisce connettività

Quando l’utente si connette ad un’altra rete, l’indirizzo IP tende a

cambiare

I pacchetti che appartengono a connessioni correntemente

attive devono essere consegnati verso il nuovo indirizzo IP

Soluzione intuitiva (approccio location registration): Che cosa fate quando cambiate appartamento in affitto?

Lasciare un indirizzo di forwarding al vostro portiere (“old post-office”)

Il vecchio portiere ha il compito di girarvi la posta presso

il nuovo portiere, che a sua volta ve la inoltra

4


Parentesi:

Host Identity Protocol

A proposal to separate identifier from locator at the

network layer of the TCP/IP stack

A new name space of public keys

A protocol for discovering and authenticating

bindings between public keys and IP addresses

Secured using signatures and keyed hashes

Architectural change to TCP/IP structure

A new layer between IP and transport

Introduces cryptographic Host Identifiers

Integrates security, mobility, and multi-homing

End-host mobility, across IPv4 and IPv6

End-host multi-address multi-homing, IPv4/v6

IPv4 / v6 interoperability for apps


Parentesi:

Host Identity Protocol

IP layer

Fragmentation

Link Layer

Forwarding

IPsec

Transport Layer End-to-end,

Host ID Tags

(HITs)

Hop-by-hop, IP

addresses

HIP

Mobility

Multi-homing

v4/v6 bridge

5


Elementi di Base per

Mobile IP Entità o elementi di base per Mobile IP

Mobile Host (MH)

Home Agent (HA) – simile al concetto di vecchio post-office

Foreign agent (FA) – simile al concetto di nuovo post-office

MH registra nuovo indirizzo presso HA

HA riceve e “cattura” i pacchetti indirizzati a MH e li gira a FA, che a sua

volta li spedisce a MH (correntem. posizionato nella sua località)

Problema di triangolar routing

CH Corresponding Host

MH

FA

HA


Home Agent (HA)

Svolge il ruolo di router, con qualche funzionalità

aggiuntiva

Posizionato nella home network di MH

Si occupa di mantenere mobility binding dell’indirizzo IP

di MH con il suo Care-of Address (CoA)

Indirizzo che identifica la locazione corrente di MH

Ovviamente si occupa di inoltrare pacchetti alla rete

appropriata quando MH non è nella sua località

Tramite incapsulamento (usualmente IP-within-IP tunneling)

6


Foreign Agent (FA)

A tutti gli effetti, un altro router con funzionalità arricchite

Quando MH non è nella stessa località di HA, si utilizza FA

per inviare/ricevere dati verso/da HA

FA esegue advertising periodico di se stesso

Messaggi di advertisement portano info sui vari CoA disponibili, nel

caso ne sia disponibile un insieme

I nodi MH possono scegliere di non attendere messaggio di

advertisement e di stimolare lo scambio di info tramite un

messaggio di solicitation. Secondo voi come?

Una volta che MH riceve il suo CoA da FA, MH registra

questo CoA presso il suo HA

La richiesta di registrazione è inviata attraverso FA


Gestione Indirizzi

Mobility Binding Table

Mantenuta presso HA di MH

Mappa l’associazione fra indirizzo home di MH e il suo CoA corrente

Visitor List

Mantenuta presso FA che sta servendo un MH

Mappa l’associazione fra indirizzo home di MH e il suo MAC address

+ indirizzo HA

7


COA Tunneling

Vi ricordate, vero, che cos’è un tunnel (differenze rispetto a proxy e gateway)?

Quando HA riceve pacchetti indirizzati a MH, HA li inoltra

verso CoA tramite incapsulamento

Il meccanismo di default per incapsulamento che

deve essere supportato da tutti gli agenti Mobile IP è

IP-within-IP (RFC 2003)

HA inserisce un nuovo IP header sull’header

originale per ogni datagramma. Quali potenziali problemi vi vengono in mente per reti IP “tradizionali”?


Esempio Mobile IP

8


COA: Ulteriori Dettagli

Care-of Address (CoA): molto spesso realizzato come normale

indirizzo IP, ma utilizzato SOLO da Mobile IP per forwarding

e per funzionalità di gestione. NON visibile ai livelli superiori

(applicativi), simile a indirizzo non pubblico in reti NAT

Due differenti tipologie

(corrispondono a due diversi

metodi forwarding di HA):

1) Foreign Agent CoA

Fornito da FA nei suoi messaggi

di Agent Advertisement

È indirizzo IP dello stesso FA

Quindi?

Nodo mobile non ha indirizzo IP

distinto su foreign network,

utilizzo di layer 2


COA: Ulteriori Dettagli

2) Co-Located Care-of Address

CoA assegnato direttamente al nodo mobile usando un

qualche mezzo esterno a Mobile IP

Ad es. manualmente da foreign network

o automatic. usando DHCP

In questo caso, CoA può essere

usato per traffic forwarding da HA

direttamente verso nodo mobile

9


Home network Foreign network

Possibili Problemi

di Filtering Ingress/Egress

MH utilizza il suo indirizzo IP home come indirizzo

sorgente

Router ai confini di un dominio e “security-conscious”

possono fare dropping dei pacchetti di MH

1. Pacchetto proveniente dalla rete interna ha indirizzo

sorgente non appartenente alla rete interna

2. Pacchetto proveniente da rete esterna e indirizzato verso

home network ha indirizzo sorgente non appartenente alla

rete esterna bensì alla stessa home network

1 2 CH

MH


Possibile Soluzione:

Tunneling Bi-direzionale

Scelta di percorso “safe” attraverso HA per entrambi i versi

possibili

Meccanismo più lento (maggiore overhead, maggiore latenza) ma

più conservativo in ogni caso di deployment

Noto in letteratura anche come quadrilateral routing

Home network Foreign network

CH MH HA

Source Address = HA

Source Address = COA

10


Triangular Routing Sub-ottimo

Quali possibilità per ottimizzare il meccanismo di routing di

Mobile IP? In quali condizioni runtime tali ottimizzazioni

sono particolarmente cruciali?

Che cosa succede se MH è nella stessa sottorete di CH e

HA si trova dall’altra parte del pianeta?

Ovviamente, vantaggi di performance se potessimo fare routing

diretto dei pacchetti senza passare per gli agenti

Ottimizzazione: consentiamo a CH di conoscere CoA di

MH (MH registra suo CoA presso CH, standard in MobileIPv6)

Processo avviato da HA che notifica CH via “binding update”

MH incapsula i suoi pacchetti per evitare problemi di source-

address filtering, ma li invia direttamente a CH

CH crea il suo proprio tunneling verso MH


Hierarchical Mobile IPv6

(HMIPv6)

Mobile Anchor Point

(MAP) svolgono il ruolo

di Gateway Foreign

Agent strutturati in

modo gerarchico

Sono configurati

staticamente in HMIPv6

e condivisi da tutti i nodi

mobili

11


Hierarchical Mobile IPv6

(HMIPv6)

Local Subnet Handoff

Registrazione CoA al MAP locale quando si ha un handoff locale

fra subnet incluse nell’area di dominio del MAP

MAP Domain Handoff

Registrazione di un CoA regionale (RCoA) presso HA e CN in

seguito ad handoff verso nuovo dominio MAP

Quale è la dimensione “giusta” per un’area di servizio di un

MAP? Quanti livelli gerarchici?


Direzioni di Ricerca: Dynamic MAP (I.R. Chen et al, J. Wireless Pers. Comm, 2007)

Nodi mobili si organizzano in MAP dinamicamente sulla

base del rapporto fra Service rate e Mobility Rate

(SMR)

La dimensione ottimale dell’area di servizio di un DMAP

è dinamica e determinata calcolando tradeoff più adatto

fra costi di service management (per packet delivery) e costi

di location management (per location update)

Degenera in MIPv6 quando SMR diventa sufficientemente

grande (perché dimensione domini DMAP decresce al crescere di

SMR); degenera in HMIPv6 quando la dimensione DMAP

è fissa

12


Direzioni di Ricerca: WMM (D.W. Huang et al, IEEE T.Mobile Comp, 2008)

Wireless Mesh Network Management Mechanism (WMM)

Basato su cache delle info di locazione presso nodi

mesh con funzionalità di routing e location management

Pointer forwarding per gestione handoff

Replicazione e consistenza “weak”

Due tabelle cached: routing table e proxy table (con informazione

sulla locazione dei nodi mobili)

Opportunistic update cache di locazione in caso di routing

Aggiornamento contenuto nell’header di pacchetto

Routing tramite utilizzo delle due tabelle: se info insufficienti allora 1)

verso infrastruttura mesh, poi 2) flooding


Proxy MIPv6 (PMIPv6)

Why PMIPv6 when we have MIP?

Main problems with MIP:

Clients must implement MIP in the kernel (MIP mobility is

host-based)

difficult to implement kernel changes

difficult to deploy (clients need software upgrade to get MIP support)

Handoff procedure is not efficient

large delay

PMIPv6 (RFC5213) is completely transparent to mobile

nodes (use of a „proxy“ to do the handoff work)

PMIPv6 is meant to be used in localized networks with

limited topology where handoff signalling delays are minimal

13


PMIPv6 Terminology

Local Mobility Domain (LMD):

Network that is PMIP-enabled, contains 1 LMA and multiple MAGs

Local Mobility Anchor (LMA):

All traffic from and to MN is routed through LMA, maintains a set of

routes for each MN connected to the LMD

Mobile Access Gateway (MAG):

performs mobility-related signalling on behalf of its MNs, the access

router (first hop router) for the MN

NetLMM:

Network based Localized Mobility Management (IETF working

group for network-based mobility support)

Binding Cache:

Cache maintained by LMA; it contains Binding Cache Entries

(BCE), with fields MN-ID, MAG proxy-CoA and MN-prefix


PMIPv6 Terminology

Binding Update List:

Cache maintained by MAG with info about attached MNs

Proxy Binding Update (PBU):

PMIP signalling packet sent by MAG to LMA to indicate a new MN,

with the fields MN-ID (e.g. MN MAC), MAG address (proxy-CoA)

and handoff indicator (whether MN-attachment is new or a handoff

from another MAG)

Proxy Binding Acknowledge (PBA):

Response to a PBU sent by LMA to MAG, contains MN-ID, MAG

address and prefix assigned to MN

Proxy care of address (proxy-CoA):

IP address of public interface of MAG

14


PMIPv6 Architecture and Deployment

Mobile Node Identifier (MN-ID):

Unique MN identifier, e.g., one of its MAC addresses but also HIP.

Home Network Prefix:

Prefix assigned to MN by LMA


General PMIPv6 Setup

15


PMIPv6 vs. Mobile IP


Mobile IP (e varianti) è Sufficiente?

TCP standard e non modificato porta a significativo

degrado di performance su link wireless

Perché?

Link wireless sono afflitti da alto Bit Error Rate (BER) e da frequenti

disconnessioni/riconnessioni

Per TCP, queste caratteristiche si manifestano come perdite di

pacchetto random & bursty

In TCP, TUTTE le perdite di pacchetto sono trattate some sintomi

di congestione di rete, e quindi producono riduzione della

frequenza di trasmissione (in modo moltiplicativo), con ri-crescita

lenta…

16


I-TCP:

Idea di Base

Utilizzo di un approccio a “split-connection”

TCP tradizionale e standard fra Fixed Host (FH) e Mobile Source

Router (MSR)

Wireless TCP fra Mobile Host (MH) e MSR

Mobile Host

Base Station Internet

Fixed Host

Split connection

Wireless TCP

Regular TCP

MSR


Split Connection:

Vantaggi e Svantaggi

Vantaggi

Separa controllo di flusso e di congestione sulle due tratte

(link wireless e link wired separati)

Retro-compatibile con TCP (FH può NON essere aware di

MSR)

Svantaggi

Violazione della semantica classica end-to-end (ne parleremo anche più avanti – principio end-to-end)

MSR mantiene stato

Guasto su MSR può produrre perdita di connessione

Latenza di handoff cresce per la necessità di trasferimento

di stato

Se non si fanno ottimizzazioni particolari, copia di dati presso

MSR

17


I-TCP

Costruito su Mobile IP

MSR fa da proxy per MH

Svolge il ruolo di immagine di MH e inoltra il suo stato al nuovo MSR in caso di handoff

I-TCP non compromette affidabilità end-to-end

Purché non ci sia guasto di MSR e disconnessione di MH per tempo indefinito

Adatto per applicazioni throughput intensive


Handoff in I-TCP

Fortemente integrato con la procedura di

registrazione in Mobile IP

Handoff comincia quando MH avvia la registrazione del nuovo

CoA presso HA

Trasferimento dello stato della socket operato da un

demone I-TCP verso il nuovo MSR

Buffering di segmenti dati in transito durante lo

svolgimento della procedura di handoff – per evitare

congestion control

Deve essere veloce al fine di evitare realizzazione e trasferimento di

copie non necessarie

18

Mobile IP e Posizionamento - Sistemi Mobili M

Ricapitolando…

Alcuni pattern/direzioni di soluzione che abbiamo già

incontrato e di validità generale:

Anchor point fisso (home)

Proxy (più o meno trasparenti ai vari livelli)

Organizzazione gerarchica ai fini di scalabilità, più o meno dinamica

Raggruppamento

Funzioni differenziate all’interno del gruppo

Decisioni (e protocolli) che sfruttano concetto di

località, cercando di convergere verso comportamento

globale desiderato senza coordinamento globale pesante

Approccio verso soluzioni approssimative (purché lightweight) e

ottimistico

35


Nuova classe di servizi, sempre più diffusi:

Location-Based Services (LBS)

E-911 Emergency assistance

Advertising

Tracking: ad es. tracce di mobilità abituale

Virtual Tour: a che cosa ti trovi vicino?

Service discovery

Ottimizzare comunicazioni ad hoc fra dispositivi mobili

Locazione (o Posizionamento):

Perché?

http://images.google.it/imgres?imgurl=http://images.amazon.com/images/P/B00029BQ9S.01._SCLZZZZZZZ_.jpg&imgrefurl=http://www.rated4stars.com/html/tomtom-go-gps-32mb.html&h=421&w=500&sz=38&tbnid=iH1dgeYbziMJ:&tbnh=106&tbnw=127&hl=it&start=17&prev=/images%3Fq%3Dtom%2Btom%26svnum%3D10%26hl%3Dit%26lr%3D%26sa%3DG

19


Come Ottenere

Info di Posizionamento?

Molte applicazioni LBS requisiti molto differenziati

– E-911: on request (coordinate xy)

– advertising + virtual tour: cambi di locazione (stanza, strada, …)

– Supporto alla rete: ogni X minuti (network area)

– Supporto alla navigazione: ogni X secondi (coordinate xy)

Altri requisiti non-funzionali:

– Basso consumo di potenza, facilità di utilizzo, privacy,

...

La conseguenza è molti sistemi di

posizionamento con caratteristiche

differenziate


Classificazione:

Fisico vs. Simbolico Fisico

Associato a info adatte per elaborazione machine/computational

WGM84 Location (GPS) - latitudine, longitudine, altezza ellissoide (altitudine)

Simbolico

Associato a info adatte per human speaking/thinking

Locazione a livelli - {Italy, Bologna, EngFaculty, DEIS, Lab2}

Anche Assoluto vs. Relativo

Assoluto

Unico sistema di riferimento per tutti

gli oggetti localizzati

Fisico o simbolico

Relativo

Relativo alla locazione di un altro oggetto

Tipicamente fisico e utile per scenari ad-hoc

20


Classificazione:

Centralizzato vs. Distribuito

Centralizzato Un sistema centrale processa info e

determina locazione per tutti gli oggetti

posizionati

Distribuito Ognuno determina la propria locazione

Problematiche di privacy: Comunicazione in rete intrinseca limitazione,

no privacy in senso stretto,

a meno di relazioni di trust

Ogni info location-dependent resa visibile

riduce la privacy utente

LBS

Positioning

Service

MN


Classificazione:

Accuratezza & Precisione

Accuratezza: range di errore (ad es. metri)

Precisione: grado di fiducia nel range di errore (confidence, in percentuale)

GPS: accuratezza = 10 metri, precisione = 95%

Accuratezza e precisione derivano usualmente in modo

diretto dal sistema di posizionamento utilizzato e dalle

condizioni dell’ambiente di deployment

Scalabilità

quale area e di quali dimensioni? Ad es. coverageArea / #infrastructUnit

quanti utenti? Ad es. #user/(infrastructure unit * time unit)

Quante risorse computazionali? Quale complessità infrastruttura e

middleware?

21


Classificazione:

Costo e Limiti

Costo. In termini di:

tempo, infrastruttura, deployment di infrastruttura, lato cliente,

hardware addizionale, consumo di batteria, consumo di

memoria, consumo di computing power, …

Limiti

Dove/quando possibile utilizzarlo?

Ad es. indoor vs. outdoor


Scelte di Design/Progetto

o Vincoli Tecnologici?

Come riuscire a mettere insieme caratteristiche multiple in un unico sistema di posizionamento?

Location Based

Service constraints

Environment

constraints

Positio

nin

g S

yste

m

Physical/Symbolic

Absolute/Relative

Centralized/Distributed

Accuracy & Precision

Recognition

Limitations

Cost

Scale

User requests

?

22


Tecniche di Base:

Lateration

2D 3 circonferenze

numero maggiore di circonferenze

per mitigare errori nella misura

di distanza

Note:

2 variabili, 3 misure

2 misure sufficienti solo quando sulla linea fra due

reference point (circonferenze tangenti)

Reference point

Locating point


Misura diretta

Time of Arrival (ToA) distance = signal speed * ToA

Received Signal Strength Indication (RSSI) Potenza e attenuazione segnale

Tecnologie utilizzate comunemente

InfraRosso (IR), RadioFrequenza (RF), UltraSound (US)

Determinazione Distanza: Come?

Tx Rx 1s

2s

3s

Tx Rx -60dB -70dB

-80dB

23


three different TDoA:

0.4, 0.6 and 0.9 scale units

Time Difference of Arrival

2D 2(3) iperboli

iperbole: punto posto alla stessa Time

Difference of Arrival (TDoA) da due punti di

riferimento

1 2

3

TDoA13

TDoA12


Angolazione

Prerequisito:

Conoscere la distanza fra due punti di riferimento

2D 2 angoli 2 misure

Teorema di Carnot

a2=b2+c2-2bc•cos

b2=a2+c2-2ac•cos

2 equazioni con

2 variabili (a, b)

known length c

a b

sinsin

ba

Teorema di Eulero

24


Analisi Scenario di Deployment:

Scene Analysis

Inferenza di posizione usando osservazione passiva di “fenomeni fisici” (immagini, RSSI...), ma senza sfruttare valori fisici come distanze, angoli, iperboli, …

Requisito: conoscenza ambiente Ambiente si modifica nel tempo?

Fase preliminare

Osservazione ambiente e collezionamento dati monitoraggio

Fase operativa Osservazione ambiente e comparazione fra dati osservati e “dati

storici”


Prossimità

Locazione corrente ≡ punto di riferimento più vicino ToA, RSSI...

Contatto fisico mouse, keyboard, sedie, …

Cella che “fa da Care of”

Accuratezza dipende da raggio

della cella

Sistemi automatici di identificazione Carta credito, sistemi pedaggio autostradale (Telepass, e-toll

system, …), carte di fidelizzazione (carburante, supermercati, ...),RFID (accesso edifici, ad es. Ingegneria)

25


Sorgenti di Errore

Non Line Of Sight (NLOS)

Fading:

Multipath

Shadowing

Sincronizzazione clock

Tx Rx

Tx Rx


Sistemi di Posizionamento

per Ad-hoc Network

Obiettivo importante: ottenere info topologiche e

posizionamento per

Mantenimento connettività

Ottimizzazione traffico

Metodologie cooperative, con ruolo uniforme per tutti i

nodi:

1. Ogni nodo riceve informazioni di range e posizionamento dai nodi

vicini

2. Risolve un problema locale di posizionamento

3. Trasmette il risultato ottenuto ai vicini

Algoritmi distribuiti senza necessità di comunicazione

globale

Particolarmente usabili quando mobilità nodi è limitata

26


Assumption Based Coordinates

(ABC)

Anchor node: nodo dalla locazione nota a priori

Assumption Based Coordinates Informazione nota: distanza relativa fra nodi

Distanze possono essere affette da errori

Ogni anchor node si crea la propria mappa delle distanze relative per nodi a distanza one-hop

01

132

032

012

32r

rrr x

01

32

2

2

2

2232

032

32r

2rr xxyxy

2

3

2

3032

3 r yxz

01

122

022

012

22r

rrr x

2

2022

2 r xy

011 rx

rjk: distanza fra nodo j e nodo k

n1=(x1, 0, 0)

x

y

z

x1

y2

x2

z3 y3

x3

n2=(x2, y2, 0) n3=(x3, y3, z3)

n1

n2

n3

n0


TERRAIN

Triangulation via Extended Range and Redundant

Association of Intermediate Nodes (TERRAIN)

Creare una unica mappa dei

nodi che sfrutta

informazioni di nodi a

distanza multi-hop

extended range =

#hop * average node distance

27


Sistemi di Posizionamento con

Hardware Addizionale

Hardware special-purpose sviluppato specificamente e

aggiunto per ottenere info di locazione

Basato su RadioFrequenza, InfraRosso, (Ultra)Sound

Migliora accuratezza e precisione

Tende ad accrescere dimensione device e

consumo di energia

Esempio notevole sistema posizionamento

esterno= Global Positioning System (GPS)

USA Department of Defense (DOD)

Almeno 24 satelliti operativi in orbita a 11000 miglia (ca. 18000km)

http://tycho.usno.navy.mil/gps.html

Primo satellite: 14 Feb 1989

Sistema di posizionamento più diffuso (non è l’unico…)


Informazioni conosciute grazie a GPS:

Posizione satellite

Tempo di propagazione segnale da satellite a cliente (ca. 60ms)

distanza=ToA*light speed

Come usare queste info?

Lateration + ToA

3 satelliti 2 posizioni possibili

1 posizione non è però sulla superficie terrestre

(space/ultra-atmospheric elevation)

GPS: Come Funziona?

28


GPS: Sincronizzazione

ToA necessità di

sincronizzazione clock

satellite con clock atomico

Alta accuratezza

clienti con clock “normale”

Problemi di accuratezza

Errore di 1µs ca. 300m

Sincronizzazione, sfruttando protocollo con 4 satelliti (3 per soluzioni

2D): clock cliente sono affetti da

shifting fino a operazione di

sincronizzazione esempio 2D di errori di sinc

61µs

(60µs)

51µs

(50µs)

71µs

(70µs)

overestimated

(correct)


Errori in GPS

Altre svariate potenziali sorgenti di errore:

Condizioni atmosferiche: ionosfera (0-30m) e troposfera (0-30m) rifraggono segnale GPS cambio di velocità segnale GPS

Errori dovuti alle Ephemeridi: posizionamento orbita satellitare (1-5m)

Clock drift: anche gli orologi atomici non sono perfetti (0-1.5m)

“Rumore” di misurazione (0-10m)

Selective Availability: fino al 2000, introdotta appositamente da DoD (0-70m)

Multipath: edifici di altezza elevata, montagne, ... (0-1m)

Per maggiore accuratezza GPS differenziale

29


GPS Differenziale (D-GPS) come esempio di Ground Based Augmentation System

Si sfrutta una base station (o

altro elemento di infrastruttura) con

posizione perfettamente

nota per calcolare differenze da posizionamento esatto ed

eliminare errori (errore sistematico)

Cliente GPS opera l’usuale

computazione

Migliore accuratezza (anche

15-50cm vs. 50-100m)

sottraendo vettore errore

sistematico a locazione

calcolata da GPS non

differenziale

Source GPS D-GPS

Ionosphere 0-30m Mostly

Removed

Troposphere 0-30m All Removed

Signal Noise 0-10m All Removed

Ephemeris

Data 1-5m All Removed

Clock Drift 0-1.5m All Removed

Multipath 0-1m Not Removed

SA 0-70m All Removed


Locazione fisica + assoluta

WGS84 World Geodetic System: latitudine, longitudine e

altezza ellissoide (compensa movimento continenti)

Distribuito

Costo: infrastruttura (!!!) + cliente

Scalabilità: completamente distribuito ottima scalabilità

No identificazione + distribuito user privacy

Accuratezza = 100m/

30


Non solo GPS:

Active Badge Olivetti Research Laboratory (ora AT&T Cambridge):

uno dei primi approcci al problema

Tecnologia a infrarossi Badge emette periodicamente un identificatore unico

Rete di sensori riceve segnali dai badge (necessità di prossimità, tipicam. stessa stanza)

Server centrale raccoglie dati

dei sensori

Proprietà: Basato su prossimità

Simbolico, assoluto

Identificazione utenti

Basso costo

Accuratezza a livello di stanza

IR non lavora bene in presenza di

luce solare e fluorescenza


Active BAT

AT&T Active BAT Sostanzialm. tecnologia ultrasuoni (US)

Badge emette un identificatore unico verso un server centrale

Server centrale Fa triggering del badge (via RF), chiedendogli

di inviare segnale US

Fa reset dei ricevitori US montati su soffitto

Raccoglie dati

Calcola la posizione del badge

Proprietà:

ToA, fisico, assoluto, identificazione,

basso costo, accuratezza = 9 cm,

precisione = 95%

31


AHLoS:

Ad-Hoc Localization System

UCLA AHLoS

Tecnologie RF, US

Lateration + ToA

RSSI vs. RF, US WINS (900 MHz RF)

Medusa (US)

Property RSSI UltraSound

Range same as radio

communication range 3m

Accuracy 2-4m for WINS 2cm for Medusa

Measurement

Reliability

hard to predict, multipath

and shadowing

multipath mostly predictable,

time is a more robust metric

Hardware

Requirements

RF signal strength must be

available

US transducers and amplifier

circuitry

Additional Power

Requirements none tx and rx signal amplification

Challenges

large variances in RSSI

readings, multipath,

shadowing, fading effects

interference, obstacles,

multipath


Sistemi di Posizionamento senza

Hardware Addizionale

Utilizzare ciò che è già disponibile per motivi di

comunicazione: GSM/GPRS/UMTS, Bluetooth, 802.11

Ad esempio, reti cellulari GSM e posizion. network-based Cell Global Identity (CGI)

Angle of Arrival (AoA)

Timing Advance (TA)

Signal Strength

Uplink Time of Arrival (UL-ToA)

Uplink Time Difference of Arrival (UL-TDoA)

CGI (with directional antennas)

CGI + TA (with directional antennas)

CGI + TA

550 m

100m – 35Km

CGI

32


Posizionamento tramite GSM

Oppure, sempre in GSM, Mobile Station (MS)-based

Enhanced - Observed Time Difference (E-OTD ≡

TDoA)

Almeno tre Base Transceiver Station in visibilità

Timing Advance

Almeno 2 handover “forzati”

Technology Computation

locality

User

Controlled

Privacy

Modifications System Accuracy

HW SW urban

environment

rural

environment

CGI network no none none > 100m < 35 Km

CGI+TA network no none none > 100 m circle of arc

of 550 m

UL-ToA network no GPS for clock synch 150 m 50 m

UL-TDoA network no GPS for clock synch 50 m 80 m

E-OTD MS yes none yes 200 m 60 m


Posizionamento tramite Bluetooth

Bluetooth è a basso costo e raggio copertura relativam. limitato prossimità, accuratezza < raggio BT (ca. 10m)

simbolico, assoluto, distribuito

Possibile soluzione : Dispositivi BT installati presso Point Of Interest (POI)

DB locazioni POI:

associazione BT POI MAC Address locazione POI

Visibilità di molteplici dispositivi BT

Scelta di quello più vicino con maggiore RSSI

LocA LocB

33


1. POI fanno broadcast MAC address

2. Dispositivo fa overhearing dei POI

3. Dispositivo si connette ai POI visibili

4. Per ogni POI, dispositivo misura

RSSI della connessione

5. Dispositivo calcola la sua locazione

sfruttando comparazione di RSSI

Possibile Funzionamento

Looking for

BT POI Read RSSI

Select a POI

Connect to

BT POI

Baseband

connection

& RSSI

MAC

address


Bluetooth permette

Livelli di Privacy Differenziati

Dispositivo vuole conoscere quali POI sono vicini, ma forse

non rendere consapevoli i POI della sua presenza.

Ricordiamoci che comunicazioni wireless possono

essere asimmetriche

Cliente BT:

inquiry scan on

Ogni POI BT vicino può vedere il dispositivo

page scan on, inquiry scan off

POI non possono vedere il dispositivo ma possono tentare

connessione se conoscono identificatore

Inquiry scan off, page scan off (NO visibilità di RSSI però…)

stealth mode: nessuno può vedere il dispositivo (fino a che non si

connette…)

34


PlaceLab

Idea base: sfruttare wide-scale WiFi deployment

Aree urbane con copertura “densa” di WiFi AP

WiFi AP inviano beacon con ID unici (MAC address di AP)

Posizionare dispositivi WiFi utilizzando una mappa di

corrispondenze base-station-ID verso locazioni

Molti algoritmi disponibili per calcolare la posizione

approssimata basata su punti di riferimento noti


PlaceLab:

Quali Problemi Principali?

Costruire un DB mondiale delle posizioni di tutti gli AP WiFi Come stimare la posizione di AP se i dati esatti non sono

disponibili?

Buoni algoritmi per posizionamento accurato Tradeoff fra accuratezza e overhead di calibrazione

Modello di privacy accettabile per un largo pubblico di utenti Chi determina la locazione?

Come può l’utente finale tenere sotto controllo la sua info di locazione?

//slashdot.org/search.pl?topic=193//slashdot.org/search.pl?topic=193//slashdot.org/search.pl?topic=193//slashdot.org/search.pl?topic=193

35

Panoramica su Comunicazioni Wireless - Sistemi Mobili M

PlaceLab: Metodologia

Fase di Training Raccogliere beacon da AP WiFi tramite “war driving” con dispositivi

equipaggiati di IEEE802.11+GPS

Da questa raccolta dati si memorizzano

Coordinate GPS

Liste di AP

Richiede circa lavoro di 1hr per km2

Costruire mappa del segnale radio a partire dalle tracce raccolte

Fase di Positioning Utilizzare mappa radio per posizionare utente finale

Eventualm. comparare la posizione stimata con quella restituita da GPS per raffinamenti successivi


RADAR: Idea di Base

Per certi versi simile a PlaceLab, per ambienti indoor

Scenario: IEEE 802.11 AP

Analisi di scena (scene analysis, fingerprinting) basato su RSSI

2 fasi: prima fase off-line, poi fase real-time

36


RADAR: Fase Off-line e

Fase Real-Time

Fase off-line

Raccolta di dati empirici dal campo, accumulati lato

infrastruttura

Clienti mobili fanno broadcast periodico di pacchetti UDP che

contengono locazione e orientamento spaziale inseriti

manualmente dagli utenti

AP raccolgono e memorizzano RSSI (medio) per pacchetti

UDP ricevuti, con associato timestamp (necessità sinc. nodi)

server mette insieme dati raccolti da ogni AP partecipante

Fase real-time: tracking dei dispositivi

Clienti mobili fanno broadcast periodico di pacchetti UDP

Server centralizzato calcola locazione

Nearest Neighbor in Signal Space (NNSS), con distanza

euclidea fra valori di RSSI, oppure

Algoritmi basati su storico, oppure…


Ekahau: Idea di Base

Modello di mondo-ambiente stocastico, non

deterministico e viene accettato il fatto che i segnali

misurati siano inerentemente affetti da rumore

Calibrazione del modello risolto come problema di

machine learning: ancora una volta, scene analysis basato su valori di RSSI

Principio di rail tracking:

Locazione corrente è probabilmente vicina alle locazioni più

recenti

Utenti possono solo seguire cammini consentiti (legal path, ad es.

NO attraversamento di muri) Hidden Markov Model

37


Ekahau: Architettura e Principi

Simile a RADAR (fase learning, RSSI fingerprinting) ma...

Dispositivi mobili raccolgono dati di RSSI (non AP) e li inviano

a server centralizzato solo quando necessario per determinare

loro locazione quindi dispositivi mobili possono scegliere

quando/se essere posizionati dal server

Rail tracking con mappa

dell’ambiente e percorsi

consentiti


Ekahau: Caratteristiche

fisico & simbolico

assoluto

basso costo? raccolta dati è time-consuming

privacy: ci fidiamo del server Ekahau?

38


Sensor Fusion:

Positioning Fusion

In generale, approccio in cui N sorgenti

dati vengono aggregate per fornire M

output

Da raw data a structured/aggregated

data con maggiore livello di astrazione

Approccio possibile anche per

posizionamento. Ad esempio, sistema

VTT:

NO aggregazione, pura selezione

Meccanismo di voto (massimizzare)

velocità v, età del posizionamento tage,

accuratezza ε

vtk

age

n

*

1


Universal Location Framework

Molteplicità di sistemi di

posizionamento

GPS, IEEE 802.11, Mote (sensore

low-cost di Berkeley)

Misure in formato WGS-84

GPS: raw data

aggiunta di info accuratezza

802.11: RADAR-like

aggiunta di altitudine

gestione consumo batteria

Mote: prossimità WGS-84

da info simbolica a fisica

39


Fusione

Gestione sensori

uno o multipli insieme?

accuratezza & precisione

Modello di mobilità

sfruttamento di info di velocità e

orientamento spaziale

Calcolo del valore “fuso”

Location API comune e di alto

livello

aggiornamento automatico, manuale,

periodico

Gestione cross-layer di sensori

e qualità dell’info di locazione

Universal Location Framework


PoSIM e JSR-179

Positioning System Integration and Management (PoSIM)

Basato su approccio “translucent”

Trasparenza: Policy & Data Managers

Visibilità: Positioning System Access Facility

Conforme a standard Java JSR-179 (per chi volesse approfondire…)

control data

Positioning

System

PSW

Positioning

System

PSW

Positioning

System

PSW

Data

Manager

Applic

atio

ns

Policy

Manager

PoS

IM A

PI

tran

sp

are

nt v

isib

le

Positio

nin

g S

yste

m

Access F

acility

Sistemi Mobili M - unibo.itlia.deis.unibo.it/Courses/sm1415-info/lucidi/03-Mobility(2x).pdf · 4...

Documents

Transcript of Sistemi Mobili M - unibo.itlia.deis.unibo.it/Courses/sm1415-info/lucidi/03-Mobility(2x).pdf · 4...