Message routeing and percolation in interference limited multihop networks
András Tóbiás · DepositOnce · 2019
This thesis consists of two main parts. In the first part, we investigate a probabilistic model for routeing of messages in relay-augmented multihop ad-hoc networks, where each transmitter sends one message to the origin. Given the (random) transmitter locations, we weight the family of random, uniformly distributed message trajectories by an exponential probability weight, favouring trajectories with low interference (measured in terms of signal-to-interference ratio) and trajectory families with little congestion (measured in terms of the number of pairs of hops using the same relay). Under the resulting Gibbs distribution, the system targets the best compromise between entropy, interference, and congestion for a common welfare, instead of an optimization of the individual trajectories. We also discuss a game-theoretic relation of our Gibbsian model with a joint optimization of message trajectories opposite to a selfish optimization. In the limit of high spatial density of users, we describe the totality of all the message trajectories in terms of empirical measures. Employing large deviations arguments, we derive a characteristic variational formula for the limiting free energy and analyse the minimizer of the formula, which describe the most likely shape of the trajectory flow. The empirical measures of the message trajectories well describe the interference, but not the congestion; the latter requires introducing an additional empirical measure. Our results remain valid under replacing the two penalization terms with more general functionals of these two empirical measures. In the special case where congestion is not penalized, we derive qualitative properties of this minimizer. We analytically identify the emerging typical scenarios in three extreme regimes. We analyse the typical number of hops and the typical length of a hop, and the deviation of the trajectory from the straight line, (1) in the limit of a large communication area and large distances, and (2) in the limit of a strong interference weight. In both regimes, the typical trajectory approaches a straight line quickly, in regime (1) with equal hop lengths. Interestingly, in regime (1), the typical length of a hop diverges logarithmically in the distance of the transmitter to the origin. We further analyse (3) local and global repulsive effects of a densely populated subarea on the trajectories. Our findings are illustrated by numerical examples. In the second part of the thesis, we study signal-to-interference plus noise ratio (SINR) percolation for Cox point processes, i.e., Poisson point processes with a random intensity measure. SINR percolation was first studied by Dousse et al. in the case of a two-dimensional Poisson point process. It is a version of continuum percolation where the connection between two points depends on the locations of all points of the point process. Continuum percolation for Cox point processes was recently studied by Hirsch, Jahnel, and Cali. We study the SINR graph model for a stationary Cox point process in two or higher dimensions. We show that under suitable moment or boundedness conditions on the path-loss function and the intensity measure, this graph has an infinite connected component if the spatial density of points is large enough and the interferences are sufficiently reduced (without vanishing). This holds in all dimensions larger than 1 if the intensity measure is asymptotically essentially connected, and also if the intensity measure is only stabilizing but the connection radius is large. A prominent example of the intensity measure is the two-dimensional Poisson--Voronoi tessellation. We show that its total edge length in a given square has all exponential moments. We conclude that its SINR graph has an infinite cluster if the path-loss function is bounded and has a power-law decay of exponent at least 3. Both models investigated in the thesis describe multihop networks where the signal-to-interference (plus noise) ratio is decisive for determining the quality of service. Based on these properties, we conclude the thesis with establishing relations between the two models and the recent work by Hirsch, Jahnel, Keeler, and Patterson about probabilities of frustration events in highly dense interference limited relay-augmented ad-hoc networks. We also investigate how the choice of path-loss function influences the results of our thesis and preliminary work, and we discuss the most relevant open questions related to our two main subjects.