  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 we 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, we consider an ad hoc network with
half-duplex radios that uses multihop routing and slotted ALOHA for the MAC
contention and introduce a random dynamic multi-digraph to model its
connectivity. We first provide analytical results about the degree distribution
of the graph. Next, defining the path formation time as the minimum time
required for a causal path to form between the source and destination on the
dynamic graph, we derive the distributional properties of the connection delay
using techniques from first-passage percolation and epidemic processes. We
consider the giant component of the network formed when communication is
noise-limited (by neglecting interference). Then, in the presence of
interference, we prove that the delay scales linearly with the
source-destination distance on this giant component. We also provide simulation
results to support the theoretical results.
