Fast broadcasting and gossiping in radio networks

被引：73

作者：

Chrobak, M ^{[1
]}

Gasieniec, L ^{[1
]}

Rytter, W ^{[1
]}

机构：

[1] Univ Calif Riverside, Dept Comp Sci, Riverside, CA 92521 USA

来源：

41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2000年

关键词：

D O I：

10.1109/SFCS.2000.892325

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We establish an O(n log(2) n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Omega (n log n). The fastest previously known algorithm for this problem works in time O(n(3/2)). Using our broadcasting algorithm, we develop an O (n(3/2) log(2) n) algorithm for gossiping in the same network model.

引用

页码：575 / 581

页数：7

共 26 条

[1] SINGLE ROUND SIMULATION ON RADIO NETWORKS
ALON, N
BARNOY, A
LINIAL, N
PELEG, D
[J]. JOURNAL OF ALGORITHMS, 1992, 13 (02) : 188 - 210
[2] A LOWER BOUND FOR RADIO BROADCAST
ALON, N
BARNOY, A
LINIAL, N
PELEG, D
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1991, 43 (02) : 290 - 298
[3] ALON N, 1992, PROBABILISTIC METHOD
[4] [Anonymous], 2000, COMMUNICATION
[5] MULTIPLE COMMUNICATION IN MULTIHOP RADIO NETWORKS
BARYEHUDA, R
ISRAELI, A
ITAI, A
[J]. SIAM JOURNAL ON COMPUTING, 1993, 22 (04) : 875 - 887
[6] ON THE TIME-COMPLEXITY OF BROADCAST IN MULTIHOP RADIO NETWORKS - AN EXPONENTIAL GAP BETWEEN DETERMINISM AND RANDOMIZATION
BARYEHUDA, R
GOLDREICH, O
ITAI, A
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1992, 45 (01) : 104 - 126
[7] Lower bounds for the broadcast problem in mobile radio networks
Bruschi, D
DelPinto, M
[J]. DISTRIBUTED COMPUTING, 1997, 10 (03) : 129 - 135
[8] ON BROADCASTING IN RADIO NETWORKS - PROBLEM ANALYSIS AND PROTOCOL DESIGN
CHLAMTAC, I
KUTTEN, S
[J]. IEEE TRANSACTIONS ON COMMUNICATIONS, 1985, 33 (12) : 1240 - 1246
[9] Chlebus BS, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P861
[10] CHLEBUS M, IN PRESS P 27 INT C

← 1 2 3 →