Date Added: Mar 2010
In a wireless network the set of transmitting nodes changes frequently because of the MAC scheduler and the traffic load. Previously, connectivity in wireless networks was analyzed using static geometric graphs, and as the authors show leads to an overly constrained design criterion. The dynamic nature of the transmitting set introduces additional randomness in a wireless system that improves the connectivity, and this additional randomness is not captured by a static connectivity graph. In this paper, they consider an ad hoc network with half-duplex radios that uses multi-hop routing and slotted ALOHA for the 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.