TY - GEN
T1 - Distributed deterministic broadcasting in uniform-power ad hoc wireless networks
AU - Jurdzinski, Tomasz
AU - Kowalski, Dariusz R.
AU - Stachowiak, Grzegorz
PY - 2013
Y1 - 2013
N2 - In this work we study broadcasting in ad hoc wireless networks with uniform transmission powers, deployed in two dimensional Euclidean space.We consider two models based on the Signal-to-Interference- and-Noise Ratio (SINR): with opportunistic links, and with randomly disturbed SINR. In the former model, we deliver and analyze two algorithms: one accomplishing broadcast in O(D logg) rounds under assumption that the granularity g of the network is known, and the other without such assumption working in O(D log2 n) rounds, where n is the number of nodes and D is the diameter of the network. It is also shown how to accelerate broadcast in the model to O(D + log2 n) rounds when stations can wake up spontaneously. Finally, we modify the main two algorithms to make them efficient in the latter model with randomly disturbed SINR, with only logarithmic growth of performance.
AB - In this work we study broadcasting in ad hoc wireless networks with uniform transmission powers, deployed in two dimensional Euclidean space.We consider two models based on the Signal-to-Interference- and-Noise Ratio (SINR): with opportunistic links, and with randomly disturbed SINR. In the former model, we deliver and analyze two algorithms: one accomplishing broadcast in O(D logg) rounds under assumption that the granularity g of the network is known, and the other without such assumption working in O(D log2 n) rounds, where n is the number of nodes and D is the diameter of the network. It is also shown how to accelerate broadcast in the model to O(D + log2 n) rounds when stations can wake up spontaneously. Finally, we modify the main two algorithms to make them efficient in the latter model with randomly disturbed SINR, with only logarithmic growth of performance.
KW - Ad hoc wireless networks
KW - Broadcast problem
KW - Local leader election
KW - Signal-to-Interference-and-Noise- Ratio (SINR)
KW - Uniform-power
UR - http://www.scopus.com/inward/record.url?scp=84883165578&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883165578&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-40164-0_20
DO - 10.1007/978-3-642-40164-0_20
M3 - Conference contribution
AN - SCOPUS:84883165578
SN - 9783642401633
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 195
EP - 209
BT - Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings
T2 - 19th International Symposium on Fundamentals of Computation Theory, FCT 2013
Y2 - 19 August 2013 through 21 August 2013
ER -