Resistencia de barrera
La resiliencia de la barrera es un problema de optimización algorítmica en geometría computacional motivado por el diseño de redes de sensores inalámbricos , en el que se busca un camino a través de una colección de barreras (a menudo modeladas como discos unitarios ) que atraviesan la menor cantidad posible de barreras.
El problema de la resistencia de la barrera fue introducido por Kumar, Lai y Arora (2005) (utilizando una terminología diferente) para modelar la capacidad de las redes de sensores inalámbricos para detectar intrusos de manera robusta cuando algunos sensores pueden fallar. En este problema, la región bajo vigilancia de cada sensor se modela como un disco unitario en el plano euclidiano . Un intruso puede alcanzar una región objetivo del plano sin ser detectado, si existe un camino en el plano que conecta una región de inicio determinada con la región objetivo sin cruzar ninguno de los discos sensores. La barrera de la resilienciade una red de sensores se define como el mínimo, en todas las rutas desde la región de inicio a la región objetivo, del número de discos de sensores intersectados por la ruta. El problema de la resistencia de las barreras es el problema de calcular este número encontrando una ruta óptima a través de las barreras. [1]
Una simplificación del problema, que encapsula la mayoría de sus características esenciales, hace que la región objetivo sea el origen del plano y la región de inicio sea el conjunto de puntos fuera del casco convexo de los discos sensores. En esta versión del problema, el objetivo es conectar el origen a puntos arbitrariamente alejados del origen mediante una ruta a través de la menor cantidad posible de discos sensores.
Otra variación del problema cuenta el número de veces que una ruta cruza el límite de un disco sensor. Si una ruta cruza el mismo disco varias veces, cada cruce cuenta para el total. El grosor de la barrera de una red de sensores es el número mínimo de cruces de un camino desde la región de inicio a la región de destino. [1]
El espesor de la barrera se puede calcular en tiempo polinomial construyendo la disposición de las barreras (la subdivisión del plano formado al superponer todos los límites de la barrera) y calculando una ruta más corta en el gráfico dual de esta subdivisión. [1]
La complejidad de la resistencia de la barrera para las barreras de disco unitarias es un problema abierto. Puede resolverse mediante un algoritmo manejable de parámetros fijos cuyo tiempo es cúbico en el número total de barreras y exponencial en el cuadrado de la resiliencia, pero no se sabe si tiene una solución de tiempo completamente polinomial. [2] Se sabe que el problema correspondiente para las barreras de algunas otras formas, incluidos los segmentos de línea de longitud unitaria o los rectángulos alineados con el eje con una relación de aspecto cercana a 1, es NP-duro . [3]
