Komplexität der Lokalisierung in drahtlosen Netzwerken

Lassen Sie verschiedene Punkte in . Wir sagen, dass die Punkte und Nachbarn sind, wenn , was bedeutet, dass jeder Punkt Nachbarn mit Punkten mit Indexen innerhalb von , die sich umschließen. $1 ... n$ $\mathbb{R}^2$ $i$ $j$ $|i-j| < 3 \pmod{n-2}$ $2$

Das Problem ist:

Für jedes Paar Nachbarn erhalten wir ihre paarweisen Abstände (und wir wissen, welcher Abstand welchen Punkten entspricht), und wir wollen die paarweisen Abstände aller Punkte rekonstruieren. Meine Fragen sind, was ist die Komplexität dieses Lokalisierungsproblems?

Ich kenne keinen polynomiellen Zeitalgorithmus.

Dies ist auf Lokalisierungsprobleme in Sensornetzwerken zurückzuführen , in denen ad-hoc platzierte Agenten drahtlos mit ihren lexikografischen Nachbarn kommunizieren können und wir ihre Positionen rekonstruieren möchten.

Ich weiß nicht viel über Geometrie- / Lokalisierungsprobleme, daher ist dies möglicherweise einfach oder bekannt. Das nächste Problem, das ich kenne, ist das Turnpike-Problem , auf das @Suresh Venkat kürzlich in diesem Forum hingewiesen hat.

cg.comp-geom Lev Reyzin
quelle

gut definiert? Wenn zwei Punkte auf demselben Punkt in R ^ 2 landen dürfen, können Sie Scharniere herstellen.

RJK

Entschuldigung ...

Lev Reyzin

Lev, es scheint so, als ob tex jetzt aktiviert ist. kannst du versuchen, deinen Beitrag zu bearbeiten, um Latex zu verwenden und zu sehen, ob es funktioniert?

Suresh Venkat

Sie haben nicht geklärt, ob bei gegebener Distanz d ich weiß, welches Paar (i, j) es geschafft hat. Der Unterschied ist entscheidend

Suresh Venkat

@suresh - Ich habe Ihre Frage geklärt - wir kennen die entsprechenden Entfernungen. auch tex support ist super! @Jukka - danke, ich werde deinen Link überprüfen.

Lev Reyzin

Antworten:

(Ich habe keine wirkliche Antwort, aber das war zu lang für einen Kommentar, also poste es hier trotzdem ...)

Ich vermute, dass das Problem NP-schwer ist, wenn man es vom Teilmengen-Summenproblem her reduziert. Eine Beweisidee:

Reduktion: Wenn das - te Element in der Teilmenge Summe Instanz , dann wird der Abstand zwischen dem Knoten und ist , Abstand zwischen und ist , Abstand zwischen und ist auch und der Abstand zwischen und ist . $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}$

Es sei angenommen, dass die Kanten zwischen und für alle vertikal sind. Dann besteht der gesamte Graph aus einer Kette von Rechtecken mit Diagonalen. Sie können jedoch jedes Rechteck "spiegeln", sodass sich entweder auf der linken Seite von oder auf der rechten Seite von . Und Sie müssen die richtige Untergruppe von Flips finden, damit der Abstand zwischen dem letzten Knoten und dem Knoten "korrekt" ist (und der Abstand zwischen und korrekt ist und der Abstand zwischen und ist richtig). $2i-1$ $2i$ $i$ $2i+2$ $2i$ $2i$ $n = 2k$ $2$ $2k-1$ $1$ $2k-1$ $2$

So weit so gut, aber unsere Rechtecke sind nicht wirklich starr; wir könnten auch entlang der Diagonale kippen. Ich denke jedoch, wenn wir einen fiesen Wert wählen , dann könnten wir vielleicht zeigen, dass alles schrecklich schief geht, wenn wir jemals eine Diagonale durchlaufen (z. B. sind die Koordinaten von nicht rational). Dies kann jedoch einige Anpassungen der Werte erforderlich machen . $s$ $2k$ $x_i$

Jukka Suomela
quelle

interessante Idee - danke. Eine kurze Klärungsfrage: Wie können Sie davon ausgehen, dass alle 1-Nachbar-Kanten vertikal sind?

Lev Reyzin

Ich gehe nur davon aus, dass die Kanten 1-2, 3-4, ... vertikal sind. Natürlich können Sie die Ausrichtung der Kante 1-2 beliebig wählen und festlegen, dass sie "vertikal" ist. Dann gibt es nur zwei mögliche Konfigurationen für die Kante 3-4: Entweder ist sie vertikal oder Sie haben entlang der Kante 2-3 "gespiegelt" (gespiegelt). Wir möchten die zweite Möglichkeit vermeiden, die den Beweis erschwert. im teil "so weit so gut ..." finden sie eine mögliche vorstellung, wie man damit umgeht.

Jukka Suomela

Ich

verstehe

Thm 4.1 (pg 50) von cs.yale.edu/homes/dkg6/papers/thesis.pdf diese These besagt, dass das Quadrat eines 2-zusammenhängenden Graphen eine eindeutige Lokalisierung hat. Wenn Sie eine globale Lokalisierung angegeben haben, die durch Lösen der Teilmengensumme gefunden wird, wissen wir, dass es keine weiteren Antworten gibt (und Sie müssen sich keine Gedanken über diagonale Umkehrungen machen). Ich denke, das beendet den Beweis!

Lev Reyzin

Es ist eigentlich NP-schwer. Weitere Informationen finden Sie im folgenden Dokument.

Sriram V. Pemmaraju, Imran A. Pirwani: Virtuelle Realisierung von Einheitskugelgraphen in guter Qualität. ESA 2007: 311-322

Imran Rauf
quelle

Decken die Referenzen tatsächlich den im OP genannten Sonderfall ab? Das heißt, Ihre Graphentopologie ist das Quadrat eines Zyklus?

Jukka Suomela

Du hast ja so recht. Es deckt nur Einbettungen in R ^ d ab.

Imran Rauf

Gute Referenz - danke

Lev Reyzin

Drineas et al. schrieb die Arbeit Distance Matrix Reconstruction from Incomplete Distance Information für Sensor Network Localization . Aber was sie erreichen, ist wahrscheinlich nicht genau das, wonach Sie fragen: Sie berechnen die gesamte Entfernungskarte von einer unvollständigen, selbst bei Rauschen und Knotenausfällen.

Sylvain Peyronnet
quelle