Data Storage selection in sensor networks

صفحه 1:
Data Storage selection in sensor network Report of Advanced Data Base Topics Project Instructor :Dr.rahgozar euhanna ghadimi,Aliabbasi,kavepashaii 

صفحه 2:
Outline ‘#7. Introduction #Definition, Applications, Differences, Storage #2. Queries 2.7. Querying in Cougar $2.2. Queryingin TinyDB #2,3.In-network Aggregation 3. Other Issues 

صفحه 3:
Introduction ‘roma data storage point of view,a sensor networkdatabase: a distributeddatabase that collects physical measurements about theenvironment, indexes them, and serves queries fromusers andother applicationsexternal toorfrom within the network” @Researchinsensor network databases: * relatively new can benefit fromcurrent effortsin data streams andP2P networks 

صفحه 4:
Thelongtermgoal Embed numerous es devices to or and interact with physical world: in work- spaces, hospitals, homes, 

صفحه 5:
Sensor Net Sample Apps Habitat Monitoring:Storm —petretson Great DuckIsland, microclimates on James Reserve. Vehicle detection:sensorsalonga Yoad, collect data about passing vehicles. raditional monitoring apparatus. 

صفحه 6:
Overview of research * Sensor network challenges * Oneapproach: Directed diffusion * Basicalgorithm * Initial simulation results Intanagowat) * Other interesting Cocalizedalgorithmsin progress: * Aggregation (Kumar) * Adaptive fidelty (Xu) ۶ Address freearchitecture, Time synch (Elson) * Localization (Bulusu, Girod) ۶ Self-configuration using robotic nodes (Bulusu,Cerpa) ° Instrumentationand debugging (Jerry Zhao) 

صفحه 7:
The Challengeis Dynamics! sical-worldis dynamic * Dynamic operating conditions * Dynamicavailability of resources * ...particularly energy! * Dynamictasks @Devicesmust adapt automatically tothe environment * Toomany devicesfor manual configuration * Environmental conditionsareunpredictable @unattendedandun-tet heredoperationis key tomany applications 

صفحه 8:
Approach PEnergyis the bottleneck resource Andcommunicationisamajor consumer--avoid communication over Cong distances ~Pre-configurationand global knowledgeare not applicable * Achieve desired global behavior throughlocalized interactions * Empirically adapt toobservedenvironment @Leveragepoints * small-form-factor nodes, densely distributedto achieve Physical locality tosensedphenomena ° Application-specific, data-centric networks * Data processing/aggregation inside the network 

صفحه 9:
Directed Diffusion Concepts Sayplication- aware communication primitives * expressedin terms of nameddata (not in terms of the nodesgenerating or equesting data) is process setsup gradients in the networkwhichchannel the delivery of data inforcement and negative reinforcement used to converge to efficient distribution @intermediate nodes opportunistically fuseinterests,aggregate, correlateor cache data 

صفحه 10:
I(Custrating Directed Diffusion 6 O-—: Sending data 3 3 Source GE ' Sourcel > AT 5 6 ‏و‎ Reinforcing stablepath Sourcet eee 6 Sink 0 ‘8 Sink ‘Recovering fromnodefaiture © 10 

صفحه 11:
Sensor Network Tomography: Key Ideas @xKindsof tomograms * network health * resource-fevel indicators responses toexternal stimuli Canexchangeresourcehealth * during low-level housekeeping functions 1 suchas radio synchronization ‘Key cha(Cenge:energy- efficiency * need toaggregatelocal representations algorithms must auto-scale outlier indicatorsare different 2 andChallenges 

صفحه 12:
Self configuring networksusingand supporting robotic nodes Cerpa, Estrin, Heidemann, Mataric,Sukhatme) PRoboticsintroduces Place nodes for self-mobile nodes ‏یایب‎ ‎andadaptively tati placednodes ‏ی‎ ۳۹ @Self configuringad S@ildcbhedcbristor hocnetworksinthe : context of localization unpredictable RF granularity environment n 

صفحه 13:
11001 0/۱۲۲۱ ۱20۴ 5 Hard 4,11 | | 1 Current (mA) by Processing Phase Current (mA) 8 3. 8 a ° Processing Processing & Processing & Idle 

صفحه 14:
* Expressive & easy-to-useinterface * High-level operators * Well-definedinteractions * “Transparent Optimizations” that many programmers wouldmiss * Sensor-net specifictechniques * Power efficient execution framework Question: do sensor networks change query processing? 1 Ves! 

صفحه 15:
Overview 4 inyDB: Queries for Sensor Nets # Processing Aggregate Queries (TAG) Taxonomy & Experiments # Acquisitional Query Processing Other Research @ Future Directions 15 

صفحه 16:
Overview inyDB: Queries for Sensor Nets @ Processing Aggregate Queries (TAG) @Taxonomy & Experiments * Acquisitional Query Processing Other Research Future Directions 16 

صفحه 17:
TinyDBDemo ۳۰۳ ۳ ie Be by -) ‏جه | دست‎ | = teste ey 17 

صفحه 18:
5 TinyDB Architecture Pe AVG(temp) Queries Results 7:2, 1250 Cight > 400 | Schema ~10,000 Lines Embedded CCode — get | ~,000 Lines (PC-Side) Java a ~3200 Bytes RAM (w/ 768 byteheap) ~58RBcompiledcode (3x Carger than 2™Cargest TinyOS Program) 

صفحه 19:
۲ 0۳/۱ © 017 01 أ60 لل Light 455 405 43 Sensors west NT 9 17 25 Mode “Find the sensorsin bright 4 nests.” ‘Epoch Networks Otxamples: SELECT nodeid nest No,Cight ‘PROM sensors “WITERE Fight > 400 EPOCH DURATION 4s 

صفحه 20:
AVG(...) 360 520 370 520 “ Regionsw/AVG(sound)>200 ~ 3 2 SELECT AVG(sound) “Count the number occupied nestsineachloudregion of PROM sensors i ۰ theisland,” region. Nort 6 South North South Aggregation Queries EPOCH DURATION 5 Epoch @)ssercrregion, cn Toccupied) 0 ۷) 8 FROM sensors 11 GROUP BY region [R15 HAVING XVG(sound)> 200 ‏أ‎ ‎EPOCH DURATION 70s 1 

صفحه 21:
Overview inyDB: Queries for Sensor Nets @ Processing Aggregate Queries (TAG) Taxonomy & Experiments * Acquisitional Query Processing Other Research @Future Directions a 

صفحه 22:
Tiny Aggregation (TAG) PIn-networkprocessing of aggregates * Common data analysis operation * Aka gather operation or reductionin|| programming * Communication reducing * Operator dependent benefit * Across nodes during same epoch Exploit query semantics toimprove efficiency! 22 

صفحه 23:
Query Propagation Via ‘lree- Based Routing | 9 1 @rrec-basedrouting fia “ECT * Usedin: oe |? Query detivery 8 | * Datacolfection *) Topology setectionisimportant: 9. | * Krishnamachari,!) ERs 2002, Intanagonwiwat,1CD S 2002, ‘Heidemann, SOs? 2007 + LEACH SPIN Meinzefmanet al. Monicom 9p ۶ 10۶ * Continuous process * mitigatesfaiures 23 

صفحه 24:
Basic Aggregation Bach node samplesCocal sensors once Generatespartial state record (PSR) + Cocat readings + veadingsfromehitéven Outputs PSR during assignedcomm.intervat tendofepoch, PSRfor whole networkoutput at root few result on each successive epoch + Predicate-basedpartitioning via GROUP BY 2 

صفحه 25:
۱ Interva t —_ © Jf sett aes 0۰ 4 Sensor # te aes = ‎Interval #‏ ساسا ج سا | | دا هچ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 26:
۱ SELECT COUNT(*) FROM sensors Interval 3! Sensor # ® 0 ‏الس هل‎ HN r 6 ١ 0 ۱ 9 Interval # ‏نم‎ 26 

صفحه 27:
۱ 4 Sensor # te aes 1 Interval 2' ‘Q 3 vA 2 6 oe” [2 SA TN lays Interval # eA = 

صفحه 28:
۱ @ -_ 1 aN 6 ‏هر‎ ‎6 هه Sensor # te aes 4 ‏اك‎ 5 2 2 ‏كال‎ ‎5 ye =a 1s =| iS ile 

صفحه 29:
۱ 1 ‏دده‎ 4 NN 3 ۶ 4 6 o 4 Sensor # te aes [2 Interval # re eo eis [ulals 

صفحه 30:
Interval Assignment: An Approach geezer ‏لماك‎ | | | CommiIntervat | °CSMA for collision avoidance *Timeintervals for power conservation *Manyvariations( 3 2 و 51 6م15 * 

صفحه 31:
Aggregation Framework * |Asinextensible databases,wesupportany aggregationfunction conforming to: Aggn=(finit, fmerge,fevatuate) Finit (ao) > <ao> Sef beret Store Reed BSR? a <012> ج (<02>,< 01>) ع وعم ‎Fevaluate (<a7>) >aggregatevalue‏ ‎Example: Average‏ < ,> ره ‎AVGinit‏ ‎AVGmerge (<S1,C1>,<S2,C2>) >< S1+S$2,C7+C2>‏ ‎AVGevaluate(<S,C>} =p S{C‏ ‎Restriction: Merge associative,commutative‏ 

صفحه 32:
Types of Aggregates ۹۹ supports MIN, MAX, SUM, COUNT, AVERAGE @ Anyfunction over aset canbecomputedvia TAG in network benefit for many operations * £.g.Standard deviation, top/bottom N, spatial union/intersection,histograms,etc, * Compactness of PSR 32 

صفحه 33:
Overview inyDB: Queries for Sensor Nets # Processing Aggregate Queries (TAG) Taxonomy & Experiments * Acquisitional Query Processing Other Research Future Directions 33 

صفحه 34:
Simulation Environment @tvaluatedTAG via simulation @coarse grainedevent basedsimulator * Sensorsarrangedonagrid * Twocommunication models * LossCess: ALC neighbors hear afl messages * Lossy: Messages Cost with probability that increases with distance communication (message counts) as performance metric 2 

صفحه 35:
as Taxonomy of Aggregat es @TAG insight: classifyaggregates according to various functional properties ۶ Yields a general set of optimizations that can automatically beapplied Properties PartialState Monptonicity mplary vs. Summary sitivity Duplicate Se 

صفحه 36:
Affects ‘Effectiveness of TAG 36 Partial State jowthof PSRvs. number of aggregatedvatues (n) ‘Atgebraic: — |PSRi=7(e.g.-MIN) Distributive; (PSR) =c(e.g-AVG) Holistic: |PSR| =n (e.g. MEDIAN) unique: IPSRi=d (e.g. COUNTDISTINCT) © d= #ofdistinct vatues Content Sensitive: |PSRI<n (e.g. HISTOGRAM) Property Examples ialStat MEDIAN unbounded, MAX: 4 record 

صفحه 37:
Beneyjrt oy LN-Networr Processing Total Bytes Xmitted vs. Aggregation Function 7 21 100000 Hoist 20000 § r0000 || R 60000 & soo00 ‏لم‎ ‎3 s0000 \ | BEEBE 8 eee Distrifuris Lt + Algebraic 5 2 ۲۱ 55 ‏تست سم‎ Bo 5 6 EXTERNAL MAX AVERAGE DISTINCT MEDIAN 7 28 Aaaregation Furetion ‏ال‎ a 

صفحه 38:
Monotonicity & Exemplaryvs. Affects Effectiveness of TAG ‘Hypothesis Testing, Snooping Applicability of Sampling, Effect of Loss 38 Summary Property Examples PattialState | MEDIAN unbounded, MAX?7 record ۷ COUNT :monotonic AVG non-monotonic xemplaryys. | MAX:exemplary 1/0 COUNT: summary 

صفحه 39:
Channel Sharing (“Snooping”) insight: Sharedchannel can reduce communicatio @Suppress messages that won't affect aggregate 5 MAX * Appliestoall exemplary,monotonicaggregates Only snoopinlisten/transmit slots * Futurework: explore snooping/Cistening tradeoffs و 

صفحه 40:
Hypothesis Testing Insight: Guessfromroot can beusedfor suppression ۶ 20,0۸۲ > * Works for monotonic & exemplary aggregates * Alsosummary, ifimprecision allowed @ How is hypothesis computed? ۰ Blindor statistically informed guess * Observation over network subset 40 

صفحه 41:
000۲1۱۹۵۲ ۱ ۰ Hypothesis Testing Messages/ Epoch vs. Network Diameter uniform (SELECT MAX(attr), R(attr) = [0,100]) Value 3000 aie Distribution “+ No Guess 2 ee -w Guess = 50 5 Dense 2000 ‏ها‎ Guess = 90 Packing -t Snooping 7 vat 1500 {Sa ‏سنج‎ ‎municatto ‎ — A a i a Pruning a in 500 8 a Network | ‏الل ی‎ of 10 20 30 40 50 Network Diameter 2 Messages / Epoct 

صفحه 42:
Affects ‘Effectiveness of TAG Hypothesis Testing, Snooping Applicability of Sampling, Effect of Loss ‘Routing Redundancy 42 DuplicateSensitivity Examples MEDIAN unbounded, MAX:7 record COUNT: monotonic AVG non-monotonic MAX exemplary COUNT:summary MIN : dup, insensitive, AVG :dup. sensitive Property Pajrtial State Mdnotonicity ‘Exemplary vs. Summary 

صفحه 43:
Use Multiple Parents segraphstructure Increase delivery probability withnocommunication overhead @ For duplicateinsensitive aggregates, or 4 ggsexpressibleassumofparts SELECT COUNT(*) Send (part of aggregate toall parents 5 2 * Injust onemessage,via multicast * Assuming independence, decreases variance| P(Cink xmit successful ۳93۳9۳9 P(successfromA->R) =p? =n *cin *p? ‏مرجع د راع‎ Elent)=n *(c/n *p*) Var(ent)=n *(c/n)? *p? Varicnt)=c? *p? *(7_p?) = 5 7 ‏حور و)»*‎ Vin 

صفحه 44:
MultipleParents Results No Splitting With Splitting 1 Critical ites xj ink! #Lo a ‏مت‎ ‎In ‎da 7 

صفحه 45:
Taxonomy RelatedInsights سآ انار 13.2 ماو 1 In-network Aggregation (Partial State) ° atypothesis Testing (Exemplary & Monotonic) * snooping (Exemplary & Monotonic) * sampling @QualityIncreasing * Multiple Parents (DuplicateInsensitive) * ChildCache 3 

صفحه 46:
72۸9 ۵۸ ‘imple but powerful data cofCection language * Vehicletracking: SELECT ONEMAX(magmodeid) bracatpurralro% soms istributedatgorithmforin-networRaggregation * Communication Reducing * Power Aware * Integration of sleeping, computation * Predicate-based grouping xonomy driven API ‘Enablestransparent application of techniquesto © Improve quality parent splitting) + Reduce communication (snooping hypo. testing) 46 

صفحه 47:
Overview inyDB: Queries for Sensor Nets @ Processing Aggregate Queries (TAG) @Taxonomy & Experiments ‏ا‎ Query Processing Other Research Future Directions a7 

صفحه 48:
Acqutisitronal Query Processing (ACQP) Closed worldassumption does not hold * cowldgenerateaninfinite number of samples nacqusitional query processor controfs * when, * where, اللعناعء ]ام كا هنانمك رع اتعديوء 1[ نمطا ۱ @Versustraditional systems where data isprovided a priori Madden, Franklin, Hellerstein,andHong. The Design of An 48 Acqusitional Query Processor. SIGMOD, 2003 

صفحه 49:
49 ACQP: What's Different? ۱ query be processed? * Sampling asafirst class operation * Event join duality @How doestheuser control acquisition? * Rates or lifetimes * Event-basedtriggers @whichnodeshaverelevant data? * Index-like data structures @whichsamples showdbetransmitted? * Prioritization, summary, andrate control 

صفحه 50:
Operator Ordering: InterleaveSampling + Selection Cight,mag ۰ ۱ sensors predz(mag) pred2(Cight) Correct ordering (unless predi is very selective and pred2 is not): 15 

صفحه 51:
Exemplary Aggregate Pushdown CTWINMAX(Cight,8s,8s) Ru) M sensors * Novel, general pushdown technique * Mag sampling is themost expensive operation! 2 

صفحه 52:
Lifetime Queries Lifetimes. sample rate SELECT... EPOCH DURATION 70s SELECT... LIPETIME 30 days @Extra:Allowa MAXSAMPLE PERIOD * Discardsome samples ° Sampling cheaper thantransmitting 32 

صفحه 53:
(Single Node) Lifetime Prediction Voltage vs. Time, Measured Vs. Expected Lifetime Goal = 24 Weeks (4032 Hours. 15 s | sample) 2 Voltage (Expected) R =0.8455 5 Voltage (Measured) _ Linear Fit ‘Expected كي 1 ‏خجعاعا لاك‎ Voltage to 200 Operate (V= 350) 0 1000 2000 3000 4000 Time (Hours) 

صفحه 54:
Overview 4 inyDB: Queries for Sensor Nets # Processing Aggregate Queries (TAG) @Taxonomy & Experiments * Acquisitional Query Processing Other Research @Future Directions ae 

صفحه 55:
0 ۷ 01۷۹0۲ د ‎Problems‏ @Temporal aggregates Sophisticated, sensor network specificaggregates * Isobar Finding * Vehicle Tracking * Lossy compression * Wavelets ‘Isobar Finding” Hellerstein, Hong, Madden,andStanek. Beyond-Average, 230 3 

صفحه 56:
TinyDB Deployments #initial efforts: * Networkmonitoring * Vehicle tracking P Ongoing deployments: * Environmental monitorii ° GenericSensor Kit * Building Monitoring * Golden Gate Bridge ۱ 56 

صفحه 57:
Data Storage ۷۵۵۵۸ )۲ 001۱ م1 1 عا ۵ ۲9۲۵۴ ,با وی و۶۵۲ (sheng et. al ACM MobiHoc 2006) 

صفحه 58:
Problems Data Storage Placement * (Shenget.al paper) #Data StorageSelection * Our method: Anadaptiveand decentralizedmethod 38 

صفحه 59:
Costsinthesystem ‏لللللم‎ reply cost: .cost of reply for sd x from storage node i to sink after recomputing reply tree in each round reply costa; cost of reply for sd, from storage node j to sink after reconputing reply mee ineach round sp, ¢ shortest path of i to an SN ancestor in query diffusion tree 0 ۱ 8 | ‏(رصعا يقي‎ if'i has some fir child diffusion cost of i: E sp; : shortest path of j to. an SN ancestor in query diffusion tree fo if no fn selects j | ‏(رصا)پی‎ af j has some fir child diffusion cost of j: Eg 33 

صفحه 60:
Overall cost Overall cost for a forwarding node with respect to a storage node iis: Total Costa; = ‏رو‎ + reply cost; +diffusion cost of i 60 

صفحه 61:
61 Our method Constructing query reply tree ; Parent selection method Algoritian I. i: Storage Node; Dy > disien between i cme j. Da any * Gisteunce berween i and sink; Dy sar Uist fer benveen; and sink: ach j in adjacency of i if (ie Path, and je Path, ge, ) # CDSy)-Diy + (LSet ‏یط ۰( پکر‎ I CD84). Dey t+ (YL 8a+TSq)- Dyan) ) i=j's parent else J = i's parent; 

صفحه 62:
62 Our method (Cont.) ‏امه‎ Algorithm 2: Data Storage selection for forwarding node fir foreach, forwarding node jn in netvork) 1 ‎Storage Node selected by fi: Active Node‏ رز ‎forech (storage node i in adjacency of fi)‏ 7 ‎t‏ ‎Tf (raw transys + reply costs + Ey) <‏ ‎(raw transing + reply costs + Eg) )‏ 7 < وج 7[ 

صفحه 63:
Our results Very Good 1! 

صفحه 64:
References * Wireless Sensor Networks: AnInformation Processing Approach, by F.ZhacandL. Guibas, Elsevier, 2004. ‘Papers: * [7]BoSheng,Qun Li,and Weizhen Mao. Data Storage Placement insensor networks ACM Mobihoc 2006, Florence, Italy, May 22-25,2006, * [2]B. Bonfils,.P. Bonnet, Adaptiveand Decentralized Operator Placement for In- Network Query Processing 2003, springer verlag. 4 

صفحه 65:
References(Cont.) + ttacharya,H. Kim,S.Prabh,andT. Abdelzaher. Energy-conserving data placement andasynchronous multicast in wireless sensor networks. In Proceedings of the astinternational conferenceon Mobile systems, applicationsand services, pages 173.185, New York, NY, ASA, 2003. ACM Press. [4]9£.S.Kim,T. F. Abde(zaher,andW.H. Kwon. Minimum- energy asynchronous dissemination tomobilesinksin wireless sensor networks.In Proceedings of the 7st international conference on Embedded networkedsensor systems, pages 793.204, New York, NY, USA, 2003. ACM Press. [5] A. Trigoni,Y. Yao, A. Demers, J.GehrkeandR, Rajaraman, Multi-Query Optimization for Sensor Networks.intheInternational Conferenceon Distributed Processing on Sensor Systems (DCOSS), 2005. ىه 

صفحه 66:
References(Cont.) é]MaddenS., Franklin M.J., Hellerstein jJ.M., Hong W., The Design ofan Acquisitional Query Processor For Sensor Networks, Proc.Int.Conf.on Management of Data (SIGMOD),San Diego (USA), 2003. ° [7]®. Bonnet, J. Gehrke, P. Seshadri, Towards Sensor DatabaseSystems, Lecture Notesin Computer Science, 2007,Springer Verlag 66 

Data Storage selection in sensor networks Report of Advanced Data Base Topics Project Instructor : Dr. rahgozar euhanna ghadimi, Ali abbasi , kave pashaii 1 Outline 1. Introduction Definition, Applications, Differences, Storage 2. Queries 2.1. Querying in Cougar 2.2. Querying in TinyDB 2.3. In-network Aggregation 3. Other Issues 2 Introduction From a data storage point of view, a sensor network database : “a distributed database that collects physical measurements about the environment, indexes them, and serves queries from users and other applications external to or from within the network” Research in sensor network databases: • relatively new • can benefit from current efforts in data streams and P2P networks 3 The long term goal Embed numerous distributed devices to monitor and interact with physical world: in workspaces, hospitals, homes, vehicles, and “the environment” (water, soil, Circulatory Net air…) Disaster Response Network these devices so that they can coordinate to perform higher-level tasks. Requires robust distributed systems of tens of thousands of devices. 4 Sensor Net Sample Apps Habitat Monitoring: Storm petrels on Great Duck Island, microclimates on James Reserve. Vehicle detection: sensors along a road, collect data about passing vehicles. Earthquake monitoring in shake-test sites. Traditional monitoring apparatus. 5 Overview of research • Sensor network challenges • One approach: Directed diffusion • Basic algorithm • Initial simulation results (Intanagowat) • Other interesting localized algorithms in progress: • • • • • Aggregation (Kumar) Adaptive fidelty (Xu) Address free architecture, Time synch (Elson) Localization (Bulusu, Girod) Self-configuration using robotic nodes (Bulusu, Cerpa) • Instrumentation and debugging (Jerry Zhao) 6 The Challenge is Dynamics! The physical world is dynamic • Dynamic operating conditions • Dynamic availability of resources • … particularly energy! • Dynamic tasks Devices must adapt automatically to the environment • Too many devices for manual configuration • Environmental conditions are unpredictable Unattended and un-tethered operation is key to many applications 7 Approach Energy is the bottleneck resource • And communication is a major consumer--avoid communication over long distances Pre-configuration and global knowledge are not applicable • Achieve desired global behavior through localized interactions • Empirically adapt to observed environment Leverage points • Small-form-factor nodes, densely distributed to achieve Physical locality to sensed phenomena • Application-specific, data-centric networks • Data processing/aggregation inside the network 8 Directed Diffusion Concepts Application-aware communication primitives • expressed in terms of named data (not in terms of the nodes generating or requesting data) Consumer of data initiates interest in data with certain attributes Nodes diffuse the interest towards producers via a sequence of local interactions This process sets up gradients in the network which channel the delivery of data Reinforcement and negative reinforcement used to converge to efficient distribution Intermediate nodes opportunistically fuse interests, aggregate, correlate or cache data 9 Illustrating Directed Diffusion Setting up gradients Sending data Source Source Sink Sink Reinforcing stable path Source Source Sink Recovering from node failure Sink 10 Sensor Network Tomography: Key Ideas and Challenges Kinds of tomograms • network health • resource-level indicators • responses to external stimuli Can exchange resource health • during low-level housekeeping functions • … such as radio synchronization Key challenge: energyefficiency • need to aggregate local representations • algorithms must auto-scale • outlier indicators are different 11 Self configuring networks using and supporting robotic nodes (Bulusu, Cerpa, Estrin, Heidemann, Mataric, Sukhatme) Robotics introduces selfmobile nodes and adaptively placed nodes Self configuring ad hoc networks in the context of unpredictable RF environment Place nodes for network augmentation or formation Place beacons for localization granularity 12 Programming Sensor Nets Is Hard • Months of lifetime required from small batteries (mA) by recharge Processing • 3-5Current days naively; can’t oftenPhase • 20 Interleave sleep with processing Current (mA) –Lossy, low-bandwidth, short range 15 communication 200-800 High-Level Abstraction Is Need high level »Nodes coming and going instructions per bit Needed! 10 »~20% loss @ 5m abstractions! transmitted! »Multi-hop 5 –Remote, zero administration deployments –Highly distributed environment 0 –Limited Development Processing ProcessingTools & Processing & I dle »Embedded, LEDs for Debugging! Listening Transmitting 13 A Solution: Declarative Queries Users specify the data they want • Simple, SQL-like queries • Using predicates, not specific addresses • Same spirit as Cougar – Our system: TinyDB Challenge is to provide: • Expressive & easy-to-use interface • High-level operators • Well-defined interactions • “Transparent Optimizations” that many programmers would miss • Sensor-net specific techniques • Power efficient execution framework Question: do sensor networks change query processing? Yes! 14 Overview TinyDB: Queries for Sensor Nets Processing Aggregate Queries (TAG) Taxonomy & Experiments Acquisitional Query Processing Other Research Future Directions 15 Overview TinyDB: Queries for Sensor Nets Processing Aggregate Queries (TAG) Taxonomy & Experiments Acquisitional Query Processing Other Research Future Directions 16 TinyDB Demo 17 TinyDB Architecture SELECT T:1, AVG: 225 AVG(tem Queries ResultsT:2, AVG: 250 p) WHERE light > Multihop Schema: 400 Network Query Processor Aggavg(tem •“Catalog” of commands & attributes p) ~10,000 Lines Embedded CName: Code temp Filter light > Time to sample: 50 uS Cost to sample: 90 uJ SchemaRAM (w/ 768 byte ~3200 Bytes heap) Table: 3 Calibration getTempFunc(…) Units: Deg. F ~58 kB TinyOS compiled code Error: ± 5 Deg F Get f : getTempFunc()… (3x larger than 2nd largest TinyOS Program) ~5,000 (PC-Side) Java got(‘temp’) 400Lines get (‘temp’) Tables Samples TinyDB 18 Declarative Queries for Sensor Networks “Find the sensors in bright nests.” 1 Examples: SELECT nodeid, nestNo, light FROM sensors WHERE light > 400 EPOCH DURATION 1s Sensors Epoc h Nodei d nestN o Light 0 0 1 1 1 17 455 2 25 389 1 17 422 2 25 405 19 Aggregation Queries 2 SELECT AVG(sound) FROM sensors EPOCH DURATION 10s “Count the number occupied nests in each loud region of the island.” Epoch region CNT(…) AVG(…) 3 SELECT region, CNT(occupied) 0 North 3 360 0 South 3 520 1 North 3 370 1 South 3 520 AVG(sound) FROM sensors GROUP BY region HAVING AVG(sound) > 200 EPOCH DURATION 10s Regions w/ AVG(sound) > 20020 Overview TinyDB: Queries for Sensor Nets Processing Aggregate Queries (TAG) Taxonomy & Experiments Acquisitional Query Processing Other Research Future Directions 21 Tiny Aggregation (TAG) In-network processing of aggregates • Common data analysis operation • Aka gather operation or reduction in || programming • Communication reducing • Operator dependent benefit • Across nodes during same epoch Exploit query semantics to improve efficiency! 22 Query Propagation Via TreeBased Routing Tree-based routing Q:SELECT … • Used in: • Query delivery • Data collection • Topology selection is important; e.g. • Krishnamachari, DEBS 2002, Intanagonwiwat, ICDCS 2002, Heidemann, SOSP 2001 • LEACH/SPIN, Heinzelman et al. MOBICOM 99 • SIGMOD 2003 • Continuous process • Mitigates failures A Q Q R:{…} R:{…} B Q Q R:{…} Q D R:{…} Q E C Q Q R:{…} Q Q Q F Q 23 Basic Aggregation In each epoch: • • Each node samples local sensors once Generates partial state record (PSR) • • • local readings readings from children At end of epoch, PSR for whole network output at root New result on each successive epoch Extras: • 1 Outputs PSR during assigned comm. interval Predicate-based partitioning via GROUP BY 2 3 4 5 24 Illustration: Aggregation SELECT COUNT(*) FROM sensors Sensor # 1 Interval # 4 2 3 4 Interval 4 1 Epoch 5 1 2 3 3 2 1 4 4 1 5 25 Illustration: Aggregation SELECT COUNT(*) FROM sensors Sensor # 1 2 3 1 4 Interval # 2 5 1 4 3 Interval 3 2 3 2 2 4 1 4 5 26 Illustration: Aggregation SELECT COUNT(*) FROM sensors Sensor # 1 2 3 4 Interval # 1 1 5 1 4 3 2 3 2 3 2 Interval 2 1 3 4 1 4 5 27 Illustration: Aggregation SELECT COUNT(*) FROM sensors Sensor # 1 2 3 4 Interval # 5 2 3 2 3 1 2 4 Interval 1 1 1 4 1 5 3 4 5 5 28 Illustration: Aggregation SELECT COUNT(*) FROM sensors Sensor # 1 2 3 4 Interval # 5 2 3 2 3 1 2 4 1 1 4 1 Interval 4 3 4 5 1 1 5 29 Interval Assignment: An Approach 4 intervals / epoch SELECT COUNT(*)… Comm Interval Interval # = Level Level = 1 •CSMA for collision T Z Z L Z 2 2 avoidance Z Z Z Z Z Z Z Z 1 Yao & Gehrke, CIDR 2003) 4 •Time Sync (e.g. Elson & Estrin OSDI 2002) Z Z Z Z Z Z Z Epoch 3 Z •Time intervals for power conservation 3 •Many variations(e.g. Z 5 4 3 2 1 5 L T Z Z Z Z 4 Z Z Z Z Z Z Z Z Z L T L T Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z L T L Pipelining: Increase throughput by 5 arrival until a later epoch delaying result Z Z Z Z Z Z Madden, Szewczyk, Franklin, Culler. Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor 30 Networks. WMCSA 2002. Aggregation Framework • As in extensible databases, we support any aggregation function conforming to: Aggn={finit, fmerge, fevaluate} Finit {a0}  <a0> Partial State Record (PSR) Fmerge {<a1>,<a2>}  <a12> Fevaluate {<a1>} value Example: Average  aggregate AVGinit {v} AVGmerge + C2> {<S1, C1>, <S2, C2>}  <v,1>  < S1 + S2 , C1 AVGevaluate{<S, C>}  S/C Restriction: Merge associative, commutative 31 Types of Aggregates SQL supports MIN, MAX, SUM, COUNT, AVERAGE Any function over a set can be computed via TAG In network benefit for many operations • E.g. Standard deviation, top/bottom N, spatial union/intersection, histograms, etc. • Compactness of PSR 32 Overview TinyDB: Queries for Sensor Nets Processing Aggregate Queries (TAG) Taxonomy & Experiments Acquisitional Query Processing Other Research Future Directions 33 Simulation Environment Evaluated TAG via simulation Coarse grained event based simulator • Sensors arranged on a grid • Two communication models • Lossless: All neighbors hear all messages • Lossy: Messages lost with probability that increases with distance Communication (message counts) as performance metric 34 Taxonomy of Aggregates TAG insight: classify aggregates according to various functional properties • Yields a general set of optimizations that can automatically be applied Properties Partial State Drives an API! Monotonicity Exemplary vs. Summary Duplicate Sensitivity 35 Partial State Growth of PSR vs. number of aggregated values (n) • • • • Algebraic: Distributive: Holistic: Unique: (e.g. COUNT DISTINCT) • • |PSR| = 1 (e.g. MIN) |PSR| = c (e.g. AVG) |PSR| = n (e.g. MEDIAN) d = # of distinct values Content Sensitive: Property Partial State |PSR| < n (e.g. HISTOGRAM) Examples MEDIAN : unbounded, MAX : 1 record |PSR| = d “Data Cube”, Gray et. al Affects Effectiveness of TAG 36 Benefit of In-Network Processing Simulation Results 2500 Nodes 50x50 Grid Depth = ~10 Total Bytes Xmitted vs. Aggregation Function Neighbors = ~20 Uniform Dist. 100000 Total Bytes Xmitted 90000 Unique 80000 Holistic 70000 • Aggregate & depth dependent Distributive benefit! Algebraic 60000 50000 40000 30000 20000 10000 0 EXTERNAL MAX AVERAGE DI STI NCT MEDI AN Aggregation Function 37 Monotonicity & Exemplary vs. Summary Property Examples Affects Partial State MEDIAN : unbounded, MAX : 1 record Effectiveness of TAG Monotonicity COUNT : monotonic AVG : non-monotonic MAX : exemplary COUNT: summary Hypothesis Testing, Snooping Exemplary vs. Summary Applicability of Sampling, Effect of Loss 38 Channel Sharing (“Snooping”) Insight: Shared channel can reduce communication Suppress messages that won’t affect aggregate • E.g., MAX • Applies to all exemplary, monotonic aggregates Only snoop in listen/transmit slots • Future work: explore snooping/listening tradeoffs 39 Hypothesis Testing Insight: Guess from root can be used for suppression • E.g. ‘MIN < 50’ • Works for monotonic & exemplary aggregates • Also summary, if imprecision allowed How is hypothesis computed? • Blind or statistically informed guess • Observation over network subset 40 Experiment: Snooping vs. Hypothesis Testing Uniform Value Distribution Dense Packing Ideal Pruning Communication at Leaves Messages/ Epoch vs. Network Diameter (SELECT MAX(attr), R(attr) = [0,100]) Messages / Epoch 3000 No Guess 2500 Guess = 50 Guess = 90 2000 Snooping 1500 1000 Pruning in Network 500 0 10 20 30 40 Network Diameter 50 41 Duplicate Sensitivity Property Examples Affects Partial State MEDIAN : unbounded, MAX : 1 record Effectiveness of TAG Monotonicity COUNT : monotonic AVG : non-monotonic MAX : exemplary COUNT: summary MIN : dup. insensitive, AVG : dup. sensitive Hypothesis Testing, Snooping Exemplary vs. Summary Duplicate Sensitivity Applicability of Sampling, Effect of Loss Routing Redundancy 42 Use Multiple Parents Use graph structure • Increase delivery probability with no communication overhead For duplicate insensitive aggregates, or SELECT COUNT(*) Aggs expressible as sum of parts • Send (part of) aggregate to all parents R • In just one message, via multicast • Assuming independence, decreases variance P(link xmit successful) = p P(success from A->R) = p2 E(cnt) = c * p2 Var(cnt) = c2 * p2 * (1 – # of parents = n B E(cnt) = n * (c/n * p2) Var(cnt) = n * (c/n) * p2 * (1 – p2) = 2 V/n C c c/n n= 2 c/n A 43 Multiple Parents Results No Splitting than Avg . COUNT Better previous analysis Critical expected! Link! Losses aren’t independent! Insight: spreads data over many links With Splitting Be n e fi t o f Re s u l t Sp l i t t i n g (COUNT q u e ry) 1400 1200 1000 800 Spli t t i ng No Spli t t i ng 600 400 200 0 (2500n o d e s , l o s s y ra d i o mo d e l , 6p a re n t s p e r node) 44 Taxonomy Related Insights Communication Reducing • In-network Aggregation (Partial State) • Hypothesis Testing (Exemplary & Monotonic) • Snooping (Exemplary & Monotonic) • Sampling Quality Increasing • Multiple Parents (Duplicate Insensitive) • Child Cache 45 TAG Contributions Simple but powerful data collection language • Vehicle tracking: SELECT ONEMAX(mag,nodeid) EPOCH DURATION 50ms Distributed algorithm for in-network aggregation • • Communication Reducing Power Aware • Predicate-based grouping • Integration of sleeping, computation Taxonomy driven API • Enables transparent application of techniques to • Improve quality (parent splitting) • Reduce communication (snooping, hypo. testing) 46 Overview TinyDB: Queries for Sensor Nets Processing Aggregate Queries (TAG) Taxonomy & Experiments Acquisitional Query Processing Other Research Future Directions 47 Acquisitional Query Processing (ACQP) Closed world assumption does not hold • Could generate an infinite number of samples An acqusitional query processor controls • when, • where, • and with what frequency data is collected! Versus traditional systems where data is provided a priori Madden, Franklin, Hellerstein, and Hong. The Design of An Acqusitional Query Processor. SIGMOD, 2003 48 ACQP: What’s Different? How should the query be processed? • Sampling as a first class operation • Event – join duality How does the user control acquisition? • Rates or lifetimes • Event-based triggers Which nodes have relevant data? • Index-like data structures Which samples should be transmitted? • Prioritization, summary, and rate control 49 Operator Ordering: Interleave Sampling + Selection At 1 sample / sec, total power SELECT light, mag •savings E(sampling mag) >> E(sampling could be as much as FROM sensors light) WHERE pred1(mag) 3.5mW  Comparable to 1500 uJ vs. 90 uJ processor! AND pred2(light) Correct ordering EPOCH DURATION 1s (unless pred1 is very Traditional DBMS  (pred1 ) (pred2) selective and pred2 is not):  (pred1 ) ACQP Costly (pred2) Cheap mag light mag light (pred2) light  (pred1 ) mag 50 Exemplary Aggregate Pushdown SELECT WINMAX(light,8s,8s) FROM sensors WHERE mag > x EPOCH DURATION 1s Traditional DBMS WINMAX  (mag> x) ACQP WINMAX  (mag> x) mag (light > MAX) • Novel, general pushdown technique • Mag sampling is the most expensive operation! light mag light 51 Lifetime Queries Lifetime vs. sample rate SELECT … EPOCH DURATION 10 s SELECT … LIFETIME 30 days Extra: Allow a MAX SAMPLE PERIOD • Discard some samples • Sampling cheaper than transmitting 52 (Single Node) Lifetime Prediction Voltage vs. Time, Measured Vs. Expected Lif etime Goal =24 Weeks (4032 Hours. 15 s / sample) Voltage (Raw Units) 1000 Voltage (Expected) Voltage (Measured) Linear Fit R2 =0.8455 900 800 700 Expected Measured 1030 1010 600 990 500 970 950 400 0 100 200 300 I nsuffi cient Voltage to Operate (V =350) 300 0 1000 2000 Time (Hours) 3000 4000 53 Overview TinyDB: Queries for Sensor Nets Processing Aggregate Queries (TAG) Taxonomy & Experiments Acquisitional Query Processing Other Research Future Directions 54 Sensor Network Challenge Problems Temporal aggregates Sophisticated, sensor network specific aggregates • Isobar Finding • Vehicle Tracking • Lossy compression • Wavelets “Isobar Finding” Hellerstein, Hong, Madden, and Stanek. Beyond Average. IPSN 2003 55 TinyDB Deployments Initial efforts: • Network monitoring • Vehicle tracking Ongoing deployments: • • • • Environmental monitoring Generic Sensor Kit Building Monitoring Golden Gate Bridge 56 Data Storage Recently Introduced Larger capacity, larger battery power Usual sensors send their data to it It replies queries (sheng et. al ACM MobiHoc 2006) 57 Problems Data Storage Placement • (Sheng et. al paper) Data Storage Selection • Our method : An adaptive and decentralized method 58 Costs in the system 59 Overall cost 60 Our method 61 Our method (Cont.) 62 Our results Very Good !! 2500 2000 1500 1000 248 235 204 19 1 17 7 16 6 15 7 145 131 117 106 92 79 65 55 43 29 0 19 500 1 cost id 63 References Book: • Wireless Sensor Networks: An Information Processing Approach, by F. Zhao and L. Guibas, Elsevier, 2004. Papers: • [1]Bo Sheng, Qun Li, and Weizhen Mao. Data Storage Placement in sensor networks ,ACM Mobihoc 2006, Florence, Italy, May 22-25, 2006, • [2]B. Bonfils,.P. Bonnet , Adaptive and Decentralized Operator Placement for InNetwork Query Processing ,2003, springer verlag . 64 References(Cont.) • [3]S. Bhattacharya, H. Kim, S. Prabh, and T. Abdelzaher. Energy-conserving data placement and asynchronous multicast in wireless sensor networks. In Proceedings of the 1st international conference on Mobile systems, applications and services, pages 173–185, New York, NY, USA, 2003. ACM Press. • [4]H. S. Kim, T. F. Abdelzaher, and W. H. Kwon. Minimum-energy asynchronous dissemination to mobile sinks in wireless sensor networks. In Proceedings of the 1st international conference on Embedded networked sensor systems, pages 193– 204, New York, NY, USA, 2003. ACM Press. • [5] A. Trigoni, Y. Yao, A. Demers, J. Gehrke and R. Rajaraman. Multi-Query Optimization for Sensor Networks. in the International Conference on Distributed Processing on Sensor Systems (DCOSS), 2005. 65 References(Cont.) • [6]Madden S., Franklin M.J., Hellerstein J.M., Hong W., The Design of an Acquisitional Query Processor For Sensor Networks, Proc. Int. Conf. on Management of Data (SIGMOD), San Diego (USA), 2003. • [7] P. Bonnet, J. Gehrke, P. Seshadri, Towards Sensor Database Systems, Lecture Notes in Computer Science, 2001, Springer Verlag 66