HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Optimal Gathering Protocols on Paths under Interference Constraints

Jean-Claude Bermond 1 Ricardo Correa 2 Min-Li Yu 3
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 simultaneously transmitted. 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 $\di \geq 1$, which implies that nodes within distance $ \di$ 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. The protocols are shown to be optimal for any $d$ in the first case, and for $1 \leq \di \leq 4$, in the second case.
Document type :
Complete list of metadata

Contributor : Jean-Claude Bermond Connect in order to contact the contributor
Submitted on : Friday, August 24, 2007 - 5:35:37 PM
Last modification on : Friday, February 4, 2022 - 3:20:15 AM


  • HAL Id : inria-00168162, version 1



Jean-Claude Bermond, Ricardo Correa, Min-Li Yu. Optimal Gathering Protocols on Paths under Interference Constraints. [Research Report] 2007, pp.23. ⟨inria-00168162⟩



Record views