Speaker: Alexander Kesselman, Max Plank Institute

Time: Sunday, OCtober 24, 1:15 PM
Location: Schreiber 209

Title:"Fast Distributed Algorithm for Convergecast 
in Ad Hoc Geometric Radio Networks"


Abstract:
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 {\em 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 {\em 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 {\em distributed} 
algorithm that has the expected running time $\cO(\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 $\cO(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 $\cO(\log n)$ time steps 
requires $\Omega(n)$ times the minimum energy.

Joint work with Dariusz Kowalski.