A hybrid metaheuristic strategy for covering with wireless device
Fecha
01/10/2012Autor
Estado
info:eu-repo/semantics/publishedVersionMetadatos
Mostrar el registro completo del ítemResumen
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.
A hybrid metaheuristic strategy for covering with wireless device
Tipo de Actividad
Artículos en revistasISSN
0948-695XPalabras Clave
Geometría Computacional, Problema de Galerías de Arte, Problemas de Visibilidad y Cobertura, Metaheurísticas Híbridas y Algoritmos Aproximados.Computational Geometry, Art Gallery Problems, Visibility and Coverage Problems, Hybrid Metaheuristics and Approximation Algorithms.