Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Model-Driven Data Acquisition Model-Driven Data Acquisition in Sensor Networksin Sensor Networks- Amol Deshpande et al., VLDB ‘04- Amol Deshpande et al., VLDB ‘04Jisu OhMarch 20, 2006CS 580S Paper PresentationProblems Problems – Sensornet is not a database!– Sensornet is not a database! Databases- complete, authoritative sources of information- Answer a query “CORRECTLY” based upon all the available data Sensornets- Misrepresentations of data :only samples acquired, not random:need to complement the sensornet readings- Inefficient approximate queries:Existing query processing from a completist’s approach is costlySolutions Solutions – Model-driven data acquisition– Model-driven data acquisitionUse a statistical model which maps the raw sensor readings onto physical reality - in order to robustly interpret sensor readings- and provide a framework for optimizing the acquisition of sensor readingsProposed approachesProposed approaches- Architecture- ArchitectureArchitecture for model-based querying in sensor networksProposed approaches (cont.)Proposed approaches (cont.)- Probability density function (pdf)- Probability density function (pdf)Probability density function (pdf)- Based on time-varying multivariate Gaussians- Estimates sensor readings in the current time period- Properties: correlation between different attributes: cost differential - Constraints: need historical data and training with themKey conceptsKey concepts – Probabilistic queries – Probabilistic queriesBBQ query processing (static probabilistic model)A user requests a range query that ask if an attribute Xi is in the range [ai, bi] with confidence (1-α)Marginalize a prior density (probability density function), p(Xi, …, Xn) to a density over only attribute Xi, p(xi)Compute P(Xi ∈[ai, bi]) = ∫ai bi p(xi)dxiAnswer true if p>1-α, false if p> αOtherwise, move on conditioning stepKey conceptsKey concepts – Probabilistic queries (cont.) – Probabilistic queries (cont.) BBQ query processing (conditioning)Acquire new sensor readings, o, a set of observationsMarginalize a posterior density (conditional probability density function), p(Xi, … Xj-1, Xj+1, … Xn | xj) to a density over only attribute Xj p(xj|o)Compute P(Xi ∈[ai, bi] | xj) = ∫ai, bi p(xi|o)dxiAnswer true if p>1-α, false if p> αKey conceptsKey concepts – Probabilistic queries (cont.) – Probabilistic queries (cont.) BBQ query processing (dynamic probabilistic model)describe the evolution of the system over timefor time evolved attributesuse transition model p(X1t+1, .. Xnt+1 | X1t .. Xnt) for conditioningmarginalize transition model then obtain p(X1t+1, .. Xnt+1 | O1…t)Key concepts (cont.)Key concepts (cont.)– Choosing on observation plan– Choosing on observation plan Choose a data acquisition plan for the sensornet to best refine the query anser. Cost(O) = Ca(O) + Ct(O) Ri(O), statistical benefit of acquiring a reading Minimize O ⊆{1, …, n} C(O), such that R(O) ≥ 1-αContributionContribution integrate a database system with a correlation-aware probabilistic model build the model from historical readings and improve it from current readings answer approximately SQL queries by consulting the model+ shield from faulty sensors+ reduce # expensive sensor readings+ reduce # radio transmissionsExperiment resultsExperiment resultsExperiment resultsExperiment resultsConclusionsConclusions Probabilistic model-driven data acquisition Help to provide approximations with probabilistic confidences, significantly more efficient to compute in both time and energy Strong assumptions and constraints- The model must be trained - based on static network topology- all sensor nodes are well
View Full Document