Fast Distributed Algorithm for Convergecast in Ad Hoc Geometric Radio Networks
Fast Distributed Algorithm for Convergecast in Ad Hoc Geometric Radio Networks
复制标题
DOI：
10.1016/j.jpdc.2005.11.004
复制
发表时间：
2005-01
期刊：
影响因子：
--
通讯作者：
A. Kesselman;D. Kowalski
中科院分区：
文献类型：
--
作者：
A. Kesselman;D. Kowalski
无线自组织无线网络近年来受到了人们的广泛关注。我们考虑几何网络，其中节点位于欧几里得平面上。我们假设每个节点具有可变的传输范围，并且可以学习到最近邻居的距离。我们还假设节点具有特殊的冲突检测(CD)能力，以便传输节点可以检测其传输范围内的冲突。我们研究了从所有节点收集数据的基本通信问题，称为聚合广播。我们测量聚合广播的延迟，即在任何n节点网络中收集数据所需的时间步数。我们提出了一个非常简单的随机分布式算法，其预期运行时间为O(Logn)。我们还证明了这个界是紧的，并且任何算法在任意网络中执行收敛广播时都需要Ω(Logn)个时间步长。在无线自组织网络中，最重要的问题之一就是最小化能量消耗，从而最大化网络生命周期。我们研究了汇聚广播的能量和时延之间的权衡。我们证明了我们的算法消耗的能量至多是最小能量的O(Nlogn)倍。我们还证明了对于线状拓扑，最小能量收敛需要n-1个时间步，而任何算法在O(Logn)个时间步内执行收敛都需要Ω(N)倍的最小能量。
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.