WSN
Z Wikipedii
WSN (ang. Wireless Sensor Network pl. Bezprzewodowa sieć sensorowa) - sieć złożona z wielu małych urządzeń rozlokowanych na pewnym obszarze w celu realizacji pewnego - wspólnego dla wszystkich zadania. Podstawowym elementem sieci jest sensor monitorujący zmienność pewnych zjawisk, takich jak temperatura, wilgotność, obecność (nieobecność) obiektu, dźwięk, ciśnienie, ruch, stopień zanieczyszczenia powietrza itp. w różnych lokalizacjach. Początkowo technologie oparte na bezprzewodowych sieciach sensorowych rozwijane były tylko na potrzeby militarne, jednak z czasem sieci te zyskują co raz szersze zastosowanie w dziedzinach życia codziennego (monitorowanie środowiska, zarządzanie ruchem, automatyzacja w domach).
Typowy węzeł bezprzewodowej sieci sensorowej 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.
Węzły sieci sensorowych są odpowiednio zarządzane, tak by poprzez przechodzenie do trybu zmniejszonego poboru mocy oraz optymalizację komunikacji bezprzewodowej w celu oszczędzania źródeł zasilania, znacznie wydłużyć czas życia sensorów w terenie. Opracowywane i implementowane są wydajne algorytmy oraz metody rutingu skupiające się na niezawodności polegającej na ww. czynnikach oraz odtwarzaniu stanu po awarii sieci.
Spis treści |
[edytuj] Metody niezawodnościowe w sieciach WSN
Techniki rutingu stosowane w sieciach ad-hoc nie mogą zostać zaimplementowane w bezprzewodowych sieciach sensorowych ponieważ:
-
- tradycyjne protokoły IP bazujące na unikalnych adresach IP każdego węzła nie sprawdzają się dla ogromnej liczby węzłów w sieciach sensorowych,
- w przeciwieństwie do typowych połączeń sieciowych, prawie wszystkie aplikacje sieci WSN (Wireless Sensor Network) wymagają przepływu danych z wielu źródeł do jednego celu,
- węzły sensorowe narzucają wiele ograniczeń dot. mocy transmisji, rezerwacji energii, ilości pamięci niezbędnej do wykonania wszystkich procesów,
- wiele sieci sensorowych 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 o toczenia przekroczy 60° C, to odpowiadać powinny jedynie sensory rejestrujące temperaturę większą niż zadana.
- tradycyjne protokoły IP bazujące na unikalnych adresach IP każdego węzła nie sprawdzają się dla ogromnej liczby węzłów w sieciach sensorowych,
[edytuj] Płaskie Protokoły Rutingu (Flat Routing Protocols)
Ruting płaski zakłada, że wszystkie węzły w sieci wykonują identyczne, przydzielone im wcześniej zadania.
W płaskiej topologii wszystkie węzły współpracują ze sobą w celu realizacji określonego celu, np. monitorowania danego zjawiska fizycznego. Ponieważ liczba węzłów w sieciach sensorowych 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 rutingu danowo—zcentralizowanego (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, np. wzrost temperatury powyżej określonego poziomu (wyzwalanie zdarzeniem).
[edytuj] 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 opartych na 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 m.in. 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 długości życia sieci. Wadą jest brak potwierdzenia dostarczenia wiadomości.
[edytuj] 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 ograniczając 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 tzw. 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ą lub co najwyżej kilka ścieżek.
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.
[edytuj] Rumour Routing
Podstawą działania tego protokołu jest używanie tzw. agentów (agents)
tworzących ścieżki do każdego ze zdarzeń rejestrowanych przez sensory. Agenci są wiadomościami o długim czasie życia krążącymi po całej sieci. Powstałe zapytania rutowane 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. Agenci tworzeni 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ść-agent 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ż znana mu, aktualizuje jego tablicę rutingu wpisując ścieżkę krótszą.
[edytuj] Minimum Cost Forwarding Algorithm (MCFA)
Algorytm zawsze rutuje 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, itp. 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ł—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, to 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ę.
[edytuj] Hierarchiczne protokoły rutingu (Hierarchical Routing Protocols)
Ważnym czynnikiem branym pod uwagę podczas projektowania sieci sensorowej
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 dystanse (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 rutingu opartych na gromadach sensorów (cluster-based) – tzw. 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 ruting rejestrowanych danych. W sieciach sensorowych wykorzystuje się ruting oparty 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 itd.
[edytuj] LEACH (Low Energy Adaptive Clustering Hierarchy)
LEACH (Low Energy Adaptive Clustering Hierarchy) 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ół opiera się na dwóch fazach. 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:
p—przewidywana liczba węzłów mających stać się węzłami głównymi,
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 kreś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 bliskiej 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.
[edytuj] Zobacz też
[edytuj] Linki zewnętrzne
- Sensor Network Technologies
- Studencki Projekt WSN na Uniwersytecie Berkeley
- Sieci WSN w medycynie
- Mobicom2002 - WSN Tutorial
- WSN Market
- Wireless Sensor Networks LAB
[edytuj] Bibliografia
- Nitaigour P. Mahalik (editor)—Sensor Networks and Configuration (wyd. 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, 03.2007, art.5)
