Heuristics for MPR selection

Each node of the network independently selects its own set of MPRs. The MPR set is calculated to contain a subset of the 1-hop neighbors which provide maximum bandwidth to each 2-hop neighbor. The MPR set needs not be optimal, however it SHOULD be small enough to minimize the flooding of broadcast messages in the network.

The heuristic for the selection of multipoint relays in the standard OLSR does not take into account other metrics. It computes a multipoint relay set of minimal cardinality. Links with interesting metrics can be omitted. Consequently, the path calculated between two nodes using the known partial topology is not the best one in the whole network.

The decision of how each node selects its MPRs is essential to determine the maximum capacity in the network. In the MPR selection, links with better metrics are very important and SHOULD not be omitted.

We have developed two heuristics:

  • MPR-1: prefer locally better neighbors in case of a tie;
  • MPR-2: select neighbors that locally offer best metrics.

We have proved that MPR-2 yields better performance.

Webmaster: Ignacy Gawędzki