Барьерная устойчивость - Barrier resilience

Барьерная устойчивость. У этого экземпляра устойчивость = 1 (можно соединить зеленые области дорогой, которая пересекает только один барьер, синий), но барьер должен быть пересечен путем дважды.

Барьерная устойчивость является алгоритмический проблема оптимизации в вычислительная геометрия мотивированы дизайном беспроводные сенсорные сети, в котором человек ищет путь через набор препятствий (часто моделируемых как единичные диски ), который проходит через как можно меньше препятствий.

Определения

Проблема устойчивости барьеров была введена Кумар, Лай и Арора (2005) (используя другую терминологию) для моделирования способности беспроводные сенсорные сети для надежного обнаружения злоумышленников, когда некоторые датчики могут выйти из строя. В этой задаче область наблюдения от каждого датчика моделируется как единичный диск в Евклидова плоскость. Злоумышленник может достичь целевой области самолета без обнаружения, если существует путь в плоскости, соединяющий данную начальную область с целевой областью, не пересекая какой-либо из сенсорных дисков. В устойчивость барьера сети датчиков определяется как минимальное по всем путям от начальной области до целевой области количества сенсорных дисков, пересекаемых этим путем. Проблема устойчивости барьеров - это проблема вычисления этого числа путем поиска оптимального пути через барьеры.[1]

Упрощение задачи, которое включает в себя большинство ее основных функций, делает целевой регион источник плоскости, а начальная область - набор точек за пределами выпуклый корпус сенсорных дисков. В этой версии задачи цель состоит в том, чтобы связать исходную точку с точками, произвольно удаленными от исходной точки, путем прохождения через как можно меньшее количество сенсорных дисков.

Другой вариант задачи - подсчет количества раз, когда путь пересекает границу сенсорного диска. Если путь пересекает один и тот же диск несколько раз, каждое пересечение считается общим. В толщина барьера сенсорной сети - это минимальное количество пересечений пути от начальной области до целевой.[1]

Вычислительная сложность

Толщина барьера может быть вычислена в полиномиальное время путем построения расположение барьеров (подразделение плоскости, образованной перекрытием всех границ барьеров) и вычисление кратчайший путь в двойственный граф этого подразделения.[1]

Сложность барьерной устойчивости для барьеров из единичных дисков является открытой проблемой. Это может быть решено управляемый алгоритм с фиксированными параметрами время которого является кубическим по отношению к общему количеству барьеров и экспонентой в квадрате устойчивости, но неизвестно, имеет ли оно полностью полиномиальное временное решение.[2]Соответствующая задача для преград других форм, в том числе единичной длины. сегменты линии или по оси прямоугольники из соотношение сторон близко к 1, как известно NP-жесткий.[3]

Вариант проблемы устойчивости барьеров, изученный Кумар, Лай и Арора (2005), ограничивает как датчики, так и путь эвакуации прямоугольник в плоскости. В этом варианте цель состоит в том, чтобы найти путь от верхней стороны прямоугольника к нижней стороне, который проходит через как можно меньшее количество сенсорных дисков. Применяя Теорема Менгера к граф единичного диска определенное барьерами, это минимальное количество дисков может быть показано равным максимальному количеству подмножеств, на которые могут быть разделены все диски, так что каждое подмножество содержит цепочку дисков, проходящих полностью слева направо прямоугольника. Так как Кумар, Лай и Арора (2005) показал, что эта характеристика позволяет вычислить оптимальную устойчивость за полиномиальное время путем преобразования проблемы в экземпляр проблема максимального потока.

Для единичных дисков с ограниченным слой (максимальное количество дисков, которые имеют общее пересечение) существует схема полиномиальной аппроксимации для устойчивости, которую можно распространить на формы барьеров того же размера, что и друг друга, с ограниченными пропорциями.[2] Для единичных дисков без использования ограниченного слоя проблема вычисления упругости может быть аппроксимирована с точностью до постоянного множителя, используя тот факт, что для этой формы барьера оптимальный путь может пересекать каждый барьер только постоянное количество раз, поэтому толщина барьера и устойчивость барьеров находятся в пределах постоянного коэффициента друг от друга.[1] Подобные методы можно распространить на неоднородные датчики примерно одинакового размера.[4]

Заметки

  1. ^ а б c d Берег и Киркпатрик (2009).
  2. ^ а б Korman et al. (2014).
  3. ^ Alt et al. (2011); Ценг и Киркпатрик (2012); Korman et al. (2014).
  4. ^ Чан и Киркпатрик (2013).

Рекомендации

  • Альт, Гельмут; Кабельо, Серджио; Яннопулос, Панос; Кнауэр, Кристиан (2011), Минимальное соединение и разделение ячеек в компоновке сегментов линии, arXiv:1104.4618, Bibcode:2011arXiv1104.4618A.
  • Берег, Сергей; Киркпатрик, Дэвид (2009), «Приблизительная устойчивость барьеров в беспроводных сенсорных сетях», Алгоритмические аспекты беспроводных сенсорных сетей: 5-й международный семинар, ALGOSENSORS 2009, Родос, Греция, 10-11 июля 2009 г., пересмотренные избранные статьи, Конспект лекций по информатике, 5804, Springer, стр. 29–40, Bibcode:2009LNCS.5304 ... 29B, Дои:10.1007/978-3-642-05434-1_5.
  • Чан, Дэвид Ю Ченг; Киркпатрик, Дэвид (2013), «Приближение устойчивости барьера для устройств неодинаковых дисковых датчиков», Алгоритмы для сенсорных систем: 8-й Международный симпозиум по алгоритмам для сенсорных систем, беспроводных специальных сетей и автономных мобильных объектов, ALGOSENSORS 2012, Любляна, Словения, 13-14 сентября 2012 г., Отредактированные избранные статьи, Конспект лекций по информатике, 7718, Springer, стр. 42–53, Дои:10.1007/978-3-642-36092-3_6.
  • Корман, Матиас; Лёффлер, Маартен; Сильвейра, Родриго I .; Страш, Даррен (2014), «О сложности барьерной устойчивости жировых отложений», Алгоритмы для сенсорных систем: 9-й международный симпозиум по алгоритмам и экспериментам для сенсорных систем, беспроводных сетей и распределенной робототехники, ALGOSENSORS 2013, Sophia Antipolis, Франция, 5-6 сентября 2013 г., исправленные избранные статьи, Конспект лекций по информатике, 8243, Springer, стр. 201–216, arXiv:1302.4707, Дои:10.1007/978-3-642-45346-5_15.
  • Кумар, Сантош; Lai, Ten H .; Арора, Аниш (2005), «Барьерное покрытие с помощью беспроводных датчиков», Материалы 11-й ежегодной международной конференции по мобильным вычислениям и сетям (MobiCom '05, Кельн, Германия), Нью-Йорк, Нью-Йорк, США: ACM, стр. 284–298, Дои:10.1145/1080829.1080859, ISBN  1-59593-020-5.
  • Ценг, Куан-Чие Роберт; Киркпатрик, Дэвид (2012), «О барьерной устойчивости сенсорных сетей», Алгоритмы для сенсорных систем: 7-й Международный симпозиум по алгоритмам для сенсорных систем, беспроводных специальных сетей и автономных мобильных объектов, ALGOSENSORS 2011, Саарбрюккен, Германия, 8-9 сентября 2011 г., пересмотренные избранные статьи, Конспект лекций по информатике, 7111, Springer, стр. 130–144, Дои:10.1007/978-3-642-28209-6_11.