Faster Deterministic Communication in Radio Networks |
| |
Authors: | Ferdinando Cicalese Fredrik Manne Qin Xin |
| |
Affiliation: | 1.AG Genominformatik, Technische Fakult?t,Universit?t Bielefeld,Bielefeld,Germany;2.Department of Informatics,The University of Bergen,Bergen,Norway;3.Simula Research Laboratory,Lysaker,Norway |
| |
Abstract: | We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication)
in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full
knowledge about the size and the topology of the network. We show that gossiping can be completed in
time units in any radio network of size n, diameter D, and maximum degree Δ=Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than
units of time. Moreover, we show a
schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules
by Gąsieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129–137, 2005), i.e., a O(D+Δlog n) time schedule for gossiping and a D+O(log 3
n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+log 2
n) time broadcasting schedule by Kowalski and Pelc.
A preliminary version of this paper appeared in the proceedings of ISAAC’06.
F. Cicalese supported by the Sofja Kovalevskaja Award 2004 of the Alexander von Humboldt Stiftung. F. Manne and Q. Xin supported
by the Research Council of Norway through the SPECTRUM project. |
| |
Keywords: | Centralized radio networks Broadcasting Gossiping |
本文献已被 SpringerLink 等数据库收录! |
|