Distributed connectivity of wireless networks

DOI10.1145/2332432.2332469zbMATH Open1301.68255arXiv1205.5164OpenAlexW1966601609MaRDI QIDQ2933796FDOQ2933796

Authors: Magnús M. Halldórsson, Pradipta Mitra 

Publication date: 5 December 2014

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

Abstract: We consider the problem of constructing a communication infrastructure from scratch, for a collection of identical wireless nodes. Combinatorially, this means a) finding a set of links that form a strongly connected spanning graph on a set of $n$ points in the plane, and b) scheduling it efficiently in the SINR model of interference. The nodes must converge on a solution in a distributed manner, having no means of communication beyond the sole wireless channel. We give distributed connectivity algorithms that run in time $O(poly(logDelta,logn))$, where $Delta$ is the ratio between the longest and shortest distances among nodes. Given that algorithm without prior knowledge of the instance are essentially limited to using uniform power, this is close to best possible. Our primary aim, however, is to find efficient structures, measured in the number of slots used in the final schedule of the links. Our main result is algorithms that match the efficiency of centralized solutions. Specifically, the networks can be scheduled in $O(logn)$ slots using (arbitrary) power control, and in $O(logn(loglogDelta+logn))$ slots using a simple oblivious power scheme. Additionally, the networks have the desirable properties that the latency of a converge-cast and of any node-to-node communication is optimal $O(logn)$ time.

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

Recommendations

• Connectivity of Heterogeneous Wireless Networks
• Connectivity and aggregation in multihop wireless networks
• Dispersion with connectivity in wireless mesh networks
• Distributed link scheduling in wireless networks
• Distributed bare-bones communication in wireless networks
• Distributed contention resolution in wireless networks
• Distributed algorithms for connected domination in wireless networks
• Connectivity of Large Wireless Networks Under A General Connection Model

zbMATH Keywords

sinr modelwireless connectivity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Cited In (13)

• Contention resolution on a fading channel
• A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model
• Connectivity and aggregation in multihop wireless networks
• Distributed bare-bones communication in wireless networks
• Title not available (Why is that?)
• The power of oblivious wireless power
• Connectivity problem in wireless networks
• STACS 2005
• Distributed algorithms for connected domination in wireless networks
• Initializing sensor networks of non-uniform density in the weak sensor model
• Distributed backbone structure for algorithms in the SINR model of wireless networks
• Title not available (Why is that?)
• Wireless connectivity and capacity

This page was built for publication: Distributed connectivity of wireless networks

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