Nearly optimal local broadcasting in the SINR model with feedback

Leonid Barenboim, David Peleg

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


We consider the SINR wireless model with uniform power. In this model the success of a transmission is determined by the ratio between the strength of the transmission signal and the noise produced by other transmitting processors plus ambient noise. The local broadcasting problem is a fundamental problem in this setting. Its goal is producing a schedule in which each processor successfully transmits a message to all its neighbors. This problem has been studied in various variants of the setting, where the best currently-known algorithm has running time O(Δ+log2n) in n-node networks with feedback, where Δ is the maximum neighborhood size [9]. In the latter setting processors receive free feedback on a successful transmission. We improve this result by devising a local broadcasting algorithm with time O(Δ+lognloglogn) in networks with feedback. Our result is nearly tight in view of the lower bounds Ω(Δ) and Ω(logn) [13]. Our results also show that the conjecture that Ω(Δ+log2n) time is required for local broadcasting [9] is not true in some settings. We also consider a closely related problem of distant-k coloring. This problem requires each pair of vertices at geometrical distance of at most k transmission ranges to obtain distinct colors. Although this problem cannot be always solved in the SINR setting, we are able to compute a solution using an optimal number of Steiner points (up to constant factors). We employ this result to devise a local broadcasting algorithm that after a preprocessing stage of O(log∗n⋅(Δ+lognloglogn)) time obtains a local-broadcasting schedule of an optimal (up to constant factors) length O(Δ). This improves upon previous local-broadcasting algorithms in various settings whose preprocessing time was at least O(Δlogn) [3,10,5,]. Finally, we prove a surprising phenomenon regarding the influence of the path-loss exponent α on performance of algorithms. Specifically, we show that in vacuum (α = 2) any local broadcasting algorithm requires Ω(Δlogn) time, while on earth (α > 2) better results are possible as illustrated by our O(Δ+lognloglogn)-time algorithm.

שפה מקוריתאנגלית
כותר פרסום המארחStructural Information and Communication Complexity - 22nd International Colloquium, SIROCCO 2015, Post-Proceedings
עורכיםChristian Scheideler
מוציא לאורSpringer Verlag
מספר עמודים15
מסת"ב (מודפס)9783319252575
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2015
אירוע22nd International Colloquium on Structural Information and Communication Complexity, SIROCCO 2015 - Montserrat, ספרד
משך הזמן: 14 יולי 201516 יולי 2015

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349


כנס22nd International Colloquium on Structural Information and Communication Complexity, SIROCCO 2015

הערה ביבליוגרפית

Publisher Copyright:
© Springer International Publishing Switzerland 2015.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Nearly optimal local broadcasting in the SINR model with feedback'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי