Сложность локализации в беспроводных сетях

Пусть отдельные точки находятся в . Мы говорим, что точки и являются соседями, если | ij | <3 \ pmod {n-2} , что означает, что каждая точка является соседом с точками с индексами в пределах 2 , обтеканием.R 2 i $1 ... n$$\mathbb{R}^2$$i$$j$$|i-j| < 3 \pmod{n-2}$$2$

Проблема в:

Для каждой пары соседей нам даны их попарные расстояния (и мы знаем, какое расстояние соответствует каким точкам), и мы хотим восстановить попарные расстояния всех точек. Мои вопросы, какова сложность этой проблемы локализации?

Я не знаю алгоритма полиномиального времени.

Это связано с проблемами локализации в сенсорных сетях , где агенты, размещенные в режиме ad-hoc, могут осуществлять беспроводную связь со своими лексикографическими соседями, и мы хотим восстановить их позиции.

Я не знаю много о проблемах геометрии / локализации, так что это может быть легко или известно. Самая близкая проблема, о которой я знаю, - это проблема Turnpike , недавно упомянутая на этом форуме @Suresh Venkat.

(У меня нет реального ответа, но это было слишком долго для комментария, так что в любом случае размещать его здесь ...)

Я подозреваю, что проблема NP-трудна, путем сокращения от проблемы суммы подмножеств. Идея доказательства:

Сокращение: если й элемент в экземпляре суммы поднабора равен , то расстояние между узлами и равно , расстояние между и равно , расстояние между и также равно и расстояние между и равно .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}$

Предположим, что ребра между и для всех являются вертикальными. Тогда весь граф состоит из цепочки прямоугольников с диагоналями. Тем не менее, вы можете «перевернуть» каждый прямоугольник так, чтобы либо на левой стороне либо на правой стороне . И вам нужно найти правильное подмножество сальто, чтобы расстояние между последним узлом и узлом «правильным» (а расстояние между и правильным и расстояние между и правильно).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$

Пока все хорошо, но наши прямоугольники не очень жесткие; мы могли бы также перевернуть диагональ. Тем не менее, я думаю, что если мы выберем неприятное значение , то, возможно, мы могли бы показать, что все идет ужасно неправильно, если мы когда-нибудь перевернем диагональ (например, координаты не будут рациональными)? Это может потребовать некоторых изменений в значениях .2 к х $s$$2k$$x_i$

Это на самом деле NP-жесткий. См. Следующую статью для справок.

Шрирам В. Пеммараю, Имран А. Пирвани: хорошее качество виртуальной реализации единичных шаровых графов. ESA 2007: 311-322

Drineas et al. написал статью « Восстановление матрицы расстояний по неполной информации о расстоянии для локализации сенсорной сети» . Но то, что они достигают, вероятно, не совсем то, что вы просите: они вычисляют всю карту расстояний из неполной, даже при наличии шума и отказов узлов.