Robust Aggregation in Sensor Networks Jie Gao Computer Science Department Stony Brook University 1 Papers 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 Allerton Conference on Communication Control and Computing pp 636 646 2002 2 Aggregation tree in practice Tree is a fragile structure If a link fails the data from the entire subtree is lost Fix 1 use a DAG instead of a tree Send 1 k data to each of the k upstream nodes parents 1 1 A link failure lose 1 k data 2 3 2 4 6 3 4 5 6 5 3 Aggregation tree in practice tree DAG True value 4 Fundamental problem Aggregation and routing are coupled Improve routing robustness by multipath routing Same data might be delivered multiple times 1 Message over counting Decouple routing aggregation Work on the robustness of each separately 2 3 4 6 5 5 Order and duplicate insensitive ODI synopsis 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 6 Aggregation 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 7 An easy example ODI synopsis for MAX MIN Synopsis generation SG Output the value itself Synopsis fusion SF 1 2 4 Synopsis evaluation SE 3 Take the MAX MIN of the two input values Output the synopsis 6 5 8 Three 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 filter 9 Definition 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 10 Definition of ODI correctness Connection to streaming model data item comes 1 by 1 11 Test for ODI correctness 1 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 12 Proof of ODI correctness 1 Start from the DAG Duplicate a node with outdegree k to k nodes each with out degree 1 duplicates preserving 13 Proof of ODI correctness 2 Re order the leaf nodes by the increasing value of the synopsis Commutative 14 Proof of ODI correctness 3 Re organize the tree s t adjacent leaves with the same value are input to a SF function Associative SF SF SG r3 SG SF r1 SG SG r2 r2 15 Proof of ODI correctness 4 Replace SF s s by s same synopsis idempotent SF SF SF SG SF SG r3 SG SF r1 SG SG r2 r2 r3 SG SG r1 r2 16 Proof of ODI correctness 5 6 Re order the leaf nodes by the increasing canonical order Commutative QED 17 Design 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 18 Counting distinct elements Each sensor generates a sensor reading Count the total number of different readings Counting distinct element in a multi set Flajolet and 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 19 Counting 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 OR of 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 2i nodes each trying to set it with probability 1 2i 1 0 0 0 0 0 OR 0 1 0 0 0 0 1 1 0 0 0 0 i 3 20 Distinct 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 1 0 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 21 Counting 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 1 0 0 0 0 0 OR 0 1 0 0 0 0 1 1 0 0 0 0 Total storage O logn bits i 3 22 Robust routing ODI Use Directed Acyclic Graph DAG to replace tree Rings overlay Query distribution nodes in ring Rj are j hops from q Query aggregation node in ring Rj wakes up in its allocated time slot and receives message from nodes in Rj 1 23 Rings and adaptive rings Adaptive rings cope with network dynamics node deletions and insertions etc Each node on ring j monitor the success rate of its parents on ring j 1 If the success rate is low the node connects to other node whose transmission is overhead a lot Nodes at ring 1 may transmit multiple times to ensure robustness 24 Implicit acknowledgement Explicit acknowledgement 3 way handshake Used for wired networks u v Implicit acknowledgement Used on ad hoc wireless networks Node u sending to v snoops the subsequent broadcast from v to see if v indeed forwards the message for u Explores broadcast property saves energy With aggregation this is problematic Say u sends value x to v and subsequently hears value z U does not know whether or not x is incorporated into z 25 Implicit acknowledgement ODI synopsis enables efficient implicit acknowledgement U sends to v synopsis x Afterwards u hears that v transmitting synopsis z U verifies whether SF x z z u v 26 Error of …