Skip to Main content Skip to Navigation
New interface
Journal articles

Optimal Gathering Protocols on Paths under Interference Constraints

Jean-Claude Bermond 1, * Ricardo Correa 2 Min-Li Yu 3 
* Corresponding author
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being transmitted simultaneously. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d?1, which implies that nodes within distance d in the graph from one sender cannot receive messages from another node. In this paper, we suppose that each node has one unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem when the network is a path and the destination node is either at one end or at the center of the path. These protocols are shown to be optimal for any d in the first case, and for d=1,2,3,4, in the second case.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Jean-Claude Bermond Connect in order to contact the contributor
Submitted on : Friday, October 30, 2009 - 5:49:33 PM
Last modification on : Thursday, August 4, 2022 - 4:52:39 PM
Long-term archiving on: : Thursday, June 17, 2010 - 6:50:41 PM


Files produced by the author(s)


  • HAL Id : inria-00429084, version 1



Jean-Claude Bermond, Ricardo Correa, Min-Li Yu. Optimal Gathering Protocols on Paths under Interference Constraints. Discrete Mathematics, 2009, 309 (18), pp.5574-5587. ⟨inria-00429084⟩



Record views


Files downloads