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 ...