Optimal Gathering Protocols on Paths under Interference Constraints - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

Optimal Gathering Protocols on Paths under Interference Constraints

Résumé

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.
Fichier non déposé

Dates et versions

inria-00168162 , version 1 (24-08-2007)

Identifiants

  • HAL Id : inria-00168162 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More