HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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 :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 6:24:37 PM
Last modification on : Friday, February 4, 2022 - 3:10:38 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:22:50 PM


  • HAL Id : inria-00071654, version 1



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



Record views


Files downloads