Diz 37 cz

Z DCEwiki
Skočit na navigaci Skočit na vyhledávání

Distribuované a Real-time řízení toku dat v senzorových sítích

Autor: Jiří Trdlička


Disertační práce 2012

Stáhnout práci v PDF

Tato práce je zaměřena na distribuované a real-time routovací algoritmy pro senzorové sítě. Práce se soustředí na matematicky odvozené algoritmy, které jsou založeny na teorii konvexní optimalizace a jsou schopny nalézt optimální řešení ve smyslu spotřeby energie. Práce se skládá ze tří částí.

První část je věnována centralizovaným algoritmům pro real-time routování. V této části jsou odvozeny dva algoritmy. První algoritmus je určen pro souvislé datově toky s časovým omezením na komunikační zpoždění. Druhý algoritmus je pak určen pro periodicky zasílané zprávy s periodou vysílání výrazně vyšší, než doba jednoho komunikačního skoku. Oba algoritmy jsou založeny na teorii nejlevnějších multi-komoditních toků v síti. Algoritmy vykazují velmi dobrou časovou náročnost při řešení pomocí Lineárního Programování. Překvapivě, výkon algoritmů neklesá ani pro celočíselné problémy, které patří mezi NP-úplné problémy.

Druhá část práce je věnována distribuovaným ne-real-time routovacím algoritmům. V této části jsou odvozeny tři algoritmy: Dvou-Smičkový Distribuovaný Algoritmus (TLDRA), Jedno-Smičkový Distribuovaný Algoritmus s Inkrementálním krokem (OLDRAi) a {Jedno-Smičkový Distribuovaný Algoritmus s Optimálním krokem (OLDRAo). Algoritmy jsou odvozeny za pomoci metody přibližného bodu a duální dekompozice pro konvexní problémy. Algoritmy naleznou optimální řešení bez potřeby centrálního výpočetního bodu a jednotlivá zařízení komunikují pouze se sousedy v komunikačním dosahu. Na rozdíl od ostatních prací v této oblasti, algoritmy prezentované v této disertační práci nejsou omezeny pouze na striktně konvexní problémy a dokáží řešit i lineární problémy. Důkaz konvergence je součástí odvození algoritmů.

Třetí část práce je zaměřena na distribuovaný real-time routovací algoritmus. Algoritmus je založen na OLDRAo algoritmu a na centralizovaném algoritmu pro real-time routování z předchozích dvou částí.

Chování všech prezentovaných algoritmů bylo otestováno a vyhodnoceno simulacemi v prostředí Matlab.

Diz 2012 trdlicka jiri.pdf
Diz 37 beran jan.pdf
Diz 37 janecek jan.pdf
Diz 37 lipari giuseppe.pdf