A hybrid metaheuristic strategy for covering with wireless device

Abstract

En este trabajo nos centramos en soluciones aproximadas para resolver una nueva clase del Problema de Galerías de Arte inspirados en la localización inalámbrica. En vez de los guardias habituales consideramos dispositivos inalámbricos cuya señal puede cruzar cierto número k de paredes.Estos dispositivos se llaman k-transmisores. Proponemos un algoritmo para construir el polígono de visibilidad de un k-transmisor situado en un punto de un polígono simple. Entonces aplicamos una estrategia metaheurística híbrida para abordar el problema de minimizar el número de k-transmisores situados en los vértices que cubren un polígono simple dado se comparan sus resultados con metaheurísticas puras. Concluimos que las soluciones aproximadas obtenidas con la estrategia híbrida para 2 transmisores y 4 transmisores en polígonos monótonos, polígonos ortogonales y polígonos ortogonales monótonos son mejores que las soluciones obtenidas con las estrategias puras.

In this paper we focus on approximate solutions to solve a new class of Art Gallery Problems inspired by wireless localization. Instead of the usual guards we consider wireless devices whose signal can cross a certain number, k, of walls. These devices are called k-transmitters. We propose an algorithm for constructing the visibility region of a k-transmitter located on a point of a simple polygon. Then we apply a hybrid metaheuristic strategy to tackle the problem of minimizing the number of k-transmitters, located at vertices, that cover a given simple polygon, and compare its performance with two pure metaheuristics. We conclude that the approximate solutions obtained with the hybrid strategy, for 2-transmitters and 4-transmitters, on simple polygons, monotone polygons, orthogonal polygons and monotone orthogonal polygons, are better than the solutions obtained with the pure strategies.