Go to the content. | Move to the navigation | Go to the site search | Go to the menu | Contacts | Accessibility

| Create Account

Pettarin, Alberto (2012) Graph Models of Information Spreading in Wireless Networks. [Ph.D. thesis]

Full text disponibile come:

[img]
Preview
PDF Document
1506Kb

Abstract (english)

This thesis investigates the structural properties of graph models of wireless networks, where autonomous agents communicate using radios in order to accomplish a predefined task. Ad hoc, sensor, and vehicle networks are perhaps the most familiar examples. The goal of this thesis is the analytical characterization of information spreading in graph models of wireless networks, since this fundamental process is a primitive needed to accomplish more complex tasks.
The well-established graph-based approaches adopted when analyzing
the behavior of “classical” distributed systems (e.g., P2P networks, computing clusters, etc.) fail to generalize to wireless networks, due to several causes, including the stricter physical constraints governing the operation of these systems (e.g., interference on the physical channel or scarce energy/computational resources) and the fact that the topology of the network might be unknown at design time or it might evolve over time.
This thesis shows how to tackle these problems by suitably defining
and rigorously analyzing graph models and graph processes capturing
the structure, evolution and operation of these networks. We present two
reference scenarios.
In the first one we study a family of random graphs known as Bluetooth Topology, which closely model the connectivity of a network built by
the device discovery phase of Bluetooth-like protocols, largely employed
in wireless networks. Formally, the Bluetooth Topology generalizes the
well-known Random Geometric Graph model, introducing a distributed
pruning of the edge set. We investigate the expansion and the diameter of
these graphs, as they quantify the bandwidth and the latency of a wireless
network. We give tight bounds on the expansion and, leveraging on these,
we prove nearly-tight bounds on the diameter. Our results show that the
Bluetooth Topology features the same global level of connectivity of the Random Geometric Graph but requires maintaining much fewer communication links.
Motivated by the recent and rapidly growing interest in mobile systems,
in the second part of the thesis we turn our attention to the dynamics of
information dissemination between agents performing random walks on
a planar grid and communicating over short distances. This setting can
also be employed to study phenomena like the spreading of a disease,
where infections are the result of local interactions between agents. We
prove that, for a sufficiently sparse system, the broadcast time of a message
is independent from the transmission radius; indeed, we show that the
broadcast time is dominated by the time needed for many agents to meet.
Our findings nicely complements previous results that dealt with dense
systems, where there is dependency from the transmission radius. Moreover,
our analysis techniques extend to similar mobility-communication models,
suggesting some interesting further research directions.

Abstract (italian)

Questa tesi studia le proprieta' strutturali di alcuni modelli a grafo di reti
di agenti autonomi che comunicano via radio per completare un prefissato compito. Reti ad hoc, di sensori e veicolari sono forse gli esempi piu' immediati. Lo scopo di questa tesi e caratterizzare la diffusione dell’infor-
mazione in questi modelli a grafo di reti wireless, considerata l’importanza
di questo processo come primitiva fondamentale per realizzare protocolli piu' complessi.
Gli approcci basati su tecniche combinatorie adottati per l’analisi di
sistemi distribuiti “classici”, come le reti P2P o i cluster di calcolo, non
possono essere estesi alle reti wireless, per varie ragioni: ad esempio a
causa dei vincoli fisici che governano il funzionamento di questi sistemi
(interferenza sul canale radio, scarse risorse energetiche/computazionali,
ecc.) e per il fatto che la topologia della rete puo' essere ignota in fase di
progettazione o puo' evolvere nel tempo.
Questa tesi suggerisce come sia possibile affrontare tali problemi tramite
l’opportuna definizione e l’analisi rigorosa di modelli a grafo (o processi
su grafi) che catturino l’evoluzione e il funzionamento delle reti wireless.
Mostriamo come sia possibile applicare quest’approccio a due scenari di
riferimento.
Innanzitutto studiamo una famiglia di grafi random nota come Bluetooth
Topology, che ben rappresenta la connettivita' della rete creata dalla fase di device discovery in protocolli simili al Bluetooth, largamente utilizzati nelle reti wireless. Dal punto di vista formale, la Bluetooth Topology generalizza il ben noto modello Random Geometric Graph, introducendovi una selezione distribuita degli archi. Studiamo l’espansione e il diametro di questi grafi, poiche' quantificano la banda e la latenza della rete. Dimostriamo limiti stretti all’espansione e, sfruttando questa caratterizzazione, diamo dei limiti quasi stretti al diametro. I nostri risultati provano che la Bluetooth Topology presenta lo stesso livello globale di connettivita' del Random Geometric Graph, pur richiedendo molti meno link di comunicazione.
Graph, pur richiedendo molti meno link di comunicazione.
Motivati dal recente crescente interesse verso i sistemi mobili, nella
seconda parte della tesi concentriamo la nostra attenzione sulle dinamiche
di disseminazione dell’informazione tra agenti che effettuano random walk
su una griglia planare e che comunicano su brevi distanze. Questo scenario puo' essere utilizzato per studiare fenomeni come la diffusione di malattie, dove le infezioni sono il risultato di interazioni locali tra gli agenti. Proviamo che, per un sistema sufficientemente sparso, il tempo di broadcast di un messaggio e indipendente dal raggio di trasmissione, dimostrando che esso e' dominato dal tempo necessario affinche' molti agenti si incontrino. I nostri risultati completano l’analisi, apparsa in lavori precedenti, di sistemi densi, dove viceversa vi e' dipendenza del tempo di broadcast dal raggio di trasmissione. Inoltre le nostre tecniche di analisi possono essere estese a modelli di mobilita'-comunicazione simili, suggerendo alcune interessanti linee di ulteriore ricerca.

Statistiche Download - Aggiungi a RefWorks
EPrint type:Ph.D. thesis
Tutor:Pucci, Geppino
Ph.D. course:Ciclo 24 > Scuole 24 > INGEGNERIA DELL'INFORMAZIONE > SCIENZA E TECNOLOGIA DELL'INFORMAZIONE
Data di deposito della tesi:25 January 2012
Anno di Pubblicazione:2012
Key Words:graph models, wireless networks, Bluetooth Topology, Random Geometric Graph, random walks, percolation
Settori scientifico-disciplinari MIUR:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/05 Sistemi di elaborazione delle informazioni
Area 01 - Scienze matematiche e informatiche > INF/01 Informatica
Struttura di riferimento:Dipartimenti > Dipartimento di Ingegneria dell'Informazione
Codice ID:4494
Depositato il:17 Dec 2012 14:11
Simple Metadata
Full Metadata
EndNote Format

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record