TY - GEN
T1 - On the impact of geometry on ad hoc communication in wireless networks
AU - Jurdzinski, Tomasz
AU - Kowalski, Dariusz R.
AU - Rozanski, Michal
AU - Stachowiak, Grzegorz
PY - 2014/1/1
Y1 - 2014/1/1
N2 - In this work we address the question how important is the knowledge of geometric location and network density to the efficiency of (distributed) wireless communication in ad hoc networks. We study fundamental communication task of broadcast and develop well-scalable, randomized algorithms that do not rely on GPS information, and which efficiency formulas do not depend on how dense the geometric network is. We consider two settings: with and without spontaneous wake-up of nodes. In the former setting, in which all nodes start the protocol at the same time, our algorithm accomplishes broadcast in O(D log n + log2 n) rounds under the SINR model, with high probability (whp), where D is the diameter of the communication graph and n is the number of stations. In the latter setting, in which only the source node containing the original message is active in the beginning, we develop a slightly slower algorithm working in O(D log2 n) rounds whp. Both algorithms are based on a novel distributed coloring method, which is of independent interest and potential applicability to other communication tasks under the SINR wireless model.
AB - In this work we address the question how important is the knowledge of geometric location and network density to the efficiency of (distributed) wireless communication in ad hoc networks. We study fundamental communication task of broadcast and develop well-scalable, randomized algorithms that do not rely on GPS information, and which efficiency formulas do not depend on how dense the geometric network is. We consider two settings: with and without spontaneous wake-up of nodes. In the former setting, in which all nodes start the protocol at the same time, our algorithm accomplishes broadcast in O(D log n + log2 n) rounds under the SINR model, with high probability (whp), where D is the diameter of the communication graph and n is the number of stations. In the latter setting, in which only the source node containing the original message is active in the beginning, we develop a slightly slower algorithm working in O(D log2 n) rounds whp. Both algorithms are based on a novel distributed coloring method, which is of independent interest and potential applicability to other communication tasks under the SINR wireless model.
KW - Ad Hoc wireless networks
KW - Broadcast
KW - Coloring
KW - Distributed algorithms
KW - Signal-to-Interference-and-Noise-Ratio (SINR) model
UR - http://www.scopus.com/inward/record.url?scp=84905447677&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84905447677&partnerID=8YFLogxK
U2 - 10.1145/2611462.2611487
DO - 10.1145/2611462.2611487
M3 - Conference contribution
AN - SCOPUS:84905447677
SN - 9781450329446
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 357
EP - 366
BT - PODC 2014 - Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
T2 - 2014 ACM Symposium on Principles of Distributed Computing, PODC 2014
Y2 - 15 July 2014 through 18 July 2014
ER -