TY - JOUR

T1 - Fast distributed algorithm for convergecast in ad hoc geometric radio networks

AU - Kesselman, Alex

AU - Kowalski, Dariusz R.

N1 - Funding Information:
2The work of the second author was done during his staying at the Max Planck Institüt für Informatik, Saarbrücken, Germany, and was supported in part by EU DELIS project.
Funding Information:
1The work of the first author is supported by AvH-Stiftung. A part of this work has been done while visiting the Dipartimento di Scienze dell’Informazione at Universita di Roma La Sapienza, Italy. Supported in part by EYES project and MIUR grant FIRB WebMinds.

PY - 2006/4

Y1 - 2006/4

N2 - 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(logn). We also show that this bound is tight and any algorithm needs Ω(logn) 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(nlogn) 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(logn) time steps requires Ω(n/logn) times the minimum energy.

AB - 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(logn). We also show that this bound is tight and any algorithm needs Ω(logn) 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(nlogn) 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(logn) time steps requires Ω(n/logn) times the minimum energy.

KW - Convergecast

KW - Energy/latency trade-off

KW - Radio networks

KW - Randomized algorithms

UR - http://www.scopus.com/inward/record.url?scp=33644969565&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33644969565&partnerID=8YFLogxK

U2 - 10.1016/j.jpdc.2005.11.004

DO - 10.1016/j.jpdc.2005.11.004

M3 - Article

AN - SCOPUS:33644969565

VL - 66

SP - 578

EP - 585

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

IS - 4

ER -