Abstract
We study the problem of gathering information from the nodes of a multi-hop radio network into a pre-determined destination node under interference constraints which are modeled by an integer d ≥ 1, so that any node within distance d of a sender cannot receive calls from any other sender. A set of calls which do not interfere with each other is referred to as a round. We give algorithms and lower bounds on the minimum number of rounds for this problem, when the network is a path and the destination node is either at one end or at the center of the path. The algorithms are shown to be optimal for any d in the first case, and for 1 ≤ d ≤ 4, in the second case.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bermond, J.-C., Galtier, J., Klasing, R., Morales, N., Pérennes, S.: Hardness and approximation of gathering in static radio networks. In: FAWN 2006, Pisa, Italy (March 2006)
Bermond, J.-C., Peters, J.: Efficient gathering in radio ids with interference. In: AlgoTel 2005, Presqu’le de Giens, May 2005, pp. 103–106 (2005)
Bertin, P., Bresse, J.-F., Le Sage, B.: Accs haut dbit en zone rurale: une solution ”ad hoc”. France Telecom R&D 22, 16–18 (2005)
Christersson, M., Gasieniec, L., Lingas, A.: Gossiping with bounded size messages in ad-hoc radio networks. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 377–389. Springer, Heidelberg (2002)
Chrobak, M., Gasieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. Journal of Algorithms 43(2), 177–189 (2002)
Elkin, M.L., Kortsarz, G.: Logarithmic inapproximability of the radio broadcast problem. Journal of Algorithms 52(1), 8–25 (2004)
Gaber, I., Mansour, Y.: Centralized broadcast in multihop radio networks. Journal of Algorithms 46(1), 1–20 (2003)
Gasieniec, L., Potapov, I.: Gossiping with unit messages in known radio networks. In: Proceedings of the IFIP 17th World Computer Congress, pp. 193–205. Kluwer, B.V (2002)
Klasing, R., Morales, N., Pérennes, S.: On the complexity of bandwidth allocation in radio networks with ste ady traffic demands. Technical report, INRIA Research Report RR-5432 and I3S Research Report I3S/RR-2 004-40-FR (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bermond, JC., Corrêa, R., Yu, M. (2006). Gathering Algorithms on Paths Under Interference Constraints. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds) Algorithms and Complexity. CIAC 2006. Lecture Notes in Computer Science, vol 3998. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758471_14
Download citation
DOI: https://doi.org/10.1007/11758471_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34375-2
Online ISBN: 978-3-540-34378-3
eBook Packages: Computer ScienceComputer Science (R0)