Złożoność lokalizacji w sieciach bezprzewodowych

Niech wyraźne punkty $1 ... n$ siedzieć $\mathbb{R}^2$ . Mówimy, że punkty $i$ i $j$ są sąsiadami, jeśli , co oznacza, że ​​każdy punkt jest sąsiadem z punktami o indeksach w obrębie 2 , otaczających.$|i-j| < 3 \pmod{n-2}$$2$

Problemem jest:

Dla każdej pary sąsiadów podajemy ich odległości par (i wiemy, która odległość odpowiada danym punktom) i chcemy zrekonstruować odległości par wszystkich punktów. Moje pytania brzmią: jaka jest złożoność tego problemu z lokalizacją?

Nie znam algorytmu wielomianowego czasu.

Jest to motywowane problemami z lokalizacją w sieciach czujników , w których agenci, umieszczeni ad hoc, mogą bezprzewodowo komunikować się ze swoimi leksykograficznymi sąsiadami, a my chcemy zrekonstruować ich pozycje.

Nie wiem dużo o problemach z geometrią / lokalizacją, więc może to być łatwe lub znane. Najbliższym problemem, o którym wiem, jest problem Turnpike , na który niedawno wskazał na tym forum @Suresh Venkat.

(Nie mam prawdziwej odpowiedzi, ale było to zbyt długo na komentarz, więc opublikuj go tutaj ...)

I podejrzewam , że problem jest NP-trudne, przez redukcję od problemu sumy podzbioru. Pomysł na dowód:

Redukcja: jeśli ty element w instancji sumy podzbioru wynosi , to odległość między węzłami i wynosi , odległość między a wynosi , odległość między a również jest , a odległość między a wynosi .$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}$

Załóżmy, że krawędzie między a dla wszystkich są pionowe. Cały wykres składa się z łańcucha prostokątów z przekątnymi. Możesz jednak „przerzucić” każdy prostokąt, tak aby znajdował się po lewej stronie lub po prawej stronie . Musisz znaleźć odpowiedni podzestaw przerzutów, aby odległość między ostatnim węzłem a węzłem była „poprawna” (a odległość między a jest prawidłowa, a odległość między a jest poprawne).$2i-1$$2i$$i$$2i+2$$2i$$2i$$n = 2k$$2$$2k-1$$1$$2k-1$$2$

Jak dotąd tak dobrze, ale nasze prostokąty nie są tak naprawdę sztywne; moglibyśmy również przerzucić wzdłuż przekątnej. Myślę jednak, że jeśli wybierzemy nieprzyjemne wartości , to być może moglibyśmy pokazać, że wszystko pójdzie strasznie źle, jeśli kiedykolwiek przerzucimy przekątną (np. Współrzędne nie będą racjonalne)? Może to jednak wymagać pewnych poprawek w wartościach .$s$$2k$$x_i$

To jest w rzeczywistości trudne NP. Odwołaj się do poniższej pracy.

Sriram V. Pemmaraju, Imran A. Pirwani: Dobra jakość wirtualnej realizacji grafów z kulkami jednostkowymi. ESA 2007: 311–322

Drineas i in. napisał artykuł Rekonstrukcja macierzy odległości z niekompletnych informacji o odległości dla lokalizacji sieci czujników . Ale to, co osiągają, prawdopodobnie nie jest dokładnie tym, o co prosisz: obliczają całą mapę odległości z niepełnej, nawet w obecności hałasu i awarii węzłów.