Definizione e valutazione di un algoritmo di selezione di edge mobili in supporto ad applicazioni di Mobile Crowdsensing per ottimizzare la raccolta e la condivisione dei dati in relazione alla mobilità e alla socialità degli utenti

(1)

UNIVERSITÀ DI PISA

Dipartimento di Informatica

Corso di Laurea Magistrale in Informatica

TESI DI LAUREA

Definizione e valutazione di un algoritmo di selezione di

edge mobili in supporto ad applicazioni di Mobile Crowdsensing per

ottimizzare la raccolta e la condivisione dei dati in relazione alla

mobilità e alla socialità degli utenti

Candidato

Relatori

Giampiero Di Paolo

Prof. Stefano Chessa

Dott. Dimitri Belli

(2)

(3)

UNIVERSITÀ DI PISA

Dipartimento di Informatica

Corso di Laurea Magistrale in Informatica

TESI DI LAUREA

Definizione e valutazione di un algoritmo di selezione di

edge mobili in supporto ad applicazioni di Mobile Crowdsensing per

ottimizzare la raccolta e la condivisione dei dati in relazione alla

mobilità e alla socialità degli utenti

Giampiero Di Paolo

Prof. Stefano Chessa

Dott. Dimitri Belli

(4)

(5)

Abstract ... 1

1. Introduzione ... 2

2. Stato dell’arte ... 8

3. Soluzioni proposte ... 11

3.1. Modello architetturale composto da soli edge fissi ... 11

3.1.1. Descrizione e impiego di un edge fisso ... 12

3.1.2. Localizzazione degli edge fissi ... 12

3.2. Modello architetturale composto da soli edge mobili ... 14

3.2.1. Descrizione e impiego ... 14

3.2.2. Studio di reti sociali: approccio e algoritmi ... 15

3.3. Modello architetturale composto da edge fissi e edge mobili ... 15

3.3.1. Descrizione e impiego ... 15

4. Ambiente di sperimentazione e sviluppo ... 17

4.1. Dataset ... 17

4.2. Simulatore ... 19

4.3. Tecnologie impiegate ... 25

5. Metaeuristiche per la selezione degli edge ... 27

5.1. Localizzazione degli edge fissi ... 27

5.1.1. Algoritmi di clustering spaziale ... 27

5.1.2. Altri tipi di distribuzione ... 29

5.2. Selezione degli edge mobili ... 30

5.2.1. Individuazione delle comunità ... 31

5.2.2. Calcolo delle comunità top ... 32

5.2.3. Calcolo della misura di centralità ... 33

6. Analisi del modello architetturale composto da soli edge fissi ... 35

6.1. DBSCAN... 35

6.1.1. Numero di edge fissi: 6 ... 36

(6)

6.3. Distribuzione a griglia ... 82

6.4. Distribuzione casuale ... 90

7. Analisi del modello architetturale composto da soli edge mobili ... 141

7.1. Betweenness Centrality ... 142

7.1.1. Numero di edge mobili: 1 ... 142

7.2. Eigenvector Centrality ... 167

8. Analisi del modello architetturale composto da edge fissi e mobili ... 192

8.1. DBSCAN e Betweenness Centrality ... 193

(7)

9.1.1. Modello architetturale composto da soli edge fissi ... 253

9.1.2. Modello architetturale composto da soli edge mobili ... 262

9.1.3. Modello architetturale composto da edge fissi e mobili ... 266

9.2. Euristiche per la selezione degli edge ... 282

10. Conclusioni ... 285

Riferimenti ... 288

Indice delle figure ... 290

Indice delle tabelle ... 295

(8)

1

Abstract

I modelli architetturali di Mobile Edge Computing (MEC) consentono la trasmissione di grandi quantità di dati dal Cloud verso i punti in cui le informazioni sono realmente richieste ed utilizzate, in prossimità degli utenti, e viceversa. La combinazione tra MEC e Mobile Crowdsensing (MCS) consente un notevole aumento delle prestazioni delle piattaforme per la raccolta di informazioni, traendo vantaggio dalle capacità di elaborazione e memorizzazione di dati proprie dei dispositivi mobili e indossabili. In questo lavoro si analizzano vari modelli architetturali MEC composti da edge fissi e edge mobili. L'obiettivo è quello di ottimizzare la condivisione dei contenuti tra dispositivi e Cloud, selezionando gli edge in base alla mobilità e alla socialità degli utenti. A tal proposito, si presenta e valuta un algoritmo per identificare il miglior insieme di edge mobili e si dimostra come tale modalità di selezione aumenti le prestazioni di un sistema di condivisione di dati. Le simulazioni sono basate su ParticipAct, un dataset contenente le tracce di mobilità di circa 170 utenti, raccolte in un arco temporale di 18 mesi. Gli esperimenti avvalorano il concetto per cui il numero di richieste soddisfatte dagli edge mobili è maggiore di quello delle richieste evase da edge fissi. Ne deriva che gli edge mobili possono essere considerati validi elementi da affiancare agli edge fissi in un sistema ibrido e un'alternativa plausibile a questi ultimi in quanto, a differenza degli edge fissi, gli edge mobili non richiedono costi di installazione e manutenzione; inoltre, migliorano notevolmente la qualità del servizio offerto.

(9)

2

1. Introduzione

Al giorno d’oggi la maggior parte dei dispositivi elettronici utilizzati nella vita quotidiana ha la possibilità di connettersi ad Internet. Gli smartphone, e in generale tutti i dispositivi mobili più diffusi, ricoprono un ruolo fondamentale. Infatti, oltre alle funzionalità di base per la comunicazione tra individui, essi sono dotati di interfacce di comunicazione a corto raggio (Wi-Fi, Bluetooth, ZigBee ecc.) che consentono loro lo scambio di informazioni in assenza di una qualsiasi infrastruttura di rete fisica. Con l’avvento delle nuove tecnologie, in questi dispositivi sono incorporati magnetometri, giroscopi, accelerometri e molti altri sensori (o trasduttori), che rendono possibile la raccolta di informazioni di ogni tipo e da ogni luogo, generando di conseguenza una quantità considerevole di dati. L’enorme diffusione di questi dispositivi, unita al numero di sensori che possono ospitare ed alle interfacce di comunicazione a corto raggio, ha reso possibili forme di sensing partecipativo e opportunistico, in una parola Mobile Crowdsensing (MCS).

Il MCS è una tecnica di raccolta e condivisione di dati, largamente diffusa, secondo la quale un grande numero di individui, equipaggiati con dispositivi mobili dotati di un’ampia gamma di sensori in grado di raccogliere ed elaborare una notevole quantità di dati, condivide informazioni al fine di ottenere risultati utili a misurare, analizzare e stimare qualsiasi processo di interesse comune. In base al coinvolgimento degli utenti, il MCS si può classificare in: partecipativo, dove gli utenti partecipano volontariamente alla raccolta delle informazioni; opportunistico, dove i dati sono rilevati, raccolti e condivisi automaticamente senza alcun intervento umano e, in alcuni casi, addirittura senza la consapevolezza esplicita degli utenti. Generalmente un processo di MCS è composto da tre fasi: raccolta dei dati, elaborazione e memorizzazione, upload diretto verso il Cloud. Quest’ultima caratteristica identifica un modello architetturale classificabile come Cloud a due livelli, un modello in cui viene instaurato un collegamento diretto tra l’utente e il Cloud.

Il Mobile Edge Computing (MEC) è un modello architetturale proposto dall’ETSI (European Telecommunications Standards Institute) sviluppato per far evolvere il

(10)

3 tradizionale modello di comunicazione a due livelli tra i dispositivi e il Cloud con l’introduzione di un terzo livello intermedio. La Figura 1 descrive tale modello architetturale. Questa configurazione permette lo spostamento delle risorse, di calcolo e di storage, verso gli edge della rete, quindi più vicino agli utilizzatori finali [1]. In un’architettura MEC generica, gli edge sono fissi, posizionati in punti strategici di un territorio dai fornitori di servizi di telecomunicazione, e accoppiati con le stazioni di reti RAN (Radio Access Network).

La chiave di volta di questo studio è la valutazione di un modello di scambio di informazioni, caratterizzato dall’utilizzo sinergico della tecnologia MCS e dell’architettura MEC, al fine di facilitare la trasmissione dei dati tra dispositivi, sia fissi che mobili. Tuttavia, per alcuni servizi di MCS estremamente esigenti, i costi a carico degli utenti per eseguire le attività richieste sono molto elevati, principalmente quelli di comunicazione del traffico dati. In altre parole, esistono diversi casi pratici di grande rilevanza in cui l’utilizzo congiunto delle soluzioni MEC e MCS porterebbe benefici significativi in termini di utilizzo efficiente delle risorse, costi a carico degli utenti e qualità del servizio. Al fine di migliorare lo scambio di informazioni tra il Cloud e i dispositivi personali, l’idea è quella di affiancare agli edge della rete fissa definiti dal modello MEC, denominati fixed MEC (FMEC), degli edge mobili temporanei, denominati mobile MEC (M2EC), selezionati tra i nodi della rete in modo non arbitrario. È possibile infatti individuare dinamicamente un’entità da attivare in luoghi strategici, magari dove le persone tendono a rimanere più a lungo, che assuma il ruolo di elemento intermediario nella comunicazione tra i dispositivi e il Cloud. Così facendo, l’architettura MEC standard a tre livelli viene potenziata con l’introduzione di una nuova entità, con le stesse funzionalità di un edge fisso, il cui punto di forza è la mobilità. Proprio quest'ultimo aspetto permette di superare le problematiche relative alla copertura sociale e spaziale presenti in tale modello. In questo contesto è fondamentale la modalità di selezione degli M2_{EC, che dovrebbe privilegiare i nodi} della rete aventi maggiori possibilità di scambiare dati con gli altri nodi. La Figura 2 mostra il modello architetturale MEC esteso con l’introduzione dei nodi M2_EC. L’obiettivo principale di questa tesi è l’analisi e la formalizzazione di un algoritmo per la selezione degli edge mobili, inclusa la valutazione del contributo fornito dall’applicazione in un contesto come quello appena descritto. A tale scopo, si vogliono

(11)

4 analizzare diversi modelli architetturali, valutandone la qualità sulla base di vari indicatori. Al concetto di qualità viene associato il numero di richieste di trasmissione dei dati, avanzate dagli utenti del sistema e provenienti da o indirizzate verso il Cloud. Fondamentale, in questo contesto, il tempo che trascorre tra il momento in cui una richiesta viene avanzata e il momento in cui la stessa viene soddisfatta, da un edge fisso o mobile, a seconda dell’architettura. Sono stati utilizzati questi indicatori in quanto ritenuti tra i più significativi per valutare la qualità dei modelli analizzati, in un contesto applicativo in cui l’obiettivo principale è quello di instaurare connessioni e trasmettere dati, in un tempo ragionevolmente breve. I modelli architetturali studiati sono tre: 1. il modello MEC standard, che comprende solo edge fissi (FMEC) come elementi

intermedi tra dispositivi e Cloud;

2. il modello M2EC, che considera come elementi intermedi solo gli edge mobili (M2EC);

3. il modello ibrido, che affianca gli edge mobili agli edge fissi.

Figura 1: modello architetturale MEC. Figura 2: modello architetturale MEC esteso con M2_EC.

Riflettendo sui pro e i contro delle diverse soluzioni, il modello architetturale con soli edge fissi risulta essere molto vantaggioso per gli utenti, che non necessitano di una comunicazione diretta con il Cloud, in quanto vengono ridotti i tempi per il

(12)

5 trasferimento delle informazioni e si risparmia sia sui costi di comunicazione del traffico dati sia sui consumi energetici dei dispositivi. Inoltre, considerando che il carico di lavoro per la fornitura del servizio viene distribuito sugli edge della rete, il modello si dimostra vantaggioso anche per il gestore del sistema. Tuttavia, risulta essere una soluzione i cui costi sono per lo più a carico del suddetto gestore, per l’installazione degli apparati che compongono l’infrastruttura, per la loro manutenzione e per i consumi energetici. È possibile osservare altri punti deboli di questo modello. Per prima cosa il numero degli edge fissi è solitamente limitato; inoltre questi sono raramente ricollocati e ciò potrebbe essere altamente inefficiente; infine, alcune aree geografiche potrebbero essere popolate, quindi interessate ad un servizio, solo durante specifici periodi secondo pattern giornalieri, settimanali o addirittura annuali.

In un modello architetturale composto da soli edge mobili, il vantaggio è principalmente quello di non avere costi di installazione e manutenzione dei suddetti apparati, dato che la comunicazione avviene completamente sulla base delle risorse dei dispositivi degli utenti. Per come è strutturato il modello, si potrebbe pensare a problemi causati da sovraccarichi di lavoro per i nodi M2EC, ma dato che possono essere scelti e cambiati dinamicamente, questa evenienza può essere facilmente evitata. Questo modello permetterebbe di risolvere anche il problema della copertura di quelle aree densamente popolate solo in alcuni periodi del giorno, abilitando a facenti funzione di M2EC utenti scelti tra quelli presenti in tali aree.

Nel caso di un modello architetturale ibrido, intuitivamente gli edge mobili forniscono supporto agli edge fissi, principalmente per ampliare la copertura spaziale e sociale intervenendo nelle zone lontane da questi ultimi. In questa tipologia di architettura, la trasmissione dei dati da e verso il Cloud può avvenire tramite un collegamento diretto con un edge fisso oppure tramite uno scambio di informazioni con un edge mobile. Tornando a discutere la qualità di un sistema, tra gli indicatori elencati è presente il tempo di latenza di una richiesta. A seconda dello scenario il calcolo di tale valore avviene in modo diverso.

Nel caso in cui la richiesta venga soddisfatta da un edge fisso, il tempo di latenza corrisponde esattamente al tempo che intercorre tra il momento in cui la richiesta viene avanzata e quello in cui la richiesta viene evasa dall’edge fisso.

(13)

6 Nel caso in cui la richiesta venga soddisfatta da un edge mobile, la comunicazione del dato verso il Cloud ancora non è avvenuta. Infatti, l’utente ha completato la trasmissione del dato verso l’edge mobile, ma non è detto che questo sia stato poi trasmesso verso il Cloud. Si presentano allora due possibili modalità di calcolo della latenza: si considera la latenza come la somma della latenza nella comunicazione tra utente e M2EC e della latenza nella comunicazione tra M2EC e FMEC (in questo caso l'edge mobile dovrebbe essere scelto non solo sulla base delle relazioni sociali, ma anche dei contatti con gli FMEC); si considera soltanto la latenza della comunicazione tra utente e M2EC. Quest’ultimo scenario è plausibile così come lo è il primo, considerando che l’M2_{EC può comunicare verso il Cloud attraverso la propria} connessione broadband, magari godendo di un contratto particolare con il gestore della piattaforma in merito ai costi delle comunicazioni. In questo lavoro si è scelto di adottare la seconda soluzione, considerando che in molte campagne reali di MCS le informazioni non vengono elaborate in tempo reale, ma sono raccolte e memorizzate per un’analisi successiva.

Questo studio propone varie metodologie di selezione degli edge, sia fissi che mobili. Nel caso degli edge fissi, vengono considerati diversi algoritmi che analizzano le posizioni degli utenti per determinare in quali zone tendono a formarsi comunità. In prossimità di queste zone sarebbe vantaggioso installare un edge fisso. In dettaglio, sono stati applicati due algoritmi di clustering spaziale per individuare i punti di aggregazione degli utenti: DBSCAN [2] e HDBSCAN [3]. Per quantificare il contributo fornito dagli algoritmi, sono stati analizzati altri due scenari, nei quali la posizione degli edge fissi è stata determinata in modo casuale, secondo una distribuzione regolare. Nel caso degli edge mobili, l’idea di base è stata quella di selezionare gli utenti più centrali, ossia quelli che vantano il maggior numero di connessioni con gli altri nodi della rete. I dispositivi degli utenti selezionati avranno maggiori probabilità di essere connessi e quindi di scambiare informazioni con una più ampia parte di utenti della rete, favorendo il flusso di dati verso gli M2_{EC e di} conseguenza verso il Cloud. A questo scopo è stato applicato un algoritmo per la ricerca di comunità in una rete sociale dinamica, TILES [4], e diverse metriche per il calcolo della misura di centralità di un nodo in un grafo.

(14)

7 Lo studio è fondato sull’ipotesi di interazione in un contesto ideale, nel quale i vari utenti del sistema possono sempre comunicare con gli altri, tenendo conto sia della distanza tra loro che della tecnologia utilizzata nelle comunicazioni, ma trascurando alcune possibili problematiche relative a interferenze, congestioni della rete e allocazione di banda per spostare i dati da e verso gli edge.

La qualità dei vari modelli architetturali è stata valutata eseguendo esperimenti e simulazioni sui dati della piattaforma di MCS partecipativo ParticipAct [5].

(15)

8

2. Stato dell’arte

Allo stato attuale della conoscenza, un esiguo numero di ricerche ha analizzato i vantaggi nell'uso sinergico delle soluzioni MCS e MEC. Gli studi si sono focalizzati principalmente su aspetti puramente tecnici relativi alla comunicazione tra dispositivi, senza considerare l’importanza di avere esseri umani come partecipanti attivi nelle dinamiche del sistema [6] [7].

Un recente studio, nonché punto di partenza di quello presente, mira a colmare questa lacuna e propone un nuovo modello architetturale di Human-driven Edge Computing (HEC), per facilitare l’approvvigionamento e l'implementazione delle piattaforme MEC e per permettere l’esecuzione di applicazioni MCS più potenti [8]. In primo luogo, il modello HEC cerca di limitare i potenziali punti deboli del modello MEC, come avere soltanto edge fissi, integrando le funzionalità di rilevazione di informazioni del MCS e proponendo una riconfigurazione dinamica del sistema a seguito dell’individuazione di nuovi hotspot per la distribuzione degli edge. Inoltre, HEC consente l’implementazione e l’attivazione dinamica e temporanea di edge mobili (M2EC) che sfruttano le risorse dei device mobili disponibili localmente. Un M2EC è attivato dinamicamente in un’area geografica circoscritta, potenzialmente dove le persone tendono ad aggregarsi. Nel modello HEC una comunicazione tra dispositivo e M2_{EC è diretta (one-hop) e si sfruttano gli spostamenti delle persone per consentire lo} scambio dei dati tra FMEC e M2_{EC. In questo scenario, le comunicazioni possono} avvenire utilizzando diverse interfacce come Bluetooth, Wi-Fi, LTE, variando il raggio di copertura, ossia la distanza massima tra i dispositivi comunicanti, da circa 25, a circa 150, a circa 500 metri rispettivamente. Per la selezione di FMEC e M2EC, sono state analizzate le tracce di mobilità degli utenti considerando diversi intervalli temporali. In merito agli FMEC, sono state individuate le zone di interesse, ipotizzandole costanti nel tempo e utilizzando come tecnica di clustering spaziale l’algoritmo DBSCAN. Per quanto riguarda gli M2EC, sono state considerate quelle regioni dello spazio risultate densamente popolate soltanto in specifici periodi temporali. Successivamente, sono state analizzate le tracce di mobilità in tali intervalli e, per ognuno di questi, sono stati

(16)

9 individuati i cluster formati dalle persone in modo analogo al caso degli FMEC. I risultati ottenuti dagli esperimenti hanno confermato che tecniche di clustering spaziale possono essere impiegate per pianificare la collocazione di FMEC e M2EC. Tuttavia, è doveroso sottolineare che questa ricerca non considera né gli aspetti sociali che caratterizzano il contesto applicativo della soluzione, né la rete nella quale si collocano gli M2EC, impiegando solo algoritmi di clustering spaziale per l’individuazione di questi ultimi.

Gli stessi autori propongono in [9] un nuovo algoritmo per la selezione di M2_{EC, che} sfrutta la conoscenza delle comunità di utenti della rete per selezionare gli individui meglio connessi agli altri, per favorire lo scambio di dati tra utenti e M2EC. I risultati dei test mostrano che piattaforme convenzionali di MEC possono trarre un grande vantaggio dall’integrazione di elementi M2_{EC, i quali si presentano come validi} sostituti degli FMEC eguagliandone le prestazioni. Tuttavia, l’analisi non affronta tematiche relative al confronto di diversi algoritmi per la selezione di M2EC e non approfondisce gli aspetti relativi al bilanciamento del numero degli edge fissi e mobili in un modello architetturale che prevede l’applicazione di entrambe le tipologie di edge. Come riportato in [1], alcune attività di ricerca hanno approfondito l’analisi dell’interazione tra edge ed elementi core dell’infrastruttura MEC, ma pochi si sono concentrati sulle opportunità di cooperazione tra edge e dispositivi mobili.

Considerando lo scenario applicativo del MCS, gli articoli [6] e [10] propongono di migliorare il processo MCS sfruttando i nodi MEC intermedi (FMEC) per favorire lo spostamento dei dati dai dispositivi all'infrastruttura [6] e per mettere a disposizione capacità di elaborazione e archiviazione più potenti in prossimità dei dispositivi degli utenti [10].

Per studiare gli argomenti relativi all'efficienza energetica, in [11] viene proposto un approccio basato sulla teoria dei giochi al fine di selezionare le attività e gestirne la pianificazione diretta presso gli edge della rete, introducendo la nozione di “container as a service”.

Un lavoro che si avvicina al modello di HEC nel consentire una maggiore collaborazione tra entità situate presso gli edge della rete è presentato in [7]. In questo studio si propone non solo di avere la tradizionale collaborazione "verticale" tra

(17)

10 dispositivi e Cloud, ma anche una collaborazione "orizzontale" tra entità sullo stesso livello tramite comunicazioni ad hoc. Tuttavia, non vengono prese in considerazione le caratteristiche sociali e di mobilità degli utenti; in particolare non vi è alcun riferimento alla selezione dinamica degli M2EC, argomento cruciale che questo studio si propone di approfondire.

Per quanto riguarda le problematiche legate al sistema e agli altri aspetti implementativi, poche attività di ricerca si sono concentrate sulla migrazione di virtual machine e container sul livello middleware del modello architetturale MEC, per favorire la fornitura di servizi mobili anche in ambienti ostili. Gli articoli [12], [13], [14], [15] e [16] analizzano diverse soluzioni in questo ambito, approfondendo anche il problema della gestione integrata delle operazioni di migrazione di virtual machine e container, ma nessuno si concentra sulla possibilità di utilizzare i dispositivi mobili delle persone come possibili locazioni di storage, installazione ed esecuzione di virtual machine e container.

(18)

11

3. Soluzioni proposte

In questo capitolo vengono illustrati i modelli architetturali proposti come soluzione al problema descritto in apertura. In primo luogo, viene analizzata una soluzione che si basa su un’infrastruttura composta da soli edge fissi. In secondo luogo, viene presa in considerazione una soluzione che prevede solo edge mobili sociali. Infine, viene esposta una soluzione ibrida che impiega sia edge fissi che edge mobili.

L’obiettivo dello studio è quello di valutare quanto le diverse proposte possano favorire la diminuzione dei costi a carico degli utenti del sistema, sia in termini di traffico dati che di energia consumata, nella comunicazione dei dati da e verso il Cloud. I risultati ottenuti nelle varie configurazioni vanno interpretati in un’ottica che consideri tale obiettivo. Infatti, uno degli indicatori più importanti preso in considerazione è relativo alla percentuale di richieste di connessione da parte degli utenti del sistema che vengono soddisfatte dagli edge.

È importante sottolineare l’interpretazione data a questo indicatore e chiarire quale significato è stato dato al concetto di “richiesta soddisfatta”, ma ancor più a quello di “richiesta non soddisfatta”. Nell’analisi si è adottato il principio secondo il quale una richiesta soddisfatta corrisponde ad una comunicazione a costo zero per l’utente. Al contrario una richiesta non soddisfatta corrisponde ad una comunicazione con un determinato costo per l’utente, che rimanendo quindi a suo carico, non corrisponde ad una reale impossibilità di trasmissione di dati. Inoltre, si è ipotizzato che una richiesta abbia un tempo massimo per essere evasa e ogni edge abbia un raggio di copertura limitato.

3.1. Modello architetturale composto da soli edge fissi

In questo paragrafo si analizza la soluzione al problema che prevede l’utilizzo di soli edge fissi, ricordando che per edge fisso si intende un componente dell’architettura la

(19)

12 cui caratteristica principale è quella di essere posizionato in un punto stabilito e non avere possibilità di movimento.

Nelle sezioni seguenti verrà ulteriormente specificato il concetto di edge fisso e sarà descritto l’approccio scelto per affrontare il problema al centro di questo studio.

3.1.1. Descrizione e impiego di un edge fisso

L’edge fisso è un componente del modello architetturale MEC che ha come caratteristica principale quella di essere inamovibile una volta installato in un punto più o meno strategico. L’individuazione del punto migliore in cui posizionare un edge fisso è l’argomento di studio verso il quale si è rivolta l’attenzione. Gli utenti in un sistema composto da soli edge fissi comunicano da e verso il Cloud instaurando connessioni con tali edge. Se da un lato questa soluzione risulta essere molto favorevole per gli utenti, eliminando la necessità di avere una comunicazione diretta con il Cloud e risparmiando così sui costi di comunicazione del traffico dati e sui consumi energetici dei dispositivi, dall’altro risulta essere costosa per il gestore del sistema, sia per quanto riguarda i costi di installazione e manutenzione degli edge fissi, sia per gli elevati consumi energetici. D’altra parte, il costo per il gestore del sistema sarebbe composto dalla spesa una tantum per l’installazione dei componenti infrastrutturali e dai costi di gestione che potrebbero essere abbattuti sfruttando politiche di partnership.

3.1.2. Localizzazione degli edge fissi

In merito alla localizzazione degli edge fissi, questo lavoro si è posto l’obiettivo di individuare le migliori posizioni nelle quali installare un numero prestabilito di edge fissi al fine di massimizzare la copertura rispetto al numero di utenti del sistema. In altre parole, si vuole minimizzare la quantità di richieste di connessione avanzate dagli utenti che non riescono ad essere soddisfatte dagli edge (le cosiddette “richieste non soddisfatte”).

Sono stati individuati diversi approcci possibili per risolvere il problema descritto, spaziando da alternative semplici a soluzioni più articolate.

(20)

13 La prima soluzione è relativa ad una distribuzione casuale degli edge fissi, in uno spazio limitato, al fine di evitare una dispersione esagerata delle risorse. Per evitare un’eccessiva concentrazione di edge nella stessa zona, si è pensato che gli edge debbano avere una distanza minima tra l’uno e l’altro. Tuttavia, questa soluzione presenta un problema evidente: potenzialmente gli utenti potrebbero non avere la possibilità di avvicinarsi ad un edge, ad esempio nel caso in cui questo, considerato il suo raggio di copertura, sia posizionato in una zona non transitabile.

Un’altra soluzione analizzata è quella di determinare la posizione degli edge secondo una distribuzione “regolare”, in modo da seguire un pattern predefinito. Nello specifico, si è pensato di suddividere lo spazio, limitato come nel caso precedente, in una griglia le cui dimensioni dipendano dal numero di edge a disposizione. Ad esempio, avendo a disposizione 6 edge e uno spazio limitato da un perimetro rettangolare, la divisione di tale spazio potrebbe essere una griglia 3 x 2 (oppure 2 x 3, a seconda della forma della zona delimitata) in cui i centri delle celle indicano le posizioni degli edge. Questa soluzione offre sicuramente una copertura più uniforme dello spazio, al contrario della proposta precedente, ma non esclude il problema che si presenta quando un edge viene collocato in una zona non accessibile agli utenti.

Entrambe le soluzioni proposte non tengono in considerazione come gli utenti del sistema si spostano e si aggregano nello spazio. Si è pensato quindi di analizzare i movimenti degli utenti e utilizzare i risultati per definire i punti strategici dove installare gli edge fissi, non limitandosi a una distribuzione che considera esclusivamente una copertura spaziale ottimale. Sulla base della posizione degli utenti, l’approccio ritenuto più interessante è stato quello di individuare le zone in cui essi si concentrano, ossia, in termini tecnici, i cluster che formano. Tra tutti i cluster individuabili, si è pensato di estrarre quelli formati dal maggior numero di utenti distinti, per poi determinare il punto in cui collocare ogni edge fisso calcolando il centroide di ogni cluster.

Nei prossimi capitoli verranno introdotti gli algoritmi di clustering spaziale studiati e approfonditi i dettagli implementativi della soluzione. Inoltre, saranno analizzati i risultati ottenuti eseguendo degli esperimenti sul dataset messo a disposizione per lo

(21)

14 studio, comparando i valori prodotti e determinando il contributo fornito dagli algoritmi di clustering rispetto alle altre tipologie di distribuzione.

3.2. Modello architetturale composto da soli edge mobili

In questo paragrafo si analizza la soluzione al problema che prevede l’utilizzo di soli edge mobili, ricordando che per edge mobile si intende un componente dell’architettura la cui caratteristica principale è quella di essere scelto in modo dinamico e non arbitrario tra gli utenti del sistema.

Nelle sezioni seguenti verrà ulteriormente specificato il concetto di edge mobile e sarà descritto l’approccio che si è scelto per affrontare il problema al centro di questo studio.

3.2.1. Descrizione e impiego

L’edge mobile (M2_{EC) è un componente che estende il modello architetturale MEC} identificato tra gli utenti del sistema secondo determinate logiche, più o meno complesse. Gli utenti di un sistema composto da soli edge mobili comunicano da e verso il Cloud attraverso connessioni instaurate con tali edge. L’obiettivo è effettuare la selezione degli edge mobili su base “sociale”, in modo tale da massimizzare il numero di contatti tra gli M2_{EC e gli altri utenti, cercando quindi di massimizzare la} possibilità di scambio dei dati nel sistema. Le comunicazioni possono essere instaurate tramite diverse tecnologie, quali Bluetooth, Wi-Fi oppure LTE. Se da un lato questa soluzione, se da un lato risulta essere molto vantaggiosa per il gestore del sistema, dato che non è prevista l’installazione di alcun tipo di apparati, dall’altro risulta essere dispendiosa per gli utenti che vengono eletti M2EC, soprattutto in termini di consumo energetico e traffico dati. Tuttavia, dato che gli edge mobili vengono scelti dinamicamente, la loro funzione è limitata nel tempo e sono un numero relativamente piccolo rispetto all’intera popolazione, tale costo risulta essere distribuito per tutti gli utenti e in qualche modo “mascherato” al singolo.

(22)

15

3.2.2. Studio di reti sociali: approccio e algoritmi

L’obiettivo che lo studio si è posto in merito alla selezione degli edge mobili è stato quello di individuare i migliori candidati tra gli utenti del sistema in modo da massimizzare il numero di utenti che vengono incontrati, il numero di incontri che si hanno e la frequenza con cui avvengono. Tutto ciò senza dimenticare l’obiettivo generale di minimizzare il numero di richieste di connessione avanzate dagli utenti che non riescono ad essere soddisfatte dagli edge.

L’approccio scelto per la selezione degli M2_{EC è composto da due fasi. Nella prima} sono individuate le comunità che gli utenti formano nella rete sociale ricavata a partire dal dataset a disposizione. Il passo successivo consiste nel selezionare, per ogni comunità, il nodo che risulta essere più sociale. La classificazione dei nodi è basata sulla misura di centralità: a valori più alti corrispondono nodi migliori.

Nei prossimi capitoli verranno descritti gli algoritmi, sia per il calcolo delle comunità di utenti che per quello della misura di centralità, e approfonditi i dettagli implementativi della soluzione. Inoltre, saranno analizzati i risultati ottenuti eseguendo degli esperimenti sul dataset messo a disposizione per lo studio, comparando i valori prodotti a seconda dell’algoritmo utilizzato per il calcolo della misura di centralità.

3.3. Modello architetturale composto da edge fissi e edge mobili

In questo paragrafo si analizza la soluzione al problema che prevede l’utilizzo di edge sia fissi che mobili.

3.3.1. Descrizione e impiego

L’architettura in esame segue quella di un modello MEC con edge fissi, al quale vengono affiancati alcuni edge mobili, selezionati dinamicamente tra gli utenti del sistema, con le stesse funzioni degli edge fissi, ossia raccolta, memorizzazione, ricezione e trasmissioni di dati da e verso il Cloud. Il sistema ibrido risultante permette

(23)

16 di avere un’alternativa agli edge fissi nelle zone coperte da questi e allo stesso tempo, grazie all’abilitazione degli edge mobili, di estendere la copertura del servizio in zone prive di edge fissi e aree densamente popolate solo in alcuni periodi della giornata. È possibile affermare che questa soluzione sintetizza ciò che è stato descritto nell’analisi degli altri modelli architetturali. Dal punto di vista dell’utente, vengono accentuati i vantaggi riconosciuti nel caso di un sistema composto soltanto da edge fissi. Infatti, grazie all’utilizzo sinergico di edge fissi e mobili gli utenti non necessitano di una comunicazione diretta con il Cloud, risparmiando sia sui costi di comunicazione del traffico dati che sui consumi energetici dei dispositivi. Dal punto di vista del gestore del sistema, benché risulti essere una soluzione costosa in termini di costi di installazione, manutenzione e consumo energetico degli edge fissi, essa offre un servizio migliore, non solo per quanto riguarda la garanzia di una maggiore copertura spaziale, ma anche per quanto riguarda la qualità del servizio in relazione alla latenza e al numero di richieste di connessione che è possibile soddisfare.

(24)

17

4. Ambiente di sperimentazione e

sviluppo

Il questo capitolo vengono approfonditi gli aspetti relativi all’ambiente di simulazione realizzato e i dettagli riguardanti gli esperimenti effettuati al fine di verificare l’efficacia e la qualità delle soluzioni proposte. Vengono descritti il dataset utilizzato, il simulatore implementato e i framework utilizzati a supporto.

4.1. Dataset

Tutti gli esperimenti sono stati effettuati con l’ausilio di ParticipAct [5], un dataset contenente informazioni di mobilità relative a circa 170 studenti, per la maggior parte dell’Università di Bologna, nella regione Emilia Romagna. La raccolta dei dati è avvenuta fornendo ad ogni volontario uno smartphone Android equipaggiato con una specifica applicazione in grado di tracciare la propria posizione e garantire possibilità di interazione con il dispositivo attraverso una API (Application Programming Interface) messa a disposizione da Google. Le posizioni di ogni utente, rilevate ad intervalli di 2.5 minuti, sono ottenute sommando informazioni provenienti da sensori GPS, coordinate di Hotspot Wi-Fi e da celle della rete telefonica. Il dataset copre un arco temporale di circa 18 mesi, da Dicembre 2013 a Giugno 2015. Si può osservare che gli spostamenti degli utenti seguono pattern di mobilità tipici di studenti universitari: alcuni transitano da zone periferiche verso il centro urbano e viceversa, altri trascorrono la maggior parte del tempo nel centro della città.

Per gli esperimenti relativi agli edge fissi sono stati estratti da ParticipAct i dati relativi alle tracce di co-locazione degli utenti conservando le informazioni utili allo studio, ossia: l’identificativo dell’utente, le coordinate geografiche in formato decimale (gradi decimali) e la data della rilevazione.

(25)

18 Per gli esperimenti relativi agli edge mobili è stato utilizzato un dataset pre-elaborato in un contesto precedente a questo studio e arricchito con informazioni sulle connessioni punto-punto tra dispositivi. Nel dettaglio, il risultato prodotto descrive per ogni connessione due tipologie di dato: una relativa al momento nel quale la connessione viene instaurata e un’altra relativa al momento nel quale la stessa si interrompe. Le informazioni di interesse che caratterizzano un record del dataset sono le seguenti:

• il timestamp, indicante il momento in cui si verifica l’evento; • gli utenti coinvolti;

• la tipologia di evento, marcata con l’etichetta “up” per indicare che una connessione è stata instaurata oppure con l’etichetta “down” per indicare il termine di una connessione.

Il timestamp rappresenta un offset in secondi rispetto ad una data base fissata. Non è dunque possibile dedurre da questo alcuna informazione riguardo alla data e all’ora esatte in cui l’evento si è verificato.

Per gli esperimenti relativi al sistema ibrido è stato utilizzato lo stesso dataset impiegato per gli esperimenti relativi al sistema composto da soli edge mobili arricchito con informazioni riguardanti le connessioni tra utenti e sei edge fissi. Le posizioni degli edge fissi sono state individuate in uno studio [8] realizzato precedentemente al presente utilizzando l’algoritmo di clustering spaziale DBSCAN su un periodo di osservazione che va dal 1° Marzo al 23 Marzo 2014. Gli identificativi degli FMEC vanno da 1000 a 1005. La Figura 3 mostra le posizioni individuate, corrispondenti ai punti centroidi di ogni cluster trovato.

(26)

19

Figura 3: posizioni degli edge fissi individuate per gli esperimenti del sistema composto da edge fissi e da edge mobili [8].

4.2. Simulatore

In base a quanto descritto nel capitolo precedente e avendo a disposizione le informazioni collezionate nel dataset ParticipAct, è stato progettato e realizzato un simulatore per valutare la qualità delle soluzioni proposte.

Prima di introdurre nel dettaglio il simulatore, è doveroso approfondire il concetto di qualità di una soluzione. Un sistema ha una qualità tanto più elevata quanto più è alto il numero di richieste di connessione che riesce a soddisfare e allo stesso tempo quanto più è basso il tempo che intercorre tra il momento in cui una richiesta di connessione viene avanzata e l’effettivo istante in cui tale richiesta viene evasa (tempo di latenza). Definito il concetto di qualità, il primo passo verso la realizzazione del simulatore è stato quello di specificare un insieme di richieste di comunicazione tra un utente e un edge, fisso o mobile. Le richieste sono rappresentate da una coppia formata da un identificativo utente e un timestamp indicante l’istante in cui l’utente avanza la richiesta. Nel simulatore è stato generato casualmente un insieme di 5000 richieste, numero ritenuto sufficientemente grande per ottenere risultati significativi per questo studio. Nello scenario applicativo composto da soli edge fissi è stata utilizzato lo stesso

(27)

20 insieme per tutti gli esperimenti, mentre nello scenario applicativo composto da soli edge mobili e in quello ibrido le richieste sono state generate casualmente ad ogni esperimento effettuato, escludendo gli utenti eletti a svolgere il ruolo di M2EC. A queste premesse, va aggiunto il concetto di Time-To-Live (TTL) di una richiesta, ossia il tempo di vita e limite oltre il quale una richiesta non soddisfatta decade. Il TTL è fissato a circa una settimana, ossia un quarto del periodo di osservazione, per ogni richiesta. Tale scelta è stata motivata dal fatto che, nonostante il periodo di osservazione vari a seconda del sistema analizzato, lo stesso rimane in ogni caso di grandezza pari a circa 30 giorni. Una volta fissato il periodo di osservazione, le richieste casuali sono state generate nei primi tre quarti dello stesso. Per questo, si può affermare che tutte le richieste hanno la stessa possibilità di essere soddisfatte e il calcolo risulta attendibile. Tuttavia, negli esperimenti che coinvolgono edge mobili l’impostazione descritta per il TTL non rappresenta un’ipotesi neutra, infatti è un aspetto da tenere in considerazione nell’interpretazione dei risultati degli esperimenti. In altre parole, con la scelta di un TTL elevato si potrebbero ottenere risultati buoni anche nel caso di una scelta sbagliata di M2EC, riconoscendo le conseguenze della scelta soltanto sulla latenza e non sul numero di richieste soddisfatte. Al contrario, un TTL breve permetterebbe di evidenziare in modo migliore le differenze nel numero di richieste soddisfatte.

Occorre a questo punto distinguere l’applicazione del simulatore nelle soluzioni precedentemente esposte. Per ciascun caso vengono descritti: input, output ed eventualmente alcuni dettagli dell’elaborazione. Relativamente all’output del simulatore, ci si limita in questa sezione ad una breve disamina, una descrizione completa ed esaustiva verrà presentata nei prossimi capitoli.

Nello scenario applicativo composto soltanto da edge fissi, è previsto un input composto dalle posizioni individuate dai vari algoritmi discussi nel capitolo precedente e le 5000 richieste di connessione generate casualmente. L’output prodotto corrisponde ad una serie di statistiche relative alle richieste soddisfatte e non soddisfatte sia dal punto di vista delle posizioni individuate per il collocamento degli edge fissi sia dal punto di vista temporale. In altre parole, i risultati sono relativi all’andamento del numero delle richieste gestite dal sistema al variare della latenza. Per quanto riguarda

(28)

21 il dataset, il periodo di osservazione è stato limitato all’intervallo di tempo che va dal 1° Marzo 2014 al 30 Marzo 2014, estremi inclusi, al fine di aumentare le probabilità di trovare utenti attivi nel territorio cittadino.

Riguardo al processo di generazione delle richieste, sia l’utente che il timestamp sono stati generati in modo casuale, estraendo il primo dall’insieme degli utenti (le cui rilevazioni sono presenti nel periodo di osservazione stabilito) e fissando il secondo in modo da rispettare le seguenti regole, al fine di rendere più realistiche le simulazioni: • essere compreso nella fascia oraria che va dalle 9:00 alle 20:00;

• essere incluso nei primi tre quarti del periodo di osservazione, quindi tra il 1° Marzo 2014 e il 23 Marzo 2014 (circa).

Il vincolo della fascia oraria è motivato dall’assunzione secondo cui gli utenti, che nel caso di ParticipAct sono 170 studenti, hanno maggiore mobilità nelle ore diurne piuttosto che in quelle notturne, considerando che in queste ultime il più delle volte si trovano nelle loro abitazioni. Infatti, analizzando il dataset, si evince che la maggior parte delle interazioni tra utenti avvengono proprio durante il giorno.

Riguardo la comunicazione tra un utente e un edge fisso, la distanza limite affinché una comunicazione tra queste entità sia possibile è stata fissata a 100 metri. Inoltre, nel caso in cui una richiesta sia avanzata da un punto nel raggio di copertura di più di un edge, l’edge fisso più vicino verrebbe scelto come candidato a soddisfare la richiesta. Tuttavia, una distribuzione oculata degli edge fissi dovrebbe essere tale da evitare questa situazione. Il valore scelto per il raggio di copertura è motivato dall’ipotesi che a 100 metri corrisponda una distanza ragionevole per poter stabilire una trasmissione dati attraverso le interfacce di comunicazione a corto raggio dei dispositivi. Dunque, considerando il momento in cui una richiesta viene avanzata, tutti i record nel dataset con timestamp successivo vengono analizzati fin quando l’utente risulta essere in prossimità di un edge fisso oppure la richiesta esaurisce il proprio TTL.

Per completare la descrizione del simulatore in merito alla localizzazione degli edge fissi è necessario precisare che nei casi in cui viene applicato un algoritmo di clustering il calcolo è stato eseguito su un sottoinsieme del dataset composto dalle prime 200000 rilevazioni, per evitare problemi legati ai limiti di memoria dell’elaboratore. Si è

(29)

22 ritenuta questa soglia sufficientemente grande per ottenere risultati significativi nella fase preventiva dello studio.

Nello scenario applicativo di un sistema costituito soltanto da edge mobili, è stato previsto un input composto dalle comunità di utenti individuate e le 5000 richieste di connessione generate casualmente. L’output prodotto corrisponde ad una serie di statistiche relative alle richieste soddisfatte e non soddisfatte sia dal punto di vista degli edge mobili sia dal punto di vista temporale. In altre parole, i risultati sono relativi al modo in cui la latenza delle richieste gestite dal sistema varia nel tempo. Per quanto riguarda il dataset, il periodo di osservazione è limitato ad un intervallo temporale ampio 30 giorni.

È doveroso puntualizzare il processo di generazione delle richieste. Sia l’utente sia il timestamp sono stati generati in modo casuale, estraendo il primo dall’insieme degli utenti le cui informazioni sono presenti nel periodo di osservazione deciso, includendo il secondo nei primi tre quarti del periodo di osservazione, in coerenza con le logiche relative al TTL.

Avendo definito la struttura del dataset per gli esperimenti sul sistema e avendo delineato le tipologie di collegamento che è possibile trovare nei dati, è necessario precisare come si riconosce un “collegamento utile per soddisfare una richiesta di connessione” e, in parallelo, come avviene il calcolo della latenza. Si considera “collegamento utile per soddisfare una richiesta di connessione” una connessione di tipo “up” caratterizzata da un timestamp che precede quello della richiesta e per la quale non esiste ancora la corrispondente connessione di tipo “down” con timestamp precedente o uguale a quello di tale richiesta. In questo caso, dato che una connessione tra utente e edge è già instaurata, la latenza è pari a zero. Nel caso in cui non vengano individuate connessioni utili, si procede analizzando quelle con timestamp uguale o successivo a quello della richiesta. In modo speculare, si considera utile allo scopo una connessione di tipo “down” caratterizzata da un timestamp successivo a quello della richiesta e per la quale non esiste la corrispondente connessione di tipo “up” con timestamp uguale o successivo a quello di tale richiesta. Anche in questo caso la latenza è pari a zero. Infine, se nessuno dei casi precedenti si verifica, viene presa in considerazione una connessione di tipo “up” con timestamp successivo o uguale a

(30)

23 quello della richiesta e minore della somma tra il timestamp della richiesta e il TTL, ossia tale per cui la richiesta è ancora valida.

Nella Figura 4 e nella Figura 5 vengono mostrati due esempi del calcolo della latenza descritto. Nella prima rappresentazione l’utente è in contatto con un M2EC dalle ore 9:15 alle ore 9:45. Per questa ragione, la “richiesta 1” viene evasa dopo 15 minuti dal momento in cui viene avanzata (ore 9:00), mentre la “richiesta 2” viene soddisfatta con una latenza pari a 0, dato che nel momento in cui viene generata (ore 9:30) la connessione tra utente e M2_{EC risulta instaurata e non ancora terminata. Nella seconda} rappresentazione, l’utente si trova nel raggio di copertura di un FMEC dalle ore 8:50 alle ore 9:50 ed è in contatto con un M2EC dalle ore 9:15 alle ore 9:45. Per questo, sia la “richiesta 1” che la “richiesta 2” vengono soddisfatte con una latenza pari a 0, la prima dall’edge fisso, la seconda dall’edge fisso oppure dall’edge mobile.

Si ritiene utile menzionare due ulteriori dettagli implementativi che non forniscono un particolare apporto allo studio, ma completano la logica appena descritta. Il primo è relativo al caso in cui la richiesta risulti soddisfatta da più di un M2EC contemporaneamente. In questa circostanza viene presa in considerazione la connessione con l’edge, sia essa “up” oppure “down”, temporalmente più vicina al timestamp della richiesta. Il secondo è relativo al caso in cui una richiesta, per ognuno dei passaggi sopra descritti, risulti soddisfatta contemporaneamente da un FMEC e da uno o più M2EC. In questo caso si considera solo la connessione con l’edge fisso.

Figura 4: rappresentazione grafica del calcolo della latenza nel caso di connessione instaurata con un M2_EC.

(31)

24

Figura 5: rappresentazione grafica del calcolo della latenza nel caso di connessione instaurata con un FMEC.

Nello scenario applicativo composto da edge fissi e mobili, come in precedenza, l’input è composto dalle comunità di utenti individuate e le 5000 richieste di connessione generate casualmente. L’output prodotto corrisponde ad una serie di statistiche relative alle richieste soddisfatte e non soddisfatte sia dal punto di vista degli edge sia dal punto di vista temporale. In altre parole, i risultati sono relativi al modo in cui la latenza delle richieste gestite dal sistema varia nel tempo. A titolo informativo, si riportano statistiche relative al rapporto tra le richieste soddisfatte dagli edge fissi e quelle soddisfatte dagli edge mobili, ma si precisa che tale aspetto non è stato approfondito in questo studio. Infatti, nel simulatore non è stata definita alcuna priorità tra edge fissi e mobili al fine di soddisfare una richiesta. Questo vuol dire che, nel caso in cui sia un edge fisso che un edge mobile sono in grado di soddisfare una richiesta, la scelta dell’edge non è guidata da regole particolari. La ricerca dei “collegamenti utili per soddisfare una richiesta di connessione” è lo stesso descritto per un sistema composto solo da edge mobili. Si analizzano, per prima cosa, le connessioni “up” con timestamp precedente o uguale a quello della richiesta; successivamente, si analizzano le connessioni “down” con un timestamp successivo a quello della richiesta; infine, si analizzano le connessioni “up” con timestamp uguale o successivo a quello della richiesta. Gli edge fissi vengono considerati prioritariamente rispetto a quelli mobili soltanto all’interno di ogni passaggio. Per quanto riguarda il dataset, si è limitato il periodo di osservazione ad un intervallo temporale ampio 30 giorni, esattamente lo stesso utilizzato negli esperimenti del sistema composto solo da edge mobili.

(32)

25

4.3. Tecnologie impiegate

Sono di seguito discussi alcuni dettagli tecnici sull’implementazione del simulatore, dal linguaggio scelto alle librerie utilizzate. Il software è stato realizzato in linguaggio Python 3.6 e i framework di sviluppo utilizzati sono stati Eclipse e gli editor di testo Sublime Text e Notepad++. Tra le librerie esterne utilizzate si riportano le più importanti: numpy, pandas, geopy, shapely, networkx, folium. Oltre a queste è importante sottolineare come si è deciso di procedere in merito alle implementazioni gli algoritmi di clustering spaziale e di individuazione di reti sociali. Tali algoritmi verranno introdotti e discussi nei capitoli successivi, tuttavia si anticipano di seguito le scelte in merito alle implementazioni e alle librerie utilizzate. La scelta di quale implementazione utilizzare per ogni algoritmo è basata sull’esperienza fatta in studi precedenti e sulla documentazione consultata per valutarne facilità di utilizzo, affidabilità e uso in contesti come quello nel quale si pone questo lavoro. Si è scelta l’implementazione dell’algoritmo DBSCAN fornita dal progetto scikit-learn (v0.19.1) e l’implementazione dell’algoritmo HDBSCAN fornita dalla libreria omonima hdbscan, per garantire alte prestazioni dell’algoritmo. Per completezza, si vuole precisare anche come sono stati scelti i valori relativi ai parametri sia dell’implementazione scelta per DBSCAN, sia di quella scelta per HDBSCAN. Di seguito sono trattati solo i parametri utilizzati nel simulatore, per approfondimenti si rimanda alla documentazione ufficiale1_{. Per quanto riguarda l’algoritmo DBSCAN,} sono stati considerati i parametri min_samples, eps, algorithm e metric, indicanti rispettivamente il numero minimo di punti nel vicinato di un punto candidato ad essere “core sample” (includendo il punto stesso), la distanza massima tra due punti per essere considerati nello stesso vicinato, l'algoritmo che deve essere utilizzato da un modulo interno all’implementazione per calcolare le distanze tra coppie di punti al fine di individuare quelli più vicini e la metrica da utilizzare nel calcolo della distanza tra due punti. Per quanto riguarda l’implementazione scelta per l’algoritmo HDBSCAN, sono stati considerati i parametri min_samples, min_cluster_size, metric, indicanti rispettivamente il numero minimo di punti nel vicinato di un punto candidato ad essere “core sample” (includendo il punto stesso), la dimensione minima di un cluster e la

(33)

26 metrica da utilizzare nel calcolo della distanza tra due punti. Una nota sulle prestazioni degli algoritmi: non si ritiene interessante approfondire in questo studio l’analisi delle prestazioni degli algoritmi di clustering e dell’algoritmo utilizzato per l’individuazione del punto centroide di ogni cluster. Queste operazioni, anche considerando un’applicazione reale del sistema, vengono eseguite senza requisiti specifici sul tempo di esecuzione, essendo utilizzate per definire le posizioni degli edge in fase di progettazione del sistema stesso. Infine, si è scelta l’implementazione degli algoritmi per il calcolo delle misure di centralità, betweenness_centrality ed eigenvector_centrality, entrambe fornite dalla libreria networkx. I calcoli sono stati eseguiti sul grafo definito utilizzando la stessa libreria a partire dalle informazioni contenute nel dataset; non sono stati specificati particolari parametri. Anche in questo caso, una nota sulle prestazioni degli algoritmi: come nel caso degli algoritmi di clustering, non si ritiene importante per questo studio approfondire l’analisi delle prestazioni degli algoritmi di calcolo della misura di centralità. Tuttavia, si riconosce come questo aspetto potrebbe essere significativo considerando un’applicazione di questo studio in un contesto reale, infatti le operazioni dovrebbero essere ripetute frequentemente nel sistema, considerata la natura dello stesso, che evolve nel tempo a seguito di riconfigurazioni dei nodi M2EC.

(34)

27

5. Metaeuristiche per la selezione

degli edge

Il questo capitolo vengono analizzati gli algoritmi selezionati per individuare le posizioni degli edge fissi e per selezionare gli edge mobili, in accordo alle soluzioni proposte in precedenza.

5.1. Localizzazione degli edge fissi

Nel Capitolo 3 sono stati delineati diversi possibili approcci per individuare le posizioni in cui installare gli edge fissi, spaziando da alternative semplici a soluzioni più articolate, per cui è doveroso fornire ulteriori dettagli. Si discutono dapprima le soluzioni più complesse che studiano i cluster formati dagli utenti, successivamente le soluzioni riguardanti una distribuzione degli edge casuale e una “regolare”.

5.1.1. Algoritmi di clustering spaziale

Sulla base della posizione degli utenti, l’approccio ritenuto più interessante è stato quello di individuare le zone in cui essi si concentrano, ossia, in termini tecnici, i cluster che formano. Per far ciò, sono stati scelti due algoritmi di clustering spaziale molto noti in letteratura: l’algoritmo DBSCAN e l’algoritmo HDBSCAN.

5.1.1.1. DBSCAN

L’algoritmo DBSCAN (Density-Based Spatial Clustering of Applications with Noise) è uno dei più citati algoritmi in ambito scientifico per il clustering spaziale di dati con rumore basato su densità. Dato un insieme di punti in un certo spazio, l’algoritmo

(35)

28 raggruppa i punti che sono estremamente raccolti, in altre parole raggruppa i punti che hanno molti punti “vicini” a una distanza minore di una fissata soglia ε, marcando come “valori anomali” (rumore) i punti che si trovano in regioni dello spazio a bassa densità, ossia dove i punti “vicini” più vicini sono troppo lontani.

Si ricorda che l’implementazione dell’algoritmo DBSCAN scelta è quella fornita dal progetto scikit-learn (v0.19.1). Sono state considerate due diverse configurazioni dei parametri in input al DBSCAN, mostrate nella Tabella 1. Precisamente, le configurazioni differiscono per il parametro min_samples, che nella prima versione è impostato a 10 mentre nella seconda a 3. Gli altri parametri sono stati settati con i seguenti valori: eps a 0.05 / 6371 (equivalente a circa 50 metri, il valore tiene in considerazione la disposizione dei punti su una superficie “quasi” sferica e considera il radiante come unità di misura nel calcolo delle distanze su una sfera, da qui il denominatore, che rappresenta i chilometri compresi in un radiante, ossia 6371), metric a “haversine” (metrica adatta al calcolo di distanze su una sfera) e algorithm a “ball_tree”.

CONF. 1 (v1) CONF. 2 (v2)

min_samples 10 3

eps 0.05 / 6371 0.05 / 6371

metric haversine haversine

algorithm ball_tree ball_tree

Tabella 1: configurazioni dei parametri dell’algoritmo DBSCAN.

In seguito, si farà riferimento alla prima configurazione con la sigla v1 e alla seconda con la sigla v2.

5.1.1.2. HDBSCAN

L’algoritmo HDBSCAN (Hierarchical Density-Based Spatial Clustering of Applications with Noise) è un’alternativa all’algoritmo sopra citato per il clustering spaziale di dati con rumore. La particolarità di questo algoritmo è l’essere gerarchico e basato su densità. L’HDBSCAN estende a tutti gli effetti il DBSCAN, eseguendo

(36)

29 quest’ultimo su diversi valori del parametro ε (in input) e integrando il risultato trovato per stabilire un clustering con una migliore stabilità sullo stesso valore di soglia ε. A differenza di DBSCAN, tutto ciò permette a HDBSCAN di individuare cluster con densità variabile e di garantire più robustezza rispetto alla selezione dei parametri. Si ricorda che l’implementazione dell’algoritmo HDBSCAN scelta è quella fornita dalla libreria omonima hdbscan. Sono state considerate due diverse configurazioni dei parametri in input all’HDBSCAN, mostrate nella Tabella 2. Precisamente, le configurazioni differiscono per il parametro, min_samples, che nella prima versione è stato impostato a 3, mentre nella seconda a 10. Gli altri parametri sono stati settati con i seguenti valori: min_cluster_size a 500 e metric a “haversine” (metrica adatta al calcolo delle distanze tra punti su una sfera).

CONF. 1 (v1) CONF. 2 (v2)

min_samples 3 10

min_cluster_size 500 500

metric haversine haversine

Tabella 2: configurazioni dei parametri dell’algoritmo HDBSCAN.

In seguito, si farà riferimento alla prima configurazione con la sigla v1 e alla seconda con la sigla v2.

5.1.2. Altri tipi di distribuzione

In merito agli algoritmi di generazione delle posizioni con divisione dello spazio “a griglia” ed a quello di generazione di posizioni casuali è necessario precisare alcune limitazioni imposte nel calcolo.

La generazione casuale di posizioni per la collocazione degli edge fissi è stata vincolata in modo tale da fissare la distanza minima tra ogni edge a 500 metri. Inoltre, sia per la generazione casuale sia per la distribuzione a griglia l’area della città di Bologna nella quale posizionare gli edge è stata circoscritta al centro della città, dove sono concentrate la maggior parte delle rilevazioni del dataset e dove anche l’output dell’elaborazione

(37)

30 di tutti gli algoritmi di clustering ha individuato approssimativamente la posizione degli edge fissi. Il perimetro, mostrato dalla Figura 6, è rappresentato con una forma rettangolare, larga 3.5 km e alta 3 km.

Figura 6: bounding-box dello spazio per la distribuzione degli edge fissi.

5.2. Selezione degli edge mobili

Nel Capitolo 3 è stato delineato l’approccio scelto per la selezione degli M2EC. Tale processo è composto da due fasi: dapprima di ricavano le comunità che gli utenti formano nella rete sociale ricavata a partire dal dataset a disposizione; poi si seleziona, per ogni comunità, il nodo che risulta essere più sociale.

L’algoritmo proposto per la selezione degli edge mobili è articolato come descritto dalla Figura 7. Sono previsti due valori in input: la lista di comunità individuate e il numero desiderato di M2_{EC. L’output prodotto dall’algoritmo è la lista di M}2_{EC. In} prima battuta, si filtrano le comunità in input in modo tale che da averne al massimo una quantità pari al numero di edge mobili specificato in input. Tali comunità sono qualificate con l’appellativo top. Successivamente, per ogni comunità top si eseguono due passi. Per prima cosa, si calcola la misura di centralità di ogni nodo nella comunità. In seguito, per ogni comunità top viene eletto M2EC il nodo con il valore di centralità più alto; nel caso in cui tale nodo sia uno degli edge mobili selezionati nelle iterazioni

(38)

31 precedenti, si procede seguendo l’ordinamento definito selezionando un ulteriore nodo della comunità. Senza perdita di generalità, nel caso in cui tutti i nodi risultino già essere stati eletti per rivestire il ruolo di M2EC, non viene selezionato alcun ulteriore edge mobile. Tale situazione può verificarsi quando un nodo appartiene a diverse comunità.

Nelle sezioni successive si presentano gli algoritmi scelti per l’implementazione dei passaggi descritti.

5.2.1. Individuazione delle comunità

Lo strumento utilizzato per l’individuazione delle comunità è TILES, un algoritmo che estrae comunità, possibilmente sovrapposte, da un grafo dinamico, tenendo traccia della loro evoluzione nel tempo e seguendo una procedura iterativa. L’algoritmo attua

Input:

lista di comunità, lc;

numero di M2_EC_{desiderato, n_m2ec.}

Output:

lista di nodi M2EC, lm2ec.

Algoritmo: top_c = calcoloComunitaTop(lc) foreach tc in top_c: foreach n in tc: calcoloCentralita(n) lm2ec += calcoloM2EC(tcs) return lm2ec Funzionalità ausiliarie:

calcoloComunitaTop(): calcola le migliori n_m2ec comunità; calcoloCentralita(n): calcola la misura di centralità del nodo n;

calcoloM2EC(tc): calcola il nodo con il più alto valore di misura di centralità in tc (se già presente in lm2ec, viene considerato il secondo nodo con valore

più alto, e così via; se tutti i nodi in tc sono già presenti in lm2ec, alla lista non viene aggiunto alcun ulteriore edge mobile).

(39)

32 una strategia a “effetto domino”, ricalcolando l’appartenenza dei nodi alle comunità ad ogni iterazione, senza imporre alcuna soglia temporale nel calcolo delle partizioni della rete e nel processo di estrazione delle comunità. Esistono molti algoritmi per identificare comunità su reti statiche, che non cambiano nel tempo; tuttavia, le reti sociali sono realtà dinamiche e in tali scenari la ricerca statica di comunità non riesce a identificare partizioni del grafo semanticamente coerenti con le informazioni temporali espresse dai dati. La scelta di TILES è avvalorata dal fatto che l’oggetto di studio è esattamente una rete sociale, che evolve nel tempo.

5.2.2. Calcolo delle comunità top

Dopo aver calcolato utilizzando TILES le comunità di utenti cosiddette strong, si procede con il passo seguente. Si dispongono tali comunità secondo un ordinamento ascendente in base alla somma delle grandezze degli ego-set dei nodi che le compongono. In funzione di questo ordinamento, sono mantenute le comunità strong con valore più alto e scartate le altre.

L’ego-set è un insieme di nodi della rete con determinate proprietà e rappresenta la caratteristica discriminante per classificare i nodi delle comunità strong sulla base dei principi definiti per la selezione dei nodi M2EC. Per il calcolo dell’ego-set di un nodo n si considerano inizialmente tutti i record in cui il nodo n è presente, in seguito, per ogni nodo m con cui n entra in contatto, si calcolano le durate delle connessioni instaurate. Tutti i nodi m che hanno almeno una connessione con n di durata maggiore o uguale a 30 minuti sono inseriti nell’ego-set del nodo n. La soglia dei 30 minuti è stata decisa dopo un’accurata serie di esperimenti al fine di garantire risultati in linea con gli obiettivi di questo studio, ma consapevoli che in contesti reali di piattaforme MEC integrate a piattaforme MCS tale soglia potrebbe risultare troppo elevata, in quanto anche un breve incontro (intenzionale o meno) tra due o più persone permetterebbe uno scambio di informazioni completo. Tuttavia, si può ipotizzare che connessioni di durata maggiore siano più stabili rispetto a connessioni di durata minore, per questo nel processo di selezione degli edge mobili sono state ragionevolmente preferite le prime.

(40)

33 Una nota sul calcolo della durata delle connessioni. Gli estremi del periodo di osservazione descritto sono considerati come limite inferiore e limite superiore. Quindi, nel caso in cui nel dataset l’ultimo record relativo ai nodi n e m sia una connessione di tipo “up”, la durata della connessione sarà pari all’arco temporale compreso tra il momento in cui la connessione viene instaurata e il limite superiore dell’intervallo di osservazione definito. Diversamente, nel caso in cui nel dataset il primo record relativo ai nodi n e m sia una connessione di tipo “down”, la durata della connessione sarà pari all’arco temporale compreso tra il limite inferiore dell’intervallo di osservazione e il momento in cui la connessione termina.

5.2.3. Calcolo della misura di centralità

L’ultima fase da discutere è relativa al calcolo della misura di centralità di un nodo. Tale valore non è altro che una proprietà descrittiva di una rete, che caratterizza un nodo e la rete sociale nella quale questo si colloca. Sono state selezionate e testate due diverse misure di centralità: betweenness centrality ed eigenvector centrality.

Nella teoria dei grafi, la betweenness centrality è una misura di centralità di un nodo in un grafo basata sui cammini. Per ogni coppia di nodi in un grafo connesso, esiste almeno un cammino, tra tutti i possibili cammini, tale che il numero di archi attraversati (per un grafo non pesato) oppure la somma dei pesi degli archi attraversati (per un grafo pesato) è minimo. In breve, la betweenness centrality di un nodo è il numero di cammini minimi che attraversano tale nodo. Nella teoria delle reti, questo valore rappresenta il grado di interazione che un nodo ha con gli altri nodi della rete. Ad esempio, un nodo con maggiore centralità in una rete sociale risulta avere un maggior numero di connessioni con altri nodi e quindi la possibilità di scambiare più informazioni. Nella teoria dei grafi, la eigenvector centrality è una misura dell’influenza che ha un nodo in una rete. Il valore viene assegnato ad ogni nodo della rete in base al seguente principio: connessioni dirette con nodi aventi alti valori di centralità contribuiscono in modo maggiore rispetto a connessioni dirette con nodi aventi bassi valori di centralità all’incremento del valore di centralità del nodo in questione. Tale misura di centralità differisce dalla precedente in quanto non è basata sulla morfologia della rete. Infatti,