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.

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

Maccari, Leonardo;
2018

Abstract

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.
File in questo prodotto:
File Dimensione Formato  
mpr-submitted.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Accesso chiuso-personale
Dimensione 841.74 kB
Formato Adobe PDF
841.74 kB Adobe PDF Visualizza/Apri
1-s2.0-S1570870518301537-main.pdf

non disponibili

Tipologia: Versione dell'editore
Licenza: Accesso chiuso-personale
Dimensione 2.04 MB
Formato Adobe PDF
2.04 MB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10278/3717581
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 8
social impact