WSN jako glob ální deduktivní databáze

transcript

WSN jako globální deduktivní databáze

Petr Sobotka - DJ2, 5.4.2011

Petr Sobotka WSN jako glob. deduktivní DB 2

Osnova

• WSN – popis problému

• Existující řešení a návrhy

• Popis nového návrhu

• První testy a měření

• Shrnutí a závěr

• Wireless Sensor Network• Síť z (mnoha) zařízení se senzory a vstupního

• Senzorové uzly• Poskytují různá data, z různých lokalit• Propojeny do jedné sítě bezdrátově (často špatně

dostupná umístění)• Nemívají k dispozici mnoho energie – třeba šetřit!

• Přes vstupní uzel se lze dotazovat na data celé sítě – navenek se WSN tváří jako DB

• Např.: Oblasti, kde je teplo a přitom není vlhko.

• Mnoho využití• Sledování počasí (teplota, vlhkost, tlak,…)• Vojenské či bezpečnostní• Měření seismické činnosti, hurikánů, stavu vody v

řece…• Výroba (stav zásob, opotřebení strojů, …)• Chytrá elektronika, košíky v obchodech,…• …

WSN jako relační DB

• Projekt Cougar (Cornell University)• První abstrakce WSN jako relační DB

– Dotaz varianta SQL

• Zajímavý nápad: přesun dotazů na samotné uzly– Uzlů mnoho – centrálně drahé a ne vždy proveditelné

• Projekt Directed Diffusion (USC)

• TinyDB• Nástupce Cougar a Directed Diffusion• Distribuovaná na jednotlivé uzly (zrnka, motes)• Rozhraní obdoba SQL či deklarativně• Dokáže vyhodnocovat dotazy přes více uzlů, více zároveň• Spravuje topologii sítě• Agregace dat, cache – úspora energie• Běží nad TinyOS

– OS pro malá bezdrátová zařízení

– Nízké energetické nároky

– Zadarmo (BSD licence)

• Netriviální použití

• Nevýhody ex. relačních řešení:• Slabší vyjadřovací schopnost dotazu oproti

deklarativním DB• Obtížná práce globálně (přes více atributů různých

uzlů)– Data vázána k jednotlivým uzlům – musí se projít a

agregovat

• Neimplementují rekurzivní dotazy• Nepodporují logické dotazy

WSN jako deduktivní DB

• Lepší vyjadřovací schopnost, rekurzivní dotazy

• Datalog – oblíbený jazyk na kladení dotazů nad deduktivní DB

• Snlog• Dialekt Datalogu vyvinutý pro WSN• Ale deklarativní charakter• Pro Low-level programátory• Dotazy lokálně + musí se řešit síťové detaily a

protokoly

Příklad dotazů v Datalogu

maTepleMisto(OblastID):- teplota(UzelID, Teplota), Teplota > 25, oblast(UzelID, OblastID).

nebezpeci(OblastID) :-teplota(UzelID, T), T > 42,oblast(UzelID, OblastID).

nebezpeci(OblastID) :- vlhkost(UzelID, H),H < 40, oblast(UzelID, OblastID), soused(OblastID, SousOblast), nebezpeci(SousOblast).

WSN jako glob. deduktivní DB

• Celá WSN je jedna velká deduktivní DB

• Nahrazení TinyDB vlastní LogicQ

• Původní způsoby zpracování dotazů pro deduktivní DB nebyly vytvořeny pro WSN

• Typy zpracování dotazů• Prologové (Prologue + DB)• Shora dolů• Zdola nahoru

WSN jako glob. deduktivní DB

• V klasických deduktivních DB často preferován způsob „zdola nahoru“

• Ale ve WSN máme v každém uzlu lokální data a posílat je všechny „nahoru“ pro každý dotaz by bylo drahé

• Použití způsobu „Shora dolů“• Šlo by omezit, ze kterých uzlů data chceme

– Např. potvrzení faktu stačí od jednoho uzlu

• Vhodné pro rekurzivní dotazy• Neměnné fakty lze cachovat centrálně• Výsledky poddotazů lze využít pro filtraci následujících

Příklad použití výsledků předchozích poddotazů

horkyObjekt(ObjektID, OblastID):-

detekuje(ObjektID, OblastID),

teplota(ObjektID, T), T > 50

• Dotaz ?-horkyObjekt(X,oblast70)• Odešle se detekuje(ObjektID, oblast70) a na to odpoví jen

relevantní část uzlů (nagativní mlčí) = uzly z oblasti 70• Každý získaný ObjektID se pak dá do teplota(…,T)• Dokonce můžeme ještě dříve použít T > 50 a brát jen ty uzly

LogicQ

• Namísto TinyDB poběží LogicQ na každém uzlu (nad TinyOS)

• Predikáty spojené s funkcí sensorů jsou zadány při instalaci

• např. teplota(Uzel1, T) – senzor dá do T naměřenou hodnotu• Vyhodnocovač dotazů („nahoře“) má dáno, co poslat jako

poddotazy „dolů“ (~iniciální pravidla v log. programování)

• Při startu se sestaví Směrovací strom• Kořen je vstupní uzel• Každý (kromě kořene) uzel má jen jednoho otce• Slouží k jednoduchému přeposílání dotazů dle potřeby

(pokud již uzel výše ve stromu sám neuspokojí)

LogicQ

• Rozlišovány 2 typy poddotazů:• Ověření faktu

– detekuje(nádrž1, oblast70) – true/false– Lze splnit dříve než poslánio všem uzlům

• Získání všech splněných predikátů– detekuje(X, oblast70) – nádrž1, nádrž2, nádrž8, …– Musí se poslat všem uzlům (které zatím nevyloučeny)

LogicQ

• Pseudokód vyhodnocování poddotazů:If (typ == overeni){ if (splnenoLokalne) posliNahoru(true); else posliDotazDetem;}Else //typ == ziskani všech splnenych{ posliDotazDetem; if (necoLokalneSplnuje) posliNahoru(MnozinaSplnujici);}

První měření LogicQ

• Pomocí TOSSIM (TinyOS Simulator)

• Předpokládáno spolehlivé spojení

• Měřené metriky:• Úplnost (# získaných odpovědí / # vzniklých)• Přesnost (# relevantních odpovědí / # získaných)• Nákladnost (na energii, jako počet posílaných

zpráv)

• Měřeno vůči standardní metodě „zdola nahoru“

První měření LogicQ

• LogicQ dosáhl 100% přesnosti za téměř 100% úplnosti a nákladech ve většině případů nižší než při použití metody „zdola nahoru“

• Úplnost měla drobné ztráty v důsledku zahlcení, avšak díky menšímu počtu poslaných zpráv k jevu docházelo méně často než ve druhém případě

• Při narůstajícím počtu uzlů se rozdíl v nákladech snižoval, jelikož naivní implementace LogicQ posílá při bindingu zprávu pro každou hodnotu zvlášť

Shrnutí

• WSN jedna velká deduktivní DB• Logická pravidla i dotazy snadno zadatelná přes

všechny uzly (globálně)• Podpora rekurzivních dotazů• Optimalizace

• Dřívějším bindingem / splněním dříve

• Nedostatky (zatím)• Naivní implementace dřívějšího bindování (jednotlivě a ne

jako množiny – vícekrát posláno)• Není navrhnuté řízení zahlcení

Závěr

• Jedná se zatím jen o první pokusy nového řešení

• Na rozdíl od TinyDB, která je již řadu let úspěšně používaná

• Poskytuje ovšem již nyní směr vývoje WSN, který by mohl v řadě případů být lepším než stávající řešení

Zdroje

• A System for Using Wireless Sensor Networks as Globally Deductive Databases

• Supasate Choochaisri, Chalermek Intanagonwiwat, wimob, pp.649-654, 2008 IEEE International Conference on Wireless & Mobile Computing, Networking & Communication, 2008

• http://www.cs.cornell.edu/bigreddata/cougar• http://telegraph.cs.berkeley.edu/tinydb/• http://www.tinyos.net/• http://en.wikipedia.org

WSN jako glob ální deduktivní databáze

Documents