Il nodo ni si muove nella rete ed entra in contatto con altri nodi memorizzandoli
all’interno della contact-history Ti, in particolare per ogni nodo incontrato nj viene
• Il tempo di inter-contatto tra il nodo ni e il nodo nj, ict(i, j), definito come il tempo
medio trascorso tra due contatti successivi. • L’ultima volta che ni ha incontrato nj, lt(i, j).
La tabella Ti viene aggiornata ogni volta che ni incontra un nuovo nodo.
L’algoritmo 1 mostra la fase reattiva di CORDIAL. Algoritmo 1 Fase reattiva
1: q = generateQuery(SIi) 2: if λ(q) 6= ∅ then 3: selezione e accesso 4: else 5: C = DetectCommunity(Nt i, CTi, τ ) 6: C0 = F S(C, q)
7: inoltrare q ai top-k nodi di C0 8: end if
CORDIAL non impone alcun vincolo nell’utilizzo di un particolare algoritmo di com-
munity detection piuttosto, CORDIAL pu`o essere configurato con un algoritmo distri-
buito esistente. Per esempio gli autori in [8] hanno configurato CORDIAL con DRAFT
[24]; mentre in questa tesi CORDIAL `e configurato con K-Clique [7]. Dopo che un
nodo ni ha rilevato la sua comunit`a Ci (linea 5 Algoritmo 1), il nodo ni calcola il
sottoinsieme dei nodi scelti per inoltrare la query, a tal proposito viene utilizzata una funzione F S(C, q) (linea 6 Algoritmo 1) che assegna ad ogni nodo nj ∈ C t.c. q /∈ P Qj
un punteggio, social centrality score, che indica la capacit`a del nodo a rispondere alla query q. Il punteggio ρ `e dato da:
ρ
j=
J (q, I
j)
1 + ict(i, j)
+
X
w ∈ Cj − Ci ict(i, w) > ict(j, w)J (q, I
w)
1 + ict(j, w)
(3.1)
• La prima parte dell’equazione indica il rapporto tra l’indice di similarit`a tra gli interessi della query e gli interessi di nj rispetto il tempo di inter-contatto tra ni e
nj. In questo modo si misura la capacit`a di nj a rispondere alla query in maniera
diretta.
• La seconda parte dell’equazione seleziona i nodi che appartengono solo a Cj e
che sono visitati pi`u spesso da nj che da ni. Definisce il rapporto tra l’indice di
tempo di inter-contatto tra nj e nw. In questo modo si misura la capacit`a di nj di
entrare in contatto con i nodi che possono rispondere alla query, quindi la capacit`a di nj di rispondere indirettamente.
Una volta calcolati i punteggi vengono selezionati i primi k nodi con punteggio pi`u alto (linea 7 Algoritmo 1).
L’algoritmo 2 mostra la fase proattiva di CORDIAL. Nella prima parte dell’algorit- Algoritmo 2 Fase proattiva
1: for all adv ∈ CHi do
2: Vt = {nj ∈ Nit|J(Ij, adv) > τ ∧ adv /∈ CHj}
3: Inoltrare adv a Vt
4: end for
5: for all adv ∈ F orwardingCachei do
6: if la destinazione finale di adv `e in contatto then
7: Inoltrare adv al destinatario finale
8: else 9: nk = T emporalF orwarder(adv) 10: Inoltrare adv a nk 11: end if 12: end for 13: for all q ∈ P Qi do 14: C = DetectCommunity(Nt i, CTi, τ ) 15: C0 = F S(C, q)
16: inoltrare q ai top-k nodi di C0
17: end for
mo (linee 1-4 Algoritmo 2) viene implementato lo scambio degli advertisement tra i
nodi: per ogni advertisement contenuto nella cache CHi del nodo ni viene costruito
l’insieme Vt ⊆ Nit composto da tutti quei nodi i cui interessi corrispondono con quelli
dell’advertisement e che non l’hanno ancora ricevuto. Una volta costruito questo insie- me, ni inoltra l’advertisement a tutti i suoi membri.
Dopo questa fase di scambio il nodo ni controlla se ci sono advertisement all’interno
della ForwardingCache che pu`o inoltrare al destinatario finale (linee 5-12 Algoritmo 2). Dato adv ∈ F orwardingCache il cui destinatario finale `e nj, se nj `e in contatto con
ni allora quest’ultimo lo inoltrer`a direttamente a nj, altrimenti ni esegue la Temporal-
Forwarder. Questa funzione seleziona il nodi nw ∈ Nit con il minor tempo rimanente
di inter-contatto tra nw e il destinatario finale, sar`a questo nodo a inoltrare l’adverti-
tra il nodo nw e il nodo nk definisce il tempo rimanente prima che si rincontrano ed `e:
r − ict = |ict(w, k) − [t − lt(w, k)]|
(3.2)
L’equazione 2.2 misura la differenza tra il tempo medio di inter-contatto tra nw e nk e
il tempo trascorso dall’ultima volta che si sono incontrati. Pi`u piccolo `e questo valore, pi`u velocemente nw incontrer`a nuovamente nk e potr`a consegnargli l’advertisement. Se
il risultato della TemporalForwarder `e un nodo nw 6= ni allora ni consegna l’advertise-
ment a nw.
L’ultima parte dell’algoritmo (linee 13-17 Algoritmo 2) si occupa di gestire le query al- l’interno di P Qiadottando la stessa strategia della fase reattiva (linee 5-7 Algoritmo 1).
L’algoritmo 3 mostra la gestione dei messaggi, query o advertisement, di CORDIAL e vengono distinti i seguenti casi:
• Il messaggio ricevuto da ni `e una query (linee 1-13 Algoritmo 3):
Viene inizialmente eseguita la funzione λ(q) per controllare se all’interno di CHi
`
e contenuto uno o pi`u advertisement corrispondenti; se questo non `e il caso me-
morizza la query in P Qi prendendosi cura di trovare una risposta a m (strategia
collaborativa di CORDIAL).
Viceversa, sia r il nodo che ha generato la query e che sta attendendo una risposta, se ni `e in contatto con r allora inoltra l’advertisement o gli advertisement corri-
spondenti, che verranno memorizzati nella forwarding cache di ni; altrimenti ni
seleziona il nodo nk con r − ict minore.
• Il messaggio ricevuto da ni `e un advertisement (linee 14-39 Algoritmo 3):
Inizialmente ni controlla se ci sono query generate da lui stesso in P Qi che possono
ricevere risposta da m, in caso affermativo questo insieme di query, D, pu`o essere rimosso da P Qi. Dopodich´e controlla se ci sono query generate da altri nodi in P QI
che possono ricevere risposta da m, insieme D0. Per ogni query in D0, niinoltrer`a m
al nodo che le ha generate, r, se sono in contatto, altrimenti ni selezioner`a il nodo
nk con r − ict minore a cui inoltrer`a m. Dopo questi controlli, ni controlla chi `e il
destinatario finale, dest di m : se dest 6= ni allora ni ha ricevuto un advertisement
diretto ad un altro nodo e si occuper`a di inoltrarlo a dest solo se sono in contatto, memorizzandolo nella forwarding cache di ni, altrimenti lo inoltrer`a al nodo con
r − ict minore (strategia collaborativa di CORDIAL).
L’ultima operazione `e memorizzare m in CHi se ni`e interessato ad accedere a quel
Algoritmo 3 Gestione dei messaggi
1: if m `e una query then
2: r `e chi ha generato q
3: if λ(q) 6= ∅ then
4: if r `e in contatto con ni then
5: Inoltra λ(q) a r 6: else 7: nk= T emporalF orwarder(r) 8: Inoltra λ(q) a nk 9: end if 10: else 11: memorizza q in P Qi 12: end if 13: end if 14: if m `e un advertisement then
15: dst `e il destinatario finale di adv
16: D = {q ∈ P Qi|requester(q) = ni∧ J(q, adv) > τ }
17: Rimuovi D da P Qi
18: D0 = {q ∈ P Qi|requester(q) 6= ni∧ J(q, adv) > τ }
19: for all q ∈ D0 do
20: r `e chi ha generato la query
21: if r `e in contatto then 22: Inoltra m a r 23: else 24: nk= T emporalF orwarder(r) 25: Inoltra m a nk 26: end if 27: end for 28: if dst 6= ni then 29: if dst `e in contatto then 30: Inoltra m a dest 31: else 32: nk= T emporalF orwarder(dst) 33: Inoltra m a nk 34: end if 35: end if 36: if J (m, Ii) > τ then 37: aggiungi m alla CHi 38: end if 39: end if
CAPITOLO
4
Configurazione della sperimentazione
Questo capitolo descrive la configurazione dell’ambiente di sperimentazione utilizzato per studiare e valutare l’efficacia e le performance di CORDIAL [8] e di un altro algorit- mo di service discovery basato sulla tecnica del flooding (Flooding). Questo algoritmo, descritto nel paragrafo 4.6, sfrutta unicamente la mobilit`a dei nodi per la progettazione delle fasi principali di pubblicazione e ricerca dei servizi.
Lo studio delle performance dei due algoritmi di service discovery viene svolto variando diverse componenti che permettono di determinare il comportamento dei nodi della rete e la strategia di diffusione dei messaggi. Il comportamento dei nodi viene determinato mediante l’utilizzo di due dataset di tracce di co-locazione reali ottenute analizzando la mobilit`a di due diversi campioni di individui sia in un ambiente interno che in un ambiente esterno, Cambridge [6], e MDC Nokia [14, 15], descritti nel paragrafo 4.2. Inoltre vi sono altre tre componenti che influenzano il comportamento dei nodi nel processo di service discovery, descritte nel paragrafo 4.3: (i) la generazione dei servizi, (ii) la generazione delle query attraverso la distribuzione di Poisson e (ii) la distribu- zione degli interessi ai nodi attraverso la distribuzione di Zipf.
Le strategie di diffusione dei messaggi, descritte nel paragrafo 4.4, sono: BubbleRap [16], Epidemic [17], Prophet [19] e Spray&Wait [18]. A seconda dell’algoritmo di service discovery analizzato, tali strategie di routing verranno utilizzate o nella loro versione originale, oppure in una versiore rivisitata in cui vi `e adattato un algoritmo di com- munity detection K-Clique [7] (nativo per BubbleRap). CORDIAL sfrutta la struttura delle comunit`a per rendere la fase di ricerca dei servizi pi`u efficiente, per esempio un individuo che ricerca un servizio pu`o propagare la richiesta prima tra i membri del- la propria comunit`a data la probabilit`a pi`u alta di trovare una risposta. Alla luce di ci`o si adatta l’algoritmo K-Clique, descritto nel paragrafo 4.5, a Epidemic, Prophet e
Spray&Wait. Mentre Flooding, sfruttando unicamente i contatti tra i nodi, utilizza le strategie di routing nella loro versione originale.
Lo studio e la valutazione dell’efficacia e delle performance degli algoritmi di service discovery avviene attraverso un simulatore per le reti opportunistiche, TheONE [5], descritto nel paragrafo 4.1. Questo strumento permette di simulare le fasi di ricerca e pubblicazione dei servizi di CORDIAL e Flooding, la mobilit`a dei nodi, la diffusio-
ne dei messaggi ed il rilevamento delle comunit`a. Attraverso TheONE si analizzano i
risultati generati in fase di sperimentazione sotto diversi aspetti, in modo da esegui- re un’analisi approfondita delle performance degli algoritmi (capitolo 5). Tali risultati vengono descritti utilizzando delle metriche che fanno emergere determinate caratteri- stiche importanti per l’analisi. Il paragrafo 4.7 mostra le metriche per valutare le tracce di co-locazione, gli algoritmi di routing e gli algoritmi di service discovery.
La Figura 4.1 rappresenta l’impostazione dell’ambiente di sperimentazione, mostran- do nel dettaglio i collegamenti tra tutte le componenti necessarie per progettare gli esperimenti. Infine i paragrafi 4.8 e 4.9 mostrano nel dettaglio i parametri necessari ad impostare la sperimentazione mediante TheONE e l’hardware su cui vengono effettuati gli esperimenti.
The One
Algoritmi di service discovery Algoritmo di rilevamento delle comunitàRisultati
Algoritmi di routing Generazione delle query Tracce di co-locazione Generazionedei servizi
Distribuzione degli interessi BubbleRap Epidemic Spray&Wait ProphetK-Clique CORDIAL Flooding
Cambridge MDC Nokia Distribuzione di Poisson Distribuzione di Zipf Metriche
4.1
Strumento di simulazione
The ONE (Opportunistic Network Enviroment) [5] `e un simulatore per reti opportu-
nistiche specificatamente progettato per valutare i protocolli di routing e i protocolli applicativi. Fornisce agli utenti una piattaforma open-source basata su Java in cui `e possibile implementare i propri protocolli e creare degli scenari basati su diversi mo- delli di movimento, sintetici o reali. Il fattore importante di questo simulatore `e che i protocolli vengono valutati sotto diverse impostazioni che l’utente pu`o modificare in modo da adattare la simulazione il pi`u possibile allo scenario del protocollo applicativo che intende implementare. Gli scenari di simulazione sono costruiti da gruppi di nodi in cui ogni gruppo condivide al suo interno delle funzionalit`a particolari che `e possibile modellare: la dimensione del buffer dei messaggi, l’interfaccia radio, la capacit`a di me- moria e l’energia disponibile. Inoltre dispongono di funzionalit`a pi`u complesse come il movimento e il routing dei messaggi che sono configurati attraverso moduli specializzati che implementano un comportamento particolare.
routing
visualization and results
simulation
engine connectivitydata
external DTN routing sim internal routing logic routing data visualization,
reports, etc. post processors(e.g. graphviz)
graphs, charts, etc.
event generators
External events file
Message event generator
etc. movement models Random waypoint External trace Map-based movement etc.
Figura 4.2: Struttura del simulatore [5]
La figura Figura 4.2 mostra le componenti principali che compongono la struttura del simulatore e le possibili alternative che consentono di personalizzare la simulazione. Le componenti di ONE permettono di:
• Simulare il modo in cui si muovono i nodi e di conseguenza simulare i contatti. I modelli di mobilit`a si basano o su tracce di co-locazione (generate da uno strumento
esterno o raccolte da movimenti reali) importate al suo interno oppure mediante la generazione di movimenti sintetici, entrambe ottimi soluzioni se si vuole riprodurre uno scenario in cui le persone si muovono secondo determinati criteri. Esempi di modello sintetico sono: (i) Map-Based Model in cui i nodi vengono collocati in maniera random all’interno di una mappa e si muovono lungo i percorsi avanti e indietro; e (ii) Random Waypoint in cui i nodi si muovono liberamente nello spazio considerato, in particolare ad ogni nodo inizialmente viene assegnata una posizione casuale e successivamente ognuno di essi sceglie, sempre in maniera casuale, una destinazione e una volta raggiunta ne sceglie un’altra e cosi via.
• Generare eventi esterni, per esempio generare la creazione dei messaggi. Gli eventi possono essere generati attraverso: (1) un generatore di eventi, ossia una classe Java che crea in maniera dinamica gli eventi, e (2) l’inclusione di tracce esterne, ossia file di testo in cui vengono elencati una serie di eventi come la creazione dei messaggi. E’ possibile usare pi`u generatori di eventi in contemporanea.
• Simulare l’invio e la ricezione dei messaggi nella rete utilizzando diverse strategie di routing. Alcune strategie sono gi`a incluse all’interno del simulatore, come quel- le a copia multipla :Prophet, Spray&Wait o Epidemic, o quelle a copia singola, come DirectDelivery (DD) [25] o FirstContact (FC) [26]. E’ comunque possibile introdurre nuove strategie di routing.
• Visualizzare, tramite un’interfaccia grafica, GUI, i movimenti dei nodi e le loro comunicazioni in tempo reale, Figura 4.3. All’interno dell’interfaccia `e possibile vi- sualizzare la localizzazione dei nodo, la connessione tra i nodi, il numero di messaggi trasportati e altri eventi.
Al termine delle simulazioni vengono raccolti i risultati tramite dei report generati in fase di esecuzione, per esempio report che riguardano le statistiche sui messaggi oppure riguardo i contatti tra i nodi. I report ricevono degli eventi dal simulatore e generano dei risultati che possono essere successivamente elaborati tramite degli strumenti esterni,
per esempio tramite Matlab `e possibile importare i report e produrre dei grafici di
output.