Komunikační protokoly v bezdrátových senzorových sítích

MASARYKOVA UNIVERZITA FAKULTA INFORMATIKY

Komunikační protokoly v bezdrátových senzorových sítích DIPLOMOVÁ PRÁCE

Martin Langer

Brno, 2014

Prohlášení Prohlašuji, že tato práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.

Vedoucí práce: prof. RNDr. Václav Matyáš, M.Sc., Ph.D.

Poděkování Na tomto místě bych rád poděkoval prof. RNDr. Václavu Matyášovi, M.Sc., Ph.D. za vedení mé diplomové práce, cenné rady a připomínky. Dále bych rád poděkoval RNDr. Martinu Stehlíkovi za cenné rady při vytváření implementační části práce.

Shrnutí Tato diplomová práce se zabývá komunikačními protokoly, které se používají v bezdrátových senzorových sítích. Cílem první části práce je vypracování přehledu protokolů, které se používají pro řízení přístupu k médiu, a protokolů, které se používají pro směrování v bezdrátových senzorových sítích. Druhá část práce se zabývá implementací vybraných směrovacích protokolů pro simulátor MiXiM a jejich simulaci ve vytvořeném simulačním prostředí.

Klíčová slova Bezdrátová senzorová síť, řízení přístupu k médiu, MAC, směrování, SPIN, OMNeT++, MiXiM, simulace.

Obsah 1 Úvod

3

2 Fyzická vrstva

6

3 Protokoly pro řízení přístupu k médiu 3.1 Řízení přístupu k médiu . . . . . . . . 3.2 Protokoly založené na soupeření . . . . 3.2.1 S-MAC . . . . . . . . . . . . . . 3.2.2 T-MAC . . . . . . . . . . . . . 3.2.3 B-MAC . . . . . . . . . . . . . 3.2.4 X-MAC . . . . . . . . . . . . . 3.2.5 WiseMAC . . . . . . . . . . . . 3.2.6 RI-MAC . . . . . . . . . . . . . 3.2.7 PW-MAC . . . . . . . . . . . . 3.2.8 PMAC . . . . . . . . . . . . . . 3.3 Protokoly založené na plánu . . . . . . 3.3.1 LEACH . . . . . . . . . . . . . 3.3.2 SMACS . . . . . . . . . . . . . 3.3.3 TRAMA . . . . . . . . . . . . . 3.3.4 PEDAMACS . . . . . . . . . . 3.3.5 DMAC . . . . . . . . . . . . . . 4 Směrovací protokoly 4.1 Klasifikace směrovacích protokolů 4.2 Protokoly pro ploché směrování . 4.2.1 SPIN . . . . . . . . . . . . 4.2.2 Directed diffusion . . . . . 4.2.3 Rumor routing . . . . . . 4.2.4 GBR . . . . . . . . . . . . 4.2.5 MCFA . . . . . . . . . . . 4.2.6 COUGAR . . . . . . . . . 4.2.7 ACQUIRE . . . . . . . . . 4.2.8 IDSQ a CADR . . . . . .

. . . . . . . . . . 1

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

9 9 9 10 12 15 15 17 17 19 20 21 21 22 24 25 26

. . . . . . . . . .

29 29 30 30 33 34 36 36 37 38 39

OBSAH

4.3

4.4

4.2.9 Energy aware routing . . . . Hierarchické protokoly . . . . . . . 4.3.1 LEACH . . . . . . . . . . . 4.3.2 PEGASIS . . . . . . . . . . 4.3.3 TEEN . . . . . . . . . . . . 4.3.4 APTEEN . . . . . . . . . . 4.3.5 SOP . . . . . . . . . . . . . Protokoly založené na umístění uzlů 4.4.1 GAF . . . . . . . . . . . . . 4.4.2 GEAR . . . . . . . . . . . . 4.4.3 MECN . . . . . . . . . . . . 4.4.4 SMECN . . . . . . . . . . . 4.4.5 SPAN . . . . . . . . . . . . 4.4.6 SPEED . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

40 40 40 40 42 43 43 44 45 46 48 49 49 50

5 Implementace směrovacích protokolů 5.1 Simulátory pro bezdrátové senzorové sítě 5.2 OMNeT++ . . . . . . . . . . . . . . . . 5.2.1 MiXiM . . . . . . . . . . . . . . . 5.3 Implementace protokolu SPIN-PP . . . . 5.4 Implementace protokolu SPIN-BC . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

52 52 52 53 54 56

6 Simulace protokolů 6.1 Parametry simulací 6.2 Simulace 1 . . . . . 6.3 Simulace 2 . . . . . 6.4 Diskuse výsledků .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

57 57 58 61 62

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

7 Závěr

64

Seznam použité literatury

66

A Instalace frameworku OMNeT++ a simulátoru MiXiM

70

B Obsah přiloženého CD

71

2

Kapitola 1 Úvod V současné době se stále více setkáváme se senzory a bezdrátovými senzorovými sítěmi. Bezdrátové senzorové sítě se skládají z velkého množství prostorově distribuovaných zařízení označovaných jako senzorové uzly, které slouží k monitorování podmínek okolního prostředí, jako jsou teplota, světlo, tlak, hustota, vlhkost, průtok atd. Vývoj těchto sítí začal v devadesátých letech dvacátého století a byl motivován vojenským výzkumem, jehož cílem bylo monitorování fyzikálních veličin pomocí senzorů rozmístěných na rozsáhlém území. Na základě hodnot naměřených těmito senzory bylo možné získat informace o změnách teploty, tlaku a vibrací, a tím tedy odhalit pohyb nepřátelských vojsk. Kromě využití ve vojenství nachází bezdrátové senzorové sítě v současné době uplatnění i v mnoha dalších odvětvích – lze je využít ve zdravotnictví (monitorování pacientů), v zemědělství, pro monitorování životního prostředí (počasí, teplota, tlak. . . ) nebo například pro tzv. inteligentní domy (domy, jejichž základem je řídící jednotka, která se stará o optimální využití dostupných tepelných zdrojů, ovládání různých domácích spotřebičů, zabezpečení atd.). Senzorové uzly, ze kterých se síť skládá, se obecně skládají z výpočetní části, senzorové části, radiofrekvenčního vysílače a baterie. Vzhledem k tomu, že jsou senzorové uzly napájeny baterií, jedním z nejdůležitějších požadavků při budování takovéto sítě se stává minimalizace energetické náročnosti. Tomuto požadavku je podřízen nejen výpočetní výkon senzorového uzlu a programové vybavení, ale i přenosové protokoly, které jsou navrhovány s cílem maximální úspory energie. Jednotlivé senzorové uzly tvořící bezdrátovou senzorovou síť spolu tedy komunikují pomocí co nejjednodušších protokolů a navíc jsou závislé na komunikaci s tzv. základnovou stanicí (označovanou jako base station nebo gateway), která celou síť řídí, přijímá a vyhodnocuje informace od všech uzlů a zprostředkovává komunikaci s okolním světem. Jak již bylo uvedeno, bezdrátové senzorové sítě našly široké uplatnění v mnoha různých odvětvích. Velká rozmanitost těchto odvětví ale způsobuje, že není možné použití univerzálních technik pro komunikaci mezi jednotlivými uzly sítě. Z toho důvodu se používá poměrně velký počet různých komunikačních protokolů, které jsou navrhovány tak, aby plnily požadavky sítě implementované v určitém prostředí. Mezi základní vlastnosti bezdrátových senzorových sítí, které jsou zohledňovány při návrhu protokolů, patří následující:

3

KAPITOLA 1. ÚVOD

• omezená životnost senzorového uzlu způsobená napájením uzlu baterií, • schopnost automatické konfigurace sítě, • nespolehlivá komunikace způsobená bezdrátovým přenosovým médiem, • velký počet uzlů v síti (až v řádu tisíců), • poruchovost uzlů (způsobená podmínkami daného prostředí), • malá velikost uzlů (a s tím spojená menší velikost baterie, menší výpočetní výkon a paměť), • nepohyblivost uzlů (ve většině případů není obvykle nutné řešit mobilitu uzlů), • možnost kooperace uzlů (díky tomu, že se všechny uzly snaží dosáhnout určitého společného cíle). Zohledňování těchto vlastností při návrhu protokolů je důležité pro efektivní využívání zdrojů sítě. Na druhou stranu je vhodné, aby protokoly byly co nejjednodušší. Proto se obvykle zohledňují pouze některé vlastnosti s ohledem na konkrétní prostředí.

Obrázek 1.1: Bezdrátová senzorová síť [1] Cílem této diplomové práce je zpracování přehledu nejpoužívanějších protokolů, na jejichž základě probíhá komunikace mezi senzorovými uzly v bezdrátových senzorových sítích. Druhá část práce je věnována implementaci dvou směrovacích protokolů (SPIN-PP a SPIN-BC) pro simulátor MiXiM a jejich simulaci ve vytvořeném simulačním prostředí. První kapitola obsahuje úvodní informace o hlavní náplni práce a stručně popisuje základní vlastnosti bezdrátových senzorových sítí. Ve druhé kapitole je stručně popsán princip modulace dat pro přenos bezdrátovým přenosovým médiem. V těchto prvních dvou kapitolách čerpám zejména z knihy Protocols and Architectures for Wireless Sensor Networks [2]. Třetí kapitola se podrobněji zabývá protokoly pro řízení přístupu k médiu, které jsou zde rozděleny do dvou skupin (protokoly založené na soupeření a protokoly založené na plánu). 4

KAPITOLA 1. ÚVOD

Čtvrtá kapitola se zabývá směrováním v bezdrátových senzorových sítích. Jednotlivé protokoly jsou v této kapitole rozdělovány do tří skupin (protokoly pro ploché směrování, hierarchické protokoly a protokoly založené na umístění uzlů). Pátá kapitola je věnována implementaci směrovacích protokolů SPIN-PP a SPIN-BC pro simulátor MiXiM a šestá kapitola jejich simulaci ve vytvořeném simulačním prostředí.

5

Kapitola 2 Fyzická vrstva Jedním z hlavních úkolů fyzické vrstvy (nejnižší vrstvy referenčního modelu ISO/OSI) v bezdrátových senzorových sítích je přenos digitálních dat pomocí tzv. modulace a demodulace. Tento úkol je prováděn pomocí vysílače, resp. přijímače, který je součástí každého senzorového uzlu. Pro přenos analogového signálu je velmi důležitý výběr nosné frekvence (resp. frekvenčního pásma), která výrazně ovlivňuje šíření signálu (např. jak dobře signál prochází překážkami, jako jsou zdi). V případě radiofrekvenčních komunikací začíná rozsah používaných frekvencí v pásmu tzv. „velmi nízké frekvence“ (very low frequency, VLF) a končí v pásmu „extrémně vysoké frekvence“ (extremely high frequency, EHF). Místo radiofrekvenční komunikace je také možné použít komunikaci infračervenou, kde infračervené spektrum je mezi vlnovými délkami 1 mm (odpovídající přibližně 300 GHz) a 2,5 µm (120 THz) nebo komunikaci optickou, kde rozsah končí u vlnové délky 780 nm (přibližně 385 THz) [2].

Obrázek 2.1: Elektromagnetické spektrum – radiofrekvenční komunikace [2] Při přenosu dat v síti se používá modulace, což je proces, kterým se pomocí modulujícího signálu mění vlastnosti nosného signálu (amplituda, frekvence nebo fáze). Tento odeslaný 6

KAPITOLA 2. FYZICKÁ VRSTVA

modulovaný signál přijímá příjemce, který na základě parametrů modulovaného signálu získá pomocí demodulace původní modulační signál. Tyto parametry lze vyjádřit pomocí následující rovnice: s(t) = A(t) ∗ cos(ω(t) + Φ(t)), kde A(t) označuje časově závislou amplitudu, ω(t) časově závislou frekvenci a Φ(t) fázový posun [2]. Existují tři základní používané typy modulací (příp. jejich kombinace): • Amplitudová digitální modulace (Amplitude Shift Keying, ASK) - mění se amplituda nosného signálu (modulace signálu, který reprezentuje logickou hodnotu „0“ , má jinou amplitudu oproti logické hodnotě „1“ ). • Frekvenční digitální modulace (Frequency Shift Keying, FSK) – mění se frekvence nosného signálu. • Fázová digitální modulace (Phase Shift Keying, PSK) – mění se fáze nosného signálu.

Obrázek 2.2: Příklad modulace ASK, FSK, PSK [3] Při přenosu analogového signálu bezdrátovým přenosovým médiem na signál působí různé fyzikální jevy, které jej mohou deformovat. To může způsobit, že příjemce přijímá signál, který se liší od původního odeslaného signálu. Mezi základní jevy, ke kterým dochází při šíření vlnění, patří následující [2]: 7

KAPITOLA 2. FYZICKÁ VRSTVA

• Odraz – k odrazu dochází, pokud se přicházející vlnění dostane na rozhraní dvou prostředí. Pokud je toto rozhraní dostatečně hladké, část vlnění se odrazí zpět do prostředí, ze kterého vlnění přichází, část vlnění se přenáší do nového prostředí a zbytek vlnění je absorbován. • Ohyb – pokud se vlnění setká s nějakou překážkou, potom dojde na této překážce k jeho ohybu. Tím se vlnění odkloní od přímého směru svého šíření a dále se šíří i do oblasti tzv. geometrického stínu. • Rozptyl – pokud vlnění dopadne na rozhraní, které je drsné, potom se vlnění odráží v různých místech do různých směrů. • Dopplerův jev – jestliže se vysílající zdroj vlnění a přijímač pohybují, potom je při jejich vzájemném vzdalování frekvence vlnění přijímaného přijímačem nižší, při jejich přibližování je frekvence přijímaného vlnění naopak vyšší.

Obrázek 2.3: Ilustrace odrazu (a), ohybu (b) a rozptylu (c) vlnění [2] Tyto fyzikální jevy umožňují, že vysílač a přijímač nemusí být v přímé viditelnosti. Aby se účinky těchto jevů co nejvíce minimalizovaly, je analogový signál vysílán v několika kopiích, které se dostanou k přijímači po různých cestách a s různým útlumem. Signál přijímaný přijímačem je tedy superpozicí několika kopií stejného signálu.

8

Kapitola 3 Protokoly pro řízení přístupu k médiu 3.1

Řízení přístupu k médiu

Druhou vrstvou modelu ISO/OSI je linková vrstva. Mezi její hlavní úkoly patří přijímání paketů od síťové vrstvy a tvorba rámců, adresování entit pomocí fyzických (MAC) adres, chybové řízení, řízení toku a řízení přístupu k médiu (Medium Access Control, MAC). Následující kapitola se věnuje protokolům, které byly navrženy pro řízení přístupu k médiu v bezdrátových senzorových sítích (tzv. MAC protokoly). Hlavním úkolem těchto protokolů je koordinace přístupu jednotlivých uzlů v síti ke sdílenému přenosovému médiu. Tyto protokoly jsou obvykle navrhovány s cílem co největší propustnosti, spravedlnosti, co nejmenšího zpoždění a zejména co největší úspory energie. Té lze dosáhnout například přechodem senzorového uzlu do režimu spánku. MAC protokoly používané v bezdrátových senzorových sítích se obvykle rozdělují do dvou skupin: • protokoly založené na soupeření (contention-based protocols), • protokoly založené na plánu (schedule-based protocols). Následující část práce popisuje některé významné protokoly používané v bezdrátových senzorových sítích.

3.2

Protokoly založené na soupeření

Protokoly založené na soupeření umožňují uzlu odeslání paketu do přenosového média bez nutnosti využívání plánovacích mechanismů. Jsou založené na tom, že jednotlivé uzly soupeří se svými sousedy o přístup ke sdílenému médiu. V případě, že se více uzlů snaží získat přístup ke sdílenému médiu ve stejný okamžik, mohou vzniknout kolize. Proto je nutné používat mechanismy, které případné kolize detekují a poté se s nimi vypořádají.

9

KAPITOLA 3. PROTOKOLY PRO ŘÍZENÍ PŘÍSTUPU K MÉDIU

3.2.1

S-MAC

S-MAC (Sensor MAC) [4] je protokol navržený v roce 2002 speciálně pro senzorové sítě. Jeho hlavním cílem je redukce spotřeby energie. Vychází z toho, že v mnoha aplikacích senzorových sítí jsou uzly poměrně dlouhou dobu ve stavu nečinnosti, ve kterém pouze naslouchají, co se děje na přenosovém médiu, čímž se zbytečně spotřebovává energie uzlu. Tento problém řeší protokol S-MAC tím, že se v uzlech periodicky střídá režim naslouchání a režim spánku, přičemž pouze v režimu naslouchání je uzel schopen komunikovat s ostatními uzly. Během režimu spánku uzel vypne svůj přijímač a nastaví si časovač na dobu, kdy má být probuzen.

Obrázek 3.1: Periodické střídání režimu naslouchání a režimu spánku [4] Režim naslouchání lze rozdělit do dvou fází: • SYNC fáze, • RTS/CTS fáze. Režim naslouchání a spánku vyžaduje synchronizaci mezi uzly. Té je dosaženo tím, že každý uzel periodicky vysílá všesměrovým vysíláním (broadcast) krátký synchronizační paket SYNC, který umožňuje časovou synchronizaci a obsahuje informace o tom, kdy odesílající uzel přejde příště do režimu spánku. Tyto informace si každý uzel, který tento paket přijme, ukládá v plánovací tabulce (schedule table). Přijímání těchto synchronizačních paketů je prováděné v tzv. SYNC fázi, která je rozdělena do několika časových dílů, o které soupeří sousední uzly. Uzel, který se snaží odeslat svůj paket SYNC, si náhodně vybere jeden z časových dílů přijímajícího uzlu a pomocí protokolu CSMA (Carrier Sense Multiple Access) naslouchá na přenosovém médiu a pokouší se detekovat přítomnost jiného signálu v médiu. Pokud nedetekuje žádný signál do konce časového dílu, získá přístup k přenosovému médiu a začne vysílat svůj paket SYNC. Vzhledem k tomu, že více uzlů se může snažit vysílat přijímajícímu uzlu ve stejný okamžik, mohou v přenosovém médiu vznikat kolize. Pro omezení kolizí při posílání datových paketů se používají speciální krátké pakety RTS a CTS. Pokud některý uzel chce vysílat, poslouchá, zdali je na síti nějaká aktivita. Pokud zjistí, že je síť nečinná, odešle nejdříve uzlu, se kterým chce komunikovat, krátký paket RTS (Request To Send), kterým daný uzel žádá o právo k němu vysílat a informuje jej, jak dlouho bude vysílání trvat. V opačném 10


případě počká náhodně dlouhou dobu a poté znovu testuje aktivitu na síti. Pokud uzel odesílající paket RTS obdrží od uzlu, se kterým chce komunikovat, během určitého časového intervalu paket CTS (Clear To Send), může začít přenášet data. Součástí každého přenášeného paketu je i informace o tom, jak dlouho bude ještě přenos probíhat. Všechny uzly, které tyto pakety přijmou, si na základě této informace nastaví indikátor virtuálního naslouchání, tzv. NAV (Network Allocation Vector) na dobu trvání přenosu a nastaví si časovač, který po určitých intervalech snižuje hodnotu NAV, dokud nedosáhne nuly. Pokud některý uzel chce posílat data jinému uzlu, podívá se nejdříve na hodnotu NAV a pokud zjistí, že tato hodnota není nulová, tak vysílání odloží, protože médium je obsazené. Při vysílání dlouhých zpráv je obvykle vhodné jejich rozdělení do mnoha malých fragmentů (posílání dlouhých zpráv v jednom velkém paketu v případě poškození jeho malé části by vedlo k většímu plýtvání energií a zvyšování latence). Na začátku přenosu si uzly pouze jednou mezi sebou pošlou pakety RTS a CTS a poté se již zasílají jednotlivé fragmenty. Po přijetí každého fragmentu posílá přijímající uzel potvrzení o jeho doručení (ACK). Součástí každého přenášeného fragmentu i potvrzení je navíc informace o době potřebné pro přenesení zbývajících fragmentů. Po poslání každého fragmentu vysílající uzel vždy čeká na přijetí potvrzení o doručení. Pokud jej v daném časovém intervalu nedostane, zvýší informaci o době trvání přenosu zbývajících fragmentů (o dobu nutnou pro přenos jednoho fragmentu navíc) a okamžitě opakuje přenos nepotvrzeného fragmentu.

Obrázek 3.2: Fragmentace paketů v protokolu S-MAC [2]

11


Hlavní výhodou protokolu S-MAC je tedy výrazné šetření energie díky střídání režimu naslouchání a režimu spánku. Toto periodické přecházení do režimu spánku ale může vést k vysoké latenci (vzhledem k tomu, že každý uzel má svůj vlastní plán, kdy přechází do režimu spánku). Vysokou latenci je ale možné snížit pomocí tzv. adaptivního naslouchání. Tato technika je založená na tom, že uzel, který se dozví o probíhajícím přenosu sousedního uzlu (např. díky paketu RTS nebo CTS), čeká na dokončení tohoto přenosu (délka doby přenosu je známá díky informaci o době trvání uvedené v paketu RTS nebo CTS) a na konci přenosu se na krátkou dobu probudí. Díky tomu může sousední uzel začít odesílat tomuto uzlu data, aniž by musel čekat do doby, kdy by se měl uzel probudit podle svého původního plánu.

3.2.2

T-MAC

Dalším MAC protokolem, který patří mezi protokoly založené na soupeření, je protokol T-MAC (Timeout MAC) [5]. Tento protokol je založený na podobných principech jako protokol S-MAC. Uzly spolu komunikují s využitím paketů RTS, CTS a ACK. Stejně jako u protokolu S-MAC se i zde periodicky střídá režim naslouchání (doba, kdy uzel může komunikovat s ostatními uzly a během které odesílá zprávy, které se řadí do fronty během režimu spánku) a režim spánku (doba, po kterou má uzel vypnutý přijímač). Na rozdíl od protokolu S-MAC, kde režim naslouchání trvá vždy pevně danou předem definovanou dobu, u protokolu T-MAC se délka této doby dynamicky mění. Uzel přechází z režimu naslouchání do režimu spánku, pokud po dobu definovaného časového intervalu TA nenastala žádná aktivační událost. Touto aktivační událostí může být např. přijetí dat přijímačem uzlu (příp. paketů RTS, CTS, ACK), dokončení přenosu dat odesílaných uzlem atd. Během režimu spánku se potom ukládají zprávy do vyrovnávací paměti (buffer) a na začátku příštího režimu naslouchání jsou všechny odeslány (viz obrázek 3.3).

Obrázek 3.3: Srovnání střídání režimu naslouchání a režimu spánku u protokolů S-MAC a T-MAC (šipky označují odesílání a přijímání zpráv) [5] Během tohoto hromadného odesílání zpráv na začátku každého režimu naslouchání by mohlo dojít k zahlcení přenosového média. Proto na začátku každého přenosu (resp. před odesláním paketu RTS) uzel nejdříve čeká a poslouchá aktivitu na médiu po náhodně dlouhou dobu z pevně definovaného intervalu (označovaného jako interval pro soupeření). Na začátku přenosu odesílá vysílající uzel paket RTS a čeká po určitou dobu na odpověď od příjemce (ve formě paketu CTS) s povolením zahájit přenos dat. Pokud během této doby odesílající uzel nedostane paket CTS, mohlo dojít k některé z následujících událostí: 12


• přijímající uzel nepřijal paket RTS kvůli kolizi, • přijímající uzel přijal RTS nebo CTS od jiných uzlů, • přijímající uzel je v režimu spánku. Pokud odesílající uzel nedostane během intervalu TA odpověď od příjemce, měl by přejít do režimu spánku. Tím by se ale výrazně snížila propustnost, protože příjemce mohl být v režimu naslouchání a na paket RTS neodpověděl například z důvodu kolize. Proto odesílající uzel, který nedostal žádnou odpověď, odešle paket RTS znovu. Pokud nedostane žádnou odpověď ani po třetím odeslání paketu RTS, tak potom teprve přejde do režimu spánku. Dalším problémem, který musí protokol T-MAC řešit, je délka intervalu TA. Tento interval musí být dostatečně dlouhý, aby během něj byl odesílající uzel schopen přijmout alespoň začátek paketu CTS. Na druhou stranu by ale neměl být příliš dlouhý, aby se výrazně nezvyšovala spotřeba energie. Jeho minimální délka by měla splňovat následující nerovnost: T A > C + R + T, kde C označuje délku intervalu pro soupeření, R označuje délku paketu RTS a T označuje krátkou dobu od konce paketu RTS do začátku paketu CTS (viz obrázek 3.4).

Obrázek 3.4: Přenos dat v protokolu T-MAC – uzel C zaslechne paket CTS a nebude rušit komunikaci mezi uzly A a B (interval TA musí být dostatečně dlouhý, aby uzel C zaslechl začátek paketu CTS) [5] Asi největší výhodou protokolu T-MAC oproti protokolu S-MAC je, že je méně energeticky náročný. Na druhou stranu ale může způsobovat snížení propustnosti díky tomu, že doba, po kterou je uzel aktivní, má proměnlivou délku, a může tedy dojít k situaci, kdy uzel přejde do režimu spánku, přestože má jeho soused zprávy, které by mu chtěl zaslat. K tomuto problému dochází v případě, kdy provoz v síti je převážně jednosměrný.

13


Obrázek 3.5: Problém předčasného přechodu do režimu spánku [5] Na obrázku 3.5 se uzel C snaží poslat zprávu uzlu D. Nejdříve ale musí soupeřit o přístup k médiu s uzly A a B. Vzhledem k tomu, že zaslechne paket CTS odeslaný uzlem B, nemůže odeslat svůj paket RTS určený uzlu D. Uzel D ale neví o probíhající komunikaci mezi uzly A a B, a proto po uplynutí intervalu TA přejde do režimu spánku. Uzel C tedy nemůže poslat paket RTS uzlu D a další příležitost bude mít, až uzel D přejde znovu do aktivního stavu. Tento problém lze řešit dvěma způsoby. Prvním řešením je zaslání speciálního paketu FRTS (Future Request To Send). Na obrázku 3.5 by jej zaslal uzel C uzlu D hned po zaslechnutí paketu CTS od uzlu B. Tento paket obsahuje informace o tom, jak dlouho bude přenosové médium obsazené (tato informace je známá z paketu CTS). Uzel D tedy z tohoto paketu zjistí, že mu uzel C v určité době pošle paket RTS a v této době tedy musí být v aktivním stavu. Aby se zabránilo kolizi mezi daty odesílanými uzlem A uzlu B a paketem FRTS, odesílá uzel A nejdříve krátký paket DS (Data Send), který neobsahuje žádné důležité informace (v případě kolize tedy nedojde k žádné ztrátě). Poté již uzel A začne odesílat datové pakety. Druhé možné řešení je založené na tom, že nějaký uzel E, který má už téměř zaplněnou vyrovnávací paměť pro ukládání zpráv, se může rozhodnout, že bude raději zprávy odesílat než přijímat. Pokud tedy takový uzel přijme paket RTS, neodpoví na něj pomocí paketu CTS, ale místo toho odešle svůj vlastní paket RTS jinému uzlu, kterému by sám chtěl odesílat zprávy. Vzhledem k tomu, že uzel, který zasílal původní RTS, již získal přístup k médiu, se zvyšuje šance, že uzel E bude moci odesílat své vlastní zprávy.

14


3.2.3

B-MAC

Protokol B-MAC (Berkeley MAC) [6] je jedním z nejpoužívanějších MAC protokolů v bezdrátových senzorových sítích. Mezi jeho největší výhody patří například: • velmi nízká spotřeba energie, • efektivní vyhýbání se kolizím, • efektivní využívání komunikačního kanálu, • efektivita při vysoké i nízké rychlosti přenosu dat, • jednoduchá implementace. Efektivního vyhýbání se kolizím dosahuje protokol B-MAC tím, že každý uzel testuje, zda je komunikační kanál volný (pomocí tzv. Clear Channel Assessment, CCA). Hlavním problémem zde je, že uzel musí být schopen rozlišit, co je signál a co je šum. K tomu protokol B-MAC využívá speciální software AGC (Automatic Gain Control). Pomocí tohoto softwaru snímá vzorky síly signálu (toto snímání provádí v době, kdy předpokládá, že je kanál volný). Tyto snímky jsou řazeny do fronty a na základě těchto naměřených hodnot se určí prahová hodnota šumu. Pokud poté uzel chce odeslat nějaký paket, musí testovat, zda je kanál volný. To provádí tak, že nasnímá pět vzorků a podívá se na naměřenou sílu signálu. Pokud alespoň jeden ze snímků má sílu signálu výrazně nižší, než je prahová hodnota šumu, je kanál považován za volný. Pro snížení spotřeby energie protokol B-MAC používá techniku nazvanou Low Power Listening (LPL). Tato technika je založená na tom, že se uzel periodicky probouzí, zapne přijímač a pomocí CCA testuje aktivitu na komunikačním kanálu. Pokud detekuje aktivitu, zůstane v aktivním stavu po dobu potřebnou pro přijetí příchozího paketu. Po přijetí paketu uzel přejde do režimu spánku (případně přejde do režimu spánku po uplynutí časového intervalu, pokud žádný paket nepřijme). Aby bylo možné spolehlivě přijímat data, je délka preambule (začátku paketu) nastavena s ohledem na interval, během kterého se uzel probouzí, aby otestoval aktivitu v kanálu (tedy délka preambule by měla být alespoň tak dlouhá jako tento interval). Díky tomu by měl uzel mít dostatek času na to, aby se probudil, otestoval aktivitu v kanálu, přijal preambuli a poté i zprávu. Protokol B-MAC nepoužívá pro přenos dat pakety RTS a CTS ani synchronizaci používanou protokoly S-MAC a T-MAC. Díky tomu je jeho implementace jednodušší, což je vhodné vzhledem k tomu, že paměť senzorového uzlu je velmi malá.

3.2.4

X-MAC

Přestože je B-MAC jednoduchý, velmi efektivní a často používaný protokol, jedním z jeho největších nedostatků je zasílání příliš dlouhé preambule, čímž dochází k větší spotřebě energie. Pokud se přijímající uzel probudí a detekuje preambuli v přenosovém médiu, musí zůstat probuzený po zbytek doby přenosu dlouhé preambule a poté se teprve dozví, zda 15


je adresátem příslušného datového paketu (pokud není, tak přejde do režimu spánku). Tento problém řeší protokol X-MAC [7], který při přenosu dat nepoužívá jednu dlouhou preambuli, ale místo toho používá sérii několika preambulí kratších. Každá z těchto krátkých preambulí obsahuje adresu cílového uzlu. Pokud se přijímající uzel probudí a přijme tuto preambuli, podívá se, zda je jeho adresa shodná s adresou cílového uzlu uvedenou v preambuli. Pokud není, uzel přejde zpět do režimu spánku. V opačném případě zůstane probuzený a čeká na příjem datového paketu. Tyto jednotlivé krátké preambule nejsou odesílány v souvislém proudu, ale s určitými krátkými časovými odstupy. To umožňuje příjemci, který se již probudil a přijal jednu z preambulí, aby odeslal potvrzující paket (ACK) uzlu odesílajícímu preambule. V okamžiku, kdy odesílající uzel přijme tento paket, přestane již odesílat preambule a odešle datový paket (viz obrázek 3.6).

Obrázek 3.6: Porovnání protokolu používajícího dlouhé preambule s protokolem X-MAC [7] V některých případech odesílající uzel navíc nemusí vůbec odesílat preambule. Pokud v době, kdy tento uzel čeká na uvolnění komunikačního kanálu, detekuje preambuli a poté i potvrzující paket od uzlu, kterému chce sám odesílat data, počká náhodně dlouhou dobu, která je ale dostatečně dlouhá na to, aby byl během ní dokončen právě probíhající přenos. 16


Po uplynutí této doby začne odesílat data uzlu bez odesílání preambulí, protože již ví, že uzel je probuzený. Aby bylo možné použít tuto techniku, zůstává přijímající uzel probuzený ještě po určitou dobu po přijetí datového paketu pro případ, že by některý z uzlů mu chtěl také odeslat data.

3.2.5

WiseMAC

Dalším z protokolů, které při přístupu k médiu používají techniku LPL (stejně jako protokoly B-MAC a X-MAC), je protokol WiseMAC [8]. Všechny uzly zde testují aktivitu na médiu ve stejných časových intervalech, ale nezávisle na sobě (tedy přistupují k médiu v různém čase, ale intervaly mezi jednotlivými přístupy jsou pro všechny uzly stejné). Jak již bylo zmíněno, protokol B-MAC posílá dlouhou preambuli před vlastním datovým paketem, což způsobuje zbytečné plýtvání energií. Protokol WiseMAC řeší tento problém tak, že jednotlivé uzly zjistí, v jakých časových intervalech přistupují k médiu jejich sousedi, a na základě těchto informací určí co nejmenší možnou velikost preambule. Uzly, které úspěšně přijaly data, odesílají potvrzující paket (ACK) nejen proto, aby potvrdily úspěšný přenos dat, ale také pomocí tohoto paketu informují o době, kdy se pokusí znovu přistoupit k médiu. Díky tomu si mohou uzly udržovat tabulky obsahující informace o tom, kdy sousední uzly přistupují k médiu, a mohou jim tedy zasílat pakety ve správný čas. Podobně, jako protokol S-MAC nabízí mechanismus pro fragmentaci paketů, používá protokol WiseMAC za stejným účelem speciální bit umístěný v hlavičce datového paketu. Nastavením tohoto bitu na jedničku je přijímající uzel informován o tom, že odesílající uzel chce odeslat danému uzlu další data. V takovém případě přijímající uzel odešle paket ACK a čeká na příchod dalšího paketu. Tento způsob je navíc flexibilnější než fragmentace používaná protokolem S-MAC, protože umožňuje i zasílání několika různých zpráv (tedy nikoliv pouze fragmentů jedné zprávy). WiseMAC je energeticky nenáročným protokolem a díky možnosti dynamicky měnit délku preambule poskytuje velmi dobrý výkon i v případě proměnlivého provozu v síti. Hlavní nevýhodou tohoto protokolu ale je decentralizovaný přechod do režimu naslouchání a spánku (každý uzel přechází do režimu naslouchání a spánku v jiný čas). Tento problém se projeví zejména při všesměrovém vysílání, kdy takto odesílané pakety určené pro sousedy, které jsou v režimu spánku, jsou ukládány ve vyrovnávací paměti a doručovány několikrát v závislosti na tom, kdy se jednotlivé sousední uzly probouzí, což vede ke zvyšování latence a větší spotřebě energie.

3.2.6

RI-MAC

Protokoly založené na soupeření se často rozdělují do dvou skupin – na synchronní a asynchronní. Synchronní protokoly (mezi které patří např. protokoly S-MAC a T-MAC) vyžadují synchronizaci mezi uzly. Tyto uzly si pomocí synchronizačních paketů vyměňují informace o přechodech mezi režimem spánku a režimem naslouchání. Asynchronní protokoly synchronizaci nevyžadují a umožňují uzlům pracovat více samostatně. Asynchronní protokoly lze dále rozdělit do dvou následujících skupin: 17


• sender-initiated (např. B-MAC, X-MAC, WiseMAC) – protokoly, ve kterých komunikaci iniciuje odesílající uzel odesláním preambule před odesláním datového paketu, • receiver-initiated (např. RI-MAC, PW-MAC) – protokoly, ve kterých komunikaci iniciuje přijímající uzel pomocí signalizačních rámců (beacon). Jedním z nejvýznamnějších asynchronních protokolů založeném na soupeření, ve kterém je komunikace iniciována přijímajícím uzlem, je protokol RI-MAC (Receiver-Initiated MAC) [9]. Na rozdíl od protokolů iniciovaných odesílajícím uzlem, kde odesílající uzel vysílá dlouhé preambule, protokol RI-MAC žádné preambule nepoužívá. Odesílající uzel zde zůstává v aktivním stavu a čeká, dokud mu přijímající uzel neoznámí pomocí speciálního signalizačního rámce, že je připraven na přenos dat. Velikost tohoto rámce je mnohem menší než velikost preambule, což umožňuje vyšší propustnost sítě a snižuje pravděpodobnost vzniku kolize.

Obrázek 3.7: Přenos dat v protokolu RI-MAC [9] Přenos dat v protokolu RI-MAC je znázorněn na obrázku 3.7. Každý uzel se periodicky probouzí na základě svého vlastního plánu a všesměrovým vysíláním odesílá signalizační rámec, pomocí kterého informuje ostatní uzly o tom, že je probuzený a připravený přijímat datové pakety. Uzel S, který chce odeslat data uzlu R, zůstává probuzený a čeká na signalizační rámec od uzlu R. Po přijetí tohoto rámce může uzel S začít odesílat data uzlu R. Poté, co uzel R přijme data odeslaná uzlem S, odešle R ještě jeden signalizační rámec, který slouží jako potvrzení přenosu dat a také zároveň tímto rámcem informuje uzly o tom, že je připravený přijímat další data. Pokud žádný jiný uzel již nemá žádná data určená pro uzel R, může R přejít do režimu spánku. Vzhledem k tomu, že může dojít k situaci, kdy více uzlů najednou začne po přijetí signalizačního rámce odesílat svá data stejnému příjemci, může dojít ke vzniku kolize. Tento problém lze řešit pomocí pole BF (backoff window size), které je součástí signalizačního rámce. Pokud se uzel R probudí, odešle všem uzlům signalizační rámec bez pole BF. Uzly, 18


které chtějí tomuto uzlu odesílat data, tak mohou učinit ihned po přijetí signalizačního rámce. Pokud začne více uzlů odesílat data stejnému uzlu R a dojde ke kolizi, zvýší R hodnotu v poli BF a znovu odešle signalizační rámec. Každý uzel, který přijme tento rámec s vyplněnou hodnotou BF a který chce odeslat data uzlu R, počká náhodně dlouhou dobu odvozenou z hodnoty uvedené v poli BF. Pokud opět dojde ke kolizi, uzel R znovu zvýší hodnotu v poli BF. Pokud je překročena maximální povolená hodnota pro pole BF, přejde uzel R do režimu spánku. Kromě pole BF obsahuje každý signalizační rámec i pole Src, které obsahuje adresu uzlu odesílajícího tento rámec, a také může obsahovat pole Dst, které slouží pro adresaci cílových uzlů. Pokud dojde k situaci, kdy přijímající uzel R je již v aktivním stavu v době, kdy se probudí uzel S, který mu chce odeslat data, uzel S se nedozví, že R je aktivní a signalizační rámec již odeslal. Tuto situaci lze řešit tak, že uzel S po probuzení odešle signalizační rámec s vyplněným polem Dst obsahujícím adresu cílového uzlu (tedy uzlu R). Pokud je uzel R aktivní, odpoví na tento rámec odesláním vlastního rámce umožňujícího uzlu S zahájit přenos dat (viz obrázek 3.8).

Obrázek 3.8: Optimalizace protokolu RI-MAC pro situaci, kdy přijímající uzel R je již aktivní v době, kdy se probudí uzel S, který chce uzlu R odeslat data [9]

3.2.7

PW-MAC

Dalším asynchronním protokolem, ve kterém je komunikace iniciována přijímajícím uzlem, je protokol PW-MAC (Predictive-Wakeup MAC) [10]. Na rozdíl od protokolu RI-MAC, kde uzel, který chtěl odeslat data jinému uzlu, musel často dlouho čekat, dokud se příjemce neprobudil a neodeslal mu signalizační rámec, protokol PW-MAC umožňuje odesílajícím uzlům předvídat čas, kdy se příjemce probudí. Hlavním cílem při návrhu protokolu PW-MAC bylo, aby se odesílající uzel probudil těsně předtím, než se probudí uzel, kterému by chtěl poslat data. Každý uzel používá generátor pseudonáhodných čísel, pomocí nichž si vypočítá časy, kdy se probudí. Různé uzly 19


používají pro své generátory různé parametry, tudíž každý uzel si vypočítá jiné hodnoty a uzly v síti se tedy neprobouzí ve stejnou dobu, což vede ke snížení pravděpodobnosti vzniku kolizí. Díky tomu, že generovaná čísla jsou pseudonáhodná, může odesílající uzel, který zná parametry příjemce, předvídat, kdy se daný uzel probudí. Pokud nějaký uzel A chce odeslat data uzlu B a nezná dosud jeho parametry pro generátor pseudonáhodných čísel, počká, dokud mu B neodešle signalizační rámec (tímto rámcem uzel B oznamuje, že je připravený přijímat data). Poté, co uzel A přijme tento rámec, odešle datový paket, jehož součástí je i žádost o zaslání parametrů uzlu B (ve formě příznaku umístěného v hlavičce paketu). Po přijetí paketu uzel B odešle další signalizační rámec potvrzující přijetí paketu, jehož součástí jsou i parametry uzlu B, semínko pro generátor pseudonáhodných čísel a aktuální čas uzlu (ten slouží k výpočtu časové diference mezi hodinami uzlů A a B). Díky těmto informacím o uzlu B může uzel A již předvídat časy, kdy se uzel B příště probudí. Znalost časů, kdy se daný uzel probudí, také umožňuje efektivně řešit problém, kdy dojde k chybě při přenosu paketu a je nutné daný paket odeslat znovu. Pokud uzel A odešle datový paket uzlu B, ale nedostane už od uzlu B potvrzení o přijetí (ve formě signalizačního rámce odeslaného uzlem B), předpokládá, že došlo k chybě buď při přenosu datového paketu nebo při přenosu signalizačního rámce. V takovém případě přejde uzel A do režimu spánku, probudí se v době, kdy se má příště probudit uzel B, a znovu se pokusí odeslat datový paket. Pokud dojde ke kolizi díky tomu, že více uzlů ve stejné době odešle svá data stejnému příjemci, použije se pro řešení kolize stejný mechanismus, který používá protokol RI-MAC (tedy použije se pole BF, které je součástí signalizačního rámce). Vzhledem k tomu, že každý uzel má své vlastní hodiny, může být problém s přesností předvídání času, kdy se daný uzel probudí. Proto byla definována chyba předvídání (prediction error), která představuje rozdíl mezi skutečným časem probuzení a předvídaným časem probuzení uzlu. Odesílající uzel si udržuje parametr (tzv. sender wakeup advance time), který zohledňuje např. zpoždění operačního systému, hardwaru, odchylku hodin atd. Pokud odesílající uzel zjistí, že chyba předvídání je větší než hodnota tohoto parametru, požádá příjemce, aby mu znovu zaslal své parametry, semínko pro generátor pseudonáhodných čísel a informace o čase uzlu.

3.2.8

PMAC

Protokol PMAC (Pattern MAC) [11] je velmi podobný protokolu S-MAC. Oba dva protokoly používají časové díly s pevně danou velikostí, během nichž je uzel buď v režimu naslouchání, nebo v režimu spánku. Na rozdíl od protokolu S-MAC, kde se v uzlech tyto režimy periodicky střídají, u protokolu PMAC se střídat nemusí a uzel si plán přechodů do režimu naslouchání a spánku upravuje v závislosti na aktuálním provozu v síti. Každý uzel si sestavuje vzor (pattern), což je řetězec jedniček a nul udávající, kdy uzel předpokládá, že se bude nacházet v režimu naslouchání a kdy v režimu spánku. Bit 1 udává, že se bude nacházet v režimu naslouchání, bit 0, že bude v režimu spánku (tedy například řetězec 00001 znamená, že uzel bude ve čtyřech po sobě jdoucích časových dílech v režimu spánku, v pátém bude v režimu naslouchání). Tento vzor je vždy ve tvaru 0m 1 20


(m udává počet nul ve vzoru), přičemž hodnota m se může maximálně rovnat N − 1, kde N udává celkový počet časových dílů v rámci jedné periody. Pokud je délka vzoru kratší než délka této periody, potom se po zbývající dobu tento vzor opakuje. Vysoká hodnota m představuje nízkou zátěž sítě, nízká hodnota m naopak zátěž vysokou. Na počátku má každý uzel vzor s hodnotou 1. Pokud nemá žádná data, která by chtěl poslat jinému uzlu, nastaví si vzor na 01 a přejde do režimu spánku. Pokud ani po příštím probuzení (tedy po uplynutí jednoho časového dílu, kdy byl v režimu spánku) nemá stále žádná data, která by odeslal, zdvojnásobí počet nul ve vzoru (tedy vzor bude 001) a přejde znovu do režimu spánku (tentokrát na dobu odpovídající dvěma časovým dílům). Takto stále zdvojnásobuje počet nul ve vzoru (pokud nemá žádná data k odeslání), dokud jejich počet nedosáhne předem definované hranice δ. Poté již navyšuje počet nul lineárně (dokud počet nedosáhne hranice N − 1). Pokud uzel má nějaká data, která chce odeslat, pak hodnota příštího vzoru bude znovu 1. Jak již bylo uvedeno výše, tyto vzory udávají, kdy uzel pouze předpokládá, že bude v režimu naslouchání a kdy v režimu spánku. Skutečný plán (schedule) je odvozen z tohoto vzoru a ze vzorů, které si na konci periody vymění se svými sousedy. Na základě těchto informací si poté každý uzel sestaví optimální plán. Protokol PMAC dosahuje dobrých výsledků zejména v případě, kdy provoz v síti je stabilní. V prostředí, kde dochází k častým změnám zátěže v síti, může být adaptace na tyto změny pomalá.

3.3

Protokoly založené na plánu

Protokoly založené na plánu přidělují každému uzlu časový díl pro komunikaci. Během tohoto časového dílu má uzel zaručeno, že se v přenosovém médiu nenachází žádný jiný signál, který by mohl způsobit vznik kolize. To je zároveň největší výhodou těchto protokolů oproti protokolům založeným na soupeření, u kterých kolize vznikat mohou a které tedy vyžadují větší spotřebu energie pro případné opakované zasílání paketů. Na druhou stranu ale jednou z hlavních nevýhod protokolů založených na plánu je, že vyžadují velmi přesnou synchronizaci. Tento způsob, ve kterém je uzlům přidělována vždy na určitou dobu celá dostupná šířka pásma přenosového média, se nazývá časový multiplex (Time Division Multiple Access, TDMA).

3.3.1

LEACH

Protokol LEACH (Low-Energy Adaptive Clustering Hierarchy) [12] organizuje jednotlivé uzly v síti do několika skupin, přičemž v každé skupině (označované jako cluster) je jeden vedoucí uzel (označovaný jako cluster-head), který v podstatě plní roli lokální základnové stanice, řídí komunikaci v dané skupině a je zodpovědný za komunikaci se základnovou stanicí. Vzhledem k tomu, že tyto činnosti spotřebovávají velké množství energie, není vhodné, aby zvolený uzel plnil funkci vedoucího uzlu neustále. Proto je po určité době za vedoucí uzel zvolen uzel jiný. 21


Na počátku se každý uzel rozhodne, zda se stane vedoucím uzlem. Toto rozhodnutí provádí nezávisle na ostatních uzlech podle toho, kolik mu ještě zbývá energie. Během rozhodování se zohledňuje přibližný počet vedoucích uzlů, které by měly být v síti (toto číslo je známé předem a je vyjádřeno v procentech – např. 5 % uzlů v síti bude plnit funkci vedoucího uzlu), a počet, kolikrát již daný uzel plnil funkci vedoucího uzlu předtím. Toto rozhodování probíhá tak, že si uzel n zvolí náhodné číslo mezi nulou a jedničkou. Také si spočítá prahovou hodnotu T (n): ( P jestliže n ∈ G 1 , T (n) = 1−P ∗(r mod P ) 0 jinak kde P je požadované procento vedoucích uzlů v síti (např. P = 0, 05 při 5% zastoupení vedoucích uzlů v síti), r označuje číslo, které udává, o kolikátou volbu se jedná (jak již bylo uvedeno, uzel se stává vedoucím uzlem pouze na určitou dobu a poté je proces volby opakován) a G označuje množinu uzlů, které neplnily funkci vedoucího uzlu v posledních 1 volbách. Pokud je náhodné číslo, které si uzel n zvolil, menší než hodnota T (n), stane se p tento uzel vedoucím uzlem. Každý uzel, který se stane vedoucím uzlem, odešle všesměrovým vysíláním zprávu ostatním uzlům. Uzel, který tuto zprávu přijme (a sám se nestal vedoucím uzlem), se na základě síly přijatého signálu rozhodne, do které skupiny bude patřit, protože zpráva s nejsilnějším signálem pochází od vedoucího uzlu, se kterým bude následná komunikace nejméně energeticky náročná. Poté, co každý uzel provede rozhodnutí, odešle zprávu příslušnému vedoucímu uzlu, čímž ho informuje o tom, že by chtěl být součástí jím spravované skupiny. Vedoucí uzel přijme zprávy od všech uzlů, které chtějí být součástí této skupiny, a na základě počtu uzlů sestaví plán, který každému uzlu přidělí určitý časový díl, ve kterém může daný uzel vysílat, a tento plán uzlům odešle. Každý uzel ve skupině může odesílat data vedoucímu uzlu pouze během přiděleného časového dílu. Díky tomu může uzel šetřit energii tím, že až do začátku tohoto časového dílu bude v režimu spánku. Poté, co vedoucí uzel přijme data od jednotlivých uzlů ve skupině, zkomprimuje je do jediného signálu, který odešle základnové stanici. Jedním z problémů, který je nutné řešit, je, že komunikace v jedné skupině může ovlivňovat komunikaci ve skupině, která se nachází poblíž. Aby tato interference mezi jednotlivými skupinami byla co nejmenší, používá se pro komunikaci v rámci každé skupiny tzv. kódový multiplex (Code Division Multiple Access, CDMA). Každé skupině je přiřazen unikátní kód, pomocí kterého všechny uzly kódují data odesílaná příslušnému vedoucímu uzlu. Vedoucí uzel potom filtruje veškeré přijaté zprávy na základě daného kódu, přičemž vysílání uzlů z jiných skupin chápe jako šum.

3.3.2

SMACS

Na rozdíl od protokolu LEACH, který uspořádává uzly do hierarchické struktury, protokol SMACS (Self-Organizing Medium Access Control for Sensor Networks) [13] pracuje s plochou topologií. Jednotlivé uzly v síti si samy vytváří mezi sebou přímá spojení bez 22


pomoci nějakého nadřazeného uzlu. Tato spojení se mezi uzly vytváří tak dlouho, dokud v síti neexistuje alespoň jedna cesta mezi každými dvěma různými uzly.

Obrázek 3.9: Vytváření spojení mezi uzly v protokolu SMACS [13] Na obrázku 3.9 je znázorněno, jakým způsobem probíhá vytváření spojení mezi dvěma uzly. Uzel A se probudí v čase Ta , uzel D v čase Td . Pokud se tyto dva uzly rozhodnou mezi sebou vytvořit spojení, dohodnou se spolu na dvojici časových dílů, které budou používat pro vzájemnou komunikaci (jeden díl bude sloužit pro odesílání dat, druhý pro přijímání). Tyto časové údaje si každý uzel uloží do tzv. superrámce (super frame), jehož délka je Tf rame , přičemž po uplynutí doby Tf rame se posloupnost časových dílů uvedená v superrámci periodicky opakuje (proto je nutné, aby velikost superrámce byla pro všechny uzly pevně daná). Stejným způsobem si poté mezi sebou vytvoří spojení uzly B a C. Vzhledem k tomu, že uvedený mechanismus by mohl vést ke vzniku kolizí, používá každá dvojice uzlů jiné frekvenční pásmo (uzly A a D používají pro komunikaci frekvenční pásmo fx , uzly B a C frekvenční pásmo fy ). Používaná frekvenčního pásma jsou zvolena náhodně, a je tedy malá pravděpodobnost, že by pro dvě různá spojení, která jsou v dosahu, byla zvolena stejná frekvenční pásma. Každý uzel si tím, že objevuje nové sousedy, postupně doplňuje svůj superrámec. V době, kdy uzel nemá v superrámci naplánovanou komunikaci s žádným jiným uzlem, může přejít do režimu spánku. Předtím, než spolu dva různé uzly mohou vytvořit nové spojení, musí se nejdříve nějakým způsobem dozvědět o své existenci. To je řešeno tak, že každý uzel po určitou náhodně dlouhou dobu po probuzení poslouchá na přenosovém médiu, zda nějaký jiný uzel neodeslal zprávu s výzvou o navázání spojení. Pokud se tak nestane, po uplynutí této doby sám odešle všesměrovým vysíláním zprávu s touto výzvou a čeká na odpovědi od uzlů, které by s ním chtěly navázat spojení. Ze všech odpovědí, které přijme, si vybere právě jeden uzel 23


(např. ten, jehož odpověď mu přišla nejdříve, nebo ten, ke kterému je již připojeno nejvíce uzlů) a odešle zprávu, ve které uzly informuje, kterého z nich si vybral. Součástí této zprávy jsou i informace uvedené v jeho superrámci a také čas příštího začátku superrámce. Tyto informace použije vybraný uzel k tomu, aby na základě svého a přijatého superrámce vybral dvojici časových dílů pro komunikaci, a spolu s náhodně vybraným frekvenčním pásmem tyto informace pošle zpátky uzlu, se kterým vytváří spojení.

3.3.3

TRAMA

Dalším protokolem patřícím mezi protokoly založené na plánu je protokol TRAMA (TrafficAdaptive Medium Access) [14]. Tento protokol se skládá ze tří komponent – Neighbor Protocol (NP), Schedule Exchange Protocol (SEP) a Adaptive Election Algorithm (AEA). Cílem protokolu NP je zmapování nejbližšího okolí každého uzlu. Každý uzel odesílá svým sousedům signalizační pakety, jejichž součástí jsou informace o jeho sousedech (tedy o uzlech, které jsou od něj ve vzdálenosti jeden hop). Díky tomu získá každý uzel informaci o tom, které uzly jsou od něj ve vzdálenosti dvou hopů. Při odesílání těchto signalizačních paketů spolu uzly soupeří za účelem získání přístupu k přenosovému médiu, tudíž může dojít ke ztrátě paketů z důvodu kolize. Proto je nutné vhodně zvolit délku doby, během které budou vysílány signalizační pakety, tak, aby získané informace o topologii sítě byly co nejpřesnější. Protokol SEP slouží k výměně informací mezi sousedy o plánovaném přenosu dat. Každý uzel informuje své sousedy o tom, komu chce odeslat nějaká data, tím, že jim zašle svůj plán, který se skládá z časových dílů a který si uzel sám vypočítal. Vytváření takového plánu probíhá tak, že si uzel nejdříve vypočítá číslo (označované jako SCHEDULE_INTERVAL), které představuje počet časových dílů, během kterých uzel bude moci informovat své sousedy o svém plánu (např. 100 dílů). Poté v nějakém čase t si pro všechny časové díly z intervalu [t, t + SCHEDULE_INTERVAL] vypočítá svoji prioritu a prioritu uzlů ve vzdálenosti dvou hopů. Pokud tedy např. SCHEDULE_INTERVAL je roven 100 a čas t je 500, potom bude počítat priority pro časové díly v intervalu [500, 600]. Pro výpočet priority každého uzlu pro daný časový díl se použije následující hašovací funkce: p(x, t) = h(x ⊕ t), kde h je hašovací funkce, x je identifikátor uzlu, t je časový díl a x ⊕ t je spojením identifikátoru x a časového dílu t. Časové díly, ve kterých má uzel nejvyšší prioritu (tzv. vítězné díly), může tento uzel použít pro přenos paketů a o zamýšleném přenosu informuje příslušné příjemce těchto paketů. Pokud uzel získal více vítězných dílů, než kolik potřebuje pro přenos paketů, může se některých dílů vzdát ve prospěch jiných uzlů. Poslední vítězný díl je vždy rezervován pro odeslání příštího plánu uzlu. Úkolem AEA je vybrat, které časové díly budou použity pro odesílání a které pro přijímání paketů. V každém časovém dílu je provedeno rozhodnutí (na základě výsledku hašovací funkce uvedené výše) o tom, ve kterém z následujících tří stavů se určitý uzel bude nacházet: 24


• stav odesílání (transmit, TX) – pokud má uzel nejvyšší prioritu a chce odeslat nějaká data, • stav přijímání (receive, RX) – pokud uzel není ve stavu TX a existuje nějaký jiný uzel, který je ve stavu TX a který mu chce odeslat data (tuto informaci zjistí z plánu, který od něj získal), • stav spánku (sleep, SL) – uzel se nebude účastnit žádného přenosu dat (není ve stavu TX a ani mu žádný uzel nechce odeslat data) a může tedy přejít do režimu spánku. Toto rozdělení, kdy se každý uzel v každém časovém dílu nachází v právě jednom z uvedených tří stavů, umožňuje uzlům odesílat data bez rizika vzniku kolize.

3.3.4

PEDAMACS

Senzorové sítě, které používají protokol PEDAMACS (Power-Efficient and Delay-Aware Medium Access) [15], se skládají z několika senzorových uzlů a z jednoho hlavního uzlu označovaného jako přístupový bod (access point, AP), pro který platí, že všechny senzorové uzly v síti se nachází v jeho dosahu (tedy všechny jsou od něj ve vzdálenosti jeden hop). Senzorové uzly ale mohou potřebovat více než jeden hop k dosažení AP. V takovéto senzorové síti se používají tři různé úrovně síly signálu – signál s nejdelším dosahem (Pl ), s nejkratším dosahem (Ps ) a se středním dosahem (Pm ). Protokol PEDAMACS pracuje ve třech fázích. Během první fáze (fáze zjišťování topologie) vysílá AP všesměrovým vysíláním (pomocí Pl ) paket, pomocí kterého se všechny uzly v síti synchronizují. Poté odešle AP další paket (tentokrát pomocí Pm ), jehož účelem je vybudování stromové topologie v síti. Tento paket v sobě nese informaci o počtu hopů, přičemž každý uzel, který jej přijme, zvýší hodnotu počtu hopů o jedničku a přepošle jej dál (formou záplavy). Tímto se vytvoří v síti stromová struktura, ve které každý uzel identifikuje své sousedy (uzly, kterým odeslal paket pomocí Ps a které byly schopny jej dekódovat), identifikuje potenciální zdroje rušení (uzly, které nebyly schopny dekódovat paket odeslaný pomocí Ps , ale přijatý signál byl dostatečně silný na to, aby mohl rušit jiné signály) a zvolí si svého rodiče (uzel s nejnižším počtem hopů k AP). Pro přístup k přenosovému médiu se v této fázi používá protokol CSMA (tedy uzly soupeří o přístup k přenosovému médiu). Ve druhé fázi (fáze získání topologie) vysílá AP všesměrovým vysíláním paket, na který všechny uzly odpoví odesláním lokální topologie, kterou si vytvořily v první fázi. Tato topologie je tvořena rodičem uzlu, jeho sousedy a uzly, které mohou způsobovat rušení signálu. I ve druhé fázi je pro přenos paketů používán protokol CSMA. Na začátku třetí fáze (fáze plánování) vytvoří AP na základě informací získaných ve druhé fázi plán, ve kterém jednotlivým uzlům přiděluje časové díly, ve kterých budou moci odesílat nebo přijímat data, a odešle paket obsahující tento plán všem uzlům. Jednotlivé uzly potom mohou v přidělených časových dílech odesílat nebo přijímat data, v ostatních dílech mohou být v režimu spánku. Protokol PEDAMACS může být vhodné použít pro periodické odesílání dat nebo pro událostmi řízené senzorové sítě, kde se přidělený časový díl použije pro odeslání dat pouze 25


v případě, pokud v daném prostředí nastala určitá událost (v opačném případě může uzel zůstat v režimu spánku). Nevýhodou protokolu PEDAMACS může být, že AP spotřebovává velké množství energie, a tedy jeho nasazení v určitých prostředích nemusí být možné.

3.3.5

DMAC

Protokol DMAC (Data-Gathering MAC) [16] je protokolem, který je založený na vytváření plánu, který určuje, kdy určitá skupina uzlů může přistupovat k přenosovému médiu. Tato skupina uzlů poté přistupuje k médiu pomocí mechanismů založených na vzájemném soupeření, proto zařazení protokolu DMAC do jedné ze dvou uvedených skupin MAC protokolů (protokoly založené na soupeření, protokoly založené na plánu) není úplně jednoznačné a DMAC se nachází spíše na pomezí těchto dvou skupin.

Obrázek 3.10: Stromová struktura používaná v protokolu DMAC, ve které se uzly na stejné úrovni stromu nachází buď ve stavu přijímání (RX), odesílání (TX) nebo ve stavu spánku [16] Jednotlivé uzly v síti jsou vzájemně propojeny tak, že vytváří stromovou strukturu (tzv. data gathering tree). Všechny uzly potom odesílají datové pakety vždy svému rodiči, který tyto pakety přepošle dále směrem ke kořenu stromu (tento kořenový uzel shromažďuje datové pakety od všech uzlů v síti). Na obrázku 3.10 je znázorněno, jakým způsobem přenos těchto paketů probíhá. Uzly v síti se vždy nachází v jednom z následujících stavů, které se periodicky opakují – stav přijímání, stav odesílání a stav spánku, přičemž pro všechny uzly, které se ve stromu nachází na stejné úrovni, platí, že se v těchto stavech nachází vždy ve stejné době (tedy například pokud je uzel na třetí úrovni stromu právě ve stavu odesílání, potom jsou i všechny ostatní uzly na třetí úrovni ve stavu odesílání). Přenos datových paketů probíhá tak, že ve stavu přijímání uzel přijímá datový paket od svého potomka a po jeho obdržení mu zpět odešle potvrzení o doručení (ACK). Poté přejde uzel do stavu odesílání, ve kterém odešle paket svému rodiči a čeká na přijetí potvrzení. Tento stav trvá stejně dlouhou dobu jako stav přijímání (tato doba je dostatečně dlouhá pro odeslání jednoho paketu). Po uplynutí této doby přejde uzel do stavu spánku, přičemž po 26


uplynutí určité doby uzel znovu přejde do režimu přijímání. Platí tedy, že pokud se uzly na úrovni n nachází ve stavu odesílání, potom se všechny uzly na úrovni n − 1 v této době nachází ve stavu přijímání. Vzhledem k tomu, že uzly nacházející se na stejné úrovni stromu odesílají pakety ve stejné době, může dojít ke vzniku kolize. Proto se používají potvrzující pakety. Pokud uzel, který odešle datový paket svému rodiči, nedostane potvrzení o přijetí, uloží si datový paket do fronty a pokusí se jej odeslat znovu, až se příště dostane do stavu odesílání. Po určitém počtu neúspěšných pokusů o odeslání tohoto paketu (obvykle po třech) je datový paket zahozen. Pro snížení pravděpodobnosti vzniku kolize navíc uzel odesílající datový paket před jeho odesláním vždy čeká náhodně dlouhou dobu. Jak již bylo uvedeno, doba trvání stavu přijímání (odesílání) je dostatečně dlouhá pro přijetí (odeslání) jednoho paketu. Pokud nějaký uzel chce odeslat více paketů (například pokud došlo ke kolizi a uzel si paket, jehož přijetí nebylo potvrzeno, uloží do fronty), může požádat ostatní uzly nacházející se na cestě ke kořenu stromu o další časový díl, který by mu umožnil odeslat další paket (a zároveň požádá tyto uzly, aby si také přidaly další časový díl). To je provedeno tak, že uzel, který chce odeslat více paketů, nastaví v hlavičce odesílaného paketu speciální příznak. Uzel, který přijme paket s tímto nastaveným příznakem, nastaví tento příznak i v hlavičce paketu ACK, který odešle jako potvrzení zpátky, a přijatý paket odešle (i s nastaveným příznakem) svému rodiči. Uzel se rozhodne přidat si další časové díly (pro přijímání a odesílání paketů), pokud odešle datový paket s nastaveným příznakem a později přijme paket ACK s tímto nastaveným příznakem nebo pokud uzel přijme datový paket s nastaveným příznakem. Pokud více potomků chce ve stavu odesílání odeslat paket svému společnému rodiči A, potom je zřejmé, že přístup k přenosovému médiu v tomto časovém dílu získá pouze jeden z nich, protože délka doby přijímání uzlu A je velmi krátká a stačí pouze pro přijetí jednoho paketu. Ostatní potomci již tedy nemohou v tomto časovém dílu odeslat svému rodiči pakety, protože uzel A po přijetí paketu od vítězného uzlu a po uplynutí doby, kdy se nachází ve stavu odesílání, přejde do stavu spánku, pokud od žádného uzlu nepřijal paket s nastaveným příznakem (používaným pro informování uzlů o tom, že daný uzel chce odeslat více paketů) v hlavičce. Tento problém je řešen tak, že uzel A předpokládá, že mu více potomků chtělo odeslat své pakety, a proto se po určité době od přechodu do stavu spánku probudí (délka této doby je 3 ∗ d, kde d je doba, po kterou se uzel nachází ve stavu přijímání, resp. ve stavu odesílání). Pokud v této době nepřijme žádný další paket od některého ze svých potomků (tito potomci se rovněž v této době probudí, pokud chtějí uzlu A odeslat nějaké pakety), přejde opět do stavu spánku. Podobný problém může nastat v případě, kdy dva uzly, které jsou ve vzájemném dosahu, chtějí ve stejnou chvíli odeslat pakety svým (různým) rodičům. Tento problém lze řešit pomocí krátkého paketu MTS (More-To-Send). Uzel odešle svému rodiči paket MTS s příznakem nastaveným na 1 (tzv. request MTS, RMTS), pokud nemůže odeslat svůj paket, protože je kanál obsazený (tedy přístup k médiu získal jiný uzel) nebo pokud přijal paket RMTS od svého potomka. Pokud je vyrovnávací paměť uzlu prázdná (tedy uzel nechce odeslat žádný další paket), potom odešle svému rodiči paket MTS s příznakem nastaveným na 0 (tzv. clear MTS, CMTS). Paket CMTS ale uzel může odeslat pouze 27


v případě, pokud předtím odeslal svému rodiči paket RMTS a pokud od všech svých potomků, od kterých přijal paket RMST, přijal poté již také paket CMTS. Uzel, který odešle nebo přijme paket RMTS, se poté periodicky probouzí (vždy po uplynutí doby délky 3 ∗ d) až do doby, kdy odešle (příp. přijme od všech svých potomků, kteří odeslali paket RMTS) paket CMTS. Hlavními výhodami protokolu DMAC je, že dosahuje velmi nízké latence a díky tomu, že uzly jsou v aktivním stavu pouze velmi krátkou dobu, není energeticky příliš náročný. Na druhou stranu ale neposkytuje příliš silné metody pro vyhýbání se kolizím (v případě, kdy se více uzlů na stejné úrovni stromu pokusí odeslat paket ve stejnou dobu stejnému uzlu) a umožňuje přenos datových paketů pouze jedním směrem (ke kořenu stromu). Protokol DMAC může být vhodné použít v senzorových sítích, kde jsou přenosové rychlosti a cesty předem známé a v čase se příliš nemění.

28

Kapitola 4 Směrovací protokoly 4.1

Klasifikace směrovacích protokolů

Třetí vrstvou modelu ISO/OSI je síťová vrstva. Mezi hlavní úkoly této vrstvy patří například logické propojování samostatných heterogenních fyzických sítí (tak, aby vyšším vrstvám poskytovala iluzi jedné velké sítě), mapování fyzických a síťových adres, vytváření paketů ze segmentů přijatých z transportní vrstvy, adresování jednotlivých uzlů v síti pomocí síťových adres a směrování paketů (tedy proces nalezení cesty mezi uzly, které spolu komunikují). V této kapitole jsou popsány protokoly, které se používají v bezdrátových senzorových sítích pro směrování paketů (tzv. směrovací protokoly). Na rozdíl od MAC protokolů, jejichž hlavním úkolem je specifikovat, kdy daný uzel může odesílat pakety, směrovací protokoly specifikují, komu by měl uzel odeslat paket. Existuje mnoho způsobů, jak lze směrovací protokoly klasifikovat. Jedním z nich je rozdělení protokolů na proaktivní a reaktivní. Proaktivní protokoly jsou založené na periodické výměně informací o topologii sítě mezi uzly. Uzly si tedy mohou spočítat vzdálenosti k jiným uzlům a tyto informace si pamatují a na jejich základě odesílají pakety. Díky tomu lze dosáhnout nižší latence, nicméně je zapotřebí vyšší režie pro udržování stavu topologie (a s tím i spojená vyšší spotřeba energie uzlů). Reaktivní protokoly si informace o stavu sítě periodicky nevyměňují. Uzly začnou hledat cestu k určitému uzlu až v okamžiku, kdy tomuto uzlu chtějí odeslat paket. Tyto protokoly více šetří energii uzlů, na druhou stranu ale dosahují vyšší latence. Směrovací protokoly lze také rozdělit na tabulkami řízené protokoly (table-driven), kde každý uzel přepošle paket některému ze svých sousedů na základě svých tabulek (tedy stará se pouze o výběr sousedů, kterým by paket měl odeslat), a protokoly založené na zdrojovém uzlu (source-based), kde je součástí přenášeného paketu i jeho kompletní cesta k cílovému uzlu (tuto cestu určí zdrojový uzel). Tyto protokoly ale mají vyšší režii než tabulkami řízené protokoly. Dále lze směrovací protokoly například rozdělit podle struktury sítě do následujících tří skupin [17]:

29

KAPITOLA 4. SMĚROVACÍ PROTOKOLY

• protokoly pro ploché směrování – všechny uzly jsou si rovny a pro směrování používají stejné algoritmy, • hierarchické protokoly – některé uzly jsou nadřazené jiným uzlům, plní více úkolů a používají složitější algoritmy, • protokoly založené na umístění uzlů – uzly jsou adresovány na základě jejich umístění (k určení jejich polohy lze např. použít GPS). Poslední uvedená klasifikace je používána v následující části práce popisující významné protokoly používané pro směrování v bezdrátových senzorových sítích, přestože zařazení některých protokolů do jedné z těchto skupin nemusí být vždy úplně jednoznačné. Pro směrování v těchto sítích lze použít i mnoho protokolů, které byly navrženy pro bezdrátové ad hoc sítě, nicméně ty zde často nejsou příliš efektivní (například kvůli tomu, že byly navrženy pro sítě, ve kterých není třeba řešit omezenou životnost uzlů). V následující části práce jsou tedy popisovány protokoly, které byly navrženy přímo pro bezdrátové senzorové sítě nebo které byly navrženy pro bezdrátové ad hoc sítě, ale lze je efektivně používat i v bezdrátových senzorových sítích.

4.2

Protokoly pro ploché směrování

Jak již bylo uvedeno, v sítích používajících tyto protokoly si jsou všechny uzly rovny a vzájemně spolupracují. To může vést k výraznému zvýšení režie potřebné pro směrování v případě zvyšování počtu uzlů v síti. Na druhou stranu ale výhodou těchto směrovacích protokolů je, že mohou být relativně jednoduché. Nejjednoduššími způsoby pro přenášení informací v bezdrátových senzorových sítích je použití záplavy nebo výběru náhodného souseda (gossiping) [17]. Záplava funguje tak, že každý uzel, který přijme nějaká data, odešle tato data všem svým sousedům a tento proces pokračuje tak dlouho, dokud není nalezen cílový uzel nebo dokud není vyčerpán maximální počet hopů uvedený v hlavičce paketu (každý uzel, který tento paket přijme, sníží hodnotu počtu hopů uvedenou v hlavičce paketu o jedničku). Implementace záplavy je jednoduchá, ale zároveň má tato technika i mnoho nedostatků. Mezi ně patří například zahlcení senzorových uzlů (způsobené přijímáním stejných zpráv vícekrát od okolních sousedů), plýtvání šířkou pásma atd. Gossiping funguje podobným způsobem. Uzel, který přijme nějaká data, tato data odešle náhodně vybranému sousedovi, který tato data také přepošle svému náhodně vybranému sousedovi. Výhodou tohoto způsobu je také jednoduchá implementace. Navíc zabraňuje přijímání stejných zpráv vícekrát. Nevýhodou ale je velké zpoždění při přenosu dat a také to, že není zaručeno, že odeslaná zpráva bude zaslána všem uzlům v síti.

4.2.1

SPIN

SPIN (Sensor Protocols for Information via Negotiation) [18] je označení pro několik protokolů, které se používají pro směrování v bezdrátových senzorových sítích. Tyto protokoly 30


jsou založené na tom, že si uzly vzájemně vyměňují informace o tom, která data mají a která by chtěly od jiných uzlů získat. Vzhledem k tomu, že uzly, které se nachází v daném prostředí blízko sebe, drží obvykle podobná data, není nutné, aby si vyměňovaly všechna svá data, ale stačí, pokud uzel odešle jinému uzlu pouze ta data, která tento přijímající uzel dosud nevlastní. Proto jednotlivé uzly používají tzv. metadata, která popisují jimi držená data, a pomocí těchto metadat informují ostatní uzly o tom, jaká data vlastní. Tato metadata mají menší velikost než data, která popisují, proto je jejich přenos v síti (za účelem informování ostatních uzlů o tom, jaká data uzel vlastní), výhodnější než přenos samotných dat. Formát těchto metadat musí být navíc navržený tak, aby dva uzly, které drží stejná data, tato data popisovaly stejnými metadaty. SPIN používá následující tři typy paketů pro výměnu dat mezi uzly: • ADV – pomocí tohoto paketu uzel oznamuje ostatním uzlům, jaká data vlastní, • REQ – tento paket odesílají uzly, které žádají určitý uzel o nějaká data, • DATA – paket obsahující určitá data senzorového uzlu. Jak již bylo uvedeno, SPIN zahrnuje více protokolů, mezi které patří: • SPIN-PP, • SPIN-EC, • SPIN-BC, • SPIN-RL. Protokol SPIN-PP je navržený pro tzv. point-to-point komunikaci, tedy komunikaci, kdy spolu dva uzly komunikují, aniž by byly rušeny jinými uzly. Na obrázku 4.1 je znázorněno, jak probíhá přenos dat pomocí protokolu SPIN-PP. Uzel A, který získá nějaká data, která by chtěl šířit dál, odešle svým sousedům paket ADV. Tento paket obsahuje metadata popisující data uzlu. Uzly, které tento paket přijmou (v tomto případě pouze uzel B), na něj odpoví pomocí paketu REQ adresovaného uzlu A (nejdříve ale zjistí, zda již daná data nevlastní nebo o ně již nepožádaly dříve). Po přijetí paketu REQ odešle uzel A, který data vlastní, paket DATA, který již obsahuje požadovaná data (tento paket odešle pouze uzlu, od kterého přijal paket REQ, tedy uzlu B). Poté uzel B odešle všem svým sousedům paket ADV, který obsahuje metadata popisují data, která uzel B získal od uzlu A. Všechny uzly, které tato data dosud nevlastní (ani o ně dosud nepožádaly) odpoví na tento paket pomocí paketu REQ. Uzel B poté odešle každému uzlu, od kterého přijme paket REQ, paket DATA obsahující požadovaná data.

31


Obrázek 4.1: Přenos dat pomocí protokolu SPIN-PP [18] Protokol SPIN-EC je rozšířením protokolu SPIN-PP. Protokol SPIN-EC pracuje stejným způsobem jako protokol SPIN-PP, každý uzel má ale navíc definovanou určitou prahovou hodnotu. Pokud má uzel dostatek energie, používá stejný mechanismus, jaký používá protokol SPIN-PP. Pokud se ale energie uzlu začne blížit této prahové hodnotě, uzel svoji činnost omezí. Pokud přijme paket ADV, zjistí (pomocí různých heuristik), zda má dostatek energie na to, aby odeslal paket REQ a poté ještě přijal data. Pokud zjistí, že by po provedení těchto kroků klesla energie uzlu pod prahovou hodnotu, nebude paket REQ odesílat. Podobně uzel postupuje v případě, pokud získá nová data. Zjistí, zda má dostatek energie pro odeslání paketu ADV, přijetí paketu REQ od svých sousedů a následné odeslání dat. Pokud by energie uzlu měla klesnout pod prahovou hodnotu, nebude paket ADV odesílat. Protokol SPIN-BC je podobný protokolu SPIN-PP, ale na rozdíl od něj uzel neodesílá paket jednomu konkrétnímu uzlu (tedy komunikace již není point-to-point), ale všechny pakety jsou vždy odesílány všem uzlům, které se nachází v dosahu. Výhodou tohoto protokolu je, že odesílající uzel může paket odeslat jen jednou, i když je určen pro více uzlů. To lze využít například v případě, kdy nějaký uzel A oznámí pomocí paketu ADV, že vlastní nějaká data, a alespoň dva uzly tato data chtějí. Uzlu A tedy stačí, aby přijal pouze jednu žádost (paket REQ) o zaslání dat, protože tato data budou odeslána všesměrovým vysíláním. Je tedy zřejmé, že pokud uzel A přijme více než jednu žádost, jsou tyto ostatní žádosti již nadbytečné (a uzel na ně již nebude nijak reagovat). Uzel, který má o data uzlu A zájem, tedy odešle žádost ve formě paketu REQ (rovněž pomocí všesměrového vysílání všem uzlům v dosahu) a všechny uzly, které tuto žádost přijmou a také mají zájem o stejná data, již svoji žádost odesílat nemusí. Na druhou stranu ale tímto může docházet k větší spotřebě energie uzlů, které jsou v dosahu a musí takové pakety přijmout, přestože 32


se dané komunikace nechtějí účastnit. Posledním uvedeným protokolem je SPIN-RL, který je rozšířením protokolu SPIN-BC a zaměřuje se na spolehlivý přenos dat. Pokud uzel odešle žádost o nějaká data (jako odpověď na paket ADV) a pokud požadovaná data nepřijme do určité doby, odešle žádost znovu. Nemusí ji ale odeslat stejnému uzlu, ale libovolnému ze svých sousedů, které oznámily, že tato data mají. Druhý rozdíl oproti protokolu SPIN-BC je v tom, že pokud uzel odešle data (paket DATA), počká určitou dobu, než bude moci znovu tato data odeslat (pokud by přijal další žádost o tato data).

4.2.2

Directed diffusion

Dalším způsobem, jak lze řešit směrování v bezdrátových senzorových sítích, je použití paradigmatu nazvaného directed diffusion [19]. Všechna data vytvářená uzly a také žádosti o tato data jsou popsány pomocí dvojic tvořených atributy a jejich hodnotami. Těmito atributy mohou být například jméno objektu, který je v daném prostředí sledován, interval vysílání, trvání vysílání, vymezení určité geografické oblasti atd. Jednotlivé atributy používané v prostředí, ve kterém je cílem monitorování zvířat, mohou vypadat následujícím způsobem [19]: type = four-legged animal interval = 10 ms duration = 10 s rect = [-100, 100, 200, 400]

// // // // //

detekuj pozici zvířete pošli data každých 10 ms ... po dobu 10 sekund ... z uzlů nacházejících se uvnitř čtyřúhelníku s těmito souřadnicemi

Jeden z hlavních rozdílů oproti protokolu SPIN je v tom, že zatímco v síti používající protokol SPIN uzly oznamují ostatním uzlům, že vlastní nějaká data, v síti používající directed diffusion je síť zaplavována žádostmi o určitá specifická data. Pokud některý uzel v síti chce získat nějaká data držená jinými uzly, odešle žádost se zájmem o tato data (tzv. interest). Tato zpráva obsahuje výše uvedené dvojice atributů a hodnot, pomocí nichž uzel specifikuje, o jaká data má zájem. Tato zpráva je přenášena sítí, přičemž každý uzel ji přeposílá svým sousedům. Uzly si uchovávají záznamy o přijatých zprávách, přičemž ke každé takové zprávě si vytvoří právě jeden záznam. Tyto záznamy obsahují kromě informací o dané zprávě také gradienty. Tyto gradienty slouží zejména k uchování informace o tom, od kterého uzlu byla zpráva přijata, ale také informace o rychlosti přenosu dat, době trvání přenosu zprávy a době vypršení platnosti zprávy (tyto informace uzel zjistí z přijaté zprávy). Získané informace lze využít pro ustavení cesty mezi uzlem, který zprávu odeslal, a uzlem, který vlastní hledaná data. Těchto cest navíc může být ustaveno několik. Uzel, který vlastní hledaná data a přijme zprávu s žádostí o tato data, začne tato data odesílat, přičemž k tomu může využít více vytvořených cest. Uzel, který o tato data má zájem (tedy uzel, který původně odeslal zprávu s žádostí o tato data), poté, co začne tato data přijímat, vybere jednu z těchto cest a informuje svého souseda, který se na této nové 33


cestě bude nacházet. To může provést tak, že tomuto sousednímu uzlu znovu odešle žádost se zájmem o data, ale tentokrát tato žádost bude obsahovat požadavek na vyšší přenosovou rychlost (tedy uzel vlastnící data bude po nově ustavené cestě posílat data vyšší rychlostí). Tento sousední uzel dále přepošle tuto zprávu vybranému sousedovi. Tímto způsobem se vytvoří celá cesta. Pokud by došlo k výpadku na této cestě, tak se podobným způsobem může vytvořit cesta nová, protože uzly mají uložené záznamy o přenášených zprávách.

Obrázek 4.2: Přenos dat pomocí directed diffusion [19] Directed diffusion není vhodné používat pro jednorázové dotazy, protože je zbytečné vytvářet gradienty pro dotazy, které použijí určitou cestu jen jednou. Na druhou stranu ale v prostředí, kde dotazy jednorázové nejsou, může uchovávání informací o zprávách výrazně snižovat energetickou náročnost.

4.2.3

Rumor routing

Rumor routing [20] je dalším způsobem používaným pro směrování v bezdrátových senzorových sítích. Jeho základní myšlenkou je vytvoření cesty v síti ke každé události. To je řešeno tak, že každý uzel si udržuje seznam svých sousedů a tabulku událostí obsahující informace o cestách ke všem událostem, o kterých ví. Pokud uzel detekuje nějakou událost, přidá si informace o ní do své tabulky událostí a vygeneruje paket, který se nazývá agent. Tento agent obsahuje informace o dané události a je šířen sítí za účelem informování vzdálených uzlů o této události. Uzel, který agenta přijme, si uloží informace o události do své tabulky událostí a agenta odešle některému ze svých sousedů. Agent navíc obsahuje také informaci o počtu hopů, přičemž pokud nějaký uzel, který přijme agenta, zjistí, že počet hopů již byl vyčerpán, tak jej již nebude odesílat (pokud vyčerpán nebyl, tak sníží hodnotu počtu hopů o jedničku a agenta odešle některému svému sousedovi). Agent si také udržuje seznam nedávno navštívených uzlů, aby bylo možné zabránit navštívení některého uzlu vícekrát. Díky tomu se v síti vytváří cesta, která vede k uzlu, který detekoval událost a agenta vygeneroval. Pokud některý uzel již má nějaké záznamy ve své tabulce událostí a přijme agenta, který jej informuje o události jiné, přidá si tuto informaci do své tabulky událostí. Zároveň ale i agent si doplňuje informace o jiných událostech, o kterých se dozví

34


z tabulek událostí uzlů, které jej přijmou, a dále tedy šíří informace o všech událostech, o nichž se na své cestě dozvěděl.

Obrázek 4.3: Šíření paketu (agenta) informujícího uzly v síti o výskytu nějaké události [20] Pokud nějaký uzel A chce získat data od uzlu, který detekoval určitou událost, odešle mu dotaz. Pokud má uzel A ve své tabulce událostí informace o této události (tyto informace by získal od agenta), odešle dotaz po této již známé cestě. Pokud v tabulce událostí žádnou informaci nemá, nastaví u dotazu maximální počet hopů a odešle jej náhodně vybranému sousedovi. Ten sníží hodnotu počtu hopů o jedničku a odešle jej svému sousedovi. Takto je dotaz šířen v síti, dokud není vyčerpán počet hopů nebo dokud dotaz nepřijme uzel, který má ve své tabulce událostí informace o této hledané události. Pokud takový uzel přijme dotaz, tak jej odešle po příslušné cestě na základě své tabulky událostí. Pokud ale takový uzel není nalezen a dříve dojde k vyčerpání počtu hopů (a tedy uzel vlastnící hledaná data nebude nalezen), může na to uzel, který původně odeslal dotaz, zareagovat více způsoby. Buď již nebude nic znovu odesílat, nebo se může pokusit odeslat dotaz znovu, nebo může rozeslat dotaz vícekrát pomocí záplavy. Rumor routing je vhodné používat pouze v sítích, ve kterých je počet událostí nízký.

35


4.2.4

GBR

Dalším způsobem směrování je směrování založené na gradientech (gradient-based routing, GBR). GBR [21] je velmi podobné directed diffusion. Uzel, který má zájem o určitá data, odešle zprávu (tzv. interest) a jednotlivé uzly v síti si udržují gradienty. Tato odeslaná zpráva si během svého šíření v síti zaznamenává informaci o počtu hopů. Uzel, který ji přijme, zjistí aktuální počet hopů a toto číslo je dále považováno za tzv. výšku uzlu (tedy udává vzdálenost tohoto uzlu od uzlu, který zprávu původně odeslal). Rozdíl mezi výškou uzlu a výškou sousedního uzlu se označuje jako gradient pro toto spojení. Pokud uzel poté přijme data adresovaná uzlu, který původně odeslal žádost, tak je odešle sousedovi, s nímž má spojení ohodnocené nejvyšším gradientem. Pro přenos datových paketů se navíc používají následující techniky: • Pokud existuje více než jedno spojení ohodnocené stejným gradientem, uzel si náhodně vybere jedno z nich. • Pokud energie uzlu klesne pod určitou hodnotu, uzel si zvýší hodnotu své výšky a o této změně informuje ostatní uzly (díky tomu se sníží šance, že ostatní uzly budou tomuto uzlu posílat pakety). • Pokud se již nějaký uzel účastní přenosu proudu paketů, oznámí všem svým sousedům (s výjimkou těch, kteří se rovněž účastní tohoto přenosu), že si zvýšil svoji výšku (díky tomu se sníží šance, že se tento uzel bude současně účastnit i přenosu jiného proudu paketů).

4.2.5

MCFA

MCFA (Minimum Cost Forwarding Algorithm) [22] je algoritmus, který je založený na tom, že každý uzel je nějakým způsobem ohodnocený vůči základnové stanici, kde toto ohodnocení představuje ohodnocení minimální cesty od tohoto uzlu k základnové stanici a může záviset na faktorech, jako je například počet hopů, spotřeba energie, zpoždění atd. Toto ohodnocení se provádí následujícím způsobem. Každý uzel si nejdříve nastaví své ohodnocení na nekonečno. Základnová stanice odešle všesměrovým vysíláním zprávu, která je také ohodnocena (na počátku má hodnotu 0). Každý uzel, který tuto zprávu přijme, si spočítá, zda je ohodnocení zprávy menší než součet aktuálního ohodnocení uzlu a ohodnocení spojení mezi ním a uzlem, od kterého zprávu přijal. Pokud je menší, tak si aktualizuje své vlastní ohodnocení a také ohodnocení zprávy a aktualizovanou zprávu odešle svým sousedům. Pokud je ohodnocení zprávy větší než vypočítaný součet, tak uzel neprovádí žádné změny a zprávu nikomu neodešle. Tento postup ale není příliš efektivní, protože zde může docházet k příliš častému odesílání aktualizovaných zpráv. Proto každý uzel, který změní své ohodnocení a ohodnocení zprávy, čeká před odesláním této zprávy po dobu a ∗ L, kde a je konstanta a L je ohodnocení spojení s uzlem, od kterého zprávu přijal. Poté, co je provedeno ohodnocení uzlů v síti, jsou zprávy určené základnové stanici odesílány po cestě s minimálním ohodnocením. Uzel, který chce odeslat zprávu základnové 36


stanici, přidá k této zprávě informace o minimálním ohodnocení cesty od tohoto uzlu k základnové stanici (tedy své vlastní ohodnocení) a tuto zprávu odešle všesměrovým vysíláním. Součástí této zprávy je také informace o tom, jaké je celkové ohodnocení cesty, kterou zpráva dosud urazila. Toto číslo použije každý uzel, který tuto zprávu přijme, a přičte k němu své vlastní ohodnocení. Tento součet porovná s ohodnocením celé cesty (tedy cesty od uzlu, který zprávu původně odeslal, k základnové stanici) a pokud se obě čísla rovnají, tak zprávu pomocí všesměrového vysílání odešle (protože zjistil, že se nachází na této minimální cestě). Stejným způsobem postupují ostatní uzly, které zprávu přijmou, dokud není zpráva doručena základnové stanici. Tento mechanismus umožňuje, že si každý uzel může uchovávat pouze informaci o svém ohodnocení, není tedy nutné přidělovat uzlům jedinečné identifikátory ani vytvářet směrovací tabulky.

4.2.6

COUGAR

COUGAR [23] přistupuje k sítím jako k velkým distribuovaným databázovým systémům. Hlavní důraz je zde kladen na zpracování dotazů. Tyto dotazy mohou být velmi složité, mohou se skládat z velkého počtu parametrů a operátorů, mohou obsahovat požadavky na maximální přípustnou velikost zpoždění atd. Příkladem jednoduchého dotazu v senzorové síti, ve které senzorové uzly měří teplotu prostředí, může být například dotaz, jehož cílem je informovat uživatele v případě, že průměrná teplota v místnosti přesáhla určitou uživatelem definovanou hodnotu. Jedním z hlavním problémů, který se snaží COUGAR řešit, je problém s agregací dat, tedy s doručováním dat z více senzorových uzlů do jednoho vybraného uzlu. Tento vybraný uzel (tzv. vedoucí uzel) shromažďuje data, která mu odeslaly jednotlivé uzly, provádí na nich výpočty (vyhodnocuje dotazy) a také komunikuje se základnovou stanicí. Za vedoucí uzel je vhodné zvolit takový uzel, který bude mít co nejlepší vzdálenost od ostatních senzorových uzlů i od základnové stanice nebo třeba uzel, který má dostupné větší množství energie. Jak již bylo uvedeno, vybraný vedoucí uzel vyhodnocuje dotazy nad daty, která mu posílají jednotlivé uzly. Vzhledem k tomu, že ve větších sítích by toto mohlo vést k zasílání velkého množství zpráv, může být vhodné částečně vyhodnocovat některé dotazy na uzlech, které se nacházejí na cestě k vedoucímu uzlu, pokud je to možné. Takto lze například zpracovávat dotazy obsahující agregační funkce typu avg (výpočet průměrné hodnoty), max (maximální hodnota) atd. Vedoucí uzel poté provede vyhodnocení na základě těchto částečně vyhodnocených dotazů. Nevýhodou tohoto částečného vyhodnocování ale je, že uzel, který jej provádí, musí čekat na potřebná data od všech příslušných uzlů, což může být problém v sítích s vysokou ztrátovostí. Všechny tyto úkony jsou popsány v tzv. plánu dotazu. Tento plán je vytvářen základnovou stanicí a obsahuje například informace o tom, jakým způsobem bude zvolen vedoucí uzel, jakým způsobem budou přenášena data mezi senzorovými uzly nebo jakým způsobem bude prováděn výpočet na jednotlivých uzlech. Pro sestavení co nejlepšího plánu je vhodné si udržovat informace například o umístění senzorových uzlů, zátěži systému, stabilitě sítě atd. Tento plán je poté rozeslán jednotlivým senzorovým uzlům.

37


Obrázek 4.4: Plán dotazu pro vedoucí uzel (vedoucí uzel přijme všechny částečně vyhodnocené dotazy, vypočítá průměrnou hodnotu a pokud je větší než prahová hodnota threshold, odešle výsledky základnové stanici) [23]

4.2.7

ACQUIRE

ACQUIRE [24] přistupuje (stejně jako COUGAR) k senzorovým sítím jako k distribuovaným databázovým systémům. Základnová stanice odešle dotaz, který může být velmi složitý a může se skládat z mnoha poddotazů. Tento dotaz je šířen sítí, přičemž každý uzel, který jej přijme (tzv. aktivní uzel), se snaží tento dotaz alespoň částečně vyřešit na základě vlastních informací a informací, které získal od všech uzlů, které se od něj nachází do vzdálenosti d hopů. Pokud jsou informace tohoto aktivního uzlu zastaralé (tedy už uběhla určitá definovaná doba od doby, kdy získal nějaké informace od těchto uzlů), požádá tyto uzly o zaslání aktuálních informací. Poté, co aktivní uzel vyřeší co největší část dotazu, odešle jej některému ze svých sousedů, kterého si může vybrat buď náhodně, nebo na základě nějakých dalších informací, které si udržuje. Tímto způsobem je dotaz dál částečně řešen, dokud se nedostane k uzlu, který je schopen jej vyřešit úplně. Poté, co tento uzel dotaz vyřeší, odešle jej zpátky základnové stanici (buď po stejné cestě, nebo po nejkratší cestě). Volba hodnoty d výrazně ovlivňuje efektivitu zpracování dotazů. Čím větší je hodnota d, tím kratší vzdálenost v síti musí urazit odeslaný dotaz. Na druhou stranu ale vyšší hodnota d zvyšuje náročnost udr38


žování aktuálních informací jednotlivých uzlů v síti.

4.2.8

IDSQ a CADR

IDSQ (Information-driven sensor querying) a CADR (Constrained anisotropic diffusion routing) [25] jsou dva mechanismy používané pro směrování v bezdrátových senzorových sítích. Hlavním úkolem IDSQ je výběr uzlů, které mohou poskytnout co nejlepší odpověď na zadaný dotaz. Uzly jsou rozděleny do několika skupin a na počátku znají všechny uzly pouze informaci o svém vlastním umístění v síti. Tyto uzly si poté zvolí mezi sebou tzv. vedoucí uzel, který bude znát další potřebné informace (např. pozice všech uzlů ve skupině). Tento vedoucí uzel potom zpracovává dotazy, které se týkají událostí, jež nastaly ve skupině, ve které byl zvolen. Pokud vedoucí uzel má zpracovat určitý dotaz, nejdříve zjistí, zda již má dostatek informací k tomu, aby tento dotaz zpracoval sám. Tyto informace zahrnují informace, které získal vedoucí uzel sám vlastním měřením, a také informace, které již získal od ostatních uzlů (vedoucí uzel si udržuje seznam uzlů, od kterých již nějaké informace dříve získal). Pokud dostatek informací dosud nemá, vybere si nějaký uzel ve skupině, o kterém předpokládá (na základě dříve získaných informací), že by mohl mít potřebné informace, a odešle mu žádost. Po přijetí odpovědi na tuto žádost si vedoucí uzel přidá tento uzel do seznamu a případně odešle žádosti dalším uzlům, dokud není schopen zpracovat dotaz. Vedoucí uzel se tedy snaží vybírat uzly ve skupině takovým způsobem, aby informace od nich získaná byla pro něj co nejvíce užitečná. K měření užitečnosti těchto informací lze použít mnoho různých způsobů, např. měření založené na kovarianci, měření založené na entropii atd. IDSQ se tedy zaměřuje na výběr těchto uzlů, ale nedefinuje, jakým způsobem bude ve skupině prováděno směrování dotazů. Hlavním úkolem CADR je šíření dotazů ve skupině a nalezení uzlů, které mají určitá data. K tomu lze přistupovat různými způsoby. Pokud má vedoucí uzel informace o pozicích všech uzlů ve skupině, potom může být dotaz adresován konkrétnímu uzlu, který se nachází co nejblíže určitému místu v síti, z něhož chce vedoucí uzel získat potřebné informace. Výběr tohoto optimálního místa je prováděn pomocí funkce M . Výsledek této funkce je založený na informacích, jako je např. užitečnost zde se nacházejících informací nebo cena jejich přenosu (dostupná šířka pásma, zpoždění atd.). Pokud vedoucí uzel nezná pozice všech uzlů ve skupině, potom každý uzel v síti, který přijme dotaz odeslaný vedoucím uzlem, sám rozhoduje o tom, komu by jej měl odeslat (k tomu opět využívá funkci M ). Aby mohl každý uzel co nejlépe vyhodnotit funkci M , musí vedoucí uzel spolu s dotazem odesílat i další potřebné informace, které již sám získal dříve od ostatních uzlů. Tento dotaz je tedy uzly přeposílán tak dlouho, dokud není nalezen uzel, který se nachází nejblíže optimálnímu místu, ze kterého je možné získat potřebná data. Někdy navíc tento uzel ani nemusí být nutné nalézt. Pokud uzly, které se nachází na cestě k tomuto uzlu, jsou již schopny také odpovědět na určitý dotaz, mohou odeslat tyto informace vedoucímu uzlu, který, pokud zjistí, že přijaté informace jsou již dostatečně přesné, může ukončit zpracování dotazu dříve, než je nalezen uzel nejblíže optimálnímu místu.

39


4.2.9

Energy aware routing

Energy aware routing [26] je protokol, který je podobný directed diffusion. Zatímco ale directed diffusion používá pro přenos dat jednu nejlepší cestu, kterou vybere z několika cest, a po ní přenáší data s vyšší přenosovou rychlostí, energy aware routing si udržuje více cest. To je výhodné zejména proto, že používání jediné cesty může vést k vysoké spotřebě energie uzlů, které se na této cestě nachází. Pokud nějaký uzel chce získat určitá data držená jinými uzly, tak odešle (formou záplavy) žádost o tato data (podobně jako u directed diffusion). Každý uzel, který tuto žádost přijme, ji odešle svým sousedům. Zároveň si uzly průběžně vypočítávají i cenu cesty, kterou přidávají k odesílané žádosti. Díky tomu se mezi uzlem požadujícím data a uzlem vlastnícím tato data vytvoří několik ohodnocených cest, přičemž cesty, které mají příliš vysoké ohodnocení se pro přenos dat nebudou používat. Na základě ohodnocení jednotlivých cest je potom každé cestě přiřazena pravděpodobnost jejího využití. Pokud tedy potom bude chtít uzel odeslat nějaká data, vždy si náhodně vybere jednu z těchto cest podle hodnoty její pravděpodobnosti. Tento způsob výběru cest umožňuje rovnoměrnější spotřebu energie uzlů v síti ve srovnání s případem, kdy jsou data přenášena pouze po jedné vybrané nejlepší cestě.

4.3

Hierarchické protokoly

Hierarchické protokoly se obvykle používají v rozsáhlejších sítích za účelem dosažení lepší škálovatelnosti a efektivnější komunikace. Celá síť je obvykle rozdělená do několika oblastí, přičemž v každé takové oblasti je vybrán jeden uzel, který je nadřazený ostatním uzlům. Tímto nadřazeným uzlem je obvykle ten uzel, který má co největší zdroj energie, co nejlepší hardwarové vybavení, co nejlepší umístění v síti atd. Jeho úkolem je řídit komunikaci v dané oblasti a komunikovat (buď přímo nebo přes další senzorové uzly) se základnovou stanicí.

4.3.1

LEACH

LEACH je hierarchickým směrovacím protokolem, ve kterém jsou uzly organizovány do skupin a v rámci každé skupiny si mezi sebou zvolí jeden vedoucí uzel, který řídí komunikaci ve skupině a sestaví plán, ve kterém je každému uzlu nacházejícímu se v této skupině přidělen určitý časový díl, během kterého smí odesílat data tomuto vedoucímu uzlu. Poté, co vedoucí uzel přijme data od všech uzlů ve skupině, odešle je základnové stanici. Protokol LEACH je podrobněji popsán v kapitole 3.3.1.

4.3.2

PEGASIS

PEGASIS (Power-Efficient Gathering in Sensor Information Systems) [27] je směrovací protokol, který byl navržený jako vylepšení protokolu LEACH. Na rozdíl ale od protokolu LEACH, který rozděluje uzly v síti do několika skupin, protokol PEGASIS organizuje uzly do řetězů. Tento řetěz může vytvořit buď přímo základnová stanice, která jej poté rozešle 40


všesměrovým vysíláním všem uzlům, nebo si jej mohou vytvořit uzly samy tak, že určitý vybraný uzel zjistí (na základě síly vysílaného signálu), který uzel je mu nejblíže, a tyto dva uzly budou sousedy ve vytvářeném řetězu. Tímto se tedy postupně prodlužuje řetěz, přičemž každý nově připojený uzel do tohoto řetězu vždy zjistí, který uzel je mu nejblíže a dosud není součástí vytvářeného řetězu (viz obrázek 4.5). Pokud dojde k výpadku některého z uzlů, je tento řetěz vytvořen stejným způsobem znovu.

Obrázek 4.5: Vytváření řetězu v protokolu PEGASIS (uzel BS představuje základnovou stanici, uzel 0 se nejdříve spojí s uzlem 3, uzel 3 se poté spojí s uzlem 1, nakonec se uzel 1 spojí s uzlem 2) [27] Přenos dat probíhá tak, že uzel, který přijme nějaká data od svého souseda, k těmto datům připojí svá vlastní data a vše odešle svému druhému sousedovi v řetězu. Tímto způsobem se data přenáší v řetězu, přičemž je vždy na určitou dobu náhodně vybrán jeden z uzlů v řetězu (tzv. vedoucí uzel), který bude získaná data odesílat základnové stanici (po uplynutí této doby je vybrán uzel jiný). Na obrázku 4.6 je znázorněno, jak přenos dat pomocí protokolu PEGASIS probíhá. Uzel c2 je vybrán jako vedoucí uzel a odešle jednomu ze svých dvou sousedů speciální zprávu (tzv. token). Pokud si vybere uzel c1, potom uzel c1 přepošle token uzlu c0. Uzel c0 odešle svá data uzlu c1, který k nim připojí svá vlastní data a vše odešle vedoucímu uzlu c2. Uzel c2 poté odešle token uzlu c4 (přes uzel c3) a stejným způsobem přijme data od těchto dvou uzlů. Poté uzel c2 odešle všechna data, která takto získal od obou svých sousedů, uzlu BS (základnové stanici).

Obrázek 4.6: Přenos dat v protokolu PEGASIS [27] Výhodou protokolu PEGASIS oproti protokolu LEACH je, že umožňuje mnohem větší šetření energie. Na druhou stranu ale jeho nevýhodou může být příliš velké zpoždění pro vzdálené uzly na vytvořeném řetězu a také to, že každý uzel by měl být schopný komunikovat přímo se základnovou stanicí (to lze ale částečně řešit tak, že některým uzlům, které se nachází příliš daleko od základnové stanice, může být vhodné zakázat, aby se staly vedoucími uzly). Problém s velkým zpožděním pro vzdálené uzly je možné řešit více 41


způsoby. Jedním z těchto způsobů je použití hierarchické verze protokolu PEGASIS [28], která využívá souběžné odesílání dat a kódový multiplex (CDMA). Postup při přenosu dat je znázorněn na obrázku 4.7. Na tomto obrázku je uzel c3 vybrán jako vedoucí uzel. Přenos dat probíhá v několika úrovních (vedoucí uzel se nachází ve všech těchto úrovních), přičemž uzly na určité úrovni jsou vždy podmnožinou uzlů nacházejících se na úrovni nižší. Na nejnižší úrovni se nachází všechny uzly a každému z nich je přiřazena pozice (uzel c0 je na pozici 0, uzel c1 je na pozici 1 atd.). Všechny uzly, které se na této úrovni nachází na sudé pozici, odesílají svá data svému pravému sousedovi, který k nim připojí svá vlastní data. Vzhledem k tomu, že vedoucí uzel c3 se nachází v této úrovni na liché pozici, tak všechny ostatní uzly na lichých pozicích budou také přijímat data. Pouze uzly, které na dané úrovni přijímají data (v tomto případě uzly c1, c3, c5 a c7), se objeví na vyšší úrovni hierarchie. Na vyšší úrovni (tvořené uzly c1, c3, c5 a c7) se uzel c3 nachází opět na liché pozici (pozice 1), proto všechny uzly nacházející se na lichých pozicích (c3 a c7) budou přijímat data od svých levých sousedů. Tato přijatá data opět spojí se svými vlastními daty. Na vyšší úrovni se nachází uzly c3 a c7. Uzel c3 se nachází na pozici 0, proto přijme data od svého souseda na liché pozici (uzel c7), připojí k nim svá data a na nejvyšší úrovni (zde se nachází pouze vedoucí uzel) všechna data odešle základnové stanici (uzlu BS).

Obrázek 4.7: Přenos dat pomocí hierarchické verze protokolu PEGASIS [28]

4.3.3

TEEN

Protokol TEEN (Threshold-sensitive Energy Efficient Sensor Network) [29] je dalším hierarchickým směrovacím protokolem. Uzly jsou (podobně jako u protokolu LEACH) rozděleny do několika skupin a v každé skupině je vybrán jeden vedoucí uzel (označovaný jako cluster-head), který bude přijímat data od všech ostatní uzlů v dané skupině a tato data bude poté odesílat buď přímo základnové stanici, nebo jinému vedoucímu uzlu, který se nachází na vyšší úrovni. Po tomto rozdělení sítě vedoucí uzel rozešle všem uzlům ve skupině dvě prahové hodnoty – HT (Hard Threshold) a ST (Soft Threshold). HT označuje minimální hodnotu veličiny, kterou v daném prostředí uzly monitorují (například minimální teplotu okolního prostředí). Pokud naměřená hodnota této veličiny přesáhne velikost HT , uzel odešle zprávu příslušnému vedoucímu uzlu a aktuální naměřenou hodnotu si uloží do proměnné SV (sensed value). ST označuje velikost změny této veličiny. Uzel, který odeslal zprávu vedoucímu uzlu po překročení prahové hodnoty HT , dál pokračuje v měření okolního 42


prostředí, ale další zprávu odešle vedoucímu uzlu pouze v případě, pokud nově naměřená hodnota veličiny je větší než součet SV + ST nebo pokud je rovna součtu SV + ST . Po odeslání zprávy si uzel nastaví hodnotu proměnné SV na hodnotu této nově naměřené veličiny. Uzel tedy odesílá zprávu vedoucímu uzlu pouze v případě, že hodnota měřené veličiny se zvýšila alespoň o hodnotu ST . Použití těchto dvou prahových hodnot výrazně snižuje spotřebu energie uzlů (vysílání je výrazně omezeno) a je vhodné je použít, pokud je cílem sledování hodnot měřené veličiny pouze v určitém rozsahu (například pro informování před možným vznikem požáru v případě výrazného zvýšení teploty prostředí). Používání těchto prahových hodnot ale zároveň může být i nevýhodou, protože pokud není překročena prahová hodnota HT , uzly neodesílají žádné informace a uživatel tedy ani nemusí zjistit, že došlo k výpadku těchto uzlů.

4.3.4

APTEEN

Protokol APTEEN (Adaptive Periodic Threshold-sensitive Energy Efficient Sensor Network) [30] je velmi podobný protokolu TEEN, ale navíc se snaží řešit situaci, kdy uživatel chce získat informace o aktuálních hodnotách sledovaných veličin, přestože tyto hodnoty nepřekročily prahovou hodnotu HT . To je prováděno tak, že zvolený vedoucí uzel ve skupině odesílá všem uzlům prahové hodnoty (HT a ST ), informace o tom, jaké veličiny mají sledovat, plán vysílání přidělující každému uzlu časový díl, během kterého může uzel vysílat (podobně jako u protokolu LEACH), a časovou hodnotu (count time, TC ). Hodnota TC označuje maximální dobu mezi odesláním dvou zpráv jedním uzlem. Pokud uzel po dobu TC neodeslal žádnou zprávu vedoucímu uzlu, musí tak po uplynutí této doby učinit. Výhodou protokolu APTEEN je jeho velká flexibilita díky možnosti nastavení hodnot HT , ST a TC podle požadavků uživatele. Vhodným nastavením prahových hodnot a při nastavení vyšší hodnoty TC lze dosáhnout omezení vysílání uzlů (a tedy zvýšení životnosti sítě), nastavení nižší hodnoty TC lze použít v případě, kdy uživatel chce získávat informace o naměřených hodnotách veličin pravidelně.

4.3.5

SOP

SOP (Self-Organizing Protocol) [31] je protokol používaný v bezdrátových senzorových sítích, které jsou tvořeny dvěma typy senzorových uzlů. Prvním typem uzlů jsou specializované uzly, které monitorují okolní prostředí a naměřená data odesílají ostatním uzlům, druhým typem jsou směrovací uzly. Tyto směrovací uzly musí být nepohyblivé (na rozdíl od specializovaných uzlů, které pohyblivé být mohou) a vytváří páteř senzorové sítě. Uzly, které získaly nějaká data, odesílají tato data přilehlému směrovacímu uzlu, který tato data odesílá (přes další směrovací uzly) základnové stanici. Pro každý specializovaný uzel by tedy měl být dosažitelný nějaký směrovací uzel. Každý uzel si navíc udržuje směrovací tabulku a má přidělenou jedinečnou adresu v síti. Hlavním úkolem protokolu SOP je samoorganizace směrovacích uzlů a vytváření směrovacích tabulek, přičemž specializované uzly si musí udržovat přehled o tom, který směrovací

43


uzel je k nim nejblíže. Tento protokol se skládá ze čtyř fází. Během první fáze (fáze objevování) si každý uzel vytvoří seznam svých sousedů. To provádí tak, že odešle zprávu všesměrovým vysíláním (součástí této zprávy je i informace o tom, zda odesílající uzel je specializovaným nebo směrovacím uzlem) a všechny uzly, které tuto zprávu přijmou, na ni odpoví. Na základě těchto odpovědí si každý uzel vytvoří seznam svých sousedů, přičemž směrovací uzly si vytváří spojení s oběma typy uzlů, ale specializované uzly si vytváří spojení pouze se směrovacími uzly. Ve druhé fázi (organizační fáze) se jednotlivé uzly organizují do skupin. Každý směrovací uzel vytvoří tzv. základní skupinu se svými sousedy, přičemž platí, že každý uzel v síti patří do právě jedné základní skupiny. Každému uzlu v této skupině je poté přiřazena adresa o velikosti 3 bity (tedy v základní skupině může být maximálně 8 uzlů) a také si každý uzel udržuje informace o tom, jakým způsobem lze dosáhnout všech ostatních uzlů v základní skupině (tedy udržuje si příští hop směrem ke každému uzlu ve skupině). Tyto skupiny se dále spojují do větších skupin, přičemž platí, že pokud se spojují dvě skupiny G1 a G2 do jedné skupiny G, potom všechny uzly ze skupiny G1 si doplní bit 0 na začátek své adresy a všechny uzly ze skupiny G2 si doplní bit 1 na začátek své adresy. Jednotlivé skupiny se dále spojují (o své existenci se navzájem dozví pomocí zpráv zasílaných všesměrovým vysíláním), dokud se všechny nespojí do jedné. Díky tomu se v síti vytvoří hierarchická stromová struktura, ve které má každý uzel svoji jedinečnou adresu, a na základě těchto informací si každý uzel vytvoří směrovací tabulku. Během třetí fáze (fáze údržby) se uzly navzájem informují o tom, zda nedošlo k výpadku. To může být prováděno dvěma způsoby – buď aktivně (každý uzel periodicky odesílá zprávu, pomocí které informuje své sousedy o tom, že stále funguje), nebo pasivně (uzel A odešle uzlu B zprávu, na kterou uzel B odpoví potvrzením, že stále funguje). Uzly také informují své sousedy o svých směrovacích tabulkách a o tom, kolik jim ještě zbývá energie. Na základě těchto informací si uzly aktualizují své směrovací tabulky (tak, aby pro dosažení nějakého uzlu byla použita co nejméně energeticky náročná cesta). Čtvrtá fáze (fáze reorganizace) se uplatní, pokud dojde například k výpadku některých uzlů. V takovém případě si sousedé uzlu, který měl výpadek, aktualizují své směrovací tabulky. Pokud by došlo k výpadku všech sousedů nějakého uzlu, potom uzel odešle zprávu, pomocí které se pokusí získat nové sousedy (podobným způsobem jako v první fázi). Protokol SOP je vhodné použít pro aplikace, kde je vyžadovaná komunikace s konkrétními uzly (každý uzel zde má svou jedinečnou adresu). Jeho další výhodou je, že udržování směrovacích tabulek není příliš nákladné. Na druhou stranu ale není příliš vhodný v případě, kdy v síti dochází často k výpadkům a je tedy nutné často provádět reorganizaci.

4.4

Protokoly založené na umístění uzlů

Mnoho směrovacích protokolů pro bezdrátové senzorové sítě vyžaduje informace o umístění senzorových uzlů. Tyto informace jsou vhodné například pro výpočet vzdáleností mezi dvěma uzly, které spolu komunikují (na základě této vzdálenosti lze odhadovat spotřebu energie). V případě, kdy předem známe geografickou oblast, ze které chceme získat data, 44


můžeme dotaz odeslat pouze do této požadované oblasti. V následující části práce jsou popsány některé z protokolů, které využívají informace o umístění uzlů, přičemž některé z nich byly navrženy primárně pro bezdrátové ad hoc sítě, ale lze je dobře aplikovat i v bezdrátových senzorových sítích.

4.4.1

GAF

GAF (Geographic Adaptive Fidelity) [32] je algoritmus využívající informace o umístění uzlů, který byl původně navržený pro směrování v ad hoc sítích. Informaci o svém umístění mohou uzly získat např. pomocí GPS (Global Positioning System), což je systém používaný pro určování polohy a přesného času. Na počátku se v síti používající algoritmus GAF vytvoří virtuální mřížky, přičemž uzly, které se nachází ve stejné virtuální mřížce, jsou z hlediska směrování ekvivalentní. To znamená, že pro každé dvě přilehlé virtuální mřížky A a B platí, že všechny uzly v A mohou komunikovat se všemi uzly v B a naopak. Díky tomu je možné snížit spotřebu energie tím, že v každé virtuální mřížce může být v určitém okamžiku pouze jeden uzel aktivní a ostatní mohou být v režimu spánku. Na obrázku 4.8 jsou znázorněny tři virtuální mřížky (A, B a C). Uzel 1 může tedy komunikovat s uzly 2, 3 a 4, uzly 2, 3 a 4 mohou komunikovat s uzlem 5. Díky tomu může pouze jeden z uzlů v mřížce B být aktivní a zbylé dva mohou být v režimu spánku.

Obrázek 4.8: Rozdělení sítě na virtuální mřížky pomocí protokolu GAF [32] Každý uzel se vždy nachází v jednom ze tří stavů – stav objevování, aktivní stav a stav spánku. Ve stavu objevování uzel odesílá zprávy za účelem nalezení ostatních uzlů ve stejné virtuální mřížce. Tyto zprávy (discovery messages, dm) obsahují identifikátor uzlu, identifikátor virtuální mřížky, stav uzlu a odhadovanou dobu aktivního stavu uzlu (estimated node active time, enat), která závisí na životnosti uzlu. Po uplynutí určité doby některý uzel přejde do aktivního stavu (pro výběr uzlu, který se stane aktivním, se zejména používá hodnota enat, kterou si uzly vzájemně posílají pomocí zpráv dm). V aktivním stavu se uzel účastní směrování v síti a periodicky rozesílá všem uzlům ve virtuální mřížce zprávy dm. Po uplynutí doby enat (nebo pokud dříve přijme zprávu dm od uzlu, který má podstatně větší hodnotu enat a přejde místo něj do aktivního stavu) uzel přejde zpět do 45


stavu objevování. Ze stavu objevování i z aktivního stavu může uzel přejít do stavu spánku, pokud zjistí, že nějaký jiný uzel v této virtuální mřížce bude v aktivním stavu provádět směrování. Dobu, kterou uzel stráví ve stavu spánku, si odvodí na základě hodnoty enat přijaté od uzlu, který se zrovna nachází v aktivním stavu. Jak již bylo uvedeno, v každé virtuální mřížce je dostačující, aby byl v aktivním stavu v určitém okamžiku pouze jeden uzel a ostatní uzly mohou být po tuto dobu ve stavu spánku. Problém ale může nastat v sítích, ve kterých se uzly mohou pohybovat. Mohlo by tedy dojít k situaci, kdy uzel v aktivním stavu opustí virtuální mřížku, přičemž všechny ostatní uzly by zůstaly ve stavu spánku. Tento problém lze řešit tak, že každý uzel odhadne dobu, kdy očekává, že opustí virtuální mřížku (expected node grid time, engt) a tuto hodnotu přidá do zprávy dm. Uzel si může vypočítat přibližnou hodnotu engt na základě velikosti virtuální mřížky a své rychlosti (k tomu lze použít GPS). Uzel, který přejde do stavu spánku, si potom nastaví dobu spánku na základě menší z hodnot enat a engt.

4.4.2

GEAR

GEAR (Geographic and Energy Aware Routing) [33] je algoritmus, ve kterém uzly, které požadují určitá data, odesílají žádosti podobně jako u directed diffusion, ale na rozdíl od directed diffusion, kde byly žádosti odesílané do celé sítě, GEAR tyto žádosti odesílá do určité geografické oblasti. Díky tomu lze dosáhnout větší úspory energie uzlů. Proces směrování paketů pomocí algoritmu GEAR lze rozdělit do dvou fází – přenos paketu od uzlu, který žádá určitá data, do určité geografické oblasti a přenos paketu uvnitř této oblasti. Každý paket se žádostí o nějaká data obsahuje informace o tom, do jaké geografické oblasti má být odeslán. Každý uzel v síti, který tento paket přijme, si udržuje tzv. odhadovanou cenu (estimated cost) a naučenou cenu (learned cost). Uzel N si vypočítá odhadovanou cenu c(Ni , R) pro každého svého souseda Ni a pro geografickou oblast R. Tento výpočet závisí na dostupné energii sousedního uzlu Ni a na vzdálenosti uzlu do cílové oblasti. Naučená cena h(Ni , R) je na počátku rovna c(Ni , R), nicméně se její hodnota časem může měnit (například z důvodu výpadku některých uzlů). Pokud uzel N přijme nějaký paket, odešle jej některému ze svých sousedů Ni , který se nachází blíže cílové geografické oblasti než on sám. Z těchto sousedů vybere ten s co nejnižší hodnotou h(Ni , R) a odešle mu paket. Pokud uzel N nemá žádného souseda, který by se nacházel blíže cílové oblasti než on sám, potom uzel N odešle paket svému sousedovi Ni , který má co nejnižší hodnotu h(Ni , R). V obou případech si uzel N poté, co odešle paket tomuto sousedovi Ni , aktualizuje svou vlastní naučenou cenu h(N, R) následujícím způsobem: h(N, R) = h(Ni , R) + C(N, Ni ), kde C(N, Ni ) označuje cenu přenosu paketu z uzlu N uzlu Ni . Tuto nově vypočítanou cenu potom může odeslat svým sousedům. Přenos paketů do cílové oblasti je znázorněn na obrázku 4.9. Uzel S odesílá paket 46


určený do oblasti, v jejímž středu se nachází uzel T. Vzdálenost mezi sousedními uzly na uvedeném obrázku (např. mezi uzly A a B) je rovna 1, uzly G, H a I již nepřeposílají pakety (např. z důvodu vyčerpání dostupné energie). Na počátku si uzel S vybere jednoho ze svých sousedů, kteří se nacházejí blíže√k uzlu T než on sám (těmito uzly jsou B, C a D),√přičemž platí, že h(B, T ) = c(B, T ) = 5, h(C, T ) = c(C, T ) = 2, h(D, T ) = c(D, T ) = 5. Uzel S si tedy vybere uzel C, kterému odešle paket. Uzel C po přijetí paketu zjistí, že žádný z jeho sousedů se nenachází blíže uzlu T než on sám, proto odešle paket uzlu s minimální hodnotou h(N, T ). Pokud si vybere uzel B (mohl by si vybrat i uzel D), odešle mu paket a √ nastaví si h(C, T ) = h(B, T ) + C(C, B), tedy h(C, T ) = 5 + 1 (pokud předpokládáme, že cena přenosu paketu mezi uzly C a B je rovna 1). Pokud někdy později √ bude uzel S odesílat √ 5, h(C, T ) = 5 + 1, paket opět do oblasti, v jejímž středu je uzel T, zjistí, že h(B, T ) = √ h(D, T ) = 5. V tomto případě uzel S již nebude odesílat paket uzlu C, ale odešle jej přímo uzlu B (příp. uzlu D).

Obrázek 4.9: Přenos paketu do cílové geografické oblasti pomocí algoritmu GEAR [33] Pro šíření paketu uvnitř cílové geografické oblasti lze použít například záplavu (pro sítě s nízkou hustotou uzlů). Pro sítě s větší hustotou uzlů je ale záplava nevhodná, proto se používá rekurzivní geografické směrování. To funguje tak, že uzel, který přijme paket a již se nachází v cílové oblasti, vytvoří čtyři kopie tohoto paketu. Celá geografická oblast se rozdělí do čtyř podoblastí a do každé z těchto podoblastí je odeslána jedna kopie paketu. Tento postup se opakuje tak dlouho, dokud uzel, který přijme paket, není jediným uzlem v dané podoblasti.

47


4.4.3

MECN

Protokol MECN (Minimum Energy Communication Network) [34] je směrovací protokol, který vytváří v senzorové síti podsíť, jež je tvořena uzly, které umožňují efektivní a energeticky méně náročný přenos dat v síti. Po vytvoření této podsítě spolu tedy jakékoli dva uzly v síti komunikují pouze prostřednictvím uzlů, které se nachází ve vytvořené podsíti. Při vytváření této podsítě se pro každý uzel nejdříve vytvoří tzv. přenosová oblast, která je tvořena takovými uzly z okolí tohoto uzlu, které umožňují energeticky méně náročný přenos. Tato přenosová oblast pro dvojici uzlů (i, r) je definovaná takto: Ri→r ≡ {(x, y)|Pi→r→(x,y) < Pi→(x,y) }, kde Pi→(x,y) označuje energii nutnou pro přímý přenos informace z uzlu i uzlu, který se nachází na pozici (x, y), a Pi→r→(x,y) označuje energii nutnou pro přenos informace z uzlu i uzlu na pozici (x, y) přes uzel r. Přenosová oblast pro dvojici uzlů (i, r) tedy představuje množinu pozic, na které je vhodnější přenášet informace přes uzel r. Každý uzel nejdříve odešle všem svým sousedům zprávu, ve které je informuje o své pozici. Zároveň přijímá zprávy od ostatních uzlů, které jej informují o své pozici. Pokud uzel přijme zprávu od nějakého uzlu, zjistí pozici tohoto uzlu a vypočítá si pro něj přenosovou oblast. Zároveň si uloží informaci o tom, zda se tento uzel nachází v přenosové oblasti některého jiného uzlu, od kterého přijal zprávu dříve. Pouze uzly, které se nenachází v přenosových oblastech žádného jiného nalezeného uzlu, bude uzel používat pro přenos dat. Na základě těchto informací si každý uzel vytváří přenosový graf, který obsahuje informace o tom, které uzly lze použít pro přenos dat. V tomto grafu jsou jednotlivé uzly ohodnoceny, přičemž jako metrika se používá energetická spotřeba. Každý uzel si tedy vypočítá své ohodnocení, které odpovídá minimální energii potřebné pro komunikaci se základnovou stanicí. Tento výpočet provede na základě výměny informací se svými sousedy. Pokud uzel i přijme od svého souseda n zprávu obsahující jeho ohodnocení Cost(n), provede následující výpočet: Ci,n = Cost(n) + Ptransmit (i, n) + Preceiver (n), kde Ptransmit (i, n) označuje energii potřebnou pro přenos informace z uzlu i k uzlu n a Preceiver (n) označuje energii potřebnou pro uzel n pro přijetí informace od uzlu i. Na základě těchto vypočítaných hodnot získaných od všech svých sousedů si uzel i vybere tu nejmenší, která bude ohodnocením uzlu i, tedy Cost(i). Poté jsou (na základě ohodnocení uzlů) v grafu vypočítány nejkratší cesty pro přenos dat mezi uzly. Nevýhodou tohoto protokolu je, že při přenosu dat nezohledňuje dostupnou energii uzlů. Uzel si tedy vždy vybírá souseda na základě vypočítané nejkratší cesty, a tudíž tento vybraný uzel bude rychle spotřebovávat svou dostupnou energii.

48


4.4.4

SMECN

Protokol SMECN (Small Minimum Energy Communication Network) [35] je rozšířením protokolu MECN. Protokol SMECN se snaží vytvořit graf (podobně jako protokol MECN) takovým způsobem, aby přenos dat v síti na základě tohoto grafu byl energeticky co nejméně náročný. Tento graf je vytvářen takovým způsobem, aby mezi každou dvojicí uzlů existovala cesta, která by umožňovala přenos dat v síti s minimální spotřebou energie. Při použití protokolu SMECN vysílá každý uzel u všesměrovým vysíláním zprávu NDM (neighbor discovery message) s použitím signálu o počáteční síle p0 . Každý uzel, který tuto zprávu přijme, na ni odpoví. Nechť platí: \ RF (u) = (F (u, pmax ) − Ru→v ), v∈NF

kde F (u, pmax ) označuje množinu všech uzlů dosažitelných uzlem u s použitím maximální síly signálu pmax , Ru→v označuje přenosovou oblast pro dvojici uzlů (u, v) a v ∈ NF označuje množinu všech uzlů nacházejících se v oblasti F . Uzel u potom zkontroluje, zda množina RF (u,p0 ) (u) je podmnožinou množiny F (u, p0 ), tedy množiny uzlů, které odpověděly na zprávu NDM. Pokud ano, tak může uzel u používat tuto sílu signálu pro komunikaci se svými sousedy. Pokud ne, tak uzel znovu odešle zprávu NDM s vyšší hodnotou síly signálu (p1 ) a poté zkontroluje, zda množina RF (u,p1 ) (u) je podmnožinou množiny F (u, p1 ). Takto může zvyšovat sílu signálu až do hodnoty pmax .

4.4.5

SPAN

SPAN [36] je další z algoritmů využívající informace o umístění uzlů, který byl původně navržený pro ad hoc sítě. Uzly mezi sebou volí tzv. koordinátory, což jsou uzly, které vytváří páteř bezdrátové senzorové sítě a jejichž úkolem je směrování paketů. Při volbě koordinátorů je hlavní důraz kladen na to, aby v síti bylo koordinátorů co nejméně, ale zároveň aby každý uzel měl alespoň jednoho koordinátora ve svém dosahu. Také je vhodné, aby uzly plnily roli koordinátora pouze po určitou dobu a poté byly vystřídány jiným uzlem. Volba koordinátorů probíhá tak, že uzly periodicky vysílají všesměrovým vysíláním zprávy (tzv. HELLO messages, hm) obsahující informace o tom, zda odesílající uzel je koordinátorem, seznam koordinátorů nacházejících se v jeho dosahu a seznam jeho sousedů. Uzel, který není koordinátorem, se rozhodne, že se koordinátorem stane, pokud dva jeho sousedé nemohou spolu komunikovat ani přímo ani s pomocí jednoho nebo dvou koordinátorů. Pokud se uzel rozhodne, že se stane koordinátorem, oznámí to ostatním uzlům pomocí zprávy hm. Problém by mohl nastat v případě, pokud by se více uzlů rozhodlo stát se koordinátorem ve stejnou dobu. Proto uzel, který se chce stát koordinátorem, nejdříve počká náhodně dlouhou dobu a zprávu hm odešle pouze v případě, pokud během této doby nepřijme zprávu hm od žádného jiného uzlu, který se chtěl také stát koordinátorem. Pokud takovou zprávu přijme, tak znovu opakuje proces zjišťování, zda by se měl stát koordinátorem. 49


Každý uzel, který byl zvolen koordinátorem, dále periodicky zjišťuje, zda stále platí podmínky pro to, aby zůstal koordinátorem. Pokud podmínky neplatí (tedy každá dvojice jeho sousedů je již schopna spolu komunikovat přímo nebo s pomocí jednoho nebo dvou jiných koordinátorů), uzel již koordinátorem nebude. Koordinátor se také může rozhodnout, že po uplynutí určité definované doby koordinátorem již dále nebude, pokud každá dvojice jeho sousedů spolu může komunikovat přes nějakého jiného souseda, přestože tento soused není koordinátorem. Tento soused se poté může stát kandidátem při volbě nového koordinátora (původní koordinátor ještě ale po určitou krátkou dobu plní funkci koordinátora z důvodu zachování spojení v síti).

4.4.6

SPEED

SPEED [37] je protokol navržený pro senzorové sítě, jehož cílem je dosažení komunikace v reálném čase. Poskytuje tři služby pro komunikaci v reálném čase – unicast (odeslání paketu konkrétnímu uzlu v síti), multicast (odeslání kopií paketu skupině uzlů v určité oblasti, k jejíž identifikaci se používá pozice jejího středu a rádius) a anycast (odeslání kopie paketu alespoň jednomu z uzlů, který se nachází v určité oblasti). Každý uzel v síti periodicky odesílá všesměrovým vysíláním paket. Díky této výměně paketů získávají uzly informace o umístění svých sousedů. Uzly také odesílají svým sousedům pakety za účelem odhadu zpoždění. Toto zpoždění je vypočítáno tak, že odesílající uzel přidá k paketu časové razítko. Uzel, který tento paket přijme, na něj odpoví pomocí potvrzujícího paketu (ACK), který navíc obsahuje i informace o době zpracování tohoto paketu. Uzel, který tento potvrzující paket přijme, si vypočítá (na základě tohoto paketu a také paketů přijatých dříve) přibližnou hodnotu zpoždění. Tyto vypočítané informace poté může odeslat svým sousedům, které je poté používají při výběru uzlů pro směrování paketů. Pro směrování paketů se používá algoritmus SNGF (Stateless Non-deterministic Geographic Forwarding). Pokud uzel přijme paket, potom jej odešle některému ze svých sousedů, který se nachází blíže k cílovému uzlu. Tyto uzly, které se nachází blíže k cílovému uzlu, si uzel rozdělí do dvou skupin. V první skupině se nachází uzly, které poskytují přenosovou rychlost vyšší, než je definovaná požadovaná přenosová rychlost (tato požadovaná rychlost je označovaná Ssetpoint ), ve druhé skupině jsou uzly, které požadovanou přenosovou rychlost neposkytují. Pro přenos paketu si uzel vybere uzel z první skupiny. Čím vyšší přenosovou rychlost tento sousední uzel poskytuje, tím je vyšší pravděpodobnost, že si jej uzel vybere pro odeslání paketu. Uzly si navíc udržují informace o tom, kdy odeslání paketu určitému sousedovi skončilo s chybou. Touto chybou může být ztráta z důvodu kolize nebo situace, kdy paket odeslaný určitému uzlu má nižší přenosovou rychlost než Ssetpoint . Na základě těchto informací si uzel vypočítá hodnotu, která závisí na chybách přenosu jeho sousedů. Tuto hodnotu uzel použije v případě, kdy neexistuje žádný uzel z první skupiny, kterému by mohl odeslat paket, a uzel se potřebuje rozhodnout, zda má daný paket zahodit. Uzel zahodí paket, pokud náhodně vygenerované číslo z intervalu (0,1) je větší než tato vypočítaná hodnota. Paket je tedy zahozen, pokud žádný uzel, který se nachází blíže k cílovému uzlu, není schopen 50


garantovat přenosovou rychlost Ssetpoint . Pokud ale existuje nějaká jiná cesta, která by splňovala požadavky na přenosovou rychlost, potom může být paket poslán po této cestě. Na obrázku 4.10 je znázorněno toto hledání jiné cesty. Uzel 5 by měl odeslat paket některému z uzlů, který se nachází blíže cílovému uzlu 13 (tedy uzlu 7, 9 nebo 10). Pokud ale u těchto uzlů dojde k zahlcení, nemusí již dále poskytovat dostatečně velkou přenosovou rychlost. Uzel 5 tedy odešle paket, ve kterém informuje své sousedy o své hodnotě zpoždění, kterou vypočítá jako průměr z hodnot zpoždění při přenosu z uzlu 5 uzlům 7, 9 a 10. Každý uzel, který tento paket přijme, nejdříve zjistí, zda se uzel 5 nachází blíže k cílovému uzlu 13 než on. Pokud toto neplatí (v případě uzlů 4 a 6), potom tento paket ignoruje. Uzel 3, pro který platí, že se uzel 5 nachází blíže uzlu 13, si upraví hodnotu zpoždění pro uzel 5 (na základě informací z přijatého paketu), čímž se zvýší pravděpodobnost, že pakety určené pro uzel 13 bude uzel 3 odesílat uzlu 4.

Obrázek 4.10: Hledání jiné cesty v protokolu SPEED [37] Pokud je paket určen pro skupinu uzlů (multicast), potom uzel, který jej přijme jako první uvnitř dané oblasti, nastaví paketu hodnotu TTL (time to live) s ohledem na velikost dané oblasti a potom tento paket všesměrovým vysíláním odešle všem svým sousedům. Každý uzel, který tento paket přijme a nachází se v této oblasti, sníží hodnotu TTL o 1 a paket opět odešle svým sousedům. Pokud paket přijme uzel, který se nenachází v této oblasti, tak tento paket ignoruje. Toto přeposílání paketu se opakuje, dokud uzel, který jej přijme, nezjistí, že hodnota TTL je rovna 0.

51

Kapitola 5 Implementace směrovacích protokolů 5.1

Simulátory pro bezdrátové senzorové sítě

Aby nebylo nutné při testování různých síťových protokolů a aplikací používat fyzické síťové komponenty, bylo vytvořeno mnoho síťových simulátorů, které umožňují simulovat chování těchto protokolů a aplikací v sítích, které je daný simulátor schopný modelovat. Tyto simulátory poskytují dobrý kompromis mezi cenou a přesností získaných výsledků. Různé simulátory poskytují uživatelům různé možnosti, různé způsoby testování, určitá omezení atd. Výběr vhodného simulátoru pro testování tedy záleží na konkrétních požadavcích uživatele. Existuje velké množství simulátorů, které byly vytvořeny pro simulování procesů v bezdrátových senzorových sítích. Mezi simulační nástroje používané pro bezdrátové senzorové sítě patří OMNeT++, ns-3, TOSSIM, COOJA atd.

5.2

OMNeT++

OMNeT++ [38] je rozšiřitelný, modulární, objektově orientovaný framework určený především pro vytváření síťových simulátorů. OMNeT++ není síťový simulátor, ale pouze poskytuje prostředky pro vytváření simulací. Lze jej použít pro modelování senzorových sítí, ad hoc sítí, návrh a testování hardwaru, síťových protokolů atd. Je volně dostupný pro akademické a nekomerční použití a je multiplatformní, tedy jej lze používat na různých operačních systémech (např. Windows, Linux, Mac OS X). Simulační modely jsou tvořeny moduly. Jednotlivé moduly jsou naprogramovány v jazyce C++ a vytváří hierarchickou strukturu (tedy jeden složený modul se může skládat z více jiných modulů). Základem komunikace mezi těmito moduly je zasílání zpráv. Posílání zpráv mezi jednotlivými moduly je řízeno simulačním časem. Modul může buď odeslat zprávu jinému modulu nebo může zpráva na daném modulu zůstat a plnit úlohu časovače, kdy po uplynutí definované doby jsou provedeny určité akce v tomto modulu. Definování struktury zprávy se provádí v souboru .msg, přičemž při překladu jsou automaticky vygenerovány implementační třídy C++ (soubory .cc a .h). Definice jednoduché zprávy, která obsahuje pouze informace o adrese zdrojového a cílového uzlu a počtu hopů, může vypadat 52

KAPITOLA 5. IMPLEMENTACE SMĚROVACÍCH PROTOKOLŮ

následujícím způsobem: packet MyPacket { int srcAddr; int destAddr; int hopCount; }; Struktura simulačního modelu je popisována pomocí jazyka NED (Network Descriptor). Jazyk NED lze použít pro deklaraci jednoduchých modulů, propojování modulů mezi sebou atd. Každý modul může obsahovat parametry. Tyto parametry mohou mít nastaveny výchozí hodnoty buď přímo v definici tohoto modulu nebo v konfiguračním souboru simulace (soubor omnetpp.ini). Pokud výchozí hodnoty nastaveny nejsou ani jedním z uvedených způsobů, potom je uživatel vyzván k jejich zadání pomocí dialogového okna při spuštění simulace. OMNeT++ také umožňuje zaznamenávání výsledků simulací. K tomu lze použít skaláry a vektory. Skaláry (ukládány do souboru .sca) jsou proměnné, které lze použít pro ukládání informací např. o počtu přijatých paketů, počtu odeslaných paketů, počtu hopů atd. Vektory (ukládány do souboru .vec) přidávají ke každé hodnotě ještě časové razítko udávající, kdy byl záznam této hodnoty proveden. Díky tomu je možné sledovat změny hodnoty nějaké proměnné v průběhu simulace.

5.2.1

MiXiM

MiXiM (Mixed simulator) [39] je simulátor pro OMNeT++ vytvořený pro mobilní a pevné bezdrátové sítě. Lze jej použít pro modelování bezdrátových senzorových sítí, ad hoc sítí, sítí BAN (body area network), VANET (vehicular ad hoc network) atd. Zaměřuje se spíše na nižší vrstvy síťového modelu, zejména na šíření rádiových vln, odhadování interference, podporuje mnoho komunikačních protokolů (zejména MAC protokolů) atd. MiXiM umožňuje modelování dvourozměrného i trojrozměrného prostředí. Pro simulování šíření vln je tedy možné do modelovaného prostředí umístit mnoho různých objektů (jako například dům nebo zeď). Pozice všech uzlů v síti a jejich vzájemné spojení je spravováno modulem ConnectionManager. Objekty i uzly v síti se navíc mohou pohybovat. Fyzická vrstva simulátoru MiXiM je zodpovědná zejména za přijímání a odesílání zpráv, detekci kolizí a chyb při přenosu. Skládá se ze tří částí: • BasePhyLayer – poskytuje rozhraní na linkovou vrstvu a na fyzickou vrstvu jiných uzlů, • AnalogueModel – slouží pro simulování útlumu přijatého signálu, • Decider – slouží pro oddělování signálu od šumu a demodulaci přijatých zpráv.

53


Na linkové vrstvě poskytuje MiXiM velké množství různých MAC protokolů. Podporuje standardy IEEE 802.11 a IEEE 802.15.4, dále CSMA, B-MAC atd. MiXiM také umožňuje implementaci vlastního MAC protokolu. Pro tento účel lze použít modul BaseMACLayer, který poskytuje rozhraní na fyzickou a síťovou vrstvu. Na síťové vrstvě se používají tři základní způsoby pro směrování paketů – flooding (záplava), probabilistic broadcast (pravděpodobnostní všesměrové vysílání, ve kterém jsou pakety odesílány s určitou pravděpodobností, čímž se redukuje počet paketů odeslaných uzlem) a wise route (základnová stanice odešle zprávu všem svým sousedům, všechny uzly, které tuto zprávu přijmou, zvolí základnovou stanici za svého rodiče a zprávu přepošlou všem svým sousedům, čímž se vytváří v síti stromová struktura). Kromě toho je možné implementovat vlastní směrovací protokol (s pomocí základního modulu BaseNetwLayer ). MiXiM také umožňuje modelování operací, které spotřebovávají energii uzlů. K tomu slouží modul, který přijímá zprávy (tzv. DRAW zprávy) od všech energeticky závislých zařízení v síti a vypočítává si potřebné hodnoty udávající stav baterie daného zařízení. Pro modelování energeticky závislých operací lze použít modul SimpleBattery. V následující části práce je popsána implementace protokolů SPIN-PP a SPIN-BC pro simulátor MiXiM. Pro implementaci byl použit OMNeT++ 4.3.1, který je dostupný zde [40], a simulátor MiXiM-2.3, který je dostupný zde [41].

5.3

Implementace protokolu SPIN-PP

Jak již bylo uvedeno, simulátor MiXiM používá pro směrování v senzorových sítích tři základní způsoby – záplavu, pravděpodobnostní všesměrové vysílání a wise route. Definice těchto modulů jsou v simulátoru MiXiM uloženy v adresáři \MiXiM\src\modules\netw. Pokud se uživatel rozhodne implementovat vlastní směrovací protokol, potom je třeba umístit potřebné soubory právě do tohoto adresáře. Protokol SPIN-PP (popsaný v podsekci 4.2.1), který je k dispozici na přiloženém CD, se skládá ze tří souborů – SpinPP.ned, SpinPP.h a SpinPP.cc. Soubor SpinPP.ned definuje jednoduchý modul SpinPP, který je rozšířením modulu BaseNetwLayer. BaseNetwLayer je základní modul, který poskytuje rozhraní na linkovou a aplikační vrstvu, stará se o zapouzdření paketů pro linkovou vrstvu atd. Soubor Spin.h je hlavičkový soubor pro deklaraci proměnných, struktur a podprogramů a SpinPP.cc obsahuje implementaci chování protokolu SPIN-PP (naprogramovanou v programovacím jazyce C++). Dále bude podrobněji popsáno chování algoritmu implementované v souboru SpinPP.cc. Na počátku je zavolána funkce initialize. V této funkci jsou nastaveny počáteční hodnoty proměnných pro každý uzel v síti. Mezi těmito hodnotami je i velikost paketu ADV, resp. velikost paketu DATA. Velikosti těchto paketů si může uživatel nastavit sám tak, že nastaví požadované hodnoty v souboru SpinPP.ned. Pokud žádné hodnoty v tomto souboru nastavené nejsou, nastaví se jako výchozí hodnota pro velikost paketu ADV (a tedy i paketu REQ) 16 bytů, pro velikost paketu DATA 500 bytů. Pokud uzel získá vlastním měřením nějaká data, odešle paket ADV všem svým sousedům. K tomuto úkonu slouží funkce handleUpperMsg. Tato funkce je zavolána, pokud 54


modul přijme paket z vyšší vrstvy. Jak již bylo uvedeno, paket ADV neobsahuje naměřená data, ale pouze metadata, která tato data popisují (proto je jeho velikost podstatně menší než velikost paketu DATA). SPIN nijak nespecifikuje formát těchto metadat. Jedním ze způsobů, jak lze odlišit data, která naměřily různé uzly, je použití identifikátoru uzlu pro označení původu dat (v případě, kdy uzly pokrývají různé geografické oblasti). Ve zde implementovaných protokolech (SPIN-PP, SPIN-BC) slouží pro popis dat kombinace identifikátoru uzlu (síťové adresy uzlu) a sekvenčního čísla jím odeslaného paketu (pro odlišení více paketů odeslaných stejným uzlem). Struktura paketu je definovaná v souboru SpinPkt.msg a v souborech SpinPkt_m.cc a SpinPkt_m.h, které se vygenerují při překladu. Tyto soubory jsou součástí přiloženého CD a je třeba je umístit do adresáře \MiXiM\src\modules\messages (tato struktura paketu je použita i pro implementaci protokolu SPIN-BC). Soubor SpinPkt.msg definuje strukturu paketu SpinPkt, který je rozšířením paketu NetwPkt definovaného v souboru NetwPkt.msg. Před odesláním paketu je třeba vyplnit potřebné informace v hlavičce paketu – adresu odesílajícího uzlu, adresu cílového uzlu (paket ADV je určený všem sousedům uzlu), adresu uzlu, který získal data vlastním měřením, velikost paketu a sekvenční číslo paketu. Paket je také před odesláním pojmenován (v tomto případě je jeho jméno ADV) a pomocí funkce setDownControlInfo jsou doplněny informace o MAC adrese cílového uzlu (v tomto případě se jedná o všesměrové vysílání), které bude potřebovat nižší (linková) vrstva. Pomocí funkce sendDown je poté paket odeslán nižší vrstvě. Uzel si také ještě uloží do tabulky metadata popisující jím získaná data. Pokud modul přijme paket z nižší vrstvy, potom je zavolána funkce handleLowerMsg. V této funkci jsou prováděné určité operace v závislosti na jméně přijatého paketu. Toto jméno může nabývat tří různých hodnot: • ADV – uzel zjistí, zda již má ve své tabulce uložený záznam o datech popsaných pomocí metadat tohoto paketu. Pokud záznam v tabulce již existuje, tak žádný paket neodesílá. Pokud záznam v tabulce nemá, potom si jej vytvoří a odešle paket s názvem REQ, kde cílovou adresou je adresa uzlu, od kterého přijal paket ADV. • REQ – uzel zjistí, zda je paket určený pro něj a pokud ano, odešle paket s názvem DATA uzlu, od kterého přijal paket REQ (tento paket bude mít větší velikost než paket REQ). • DATA – uzel zjistí, zda je paket určený pro něj a pokud ano, odešle paket vyšší vrstvě (pomocí funkce sendUp), poté uzel odešle paket s názvem ADV, který má menší velikost než paket DATA, všem svým sousedům (tímto způsobem nabízí všem svým sousedům data, která právě získal). Poslední funkcí je funkce finish. Tato funkce je volána po ukončení simulace a ukládá hodnoty uvedených sledovaných proměnných (skalárů, vektorů) do souboru.

55


5.4

Implementace protokolu SPIN-BC

Protokol SPIN-BC (popsaný v podsekci 4.2.1) je podobný protokolu SPIN-PP. Jeho hlavní rozdíl je ale v tom, že každý uzel odesílá všechny typy paketů všem svým sousedům. Protokol SPIN-BC (k dispozici na přiloženém CD) se také skládá ze tří souborů – SpinBC.ned, SpinBC.h a SpinBC.cc. Funkce implementované v souboru SpinBC.cc jsou podobné těm, které jsou implementované v souboru SpinPP.cc. Uzel si ale navíc musí ukládat i další informace, např. zda již někdy odeslal svým sousedům určitý paket DATA, zda již dříve přijal paket REQ od některého ze svých sousedů a tudíž již sám nemusí odesílat paket REQ s žádostí o stejná data atd. Pokud nějaký uzel získá vlastním měřením nějaká data, odešle všem svým sousedům paket ADV pomocí funkce handleUpperMsg a uloží si do tabulky metadata popisující jím získaná data (dvojice tvořená síťovou adresou uzlu a sekvenčním číslem paketu) a informaci o tom, že tato data vlastní, ale dosud neodeslal paket DATA. Při přijetí paketu z nižší vrstvy je zavolána funkce handleLowerMsg. Na základě jména přijatého paketu jsou prováděné různé operace. Pokud uzel přijal paket ADV, potom prohledá svoji tabulku a zjistí, zda již má v tabulce záznam o tomto paketu. Pokud ano, žádný paket neodesílá. Pokud ne, potom si uloží do tabulky informace o paketu (adresu uzlu, který naměřil data, a sekvenčním číslo paketu) a informaci o tom, že přijal paket ADV. V tomto okamžiku by měl uzel odeslal paket REQ, nicméně je vhodné, aby uzel počkal určitou dobu a paket REQ odeslal pouze v případě, že během této doby nepřijme paket REQ žádající stejná data od některého ze svých sousedů. To lze vyřešit pomocí funkce scheduleAt, jejímž parametrem je náhodně vygenerovaný časový údaj, který lze získat vygenerováním náhodného čísla z určitého intervalu a jeho přičtením k výsledku funkce simTime, která vrací aktuální čas simulace. Během této doby uzel dále přijímá jiné pakety a pokud přijme paket REQ žádající stejná data, o která chce požádat on sám, uloží si do tabulky informaci o tom, že již paket REQ odesílat nemusí. Po uplynutí doby určené funkcí scheduleAt je zavolána funkce handleSelfMsg, ve které uzel znovu zpracovává přijatý paket ADV a zjistí, zda je třeba odesílat paket REQ. Pokud ano, odešle paket REQ všem svým sousedům. Pokud uzel přijme paket REQ, prohledá svoji tabulku. Pokud zjistí, že vlastní požadovaná data a dosud ani jednou neodeslal paket DATA, tak odešle paket DATA všem svým sousedům. V opačném případě paket DATA neodešle. Pokud uzel z tabulky zjistí, že čeká na uplynutí doby (určené funkcí scheduleAt) a sám chce o tato data také požádat, uloží si v tabulce informaci o tom, že již paket REQ odesílat nemusí. Pokud uzel přijme paket DATA, prohledá tabulku a zjistí, zda již data vlastní. Pokud ne, odešle data vyšší vrstvě, upraví si příslušné informace v tabulce a odešle paket ADV nabízející tato data všem svým sousedům.

56

Kapitola 6 Simulace protokolů 6.1

Parametry simulací

Nastavení a parametry potřebné pro simulace ve frameworku OMNeT++ se nastavují v konfiguračním souboru omnetpp.ini. V tomto souboru je podrobně popsáno celé simulační prostředí. V následující části práce jsou stručně popsány některé parametry, které jsou významné pro simulaci zde implementovaných protokolů: • parametry simulace: – playgroundSizeX, playgroundSizeY – rozměry prostředí, ve kterém jsou rozmístěny uzly (hodnota uvedená u playgroundSizeZ se použije pouze v případě, pokud je simulační prostředí trojrozměrné), – numNodes – počet uzlů nacházejících se v daném prostředí, • parametry kanálu: – – – –

connectionManager.pMax – maximální síla signálu používaná v síti, connectionManager.sat – prahová hodnota útlumu signálu, connectionManager.alpha – koeficient útlumu signálu, connectionManager.carrierFrequency – minimální nosná frekvence kanálu,

• parametry linkové vrstvy: – node[*].nic.mac.queueLength – velikost fronty (maximální počet paketů určených pro odeslání ve frontě), – node[*].nic.mac.headerLength – velikost hlavičky paketu na linkové vrstvě (v bitech), – node[*].nic.mac.bitrate – přenosová rychlost, – node[*].nic.mac.useMACAcks – používání potvrzovacích paketů (ACK), – node[*].nic.mac.ackLength – velikost potvrzovacích paketů (v bitech), – node[*].nic.mac.macMaxFrameRetries – maximální počet opakovaných přenosů, – node[*].nic.mac.macAckWaitDuration – délka doby čekání na potvrzení, 57

KAPITOLA 6. SIMULACE PROTOKOLŮ

• parametry aplikační vrstvy: – – – – –

node[*].applicationType – typ aplikační vrstvy, appl.trafficType – typ přenosu (periodický, rovnoměrný nebo exponenciální), appl.broadcastPackets – odesílání paketů všesměrovým vysíláním, appl.nbPackets – počet paketů odeslaných aplikační vrstvou, appl.initializationTime – minimální čas před odesláním prvního paketu,

• parametry síťové vrstvy: – node[*].networkType – typ síťové vrstvy, – node[*].netwl.headerLength – velikost hlavičky paketu (v bitech), • parametry pro pohyb uzlů: – node[*].mobilityType – pohyblivost uzlů, – node[0].mobility.initialX, node[0].mobility.initialY – souřadnice uzlu 0 (případně node[0].mobility.initialZ pro trojrozměrné prostředí), tímto způsobem lze definovat souřadnice všech uzlů.

6.2

Simulace 1

Součástí přiloženého CD jsou také ukázky možného nastavení konfiguračních souborů omnetpp.ini pro simulaci protokolů SPIN-PP a SPIN-BC. V adresáři simulation_1 se nachází dva adresáře (sim_1 a sim_2 ). Tyto adresáře je třeba překopírovat do adresáře \MiXiM\examples. V těchto adresářích se nachází soubory pro vytvoření simulačního prostředí. Soubory v adresáři sim_1 slouží k vytvoření simulačního prostředí, ve kterém uzly používají pro směrování protokol SPIN-PP, adresář sim_2 obsahuje soubory vytvářející stejné prostředí (se stejnými parametry), ale uzly používají protokol SPIN-BC. Jak již bylo uvedeno, základním konfiguračním souborem je soubor omnetpp.ini, který je součástí obou adresářů a s výjimkou použitého směrovacího protokolu vytváří identické simulační prostředí. Pro vytvářené prostředí byly použity následující hodnoty: **.playgroundSizeX = 300m **.playgroundSizeY = 300m **.numNodes = 3 V tomto prostředí se tedy nachází tři uzly (tyto uzly se nepohybují a jejich souřadnice jsou uvedeny na konci souboru omnetpp.ini ). Celé prostředí se nachází na ploše o rozměrech 300 x 300 metrů. V souboru omnetpp.ini je také uvedená hodnota pro playgroundSizeZ, nicméně vzhledem k tomu, že vytvářené prostředí je dvourozměrné, není tato hodnota již nijak dále využívána. Pro přístup k přenosovému médiu je používán protokol CSMA. Pro aplikační vrstvu je použito následující nastavení:

58


**.node[*].applicationType = "SensorApplLayer" **.appl.trafficType = "periodic" **.appl.broadcastPackets = true **.appl.nbPackets = 3 **.appl.initializationTime = 10s Na aplikační vrstvě je tedy používán modul SensorApplLayer, který periodicky odesílá pakety síťové vrstvě. Počet těchto paketů je tři, což znamená, že každý uzel v této simulaci vytvoří na úrovni aplikační vrstvy tři pakety, které chce odeslat ostatním uzlům v síti. Před vytvořením prvního paketu je nutné počkat minimálně 10 sekund. Soubor omnetpp.ini obsahuje mnoho dalších parametrů, které lze měnit pro potřeby konkrétních simulací. Samotnou simulaci lze spustit následujícím způsobem. Po spuštění IDE frameworku OMNeT++ je třeba nalézt soubor \MiXiM\examples\sim_1\omnetpp.ini. Na tento soubor je třeba kliknout pravým tlačítkem myši a v otevřené nabídce vybrat Run As a následně Run Configurations. V nově otevřeném okně je třeba pravým tlačítkem myši kliknout na OMNeT++ Simulation a vybrat položku New. Po kliknutí na tlačítko Run se otevře grafické uživatelské rozhraní Tkenv, ve kterém lze spouštět simulace. Samotnou simulaci lze spustit kliknutím na tlačítko Run (příp. výběrem položky Run v nabídce Simulate), resp. Fast run pro zrychlený průběh simulace. Probíhající simulaci lze zastavit kliknutím na tlačítko Stop. Po ukončení simulace lze v nabídce Simulate kliknout na položku Call finish() for All Modules. Tím se zavolá funkce finish a výsledky této simulace se uloží do adresáře results nacházejícího se ve stejném adresáři jako soubor omnetpp.ini. Tímto způsobem lze spouštět i všechny ostatní simulace nacházející se na přiloženém CD. Součástí CD jsou i soubory s výsledky simulací, které se nachází v adresáři results u příslušných simulací. Mezi sledovanými hodnotami na síťové vrstvě je zde počet odeslaných paketů ADV (nbADVPacketsSent), počet odeslaných paketů REQ (nbREQPacketsSent), počet odeslaných paketů DATA (nbDATAPacketsSent), počet přijatých paketů ADV (nbADVPacketsReceived ), počet přijatých paketů REQ (nbREQPacketsReceived ) a počet přijatých paketů DATA (nbDATAPacketsReceived ). V uvedeném simulačním prostředí se tedy nachází tři uzly, přičemž aplikační vrstva každého z těchto uzlů odešle dohromady tři pakety. Po ukončení simulace při použití protokolu SPIN-PP byly hodnoty uvedených proměnných zaznamenané v souboru \simulation_1\sim_1\results\General-0.sca následující: scalar scalar scalar scalar scalar scalar scalar scalar

Sim_1.node[0].netwl Sim_1.node[0].netwl Sim_1.node[0].netwl Sim_1.node[0].netwl Sim_1.node[0].netwl Sim_1.node[0].netwl Sim_1.node[0].appl Sim_1.node[0].appl

nbADVPacketsSent nbADVPacketsReceived nbREQPacketsSent nbREQPacketsReceived nbDATAPacketsSent nbDATAPacketsReceived nbPacketsSent nbPacketsReceived

59

9 18 6 6 6 6 3 6


scalar scalar scalar scalar scalar scalar scalar scalar



9 18 6 6 6 6 3 6




9 18 6 6 6 6 3 6

Na aplikační vrstvě tedy každý uzel vytvořil 3 pakety, které odeslal síťové vrstvě, a ze síťové vrstvy přijal 6 paketů, které získal od ostatních (dvou) uzlů v síti. Na síťové vrstvě každý uzel odeslal nižší vrstvě 9 paketů ADV, 6 paketů REQ a 6 paketů DATA a přijal z nižší vrstvy 18 paketů ADV, 6 paketů REQ a 6 paketů DATA. Po ukončení simulace při použití protokolu SPIN-BC byly hodnoty proměnných zaznamenané v souboru \simulation_1\sim_2\results\General-0.sca následující: scalar scalar scalar scalar scalar scalar scalar scalar



9 18 6 11 4 8 3 6




9 18 6 11 4 8 3 6

60





9 18 5 12 4 8 3 6

Na aplikační vrstvě tedy uzly odeslaly i přijaly stejný počet paketů jako při použití protokolu SPIN-PP. Na síťové vrstvě jednotlivé uzly odeslaly méně paketů REQ a paketů DATA ve srovnání s protokolem SPIN-PP. Na druhou stranu ale u protokolu SPIN-BC je počet přijatých paketů REQ a paketů DATA u jednotlivých uzlů vyšší než u protokolu SPIN-PP.

6.3

Simulace 2

V adresáři simulation_2 na přiloženém CD se nachází další dva adresáře (sim_3 a sim_4 ), které obsahují soubory pro vytvoření jiného simulačního prostředí. V tomto simulačním prostředí se nachází 20 uzlů na ploše o rozměrech 400 x 400 metrů. Souřadnice těchto uzlů jsou opět uvedeny na konci souboru omnetpp.ini. Na aplikační vrstvě je opět použitý modul SensorApplLayer. Každý uzel pomocí tohoto modulu tentokrát odesílá nižší vrstvě 10 paketů. Vzhledem k většímu množství uzlů se na linkové vrstvě používají potvrzovací pakety. Pokud uzel nepřijme potvrzovací paket během určité definované doby, pokusí se nejvýše třikrát o opakování přenosu tohoto paketu. Pro přístup k přenosovému médiu je opět používán protokol CSMA. Hodnoty proměnných po ukončení simulace jsou zaznamenané na přiloženém CD v souboru \simulation_2\sim_3\results\General-0.sca (při použití protokolu SPIN-PP), resp. v souboru \simulation_2\sim_4\results\General-0.sca (při použití protokolu SPIN-BC). Celkový počet přenesených paketů je uvedený v následující tabulce (hodnota proměnné nbPacketsReceived udává počet přijatých paketů na úrovni aplikační vrstvy). Proměnná SPIN-PP SPIN-BC nbADVPacketsSent 3 751 3 730 nbADVPacketsReceived 17 128 17 392 nbREQPacketsSent 3 591 3 238 nbREQPacketsReceived 3 578 14 969 nbDATAPacketsSent 3 578 2 722 nbDATAPacketsReceived 3 551 13 601 nbPacketsReceived 3 551 3 530

61


6.4

Diskuse výsledků

Vzhledem k tomu, že pro první simulaci (popsané v sekci 6.2) bylo vytvořeno velmi jednoduché simulační prostředí tvořené pouze třemi uzly, budou v následující části práce diskutovány pouze výsledky druhé simulace (popsané v sekci 6.3). Při použití protokolu SPIN-PP bylo tedy během této simulace odesláno více paketů REQ než při použití protokolu SPIN-BC. To je způsobené tím, že pokud uzel (při použití protokolu SPIN-BC) přijme paket REQ od jiného uzlu požadující data, která chce získat i on sám, nemusí již svoji žádost odesílat. Z podobného důvodu bylo během simulace při použití protokolu SPIN-BC odesláno méně paketů DATA (uzel odesílá data všesměrovým vysíláním, tudíž stačí, aby každá data odeslal pouze jednou po přijetí první žádosti). Na druhou stranu ale u protokolu SPIN-BC bylo dohromady všemi uzly přijato mnohem více paketů REQ a paketů DATA než u protokolu SPIN-PP. To je způsobené tím, že pakety odesílané všesměrovým vysíláním jsou přijaty všemi sousedy uzlu. Není jednoduché rozhodnout, který z protokolů je vhodnější použít pro uvedenou simulaci. Odesílání všech paketů všesměrovým vysíláním u protokolu SPIN-BC vyžaduje větší spotřebu energie všech sousedních uzlů, které musí tyto pakety přijmout. Na druhou stranu je ale dostačující, aby každý uzel odeslal paket DATA pouze jednou, což je výhodné zejména proto, že tento paket má podstatně větší velikost (v této simulaci byla velikost tohoto paketu nastavena na 500 bytů) než pakety ADV a REQ (každý o velikosti 16 bytů). Díky tomu i celkový čas simulace (měřený do doby, kdy uzly již neměly žádné další pakety určené k odeslání) při použití protokolu SPIN-BC byl menší (simulace skončila v čase T = 626) než při použití protokolu SPIN-PP (simulace skončila v čase T = 951). Delší čas simulace u protokolu SPIN-PP je způsobený také tím, že byly na úrovni linkové vrstvy používány potvrzovací pakety. Ty je vhodné používat proto, že pakety REQ a DATA jsou vždy odesílány na adresu konkrétního uzlu a může dojít k jejich ztrátě. Při použití protokolu SPIN-PP bez použití potvrzovacích paketů byl čas simulace T = 485 (tedy mnohem menší než celkový čas simulace s použitím potvrzovacích paketů), nicméně počet přijatých paketů na úrovni aplikační vrstvy byl mnohem menší (např. při spuštění simulace s použitím potvrzovacích paketů přijal uzel 0 na úrovni aplikační vrstvy 182 paketů, ale při spuštění simulace bez použití potvrzovacích paketů přijal pouze 81 paketů). Tyto potvrzovací pakety se používají pouze v případě, kdy je v síti adresován jeden konkrétní uzel (unicast). Při použití protokolu SPIN-BC tedy uzly potvrzovací pakety nepoužívají, protože všechny pakety jsou odesílány všesměrovým vysíláním. Výsledky uvedené simulace jsou rovněž ovlivňovány hodnotami parametrů nic.mac.macAckWaitDuration (udává délku doby čekání na potvrzovací paket) a nic.mac.macMaxFrameRetries (udává maximální počet opakování přenosu paketu v případě nepřijetí potvrzovacího paketu během doby nastavené pomocí parametru nic.mac.macAckWaitDuration). Při simulaci protokolů je důležité vhodné nastavení parametrů simulačního prostředí. Jedním z těchto důležitých parametrů je koeficient útlumu signálu (v souboru omnetpp.ini se nastavuje pomocí parametru connectionManager.alpha). Pro uvedenou simulaci byl použitý koeficient 3.0, přičemž platí, že se snižováním hodnoty tohoto koeficientu se zvyšuje počet uzlů, kterým je daný uzel schopný odesílat pakety (tedy zvyšuje se dosah uzlu). 62


Při změně hodnoty koeficientu v souboru omnetpp.ini je třeba nastavit stejnou hodnotu i v souboru config.xml, který se nachází ve stejném adresáři jako soubor omnetpp.ini. Dalším důležitým parametrem ovlivňujícím výsledek uvedené simulace je velikost fronty na linkové vrstvě. Její velikost je určena hodnotou parametru nic.mac.queueLength v souboru omnetpp.ini, přičemž tato hodnota udává počet paketů určených pro odeslání, které lze umístit do fronty. Pro uvedenou simulaci byla použita velikost 200, nicméně změnou této hodnoty lze dosáhnout výrazně jiných výsledků. Při spuštění této simulace s použitím protokolu SPIN-BC a nastavením velikosti fronty na hodnotu 200 přijal uzel 0 na úrovni aplikační vrstvy celkem 180 paketů (stejný počet paketů přijal i při použití fronty o velikosti 300), při použití fronty o velikosti 100 přijal uzel 168 paketů a při použití fronty o velikosti 30 přijal uzel pouze 108 paketů. Velikost fronty je tedy nutné nastavit s ohledem na očekávanou zátěž v síti. V uvedené simulaci jsou všechny uzly nepohyblivé, tedy parametr mobilityType je nastavený na StationaryMobility. Pokud by bylo cílem vytvořit simulační prostředí, ve kterém se uzly mohou pohybovat, potom by bylo třeba nastavit hodnotu tohoto parametru v souboru omnetpp.ini na ConstSpeedMobility. Rychlost pohybu uzlů lze poté nastavit pomocí parametru mobility.speed.

63

Kapitola 7 Závěr Cílem této diplomové práce bylo vypracování přehledu komunikačních protokolů pro bezdrátové senzorové sítě a implementace dvou směrovacích protokolů pro simulátor MiXiM. V první části práce jsou nejdříve popisovány protokoly pro řízení přístupu k médiu. Tyto protokoly lze rozdělit do dvou skupin. První skupinou jsou protokoly založené na soupeření, které jsou založené na tom, že jednotlivé uzly mezi sebou soupeří o přístup ke sdílenému přenosovému médiu. Druhou skupinou jsou protokoly založené na plánu. Ty každému uzlu přidělují časový díl, během kterého může daný uzel vysílat nebo přijímat pakety, což umožňuje zabránění vzniku kolize. V další části práce jsou popisovány protokoly používané pro směrování v bezdrátových senzorových sítích. Směrování představuje jeden z hlavních problémů v bezdrátových senzorových sítích a již bylo navrženo velké množství různých algoritmů pro jeho řešení. Mezi hlavní problémy, které je nutné řešit při návrhu směrovacích protokolů, patří omezená energie uzlů, adresování uzlů (v prostředí s velkým počtem uzlů často není možné přidělovat každému uzlu jedinečnou adresu) a škálovatelnost. Volba vhodného směrovacího protokolu také závisí na konkrétní aplikaci. V sítích, kde je úkolem monitorovat podmínky okolního prostředí a periodicky odesílat získaná data základnové stanici, je třeba použít jiné protokoly než v sítích, kde jsou data odesílána základnové stanici pouze v případě výskytu nějaké události (např. pokud teplota prostředí přesáhla určitou definovanou hodnotu). Protokoly používané v bezdrátových senzorových sítích bývají často rozdělovány do tří skupin – protokoly pro ploché směrování (všechny uzly v síti jsou si rovny a používají stejné algoritmy pro směrování paketů), hierarchické protokoly (některé uzly jsou nadřazené jiným, používají složitější algoritmy, řídí komunikaci v určité části sítě atd.) a protokoly založené na umístění uzlů (každý uzel je adresován na základě svého umístění, které lze získat např. pomocí systému GPS). Vzhledem k tomu, že při návrhu těchto protokolů je často velmi složité jejich testování na reálných senzorových uzlech, byla navržena řada síťových simulátorů umožňujících chování těchto protokolů simulovat. Jedním z těchto simulátorů je MiXiM vytvořený pro framework OMNeT++. Poslední část práce je věnována implementaci dvou směrovacích protokolů (SPIN-PP a SPIN-BC) pro tento simulátor a jejich porovnání z hlediska počtu paketů přenesených v síti. Pro testování uvedených protokolů byly vytvořeny dvě simu64

KAPITOLA 7. ZÁVĚR

lační prostředí pro simulaci chování těchto protokolů. V prvním vytvořeném simulačním prostředí se nachází tři uzly, přičemž každý z těchto uzlů vytvoří na úrovni aplikační vrstvy tři pakety, které postupně odesílá svým sousedům. Ve druhém simulačním prostředí se nachází dvacet uzlů a každý z těchto uzlů vytvoří deset paketů, které odesílá svým sousedům. V obou těchto simulačních prostředích byl nejdříve simulován přenos paketů s použitím protokolu SPIN-PP a poté s použitím protokolu SPIN-BC. Výsledky simulací při použití protokolu SPIN-PP a SPIN-BC záleží na hodnotách parametrů použitých pro vytvářené simulační prostředí. K nastavení hodnot těchto parametrů se v simulátoru MiXiM používá konfigurační soubor omnetpp.ini, který popisuje celé simulační prostředí, obsahuje informace o modulech použitých na úrovni aplikační vrstvy, na úrovni síťové vrstvy atd. Změnou hodnot parametrů nastavených v tomto souboru lze výrazně ovlivnit výsledky simulací. Tyto parametry mohou například určovat, zda budou v síti používány potvrzovací pakety (jejich použitím lze zvýšit úspěšnost doručování paketů, nicméně za cenu delšího času simulace a větší spotřeby energie uzlů), mohou určovat velikost hlaviček paketů, velikost fronty na linkové vrstvě, do které se ukládají pakety určené pro odeslání, přenosovou rychlost, celkový počet paketů odeslaných uzly na úrovni aplikační vrstvy, maximální sílu signálu používaného v síti, koeficient útlumu signálu atd. Na základě výsledků uvedených simulací je zřejmé, že v sítích používajících protokol SPIN-BC uzly zpravidla odesílají méně paketů REQ a méně paketů DATA než v sítích používajících protokol SPIN-PP (díky tomu, že všechny pakety v sítích používajících protokol SPIN-BC jsou odesílány všesměrovým vysíláním). To je výhodné zejména proto, že velikost paketu DATA, který obsahuje požadovaná data, je mnohem větší než velikost paketu REQ, který obsahuje pouze metadata, která tato data popisují. Na druhou stranu ale nevýhodou protokolu SPIN-BC je, že pakety odesílané všesměrovým vysíláním vyžadují větší spotřebu času a energie všech sousedních uzlů, které musí tyto pakety přijímat (uzly při použití protokolu SPIN-BC musí přijmout více paketů REQ a DATA než při použití protokolu SPIN-PP). Změnou hodnot parametrů v souboru omnetpp.ini (např. zvětšením velikosti fronty na linkové vrstvě, zvýšením koeficientu útlumu signálu atd.) lze výrazně ovlivnit počet přijatých a odeslaných paketů u jednotlivých uzlů, nicméně opět zpravidla platí, že při použití protokolu SPIN-PP budou uzly přijímat méně paketů REQ a DATA a odesílat více těchto paketů než při použití protokolu SPIN-BC. Pro simulaci uvedených protokolů byl vybrán simulátor MiXiM. Tento simulátor, vytvořený pro framework OMNeT++, se zaměřuje na nižší vrstvy síťového modelu. Poskytuje moduly, které umožňují detailně simulovat šíření rádiových vln, odhadování interference, pohyblivost uzlů, spotřebu energie uzlů atd. Rovněž poskytuje i velké množství MAC protokolů na linkové vrstvě. Na druhou stranu se ale již méně zaměřuje na síťovou vrstvu a směrování paketů. Pro tyto účely nabízí pouze tři způsoby směrování – flooding (záplavu), probabilistic broadcast (pravděpodobnostní všesměrové vysílání) a wise route. Poskytuje nicméně uživateli prostředky umožňující implementaci vlastního směrovacího protokolu (k tomu lze využít základní modul BaseNetwLayer ). Díky modulární struktuře simulátoru MiXiM lze navíc poměrně snadno implementovat také vlastní MAC protokol, vlastní modul pro simulování útlumu přenášeného signálu atd.

65

Seznam použité literatury [1] Wireless sensor network. Dostupné na URL: http://en.wikipedia.org/wiki/Wireless_sensor_network (prosinec 2013). [2] Holger, K., Willig, A. Protocols and Architectures for Wireless Sensor Networks. 1. vydání. Wiley, 2005. [3] Physical Layer and Modulation. Dostupné na URL: http://polaris.umuc.edu/~ibojanov/GSMT/TLMN645/Lecture Notes/Lecture Notes 03.htm (prosinec 2013). [4] Ye, W., Heidemann, J., Estrin, D. An Energy-Efficient MAC Protocol for Wireless Sensor Networks. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002), vol. 3, pages 1567–1576, 2002. [5] van Dam, T., Langendoen, K. An Adaptive Energy-Efficient MAC Protocol for Wireless Sensor Networks. In Proceedings of the 1st international conference on Embedded networked sensor systems (SenSys ’03), pages 171–180, 2003. [6] Polastre, J., Hill, J., Culler, D. Versatile Low Power Media Access for Wireless Sensor Networks. In Proceedings of the 2nd international conference on Embedded networked sensor systems (SenSys ’04), pages 95–107, 2004. [7] Buettner, M., Yee, G. V., Anderson, E., Han, R. A Short Preamble MAC Protocol for Duty-Cycled Wireless Sensor Networks. In Proceedings of the 4th international conference on Embedded networked sensor systems (SenSys ’06), pages 307–320, 2006. [8] El-Hoiydi, A., Decotignie, J.-D. WiseMAC: An Ultra Low Power MAC Protocol for Multi-hop Wireless Sensor Networks. In Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS 2004), pages 18–31, 2004. [9] Sun, Y., Gurewitz, O., Johnson, D. B. RI-MAC: A Receiver-Initiated Asynchronous Duty Cycle MAC Protocol for Dynamic Traffic Loads in Wireless Sensor Networks. In Proceedings of the 6th ACM conference on Embedded network sensor systems (SenSys ’08), pages 1–14, 2008. 66

SEZNAM POUŽITÉ LITERATURY

[10] Tang, L., Sun, Y., Gurewitz, O., Johnson, D. B. PW-MAC: An Energy-Efficient Predictive-Wakeup MAC Protocol for Wireless Sensor Networks. In Proceedings of the 30th IEEE International Conference on Computer Communications (INFOCOM 2011), pages 1305–1313, 2011. [11] Zheng, T., Radhakrishnan, S., Sarangan, V. PMAC: An adaptive energy-efficient MAC protocol for Wireless Sensor Networks. In Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS ’05), pages 65–72, 2005. [12] Heinzelman, W. R., Chandrakasan, A., Balakrishnan, H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks. In Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS ’00), vol. 8, pages 174–185, 2000. [13] Sohrabi, K., Gao, J., Ailawadhi, V., Pottie, G. J. Protocols for Self-Organization of a Wireless Sensor Network. In IEEE Personal Communications, vol. 7, pages 16–27, 2000. [14] Rajendran, V., Obraczka, K., Garcia-Luna-Acevez, J. J. Energy-Efficient, CollisionFree Medium Access Control for Wireless Sensor Networks. In Proceedings of the 1st international conference on Embedded networked sensor systems (SenSys ’03), pages 181–192, 2003. [15] Coleri, S., Puri, A., Varaiya, P. PEDAMACS: Power efficient and delay aware medium access protocol for sensor networks. In IEEE Transactions on Mobile Computing, vol. 5, pages 920–930, 2006. [16] Lu, G., Krishnamachari, B., Raghavendra, C. S. An Adaptive Energy-Efficient and Low-Latency MAC for Data Gathering in Wireless Sensor Networks. In Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS ’04), pages 3091–3098, 2004. [17] Akyildiz, I. F., Vuran, M. C. Wireless Sensor Networks. 1. vydání. Wiley, 2010. [18] Kulik, J., Heinzelman, W., Balakrishnan, H. Negotiation-Based Protocols for Disseminating Information in Wireless Sensor Networks. In Wireless Networks - Selected Papers from Mobicom ’99, vol. 8, pages 169–185, 2002. [19] Intanagonwiwat, C., Govindan, R., Estrin, D. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. In Proceedings of the 6th annual international conference on Mobile computing and networking (MobiCom ’00), pages 56–67, 2000. [20] Braginsky, D., Estrin, D. Rumor Routing Algorithm For Sensor Networks. In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications (WSNA ’02), pages 22–31, 2002.

67


[21] Schurgers, C., Srivastava, M. B. Energy Efficient Routing in Wireless Sensor Networks. In Proceedings of IEEE Military Communication Conference (MILCOM 2001), pages 357–361, 2001. [22] Ye, F., Chen, A., Lu, S., Zhang, L. A Scalable Solution to Minimum Cost Forwarding in Large Sensor Networks. In Proceedings of the 10th International Conference on Computer Communications and Networks (ICCCN), pages 304–309, 2001. [23] Yao, Y., Gehrke, J. The Cougar Approach to In-Network Query Processing in Sensor Networks. In ACM SIGMOD Record, vol. 31, pages 9–18, 2002. [24] Sadagopan, N., Krishnamachari, B., Helmy, A. The ACQUIRE Mechanism for Efficient Querying in Sensor Networks. In Proceedings of the 1st IEEE International Workshop on Sensor Network Protocols and Applications (SNPA ’03), pages 149–155, 2003. [25] Chu, M., Haussecker, H., Zhao, F. Scalable Information-Driven Sensor Querying and Routing for ad hoc Heterogeneous Sensor Networks. In International Journal of High Performance Computing Applications, vol. 16, pages 293–313, 2002. [26] Shah, R. C., Rabaey, J. M. Energy Aware Routing for Low Energy Ad Hoc Sensor Networks. In Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), vol. 1, pages 350–355, 2002. [27] Lindsey, S., Raghavendra, C. S. PEGASIS: Power-Efficient Gathering in Sensor Information Systems. In Proceedings of IEEE Aerospace Conference, vol. 3, pages 1125–1130, 2002. [28] Lindsey, S., Raghavendra, C., Sivalingam, K. Data Gathering in Sensor Networks using the Energy*Delay Metric. In Proceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS ’01), pages 2001–2008, 2001. [29] Manjeshwar, A., Agrawal, D. P. TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks. In Proceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS ’01), pages 2009–2015, 2001. [30] Manjeshwar, A., Agrawal, D. P. APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks. In Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS ’02), pages 195–202, 2002. [31] Subramanian, L., Katz, R. H. An Architecture for Building Self-Configurable Systems. In Proceedings of the 1st Annual Workshop on Mobile and Ad Hoc Networking and Computing (MobiHOC 2000), pages 63–73, 2000.

68


[32] Xu, Y., Heidemann, J., Estrin, D. Geography-informed Energy Conservation for Ad Hoc Routing. In Proceedings of the 7th annual international conference on Mobile computing and networking (MobiCom ’01), pages 70–84, 2001. [33] Yu, Y., Govindan, R., Estrin, D. Geographical and Energy Aware Routing: a recursive data dissemination protocol for wireless sensor networks. In UCLA Computer Science Department Technical Report, UCLA-CSD TR-01-0023, 2001. [34] Rodoplu, V., Meng, T. H. Minimum Energy Mobile Wireless Networks. In IEEE Journal of Selected Areas on Communication, vol. 17, pages 1333–1344, 1999. [35] Li, L., Halpern, J. Y. Minimum-Energy Mobile Wireless Networks Revisited. In IEEE International Conference on Communications (ICC 2001), vol. 1, pages 278–283, 2001. [36] Chen, B., Jamieson, K., Balakrishnan, H., Morris, R. SPAN: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks. In Wireless Networks, vol. 8, pages 481–494, 2002. [37] He, T., Stankovic, J. A., Lu, C., Abdelzaher, T. SPEED: A Stateless Protocol for RealTime Communication in Sensor Networks. In Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS ’03), pages 46–55, 2003. [38] OMNeT++. Dostupné na URL: http://omnetpp.org (prosinec 2013). [39] MiXiM. Dostupné na URL: http://mixim.sourceforge.net (prosinec 2013). [40] OMNeT++. Downloads of the OMNeT++ simulation platform. Dostupné na URL: http://omnetpp.org/component/docman/cat_view/17-downloads/1-omnet-releases (prosinec 2013). [41] MiXiM - Browse Files at SourceForge.net. Dostupné na URL: http://sourceforge.net/projects/mixim/files (prosinec 2013). [42] OMNeT++ documentation and tutorials. Dostupné na URL: http://www.omnetpp.org/documentation (prosinec 2013). [43] Installation – mixim. Dostupné na URL: http://sourceforge.net/apps/trac/mixim/wiki/Installation (prosinec 2013).

69

Příloha A Instalace frameworku OMNeT++ a simulátoru MiXiM Instalace frameworku OMNeT++ je popsána zde [42]. Pro operační systémy Windows (podporovanými jsou Windows XP, Windows 7 a Windows 8) je třeba rozbalit stažený archiv do adresáře, jehož celá cesta neobsahuje mezery (tedy neměl by se např. nacházet v adresáři Program Files). Po rozbalení je třeba spustit soubor mingwenv.cmd a zadat následující příkazy: $ ./configure $ make Následně lze spustit IDE frameworku OMNeT++ příkazem: $ omnetpp Po otevření IDE je ještě třeba nainstalovat simulátor MiXiM (popsáno zde [43]). To lze provést kliknutím na položku Import v nabídce File. V otevřeném okně je třeba vybrat Existing Projects into Workspace, kliknout na tlačítko Next, v dalším okně do pole Select archive file vložit stažený archiv simulátoru MiXiM a poté kliknout na tlačítko Finish. Poté je třeba kliknout pravým tlačítkem myši na vytvořený projekt MiXiM a v otevřené nabídce vybrat Build Project.

70

Příloha B Obsah přiloženého CD Součástí práce je přiložené CD, které obsahuje elektronickou verzi této diplomové práce a také následující adresáře: • SPIN-PP – implementace protokolu SPIN-PP, obsahuje dva adresáře: – netw – obsahuje soubory SpinPP.ned, SpinPP.h a SpinPP.cc, které je třeba nakopírovat do adresáře \MiXiM\src\modules\netw, – messages – obsahuje soubory SpinPkt.msg, SpinPkt_m.h a SpinPkt_m.cc, které je třeba nakopírovat do adresáře \MiXiM\src\modules\messages, • SPIN-BC – implementace protokolu SPIN-BC, obsahuje dva adresáře: – netw – obsahuje soubory SpinBC.ned, SpinBC.h a SpinBC.cc, které je třeba nakopírovat do adresáře \MiXiM\src\modules\netw, – messages – obsahuje soubory SpinPkt.msg, SpinPkt_m.h a SpinPkt_m.cc, které jsou stejné jako pro protokol SPIN-PP, • simulation_1 – obsahuje adresáře sim_1 (pro protokol SPIN-PP) a sim_2 (pro protokol SPIN-BC), které lze použít pro simulaci uvedených protokolů a které je třeba nakopírovat do adresáře \MiXiM\examples, • simulation_2 – obsahuje adresáře sim_3 (pro protokol SPIN-PP) a sim_4 (pro protokol SPIN-BC), které obsahují soubory pro druhou simulaci uvedených protokolů a které je třeba nakopírovat do adresáře \MiXiM\examples.

71

Komunikační protokoly v bezdrátových senzorových sítích

Recommend Documents