Where have all the MPRs gone? On the optimal selection of Multi-Point Relays

Optimized Link State Routing (OLSR) is a widespread routing protocol in wireless mesh networks: static, mobile, ad-hoc, and even sensor networks. The selection of Multi-Point Relays (MPR) that form a signaling backbone is at the heart of the protocol and it is a crucial process to reduce the signaling overhead. Since the protocol proposal and specification, the original heuristic for MPRs selection has been largely studied showing it has good local properties; however, this does not give insight about the properties of the global set of MPRs. Here lays the contribution of this paper: First we define the problem of the minimization of the global MPR set (the union of all the MPR sets) as a centralized integer linear programming problem, which is NP-hard. We are able to solve it for networks of practical size, up to 150 nodes. Second, we define a bound that we call the “distributed optimum,” which we show to be a lower bound for distributed MPR selection algorithms, still requiring considerable power to be computed. Finally, we set-up an experimental performance evaluation methodology and we show that a heuristic that we recently proposed performs very close to the distributed optimum, and always outperforms the original heuristic.