An Ω(D log(N/D)) lower bound for broadcast in radio networks

被引：178

作者：

Kushilevitz, E

Mansour, Y

机构：

[1] Harvard Univ, Aiken Computat Lab, Cambridge, MA 02138 USA

[2] Tel Aviv Univ, Dept Comp Sci, IL-69978 Tel Aviv, Israel

[3] IBM Corp, TJ Watson Res Ctr, Armonk, NY 10504 USA

来源：

SIAM JOURNAL ON COMPUTING | 1998年 / 27卷 / 03期

关键词：

radio networks; broadcast; lower bounds;

D O I：

10.1137/S0097539794279109

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that for any randomized broadcast protocol for radio networks, there exists a network in which the expected time to broadcast a message is Omega(Dlog(N/D)), where D is the diameter of the network and N is the number of nodes. This implies a tight lower bound of Omega(Dlog N) for any D less than or equal to N1-epsilon, where epsilon > 0 is any constant.

引用

页码：702 / 712

页数：11

共 14 条

[1] SINGLE ROUND SIMULATION ON RADIO NETWORKS [J].

ALON, N ;

BARNOY, A ;

LINIAL, N ;

PELEG, D .

JOURNAL OF ALGORITHMS, 1992, 13 (02) :188-210

[2] A LOWER BOUND FOR RADIO BROADCAST [J].

ALON, N ;

BARNOY, A ;

LINIAL, N ;

PELEG, D .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1991, 43 (02) :290-298

[3]

[Anonymous], COMPUTER NETWORKS

[4] EFFICIENT EMULATION OF SINGLE-HOP RADIO NETWORK WITH COLLISION DETECTION ON MULTIHOP RADIO NETWORK WITH NO COLLISION DETECTION [J].

BARYEHUDA, R ;

GOLDREICH, O ;

ITAI, A .

DISTRIBUTED COMPUTING, 1991, 5 (02) :67-71

[5] MULTIPLE COMMUNICATION IN MULTIHOP RADIO NETWORKS [J].

BARYEHUDA, R ;

ISRAELI, A ;

ITAI, A .

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 [J].

BARYEHUDA, R ;

GOLDREICH, O ;

ITAI, A .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1992, 45 (01) :104-126

[7]

Chlamtac I., 1987, IEEE INFOCOM '87. The Conference on Computer Communications. Proceedings. Sixth Annual Conference - Global Networks: Concept to Realization (Cat. No.87CH2412-5), P874

[8]

CHLAMTAC I, 1987, IEEE T COMPUT, V36, P1209, DOI 10.1109/TC.1987.1676861

[9] ON BROADCASTING IN RADIO NETWORKS - PROBLEM ANALYSIS AND PROTOCOL DESIGN [J].

CHLAMTAC, I ;

KUTTEN, S .

IEEE TRANSACTIONS ON COMMUNICATIONS, 1985, 33 (12) :1240-1246

[10]

Chlamtac I, 1985, IEEE INFOCOM, P389

← 1 2 →