Beyond geometry: towards fully realistic wireless models

DOI10.1145/2611462.2611476MaRDI QIDQ2943635zbMATH OpenOpenAlexFDO

Authors Marijke Hans L. Bodlaender, Magnús M. Halldórsson

Publication date 3 September 2015

Published in Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

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

zbMATH Keywords

capacitydistributed algorithmswireless networksSINR

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Distributed algorithms (68W15) Communication networks in operations research (90B18)

Abstract: Signal-strength models of wireless communications capture the gradual fading of signals and the additivity of interference. As such, they are closer to reality than other models. However, nearly all theoretic work in the SINR model depends on the assumption of smooth geometric decay, one that is true in free space but is far off in actual environments. The challenge is to model realistic environments, including walls, obstacles, reflections and anisotropic antennas, without making the models algorithmically impractical or analytically intractable. We present a simple solution that allows the modeling of arbitrary static situations by moving from geometry to arbitrary decay spaces. The complexity of a setting is captured by a metricity parameter Z that indicates how far the decay space is from satisfying the triangular inequality. All results that hold in the SINR model in general metrics carry over to decay spaces, with the resulting time complexity and approximation depending on Z in the same way that the original results depends on the path loss term alpha. For distributed algorithms, that to date have appeared to necessarily depend on the planarity, we indicate how they can be adapted to arbitrary decay spaces. Finally, we explore the dependence on Z in the approximability of core problems. In particular, we observe that the capacity maximization problem has exponential upper and lower bounds in terms of Z in general decay spaces. In Euclidean metrics and related growth-bounded decay spaces, the performance depends on the exact metricity definition, with a polynomial upper bound in terms of Z, but an exponential lower bound in terms of a variant parameter phi. On the plane, the upper bound result actually yields the first approximation of a capacity-type SINR problem that is subexponential in alpha.

Recommendations

• Wireless capacity with oblivious power in general metrics
• A constant-factor approximation for wireless capacity maximization with power control in the SINR model
• SINR diagrams, towards algorithmically usable SINR models of wireless networks
• Wireless capacity with arbitrary gain matrix
• Conflict graphs and the SINR-capacity of the mean power scheme

Cited in

(8)

• Effective Wireless Scheduling via Hypergraph Sketches
• Deterministic protocols in the SINR model without knowledge of coordinates
• Distributed bare-bones communication in wireless networks
• The power of oblivious wireless power
• Spanning trees with edge conflicts and wireless connectivity
• Token traversal in ad hoc wireless networks via implicit carrier sensing
• Network design under general wireless interference
• Limitations of current wireless link scheduling algorithms

This page was built for publication: Beyond geometry: towards fully realistic wireless models

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