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/WP1Sono 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 piccolo-medio 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 ad-hoc.

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 cluster-based 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 GianuzziDISI 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 Algorithmfor 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, thecost of which is defined as:

C(P) = i w ( (ni-1,ni) )

MERG

The Minimum Energy Reachability Graph (MERG) is the graph obtainedfrom 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