La resiliencia de barreras 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 atraviese la menor cantidad de barreras posible.
El problema de la resiliencia de la barrera fue introducido por Kumar, Lai y Arora (2005) (usando 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 avión sin ser detectado, si existe un camino en el avión que conecta una región de inicio determinada con la región objetivo sin cruzar ninguno de los discos sensores. La resiliencia de barrera de una red de sensores se define como el mínimo, en todos los caminos desde la región inicial hasta la región objetivo, del número de discos de sensores atravesados por el camino. El problema de la resiliencia de las barreras es el problema de calcular este número encontrando un camino óptimo a través de las barreras. [1]
Una simplificación del problema, que resume la mayoría de sus características esenciales, hace que la región objetivo sea el origen del avión y la región inicial 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 un camino a través de la menor cantidad posible de discos sensores.
Otra variación del problema cuenta el número de veces que un camino cruza el límite de un disco sensor. Si un camino cruza el mismo disco varias veces, cada cruce cuenta para el total. El espesor de la barrera de una red de sensores es el número mínimo de cruces de un camino desde la región inicial hasta la región objetivo. [1]
El espesor de la barrera se puede calcular en tiempo polinómico construyendo la disposición de las barreras (la subdivisión del plano formado al superponer todos los límites de las barreras) y calculando el camino más corto en el gráfico dual de esta subdivisión. [1]
La complejidad de la resiliencia de las barreras de disco unitario 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 temporal totalmente polinomial. [2] Se sabe que el problema correspondiente para barreras de algunas otras formas, incluidos segmentos de línea de longitud unitaria o rectángulos alineados con el eje con una relación de aspecto cercana a 1, es NP-duro . [3]
Una variación del problema de resiliencia de la barrera, estudiada por Kumar, Lai y Arora (2005), restringe tanto los sensores como la ruta de escape a un rectángulo en el plano. En esta variación, el objetivo es encontrar un camino desde el lado superior del rectángulo hasta el lado inferior que pase a través de la menor cantidad posible de discos sensores. Al aplicar el teorema de Menger al gráfico de discos unitarios definido a partir de las barreras, se puede demostrar que este número mínimo de discos es igual al número máximo de subconjuntos en los que se pueden dividir todos los discos, de modo que cada subconjunto contenga una cadena de discos que pasan todos el camino desde el lado izquierdo al derecho del rectángulo. Como mostraron Kumar, Lai y Arora (2005), esta caracterización permite calcular la resiliencia óptima en tiempo polinómico transformando el problema en una instancia del problema de flujo máximo .
Para discos unitarios con capas acotadas (el número máximo de discos que tienen una intersección común) existe un esquema de aproximación de tiempo polinomial para la resiliencia, que se puede generalizar a formas de barrera del mismo tamaño entre sí con relaciones de aspecto acotadas. [2] Para discos unitarios sin asumir capas acotadas, el problema de calcular la resiliencia se puede aproximar dentro de un factor constante, utilizando el hecho de que para esta forma de barrera el camino óptimo solo puede cruzar cada barrera un número constante de veces, por lo que el espesor de la barrera y la resiliencia de la barrera están dentro de un factor constante entre sí. [1] Se pueden generalizar métodos similares a sensores no uniformes de aproximadamente el mismo tamaño. [4]