Advertisement
Published in:
2017 | OriginalPaper | Chapter
Leader Election in SINR Model with Arbitrary Power Control
Authors : Magnús M. Halldórsson, Stephan Holzer, Evangelia Anna Markatou
Published in: Structural Information and Communication Complexity
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this article, we study the Leader Election Problem in the Signal-to-Interference-plus-Noise-Ratio (SINR) model where nodes can adjust their transmission power. We show that in this setting it is possible to solve the leader election problem in two communication rounds, with high probability. Previously, it was known that \(\varOmega (\log n)\) rounds were sufficient and necessary when using uniform power, where n is the number of nodes in the network.
We then examine how much power control is needed to achieve fast leader election. We show that any 2-round leader election algorithm in the SINR model running correctly w.h.p. requires a power range \(2^{\varOmega (n)}\) even when n is known. We match this with an algorithm that uses power range \(2^{\tilde{O}(n)}\), when n is known and \(2^{\tilde{O}(n^{1.5})}\), when n is not known. We also explore tradeoffs between time and power used, and show that to elect a leader in t rounds, a power range \(exp(n^{1/\varTheta (t)})\) is sufficient and necessary.