Complejidad de localización en redes inalámbricas

Deje puntos distintos $1 ... n$ sentarse en $\mathbb{R}^2$ . Decimos que los puntos $i$ y $j$ son vecinos si , lo que significa que cada punto es vecino con puntos con índices dentro de 2 , envolviendo.$|i-j| < 3 \pmod{n-2}$$2$

El problema es:

Para cada par de vecinos se nos dan sus distancias por pares (y sabemos qué distancia corresponde a qué puntos), y queremos reconstruir las distancias por pares de todos los puntos. Mi pregunta es, ¿cuál es la complejidad de este problema de localización?

No sé de un algoritmo de tiempo polinómico.

Esto está motivado por problemas en la localización en redes de sensores , donde los agentes, colocados ad-hoc, pueden comunicarse de forma inalámbrica con sus vecinos lexicográficos, y queremos reconstruir sus posiciones.

No sé mucho sobre problemas de geometría / localización, por lo que esto podría ser fácil o conocido. El problema más cercano que conozco es el problema Turnpike , recientemente señalado en este foro por @Suresh Venkat.

(No tengo una respuesta real, pero esto fue demasiado largo para un comentario, así que publícalo aquí de todos modos ...)

Yo sospecho que el problema es NP-duro, por la reducción del problema de la suma de subconjuntos. Una idea de prueba:

Reducción: si el ésimo elemento en la instancia de suma de subconjuntos es , entonces la distancia entre los nodos y es , la distancia entre y es , la distancia entre y también es , y la distancia entre y es .x i 2 i - 1 2 i s 2 i - 1 2 i + 1 x i 2 i 2 i + 2 x i 2 i 2 i + 1 $i$$x_i$$2i-1$$2i$$s$$2i-1$$2i+1$$x_i$$2i$$2i+2$$x_i$$2i$$2i+1$$\sqrt{s^2 + x_i^2}$

Suponga que los bordes entre y para todo son verticales. Entonces todo el gráfico consiste en una cadena de rectángulos con diagonales. Sin embargo, puede "voltear" cada rectángulo para que esté en el lado izquierdo de o en el lado derecho de . Y necesita encontrar el subconjunto correcto de volteos para que la distancia entre el último nodo y el nodo sea ​​"correcta" (y la distancia entre y sea ​​correcta y la distancia entre y es correcto).2 i i 2 i + 2 2 i 2 i n = 2 k 2 2 k - 1 1 2 k - 1 $2i-1$$2i$$i$$2i+2$$2i$$2i$$n = 2k$$2$$2k-1$$1$$2k-1$$2$

Hasta ahora todo bien, pero nuestros rectángulos no son realmente rígidos; También podríamos voltear a lo largo de la diagonal. Sin embargo, creo que si elegimos un valor desagradable , ¿tal vez podríamos demostrar que todo sale terriblemente mal si alguna vez volteamos a lo largo de una diagonal (por ejemplo, las coordenadas de no serán racionales)? Sin embargo, esto puede requerir algunos ajustes en los valores .2 k x $s$$2k$$x_i$

En realidad es NP-hard. Consulte el siguiente documento para obtener referencias.

Sriram V. Pemmaraju, Imran A. Pirwani: Realización virtual de buena calidad de gráficos de bolas de unidad. ESA 2007: 311-322

Drineas y col. escribió el documento Reconstrucción de matriz de distancia a partir de información de distancia incompleta para la localización de la red de sensores . Pero lo que logran probablemente no sea exactamente lo que usted pide: calculan el mapa de distancia completo de uno incompleto, incluso en presencia de ruido y fallas de nodos.