Deterministic Radio Broadcasting at Low Cost
作者： Anders Dessmark , Andrzej Pelc
关键词:
摘要: We consider the problem of distributed deterministic broadcasting in radio networks. The network is synchronous. A node receives a message given round if and only exactly one its neighbors transmits. source has to reach all nodes. assume that nodes do not know topology or even their immediate neighborhood. are concerned with two efficiency measures algorithms: execution time (number rounds), cost transmissions). focus our study on algorithms which have close minimum. We scenarios depending whether global parameters network: number n eccentricity D source. Our main contribution lower bounds low-cost show sharp differences between these scenarios.
springer.com
sci-hub.st 参考文章(21)
D. Krizanc, A. Pelc, E. Kranakis, Fault-tolerant broadcasting in radio networks Lecture Notes in Computer Science. pp. 283- 294 ,(1998)
Krzysztof Diks, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, The Impact of Knowledge on Broadcasting Time in Radio Networks european symposium on algorithms. pp. 41- 52 ,(1999) , 10.1007/3-540-48481-7_5
Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract) european symposium on algorithms. pp. 283- 294 ,(1998) , 10.1007/3-540-68530-8_24
Chlamtac, Kutten, Tree-Based Broadcasting in Multihop Radio Networks IEEE Transactions on Computers. ,vol. 36, pp. 1209- 1223 ,(1987) , 10.1109/TC.1987.1676861
Baruch Awerbuch, Oded Goldreich, Ronen Vainish, David Peleg, A trade-off between information and communication in broadcast protocols Journal of the ACM. ,vol. 37, pp. 238- 256 ,(1990) , 10.1145/77600.77618
Artur Czumaj, Leszek Gasieniec, Andrzej Pelc, Time and Cost Trade-Offs in Gossiping SIAM Journal on Discrete Mathematics. ,vol. 11, pp. 400- 413 ,(1998) , 10.1137/S0895480295292934
Eyal Kushilevitz, Yishay Mansour, An Ω(D log(N/D)) lower bound for broadcast in radio networks Proceedings of the twelfth annual ACM symposium on Principles of distributed computing - PODC '93. pp. 65- 74 ,(1993) , 10.1145/164051.164059
Leszek Gąsieniec, Wojciech Rytter, Bogdan S. Chlebus, Andrzej Pelc, Alan Gibbons, Deterministic broadcasting in unknown radio networks symposium on discrete algorithms. pp. 861- 870 ,(2000) , 10.5555/338219.338652
Gianluca De Marco, Andrzej Pelc, Faster broadcasting in unknown radio networks Information Processing Letters. ,vol. 79, pp. 53- 56 ,(2001) , 10.1016/S0020-0190(00)00178-2
Iris Gaber, Yishay Mansour, Broadcast in radio networks symposium on discrete algorithms. pp. 577- 585 ,(1995) , 10.5555/313651.313821