Faster broadcasting in unknown radio networks
作者： Gianluca De Marco , Andrzej Pelc
DOI: 10.1016/S0020-0190(00)00178-2
关键词:
摘要: Abstract We study the time of distributed deterministic broadcasting in synchronous radio networks unknown topology and size. If a node u can be reached from two nodes which send messages same round, none is received by . assume that are completely ignorant network: they know neither its topology, nor size, even their immediate neighborhood. The initial knowledge every limited to own label. Chlebus et al. [Proc. 11th Annual ACM-SIAM Symp. on Discrete Algorithms, 2000, p. 861] constructed algorithm working O (n 11/6 ) under this total ignorance scenario. improve result showing how broadcast 5/3 ( log n) 1/3 model.
uni.wroc.pl
elsevier.com参考文章(14)
Reuven Bar-Yehuda, Amos Israeli, Alon Itai, Multiple Communication in Multihop Radio Networks SIAM Journal on Computing. ,vol. 22, pp. 875- 887 ,(1993) , 10.1137/0222055
Ding-Zhu Du, Frank Kwang Hwang, Combinatorial Group Testing and Its Applications ,(1993)
Uzi Vishkin, Deterministic sampling: a new technique for fast pattern matching SIAM Journal on Computing. ,vol. 20, pp. 22- 40 ,(1991) , 10.1137/0220002
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
Iris Gaber, Yishay Mansour, Broadcast in radio networks symposium on discrete algorithms. pp. 577- 585 ,(1995) , 10.5555/313651.313821
Danilo Bruschi, Massimiliano Del Pinto, Lower bounds for the broadcast problem in mobile radio networks Distributed Computing. ,vol. 10, pp. 129- 135 ,(1997) , 10.1007/S004460050030
Eyal Kushilevitz, Yishay Mansour, An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks SIAM Journal on Computing. ,vol. 27, pp. 702- 712 ,(1998) , 10.1137/S0097539794279109
A perspective on multiaccess channels IEEE Transactions on Information Theory. ,vol. 31, pp. 124- 142 ,(1985) , 10.1109/TIT.1985.1057022
Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg, A lower bound for radio broadcast Journal of Computer and System Sciences. ,vol. 43, pp. 290- 298 ,(1991) , 10.1016/0022-0000(91)90015-W
M. Chrobak, L. Gasieniec, W. Rytter, Fast broadcasting and gossiping in radio networks foundations of computer science. pp. 575- 581 ,(2000) , 10.1109/SFCS.2000.892325