Typowa topologia bezprzewodowej sieci czujnikowej

Bezprzewodowa sieć czujnikowa, WSN (od ang. wireless sensor network) – sieć złożona z wielu urządzeń rozlokowanych na pewnym obszarze w celu realizacji wspólnego zadania. Podstawowym elementem sieci jest węzeł wyposażony w czujnik monitorujący zmienność pewnych zjawisk (temperatury, wilgotności, obecności lub nieobecności obiektu, dźwięku, ciśnienia, ruchu, stopnia zanieczyszczenia powietrza) w różnych miejscach. Początkowo technologie oparte na bezprzewodowych sieciach czujnikowych rozwijane były tylko na potrzeby militarne, jednak zyskują one coraz szersze zastosowanie w dziedzinach życia codziennego (monitorowanie środowiska, zarządzanie ruchem, automatyzacja w domach).

Typowy węzeł bezprzewodowej sieci czujnikowej zbudowany jest z nadajnika-odbiornika radiowego, modułu pamięci, mikroprocesora oraz baterii lub innego źródła energii. Koszt pojedynczego węzła to kwota od kilkunastu centów do kilkuset dolarów, w zależności od jego parametrów.

Najważniejsze parametry, którymi różnią się między sobą sieci czujnikowe oraz które odróżniają je od innych sieci (na przykład komputerowych), to:

  • małe fizyczne rozmiary węzłów
  • optymalizacja komunikacji bezprzewodowej, między innymi poprzez implementację wydajnych algorytmów oraz metod trasowania, w celu oszczędzania energii
  • ograniczenie mocy obliczeniowej i pamięci w celu dalszej minimalizacji zużycia energii
  • zdolność do samoorganizacji
  • odporność na uszkodzenia węzłów
  • silne zabezpieczenie komunikacji (najczęściej bezprzewodowej) przed błędami transmisji
  • istotny nacisk na szybkość przesyłu informacji (szczególnie w sieciach czujnikowych mających ostrzegać przed zagrożeniami)
  • minimalizacja lub całkowity brak udziału człowieka w utrzymaniu sprawności sieci
  • jednorazowość: po zużyciu baterii lub uszkodzeniu węzły sieci czujnikowych często nie są naprawiane, lecz zastępowane nowymi.

Historia

Jako najwcześniejsze przykłady nieświadomie kreowanych sieci czujnikowych można przyjąć już sieci radarów naziemnych do kontroli ruchu powietrznego, zbudowanych przed wybuchem drugiej wojny światowej u wybrzeży Wielkiej Brytanii (Chain Home), lub pierwsze sieci energetyczne zdolne do wykrywania spadku napięcia[1]. Rozwój sieci czujnikowych był na początku napędzany głównie przez przemysł militarny (SOSUS, AWACS). Sieci takie służyły jedynie detekcji obiektów i istotną rolę pełnili w nich ludzie.

Prace nad sieciami czujnikowymi w dzisiejszym rozumieniu tego pojęcia rozpoczęły się około roku 1980 w ramach programu Distributed Sensor Network (DSN), realizowanego w amerykańskiej Agencji Zaawansowanych Obronnych Projektów Badawczych (DARPA)[1]. Badano wówczas możliwość stworzenia sieci czujnikowej w oparciu o wczesną wersję internetu, który miał w tamtych czasach około 200 hostów, a węzły sieci musiały być przewożone ciężarówkami. Systemy kontrolno-pomiarowe produkowane przed rokiem 1980 posiadały wyraźnie wydzielony komputer centralny, który wykonywał wszystkie obliczenia i do którego spływały dane z nieinteligentnych czujników[2]. W latach 80., wraz z postępami w elektronice i informatyce, zaczęto stosować w nich proste rozwiązania sieciowe, m.in. w postaci tzw. direct digital controllers (DDC), umożliwiając dodatkowo ograniczone przetwarzanie informacji w modułach wejścia/wyjścia. Wśród rozwiązań militarnych z lat 80. i 90. pojawiały się takie, które w coraz większym stopniu samodzielnie przetwarzały dane i podejmowały na ich podstawie decyzje (np. Cooperative Engagement Capability – CEC lub Remote Battlefield Sensor System – REMBASS) bez udziału człowieka. Zmieniały się również sposoby połączenia węzłów z jednostką centralną: od prostych połączeń dial-up, poprzez protokół ethernet, aż po wyspecjalizowane protokoły komunikacji (np. w sieciach LonWorks, BACnet) w połowie lat 90[2].

Przełomowe okazały się lata dziewięćdziesiąte, kiedy powstały między innymi protokoły LonTalk i BACnet, a na Uniwersytecie w Wallongong w Australii rozpoczęto prace nad wireless ad hoc control networks, które posiadały typowe cechy współczesnych sieci czujnikowych[2].

Od 1995 roku rozwijana jest norma IEEE 1451, która określa konstrukcję inteligentnych przetworników (ang. smart transducer) oraz sposób ich połączenia z mikrokontrolerami. Zgodność z normą IEEE 1451 wykazuje wiele spotykanych obecnie rozwiązań w dziedzinie bezprzewodowych sieci czujnikowych (ZigBee, Wi-Fi, Bluetooth)[3].

Na przełomie stuleci ważnym krokiem w rozwoju sieci czujnikowych był program agencji DARPA o nazwie SensIT. Położono w nim nacisk na podniesienie poziomu zaawansowania sieci, zdolność do dynamicznej i automatycznej reorganizacji w wypadku zmiany ilości i położenia węzłów sieci oraz zwiększenie sprawności przetwarzania danych w jej ramach[1].

Nowe technologie (na przykład mikroukłady elektromechaniczne) pozwalają na miniaturyzację, zwiększenie wydajności, a zarazem obniżenie kosztów produkcji, czujników i – co za tym idzie – rozpowszechnienie sieci czujnikowych. Wiele firm (między innymi Ember, Echelon, Sensoria) oferuje gotowe urządzenia, wyposażone w czujniki, mikrokontrolery oraz urządzenia nadawczo-odbiorcze[4].

W związku z rozpowszechnieniem urządzeń bezprzewodowych (telefonów komórkowych, odbiorników GPS) oraz popularyzacją dostępu do internetu, bezprzewodowe sieci czujnikowe mogą obecnie korzystać ze zróżnicowanych rozwiązań komunikacyjnych, dopasowanych do ich przeznaczenia. Od początku XXI wieku można zaobserwować doskonalenie algorytmów, protokołów, jak również samych urządzeń elektronicznych używanych w sieciach czujnikowych.

Zastosowania

Bezprzewodowe sieci czujnikowe znajdują zastosowanie w[1]:

  • wojskowości
  • medycynie
  • kontroli ruchu powietrznego
  • nadzorze ruchu drogowego
  • ochronie zdrowia i mienia
  • automatyzacji procesów przemysłowych i produkcyjnych
  • ochronie i badaniach nad środowiskiem naturalnym
  • budownictwie
  • inteligentnych budynkach.

Samoorganizacja węzłów sieci czujnikowych

Algorytmy stosowane do samoorganizacji sieci czujnikowych muszą być w stanie działać lokalnie, gdyż najczęściej rozmiar sieci przekracza zasięg pojedynczego węzła a ich rozmieszczenie jest przypadkowe i nieregularne. Każdy węzeł sieci czujnikowej stanowi więc autonomiczne urządzenie[5].

Głównym zadaniem algorytmów samoorganizacyjnych jest stworzenie struktury sieci po rozmieszczeniu węzłów oraz utrzymywanie jej przez jak najdłuższy czas. Oznacza to, że algorytmy samoorganizacji zdolne są także do naprawy struktury sieci w przypadku utraty pewnych węzłów i przyłączania nowych węzłów. Celem działania algorytmów samoorganizacyjnych, po pierwotnym zorganizowaniu sieci, jest zapobieżenie podziałowi sieci i minimalizacja utraty danych podczas transmisji. Struktura sieci tworzona jest tak, aby maksymalnie wydłużyć czas działania baterii węzłów.

Zazwyczaj organizacja sieci czujnikowej rozpoczyna się od detekcji sąsiadów oraz pomiaru odległości od nich[6]. Lokalizacja geometryczna węzła uzyskiwana jest w jeden z trzech sposobów:

  • na podstawie pomiaru RSSI (Radio Signal Strength Indication) – przy sieciach bezprzewodowych,
  • na podstawie pomiaru czasu przesyłu pakietów,
  • poprzez komunikację z węzłami referencyjnymi, których położenie jest znane.

Dzięki działaniu specjalnych algorytmów lokalizacyjnych, wykrywana jest topologia sieci, a dopiero później ma miejsce jej właściwa organizacja.

Niektóre algorytmy są w stanie zdecydować o nieużywaniu tych wykrytych węzłów, które nie są niezbędne do realizacji zadania, aby zaoszczędzić ich baterie (ang. Dominating Set based algorithms)[6]. Inne wykorzystują wszystkie znalezione węzły, ale ograniczają sposoby ich połączenia (ang. Link-pruning algorithms)[7]. Większa ilość krótkich przesłań jest bardziej wydajna z punktu widzenia oszczędności energii oraz zmniejsza ryzyko interferencji w przypadku komunikacji bezprzewodowej[5].

Struktura sieci może przyjmować różne postaci, w zależności od tego czy wszystkie węzły są identyczne, czy też istnieją węzły wyróżnione, spełniające specyficzne funkcje. Często struktura sieci budowana jest wokół pojedynczego urządzenia, do którego spływają wszystkie dane (ang. data sink). Hierarchicznej architekturze sprzyja zwiększona możliwość przetwarzania (np. uśredniania, kompresowania) danych w wyróżnionych węzłach, co pozwala zmniejszyć sumaryczną ilość przesyłanych danych. Wydzielone fragmenty sieci czujnikowych komunikujące się z jednym węzłem liderem nazywa się klastrami. Czasami, oprócz korzyści wynikających z hierarchicznej architektury sieci, tworzenie klastrów może mieć na celu utworzenie grupy węzłów znajdujących się na zadanym obszarze do wykonania konkretnego zadania[8].

TopDisc[9]

TopDisc to algorytm służący do wykrywania topologii sieci. Jeden z węzłów w sieci rozsyła żądanie topology discovery request, które przekazywane jest przez wszystkie węzły. Czas, po którym dany węzeł wysyła odpowiedź na to żądanie, zależy od tego, po ilu „przeskokach” (ang. hops) je otrzymał. Im bliżej znajduje się on od węzła rozsyłającego, tym dłużej będzie zwlekał z odpowiedzią, aby najpierw zebrać dane z bardziej oddalonych fragmentów sieci. Liczba przeskoków wskazuje na odległość danego węzła od węzła rozsyłającego. Na podstawie tej informacji możliwe jest utworzenie przybliżonej topologii sieci.

Connected dominant set (CDS)[7]

Konstrukcja sieci w przypadku tego algorytmu następuje w dwóch fazach. Najpierw ma miejsce proces oznaczania: te węzły, które mają dwóch niepołączonych sąsiadów oznaczają się jako możliwe węzły dominujące. Aby dodatkowo zmniejszyć liczbę takich węzłów, w drugiej fazie organizacji sieci rozsyłana jest wiadomość identyfikująca węzeł jako oznaczony lub nieoznaczony. Na jej podstawie, jeśli wokół danego oznaczonego węzła znajduje się k innych węzłów oznaczonych jako dominujące, staje się on węzłem nieoznaczonym. Parametr k może przyjmować różne wartości, zależnie od potrzeb danej sieci.

W wyniku działania tego algorytmu połączone w sieci są tylko węzły dominujące, które są odpowiedzialne za odbiór danych od nieoznaczonych węzłów i przesłanie ich dalej. Zaletą tego algorytmu jest jego nieskomplikowanie.

Low-energy self-organization scheme (LEGOS)[7]

Algorytm ten oprócz pierwotnej organizacji sieci zawiera funkcje podtrzymujące jej trwanie. W celu zaoszczędzenia baterii węzłów reorganizacja sieci może następować lokalnie, na przykład w miejscu awarii lub dołączenia nowego węzła. W LEGOS wyróżnione są trzy rodzaje węzłów:

  • lidery (leader), z których tworzony jest szkielet sieci,
  • bramy (gateway), odpowiedzialne za połączenia między liderami,
  • człony (member), połączone wyłącznie z liderami.

Organizacja sieci w algorytmie LEGOS opiera się na spontanicznym przyłączaniu nowych węzłów do istniejącego szkieletu. Każdy węzeł najpierw oczekuje na wiadomość LDBR (leader broadcast msg), w której uzyskuje informację o istniejących już w okolicy liderach. Domyślnie węzeł rozpoczyna procedurę przyłączenia się jako członek sieci do najbliższego lidera, od którego otrzymał wiadomość. Jednak jeśli żadna wiadomość LDBR nie nadejdzie, węzeł rozsyła komunikat Member_Solicitation_Msg, aby odszukać istniejących w otoczeniu członków sieci lub bramy. Następuje rejestracja nowego węzła w sieci jako lidera, z pomocą istniejącego, najbliższego (a więc oddalonego o dwa przeskoki), lidera. Jeśli w komunikacji pomiędzy liderami pośredniczyła brama, rejestracja nowego lidera kończy procedurę; jeśli pośredniczył zwykły członek, staje się on bramą.

Istnieje również odmiana algorytmu nazywana p-LEGOS, która zezwala na pośredniczenie p bram pomiędzy każdymi dwoma liderami. Pozwala to na zmniejszenie liczby liderów w silnie rozproszonych sieciach.

Lokalne minimalne drzewo rozpinające (minimum spanning tree – MST)

Na podstawie informacji o swoim sąsiedztwie każdy węzeł jest w stanie stworzyć lokalne minimalne drzewo rozpinające. Połączenie między dwoma węzłami (u,v) zostaje ustanowione wtedy i tylko wtedy, gdy węzeł u należy do MST węzła v oraz węzeł v należy do MST węzła u[7]. Informacja o sąsiedztwie uzyskiwana jest poprzez rozsyłanie przez wszystkie węzły wiadomości identyfikującej.

Ta metoda organizacji sieci charakteryzuje się liniową złożonością obliczeniową[7].

Samoorganizacja sieci WACNet (wireless ad hoc control network)

W stworzonej w 2005 roku na Uniwersytecie w Wallongong sieci czujników WACNet zastosowano niezależny algorytm samoorganizacji[10], składający się z kilku faz:

  • Stworzenie listy sąsiadujących węzłów. Węzły nasłuchują wiadomości od sąsiadów będących w ich zasięgu.
  • Wykrycie funkcji (ang. service discovery). W sieci WACNet funkcjonuje specjalny protokół SDP (ang. service discovery protocol), umożliwiający przesyłanie wiadomości do konkretnych odbiorców zamiast rozsyłania jej po całej sieci czujników[10]. Specyfikacji uległy też same wiadomości, które pozwalają na oferowanie usług danego węzła w sieci. W związku z tym w jednej sieci mogą znajdować się węzły o różnej funkcjonalności. Do identyfikacji węzłów zastosowano normę IEEE 1451. Przeszukiwanie węzłów w sieci może przebiegać pod kątem znalezienia węzła do spełnienia konkretnego zadania (na przykład pomiaru konkretnej wielkości).
  • Formowanie klastrów. Klastry składają się z co najwyżej 8 węzłów[11], nazywanych STIM (od ang. smart transducer interface module). Spośród nich jeden pełni funkcję nadrzędną (ang. master) a pozostałe człony klastra (ang. slaves) komunikują się jedynie z nim. W sieci wyróżnione są także węzły NCAP (od ang. network-capable application), służące jako ujście informacji z sieci, zdolne do komunikacji poprzez protokół TCP/IP. Na to, czy dany węzeł wejdzie w skład klastra, wpływają jego odległość od pozostałych węzłów oraz zdolność do wykonania zadania przydzielonego danemu klastrowi. Informacja o tych dwóch parametrach jest rozsyłana w sieci. W pięciu krokach, na podstawie rozesłanych informacji, algorytm formuje klaster sieci[11]:
    1. wybór węzła nadrzędnego (master) spośród wszystkich węzłów STIM
    2. przydział pozostałych węzłów do danego węzła nadrzędnego
    3. połączenie węzła nadrzędnego z resztą sieci (docelowo z węzłem NCAP)
    4. konsolidacja klastra
    5. ewolucja sieci – przyłączanie nowych węzłów, reakcja na zużycie lub uszkodzenie niektórych węzłów, zmiana zadania przydzielonego sieci lub klastrowi, zmiana węzła nadrzędnego.

Graf sąsiedztwa względnego (relative neighborhood graph) oraz graf Gabriela

Algorytmy te bazują na znajomości geograficznego położenia węzłów (co jest typową cechą tzw. link-pruning algorithms[7]). Ich celem jest stworzenie takich połączeń między węzłami, aby uniknąć długich transmisji, które powodują większe zużycie energii[5]. W tym celu wyznaczany jest obszar pomiędzy węzłami, który nie może zawierać żadnego innego węzła, aby połączenie było dopuszczalne. Jeśli obszar ten nie jest pusty, węzły, które się w nim znajdują, stają się węzłami pośrednimi w komunikacji.

Metody niezawodnościowe w sieciach WSN

Technik trasowania stosowanych w sieciach ad hoc nie można zaimplementować w bezprzewodowych sieciach czujnikowych, ponieważ:

  1. tradycyjne protokoły internetowe bazujące na unikalnych adresach IP każdego węzła nie sprawdzają się dla ogromnej liczby węzłów w sieciach czujnikowych
  2. w przeciwieństwie do typowych połączeń sieciowych, prawie wszystkie aplikacje bezprzewodowych sieci czujnikowych wymagają przepływu danych z wielu źródeł do jednego celu
  3. węzły czujnikowe narzucają wiele ograniczeń mocy transmisji, rezerwacji energii, ilości pamięci niezbędnej do wykonania wszystkich procesów
  4. wiele sieci czujnikowych wymaga adresowania opartego na danym atrybucie – wszelkie zapytania winny być tworzone w oparciu o parę atrybut–wartość. Przykładowo, jeśli sieć ma działać, gdy temperatura otoczenia przekroczy 60 °C, odpowiadać powinny jedynie sensory rejestrujące temperaturę większą niż zadana.

Płaskie protokoły trasowania (flat routing protocols)

Ruting płaski zakłada, że wszystkie węzły w sieci wykonują identyczne, przydzielone im wcześniej zadania.

Trasowanie płaskie

W płaskiej topologii wszystkie węzły współpracują z sobą w celu realizacji określonego celu, na przykład monitorowania danego zjawiska fizycznego. Ponieważ liczba węzłów w sieciach czujnikowych zazwyczaj jest ogromna, trudne jest nadanie każdemu z nich unikalnego identyfikatora, co z kolei powoduje trudność w wysłaniu zapytań do konkretnych sensorów. Zazwyczaj dane przesyłane są ze wszystkich węzłów, wskutek czego stacja bazowa otrzymuje wiele informacji nadmiarowych, co jest rozwiązaniem niewydajnym energetycznie. Doprowadziło to do powstania trasowania scentralizowanego danowo (ang. data-centric routing), w którym pewne atrybuty specyfikują przesyłane dane ulegające procesowi agregacji podczas transmisji do stacji bazowej. Stacja bazowa może wysyłać zapytania do części węzłów sieci i tylko z nich otrzymywać odpowiedź (wyzwalanie zapytaniem). Innym rozwiązaniem jest wysyłanie danych przez sensory z określoną częstotliwością (wyzwalanie czasem) lub wtedy, gdy ma miejsce jakieś zdarzenie (wyzwalanie zdarzeniem), na przykład wzrost temperatury powyżej określonego poziomu.

Sensor protocol for information via negotiation (SPIN)

SPIN to protokół skupiający się na oszczędzaniu energii oraz przedłużaniu żywotności sieci poprzez zastosowanie algorytmów negocjacji. Mechanizm ten oparty jest na wysyłaniu ogłoszeń przez dany sensor do wszystkich sąsiadów (węzłów oddalonych o 1 przeskok). Jeśli któryś z sąsiadów zainteresowany jest pozyskaniem danych, wysyła wiadomość zwrotną, po czym sensor źródłowy wysyła dane. Dodatkowo protokół ten ma dostęp do informacji na temat aktualnego poziomu energii w sensorze. SPIN wykorzystuje trzy rodzaje wiadomości: ADV (ogłaszanie danych), REQ (żądanie danych), DATA (właściwe dane). Podczas wysyłania każdej z tych wiadomości realizowany jest jeden z trzech etapów komunikacji. SPIN to cała rodzina protokołów, w której wyróżnić możemy SPIN1, SPIN2 (wprowadza dodatkowe zabezpieczenie: jeśli poziom energii spadnie poniżej określonego poziomu, sensor może uczestniczyć w transmisji tylko wtedy, gdy jest w stanie przejść przez wszystkie 3 etapy transmisji), SPIN-BC (przeznaczony do kanałów rozgłoszeniowych), SPIN-RC, SPIN-PP (kanały punkt–punkt). Wszystkie łączy trzyetapowy proces transmisji danych.

Zaletami SPIN są: rejestracja zmian topologii, unikanie dublowania tych samych wiadomości do tego samego węzła, zwiększenie trwałości sieci. Wadą jest brak potwierdzenia dostarczenia wiadomości.

Directed diffusion (ukierunkowane rozchodzenie się)

W protokole directed diffusion wszystkie dane generowane przez sensory określone są poprzez pary atrybut–wartość, co powoduje brak konieczności wykonywania dodatkowych operacji (modyfikacji danych) w warstwie sieci i ogranicza zużycie energii. Użytkownik (stacja bazowa) wysyła zapytania (interests), które docierają do wszystkich węzłów w sieci. Podczas rozsyłania takiego zapytania każdy z węzłów, który otrzyma żądanie odwołujące się do zgromadzonych przez niego danych, tworzy tak zwany gradient, wskazujący kierunek ścieżki prowadzącej do źródła zapytania. Gradienty wysyłane są do źródła, informując je tym samym o możliwych ścieżkach transmisji pasujących do danych zapytań danych. Źródło wybiera jedną ścieżkę (lub co najwyżej kilka).

Uproszczony schemat działania protokołu directed diffusion

W opisanej sytuacji protokół opiera się na zapytaniach stacji bazowej. Istnieją jednak również implementacje protokołu ze ścieżkami opartymi na wywoływaniu zdarzeniami. Zaletami protokołu są: oszczędność energii, przechowywanie danych, agregacja danych (możliwe łączenie danych z wielu źródeł), małe opóźnienia w przesyłaniu danych, brak konieczności indywidualnego adresowania wszystkich węzłów.

Rumour routing

Rumour routing

Podstawą działania tego protokołu jest używanie tak zwanych agentów (agents), tworzących ścieżki do każdego ze zdarzeń rejestrowanych przez sensory. Agenty są wiadomościami o długim czasie życia krążącymi po całej sieci. Powstałe zapytania trasowane są poprzez utworzone wcześniej ścieżki. W celu dołączenia do konkretnej ścieżki zapytanie wysyłane jest losową drogą.

Każdy węzeł sieci ma tablicę sąsiadów oraz zdarzeń, a także informacje o kierunku do innych znanych mu zdarzeń w sieci. Agenty tworzone są w jednym z węzłów rejestrujących to samo zdarzenie. Następnie agent wędruje poprzez losowo wybrane węzły przez określoną wcześniej maksymalną liczbę skoków. Podczas takiej wędrówki wiadomość agencka tworzy własną tablicę zdarzeń odwiedzanych sensorów. Jeśli agent trafia na ścieżkę prowadzącą do innego zdarzenia następuje agregacja tras. Dodatkowo, jeśli agent trafi na węzeł będący częścią ścieżki dłuższej niż mu znana, aktualizuje jego tablicę trasowania, wpisując ścieżkę krótszą.

Minimum cost forwarding algorithm (MCFA)

Algorytm zawsze trasuje dane ścieżką o najmniejszym koszcie, prowadzącą do stacji bazowej. Dzięki jego prostocie w sieci funkcjonować mogą sensory ze znacznie ograniczoną mocą oraz pamięcią. Protokół zakłada, że wszystkie dane w sieci kierowane są do stacji bazowej, wobec czego nie jest potrzebny żaden nadrzędny schemat adresacji – jednak każdy z węzłów musi znać koszt dotarcia informacji od niego do stacji. Koszt w szczególności oznaczać może poziom energii, liczbę przeskoków, opóźnienie, liczbę retransmisji. Każdy węzeł po otrzymaniu danych natychmiast przekazuje je dalej, pod warunkiem że znajduje się na ścieżce o najmniejszym koszcie.

Na początku stacja bazowa inicjalizuje koszt do samej siebie równy 0, natomiast każdy inny węzeł koszt równy nieskończoności. Stacja bazowa rozgłasza swój koszt do sąsiadów. Każdy z nich aktualizuje swój wpis i posyła go dalej. Każdy z węzłów aktualizuje swój wpis wtedy, gdy otrzymany koszt jest mniejszy niż dotąd posiadany. Jeśli ścieżką, z której sensor odbiera nowy koszt, jest LC, oczekuje on czas proporcjonalny do LC, zanim rozgłosi swój koszt. W ten sposób unika się niepotrzebnych rozgłoszeń, oszczędzając energię.

Hierarchiczne protokoły trasowania (hierarchical routing protocols)

Trasowanie hierarchiczne – topologie

Ważnym czynnikiem branym pod uwagę podczas projektowania sieci czujnikowej jest jej skalowalność. Sieć z pojedynczą bramą nie jest skalowalna, gdy liczba węzłów zwiększa się oraz rozprzestrzenia się na dużej powierzchni – zazwyczaj sensory nie mogą komunikować się na bardzo duże odległości (taka sieć byłaby niewydajna energetycznie). Ponadto taka architektura sieci wiąże się z ryzykiem przeciążenia bramy, ponieważ musi ona przyjmować nierzadko powielające się dane ze wszystkich węzłów sieci. Wychodząc naprzeciw tym zagadnieniom, opracowano rodzinę protokołów trasowania opartych na gromadach sensorów (cluster-based), tak zwane protokoły hierarchiczne. Algorytmy oparte na hierarchii węzłów zwiększają efektywność sieci poprzez przetwarzanie oraz agregację danych w skupiskach sensorów. Protokoły te obejmują zazwyczaj dwie fazy – w pierwszej formowane są gromady, w drugiej natomiast ma miejsce trasowanie rejestrowanych danych. W sieciach czujnikowych stosuje się trasowanie oparte zarówno na gromadzeniu w jednej warstwie (single-layer clustering), jak i wielu warstwach (multi-layer clustering), w którym gromady warstwy niższej tworzą gromadę warstwy wyższej.

LEACH (low-energy adaptive clustering hierarchy)

LEACH jest protokołem działającym w oparciu o wyżej wspomniane gromady sensorów. Gromada to grupa sensorów, które łączą się z jednym i tym samym węzłem głównym (cluster head). Powstanie gromady rozpoczyna się od wyboru węzłów głównych obejmujących kilka procent sensorów całej sieci. Pośród innych wykonywanych funkcji węzły główne agregują dane pochodzące ze wszystkich sensorów należących do gromady, po czym wysyłają je do stacji bazowej. Skutkiem tego jest zmniejszenie ilości danych przesyłanych bezpośrednio do stacji bazowej. LEACH wykorzystuje mechanizm CDMA/TDMA w celu zmniejszenia liczby kolizji wewnątrz gromad oraz pomiędzy nimi. Protokół pracuje cyklicznie, a każdy cykl składa się z dwóch faz[12]. Faza pierwsza obejmuje formowanie się gromad oraz wybór węzłów głównych. Każdy węzeł generuje losową liczbę z zakresu 0 do 1. Jeśli liczba okazuje się mniejsza niż progowa wartość T(n), węzeł staje się węzłem głównym gromady. Wartość T(n) obliczana jest w następujący sposób:

gdzie:

p – przewidywana liczba węzłów mających stać się węzłami głównymi,
r – ilość minionych cykli,
G – zbiór węzłów biorących udział w procesie selekcji.

Nowo wybrane węzły główne wysyłają wiadomość-ogłoszenie do wszystkich węzłów sieci. Węzły przyłączają się do tych węzłów głównych, z których otrzymują największą siłę sygnału, przy czym węzeł główny wylicza harmonogram TDMA dla wszystkich członków powstającej w ten sposób gromady. Druga faza to gromadzenie i przesyłanie danych do węzłów głównych, które agregują je i przesyłają do stacji bazowej. Po określonym czasie sieć ponownie przechodzi przez fazę pierwszą.

Protokół wprowadza następujące założenia:

  • każdy węzeł transmituje z energią wystarczającą do przesłania danych do stacji bazowej
  • węzły zawsze mają dane do wysłania
  • węzły zlokalizowane w małej odległości posiadają wspólne dane.

Wadą algorytmu jest możliwość występowania przeciążeń sieci związanych z wyborem węzłów głównych w obrębie jednego obszaru sieci.

Przypisy

  1. 1 2 3 4 Chee-Yee Chong, Srikanta P. Kumar: Sensor Networks: Evolution Opportunities and Challenges. Proceedings of the IEEE, 2003.
  2. 1 2 3 Fazel Naghdy, Nathan Simiana: Adaptive Self-organisation of Wireless Ad-hoc Control Networks. Wollongong: IEEE, 2007.
  3. ↑ Eugene Y. Song, Kang Lee. Understanding IEEE 1451 – Networked Smart Transducer Interface Standard. „IEEE Instrumentation & Measurement Magazine”, 2008. IEEE.
  4. ↑ Oficjalna strona firmy Ember. [dostęp 2011-09-01].
  5. 1 2 3 Hugues Smeets, Kris Steenhaut, Ann Nowé: An efficient distributed self-organizing routing algorithm for Wireless Sensor Networks. Washington, DC, USA: IEEE Computer Society, 2008, seria: Proceedings of the 2008 International Conference on Complex, Intelligent and Software Intensive Systems. ISBN 978-0-7695-3109-0.
  6. 1 2 Jian Zhong, Peter Bertok: A Variable Threats Based Self-Organization Scheme for Wireless Sensor Networks. Washington, DC, USA: IEEE Computer Society, 2009, seria: Proceedings of the 2009 Third International Conference on Sensor Technologies and Applications. ISBN 978-0-7695-3669-9.
  7. 1 2 3 4 5 6 Ibrahim Amadou, Fabrice Valois: Performance evaluation of distributed self-organization protocols in wireless sensor networks. Nowy Jork, NY, USA: 2010, seria: Proceedings of the 7th ACM workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks. ISBN 978-1-4503-0276-0.
  8. ↑ Kamal Premaratne, Jinsong Zhang, Murat Dogruel. Location Information-aided Task-oriented Self-organization of Ad-hoc Sensor Systems. „IEEE Sensors Journal”, 2004.
  9. ↑ Budhaditya Deb, Sudeept Bhatnagar, Badri Nath: A Topology Discovery Algorithm for Sensor Networks with Applications to Network Management. 2002.
  10. 1 2 Fazel Naghdy, Shengrong Bu. Wireless Ad-hoc Networks. „3rd IEEE International Conference on Industrial Informatics (INDIN)”, 2005.
  11. 1 2 Fazel Naghdy, Nathan Simiana. Adaptive Self-organisation of Wireless Ad-hoc Control Networks. „IEEE International Conference on Signal Processing and Communications”, 2007.
  12. ↑ Editor Ijatca, Review study of detection and prevention methods of various possible attacks in Leach protocol [online] [dostęp 2021-02-04] (ang.).

Bibliografia

  • Nitaigour P. Mahalik (editor): Sensor Networks and Configuration. Springer-Verlag, 2007.
  • Aleksi Ahtiainen: Summary of Routing in Wireless Sensor. Helsinki University of Technology, Laboratory of Information Processing Science.
  • Chalermek Intanagonwiwat: Directed Diffusion for Wireless Sensor Networks.
  • Chi-Fu Huang, Hsiao-Lu Wu, Yu-Chee Tseng: Distributed protocols for Ensuring Both Coverage and Connectivity of a Wireless Sensor Network. ACM Transactions on Sensor Networks, 2007.
  • Cauligi S. Raghavendra, Krishna M. Sivalingam, Taieb Znati: Wireless sensor network. New York: Kluwer Acedemic Publishers, 2004. ISBN 978-1-4020-7884-2.

Linki zewnętrzne

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.