Complexité de la localisation dans les réseaux sans fil

12

Soit des points distincts asseyez-vous dans R 2 . On dit que les points i et j sont voisins si | i - j | < 31...nR2ij , ce qui signifie que chaque point est voisin avec des points avec des index à moins de 2 , s'enroulant autour.|ij|<3(modn2)2

Le problème est:

Pour chaque paire de voisins, on nous donne leurs distances par paire (et nous savons quelle distance correspond à quels points), et nous voulons reconstruire les distances par paire de tous les points. Ma question est, quelle est la complexité de ce problème de localisation?

Je ne connais pas d'algorithme de temps polynomial.

Ceci est motivé par des problèmes de localisation dans les réseaux de capteurs , où les agents, placés ad hoc, peuvent communiquer sans fil avec leurs voisins lexicographiques, et nous voulons reconstruire leurs positions.

Je ne connais pas grand-chose aux problèmes de géométrie / localisation, donc cela pourrait être facile ou connu. Le problème le plus proche que je connaisse est le problème de Turnpike , récemment signalé sur ce forum par @Suresh Venkat.

Lev Reyzin
la source
bien défini? si deux points sont autorisés à atterrir sur le même point dans R ^ 2, alors vous pouvez faire des charnières.
RJK
désolé de réparer ...
Lev Reyzin
1
Lev, il semble que tex soit désormais activé. pouvez-vous essayer de modifier votre publication pour utiliser du latex et voir si cela fonctionne?
Suresh Venkat
vous n'avez pas précisé si étant donné une distance d je sais quelle paire (i, j) a réussi. la différence est cruciale
Suresh Venkat
@suresh - J'ai clarifié votre question - nous connaissons les distances correspondantes. aussi le support tex est super! @Jukka - merci, je vais vérifier votre lien.
Lev Reyzin

Réponses:

4

(Je n'ai pas de vraie réponse, mais c'était trop long pour un commentaire, alors postez-le ici quand même ...)

Je soupçonne que le problème est NP-difficile, par réduction du problème de somme de sous-ensemble. Une idée de preuve:

Réduction: si le ème élément dans l'instance de somme de sous-ensemble est x i , alors la distance entre les nœuds 2 i - 1 et 2 i est s , la distance entre 2 i - 1 et 2 i + 1 est x i , la distance entre 2 i et 2 i + 2 est également x i , et la distance entre 2 i et 2 i + 1 estixi2i12is2i12i+1xi2i2i+2xi2i2i+1 .s2+xi2

Supposons que les arêtes entre et 2 i pour tout i soient verticales. Ensuite, le graphique entier se compose d'une chaîne de rectangles avec des diagonales. Cependant, vous pouvez "inverser" chaque rectangle de sorte que 2 i + 2 soit sur le côté gauche de 2 i ou sur le côté droit de 2 i . Et vous devez trouver le bon sous-ensemble de flips pour que la distance entre le dernier nœud n = 2 k et le nœud 2 soit "correcte" (et la distance entre2i12ii2i+22i2in=2k2 et2k1 est correct et la distance entre 2 k - 1 et 2 est correcte).12k12

Jusqu'ici tout va bien, mais nos rectangles ne sont pas vraiment rigides; nous pourrions également retourner le long de la diagonale. Cependant, je pense que si nous choisissons une valeur désagréable , alors nous pourrions peut-être montrer que tout va horriblement mal si nous retournons le long d'une diagonale (par exemple, les coordonnées de 2 k ne seront pas rationnelles)? Cela peut cependant nécessiter quelques ajustements dans les valeurs x i .s2kxi

Jukka Suomela
la source
idée intéressante - merci. une question de clarification rapide - qu'est-ce qui vous permet de supposer que toutes les arêtes à 1 voisin sont verticales?
Lev Reyzin
1
Je suppose seulement que les bords 1-2, 3-4, ... sont verticaux. Bien sûr, vous pouvez choisir arbitrairement l'orientation de l'arête 1-2 et définir qu'elle est "verticale". Ensuite, il n'y a que deux configurations possibles pour le bord 3-4: soit il est vertical ou vous avez "inversé" (miroir) le long du bord 2-3. Nous voudrions éviter la deuxième possibilité qui complique la preuve; voir la partie "jusqu'ici tout va bien ..." pour une idée possible de la façon de gérer cela.
Jukka Suomela
Je vois - bonne idée
Lev Reyzin
Thm 4.1 (pg 50) de cs.yale.edu/homes/dkg6/papers/thesis.pdf cette thèse dit que le carré de tout graphe à 2 connexions a une localisation unique. Étant donné que vous avez présenté une localisation globale qui est trouvée en résolvant la somme des sous-ensembles, nous savons qu'il n'y a plus de réponses (et ne vous inquiétez pas des retournements diagonaux). Je pense que cela termine la preuve!
Lev Reyzin
6

C'est en fait NP-difficile. Voir le document suivant pour les références.

Sriram V. Pemmaraju, Imran A. Pirwani: Réalisation virtuelle de bonne qualité des graphiques à billes unitaires. ESA 2007: 311-322

Imran Rauf
la source
1
Les références couvrent-elles réellement le cas spécial mentionné dans le PO? Autrement dit, votre topologie graphique est le carré d'un cycle?
Jukka Suomela
1
Tu as tellement raison. Il ne couvre que les plongements dans R ^ d.
Imran Rauf
Bonne référence cependant - merci
Lev Reyzin