Hierarchiczne protokoły rutingu
Protokół LEACH
Protokół LEACH (ang. Low-Energy Adaptive Clustering Hierarchy) [ 10], [3] czyli niskoenergetyczna samoadaptująca się hierarchia grup jest jednym z pierwszych hierarchicznych protokołów routingu w sieciach sensorowych. Jest on protokołem bazującym na tworzeniu klastrów węzłów sieci sensorowych, które służą do komunikacji z węzłem nadrzędnym (ang. sink). Autorzy protokołu pozwolili na losową rotację w wyborze węzłów głównych w klastrach co pozwoliło na redukcję w wykorzystaniu energii i równomierną dystrybucje obciążenia energetycznego na wszystkie węzły w sieci. LEACH wykorzystuje współrzędne lokalizacyjne do zapewnienia skalowalności sieci sensorowych oraz zapewnia agregację danych, dzięki czemu znacznie ogranicza liczbę danych transmitowanych do węzła nadrzędnego. Ponadto autorzy użyli technikę TDMA (ang. Time Division Multiplexing Access) i CDMA (ang. Code Division Multipexing Access), aby zredukować kolizje i interferencje międzyklastrowe oraz wewnątrzklastrowe.
Działanie protokołu LEACH można podzielić na dwie fazy: fazę zestawiania i fazę ustaloną. W fazie zestawiania organizują się klastry i wybierany jest węzły główny w każdym klastrze. Natomiast, w fazie ustalonej jest wykonywana transmisja danych do węzła nadrzędnego w sieci. Czas trwania fazy ustalonej jest zdecydowanie dłuższy od fazy zestawienia, co wynika z chęci zminimalizowania narzutu w sieci oraz efektywnego wykorzystania sieci.
Podczas fazy zestawiania pewna część węzłów sieciowych p wybiera spośród siebie węzeł główny w sposób przedstawiony poniżej:
Węzeł sensorowy wybiera losowo numer r z przedziału od 0 do 1. Jeśli ten numer jest mniejszy niż wartość progowa T(n) węzeł ten staje się węzłem głównym dla danego klastra.
Wartość progowa wyliczana jest ze wzoru nr 3.1, która bierze pod uwagę procentową chęć stania się przez węzeł węzłem głównym dla klastra, teraźniejszą rundę wyboru oraz grupy węzłów jeszcze nie wybranych na główny dla klastra w ostatnich 1/p rundach – oznaczonych jako G. Cała formuła wygląda następująco:
jeśli n ε G
(3.1)
Po tym jak węzły główne zostały wybrane rozsyłają one do wszystkich innych węzłów informacje o swoim istnieniu. Podczas odbioru tej informacji węzły decydują do których klastrów chcą należeć. Przy wyborze główną metryką jest moc sygnału przy odbiorze informacji od węzłów głównego. Następnie węzły sensorowe informują wybrane węzły główne, że będą członkami ich klastra.
Po otrzymaniu wszystkich informacji od węzłów, które chcą wchodzić w skład klastra, węzeł główny przydziela każdemu węzłowi szczelinę czasową zgodnie z techniką TDMA, aby ten mógł transmitować do niego dane. W czasie fazy ustalonej węzły w klastrze mogą wykonywać swoje zadania (pomiary i obserwacje) i transmitować dane w swojej szczelinie czasowej. Węzeł główny agreguje dane odebrane od węzłów w klastrze i przesyła je do węzła nadrzędnego. Po określonym czasie sieć wraca do fazy zestawiania i wkracza w następną rundę elekcji węzłów głównych dla klastrów (rys. 3.10). Zauważyć należy, że każdy klaster używa różnego kodu CDMA podczas komunikacji co ma na celu redukcję interferencji pochodzących od węzłów należących do innych klastrów.
Rysunek. 3.10 Przebieg wyboru węzłów głównych w protokole LEACH.
Zostało udowodnione, że protokół LEACH dzięki swojemu działaniu jest w stanie podnieść żywotność sieci . Uwidaczniają się jednak pewne słabości protokołu:
Zakłada on, że każdy węzeł w sieci ma energię wymaganą do transmisji danych i zapewni energię protokołom niższych warstw, co może być błędem.
Nie przewiduje sytuacji, w której węzły leżą bardzo blisko siebie i transmitują identyczne dane.
Zakłada, że węzły mają cały czas dane do wysłania.
Ciężko jest określić czy przewidzieć liczbę potrzebnych węzłów głównych klastrów p. Możliwa jest sytuacja w której wybrane węzły główne leżą w tej same części sieci i pewne węzły mogą nie należeć do żadnych klastrów.
Dlatego też protokół potrzebuje pewnych usprawnień. Jedną z najważniejszych rzeczy jest wprowadzenie mechanizmu, który bierze pod uwagę niejednolite zasoby energetyczne każdego węzła. Inną propozycją jest dodanie do protokołu fazy negocjacji, która podobnie jak w protokole SPIN decydowałaby o potrzebie przesyłania danych od węzłów w klastrach do węzłów głównych. Mogłoby to zapewnić przesył tylko nowym informacjom do węzła głównego.
Protokół TEEN
TEEN (ang. Threshold sensitive Energy Efficient sensor Network) [17] jest protokołem hierarchicznym opartym na dobrze znanym protokole LEACH. Protokół stosuje ruting reaktywny czyli przeznaczony jest do aplikacji, w których ważne jest natychmiastowe wykrycie znacznych zmian wartość mierzonego atrybutu np. temperatury.
Podobnie jak w protokole LEACH węzły sensorowe organizowane są w klastry i wybierany jest węzeł główny klastra. Następnie węzeł główny rozsyła dwie wartości progowe do wszystkich węzłów: twardy próg HT (ang. hard threshold ) i miękki próg ST (ang. soft threshold) oraz przydziela szczelinę czasową w technice TDMA. Twardy próg to minimalna wartość mierzonego atrybutu, przy którym następuje włączenie nadajnika i transmitowanie danych do węzła głównego. W ten sposób twardy próg pozwala węzłowi na transmisje tylko jeśli atrybut jest w zakresie zainteresowania aplikacji, a przez to redukuje liczbę transmisji.
Węzeł zapisuje zmierzoną wartość (wyższą od HT) w zmiennej nazywanej SV (ang. sesned value). Następne dane węzeł będzie transmitował jeśli zostaną spełnione dwa warunki:
następna zmierzona wartość atrybutu jest wyższa od twardego progu HT,
następna zmierzona wartość atrybutu różni się od zmierzonej wartości poprzedniej SV o wartość większą lub równa miękkiemu progowi ST,
W rezultacie miękki próg redukuje liczbę transmisji, jeśli nie ma zmiany mierzonej wartości lub jest ona minimalna przez co wpływa na mniejsze zużycie energii. Odpowiednie ustawienie progu miękkiego i twardego daje możliwość regulacji liczby transmitowanych pakietów.
Główną wadą protokołu jest fakt, że jeśli w/w progi nie zostaną osiągnięte, to węzeł nigdy się nie skomunikuje i użytkownik nie otrzyma żadnych danych z sieci. Idąc dalej użytkownik może nawet nie wiedzieć, że wszystkie węzły w sieci zostały zniszczone. Dodatkowo protokół może marnować szczeliny czasowe przydzielone do węzła, które nic nie transmitują. Z tych powodów protokół nie jest odpowiedni dla aplikacji, gdzie dane muszą być regularnie dostarczane. Wydaje się, że najlepszym zastosowaniem tego protokołu TEEN jest w aplikacjach detekcyjnych np. detekcja wybuchu czy pożaru.
Protokół APTEEN
Protokół APTEEN (ang. Adaptive Threshold sensitive Energy Efficient sensor Network) [10] jest rozszerzeniem protokołu TEEN i skupia się zarówno na okresowym przetwarzaniu danych z węzłów jak i na reakcji na zdarzenia (ang. event-driven) czyli przeprowadza ruting hybrydowy. Protokół działa w podobny sposób do protokołu TEEN ustalając twardy i miękki próg, a także przydziela szczelinę czasową dla każdego węzła w technice TDMA. Ponadto został wprowadzony licznik czasu CT (ang. count time), który określa maksymalny czas pomiędzy przesłaniem kolejnych raportów danych. Trzeba zaznaczyć, że APTEEN umożliwia stosowanie trzech różnych zapytań: historyczne – analiza danych z przeszłości, rzeczywiste – analiza aktualnego stanu sieci i monitorujące – monitowanie określonego zdarzenia przez wyznaczony okres czasu w przyszłości. W odróżnieniu od protokołu TEEN rozróżnia on węzły uszkodzone w sieci, a także w sposób bardziej elastyczny i optymalny przydziela szczeliny czasowe.
Protokół powiela jednak większość wad protokołu LEACH, a ponadto jest bardziej skomplikowany.
Protokół PEGASIS
Protokół PEGASIS (ang. Power-Efficient Gathering in Sensor Information Systems) [17] jest rozszerzeniem protokołu LEACH. Główną ideą protokołu jest wydłużenie życia sieci poprzez komunikacje wybranego węzła tylko z najbliższym sąsiadem oraz rundowy wybór węzła, który będzie się komunikował z węzłem nadrzędnym. Kiedy runda wszystkich węzłów komunikujących się z węzłem nadrzędnym się skończy następuje start kolejnej rundy i tak dalej. Takie zachowanie węzłów znacznie redukuje moc potrzebną do transmisji danych w czasie rundy ponieważ zapotrzebowanie na nią jest równomiernie rozłożone na wszystkie węzły. W ten sposób protokół osiąga swoje dwa zadania:
Zwiększa długości życia każdego węzła poprzez użycie techniki współpracy a przez to zwiększenie życia całej sieci,
Zezwala tylko na lokalną koordynację pomiędzy węzłami, które są najbliżej siebie, a przez to wykorzystanie pasma przy komunikacji jest znacznie zmniejszone.
Aby zlokalizować najbliższego sąsiada każdy węzeł używa siły sygnału do zmierzenia odległości do węzłów sąsiednich, a następnie dostraja siłę sygnału tak, aby był on odbierany tylko przez jeden węzeł. Łańcuch tworzony przez PEGASIS składa się z węzłów nawzajem najbliższych przez co formuje się ścieżka do węzła nadrzędnego. Zagregowane dane są przesyłane, przez każdy węzeł w łańcuchu, a węzły w kolejnych rundach określają, który z nich przesyła dane bezpośrednio do węzła nadrzędnego. Autorzy protokołu w swoich symulacjach [17] pokazali, że PEGASIS może wydłużyć czas życia sieci dwukrotnie w porównaniu do sieci działającej na protokole LEACH – rys 3.11.
Rysunek. 3.11. Wydłużenie czasu życia sieci dzięki zastosowaniu protokołu PEGASIS w porównaniu do protokołu LEACH. Sieci o obszarze 50m x 50m i energii początkowej 25J/węzeł.
Niemniej jednak protokół PEGASIS wymaga przyjęcia pewnych założeń co znacznie utrudnia stosowanie go w rzeczywistych aplikacja :
Każdy węzeł w sieci może komunikować się z węzłem nadrzędnym. A jak wiemy z praktyki węzły sensorowe używają komunikacji wieloskokowej.
Każdy węzeł w sieci posiada i zarządza kompletną bazą danych o lokalizacji wszystkich węzłów w sieci.
Wszystkie węzły w sieci posiadają takie same zasoby energetyczne i prawdopodobnie zginą w tym samym czasie.
Z w/w powodów PEGASIS może być stosowany tylko w szczególnych aplikacjach.
Protokół HAR
HAR (ang. Hierarchy-based Anycast Routing) [6], [21] to protokół rutingu, który buduje drzewo rutingu w węźle nadrzędnym. Węzeł ten inicjuje tworzenie drzewa rutingu poprzez rozgłoszenie pakietu zapraszającego węzły pochodne. Węzeł odbierający pakiet z zaproszeniem czeka na inne takie pakiety od alternatywnych węzłów nadrzędnych, a następnie wybiera najlepszy z nich i wysyła pakiet z chęcią dołączenia. Węzeł nadrzędny akceptuje zgłoszenie węzła i przesyła pakiet akceptacji. Jeśli węzeł pochodny nie otrzyma pakietu akceptacji w określonym czasie wysyła ponownie pakiet z chęcią dołączenia do węzła nadrzędnego (drugi i ostatni raz). Kiedy węzeł pochodny otrzyma pakiet akceptacji zaczyna on staranie o bycie węzłem nadrzędnym dla innych węzłów i rozsyła pakiet z zaproszeniem. W ten sposób tworzona jest struktura hierarchiczna sieci, w której każdy węzeł („dziecko”) zna swój węzeł nadrzędny („ojciec”) i węzeł nadrzędny („dziadek”) swojego węzła nadrzędnego.
Ponieważ węzeł przesyła wszystkie dane zawsze tylko do węzła nadrzędnego jedną z głównych wad protokołu jest problem „hostspot” czyli nadmierne wykorzystanie węzłów nadrzędnych, a co z tym idzie ich zanikanie. Ponadto podczas tworzenia tabeli rutingu jest wysyłana bardzo duża liczba pakietów co wprowadza znaczny narzut transmitowanych danych.
komentarze
Copyright © 2008-2010 EPrace oraz autorzy prac.