Improved schedule for radio broadcast

ABSTRACT

We show that for every radio network G = (V, E) and source s ε V, there exists a radio broadcast schedule for G of length Rad(G, s) + O(√ Rad(G, s). log² n) = O(Rad(G, s) + log⁴ n), where Rad(G, s) is the radius of the radio network G with respect to the source s. This result improves the previously best-known upper bound of O(Rad(G, s)+log⁵ n) due to Gaber and Mansour [12].For graphs with small genus, particularly for planar graphs, we provide an even better upper bound of Rad(G, S) + O(√ Rad(G, s). log n + log³ n) = O(Rad(G, s) + log³ n).

REFERENCES

• 1: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 2: Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Fast network decomposition, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.169-177, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135456]
• 3: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection, Distributed Computing, v.5 n.2, p.67-71, September 1991 [doi>10.1007/BF02259748]
• 4: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, v.45 n.1, p.104-126, Aug. 1992 [doi>10.1016/0022-0000(92)90042-H]
• 5: I. Chlamtac and S. Kutten. A spatial-reuse tdma/fdma for mobile multihop radio networks. In Proc. IEEE INFOCOM, pages 389--394, 1985.
• 6: I. Chlamtac and Weinstein. The wave expansion approach to broadcasting in multihop radio networks. In Proc. IEEE INFOCOM, pages 874--881, 1987.
• 7: Bogdan S. Chlebus , Leszek Gasieniec , Alan Gibbons , Andrzej Pelc , Wojciech Rytter, Deterministic broadcasting in ad hoc radio networks, Distributed Computing, v.15 n.1, p.27-38, January 2002 [doi>10.1007/s446-002-8028-1]
• 8: M. Chrobak , L. Gasieniec , W. Rytter, Fast broadcasting and gossiping in radio networks, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.575, November 12-14, 2000
• 9: Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Distributed broadcast in radio networks of unknown topology, Theoretical Computer Science, v.302 n.1-3, p.337-364, 13 June 2003 [doi>10.1016/S0304-3975(02)00851-4]
• 10: Artur Czumaj , Wojciech Rytter, Broadcasting Algorithms in Radio Networks with Unknown Topology, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.492, October 11-14, 2003
• 11: M. Elkin and G. Kortsarz. Polylogarithmic additive inapproximability of the radio broadcast problem. Yale Technical Report TR1274, 2004.
• 12: Iris Gaber , Yishay Mansour, Broadcast in radio networks, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.577-585, January 22-24, 1995, San Francisco, California, United States
• 13: Piotr Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 06-08, 2002, San Francisco, California
• 14: Dariusz R. Kowalski , Andrzej Pelc, Deterministic Broadcasting Time in Radio Networks of Unknown Topology, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.63-72, November 16-19, 2002
• 15: Dariusz R. Kowalski , Andrzej Pelc, Broadcasting in undirected ad hoc radio networks, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.73-82, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872045]
• 16: D. Kowalski and A. Pelc. Centralized deterministic broadcasting in undirected multi-hop radio network. to appear, 2004.
• 17: Eyal Kushilevitz , Yishay Mansour, An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks, SIAM Journal on Computing, v.27 n.3, p.702-712, June 1998 [doi>10.1137/S0097539794279109]
• 18: Nathan Linial , Michael Saks, Decomposing graphs into regions of small diameter, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.320-330, January 28-30, 1991, San Francisco, California, United States