CS 268: Computer NetworkingL-13 Sensor NetworksSensor Networks• Directed Diffusion• Aggregation• Assigned reading• TAG: a Tiny AGgregation Service for Ad-HocSensor Networks• Directed Diffusion: A Scalable and RobustCommunication Paradigm for Sensor Networks2Outline• Sensor Networks• Directed Diffusion• TAG• Synopsis Diffusion34Smart-Dust/Motes• First introduced in late 90’s by groups atUCB/UCLA/USC• Published at Mobicom/SOSP conferences• Small, resource limited devices• CPU, disk, power, bandwidth, etc.• Simple scalar sensors – temperature, motion• Single domain of deployment (e.g. farm, battlefield,etc.) for a targeted task (find the tanks)• Ad-hoc wireless network5Smart-Dust/Motes• Hardware• UCB motes• Programming• TinyOS• Query processing• TinyDB• Directed diffusion• Geographic hash tables• Power management• MAC protocols• Adaptive topologies• Devices that incorporatecommunications,processing, sensors, andbatteries into a smallpackage• Atmel microcontroller withsensors and acommunication unit• RF transceiver, lasermodule, or a corner cubereflector• Temperature, light,humidity, pressure, 3 axismagnetometers, 3 axisaccelerometersBerkeley Motes67Berkeley Motes (Levis & Culler, ASPLOS 02)Sensor Net Sample Apps8Traditional monitoringapparatus.Earthquake monitoring in shake-test sites.Vehicle detection: sensors along aroad, collect data about passingvehicles.Habitat Monitoring: Stormpetrels on great duck island,microclimates on JamesReserve.9Metric: Communication• Lifetime from one pairof AA batteries• 2-3 days at full power• 6 months at 2% dutycycle• Communicationdominates cost• < few mS to compute• 30mS to sendmessageTime v. Current Draw During Query Processing051015200 0.5 1 1.5 2 2.5 3Time (s)Current (mA)SnoozingProcessingProcessingand ListeningTransmitting10Communication In Sensor Nets• Radio communicationhas high link-levellosses• typically about 20% @5m• Ad-hoc neighbordiscovery• Tree-based routingABCDFEOutline• Sensor Networks• Directed Diffusion• TAG• Synopsis Diffusion11The long term goal12Disaster ResponseCirculatory NetEmbedEmbed numerous distributeddevices to monitor and interactwith physical world: in work-spaces, hospitals, homes,vehicles, and “the environment”(water, soil, air…)Network these devices sothat they can coordinate toperform higher-level tasks.Requires robust distributedsystems of tens of thousandsof devices.Motivation• Properties of Sensor Networks• Data centric, but not node centric• Have no notion of central authority• Are often resource constrained• Nodes are tied to physical locations, but:• They may not know the topology• They may fail or move arbitrarily• Problem: How can we get data from the sensors?13Directed Diffusion• Data centric – nodes are unimportant• Request driven:• Sinks place requests as interests• Sources are eventually found and satisfy interests• Intermediate nodes route data toward sinks• Localized repair and reinforcement• Multi-path delivery for multiple sources, sinks, andqueries14Motivating Example• Sensor nodes are monitoring a flat spacefor animals• We are interested in receiving data for all 4-legged creatures seen in a rectangle• We want to specify the data rate15Interest and Event Naming• Query/interest:• Type=four-legged animal• Interval=20ms (event data rate)• Duration=10 seconds (time to cache)• Rect=[-100, 100, 200, 400]• Reply:• Type=four-legged animal• Instance = elephant• Location = [125, 220]• Intensity = 0.6• Confidence = 0.85• Timestamp = 01:20:40• Attribute-Value pairs, no advanced namingscheme16Diffusion (High Level)• Sinks broadcast interest to neighbors• Interests are cached by neighbors• Gradients are set up pointing back to whereinterests came from at low data rate• Once a sensor receives an interest, itroutes measurements along gradients1718Illustrating Directed DiffusionSinkSourceSetting up gradientsSinkSourceSending dataSinkSourceRecoveringfrom node failureSinkSourceReinforcingstable pathSummary• Data Centric• Sensors net is queried for specific data• Source of data is irrelevant• No sensor-specific query• Application Specific• In-sensor processing to reduce data transmitted• In-sensor caching• Localized Algorithms• Maintain minimum local connectivity – save energy• Achieve global objective through local coordination• Its gains due to aggregation and duplicate suppression maymake it more viable than ad-hoc routing in sensor networks19Outline• Sensor Networks• Directed Diffusion• TAG• Synopsis Diffusion20TAG Introduction• Programming sensor nets is hard!• Declarative queries are easy• Tiny Aggregation (TAG): In-networkprocessing via declarative queries• In-network processing of aggregates• Common data analysis operation• Communication reducing• Operator dependent benefit• Across nodes during same epoch• Exploit semantics improve efficiency!• Example:• Vehicle tracking application: 2 weeks for 2students• Vehicle tracking query: took 2 minutes towrite, worked just as well!21SELECT MAX(mag)FROM sensorsWHERE mag > threshEPOCH DURATION 64msBasic Aggregation• In each epoch:• Each node samples local sensors once• Generates partial state record (PSR)• local readings• readings from children• Outputs PSR during its comm. slot.• At end of epoch, PSR for wholenetwork output at root• (In paper: pipelining, grouping)2212 34523Illustration: Aggregation1 2 3 4 51 12341123451Sensor #Slot #Slot 1SELECT COUNT(*)FROM sensors24Illustration: Aggregation1 2 3 4 51 12 2341123452Sensor #Slot #Slot 2SELECT COUNT(*)FROM sensors25Illustration: Aggregation1 2 3 4 51 12 23 1 3411234531Sensor #Slot #Slot 3SELECT COUNT(*)FROM sensors26Illustration: Aggregation1 2 3 4 51 12 23 1 34 51123455Sensor #Slot #Slot 4SELECT COUNT(*)FROM sensors27Illustration: Aggregation1 2 3 4 51 12 23 1 34 51 1123451Sensor #Slot #Slot 1SELECT COUNT(*)FROM sensors28Types of Aggregates• SQL supports MIN, MAX, SUM, COUNT,AVERAGE• Any function can be computed via TAG• In network benefit for many operations• E.g. Standard deviation, top/bottom N, spatialunion/intersection, histograms, etc.• Compactness of PSRTaxonomy of Aggregates• TAG insight: classify aggregates according tovarious functional properties• Yields a general set of optimizations that canautomatically be applied29Property Examples
View Full Document
Unlocking...