Time efficient k-shot broadcasting in known topology radio networks |
| |
Authors: | Leszek Gąsieniec Erez Kantor Dariusz R. Kowalski David Peleg Chang Su |
| |
Affiliation: | (1) Department of Computer Science, University of Liverpool, Ashton Street, L69 3BX Liverpool, UK;(2) Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, 76100 Rehovot, Israel |
| |
Abstract: | The paper considers broadcasting protocols in radio networks with known topology that are efficient in both time and energy. The radio network is modelled as an undirected graph G = (V, E) where |V| = n. It is assumed that during execution of the communication task every node in V is allowed to transmit at most once. Under this assumption it is shown that any radio broadcast protocol requires transmission rounds, where D is the diameter of G. This lower bound is complemented with an efficient construction of a deterministic protocol that accomplishes broadcasting in rounds. Moreover, if we allow each node to transmit at most k times, the lower bound on the number of transmission rounds holds. We also provide a randomised protocol that accomplishes broadcasting in rounds. The paper concludes with a number of open problems in the area. The research of L. Gąsieniec, D.R. Kowalski and C. Su supported in part by the Royal Society grant Algorithmic and Combinatorial Aspects of Radio Communication, IJP - 2006/R2. The research of E. Kantor and D. Peleg supported in part by grants from the Minerva Foundation and the Israel Ministry of Science. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|