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