Approximation Algorithms for Multi-Point Relay Selection in Mobile Wireless Networks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2003

Approximation Algorithms for Multi-Point Relay Selection in Mobile Wireless Networks

Résumé

Routing is one of the main problems for Mobile Wireless Networks. In the case of infrastructureless multihop wireless networks, the selection of Multi-Point Relays provides efficient routing schemes. As such a selection is NP-hard, an efficient heuristic has been designed and effectively implemented in protocols for Mobile Ad Hoc Networks such as the Optimized Link State Routing protocol (OLSR). In this paper, we introduce two variants of this practical heuristic by exploiting the topological properties of the network (without assuming a knowledge of geographic positions or geometric properties). For each heuristic, we give their respective guaranteed approximation performances when compared to a solution of optimal value. We argue that the heuristics proposed are of considerable interest when other problems are considered in addition to the routing efficiency (e.g., minimum remaining bandwidth, minimum remaining energy,...).
Fichier principal
Vignette du fichier
RR-4925.pdf (286.97 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00071654 , version 1 (23-05-2006)

Identifiants

  • HAL Id : inria-00071654 , version 1

Citer

Bernard Mans. Approximation Algorithms for Multi-Point Relay Selection in Mobile Wireless Networks. [Research Report] RR-4925, INRIA. 2003. ⟨inria-00071654⟩
108 Consultations
314 Téléchargements

Partager

Gmail Facebook X LinkedIn More