Leader election in SINR model with arbitrary power control

被引：9

作者：

Halldorsson, Magnus M. ^{[1
]}

Holzer, Stephan ^{[2
]}

Markatou, Evangelia Anna ^{[2
]}

Lynch, Nancy ^{[2
]}

机构：

[1] Reykjavik Univ, Sch Comp Sci, ICE TCS, Reykjavik, Iceland

[2] MIT, TDS Grp, Cambridge, MA 02139 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2020年 / 811卷

关键词：

SINR; Leader election; Power control; Capture effect;

D O I：

10.1016/j.tcs.2019.01.024

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider 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 elect a leader in two communication rounds, with high probability. Previously, it was known that Theta(logn) 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(Omega(n)), even when n is known. We complement this with an algorithm that uses power range 2((o) over tilde (n)1), when n is known, and 2((o) over tilde (n1.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/Theta(t))) is sufficient and necessary. (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：21 / 28

页数：8

共 12 条

[1]

Abramson N., P AFIPS 70 FALL P FA, DOI [10.1145/1478462.1478502, DOI 10.1145/1478462.1478502]

[2]

[Anonymous], [No title captured]

[3]

Bar-Yehuda R., 1987, ACM PODC, P98, DOI DOI 10.1145/41840.41849

[4] Wireless link scheduling with power control and SINR constraints [J].

Borbash, Steven A. ;

Ephremides, Anthony .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (11) :5106-5111

[5] TREE ALGORITHMS FOR PACKET BROADCAST CHANNELS [J].

CAPETANAKIS, JI .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1979, 25 (05) :505-515

[6] ON BROADCASTING IN RADIO NETWORKS - PROBLEM ANALYSIS AND PROTOCOL DESIGN [J].

CHLAMTAC, I ;

KUTTEN, S .

IEEE TRANSACTIONS ON COMMUNICATIONS, 1985, 33 (12) :1240-1246

[7]

Cruz RL, 2003, IEEE INFOCOM SER, P702

[8]

Daum S., 2012, P 2012 ACM S PRINC D, P215

[9] Contention Resolution on a Fading Channel [J].

Fineman, Jeremy T. ;

Gilbert, Seth ;

Kuhn, Fabian ;

Newport, Calvin .

PROCEEDINGS OF THE 2016 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'16), 2016, :155-164

[10]

Moscibroda T, 2006, IEEE INFOCOM SER, P25

← 1 2 →