Diz 37 cz
Distribuované a Real-time řízení toku dat v senzorových sítích
Autor: Jiří Trdlička
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.
- Jiří Trdlička, mailto:jiri@trdlicka.cz, www.trdlicka.cz