Ricerca di servizi in Reti Mobili Sociali: Studio e valutazione tramite un simulatore per reti opportunistiche

(1)

Facolt`

a di Scienze, Matematiche, Fisiche e Naturali

CORSO DI LAUREA MAGISTRALE IN INFORMATICA

TESI DI LAUREA

Ricerca di servizi in Reti Mobili Sociali:

Studio e valutazione tramite un simulatore

per reti opportunistiche

RELATORI:

Prof. Stefano Chessa

Dott. Michele Girolami

CANDIDATA:

Stela Bici

ANNO ACCADEMICO

2015-2016

(2)

(3)

Indice

1 Introduzione 1 1.1 Obiettivi . . . 3 1.2 Metodologia e risultati . . . 3 1.3 Organizzazione . . . 6 2 Stato dell’arte 8 2.1 Mobile Social Networks . . . 8

2.1.1 Nodi di una MSN . . . 10

2.1.2 Mobilit`a degli utenti e relazioni sociali . . . 11

2.1.3 Neighborhood . . . 11

2.1.4 Comunit`a all’interno di una MSN . . . 13

2.1.4.1 Strategie di community detection distribuite . . . 14

2.1.5 Instradamento e diffusione delle informazioni nelle MSN . . . . 14

2.1.5.1 Strategie di Routing . . . 16

2.1.5.2 Strategie di Data Dissemination . . . 18

2.2 Service Discovery . . . 19

2.2.1 Il processo di service discovery . . . 20

2.2.1.1 Pubblicazione e richiesta dei servizi . . . 21

2.2.1.2 Selezione dei servizi . . . 25

2.2.1.3 Accesso dei servizi . . . 26

2.2.2 Architetture di service discovery . . . 26

3 CORDIAL: COllaborative seRvice DIscovery ALgorithm 30 3.1 Concetti preliminari . . . 31

3.2 Fasi di CORDIAL . . . 33

3.2.1 Fase reattiva . . . 35

3.2.2 Fase proattiva . . . 35

(4)

3.3 L’algoritmo CORDIAL . . . 37

4 Configurazione della sperimentazione 42 4.1 Strumento di simulazione . . . 44

4.2 Tracce di co-locazione . . . 46

4.3 Comportamento dei nodi . . . 48

4.4 Algoritmi di Routing . . . 49

4.5 Algoritmo di community detection . . . 56

4.6 Algoritmi di Service Discovery . . . 57

4.7 Metriche di interesse . . . 60

4.7.1 Analisi delle tracce di co-locazione . . . 60

4.7.2 Valutazione degli algoritmi di routing . . . 61

4.7.3 Valutazione degli algoritmi di service discovery . . . 62

4.8 Parametri di Simulazione . . . 64

4.9 Hardware di simulazione . . . 68

5 Risultati sperimentali 69 5.1 Analisi delle tracce . . . 69

5.2 Analisi degli algoritmi di routing . . . 75

5.3 Analisi degli algoritmi di Service Discovery . . . 80

5.3.1 Discussione . . . 97

5.4 Analisi dell’algoritmo K-Clique . . . 99

5.4.1 Performance ottenute variando K . . . 100

5.4.2 Performance ottenute variando la Familiar Threshold . . . 104

6 Conclusioni e sviluppi futuri 108

(5)

Elenco delle figure

1.1 Fasi della sperimentazione . . . 5

2.1 Una MSN come intersezione tra la rete mobile e la rete sociale [1] . . . 9

2.2 Architettura di una MSN . . . 10

2.3 Numero di contatti Vs durata dei contatti [2] . . . 12

2.4 Collegamento tra comunit`a diverse . . . 13

2.5 Routing del messaggio m dal nodo i al nodo d . . . 15

2.6 Diffusione del messaggio m . . . 16

2.7 Categorie di routing sulla base delle comunit`a . . . 17

2.8 Categorie di routing sulla base delle copie dei messaggi . . . 18

2.9 Classificazione dei servizi offerti all’interno di una MSN [3] . . . 20

2.10 Processo di Service discovery [3] . . . 21

2.11 Strategie di selezione [3] . . . 25

2.12 Architettura basata sulla directory . . . 28

2.13 Architettura senza la directory . . . 29

3.1 Esempio della formazione di comunit`a a seguito della mobilit`a di un individuo [4] . . . 31

3.2 Consegna di una risposta tramite un meccanismo diretto . . . 34

3.3 Consegna di una risposta tramite un meccanismo indiretto . . . 35

3.4 Fase reattiva di CORDIAL . . . 36

3.5 Fase proattiva di CORDIAL . . . 36

3.6 Gestione dei messaggi in CORDIAL . . . 37

4.1 Componenti coinvolte nella tesi . . . 43

4.2 Struttura del simulatore [5] . . . 44

4.3 Interfaccia GUI di ONE . . . 45

4.4 Esempio di traccia di co-locazione presa dal dataset Cambridge . . . . 46

(6)

4.6 Regione del lago di Geneva, Svizzera . . . 48

4.7 Diffusione delle informazioni basandosi sul ranking dei nodi . . . 51

4.8 Scambio delle summery vector . . . 52

4.9 Scambio dei messaggi . . . 52

4.10 Spray&Wait binario . . . 53

4.11 Sequenza delle interazioni tra due nodi che usano Prophet . . . 55

4.12 Esempio di comunit`a rilevate al variare di K . . . 56

4.13 Criteri di ammissione per K-Clique [7] . . . 57

4.14 Fase reattiva di Flooding . . . 58

4.15 Fase proattiva di Flooding . . . 59

4.16 Gestione dei messaggi in Flooding . . . 59

4.17 Durata dei contatti e dei intercontatti tra due nodi . . . 61

5.1 Cardinalit`a media delle comunit`a in Cambridge . . . 70

5.2 Cardinalit`a media delle comunit`a in MDC Nokia . . . 71

5.3 Numero di contatti per ora in Cambridge . . . 72

5.4 Numero di contatti per ora in MDC Nokia . . . 73

5.5 Inter Contact Time in MDC Nokia e Cambridge . . . 74

5.6 Contact Time in MDC Nokia e Cambridge . . . 75

5.7 Message Delivery usando Cambridge . . . 77

5.8 Message Delivery usando MDC Nokia . . . 78

5.9 Message delay usando Cambridge . . . 79

5.10 Message delay usando MDC Nokia . . . 80

5.11 Accuracy Flooding usando Cambridge . . . 81

5.12 Accuracy Flooding usando Nokia . . . 83

5.13 Proactivity CORDIAL usando Cambridge . . . 84

5.14 Proactivity CORDIAL usando MDC Nokia . . . 85

5.15 Proactivity Flooding usando Cambridge . . . 86

5.16 Proactivity Flooding usando Nokia . . . 87

5.17 Query Response Time CORDIAL usando Cambridge . . . 88

5.18 Query Response Time CORDIAL usando MDC Nokia . . . 89

5.19 Query Response Time Flooding usando Cambridge . . . 90

5.20 Query Response Time Flooding usando MDC Nokia . . . 91

5.21 Dimensione media della service cache CORDIAL usando Cambridge . . 93

5.22 Dimensione media della service cache CORDIAL usando MDC Nokia . 93 5.23 Dimensione media della service cache Flooding usando Cambridge . . 95

(7)

5.25 Dimensione media della forwarding cache usando Cambridge . . . 96

5.26 Dimensione media della forwarding cache usando MDC Nokia . . . 97

5.27 Media della cardinalit`a delle comunit`a usando Cambridge . . . 101

5.28 Media della cardinalit`a delle comunit`a usando MDC Nokia . . . 101

5.29 Media della proactivity al variare di K usando Cambridge . . . 102

5.30 Media della query response time al variare di K usando Cambridge . . 102

5.31 Media della proactivity al variare di K usando MDC Nokia . . . 103

5.32 Media della query response time al variare di K usando MDC Nokia . 103 5.33 Media della cardinalit`a delle comunit`a usando Cambridge e MDC Nokia 104 5.34 Media della proactivity al variare di Tth usando Cambridge . . . 105

5.35 Media della query response time al variare di Tth usando Cambridge . 106 5.36 Media della proactivity al variare di Tth usando MDC Nokia . . . 106

(8)

Elenco delle tabelle

4.1 Numero di esecuzioni in CORDIAL per la confidenza statistica . . . 65

4.2 Numero di esecuzioni in Flooding per la confidenza statistica . . . 65

5.1 Indice di correlazione di Pearson CORDIAL . . . 92

5.2 Indice di correlazione di Pearson Flooding . . . 94

5.3 Valori ottimali di K per Cambridge e MDC Nokia . . . 102

(9)

CAPITOLO

1

Introduzione

Nell’ultimo decennio una rapida crescita dei dispositivi mobili ha permesso alle perso-ne di essere costantemente conperso-nesse a comunicazioni wireless e alle tecnologie di rete cambiando il modo in cui interagiscono con i loro simili. Allo stesso tempo continua-no a diffondersi sempre più le reti sociali Online, OSN (Online Social Network) come Facebook, Twitter o LinkedIn, che forniscono un sistema virtuale di condivisione dei contenuti ovunque nel mondo, in qualsiasi momento e con chiunque (conoscenti e non). Il legame sempre più stretto che si è creato tra questi due mondi ci ha portato alle reti mobili sociali (MSN: Mobile Social Network), basate su concetti derivanti sia dalle OSN che dalle reti opportunistiche [8].

Una MSN `e una rete formata da dispositivi mobili (smartphone, tablet, smartwatch

e bracciali sensorizzati) che attraverso le interfacce di comunicazione (Wireless, Blue-tooth, GPRS, 3G e LTE) e i sensori di cui sono dotati (accelerometro, giroscopio e GPS), permettono agli utenti che li trasportano o li indossano di creare opportunit`a di comunicazione, in particolare di accedere, condividere e distribuire dati sfruttando le interazioni sociali e la loro mobilit`a.

L’architettura di rete richiesta da una MSN si differenzia da quella delle OSN, infatti, quest’ultima si affida a server centralizzati sempre on-line e sostenuti da infrastruttu-re di infrastruttu-rete ultra veloci fissi o mobili (base station, gateway o access point). Gli utenti condividono i propri dati collegandosi a questi server attraverso collegamenti WiFi o broadband come LTE.

Le MSN possono essere costruite in modo distribuito. In questo caso non si assume l’esistenza di alcuna infrastruttura di rete stabile che possa garantire la connettivit`a tra i dispositivi, di conseguenza la comunicazione avviene direttamente fra i nodi in modo opportunistico. Il termine opportunistico definisce un metodo di comunicazione

(10)

per le reti caratterizzate da connettivit`a intermittente in cui due utenti possono comu-nicare solo se si trovano nelle vicinanze in modo da stabilire una connessione mediante le interfacce di cui sono dotati i dispositivi che trasportano. Una MSN `e caratterizzata da due aspetti chiave:

• Comportamento umano: Le interazioni sociali che si creano tra gli utenti nella rete sono strettamente correlate alla mobilità degli utenti stessi. Quest’ultimo è carat-terizzato a sua volta da quattro aspetti chiave [3], in particolare gli individui: (i) svolgono attività comuni, (ii) visitano un numero limitato di luoghi, (iii) viaggiano prevalentemente su percorsi brevi anziché su percorsi più lunghi e (iv) tendono a incontrare frequentemente e per lunghi periodi altri individui con un profilo simile (i loro interessi coincidono).

Lo studio delle interazioni sociali `e un campo di ricerca di notevole importanza, esso caratterizza il modo in cui le persone si muovono determinando di conseguenza

la topologia della MSN e influenzando fortemente le opportunit`a di

comunicazio-ne che si creano. A tal proposito il pi`u del lavoro in letteratura si focalizza sullo studio delle caratteristiche sociali degli individui, in particolare dei legami sociali. Granovetter fu il primo a quantificare la forza dei legami sociali [9]:

“La forza di un legame è una combinazione (probabilmente lineare) della quantità di tempo, l’intensità emotiva, l’intimità (confidenza reciproca) e i servizi reciproci che caratterizzano il legame.”

• Computazione orientata ai servizi : I dispositivi della rete sono caratterizzati da una grande disponibilit`a di risorse (sia hardware che software) che vengono offerte agli utenti in termini di “servizi ” (riguardanti contenuti multimediali, messaggi, funzionalit`a della rete).

Il problema di ricercare e accedere ai servizi offerti all’interno di una MSN distri-buita viene chiamato Service Discovery e l’obiettivo principale `e quello di permette ai dispositivi di pubblicizzare i propri servizi e di fornire ad altri nodi i servizi di cui necessitano e a cui vogliono accedere il pi`u velocemente possibile senza affidarsi ad alcuna infrastruttura di rete che assicuri una connessione permanente. Negli anni sono stati proposti molti protocolli di service discovery, come Jini [10], UPnP [11], SLP [12], tutti riguardanti la ricerca dei servizi nelle reti dotate di infrastrutture basate su IP oppure protocolli per le reti mobili come quelle ad-hoc [13].

Nessu-na di queste soluzioni `e adatta alla natura di una MSN in quanto non tengono

(11)

considerata la tendenza di visitare in continuazione i luoghi familiari, o di formare comunit`a composte da persone che condividono interessi simili.

1.1 Obiettivi

Il presente lavoro di tesi ha come obiettivo principale quello di studiare per via spe-rimentale le performance di alcune strategie di service discovery su MSN, le cui fasi cruciali sono la richiesta e la pubblicazione dei servizi. L’obiettivo comune di entrambe le fasi `e quello di fornire ai nodi i servizi richiesti o necessari il pi`u velocemente possibile tenendo conto del modo in cui si muovono all’interno della rete e al contempo cercare di limitare il consumo delle risorse dovute alle trasmissioni.

Dunque si vuole innanzitutto analizzare lo scenario della rete, in particolare le modalità di creazione dei legami sociali e quindi le opportunità di comunicazione dei dispositi-vi mobili, a partire dall’analisi approfondita della natura dei modispositi-vimenti umani. A tal proposito verranno utilizzate due tracce reali di socialità tra utenti della MSN.

Successivamente si vuole analizzare il comportamento di varie strategie di routing dei messaggi al variare della traccia utilizzata.

Le informazioni ricavate da queste prime due analisi servono a valutare l’efficacia degli algoritmi di service discovery variando la traccia e la strategia di diffusione dei servizi in modo da soddisfare gli obbiettivi precedentemente introdotti della fase di ricerca e di pubblicazione.

1.2 Metodologia e risultati

Il presente lavoro di tesi parte dallo studio di un protocollo di service discovery directory-less su MSN, CORDIAL [8] (capitolo 3), evoluzione di una precedente versione proposta dagli stessi autori, SIDEMAN [4]. SIDEMAN è una strategia progettata per le reti mo-bili sociali distribuite che sfrutta le caratteristiche comportamentali degli utenti come: i movimenti, i legami sociali e la condivisione di interessi con alcuni membri della pro-pria comunità. CORDIAL in aggiunta sfrutta la cooperazione dei nodi più popolari in modo da migliorare le performance, in particolare aumentare l’opportunità di trovare il servizio desiderato all’interno della rete.

Lo studio delle performance di CORDIAL viene svolto variando diverse componenti che permettono di determinare il comportamento dei nodi della rete e la strategia di diffusione dei messaggi. Per determinate il comportamento dei nodi vengono utilizzati due dataset di socialit`a tra utenti di MSN disponibili in letteratura: Cambridge [6],

(12)

e MDC Nokia [14, 15]. Tali dataset contengono delle tracce di co-locazione ottenute analizzando la mobilità delle persone in due diverse aree: Cambridge è stata ottenuta all’interno di un’area molto limitata, l’università di Cambridge, e analizza la mobilità

di un campione omogeneo (36 studenti), mentre MDC Nokia `e stata ottenuta dal Nokia

research center all’interno di una vasta regione di circa 2000 km2 _{in Svizzera e analizza}

la mobilità di un campione eterogeneo (circa 200 volontari di differente sesso e età). Le tracce di co-locazione descrivono in particolare i contatti che avvengono tra le persone rilevati grazie alle interfacce a corto raggio dei dispositivi da loro trasportati. Questa analisi propedeutica è fondamentale in quanto permette di comprendere la complessità dello scenario e di conseguenza permette di valutare il comportamento e l’efficacia del-l’algoritmo di service discovery considerato.

Le strategie di diffusione dei messaggi utilizzati sono: BubbleRap [16], Epidemic [17], Spray&Wait [18] e Prophet [19]. Tali strategie differenziano nell’utilizzo o meno di un algoritmo che permette di rilevare le comunità, community detection. BubbleRap è un algoritmo di routing basato sulle comunità, sfrutta infatti l’algoritmo di community detection K-Clique [7]; mentre gli altri sono algoritmi di routing indipendenti dalle comunità.

Una caratteristica fondamentale per CORDIAL `e che sfrutta la struttura della

comu-nità per rendere la fase di ricerca dei servizi più efficiente, infatti come già discusso le persone che tendenzialmente condividono interessi simili tendono a incontrarsi di frequente e per lunghi periodi. A tal proposito un individuo che ricerca un servizio può propagare la richiesta prima tra i membri della propria comunità data la probabilità più alta di trovare una risposta. Alla luce di ciò è utile adattare l’algoritmo di community detection K-Clique a Epidemic, Spray&Wait e Prophet per permettere di analizzarle insieme a CORDIAL.

Parallelamente allo studio di CORDIAL `e stato condotto anche uno studio su un altro

algoritmo di service discovery basato sulla tecnica del “flooding”, banalmente denomi-nato Flooding (capitolo 4.6). Questo algoritmo sfruttata solo la mobilità dei nodi per implementare le fasi di ricerca e pubblicazione dei servizi. Alla luce di ciò le strategie di routing vengono combinate nella loro versione originale, non essendo necessaria la rilevazione delle comunità.

Gli studi sperimentali vengono effettuati attraverso uno strumento di simulazione per reti opportunistiche TheONE [5] che permette di valutare l’efficacia e le performan-ce delle strategie di serviperforman-ce discovery proposte. TheONE simula le fasi di CORDIAL e Flooding al variare di alcune componenti: algoritmi di routing, algoritmo di com-munity detection, traccia di co-locazione e il comportamento dei nodi (distribuzione

(13)

degli interessi, generazione delle query e generazione dei servizi (capitolo 4.3). La Figu-ra 1.1 Figu-rappresenta le componenti necessarie per effettuare gli esperimenti utilizzando il simulatore.

TheONE

Algoritmi di

service

discovery

Algoritmo di rilevamento delle comunità

Risultati

Algoritmi

di routing

Generazione

delle query

Tracce di co-locazione

Generazione

dei servizi

degli interessi

Distribuzione

Figura 1.1: Fasi della sperimentazione

Attraverso TheONE si analizzano i risultati generati in fase di sperimentazione sotto diversi aspetti, in modo da eseguire un’analisi approfondita delle performance degli algoritmi di service discovery. L’impostazione effettuata `e la seguente:

• Studio di due algoritmi di service discovery, CORDIAL e Flooding: Tale studio viene effettuato al fine di comprendere nel dettaglio il comportamento della fase di ricerca e pubblicazione dei servizi. Le performance di tali fasi sono determinate dalle strategie adottate; in particolare CORDIAL sfrutta le caratteristiche sociali dei nodi (la periodicità nei movimenti, l’appartenenza a un certo numero di comu-nità e la tendenza di incontrare frequentemente e per lunghi periodi i membri delle proprie comunità con cui condividono tendenzialmente gli interessi) per implemen-tare la ricerca e la pubblicazione dei servizi. Flooding, invece sfrutta unicamente la mobilità dei nodi.

• Analisi di due scenari di mobilit`a effettuata analizzando le tracce di co-locazione: Tale analisi permette di evidenziare le caratteristiche sociali e temporali dei nodi

(14)

che influenzano le opportunit`a di interazione e di conseguenza influenzano le perfor-mance dell’algoritmo che ne fa uso. Dall’analisi approfondita svolta nel capitolo 5 emerge che una traccia caratterizzata da molte interazione fra i nodi (con una con-seguente probabilit`a maggiore di comunicazione) permette di ottenere performance migliori, rispetto ad una traccia caratterizzata da poche interazioni.

• Analisi degli algoritmi di routing variando la traccia di co-locazione: Tale analisi viene effettuata al fine di comprendere il comportamento degli algoritmi di routing nel consegnare i messaggi creati a destinazione producendo un ritardo minimo. Da ci`o si evidenzia la forte influenza della mobilit`a dei nodi nelle performance di questi algoritmi.

• Analisi degli algoritmi di service discovery variando sia la traccia di co-locazione che la strategia di routing: Tale analisi `e fondamentale per gli obiettivi di que-sta tesi, si vuole infatti evidenziare come il comportamento dei nodi e la scelta della strategia di routing da utilizzare influenzano le opportunit`a di contatto e di conseguenza le performance della fase di ricerca e pubblicazione. Dall’analisi approfondita svolta nel capitolo 5 emerge che:

– la densit`a dei contatti tra i nodi influenza fortemente le performance di en-trambi gli algoritmi di service discovery,

– la scelta dell’algoritmo di routing `e significativa per Flooding ed `e invece ininfluente per CORDIAL.

• Analisi degli algoritmi di community detection: Tale analisi ha l’obiettivo di in-dividuare una configurazione dei parametri di K-Clique tale da ottimizzare le prestazioni di CORDIAL.

1.3 Organizzazione

La struttura della tesi `e la seguente:

Il capitolo 2 presenta una panoramica riguardante tutto il contesto di questa tesi: ini-zialmente si discuterà delle caratteristiche e delle principali problematiche delle reti mobili sociali distribuite, in particolare si mostreranno alcune strategie per il problema dell’instradamento e della diffusione dei messaggi nella rete, infine si presenterà nel dettaglio la problematica principale di questo ambiente sociale e orientato ai servizi: la possibilità di condividere le risorse (hardware e software) dei dispositivi mobili traspor-tati dagli utenti. Questo problema è comunemente conosciuto come “ricerca di servizi”

(15)

o Service discovery, ampiamente studiato negli anni per le reti dotate di infrastrutture basate su IP e per le reti Wireless.

Il capitolo 3 analizza nel dettaglio un protocollo di service discovery che sfrutta la

mobilit`a e le relazioni sociali degli utenti: CORDIAL. Questo algoritmo, insieme ad

un altro basato sulla tecnica del flooding, saranno alla base dello studio sperimentale effettuato in questa tesi.

Il capitolo 4 descrive tutte le configurazioni dell’ambiente di sperimentazione utilizzati per valutare le prestazioni di CORDIAL, (i) l’ambiente di simulazione, (ii) le tracce di co-locazione, (iii) le soluzioni adottate per generare, distribuire e richiedere i servizi nella rete, (iv) le soluzioni adottate per i problemi di instradamento e diffusione dati, (v) la soluzione per rilevare le comunit`a, (vi) le metriche usate per valutare i nostri esperimenti, (vii) l’hardware di simulazione e (viii) i parametri di simulazione.

Il capitolo 5 mostra i risultati degli esperimenti per analizzare, mediante metriche di interesse, le performance ottenute dalle soluzioni proposte descritte nel capitolo 4.

(16)

CAPITOLO

2

Stato dell’arte

Questo capitolo mostra le MSN nel dettaglio evidenziando le principali tipologie, le caratteristiche e le problematiche che da molti anni si cerca di studiare. Infine analizza il paradigma del Service Discovery illustrando le strategie adottate nello scenario delle MSN.

2.1 Mobile Social Networks

Una MSN `e una reti formata da dispositivi mobili, come smartphone, tablet,

smart-watch e bracciali sensorizzati. Tali dispositivi, tipicamente indossati o trasportati da persone, si muovono nella rete partecipando alla distribuzione dei contenuti anzich´e essere semplicemente dei destinatari di informazioni per le infrastrutture di telecomu-nicazione [4]. Queste reti sono state introdotte combinando concetti derivanti da due diverse discipline (Figura 2.1) [1]:

• Social network definita come una rete di entità collegate tra loro attraverso una o più interdipendenze: contatti fisici, partecipazioni di gruppo, legami sociali e condivisione di interessi. La forma dei primi social network era quella delle chat e dei forum, con l’evoluzione di internet e delle reti centralizzate, il concetto social network è stato utilizzato nel contesto dell’informatica e della comunicazione per fornire un sistema efficiente di scambio e la condivisione dei dati studiando la mobilità, i comportamento e i rapporti che si instaurano tra le entità che ne fanno parte.

• Mobile network definita come una rete di telecomunicazione che permette a pi`u sog-getti di comunicare a distanza, in particolare di trasmettere e ricevere informazioni di qualsiasi tipo, mediante i servizi offerti dai dispositivi elettronici.

(17)

Le MSN rappresentano un nuovo paradigma di ricerca in cui grazie alla onnipresenza dei dispositivi mobili, gli utenti si spostano negli spazi reali e interagiscono tra loro attraverso lo scambio di contenuti. Una MSN è pertanto una rete dinamica, la mobilità dei nodi è fortemente correlata con la mobilità delle persone che li trasportano e alle relazione sociale che creano, di conseguenza i dispositivi trasportati dagli utenti sono in grado di interagire solo per periodi brevi e intermittenti.

Possiamo quindi precisare che le reti mobili sociali sono strettamente associate alle reti opportunistiche, ossia reti incentrate sul comportamento umano che “seguono” in maniera opportunistica il modo in cui gli utenti entrano in contatto e sfruttano le relazioni sociali che vi si creano per permettere di stabilire una comunicazione efficiente tra i nodi.

MSN

Mobile

Networks NetworksSocial

GPS Wi-Fi Bluetooth Misura di centralità Legami sociali Servizi dei social network

Figura 2.1: Una MSN come intersezione tra la rete mobile e la rete sociale [1]

A secondo della modalit`a con cui vengono diffuse e condivise le informazioni all’in-terno di una MSN, identifichiamo diverse architetture Figura 2.2:

• MSN centralizzata: Questa architettura si affida a server centralizzati usati per la condivisione e la diffusione dei dati tra gli utenti. Questi server sono sempre on-line e si occupano principalmente di memorizzare e iniettare i dati a gruppi di dispositivi tramite l’uso di infrastrutture di rete affidabili e super veloci, fisse o mobili (base station, gateway o access point). Queste infrastrutture vengono anche utilizzate dai dispositivi stessi per accedere ai server in modo da comunicare tra loro. Un’architettura di questo tipo viene utilizzata dalle OSN.

• MSN distribuita: Caratteristica chiave di questa architettura `e la totale assenza di un server centralizzato che permetta la comunicazione tra i dispositivi, che avvie-ne in maniera diretta mediante l’utilizzo di interfacce di comunicazioavvie-ne (Bluetooth,

(18)

Wireless,...) e sulla base della loro mobilità e delle opportunità di contatto che si creano. Dato che non viene considerata alcuna infrastruttura di rete, la diffusione dei dati avviene attraverso i dispositivi stessi che si occupano di memorizzare e di instradare le informazioni fino a che non viene raggiunta la destinazione corretta. Un’architettura centralizzata non è sempre affidabile in quanto si ha un singolo punto di fallimento, in tal caso l’intera rete si potrebbe bloccare, e si ha il problema della congestione dei server quando molti dispositivi tentano di accedervi in contemporanea. Nel nostro caso ci interessa considerare un’architettura distribuita in cui si ha una comunicazione basata sulla mobilità dei dispositivi e sulle interazioni sociali che vi si creano, conforme con i nostri obbiettivi.

Internet Server

centralizzato

Distribuito Centralizza

Figura 2.2: Architettura di una MSN

2.1.1 Nodi di una MSN

I nodi di una MSN sono i dispositivi mobili come gli smartphone, i tablet, i palmari o gli smart watch, tipicamente indossati o trasportati da persone che li utilizzano per poter accedere ai servizi offerti nella rete.

Questi dispositivi sono dotati di diverse interfacce di rete, quelle a corto raggio come WiFi o Bluetooth, e quelle a lungo raggio come GPRS, 3G e LTE. Le interfacce a corto raggio permettono di rilevare i dispositivi vicini, mentre quelle a lungo raggio garanti-scono la connettività a banda larga in tutto il mondo. Inoltre sono dotati di capacità di calcolo aggiuntive e di sensori come l’accelerometro, il giroscopio e il GPS che permetto-no di rilevare la posizione esatta e l’orientamento di un permetto-nodo. Tutte queste funzionalità

(19)

di cui sono provvisti i dispositivi sono fondamentali per permettere agli utenti di una MSN di comunicare opportunisticamente senza utilizzare alcuna interfaccia di rete.

2.1.2 Mobilit`

a degli utenti e relazioni sociali

La mobilità e le caratteristiche sociali degli utenti sono due fattori chiave molto im-portanti in quanto influenzano le relazioni tra le persone e quindi le opportunità di interazione tra i nodi. Una relazione sociale tra due utenti è definita come una strut-tura sociale che agisce da “collegamento” tra due nodi determinato da un insieme di interazioni, spesso chiamati anche legami sociali che non è facile individuare e model-lare. Un legame rappresenta l’esistenza o meno di relazioni sociali significative tra due individui.

In [9] gli autori hanno definito la forza dei legami come la combinazione del tempo trascorso, della frequenza degli incontri, l’intensità delle emozioni, l’intimità e i ser-vizi reciproci che caratterizzano i legami. Per esempio se prendiamo due amici, loro trascorrono molto tempo insieme, condividendo molti interessi e tendono a incontrarsi spesso, al contrario due persone che non condividono interessi hanno meno opportunità di incontrarsi.

Le metriche che modellano la forza dei legami sociali sono:

• Frequenza: “più frequentemente due persone interagiscono fra loro, più forte è il loro sentimento di amicizia l’uno per l’altro” [cit. Homas [20]].

• Intimità: “è un indicatore della fiducia reciproca, rappresenta il tempo investito in un contatto, inoltre è direttamente connesso all’ammontare di tempo da quando si è creato il legame” [cit. Granovetter [9]].

• Regolarità: “quando un incontro si ripete con regolarità allora si può individuare una relazione” [cit. Nazir [21]].

• Omogeneità:“ è il grado in cui le preferenze degli individui in una società tendono ad essere simili” [cit.Gehrlein [22]]

La tendenza o meno delle persone di essere in contatto con i loro simili con cui condivi-dono o meno determinati interessi caratterizzano il modo in cui le persone si muovono all’interno della MSN e di conseguenza la mobilit`a dei nodi.

2.1.3 Neighborhood

I vicini di un nodo possono essere classificati in vicini fisici, physical neighbours, oppure vicini sociali, social neighbours. Ad esempio, ciascun nodo in qualsiasi momento pu`o

(20)

essere circondato da altri nodi, considerati vicini fisici. Mentre i vicini sociali sono quei nodi che mantengono un rapporto sociale significativo tra loro. Nonostante siano due categorie distinte, vi pu`o essere una connessione: la frequenza e la durata del contatto fisico tra due nodi indicano chiaramente la presenza o meno di un rapporto sociale identificato mediante il loro monitoraggio.

I vicini sociali possono essere categorizzati in base alla forza dei legami, identifichiamo cos`ı le seguenti categorie [2] Figura 2.3:

• Membri della Comunit`a : Questa categoria descrive due nodi appartenenti ad

uno stesso gruppo sociale, ed `e caratterizzata da un elevato numero di contatti di lunga durata.

• Familiari : Questa categoria descrive una coppia di nodi che si incontrano con

regolarit`a ma che non passano molto tempo insieme, ed `e caratterizzata da un

elevato numero di contatti ma con durata breve.

• Sconosciuti : Questa categoria descrive una coppia di nodi che non si incontra con regolarit`a e non passa tanto tempo insieme, ed `e caratterizzata da un basso numero di contatti di breve durata.

• Amici : Questa categoria descrive una coppia di nodi che non si incontra con

regolarit`a ma che passa tanto tempo insieme, ed `e caratterizzata da un basso

numero di contatti di elevata durata.

II

Familiari

I

Comunità

III

Sconosciuti

IV

Amici

Familiarità F re qu e n za

Durata dei contatti

N u m e ro d i c o n ta tti

(21)

2.1.4 Comunit`

a all’interno di una MSN

Tra le categorie dei vicini sociali abbiamo introdotto il termine comunità. Non esiste una definizione univoca di “comunità”; intuitivamente possiamo definirla come un insieme di nodi strettamente collegati tra loro da relazioni sociali significative che si muovono all’interno di una regione limitata. Questi nodi creano tra loro forti legami sociali dovuti principalmente alla condivisione degli stessi interessi. Esempi di comunità sono persone legate da una relazione di amicizia, persone legate da una relazione familiare o da una

relazione lavorativa. Qualche membro di una comunit`a tende anche a creare qualche

relazione sociale con i membri di altre comunit`a, Figura 2.4 cerchiati in rosso.

Figura 2.4: Collegamento tra comunit`a diverse

Le caratteristiche sociali dei nodi (la localizzazione, le relazioni sociali, gli interessi

e i modelli di movimento) possono cambiare dinamicamente nel tempo e ci`o ha reso la

rilevazione delle comunit`a un passo fondamentale per studiare sia gli effetti della mo-bilit`a sia l’individuazione di una strategia efficiente per l’instradamento e la diffusione delle informazioni.

Gli algoritmi per la rilevazione delle comunit`a, Community detection algorithm possono avere due forme:

• Algoritmi centralizzati: Questi algoritmi presentano un punto della rete in cui si convogliano tutte le informazioni riguardanti i nodi nella rete e i legami che creano. Tali informazioni vengono utilizzate per rilevare le comunit`a presenti.

• Algoritmi distribuiti: In questi algoritmi non è presente l’aspetto descritto pri-ma, saranno quindi i nodi stessi a rilevare le comunità a cui appartengono tramite una visione locale della rete. Inoltre ogni nodo necessita di sapere la qualità degli incontri in termini delle:

(22)

– Metriche temporali: Queste metriche misurano la dimensione temporale degli incontri, in particolare la durata dei contatti, il tempo medio di Inter-contatto e l’ultima volta che si sono incontrati.

– Metriche di similarità: Queste metriche calcolano il tasso di similarità tra i dispositivi che entrano in contatto, in particolare la misura degli interessi, il numero di contatti simili o la similarità dei luoghi visitati.

La mobilit`a e la natura dinamica di una MSN ci conducono a considerate gli algoritmi distribuiti, a tal proposito si andr`a a citare alcuni algoritmi di community detection che verranno considerati nei prossimi capitoli (DRAFT in quanto usato da CORDIAL in [8] e la famiglia di tre algoritmi proposti da Hui et al. in quanto nei nostri studi CORDIAL utilizza K-Clique).

2.1.4.1 Strategie di community detection distribuite

In [7] gli autori hanno proposto una famiglia di algoritmi, SIMPLE, MODULARITY e K-Clique. Come principio generale ogni nodo dispone di un insieme, familiar set, composto da tutti i dispositivi le cui durate dei contatti superano una determinata soglia. La comunit`a di ogni nodo contiene tutti i nodi del familiar set pi`u altri nodi scelti in base ai criteri di ammissione sul numero di contatti in comune di ciascun algoritmo.

Per esempio in SIMPLE due comunit`a vengono unite se hanno in comune pi`u nodi

di una determinata soglia, in K-Clique se il familiar set del nodo incontrato contiene

almeno k − 1 nodi in comune con la comunit`a del nodo corrente e in MODULARITY se

il familiar set del nodo incontrato non `e incluso nel familiar set del nodo corrente. Nelle nostre configurazioni sperimentali presentate nel capitolo 4 verr`a utilizzato K-Clique.

Uno svantaggio di SIMPLE `e che non vengono mai rimossi i nodi dal familiar set, a

tal proposito in [23] hanno proposto AD-SIMPLE estensione di SIMPLE in cui venne aggiunto un meccanismo per eliminare i nodi obsoleti.

Un altro algoritmo molto usato è DRAFT [24], viene considerata la durata dei contatti per aggiungere i nodi alle comunità, esattamente come negli algoritmi proposti da Hui et Al, in più è previsto un meccanismo che permette di eliminare i nodi obsoleti. Si analizzerà nel dettaglio nel capitolo 3.4.

2.1.5 Instradamento e diffusione delle informazioni nelle MSN

Il routing e la disseminazione di informazione (data dissemination) rappresentano due problemi fondamentali delle MSN. Tali problemi non hanno una soluzione univoca-mente accettata, piuttosto esistono una serie di soluzioni algoritmiche proposte la cui

(23)

efficacia, spesso, dipende dallo scenario utilizzato.

Il Routing si occupa di consegnare un messaggio dalla sorgente alla destinazione con l’obiettivo di minimizzare il ritardo sfruttando le caratteristica sociali dei dispositi-vi che tendono a spostarsi prevalentemente all’interno delle proprie comunità creando rapporti sociali. Data la natura dinamica delle MSN non è possibile né conoscere a priori la topologia della rete né avere connessioni dirette o stabili tra due nodi; quindi

ogni nodo dovr`a “cooperare” alla comunicazione selezionando in maniera autonoma il

nodo o i nodi a cui inoltrare il messaggio in modo che possa raggiungere la destinazio-ne. Uno schema di questo tipo è il modello store-carry-and-forward, rappresentato in Figura 2.5: in mancanza di un’opportunità di comunicazione diretta tra la sorgente e il destinatario, in questo caso tra il nodo i e il nodo d, il nodo intermedio j memorizza il messaggio e sfrutta ogni futura opportunità di contatto con altri nodi, u, per trasferirlo verso la destinazione. Ogni nodo effettua scelte locali per decidere in modo autonomo

chi possa consegnare il messaggio con un ritardo minimo, pu`o essere il nodo stesso

oppure un suo vicino.

i

j

k

i

u

v

u

d

t

t’

t’’

...

Figura 2.5: Routing del messaggio m dal nodo i al nodo d

La Data Dissemination invece, si occupa di diffondere le informazioni prodotte da un nodo a tutti gli altri nodi che sono interessati al loro utilizzo senza sovraccaricare la rete. Questi protocolli sono stati introdotti come conseguenza della tendenza degli utenti a generare un gran numero di informazioni e condividerle con coloro con cui han-no un rapporto sociale o un interesse in comune. Come accennato prima, la topologia della rete non è conosciuta a priori e la mobilità dei nodi non permette di individuare un percorso diretto da un nodo che produce le informazioni (nodo fornitore o provi-der) a un nodo che è interessato a usufruirne (nodo consumatore); è quindi necessario individuare efficienti protocolli di diffusione che permettano alle informazioni di muo-versi e replicarsi nella rete in modo da arrivare ai consumatori, stando attenti a non

(24)

sovraccaricare la rete e a non utilizzare troppe risorse. Possiamo vedere un esempio in Figura 2.6: il dispositivo i genera e propaga il messaggio m tra i dispositivi interessati nel riceverlo; in particolare i seleziona k al tempo t0, k a sua volta selezione u e h al tempo t00 e infine u seleziona d. In questo caso non vi `e un solo destinatario finale ma un numero di destinatari interessati.

i

j

k

u

v

u

d

t

t’

t’’

...

Figura 2.6: Diffusione del messaggio m

2.1.5.1 Strategie di Routing

Possiamo individuare pi`u classificazioni sui protocolli di routing, una prima distinzione riguarda se vengono sfruttate o meno le comunit`a rilevate Figura 2.7:

• Routing basato sulle comunit`a : Rientrano in questa categoria i protocolli che

sfruttano l’esistenza delle comunità e/o di altre caratteristiche sociali (la centralità dei nodi, la forza dei legami o le similarità tra i nodi) per trasportare i messaggi verso la destinazione. Un esempio è BubbleRap [16], un protocollo che sfrutta le co-munità rilevate usando l’algoritmo K-Clique [7] e la centralità dei nodi per decidere a chi inoltrare i messaggi.

• Routing indipendente dalle comunit`a : Rientrano in questa categoria i

pro-tocolli che ignorano le comunità e utilizzano altre strategie per scegliere i nodi che dovranno trasportare i messaggi verso la destinazione. Il più semplice, Epidemic [17], utilizza la tecnica del Flooding : non potendo basarsi su alcun tipo di cono-scenza ogni messaggio deve essere distribuito il più possibile nella rete quindi ogni nodo invia a tutti gli altri nodi con cui è in contatto una copia. Tale strategia non prevede alcun controllo sul numero di copie diffuse nella rete e in questo modo, a discapito di un utilizzo maggiore delle risorse, si ha più probabilità che il mes-saggio arrivi a destinazione. Spray&Wait [18] è molto simile a Epidemic ma pone un limite nel numero di copie da diffondere continuando a tenere alto il tasso di

(25)

successo nelle consegne e riducendo il consumo di risorse.

Prophet [19], è un altro protocollo evoluzione di Epidemic che introduce il concetto di prevedibilità nella consegna, in particolare si assume che i nodi non si muovono in modo del tutto causale e si cerca quindi di calcolare la probabilità che un nodo sia in grado di consegnare un messaggio a un altro nodo e in base a si effettuano scelte in base a tale valore.

Un’altra classificazione riguarda il numero di copie di un messaggio che vengono diffuse nella rete Figura 2.8:

• Copia singola: Esempi di algoritmi appartenenti a questa categoria sono la Direct Delivery [25],che implementa una consegna diretta da parte del nodo sorgente al nodo destinatario, e la First Contact [26] in cui il nodo sorgente invia una singola copia al primo nodo che incontra che a sua volta la inoltrer`a al suo primo contatto e cosi via fino a che il messaggio non raggiunge il destinatario. Questo schema `e raro nelle MSN in quanto si ha un basso tasso di successo nella consegna dei messaggi e un’elevata latenza (tempo che intercorre tra la generazione del messaggio alla ricezione).

• Copie multiple: Questi algoritmi si possono ulteriormente classificare in copie illi-mitate in cui non vi è limite sul numero di repliche di un messaggio, in particolare se N è il numero dei nodi e Ki è il numero di repliche dell’i-esimo messaggio, allora

Ki ∈ [0, N ] (Epidemic, Prophet, BubbleRap); oppure limitate a un numero L che

cambia a seconda dell’algoritmo (Spray&Wait). Questo schema assicura un alto tasso di successo nelle consegne dei messaggi a discapito di un maggior consumo di memoria, di energia e di larghezza di banda. Spesso vengono usate determinate euristiche per decidere Ki ed `e stato dimostrato che determinare questo valore `e

un problema NP-hard [27].

Routing

Indipendente

dalle comunità

sulle comunità

Basato

Algoritmo di rilevamento delle comunità

(26)

Routing

Copia singola

Copia multipla

Euristiche

Illimitate

Limitate

Figura 2.8: Categorie di routing sulla base delle copie dei messaggi

I protocolli accennati verranno analizzati nel dettaglio nel capitolo 4, in quanto sono oggetto delle nostre sperimentazioni.

2.1.5.2 Strategie di Data Dissemination

Una soluzione potente e semplice si basa sul flooding, con una tecnica simile a quella adottata dal protocollo Epidemic, ma chiaramente si avrebbe un sovraccarico della rete e un elevato consumo delle risorse. Approcci pi`u realistici possono essere divisi in due gruppi:

• Publish-subscribe: Obiettivo di questo algoritmo `e quello di consegnare un’in-formazione ai nodi consumatori solo se hanno diffuso una sottoscrizione di interesse per un certo tipo di contenuto (sport, news, radio,...). Il provider e il consumatore sono fortemente disaccoppiati infatti non sono a conoscenza l’uno dell’altro ma sem-plicemente iniettano messaggi nella rete, il che `e inerente con la natura dinamica in cui le parti coinvolte nella comunicazione cambiano nel tempo o si disconnettono

nel momento in cui viene generato il messaggio. Un esempio `e il PodNet [28] il

quale non sfrutta le interazioni sociali ma incorpora le politiche di caching come la selezione greedy e uniforme. La sua idea si basa sull’organizzare i contenuti in ca-nali e permettere agli utenti di sottoscriversi cosi dai ricevere automaticamente gli aggiornamenti sui contenuti a cui sono interessati. Un altro esempio `e SocialCast [29] e si basa sul l’assunzione che gli utenti con interessi comuni tendono a incon-trarsi spesso. Questo protocollo sfrutta in particolare le predizioni sulle metriche che riguardano le interazioni sociali.

(27)

• Social-aware: Questo algoritmo sfrutta le relazioni sociali degli utenti per il

pro-cesso di diffusione. Un esempio `e PrefCast [30] che ha come obiettivo quello di

massimizzare la soddisfazione dell’utente, in base ai propri interessi, delle informa-zioni ricevute. Un altro esempio `e DIFFUSE [31] basato sul calcolo del contributo di ogni dispositivo, un parametro che indica la frequenza e la durata dei contatti tra gli utenti e che viene utilizzato per selezionare i nodi a cui inoltrare i dati.

2.2 Service Discovery

Il problema di ricercare e accedere ai servizi offerti all’interno di una MSN `e noto

come Service Discovery : SD. Fino ad oggi `e stato ampiamente studiato per le reti

dotate di infrastrutture basate su IP, alcune soluzioni le troviamo in [10],[11], [12], e per le reti wireless come[13]. Ma nessuna di queste soluzioni tiene in considerazione la natura dinamica di una MSN, in particolare non viene considerato il comportamento umano da cui consegue la mobilità e i legami che si creano. Questo capitolo mostra una panoramica sulle entità e le funzionalità di un protocollo di service discovery, illustra molte strategie proposte al fine di individuare un protocollo efficiente e leggero adatto alla natura delle MSN.

Con il termine “servizio” indichiamo qualsiasi tipo di risorsa disponibile, sia hardware che software, fornite dai dispositivi che rappresentano specifiche funzionalit`a per conto degli utenti e delle applicazioni sulla rete. Alcuni servizi sono significativi solo in un determinato istante temporale e in una determinata area geografica. Dalla Figura 2.9 possiamo vedere la classificazione dei servizi in 3 diverse categorie [3]:

• Servizi basati sul contenuto, in particolare si tratta della condivisione di contenuti multimediali ( video, foto, streaming di piccoli video,...), oppure anche servizi di utilit`a per i contenuti multimediali come la modifica di immagini.

• Servizi basati sulla rete, in particolare oltre ai tradizionali servizi come stampan-te, scanner, fax, troviamo anche servizi progettati per condividere funzionalit`a della rete con i dispositivi mobili come per esempio la condivisione della pro-pria connessione a internet oppure servizi che permettono di abilitare messaggi e chiamate.

• Servizi basati sui sensori, ossia tutti quelli che sfruttano i sensori installati nei dispositivi.

(28)

Figura 2.9: Classificazione dei servizi offerti all’interno di una MSN [3]

Le parti coinvolte in questo processo sono:

• Service provider definito come il nodo a cui viene data la possibilit`a di annunciare l’esistenza di un servizio che intende fornire.

• Service client definito come il nodo interessato ad un servizio a cui viene data la possibilit`a di ricercarlo nella rete e usufruirne.

• Service registry definito come un insieme di nodi che si occupano di memorizzare i servizi diffusi nella rete appartenente a qualche service provider in attesa di una futura opportunit`a di contatto con un service client che ne `e interessato.

2.2.1 Il processo di service discovery

Il processo di service discovery pu`o essere rappresentato come un ciclo di 4 fasi come mostrato in Figura 2.10 [3] :

• Advertisement: In questa fase il service provider pubblicizza i propri servizi. • Query: In questa fase il service client richiede un servizio offerto da un service

provider.

• Selection: In questa fase il service client seleziona il servizio pi`u interessante tra quelli a disposizione.

• Access: In questa fase il service client usufruisce del servizio offertogli inviando una richiesta di accesso.

(29)

Figura 2.10: Processo di Service discovery [3]

I servizi che vengono richiesti e offerti nella rete, viaggiano sotto forma di messaggi, in particolare possiamo distinguere due tipi:

• Advertisement: Questo messaggio viene propagato quando il service provider intende pubblicizzare nella rete i servizi di cui dispone. Tale messaggio contiene determinate caratteristiche che identificano il servizio, come per esempio l’identi-ficativo del service provider, un’interesse che classifica il servizio a seconda delle funzionalit`a fornite, informazioni sulla qualit`a del servizio come le performance ottenute e parametri di input/output necessari per invocare il servizio.

• Query: Questo messaggio viene propagato quando il service client richiede un servizio a cui gli interessa accedere. Tale messaggio contiene: l’interesse che specifica le funzionalit`a necessarie al client e le caratteristiche che richiedono uno specifico livello di performance.

La diffusione nella rete di advertisement e di query rappresenta la sfida pi`u importante per l’introduzione di un paradigma orientato ai servizi nelle reti mobili sociali.

Andiamo ora ad analizzare tutte le quattro fasi mostrando gli obbiettivi e le strategie adottate, sia quelle progettate specificatamente per il problema del service discovery, sia quelle progettate per i problemi di instradamento e diffusione dei dati che possono comunque essere applicate in questo contesto.

2.2.1.1 Pubblicazione e richiesta dei servizi

Le due fasi principali individuano due modelli: un service discovery reattivo in cui il service client diffonde una query nella rete per poter ricercare ed accedere ad un par-ticolare servizio, e un service discovery proattivo in cui il service provider propaga gli

(30)

advertisement ai dispositivi incontrati opportunisticamente nella rete. L’obiettivo della fase di query è quello di propagare le richieste ai nodi che possono rispondere con un advertisement corrispondente in tempo breve, è importante quindi esplorare la rete per individuare un dispositivo che fornisce una risposta oppure che conosce l’advertisement in quanto ne ha usufruito in precedenza. L’obiettivo della fase di advertisement è quel-lo di diffondere i servizi soquel-lo agli utenti che sono interessati ad accedervi nel caso in cui non si conosce a priori l’insieme dei destinatari, oppure in caso contrario si cerca

consegnarglielo producendo il minimo ritardo, `e importante evitare i nodi che hanno

ricevuto quel particolare advertisement in precedenza.

Per soddisfare questi obbiettivi si può sfruttare la struttura delle comunità dato che si tratta di gruppi formati da persone che tendenzialmente condividono interessi simili: un service client può propagare le query prima all’interno della comunità in modo da avere più probabilità di trovare un advertisement corrispondente, allo stesso modo il service provider può diffondere gli advertisement all’interno della propria comunità. Inoltre si può sfruttare la mobilità dei nodi, è utile quindi cercare di predire i loro movimenti osservando la mobilità passata, per esempio, se k individua h che può ri-spondere alla sua query con probabilità alta, allora analizza gli incontri passati di h per predire quando si possono rincontrare nuovamente e decidere se attendere questa futura occasione oppure scegliere un nodo registry. Il problema di capire i pattern di mobilità non è integrato nel ciclo del processo di service discovery.

Analizziamo ora le strategie di inoltro e diffusione dei dati adatte a soddisfare gli obbiettivi preposti nella maniera pi`u efficace possibile.

• Strategie basate sugli interessi

Queste strategie sfruttano gli interessi associati ad ogni dispositivo, per poter rap-presentare il profilo dell’utente, ad ogni query e ad ogni advertisement per diffon-dere i messaggi. L’obiettivo `e quello di propagarlo ai dispositivi per cui una data funzione di similarit`a indica una corrispondenza tra gli interessi. Esempi di queste funzioni sono l’indice di Jaccard o la distanza Hamming.

L’idea su cui si basano la maggior parte degli algoritmi che adottano questo tipo di strategia `e che le persone che condividono gli stessi interessi tendono a incontrarsi frequentemente rispetto alle persone che non hanno molto in comune.

Analizziamo brevemente alcuni algoritmi proposti:

– Social Cast [29]: Questo algoritmo implementa un paradigma di tipo “pu-blish subscribe” in cui si cerca di prevedere la futura evoluzione dei movimenti delle persone con interessi simili basandosi su osservazioni precedenti del loro comportamento, della loro mobilit`a nella rete e delle relazioni sociali create.

(31)

Queste predizioni sono utilizzate per stimare quali sono i nodi migliori per trasportare i messaggi, nodi registry. I passi fondamentali di questo algoritmo sono tre: (i) diffusione degli interessi, (ii) selezione dei nodi trasportatori, e (iii) diffusione dei messaggi tramite sottoscrizioni di interesse.

– SANE [32] : Obiettivo di questo algoritmo è quello di diffondere in maniera efficiente le informazioni al più alto numero di dispositivi interessati basandosi sulla misura della similarità tra tutte le coppie di utenti usando la metrica della similarità del coseno.

– InterestBased [33]: Questo algoritmo presenta delle similitudini con SANE, viene calcolata la similarità del coseno tra gli utenti e in base a tale valore si decide se inviare o no l’informazione. In particolare si basa sull’idea che il nodo sorgente genera sempre due copie del messaggio, una la memorizza localmente mentre l’altra la inoltra al primo nodo incontrato tale per cui la similarità eccede una determinata soglia. E’ un approccio stateless, infatti gli interessi dei nodi vengono memorizzati solo per il tempo necessario a calcolare la similarità.

– Sideman [4]: Questo algoritmo, insieme alla sua evoluzione CORDIAL [8], sfrutta le similitudini degli interessi tra i nodi in modo da diffondere le query attraverso persone che hanno una più alta probabilità di rispondere, e diffon-dere advertisement attraverso persone che possono essere interessate a tale messaggio. Sono algoritmi di natura sociale e opportunistica che sfruttano i comportamenti umani, come la mobilità e le relazioni sociali che creano

for-mando comunit`a. Per diffondere le query e gli advertisement in modo pi`u

efficiente possibile sfruttano un algoritmo di community detection, DRAFT [24]. Nel capitolo 3 si presenter`a l’algoritmo CORDIAL nel dettaglio.

• Strategie basate sulla tecnica del flooding

L’obiettivo comune di queste strategie è quello di massimizzare il numero dei desti-natari degli advertisement e delle query senza utilizzare alcuna metrica sociale per selezionare i nodi che dovranno trasportare i messaggi. Il vantaggio è l’efficacia e la semplicità delle tecniche di diffusione a scapito di un overhead più alto in termini di consumo di energia e larghezza di banda della rete.

Analizziamo brevemente alcune soluzioni proposte:

– Una strategia per le reti MANET (Mobile ad hoc network) [34] con una bassa mobilit`a dei dispositivi. In questo caso i messaggi corrispondenti ai servizi non contengono alcun identificativo e alcuna descrizione sul servizio, ma solo

(32)

i parametri necessari per essere invocati. Ogni dispositivo contiene una ta-bella con tutti i servizi e i parametri di I/O necessari. Diffondere nella rete i parametri corrispondenti ai servizi anziché le informazioni sul servizio è una buona strategia poiché se si propagano le informazioni sui servizi si assume che ogni nodo ha una piena conoscenza di tutti i servizi che possono essere diffusi nella rete. Gli advertisement e le query vengono diffuse con la tecnica del flooding, in particolare ai vicini viene inviata la tabella (sotto forma di messaggio).

– OLFServ [35]: Questa strategia per le DMANET ( Disconnected mobile ad

hoc network) `e progettata per eseguire una diffusione geograficamente

con-trollata dei servizi. Il provider pubblicizza i propri servizi specificando negli advertisement la sua locazione e l’area geografica dove possono essere ricer-cati e invoricer-cati. Il client invece deve specificare nelle query la sua locazione, l’area in cui possono essere diffusi i messaggi ed eventualmente la locazione del provider se conosciuta.

• Strategie basate sulle caratteristiche sociali

Questi algoritmi sfruttano le informazioni sulle relazioni sociali per effettuare la diffusione di query e advertisement. Per determinare le relazioni sociali tra gli utenti si usano diverse metriche, come per esempio la durata dei contatti, la durata degli inter-contatti oppure la betweenness centrality data dal numero di percorsi tra sorgente e destinatario che passano per un determinato nodo.

Analizziamo brevemente alcune soluzioni proposte:

– Delegation forwarding [36]: Obiettivo principale di questo algoritmo `e

quello di cercare di trasmettere un messaggio solamente ai nodi di alta qualit`a in base ad una metrica associata. Sono state analizzate e studiate diverse metriche di qualit`a :

∗ Frequenza: Il nodo Ni inoltra un messaggio a Nj se Nj ha pi`u contatti

con altri nodi rispetto a Ni.

∗ Ultimo contatto: Il nodo Ni inoltra un messaggio a Nj se Nj ha contattato

un nodo di recente rispetto a Ni.

∗ Frequenza di destinazione: Il nodo Ni inoltra il messaggio a Nj se Nj ha

contattato il destinatario del messaggio pi`u spesso di Ni.

∗ Ultimo contatto di destinazione: Il nodo Ni inoltra il messaggio a Nj se

(33)

– BubbleRap [16]: Questo algoritmo, visto in precedenza, implementa una

strategia basata su due metriche fondamentali, la popolarit`a dei nodi e la

struttura delle comunit`a. Analizzeremo questa strategia nel dettaglio nel ca-pitolo 4.

– Socio-aware [2]: Questo algoritmo implementa una strategia di tipo publish subscribe che si basa sulle comunità rilevate. I nodi con elevata centralità, detti broker, hanno più visibilità di altri nodi, quindi l’idea è quella di creare una struttura di sovrapposizione su di essi. Ogni nodo ha una propria visione sulla comunità e di conseguenza può calcolarsi la propria centralità; il broker ricevono tutte le sottoscrizioni e le liste contenenti i valori di centralità dei nodi in contatto e in base ai tali valori decide chi sarà il broker successivo a cui trasferirà tutto ciò che possedeva. Una volta che il broker riceve le sotto-scrizioni controlla se nella comunità esiste un nodo contenente l’informazione corrispondente alla sottoscrizione e in caso affermativo la diffonde altrimenti inoltra le sottoscrizioni agli altri broker.

2.2.1.2 Selezione dei servizi

Durante la fase in cui vengono diffusi gli advertisement e le query, un dispositivo può ricevere più advertisement i cui servizi forniscono le medesime funzionalità, è quindi necessario selezionare il miglior advertisement che descrive il servizio richiesto. La se-lezione viene effettuata cercando di massimizzare una determinata funzione obiettivo scelta in base a diverse strategie [3] Figura 2.11.

Figura 2.11: Strategie di selezione [3]

La selezione manuale, ossia quella che richiede l’intervento dell’utente, non `e con-sigliata per le MSN in quanto gli utenti non sono consapevoli dei meccanismi interni e

(34)

delle politiche usate, quindi `e preferibile usare una strategia automatica come :

• La qualità del servizio può essere ricondotta alla rilevanza degli attributi, alla capa-cità di minimizzare il tempo di risposta, alla descrizione del servizio o alla capacità di minimizzare il numero di intermediari attraverso il quale viene diffuso.

• La localizzazione indica la vicinanza o la prossimit`a del service provider.

• L’energia la possiamo considerare o come l’energia come numero di nodi rel`e utilizzati oppure come il consumo per l’accesso al servizio.

• Interessante indica la reputazione del service provider.

2.2.1.3 Accesso dei servizi

In questa fase, il service client richiede al service provider il servizio che ha preceden-temente selezionato. Nei casi in cui non è presente un percorso diretto tra i due, sia la richiesta che la risposta viaggiano all’interno della rete producendo qualche ritardo che è necessario minimizzare adottando un protocollo efficiente. A differenza della diffusio-ne degli advertisement e della ricerca dei servizi, le comunicazioni coinvolte diffusio-nella fase di accesso dipendono dalla natura del servizio, per esempio potrebbe essere richiesta la trasmissione di una grande quantità di dati come un video streaming e di conseguenza si avrebbe un elevato consumo di risorse.

L’obiettivo in questa fase `e quello di permettere alle richieste e ai servizi di viaggiare cercando di limitare i consumi delle risorse disponibili (larghezza di banda, energia richiesta,..). E’ utile quindi adottare efficienti strategie di instradamento diverse da quelle viste per il service discovery in quanto si cerca di limitare le risorse disponibili e minimizzare i ritardi.

2.2.2 Architetture di service discovery

Le architetture di service discovery si distinguono in: (i) directory-less architecture e (ii) directory-based architecture. Una directory è un’entità che memorizza le informa-zioni sui servizi disponibili nella rete, detti service description, in modo da permettere la ricerca dei servizi e la loro invocazione. Nelle MSN sono usati diversi formalismi (lin-guaggi) per descrivere le proprietà di un servizio: un esempio è la coppia chiave-valore, dove la chiave indica l’attributo, oppure attraverso una descrizione XML.

La distinzione sulle architetture si basa su come vengono diffuse le informazioni riguar-danti i servizi:

(35)

• Directory-based : Con questa architettura si assume l’esistenza della directory il cui ruolo `e quello di facilitare la comunicazione tra il service provider e il service client, Figura 2.12, in particolare si occupa di:

– Memorizzare i service description.

– Gestire gli advertisement forniti dai dispositivi.

– Gestire le query che riceve dai dispositivi che stanno cercando un servizio. Se la query corrisponde con uno o pi`u advertisement allora la directory risponde con l’advertisement corrispondente.

La directory pu`o essere implementata in diversi modi, a tal proposito possiamo

identificare un’ulteriore classificazione dell’architettura directory-based:

– Centralizzata: Con questa architettura esiste un unico dispositivo che fa da directory e memorizza le informazioni su tutti i servizi disponibili nella rete. Tutti gli altri dispositivi sono a conoscenza del dispositivo-directory. I service provider pubblicizzano i propri servizi alla directory centrale con un messag-gio unicast, mentre i service client prima contattano la directory per ottenere le informazioni sul servizio, successivamente sulla base del service description ottenuto interagiscono con il provider. La tecnica centralizzata non è una buo-na soluzione per le MSN in cui un nodo potrebbe non essere raggiungibile in un determinato istante, per altro individuiamo diversi problemi in quanto ab-biamo un singolo punto critico che in caso di guasto non sarà più in condizioni di gestire i messaggi e i dispositivi non potranno più condividere e ricercare i servizi, inoltre non è scalabile in quanto un singolo dispositivo non è in con-dizioni di gestire un gran numero di messaggi che viaggiano all’interno di una MSN.

– Distribuita: Con questa architettura esistono pi`u dispositivi che fanno da di-rectory e comunicano costantemente tra loro per distribuirsi gli advertisement. Le directory distribuite sono pi`u adatte e vengono implementate configurando in modo statico i dispositivi che implementano la directory oppure dinamica-mente eleggendo i dispositivi che soddisfano una determinata metrica. A sua volta possiamo distinguerla in:

∗ Infrastructure-less: Con questa architettura non si assume l’esistenza di alcuna infrastruttura e le directory vengono selezionate dinamicamente

tra i nodi che hanno una capacit`a sufficiente come batteria, memoria,

(36)

in pi`u nella rete in quanto si vuole selezionare una directory che si adatti bene alla topologia variabile della rete e si vuole informare tutti gli altri nodi sulla sua identit`a.

∗ Infrastructure-based : Questa architettura è caratterizzata dalla presenza di più reti separate e connesse tra loro mediante una rete fissa dotata di un’infrastruttura contenente la directory. Un service client che necessita di un servizio contenuto in un’altra rete vi si connette indirettamente at-traverso la rete fissa. Questa architettura assume che l’ambiente contenga più di un milione di nodi in questo modo si riducono i costi di calcolo e il sovraccarico di memoria.

E’ importante notare che gli approcci basati sull’esistenza di una directory

impli-cano pi`u costi di comunicazione per mantenere la directory e per supportare lo

scambio di dati tra quest’ultimo e gli altri nodi

Service

client

provider

Service

client

provider

Service

Service request Service reply

Figura 2.13: Architettura senza la directory

• Ibrida : Questa architettura `e una combinazione delle due architetture in cui esiste una directory, ma se un nodo che richiede un servizio non riceve risposta dalla directory allora propaga la query nella rete.

(38)

CAPITOLO

3

CORDIAL: COllaborative seRvice DIscovery

ALgorithm

CORDIAL, COllaborative seRvice DIscovery ALgorithm [8], `e un protocollo per la

ricerca dei servizi all’interno di una MSN distribuita (in cui non si sfrutta alcuna infra-struttura di rete stabile) e dotata di un’architettura “directory-less” che trae vantaggio dalle caratteristiche sociali del comportamento umano, una tra le più importanti è la mobilità degli individui che permette di creare le opportunità di comunicazione. Le per-sone si muovono a seconda degli obbiettivi e delle attività derivanti dalle loro relazioni sociali, possiamo quindi individuare tre aspetti chiave che caratterizzano il modo in cui si muove un individuo : (i) la mobilità è determinata dalla sua relazione sociale, per esempio le persone che hanno molte conoscenze all’interno di una grande area urbana tendono a muoversi con maggiore frequenza rispetto alle persone più solitarie. (ii) Il numero dei luoghi visitati è limitato (si va a lavoro, al supermercato, in ufficio), (iii) le persone tendono a viaggiare per percorsi brevi anziché per percorsi più lunghi. Un’ altra caratteristica molto importante è la condivisione degli interessi, strettamente correlata alla mobilità degli utenti in quanto le persone che condividono alcuni interessi tendono a frequentare gli stessi luoghi, le stesse persone, a svolgere attività comuni, e

di conseguenza tendono a incontrarsi spesso e per tempi pi`u lunghi formando

comu-nità. Per esempio guardando la Figura 3.1[4], Alice, rappresentata con un cerchio nero, durante il giorno entra a far parte di tre comunità diverse, rappresentate con un cerchio bianco, i colleghi di lavoro in ufficio con cui condivide interessi nell’attività lavorativa, gli amici incontrati al pub con cui condivide interessi riguardo hobby/attività preferite come il calcio o andare a ballare, e la famiglia a casa con cui condivide interessi per eventi ricreativi come guardare programmi in Tv. In alcuni momenti Alice è in grado di comunicare con alcuni di loro (linee dirette) e in altri no (mancanza di linee) in quanto

(39)

non sono abbastanza vicini per garantire una comunicazione e scambiare informazioni.

Figura 3.1: Esempio della formazione di comunit`a a seguito della mobilit`a di un

individuo [4]

In CORDIAL ogni nodo sfrutta la propria mobilit`a e quella degli altri per diffondere messaggi (query o advertisement) in quanto possono non esistere cammini diretti tra il nodo sorgente e il nodo destinatario, quindi ogni nodo intermedio collabora inoltrando i messaggi nella rete secondo il modello store, carry and forward. Inoltre l’algoritmo sfrutta le caratteristiche sociali dei nodi per implementate efficienti politiche di ricerca e pubblicazione dei servizi mediante la diffusione nella rete di messaggi.

I prossimi paragrafi introducono alcune nozioni base e mostrano nel dettaglio le fasi principali dell’algoritmo CORDIAL e i loro obiettivi.

La fase di selezione e quella di accesso sono fuori dagli scopi di questa tesi e quindi non verranno descritte.

3.1 Concetti preliminari

La rete e le comunit`a

Rappresentiamo una MSN come un grafo non orientato al tempo t: Gt = (V, Et) in

cui V = {n1, ...nv} `e l’insieme dei nodi e Et = {eij = (ni, nj) : ni, nj ∈ V } `e l’insieme

(40)

comunicazione a una via tipica delle reti opportunistiche. Le principali strutture che individuiamo sono:

• Neighborhood [Ni

t]: Questa struttura contiene tutti i nodi che comunicano con

ni al tempo t, in particolare contiene nj ∈ V tale che eij ∈ Et.

• Contact-history [Ti_{]: Questa struttura contiene i nodi che entrano in contatto}

con ni nel tempo. Un record di tale tabella contiene:

– ID del nodo incontrato;

– l’ultima volta che `e stato incontrato; – il tempo medio tra due incontri successivi.

• Comunit`a [C]: Questa struttura `e un sottoinsieme di Ni

t contenente ni e tutti

i nodi che sono entrati in contatto con lui i quali soddisfano determinati criteri stabiliti da un algoritmo di community detection.

Ricerca dei servizi

Come abbiamo accennato le fasi principali su cui ci focalizzeremo sono la pubblicazione e la richiesta dei servizi, le principali strutture che caratterizzano queste fasi sono:

• Interessi [I]: Questa struttura contiene tutti gli interessi che modellano i possi-bili topic a cui gli utenti di una MSN possono essere affiliati, come per esempio “sport”,“videogiochi”, “cronaca” o “spettacolo”. Tale insieme rappresenta quindi una tassonomia degli interessi possibili delle MSN.

• Service advertisement [advj]: Questa struttura `e memorizzata all’interno della

service cache CH dei nodi. Un advertisement descrive le caratteristiche pi`u

im-portanti di un servizio come per esempio l’identificatore del provider, gli interessi associati, le informazioni relative alla qualit`a ed alle performance e i parametri necessari per l’invocazione.

• Service query [q]: Questa struttura contiene un’insieme di caratteristiche che descrivono il tipo di servizio richiesto dal client, come per esempio il tipo di fun-zionalit`a che il client necessita e altre caratteristiche che richiedono determinate performance.

• Pending query [P Qi]: Questa struttura contiene tutte le query generate da ni che

non hanno ancora ricevuto risposta, più precisamente non è stato ancora trovato un advertisement corrispondente. Oltre alla query appartenente a ni conterrà anche

quelle appartenente ad altri nodi, vedremo quali quando descriveremo le fasi di CORDIAL.