Odporność na bariery
Odporność na bariery to algorytmiczny problem optymalizacji w geometrii obliczeniowej motywowany projektowaniem bezprzewodowych sieci czujników , w którym poszukuje się ścieżki przez zbiór barier (często modelowanych jako dyski jednostkowe ), która przechodzi przez jak najmniej barier.
Definicje
Problem odporności bariery został wprowadzony przez Kumara, Lai i Arora (2005) (używając innej terminologii) w celu modelowania zdolności bezprzewodowych sieci czujników do niezawodnego wykrywania intruzów, gdy niektóre czujniki mogą ulec uszkodzeniu. W tym zadaniu obszar obserwowany przez każdy czujnik jest modelowany jako dysk jednostkowy na płaszczyźnie euklidesowej . Intruz może dotrzeć do docelowego obszaru płaszczyzny bez wykrycia, jeśli istnieje ścieżka w płaszczyźnie łącząca dany region początkowy z regionem docelowym bez przecinania któregokolwiek z dysków czujników. Odporność bariery sieci czujników jest zdefiniowana jako minimalna liczba dysków czujników przeciętych przez ścieżkę na wszystkich ścieżkach od regionu początkowego do regionu docelowego. Problem odporności na bariery to problem obliczenia tej liczby poprzez znalezienie optymalnej ścieżki przez bariery.
Uproszczenie problemu, które obejmuje większość jego istotnych cech, sprawia, że obszarem docelowym jest początek płaszczyzny , a obszarem początkowym zbiór punktów na zewnątrz wypukłej otoczki dysków czujnika. W tej wersji problemu celem jest połączenie początku z punktami dowolnie odległymi od początku ścieżką przez jak najmniejszą liczbę dysków czujników.
Inna odmiana problemu liczy, ile razy ścieżka przecina granicę dysku czujnika. Jeśli ścieżka przecina ten sam dysk wiele razy, każde skrzyżowanie liczy się do sumy. Grubość bariery sieci czujników to minimalna liczba przecięć ścieżki od regionu początkowego do regionu docelowego.
Złożoność obliczeniowa
Grubość bariery można obliczyć w czasie wielomianowym , konstruując układ barier (podział płaszczyzny utworzony przez nałożenie wszystkich granic barier) i obliczając najkrótszą ścieżkę na wykresie dualnym tego podziału.
Złożoność odporności na bariery dla barier dysków jednostkowych jest problemem otwartym. Można go rozwiązać za pomocą wykonalnego algorytmu o stałych parametrach, którego czas jest sześcienny w całkowitej liczbie barier i wykładniczy w kwadracie sprężystości, ale nie wiadomo, czy ma on w pełni wielomianowe rozwiązanie czasowe. Odpowiedni problem dla barier o innych kształtach, w tym segmentów linii o jednostkowej długości lub prostokątów ustawionych w osiach o współczynniku kształtu bliskim 1, jest znany jako NP-trudny .
Odmiana problemu sprężystości bariery, badana przez Kumara, Lai i Arora (2005) , ogranicza zarówno czujniki, jak i drogę ucieczki do prostokąta w płaszczyźnie. W tej odmianie celem jest znalezienie ścieżki od górnej krawędzi prostokąta do dolnej krawędzi, która przechodzi przez jak najmniejszą liczbę dysków czujników. Stosując twierdzenie Mengera do wykresu dysku jednostkowego określonego na podstawie barier, można pokazać, że ta minimalna liczba dysków jest równa maksymalnej liczbie podzbiorów, na które można podzielić wszystkie dyski, tak że każdy podzbiór zawiera łańcuch dysków przechodzących wszystkie drogę od lewej do prawej strony prostokąta. Jak Kumar, Lai i Arora (2005) , ta charakterystyka umożliwia obliczenie optymalnej sprężystości w czasie wielomianowym poprzez przekształcenie problemu w przypadek problemu maksymalnego przepływu .
W przypadku dysków jednostkowych z ograniczoną warstwą (maksymalna liczba dysków, które mają wspólne przecięcie) istnieje schemat aproksymacji sprężystości w czasie wielomianowym , który można uogólnić na kształty barier o tym samym rozmiarze co inne z ograniczonymi współczynnikami kształtu. W przypadku dysków jednostkowych bez założenia ograniczonej warstwy problem obliczenia sprężystości można przybliżyć do stałego współczynnika, wykorzystując fakt, że dla tego kształtu bariery optymalna ścieżka może przekroczyć każdą barierę tylko stałą liczbę razy, więc grubość bariery i sprężystość bariery mieszczą się w stałym współczynniku względem siebie. Podobne metody można uogólnić na niejednorodne czujniki o mniej więcej równej wielkości.
Notatki
- Alt, Helmut ; Cabello, Sergio; Giannopoulos, Panos; Knauer, Christian (2011), Minimalne połączenie i separacja komórek w układach segmentów linii , arXiv : 1104.4618 , Bibcode : 2011arXiv1104.4618A .
- Bereg, Siergiej; Kirkpatrick, David (2009), „Approximating bariera resilience in wireless sensor networks”, Algorithmic Aspects of Wireless Sensor Networks: 5th International Workshop, ALGOSENSORS 2009, Rodos, Grecja, 10-11 lipca 2009, Revised Selected Papers, Lecture Notes in Computer Nauka, tom. 5804, Springer, s. 29–40, Bibcode : 2009LNCS.5304...29B , doi : 10.1007/978-3-642-05434-1_5 .
- Chana, Davida Yu Chenga; Kirkpatrick, David (2013), „Approximating bariera sprężystość dla układów nieidentycznych czujników dyskowych”, Algorithms for Sensor Systems: 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Ljubljana, Słowenia , 13-14 września 2012, poprawione wybrane artykuły , Notatki z wykładów z informatyki, tom. 7718, Springer, s. 42–53, doi : 10.1007/978-3-642-36092-3_6 .
- Korman, Matias; Löffler, Maarten; Silveira, Rodrigo I.; Strash, Darren (2014), „O złożoności odporności barierowej dla regionów tłuszczu”, Algorytmy dla systemów czujników: 9. Międzynarodowe Sympozjum Algorytmów i Eksperymentów dla Systemów Czujników, Sieci Bezprzewodowych i Rozproszonej Robotyki, ALGOSENSORS 2013, Sophia Antipolis, Francja, wrzesień 5-6, 2013, poprawione wybrane artykuły , notatki z wykładów z informatyki, tom. 8243, Springer, s. 201–216, arXiv : 1302.4707 , doi : 10.1007/978-3-642-45346-5_15 .
- Kumar, Santosh; Lai, Ten H.; Arora, Anish (2005), „Pokrycie bariery czujnikami bezprzewodowymi”, Proceedings of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom '05, Kolonia, Niemcy) , Nowy Jork, NY, USA: ACM, s. 284– 298, doi : 10.1145/1080829.1080859 , ISBN 1-59593-020-5 .
- Tseng, Kuan-Chieh Robert; Kirkpatrick, David (2012), „O odporności barierowej sieci czujników”, Algorithms for Sensor Systems: 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2011, Saarbrücken, Niemcy, 8-9 września , 2011, poprawione wybrane artykuły , notatki z wykładów z informatyki, tom. 7111, Springer, s. 130–144, doi : 10.1007/978-3-642-28209-6_11 .