Opin vísindi

Leader election in SINR model with arbitrary power control

Leader election in SINR model with arbitrary power control

Title: Leader election in SINR model with arbitrary power control
Author: Halldórsson, Magnús M.   orcid.org/0000-0002-5774-8437
Holzer, Stephan
Markatou, Evangelia Anna
Lynch, Nancy
Date: 2020-04
Language: English
Scope: 21-28
University/Institute: Háskólinn í Reykjavík
Reykjavik University
School: Tæknisvið (HR)
School of Technology (RU)
Department: Tölvunarfræðideild (HR)
School of Computer Science (RU)
Series: Theoretical Computer Science;811
ISSN: 0304-3975
1879-2294 (eISSN)
DOI: 10.1016/j.tcs.2019.01.024
Subject: Theoretical Computer Science; Algorithms; Wireless communication systems; Tölvunarfræði; Reiknirit; Þráðlaus kerfi
URI: https://hdl.handle.net/20.500.11815/2033

Show full item record


We consider the Leader Election Problem in the Signal-to-Interference-plusNoise-Ratio (SINR) model where nodes can adjust their transmission power. We show that in this setting it is possible to elect a leader in two communication rounds, with high probability. Previously, it was known that Θ(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 every 2-round leader election algorithm in the SINR model running correctly w.h.p. requires a power range 2Ω(n) , even when n is known. We complement this with an algorithm that uses power range 2O˜(n)1, when n is known, and 2O˜(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 range of possible power levels of size exp(n 1/Θ(t) ) is sufficient and necessary


Post-print (lokagerð höfundar)


Post print (lokagerð höfundar)

Files in this item

This item appears in the following Collection(s)