Graph Models of Information Spreading in Wireless Networks
Alberto Pettarin · Padua Research Archive (University of Padova) · 2012
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.