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