Multipoint relaying

The concept of multipoint relaying is to reduce the number of duplicate retransmissions while forwarding a broadcast packet. This technique restricts the set of nodes retransmitting a packet from all nodes, to a subset of all nodes. The size of this subset depends on the topology of the network.

Figure: Flooding a packet in a wireless multihop network. The arrows show the way information is passed, not all transmissions.

Figure: Flooding a packet in a wireless multihop network from the center node using MPRs(black). The arrows show the way information is passed, not all transmissions.

This is achieved by selecting neighbors as Multipoint relays(MPRs). Every node calculates its own set of MPRs as a subset of its symmetric neighbor nodes chosen so that all 2 hop neighbors can be reached through a MPR. This means that for every node $n$ in the network that can be reached from the local node by at minimum two symmetric hops, there must exist a MPR $m$ so that $n$ has a symmetric link to $m$ and $m$ is a symmetric neighbor of the local node. In the scenario illustrated in figure 3.6, node A selects the black nodes as MPRs. This way all two hop nodes can be reached through a MPR. Node B will not retransmit traffic from A that is to be flooded.

Figure: Node A has selected the black nodes ar its MPRs.

OLSR lets nodes announce their own willingness to act as MPRs for neighbors. 8 levels of willingness are defined from the lowest WILL_NEVER(0), which indicates that this node must never be chosen as a MPR, to the highest WILL_ALWAYS(7), which indicates that this node should always be chosen as a MPR. The willingness is spread through HELLO messages and this information must be considered when calculating MPRs.

Finding the optimal MPR set has been proved to be a NP-complete problem in [62]. RFC 3626 proposes a rather simple heuristic for MPR calculation. The MPR scheme has been further studied and analyzed in amongst others, [52], [15] and [51]. In this thesis the MPR technique is not further analyzed.