Dynamic Connectivity and Packet Propagation Delay in ALOHA Wireless Networks
The authors consider an ad hoc network which uses multihop and slotted ALOHA for its MAC contention. They then formulate the minimum time required for a packet to reach the destination from the origin. They define this delay as the minimum time required for a causal path to form between the source and destination. They derive the distributional properties of the connection time using ideas from first passage percolation and epidemic processes. They show that the delay scales linearly with the distance and also provide asymptotic results (w.r.t time) for the positions of the nodes which are able to connect to a transmitter located at the origin. They also provide simulation results to support the theoretical results.