Fast distributed algorithm for convergecast in ad hoc geometric radio networks

被引:40
作者
Kesselman, A [1 ]
Kowalski, DR
机构
[1] Max Planck Inst Informat, Saarbrucken, Germany
[2] Univ Liverpool, Dept Comp Sci, Liverpool L69 3BX, Merseyside, England
关键词
radio networks; convergecast; randomized algorithms; energy/latency trade-off;
D O I
10.1016/j.jpdc.2005.11.004
中图分类号
TP301 [理论、方法];
学科分类号
081202 [计算机软件与理论];
摘要
Wireless ad hoc radio networks have gained a lot of attention in recent years. We consider geometric networks, where nodes are located in a Euclidean plane. We assume that each node has a variable transmission range and can learn the distance to the closest active neighbor at any time. We also assume that nodes have a special collision detection (CD) capability so that a transmitting node can detect a collision within its transmission range. We study the basic communication problem of collecting data from all nodes called convergecast. Recently, there appeared many new applications such as real-time multimedia, battlefield communications and rescue operations that impose stringent delay requirements on the convergecast time. We measure the latency of convergecast, that is the number of time steps needed to collect the data in any n-node network. We propose a very simple randomized distributed algorithm that has the expected running time O(log n). We also show that this bound is tight and any algorithm needs Omega(log n) time steps while performing convergecast in an arbitrary network. One of the most important problems in wireless ad hoc networks is to minimize the energy consumption, which maximizes the network lifetime. We study the trade-off between the energy and the latency of convergecast. We show that our algorithm consumes at most O(n log n) times the minimum energy. We also demonstrate that for a line topology, the minimum energy convergecast takes n time steps while any algorithm performing convergecast within O(log n) time steps requires Omega(n/log n) times the minimum energy. (c) 2006 Elsevier Inc. All rights reserved.
引用
收藏
页码:578 / 585
页数:8
相关论文
共 36 条
[1]
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
[2]
Annamalai V, 2003, IEEE WCNC, P1942
[3]
[Anonymous], 2003, P INT S PRINC DISTR
[4]
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
[5]
Cagalj M., 2002, P 8 ANN INT C MOB CO, P172
[6]
CALINESCI G, P ADHOC NOW 03
[7]
CARTIGNY J, 2003, P 22 ANN JOINT C IEE
[8]
THE STRONGLY CONNECTING PROBLEM ON MULTIHOP PACKET RADIO NETWORKS [J].
CHEN, WT ;
HUANG, NF .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1989, 37 (03) :293-295
[9]
THE WAVE EXPANSION APPROACH TO BROADCASTING IN MULTIHOP RADIO NETWORKS [J].
CHLAMTAC, I ;
WEINSTEIN, O .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1991, 39 (03) :426-433
[10]
CHLEBUS BS, 2001, P 5 INT WORKSH DISCR, P44