1Robust Aggregation in Sensor Robust Aggregation in Sensor NetworksNetworksJie GaoComputer Science DepartmentStony Brook University2PapersPapers• [Nath04] Suman Nath, Phillip B. Gibbons, Zachary Anderson, and Srinivasan Seshan, Synopsis Diffusion for Robust Aggregation in Sensor Networks". In proceedings of ACM SenSys'04.• [Broder02] A. Broder and M. Mitzenmacher, Network Applications of Bloom Filters: A Survey, Proceedings of the 40th Annual AllertonConference on Communication, Control, and Computing, pp. 636-646, 2002.3Aggregation tree in practiceAggregation tree in practice• Tree is a fragile structure.– If a link fails, the data from the entire subtreeis lost.• Fix #1: use a DAG instead of a tree.– Send 1/k data to each of the k upstream nodes (parents).– A link failure lose 1/k data1234561234564Aggregation tree in practiceAggregation tree in practicetreeDAGTrue value5Fundamental problemFundamental problem• Aggregation and routing are coupled• Improve routing robustness by multi-path routing?– Same data might be delivered multiple times.– Message over-counting.• Decouple routing & aggregation– Work on the robustness of each separately1234566Order and duplicate insensitive (ODI) Order and duplicate insensitive (ODI) synopsissynopsis• Aggregated value is insensitive to the sequence or duplication of input data.• Small-sizes digests such that any particular sensor reading is accounted for only once. – Example: MIN, MAX.– Challenge: how about COUNT, SUM?7Aggregation frameworkAggregation framework• Solution for robustness aggregation:– Robust routing (e.g., multi-hop) + ODI synopsis.• Leaf nodes: Synopsis generation: SG(⋅).• Internal nodes: Synopsis fusion: SF(⋅) takes two synopsis and generate a new synopsis of the union of input data. • Root node: Synopsis evaluation: SE(⋅) translates the synopsis to the final answer.8An easy example: ODI synopsis for An easy example: ODI synopsis for MAX/MINMAX/MIN• Synopsis generation: SG(⋅).– Output the value itself.• Synopsis fusion: SF(⋅) – Take the MAX/MIN of the two input values.• Synopsis evaluation: SE(⋅).– Output the synopsis.1234569Three questionsThree questions• What do we mean by ODI, rigorously?• Robust routing + ODI• How to design ODI synopsis?– COUNT– SUM– Sampling– Most popular k items– Set membership – Bloom filter10Definition of ODI correctnessDefinition of ODI correctness• A synopsis diffusion algorithm is ODI-correct if SF() and SG() are order and duplicate insensitive functions. • Or, if for any aggregation DAG, the resulting synopsis is identical to the synopsis produced by the canonical left-deep tree.• The final result is independent of the underlying routing topology.– Any evaluation order.– Any data duplication.11Definition of ODI correctnessDefinition of ODI correctnessConnection to streaming model: data item comes 1 by 1.12Test for ODI correctnessTest for ODI correctness1. SG() preserves duplicates: if two readings are duplicates (e.g., two nodes with same temperature readings), then the same synopsis is generated.2. SF() is commutative.3. SF() is associative.4. SF() is same-synopsis idempotent, SF(s, s)=s.Theorem: The above properties are sufficient and necessary properties for ODI-correctness.Proof idea: transfer an aggregation DAG to a left-deep tree with the same output by using these properties.13Proof of ODI correctnessProof of ODI correctness1. Start from the DAG. Duplicate a node with out-degree k to k nodes, each with out degree 1. duplicates preserving.14Proof of ODI correctnessProof of ODI correctness2. Re-order the leaf nodes by the increasing value of the synopsis.  Commutative.15Proof of ODI correctnessProof of ODI correctness3. Re-organize the tree s.t. adjacent leaves with the same value are input to a SF function. Associative.SFSF SGSFSGr1SG SGr2 r2r316Proof of ODI correctnessProof of ODI correctness4. Replace SF(s, s) by s.  same-synopsis idempotent.SFSF SGSFSGr1SG SGr2 r2r3SFSF SGSGr1SGr2r317Proof of ODI correctnessProof of ODI correctness5. Re-order the leaf nodes by the increasing canonical order.  Commutative.6. QED.18Design ODI synopsisDesign ODI synopsis• Recall that MAX/MIN are ODI.• Translate all the other aggregates (COUNT, SUM, etc.) by using MAX.• Let’s first do COUNT.• Idea: use probabilistic counting.• Counting distinct element in a multi-set. (Flajolet and Martin 1985).19Counting distinct elementsCounting distinct elements• Each sensor generates a sensor reading. Count the total number of different readings.• Counting distinct element in a multi-set. (Flajoletand Martin 1985).• Each element choose a random number i ∈ [1, k].• Pr{CT(x)=i} = 2-i, for 1ik-1. Pr{CT(x)=k}= 2-(k-1).• Use a pseudo-random generator so that CT(x) is a hash function (deterministic). 1 0 0 0 0 0½ ¼ 1/8 1/16 …..20Counting distinct elementsCounting distinct elements• Synopsis: a bit vector of length k>logn.• SG(): output a bit vector s of length k with CT(k)’s bit set.• SF(): bit-wise boolean ORof input s and s’.• SE(): if s is the lowest index that is still 0, output 2i-1/0.77351.• Intuition: i-th position will be 1 if there are 2inodes, each trying to set it with probability 1/2i1 0 0 0 0 00 1 0 0 0 0OR1 1 0 0 0 0i=321Distinct value counter analysisDistinct value counter analysis• Lemma: For i<logn-2loglogn, FM[i]=1 with high probability (asymptotically close to 1). For i ≥3/2logn+δ, with δ ≥ 0, FM[i]=0 with high probability.• The expected value of the first zero is log(0.7753n)+P(logn)+o(1), where P(u) is a periodic function of u with period 1 and amplitude bounded by 10-5. • The error bound (depending on variance) can be improved by using multiple copies or stochastic averaging.1 022Counting distinct elementsCounting distinct elements• Check the ODI-correctness:– Duplication: by the hash function. The same reading x generates the same value CT(x).– Boolean OR is commutative, associative, same-synopsis idempotent.• Total storage: O(logn) bits.1 0 0 0 0 00 1 0 0 0 0OR1 1 0 0 0 0i=323Robust routing + ODIRobust routing + ODI• Use Directed Acyclic Graph (DAG) to replace tree.• Rings overlay:– Query distribution: nodes in ring Rjare j hops from q.– Query aggregation: node in ring Rjwakes up in its allocated time slot and receives message from nodes in Rj+1.24Rings and adaptive ringsRings and adaptive rings• Adaptive rings: