Optimal gathering algorithms in multi-hop radio tree networks with interferences.

Jean-Claude Bermond 1 Min-Li Yu 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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 pre-defined destination node under the interference constraints. In such a network, a message can only be properly received if there is no interference from another message being simultaneously transmitted. The network is modeled as a graph, where the vertices represent the nodes and the edges, the possible com- munications. The interference constraint is modeled by a fixed integer dI ? 1, which implies that nodes within distance d I in the graph from one sender cannot receive messages from another node. In this paper, we suppose that it takes one unit of time (slot) to transmit a unit-length message. A step (or round) consists of a set of non interfering (compat- ible) calls and uses one slot. We present optimal algorithms that give minimum number of steps (delay) for the gathering problem with buffer- ing possibility, when the network is a tree, the root is the destination and dI = 1. In fact we study the equivalent personalized broadcasting problem instead.
Type de document :
Article dans une revue
Ad Hoc and Sensor Wireless Networks, Old City Publishing, 2010, 9 (1-2), pp.109-128
Liste complète des métadonnées

https://hal.inria.fr/inria-00505517
Contributeur : Jean-Claude Bermond <>
Soumis le : vendredi 23 juillet 2010 - 22:42:51
Dernière modification le : vendredi 23 juillet 2010 - 22:42:51

Identifiants

  • HAL Id : inria-00505517, version 1

Collections

Citation

Jean-Claude Bermond, Min-Li Yu. Optimal gathering algorithms in multi-hop radio tree networks with interferences.. Ad Hoc and Sensor Wireless Networks, Old City Publishing, 2010, 9 (1-2), pp.109-128. <inria-00505517>

Partager

Métriques

Consultations de la notice

192