1 15-744: Computer Networking L-13 Sensor Networks Sensor Networks • Directed Diffusion • Aggregation • Assigned reading • TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks • Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks 2 Outline • Sensor Networks • Directed Diffusion • TAG • Synopsis Diffusion 3 4 Smart-Dust/Motes • First introduced in late 90’s by groups at UCB/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 network2 5 Smart-Dust/Motes • Hardware • UCB motes • Programming • TinyOS • Query processing • TinyDB • Directed diffusion • Geographic hash tables • Power management • MAC protocols • Adaptive topologies • Devices that incorporate communications, processing, sensors, and batteries into a small package • Atmel microcontroller with sensors and a communication unit • RF transceiver, laser module, or a corner cube reflector • Temperature, light, humidity, pressure, 3 axis magnetometers, 3 axis accelerometers Berkeley Motes 6 7 Berkeley Motes (Levis & Culler, ASPLOS 02) Sensor Net Sample Apps 8 Traditional monitoring apparatus. Earthquake monitoring in shake-test sites. Vehicle detection: sensors along a road, collect data about passing vehicles. Habitat Monitoring: Storm petrels on great duck island, microclimates on James Reserve.3 9 Metric: Communication • Lifetime from one pair of AA batteries • 2-3 days at full power • 6 months at 2% duty cycle • Communication dominates cost • < few mS to compute • 30mS to send message 10 Communication In Sensor Nets • Radio communication has high link-level losses • typically about 20% @ 5m • Ad-hoc neighbor discovery • Tree-based routing A B C D F E Outline • Sensor Networks • Directed Diffusion • TAG • Synopsis Diffusion 11 The long term goal 12 Disaster Response Circulatory Net Network these devices so that they can coordinate to perform higher-level tasks."Requires robust distributed systems of tens of thousands of devices.!4 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? 13 Directed 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, and queries 14 Motivating Example • Sensor nodes are monitoring a flat space for animals • We are interested in receiving data for all 4-legged creatures seen in a rectangle • We want to specify the data rate 15 Interest and Event Naming • Query/interest: 1. Type=four-legged animal 2. Interval=20ms (event data rate) 3. Duration=10 seconds (time to cache) 4. Rect=[-100, 100, 200, 400] • Reply: 1. Type=four-legged animal 2. Instance = elephant 3. Location = [125, 220] 4. Intensity = 0.6 5. Confidence = 0.85 6. Timestamp = 01:20:40 • Attribute-Value pairs, no advanced naming scheme 165 Diffusion (High Level) • Sinks broadcast interest to neighbors • Interests are cached by neighbors • Gradients are set up pointing back to where interests came from at low data rate • Once a sensor receives an interest, it routes measurements along gradients 17 18 Illustrating Directed Diffusion Sink Source Setting up gradients Sink Source Sending data Sink Source Recovering from node failure Sink Source Reinforcing stable path Summary • 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 may make it more viable than ad-hoc routing in sensor networks 19 Outline • Sensor Networks • Directed Diffusion • TAG • Synopsis Diffusion 206 TAG Introduction • Programming sensor nets is hard! • Declarative queries are easy • Tiny Aggregation (TAG): In-network processing 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 2 students • Vehicle tracking query: took 2 minutes to write, worked just as well! 21 SELECT MAX(mag) FROM sensors WHERE mag > thresh EPOCH DURATION 64ms Basic 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 whole network output at root • (In paper: pipelining, grouping) 22 1!2! 3!4!5!23 Illustration: Aggregation 1 2 3 4 5 1 1 2 3 4 1 1!2!3!4!5!1 Sensor # Slot # Slot 1 SELECT COUNT(*) FROM sensors 24 Illustration: Aggregation 1 2 3 4 5 1 1 2 2 3 4 1 1!2!3!4!5!2 Sensor # Slot # Slot 2 SELECT COUNT(*) FROM sensors7 25 Illustration: Aggregation 1 2 3 4 5 1 1 2 2 3 1 3 4 1 1!2!3!4!5!3 1 Sensor # Slot # Slot 3 SELECT COUNT(*) FROM sensors 26 Illustration: Aggregation 1 2 3 4 5 1 1 2 2 3 1 3 4 5 1 1!2!3!4!5!5 Sensor # Slot # Slot 4 SELECT COUNT(*) FROM sensors 27 Illustration: Aggregation 1 2 3 4 5 1 1 2 2 3 1 3 4 5 1 1 1!2!3!4!5!1 Sensor # Slot # Slot 1 SELECT COUNT(*) FROM sensors 28 Types of Aggregates • SQL supports
View Full Document
Unlocking...