We study a slotted version of the Aloha Medium Access (MAC) protocol in a Mobile Ad-hoc Network (MANET). Our model features transmitters randomly located in the Euclidean plane, according to a Poisson point process and a set of receivers representing the next-hop from every transmitter. We concentrate on the so-called outage scenario, where a successful transmission requires a Signal-to-Interference-and-Noise (SINR) larger than some threshold. We analyze the local delays in such a network, namely the number of times slots required for nodes to transmit a packet to their prescribed next-hop receivers. The analysis depends very much on the receiver scenario and on the variability of the fading. In most cases, each node has finite-mean geometric random delay and thus a positive next hop throughput. However, the spatial (or large population) averaging of these individual finite mean-delays leads to infinite values in several practical cases, including the Rayleigh fading and positive thermal noise case. In some cases it exhibits an interesting phase transition phenomenon where the spatial average is finite when certain model parameters (receiver distance, thermal noise, Aloha medium access probability) are below a threshold and infinite above. To the best of our knowledge, this phenomenon, which we propose to call the wireless contention phase transition, has not been discussed in the literature. We comment on the relationships between the above facts and the heavy tails found in the so-called "RESTART" algorithm. We argue that the spatial average of the mean local delays is infinite primarily because of the outage logic, where one transmits full packets at time slots when the receiver is covered at the required SINR and where one wastes all the other time slots. This results in the "RESTART" mechanism, which in turn explains why we have infinite spatial average. Adaptive coding offers another nice way of breaking the outage RESTART logic. We show examples where the average delays are finite in the adaptive coding case, whereas they are infinite in the outage case.
The goal of this paper is to increase our understanding of the fundamental performance limits of mobile and Delay Tolerant Networks (DTNs), where end-to-end multi-hop paths may not exist and communication routes may only be available through time and mobility. We use analytical tools to derive generic theoretical upper bounds for the information propagation speed in large scale mobile and intermittently connected networks. In other words, we upper-bound the optimal performance, in terms of delay, that can be achieved using any routing algorithm. We then show how our analysis can be applied to specific mobility and graph models to obtain specific analytical estimates. In particular, in two-dimensional networks, when nodes move at a maximum speed @math and their density @math is small (the network is sparse and surely disconnected), we prove that the information propagation speed is upper bounded by ( @math in the random way-point model, while it is upper bounded by @math for other mobility models (random walk, Brownian motion). We also present simulations that confirm the validity of the bounds in these scenarios. Finally, we generalize our results to one-dimensional and three-dimensional 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, we 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. 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 show that the delay scales linearly with the distance and provide asymptotic results (with respect to time) for the positions of the nodes which are able to receive information from a transmitter located at the origin. We also provide simulation results to support the theoretical results.