Data Storage selection in sensor networks
اسلاید 1: 1Report of Advanced Data Base Topics Project Instructor : Dr. rahgozareuhanna ghadimi, Ali abbasi , kave pashaiiData Storage selection in sensor networks
اسلاید 2: 2Outline1. IntroductionDefinition, Applications, Differences, Storage2. Queries2.1. Querying in Cougar2.2. Querying in TinyDB2.3. In-network Aggregation3. Other Issues
اسلاید 3: 3Introduction 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
اسلاید 4: 4Disaster ResponseCirculatory NetEmbed numerous distributed devices to monitor and interact with physical world: in work-spaces, hospitals, homes, vehicles, and “the environment” (water, soil, air…)Network these devices so that they can coordinate to perform higher-level tasks.Requires robust distributed systems of tens of thousands of devices.The long term goal
اسلاید 5: 5Sensor Net Sample AppsTraditional monitoring apparatus.Earthquake monitoring in shake-test sites.Vehicle detection: sensors along a road, collect data about passing vehicles.Habitat Monitoring: Storm petrels on Great Duck Island, microclimates on James Reserve.
اسلاید 6: 6Overview of researchSensor network challengesOne 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)
اسلاید 7: 7The Challenge is Dynamics!The physical world is dynamic Dynamic operating conditionsDynamic availability of resources… particularly energy!Dynamic tasksDevices must adapt automatically to the environmentToo many devices for manual configurationEnvironmental conditions are unpredictableUnattended and un-tethered operation is key to many applications
اسلاید 8: 8ApproachEnergy is the bottleneck resourceAnd communication is a major consumer--avoid communication over long distancesPre-configuration and global knowledge are not applicableAchieve desired global behavior through localized interactions Empirically adapt to observed environmentLeverage pointsSmall-form-factor nodes, densely distributed to achieve Physical locality to sensed phenomenaApplication-specific, data-centric networksData processing/aggregation inside the network
اسلاید 9: 9Directed Diffusion ConceptsApplication-aware communication primitivesexpressed in terms of named data (not in terms of the nodes generating or requesting data) Consumer of data initiates interest in data with certain attributesNodes diffuse the interest towards producers via a sequence of local interactionsThis process sets up gradients in the network which channel the delivery of dataReinforcement and negative reinforcement used to converge to efficient distributionIntermediate nodes opportunistically fuse interests, aggregate, correlate or cache data
اسلاید 10: 10Illustrating Directed DiffusionSinkSourceSetting up gradientsSinkSourceSending dataSinkSourceRecoveringfrom node failureSinkSourceReinforcingstable path
اسلاید 11: 11Sensor Network Tomography: Key Ideas and ChallengesKinds of tomogramsnetwork healthresource-level indicatorsresponses to external stimuliCan exchange resource health during low-level housekeeping functions… such as radio synchronizationKey challenge: energy-efficiencyneed to aggregate local representationsalgorithms must auto-scaleoutlier indicators are different
اسلاید 12: 12Self configuring networks using and supporting robotic nodes (Bulusu, Cerpa, Estrin, Heidemann, Mataric, Sukhatme)Robotics introduces self-mobile nodes and adaptively placed nodesSelf configuring ad hoc networks in the context of unpredictable RF environmentPlace nodes for network augmentation or formationPlace beacons for localization granularity
اسلاید 13: 13Programming Sensor Nets Is HardMonths of lifetime required from small batteries3-5 days naively; can’t recharge oftenInterleave sleep with processingLossy, low-bandwidth, short range communicationNodes coming and going~20% loss @ 5mMulti-hopRemote, zero administration deploymentsHighly distributed environmentLimited Development ToolsEmbedded, LEDs for Debugging!Need high level abstractions!200-800 instructions per bit transmitted!High-Level Abstraction Is Needed!
اسلاید 14: 14A Solution: Declarative QueriesUsers specify the data they wantSimple, SQL-like queriesUsing predicates, not specific addressesSame spirit as Cougar – Our system: TinyDBChallenge is to provide:Expressive & easy-to-use interfaceHigh-level operatorsWell-defined interactions“Transparent Optimizations” that many programmers would missSensor-net specific techniquesPower efficient execution frameworkQuestion: do sensor networks change query processing?Yes!
اسلاید 15: 15OverviewTinyDB: Queries for Sensor NetsProcessing Aggregate Queries (TAG)Taxonomy & ExperimentsAcquisitional Query ProcessingOther Research Future Directions
اسلاید 16: 16OverviewTinyDB: Queries for Sensor NetsProcessing Aggregate Queries (TAG)Taxonomy & ExperimentsAcquisitional Query ProcessingOther Research Future Directions
اسلاید 17: 17TinyDB Demo
اسلاید 18: 18TinyOSSchemaQuery ProcessorMultihop NetworkTinyDB ArchitectureSchema:“Catalog” of commands & attributesFilterlight > 400get (‘temp’)Aggavg(temp)QueriesSELECT AVG(temp) WHERE light > 400ResultsT:1, AVG: 225T:2, AVG: 250TablesSamplesgot(‘temp’)Name: tempTime to sample: 50 uSCost to sample: 90 uJCalibration Table: 3Units: Deg. FError: ± 5 Deg FGet f : getTempFunc()…getTempFunc(…)TinyDB~10,000 Lines Embedded C Code~5,000 Lines (PC-Side) Java~3200 Bytes RAM (w/ 768 byte heap)~58 kB compiled code(3x larger than 2nd largest TinyOS Program)
اسلاید 19: 19Declarative Queries for Sensor NetworksExamples:SELECT nodeid, nestNo, lightFROM sensorsWHERE light > 400EPOCH DURATION 1s1EpochNodeidnestNoLight0117455022538911174221225405Sensors“Find the sensors in bright nests.”
اسلاید 20: 20Aggregation QueriesEpochregionCNT(…)AVG(…)0North33600South35201North33701South3520“Count the number occupied nests in each loud region of the island.”SELECT region, CNT(occupied) AVG(sound)FROM sensorsGROUP BY regionHAVING AVG(sound) > 200EPOCH DURATION 10s3Regions w/ AVG(sound) > 200SELECT AVG(sound)FROM sensorsEPOCH DURATION 10s2
اسلاید 21: 21OverviewTinyDB: Queries for Sensor NetsProcessing Aggregate Queries (TAG)Taxonomy & ExperimentsAcquisitional Query ProcessingOther Research Future Directions
اسلاید 22: 22Tiny Aggregation (TAG)In-network processing of aggregatesCommon data analysis operationAka gather operation or reduction in || programmingCommunication reducingOperator dependent benefitAcross nodes during same epochExploit query semantics to improve efficiency!
اسلاید 23: 23Query Propagation Via Tree-Based RoutingTree-based routingUsed in:Query delivery Data collectionTopology selection is important; e.g.Krishnamachari, DEBS 2002, Intanagonwiwat, ICDCS 2002, Heidemann, SOSP 2001LEACH/SPIN, Heinzelman et al. MOBICOM 99SIGMOD 2003Continuous processMitigates failuresABCDFEQ:SELECT …QQQQQQQQQQQQR:{…}R:{…}R:{…}R:{…}R:{…}
اسلاید 24: 24Basic AggregationIn each epoch:Each node samples local sensors onceGenerates partial state record (PSR)local readings readings from children Outputs PSR during assigned comm. intervalAt end of epoch, PSR for whole network output at rootNew result on each successive epochExtras:Predicate-based partitioning via GROUP BY12345
اسلاید 25: 25Illustration: Aggregation12345413214123451Sensor #Interval #Interval 4SELECT COUNT(*) FROM sensorsEpoch
اسلاید 26: 26Illustration: Aggregation123454132214123452Sensor #Interval 3SELECT COUNT(*) FROM sensorsInterval #
اسلاید 27: 27Illustration: Aggregation123454132213141234531Sensor #Interval 2SELECT COUNT(*) FROM sensorsInterval #
اسلاید 28: 28Illustration: Aggregation123454132213154123455Sensor #SELECT COUNT(*) FROM sensorsInterval 1Interval #
اسلاید 29: 29Illustration: Aggregation1234541322131541123451Sensor #SELECT COUNT(*) FROM sensorsInterval 4Interval #
اسلاید 30: 30Interval Assignment: An Approach12345SELECT COUNT(*)…4 intervals / epochInterval # = Level43Level = 12EpochComm Interval432155ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZLTLTLTTLTLLPipelining: Increase throughput by delaying result arrival until a later epochMadden, Szewczyk, Franklin, Culler. Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks. WMCSA 2002.CSMA for collision avoidanceTime intervals for power conservationMany variations(e.g. Yao & Gehrke, CIDR 2003)Time Sync (e.g. Elson & Estrin OSDI 2002)
اسلاید 31: 31Aggregation FrameworkAs in extensible databases, we support any aggregation function conforming to:Aggn={finit, fmerge, fevaluate}Finit {a0} <a0>Fmerge {<a1>,<a2>} <a12>Fevaluate {<a1>} aggregate valueExample: AverageAVGinit {v} <v,1>AVGmerge {<S1, C1>, <S2, C2>} < S1 + S2 , C1 + C2>AVGevaluate{<S, C>} S/CPartial State Record (PSR)Restriction: Merge associative, commutative
اسلاید 32: 32Types of AggregatesSQL supports MIN, MAX, SUM, COUNT, AVERAGEAny function over a set can be computed via TAGIn network benefit for many operationsE.g. Standard deviation, top/bottom N, spatial union/intersection, histograms, etc. Compactness of PSR
اسلاید 33: 33OverviewTinyDB: Queries for Sensor NetsProcessing Aggregate Queries (TAG)Taxonomy & ExperimentsAcquisitional Query ProcessingOther ResearchFuture Directions
اسلاید 34: 34Simulation EnvironmentEvaluated TAG via simulationCoarse grained event based simulatorSensors arranged on a gridTwo communication modelsLossless: All neighbors hear all messagesLossy: Messages lost with probability that increases with distanceCommunication (message counts) as performance metric
اسلاید 35: 35Taxonomy of AggregatesTAG insight: classify aggregates according to various functional propertiesYields a general set of optimizations that can automatically be appliedPropertiesPartial StateMonotonicityExemplary vs. SummaryDuplicate SensitivityDrives an API!
اسلاید 36: 36Partial StateGrowth of PSR vs. number of aggregated values (n) Algebraic: |PSR| = 1 (e.g. MIN)Distributive: |PSR| = c (e.g. AVG)Holistic: |PSR| = n (e.g. MEDIAN)Unique: |PSR| = d (e.g. COUNT DISTINCT)d = # of distinct valuesContent Sensitive: |PSR| < n (e.g. HISTOGRAM)PropertyExamplesAffectsPartial StateMEDIAN : unbounded,MAX : 1 recordEffectiveness of TAG“Data Cube”, Gray et. al
اسلاید 37: 37Benefit of In-Network ProcessingSimulation Results2500 Nodes50x50 GridDepth = ~10Neighbors = ~20Uniform Dist.Aggregate & depth dependent benefit!HolisticUniqueDistributiveAlgebraic
اسلاید 38: 38Monotonicity & Exemplary vs. SummaryPropertyExamplesAffectsPartial StateMEDIAN : unbounded, MAX : 1 recordEffectiveness of TAGMonotonicityCOUNT : monotonicAVG : non-monotonicHypothesis Testing, SnoopingExemplary vs. SummaryMAX : exemplaryCOUNT: summaryApplicability of Sampling, Effect of Loss
اسلاید 39: 39Channel Sharing (“Snooping”)Insight: Shared channel can reduce communicationSuppress messages that won’t affect aggregateE.g., MAXApplies to all exemplary, monotonic aggregates Only snoop in listen/transmit slotsFuture work: explore snooping/listening tradeoffs
اسلاید 40: 40Hypothesis TestingInsight: Guess from root can be used for suppressionE.g. ‘MIN < 50’Works for monotonic & exemplary aggregatesAlso summary, if imprecision allowedHow is hypothesis computed?Blind or statistically informed guessObservation over network subset
اسلاید 41: 41Experiment: Snooping vs. Hypothesis TestingUniform Value DistributionDense Packing Ideal CommunicationPruning in NetworkPruning at Leaves
اسلاید 42: 42Duplicate SensitivityPropertyExamplesAffectsPartial StateMEDIAN : unbounded, MAX : 1 recordEffectiveness of TAGMonotonicityCOUNT : monotonicAVG : non-monotonicHypothesis Testing, SnoopingExemplary vs. SummaryMAX : exemplaryCOUNT: summaryApplicability of Sampling, Effect of LossDuplicate SensitivityMIN : dup. insensitive,AVG : dup. sensitiveRouting Redundancy
اسلاید 43: 43Use Multiple ParentsUse graph structure Increase delivery probability with no communication overheadFor duplicate insensitive aggregates, orAggs expressible as sum of partsSend (part of) aggregate to all parentsIn just one message, via multicastAssuming independence, decreases varianceSELECT COUNT(*)ABCRABCcRP(link xmit successful) = pP(success from A->R) = p2E(cnt) = c * p2Var(cnt) = c2 * p2 * (1 – p2) V# of parents = nE(cnt) = n * (c/n * p2)Var(cnt) = n * (c/n)2 * p2 * (1 – p2) = V/nABCc/nc/nRn = 2
اسلاید 44: 44Multiple Parents ResultsBetter than previous analysis expected!Losses aren’t independent!Insight: spreads data over many linksCritical Link!No SplittingWith Splitting
اسلاید 45: 45Taxonomy Related InsightsCommunication ReducingIn-network Aggregation (Partial State)Hypothesis Testing (Exemplary & Monotonic)Snooping (Exemplary & Monotonic)SamplingQuality IncreasingMultiple Parents (Duplicate Insensitive)Child Cache
اسلاید 46: 46TAG ContributionsSimple but powerful data collection languageVehicle tracking: SELECT ONEMAX(mag,nodeid)EPOCH DURATION 50msDistributed algorithm for in-network aggregationCommunication ReducingPower AwareIntegration of sleeping, computationPredicate-based groupingTaxonomy driven API Enables transparent application of techniques toImprove quality (parent splitting)Reduce communication (snooping, hypo. testing)
اسلاید 47: 47OverviewTinyDB: Queries for Sensor NetsProcessing Aggregate Queries (TAG)Taxonomy & ExperimentsAcquisitional Query ProcessingOther Research Future Directions
اسلاید 48: 48Acquisitional Query Processing (ACQP)Closed world assumption does not holdCould generate an infinite number of samplesAn acqusitional query processor controls when, where, and with what frequency data is collected!Versus traditional systems where data is provided a prioriMadden, Franklin, Hellerstein, and Hong. The Design of An Acqusitional Query Processor. SIGMOD, 2003
اسلاید 49: 49ACQP: What’s Different?How should the query be processed?Sampling as a first class operationEvent – join dualityHow does the user control acquisition?Rates or lifetimesEvent-based triggersWhich nodes have relevant data?Index-like data structuresWhich samples should be transmitted?Prioritization, summary, and rate control
اسلاید 50: 50 E(sampling mag) >> E(sampling light)1500 uJ vs. 90 uJOperator Ordering: Interleave Sampling + SelectionSELECT light, magFROM sensorsWHERE pred1(mag)AND pred2(light)EPOCH DURATION 1s(pred1)(pred2)maglight(pred1)(pred2)maglight(pred1)(pred2)maglightTraditional DBMSACQPAt 1 sample / sec, total power savings could be as much as 3.5mW Comparable to processor!Correct ordering(unless pred1 is very selective and pred2 is not):CheapCostly
اسلاید 51: 51Exemplary Aggregate PushdownSELECT WINMAX(light,8s,8s)FROM sensorsWHERE mag > xEPOCH DURATION 1sNovel, general pushdown techniqueMag sampling is the most expensive operation!WINMAX(mag>x)maglightTraditional DBMSlightmag(mag>x)WINMAX(light > MAX)ACQP
اسلاید 52: 52Lifetime QueriesLifetime vs. sample rateSELECT …EPOCH DURATION 10 sSELECT …LIFETIME 30 daysExtra: Allow a MAX SAMPLE PERIODDiscard some samplesSampling cheaper than transmitting
اسلاید 53: 53(Single Node) Lifetime Prediction
اسلاید 54: 54OverviewTinyDB: Queries for Sensor NetsProcessing Aggregate Queries (TAG)Taxonomy & ExperimentsAcquisitional Query ProcessingOther ResearchFuture Directions
اسلاید 55: 55Sensor Network Challenge ProblemsTemporal aggregatesSophisticated, sensor network specific aggregatesIsobar FindingVehicle TrackingLossy compressionWaveletsHellerstein, Hong, Madden, and Stanek. Beyond Average. IPSN 2003“Isobar Finding”
اسلاید 56: 56TinyDB DeploymentsInitial efforts:Network monitoringVehicle trackingOngoing deployments:Environmental monitoring Generic Sensor KitBuilding MonitoringGolden Gate Bridge
اسلاید 57: 57Data StorageRecently IntroducedLarger capacity, larger battery powerUsual sensors send their data to itIt replies queries(sheng et. al ACM MobiHoc 2006)
اسلاید 58: 58Problems Data Storage Placement(Sheng et. al paper)Data Storage SelectionOur method : An adaptive and decentralized method
اسلاید 59: 59Costs in the system
اسلاید 60: 60Overall cost
اسلاید 61: 61Our method
اسلاید 62: 62Our method (Cont.)
اسلاید 63: 63Our resultsVery Good !!
اسلاید 64: 64ReferencesBook: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 In-Network Query Processing ,2003, springer verlag .
اسلاید 65: 65References(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.
اسلاید 66: 66References(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
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.