Performance Evaluation of Approximation Algorithms for Multipoint Relay Selection

Overview

In Mobile Ad hoc NETworks (MANET), the selection of Multipoint Relays provides an efficient routing scheme for efficient broadcast and shortest-path unicast. As such a selection is NP-hard, a heuristic has been designed and effectively implemented in protocols for MANET such as the Optimized Link State Routing protocol (OLSR). This paper introduces other heuristics that consider the impact of collision by exploiting the topological properties of the network (without assuming knowledge of geographic positions or geometric properties). For each heuristic, the paper gives its respective provable guaranteed approximation performance when compared to a solution of optimal value.