Please use this identifier to cite or link to this item:
|Title:||Broadcast in the ad hoc SINR model|
|Source:||Daum, S.,Gilbert, S.,Kuhn, F.,Newport, C. (2013). Broadcast in the ad hoc SINR model. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8205 LNCS : 358-372. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-41527-2_25|
|Abstract:||An increasing amount of attention is being turned toward the study of distributed algorithms in wireless network models based on calculations of the signal to noise and interference ratio (SINR). In this paper we introduce the ad hoc SINR model, which, we argue, reduces the gap between theory results and real world deployment. We then use it to study upper and lower bounds for the canonical problem of broadcast on the graph induced by both strong and weak links. For strong connectivity broadcast, we present a new randomized algorithm that solves the problem in O (D log (n)polylog(R)) rounds in networks of size n, with link graph diameter D , and a ratio between longest and shortest links bounded by R. We then show that for back-off style algorithms (a common type of algorithm where nodes do not explicitly coordinate with each other) and compact networks (a practice-motivated model variant that treats the distance from very close nodes as equivalent), there exist networks in which centralized algorithms can solve broadcast in O (1) rounds, but distributed solutions require Ω(n) rounds. We then turn our attention to weak connectivity broadcast, where we show a similar Ω(n) lower bound for all types of algorithms, which we (nearly) match with a back-off style O (n log2 n)-round upper bound. Our broadcast algorithms are the first known for SINR-style models that do not assume synchronous starts, as well as the first known not to depend on power control, tunable carrier sensing, geographic information and/or exact knowledge of network parameters. © Springer-Verlag 2013.|
|Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jan 10, 2018
checked on Jan 12, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.