Complessit` a della valutazione

L’implementazione di una politica che sfrutti una valutazione dinamica delle alternative di esecuzione, come descritto per il modello single-hop nella sezio- ne 3.2.3, richiede che il calcolo del costo della risoluzione per le composizioni

disponibili non sia computazionalmente eccessivo.

La modifica del valore di costo assegnato ad un arco pu`o essere effettuato in tempo costante e non `e necessario modificare l’ordine topologico dei nodi, ma deve essere richiesta la completa esecuzione dell’algoritmo per il calcolo dei cammini minimi, che ha complessit`a pari a O(|E|) dove |E| `e il numero di archi presenti nel grafo.

Generalmente per un DAG il numero di archi presenti `e dell’ordine O(|V |2_),

ma possiamo sfruttare una propriet`a dei tipi che caratterizzano i servizi del- le composizioni sequenziali per affermare che la complessit`a `e di un ordine minore: se un vertice v del grafo ha archi uscenti verso un insieme di vertici Vi, non ci possono essere archi tra gli elementi di Vi.

Ci`o `e dovuto al fatto che se un vertice v a cui `e associato un servizio la cui coppia di tipi `e (Iv, Ov), ogni vertice in Vi deve rappresentare un servizio che

ha come tipo di input Ov, ma dato che il tipo di output deve essere diverso

dal tipo di input, non potranno fornire il proprio output agli altri servizi dei vertici Vi.

Sfruttiamo questa propriet`a dicendo che se ki `e il grado in uscita di un

vertice vi del grafo e se chiamo n il numero di nodi del grafo, abbiamo: n X i=1 ki = (n − 1)(n − 2)/2 − n X i=1 (ki− 1)(ki− 2)/2

Cio`e, il numero di archi della rete pu`o essere al pi`u il massimo consentito da un grafo aciclico, meno gli archi mancanti tra i vertici che hanno uno stesso predecessore. Ora manipoliamo la formula per ricavare un espressione del numero di archi del grafo che dipenda da n.

2 n X i=1 ki = n2− 3n + 2 − n X i=1 (k2_i − 3ki+ 2) n2− 5n + 2 = n X i=1 (k2_i − ki) Sapendo che Pn

i=1ki corrisponde al numero di archi totale del grafo, notiamo

di K si rapporta con il grado dei vertici come Pn i=1k 2 i = ||K||22 e Pn i=1ki = ||K||1 Sostituendo, otteniamo: n2− 5n + 2 = ||K||2₂− ||K||1

Approssimiamo ||K||2₂ usando la propriet`a che lega norma 1 e 2: ||K||2 ≤

||K||1 ≤ ||K||2∗

√ n Otteniamo due condizioni:

• n2_{− 5n + 2 = ||K||}2

1/n − ||K||1

• n2_{− 5n + 2 = ||K||}2

1− ||K||1

Da cui si ricava il valore di ||K||1:

• ||K||1 = 1/2 + (n + √ n ∗√4n2_{− 19n + 8) = O(n ∗}√_n) • ||K||1 = 1/2 + (n + √ 4n2_{− 20n + 9) = O(n)}

Se consideriamo la maggiore, otteniamo |E| = O(n ∗√n) che diventa anche il valore della complessit`a dell’algoritmo per la ricerca dei cammini minimi.

Questo risultato ci indica come il tempo necessario per effettuare la va- lutazione delle alternative ha una complessit`a affrontabile da un dispositivo della rete, anche ripetendo la valutazione ad ogni tempo di contatto o inter- contatto.

Capitolo 6

L’ambiente di simulazione

Dopo aver descritto il sistema per le composizioni dei servizi e identificato il modello matematico che lo rappresenta, abbiamo validato tale modello tra- mite la simulazione di scenari diversi, che hanno consentito di osservare il comportamento del modello al variare dei parametri di configurazione.

In questo capitolo descriveremo l’ambiente di simulazione usato e le mo- difiche che `e stato necessario effettuare all’ambiente preesistente per definire tutte le funzionalit`a richieste per le simulazioni.

Nella prima sezione presenteremo l’ambiente di simulazione selezionato, le alternative di configurazione che offre e infine le sue limitazioni.

Nella seconda sezione descriveremo tutte le modifiche introdotte al si- mulatore e i componenti aggiuntivi che abbiamo realizzato per definire un ambiente di simulazione adatto ai nostri scopi.

6.1

TheOne: un simulatore per Reti Oppor-

tunistiche

L’ambiente di simulazione da noi usato per le simulazioni `e TheOne (Oppor- tunistic Network Environment) [5], un simulatore implementato per verificare modelli e algoritmi legati alle reti mobili, in particolar modo alle reti oppor- tunistiche. Per supportare la simulazione, TheOne combina al suo interno

un modello di mobilit`a, un livello di routing, uno strumento per la visualiz- zazione della simulazione e uno strumento per il report dei risultati.

La modellazione dei movimenti pu`o essere gestita sfruttando alcuni tool per la generazione di movimenti messi a disposizione dal simulatore o tramite tracce esterne importate all’interno del simulatore. La posizione di ogni nodo nella rete determina se due nodi sono connessi fra loro e si possono scambiare messaggi.

Il modulo di routing, cos`ı come nelle reti convenzionali, gestisce l’invio e la ricezione di messaggi da parte dei nodi.

Figura 6.1: TheOne: struttura generale

TheOne permette di visualizzare, tramite una semplice interfaccia grafica, il movimento dei nodi e le loro comunicazioni. Al termine della simulazione `e possibile generare uno o pi`u report per derivare considerazioni sulle propriet`a da analizzare.

La Figura 6.1 mostra come i vari componenti dell’ambiente sono collega- ti fra loro. All’interno di ogni componente `e possibile osservare le possibili alternative che consentono di personalizzare la simulazione.

Per rendere possibile la tracciatura dei movimenti dei nodi, TheOne usa un approccio cycle based per avanzare nella simulazione. Ad ogni ciclo, di durata costante, viene aggiornato lo stato di ognuno dei nodi, aggiornata la

loro posizione, le connessioni nel loro range di trasmissione e viene gestito l’invio/ricezione di eventuali messaggi.

I nodi presenti nella rete possono avere natura diversa, e questa caratte- ristica consente di simulare l’interazione fra device con hardware diverso e persone che si muovono con abitudini, mezzi e direzioni diverse fra loro.

La simulazione consente di definire gruppi di nodi che condividono carat- teristiche sulla loro mobilit`a e sulle proprie caratteristiche hardware. Ogni gruppo pu`o differire da un altro per velocit`a di spostamento, caratteristiche fisiche del dispositivo o modalit`a di routing, e questo consente di simulare, ad esempio, pedoni, automobilisti o persone che si spostano con i mezzi pub- blici.

TheOne `e facilmente configurabile e per modificare il comportamento dei nodi, ad esempio per introdurre un nuovo algoritmo di routing `e sufficiente creare una nuova classe che descrive le nuove operazioni e specificarne il nome nel file di configurazione.