loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Second Annual Conference on Wireless On-demand Network Systems and Services (WONS'05)
Fast Distributed Algorithm for Convergecast in Ad Hoc Geometric Radio Networks
St. Moritz, Switzerland
January 19-January 21
ISBN: 0-7695-2290-0
Alex Kesselman, Max Planck Institut f?r Informatik, Germany
Dariusz Kowalski, Uniwersytet Warszawski Poland and Max Planck Instit?t f?r Informatik, Germany
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 neighbor. 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. 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 Ω(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 - 1 time steps while any algorithm performing convergecast within O(log n) time steps requires Ω(n) times the minimum energy.
Citation:
Alex Kesselman, Dariusz Kowalski, "Fast Distributed Algorithm for Convergecast in Ad Hoc Geometric Radio Networks," wons, pp.119-124, Second Annual Conference on Wireless On-demand Network Systems and Services (WONS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.