A LOCATION BASED MOBILE SOCIAL NETWORK

Fondamenti di Localizzazione e Mobilità

Di Donato Leonardo19/12/2011

Abstract

Il software proposto permette a un utente di condividere e collaborare in tempo reale con altri utenti ad esso vicini, anche in contesti mobili. Argomenti:

● Scenari d'utilizzo● Requisiti e problematiche● Tecnologia di comunicazione● Tecnologia di localizzazione● Il sistema● Valutazione del sistema

Scopo

Permettere ad ogni utente di stabilire una comunicazione con altri utenti presenti in un determinato raggio d'azione. La comunicazione è finalizzata alla condivisione di dati e/o alla collaborazione in tempo reale fra utenti. Tale obiettivo è raggiungibile anche per utenti in movimento. È auspicabile che l'utilizzo sia indipendente dal dispositivo (smartphone, tablet, laptop) di cui essi dispongono.

 

Scenari d'utilizzo

Contesto indoor

● sale per conferenze● scuole● uffici di lavoro 

Contesto outdoor

● in generale, ambienti con densità d'utenti medio-alta

Tipologie di scenari:

● connettività e sistema collaborativo su richiesta

● sistema collaborativo flessibile e distribuito In generale, i sistemi accomunabili a quello proposto, permettono: estensione della copertura di rete, diminuizione del digital divide, aggiramento dei meccanismi di controllo centralizzati, ecc. ecc.

Requisiti e problematiche

● fase di configurazione semplice e automatica● tecnica di localizzazione adeguata● meccanismo di suggerimento all'utente delle posizioni

con migliore copertura di rete● meccanismo di caching e sincronizzazione dei dati

finalizzato a rendere il software indipendente dalla presenza di connettività Internet

● meccanismo di condivisione della connessione a Internet

 Il sistema deve funzionare minimizzando il costo infrastrutturale e il dispendio energetico dei dispositivi.

Wireless Mesh Newtork (WMN)

 Cosa sono:

● nuovo tipo di reti di comunicazione wireless a topologia mesh

● ogni nodo si comporta sia da client sia da router (P2P)● rete wireless distribuita, self-organizing e self-healingCosa serve:

● dispositivi che supportino lo standard 802.11 (a/b/g/n)● algoritmo di routing dinamico● protocolli di comunicazione incentrati su metriche di

performance della rete (packet loss ratios)

Il sistema proposto è un'applicazione delle WMN.

Conoscendo la posizione dei nodi di una rete mesh è possibile migliorarne le sue caratteristiche ...

● individuare una strategia che minimizzi il numero di Mesh Router (MR) necessari e individui le loro posizioni migliori in una data area (migliore copertura di rete)

● individurare, data la posizione di un Mesh Client (MC), i migliori MR a cui collegarsi (miglior trasferimento dati)

Localizzazione

Anche se la localizzazione nelle reti mesh è un aspetto su cui non è stata riposta ancora molta attenzione, esso è molto importante.

Localizzazione

RSS Fingerprinting

● fase di calibrazione (offline): il nodo client misura la potenza dei segnali radio ricevuti (RSS) da vari nodi router mentre cambia posizione, raccoglie tali dati al fine di creare una mappa

● fase di esercizio (online): il nodo client ricava la sua posizione confrontando (in modo deterministico o probabilistico) il valore RSS attuale con la mappa

Svantaggi:

● fase di configurazione offline● tecnica più adatta a reti con topologia fissa   

Localizzazione

MultilaterationBasato sulla metrica Time Difference of Arrival (TDoA). Vantaggi:

● costo di configurazione nullo● slegato dal tempoSvantaggi:

● livello di accuratezza● necessità di (almeno 3) ricevitori in posizioni

conosciute Integrabile a supporto della tecnologia di localizzazione precedente.

 

Localizzazione

SPRA + ROL(1)

● Subtle Partial Range AwareMeto di misura della distanza basato sulla corrispondenza fra intervalli di distanze e intervalli di valori RSSI ricevuti.

● Ring Overlapping-Based Localization AlgorithmUtilizza le regole di mapping insieme-insieme di SPRA per individuare l'anello circostante ad ogni mesh router. Considerazioni: errore di localizzazione ~3 m, costo di ROL ~ O(m2) dove m è il numero di mesh router.         

(1) "A GPS-free Wireless Mesh Network Localization Approach", 2009. 

Altre tecnologie di localizzazione

● GSM Multilaterarion e GSM Fingerprinting: tecnologia valida solo per smartphone, scarsa precisione

● RFID: impatta pesantemente sull'infrastruttura

● GPS: indoor è poco preciso (le onde radio dei satelliti non penetrano facilmente imuri)

● A-GPS: per contesti outdoor è integrabile

● Advanced Forward Link Trilateration (ALFT): usa il TDoA e le torri cellulari, richiede spesso modifiche al software del device, buon livello di precisione, usato spesso in tecniche ibride

● Dead Reckoning + IMU: integrabile per ottenere maggiore precisione, insieme a algoritmi di learning (Kalman Filter o Particle Filtering) per risolvere il problema di localizzazione come un problema di ottimizzazione

 

Mesh Router Placement

Il problema:

● Quanti nodi router deve avere la WMN?

● Dove dovrebbero essere posizionati?

- numero di nodi router necessari VS richiesta di copertura - Grafo G=(V, E) per modellare il problema: V insieme di tutte le possibili posizioni candidate (o nodi).

● si cerca G'=(V', E), con V' insieme delle posizioni scelte per i nodi router, tale che questo sia un grafo di copertura minimo (MST)

● fase di merging

  

Mesh Client Allocation

Il problema:Data una determinata topologia della WMN, e la locazione di un nodo client in un determinato istante, trovare i migliori nodi router cui connettersi. Affrontato come un problema di "optimal stopping" [link].Risolto utilizzando una strategia probabilistica conservativa che massimizza la probabilità di scegliere il nodo migliore, in un determinato istante temporale. 

Algoritmi per il routing dinamico

Optimized Link State Routing (OLSR e OLSR-NG)Individua un Multipoint Relay (MR) verso il quale i nodi devono inviare informazioni di stato e da cui aspettare informazioni di routing [link]

● Hazy-Sighted Link State (HSLS)Estende il precedente ottenendo una maggiore scalabilità (fino a 1000 nodi mesh)

● Better Approach To Mobile Adhoc Networking (B.A.T.M.A.N.)Decentralizza le informazioni relative al miglior percorso di routing

Altre considerazioni

● Algoritmo efficiente di memorizzazione e compressione della topologia della rete

● Utilizzo di protocolli di comunicazione incentrati su metriche che misurano la performance della rete

● Caching dei dati in locale che preservi la loro consistenza

● Sincronizzazione dei dati locali fra i vari nodi (necessario un server locale virtuale in ogni nodo)

● Sincronizzazione con Internet, quando almeno un nodo della WMN può condividerne l'accesso

Un aspetto critico: la scalabilitàCriticità ereditata dall'architettura delle reti mesh.

 Studi teorici e applicazioni reali di applicazioni di WMN (es: OLPC) hanno dimostrato che in ogni mesh cloud, se il numero di nodi supera le 25 unità, le performance degradano significativamente. È necessario implementare un meccanismo di scelta intelligente dell'algoritmo di routing in base alla dimensione e complessità raggiunta dalla topologia della rete.Esempio: effettuare routing gerarchico fra cluster di nodi con migliori prestazioni(2). 

(2) "Scalable Mesh Networks and The Address Space Balancing Problem", 2010. 

Grazie per l'attenzione.