Sieci sensorowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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 węzeł wyposażony w czujnik 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ą coraz 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.

Typowa topologia sieci WSN

Najważniejsze parametry, którymi różnią się między sobą sieci sensorowe oraz które odróżniają je od innych sieci (np. komputerowych) to:

  • małe fizyczne rozmiary węzłów,
  • optymalizację komunikacji bezprzewodowej, m. in. poprzez implementację wydajnych algorytmów oraz metod trasowania w celu oszczędzania źródeł zasilania,
  • ograniczenie mocy obliczeniowej i pamięci w celu dalszej minimalizacji zużycia energii,
  • zdolność do samoorganizacji, odporność sieci 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 sensorowych 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 sensorowych często nie są naprawiane, a jedynie zastępowane nowymi.


Historia[edytuj | edytuj kod]

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

Prace nad sieciami sensorowymi 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 sensorowej 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 sensorowych[2].

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

Na przełomie stuleci ważnym krokiem w rozwoju sieci sensorowych 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 (np. MEMS) pozwalają na miniaturyzację, zwiększenie wydajności a zarazem obniżenie kosztów produkcji czujników, a co za tym idzie -- rozpowszechnienie sieci czujnikowych. Firmy takie jak Ember, Echelon czy Sensoria oferują gotowe urządzenia, wyposażone w czujniki, mikrokontrolery oraz urządenia nadawczo-odbiorcze[4].

W związku z rozpowszechnieniem urządzeń bezprzewodowych, takich jak telefony komórkowe, odbiorniki GPS oraz popularyzacją dostępu do internetu, bezprzewodowe sieci sensorowe 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 sensorowych.

Zastosowania[edytuj | edytuj kod]

Bezprzewodowe sieci sensorowe 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 sensorowych[edytuj | edytuj kod]

Algorytmy stosowane do samoorganizacji sieci sensorowych 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 sensorowej 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 sensorowej 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 Strenght 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 sensorowych, 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][edytuj | edytuj kod]

TopDisc to algorytm służący do wykrywania topologii sieci. Jeden z węzłów w sieci rozsyła żądanie "topology discovery request", który przekazywany 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][edytuj | edytuj kod]

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][edytuj | edytuj kod]

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 - np. w miejscu awarii lub dołączenia nowego węzła. W LEGOS wyróżnione są trzy rodzaje węzłów:

  • liderzy (leader), z których tworzony jest szkielet sieci,
  • bramy (gateway) - odpowiedzialne za połączenia między liderami,
  • członkowie sieci, połączeni 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, to 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, to rejestracja nowego lidera kończy procedurę, jeśli pośredniczył zwykły członek, to 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 (ang. Local Minimum Spanning Tree - Local MST)[edytuj | edytuj kod]

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 (ang. Wireless Ad-hoc Control Network)[edytuj | edytuj kod]

W stworzonej w 2005 roku na uniwersytecie Wollongong 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(ang). Przeszukiwanie węzłów w sieci może przebiegać pod kątem znalezienia węzła do spełnienia konkretnego zadania (np.~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 pozostali członkowie klastra (ang. Slaves) komunikują się jedynie z nim. W sieci wyróżnione są także węzły NCAP (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/uszkodzenie niektórych węzłów, zmiana zadania przydzielonego sieci lub klastrowi, zmiana węzła nadrzędnego.

Graf sąsiedztwa względnego (ang. Relative neighborhood graph) oraz Graf Gabriela(ang.)[edytuj | edytuj kod]

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, to węzły które się w nim znajdują stają się węzłami pośrednimi w komunikacji.

Metody niezawodnościowe w sieciach WSN[edytuj | edytuj kod]

Techniki trasowania stosowane w sieciach Ad-Hoc nie mogą zostać zaimplementowane w bezprzewodowych sieciach sensorowych ponieważ:

  1. 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,
  2. 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,
  3. węzły sensorowe narzucają wiele ograniczeń dot. mocy transmisji, rezerwacji energii, ilości pamięci niezbędnej do wykonania wszystkich procesów,
  4. 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 otoczenia przekroczy 60 °C, to odpowiadać powinny jedynie sensory rejestrujące temperaturę większą niż zadana.

Płaskie protokoły trasowania (Flat Routing Protocols)[edytuj | edytuj kod]

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ą 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 trasowania danowo—scentralizowanego (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).

Sensor Protocol for Information via Negotiation (SPIN)[edytuj | edytuj kod]

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.

Directed Diffusion (ukierunkowane rozchodzenie się)[edytuj | edytuj kod]

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.

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[edytuj | edytuj kod]

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 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. 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ę trasowania wpisując ścieżkę krótszą.

Minimum Cost Forwarding Algorithm (MCFA)[edytuj | edytuj kod]

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, 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ę.

Hierarchiczne protokoły trasowania (Hierarchical Routing Protocols)[edytuj | edytuj kod]

Trasowanie hierarchiczny – topologie

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 trasowania 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 trasowanie rejestrowanych danych. W sieciach sensorowych wykorzystuje 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 itd.

LEACH (Low Energy Adaptive Clustering Hierarchy)[edytuj | edytuj kod]

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:
T(n)={p \over 1-p (r\times mod\left( \frac {1}{p} \right)) }, p \in G
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 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.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • 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. , 2007. ACM Transactions on Sensor Networks. 
  • Cauligi S. Raghavendra, Krishna M. Sivalingam, Taieb Znati: Wireless sensor network. New York: Kluwer Acedemic Publishers, 2004. ISBN 978-1-4020-7884-2.

Przypisy

  1. 1,0 1,1 1,2 1,3 Chee-Yee Chong, Srikanta P. Kumar. Sensor Networks: Evolution Opportunities and Challenges. , 2003. Proceedings of the IEEE. 
  2. 2,0 2,1 2,2 Fazel Naghdy, Nathan Simiana. Adaptive Self-organisation of Wireless Ad-hoc Control Networks. , 2007. Wollongong: IEEE. 
  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. 5,0 5,1 5,2 Smeets, Hugues and Steenhaut, Kris and Now\'{e}, Ann. An efficient distributed self-organizing routing algorithm for Wireless Sensor Networks. „Proceedings of the 2008 International Conference on Complex, Intelligent and Software Intensive Systems”, 2008. IEEE Computer Society. 
  6. 6,0 6,1 Jian Zhong, Peter Bertok. A Variable Threats Based Self-Organization Scheme for Wireless Sensor Networks. „Proceedings of the 2009 Third International Conference on Sensor Technologies and Applications”, 2009. IEEE Computer Society. 
  7. 7,0 7,1 7,2 7,3 7,4 7,5 Ibrahim Amadou, Fabrice Valois. Performance evaluation of distributed self-organization protocols in wireless sensor networks. „Proceedings of the 7th ACM workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks”, 2010. 
  8. 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. 10,0 10,1 Fazel Naghdy, Shengrong Bu. Wireless Ad-hoc Networks. „3rd IEEE International Conference on Industrial Informatics (INDIN)”, 2005. 
  11. 11,0 11,1 Fazel Naghdy, Nathan Simiana. Adaptive Self-organisation of Wireless Ad-hoc Control Networks. „IEEE International Conference on Signal Processing and Communications”, 2007.