Dynamic Connectivity and Path Formation Time in Poisson Networks
The connectivity of wireless networks is commonly analyzed using static geometric graphs. However, with half-duplex radios and due to interference, static or instantaneous connectivity cannot be achieved. It is not necessary, either, since packets take multiple time slots to propagate through the network. For example, if a packet traverses a link in one time slot, it is irrelevant if the next link is available in that time slot also, but it is relevant if the next hope exists in the next time slot. To account for half-duplex constraints and the dynamic changes in the transmitting set of nodes due to MAC scheduling and traffic loads, the authors introduce a random multi-digraph that captures the evolution of the network connectivity in a dynamic fashion.