Metriche di interesse

Analizziamo ora le metriche utilizzate per descrivere le caratteristiche temporali e so- ciali delle tracce di co-locazione,e le metriche utilizzate per descrivere le performance degli algoritmi di routing e degli algoritmi di service discovery.

4.7.1

Analisi delle tracce di co-locazione

Tale analisi propedeutica `e fondamentale in quanto permette di comprendere la com-

plessit`a dello scenario e di conseguenza permette di comprendere il comportamento e le performance degli algoritmi di service discovery. Tale analisi descrive le caratteristiche sociali e temporali, e quindi le opportunit`a di interazione tra i nodi della rete. Una traccia caratterizzata da molte interazioni fra i nodi permette di ottenere performance migliori, rispetto ad una traccia caratterizzata da poche interazioni, in quanto si creano maggiori opportunit`a di comunicazione.

La metrica usata per analizzare le caratteristiche sociali delle tracce `e la cardinalit`a

media delle comunit`a rilevate da ciascun nodo, usando i risultati ottenuti dall’al-

goritmo di community detection, K-Clique. In particolare si vuole evidenziare come la mobilit`a in due diverse aree considerando due diversi campioni (area limitata con un campione omogeneo e area molto vasta con un campione eterogeneo) influenza la tendenza dei nodi nell’interagire tra loro.

Le metriche usate per analizzare le caratteristiche temporali delle tracce permettono di evidenziare i legami che si instaurano tra i nodi, in particolare la regolarit`a, la fre- quenza e la densit`a degli incontri nel tempo come la familiarit`a tra i nodi. In Figura 2.3

avevamo visto come la frequenza e la familiarit`a sono due metriche fondamentali per

permettere una classificazione dei legami tra i nodi.

• Numero di contatti nel tempo: Questa metrica rappresenta la distribuzione del numero dei contatti tra i nodi nel tempo, in particolare ad ogni ora, e indica l’attivit`a sociale dei nodi (quanto si incontrano i nodi e quando). Da questa distri- buzione si evidenzia gli intervalli temporali in cui si ha una maggiore interazione e gli intervalli in cui se ne ha meno.

• Durata dei contatti: Questa metrica misura la distribuzione delle durate medie dei contatti tra i nodi, ossia il tempo che intercorre tra l’inizio e la fine di un contat- to. In Figura 4.17 la durata del contatto tra i e j `e rappresentato dall’intervallo tra t0 e t1 e tra t2 e t3. La durata dei contatti indica la quantit`a di dati che `e possibile

trasferire ad ogni opportunit`a di contatto: se si hanno molti contatti brevi sar`a possibile trasferire meno dati. Inoltre `e un indicatore della familiarit`a tra i nodi. • Tempi di intercontatto: Questa metrica misura la distribuzione dei tempi di

intercontatto tra coppie di nodi, ossia il tempo che intercorre tra due contatti successivi. In Figura 4.17 il tempo di intercontatto tra i e j `e rappresentato dal- l’intervallo tra t1 e t2. Il tempo di intercontatto `e un indicatore della regolarit`a dei

contatti che influenza la frequenza con cui vengono trasferiti i dati tra i dispositivi.

i

j

i

j

t

t

t

t

Figura 4.17: Durata dei contatti e dei intercontatti tra due nodi

4.7.2

Valutazione degli algoritmi di routing

Prima di valutare le performance degli algoritmi di routing utilizzati, definiamo la notazione necessaria alla valutazione:

• Indichiamo con M il numero di messaggi generati nella rete e con Md il numero

dei messaggi consegnati con successo tale per cui Md⊆ M .

• Indichiamo con ti il tempo in cui mi ∈ Md `e stato creato e con t0i il tempo in cui

mi ∈ Md`e stato consegnato al destinatario tale per cui t0i > ti.

Le metriche utilizzate per valutare le performance e confrontare gli algoritmi di routing sono le seguenti [38]:

• Message Delivery :

Questa metrica indica il rapporto dei messaggi consegnati e di quelli creati, in particolare `e dato da:

|M

|

|M |

(4.7)

Il significato della message delivery `e quanto sia efficiente il protocollo di routing nel consegnare a destinazione tutti i messaggi creati.

• Message Delay :

Questa metrica misura il tempo richiesto per consegnare un messaggio dal nodo sorgente al nodo destinatario, definito come ritardo dato da:

(t

− t

)

(4.8)

Il significato della message delay `e quanto sia efficiente il protocollo di routing nel consegnare i messaggi con un ritardo minimo.

Le due metriche descritte sono molto importanti per valutare le performance di un protocollo di routing e sono fortemente influenzate dalla mobilit`a dei nodi. Infatti un algoritmo pu`o avere un alto tasso di successo nelle consegne con una determinata trac- cia di co-locazione e un tasso molto basso con un’altra traccia.

L’obiettivo di un protocollo `e quello di fornire una strategia di diffusione delle in- formazioni che massimizzi il tasso di consegna, message delivery, e allo stesso tempo minimizzi i ritardi, message delay.

4.7.3

Valutazione degli algoritmi di service discovery

Prima di valutare le performance degli algoritmi di service discovery utilizzati, definia- mo la notazione necessaria alla valutazione:

• Sia A il numero di advertisement memorizzati nelle cache del nodo ni e A0il numero

di advertisement di interesse per il nodo ni memorizzati all’interno della sua cache:

A0 ⊆ A ⊆ CHi.

• Sia QCH il numero di query generate da un nodo ni che hanno ricevuto risposta

accedendo alla sua cache CHi e Q il numero totale di query generate da ni.

• Sia QA il numero totale di query che hanno ricevuto risposta, ti il tempo in

cui la query qi ∈ QA viene creata e t0i il tempo in cui ricevo un advertisement

corrispondente a qi ∈ QA per cui t0i > ti.

Le metriche utilizzate per descrivere le performance degli algoritmi di service discovery sono le seguenti:

• Accuracy :

Questa metrica misura il rapporto tra il numero di advertisement memorizzati all’interno della cache di un nodo ni che sono di suo interesse, e il numero totale

di advertisement memorizzati nella cache:

|A

|

|A|

(4.9)

L’accuracy indica l’efficacia di un algoritmo di service discovery nel propagare solo i servizi d’interesse per i nodi evitando di diffondere servizi che i nodi potrebbero non usare. Tale valore `e compreso tra [0,1]: un valore pari a 0 indica il caso pessimo in cui nessun servizio che interessa al nodo ni `e memorizzato all’interno della sua

cache; un valore pari a 1 indica il caso ottimo in cui il nodo nimemorizza solamente

servizi di cui `e interessato. • Proactivity :

Questa metrica misura il rapporto tra il numero di volte che un nodo trova un advertisement per un servizio che necessita gi`a memorizzato nella cache e il numero di volte che il nodo genera una query per quel servizio:

|Q

|

|Q|

(4.10)

La proactivity indica l’efficacia dell’algoritmo di service discovery nel ridurre il numero di query per ottenere un advertisement. Il valore `e compreso tra [0,1]: un valore pari a 0 indica il caso pessimo in cui ogni volta che un nodo necessita di un servizio deve diffondere una richiesta; un valore pari a 1 indica il caso ottimo in cui ogni volta che un nodo necessita di un servizio lo trova all’interno della propria cache.

• Query Response Time :

Questa metrica misura il tempo medio che intercorre tra l’invio di una query per un servizio e la ricezione del primo advertisement corrispondente a tale query:

(t

− t

)

(4.11)

La query response time indica l’efficacia dell’algoritmo di service discovery nel fornire ad un nodo il servizio ricercato nel minor tempo possibile.

• Service Cache:

Questa metrica misura il numero medio di advertisement che un nodo memorizza all’interno della sua cache nel tempo. La dimensione della service cache dei nodi ci

informa dello spazio di memoria necessario per un nodo ad eseguire l’algoritmo di service discovery.

• Forwarding Cache :

Questa metrica misura il numero medio di advertisement che un nodo riceve ma che non sono diretti a lui e che memorizza all’interno della forwarding cache. La dimen- sione media della forwarding cache ci informa dello spazio di memoria necessario per un nodo ad eseguire l’algoritmo di service discovery.