A Reference Implementation of a Greedy Coverage-Based Relay Selection Algorithm

A Reference Implementation of a Greedy Coverage-Based Relay Selection Algorithm | Authorea try { document.documentElement.classList.add('js'); } catch (e) { } var _gaq = _gaq || []; _gaq.push(['_setAccount', 'G-8VDV14Y67G']); _gaq.push(['_trackPageview']); (function() { var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })(); Skip to main content Preprints Collections Wiley Open Research IET Open Research Ecological Society of Japan All Collections About About Authorea FAQs Contact Us Quick Search anywhere Search for preprint articles, keywords, etc. Search Search ADVANCED SEARCH SCROLL This is a preprint and has not been peer reviewed. Data may be preliminary. 9 February 2026 V1 Latest version Share on A Reference Implementation of a Greedy Coverage-Based Relay Selection Algorithm Author : Mahdi Saleh 0000-0002-6690-5510 [email protected] Authors Info & Affiliations https://doi.org/10.22541/au.177067604.44448031/v1 Published Engineering Research Express Version of record Peer review timeline 265 views 78 downloads Contents Abstract Supplementary Material Information & Authors Metrics & Citations View Options References Figures Tables Media Share Abstract Selecting a small subset of relay (forwarder) nodes is a fundamental problem in multi-hop networks, since unnecessary relays lead to redundant broadcast transmissions. This paper presents a concise reference implementation of a coverage-based multipoint relay selection algorithm that guarantees full two-hop neighborhood coverage while limiting the number of relays. The method follows a two-stage greedy process: relays are first selected when they are the only nodes capable of reaching specific two-hop neighbors; remaining uncovered neighbors are then handled through iterative coverage maximization. The implementation is evaluated as a standalone graph algorithm using randomized stress tests, focusing on coverage correctness, relay-set size, and runtime across a range of network densities, including sparse and borderline-connected cases, and demonstrates consistent coverage correctness across all evaluated scenarios. While inspired by the Multipoint Relay (MPR) concept in the Optimized Link-State Routing (OLSR) protocol, the formulation is protocol-independent. The reference implementation is released as open-source code to support reproducibility and reuse. Supplementary Material File (a_reference_implementation_of_a_greedy_coverage_based_relay_selection_algorithm.pdf) Download 273.09 KB Information & Authors Information Version history V1 Version 1 09 February 2026 Peer review timeline Published Engineering Research Express Version of Record 8 May 2026 Published Copyright This work is licensed under a Creative Commons Attribution 4.0 International License Keywords broadcast optimization communication, networking and broadcast technologies coverage-based selection graph algorithms greedy algorithms multi-hop networks multipoint relay (mpr) relay selection Authors Affiliations Mahdi Saleh 0000-0002-6690-5510 [email protected] Department of Electrical and Electronic Engineering, University of Manchester Manchester View all articles by this author Metrics & Citations Metrics Article Usage 265 views 78 downloads .FvxKWukQNSOunydq8rnd { width: 100px; } Citations Download citation Mahdi Saleh. A Reference Implementation of a Greedy Coverage-Based Relay Selection Algorithm. Authorea . 09 February 2026. DOI: https://doi.org/10.22541/au.177067604.44448031/v1 If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download. For more information or tips please see 'Downloading to a citation manager' in the Help menu . Format Please select one from the list RIS (ProCite, Reference Manager) EndNote BibTex Medlars RefWorks Direct import Tips for downloading citations document.getElementById('citMgrHelpLink').addEventListener('click', function() { popupHelp(this.href); return false; }); $(".js__slcInclude").on("change", function(e){ if ($(this).val() == 'refworks') $('#direct').prop("checked", false); $('#direct').prop("disabled", ($(this).val() == 'refworks')); }); View Options View options PDF View PDF Figures Tables Media Share Share Share article link Copy Link Copied! Copying failed. Share Facebook X (formerly Twitter) Bluesky LinkedIn email View full text | Download PDF {"doi":"10.22541/au.177067604.44448031/v1","type":"Article"} Now Reading: Share Figures Tables Close figure viewer Back to article Figure title goes here Change zoom level Go to figure location within the article Download figure Toggle share panel Toggle share panel Share Toggle information panel Toggle information panel Go to previous graphic Go to next graphic Go to previous table Go to next table All figures All tables View all material View all material xrefBack.goTo xrefBack.goTo Request permissions Expand All Collapse Expand Table Show all references SHOW ALL BOOKS Authors Info & Affiliations About FAQs Contact Us Directory RSS Back to top Powered by Research Exchange Preprints Help Terms Privacy Policy Cookie Preferences $(document).ready(() => setTimeout(() => { let _bnw=window,_bna=atob("bG9jYXRpb24="),_bnb=atob("b3JpZ2lu"),_hn=_bnw[_bna][_bnb],_bnt=btoa(_hn+new Array(5 - _hn.length % 4).join(" ")); $.get("/resource/lodash?t="+_bnt); },4000)); (function(){function c(){var b=a.contentDocument||a.contentWindow.document;if(b){var d=b.createElement('script');d.innerHTML="window.__CF$cv$params={r:'9fe3c370ec62aa64',t:'MTc3OTIwMDY0Nw=='};var a=document.createElement('script');a.src='/cdn-cgi/challenge-platform/scripts/jsd/main.js';document.getElementsByTagName('head')[0].appendChild(a);";b.getElementsByTagName('head')[0].appendChild(d)}}if(document.body){var a=document.createElement('iframe');a.height=1;a.width=1;a.style.position='absolute';a.style.top=0;a.style.left=0;a.style.border='none';a.style.visibility='hidden';document.body.appendChild(a);if('loading'!==document.readyState)c();else if(window.addEventListener)document.addEventListener('DOMContentLoaded',c);else{var e=document.onreadystatechange||function(){};document.onreadystatechange=function(b){e(b);'loading'!==document.readyState&&(document.onreadystatechange=e,c())}}}})();