Graph Models of Information Spreading in Wireless Networks

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.

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.