Bounds on Information Propagation Delay in Interference-Limited ALOHA Networks

In a wireless network the set of transmitting nodes changes frequently because of the MAC scheduler and the traffic load. Analyzing the connectivity of such a network using static graphs would lead to pessimistic performance results. In this paper, the authors consider an ad hoc network with half-duplex radios that uses multihop routing and slotted ALOHA for the network MAC contention, and introduce a random dynamic multi-digraph to model its connectivity. They first provide analytical results about the degree distribution of the graph.