Novel hybrid heuristics for an extension of the dynamic relay deployment problem over disaster areas

  1. Miren Nekane Bilbao 1
  2. Sergio Gil-López 2
  3. Javier Del Ser 2
  4. Sancho Salcedo-Sanz 3
  5. Mikel Sánchez-Ponte 2
  6. Antonio Arana-Castro 4
  1. 1 Universidad del País Vasco, España
  2. 2 Tecnalia Research and Innovation, España
  3. 3 Universidad de Alcalá, España
  4. 4 HISPASAT, S.A., España
Revista:
Top

ISSN: 1863-8279 1134-5764

Año de publicación: 2014

Volumen: 22

Número: 3

Páginas: 997-1016

Tipo: Artículo

Otras publicaciones en: Top

Resumen

In this paper, we propose a novel autonomous intelligent tool for the optimum design of a wireless relayed communication network deployed over disaster areas. The so-called dynamic relay deployment problem consists of finding the optimum number of deployed relays and their location aimed at simultaneously maximizing the overall number of mobile nodes covered and minimizing the cost of the deployment. In this paper, we extend the problem by considering diverse relay models characterized by different coverage radii and associated costs. To efficiently tackle this problem we derive a novel hybrid scheme comprising: (1) a Harmony Search (HS)-based global search procedure and (2) a modified version of the well-known K-means clustering algorithm as a local search technique. Single- and bi-objective formulations of the algorithm are proposed for emergency and strategic operational planning, respectively. Monte Carlo simulations are run over a emulated scenario based on real statistical data from the Castilla La Mancha region (center of Spain) to show that, in comparison with a standard implementation of the K-means algorithm followed by a exhaustive search procedure over all relay-model combinations, the proposed scheme renders on average better coverage levels and reduced costs providing, at the same time, an intelligent tool capable of simultaneously determining the number and models of the relays to be deployed.

Información de financiación

Acknowledgments This work has been supported by the ‘‘Centro para el Desarrollo Tecnologico Industrial’’ (CDTI) of the Spanish Ministry of Science and Innovation through the PROMETEO-CENIT project, as well as by the Spanish Ministry of Science and Innovation under project ECO2010-22065-C03-02.