Unita’ di Genova - DISI
Vittoria Gianuzzi
Massimo Ancona
Gabriella Dodero
Rapporto tecnico WP1T1 Architettura
Rapporto tecnico relativo alla situazione funzionale e finanziaria dei
supporti mobili disponibili.
arsenio.disi.unige.it/~gianuzzi/WP1
Sono stati considerati i punti:
• Analisi degli Scenari Operativi
• Analisi dello hardware
• Analisi delle periferiche
• Analisi del software
• Processori StrongARM e Xscale
• Protocolli 802.11b e 802.11g
• File System per reti mobili
• Protocolli di routing specializzati per reti ad-hoc
• Tool di simulazione
WP1 Scenari
Scenario A:
E' la situazione piu' semplice. Si ha una sola rete MANET che non
prevede connessioni con l'esterno.
Hardware necessario: ogni unita' deve essere munita di un elaboratore con
periferica WiFi. Si possono prevedere ulteriori periferiche quali GPS
e/o WEBcam.
WP1
Scenario B:
Access Point funzionanti in modo bridge al fine di aumentare la copertura
delle singole unita'. Tali ripetitori, posti in punti strategici, possono essere
dotati di antenne omnidirezionali.
Struttura ad albero il cui un nodo e' un router, i figli sono Access Point in
modalita' bridge o unita‘, ecc.
Hardware: ogni unita' deve essere munita di un elaboratore con periferica
WiFi. Sono necessari degli Access Point da usare in modalita' repeater,
router WiFi, batterie a lunga durata ed eventuali pannelli solari. Eventuali
antenne verticali omnidirezionali esterne, antenne direzionali quali pannelli
o yagi ed antenne direzionali ad alto guadagno quali parabole di piccolomedio diametro. Si possono prevedere ulteriori periferiche quali GPS e/o
WEBcam.
WP1
Scenario C:
Possibilita' di avere a disposizione un accesso a rete fissa raggiungibile
tramite collegamento con satelliti geostazionari a bassa quota, satelliti
LEO, collegamenti cellulari (GSM, GPRS, UMTS) o collegamenti fissi
(commutata, LAN esterne tra le quali Internet).
Il middleware dovra' scegliere, volta per volta, il media piu' indicato
considerando l'energia necessaria e le varie possibilita' di trasmissione.
Hardware: schede per i collegamenti cellulari o sistemi per la comunicazione
satellitare.
WP1
Scenario D:
Rete wireless ad hoc comprendente anche unita' non mobili quale
l'installazione di un centro coordinatore sul luogo della ricognizione (ad
es.: un furgone con generatore ed apparecchiuature varie). A questo
scenario quindi si deve abbinare sempre uno tra i precedenti scenari che
sara' quello che governa, unita' non mobili a parte, la rete MANET adhoc.
Analisi dello hardware e periferiche
PDA:
PDA attualmente disponibili e completi. La scelta e' caduta su di essi
basandosi sulle loro caratteristiche, prezzi, architettura e competenza
dimostrata dal produttore nell'ambito dei prodotti wireless.
I PDA Sharp vengono venduti con Embedix (Linux based OS).
Sugli alti e' invece necessario installare una distribuzione Linux a parte
Una distribuzione Linux completa e gia' testata presso il laboratorio
DISI e' Familiar.
WP1
Dall'analisi di questi prodotti notiamo come il mercato si stia spostando su
processori della famiglia XScale.
Access Point e Router (802.11b e 802.11g)
Periferiche considerate: webcam per PDA, schede wireless, schede GSM,
GPRS, WiFi, GPS.
Analisi del Software
In particolare software orientato a PDA
Diversi cross compilatori per C/C++ su StrongARM
Virtual Machine Java
Blackdown: supporto di AWT, SWING, RMI, JINI
Linguaggi di scripting (Python)
JXTA: Implementato in Java. Mette a disposizione un set di protocolli per la
connettivita' di sistemi mobile dai cellulari, alle reti wireless, ai PC in un
sistema P2P.
Filesystems ottimizzati per reti Ad-Hoc
I filesystem per reti mobili sono maggiormente orientati alle reti con infrastuttura,
come Coda e Odissey (basato su Coda, con elementi di QoS)
Fra quelli orientati invece a MANET abbiamo Mobile Aleph (Brown University)
e Lime
Protocolli di Routing specializzati per il Mobile
•
Algoritmi proattivi o reattivi. Nel primo caso cadono i principali algoritmi per
reti fisse. Nel secondo caso si costruiscono dei path dal mittente al destinatario
solo quando viene richiesto per la spedizione di un messaggio. Esistono anche
algoritmi ibridi
•
Algoritmi con topologia non strutturata o strutturata in termini di
organizzazione logica del network. I protocolli di routing possono essere clusterbased o gerarchici, oppure flat.
•
Algoritmi con e senza informazioni sul posizionamento dei nodi.
•
Algoritmi con diversa metrica.
alto grado di stabilita' di associazione
minimizzazione dell'energia spesa complessivamente sul cammino
massimizzazione del tempo di vita della rete.
WP1
AODV (Ad-Hoc On Demand Distance Vector ):
Reattivo, ogni nodo tiene traccia solamente del primo hop, tramissione periodica
di un messaggio HELLO per riconoscere/confermare l'esistenza dei vicini
AODV e' stato implementato come modulo kernel 2.4.x di Linux con supporto
NETLINK ed e' stato sia testato su PC che su PDA (Zaurus e Ipaq).
LUNAR:
Reattivo, trasmissione periodica di un messaggio HELLO.
Implementazione a livello user-space per OS Linux con kernel 2.4.x con
supporto NETLINK, TUN/TAP e ARPD.
WP1
OLSR (Optimized Link State Route):
Come LUNAR anche OLSR lavora in user-space, table driven, reattivo.
Alcuni nodi vengono eletti Multipoint relay (MPR) da alcuni nodi vicini e
sono questi a scambiare informazioni riguardo la topologia del
network. Il nodo MPR annuncera' al network anche di essere punto di
riferimento per i nodi che l'hanno eletto tale.
OLSR e' stato implementato per OS Linux con kernel 2.4.x e per OS
Microsoft Windows 2000 e Pocket PC.
Tool di simulazione
ns2 e' un simulatore event-driven per network fissi e mobili sviluppato dal
CMU/Monarch group. Sono simulati separatamente i vari livelli, a
partire da quello fisico. A piu' alto livello si possono definire diversi
scenari, ciascuno con una propria topologia, densita' di distribuzione,
traffico di messaggi e dinamica di posizione.
Sono inclusi nel pakage di distribuzione anche 4 algoritmi di routing per
MANET fra i piu' noti: Destination Sequence Distance Vector,
Dynamic Source Routing, Temporally Ordered Routing Algorithm e
Ad-Hoc On-demand Distance Vector.
MobiEmu consente di simulare un mobile ad-hoc network environment
tramite un network fisso di macchine Linux. In pratica e' possibile
definire uno scenario mobile, usando lo stesso formato di ns2.
File Distribution and Caching in
MANET
Vittoria Gianuzzi
DISI Tech. Report 2003
arsenio.disi.unige.it/~gianuzzi/CNR/TecRap2003.pdf
Assumptions:
The user group is performing a highly collaborative work, and is willing
to collaborate in avoiding disconnection or network partitioning.
The network users manage a collection of data and programs that are
specific of the application and must be shared by all the components.
These data must be distributed among the mobile devices: when a host
needs a copy of it, the file must be transmitted over radio links that are
very expensive in battery consumption, thus data movements must be
limited.
Data replication can be used in order to avoid data loss in case of an
involuntary disconnection, even if such an event is considered to occur
rarely.
Components
Thus, the middleware data accessibility scheme must include the
following services:
– a cache maintenance service that manages file copies together with
a distributed data lookup service that maintains a local data
availability table for data location lookup,
– a search service that allow to locate a requested file, selecting the
most convenient copy in order to minimise the energy required for
its transmission.
The gossiping approach on which Gnutella relies, collecting information
from all nodes of the virtual routing, can be efficiently applied in order
to minimise the number of hops (thus of energy) required to download
the file.
Since each node in a MANET acts as a router, every request can be
captured and analysed. Information about data distribution and locality
are then recorded. Moreover, if a requested file, a secondary copy of
which is present in the cache, the query is stopped and an ack is sent to
the client.
The client selects and downloads the closest file copy.
Data can be filtered from the Data Link Layer to the Application Layer
using a sniffer, easily implementable in Linux.
Implementazione
Gossiping – sniffer messaggi in transito
Interfaccia con algoritmo di routing (WP5 UniPI)
Distribuzione dei dati nella cache:
utilizzo di cooperative caching. Simulazione dei vari metodi (direct client
cooperation, greedy forwarding, N-chance forwarding ecc.) WP4 per
middleware e WP4 per algoritmi.
Sistema centralizzato o distribuito.
A Local Decision Algorithm
for Maximum Lifetime
in Ad Hoc Networks
A. Clematis*, D. D’Agostino#, V. Gianuzzi#
* IMATI - CNR, Genova
# DISI, University of Genova
EUROPAR 2002
arsenio.disi.unige.it/~gianuzzi/CNR/Europar.pdf
Introduction
We propose a novel routing algorithm that allows an optimization for
ad-hoc networks in terms of system lifetime, in other words a
maximization of the time until the first mobile host drains-out its
battery.
There are different proposed routing algorithms, based on:
• adjustable/not adjustable transmission energy
• routing with/without information from external equipment (i.e. GPS)
• global or local topology information
• symmetrical system (peer hosts) / preferred points
• high/low mobility of network points
The Network Model
Radio transmission between two devices at distance d requires
power consumption proportional to dn
G(V,E) is the weighted graph of a network N of wireless devices:
w(e) = c | (u, v) | n
Reachability Graph: if Wmax is maximum power transmission is obtained by G
except the e for which w(e) >Wmax
A route between two nodes is a paths P = (N1, … Nn) over RG, the
cost of which is defined as:
C(P) = i w ( (ni-1,ni) )
MERG
The Minimum Energy Reachability Graph (MERG) is the graph obtained
from RG with all and only edges belonging to minimum energy paths.
Advantages of the algorithm:
• it use only local decisions
• the low cost of the edges ensure a minimal interference and
a consequent high throughput
Disadvantage
• some host may be part of an increasing number of routes
ME + Link Selection algorithm
It extends the MERG approximation and route discovery algorithm by adding a
Link Selection strategy during transmission operation to prevent early energy
consumption in critical nodes.
It requires that some values be piggybacked with messages.
We can distinguish two different phases:
• the set-up phase (routing discovery)
• the message transmission phase
Example
ME
ME + LS