Trickle: Code Propagation andMaintenance in WirelessSensor NetworksPhilip LevisUC BerkeleyIntel BerkeleyScott ShenkerUC BerkeleyICIRNeil PatelUC BerkeleyDavid CullerUC BerkeleyIntel BerkeleyEmbedded Sensor Networks36m33m: 11132m: 11030m: 109,108,10720m: 106,105,10410m: 103, 102, 101Sensor Network BehaviorProblem Statement• Sensor network characteristics– Long lifetimes– Embedded and unreachable– Large numbers– Transient, lossy networks• Changes to running code are inevitable• Need to efficiently– Rapidly propagate new code into a network– Cheaply maintain a consistent code imageTrickle• Simple, “polite gossip” algorithm• “Every once in a while, broadcast what codeyou have, unless you’ve heard some othernodes broadcast the same thing.”• Behavior (simulation and deployment):– Scalability: thousand-fold density changes– Maintenance: a few sends per hour– Propagation: less than a minuteOutline• Problem statement• Trickle algorithm• Maintenance• Propagation• Future WorkTrickle Assumptions• Broadcast medium• Concise, comparable metadata• Metadata is the significant cost– 1 packet/minute for a day is 1440 messages– Equivalent to a 40K code image– Code will often be small: parameters, etc.Communication• As long as each mote communicates withone other, inconsistencies will be found• Transmission or reception• Maintain a lower communication bound overtime:• The closer to k, the better (efficiency)(receptions + transmissions) <= kTrickle Algorithm• Time interval of length t• Redundancy constant k (e.g., 1, 2)• Pick a time t from [0, t]• Maintain a counter c• At time t, transmit code metadata if c < k• Increment c when you hear identicalmetadata to your own• At end of t, pick a new tExample Trickle Execution, k = 1t1t2timet1t2tt1t2BCtransmissionsuppressed transmissionreceptionAOutline• Problem statement• Trickle algorithm• Maintenance• Propagation• Future WorkMaintenance Evaluation• Start with three assumptions, relax each– Lossless cell– Perfect synchronization– Single cell• Single, lossless, synchronized cell– k transmissions per interval– First k nodes to transmit suppress all others– Independent of density• In experiments (unless said otherwise), k =1Loss0246810121 2 4 8 16 32 64 128 256MotesTransmissions/Interval60%40%20%0%Logarithmic Behavior of Loss• Transmission increase is due to theprobability that one node has not heard ntransmissions• Example: 10% loss– 1 in 10 nodes will not hear one transmission– 1 in 100 nodes will not hear two transmissions– 1 in 1000 nodes will not hear three, etc.• Fundamental bound to maintaining per-interval communicationSynchronization024681012141 2 4 8 16 32 63 128 256MotesTransmissions/IntervalNot SynchronizedSynchronizedShort Listen Effect• Lack of synchronization leads to the “shortlisten effect”• For example, B transmits three times:ABCDTimetSolution• Add a listening period: t from [0.5t, t]Listen-only periodEffect of Listen Period024681012141 2 4 8 16 32 63 128 256MotesTransmissions/IntervalNot SynchronizedSynchronizedListeningMulti-Cell Case• TOSSIM simulation– No synchronization– Loss sampled from empirical models– Nodes uniformly distributed in 50’x50’ area• Logarithmic scaling holds02468101214161 2 4 8 16 32 64 128 256MotesTransmissions/IntervalHidden TerminalNo Hidden TerminalEmpirical ValidationEfficiency over Density00.20.40.60.811.21.41.61 2 4 8 16 32 64MotesEfficiencyEmpiricalSimulated• Redundancy:(transmissions + receptions)intervals- kOutline• Problem statement• Trickle algorithm• Maintenance• Propagation• Future WorkSpeeding Propagation• Adjust t: tl, th• When t expires, double t up to th• When you hear newer metadata, set t to tl• When you hear newer code, set t to tl• When you hear older metadata, send code– Blind transmission at 1, 3, and 7 seconds– Could use Trickle for suppression as wellRate Change Illustrationthtl2tlththHear Newer Metadata2TimeEmpirical Propagation• Deployed 19 nodes in office setting• Instrumented nodes for accurate timemeasurements• Introduce new code, log installation times• k=1, tl=1 second, th=1 minute• 40 test runsNetwork LayoutEmpirical ResultsPropagation Time Distribution0.00%5.00%10.00%15.00%20.00%25.00%30.00%35.00%0 5 10 15 20 25 30 35 40 45Time (seconds)MotesTime to Complete Propagation010203040506070Time (seconds)Conclusions• Trickle efficiency scales logarithmically withdensity• Can obtain rapid propagation with lowmaintenance– At most 3 sends/hour, propagates in 30 seconds• Uses beyond code propagation– Changes to data such as routing tables– E.g., predicates can scope distance• Further examination of tl, th and k neededQuestionsMulti-cell Case, Simulated02468101214161 2 4 8 16 32 64 128 256MotesTransmissions/IntervalHidden TerminalNo Hidden TerminalEmpirical Scaling• Nodes evenly spaced on a table• Very low signal strength for packet lossSimulated Propagation• TOSSIM, 20x20 node grid• Change spacing between nodes• k=1, tl=1 second, th=1 minuteTime To Reprogram, Tau, 5 Foot Spacing (seconds)16-1814-1612-1410-128-106-84-62-40-2TimeTime To Reprogram, Tau, 10 Foot Spacing (seconds)18-2016-1814-1612-1410-128-106-84-62-40-2TimeTime To Reprogram, Tau, 15 Foot Spacing (seconds)45-5040-4535-4030-3525-3020-2515-2010-155-100-5TimeTime To Reprogram, Tau, 20 Foot Spacing (seconds)56-6448-5640-4832-4024-3216-248-160-8Changing th to 20 minutes010203040506070Time (seconds)010203040506070Time (seconds)k=1
View Full Document
Unlocking...