非表示:
キーワード:
-
要旨:
We address the problem of data gathering in a wireless network using multi-hop
communication; our main goal is the analysis of simple algorithms suitable for
implementation in realistic scenarios. We study the performance of distributed
algorithms, which do not use any form of local coordination, and we focus on
the objective of minimizing average flow times of data packets. We prove a
lower bound of $\Omega(n)$ on the expected competitive ratio of any
acknowledgment-based distributed algorithm minimizing the maximum flow time,
where $n$ is the number of nodes of the network. Next, we consider a
distributed algorithm which sends packets over shortest paths, and we use
resource augmentation to analyze its performance when the objective is to
minimize the average flow time. If interferences are modeled as in Bar-Yehuda
et al. [R. Bar-Yehuda, O. Goldreich, A. Itai, On the time complexity of
broadcast in multi-hop radio networks: an exponential gap between determinism
and randomization, Journal of Computer and Systems Sciences 45 (1) (1992) 104–
126] we prove that the algorithm is $(1+\epsilon)$-competitive, when the
algorithm sends packets a factor $O(\log(\delta/\epsilon) \log \Delta)$ faster
than the optimal off-line solution; here $\delta$ is the radius of the network
and $\Delta$ the maximum degree. We finally extend this result to a more
complex interference model.
