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

DOI10.1007/978-3-642-33651-5_8MaRDI QIDQ4909405zbMATH OpenOpenAlexFDO

Authors Tomasz Jurdziński, Dariusz R. Kowalski

Publication date 13 March 2013

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

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

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)

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.

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

Cited in

(11)

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

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)