# Request Satisfaction Problem in Synchronous Radio Networks

1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We study two algorithmical problems inspired from routing constraints in a multihop synchronous radio network. Our objective is to satisfy a given set of communication requests in the following model: nodes send omnidirectional radio transmissions in synchronous slots; during a given slot, a node can receive a message from an adjacent node if and only if no other neighbor is transmiting - otherwise, radio interferences may occur if two or more neighbors transmit in the same slot -. The objective is to minimize the number of used slots. The two problems differ in the fact that the routing policy may be imposed (DAWN-paths), or not (DAWN-requests). In this second case, a path must be assigned for each request, to define the nodes to use to reach the destination from the source. We present some complexity results, in particular we show that both problems are NP-hard when the network is restricted to a tree. We also present a polynomial algorithm in $O(n^{2K})$ when the number of requests is bounded (by above) by a constant $K$, whether the communication paths are given or not.
Type de document :
Communication dans un congrès
ADHOC-NOW: Ad-hoc, Mobile and Wireless Networks, Sep 2008, Sophia Antipolis, France. 7th International Conference on Ad-hoc, Mobile and Wireless Networks, LNCS (5198), pp.451-462, 2008, 〈10.1007/978-3-540-85209-4_36〉

Littérature citée [13 références]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00322362
Contributeur : Benoit Darties <>
Soumis le : mercredi 17 septembre 2008 - 14:47:48
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : jeudi 3 juin 2010 - 21:40:50

### Fichier

Fichiers produits par l'(les) auteur(s)

### Citation

Benoit Darties, Sylvain Durand, Jérôme Palaysi. Request Satisfaction Problem in Synchronous Radio Networks. ADHOC-NOW: Ad-hoc, Mobile and Wireless Networks, Sep 2008, Sophia Antipolis, France. 7th International Conference on Ad-hoc, Mobile and Wireless Networks, LNCS (5198), pp.451-462, 2008, 〈10.1007/978-3-540-85209-4_36〉. 〈lirmm-00322362〉

### Métriques

Consultations de la notice

## 151

Téléchargements de fichiers