How well can graphs represent wireless interference?

DOI10.1145/2746539.2746585MaRDI QIDQ2941559zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson, Tigran Tonoyan

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.1263

zbMATH Keywords

conflict graphsschedulingSINRwireless networks

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Network protocols (68M12) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Efficient use of a wireless network requires that transmissions be grouped into feasible sets, where feasibility means that each transmission can be successfully decoded in spite of the interference caused by simultaneous transmissions. Feasibility is most closely modeled by a signal-to-interference-plus-noise (SINR) formula, which unfortunately is conceptually complicated, being an asymmetric, cumulative, many-to-one relationship. We re-examine how well graphs can capture wireless receptions as encoded in SINR relationships, placing them in a framework in order to understand the limits of such modelling. We seek for each wireless instance a pair of graphs that provide upper and lower bounds on the feasibility relation, while aiming to minimize the gap between the two graphs. The cost of a graph formulation is the worst gap over all instances, and the price of (graph) abstraction is the smallest cost of a graph formulation. We propose a family of conflict graphs that is parameterized by a non-decreasing sub-linear function, and show that with a judicious choice of functions, the graphs can capture feasibility with a cost of $O(lo{g}^{\ast }Delta)$, where $Delta$ is the ratio between the longest and the shortest link length. This holds on the plane and more generally in doubling metrics. We use this to give greatly improved $O(lo{g}^{\ast }Delta)$-approximation for fundamental link scheduling problems with arbitrary power control. We explore the limits of graph representations and find that our upper bound is tight: the price of graph abstraction is $Omega(lo{g}^{\ast }Delta)$. We also give strong impossibility results for general metrics, and for approximations in terms of the number of links.

Recommendations

• Conflict graphs and the SINR-capacity of the mean power scheme
• Effective Wireless Scheduling via Hypergraph Sketches
• Conflict graphs and the capacity of the mean power scheme
• Limitations of current wireless link scheduling algorithms
• Wireless scheduling with power control

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(13)

• Conflict graphs and the capacity of the mean power scheme
• Limitations of current wireless link scheduling algorithms
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Network design under general wireless interference
• Connectivity of soft random geometric graphs over annuli
• Spanning trees with edge conflicts and wireless connectivity
• Mean-field limits for large-scale random-access networks
• A note on signal to interference ratio feasibility problems
• The power of oblivious wireless power
• Token traversal in ad hoc wireless networks via implicit carrier sensing
• Reception capacity: definitions, game theory and hardness
• Generalized disk graphs
• Conflict graphs and the SINR-capacity of the mean power scheme

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: How well can graphs represent wireless interference?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941559)