Loading…
Message routeing and percolation in interference limited multihop networks
Tóbiás, András József
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.
Diese Dissertation besteht aus zwei Hauptteilen. Im ersten Teil analysieren wir ein probabilistisches Modell für Nachrichtenvermittlung in zufälligen dichten Netzwerken, in denen jeder Benutzer genau eine Nachricht zum Ursprung schickt, und Nachrichten von den anderen Benutzern (die ebenso als Relais funktionieren) weitergeleitet werden können. Gegeben die (zufälligen) Orte der Sender, gewichten wir die Familie der zufälligen, gleichverteilten Nachrichtentrajektorien mit einem exponentiellen Wahrscheinlichkeitsgewicht, das Trajektorien mit niedriger Interferenz (gemessen im Sinne der signal-to-interference ratio (SIR)) und Familien von Trajektorien mit kleiner Nachrichtenstauung (gemessen durch die Anzahl der Paare von Hops, die das gleiche Relais benutzen) bevorzugt. Unter der resultierenden Gibbs-Verteilung erzielt das System genau den besten Kompromiss zwischen Entropie, Interferenz und Nachrichtenstauung für das öffentliche Wohl, statt einer Optimierung der individuellen Trajektorien. Wir diskutieren auch eine spieltheoretische Beziehung unseres Modells mit einer gemeinsamen Optimierung der Nachrichtentrajektorien gegenüber einer eigennützigen Optimierung.
Im Grenzwert der hohen räumlichen Dichte der Benutzer beschreiben wir die Gesamtheit von allen Nachrichtentrajektorien im Sinne von empirischen Maßen. Unter der Verwendung der Methode der großen Abweichungen verzweigen wir eine charakterische Variationsformel für die begrenzende freie Energie. Zudem analysieren wir den Minimierer dieser Formel, der die wahrscheinlichste Gestalt des Abflusses der Trajektorien beschreibt. Die empirischen Maße der Nachrichtentrajektorien beschreiben die Interferenz gut, aber nicht die Nachrichtenstauung; letztere benötigt ein zusätzliches empirisches Maß. Unsere Ergebnisse bleiben mit allgemeineren Funktionalen dieser zwei empirischen Maße gültig.
Im Spezialfall, in dem Nachrichtenstauung nicht bestraft wird, beschreiben wir qualitative Eigenschaften dieses Minimierers. Wir bestimmen die entstehenden Szenarien in drei Extremfällen analytisch. Wir analysieren die typische Anzahl der Hops und die typische Länge eines Hops, und die Abweichung der Trajektorie von der Gerade, (1) im Grenzwert eines großen Kommunikationsgebietes und großer Abstände, (2) im Grenzwert eines starken Interferenzgewichtes. In beiden Fällen erreicht die typische Trajektorie die Gerade schnell, im Fall (1) mit gleichen Hoplängen. Interessanterweise divergiert im Fall (1) die typische Länge eines Hops logarithmisch im Abstand vom Ursprung. Wir analysieren weiterhin (3) lokale und globale abstoßende Effekte eines dicht bevölkerten Teilgebietes auf die Trajektorien. Unsere Erkentnisse werden mit numerischen Beispielen illustriert.
Im zweiten Teil der Dissertation untersuchen wir die signal-to-interference plus noise ratio (SINR)-Perkolation für Cox-Punktprozesse, d. h. Poisson-Punktprozesse mit zufälligem Intensitätsmaß. Die SINR-Perkolation wurde zuerst von Dousse et al. studiert, für den Fall des zweidimensionalen Poisson-Punktprozesses. Sie ist eine Version der kontinuerlichen Perkolation, wobei die Verbindung zwischen zwei Punkten von den Orten aller Punkte des Punktprozesses abhängt. Die kontinuerliche Perkolation für Cox-Punktprozesse wurde vor Kurzem von Hirsch, Jahnel und Cali studiert.
Wir studieren den SINR-Graphen eines stationären Cox-Punktprozesses in zwei oder mehr Dimensionen. Wir zeigen, dass dieser Graph unter bestimmten Annahmen an die Pfadverlust-Funktion bzw. das Intensitätsmaß, wie Beschränktheit oder Existenz von exponentiellen Momenten, eine unbeschränkte zusammenhängende Komponente hat, wenn die räumliche Dichte der Punkte groß genug ist und die Interferenzen genügend reduziert sind (ohne zu verschwinden). Dies gilt in allen Dimensionen größer als eins, wenn das Intensitätsmaß asymptotisch wesentlich zusammenhängend (asymptotically essentially connected) ist oder auch wenn das Intensitätsmaß nur stabilisierend ist, aber der Verbindungsradius groß ist.
Ein prominentes Beispiel des Intensitätsmaßes ist die zweidimensionelle Poisson-Voronoi-Parkettierung. Wir zeigen, dass ihre totale Kantenlänge in einem gegebenen Quadrat alle exponentiellen Momente hat. Wir folgern, dass ihr SINR-Graph ein unendliches Cluster hat, wenn die Pfadverlust-Funktion beschränkt ist und ihr Verfall nach einem Potenzgesetz mit Exponent nicht kleiner als 3 erfolgt.
Die beiden Modelle, die wir in dieser Dissertation betrachten, beschreiben Netzwerke mit mehreren Hops, wobei die SI(N)R für die Empfangsqualität entscheidend ist. Auf der Grundlage von diesen Eigenschaften schließen wir die Dissertation mit der Etablierung von Beziehungen zwischen den zwei Modellen und der kürzlich erschienenen Arbeit von Hirsch, Jahnel, Keeler und Patterson über die Wahrscheinlichkeiten von Frustrationsereignissen in dichten interferenzbegrenzten zufälligen Netzwerken mit Relais. Wir untersuchen auch, wie die Auswahl der Pfadverlust-Funktion die Ergebnisse dieser Dissertation und einiger vorläufiger Arbeiten beeinflusst, und wir diskutieren die wichtigsten offenen Fragen im Zusammenhang zu unseren zwei Hauptthemen.
