Skip to Main content Skip to Navigation
Reports

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

Bernard Mans 1
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : 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,...).
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071654
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:24:37 PM
Last modification on : Wednesday, October 14, 2020 - 4:00:29 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:22:50 PM

Identifiers

  • HAL Id : inria-00071654, version 1

Collections

Citation

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

Share

Metrics

Record views

217

Files downloads

478