Faster Deterministic Communication in Radio Networks

Cicalese F, Manne F, Xin Q (2009)
Algorithmica 54(2): 226-242.

Zeitschriftenaufsatz | Veröffentlicht| Englisch
 
Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Autor/in
Cicalese, Ferdinando; Manne, Frederic; Xin, Qin
Abstract / Bemerkung
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 O(D + Delta log n/log Delta-log log n) time units in any radio network of size n, diameter D, and maximum degree Delta = Omega(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically Delta-regular tree, in which the radio gossiping cannot be completed in less than Omega(D + Delta log n/log Delta) units of time. Moreover, we show a D + O(log(3) n/log log n) schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules by G. asieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129-137, 2005), i. e., a O(D + Delta 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.
Stichworte
Gossiping Centralized radio networks Broadcasting
Erscheinungsjahr
2009
Zeitschriftentitel
Algorithmica
Band
54
Ausgabe
2
Seite(n)
226-242
ISSN
0178-4617
eISSN
1432-0541
Page URI
https://pub.uni-bielefeld.de/record/2426660

Zitieren

Cicalese F, Manne F, Xin Q. Faster Deterministic Communication in Radio Networks. Algorithmica. 2009;54(2):226-242.
Cicalese, F., Manne, F., & Xin, Q. (2009). Faster Deterministic Communication in Radio Networks. Algorithmica, 54(2), 226-242. doi:10.1007/s00453-007-9136-0
Cicalese, F., Manne, F., and Xin, Q. (2009). Faster Deterministic Communication in Radio Networks. Algorithmica 54, 226-242.
Cicalese, F., Manne, F., & Xin, Q., 2009. Faster Deterministic Communication in Radio Networks. Algorithmica, 54(2), p 226-242.
F. Cicalese, F. Manne, and Q. Xin, “Faster Deterministic Communication in Radio Networks”, Algorithmica, vol. 54, 2009, pp. 226-242.
Cicalese, F., Manne, F., Xin, Q.: Faster Deterministic Communication in Radio Networks. Algorithmica. 54, 226-242 (2009).
Cicalese, Ferdinando, Manne, Frederic, and Xin, Qin. “Faster Deterministic Communication in Radio Networks”. Algorithmica 54.2 (2009): 226-242.