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

12

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

Проблема в:

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

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

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

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

Лев Рейзин
источник
хорошо определены? если двум точкам разрешено приземляться на одну и ту же точку в R ^ 2, то вы можете сделать петли.
RJK
извиняюсь за исправление ...
Лев Рейзин
1
Лев, кажется, что текст теперь включен. Можете ли вы попробовать отредактировать свой пост, чтобы использовать латекс и посмотреть, работает ли он?
Суреш Венкат
Вы не уточнили, с учетом расстояния d я знаю, какая пара (i, j) сделала это. разница решающая
Суреш Венкат
@suresh - я уточнил ваш вопрос - мы знаем соответствующие расстояния. также поддержка текс отлично! @Jukka - спасибо, я проверю вашу ссылку.
Лев Рейзин

Ответы:

4

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

Я подозреваю, что проблема 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 ixi2i12is2i12i+1xi2i2i+2xi2i2i+1s2+xi2

Предположим, что ребра между и для всех являются вертикальными. Тогда весь граф состоит из цепочки прямоугольников с диагоналями. Тем не менее, вы можете «перевернуть» каждый прямоугольник так, чтобы либо на левой стороне либо на правой стороне . И вам нужно найти правильное подмножество сальто, чтобы расстояние между последним узлом и узлом «правильным» (а расстояние между и правильным и расстояние между и правильно).2 i i 2 i + 2 2 i 2 i n = 2 k 2 2 k - 1 1 2 k - 1 22i12ii2i+22i2in=2k22k112k12

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

Юкка Суомела
источник
интересная идея - спасибо. быстрый уточняющий вопрос - что позволяет предположить, что все 1-соседние ребра являются вертикальными?
Лев Рейзин
1
Я только предполагаю, что края 1-2, 3-4, ... являются вертикальными. Конечно, вы можете произвольно выбрать ориентацию ребра 1-2 и определить, что он «вертикальный». Тогда есть только две возможные конфигурации для края 3-4: либо он вертикальный, либо вы перевернули (отразили) вдоль края 2-3. Мы хотели бы избежать второй возможности, которая усложняет доказательство; см. часть "пока все хорошо ...", чтобы узнать, как с этим справиться.
Юкка Суомела
Я вижу - хорошая идея
Лев Рейзин
Thm 4.1 (стр. 50) из cs.yale.edu/homes/dkg6/papers/thesis.pdf этот тезис говорит, что квадрат любого 2-связного графа имеет уникальную локализацию. Учитывая, что вы представили глобальную локализацию, которая определяется путем решения суммы подмножеств, мы знаем, что больше нет ответов (и не нужно беспокоиться о переворотах по диагонали). Я думаю, что это заканчивает доказательство!
Лев Рейзин
6

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

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

Имран Рауф
источник
1
Действительно ли ссылки охватывают особый случай, упомянутый в ОП? То есть ваша топология графа является квадратом цикла?
Юкка Суомела
1
Ты так прав. Он охватывает только вложения в R ^ d.
Имран Рауф
Хорошая ссылка, хотя - спасибо
Лев Рейзин
4

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

Сильвен Пейроннет
источник