Distributed backbone structure for algorithms in the SINR model of wireless networks

DOI10.1007/978-3-642-33651-5_8zbMATH Open1377.68022arXiv1207.0602OpenAlexW1914182992MaRDI QIDQ4909405FDOQ4909405

Authors: Tomasz Jurdziński, Dariusz R. Kowalski 

Publication date: 13 March 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: The Signal-to-Interference-and-Noise-Ratio (SINR) physical model is one of the legitimate models of wireless networks. Despite of the vast amount of study done in design and analysis of centralized algorithms supporting wireless communication under the SINR physical model, little is known about distributed algorithms in this model, especially deterministic ones. In this work we construct, in a deterministic distributed way, a backbone structure on the top of a given wireless network, which can be used for transforming many algorithms designed in a simpler model of ad hoc broadcast networks without interference into the SINR physical model with uniform power of stations, without increasing their asymptotic time complexity. The time cost of the backbone data structure construction is only O(Delta polylog n) rounds, where Delta is roughly the inverse of network density and n is the number of nodes in the whole network. The core of the construction is a novel combinatorial structure called SINR-selector, which is introduced and constructed in this paper. We demonstrate the power of the backbone data structure by using it for obtaining efficient O(D+Delta polylog n)-round and O(D+k+Delta polylog n)-round deterministic distributed solutions for leader election and multi-broadcast, respectively, where D is the network diameter and k is the number of messages to be disseminated.

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

Recommendations

• Distributed bare-bones communication in wireless networks
• Broadcast in the Ad Hoc SINR Model
• Deterministic protocols in the SINR model without knowledge of coordinates
• Distributed deterministic broadcasting in uniform-power ad hoc wireless networks
• Distributed connectivity of wireless networks

zbMATH Keywords

distributed algorithmsleader electionwireless networksSINRbackbone structuremulti-message broadcast

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Distributed algorithms (68W15) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Cited In (11)

• New selectors and locally thin families with applications to multi-access channels supporting simultaneous transmissions
• Nearly optimal local broadcasting in the SINR model with feedback
• Contention resolution on a fading channel
• Deterministic protocols in the SINR model without knowledge of coordinates
• Distributed bare-bones communication in wireless networks
• Broadcasting in an Unreliable SINR Model.
• Message and time efficient multi-broadcast schemes
• Fully dynamic MIS in uniformly sparse graphs
• Dynamic multiple-message broadcast: bounding throughput in the affectance model
• On the complexity of neighbourhood learning in radio networks
• Token traversal in ad hoc wireless networks via implicit carrier sensing

This page was built for publication: Distributed backbone structure for algorithms in the SINR model of wireless networks

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