In the last years, wireless mesh networks (WMNs) have gained more and more popularity in many research and industrial applications thanks to their easy implementation, maintenance, and great reliability at a low cost. Nevertheless, for a large number of nodes, the performance of such networks is heavily influenced by the positioning of routers and gateways over the area to be covered. In this paper, we tackle the router placement problem, which is known to be NP-hard, and its approximate solution through a meta-heuristic approach. The proposed solution empowers the benefits offered by a genetic algorithm pre-hybridized with a local search approach inspired by the behavior of hound dogs. The basic idea is to exploit the dogs’ capabilities in moving throughout the solution space to effectively explore it by placing themselves in areas that are more favorable for achieving a high-quality approximate solution in a reasonable time. Experimental results on several benchmarking instances and comparisons with the most effective state-of-the-art algorithms have demonstrated the potential of the proposed approach. This is evidenced by very high connectivity and coverage, a low number of generations, and a small GA population required for convergence. This results in low computational effort and significant time savings, which are of paramount importance in IoT and edge scenarios. We remark that, although offering potential, at the current state, our proposal is not able to adapt to areas with obstacles or irregular shapes.

A hound-inspired pre-hybridized genetic approach for router placement in wireless mesh networks

D'Angelo G.;Palmieri F.
2024-01-01

Abstract

In the last years, wireless mesh networks (WMNs) have gained more and more popularity in many research and industrial applications thanks to their easy implementation, maintenance, and great reliability at a low cost. Nevertheless, for a large number of nodes, the performance of such networks is heavily influenced by the positioning of routers and gateways over the area to be covered. In this paper, we tackle the router placement problem, which is known to be NP-hard, and its approximate solution through a meta-heuristic approach. The proposed solution empowers the benefits offered by a genetic algorithm pre-hybridized with a local search approach inspired by the behavior of hound dogs. The basic idea is to exploit the dogs’ capabilities in moving throughout the solution space to effectively explore it by placing themselves in areas that are more favorable for achieving a high-quality approximate solution in a reasonable time. Experimental results on several benchmarking instances and comparisons with the most effective state-of-the-art algorithms have demonstrated the potential of the proposed approach. This is evidenced by very high connectivity and coverage, a low number of generations, and a small GA population required for convergence. This results in low computational effort and significant time savings, which are of paramount importance in IoT and edge scenarios. We remark that, although offering potential, at the current state, our proposal is not able to adapt to areas with obstacles or irregular shapes.
2024
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS 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: https://hdl.handle.net/11386/4884118
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact