An overarching issue in resource management of wireless networks is assessing their capacity: How much communication can be achieved in a network, utilizing all the tools available: power control, scheduling, routing, channel assignment and rate adjustment? We propose the first framework for approximation algorithms in the physical model of wireless interference that addresses these questions in full. The approximations obtained are at most doubly logarithmic in the link length and rate diversity. Where previous bounds are known, this gives an exponential improvement (or better). A key contribution is showing that the complex interference relationship of the physical model can be simplified, at a small cost, into a novel type of amenable conflict graphs. We also show that the approximation obtained is provably the best possible for any conflict graph formulation.
The idea of modeling SINR with graphs arose early. Disc graphs were shown to be insufficient in general @cite_19 . However, it was observed rather early that equilength sets of links can be captured with unit disc graphs @cite_12 . In fact, a sandwiching result with constant tightness holds for equilength links @cite_59 . For links of widely varying lengths, less was known: a @math -tight construction was given in @cite_59 .
@cite_19 @cite_59 @cite_12
2950288120 1993294649 2065248207 2889098578
We give algorithms with constant-factor performance guarantees for several capacity and throughput problems in the SINR model. The algorithms are all based on a novel LP formulation for capacity problems. First, we give a new constant-factor approximation algorithm for selecting the maximum subset of links that can be scheduled simultaneously, under any non-decreasing and sublinear power assignment. For the case of uniform power, we extend this to the case of variable QoS requirements and link-dependent noise terms. Second, we approximate a problem related to cognitive radio: find a maximum set of links that can be simultaneously scheduled without affecting a given set of previously assigned links. Finally, we obtain constant-factor approximation of weighted capacity under linear power assignment. We consider the problem of encoding graphs with n vertices and m edges compactly supporting adjacency, neighborhood and degree queries in constant time in the @Q(logn)-bit word RAM model. The adjacency query asks whether there is an edge between two vertices, the neighborhood query reports the neighbors of a given vertex in constant time per neighbor, and the degree query reports the number of incident edges to a given vertex. We study the problem in the context of succinctness, where the goal is to achieve the optimal space requirement as a function of n and m, to within lower order terms. We prove a lower bound in the cell probe model indicating it is impossible to achieve the information-theory lower bound up to lower order terms unless the graph is either too sparse (namely, m=o(n^@d) for any constant @d>0) or too dense (namely m=@w(n^2^-^@d) for any constant @d>0). Furthermore, we present a succinct encoding of graphs supporting aforementioned queries in constant time. The space requirement of the encoding is within a multiplicative 1+@e factor of the information-theory lower bound for any arbitrarily small constant @e>0. This is the best achievable space bound according to our lower bound where it applies. The space requirement of the representation achieves the information-theory lower bound tightly within lower order terms where the graph is very sparse (m=o(n^@d) for any constant @d>0), or very dense (m>n^2 lg^1^-^@dn for an arbitrarily small constant @d>0). In this paper we study a model for ad-hoc networks close enough to reality as to represent existing networks, being at the same time concise enough to promote strong theoretical results. The Quasi Unit Disk Graph model contains all edges shorter than a parameter d between 0 and 1 and no edges longer than 1.We show that .in comparison to the cost known on Unit Disk Graphs .the complexity results in this model contain the additional factor 1 d2. We prove that in Quasi Unit Disk Graphs flooding is an asymptotically message-optimal routing technique, provide a geometric routing algorithm being more efficient above all in dense networks, and show that classic geometric routing is possible with the same performance guarantees as for Unit Disk Graphs if d = 1 v2. 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 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 in two dimensions 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 some 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.