Article: Revisiting multipoint relay selection in the optimized link state routing protocol Journal: International Journal of Communication Networks and Distributed Systems (IJCNDS) 2009 Vol.2 No.1 pp.4 - 15 Abstract: The objective of the multipoint relay (MPR) technique is to reduce the number of redundant retransmissions, while ensuring reliable delivery of broadcast messages in wireless networks. To do this, it is necessary to select a small set of re-transmitter nodes, called multipoint relays. Selecting multipoint relays is a fundamental operation in the optimized link-state routing (OLSR) protocol. Research on MPR selection commonly focuses on heuristics. We propose to model MPR selection as a mixed-integer program. Solving this model optimally provides the means to accurately analyse and compare MPR selection heuristics. We also propose a new method for exploring the graph model of the network in order to satisfy the required constraints optimally. We call this exploration method reversible marking. We then combine this reversible marking mechanism with the simple greedy heuristic to create a new OLSR-compliant MPR selection heuristic. Testing has shown that our heuristic offers a good compromise between the need to minimise the number of MPR and the need to insure good coverage. Inderscience Publishers - linking academia, business and industry through research

Title: Revisiting multipoint relay selection in the optimized link state routing protocol

Authors: Dhavy Gantsou, Patrick Sondi, Saïd Hanafi

Addresses: University of Valenciennes, LAMIH/ROI &ndash UMR CNRS 8530, Le Mont Houy &ndash ISTV2, F-59313 Valenciennes cedex 9, France. ' University of Valenciennes, LAMIH/ROI &ndash UMR CNRS 8530, Le Mont Houy &ndash ISTV2, F-59313 Valenciennes cedex 9, France. ' University of Valenciennes, LAMIH/ROI &ndash UMR CNRS 8530, Le Mont Houy &ndash ISTV2, F-59313 Valenciennes cedex 9, France

Abstract: The objective of the multipoint relay (MPR) technique is to reduce the number of redundant retransmissions, while ensuring reliable delivery of broadcast messages in wireless networks. To do this, it is necessary to select a small set of re-transmitter nodes, called multipoint relays. Selecting multipoint relays is a fundamental operation in the optimized link-state routing (OLSR) protocol. Research on MPR selection commonly focuses on heuristics. We propose to model MPR selection as a mixed-integer program. Solving this model optimally provides the means to accurately analyse and compare MPR selection heuristics. We also propose a new method for exploring the graph model of the network in order to satisfy the required constraints optimally. We call this exploration method reversible marking. We then combine this reversible marking mechanism with the simple greedy heuristic to create a new OLSR-compliant MPR selection heuristic. Testing has shown that our heuristic offers a good compromise between the need to minimise the number of MPR and the need to insure good coverage.

Keywords: optimized link state routing protocol; OLSR; multipoint relay selection; reversible marking; redundant retransmissions; reliable delivery; broadcast messages; wireless networks.

DOI: 10.1504/IJCNDS.2009.021691

International Journal of Communication Networks and Distributed Systems, 2009 Vol.2 No.1, pp.4 - 15

Published online: 30 Nov 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: Revisiting multipoint relay selection in the optimized link state routing protocol

Keep up-to-date