Tuning the Robustness of Routing Information Diffusion with Multi-Point Relays

Optimized Link State Routing is one of the most used routing protocol in wireless networks: static, mobile, ad- hoc, mesh, and even sensor networks. The selection of Multi-Point Relays (MPRs) to build a backbone for signalling traffic, which is often also used to route user traffic, is at the hearth of the protocol and its efficiency is crucial to the protocol efficiency as well as to the entire network topology management. Several heuristics exist that try to minimize the number of MPRs in order to reduce the overall signaling traffic. A recent one, called Selector Set Tie Breaker (SSTB) showed that the number of MPRs can be reduced to a few units in dense networks with hundreds of nodes. This greatly reduces the signaling traffic but also the redundancy of the information that is spread in the network. This paper investigates the consequences of the reduction of the number of MPRs on the robustness of the routing function and introduces a coefficient and a tuning parameter to influence it.